RFR: JDK-8287284: C2: loop optimization performs split_thru_phi infinitely many times [v6]

[Christian Hagedorn]

On Wed, 1 Nov 2023 09:05:16 GMT, Tobias Holenstein <tholenstein at openjdk.org> wrote:

>> ### Node* phi = PhaseIdealLoop::split_thru_phi(Node* n, Node* region, int policy) 
>> The function `PhaseIdealLoop::split_thru_phi` splits Node `n` through a merge point (phi) if there is enough "win". First a clone x<sub>i</sub> of `n` is created for each input of the merge point. The general idea is that we want to replace enough of the x<sub>i</sub> clones with existing nodes or constants. The `policy` indicates how many "wins" are needed for success. A "win" is defined as one of the following:
>> - Identity(x<sub>i</sub>) has singleton type (i.e. a constant)
>> - Identity(x<sub>i</sub>) returns an already existing node
>> - x<sub>i</sub> commons up with an existing node (i.e. hash_find(x<sub>i</sub> != null)
>> 
>> _Example_
>> Looking at the phi (119 Phi) of `n` (135 LoadI) a clone of `n` is created for each input to the phi: 
>> - x<sub>1</sub> (140 LoadI) for the input [1] (127 Phi)
>> - x<sub>2</sub> (141 LoadI) for the input [2] (90 StoreI)
>> 
>> If there are enough "wins" (win $\geq$ policy) the wins are applied and a new merge point `phi` (139 Phi) is returned. 
>> `n` (135 LoadI) is replaced with `phi` (139 Phi) outside of `PhaseIdealLoop::split_thru_phi` if successful.
>> 
>> Example with **n =** `135 LoadI`, **region =** `129 Loop`, **policy =** `1` returns **phi =** `139 Phi`
>> <img width="286" alt="split_phi" src="https://github.com/openjdk/jdk/assets/71546117/4a1bcd8d-bbfd-4267-9d2b-5ba4e057df72">
>> Success because 1 "win" occurs: `88 AddI` = Identity(`141 LoadI`)
>> <img width="186" alt="88_identity" src="https://github.com/openjdk/jdk/assets/71546117/af3cb37a-c575-445a-b8d4-967013dd3fb0">
>> 
>> 
>> 
>> ### run() has infinite loop of split_thru_phi
>> 
>> // java -Xbatch -XX:-PartialPeelLoop -XX:CompileCommand=compileonly,Test::run Test.java
>> 
>> public class Test {
>> 
>>     public static int cnt = 1;
>> 
>>     public static void run() {
>>         int j = 0;
>>         do {
>>             j = cnt;
>>             for (int k = 0; k < 20000; k++) {
>>                 cnt += 2;
>>             }
>> 
>>         } while (++j < 10);
>>     }
>> 
>>     public static void main(String[] args) {
>>         for (int i = 0; i < 10; i++ ) {
>>             run();
>>         }
>>     }
>> }
>> 
>> `Compile::optimize_loops` ends up in an endless loop when optimizing run().
>> In each `PhaseIdealLoop iteration` a `LoadI` (e.g. 135) is split through a `Phi` (e.g. 119) and the newly created `LoadI` (e.g. 140) is again split through a `Phi` (e.g. 127) creating an endless repeating pattern of `L...
>
> Tobias Holenstein has updated the pull request incrementally with one additional commit since the last revision:
> 
>   change can_move_to_inner_loop to take LoopNode

Nice summary! I agree to go with a simple solution.

I have a few minor comments, otherwise, looks good!

src/hotspot/share/opto/loopnode.hpp line 1739:

> 1737:   void update_addp_chain_base(Node* x, Node* old_base, Node* new_base);
> 1738: 
> 1739:   bool can_move_to_inner_loop(Node* n, LoopNode* region, Node* x);

Should match the signature in the cpp file:
Suggestion:

  bool can_move_to_inner_loop(Node* n, LoopNode* n_loop, Node* x);

src/hotspot/share/opto/loopopts.cpp line 158:

> 156:     phi->set_req( i, x );
> 157: 
> 158:     if (the_clone == nullptr) continue;

Nit: add braces
Suggestion:

    if (the_clone == nullptr) {
      continue;
    }

src/hotspot/share/opto/loopopts.cpp line 164:

> 162:     } else if (region->is_Loop() && i == LoopNode::LoopBackControl &&
> 163:                n->is_Load() && can_move_to_inner_loop(n, region->as_Loop(), x)) {
> 164:       // it is not a win if 'x' moved from an outer to an inner loop

Maybe you want to add a comment here why we only want to do it for loads.

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

Marked as reviewed by chagedorn (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/15536#pullrequestreview-1720267742
PR Review Comment: https://git.openjdk.org/jdk/pull/15536#discussion_r1386577570
PR Review Comment: https://git.openjdk.org/jdk/pull/15536#discussion_r1386571137
PR Review Comment: https://git.openjdk.org/jdk/pull/15536#discussion_r1386570304