RFR: 8305638: Refactor Template Assertion Predicate Bool creation and Predicate code in Split If and Loop Unswitching

[Emanuel Peter]

On Fri, 22 Dec 2023 16:47:52 GMT, Emanuel Peter <epeter at openjdk.org> wrote:

>> src/hotspot/share/opto/predicates.cpp line 245:
>> 
>>> 243: // Class to clone a Template Assertion Predicate Bool. The BoolNode and all the nodes up to but excluding the OpaqueLoop*
>>> 244: // nodes are cloned. The OpaqueLoop* nodes are transformed by the provided strategy (e.g. cloned or replaced).
>>> 245: class CloneTemplateAssertionPredicateBool : public StackObj {
>> 
>> Suggestion:
>> 
>> class CloneTemplateAssertionPredicateExpression : public StackObj {
>
> I left quite a few comments below, because I think the algorithm is difficult to understand.
> I like the idea of splitting it into smaller parts.
> 
> If I understand the basic algorithm, we do this:
> DFS, where we traverse the inputs recursively, using the `DFSNodeStack`, which uses the filter `TemplateAssertionPredicateBool::could_be_part`.
> 
> If you see a init/stride `Opaque1` node, then you obviously clone it.
> 
> If you come back from an input to a output (use to def), then you may get back a cloned input node.
> If the input node is not a clone, then we have to do nothing.
> If the input node is a clone, we also have to clone the output node. Clone it if it is not already a clone. And then update the current input slot, so we do not point to the pre-cloned input, but to the cloned input.

So we need to do work whenever we walk back down a input->output edge. We can traverse this edge, by taking the post-order traversal, and then waling from the post-order visited node to its output node.


    Node* current;
    while (_stack.is_not_empty()) {
      current = _stack.top();
      if (current->is_Opaque1()) {
        Node* transformed_node = transform_opaque_loop_node(current, transform_opaque_loop_nodes);
        _stack.replace_top(transformed_node);
        traverse_edge_back_to_output_and_pop();
      } else if (!_stack.push_next_unvisited_input()) {
        traverse_edge_back_to_output_and_pop();
      } // else: we just pushed an new input, go and visit it first
    }
    
traverse_edge_back_to_output_and_pop:
  Node* maybe_cloned_input = _stack.pop();
  if (_stack.is_empty()) {
    return; // we just visited the root node, and are now done. Maybe verify we have the root here?  
  }
  Node* output = _stack.top();
  int i = _stack.top_index();
  if (!is_clone(output)) {
    output = output->clone();
    _stack.replace_top(output);
  }
  output->set_req(i, maybe_cloned_input);

>> src/hotspot/share/opto/predicates.cpp line 273:
>> 
>>> 271:     if (must_clone_node_on_top(transformed_opaque_loop_node)) {
>>> 272:       clone_and_replace_top_node();
>>> 273:     }
>> 
>> Why do you touch the output node here? Is it not post-visited later anyway?
>
> Oh, I see. We are eagerly cloning the output node, if it is not yet cloned. Hmm. I guess that is better than trying to fiture out in the post-visit if we need to clone or not, because that would require querying if any input node is a clone?

Ah oh dear. And that is why you need to then always rewire below. Hmm.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/16877#discussion_r1435231073
PR Review Comment: https://git.openjdk.org/jdk/pull/16877#discussion_r1435193899