RFR: 8327110: Refactor create_bool_from_template_assertion_predicate() to separate class and fix identical cloning cases used for Loop Unswitching and Split If [v2]

[Emanuel Peter]

On Wed, 27 Mar 2024 11:34:56 GMT, Christian Hagedorn <chagedorn at openjdk.org> wrote:

>> This is a follow-up to the previous refactoring done in https://github.com/openjdk/jdk/pull/18080. The patch starts to replace the usages of `create_bool_from_template_assertion_predicate()` by providing a refactored and fixed cloning algorithm.
>> 
>> #### How `create_bool_from_template_assertion_predicate()` Works
>> Currently, the algorithm in `create_bool_from_template_assertion_predicate()` uses an iterative DFS walk to find all nodes of a Template Assertion Predicate Expression in order to clone them. We do the following:
>> 1. Follow all inputs if they could be a node that's part of a Template Assertion Predicate (compares opcodes):
>> https://github.com/openjdk/jdk/blob/326c91e1a28ec70822ef927ee9ab17f79aa6d35c/src/hotspot/share/opto/loopTransform.cpp#L1513
>> 
>> 2. Once we find an `OpaqueLoopInit` or `OpaqueLoopStride` node, we start backtracking in the DFS. While doing so, we start to clone all nodes on the path from the `OpaqueLoop*Nodes` node to the start node and already update the graph. This logic is quite complex and difficult to understand since we do everything simultaneously. This was one of the reasons, I've originally  tried to refactor this method in https://github.com/openjdk/jdk/pull/16877 because I needed to extend it for the full fix of Assertion Predicates in JDK-8288981.
>> 
>> #### Missing Visited Set
>> The current implementation of `create_bool_from_template_assertion_predicate()` does not use a visited set. This means that whenever we find a diamond shape, we could visit a node twice and re-discover all paths above this diamond again:
>> 
>> 
>>     ...
>>      |
>>      E
>>      |
>>      D
>>     / \
>>    B   C
>>     \ /
>>      A
>> 
>> DFS walk: A -> B -> D -> E -> ... -> C -> D -> E -> ...
>> 
>> With each diamond, the number of revisits of each node above doubles.
>> 
>> #### Endless DFS in Edge-Cases
>> In most cases, we would normally just stop quite quickly once we follow a data node that is not part of a Template Assertion Predicate Expression because the node opcode is different. However, in the test cases, we create a long chain of data nodes with many diamonds that could all be part of a Template Assertion Predicate Expression (i.e. `is_part_of_template_assertion_predicate_bool()` would return true to follow the inputs in a DFS walk). As a result, the DFS revisits a lot of nodes, especially higher up in the graph, exponentially many times and compilation is stuck for a long time (running the test cases result in a test timeout because...
>
> Christian Hagedorn has updated the pull request with a new target base due to a merge or a rebase. The incremental webrev excludes the unrelated changes brought in by the merge/rebase. The pull request contains four additional commits since the last revision:
> 
>  - Change from DFS to 2xBFS
>  - Review Emanuel first part
>  - Merge branch 'master' into JDK-8327110
>  - 8327110: Refactor create_bool_from_template_assertion_predicate() to separate class and fix pure cloning cases used for Loop Unswitching and Split If

The changes look good, just a few minor suggestions left.

src/hotspot/share/opto/predicates.cpp line 193:

> 191:   // trivially pass the _node_filter.
> 192:   NodeCheck _is_target_node;
> 193:   Unique_Node_List _collected_nodes; // The resulting node collection of all nodes on paths from source->target(s).

Suggestion:

  // The resulting node collection of all nodes on paths from source->target(s).
  Unique_Node_List _collected_nodes;

Just cosmetic. All other comments are on their own lines too.

src/hotspot/share/opto/predicates.cpp line 217:

> 215:       backtrack_from_target_nodes();
> 216:       assert(_collected_nodes.member(start_node), "must find start node again when backtracking");
> 217:     }

What scenario is there where we collect no nodes? Probably there is some, where we don't have to clone anything.. but it's a bit strange. Would be nice to have a quick comment here about that.

For simplicity, you could always call backtrack (it just does nothing anyway).
Then you can just make the assert a bit smarter:
`assert(_collected_nodes.size() == 0 || _collected_nodes.member(start_node), "must find start node again when backtracking");`

test/hotspot/jtreg/compiler/predicates/TestCloningWithManyDiamondsInExpression.java line 28:

> 26:  * @test
> 27:  * @bug 8327110
> 28:  * @requires vm.compiler2.enabled

Is this required?
Maybe we can move the ` * @run main compiler.predicates.TestCloningWithManyDiamondsInExpression` run to a new `@test` block that does not have this `@requires`? Then other compilers also get tested.

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

PR Review: https://git.openjdk.org/jdk/pull/18293#pullrequestreview-1963786755
PR Review Comment: https://git.openjdk.org/jdk/pull/18293#discussion_r1541397549
PR Review Comment: https://git.openjdk.org/jdk/pull/18293#discussion_r1541407719
PR Review Comment: https://git.openjdk.org/jdk/pull/18293#discussion_r1541420965