RFR: 8348572: C2 compilation asserts due to unexpected irreducible loop [v2]

[Emanuel Peter]

On Mon, 3 Feb 2025 18:06:55 GMT, Vladimir Kozlov <kvn at openjdk.org> wrote:

>>> The issue is we should avoid creating new irreducible loops.
>> 
>> Absolutely. This is not a fix at all. But since we can catch that the state is wrong here, we should bail out instead of continuing on in production. That is at least a little improvement. The bug-fix would come in a second step, and may be much more complicated as it would have to reconsider what to do about `split_if`. Do we postpone until after loop-opts for example? Before considering such an involved fix, I would rather want to do this "defensive" patch first. Does that make sense? This also allows us to integrate [JDK-8348570](https://bugs.openjdk.org/browse/JDK-8348570), which is currently blocked by the failing assert (which is now disabled, but bailout instead, can be enabled with the flag).
>> 
>>> What if l is already marked as irreducible l->_irreducible = 1 by following code? I don't see check above for such case.
>> 
>> If `l->_irreducible = 1`, then the corresponding node should have been marked as `MaybeIrreducibleEntry`, and so should also `m` be marked with `MaybeIrreducibleEntry`. If that is the case, we are fine, these `Region` were created at parsing and we currently consider that fine.
>> 
>> But if one of the `Region` of the now irreducible loop was not marked accordingly already during parsing, then a new irreducible loop appeared during compilation - and that's not good.
>> 
>>> And again come here but secondary_entry can be irreducible (it is Region for example or already marked) and we skip bailout. Why it is okay?
>> 
>> If we marked a `Region` with `MaybeIrreducibleEntry`, then we treat it differently in some optimizations. For example, when the region loses a control input, we have to check if the loop is now dead, with a global connectivity search. For `LoopNode` losing the control input means we already know that the loop is dead, since that was the only loop entry. But for irreducible loops, losing one entry means we do not know if there is still a secondary entry or not. For context see [JDK-8280126](https://bugs.openjdk.org/browse/JDK-8280126).
>> 
>> Does that answer your question? If not, we may have to talk about it offline ;)
>> 
>> PS:
>> The whole irreducible loop handling is still broken actually, see [JDK-8308675](https://bugs.openjdk.org/browse/JDK-8308675). We plan to eventually also disallow creation of irreducible loops at parsing. But that's a big project, and we were hoping for a student project. But we still also should not introduce new irreducible loop...
>
> First, I am fine with this "band-aid" change. I understand that it simple replaces assert with bailout which is fine.
> But I am trying to understand what it does.
> 
> There are few states when we come to this part of code:
>  - `l` is or not marked as irreducible
>  - `m` is or not marked with MaybeIrreducibleEntry (is it set only for not Loop?)
>  - `m` is or not Loop 
>  
>  So we have 8 combinations. I would like to hear reasons in which cases we should bailout and in which not.

Yeah, the existing code is not exactly pretty or straight forward 😅 

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

Let me explain what we know when we get here, with `m` as `secondary_entry`:

`m`: the CFG node we are currently looking at in the DFS.

We know that `m` is located inside the `IdealLoopTree* l`.

But now we just found out that `l` is already `postvisited`, i.e. that we already walked all CFG nodes in `l` before, and exited back through its original loop entry node.

That means the traversal has left the `l` loop structure, and has now found a second way into that loop structure `l` at `m`. Hence, we know that `m` must be a secondary entry to `l`.

We now know that `l` must be irreducible, so we set `l->_irreducible = 1`.

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

This is the `LoopStatus` definition:

  enum LoopStatus {
    // No guarantee: the region may be an irreducible loop entry, thus we have to
    // be careful when removing entry control to it.
    MaybeIrreducibleEntry,
    // Limited guarantee: this region may be (nested) inside an irreducible loop,
    // but it will never be an irreducible loop entry.
    NeverIrreducibleEntry,
    // Strong guarantee: this region is not (nested) inside an irreducible loop.
    Reducible,
  };


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

Here about the combinations:

- I don't think that it matters if `l` is already marked `irreducible` or not.  For example if `m` is marked with `NeverIrreducibleEntry`, then `l` could be irreducible, i.e. have multiple entries. But `m` is not allowed to be one of those.
- For `m` we have 3 cases:
  - `MaybeIrreducibleEntry`: everything is ok, we expect that `m` could be a secondary entry to a loop.
  - `NeverIrreducibleEntry`: it would be ok if `l` is irreducible, but that should not happen through `m` as a secondary entry. An assumption was violated - the graph state is incoherent.
  - `Reducible`: Here we do not expect `l` to be irreducible, and `m` should not be a secondary entry either. An assumption was violated - the graph state is incoherent.

That is already sufficient to justify the bailout here.

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

But let me consider if `m` is a `Loop` or just `Region` anyway.

What if `m` is:
- NOT `LoopNode`, just `Region`: we just found a new edge entering `l`. This edge was not reachable from inside the loop structure `l`, and so it must be a secondary entry.
- `LoopNode`, it has an entry `in(1)` and a backedge `in(2)`:
  - Assume we just came via the backedge: that is contradictory, as the backedge should be reachable from inside the loop, and hence we should already have visited that edge before declaring `l` postvisited.
  - Assume we came via the entry: I suppose that looks ok at first....

But we only turn `Region` into `Loop` if we are sure it is not in an irreducible loop, so I think the assumption is that a `LoopNode` only has reducible CFG inside its loop structure. Look at `beautify_loops`:

After we know that the `Region` only has 2 entries, and the `l` is reducible:

  } else if (!_head->is_Loop() && !_irreducible) {
    // Make a new LoopNode to replace the old loop head
    Node *l = new LoopNode( _head->in(1), _head->in(2) );


Hence, if we found any secondary entry into a `LoopNode* m`, that would also be a contradiction.
I could be wrong about this, and again, I think it does not matter.
All that matters is that we already have a contradiction if `m` is not marked with `MaybeIrreducibleEntry`, as we saw above.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/23363#discussion_r1939891275