loopnode.cpp

/*
 * Copyright (c) 1998, 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 "ci/ciMethodData.hpp"
#include "compiler/compileLog.hpp"
#include "gc/shared/barrierSet.hpp"
#include "gc/shared/c2/barrierSetC2.hpp"
#include "libadt/vectset.hpp"
#include "memory/allocation.inline.hpp"
#include "memory/resourceArea.hpp"
#include "opto/addnode.hpp"
#include "opto/arraycopynode.hpp"
#include "opto/callnode.hpp"
#include "opto/castnode.hpp"
#include "opto/connode.hpp"
#include "opto/convertnode.hpp"
#include "opto/divnode.hpp"
#include "opto/idealGraphPrinter.hpp"
#include "opto/loopnode.hpp"
#include "opto/movenode.hpp"
#include "opto/mulnode.hpp"
#include "opto/opaquenode.hpp"
#include "opto/opcodes.hpp"
#include "opto/predicates.hpp"
#include "opto/rootnode.hpp"
#include "opto/runtime.hpp"
#include "opto/vectorization.hpp"
#include "runtime/sharedRuntime.hpp"
#include "utilities/checkedCast.hpp"
#include "utilities/powerOfTwo.hpp"

//=============================================================================
//--------------------------is_cloop_ind_var-----------------------------------
// Determine if a node is a counted loop induction variable.
// NOTE: The method is declared in "node.hpp".
bool Node::is_cloop_ind_var() const {
  return (is_Phi() &&
          as_Phi()->region()->is_CountedLoop() &&
          as_Phi()->region()->as_CountedLoop()->phi() == this);
}

//=============================================================================
//------------------------------dump_spec--------------------------------------
// Dump special per-node info
#ifndef PRODUCT
void LoopNode::dump_spec(outputStream *st) const {
  RegionNode::dump_spec(st);
  if (is_inner_loop()) st->print( "inner " );
  if (is_partial_peel_loop()) st->print( "partial_peel " );
  if (partial_peel_has_failed()) st->print( "partial_peel_failed " );
}
#endif

//------------------------------is_valid_counted_loop-------------------------
bool LoopNode::is_valid_counted_loop(BasicType bt) const {
  if (is_BaseCountedLoop() && as_BaseCountedLoop()->bt() == bt) {
    BaseCountedLoopNode*    l  = as_BaseCountedLoop();
    BaseCountedLoopEndNode* le = l->loopexit_or_null();
    if (le != nullptr &&
        le->proj_out_or_null(1 /* true */) == l->in(LoopNode::LoopBackControl)) {
      Node* phi  = l->phi();
      Node* exit = le->proj_out_or_null(0 /* false */);
      if (exit != nullptr && exit->Opcode() == Op_IfFalse &&
          phi != nullptr && phi->is_Phi() &&
          phi->in(LoopNode::LoopBackControl) == l->incr() &&
          le->loopnode() == l && le->stride_is_con()) {
        return true;
      }
    }
  }
  return false;
}

//------------------------------get_early_ctrl---------------------------------
// Compute earliest legal control
Node *PhaseIdealLoop::get_early_ctrl( Node *n ) {
  assert( !n->is_Phi() && !n->is_CFG(), "this code only handles data nodes" );
  uint i;
  Node *early;
  if (n->in(0) && !n->is_expensive()) {
    early = n->in(0);
    if (!early->is_CFG()) // Might be a non-CFG multi-def
      early = get_ctrl(early);        // So treat input as a straight data input
    i = 1;
  } else {
    early = get_ctrl(n->in(1));
    i = 2;
  }
  uint e_d = dom_depth(early);
  assert( early, "" );
  for (; i < n->req(); i++) {
    Node *cin = get_ctrl(n->in(i));
    assert( cin, "" );
    // Keep deepest dominator depth
    uint c_d = dom_depth(cin);
    if (c_d > e_d) {           // Deeper guy?
      early = cin;              // Keep deepest found so far
      e_d = c_d;
    } else if (c_d == e_d &&    // Same depth?
               early != cin) { // If not equal, must use slower algorithm
      // If same depth but not equal, one _must_ dominate the other
      // and we want the deeper (i.e., dominated) guy.
      Node *n1 = early;
      Node *n2 = cin;
      while (1) {
        n1 = idom(n1);          // Walk up until break cycle
        n2 = idom(n2);
        if (n1 == cin ||        // Walked early up to cin
            dom_depth(n2) < c_d)
          break;                // early is deeper; keep him
        if (n2 == early ||      // Walked cin up to early
            dom_depth(n1) < c_d) {
          early = cin;          // cin is deeper; keep him
          break;
        }
      }
      e_d = dom_depth(early);   // Reset depth register cache
    }
  }

  // Return earliest legal location
  assert(early == find_non_split_ctrl(early), "unexpected early control");

  if (n->is_expensive() && !_verify_only && !_verify_me) {
    assert(n->in(0), "should have control input");
    early = get_early_ctrl_for_expensive(n, early);
  }

  return early;
}

//------------------------------get_early_ctrl_for_expensive---------------------------------
// Move node up the dominator tree as high as legal while still beneficial
Node *PhaseIdealLoop::get_early_ctrl_for_expensive(Node *n, Node* earliest) {
  assert(n->in(0) && n->is_expensive(), "expensive node with control input here");
  assert(OptimizeExpensiveOps, "optimization off?");

  Node* ctl = n->in(0);
  assert(ctl->is_CFG(), "expensive input 0 must be cfg");
  uint min_dom_depth = dom_depth(earliest);
#ifdef ASSERT
  if (!is_dominator(ctl, earliest) && !is_dominator(earliest, ctl)) {
    dump_bad_graph("Bad graph detected in get_early_ctrl_for_expensive", n, earliest, ctl);
    assert(false, "Bad graph detected in get_early_ctrl_for_expensive");
  }
#endif
  if (dom_depth(ctl) < min_dom_depth) {
    return earliest;
  }

  while (true) {
    Node* next = ctl;
    // Moving the node out of a loop on the projection of an If
    // confuses Loop Predication. So, once we hit a loop in an If branch
    // that doesn't branch to an UNC, we stop. The code that process
    // expensive nodes will notice the loop and skip over it to try to
    // move the node further up.
    if (ctl->is_CountedLoop() && ctl->in(1) != nullptr && ctl->in(1)->in(0) != nullptr && ctl->in(1)->in(0)->is_If()) {
      if (!ctl->in(1)->as_Proj()->is_uncommon_trap_if_pattern()) {
        break;
      }
      next = idom(ctl->in(1)->in(0));
    } else if (ctl->is_Proj()) {
      // We only move it up along a projection if the projection is
      // the single control projection for its parent: same code path,
      // if it's a If with UNC or fallthrough of a call.
      Node* parent_ctl = ctl->in(0);
      if (parent_ctl == nullptr) {
        break;
      } else if (parent_ctl->is_CountedLoopEnd() && parent_ctl->as_CountedLoopEnd()->loopnode() != nullptr) {
        next = parent_ctl->as_CountedLoopEnd()->loopnode()->init_control();
      } else if (parent_ctl->is_If()) {
        if (!ctl->as_Proj()->is_uncommon_trap_if_pattern()) {
          break;
        }
        assert(idom(ctl) == parent_ctl, "strange");
        next = idom(parent_ctl);
      } else if (ctl->is_CatchProj()) {
        if (ctl->as_Proj()->_con != CatchProjNode::fall_through_index) {
          break;
        }
        assert(parent_ctl->in(0)->in(0)->is_Call(), "strange graph");
        next = parent_ctl->in(0)->in(0)->in(0);
      } else {
        // Check if parent control has a single projection (this
        // control is the only possible successor of the parent
        // control). If so, we can try to move the node above the
        // parent control.
        int nb_ctl_proj = 0;
        for (DUIterator_Fast imax, i = parent_ctl->fast_outs(imax); i < imax; i++) {
          Node *p = parent_ctl->fast_out(i);
          if (p->is_Proj() && p->is_CFG()) {
            nb_ctl_proj++;
            if (nb_ctl_proj > 1) {
              break;
            }
          }
        }

        if (nb_ctl_proj > 1) {
          break;
        }
        assert(parent_ctl->is_Start() || parent_ctl->is_MemBar() || parent_ctl->is_Call() ||
               BarrierSet::barrier_set()->barrier_set_c2()->is_gc_barrier_node(parent_ctl), "unexpected node");
        assert(idom(ctl) == parent_ctl, "strange");
        next = idom(parent_ctl);
      }
    } else {
      next = idom(ctl);
    }
    if (next->is_Root() || next->is_Start() || dom_depth(next) < min_dom_depth) {
      break;
    }
    ctl = next;
  }

  if (ctl != n->in(0)) {
    _igvn.replace_input_of(n, 0, ctl);
    _igvn.hash_insert(n);
  }

  return ctl;
}


//------------------------------set_early_ctrl---------------------------------
// Set earliest legal control
void PhaseIdealLoop::set_early_ctrl(Node* n, bool update_body) {
  Node *early = get_early_ctrl(n);

  // Record earliest legal location
  set_ctrl(n, early);
  IdealLoopTree *loop = get_loop(early);
  if (update_body && loop->_child == nullptr) {
    loop->_body.push(n);
  }
}

//------------------------------set_subtree_ctrl-------------------------------
// set missing _ctrl entries on new nodes
void PhaseIdealLoop::set_subtree_ctrl(Node* n, bool update_body) {
  // Already set?  Get out.
  if (_loop_or_ctrl[n->_idx]) return;
  // Recursively set _loop_or_ctrl array to indicate where the Node goes
  uint i;
  for (i = 0; i < n->req(); ++i) {
    Node *m = n->in(i);
    if (m && m != C->root()) {
      set_subtree_ctrl(m, update_body);
    }
  }

  // Fixup self
  set_early_ctrl(n, update_body);
}

IdealLoopTree* PhaseIdealLoop::insert_outer_loop(IdealLoopTree* loop, LoopNode* outer_l, Node* outer_ift) {
  IdealLoopTree* outer_ilt = new IdealLoopTree(this, outer_l, outer_ift);
  IdealLoopTree* parent = loop->_parent;
  IdealLoopTree* sibling = parent->_child;
  if (sibling == loop) {
    parent->_child = outer_ilt;
  } else {
    while (sibling->_next != loop) {
      sibling = sibling->_next;
    }
    sibling->_next = outer_ilt;
  }
  outer_ilt->_next = loop->_next;
  outer_ilt->_parent = parent;
  outer_ilt->_child = loop;
  outer_ilt->_nest = loop->_nest;
  loop->_parent = outer_ilt;
  loop->_next = nullptr;
  loop->_nest++;
  assert(loop->_nest <= SHRT_MAX, "sanity");
  return outer_ilt;
}

// Create a skeleton strip mined outer loop: a Loop head before the
// inner strip mined loop, a safepoint and an exit condition guarded
// by an opaque node after the inner strip mined loop with a backedge
// to the loop head. The inner strip mined loop is left as it is. Only
// once loop optimizations are over, do we adjust the inner loop exit
// condition to limit its number of iterations, set the outer loop
// exit condition and add Phis to the outer loop head. Some loop
// optimizations that operate on the inner strip mined loop need to be
// aware of the outer strip mined loop: loop unswitching needs to
// clone the outer loop as well as the inner, unrolling needs to only
// clone the inner loop etc. No optimizations need to change the outer
// strip mined loop as it is only a skeleton.
IdealLoopTree* PhaseIdealLoop::create_outer_strip_mined_loop(BoolNode *test, Node *cmp, Node *init_control,
                                                             IdealLoopTree* loop, float cl_prob, float le_fcnt,
                                                             Node*& entry_control, Node*& iffalse) {
  Node* outer_test = intcon(0);
  Node *orig = iffalse;
  iffalse = iffalse->clone();
  _igvn.register_new_node_with_optimizer(iffalse);
  set_idom(iffalse, idom(orig), dom_depth(orig));

  IfNode *outer_le = new OuterStripMinedLoopEndNode(iffalse, outer_test, cl_prob, le_fcnt);
  Node *outer_ift = new IfTrueNode (outer_le);
  Node* outer_iff = orig;
  _igvn.replace_input_of(outer_iff, 0, outer_le);

  LoopNode *outer_l = new OuterStripMinedLoopNode(C, init_control, outer_ift);
  entry_control = outer_l;

  IdealLoopTree* outer_ilt = insert_outer_loop(loop, outer_l, outer_ift);

  set_loop(iffalse, outer_ilt);
  // When this code runs, loop bodies have not yet been populated.
  const bool body_populated = false;
  register_control(outer_le, outer_ilt, iffalse, body_populated);
  register_control(outer_ift, outer_ilt, outer_le, body_populated);
  set_idom(outer_iff, outer_le, dom_depth(outer_le));
  _igvn.register_new_node_with_optimizer(outer_l);
  set_loop(outer_l, outer_ilt);
  set_idom(outer_l, init_control, dom_depth(init_control)+1);

  return outer_ilt;
}

void PhaseIdealLoop::insert_loop_limit_check_predicate(ParsePredicateSuccessProj* loop_limit_check_parse_proj,
                                                       Node* cmp_limit, Node* bol) {
  assert(loop_limit_check_parse_proj->in(0)->is_ParsePredicate(), "must be parse predicate");
  Node* new_predicate_proj = create_new_if_for_predicate(loop_limit_check_parse_proj, nullptr,
                                                         Deoptimization::Reason_loop_limit_check,
                                                         Op_If);
  Node* iff = new_predicate_proj->in(0);
  cmp_limit = _igvn.register_new_node_with_optimizer(cmp_limit);
  bol = _igvn.register_new_node_with_optimizer(bol);
  set_subtree_ctrl(bol, false);
  _igvn.replace_input_of(iff, 1, bol);

#ifndef PRODUCT
  // report that the loop predication has been actually performed
  // for this loop
  if (TraceLoopLimitCheck) {
    tty->print_cr("Counted Loop Limit Check generated:");
    DEBUG_ONLY( bol->dump(2); )
  }
#endif
}

Node* PhaseIdealLoop::loop_exit_control(Node* x, IdealLoopTree* loop) {
  // Counted loop head must be a good RegionNode with only 3 not null
  // control input edges: Self, Entry, LoopBack.
  if (x->in(LoopNode::Self) == nullptr || x->req() != 3 || loop->_irreducible) {
    return nullptr;
  }
  Node *init_control = x->in(LoopNode::EntryControl);
  Node *back_control = x->in(LoopNode::LoopBackControl);
  if (init_control == nullptr || back_control == nullptr) {   // Partially dead
    return nullptr;
  }
  // Must also check for TOP when looking for a dead loop
  if (init_control->is_top() || back_control->is_top()) {
    return nullptr;
  }

  // Allow funny placement of Safepoint
  if (back_control->Opcode() == Op_SafePoint) {
    back_control = back_control->in(TypeFunc::Control);
  }

  // Controlling test for loop
  Node *iftrue = back_control;
  uint iftrue_op = iftrue->Opcode();
  if (iftrue_op != Op_IfTrue &&
      iftrue_op != Op_IfFalse) {
    // I have a weird back-control.  Probably the loop-exit test is in
    // the middle of the loop and I am looking at some trailing control-flow
    // merge point.  To fix this I would have to partially peel the loop.
    return nullptr; // Obscure back-control
  }

  // Get boolean guarding loop-back test
  Node *iff = iftrue->in(0);
  if (get_loop(iff) != loop || !iff->in(1)->is_Bool()) {
    return nullptr;
  }
  return iftrue;
}

Node* PhaseIdealLoop::loop_exit_test(Node* back_control, IdealLoopTree* loop, Node*& incr, Node*& limit, BoolTest::mask& bt, float& cl_prob) {
  Node* iftrue = back_control;
  uint iftrue_op = iftrue->Opcode();
  Node* iff = iftrue->in(0);
  BoolNode* test = iff->in(1)->as_Bool();
  bt = test->_test._test;
  cl_prob = iff->as_If()->_prob;
  if (iftrue_op == Op_IfFalse) {
    bt = BoolTest(bt).negate();
    cl_prob = 1.0 - cl_prob;
  }
  // Get backedge compare
  Node* cmp = test->in(1);
  if (!cmp->is_Cmp()) {
    return nullptr;
  }

  // Find the trip-counter increment & limit.  Limit must be loop invariant.
  incr  = cmp->in(1);
  limit = cmp->in(2);

  // ---------
  // need 'loop()' test to tell if limit is loop invariant
  // ---------

  if (!is_member(loop, get_ctrl(incr))) { // Swapped trip counter and limit?
    Node* tmp = incr;            // Then reverse order into the CmpI
    incr = limit;
    limit = tmp;
    bt = BoolTest(bt).commute(); // And commute the exit test
  }
  if (is_member(loop, get_ctrl(limit))) { // Limit must be loop-invariant
    return nullptr;
  }
  if (!is_member(loop, get_ctrl(incr))) { // Trip counter must be loop-variant
    return nullptr;
  }
  return cmp;
}

Node* PhaseIdealLoop::loop_iv_incr(Node* incr, Node* x, IdealLoopTree* loop, Node*& phi_incr) {
  if (incr->is_Phi()) {
    if (incr->as_Phi()->region() != x || incr->req() != 3) {
      return nullptr; // Not simple trip counter expression
    }
    phi_incr = incr;
    incr = phi_incr->in(LoopNode::LoopBackControl); // Assume incr is on backedge of Phi
    if (!is_member(loop, get_ctrl(incr))) { // Trip counter must be loop-variant
      return nullptr;
    }
  }
  return incr;
}

Node* PhaseIdealLoop::loop_iv_stride(Node* incr, IdealLoopTree* loop, Node*& xphi) {
  assert(incr->Opcode() == Op_AddI || incr->Opcode() == Op_AddL, "caller resp.");
  // Get merge point
  xphi = incr->in(1);
  Node *stride = incr->in(2);
  if (!stride->is_Con()) {     // Oops, swap these
    if (!xphi->is_Con()) {     // Is the other guy a constant?
      return nullptr;          // Nope, unknown stride, bail out
    }
    Node *tmp = xphi;          // 'incr' is commutative, so ok to swap
    xphi = stride;
    stride = tmp;
  }
  return stride;
}

PhiNode* PhaseIdealLoop::loop_iv_phi(Node* xphi, Node* phi_incr, Node* x, IdealLoopTree* loop) {
  if (!xphi->is_Phi()) {
    return nullptr; // Too much math on the trip counter
  }
  if (phi_incr != nullptr && phi_incr != xphi) {
    return nullptr;
  }
  PhiNode *phi = xphi->as_Phi();

  // Phi must be of loop header; backedge must wrap to increment
  if (phi->region() != x) {
    return nullptr;
  }
  return phi;
}

static int check_stride_overflow(jlong final_correction, const TypeInteger* limit_t, BasicType bt) {
  if (final_correction > 0) {
    if (limit_t->lo_as_long() > (max_signed_integer(bt) - final_correction)) {
      return -1;
    }
    if (limit_t->hi_as_long() > (max_signed_integer(bt) - final_correction)) {
      return 1;
    }
  } else {
    if (limit_t->hi_as_long() < (min_signed_integer(bt) - final_correction)) {
      return -1;
    }
    if (limit_t->lo_as_long() < (min_signed_integer(bt) - final_correction)) {
      return 1;
    }
  }
  return 0;
}

static bool condition_stride_ok(BoolTest::mask bt, jlong stride_con) {
  // If the condition is inverted and we will be rolling
  // through MININT to MAXINT, then bail out.
  if (bt == BoolTest::eq || // Bail out, but this loop trips at most twice!
      // Odd stride
      (bt == BoolTest::ne && stride_con != 1 && stride_con != -1) ||
      // Count down loop rolls through MAXINT
      ((bt == BoolTest::le || bt == BoolTest::lt) && stride_con < 0) ||
      // Count up loop rolls through MININT
      ((bt == BoolTest::ge || bt == BoolTest::gt) && stride_con > 0)) {
    return false; // Bail out
  }
  return true;
}

Node* PhaseIdealLoop::loop_nest_replace_iv(Node* iv_to_replace, Node* inner_iv, Node* outer_phi, Node* inner_head,
                                           BasicType bt) {
  Node* iv_as_long;
  if (bt == T_LONG) {
    iv_as_long = new ConvI2LNode(inner_iv, TypeLong::INT);
    register_new_node(iv_as_long, inner_head);
  } else {
    iv_as_long = inner_iv;
  }
  Node* iv_replacement = AddNode::make(outer_phi, iv_as_long, bt);
  register_new_node(iv_replacement, inner_head);
  for (DUIterator_Last imin, i = iv_to_replace->last_outs(imin); i >= imin;) {
    Node* u = iv_to_replace->last_out(i);
#ifdef ASSERT
    if (!is_dominator(inner_head, ctrl_or_self(u))) {
      assert(u->is_Phi(), "should be a Phi");
      for (uint j = 1; j < u->req(); j++) {
        if (u->in(j) == iv_to_replace) {
          assert(is_dominator(inner_head, u->in(0)->in(j)), "iv use above loop?");
        }
      }
    }
#endif
    _igvn.rehash_node_delayed(u);
    int nb = u->replace_edge(iv_to_replace, iv_replacement, &_igvn);
    i -= nb;
  }
  return iv_replacement;
}

// Add a Parse Predicate with an uncommon trap on the failing/false path. Normal control will continue on the true path.
void PhaseIdealLoop::add_parse_predicate(Deoptimization::DeoptReason reason, Node* inner_head, IdealLoopTree* loop,
                                         SafePointNode* sfpt) {
  if (!C->too_many_traps(reason)) {
    ParsePredicateNode* parse_predicate = new ParsePredicateNode(inner_head->in(LoopNode::EntryControl), reason, &_igvn);
    register_control(parse_predicate, loop, inner_head->in(LoopNode::EntryControl));
    Node* if_false = new IfFalseNode(parse_predicate);
    register_control(if_false, _ltree_root, parse_predicate);
    Node* if_true = new IfTrueNode(parse_predicate);
    register_control(if_true, loop, parse_predicate);

    int trap_request = Deoptimization::make_trap_request(reason, Deoptimization::Action_maybe_recompile);
    address call_addr = OptoRuntime::uncommon_trap_blob()->entry_point();
    const TypePtr* no_memory_effects = nullptr;
    JVMState* jvms = sfpt->jvms();
    CallNode* unc = new CallStaticJavaNode(OptoRuntime::uncommon_trap_Type(), call_addr, "uncommon_trap",
                                           no_memory_effects);

    Node* mem = nullptr;
    Node* i_o = nullptr;
    if (sfpt->is_Call()) {
      mem = sfpt->proj_out(TypeFunc::Memory);
      i_o = sfpt->proj_out(TypeFunc::I_O);
    } else {
      mem = sfpt->memory();
      i_o = sfpt->i_o();
    }

    Node *frame = new ParmNode(C->start(), TypeFunc::FramePtr);
    register_new_node(frame, C->start());
    Node *ret = new ParmNode(C->start(), TypeFunc::ReturnAdr);
    register_new_node(ret, C->start());

    unc->init_req(TypeFunc::Control, if_false);
    unc->init_req(TypeFunc::I_O, i_o);
    unc->init_req(TypeFunc::Memory, mem); // may gc ptrs
    unc->init_req(TypeFunc::FramePtr, frame);
    unc->init_req(TypeFunc::ReturnAdr, ret);
    unc->init_req(TypeFunc::Parms+0, _igvn.intcon(trap_request));
    unc->set_cnt(PROB_UNLIKELY_MAG(4));
    unc->copy_call_debug_info(&_igvn, sfpt);

    for (uint i = TypeFunc::Parms; i < unc->req(); i++) {
      set_subtree_ctrl(unc->in(i), false);
    }
    register_control(unc, _ltree_root, if_false);

    Node* ctrl = new ProjNode(unc, TypeFunc::Control);
    register_control(ctrl, _ltree_root, unc);
    Node* halt = new HaltNode(ctrl, frame, "uncommon trap returned which should never happen" PRODUCT_ONLY(COMMA /*reachable*/false));
    register_control(halt, _ltree_root, ctrl);
    _igvn.add_input_to(C->root(), halt);

    _igvn.replace_input_of(inner_head, LoopNode::EntryControl, if_true);
    set_idom(inner_head, if_true, dom_depth(inner_head));
  }
}

// Find a safepoint node that dominates the back edge. We need a
// SafePointNode so we can use its jvm state to create empty
// predicates.
static bool no_side_effect_since_safepoint(Compile* C, Node* x, Node* mem, MergeMemNode* mm, PhaseIdealLoop* phase) {
  SafePointNode* safepoint = nullptr;
  for (DUIterator_Fast imax, i = x->fast_outs(imax); i < imax; i++) {
    Node* u = x->fast_out(i);
    if (u->is_memory_phi()) {
      Node* m = u->in(LoopNode::LoopBackControl);
      if (u->adr_type() == TypePtr::BOTTOM) {
        if (m->is_MergeMem() && mem->is_MergeMem()) {
          if (m != mem DEBUG_ONLY(|| true)) {
            // MergeMemStream can modify m, for example to adjust the length to mem.
            // This is unfortunate, and probably unnecessary. But as it is, we need
            // to add m to the igvn worklist, else we may have a modified node that
            // is not on the igvn worklist.
            phase->igvn()._worklist.push(m);
            for (MergeMemStream mms(m->as_MergeMem(), mem->as_MergeMem()); mms.next_non_empty2(); ) {
              if (!mms.is_empty()) {
                if (mms.memory() != mms.memory2()) {
                  return false;
                }
#ifdef ASSERT
                if (mms.alias_idx() != Compile::AliasIdxBot) {
                  mm->set_memory_at(mms.alias_idx(), mem->as_MergeMem()->base_memory());
                }
#endif
              }
            }
          }
        } else if (mem->is_MergeMem()) {
          if (m != mem->as_MergeMem()->base_memory()) {
            return false;
          }
        } else {
          return false;
        }
      } else {
        if (mem->is_MergeMem()) {
          if (m != mem->as_MergeMem()->memory_at(C->get_alias_index(u->adr_type()))) {
            return false;
          }
#ifdef ASSERT
          mm->set_memory_at(C->get_alias_index(u->adr_type()), mem->as_MergeMem()->base_memory());
#endif
        } else {
          if (m != mem) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

SafePointNode* PhaseIdealLoop::find_safepoint(Node* back_control, Node* x, IdealLoopTree* loop) {
  IfNode* exit_test = back_control->in(0)->as_If();
  SafePointNode* safepoint = nullptr;
  if (exit_test->in(0)->is_SafePoint() && exit_test->in(0)->outcnt() == 1) {
    safepoint = exit_test->in(0)->as_SafePoint();
  } else {
    Node* c = back_control;
    while (c != x && c->Opcode() != Op_SafePoint) {
      c = idom(c);
    }

    if (c->Opcode() == Op_SafePoint) {
      safepoint = c->as_SafePoint();
    }

    if (safepoint == nullptr) {
      return nullptr;
    }

    Node* mem = safepoint->in(TypeFunc::Memory);

    // We can only use that safepoint if there's no side effect between the backedge and the safepoint.

    // mm is the memory state at the safepoint (when it's a MergeMem)
    // no_side_effect_since_safepoint() goes over the memory state at the backedge. It resets the mm input for each
    // component of the memory state it encounters so it points to the base memory. Once no_side_effect_since_safepoint()
    // is done, if no side effect after the safepoint was found, mm should transform to the base memory: the states at
    // the backedge and safepoint are the same so all components of the memory state at the safepoint should have been
    // reset.
    MergeMemNode* mm = nullptr;
#ifdef ASSERT
    if (mem->is_MergeMem()) {
      mm = mem->clone()->as_MergeMem();
      _igvn._worklist.push(mm);
      for (MergeMemStream mms(mem->as_MergeMem()); mms.next_non_empty(); ) {
        // Loop invariant memory state won't be reset by no_side_effect_since_safepoint(). Do it here.
        // Escape Analysis can add state to mm that it doesn't add to the backedge memory Phis, breaking verification
        // code that relies on mm. Clear that extra state here.
        if (mms.alias_idx() != Compile::AliasIdxBot &&
            (loop != get_loop(ctrl_or_self(mms.memory())) ||
             (mms.adr_type()->isa_oop_ptr() && mms.adr_type()->is_known_instance()))) {
          mm->set_memory_at(mms.alias_idx(), mem->as_MergeMem()->base_memory());
        }
      }
    }
#endif
    if (!no_side_effect_since_safepoint(C, x, mem, mm, this)) {
      safepoint = nullptr;
    } else {
      assert(mm == nullptr|| _igvn.transform(mm) == mem->as_MergeMem()->base_memory(), "all memory state should have been processed");
    }
#ifdef ASSERT
    if (mm != nullptr) {
      _igvn.remove_dead_node(mm);
    }
#endif
  }
  return safepoint;
}

// If the loop has the shape of a counted loop but with a long
// induction variable, transform the loop in a loop nest: an inner
// loop that iterates for at most max int iterations with an integer
// induction variable and an outer loop that iterates over the full
// range of long values from the initial loop in (at most) max int
// steps. That is:
//
// x: for (long phi = init; phi < limit; phi += stride) {
//   // phi := Phi(L, init, incr)
//   // incr := AddL(phi, longcon(stride))
//   long incr = phi + stride;
//   ... use phi and incr ...
// }
//
// OR:
//
// x: for (long phi = init; (phi += stride) < limit; ) {
//   // phi := Phi(L, AddL(init, stride), incr)
//   // incr := AddL(phi, longcon(stride))
//   long incr = phi + stride;
//   ... use phi and (phi + stride) ...
// }
//
// ==transform=>
//
// const ulong inner_iters_limit = INT_MAX - stride - 1;  //near 0x7FFFFFF0
// assert(stride <= inner_iters_limit);  // else abort transform
// assert((extralong)limit + stride <= LONG_MAX);  // else deopt
// outer_head: for (long outer_phi = init;;) {
//   // outer_phi := Phi(outer_head, init, AddL(outer_phi, I2L(inner_phi)))
//   ulong inner_iters_max = (ulong) MAX(0, ((extralong)limit + stride - outer_phi));
//   long inner_iters_actual = MIN(inner_iters_limit, inner_iters_max);
//   assert(inner_iters_actual == (int)inner_iters_actual);
//   int inner_phi, inner_incr;
//   x: for (inner_phi = 0;; inner_phi = inner_incr) {
//     // inner_phi := Phi(x, intcon(0), inner_incr)
//     // inner_incr := AddI(inner_phi, intcon(stride))
//     inner_incr = inner_phi + stride;
//     if (inner_incr < inner_iters_actual) {
//       ... use phi=>(outer_phi+inner_phi) ...
//       continue;
//     }
//     else break;
//   }
//   if ((outer_phi+inner_phi) < limit)  //OR (outer_phi+inner_incr) < limit
//     continue;
//   else break;
// }
//
// The same logic is used to transform an int counted loop that contains long range checks into a loop nest of 2 int
// loops with long range checks transformed to int range checks in the inner loop.
bool PhaseIdealLoop::create_loop_nest(IdealLoopTree* loop, Node_List &old_new) {
  Node* x = loop->_head;
  // Only for inner loops
  if (loop->_child != nullptr || !x->is_BaseCountedLoop() || x->as_Loop()->is_loop_nest_outer_loop()) {
    return false;
  }

  if (x->is_CountedLoop() && !x->as_CountedLoop()->is_main_loop() && !x->as_CountedLoop()->is_normal_loop()) {
    return false;
  }

  BaseCountedLoopNode* head = x->as_BaseCountedLoop();
  BasicType bt = x->as_BaseCountedLoop()->bt();

  check_counted_loop_shape(loop, x, bt);

#ifndef PRODUCT
  if (bt == T_LONG) {
    Atomic::inc(&_long_loop_candidates);
  }
#endif

  jlong stride_con_long = head->stride_con();
  assert(stride_con_long != 0, "missed some peephole opt");
  // We can't iterate for more than max int at a time.
  if (stride_con_long != (jint)stride_con_long || stride_con_long == min_jint) {
    assert(bt == T_LONG, "only for long loops");
    return false;
  }
  jint stride_con = checked_cast<jint>(stride_con_long);
  // The number of iterations for the integer count loop: guarantee no
  // overflow: max_jint - stride_con max. -1 so there's no need for a
  // loop limit check if the exit test is <= or >=.
  int iters_limit = max_jint - ABS(stride_con) - 1;
#ifdef ASSERT
  if (bt == T_LONG && StressLongCountedLoop > 0) {
    iters_limit = iters_limit / StressLongCountedLoop;
  }
#endif
  // At least 2 iterations so counted loop construction doesn't fail
  if (iters_limit/ABS(stride_con) < 2) {
    return false;
  }

  PhiNode* phi = head->phi()->as_Phi();
  Node* incr = head->incr();

  Node* back_control = head->in(LoopNode::LoopBackControl);

  // data nodes on back branch not supported
  if (back_control->outcnt() > 1) {
    return false;
  }

  Node* limit = head->limit();
  // We'll need to use the loop limit before the inner loop is entered
  if (!is_dominator(get_ctrl(limit), x)) {
    return false;
  }

  IfNode* exit_test = head->loopexit();

  assert(back_control->Opcode() == Op_IfTrue, "wrong projection for back edge");

  Node_List range_checks;
  iters_limit = extract_long_range_checks(loop, stride_con, iters_limit, phi, range_checks);

  if (bt == T_INT) {
    // The only purpose of creating a loop nest is to handle long range checks. If there are none, do not proceed further.
    if (range_checks.size() == 0) {
      return false;
    }
  }

  // Take what we know about the number of iterations of the long counted loop into account when computing the limit of
  // the inner loop.
  const Node* init = head->init_trip();
  const TypeInteger* lo = _igvn.type(init)->is_integer(bt);
  const TypeInteger* hi = _igvn.type(limit)->is_integer(bt);
  if (stride_con < 0) {
    swap(lo, hi);
  }
  if (hi->hi_as_long() <= lo->lo_as_long()) {
    // not a loop after all
    return false;
  }

  if (range_checks.size() > 0) {
    // This transformation requires peeling one iteration. Also, if it has range checks and they are eliminated by Loop
    // Predication, then 2 Hoisted Check Predicates are added for one range check. Finally, transforming a long range
    // check requires extra logic to be executed before the loop is entered and for the outer loop. As a result, the
    // transformations can't pay off for a small number of iterations: roughly, if the loop runs for 3 iterations, it's
    // going to execute as many range checks once transformed with range checks eliminated (1 peeled iteration with
    // range checks + 2 predicates per range checks) as it would have not transformed. It also has to pay for the extra
    // logic on loop entry and for the outer loop.
    loop->compute_trip_count(this);
    if (head->is_CountedLoop() && head->as_CountedLoop()->has_exact_trip_count()) {
      if (head->as_CountedLoop()->trip_count() <= 3) {
        return false;
      }
    } else {
      loop->compute_profile_trip_cnt(this);
      if (!head->is_profile_trip_failed() && head->profile_trip_cnt() <= 3) {
        return false;
      }
    }
  }

  julong orig_iters = (julong)hi->hi_as_long() - lo->lo_as_long();
  iters_limit = checked_cast<int>(MIN2((julong)iters_limit, orig_iters));

  // We need a safepoint to insert Parse Predicates for the inner loop.
  SafePointNode* safepoint;
  if (bt == T_INT && head->as_CountedLoop()->is_strip_mined()) {
    // Loop is strip mined: use the safepoint of the outer strip mined loop
    OuterStripMinedLoopNode* outer_loop = head->as_CountedLoop()->outer_loop();
    assert(outer_loop != nullptr, "no outer loop");
    safepoint = outer_loop->outer_safepoint();
    outer_loop->transform_to_counted_loop(&_igvn, this);
    exit_test = head->loopexit();
  } else {
    safepoint = find_safepoint(back_control, x, loop);
  }

  Node* exit_branch = exit_test->proj_out(false);
  Node* entry_control = head->in(LoopNode::EntryControl);

  // Clone the control flow of the loop to build an outer loop
  Node* outer_back_branch = back_control->clone();
  Node* outer_exit_test = new IfNode(exit_test->in(0), exit_test->in(1), exit_test->_prob, exit_test->_fcnt);
  Node* inner_exit_branch = exit_branch->clone();

  LoopNode* outer_head = new LoopNode(entry_control, outer_back_branch);
  IdealLoopTree* outer_ilt = insert_outer_loop(loop, outer_head, outer_back_branch);

  const bool body_populated = true;
  register_control(outer_head, outer_ilt, entry_control, body_populated);

  _igvn.register_new_node_with_optimizer(inner_exit_branch);
  set_loop(inner_exit_branch, outer_ilt);
  set_idom(inner_exit_branch, exit_test, dom_depth(exit_branch));

  outer_exit_test->set_req(0, inner_exit_branch);
  register_control(outer_exit_test, outer_ilt, inner_exit_branch, body_populated);

  _igvn.replace_input_of(exit_branch, 0, outer_exit_test);
  set_idom(exit_branch, outer_exit_test, dom_depth(exit_branch));

  outer_back_branch->set_req(0, outer_exit_test);
  register_control(outer_back_branch, outer_ilt, outer_exit_test, body_populated);

  _igvn.replace_input_of(x, LoopNode::EntryControl, outer_head);
  set_idom(x, outer_head, dom_depth(x));

  // add an iv phi to the outer loop and use it to compute the inner
  // loop iteration limit
  Node* outer_phi = phi->clone();
  outer_phi->set_req(0, outer_head);
  register_new_node(outer_phi, outer_head);

  Node* inner_iters_max = nullptr;
  if (stride_con > 0) {
    inner_iters_max = MaxNode::max_diff_with_zero(limit, outer_phi, TypeInteger::bottom(bt), _igvn);
  } else {
    inner_iters_max = MaxNode::max_diff_with_zero(outer_phi, limit, TypeInteger::bottom(bt), _igvn);
  }

  Node* inner_iters_limit = _igvn.integercon(iters_limit, bt);
  // inner_iters_max may not fit in a signed integer (iterating from
  // Long.MIN_VALUE to Long.MAX_VALUE for instance). Use an unsigned
  // min.
  const TypeInteger* inner_iters_actual_range = TypeInteger::make(0, iters_limit, Type::WidenMin, bt);
  Node* inner_iters_actual = MaxNode::unsigned_min(inner_iters_max, inner_iters_limit, inner_iters_actual_range, _igvn);

  Node* inner_iters_actual_int;
  if (bt == T_LONG) {
    inner_iters_actual_int = new ConvL2INode(inner_iters_actual);
    _igvn.register_new_node_with_optimizer(inner_iters_actual_int);
    // When the inner loop is transformed to a counted loop, a loop limit check is not expected to be needed because
    // the loop limit is less or equal to max_jint - stride - 1 (if stride is positive but a similar argument exists for
    // a negative stride). We add a CastII here to guarantee that, when the counted loop is created in a subsequent loop
    // opts pass, an accurate range of values for the limits is found.
    const TypeInt* inner_iters_actual_int_range = TypeInt::make(0, iters_limit, Type::WidenMin);
    inner_iters_actual_int = new CastIINode(outer_head, inner_iters_actual_int, inner_iters_actual_int_range, ConstraintCastNode::UnconditionalDependency);
    _igvn.register_new_node_with_optimizer(inner_iters_actual_int);
  } else {
    inner_iters_actual_int = inner_iters_actual;
  }

  Node* int_zero = intcon(0);
  if (stride_con < 0) {
    inner_iters_actual_int = new SubINode(int_zero, inner_iters_actual_int);
    _igvn.register_new_node_with_optimizer(inner_iters_actual_int);
  }

  // Clone the iv data nodes as an integer iv
  Node* int_stride = intcon(stride_con);
  Node* inner_phi = new PhiNode(x->in(0), TypeInt::INT);
  Node* inner_incr = new AddINode(inner_phi, int_stride);
  Node* inner_cmp = nullptr;
  inner_cmp = new CmpINode(inner_incr, inner_iters_actual_int);
  Node* inner_bol = new BoolNode(inner_cmp, exit_test->in(1)->as_Bool()->_test._test);
  inner_phi->set_req(LoopNode::EntryControl, int_zero);
  inner_phi->set_req(LoopNode::LoopBackControl, inner_incr);
  register_new_node(inner_phi, x);
  register_new_node(inner_incr, x);
  register_new_node(inner_cmp, x);
  register_new_node(inner_bol, x);

  _igvn.replace_input_of(exit_test, 1, inner_bol);

  // Clone inner loop phis to outer loop
  for (uint i = 0; i < head->outcnt(); i++) {
    Node* u = head->raw_out(i);
    if (u->is_Phi() && u != inner_phi && u != phi) {
      assert(u->in(0) == head, "inconsistent");
      Node* clone = u->clone();
      clone->set_req(0, outer_head);
      register_new_node(clone, outer_head);