RFR: 8325746: Refactor Loop Unswitching code

Wed Feb 14 10:24:06 UTC 2024

On Wed, 14 Feb 2024 09:06:03 GMT, Christian Hagedorn <chagedorn at openjdk.org> wrote:

> To simplify the review of https://github.com/openjdk/jdk/pull/16877, I've decided to split off some code into separate sub-tasks.
> 
> This sub-task focuses on the code refactoring done in Loop Unswitching. I've incorporated the feedback from @eme64 at https://github.com/openjdk/jdk/pull/16877 in the proposed changes.
> 
> #### Changes
> - Adding a more detailed description about the Loop Unswitching optimization itself below the file header.
> - Renaming `fast loop` -> `true-path-loop` and `slow loop` -> `false-path-loop` since we don't really know which one is faster and to avoid keeping a mental map of which path goes into which unswitched loop version.
> - Creating new classes:
>   - `UnswitchedLoopSelector` to create the unswitched loop selector `If` (i.e. the If node that selects at runtime which unswitched loop version is executed) based on the invariant and non-loop-exiting unswitch candidate `If`.
>   - `OriginalLoop` to do the actual unswitching (i.e. loop cloning, predicates cloning and fixing the graph to the loop selector `If`).
> - Extracting methods in `do_unswitching()` to clean it up further.
> - Improving `TraceLoopUnswitching` result printing.
> - Adding some shared utility methods.
> 
> #### Possible Follow-Up RFEs
> There are possible follow-up opportunities to further improve the loop unswitching which, however, would go to far in the context of fixing Assertion Predicates. We could follow up with RFEs to tackle these:
> - At some point it might be good to have a dedicated `LoopUnswitching` class to split all the methods off from `PhaseIdealLoop`. This would also avoid noisy "loop_unswitching" prefixes.
> - Bailout code in `has_control_dependencies_from_predicates()` is too conservative. I have already some code to improve that in the full fix for Assertion Predicates which I plan to split off and propose separatly.
> - `TraceLoopUnswitching` currently only prints the result and if it failed. We might want to improve that in the future to cover more steps to make it useful for debugging (would require some more fine-grained debug levels, though).

Nice work! A first batch of comments.

src/hotspot/share/opto/ifnode.cpp line 461:

> 459:     return new IfNode(ctrl, bol, if_node_profile->_prob, if_node_profile->_fcnt);
> 460:   } else {
> 461:     return new RangeCheckNode(ctrl, bol, if_node_profile->_prob, if_node_profile->_fcnt);

Suggestion:

  } else {
    assert(if_node_profile->Opcode() == Op_RangeCheck, "only IfNode or RangeCheckNode expected");
    return new RangeCheckNode(ctrl, bol, if_node_profile->_prob, if_node_profile->_fcnt);

src/hotspot/share/opto/loopUnswitch.cpp line 37:

> 35: // This is done by duplicating the loop and placing the if-path in one unswitched loop version (i.e. the true-path-loop)
> 36: // and the else-path in the other (i.e. the false-path-loop). The invariant test only needs to be checked once and
> 37: // depending on the outcome, one or the other unswitched loop version is executed:

Suggestion:

// Loop Unswitching is a loop optimization to move an invariant, non-loop-exiting test in the loop body before the loop.
// For one loop execution, this test is either always true or always false. Hence, we duplicate the loop: the true-path-loop always takes the true-path and the false-path-loop always takes the false-path. We move the test
// before the loops, turning it into a loop selector. The true-proj leads to the true-path-loop, and the false-proj
// leads to the false-path-loop. Now the invariant test is only checked once before the loop, and decides which
// unswitched loop version is executed:

Make sure to be consistent. I think you use `if-path` and `if-block` as synonymes, right?
Btw: are these only blocks, as in basic blocks, and hence the if-statements are only such "basic diamonds", that only have one block per if-else side? Or could the CFG be more complex?

> placing the if-path in one unswitched loop version
That is a bit confusing. It sounds like you are taking the hoisted if-true-projection, and putting it inside a loop, which does not make sense.

later you name the hoisted if a "loop selector". We could already name it the same here.

src/hotspot/share/opto/loopUnswitch.cpp line 41:

> 39: //                                                                    [Initialized Assertion Predicates]
> 40: //                                                                                    |
> 41: //    [Predicates]                                                             if (invariant-test)

Suggestion:

//    [Predicates]                                                             if (invariant-test turned into loop selector)

src/hotspot/share/opto/loopUnswitch.cpp line 113:

> 111: }
> 112: 
> 113: // This class creates an If node (i.e. loop selector) that selects if the true-path- or the false-path-loop should be

Suggestion:

// This class creates an If node (i.e. loop selector) that selects if the true-path-loop or the false-path-loop should be

might as well

src/hotspot/share/opto/loopUnswitch.cpp line 130:

> 128:   UnswitchedLoopSelector(IdealLoopTree* loop)
> 129:       : _phase(loop->_phase),
> 130:         _outer_loop(loop->_head->as_Loop()->is_strip_mined() ? loop->_parent->_parent : loop->_parent),

Is there no utility method for this?
Hmm, maybe not on `IdealLoopTree` side.

But I do find other code like this:
`head->is_strip_mined() ? loop->_parent : loop`

Maybe you could make a utility method then: `IdealLoopTree::skip_strip_mined()`, just like the one for `LoopNode`.

src/hotspot/share/opto/loopUnswitch.cpp line 142:

> 140:   IfNode* find_unswitch_candidate(IdealLoopTree* loop) {
> 141:     IfNode* unswitch_candidate = _phase->find_unswitch_candidate(loop);
> 142:     assert(unswitch_candidate != nullptr, "must exist");

Suggestion:

    assert(unswitch_candidate != nullptr, "guaranteed to exist by policy_unswitching");

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

> 162:     } else {
> 163:       proj_to_loop = new IfFalseNode(_selector);
> 164:     }

Suggestion:

    IfProjNode* proj_to_loop = (path_to_loop == TRUE_PATH) ? new IfTrueNode(_selector)
                                                             new IfFalseNode(_selector);

A question of taste. Just an idea.

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

Changes requested by epeter (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/17842#pullrequestreview-1879764935
PR Review Comment: https://git.openjdk.org/jdk/pull/17842#discussion_r1489158457
PR Review Comment: https://git.openjdk.org/jdk/pull/17842#discussion_r1489180462
PR Review Comment: https://git.openjdk.org/jdk/pull/17842#discussion_r1489198116
PR Review Comment: https://git.openjdk.org/jdk/pull/17842#discussion_r1489199101
PR Review Comment: https://git.openjdk.org/jdk/pull/17842#discussion_r1489206413
PR Review Comment: https://git.openjdk.org/jdk/pull/17842#discussion_r1489218654
PR Review Comment: https://git.openjdk.org/jdk/pull/17842#discussion_r1489221872