RFR: 8297642: PhaseIdealLoop::only_has_infinite_loops must detect all loops that never lead to termination

[Tobias Hartmann]

On Fri, 2 Dec 2022 08:11:06 GMT, Emanuel Peter <epeter at openjdk.org> wrote:

> **Will hold this back until JDK21**, unless we decide it is a regression-fix for [JDK-8294217](https://bugs.openjdk.org/browse/JDK-8294217). The problem is only a not-quite-correct assert. But the problem is not limited to infinite loops, as the example below shows it can happen with reducible loops.
> 
> **Background:**
> We have an assert that checks that `has_loops` is true when it should be. If we have `has_loops == false` even though there are loops, we will not perform loop-opts in `Compile::Optimize`.
> 
> https://github.com/openjdk/jdk/blob/8c472e481676ed0ef475c4989477d5714880c59e/src/hotspot/share/opto/loopnode.cpp#L4285-L4293
> 
> Generally, we want to verify, that if we just found loops (`_ltree_root->_child != NULL`) that `has_loops == true`.
> There are a few cases where we do not care if we miss loop-opts:
> - We only have infinite loops (`only_has_infinite_loops()`). Infinite loops never terminate anyway, so why make them faster? Plus, a loop is only infinite if it has no loop-exit other than a `NeverBranch` exit, even uncommon traps, loop-limit checks etc are exits. Thus, if a loop does anything interesting, it probably is not such a "true infinite loop". They can be more easily forced to occur by setting `-XX:PerMethodTrapLimit=0`.
> - We have only exception edges.
> 
> Note that once we check the assert, we update `has_loops`. So if all loops disappeared, we avoid doing loop-opts henceforth.
> 
> **Current implementation of PhaseIdealLoop::only_has_infinite_loops**
> https://github.com/openjdk/jdk/blob/8c472e481676ed0ef475c4989477d5714880c59e/src/hotspot/share/opto/loopnode.cpp#L4183-L4185
> 
> We check for loop exits, if there is one the loop should not be infinite.
> 
> **The Problem**
> 
> An infinte loop can have an inner loop, that subsequently loses its exit. It becomes its own infinite loop, and floats out of the outer loop. Where the outer loop enters into the former inner loop, we now have a loop-exit for the outer loop. The next time we run `build_loop_tree` and check the assert, it can fail, as `PhaseIdealLoop::only_has_infinite_loops` finds that new loop-exit from outer to inner loop.
> 
> Example: `TestOnlyInfiniteLoops::test_simple` (click on images to see them larger)
> 
> Nested infinite loop before loop-opts:
> <img src="https://user-images.githubusercontent.com/32593061/205253771-1c226f53-bf54-456f-b396-5dc81d6e4170.png" width="300">
> 
> After `build_loop_tree`, the outer loop is detected as infinite, and `NeverBranch` is inserted. No loop is attached to loop-tree, as we do not attach newly discovered infinite loops. We will set `has_loops == false` after first loop-opts round.
> <img src="https://user-images.githubusercontent.com/32593061/205254671-5f35e158-5b98-44fb-adbe-4da301e399d6.png" width="300">
> 
> During IGVN of first loop-opts round, some edges die. `88 IfTrue` is dominated by `52 IfTrue` (dominator info only becomes present during loop-opts). The outer loop now exits into the inner loop.
> <img src="https://user-images.githubusercontent.com/32593061/205254685-6bfceb44-39b4-4bb2-a5da-c73970d5ef5d.png" width="300">
> 
> The second loop-opts round detects the former inner loop as an infinite loop, inserts NeverBranch. Once we run the assert, we see that we have `has_loops == false`, but `PhaseIdealLoop::only_has_infinite_loops` finds the former outer loop's exit.
> <img src="https://user-images.githubusercontent.com/32593061/205254694-3d5e42bd-b807-4f71-b732-edfeeaae5112.png" width="300">
> 
> **Solution**
> If we ever only have infinite loops, then there will never be a way to get from any of those loops down to Root, except through a NeverBranch exit. So even if such an (outer) infinite loop ever has an exit, that exit cannot ever lead to Root, other than a NeverBranch exit. Thus, it is ok to still consider that loop as "infinite", even though it itself has an exit - that exit will never lead to termination.
> Thus, I changed the `PhaseIdealLoop::only_has_infinite_loops`  to check if any of the loops ever connect down to Root, except through NeverBranch nodes.
> 
> **Alternative Fix**
> An alternative idea to my fix here: just replace the infinite loop with a uncommon trap, and if the infinite loop is ever hit revert back to the interpreter. If we do not care to optimize infinite loops, then why even compile them?
> Advantages of that idea: No need for `NeverBranch`, no need for special-casing infinite loops.
> 
> I have another bug where assumptions are not true, because of infinite loops, and especially infinite loops not being attached to the loop-tree [JDK-8296318](https://bugs.openjdk.org/browse/JDK-8296318)
> 
> I'm looking forward to your feedback,
> Emanuel

Nice summary. Looks good to me otherwise. @rwestrel should also have a look.

test/hotspot/jtreg/compiler/loopopts/TestOnlyInfiniteLoopsMain.java line 38:

> 36:  * @compile TestOnlyInfiniteLoops.jasm
> 37:  * @summary Nested irreducible loops, where the inner loop floats out of the outer
> 38:  * @run main/othervm -XX:+UnlockExperimentalVMOptions

`-XX:+UnlockExperimentalVMOptions` is not required in both `@run`, right?

test/hotspot/jtreg/compiler/loopopts/TestOnlyInfiniteLoopsMain.java line 40:

> 38:  * @run main/othervm -XX:+UnlockExperimentalVMOptions
> 39:  *      -XX:CompileCommand=compileonly,TestOnlyInfiniteLoops::test*
> 40:  *      -XX:-TieredCompilation -Xbatch -Xcomp

`-Xcomp` implies `-Xbatch`:
https://github.com/openjdk/jdk/blob/4458de95f845c036c1c8e28df7043e989beaee98/src/hotspot/share/runtime/arguments.cpp#L1445-L1447

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

Marked as reviewed by thartmann (Reviewer).

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