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

[Christian Hagedorn]

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 background compilation is disabled).

#### New DFS Implementation
The new algorithm uses again an iterative DFS walk but uses a visited set to avoid this problem. The implementation is found in the new class `DataNodesOnPathToTargets`. It is written in a generic way such that it could potentially be reused at some point (i.e. using "source" and "target" instead of "opaque4" and "opaque loop nodes").

#### New Template Assertion Predicate Expression Cloning Algorithm
There is now a new class `TemplateAssertionPredicateExpression` that does the cloning of the Template Assertion Predicate Expression in the following way:
1. Collect nodes to clone with `DataNodesOnPathToTargets`.
2. Clone the collected nodes by reusing and extending `DataNodeGraph`.

#### Only Replacing Usages in Loop Unswitching and Split If
This patch only replaces the usages of `create_bool_from_template_assertion_predicate()` in Loop Unswitching and Split if which need an identical copy of Template Assertion Predicate Expressions. In JDK-8327111, I will replace the remaining usages which require a transformation of the `OpaqueLoop*Nodes` by adding additional strategies which implement the `TransformStrategyForOpaqueLoopNodes` interface.

#### Other Work Left for https://github.com/openjdk/jdk/pull/16877
- Clean up `Split If` code to clone down Template Assertion Predicate Expressions
  - Removes `is_part_of_template_assertion_predicate_bool()`  and `subgraph_has_opaque()`
- More renaming and small refactoring 

Thanks,
Christian

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

Commit messages:
 - 8327110: Refactor create_bool_from_template_assertion_predicate() to separate class and fix pure cloning cases used for Loop Unswitching and Split If

Changes: https://git.openjdk.org/jdk/pull/18293/files
  Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=18293&range=00
  Issue: https://bugs.openjdk.org/browse/JDK-8327110
  Stats: 418 lines in 9 files changed: 407 ins; 0 del; 11 mod
  Patch: https://git.openjdk.org/jdk/pull/18293.diff
  Fetch: git fetch https://git.openjdk.org/jdk.git pull/18293/head:pull/18293

PR: https://git.openjdk.org/jdk/pull/18293