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

[Emanuel Peter]

On Thu, 21 Mar 2024 13:31:27 GMT, Emanuel Peter <epeter 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...
>
> src/hotspot/share/opto/predicates.cpp line 301:
> 
>> 299:     }
>> 300:   }
>> 301: };
> 
> I think this is now correct. But it is 100 lines to perform and explain this DFS with backtracking.
> 
> On the other hand doing 2 BFS would just be 20+ lines.
> 
> 
> Unique_Node_List collected;
> 
> Unique_Node_List input_traversal;
> input_traversal.push(start_node);
> for (int i = 0; i < input_traversal.length(); i++) {
>   Node* n = input_traversal.at(i);
>   for (int j = 1; j < n->req(); j++) {
>     Node* input = n->in(j);
>     if (_is_target_node(input)) {
>       collected.push(input); // mark as target, where we start backtracking.
>     } else if(_filter(input)) {
>       input_traversal.push(input); // continue BFS.
>     }
>   }
> }
> assert(!collected.is_empty(), "must find some targets");
> for (int i = 0; i < collected.length(); i++) {
>   Node* n = collected.at(i);
>   for (output : n->fastout()) { // pseudocode
>     if (input_traversal.contains(output)) {
>       collected.push(output); // backtrack through nodes of input traversal
>     }
>   }
> }
> assert(collected.contains(start_node), "must find start node again");

But this is a matter of taste. The data structures probably have roughly the same size. And also runtime is probably basically the same.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/18293#discussion_r1533917234