/*
 * Copyright (c) 2023, 2025, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
 */

#include "opto/addnode.hpp"
#include "opto/callnode.hpp"
#include "opto/castnode.hpp"
#include "opto/loopnode.hpp"
#include "opto/node.hpp"
#include "opto/predicates.hpp"
#include "opto/rootnode.hpp"
#include "runtime/deoptimization.hpp"

// Walk over all Initialized Assertion Predicates and return the entry into the first Initialized Assertion Predicate
// (i.e. not belonging to an Initialized Assertion Predicate anymore)
Node* AssertionPredicates::find_entry(Node* start_proj) {
  assert(start_proj != nullptr, "should not be null");
  Node* entry = start_proj;
  while (AssertionPredicate::is_predicate(entry)) {
    entry = entry->in(0)->in(0);
  }
  return entry;
}

// An Assertion Predicate has always a true projection on the success path.
bool may_be_assertion_predicate_if(const Node* node) {
  assert(node != nullptr, "should not be null");
  return node->is_IfTrue() && RegularPredicate::may_be_predicate_if(node->as_IfProj());
}

bool AssertionPredicate::is_predicate(const Node* maybe_success_proj) {
  if (!may_be_assertion_predicate_if(maybe_success_proj)) {
    return false;
  }
  return has_assertion_predicate_opaque(maybe_success_proj) && has_halt(maybe_success_proj->as_IfTrue());
}

// Check if the If node of `predicate_proj` has an OpaqueTemplateAssertionPredicate (Template Assertion Predicate) or
// an OpaqueInitializedAssertionPredicate (Initialized Assertion Predicate) node as input.
bool AssertionPredicate::has_assertion_predicate_opaque(const Node* predicate_proj) {
  IfNode* iff = predicate_proj->in(0)->as_If();
  Node* bol = iff->in(1);
  return bol->is_OpaqueTemplateAssertionPredicate() || bol->is_OpaqueInitializedAssertionPredicate();
}

// Check if the other projection (UCT projection) of `success_proj` has a Halt node as output.
bool AssertionPredicate::has_halt(const IfTrueNode* success_proj) {
  ProjNode* other_proj = success_proj->other_if_proj();
  return other_proj->outcnt() == 1 && other_proj->unique_out()->Opcode() == Op_Halt;
}

// Returns the Parse Predicate node if the provided node is a Parse Predicate success proj. Otherwise, return null.
ParsePredicateNode* ParsePredicate::init_parse_predicate(const Node* parse_predicate_proj,
                                                         Deoptimization::DeoptReason deopt_reason) {
  assert(parse_predicate_proj != nullptr, "must not be null");
  if (parse_predicate_proj->is_IfTrue() && parse_predicate_proj->in(0)->is_ParsePredicate()) {
    ParsePredicateNode* parse_predicate_node = parse_predicate_proj->in(0)->as_ParsePredicate();
    if (parse_predicate_node->deopt_reason() == deopt_reason) {
      return parse_predicate_node;
    }
  }
  return nullptr;
}

ParsePredicate ParsePredicate::clone_to_unswitched_loop(Node* new_control, const bool is_false_path_loop,
                                                        PhaseIdealLoop* phase) const {
  ParsePredicateSuccessProj* success_proj = phase->create_new_if_for_predicate(_success_proj, new_control,
                                                                               _parse_predicate_node->deopt_reason(),
                                                                               Op_ParsePredicate, is_false_path_loop);
  NOT_PRODUCT(trace_cloned_parse_predicate(is_false_path_loop, success_proj));
  return ParsePredicate(success_proj, _parse_predicate_node->deopt_reason());
}

// Kills this Parse Predicate by marking it useless. Will be folded away in the next IGVN round.
void ParsePredicate::kill(PhaseIterGVN& igvn) const {
  _parse_predicate_node->mark_useless(igvn);
}

#ifndef PRODUCT
void ParsePredicate::trace_cloned_parse_predicate(const bool is_false_path_loop,
                                                  const ParsePredicateSuccessProj* success_proj) {
  if (TraceLoopPredicate) {
    tty->print("Parse Predicate cloned to %s path loop: ", is_false_path_loop ? "false" : "true");
    success_proj->in(0)->dump();
  }
}
#endif // NOT PRODUCT

Deoptimization::DeoptReason RuntimePredicate::uncommon_trap_reason(const IfProjNode* if_proj) {
    CallStaticJavaNode* uct_call = if_proj->is_uncommon_trap_if_pattern();
    if (uct_call == nullptr) {
      return Deoptimization::Reason_none;
    }
    return Deoptimization::trap_request_reason(uct_call->uncommon_trap_request());
}

bool RuntimePredicate::is_predicate(const Node* maybe_success_proj) {
  if (RegularPredicate::may_be_predicate_if(maybe_success_proj)) {
    return has_valid_uncommon_trap(maybe_success_proj);
  } else {
    return false;
  }
}

bool RuntimePredicate::has_valid_uncommon_trap(const Node* success_proj) {
  assert(RegularPredicate::may_be_predicate_if(success_proj), "must have been checked before");
  const Deoptimization::DeoptReason deopt_reason = uncommon_trap_reason(success_proj->as_IfProj());
  return (deopt_reason == Deoptimization::Reason_loop_limit_check ||
          deopt_reason == Deoptimization::Reason_auto_vectorization_check ||
          deopt_reason == Deoptimization::Reason_predicate ||
          deopt_reason == Deoptimization::Reason_profile_predicate);
}

bool RuntimePredicate::is_predicate(const Node* node, const Deoptimization::DeoptReason deopt_reason) {
  if (RegularPredicate::may_be_predicate_if(node)) {
    return deopt_reason == uncommon_trap_reason(node->as_IfProj());
  } else {
    return false;
  }
}

// A Regular Predicate must have an If or a RangeCheck node, while the If should not be a zero trip guard check.
// Note that this method can be called during IGVN, so we also need to check that the If is not top.
bool RegularPredicate::may_be_predicate_if(const Node* node) {
  if (node->is_IfProj() && node->in(0)->is_If()) {
    const IfNode* if_node = node->in(0)->as_If();
    const int opcode_if = if_node->Opcode();
    if ((opcode_if == Op_If && !if_node->is_zero_trip_guard())
        || opcode_if == Op_RangeCheck) {
      return true;
    }
  }
  return false;
}

// Rewire any non-CFG nodes dependent on this Template Assertion Predicate (i.e. with a control input to this
// Template Assertion Predicate) to the 'target_predicate' based on the 'data_in_loop_body' check.
void TemplateAssertionPredicate::rewire_loop_data_dependencies(IfTrueNode* target_predicate,
                                                               const NodeInLoopBody& data_in_loop_body,
                                                               const PhaseIdealLoop* phase) const {
  for (DUIterator i = _success_proj->outs(); _success_proj->has_out(i); i++) {
    Node* output = _success_proj->out(i);
    if (!output->is_CFG() && data_in_loop_body.check_node_in_loop_body(output)) {
      phase->igvn().replace_input_of(output, 0, target_predicate);
      --i; // account for the just deleted output
    }
  }
}

// A Template Assertion Predicate always has a dedicated OpaqueTemplateAssertionPredicate to identify it.
bool TemplateAssertionPredicate::is_predicate(const Node* maybe_success_proj) {
  if (!may_be_assertion_predicate_if(maybe_success_proj)) {
    return false;
  }
  IfNode* if_node = maybe_success_proj->in(0)->as_If();
  bool is_template_assertion_predicate = if_node->in(1)->is_OpaqueTemplateAssertionPredicate();
  assert(!is_template_assertion_predicate || AssertionPredicate::has_halt(maybe_success_proj->as_IfTrue()),
         "Template Assertion Predicate must have a Halt Node on the failing path");
  return is_template_assertion_predicate;
}

// Clone this Template Assertion Predicate without modifying any OpaqueLoop*Node inputs.
TemplateAssertionPredicate TemplateAssertionPredicate::clone(Node* new_control, CountedLoopNode* new_loop_node,
                                                             PhaseIdealLoop* phase) const {
  DEBUG_ONLY(verify();)
  TemplateAssertionExpression template_assertion_expression(opaque_node(), phase);
  OpaqueTemplateAssertionPredicateNode* new_opaque_node = template_assertion_expression.clone(new_control, new_loop_node);
  AssertionPredicateIfCreator assertion_predicate_if_creator(phase);
  IfTrueNode* success_proj = assertion_predicate_if_creator.create_for_template(new_control, _if_node->Opcode(),
                                                                                new_opaque_node,
                                                                                _if_node->assertion_predicate_type());
  TemplateAssertionPredicate cloned_template_assertion_predicate(success_proj);
  DEBUG_ONLY(cloned_template_assertion_predicate.verify();)
  return cloned_template_assertion_predicate;
}

// Clone this Template Assertion Predicate and use a newly created OpaqueLoopInitNode with 'new_opaque_input' as input.
TemplateAssertionPredicate TemplateAssertionPredicate::clone_and_replace_opaque_input(Node* new_control,
                                                                                      Node* new_opaque_input,
                                                                                      CountedLoopNode* new_loop_node,
                                                                                      PhaseIdealLoop* phase) const {
  DEBUG_ONLY(verify();)
  OpaqueLoopInitNode* new_opaque_init = new OpaqueLoopInitNode(phase->C, new_opaque_input);
  phase->register_new_node(new_opaque_init, new_control);
  TemplateAssertionExpression template_assertion_expression(opaque_node(), phase);
  OpaqueTemplateAssertionPredicateNode* new_opaque_node =
      template_assertion_expression.clone_and_replace_init(new_control, new_opaque_init, new_loop_node);
  AssertionPredicateIfCreator assertion_predicate_if_creator(phase);
  IfTrueNode* success_proj = assertion_predicate_if_creator.create_for_template(new_control, _if_node->Opcode(),
                                                                                new_opaque_node,
                                                                                _if_node->assertion_predicate_type());
  TemplateAssertionPredicate cloned_template_assertion_predicate(success_proj);
  DEBUG_ONLY(cloned_template_assertion_predicate.verify();)
  return cloned_template_assertion_predicate;
}

// This class is used to replace the input to OpaqueLoopStrideNode with a new node while leaving the other nodes
// unchanged.
class ReplaceOpaqueStrideInput : public BFSActions {
  Node* _new_opaque_stride_input;
  PhaseIterGVN& _igvn;

  public:
  ReplaceOpaqueStrideInput(Node* new_opaque_stride_input, PhaseIterGVN& igvn)
      : _new_opaque_stride_input(new_opaque_stride_input),
        _igvn(igvn) {}
  NONCOPYABLE(ReplaceOpaqueStrideInput);

  void replace_for(OpaqueTemplateAssertionPredicateNode* opaque_node) {
    DataNodeBFS bfs(*this);
    bfs.run(opaque_node);
  }

  bool should_visit(Node* node) const override {
    return TemplateAssertionExpressionNode::is_maybe_in_expression(node);
  }

  bool is_target_node(Node* node) const override {
    return node->is_OpaqueLoopStride();
  }

  void target_node_action(Node* target_node) override {
    _igvn.replace_input_of(target_node, 1, _new_opaque_stride_input);
  }
};

// Replace the input to OpaqueLoopStrideNode with 'new_stride' and leave the other nodes unchanged.
void TemplateAssertionPredicate::replace_opaque_stride_input(Node* new_stride, PhaseIterGVN& igvn) const {
  DEBUG_ONLY(verify();)
  ReplaceOpaqueStrideInput replace_opaque_stride_input(new_stride, igvn);
  replace_opaque_stride_input.replace_for(opaque_node());
}

// Create a new Initialized Assertion Predicate from this template at the template success projection.
InitializedAssertionPredicate TemplateAssertionPredicate::initialize(PhaseIdealLoop* phase) const {
  DEBUG_ONLY(verify();)
  InitializedAssertionPredicateCreator initialized_assertion_predicate_creator(phase);
  InitializedAssertionPredicate initialized_assertion_predicate =
      initialized_assertion_predicate_creator.create_from_template_and_insert_below(*this);
  DEBUG_ONLY(initialized_assertion_predicate.verify();)
  return initialized_assertion_predicate;
}

// Kills this Template Assertion Predicate by marking the associated OpaqueTemplateAssertionPredicate node useless.
// It will then be folded away in the next IGVN round.
void TemplateAssertionPredicate::kill(PhaseIterGVN& igvn) const {
  opaque_node()->mark_useless(igvn);
}

#ifdef ASSERT
// Class to verify Initialized and Template Assertion Predicates by trying to find OpaqueLoop*Nodes.
class OpaqueLoopNodesVerifier : public BFSActions {
  bool _found_init;
  bool _found_stride;

 public:
  OpaqueLoopNodesVerifier()
      : _found_init(false),
        _found_stride(false) {}

  // A Template Assertion Predicate has:
  // - Always an OpaqueLoopInitNode
  // - Only an OpaqueLoopStrideNode for the last value.
  void verify(const TemplateAssertionPredicate& template_assertion_predicate) {
    DataNodeBFS bfs(*this);
    bfs.run(template_assertion_predicate.opaque_node());
    if (template_assertion_predicate.is_last_value()) {
      assert(_found_init && _found_stride,
             "must find OpaqueLoopInit and OpaqueLoopStride for last value Template Assertion Predicate");
    } else {
      assert(_found_init && !_found_stride,
             "must find OpaqueLoopInit but not OpaqueLoopStride for init value Template Assertion Predicate");
    }
  }

  // An Initialized Assertion Predicate never has any OpaqueLoop*Nodes.
  void verify(const InitializedAssertionPredicate& initialized_assertion_predicate) {
    DataNodeBFS bfs(*this);
    bfs.run(initialized_assertion_predicate.opaque_node());
    assert(!_found_init && !_found_stride,
           "must neither find OpaqueLoopInit nor OpaqueLoopStride for Initialized Assertion Predicate");
  }

  bool should_visit(Node* node) const override {
    return TemplateAssertionExpressionNode::is_maybe_in_expression(node);
  }

  bool is_target_node(Node* node) const override {
    return node->is_Opaque1();
  }

  void target_node_action(Node* target_node) override {
    if (target_node->is_OpaqueLoopInit()) {
      assert(!_found_init, "should only find one OpaqueLoopInitNode");
      _found_init = true;
    } else {
      assert(target_node->is_OpaqueLoopStride(), "unexpected Opaque1 node");
      assert(!_found_stride, "should only find one OpaqueLoopStrideNode");
      _found_stride = true;
    }
  }
};

// Verify that the Template Assertion Predicate has the correct OpaqueLoop*Nodes.
void TemplateAssertionPredicate::verify() const {
  OpaqueLoopNodesVerifier opaque_loop_nodes_verifier;
  opaque_loop_nodes_verifier.verify(*this);
}

// Verify that the Initialized Assertion Predicate has no OpaqueLoop*Node.
void InitializedAssertionPredicate::verify() const {
  OpaqueLoopNodesVerifier opaque_loop_nodes_verifier;
  opaque_loop_nodes_verifier.verify(*this);
}
#endif // ASSERT

// An Initialized Assertion Predicate always has a dedicated OpaqueInitializedAssertionPredicate node to identify it.
bool InitializedAssertionPredicate::is_predicate(const Node* maybe_success_proj) {
  if (!may_be_assertion_predicate_if(maybe_success_proj)) {
    return false;
  }
  IfNode* if_node = maybe_success_proj->in(0)->as_If();
  bool is_initialized_assertion_predicate = if_node->in(1)->is_OpaqueInitializedAssertionPredicate();
  assert(!is_initialized_assertion_predicate || has_halt(maybe_success_proj->as_IfTrue()),
         "Initialized Assertion Predicate must have a Halt Node on the failing path");
  return is_initialized_assertion_predicate;
}

#ifdef ASSERT
bool InitializedAssertionPredicate::has_halt(const IfTrueNode* success_proj) {
  ProjNode* other_proj = success_proj->other_if_proj();
  if (other_proj->outcnt() != 1) {
    return false;
  }

  Node* out = other_proj->unique_out();
  // Either the Halt node is directly the unique output.
  if (out->is_Halt()) {
    return true;
  }
  // Or we have a Region that merges serval paths to a single Halt node. Even though OpaqueInitializedAssertionPredicate
  // nodes do not common up (i.e. NO_HASH), we could have Initialized Assertion Predicates from already folded loops
  // being now part of the innermost loop. When then further splitting this loop, we could be cloning the If node
  // of the Initialized Assertion Predicate (part of the loop body) while the OpaqueInitializedAssertionPredicate is not
  // cloned because it's outside the loop body. We end up sharing the OpaqueInitializedAssertionPredicate between the
  // original and the cloned If. This should be fine.
  if (out->is_Region() && out->outcnt() == 2) {
    return out->find_out_with(Op_Halt);
  }
  return false;
}
#endif // ASSERT

// Kills this Initialized Assertion Predicate by marking the associated OpaqueInitializedAssertionPredicate node useless.
// It will then be folded away in the next IGVN round.
void InitializedAssertionPredicate::kill(PhaseIterGVN& igvn) const {
  opaque_node()->mark_useless(igvn);
}

#ifdef ASSERT
// Check that the block has at most one Parse Predicate and that we only find Regular Predicate nodes (i.e. IfProj,
// If, or RangeCheck nodes).
void RegularPredicateBlock::verify_block(Node* tail) const {
  Node* next = tail;
  while (next != _entry) {
    assert(!next->is_ParsePredicate(), "can only have one Parse Predicate in a block");
    const int opcode = next->Opcode();
    assert(next->is_IfProj() || opcode == Op_If || opcode == Op_RangeCheck,
           "Regular Predicates consist of an IfProj and an If or RangeCheck node");
    assert(opcode != Op_If || !next->as_If()->is_zero_trip_guard(), "should not be zero trip guard");
    next = next->in(0);
  }
}
#endif // ASSERT

// This strategy clones the OpaqueLoopInit and OpaqueLoopStride nodes.
class CloneStrategy : public TransformStrategyForOpaqueLoopNodes {
  PhaseIdealLoop* const _phase;
  Node* const _new_control;

 public:
  CloneStrategy(PhaseIdealLoop* phase, Node* new_control)
      : _phase(phase),
        _new_control(new_control) {}
  NONCOPYABLE(CloneStrategy);

  Node* transform_opaque_init(OpaqueLoopInitNode* opaque_init) const override {
    return _phase->clone_and_register(opaque_init, _new_control)->as_OpaqueLoopInit();
  }

  Node* transform_opaque_stride(OpaqueLoopStrideNode* opaque_stride) const override {
    return _phase->clone_and_register(opaque_stride, _new_control)->as_OpaqueLoopStride();
  }
};

// This strategy replaces the OpaqueLoopInitNode with the provided init node and clones the OpaqueLoopStrideNode.
class ReplaceInitAndCloneStrideStrategy : public TransformStrategyForOpaqueLoopNodes {
  Node* const _new_init;
  Node* const _new_control;
  PhaseIdealLoop* const _phase;

 public:
  ReplaceInitAndCloneStrideStrategy(Node* new_control, Node* new_init, PhaseIdealLoop* phase)
      : _new_init(new_init),
        _new_control(new_control),
        _phase(phase) {}
  NONCOPYABLE(ReplaceInitAndCloneStrideStrategy);

  Node* transform_opaque_init(OpaqueLoopInitNode* opaque_init) const override {
    return _new_init;
  }

  Node* transform_opaque_stride(OpaqueLoopStrideNode* opaque_stride) const override {
    return _phase->clone_and_register(opaque_stride, _new_control)->as_OpaqueLoopStride();
  }
};

// This strategy replaces the OpaqueLoopInit and OpaqueLoopStride nodes with the provided init and stride nodes,
// respectively.
class ReplaceInitAndStrideStrategy : public TransformStrategyForOpaqueLoopNodes {
  Node* const _new_init;
  Node* const _new_stride;

 public:
  ReplaceInitAndStrideStrategy(Node* new_init, Node* new_stride)
      : _new_init(new_init),
        _new_stride(new_stride) {}
  NONCOPYABLE(ReplaceInitAndStrideStrategy);

  Node* transform_opaque_init(OpaqueLoopInitNode* opaque_init) const override {
    return _new_init;
  }

  Node* transform_opaque_stride(OpaqueLoopStrideNode* opaque_stride) const override {
    return _new_stride;
  }
};

// Creates an identical clone of this Template Assertion Expression (i.e.cloning all nodes from the
// OpaqueTemplateAssertionPredicate to and including the OpaqueLoop* nodes). The cloned nodes are rewired to reflect the
// same graph structure as found for this Template Assertion Expression. The cloned nodes get 'new_control' as control.
// There is no other update done for the cloned nodes. Return the newly cloned OpaqueTemplateAssertionPredicate.
OpaqueTemplateAssertionPredicateNode* TemplateAssertionExpression::clone(Node* new_control, CountedLoopNode* new_loop_node) const {
  CloneStrategy clone_init_and_stride_strategy(_phase, new_control);
  return clone(clone_init_and_stride_strategy, new_control, new_loop_node);
}

// Same as clone() but instead of cloning the OpaqueLoopInitNode, we replace it with the provided 'new_init' node.
OpaqueTemplateAssertionPredicateNode*
TemplateAssertionExpression::clone_and_replace_init(Node* new_control, Node* new_init,
                                                    CountedLoopNode* new_loop_node) const {
  ReplaceInitAndCloneStrideStrategy replace_init_and_clone_stride_strategy(new_control, new_init, _phase);
  return clone(replace_init_and_clone_stride_strategy, new_control, new_loop_node);
}

// Same as clone() but instead of cloning the OpaqueLoopInit and OpaqueLoopStride node, we replace them with the provided
// 'new_init' and 'new_stride' nodes, respectively.
OpaqueTemplateAssertionPredicateNode*
TemplateAssertionExpression::clone_and_replace_init_and_stride(Node* new_control, Node* new_init, Node* new_stride) const {
  ReplaceInitAndStrideStrategy replace_init_and_stride_strategy(new_init, new_stride);
  return clone(replace_init_and_stride_strategy, new_control, _opaque_node->loop_node());
}

// Class to collect data nodes from a source to target nodes by following the inputs of the source node recursively.
// The class takes a node filter to decide which input nodes to follow and a target node predicate to start backtracking
// from. All nodes found on all paths from source->target(s) are returned in a Unique_Node_List (without duplicates).
class DataNodesOnPathsToTargets : public StackObj {
  typedef bool (*NodeCheck)(const Node*);

  // Node filter function to decide if we should process a node or not while searching for targets.
  NodeCheck _node_filter;
  // Function to decide if a node is a target node (i.e. where we should start backtracking). This check should also
  // trivially pass the _node_filter.
  NodeCheck _is_target_node;
  // The resulting node collection of all nodes on paths from source->target(s).
  Unique_Node_List _collected_nodes;
  // List to track all nodes visited on the search for target nodes starting at a start node. These nodes are then used
  // in backtracking to find the nodes actually being on a start->target(s) path. This list also serves as visited set
  // to avoid double visits of a node which could happen with diamonds shapes.
  Unique_Node_List _nodes_to_visit;

 public:
  DataNodesOnPathsToTargets(NodeCheck node_filter, NodeCheck is_target_node)
      : _node_filter(node_filter),
        _is_target_node(is_target_node) {}
  NONCOPYABLE(DataNodesOnPathsToTargets);

  // Collect all input nodes from 'start_node'->target(s) by applying the node filter to discover new input nodes and
  // the target node predicate to stop discovering more inputs and start backtracking. The implementation is done
  // with two BFS traversal: One to collect the target nodes (if any) and one to backtrack from the target nodes to
  // find all other nodes on the start->target(s) paths.
  const Unique_Node_List& collect(Node* start_node) {
    assert(_collected_nodes.size() == 0 && _nodes_to_visit.size() == 0, "should not call this method twice in a row");
    assert(!_is_target_node(start_node), "no trivial paths where start node is also a target node");

    collect_target_nodes(start_node);
    backtrack_from_target_nodes();
    assert(_collected_nodes.size() == 0 || _collected_nodes.member(start_node),
           "either target node predicate was never true or must find start node again when doing backtracking work");
    return _collected_nodes;
  }

 private:
  // Do a BFS from the start_node to collect all target nodes. We can then do another BFS from the target nodes to
  // find all nodes on the paths from start->target(s).
  // Note: We could do a single DFS pass to search targets and backtrack in one walk. But this is much more complex.
  //       Given that the typical Template Assertion Expression only consists of a few nodes, we aim for simplicity here.
  void collect_target_nodes(Node* start_node) {
    _nodes_to_visit.push(start_node);
    for (uint i = 0; i < _nodes_to_visit.size(); i++) {
      Node* next = _nodes_to_visit[i];
      for (uint j = 1; j < next->req(); j++) {
        Node* input = next->in(j);
        if (_is_target_node(input)) {
          assert(_node_filter(input), "must also pass node filter");
          _collected_nodes.push(input);
        } else if (_node_filter(input)) {
          _nodes_to_visit.push(input);
        }
      }
    }
  }

  // Backtrack from all previously collected target nodes by using the visited set of the start->target(s) search. If no
  // node was collected in the first place (i.e. target node predicate was never true), then nothing needs to be done.
  void backtrack_from_target_nodes() {
    for (uint i = 0; i < _collected_nodes.size(); i++) {
      Node* node_on_path = _collected_nodes[i];
      for (DUIterator_Fast jmax, j = node_on_path->fast_outs(jmax); j < jmax; j++) {
        Node* use = node_on_path->fast_out(j);
        if (_nodes_to_visit.member(use)) {
          // use must be on a path from start->target(s) because it was also visited in the first BFS starting from
          // the start node.
          _collected_nodes.push(use);
        }
      }
    }
  }
};

// Clones this Template Assertion Expression and applies the given strategy to transform the OpaqueLoop* nodes.
OpaqueTemplateAssertionPredicateNode*
TemplateAssertionExpression::clone(const TransformStrategyForOpaqueLoopNodes& transform_strategy, Node* new_control,
                                   CountedLoopNode* new_loop_node) const {
  ResourceMark rm;
  auto is_opaque_loop_node = [](const Node* node) {
    return node->is_Opaque1();
  };
  DataNodesOnPathsToTargets data_nodes_on_path_to_targets(TemplateAssertionExpressionNode::is_maybe_in_expression,
                                                          is_opaque_loop_node);
  Node* bool_into_opaque_node = _opaque_node->in(1);
  const Unique_Node_List& collected_nodes = data_nodes_on_path_to_targets.collect(bool_into_opaque_node);
  DataNodeGraph data_node_graph(collected_nodes, _phase);
  const OrigToNewHashtable& orig_to_new = data_node_graph.clone_with_opaque_loop_transform_strategy(transform_strategy,
                                                                                                    new_control);
  assert(orig_to_new.contains(bool_into_opaque_node), "must exist");
  BoolNode* bool_into_opaque_node_clone = (*orig_to_new.get(bool_into_opaque_node))->as_Bool();
  OpaqueTemplateAssertionPredicateNode* opaque_clone =
      new OpaqueTemplateAssertionPredicateNode(bool_into_opaque_node_clone, new_loop_node);
  _phase->C->add_template_assertion_predicate_opaque(opaque_clone);
  _phase->register_new_node(opaque_clone, new_control);
  return opaque_clone;
}

// The transformations of this class fold the OpaqueLoop* nodes by returning their inputs.
class RemoveOpaqueLoopNodesStrategy : public TransformStrategyForOpaqueLoopNodes {
 public:
  Node* transform_opaque_init(OpaqueLoopInitNode* opaque_init) const override {
    return opaque_init->in(1);
  }

  Node* transform_opaque_stride(OpaqueLoopStrideNode* opaque_stride) const override {
    return opaque_stride->in(1);
  }
};

OpaqueInitializedAssertionPredicateNode*
TemplateAssertionExpression::clone_and_fold_opaque_loop_nodes(Node* new_control) const {
  RemoveOpaqueLoopNodesStrategy remove_opaque_loop_nodes_strategy;
  OpaqueTemplateAssertionPredicateNode* cloned_template_opaque = clone(remove_opaque_loop_nodes_strategy, new_control,
                                                                       _opaque_node->loop_node());
  OpaqueInitializedAssertionPredicateNode* opaque_initialized_opaque =
      new OpaqueInitializedAssertionPredicateNode(cloned_template_opaque->in(1)->as_Bool(), _phase->C);
  _phase->register_new_node(opaque_initialized_opaque, new_control);
  return opaque_initialized_opaque;
}

// Check if this node belongs a Template Assertion Expression (including OpaqueLoop* nodes).
bool TemplateAssertionExpressionNode::is_in_expression(Node* node) {
  if (is_maybe_in_expression(node)) {
    ResourceMark rm;
    Unique_Node_List list;
    list.push(node);
    for (uint i = 0; i < list.size(); i++) {
      Node* next = list.at(i);
      if (next->is_OpaqueLoopInit() || next->is_OpaqueLoopStride()) {
        return true;
      } else if (is_maybe_in_expression(next)) {
        list.push_non_cfg_inputs_of(next);
      }
    }
  }
  return false;
}

bool TemplateAssertionExpressionNode::is_template_assertion_predicate(const Node* node) {
  return node->is_If() && node->in(1)->is_OpaqueTemplateAssertionPredicate();
}

// This class creates the Assertion Predicate expression to be used for a Template or Initialized Assertion Predicate.
class AssertionPredicateExpressionCreator : public StackObj {
  PhaseIdealLoop* const _phase;
  const jint _stride;
  const int _scale;
  Node* const _offset;
  Node* const _range;
  const bool _upper;

 public:
  AssertionPredicateExpressionCreator(const int stride, const int scale, Node* offset, Node* range,
                                      PhaseIdealLoop* phase)
      : _phase(phase),
        _stride(stride),
        _scale(scale),
        _offset(offset),
        _range(range),
        _upper((_stride > 0) != (_scale > 0)) {} // Make sure rc_predicate() chooses the "scale*init + offset" case.

  // Create the expression for a Template Assertion Predicate with an OpaqueTemplateAssertionPredicate node.
  OpaqueTemplateAssertionPredicateNode* create_for_template(Node* new_control, Node* operand, CountedLoopNode* loop_node,
                                                            bool& does_overflow) const {
    BoolNode* bool_for_expression =  _phase->rc_predicate(new_control, _scale, _offset, operand, nullptr,
                                                          _stride, _range, _upper, does_overflow);
    return create_opaque_for_template(new_control, bool_for_expression, loop_node);
  }

 private:
  OpaqueTemplateAssertionPredicateNode* create_opaque_for_template(Node* new_control, BoolNode* bool_for_expression,
                                                           CountedLoopNode* loop_node) const {
    OpaqueTemplateAssertionPredicateNode* new_expression = new OpaqueTemplateAssertionPredicateNode(bool_for_expression,
                                                                                                    loop_node);
    _phase->C->add_template_assertion_predicate_opaque(new_expression);
    _phase->register_new_node(new_expression, new_control);
    return new_expression;
  }

 public:
  // Create the expression for an Initialized Assertion Predicate with an OpaqueInitializedAssertionPredicate node.
  OpaqueInitializedAssertionPredicateNode* create_for_initialized(Node* new_control, Node* operand,
                                                                  bool& does_overflow) const {
    BoolNode* bool_for_expression = _phase->rc_predicate(new_control, _scale, _offset, operand, nullptr,
                                                         _stride, _range, _upper, does_overflow);
    return create_opaque_for_initialized(new_control, bool_for_expression);
  }

 private:
  OpaqueInitializedAssertionPredicateNode* create_opaque_for_initialized(Node* new_control,
                                                                         BoolNode* bool_for_expression) const {
    OpaqueInitializedAssertionPredicateNode* new_expression =
        new OpaqueInitializedAssertionPredicateNode(bool_for_expression, _phase->C);
    _phase->register_new_node(new_expression, new_control);
    return new_expression;
  }
};

// Creates an If with a success and a fail path with the given assertion_expression. The only difference to
// create_for_initialized() is that we use a template specific Halt message on the fail path.
IfTrueNode* AssertionPredicateIfCreator::create_for_template(Node* new_control, const int if_opcode,
                                                             Node* assertion_expression,
                                                             const AssertionPredicateType assertion_predicate_type) const {
  const char* halt_message = "Template Assertion Predicates are always removed before code generation";
  return create(new_control, if_opcode, assertion_expression, halt_message, assertion_predicate_type);
}

// Creates an If with a success and a fail path with the given assertion_expression. The only difference to
// create_for_template() is that we use a initialized specific Halt message on the fail path.
IfTrueNode* AssertionPredicateIfCreator::create_for_initialized(Node* new_control, const int if_opcode,
                                                                Node* assertion_expression,
                                                                const AssertionPredicateType assertion_predicate_type) const {
  const char* halt_message = "Initialized Assertion Predicate cannot fail";
  return create(new_control, if_opcode, assertion_expression, halt_message, assertion_predicate_type);
}

// Creates the If node for an Assertion Predicate with a success path and a fail path having a Halt node:
//
//      new_control   assertion_expression
//                \   /
//                 If
//               /    \
//        success     fail path
//           proj      with Halt
//
IfTrueNode* AssertionPredicateIfCreator::create(Node* new_control, const int if_opcode, Node* assertion_expression,
                                                const char* halt_message,
                                                const AssertionPredicateType assertion_predicate_type) const {
  assert(assertion_expression->is_OpaqueTemplateAssertionPredicate() ||
         assertion_expression->is_OpaqueInitializedAssertionPredicate(), "not a valid assertion expression");
  IdealLoopTree* loop = _phase->get_loop(new_control);
  IfNode* if_node = create_if_node(new_control, if_opcode, assertion_expression, loop, assertion_predicate_type);
  create_fail_path(if_node, loop, halt_message);
  return create_success_path(if_node, loop);
}

IfNode* AssertionPredicateIfCreator::create_if_node(Node* new_control, const int if_opcode, Node* assertion_expression,
                                                    IdealLoopTree* loop,
                                                    const AssertionPredicateType assertion_predicate_type) const {
  IfNode* if_node;
  if (if_opcode == Op_If) {
    if_node = new IfNode(new_control, assertion_expression, PROB_MAX, COUNT_UNKNOWN, assertion_predicate_type);
  } else {
    assert(if_opcode == Op_RangeCheck, "must be range check");
    if_node = new RangeCheckNode(new_control, assertion_expression, PROB_MAX, COUNT_UNKNOWN, assertion_predicate_type);
  }
  _phase->register_control(if_node, loop, new_control);
  return if_node;
}

IfTrueNode* AssertionPredicateIfCreator::create_success_path(IfNode* if_node, IdealLoopTree* loop) const {
  IfTrueNode* success_proj = new IfTrueNode(if_node);
  _phase->register_control(success_proj, loop, if_node);
  return success_proj;
}

void AssertionPredicateIfCreator::create_fail_path(IfNode* if_node, IdealLoopTree* loop, const char* halt_message) const {
  IfFalseNode* fail_proj = new IfFalseNode(if_node);
  _phase->register_control(fail_proj, loop, if_node);
  create_halt_node(fail_proj, loop, halt_message);
}

void AssertionPredicateIfCreator::create_halt_node(IfFalseNode* fail_proj, IdealLoopTree* loop,
                                                   const char* halt_message) const {
  StartNode* start_node = _phase->C->start();
  Node* frame = new ParmNode(start_node, TypeFunc::FramePtr);
  _phase->register_new_node(frame, start_node);
  Node* halt = new HaltNode(fail_proj, frame, halt_message);
  _phase->igvn().add_input_to(_phase->C->root(), halt);
  _phase->register_control(halt, loop, fail_proj);
}

OpaqueLoopInitNode* TemplateAssertionPredicateCreator::create_opaque_init(Node* new_control) const {
  OpaqueLoopInitNode* opaque_init = new OpaqueLoopInitNode(_phase->C, _loop_head->uncasted_init_trip(_loop_head->is_main_loop()));
  _phase->register_new_node(opaque_init, new_control);
  return opaque_init;
}

OpaqueTemplateAssertionPredicateNode*
TemplateAssertionPredicateCreator::create_for_init_value(Node* new_control, OpaqueLoopInitNode* opaque_init,
                                                         bool& does_overflow) const {
  AssertionPredicateExpressionCreator expression_creator(_loop_head->stride_con(), _scale, _offset, _range, _phase);
  return expression_creator.create_for_template(new_control, opaque_init, _loop_head, does_overflow);
}

OpaqueTemplateAssertionPredicateNode*
TemplateAssertionPredicateCreator::create_for_last_value(Node* new_control, OpaqueLoopInitNode* opaque_init,
                                                         bool& does_overflow) const {
  Node* last_value = create_last_value(new_control, opaque_init);
  AssertionPredicateExpressionCreator expression_creator(_loop_head->stride_con(), _scale, _offset, _range, _phase);
  return expression_creator.create_for_template(new_control, last_value, _loop_head, does_overflow);
}

Node* TemplateAssertionPredicateCreator::create_last_value(Node* new_control, OpaqueLoopInitNode* opaque_init) const {
  Node* init_stride = _loop_head->stride();
  Node* opaque_stride = new OpaqueLoopStrideNode(_phase->C, init_stride);
  _phase->register_new_node(opaque_stride, new_control);
  Node* last_value = new SubINode(opaque_stride, init_stride);
  _phase->register_new_node(last_value, new_control);
  last_value = new AddINode(opaque_init, last_value);
  _phase->register_new_node(last_value, new_control);
  // init + (current stride - initial stride) is within the loop so narrow its type by leveraging the type of the iv phi
  last_value = new CastIINode(new_control, last_value, _loop_head->phi()->bottom_type());
  _phase->register_new_node(last_value, new_control);
  return last_value;
}

IfTrueNode* TemplateAssertionPredicateCreator::create_if_node(
    Node* new_control, OpaqueTemplateAssertionPredicateNode* template_assertion_predicate_expression,
    const bool does_overflow, const AssertionPredicateType assertion_predicate_type) const {
  AssertionPredicateIfCreator assertion_predicate_if_creator(_phase);
  return assertion_predicate_if_creator.create_for_template(new_control, does_overflow ? Op_If : Op_RangeCheck,
                                                            template_assertion_predicate_expression,
                                                            assertion_predicate_type);
}

// Creates an init and last value Template Assertion Predicate connected together with a Halt node on the failing path.
// Returns the success projection of the last value Template Assertion Predicate latter.
IfTrueNode* TemplateAssertionPredicateCreator::create(Node* new_control) const {
  OpaqueLoopInitNode* opaque_init = create_opaque_init(new_control);
  bool does_overflow;
  OpaqueTemplateAssertionPredicateNode* template_assertion_predicate_expression =
      create_for_init_value(new_control, opaque_init, does_overflow);
  IfTrueNode* template_predicate_success_proj =
      create_if_node(new_control, template_assertion_predicate_expression, does_overflow,
                     AssertionPredicateType::InitValue);
  DEBUG_ONLY(TemplateAssertionPredicate::verify(template_predicate_success_proj);)

  template_assertion_predicate_expression = create_for_last_value(template_predicate_success_proj, opaque_init,
                                                                  does_overflow);
  template_predicate_success_proj = create_if_node(template_predicate_success_proj,
                                                   template_assertion_predicate_expression, does_overflow,
                                                   AssertionPredicateType::LastValue);
  DEBUG_ONLY(TemplateAssertionPredicate::verify(template_predicate_success_proj);)
  return template_predicate_success_proj;
}

InitializedAssertionPredicateCreator::InitializedAssertionPredicateCreator(PhaseIdealLoop* phase)
    : _phase(phase) {}

// Create an Initialized Assertion Predicate from the provided template_assertion_predicate at 'new_control'.
// We clone the Template Assertion Expression and replace:
// - OpaqueTemplateAssertionPredicateNode with OpaqueInitializedAssertionPredicate
// - OpaqueLoop*Nodes with new_init and new_stride, respectively.
//
//             /         init                 stride
//             |           |                    |
//             |  OpaqueLoopInitNode  OpaqueLoopStrideNode                        /        new_init    new_stride
//  Template   |                 \     /                                          |              \     /
//  Assertion  |                   ...                                 Assertion  |                ...
//  Expression |                    |                                  Expression |                 |
//             |                   Bool                                           |              new Bool
//             |                    |                                             |                 |
//             \      OpaqueTemplateAssertionPredicate    ===>    new_control     \  OpaqueInitializedAssertionPredicate
//                                  |                                        \      /
//                                 If                                         new If
//                               /    \                                       /    \
//                         success     fail path                     new success   new Halt
//                           proj    (Halt or UCT)                       proj
//
InitializedAssertionPredicate InitializedAssertionPredicateCreator::create_from_template(
    const IfNode* template_assertion_predicate, Node* new_control, Node* new_init, Node* new_stride) const {
  OpaqueInitializedAssertionPredicateNode* assertion_expression =
      create_assertion_expression_from_template(template_assertion_predicate, new_control, new_init, new_stride);
   IfTrueNode* success_proj = create_control_nodes(new_control,
                                                   template_assertion_predicate->Opcode(),
                                                   assertion_expression,
                                                   template_assertion_predicate->assertion_predicate_type());
  return InitializedAssertionPredicate(success_proj);
}

// Create a new Initialized Assertion Predicate from the provided Template Assertion Predicate at the template success
// projection by cloning it but omitting the OpaqueLoop*Notes (i.e. taking their inputs instead).
InitializedAssertionPredicate InitializedAssertionPredicateCreator::create_from_template_and_insert_below(
    const TemplateAssertionPredicate& template_assertion_predicate) const {
  TemplateAssertionExpression template_assertion_expression(template_assertion_predicate.opaque_node(), _phase);
  IfTrueNode* template_assertion_predicate_success_proj = template_assertion_predicate.tail();
  OpaqueInitializedAssertionPredicateNode* assertion_expression =
      template_assertion_expression.clone_and_fold_opaque_loop_nodes(template_assertion_predicate_success_proj);

  IfNode* template_assertion_predicate_if = template_assertion_predicate.head();
  AssertionPredicateType assertion_predicate_type = template_assertion_predicate_if->assertion_predicate_type();
  int if_opcode = template_assertion_predicate_if->Opcode();
  IfTrueNode* success_proj = create_control_nodes(template_assertion_predicate_success_proj, if_opcode,
                                                  assertion_expression, assertion_predicate_type);
  return InitializedAssertionPredicate(success_proj);
}

// Create a new Initialized Assertion Predicate directly without a template.
IfTrueNode* InitializedAssertionPredicateCreator::create(Node* operand, Node* new_control, const jint stride,
                                                         const int scale, Node* offset, Node* range,
                                                         const AssertionPredicateType assertion_predicate_type) const {
  AssertionPredicateExpressionCreator expression_creator(stride, scale, offset, range, _phase);
  bool does_overflow;
  OpaqueInitializedAssertionPredicateNode* assertion_expression =
      expression_creator.create_for_initialized(new_control, operand, does_overflow);
  IfTrueNode* success_proj = create_control_nodes(new_control, does_overflow ? Op_If : Op_RangeCheck,
                                                  assertion_expression, assertion_predicate_type);
  DEBUG_ONLY(InitializedAssertionPredicate::verify(success_proj);)
  return success_proj;
}

// Creates the CFG nodes for the Initialized Assertion Predicate.
IfTrueNode* InitializedAssertionPredicateCreator::create_control_nodes(
    Node* new_control, const int if_opcode, OpaqueInitializedAssertionPredicateNode* assertion_expression,
    const AssertionPredicateType assertion_predicate_type) const {
  AssertionPredicateIfCreator assertion_predicate_if_creator(_phase);
  return assertion_predicate_if_creator.create_for_initialized(new_control, if_opcode, assertion_expression,
                                                               assertion_predicate_type);
}

// Create a new Assertion Expression based from the given template to be used as bool input for the Initialized
// Assertion Predicate IfNode.
OpaqueInitializedAssertionPredicateNode*
InitializedAssertionPredicateCreator::create_assertion_expression_from_template(const IfNode* template_assertion_predicate,
                                                                                Node* new_control, Node* new_init,
                                                                                Node* new_stride) const {
  OpaqueTemplateAssertionPredicateNode* template_opaque =
      template_assertion_predicate->in(1)->as_OpaqueTemplateAssertionPredicate();
  TemplateAssertionExpression template_assertion_expression(template_opaque, _phase);
  OpaqueTemplateAssertionPredicateNode* tmp_opaque =
      template_assertion_expression.clone_and_replace_init_and_stride(new_control, new_init, new_stride);
  OpaqueInitializedAssertionPredicateNode* assertion_expression =
      new OpaqueInitializedAssertionPredicateNode(tmp_opaque->in(1)->as_Bool(), _phase->C);
  _phase->register_new_node(assertion_expression, new_control);
  return assertion_expression;
}

#ifndef PRODUCT
void PredicateBlock::dump() const {
  dump("");
}

void PredicateBlock::dump(const char* prefix) const {
  if (is_non_empty()) {
    PredicatePrinter printer(prefix);
    PredicateBlockIterator iterator(_tail, _deopt_reason);
    iterator.for_each(printer);
  } else {
    tty->print_cr("%s- <empty>", prefix);
  }
}

// Dumps all predicates from the loop to the earliest predicate in a pretty format.
void Predicates::dump() const {
  if (has_any()) {
    Node* loop_head = _tail->unique_ctrl_out();
    tty->print_cr("%d %s:", loop_head->_idx, loop_head->Name());
    tty->print_cr("- Loop Limit Check Predicate Block:");
    _loop_limit_check_predicate_block.dump("  ");
    tty->print_cr("- Auto Vectorization Check Block:");
    _auto_vectorization_check_block.dump("  ");
    tty->print_cr("- Profiled Loop Predicate Block:");
    _profiled_loop_predicate_block.dump("  ");
    tty->print_cr("- Loop Predicate Block:");
    _loop_predicate_block.dump("  ");
    tty->cr();
  } else {
    tty->print_cr("<no predicates>");
  }
}

void Predicates::dump_at(Node* node) {
  Predicates predicates(node);
  predicates.dump();
}

// Debug method to dump all predicates that are found above 'loop_node'.
void Predicates::dump_for_loop(LoopNode* loop_node) {
  dump_at(loop_node->skip_strip_mined()->in(LoopNode::EntryControl));
}
#endif // NOT PRODUCT

CreateAssertionPredicatesVisitor::CreateAssertionPredicatesVisitor(CountedLoopNode* target_loop_head,
                                                                   PhaseIdealLoop* phase,
                                                                   const NodeInLoopBody& node_in_loop_body,
                                                                   bool kill_old_template)
    : _init(target_loop_head->init_trip()),
      _stride(target_loop_head->stride()),
      _target_loop_head(target_loop_head),
      _old_target_loop_entry(target_loop_head->skip_strip_mined()->in(LoopNode::EntryControl)),
      _current_predicate_chain_head(target_loop_head->skip_strip_mined()), // Initially no predicates, yet.
      _phase(phase),
      _node_in_loop_body(node_in_loop_body),
      _kill_old_template(kill_old_template) {}

// Clone Template Assertion Predicate and create an Initialized Assertion Predicate from it.
void CreateAssertionPredicatesVisitor::visit(const TemplateAssertionPredicate& template_assertion_predicate) {
  TemplateAssertionPredicate cloned_template_assertion_predicate =
      clone_template_and_replace_init_input(template_assertion_predicate);
  initialize_from_template(template_assertion_predicate, cloned_template_assertion_predicate.tail());
  _current_predicate_chain_head = cloned_template_assertion_predicate.head();
  if (_kill_old_template) {
    template_assertion_predicate.kill(_phase->igvn());
  }
}

// Create an Initialized Assertion Predicate from the provided Template Assertion Predicate.
InitializedAssertionPredicate CreateAssertionPredicatesVisitor::initialize_from_template(
  const TemplateAssertionPredicate& template_assertion_predicate, IfTrueNode* cloned_template_predicate_tail) const {
  DEBUG_ONLY(template_assertion_predicate.verify();)
  IfNode* template_head = template_assertion_predicate.head();
  InitializedAssertionPredicateCreator initialized_assertion_predicate_creator(_phase);
  InitializedAssertionPredicate initialized_assertion_predicate =
      initialized_assertion_predicate_creator.create_from_template(template_head, cloned_template_predicate_tail, _init,
                                                                   _stride);

  DEBUG_ONLY(initialized_assertion_predicate.verify();)
  template_assertion_predicate.rewire_loop_data_dependencies(cloned_template_predicate_tail,
                                                             _node_in_loop_body, _phase);
  rewire_to_old_predicate_chain_head(initialized_assertion_predicate.tail());
  return initialized_assertion_predicate;
}

// Clone the provided Template Assertion Predicate and set '_init' as new input for the OpaqueLoopInitNode.
TemplateAssertionPredicate CreateAssertionPredicatesVisitor::clone_template_and_replace_init_input(
    const TemplateAssertionPredicate& template_assertion_predicate) const {
  TemplateAssertionPredicate new_template =
      template_assertion_predicate.clone_and_replace_opaque_input(_old_target_loop_entry, _init, _target_loop_head,
                                                                  _phase);
  return new_template;
}

// Rewire the newly created predicates to the old predicate chain head (i.e. '_current_predicate_chain_head') by
// rewiring the current control input of '_current_predicate_chain_head' from '_old_target_loop_entry' to
// 'initialized_assertion_predicate_success_proj'. This is required because we walk the predicate chain from the loop
// up and clone Template Assertion Predicates on the fly:
//
//          x
//          |                                               old target
//  Template Assertion                                      loop entry
//     Predicate 1            old target         clone           |    \
//          |                 loop entry         TAP 2           |     cloned Template Assertion
//  Template Assertion             |            ======>          |            Predicate 2
//     Predicate 2            target loop                        |
//          |                                               target loop #_current_predicate_chain_head
//     source loop
//
//
//               old target                                                        old target
//               loop entry                                                        loop entry
//                    |    \                                 rewire                     |
//                    |    cloned Template Assertion         to old         cloned Template Assertion #current_predicate
//   initialize       |           Predicate 2               predicate              Predicate 2         _chain_head (new)
//     TAP 2          |               |                     chain head                  |
//    ======>         |      Initialized Assertion           ======>           Initialized Assertion
//                    |          Predicate 2                                        Predicate 2
//                    |                                                                 |
//               target loop #_current_predicate_chain_head                        target loop
//
void CreateAssertionPredicatesVisitor::rewire_to_old_predicate_chain_head(
    Node* initialized_assertion_predicate_success_proj) const {
  if (_current_predicate_chain_head->is_Loop()) {
    assert(_current_predicate_chain_head->in(LoopNode::EntryControl) == _old_target_loop_entry, "must be old loop entry");
    _phase->replace_loop_entry(_current_predicate_chain_head->as_Loop(), initialized_assertion_predicate_success_proj);
  } else {
    assert(_current_predicate_chain_head->in(0) == _old_target_loop_entry, "must be old loop entry");
    _phase->replace_control(_current_predicate_chain_head, initialized_assertion_predicate_success_proj);
  }
}

TargetLoopPredicateChain::TargetLoopPredicateChain(LoopNode* loop_head, PhaseIdealLoop* phase)
    : DEBUG_ONLY(_old_target_loop_entry(loop_head->in(LoopNode::EntryControl)) COMMA)
      DEBUG_ONLY(_node_index_before_cloning(phase->C->unique()) COMMA)
      _current_predicate_chain_head(loop_head),
      _phase(phase) {}

// Inserts the provided newly cloned predicate to the head of the target loop predicate chain.
void TargetLoopPredicateChain::insert_predicate(const Predicate& predicate) {
  rewire_to_target_chain_head(predicate.tail()->as_IfTrue());
  _current_predicate_chain_head = predicate.head();
  assert(predicate.head()->_idx >= _node_index_before_cloning, "must be a newly cloned predicate");
  assert(predicate.tail()->_idx >= _node_index_before_cloning, "must be a newly cloned predicate");
  assert(_current_predicate_chain_head->in(0) == _old_target_loop_entry &&
         _old_target_loop_entry->unique_ctrl_out() == _current_predicate_chain_head , "must be connected now");
}

void TargetLoopPredicateChain::rewire_to_target_chain_head(IfTrueNode* template_assertion_predicate_success_proj) const {
  if (_current_predicate_chain_head->is_Loop()) {
    _phase->replace_loop_entry(_current_predicate_chain_head->as_Loop(), template_assertion_predicate_success_proj);
  } else {
    _phase->replace_control(_current_predicate_chain_head, template_assertion_predicate_success_proj);
  }
}

ClonePredicateToTargetLoop::ClonePredicateToTargetLoop(LoopNode* target_loop_head, const NodeInLoopBody& node_in_loop_body,
                                                       PhaseIdealLoop* phase)
    : _target_loop_head(target_loop_head),
      _target_outer_loop_head(target_loop_head->skip_strip_mined()),
      _old_target_loop_entry(_target_outer_loop_head->in(LoopNode::EntryControl)),
      _target_loop_predicate_chain(_target_outer_loop_head, phase),
      _node_in_loop_body(node_in_loop_body),
      _phase(phase) {}

// Clones the provided Template Assertion Predicate to the head of the current predicate chain at the target loop.
void ClonePredicateToTargetLoop::clone_template_assertion_predicate(
    const TemplateAssertionPredicate& template_assertion_predicate) {
  TemplateAssertionPredicate cloned_template_assertion_predicate =
      template_assertion_predicate.clone(_old_target_loop_entry, _target_loop_head->as_CountedLoop(), _phase);
  template_assertion_predicate.rewire_loop_data_dependencies(cloned_template_assertion_predicate.tail(),
                                                             _node_in_loop_body, _phase);
  _target_loop_predicate_chain.insert_predicate(cloned_template_assertion_predicate);
}

CloneUnswitchedLoopPredicatesVisitor::CloneUnswitchedLoopPredicatesVisitor(
    LoopNode* true_path_loop_head, LoopNode* false_path_loop_head,
    const NodeInOriginalLoopBody& node_in_true_path_loop_body, const NodeInClonedLoopBody& node_in_false_path_loop_body,
    PhaseIdealLoop* phase)
    : _clone_predicate_to_true_path_loop(true_path_loop_head, node_in_true_path_loop_body, phase),
      _clone_predicate_to_false_path_loop(false_path_loop_head, node_in_false_path_loop_body, phase),
      _phase(phase),
      _is_counted_loop(true_path_loop_head->is_CountedLoop()) {}

// The PredicateIterator will always start at the loop entry and first visits the Loop Limit Check Predicate Block.
// Does not clone a Loop Limit Check Parse Predicate if a counted loop is unswitched, because it most likely will not be
// used anymore (it could only be used when both unswitched loop versions die and the Loop Limit Check Parse Predicate
// ends up at a LoopNode without Loop Limit Check Parse Predicate directly following the unswitched loop that can then
// be speculatively converted to a counted loop - this is rather rare).
void CloneUnswitchedLoopPredicatesVisitor::visit(const ParsePredicate& parse_predicate) {
  Deoptimization::DeoptReason deopt_reason = parse_predicate.head()->deopt_reason();
  if (_is_counted_loop && deopt_reason == Deoptimization::Reason_loop_limit_check) {
    return;
  }
  _clone_predicate_to_true_path_loop.clone_parse_predicate(parse_predicate, false);
  _clone_predicate_to_false_path_loop.clone_parse_predicate(parse_predicate, true);
  parse_predicate.kill(_phase->igvn());
}

// Clone the Template Assertion Predicate, which is currently found before the newly added unswitched loop selector,
// to the true path and false path loop.
void CloneUnswitchedLoopPredicatesVisitor::visit(const TemplateAssertionPredicate& template_assertion_predicate) {
  _clone_predicate_to_true_path_loop.clone_template_assertion_predicate(template_assertion_predicate);
  _clone_predicate_to_false_path_loop.clone_template_assertion_predicate(template_assertion_predicate);
  template_assertion_predicate.kill(_phase->igvn());
}

// Update the Template Assertion Predicate by setting a new input for the OpaqueLoopStrideNode. Create a new
// Initialized Assertion Predicate from the updated Template Assertion Predicate.
void UpdateStrideForAssertionPredicates::visit(const TemplateAssertionPredicate& template_assertion_predicate) {
  if (!template_assertion_predicate.is_last_value()) {
    // Only Last Value Assertion Predicates have an OpaqueLoopStrideNode.
    return;
  }
  replace_opaque_stride_input(template_assertion_predicate);
  template_assertion_predicate.update_associated_loop_node(_loop_node);
  Node* template_tail_control_out = template_assertion_predicate.tail()->unique_ctrl_out();
  InitializedAssertionPredicate initialized_assertion_predicate =
      initialize_from_updated_template(template_assertion_predicate);
  connect_initialized_assertion_predicate(template_tail_control_out, initialized_assertion_predicate);
}

// Kill the old Initialized Assertion Predicates with old strides before unrolling. The new Initialized Assertion
// Predicates are inserted after the Template Assertion Predicate which ensures that we are not accidentally visiting
// and killing a newly created Initialized Assertion Predicate here.
void UpdateStrideForAssertionPredicates::visit(const InitializedAssertionPredicate& initialized_assertion_predicate) {
  if (initialized_assertion_predicate.is_last_value()) {
    // Only Last Value Initialized Assertion Predicates need to be killed and updated.
    initialized_assertion_predicate.kill(_phase->igvn());
  }
}

// Replace the input to OpaqueLoopStrideNode with 'new_stride' and leave the other nodes unchanged.
void UpdateStrideForAssertionPredicates::replace_opaque_stride_input(
    const TemplateAssertionPredicate& template_assertion_predicate) const {
  template_assertion_predicate.replace_opaque_stride_input(_new_stride, _phase->igvn());
}

InitializedAssertionPredicate UpdateStrideForAssertionPredicates::initialize_from_updated_template(
    const TemplateAssertionPredicate& template_assertion_predicate) const {
  return template_assertion_predicate.initialize(_phase);
}

// The newly created Initialized Assertion Predicate can safely be inserted because this visitor is already visiting
// the Template Assertion Predicate above this. So, we will not accidentally visit this again and kill it with the
// visit() method for Initialized Assertion Predicates.
void UpdateStrideForAssertionPredicates::connect_initialized_assertion_predicate(
    Node* new_control_out, const InitializedAssertionPredicate& initialized_assertion_predicate) const {
  Node* initialized_assertion_predicate_success_proj = initialized_assertion_predicate.tail();
  if (new_control_out->is_Loop()) {
    _phase->replace_loop_entry(new_control_out->as_Loop(), initialized_assertion_predicate_success_proj);
  } else {
    _phase->replace_control(new_control_out, initialized_assertion_predicate_success_proj);
  }
}

// Do the following to find and eliminate useless Parse and Template Assertion Predicates:
// 1. Mark all Parse and Template Assertion Predicates "maybe useful".
// 2. Walk through the loop tree and iterate over all Predicates above each loop head. All found Parse and Template
//    Assertion Predicates are marked "useful".
// 3. Those Parse and Template Assertion Predicates that are still marked "maybe useful" are now marked "useless" and
//    removed in the next round of IGVN.
//
// Note that we only mark Predicates useless and not actually replace them now. We leave this work for IGVN which is
// better suited for this kind of graph surgery. We also not want to replace conditions with a constant to avoid
// interference with Predicate matching code when iterating through them.
void EliminateUselessPredicates::eliminate() const {
  mark_all_predicates_maybe_useful();
  if (C->has_loops()) {
    mark_loop_associated_predicates_useful();
  }
  mark_maybe_useful_predicates_useless();
}

void EliminateUselessPredicates::mark_all_predicates_maybe_useful() const {
  mark_predicates_on_list_maybe_useful(_parse_predicates);
  mark_predicates_on_list_maybe_useful(_template_assertion_predicate_opaques);
}

template<class PredicateList>
void EliminateUselessPredicates::mark_predicates_on_list_maybe_useful(const PredicateList& predicate_list) {
  for (int i = 0; i < predicate_list.length(); i++) {
    predicate_list.at(i)->mark_maybe_useful();
  }
}

void EliminateUselessPredicates::mark_loop_associated_predicates_useful() const {
  for (LoopTreeIterator iterator(_ltree_root); !iterator.done(); iterator.next()) {
    IdealLoopTree* loop = iterator.current();
    if (loop->can_apply_loop_predication()) {
      mark_useful_predicates_for_loop(loop);
    }
  }
}

// This visitor marks all visited Parse and Template Assertion Predicates useful.
class PredicateUsefulMarkerVisitor : public PredicateVisitor {
  LoopNode* const _loop_node; // The loop node from which we currently iterate through the Predicates.

 public:
  explicit PredicateUsefulMarkerVisitor(LoopNode* loop_node) : _loop_node(loop_node) {}
  NONCOPYABLE(PredicateUsefulMarkerVisitor);

  using PredicateVisitor::visit;

  void visit(const ParsePredicate& parse_predicate) override {
    parse_predicate.head()->mark_useful();
  }

  // If the stored loop node does not match the current loop node from which we iterate from, we found a Template
  // Assertion Predicate belonging to an already earlier folded loop in the graph. We mark it useless to drop this
  // Template Assertion Predicate because we are no longer splitting a loop which it belongs to. Moreover, if we do not
  // remove this Template Assertion Predicate, we could wrongly be creating Initialized Assertion Predicates from it at
  // the new loop which has completely unrelated loop values. These Initialized Assertion Predicates can then fail at
  // runtime, and we crash by executing a halt instruction.
  void visit(const TemplateAssertionPredicate& template_assertion_predicate) override {
    OpaqueTemplateAssertionPredicateNode* opaque_node = template_assertion_predicate.opaque_node();
    if (opaque_node->loop_node() == _loop_node) {
      // We actually mark the associated OpaqueTemplateAssertionPredicate node useful.
      template_assertion_predicate.opaque_node()->mark_useful();
    }
  }
};

void EliminateUselessPredicates::mark_useful_predicates_for_loop(IdealLoopTree* loop) {
  LoopNode* loop_node = loop->_head->as_Loop();
  Node* loop_entry = loop_node->skip_strip_mined()->in(LoopNode::EntryControl);
  const PredicateIterator predicate_iterator(loop_entry);
  PredicateUsefulMarkerVisitor predicate_useful_marker_visitor(loop_node);
  predicate_iterator.for_each(predicate_useful_marker_visitor);
}

// All Predicates still being marked MaybeUseful could not be found and thus are now marked useless.
void EliminateUselessPredicates::mark_maybe_useful_predicates_useless() const {
  mark_maybe_useful_predicates_on_list_useless(_parse_predicates);
  mark_maybe_useful_predicates_on_list_useless(_template_assertion_predicate_opaques);
  DEBUG_ONLY(verify_loop_nodes_of_useless_templates_assertion_predicates_are_dead();)
}

#ifdef ASSERT
// All now useless Template Assertion Predicates should not refer to any CountedLoopNode that can still be found in the
// graph (otherwise, they would have been marked useful instead). This is verified in this method.
void EliminateUselessPredicates::verify_loop_nodes_of_useless_templates_assertion_predicates_are_dead() const {
  ResourceMark rm;
  Unique_Node_List loop_nodes_of_useless_template_assertion_predicates =
       collect_loop_nodes_of_useless_template_assertion_predicates();
  verify_associated_loop_nodes_are_dead(loop_nodes_of_useless_template_assertion_predicates);
}

Unique_Node_List EliminateUselessPredicates::collect_loop_nodes_of_useless_template_assertion_predicates() const {
  Unique_Node_List loop_nodes_of_useless_template_assertion_predicates;
  for (int i = 0; i < _template_assertion_predicate_opaques.length(); i++) {
    OpaqueTemplateAssertionPredicateNode* opaque_node = _template_assertion_predicate_opaques.at(i);
    if (opaque_node->is_useless()) {
      loop_nodes_of_useless_template_assertion_predicates.push(opaque_node->loop_node());
    }
  }
  return loop_nodes_of_useless_template_assertion_predicates;
}

void EliminateUselessPredicates::verify_associated_loop_nodes_are_dead(
    const Unique_Node_List& loop_nodes_of_useless_template_assertion_predicates) const {
  if (loop_nodes_of_useless_template_assertion_predicates.size() == 0) {
    return;
  }
  for (LoopTreeIterator iterator(_ltree_root); !iterator.done(); iterator.next()) {
    IdealLoopTree* loop = iterator.current();
    Node* loop_head = loop->head();
    if (loop_head->is_CountedLoop()) {
      assert(!loop_nodes_of_useless_template_assertion_predicates.member(loop_head),
             "CountedLoopNode should be dead when found in OpaqueTemplateAssertionPredicateNode being marked useless");
    }
  }
}
#endif // ASSERT

template<class PredicateList>
void EliminateUselessPredicates::mark_maybe_useful_predicates_on_list_useless(
    const PredicateList& predicate_list) const {
  for (int i = 0; i < predicate_list.length(); i++) {
    auto predicate_node = predicate_list.at(i);
    if (!predicate_node->is_useful()) {
      predicate_node->mark_useless(_igvn);
    }
  }
}