RFR: 8350864: C2: verify structural invariants of the Ideal graph

Thu Jul 17 08:48:35 UTC 2025

Some crashes are consequences of earlier misshaped ideal graphs, which could be detected earlier, closer to the source, before the possibly many transformations that lead to the crash.

Let's verify that the ideal graph is well-shaped earlier then! I propose here such a feature. This runs after IGVN, because at this point, the graph, should be cleaned up for any weirdness happening earlier or during IGVN.

This feature is enabled with the develop flag `VerifyIdealStructuralInvariants`. Open to renaming. No problem with me! This feature is only available in debug builds, and most of the code is even not compiled in product, since it uses some debug-only functions, such as `Node::dump` or `Node::Name`.

For now, only local checks are implemented: they are checks that only look at a node and its neighborhood, wherever it happens in the graph. Typically: under a `If` node, we have a `IfTrue` and a `IfFalse`. To ease development, each check is implemented in its own class, independently of the others. Nevertheless, one needs to do always the same kind of things: checking there is an output of such type, checking there is N inputs, that the k-th input has such type... To ease writing such checks, in a readable way, and in a less error-prone way than pile of copy-pasted code that manually traverse the graph, I propose a set of compositional helpers to write patterns that can be matched against the ideal graph. Since these patterns are... patterns, so not related to a specific graph, they can be allocated once and forever. When used, one provides the node (called center) around which one want to check if the pattern holds.

On top of making the description of pattern easier, these helpers allows nice printing in case of error, by showing the path from the center to the violating node. For instance (made up for the purpose of showing the formatting), a violation with a path climbing only inputs:

1 failure for node
 211  OuterStripMinedLoopEnd  === 215 39  [[ 212 198 ]] P=0,948966, C=23799,000000
At node
    209  CountedLoopEnd  === 182 208  [[ 210 197 ]] [lt] P=0,948966, C=23799,000000 !orig=[196] !jvms: StringLatin1::equals @ bci:12 (line 100)
  From path:
    [center] 211  OuterStripMinedLoopEnd  === 215 39  [[ 212 198 ]] P=0,948966, C=23799,000000
      <-(0)- 215  SafePoint  === 210 1 7 1 1 216 37 54 185  [[ 211 ]]  SafePoint  !orig=186 !jvms: StringLatin1::equals @ bci:29 (line 100)
      <-(0)- 210  IfFalse  === 209  [[ 215 216 ]] #0 !orig=198 !jvms: StringLatin1::equals @ bci:12 (line 100)
      <-(0)- 209  CountedLoopEnd  === 182 208  [[ 210 197 ]] [lt] P=0,948966, C=23799,000000 !orig=[196] !jvms: StringLatin1::equals @ bci:12 (line 100)
# OuterStripMinedLoopInvariants:
Unexpected type: CountedLoopEnd.

or with outputs:

1 failure for node
 413  OuterStripMinedLoopEnd  === 417 41  [[ 414 399 ]] P=0,960468, C=22887,000000
At node
    415  OuterStripMinedLoop  === 415 180 414  [[ 415 416 ]]
  From path:
    [center] 413  OuterStripMinedLoopEnd  === 417 41  [[ 414 399 ]] P=0,960468, C=22887,000000
         --> 414  IfTrue  === 413  [[ 415 ]] #1
         --> 415  OuterStripMinedLoop  === 415 180 414  [[ 415 416 ]]
# OuterStripMinedLoopInvariants:
Non-unique output of expected type. Found: 0.

So far a small set of checks are implemented:
- IfProjections: check that `If` nodes have a `IfTrue` and `IfFalse`
- PhiArity: check that `Phi` nodes have a `Region` node of the same arity as 0th input
- ControlSuccessor: check that control nodes have the right amount of successors (usually 1, but 2 for if-related nodes...)
- RegionSelfLoop: check that regions are either copy, or have a self loop as 0th input
- CountedLoopInvariants: check the structure around the backedge of a counted loop
- OuterStripMinedLoopInvariants: check the structure around `OuterStripMinedLoopEnd`
- MultiBranchNodeOut: check that for `MultiBranch`, `outcnt` is smaller than or equal to `required_outcnt` (it is legitimate to have a smaller number of output, especially after some optimizations).

Some of these checks have an additional subtlety: it's ok to have some wrong shape in dead code, for instance `IfProjections`. After a lot of investigation, it seems that some dead loops are not always detected eagerly and can make some control path survive longer, until being removed before loop opts. This seems to be by design to avoid traversing the whole graph everytime a region lose an input. It seems such misshape is harmless because they are not reachable from the inputs, and the cost of removing them would be prohibitive. To deal with such cases, when such a check fails, we check whether it happened in dead code. The dead of unreachable control nodes is lazily computed to answer that, and it's shared across checkers. While computing unreachable nodes is somewhat expensive, it seems to happen rarely in practice.

This verification has found [JDK-8359344](https://bugs.openjdk.org/browse/JDK-8359344) and [JDK-8359121](https://bugs.openjdk.org/browse/JDK-8359121). It has been run on tiers 1 to 3, plus some internal testing and, after fixing the above-mentioned, it seems all passing!

Related future: add more checks, should be easy.

Less related future: could we imagine using similar patterns (without the error reporting mechanism) to use for optimizations, instead of manual traversing? It could make the code clearer to understand. We could also imagine optionally using such things in idealization to declare which patterns nodes are looking for, and if they have depth greater than 1, automatically adapting the enqueuing strategy without having to pimp `PhaseIterGVN::add_users_of_use_to_worklist` everytime. Could at least cover some basic (but numerous) cases.

-------------

Commit messages:
 - Fix declaration
 - More comments
 - Improve printing and memory footprint
 - Improve printing
 - Handle NeverBranch in ControlSuccessor
 - Verify structural invariants

Changes: https://git.openjdk.org/jdk/pull/26362/files
  Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=26362&range=00
  Issue: https://bugs.openjdk.org/browse/JDK-8350864
  Stats: 728 lines in 5 files changed: 728 ins; 0 del; 0 mod
  Patch: https://git.openjdk.org/jdk/pull/26362.diff
  Fetch: git fetch https://git.openjdk.org/jdk.git pull/26362/head:pull/26362

PR: https://git.openjdk.org/jdk/pull/26362