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

[Vladimir Kozlov]

On Thu, 28 Mar 2024 12:32:59 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 incrementally with one additional commit since the last revision:
> 
>   Moved comment + better assert

"Stamp" of approval.

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

Marked as reviewed by kvn (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/18293#pullrequestreview-1974555601