RFR: 8280126: C2: detect and remove dead irreducible loops [v3]

[Emanuel Peter]

On Thu, 12 Jan 2023 23:37:44 GMT, Vladimir Kozlov <kvn at openjdk.org> wrote:

>> src/hotspot/share/ci/ciTypeFlow.cpp line 1876:
>> 
>>> 1874:   // while(condition) { break; } infinite_loop;
>>> 1875:   // Thus, we can understand lp as an outermost loop, and can terminate and
>>> 1876:   // conclude: this block is in no irreducible loop.
>> 
>> `lp->parent() == nullptr` is true for RootNode too I think. But I see that you have an other check for Root.
>> 
>> I am confusing about case like next case (pseudo code):
>> 
>> void foo() {
>>    if (condition2) goto A;
>>    while (condition) { // irreducible
>>       while (true) { ... } // infinite
>>       A : {...}
>>    }
>> }
>
> Also what about irreducible infinite loop?
> 
> void foo() {
>    if (condition2) goto A;
>    while (condition) { // irreducible
>       while (true) {  // infinite
>         A : {...}
>       }
>    }
> }

Yes, I check root separately, though you are correct, root also has `lp->parent() == nullptr`.
I thought handling the cases separately makes the algorithm more readable.

Thanks for the two examples. The **first** one can be reshaped to this:

void foo() {
   if (condition2) goto A;
   while (condition) { // irreducible
      goto B; // loop exit
      A : {...}
   }
   return;
   B: while (true) { ... } // infinite
}

Thus, the label `B` is actually a loop exit, and then we enter the infinite loop. This is my point: when you are nested in some outer loop, and then enter an inner infinite loop, this is like exiting from the outer loop, and then entering the infinite loop, which is now not an inner loop, but its own loop, directly attached at the root. Because you will never return back to the outer loop.

Actually, in your first example, the while loop was not actually a loop. There is no path from the head to the tail. We can thus rewrite the example like this:

void foo() {
   if (condition2) { A: {...} } // after A, we go to while-loop/if
   if (condition) { // used to be while
      goto B; // "loop exit"
      // never get here, so while becomes if
   }
   return;
   B: while (true) { ... } // infinite
}

This is basically how `build_loop_tree` would look at it.

For the **second** example:
The first thing is to notice that we never exit the inner while loop (infinite). Thus, we never take the backedge of the outer while-loop. Thus, the outer while-loop is not a loop, but just an if. Thus, all we have is an infinite irreducible loop, directly attached at the root.

void foo() {
   if (condition2) goto A;
   if (condition) { // used to be while
      while (true) {  // infinite
        A : {...}
      }
      // never get here, thus outer loop is not a loop after all
   }
}


An alternative transformation would have been to simply let the infinite loop float outside its original outer loop:

void foo() {
   if (condition2) goto A;
   while (condition) {
     goto B;
   }
   return;
   B:
   while (true) {  // infinite
     A : {...}
   }
}

We realize that `goto A` actually never leads into the "outer" while loop. Thus it is not an entry to it.

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

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