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]

[Christian Hagedorn]

On Thu, 21 Mar 2024 13:32:23 GMT, Emanuel Peter <epeter at openjdk.org> wrote:

>> 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.

I think you're right. The typical Template Assertion Predicate Expression only has few nodes. So, I totally agree with you that we should go with a much simpler double BFS version instead of a single DFS walk. And if we ever find the need to have a single DFS walk with backtracking where a single walk is expensive, we could still go back to this PR and revive this code.

Updated code.

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

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