1 /*
   2  * Copyright (c) 1999, 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "gc/shared/barrierSet.hpp"
  27 #include "gc/shared/c2/barrierSetC2.hpp"
  28 #include "memory/allocation.inline.hpp"
  29 #include "memory/resourceArea.hpp"
  30 #include "opto/addnode.hpp"
  31 #include "opto/callnode.hpp"
  32 #include "opto/castnode.hpp"
  33 #include "opto/connode.hpp"
  34 #include "opto/castnode.hpp"
  35 #include "opto/divnode.hpp"
  36 #include "opto/loopnode.hpp"
  37 #include "opto/matcher.hpp"
  38 #include "opto/mulnode.hpp"
  39 #include "opto/movenode.hpp"
  40 #include "opto/opaquenode.hpp"
  41 #include "opto/rootnode.hpp"
  42 #include "opto/subnode.hpp"
  43 #include "utilities/macros.hpp"
  44 #if INCLUDE_ZGC
  45 #include "gc/z/c2/zBarrierSetC2.hpp"
  46 #endif
  47 
  48 //=============================================================================
  49 //------------------------------split_thru_phi---------------------------------
  50 // Split Node 'n' through merge point if there is enough win.
  51 Node *PhaseIdealLoop::split_thru_phi( Node *n, Node *region, int policy ) {
  52   if (n->Opcode() == Op_ConvI2L && n->bottom_type() != TypeLong::LONG) {
  53     // ConvI2L may have type information on it which is unsafe to push up
  54     // so disable this for now
  55     return NULL;
  56   }
  57 
  58   // Splitting range check CastIIs through a loop induction Phi can
  59   // cause new Phis to be created that are left unrelated to the loop
  60   // induction Phi and prevent optimizations (vectorization)
  61   if (n->Opcode() == Op_CastII && n->as_CastII()->has_range_check() &&
  62       region->is_CountedLoop() && n->in(1) == region->as_CountedLoop()->phi()) {
  63     return NULL;
  64   }
  65 
  66   int wins = 0;
  67   assert(!n->is_CFG(), "");
  68   assert(region->is_Region(), "");
  69 
  70   const Type* type = n->bottom_type();
  71   const TypeOopPtr *t_oop = _igvn.type(n)->isa_oopptr();
  72   Node *phi;
  73   if (t_oop != NULL && t_oop->is_known_instance_field()) {
  74     int iid    = t_oop->instance_id();
  75     int index  = C->get_alias_index(t_oop);
  76     int offset = t_oop->offset();
  77     phi = new PhiNode(region, type, NULL, iid, index, offset);
  78   } else {
  79     phi = PhiNode::make_blank(region, n);
  80   }
  81   uint old_unique = C->unique();
  82   for (uint i = 1; i < region->req(); i++) {
  83     Node *x;
  84     Node* the_clone = NULL;
  85     if (region->in(i) == C->top()) {
  86       x = C->top();             // Dead path?  Use a dead data op
  87     } else {
  88       x = n->clone();           // Else clone up the data op
  89       the_clone = x;            // Remember for possible deletion.
  90       // Alter data node to use pre-phi inputs
  91       if (n->in(0) == region)
  92         x->set_req( 0, region->in(i) );
  93       for (uint j = 1; j < n->req(); j++) {
  94         Node *in = n->in(j);
  95         if (in->is_Phi() && in->in(0) == region)
  96           x->set_req( j, in->in(i) ); // Use pre-Phi input for the clone
  97       }
  98     }
  99     // Check for a 'win' on some paths
 100     const Type *t = x->Value(&_igvn);
 101 
 102     bool singleton = t->singleton();
 103 
 104     // A TOP singleton indicates that there are no possible values incoming
 105     // along a particular edge. In most cases, this is OK, and the Phi will
 106     // be eliminated later in an Ideal call. However, we can't allow this to
 107     // happen if the singleton occurs on loop entry, as the elimination of
 108     // the PhiNode may cause the resulting node to migrate back to a previous
 109     // loop iteration.
 110     if (singleton && t == Type::TOP) {
 111       // Is_Loop() == false does not confirm the absence of a loop (e.g., an
 112       // irreducible loop may not be indicated by an affirmative is_Loop());
 113       // therefore, the only top we can split thru a phi is on a backedge of
 114       // a loop.
 115       singleton &= region->is_Loop() && (i != LoopNode::EntryControl);
 116     }
 117 
 118     if (singleton) {
 119       wins++;
 120       x = ((PhaseGVN&)_igvn).makecon(t);
 121     } else {
 122       // We now call Identity to try to simplify the cloned node.
 123       // Note that some Identity methods call phase->type(this).
 124       // Make sure that the type array is big enough for
 125       // our new node, even though we may throw the node away.
 126       // (Note: This tweaking with igvn only works because x is a new node.)
 127       _igvn.set_type(x, t);
 128       // If x is a TypeNode, capture any more-precise type permanently into Node
 129       // otherwise it will be not updated during igvn->transform since
 130       // igvn->type(x) is set to x->Value() already.
 131       x->raise_bottom_type(t);
 132       Node *y = x->Identity(&_igvn);
 133       if (y != x) {
 134         wins++;
 135         x = y;
 136       } else {
 137         y = _igvn.hash_find(x);
 138         if (y) {
 139           wins++;
 140           x = y;
 141         } else {
 142           // Else x is a new node we are keeping
 143           // We do not need register_new_node_with_optimizer
 144           // because set_type has already been called.
 145           _igvn._worklist.push(x);
 146         }
 147       }
 148     }
 149     if (x != the_clone && the_clone != NULL)
 150       _igvn.remove_dead_node(the_clone);
 151     phi->set_req( i, x );
 152   }
 153   // Too few wins?
 154   if (wins <= policy) {
 155     _igvn.remove_dead_node(phi);
 156     return NULL;
 157   }
 158 
 159   // Record Phi
 160   register_new_node( phi, region );
 161 
 162   for (uint i2 = 1; i2 < phi->req(); i2++) {
 163     Node *x = phi->in(i2);
 164     // If we commoned up the cloned 'x' with another existing Node,
 165     // the existing Node picks up a new use.  We need to make the
 166     // existing Node occur higher up so it dominates its uses.
 167     Node *old_ctrl;
 168     IdealLoopTree *old_loop;
 169 
 170     if (x->is_Con()) {
 171       // Constant's control is always root.
 172       set_ctrl(x, C->root());
 173       continue;
 174     }
 175     // The occasional new node
 176     if (x->_idx >= old_unique) {     // Found a new, unplaced node?
 177       old_ctrl = NULL;
 178       old_loop = NULL;               // Not in any prior loop
 179     } else {
 180       old_ctrl = get_ctrl(x);
 181       old_loop = get_loop(old_ctrl); // Get prior loop
 182     }
 183     // New late point must dominate new use
 184     Node *new_ctrl = dom_lca(old_ctrl, region->in(i2));
 185     if (new_ctrl == old_ctrl) // Nothing is changed
 186       continue;
 187 
 188     IdealLoopTree *new_loop = get_loop(new_ctrl);
 189 
 190     // Don't move x into a loop if its uses are
 191     // outside of loop. Otherwise x will be cloned
 192     // for each use outside of this loop.
 193     IdealLoopTree *use_loop = get_loop(region);
 194     if (!new_loop->is_member(use_loop) &&
 195         (old_loop == NULL || !new_loop->is_member(old_loop))) {
 196       // Take early control, later control will be recalculated
 197       // during next iteration of loop optimizations.
 198       new_ctrl = get_early_ctrl(x);
 199       new_loop = get_loop(new_ctrl);
 200     }
 201     // Set new location
 202     set_ctrl(x, new_ctrl);
 203     // If changing loop bodies, see if we need to collect into new body
 204     if (old_loop != new_loop) {
 205       if (old_loop && !old_loop->_child)
 206         old_loop->_body.yank(x);
 207       if (!new_loop->_child)
 208         new_loop->_body.push(x);  // Collect body info
 209     }
 210   }
 211 
 212   return phi;
 213 }
 214 
 215 //------------------------------dominated_by------------------------------------
 216 // Replace the dominated test with an obvious true or false.  Place it on the
 217 // IGVN worklist for later cleanup.  Move control-dependent data Nodes on the
 218 // live path up to the dominating control.
 219 void PhaseIdealLoop::dominated_by( Node *prevdom, Node *iff, bool flip, bool exclude_loop_predicate ) {
 220   if (VerifyLoopOptimizations && PrintOpto) { tty->print_cr("dominating test"); }
 221 
 222   // prevdom is the dominating projection of the dominating test.
 223   assert( iff->is_If(), "" );
 224   assert(iff->Opcode() == Op_If || iff->Opcode() == Op_CountedLoopEnd || iff->Opcode() == Op_RangeCheck, "Check this code when new subtype is added");
 225   int pop = prevdom->Opcode();
 226   assert( pop == Op_IfFalse || pop == Op_IfTrue, "" );
 227   if (flip) {
 228     if (pop == Op_IfTrue)
 229       pop = Op_IfFalse;
 230     else
 231       pop = Op_IfTrue;
 232   }
 233   // 'con' is set to true or false to kill the dominated test.
 234   Node *con = _igvn.makecon(pop == Op_IfTrue ? TypeInt::ONE : TypeInt::ZERO);
 235   set_ctrl(con, C->root()); // Constant gets a new use
 236   // Hack the dominated test
 237   _igvn.replace_input_of(iff, 1, con);
 238 
 239   // If I dont have a reachable TRUE and FALSE path following the IfNode then
 240   // I can assume this path reaches an infinite loop.  In this case it's not
 241   // important to optimize the data Nodes - either the whole compilation will
 242   // be tossed or this path (and all data Nodes) will go dead.
 243   if (iff->outcnt() != 2) return;
 244 
 245   // Make control-dependent data Nodes on the live path (path that will remain
 246   // once the dominated IF is removed) become control-dependent on the
 247   // dominating projection.
 248   Node* dp = iff->as_If()->proj_out_or_null(pop == Op_IfTrue);
 249 
 250   // Loop predicates may have depending checks which should not
 251   // be skipped. For example, range check predicate has two checks
 252   // for lower and upper bounds.
 253   if (dp == NULL)
 254     return;
 255 
 256   ProjNode* dp_proj  = dp->as_Proj();
 257   ProjNode* unc_proj = iff->as_If()->proj_out(1 - dp_proj->_con)->as_Proj();
 258   if (exclude_loop_predicate &&
 259       (unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_predicate) != NULL ||
 260        unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_profile_predicate) != NULL ||
 261        unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_range_check) != NULL)) {
 262     // If this is a range check (IfNode::is_range_check), do not
 263     // reorder because Compile::allow_range_check_smearing might have
 264     // changed the check.
 265     return; // Let IGVN transformation change control dependence.
 266   }
 267 
 268   IdealLoopTree *old_loop = get_loop(dp);
 269 
 270   for (DUIterator_Fast imax, i = dp->fast_outs(imax); i < imax; i++) {
 271     Node* cd = dp->fast_out(i); // Control-dependent node
 272     if (cd->depends_only_on_test()) {
 273       assert(cd->in(0) == dp, "");
 274       _igvn.replace_input_of(cd, 0, prevdom);
 275       set_early_ctrl(cd);
 276       IdealLoopTree *new_loop = get_loop(get_ctrl(cd));
 277       if (old_loop != new_loop) {
 278         if (!old_loop->_child) old_loop->_body.yank(cd);
 279         if (!new_loop->_child) new_loop->_body.push(cd);
 280       }
 281       --i;
 282       --imax;
 283     }
 284   }
 285 }
 286 
 287 //------------------------------has_local_phi_input----------------------------
 288 // Return TRUE if 'n' has Phi inputs from its local block and no other
 289 // block-local inputs (all non-local-phi inputs come from earlier blocks)
 290 Node *PhaseIdealLoop::has_local_phi_input( Node *n ) {
 291   Node *n_ctrl = get_ctrl(n);
 292   // See if some inputs come from a Phi in this block, or from before
 293   // this block.
 294   uint i;
 295   for( i = 1; i < n->req(); i++ ) {
 296     Node *phi = n->in(i);
 297     if( phi->is_Phi() && phi->in(0) == n_ctrl )
 298       break;
 299   }
 300   if( i >= n->req() )
 301     return NULL;                // No Phi inputs; nowhere to clone thru
 302 
 303   // Check for inputs created between 'n' and the Phi input.  These
 304   // must split as well; they have already been given the chance
 305   // (courtesy of a post-order visit) and since they did not we must
 306   // recover the 'cost' of splitting them by being very profitable
 307   // when splitting 'n'.  Since this is unlikely we simply give up.
 308   for( i = 1; i < n->req(); i++ ) {
 309     Node *m = n->in(i);
 310     if( get_ctrl(m) == n_ctrl && !m->is_Phi() ) {
 311       // We allow the special case of AddP's with no local inputs.
 312       // This allows us to split-up address expressions.
 313       if (m->is_AddP() &&
 314           get_ctrl(m->in(2)) != n_ctrl &&
 315           get_ctrl(m->in(3)) != n_ctrl) {
 316         // Move the AddP up to dominating point
 317         Node* c = find_non_split_ctrl(idom(n_ctrl));
 318         if (c->is_OuterStripMinedLoop()) {
 319           c->as_Loop()->verify_strip_mined(1);
 320           c = c->in(LoopNode::EntryControl);
 321         }
 322         set_ctrl_and_loop(m, c);
 323         continue;
 324       }
 325       return NULL;
 326     }
 327     assert(m->is_Phi() || is_dominator(get_ctrl(m), n_ctrl), "m has strange control");
 328   }
 329 
 330   return n_ctrl;
 331 }
 332 
 333 //------------------------------remix_address_expressions----------------------
 334 // Rework addressing expressions to get the most loop-invariant stuff
 335 // moved out.  We'd like to do all associative operators, but it's especially
 336 // important (common) to do address expressions.
 337 Node *PhaseIdealLoop::remix_address_expressions( Node *n ) {
 338   if (!has_ctrl(n))  return NULL;
 339   Node *n_ctrl = get_ctrl(n);
 340   IdealLoopTree *n_loop = get_loop(n_ctrl);
 341 
 342   // See if 'n' mixes loop-varying and loop-invariant inputs and
 343   // itself is loop-varying.
 344 
 345   // Only interested in binary ops (and AddP)
 346   if( n->req() < 3 || n->req() > 4 ) return NULL;
 347 
 348   Node *n1_ctrl = get_ctrl(n->in(                    1));
 349   Node *n2_ctrl = get_ctrl(n->in(                    2));
 350   Node *n3_ctrl = get_ctrl(n->in(n->req() == 3 ? 2 : 3));
 351   IdealLoopTree *n1_loop = get_loop( n1_ctrl );
 352   IdealLoopTree *n2_loop = get_loop( n2_ctrl );
 353   IdealLoopTree *n3_loop = get_loop( n3_ctrl );
 354 
 355   // Does one of my inputs spin in a tighter loop than self?
 356   if( (n_loop->is_member( n1_loop ) && n_loop != n1_loop) ||
 357       (n_loop->is_member( n2_loop ) && n_loop != n2_loop) ||
 358       (n_loop->is_member( n3_loop ) && n_loop != n3_loop) )
 359     return NULL;                // Leave well enough alone
 360 
 361   // Is at least one of my inputs loop-invariant?
 362   if( n1_loop == n_loop &&
 363       n2_loop == n_loop &&
 364       n3_loop == n_loop )
 365     return NULL;                // No loop-invariant inputs
 366 
 367 
 368   int n_op = n->Opcode();
 369 
 370   // Replace expressions like ((V+I) << 2) with (V<<2 + I<<2).
 371   if( n_op == Op_LShiftI ) {
 372     // Scale is loop invariant
 373     Node *scale = n->in(2);
 374     Node *scale_ctrl = get_ctrl(scale);
 375     IdealLoopTree *scale_loop = get_loop(scale_ctrl );
 376     if( n_loop == scale_loop || !scale_loop->is_member( n_loop ) )
 377       return NULL;
 378     const TypeInt *scale_t = scale->bottom_type()->isa_int();
 379     if( scale_t && scale_t->is_con() && scale_t->get_con() >= 16 )
 380       return NULL;              // Dont bother with byte/short masking
 381     // Add must vary with loop (else shift would be loop-invariant)
 382     Node *add = n->in(1);
 383     Node *add_ctrl = get_ctrl(add);
 384     IdealLoopTree *add_loop = get_loop(add_ctrl);
 385     //assert( n_loop == add_loop, "" );
 386     if( n_loop != add_loop ) return NULL;  // happens w/ evil ZKM loops
 387 
 388     // Convert I-V into I+ (0-V); same for V-I
 389     if( add->Opcode() == Op_SubI &&
 390         _igvn.type( add->in(1) ) != TypeInt::ZERO ) {
 391       Node *zero = _igvn.intcon(0);
 392       set_ctrl(zero, C->root());
 393       Node *neg = new SubINode( _igvn.intcon(0), add->in(2) );
 394       register_new_node( neg, get_ctrl(add->in(2) ) );
 395       add = new AddINode( add->in(1), neg );
 396       register_new_node( add, add_ctrl );
 397     }
 398     if( add->Opcode() != Op_AddI ) return NULL;
 399     // See if one add input is loop invariant
 400     Node *add_var = add->in(1);
 401     Node *add_var_ctrl = get_ctrl(add_var);
 402     IdealLoopTree *add_var_loop = get_loop(add_var_ctrl );
 403     Node *add_invar = add->in(2);
 404     Node *add_invar_ctrl = get_ctrl(add_invar);
 405     IdealLoopTree *add_invar_loop = get_loop(add_invar_ctrl );
 406     if( add_var_loop == n_loop ) {
 407     } else if( add_invar_loop == n_loop ) {
 408       // Swap to find the invariant part
 409       add_invar = add_var;
 410       add_invar_ctrl = add_var_ctrl;
 411       add_invar_loop = add_var_loop;
 412       add_var = add->in(2);
 413       Node *add_var_ctrl = get_ctrl(add_var);
 414       IdealLoopTree *add_var_loop = get_loop(add_var_ctrl );
 415     } else                      // Else neither input is loop invariant
 416       return NULL;
 417     if( n_loop == add_invar_loop || !add_invar_loop->is_member( n_loop ) )
 418       return NULL;              // No invariant part of the add?
 419 
 420     // Yes!  Reshape address expression!
 421     Node *inv_scale = new LShiftINode( add_invar, scale );
 422     Node *inv_scale_ctrl =
 423       dom_depth(add_invar_ctrl) > dom_depth(scale_ctrl) ?
 424       add_invar_ctrl : scale_ctrl;
 425     register_new_node( inv_scale, inv_scale_ctrl );
 426     Node *var_scale = new LShiftINode( add_var, scale );
 427     register_new_node( var_scale, n_ctrl );
 428     Node *var_add = new AddINode( var_scale, inv_scale );
 429     register_new_node( var_add, n_ctrl );
 430     _igvn.replace_node( n, var_add );
 431     return var_add;
 432   }
 433 
 434   // Replace (I+V) with (V+I)
 435   if( n_op == Op_AddI ||
 436       n_op == Op_AddL ||
 437       n_op == Op_AddF ||
 438       n_op == Op_AddD ||
 439       n_op == Op_MulI ||
 440       n_op == Op_MulL ||
 441       n_op == Op_MulF ||
 442       n_op == Op_MulD ) {
 443     if( n2_loop == n_loop ) {
 444       assert( n1_loop != n_loop, "" );
 445       n->swap_edges(1, 2);
 446     }
 447   }
 448 
 449   // Replace ((I1 +p V) +p I2) with ((I1 +p I2) +p V),
 450   // but not if I2 is a constant.
 451   if( n_op == Op_AddP ) {
 452     if( n2_loop == n_loop && n3_loop != n_loop ) {
 453       if( n->in(2)->Opcode() == Op_AddP && !n->in(3)->is_Con() ) {
 454         Node *n22_ctrl = get_ctrl(n->in(2)->in(2));
 455         Node *n23_ctrl = get_ctrl(n->in(2)->in(3));
 456         IdealLoopTree *n22loop = get_loop( n22_ctrl );
 457         IdealLoopTree *n23_loop = get_loop( n23_ctrl );
 458         if( n22loop != n_loop && n22loop->is_member(n_loop) &&
 459             n23_loop == n_loop ) {
 460           Node *add1 = new AddPNode( n->in(1), n->in(2)->in(2), n->in(3) );
 461           // Stuff new AddP in the loop preheader
 462           register_new_node( add1, n_loop->_head->in(LoopNode::EntryControl) );
 463           Node *add2 = new AddPNode( n->in(1), add1, n->in(2)->in(3) );
 464           register_new_node( add2, n_ctrl );
 465           _igvn.replace_node( n, add2 );
 466           return add2;
 467         }
 468       }
 469     }
 470 
 471     // Replace (I1 +p (I2 + V)) with ((I1 +p I2) +p V)
 472     if (n2_loop != n_loop && n3_loop == n_loop) {
 473       if (n->in(3)->Opcode() == Op_AddX) {
 474         Node *V = n->in(3)->in(1);
 475         Node *I = n->in(3)->in(2);
 476         if (is_member(n_loop,get_ctrl(V))) {
 477         } else {
 478           Node *tmp = V; V = I; I = tmp;
 479         }
 480         if (!is_member(n_loop,get_ctrl(I))) {
 481           Node *add1 = new AddPNode(n->in(1), n->in(2), I);
 482           // Stuff new AddP in the loop preheader
 483           register_new_node(add1, n_loop->_head->in(LoopNode::EntryControl));
 484           Node *add2 = new AddPNode(n->in(1), add1, V);
 485           register_new_node(add2, n_ctrl);
 486           _igvn.replace_node(n, add2);
 487           return add2;
 488         }
 489       }
 490     }
 491   }
 492 
 493   return NULL;
 494 }
 495 
 496 //------------------------------conditional_move-------------------------------
 497 // Attempt to replace a Phi with a conditional move.  We have some pretty
 498 // strict profitability requirements.  All Phis at the merge point must
 499 // be converted, so we can remove the control flow.  We need to limit the
 500 // number of c-moves to a small handful.  All code that was in the side-arms
 501 // of the CFG diamond is now speculatively executed.  This code has to be
 502 // "cheap enough".  We are pretty much limited to CFG diamonds that merge
 503 // 1 or 2 items with a total of 1 or 2 ops executed speculatively.
 504 Node *PhaseIdealLoop::conditional_move( Node *region ) {
 505 
 506   assert(region->is_Region(), "sanity check");
 507   if (region->req() != 3) return NULL;
 508 
 509   // Check for CFG diamond
 510   Node *lp = region->in(1);
 511   Node *rp = region->in(2);
 512   if (!lp || !rp) return NULL;
 513   Node *lp_c = lp->in(0);
 514   if (lp_c == NULL || lp_c != rp->in(0) || !lp_c->is_If()) return NULL;
 515   IfNode *iff = lp_c->as_If();
 516 
 517   // Check for ops pinned in an arm of the diamond.
 518   // Can't remove the control flow in this case
 519   if (lp->outcnt() > 1) return NULL;
 520   if (rp->outcnt() > 1) return NULL;
 521 
 522   IdealLoopTree* r_loop = get_loop(region);
 523   assert(r_loop == get_loop(iff), "sanity");
 524   // Always convert to CMOVE if all results are used only outside this loop.
 525   bool used_inside_loop = (r_loop == _ltree_root);
 526 
 527   // Check profitability
 528   int cost = 0;
 529   int phis = 0;
 530   for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
 531     Node *out = region->fast_out(i);
 532     if (!out->is_Phi()) continue; // Ignore other control edges, etc
 533     phis++;
 534     PhiNode* phi = out->as_Phi();
 535     BasicType bt = phi->type()->basic_type();
 536     switch (bt) {
 537     case T_DOUBLE:
 538     case T_FLOAT:
 539       if (C->use_cmove()) {
 540         continue; //TODO: maybe we want to add some cost
 541       }
 542       cost += Matcher::float_cmove_cost(); // Could be very expensive
 543       break;
 544     case T_LONG: {
 545       cost += Matcher::long_cmove_cost(); // May encodes as 2 CMOV's
 546     }
 547     case T_INT:                 // These all CMOV fine
 548     case T_ADDRESS: {           // (RawPtr)
 549       cost++;
 550       break;
 551     }
 552     case T_NARROWOOP: // Fall through
 553     case T_OBJECT: {            // Base oops are OK, but not derived oops
 554       const TypeOopPtr *tp = phi->type()->make_ptr()->isa_oopptr();
 555       // Derived pointers are Bad (tm): what's the Base (for GC purposes) of a
 556       // CMOVE'd derived pointer?  It's a CMOVE'd derived base.  Thus
 557       // CMOVE'ing a derived pointer requires we also CMOVE the base.  If we
 558       // have a Phi for the base here that we convert to a CMOVE all is well
 559       // and good.  But if the base is dead, we'll not make a CMOVE.  Later
 560       // the allocator will have to produce a base by creating a CMOVE of the
 561       // relevant bases.  This puts the allocator in the business of
 562       // manufacturing expensive instructions, generally a bad plan.
 563       // Just Say No to Conditionally-Moved Derived Pointers.
 564       if (tp && tp->offset() != 0)
 565         return NULL;
 566       cost++;
 567       break;
 568     }
 569     default:
 570       return NULL;              // In particular, can't do memory or I/O
 571     }
 572     // Add in cost any speculative ops
 573     for (uint j = 1; j < region->req(); j++) {
 574       Node *proj = region->in(j);
 575       Node *inp = phi->in(j);
 576       if (get_ctrl(inp) == proj) { // Found local op
 577         cost++;
 578         // Check for a chain of dependent ops; these will all become
 579         // speculative in a CMOV.
 580         for (uint k = 1; k < inp->req(); k++)
 581           if (get_ctrl(inp->in(k)) == proj)
 582             cost += ConditionalMoveLimit; // Too much speculative goo
 583       }
 584     }
 585     // See if the Phi is used by a Cmp or Narrow oop Decode/Encode.
 586     // This will likely Split-If, a higher-payoff operation.
 587     for (DUIterator_Fast kmax, k = phi->fast_outs(kmax); k < kmax; k++) {
 588       Node* use = phi->fast_out(k);
 589       if (use->is_Cmp() || use->is_DecodeNarrowPtr() || use->is_EncodeNarrowPtr())
 590         cost += ConditionalMoveLimit;
 591       // Is there a use inside the loop?
 592       // Note: check only basic types since CMoveP is pinned.
 593       if (!used_inside_loop && is_java_primitive(bt)) {
 594         IdealLoopTree* u_loop = get_loop(has_ctrl(use) ? get_ctrl(use) : use);
 595         if (r_loop == u_loop || r_loop->is_member(u_loop)) {
 596           used_inside_loop = true;
 597         }
 598       }
 599     }
 600   }//for
 601   Node* bol = iff->in(1);
 602   assert(bol->Opcode() == Op_Bool, "");
 603   int cmp_op = bol->in(1)->Opcode();
 604   // It is expensive to generate flags from a float compare.
 605   // Avoid duplicated float compare.
 606   if (phis > 1 && (cmp_op == Op_CmpF || cmp_op == Op_CmpD)) return NULL;
 607 
 608   float infrequent_prob = PROB_UNLIKELY_MAG(3);
 609   // Ignore cost and blocks frequency if CMOVE can be moved outside the loop.
 610   if (used_inside_loop) {
 611     if (cost >= ConditionalMoveLimit) return NULL; // Too much goo
 612 
 613     // BlockLayoutByFrequency optimization moves infrequent branch
 614     // from hot path. No point in CMOV'ing in such case (110 is used
 615     // instead of 100 to take into account not exactness of float value).
 616     if (BlockLayoutByFrequency) {
 617       infrequent_prob = MAX2(infrequent_prob, (float)BlockLayoutMinDiamondPercentage/110.0f);
 618     }
 619   }
 620   // Check for highly predictable branch.  No point in CMOV'ing if
 621   // we are going to predict accurately all the time.
 622   if (C->use_cmove() && (cmp_op == Op_CmpF || cmp_op == Op_CmpD)) {
 623     //keep going
 624   } else if (iff->_prob < infrequent_prob ||
 625       iff->_prob > (1.0f - infrequent_prob))
 626     return NULL;
 627 
 628   // --------------
 629   // Now replace all Phis with CMOV's
 630   Node *cmov_ctrl = iff->in(0);
 631   uint flip = (lp->Opcode() == Op_IfTrue);
 632   Node_List wq;
 633   while (1) {
 634     PhiNode* phi = NULL;
 635     for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
 636       Node *out = region->fast_out(i);
 637       if (out->is_Phi()) {
 638         phi = out->as_Phi();
 639         break;
 640       }
 641     }
 642     if (phi == NULL)  break;
 643     if (PrintOpto && VerifyLoopOptimizations) { tty->print_cr("CMOV"); }
 644     // Move speculative ops
 645     wq.push(phi);
 646     while (wq.size() > 0) {
 647       Node *n = wq.pop();
 648       for (uint j = 1; j < n->req(); j++) {
 649         Node* m = n->in(j);
 650         if (m != NULL && !is_dominator(get_ctrl(m), cmov_ctrl)) {
 651 #ifndef PRODUCT
 652           if (PrintOpto && VerifyLoopOptimizations) {
 653             tty->print("  speculate: ");
 654             m->dump();
 655           }
 656 #endif
 657           set_ctrl(m, cmov_ctrl);
 658           wq.push(m);
 659         }
 660       }
 661     }
 662     Node *cmov = CMoveNode::make(cmov_ctrl, iff->in(1), phi->in(1+flip), phi->in(2-flip), _igvn.type(phi));
 663     register_new_node( cmov, cmov_ctrl );
 664     _igvn.replace_node( phi, cmov );
 665 #ifndef PRODUCT
 666     if (TraceLoopOpts) {
 667       tty->print("CMOV  ");
 668       r_loop->dump_head();
 669       if (Verbose) {
 670         bol->in(1)->dump(1);
 671         cmov->dump(1);
 672       }
 673     }
 674     if (VerifyLoopOptimizations) verify();
 675 #endif
 676   }
 677 
 678   // The useless CFG diamond will fold up later; see the optimization in
 679   // RegionNode::Ideal.
 680   _igvn._worklist.push(region);
 681 
 682   return iff->in(1);
 683 }
 684 
 685 static void enqueue_cfg_uses(Node* m, Unique_Node_List& wq) {
 686   for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax; i++) {
 687     Node* u = m->fast_out(i);
 688     if (u->is_CFG()) {
 689       if (u->Opcode() == Op_NeverBranch) {
 690         u = ((NeverBranchNode*)u)->proj_out(0);
 691         enqueue_cfg_uses(u, wq);
 692       } else {
 693         wq.push(u);
 694       }
 695     }
 696   }
 697 }
 698 
 699 // Try moving a store out of a loop, right before the loop
 700 Node* PhaseIdealLoop::try_move_store_before_loop(Node* n, Node *n_ctrl) {
 701   // Store has to be first in the loop body
 702   IdealLoopTree *n_loop = get_loop(n_ctrl);
 703   if (n->is_Store() && n_loop != _ltree_root &&
 704       n_loop->is_loop() && n_loop->_head->is_Loop() &&
 705       n->in(0) != NULL) {
 706     Node* address = n->in(MemNode::Address);
 707     Node* value = n->in(MemNode::ValueIn);
 708     Node* mem = n->in(MemNode::Memory);
 709     IdealLoopTree* address_loop = get_loop(get_ctrl(address));
 710     IdealLoopTree* value_loop = get_loop(get_ctrl(value));
 711 
 712     // - address and value must be loop invariant
 713     // - memory must be a memory Phi for the loop
 714     // - Store must be the only store on this memory slice in the
 715     // loop: if there's another store following this one then value
 716     // written at iteration i by the second store could be overwritten
 717     // at iteration i+n by the first store: it's not safe to move the
 718     // first store out of the loop
 719     // - nothing must observe the memory Phi: it guarantees no read
 720     // before the store, we are also guaranteed the store post
 721     // dominates the loop head (ignoring a possible early
 722     // exit). Otherwise there would be extra Phi involved between the
 723     // loop's Phi and the store.
 724     // - there must be no early exit from the loop before the Store
 725     // (such an exit most of the time would be an extra use of the
 726     // memory Phi but sometimes is a bottom memory Phi that takes the
 727     // store as input).
 728 
 729     if (!n_loop->is_member(address_loop) &&
 730         !n_loop->is_member(value_loop) &&
 731         mem->is_Phi() && mem->in(0) == n_loop->_head &&
 732         mem->outcnt() == 1 &&
 733         mem->in(LoopNode::LoopBackControl) == n) {
 734 
 735       assert(n_loop->_tail != NULL, "need a tail");
 736       assert(is_dominator(n_ctrl, n_loop->_tail), "store control must not be in a branch in the loop");
 737 
 738       // Verify that there's no early exit of the loop before the store.
 739       bool ctrl_ok = false;
 740       {
 741         // Follow control from loop head until n, we exit the loop or
 742         // we reach the tail
 743         ResourceMark rm;
 744         Unique_Node_List wq;
 745         wq.push(n_loop->_head);
 746 
 747         for (uint next = 0; next < wq.size(); ++next) {
 748           Node *m = wq.at(next);
 749           if (m == n->in(0)) {
 750             ctrl_ok = true;
 751             continue;
 752           }
 753           assert(!has_ctrl(m), "should be CFG");
 754           if (!n_loop->is_member(get_loop(m)) || m == n_loop->_tail) {
 755             ctrl_ok = false;
 756             break;
 757           }
 758           enqueue_cfg_uses(m, wq);
 759           if (wq.size() > 10) {
 760             ctrl_ok = false;
 761             break;
 762           }
 763         }
 764       }
 765       if (ctrl_ok) {
 766         // move the Store
 767         _igvn.replace_input_of(mem, LoopNode::LoopBackControl, mem);
 768         _igvn.replace_input_of(n, 0, n_loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl));
 769         _igvn.replace_input_of(n, MemNode::Memory, mem->in(LoopNode::EntryControl));
 770         // Disconnect the phi now. An empty phi can confuse other
 771         // optimizations in this pass of loop opts.
 772         _igvn.replace_node(mem, mem->in(LoopNode::EntryControl));
 773         n_loop->_body.yank(mem);
 774 
 775         set_ctrl_and_loop(n, n->in(0));
 776 
 777         return n;
 778       }
 779     }
 780   }
 781   return NULL;
 782 }
 783 
 784 // Try moving a store out of a loop, right after the loop
 785 void PhaseIdealLoop::try_move_store_after_loop(Node* n) {
 786   if (n->is_Store() && n->in(0) != NULL) {
 787     Node *n_ctrl = get_ctrl(n);
 788     IdealLoopTree *n_loop = get_loop(n_ctrl);
 789     // Store must be in a loop
 790     if (n_loop != _ltree_root && !n_loop->_irreducible) {
 791       Node* address = n->in(MemNode::Address);
 792       Node* value = n->in(MemNode::ValueIn);
 793       IdealLoopTree* address_loop = get_loop(get_ctrl(address));
 794       // address must be loop invariant
 795       if (!n_loop->is_member(address_loop)) {
 796         // Store must be last on this memory slice in the loop and
 797         // nothing in the loop must observe it
 798         Node* phi = NULL;
 799         for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
 800           Node* u = n->fast_out(i);
 801           if (has_ctrl(u)) { // control use?
 802             IdealLoopTree *u_loop = get_loop(get_ctrl(u));
 803             if (!n_loop->is_member(u_loop)) {
 804               continue;
 805             }
 806             if (u->is_Phi() && u->in(0) == n_loop->_head) {
 807               assert(_igvn.type(u) == Type::MEMORY, "bad phi");
 808               // multiple phis on the same slice are possible
 809               if (phi != NULL) {
 810                 return;
 811               }
 812               phi = u;
 813               continue;
 814             }
 815           }
 816           return;
 817         }
 818         if (phi != NULL) {
 819           // Nothing in the loop before the store (next iteration)
 820           // must observe the stored value
 821           bool mem_ok = true;
 822           {
 823             ResourceMark rm;
 824             Unique_Node_List wq;
 825             wq.push(phi);
 826             for (uint next = 0; next < wq.size() && mem_ok; ++next) {
 827               Node *m = wq.at(next);
 828               for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax && mem_ok; i++) {
 829                 Node* u = m->fast_out(i);
 830                 if (u->is_Store() || u->is_Phi()) {
 831                   if (u != n) {
 832                     wq.push(u);
 833                     mem_ok = (wq.size() <= 10);
 834                   }
 835                 } else {
 836                   mem_ok = false;
 837                   break;
 838                 }
 839               }
 840             }
 841           }
 842           if (mem_ok) {
 843             // Move the store out of the loop if the LCA of all
 844             // users (except for the phi) is outside the loop.
 845             Node* hook = new Node(1);
 846             _igvn.rehash_node_delayed(phi);
 847             int count = phi->replace_edge(n, hook);
 848             assert(count > 0, "inconsistent phi");
 849 
 850             // Compute latest point this store can go
 851             Node* lca = get_late_ctrl(n, get_ctrl(n));
 852             if (n_loop->is_member(get_loop(lca))) {
 853               // LCA is in the loop - bail out
 854               _igvn.replace_node(hook, n);
 855               return;
 856             }
 857 #ifdef ASSERT
 858             if (n_loop->_head->is_Loop() && n_loop->_head->as_Loop()->is_strip_mined()) {
 859               assert(n_loop->_head->Opcode() == Op_CountedLoop, "outer loop is a strip mined");
 860               n_loop->_head->as_Loop()->verify_strip_mined(1);
 861               Node* outer = n_loop->_head->as_CountedLoop()->outer_loop();
 862               IdealLoopTree* outer_loop = get_loop(outer);
 863               assert(n_loop->_parent == outer_loop, "broken loop tree");
 864               assert(get_loop(lca) == outer_loop, "safepoint in outer loop consume all memory state");
 865             }
 866 #endif
 867 
 868             // Move store out of the loop
 869             _igvn.replace_node(hook, n->in(MemNode::Memory));
 870             _igvn.replace_input_of(n, 0, lca);
 871             set_ctrl_and_loop(n, lca);
 872 
 873             // Disconnect the phi now. An empty phi can confuse other
 874             // optimizations in this pass of loop opts..
 875             if (phi->in(LoopNode::LoopBackControl) == phi) {
 876               _igvn.replace_node(phi, phi->in(LoopNode::EntryControl));
 877               n_loop->_body.yank(phi);
 878             }
 879           }
 880         }
 881       }
 882     }
 883   }
 884 }
 885 
 886 //------------------------------split_if_with_blocks_pre-----------------------
 887 // Do the real work in a non-recursive function.  Data nodes want to be
 888 // cloned in the pre-order so they can feed each other nicely.
 889 Node *PhaseIdealLoop::split_if_with_blocks_pre( Node *n ) {
 890   // Cloning these guys is unlikely to win
 891   int n_op = n->Opcode();
 892   if( n_op == Op_MergeMem ) return n;
 893   if( n->is_Proj() ) return n;
 894   // Do not clone-up CmpFXXX variations, as these are always
 895   // followed by a CmpI
 896   if( n->is_Cmp() ) return n;
 897   // Attempt to use a conditional move instead of a phi/branch
 898   if( ConditionalMoveLimit > 0 && n_op == Op_Region ) {
 899     Node *cmov = conditional_move( n );
 900     if( cmov ) return cmov;
 901   }
 902   if( n->is_CFG() || n->is_LoadStore() )
 903     return n;
 904   if( n_op == Op_Opaque1 ||     // Opaque nodes cannot be mod'd
 905       n_op == Op_Opaque2 ) {
 906     if( !C->major_progress() )   // If chance of no more loop opts...
 907       _igvn._worklist.push(n);  // maybe we'll remove them
 908     return n;
 909   }
 910 
 911   if( n->is_Con() ) return n;   // No cloning for Con nodes
 912 
 913   Node *n_ctrl = get_ctrl(n);
 914   if( !n_ctrl ) return n;       // Dead node
 915 
 916   Node* res = try_move_store_before_loop(n, n_ctrl);
 917   if (res != NULL) {
 918     return n;
 919   }
 920 
 921   // Attempt to remix address expressions for loop invariants
 922   Node *m = remix_address_expressions( n );
 923   if( m ) return m;
 924 
 925   if (n->is_ConstraintCast()) {
 926     Node* dom_cast = n->as_ConstraintCast()->dominating_cast(&_igvn, this);
 927     // ConstraintCastNode::dominating_cast() uses node control input to determine domination.
 928     // Node control inputs don't necessarily agree with loop control info (due to
 929     // transformations happened in between), thus additional dominance check is needed
 930     // to keep loop info valid.
 931     if (dom_cast != NULL && is_dominator(get_ctrl(dom_cast), get_ctrl(n))) {
 932       _igvn.replace_node(n, dom_cast);
 933       return dom_cast;
 934     }
 935   }
 936 
 937   // Determine if the Node has inputs from some local Phi.
 938   // Returns the block to clone thru.
 939   Node *n_blk = has_local_phi_input( n );
 940   if( !n_blk ) return n;
 941 
 942   // Do not clone the trip counter through on a CountedLoop
 943   // (messes up the canonical shape).
 944   if( n_blk->is_CountedLoop() && n->Opcode() == Op_AddI ) return n;
 945 
 946   // Check for having no control input; not pinned.  Allow
 947   // dominating control.
 948   if (n->in(0)) {
 949     Node *dom = idom(n_blk);
 950     if (dom_lca(n->in(0), dom) != n->in(0)) {
 951       return n;
 952     }
 953   }
 954   // Policy: when is it profitable.  You must get more wins than
 955   // policy before it is considered profitable.  Policy is usually 0,
 956   // so 1 win is considered profitable.  Big merges will require big
 957   // cloning, so get a larger policy.
 958   int policy = n_blk->req() >> 2;
 959 
 960   // If the loop is a candidate for range check elimination,
 961   // delay splitting through it's phi until a later loop optimization
 962   if (n_blk->is_CountedLoop()) {
 963     IdealLoopTree *lp = get_loop(n_blk);
 964     if (lp && lp->_rce_candidate) {
 965       return n;
 966     }
 967   }
 968 
 969   // Use same limit as split_if_with_blocks_post
 970   if( C->live_nodes() > 35000 ) return n; // Method too big
 971 
 972   // Split 'n' through the merge point if it is profitable
 973   Node *phi = split_thru_phi( n, n_blk, policy );
 974   if (!phi) return n;
 975 
 976   // Found a Phi to split thru!
 977   // Replace 'n' with the new phi
 978   _igvn.replace_node( n, phi );
 979   // Moved a load around the loop, 'en-registering' something.
 980   if (n_blk->is_Loop() && n->is_Load() &&
 981       !phi->in(LoopNode::LoopBackControl)->is_Load())
 982     C->set_major_progress();
 983 
 984   return phi;
 985 }
 986 
 987 static bool merge_point_too_heavy(Compile* C, Node* region) {
 988   // Bail out if the region and its phis have too many users.
 989   int weight = 0;
 990   for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
 991     weight += region->fast_out(i)->outcnt();
 992   }
 993   int nodes_left = C->max_node_limit() - C->live_nodes();
 994   if (weight * 8 > nodes_left) {
 995     if (PrintOpto) {
 996       tty->print_cr("*** Split-if bails out:  %d nodes, region weight %d", C->unique(), weight);
 997     }
 998     return true;
 999   } else {
1000     return false;
1001   }
1002 }
1003 
1004 static bool merge_point_safe(Node* region) {
1005   // 4799512: Stop split_if_with_blocks from splitting a block with a ConvI2LNode
1006   // having a PhiNode input. This sidesteps the dangerous case where the split
1007   // ConvI2LNode may become TOP if the input Value() does not
1008   // overlap the ConvI2L range, leaving a node which may not dominate its
1009   // uses.
1010   // A better fix for this problem can be found in the BugTraq entry, but
1011   // expediency for Mantis demands this hack.
1012   // 6855164: If the merge point has a FastLockNode with a PhiNode input, we stop
1013   // split_if_with_blocks from splitting a block because we could not move around
1014   // the FastLockNode.
1015   for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
1016     Node* n = region->fast_out(i);
1017     if (n->is_Phi()) {
1018       for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
1019         Node* m = n->fast_out(j);
1020         if (m->is_FastLock())
1021           return false;
1022 #ifdef _LP64
1023         if (m->Opcode() == Op_ConvI2L)
1024           return false;
1025         if (m->is_CastII() && m->isa_CastII()->has_range_check()) {
1026           return false;
1027         }
1028 #endif
1029       }
1030     }
1031   }
1032   return true;
1033 }
1034 
1035 
1036 //------------------------------place_near_use---------------------------------
1037 // Place some computation next to use but not inside inner loops.
1038 // For inner loop uses move it to the preheader area.
1039 Node *PhaseIdealLoop::place_near_use(Node *useblock) const {
1040   IdealLoopTree *u_loop = get_loop( useblock );
1041   if (u_loop->_irreducible) {
1042     return useblock;
1043   }
1044   if (u_loop->_child) {
1045     if (useblock == u_loop->_head && u_loop->_head->is_OuterStripMinedLoop()) {
1046       return u_loop->_head->in(LoopNode::EntryControl);
1047     }
1048     return useblock;
1049   }
1050   return u_loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl);
1051 }
1052 
1053 
1054 bool PhaseIdealLoop::identical_backtoback_ifs(Node *n) {
1055   if (!n->is_If() || n->is_CountedLoopEnd()) {
1056     return false;
1057   }
1058   if (!n->in(0)->is_Region()) {
1059     return false;
1060   }
1061   Node* region = n->in(0);
1062   Node* dom = idom(region);
1063   if (!dom->is_If() || dom->in(1) != n->in(1)) {
1064     return false;
1065   }
1066   IfNode* dom_if = dom->as_If();
1067   Node* proj_true = dom_if->proj_out(1);
1068   Node* proj_false = dom_if->proj_out(0);
1069 
1070   for (uint i = 1; i < region->req(); i++) {
1071     if (is_dominator(proj_true, region->in(i))) {
1072       continue;
1073     }
1074     if (is_dominator(proj_false, region->in(i))) {
1075       continue;
1076     }
1077     return false;
1078   }
1079 
1080   return true;
1081 }
1082 
1083 bool PhaseIdealLoop::can_split_if(Node *n_ctrl) {
1084   if (C->live_nodes() > 35000) {
1085     return false; // Method too big
1086   }
1087 
1088   // Do not do 'split-if' if irreducible loops are present.
1089   if (_has_irreducible_loops) {
1090     return false;
1091   }
1092 
1093   if (merge_point_too_heavy(C, n_ctrl)) {
1094     return false;
1095   }
1096 
1097   // Do not do 'split-if' if some paths are dead.  First do dead code
1098   // elimination and then see if its still profitable.
1099   for (uint i = 1; i < n_ctrl->req(); i++) {
1100     if (n_ctrl->in(i) == C->top()) {
1101       return false;
1102     }
1103   }
1104 
1105   // If trying to do a 'Split-If' at the loop head, it is only
1106   // profitable if the cmp folds up on BOTH paths.  Otherwise we
1107   // risk peeling a loop forever.
1108 
1109   // CNC - Disabled for now.  Requires careful handling of loop
1110   // body selection for the cloned code.  Also, make sure we check
1111   // for any input path not being in the same loop as n_ctrl.  For
1112   // irreducible loops we cannot check for 'n_ctrl->is_Loop()'
1113   // because the alternative loop entry points won't be converted
1114   // into LoopNodes.
1115   IdealLoopTree *n_loop = get_loop(n_ctrl);
1116   for (uint j = 1; j < n_ctrl->req(); j++) {
1117     if (get_loop(n_ctrl->in(j)) != n_loop) {
1118       return false;
1119     }
1120   }
1121 
1122   // Check for safety of the merge point.
1123   if (!merge_point_safe(n_ctrl)) {
1124     return false;
1125   }
1126 
1127   return true;
1128 }
1129 
1130 //------------------------------split_if_with_blocks_post----------------------
1131 // Do the real work in a non-recursive function.  CFG hackery wants to be
1132 // in the post-order, so it can dirty the I-DOM info and not use the dirtied
1133 // info.
1134 void PhaseIdealLoop::split_if_with_blocks_post(Node *n, bool last_round) {
1135 
1136   // Cloning Cmp through Phi's involves the split-if transform.
1137   // FastLock is not used by an If
1138   if (n->is_Cmp() && !n->is_FastLock() && !last_round) {
1139     Node *n_ctrl = get_ctrl(n);
1140     // Determine if the Node has inputs from some local Phi.
1141     // Returns the block to clone thru.
1142     Node *n_blk = has_local_phi_input(n);
1143     if (n_blk != n_ctrl) {
1144       return;
1145     }
1146 
1147     if (!can_split_if(n_ctrl)) {
1148       return;
1149     }
1150 
1151     if (n->outcnt() != 1) {
1152       return; // Multiple bool's from 1 compare?
1153     }
1154     Node *bol = n->unique_out();
1155     assert(bol->is_Bool(), "expect a bool here");
1156     if (bol->outcnt() != 1) {
1157       return;// Multiple branches from 1 compare?
1158     }
1159     Node *iff = bol->unique_out();
1160 
1161     // Check some safety conditions
1162     if (iff->is_If()) {        // Classic split-if?
1163       if (iff->in(0) != n_ctrl) {
1164         return; // Compare must be in same blk as if
1165       }
1166     } else if (iff->is_CMove()) { // Trying to split-up a CMOVE
1167       // Can't split CMove with different control edge.
1168       if (iff->in(0) != NULL && iff->in(0) != n_ctrl ) {
1169         return;
1170       }
1171       if (get_ctrl(iff->in(2)) == n_ctrl ||
1172           get_ctrl(iff->in(3)) == n_ctrl) {
1173         return;                 // Inputs not yet split-up
1174       }
1175       if (get_loop(n_ctrl) != get_loop(get_ctrl(iff))) {
1176         return;                 // Loop-invar test gates loop-varying CMOVE
1177       }
1178     } else {
1179       return;  // some other kind of node, such as an Allocate
1180     }
1181 
1182     // When is split-if profitable?  Every 'win' on means some control flow
1183     // goes dead, so it's almost always a win.
1184     int policy = 0;
1185     // Split compare 'n' through the merge point if it is profitable
1186     Node *phi = split_thru_phi( n, n_ctrl, policy);
1187     if (!phi) {
1188       return;
1189     }
1190 
1191     // Found a Phi to split thru!
1192     // Replace 'n' with the new phi
1193     _igvn.replace_node(n, phi);
1194 
1195     // Now split the bool up thru the phi
1196     Node *bolphi = split_thru_phi(bol, n_ctrl, -1);
1197     guarantee(bolphi != NULL, "null boolean phi node");
1198 
1199     _igvn.replace_node(bol, bolphi);
1200     assert(iff->in(1) == bolphi, "");
1201 
1202     if (bolphi->Value(&_igvn)->singleton()) {
1203       return;
1204     }
1205 
1206     // Conditional-move?  Must split up now
1207     if (!iff->is_If()) {
1208       Node *cmovphi = split_thru_phi(iff, n_ctrl, -1);
1209       _igvn.replace_node(iff, cmovphi);
1210       return;
1211     }
1212 
1213     // Now split the IF
1214     do_split_if(iff);
1215     return;
1216   }
1217 
1218   // Two identical ifs back to back can be merged
1219   if (identical_backtoback_ifs(n) && can_split_if(n->in(0))) {
1220     Node *n_ctrl = n->in(0);
1221     PhiNode* bolphi = PhiNode::make_blank(n_ctrl, n->in(1));
1222     IfNode* dom_if = idom(n_ctrl)->as_If();
1223     Node* proj_true = dom_if->proj_out(1);
1224     Node* proj_false = dom_if->proj_out(0);
1225     Node* con_true = _igvn.makecon(TypeInt::ONE);
1226     Node* con_false = _igvn.makecon(TypeInt::ZERO);
1227 
1228     for (uint i = 1; i < n_ctrl->req(); i++) {
1229       if (is_dominator(proj_true, n_ctrl->in(i))) {
1230         bolphi->init_req(i, con_true);
1231       } else {
1232         assert(is_dominator(proj_false, n_ctrl->in(i)), "bad if");
1233         bolphi->init_req(i, con_false);
1234       }
1235     }
1236     register_new_node(bolphi, n_ctrl);
1237     _igvn.replace_input_of(n, 1, bolphi);
1238 
1239     // Now split the IF
1240     do_split_if(n);
1241     return;
1242   }
1243 
1244   // Check for an IF ready to split; one that has its
1245   // condition codes input coming from a Phi at the block start.
1246   int n_op = n->Opcode();
1247 
1248   // Check for an IF being dominated by another IF same test
1249   if (n_op == Op_If ||
1250       n_op == Op_RangeCheck) {
1251     Node *bol = n->in(1);
1252     uint max = bol->outcnt();
1253     // Check for same test used more than once?
1254     if (max > 1 && bol->is_Bool()) {
1255       // Search up IDOMs to see if this IF is dominated.
1256       Node *cutoff = get_ctrl(bol);
1257 
1258       // Now search up IDOMs till cutoff, looking for a dominating test
1259       Node *prevdom = n;
1260       Node *dom = idom(prevdom);
1261       while (dom != cutoff) {
1262         if (dom->req() > 1 && dom->in(1) == bol && prevdom->in(0) == dom) {
1263           // Replace the dominated test with an obvious true or false.
1264           // Place it on the IGVN worklist for later cleanup.
1265           C->set_major_progress();
1266           dominated_by(prevdom, n, false, true);
1267 #ifndef PRODUCT
1268           if( VerifyLoopOptimizations ) verify();
1269 #endif
1270           return;
1271         }
1272         prevdom = dom;
1273         dom = idom(prevdom);
1274       }
1275     }
1276   }
1277 
1278   // See if a shared loop-varying computation has no loop-varying uses.
1279   // Happens if something is only used for JVM state in uncommon trap exits,
1280   // like various versions of induction variable+offset.  Clone the
1281   // computation per usage to allow it to sink out of the loop.
1282   if (has_ctrl(n) && !n->in(0)) {// n not dead and has no control edge (can float about)
1283     Node *n_ctrl = get_ctrl(n);
1284     IdealLoopTree *n_loop = get_loop(n_ctrl);
1285     if( n_loop != _ltree_root ) {
1286       DUIterator_Fast imax, i = n->fast_outs(imax);
1287       for (; i < imax; i++) {
1288         Node* u = n->fast_out(i);
1289         if( !has_ctrl(u) )     break; // Found control user
1290         IdealLoopTree *u_loop = get_loop(get_ctrl(u));
1291         if( u_loop == n_loop ) break; // Found loop-varying use
1292         if( n_loop->is_member( u_loop ) ) break; // Found use in inner loop
1293         if( u->Opcode() == Op_Opaque1 ) break; // Found loop limit, bugfix for 4677003
1294       }
1295       bool did_break = (i < imax);  // Did we break out of the previous loop?
1296       if (!did_break && n->outcnt() > 1) { // All uses in outer loops!
1297         Node *late_load_ctrl = NULL;
1298         if (n->is_Load()) {
1299           // If n is a load, get and save the result from get_late_ctrl(),
1300           // to be later used in calculating the control for n's clones.
1301           clear_dom_lca_tags();
1302           late_load_ctrl = get_late_ctrl(n, n_ctrl);
1303         }
1304         // If n is a load, and the late control is the same as the current
1305         // control, then the cloning of n is a pointless exercise, because
1306         // GVN will ensure that we end up where we started.
1307         if (!n->is_Load() || late_load_ctrl != n_ctrl) {
1308           for (DUIterator_Last jmin, j = n->last_outs(jmin); j >= jmin; ) {
1309             Node *u = n->last_out(j); // Clone private computation per use
1310             _igvn.rehash_node_delayed(u);
1311             Node *x = n->clone(); // Clone computation
1312             Node *x_ctrl = NULL;
1313             if( u->is_Phi() ) {
1314               // Replace all uses of normal nodes.  Replace Phi uses
1315               // individually, so the separate Nodes can sink down
1316               // different paths.
1317               uint k = 1;
1318               while( u->in(k) != n ) k++;
1319               u->set_req( k, x );
1320               // x goes next to Phi input path
1321               x_ctrl = u->in(0)->in(k);
1322               --j;
1323             } else {              // Normal use
1324               // Replace all uses
1325               for( uint k = 0; k < u->req(); k++ ) {
1326                 if( u->in(k) == n ) {
1327                   u->set_req( k, x );
1328                   --j;
1329                 }
1330               }
1331               x_ctrl = get_ctrl(u);
1332             }
1333 
1334             // Find control for 'x' next to use but not inside inner loops.
1335             // For inner loop uses get the preheader area.
1336             x_ctrl = place_near_use(x_ctrl);
1337 
1338             if (n->is_Load()) {
1339               // For loads, add a control edge to a CFG node outside of the loop
1340               // to force them to not combine and return back inside the loop
1341               // during GVN optimization (4641526).
1342               //
1343               // Because we are setting the actual control input, factor in
1344               // the result from get_late_ctrl() so we respect any
1345               // anti-dependences. (6233005).
1346               x_ctrl = dom_lca(late_load_ctrl, x_ctrl);
1347 
1348               // Don't allow the control input to be a CFG splitting node.
1349               // Such nodes should only have ProjNodes as outs, e.g. IfNode
1350               // should only have IfTrueNode and IfFalseNode (4985384).
1351               x_ctrl = find_non_split_ctrl(x_ctrl);
1352               assert(dom_depth(n_ctrl) <= dom_depth(x_ctrl), "n is later than its clone");
1353 
1354               x->set_req(0, x_ctrl);
1355             }
1356             register_new_node(x, x_ctrl);
1357 
1358             // Some institutional knowledge is needed here: 'x' is
1359             // yanked because if the optimizer runs GVN on it all the
1360             // cloned x's will common up and undo this optimization and
1361             // be forced back in the loop.  This is annoying because it
1362             // makes +VerifyOpto report false-positives on progress.  I
1363             // tried setting control edges on the x's to force them to
1364             // not combine, but the matching gets worried when it tries
1365             // to fold a StoreP and an AddP together (as part of an
1366             // address expression) and the AddP and StoreP have
1367             // different controls.
1368             if (!x->is_Load() && !x->is_DecodeNarrowPtr()) _igvn._worklist.yank(x);
1369           }
1370           _igvn.remove_dead_node(n);
1371         }
1372       }
1373     }
1374   }
1375 
1376   try_move_store_after_loop(n);
1377 
1378   // Check for Opaque2's who's loop has disappeared - who's input is in the
1379   // same loop nest as their output.  Remove 'em, they are no longer useful.
1380   if( n_op == Op_Opaque2 &&
1381       n->in(1) != NULL &&
1382       get_loop(get_ctrl(n)) == get_loop(get_ctrl(n->in(1))) ) {
1383     _igvn.replace_node( n, n->in(1) );
1384   }
1385 
1386 #if INCLUDE_ZGC
1387   if (UseZGC) {
1388     ZBarrierSetC2::loop_optimize_gc_barrier(this, n, last_round);
1389   }
1390 #endif
1391 }
1392 
1393 //------------------------------split_if_with_blocks---------------------------
1394 // Check for aggressive application of 'split-if' optimization,
1395 // using basic block level info.
1396 void PhaseIdealLoop::split_if_with_blocks(VectorSet &visited, Node_Stack &nstack, bool last_round) {
1397   Node *n = C->root();
1398   visited.set(n->_idx); // first, mark node as visited
1399   // Do pre-visit work for root
1400   n = split_if_with_blocks_pre( n );
1401   uint cnt = n->outcnt();
1402   uint i   = 0;
1403   while (true) {
1404     // Visit all children
1405     if (i < cnt) {
1406       Node* use = n->raw_out(i);
1407       ++i;
1408       if (use->outcnt() != 0 && !visited.test_set(use->_idx)) {
1409         // Now do pre-visit work for this use
1410         use = split_if_with_blocks_pre( use );
1411         nstack.push(n, i); // Save parent and next use's index.
1412         n   = use;         // Process all children of current use.
1413         cnt = use->outcnt();
1414         i   = 0;
1415       }
1416     }
1417     else {
1418       // All of n's children have been processed, complete post-processing.
1419       if (cnt != 0 && !n->is_Con()) {
1420         assert(has_node(n), "no dead nodes");
1421         split_if_with_blocks_post( n, last_round );
1422       }
1423       if (nstack.is_empty()) {
1424         // Finished all nodes on stack.
1425         break;
1426       }
1427       // Get saved parent node and next use's index. Visit the rest of uses.
1428       n   = nstack.node();
1429       cnt = n->outcnt();
1430       i   = nstack.index();
1431       nstack.pop();
1432     }
1433   }
1434 }
1435 
1436 
1437 //=============================================================================
1438 //
1439 //                   C L O N E   A   L O O P   B O D Y
1440 //
1441 
1442 //------------------------------clone_iff--------------------------------------
1443 // Passed in a Phi merging (recursively) some nearly equivalent Bool/Cmps.
1444 // "Nearly" because all Nodes have been cloned from the original in the loop,
1445 // but the fall-in edges to the Cmp are different.  Clone bool/Cmp pairs
1446 // through the Phi recursively, and return a Bool.
1447 Node* PhaseIdealLoop::clone_iff(PhiNode *phi, IdealLoopTree *loop) {
1448 
1449   // Convert this Phi into a Phi merging Bools
1450   uint i;
1451   for (i = 1; i < phi->req(); i++) {
1452     Node *b = phi->in(i);
1453     if (b->is_Phi()) {
1454       _igvn.replace_input_of(phi, i, clone_iff(b->as_Phi(), loop));
1455     } else {
1456       assert(b->is_Bool() || b->Opcode() == Op_Opaque4, "");
1457     }
1458   }
1459 
1460   Node* n = phi->in(1);
1461   Node* sample_opaque = NULL;
1462   Node *sample_bool = NULL;
1463   if (n->Opcode() == Op_Opaque4) {
1464     sample_opaque = n;
1465     sample_bool = n->in(1);
1466     assert(sample_bool->is_Bool(), "wrong type");
1467   } else {
1468     sample_bool = n;
1469   }
1470   Node *sample_cmp = sample_bool->in(1);
1471 
1472   // Make Phis to merge the Cmp's inputs.
1473   PhiNode *phi1 = new PhiNode(phi->in(0), Type::TOP);
1474   PhiNode *phi2 = new PhiNode(phi->in(0), Type::TOP);
1475   for (i = 1; i < phi->req(); i++) {
1476     Node *n1 = sample_opaque == NULL ? phi->in(i)->in(1)->in(1) : phi->in(i)->in(1)->in(1)->in(1);
1477     Node *n2 = sample_opaque == NULL ? phi->in(i)->in(1)->in(2) : phi->in(i)->in(1)->in(1)->in(2);
1478     phi1->set_req(i, n1);
1479     phi2->set_req(i, n2);
1480     phi1->set_type(phi1->type()->meet_speculative(n1->bottom_type()));
1481     phi2->set_type(phi2->type()->meet_speculative(n2->bottom_type()));
1482   }
1483   // See if these Phis have been made before.
1484   // Register with optimizer
1485   Node *hit1 = _igvn.hash_find_insert(phi1);
1486   if (hit1) {                   // Hit, toss just made Phi
1487     _igvn.remove_dead_node(phi1); // Remove new phi
1488     assert(hit1->is_Phi(), "" );
1489     phi1 = (PhiNode*)hit1;      // Use existing phi
1490   } else {                      // Miss
1491     _igvn.register_new_node_with_optimizer(phi1);
1492   }
1493   Node *hit2 = _igvn.hash_find_insert(phi2);
1494   if (hit2) {                   // Hit, toss just made Phi
1495     _igvn.remove_dead_node(phi2); // Remove new phi
1496     assert(hit2->is_Phi(), "" );
1497     phi2 = (PhiNode*)hit2;      // Use existing phi
1498   } else {                      // Miss
1499     _igvn.register_new_node_with_optimizer(phi2);
1500   }
1501   // Register Phis with loop/block info
1502   set_ctrl(phi1, phi->in(0));
1503   set_ctrl(phi2, phi->in(0));
1504   // Make a new Cmp
1505   Node *cmp = sample_cmp->clone();
1506   cmp->set_req(1, phi1);
1507   cmp->set_req(2, phi2);
1508   _igvn.register_new_node_with_optimizer(cmp);
1509   set_ctrl(cmp, phi->in(0));
1510 
1511   // Make a new Bool
1512   Node *b = sample_bool->clone();
1513   b->set_req(1,cmp);
1514   _igvn.register_new_node_with_optimizer(b);
1515   set_ctrl(b, phi->in(0));
1516 
1517   if (sample_opaque != NULL) {
1518     Node* opaque = sample_opaque->clone();
1519     opaque->set_req(1, b);
1520     _igvn.register_new_node_with_optimizer(opaque);
1521     set_ctrl(opaque, phi->in(0));
1522     return opaque;
1523   }
1524 
1525   assert(b->is_Bool(), "");
1526   return b;
1527 }
1528 
1529 //------------------------------clone_bool-------------------------------------
1530 // Passed in a Phi merging (recursively) some nearly equivalent Bool/Cmps.
1531 // "Nearly" because all Nodes have been cloned from the original in the loop,
1532 // but the fall-in edges to the Cmp are different.  Clone bool/Cmp pairs
1533 // through the Phi recursively, and return a Bool.
1534 CmpNode *PhaseIdealLoop::clone_bool( PhiNode *phi, IdealLoopTree *loop ) {
1535   uint i;
1536   // Convert this Phi into a Phi merging Bools
1537   for( i = 1; i < phi->req(); i++ ) {
1538     Node *b = phi->in(i);
1539     if( b->is_Phi() ) {
1540       _igvn.replace_input_of(phi, i, clone_bool( b->as_Phi(), loop ));
1541     } else {
1542       assert( b->is_Cmp() || b->is_top(), "inputs are all Cmp or TOP" );
1543     }
1544   }
1545 
1546   Node *sample_cmp = phi->in(1);
1547 
1548   // Make Phis to merge the Cmp's inputs.
1549   PhiNode *phi1 = new PhiNode( phi->in(0), Type::TOP );
1550   PhiNode *phi2 = new PhiNode( phi->in(0), Type::TOP );
1551   for( uint j = 1; j < phi->req(); j++ ) {
1552     Node *cmp_top = phi->in(j); // Inputs are all Cmp or TOP
1553     Node *n1, *n2;
1554     if( cmp_top->is_Cmp() ) {
1555       n1 = cmp_top->in(1);
1556       n2 = cmp_top->in(2);
1557     } else {
1558       n1 = n2 = cmp_top;
1559     }
1560     phi1->set_req( j, n1 );
1561     phi2->set_req( j, n2 );
1562     phi1->set_type(phi1->type()->meet_speculative(n1->bottom_type()));
1563     phi2->set_type(phi2->type()->meet_speculative(n2->bottom_type()));
1564   }
1565 
1566   // See if these Phis have been made before.
1567   // Register with optimizer
1568   Node *hit1 = _igvn.hash_find_insert(phi1);
1569   if( hit1 ) {                  // Hit, toss just made Phi
1570     _igvn.remove_dead_node(phi1); // Remove new phi
1571     assert( hit1->is_Phi(), "" );
1572     phi1 = (PhiNode*)hit1;      // Use existing phi
1573   } else {                      // Miss
1574     _igvn.register_new_node_with_optimizer(phi1);
1575   }
1576   Node *hit2 = _igvn.hash_find_insert(phi2);
1577   if( hit2 ) {                  // Hit, toss just made Phi
1578     _igvn.remove_dead_node(phi2); // Remove new phi
1579     assert( hit2->is_Phi(), "" );
1580     phi2 = (PhiNode*)hit2;      // Use existing phi
1581   } else {                      // Miss
1582     _igvn.register_new_node_with_optimizer(phi2);
1583   }
1584   // Register Phis with loop/block info
1585   set_ctrl(phi1, phi->in(0));
1586   set_ctrl(phi2, phi->in(0));
1587   // Make a new Cmp
1588   Node *cmp = sample_cmp->clone();
1589   cmp->set_req( 1, phi1 );
1590   cmp->set_req( 2, phi2 );
1591   _igvn.register_new_node_with_optimizer(cmp);
1592   set_ctrl(cmp, phi->in(0));
1593 
1594   assert( cmp->is_Cmp(), "" );
1595   return (CmpNode*)cmp;
1596 }
1597 
1598 //------------------------------sink_use---------------------------------------
1599 // If 'use' was in the loop-exit block, it now needs to be sunk
1600 // below the post-loop merge point.
1601 void PhaseIdealLoop::sink_use( Node *use, Node *post_loop ) {
1602   if (!use->is_CFG() && get_ctrl(use) == post_loop->in(2)) {
1603     set_ctrl(use, post_loop);
1604     for (DUIterator j = use->outs(); use->has_out(j); j++)
1605       sink_use(use->out(j), post_loop);
1606   }
1607 }
1608 
1609 void PhaseIdealLoop::clone_loop_handle_data_uses(Node* old, Node_List &old_new,
1610                                                  IdealLoopTree* loop, IdealLoopTree* outer_loop,
1611                                                  Node_List*& split_if_set, Node_List*& split_bool_set,
1612                                                  Node_List*& split_cex_set, Node_List& worklist,
1613                                                  uint new_counter, CloneLoopMode mode) {
1614   Node* nnn = old_new[old->_idx];
1615   // Copy uses to a worklist, so I can munge the def-use info
1616   // with impunity.
1617   for (DUIterator_Fast jmax, j = old->fast_outs(jmax); j < jmax; j++)
1618     worklist.push(old->fast_out(j));
1619 
1620   while( worklist.size() ) {
1621     Node *use = worklist.pop();
1622     if (!has_node(use))  continue; // Ignore dead nodes
1623     if (use->in(0) == C->top())  continue;
1624     IdealLoopTree *use_loop = get_loop( has_ctrl(use) ? get_ctrl(use) : use );
1625     // Check for data-use outside of loop - at least one of OLD or USE
1626     // must not be a CFG node.
1627 #ifdef ASSERT
1628     if (loop->_head->as_Loop()->is_strip_mined() && outer_loop->is_member(use_loop) && !loop->is_member(use_loop) && old_new[use->_idx] == NULL) {
1629       Node* sfpt = loop->_head->as_CountedLoop()->outer_safepoint();
1630       assert(mode == ControlAroundStripMined && use == sfpt, "missed a node");
1631     }
1632 #endif
1633     if (!loop->is_member(use_loop) && !outer_loop->is_member(use_loop) && (!old->is_CFG() || !use->is_CFG())) {
1634 
1635       // If the Data use is an IF, that means we have an IF outside of the
1636       // loop that is switching on a condition that is set inside of the
1637       // loop.  Happens if people set a loop-exit flag; then test the flag
1638       // in the loop to break the loop, then test is again outside of the
1639       // loop to determine which way the loop exited.
1640       // Loop predicate If node connects to Bool node through Opaque1 node.
1641       if (use->is_If() || use->is_CMove() || C->is_predicate_opaq(use) || use->Opcode() == Op_Opaque4) {
1642         // Since this code is highly unlikely, we lazily build the worklist
1643         // of such Nodes to go split.
1644         if (!split_if_set) {
1645           ResourceArea *area = Thread::current()->resource_area();
1646           split_if_set = new Node_List(area);
1647         }
1648         split_if_set->push(use);
1649       }
1650       if (use->is_Bool()) {
1651         if (!split_bool_set) {
1652           ResourceArea *area = Thread::current()->resource_area();
1653           split_bool_set = new Node_List(area);
1654         }
1655         split_bool_set->push(use);
1656       }
1657       if (use->Opcode() == Op_CreateEx) {
1658         if (!split_cex_set) {
1659           ResourceArea *area = Thread::current()->resource_area();
1660           split_cex_set = new Node_List(area);
1661         }
1662         split_cex_set->push(use);
1663       }
1664 
1665 
1666       // Get "block" use is in
1667       uint idx = 0;
1668       while( use->in(idx) != old ) idx++;
1669       Node *prev = use->is_CFG() ? use : get_ctrl(use);
1670       assert(!loop->is_member(get_loop(prev)) && !outer_loop->is_member(get_loop(prev)), "" );
1671       Node *cfg = prev->_idx >= new_counter
1672         ? prev->in(2)
1673         : idom(prev);
1674       if( use->is_Phi() )     // Phi use is in prior block
1675         cfg = prev->in(idx);  // NOT in block of Phi itself
1676       if (cfg->is_top()) {    // Use is dead?
1677         _igvn.replace_input_of(use, idx, C->top());
1678         continue;
1679       }
1680 
1681       // If use is referenced through control edge... (idx == 0)
1682       if (mode == IgnoreStripMined && idx == 0) {
1683         LoopNode *head = loop->_head->as_Loop();
1684         if (head->is_strip_mined() && is_dominator(head->outer_loop_exit(), prev)) {
1685           // That node is outside the inner loop, leave it outside the
1686           // outer loop as well to not confuse verification code.
1687           assert(!loop->_parent->is_member(use_loop), "should be out of the outer loop");
1688           _igvn.replace_input_of(use, 0, head->outer_loop_exit());
1689           continue;
1690         }
1691       }
1692 
1693       while(!outer_loop->is_member(get_loop(cfg))) {
1694         prev = cfg;
1695         cfg = cfg->_idx >= new_counter ? cfg->in(2) : idom(cfg);
1696       }
1697       // If the use occurs after merging several exits from the loop, then
1698       // old value must have dominated all those exits.  Since the same old
1699       // value was used on all those exits we did not need a Phi at this
1700       // merge point.  NOW we do need a Phi here.  Each loop exit value
1701       // is now merged with the peeled body exit; each exit gets its own
1702       // private Phi and those Phis need to be merged here.
1703       Node *phi;
1704       if( prev->is_Region() ) {
1705         if( idx == 0 ) {      // Updating control edge?
1706           phi = prev;         // Just use existing control
1707         } else {              // Else need a new Phi
1708           phi = PhiNode::make( prev, old );
1709           // Now recursively fix up the new uses of old!
1710           for( uint i = 1; i < prev->req(); i++ ) {
1711             worklist.push(phi); // Onto worklist once for each 'old' input
1712           }
1713         }
1714       } else {
1715         // Get new RegionNode merging old and new loop exits
1716         prev = old_new[prev->_idx];
1717         assert( prev, "just made this in step 7" );
1718         if( idx == 0) {      // Updating control edge?
1719           phi = prev;         // Just use existing control
1720         } else {              // Else need a new Phi
1721           // Make a new Phi merging data values properly
1722           phi = PhiNode::make( prev, old );
1723           phi->set_req( 1, nnn );
1724         }
1725       }
1726       // If inserting a new Phi, check for prior hits
1727       if( idx != 0 ) {
1728         Node *hit = _igvn.hash_find_insert(phi);
1729         if( hit == NULL ) {
1730           _igvn.register_new_node_with_optimizer(phi); // Register new phi
1731         } else {                                      // or
1732           // Remove the new phi from the graph and use the hit
1733           _igvn.remove_dead_node(phi);
1734           phi = hit;                                  // Use existing phi
1735         }
1736         set_ctrl(phi, prev);
1737       }
1738       // Make 'use' use the Phi instead of the old loop body exit value
1739       _igvn.replace_input_of(use, idx, phi);
1740       if( use->_idx >= new_counter ) { // If updating new phis
1741         // Not needed for correctness, but prevents a weak assert
1742         // in AddPNode from tripping (when we end up with different
1743         // base & derived Phis that will become the same after
1744         // IGVN does CSE).
1745         Node *hit = _igvn.hash_find_insert(use);
1746         if( hit )             // Go ahead and re-hash for hits.
1747           _igvn.replace_node( use, hit );
1748       }
1749 
1750       // If 'use' was in the loop-exit block, it now needs to be sunk
1751       // below the post-loop merge point.
1752       sink_use( use, prev );
1753     }
1754   }
1755 }
1756 
1757 static void clone_outer_loop_helper(Node* n, const IdealLoopTree *loop, const IdealLoopTree* outer_loop,
1758                                     const Node_List &old_new, Unique_Node_List& wq, PhaseIdealLoop* phase,
1759                                     bool check_old_new) {
1760   for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
1761     Node* u = n->fast_out(j);
1762     assert(check_old_new || old_new[u->_idx] == NULL, "shouldn't have been cloned");
1763     if (!u->is_CFG() && (!check_old_new || old_new[u->_idx] == NULL)) {
1764       Node* c = phase->get_ctrl(u);
1765       IdealLoopTree* u_loop = phase->get_loop(c);
1766       assert(!loop->is_member(u_loop), "can be in outer loop or out of both loops only");
1767       if (outer_loop->is_member(u_loop)) {
1768         wq.push(u);
1769       }
1770     }
1771   }
1772 }
1773 
1774 void PhaseIdealLoop::clone_outer_loop(LoopNode* head, CloneLoopMode mode, IdealLoopTree *loop,
1775                                       IdealLoopTree* outer_loop, int dd, Node_List &old_new,
1776                                       Node_List& extra_data_nodes) {
1777   if (head->is_strip_mined() && mode != IgnoreStripMined) {
1778     CountedLoopNode* cl = head->as_CountedLoop();
1779     Node* l = cl->outer_loop();
1780     Node* tail = cl->outer_loop_tail();
1781     IfNode* le = cl->outer_loop_end();
1782     Node* sfpt = cl->outer_safepoint();
1783     CountedLoopEndNode* cle = cl->loopexit();
1784     CountedLoopNode* new_cl = old_new[cl->_idx]->as_CountedLoop();
1785     CountedLoopEndNode* new_cle = new_cl->as_CountedLoop()->loopexit_or_null();
1786     Node* cle_out = cle->proj_out(false);
1787 
1788     Node* new_sfpt = NULL;
1789     Node* new_cle_out = cle_out->clone();
1790     old_new.map(cle_out->_idx, new_cle_out);
1791     if (mode == CloneIncludesStripMined) {
1792       // clone outer loop body
1793       Node* new_l = l->clone();
1794       Node* new_tail = tail->clone();
1795       IfNode* new_le = le->clone()->as_If();
1796       new_sfpt = sfpt->clone();
1797 
1798       set_loop(new_l, outer_loop->_parent);
1799       set_idom(new_l, new_l->in(LoopNode::EntryControl), dd);
1800       set_loop(new_cle_out, outer_loop->_parent);
1801       set_idom(new_cle_out, new_cle, dd);
1802       set_loop(new_sfpt, outer_loop->_parent);
1803       set_idom(new_sfpt, new_cle_out, dd);
1804       set_loop(new_le, outer_loop->_parent);
1805       set_idom(new_le, new_sfpt, dd);
1806       set_loop(new_tail, outer_loop->_parent);
1807       set_idom(new_tail, new_le, dd);
1808       set_idom(new_cl, new_l, dd);
1809 
1810       old_new.map(l->_idx, new_l);
1811       old_new.map(tail->_idx, new_tail);
1812       old_new.map(le->_idx, new_le);
1813       old_new.map(sfpt->_idx, new_sfpt);
1814 
1815       new_l->set_req(LoopNode::LoopBackControl, new_tail);
1816       new_l->set_req(0, new_l);
1817       new_tail->set_req(0, new_le);
1818       new_le->set_req(0, new_sfpt);
1819       new_sfpt->set_req(0, new_cle_out);
1820       new_cle_out->set_req(0, new_cle);
1821       new_cl->set_req(LoopNode::EntryControl, new_l);
1822 
1823       _igvn.register_new_node_with_optimizer(new_l);
1824       _igvn.register_new_node_with_optimizer(new_tail);
1825       _igvn.register_new_node_with_optimizer(new_le);
1826     } else {
1827       Node *newhead = old_new[loop->_head->_idx];
1828       newhead->as_Loop()->clear_strip_mined();
1829       _igvn.replace_input_of(newhead, LoopNode::EntryControl, newhead->in(LoopNode::EntryControl)->in(LoopNode::EntryControl));
1830       set_idom(newhead, newhead->in(LoopNode::EntryControl), dd);
1831     }
1832     // Look at data node that were assigned a control in the outer
1833     // loop: they are kept in the outer loop by the safepoint so start
1834     // from the safepoint node's inputs.
1835     IdealLoopTree* outer_loop = get_loop(l);
1836     Node_Stack stack(2);
1837     stack.push(sfpt, 1);
1838     uint new_counter = C->unique();
1839     while (stack.size() > 0) {
1840       Node* n = stack.node();
1841       uint i = stack.index();
1842       while (i < n->req() &&
1843              (n->in(i) == NULL ||
1844               !has_ctrl(n->in(i)) ||
1845               get_loop(get_ctrl(n->in(i))) != outer_loop ||
1846               (old_new[n->in(i)->_idx] != NULL && old_new[n->in(i)->_idx]->_idx >= new_counter))) {
1847         i++;
1848       }
1849       if (i < n->req()) {
1850         stack.set_index(i+1);
1851         stack.push(n->in(i), 0);
1852       } else {
1853         assert(old_new[n->_idx] == NULL || n == sfpt || old_new[n->_idx]->_idx < new_counter, "no clone yet");
1854         Node* m = n == sfpt ? new_sfpt : n->clone();
1855         if (m != NULL) {
1856           for (uint i = 0; i < n->req(); i++) {
1857             if (m->in(i) != NULL && old_new[m->in(i)->_idx] != NULL) {
1858               m->set_req(i, old_new[m->in(i)->_idx]);
1859             }
1860           }
1861         } else {
1862           assert(n == sfpt && mode != CloneIncludesStripMined, "where's the safepoint clone?");
1863         }
1864         if (n != sfpt) {
1865           extra_data_nodes.push(n);
1866           _igvn.register_new_node_with_optimizer(m);
1867           assert(get_ctrl(n) == cle_out, "what other control?");
1868           set_ctrl(m, new_cle_out);
1869           old_new.map(n->_idx, m);
1870         }
1871         stack.pop();
1872       }
1873     }
1874     if (mode == CloneIncludesStripMined) {
1875       _igvn.register_new_node_with_optimizer(new_sfpt);
1876       _igvn.register_new_node_with_optimizer(new_cle_out);
1877     }
1878     // Some other transformation may have pessimistically assign some
1879     // data nodes to the outer loop. Set their control so they are out
1880     // of the outer loop.
1881     ResourceMark rm;
1882     Unique_Node_List wq;
1883     for (uint i = 0; i < extra_data_nodes.size(); i++) {
1884       Node* old = extra_data_nodes.at(i);
1885       clone_outer_loop_helper(old, loop, outer_loop, old_new, wq, this, true);
1886     }
1887     Node* new_ctrl = cl->outer_loop_exit();
1888     assert(get_loop(new_ctrl) != outer_loop, "must be out of the loop nest");
1889     for (uint i = 0; i < wq.size(); i++) {
1890       Node* n = wq.at(i);
1891       set_ctrl(n, new_ctrl);
1892       clone_outer_loop_helper(n, loop, outer_loop, old_new, wq, this, false);
1893     }
1894   } else {
1895     Node *newhead = old_new[loop->_head->_idx];
1896     set_idom(newhead, newhead->in(LoopNode::EntryControl), dd);
1897   }
1898 }
1899 
1900 //------------------------------clone_loop-------------------------------------
1901 //
1902 //                   C L O N E   A   L O O P   B O D Y
1903 //
1904 // This is the basic building block of the loop optimizations.  It clones an
1905 // entire loop body.  It makes an old_new loop body mapping; with this mapping
1906 // you can find the new-loop equivalent to an old-loop node.  All new-loop
1907 // nodes are exactly equal to their old-loop counterparts, all edges are the
1908 // same.  All exits from the old-loop now have a RegionNode that merges the
1909 // equivalent new-loop path.  This is true even for the normal "loop-exit"
1910 // condition.  All uses of loop-invariant old-loop values now come from (one
1911 // or more) Phis that merge their new-loop equivalents.
1912 //
1913 // This operation leaves the graph in an illegal state: there are two valid
1914 // control edges coming from the loop pre-header to both loop bodies.  I'll
1915 // definitely have to hack the graph after running this transform.
1916 //
1917 // From this building block I will further edit edges to perform loop peeling
1918 // or loop unrolling or iteration splitting (Range-Check-Elimination), etc.
1919 //
1920 // Parameter side_by_size_idom:
1921 //   When side_by_size_idom is NULL, the dominator tree is constructed for
1922 //      the clone loop to dominate the original.  Used in construction of
1923 //      pre-main-post loop sequence.
1924 //   When nonnull, the clone and original are side-by-side, both are
1925 //      dominated by the side_by_side_idom node.  Used in construction of
1926 //      unswitched loops.
1927 void PhaseIdealLoop::clone_loop( IdealLoopTree *loop, Node_List &old_new, int dd,
1928                                 CloneLoopMode mode, Node* side_by_side_idom) {
1929 
1930   LoopNode* head = loop->_head->as_Loop();
1931   head->verify_strip_mined(1);
1932 
1933   if (C->do_vector_loop() && PrintOpto) {
1934     const char* mname = C->method()->name()->as_quoted_ascii();
1935     if (mname != NULL) {
1936       tty->print("PhaseIdealLoop::clone_loop: for vectorize method %s\n", mname);
1937     }
1938   }
1939 
1940   CloneMap& cm = C->clone_map();
1941   Dict* dict = cm.dict();
1942   if (C->do_vector_loop()) {
1943     cm.set_clone_idx(cm.max_gen()+1);
1944 #ifndef PRODUCT
1945     if (PrintOpto) {
1946       tty->print_cr("PhaseIdealLoop::clone_loop: _clone_idx %d", cm.clone_idx());
1947       loop->dump_head();
1948     }
1949 #endif
1950   }
1951 
1952   // Step 1: Clone the loop body.  Make the old->new mapping.
1953   uint i;
1954   for( i = 0; i < loop->_body.size(); i++ ) {
1955     Node *old = loop->_body.at(i);
1956     Node *nnn = old->clone();
1957     old_new.map( old->_idx, nnn );
1958     if (C->do_vector_loop()) {
1959       cm.verify_insert_and_clone(old, nnn, cm.clone_idx());
1960     }
1961     _igvn.register_new_node_with_optimizer(nnn);
1962   }
1963 
1964   IdealLoopTree* outer_loop = (head->is_strip_mined() && mode != IgnoreStripMined) ? get_loop(head->as_CountedLoop()->outer_loop()) : loop;
1965 
1966   // Step 2: Fix the edges in the new body.  If the old input is outside the
1967   // loop use it.  If the old input is INside the loop, use the corresponding
1968   // new node instead.
1969   for( i = 0; i < loop->_body.size(); i++ ) {
1970     Node *old = loop->_body.at(i);
1971     Node *nnn = old_new[old->_idx];
1972     // Fix CFG/Loop controlling the new node
1973     if (has_ctrl(old)) {
1974       set_ctrl(nnn, old_new[get_ctrl(old)->_idx]);
1975     } else {
1976       set_loop(nnn, outer_loop->_parent);
1977       if (old->outcnt() > 0) {
1978         set_idom( nnn, old_new[idom(old)->_idx], dd );
1979       }
1980     }
1981     // Correct edges to the new node
1982     for( uint j = 0; j < nnn->req(); j++ ) {
1983         Node *n = nnn->in(j);
1984         if( n ) {
1985           IdealLoopTree *old_in_loop = get_loop( has_ctrl(n) ? get_ctrl(n) : n );
1986           if( loop->is_member( old_in_loop ) )
1987             nnn->set_req(j, old_new[n->_idx]);
1988         }
1989     }
1990     _igvn.hash_find_insert(nnn);
1991   }
1992 
1993   ResourceArea *area = Thread::current()->resource_area();
1994   Node_List extra_data_nodes(area); // data nodes in the outer strip mined loop
1995   clone_outer_loop(head, mode, loop, outer_loop, dd, old_new, extra_data_nodes);
1996 
1997   // Step 3: Now fix control uses.  Loop varying control uses have already
1998   // been fixed up (as part of all input edges in Step 2).  Loop invariant
1999   // control uses must be either an IfFalse or an IfTrue.  Make a merge
2000   // point to merge the old and new IfFalse/IfTrue nodes; make the use
2001   // refer to this.
2002   Node_List worklist(area);
2003   uint new_counter = C->unique();
2004   for( i = 0; i < loop->_body.size(); i++ ) {
2005     Node* old = loop->_body.at(i);
2006     if( !old->is_CFG() ) continue;
2007 
2008     // Copy uses to a worklist, so I can munge the def-use info
2009     // with impunity.
2010     for (DUIterator_Fast jmax, j = old->fast_outs(jmax); j < jmax; j++)
2011       worklist.push(old->fast_out(j));
2012 
2013     while( worklist.size() ) {  // Visit all uses
2014       Node *use = worklist.pop();
2015       if (!has_node(use))  continue; // Ignore dead nodes
2016       IdealLoopTree *use_loop = get_loop( has_ctrl(use) ? get_ctrl(use) : use );
2017       if( !loop->is_member( use_loop ) && use->is_CFG() ) {
2018         // Both OLD and USE are CFG nodes here.
2019         assert( use->is_Proj(), "" );
2020         Node* nnn = old_new[old->_idx];
2021 
2022         Node* newuse = NULL;
2023         if (head->is_strip_mined() && mode != IgnoreStripMined) {
2024           CountedLoopNode* cl = head->as_CountedLoop();
2025           CountedLoopEndNode* cle = cl->loopexit();
2026           Node* cle_out = cle->proj_out_or_null(false);
2027           if (use == cle_out) {
2028             IfNode* le = cl->outer_loop_end();
2029             use = le->proj_out(false);
2030             use_loop = get_loop(use);
2031             if (mode == CloneIncludesStripMined) {
2032               nnn = old_new[le->_idx];
2033             } else {
2034               newuse = old_new[cle_out->_idx];
2035             }
2036           }
2037         }
2038         if (newuse == NULL) {
2039           newuse = use->clone();
2040         }
2041 
2042         // Clone the loop exit control projection
2043         if (C->do_vector_loop()) {
2044           cm.verify_insert_and_clone(use, newuse, cm.clone_idx());
2045         }
2046         newuse->set_req(0,nnn);
2047         _igvn.register_new_node_with_optimizer(newuse);
2048         set_loop(newuse, use_loop);
2049         set_idom(newuse, nnn, dom_depth(nnn) + 1 );
2050 
2051         // We need a Region to merge the exit from the peeled body and the
2052         // exit from the old loop body.
2053         RegionNode *r = new RegionNode(3);
2054         // Map the old use to the new merge point
2055         old_new.map( use->_idx, r );
2056         uint dd_r = MIN2(dom_depth(newuse),dom_depth(use));
2057         assert( dd_r >= dom_depth(dom_lca(newuse,use)), "" );
2058 
2059         // The original user of 'use' uses 'r' instead.
2060         for (DUIterator_Last lmin, l = use->last_outs(lmin); l >= lmin;) {
2061           Node* useuse = use->last_out(l);
2062           _igvn.rehash_node_delayed(useuse);
2063           uint uses_found = 0;
2064           if( useuse->in(0) == use ) {
2065             useuse->set_req(0, r);
2066             uses_found++;
2067             if( useuse->is_CFG() ) {
2068               assert( dom_depth(useuse) > dd_r, "" );
2069               set_idom(useuse, r, dom_depth(useuse));
2070             }
2071           }
2072           for( uint k = 1; k < useuse->req(); k++ ) {
2073             if( useuse->in(k) == use ) {
2074               useuse->set_req(k, r);
2075               uses_found++;
2076               if (useuse->is_Loop() && k == LoopNode::EntryControl) {
2077                 assert(dom_depth(useuse) > dd_r , "");
2078                 set_idom(useuse, r, dom_depth(useuse));
2079               }
2080             }
2081           }
2082           l -= uses_found;    // we deleted 1 or more copies of this edge
2083         }
2084 
2085         // Now finish up 'r'
2086         r->set_req( 1, newuse );
2087         r->set_req( 2,    use );
2088         _igvn.register_new_node_with_optimizer(r);
2089         set_loop(r, use_loop);
2090         set_idom(r, !side_by_side_idom ? newuse->in(0) : side_by_side_idom, dd_r);
2091       } // End of if a loop-exit test
2092     }
2093   }
2094 
2095   // Step 4: If loop-invariant use is not control, it must be dominated by a
2096   // loop exit IfFalse/IfTrue.  Find "proper" loop exit.  Make a Region
2097   // there if needed.  Make a Phi there merging old and new used values.
2098   Node_List *split_if_set = NULL;
2099   Node_List *split_bool_set = NULL;
2100   Node_List *split_cex_set = NULL;
2101   for( i = 0; i < loop->_body.size(); i++ ) {
2102     Node* old = loop->_body.at(i);
2103     clone_loop_handle_data_uses(old, old_new, loop, outer_loop, split_if_set,
2104                                 split_bool_set, split_cex_set, worklist, new_counter,
2105                                 mode);
2106   }
2107 
2108   for (i = 0; i < extra_data_nodes.size(); i++) {
2109     Node* old = extra_data_nodes.at(i);
2110     clone_loop_handle_data_uses(old, old_new, loop, outer_loop, split_if_set,
2111                                 split_bool_set, split_cex_set, worklist, new_counter,
2112                                 mode);
2113   }
2114 
2115   // Check for IFs that need splitting/cloning.  Happens if an IF outside of
2116   // the loop uses a condition set in the loop.  The original IF probably
2117   // takes control from one or more OLD Regions (which in turn get from NEW
2118   // Regions).  In any case, there will be a set of Phis for each merge point
2119   // from the IF up to where the original BOOL def exists the loop.
2120   if (split_if_set) {
2121     while (split_if_set->size()) {
2122       Node *iff = split_if_set->pop();
2123       if (iff->in(1)->is_Phi()) {
2124         Node *b = clone_iff(iff->in(1)->as_Phi(), loop);
2125         _igvn.replace_input_of(iff, 1, b);
2126       }
2127     }
2128   }
2129   if (split_bool_set) {
2130     while (split_bool_set->size()) {
2131       Node *b = split_bool_set->pop();
2132       Node *phi = b->in(1);
2133       assert(phi->is_Phi(), "");
2134       CmpNode *cmp = clone_bool((PhiNode*)phi, loop);
2135       _igvn.replace_input_of(b, 1, cmp);
2136     }
2137   }
2138   if (split_cex_set) {
2139     while (split_cex_set->size()) {
2140       Node *b = split_cex_set->pop();
2141       assert(b->in(0)->is_Region(), "");
2142       assert(b->in(1)->is_Phi(), "");
2143       assert(b->in(0)->in(0) == b->in(1)->in(0), "");
2144       split_up(b, b->in(0), NULL);
2145     }
2146   }
2147 
2148 }
2149 
2150 
2151 //---------------------- stride_of_possible_iv -------------------------------------
2152 // Looks for an iff/bool/comp with one operand of the compare
2153 // being a cycle involving an add and a phi,
2154 // with an optional truncation (left-shift followed by a right-shift)
2155 // of the add. Returns zero if not an iv.
2156 int PhaseIdealLoop::stride_of_possible_iv(Node* iff) {
2157   Node* trunc1 = NULL;
2158   Node* trunc2 = NULL;
2159   const TypeInt* ttype = NULL;
2160   if (!iff->is_If() || iff->in(1) == NULL || !iff->in(1)->is_Bool()) {
2161     return 0;
2162   }
2163   BoolNode* bl = iff->in(1)->as_Bool();
2164   Node* cmp = bl->in(1);
2165   if (!cmp || (cmp->Opcode() != Op_CmpI && cmp->Opcode() != Op_CmpU)) {
2166     return 0;
2167   }
2168   // Must have an invariant operand
2169   if (is_member(get_loop(iff), get_ctrl(cmp->in(2)))) {
2170     return 0;
2171   }
2172   Node* add2 = NULL;
2173   Node* cmp1 = cmp->in(1);
2174   if (cmp1->is_Phi()) {
2175     // (If (Bool (CmpX phi:(Phi ...(Optional-trunc(AddI phi add2))) )))
2176     Node* phi = cmp1;
2177     for (uint i = 1; i < phi->req(); i++) {
2178       Node* in = phi->in(i);
2179       Node* add = CountedLoopNode::match_incr_with_optional_truncation(in,
2180                                 &trunc1, &trunc2, &ttype);
2181       if (add && add->in(1) == phi) {
2182         add2 = add->in(2);
2183         break;
2184       }
2185     }
2186   } else {
2187     // (If (Bool (CmpX addtrunc:(Optional-trunc((AddI (Phi ...addtrunc...) add2)) )))
2188     Node* addtrunc = cmp1;
2189     Node* add = CountedLoopNode::match_incr_with_optional_truncation(addtrunc,
2190                                 &trunc1, &trunc2, &ttype);
2191     if (add && add->in(1)->is_Phi()) {
2192       Node* phi = add->in(1);
2193       for (uint i = 1; i < phi->req(); i++) {
2194         if (phi->in(i) == addtrunc) {
2195           add2 = add->in(2);
2196           break;
2197         }
2198       }
2199     }
2200   }
2201   if (add2 != NULL) {
2202     const TypeInt* add2t = _igvn.type(add2)->is_int();
2203     if (add2t->is_con()) {
2204       return add2t->get_con();
2205     }
2206   }
2207   return 0;
2208 }
2209 
2210 
2211 //---------------------- stay_in_loop -------------------------------------
2212 // Return the (unique) control output node that's in the loop (if it exists.)
2213 Node* PhaseIdealLoop::stay_in_loop( Node* n, IdealLoopTree *loop) {
2214   Node* unique = NULL;
2215   if (!n) return NULL;
2216   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2217     Node* use = n->fast_out(i);
2218     if (!has_ctrl(use) && loop->is_member(get_loop(use))) {
2219       if (unique != NULL) {
2220         return NULL;
2221       }
2222       unique = use;
2223     }
2224   }
2225   return unique;
2226 }
2227 
2228 //------------------------------ register_node -------------------------------------
2229 // Utility to register node "n" with PhaseIdealLoop
2230 void PhaseIdealLoop::register_node(Node* n, IdealLoopTree *loop, Node* pred, int ddepth) {
2231   _igvn.register_new_node_with_optimizer(n);
2232   loop->_body.push(n);
2233   if (n->is_CFG()) {
2234     set_loop(n, loop);
2235     set_idom(n, pred, ddepth);
2236   } else {
2237     set_ctrl(n, pred);
2238   }
2239 }
2240 
2241 //------------------------------ proj_clone -------------------------------------
2242 // Utility to create an if-projection
2243 ProjNode* PhaseIdealLoop::proj_clone(ProjNode* p, IfNode* iff) {
2244   ProjNode* c = p->clone()->as_Proj();
2245   c->set_req(0, iff);
2246   return c;
2247 }
2248 
2249 //------------------------------ short_circuit_if -------------------------------------
2250 // Force the iff control output to be the live_proj
2251 Node* PhaseIdealLoop::short_circuit_if(IfNode* iff, ProjNode* live_proj) {
2252   guarantee(live_proj != NULL, "null projection");
2253   int proj_con = live_proj->_con;
2254   assert(proj_con == 0 || proj_con == 1, "false or true projection");
2255   Node *con = _igvn.intcon(proj_con);
2256   set_ctrl(con, C->root());
2257   if (iff) {
2258     iff->set_req(1, con);
2259   }
2260   return con;
2261 }
2262 
2263 //------------------------------ insert_if_before_proj -------------------------------------
2264 // Insert a new if before an if projection (* - new node)
2265 //
2266 // before
2267 //           if(test)
2268 //           /     \
2269 //          v       v
2270 //    other-proj   proj (arg)
2271 //
2272 // after
2273 //           if(test)
2274 //           /     \
2275 //          /       v
2276 //         |      * proj-clone
2277 //         v          |
2278 //    other-proj      v
2279 //                * new_if(relop(cmp[IU](left,right)))
2280 //                  /  \
2281 //                 v    v
2282 //         * new-proj  proj
2283 //         (returned)
2284 //
2285 ProjNode* PhaseIdealLoop::insert_if_before_proj(Node* left, bool Signed, BoolTest::mask relop, Node* right, ProjNode* proj) {
2286   IfNode* iff = proj->in(0)->as_If();
2287   IdealLoopTree *loop = get_loop(proj);
2288   ProjNode *other_proj = iff->proj_out(!proj->is_IfTrue())->as_Proj();
2289   int ddepth = dom_depth(proj);
2290 
2291   _igvn.rehash_node_delayed(iff);
2292   _igvn.rehash_node_delayed(proj);
2293 
2294   proj->set_req(0, NULL);  // temporary disconnect
2295   ProjNode* proj2 = proj_clone(proj, iff);
2296   register_node(proj2, loop, iff, ddepth);
2297 
2298   Node* cmp = Signed ? (Node*) new CmpINode(left, right) : (Node*) new CmpUNode(left, right);
2299   register_node(cmp, loop, proj2, ddepth);
2300 
2301   BoolNode* bol = new BoolNode(cmp, relop);
2302   register_node(bol, loop, proj2, ddepth);
2303 
2304   int opcode = iff->Opcode();
2305   assert(opcode == Op_If || opcode == Op_RangeCheck, "unexpected opcode");
2306   IfNode* new_if = (opcode == Op_If) ? new IfNode(proj2, bol, iff->_prob, iff->_fcnt):
2307     new RangeCheckNode(proj2, bol, iff->_prob, iff->_fcnt);
2308   register_node(new_if, loop, proj2, ddepth);
2309 
2310   proj->set_req(0, new_if); // reattach
2311   set_idom(proj, new_if, ddepth);
2312 
2313   ProjNode* new_exit = proj_clone(other_proj, new_if)->as_Proj();
2314   guarantee(new_exit != NULL, "null exit node");
2315   register_node(new_exit, get_loop(other_proj), new_if, ddepth);
2316 
2317   return new_exit;
2318 }
2319 
2320 //------------------------------ insert_region_before_proj -------------------------------------
2321 // Insert a region before an if projection (* - new node)
2322 //
2323 // before
2324 //           if(test)
2325 //          /      |
2326 //         v       |
2327 //       proj      v
2328 //               other-proj
2329 //
2330 // after
2331 //           if(test)
2332 //          /      |
2333 //         v       |
2334 // * proj-clone    v
2335 //         |     other-proj
2336 //         v
2337 // * new-region
2338 //         |
2339 //         v
2340 // *      dum_if
2341 //       /     \
2342 //      v       \
2343 // * dum-proj    v
2344 //              proj
2345 //
2346 RegionNode* PhaseIdealLoop::insert_region_before_proj(ProjNode* proj) {
2347   IfNode* iff = proj->in(0)->as_If();
2348   IdealLoopTree *loop = get_loop(proj);
2349   ProjNode *other_proj = iff->proj_out(!proj->is_IfTrue())->as_Proj();
2350   int ddepth = dom_depth(proj);
2351 
2352   _igvn.rehash_node_delayed(iff);
2353   _igvn.rehash_node_delayed(proj);
2354 
2355   proj->set_req(0, NULL);  // temporary disconnect
2356   ProjNode* proj2 = proj_clone(proj, iff);
2357   register_node(proj2, loop, iff, ddepth);
2358 
2359   RegionNode* reg = new RegionNode(2);
2360   reg->set_req(1, proj2);
2361   register_node(reg, loop, iff, ddepth);
2362 
2363   IfNode* dum_if = new IfNode(reg, short_circuit_if(NULL, proj), iff->_prob, iff->_fcnt);
2364   register_node(dum_if, loop, reg, ddepth);
2365 
2366   proj->set_req(0, dum_if); // reattach
2367   set_idom(proj, dum_if, ddepth);
2368 
2369   ProjNode* dum_proj = proj_clone(other_proj, dum_if);
2370   register_node(dum_proj, loop, dum_if, ddepth);
2371 
2372   return reg;
2373 }
2374 
2375 //------------------------------ insert_cmpi_loop_exit -------------------------------------
2376 // Clone a signed compare loop exit from an unsigned compare and
2377 // insert it before the unsigned cmp on the stay-in-loop path.
2378 // All new nodes inserted in the dominator tree between the original
2379 // if and it's projections.  The original if test is replaced with
2380 // a constant to force the stay-in-loop path.
2381 //
2382 // This is done to make sure that the original if and it's projections
2383 // still dominate the same set of control nodes, that the ctrl() relation
2384 // from data nodes to them is preserved, and that their loop nesting is
2385 // preserved.
2386 //
2387 // before
2388 //          if(i <u limit)    unsigned compare loop exit
2389 //         /       |
2390 //        v        v
2391 //   exit-proj   stay-in-loop-proj
2392 //
2393 // after
2394 //          if(stay-in-loop-const)  original if
2395 //         /       |
2396 //        /        v
2397 //       /  if(i <  limit)    new signed test
2398 //      /  /       |
2399 //     /  /        v
2400 //    /  /  if(i <u limit)    new cloned unsigned test
2401 //   /  /   /      |
2402 //   v  v  v       |
2403 //    region       |
2404 //        |        |
2405 //      dum-if     |
2406 //     /  |        |
2407 // ether  |        |
2408 //        v        v
2409 //   exit-proj   stay-in-loop-proj
2410 //
2411 IfNode* PhaseIdealLoop::insert_cmpi_loop_exit(IfNode* if_cmpu, IdealLoopTree *loop) {
2412   const bool Signed   = true;
2413   const bool Unsigned = false;
2414 
2415   BoolNode* bol = if_cmpu->in(1)->as_Bool();
2416   if (bol->_test._test != BoolTest::lt) return NULL;
2417   CmpNode* cmpu = bol->in(1)->as_Cmp();
2418   if (cmpu->Opcode() != Op_CmpU) return NULL;
2419   int stride = stride_of_possible_iv(if_cmpu);
2420   if (stride == 0) return NULL;
2421 
2422   Node* lp_proj = stay_in_loop(if_cmpu, loop);
2423   guarantee(lp_proj != NULL, "null loop node");
2424 
2425   ProjNode* lp_continue = lp_proj->as_Proj();
2426   ProjNode* lp_exit     = if_cmpu->proj_out(!lp_continue->is_IfTrue())->as_Proj();
2427 
2428   Node* limit = NULL;
2429   if (stride > 0) {
2430     limit = cmpu->in(2);
2431   } else {
2432     limit = _igvn.makecon(TypeInt::ZERO);
2433     set_ctrl(limit, C->root());
2434   }
2435   // Create a new region on the exit path
2436   RegionNode* reg = insert_region_before_proj(lp_exit);
2437   guarantee(reg != NULL, "null region node");
2438 
2439   // Clone the if-cmpu-true-false using a signed compare
2440   BoolTest::mask rel_i = stride > 0 ? bol->_test._test : BoolTest::ge;
2441   ProjNode* cmpi_exit = insert_if_before_proj(cmpu->in(1), Signed, rel_i, limit, lp_continue);
2442   reg->add_req(cmpi_exit);
2443 
2444   // Clone the if-cmpu-true-false
2445   BoolTest::mask rel_u = bol->_test._test;
2446   ProjNode* cmpu_exit = insert_if_before_proj(cmpu->in(1), Unsigned, rel_u, cmpu->in(2), lp_continue);
2447   reg->add_req(cmpu_exit);
2448 
2449   // Force original if to stay in loop.
2450   short_circuit_if(if_cmpu, lp_continue);
2451 
2452   return cmpi_exit->in(0)->as_If();
2453 }
2454 
2455 //------------------------------ remove_cmpi_loop_exit -------------------------------------
2456 // Remove a previously inserted signed compare loop exit.
2457 void PhaseIdealLoop::remove_cmpi_loop_exit(IfNode* if_cmp, IdealLoopTree *loop) {
2458   Node* lp_proj = stay_in_loop(if_cmp, loop);
2459   assert(if_cmp->in(1)->in(1)->Opcode() == Op_CmpI &&
2460          stay_in_loop(lp_proj, loop)->is_If() &&
2461          stay_in_loop(lp_proj, loop)->in(1)->in(1)->Opcode() == Op_CmpU, "inserted cmpi before cmpu");
2462   Node *con = _igvn.makecon(lp_proj->is_IfTrue() ? TypeInt::ONE : TypeInt::ZERO);
2463   set_ctrl(con, C->root());
2464   if_cmp->set_req(1, con);
2465 }
2466 
2467 //------------------------------ scheduled_nodelist -------------------------------------
2468 // Create a post order schedule of nodes that are in the
2469 // "member" set.  The list is returned in "sched".
2470 // The first node in "sched" is the loop head, followed by
2471 // nodes which have no inputs in the "member" set, and then
2472 // followed by the nodes that have an immediate input dependence
2473 // on a node in "sched".
2474 void PhaseIdealLoop::scheduled_nodelist( IdealLoopTree *loop, VectorSet& member, Node_List &sched ) {
2475 
2476   assert(member.test(loop->_head->_idx), "loop head must be in member set");
2477   Arena *a = Thread::current()->resource_area();
2478   VectorSet visited(a);
2479   Node_Stack nstack(a, loop->_body.size());
2480 
2481   Node* n  = loop->_head;  // top of stack is cached in "n"
2482   uint idx = 0;
2483   visited.set(n->_idx);
2484 
2485   // Initially push all with no inputs from within member set
2486   for(uint i = 0; i < loop->_body.size(); i++ ) {
2487     Node *elt = loop->_body.at(i);
2488     if (member.test(elt->_idx)) {
2489       bool found = false;
2490       for (uint j = 0; j < elt->req(); j++) {
2491         Node* def = elt->in(j);
2492         if (def && member.test(def->_idx) && def != elt) {
2493           found = true;
2494           break;
2495         }
2496       }
2497       if (!found && elt != loop->_head) {
2498         nstack.push(n, idx);
2499         n = elt;
2500         assert(!visited.test(n->_idx), "not seen yet");
2501         visited.set(n->_idx);
2502       }
2503     }
2504   }
2505 
2506   // traverse out's that are in the member set
2507   while (true) {
2508     if (idx < n->outcnt()) {
2509       Node* use = n->raw_out(idx);
2510       idx++;
2511       if (!visited.test_set(use->_idx)) {
2512         if (member.test(use->_idx)) {
2513           nstack.push(n, idx);
2514           n = use;
2515           idx = 0;
2516         }
2517       }
2518     } else {
2519       // All outputs processed
2520       sched.push(n);
2521       if (nstack.is_empty()) break;
2522       n   = nstack.node();
2523       idx = nstack.index();
2524       nstack.pop();
2525     }
2526   }
2527 }
2528 
2529 
2530 //------------------------------ has_use_in_set -------------------------------------
2531 // Has a use in the vector set
2532 bool PhaseIdealLoop::has_use_in_set( Node* n, VectorSet& vset ) {
2533   for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
2534     Node* use = n->fast_out(j);
2535     if (vset.test(use->_idx)) {
2536       return true;
2537     }
2538   }
2539   return false;
2540 }
2541 
2542 
2543 //------------------------------ has_use_internal_to_set -------------------------------------
2544 // Has use internal to the vector set (ie. not in a phi at the loop head)
2545 bool PhaseIdealLoop::has_use_internal_to_set( Node* n, VectorSet& vset, IdealLoopTree *loop ) {
2546   Node* head  = loop->_head;
2547   for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
2548     Node* use = n->fast_out(j);
2549     if (vset.test(use->_idx) && !(use->is_Phi() && use->in(0) == head)) {
2550       return true;
2551     }
2552   }
2553   return false;
2554 }
2555 
2556 
2557 //------------------------------ clone_for_use_outside_loop -------------------------------------
2558 // clone "n" for uses that are outside of loop
2559 int PhaseIdealLoop::clone_for_use_outside_loop( IdealLoopTree *loop, Node* n, Node_List& worklist ) {
2560   int cloned = 0;
2561   assert(worklist.size() == 0, "should be empty");
2562   for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
2563     Node* use = n->fast_out(j);
2564     if( !loop->is_member(get_loop(has_ctrl(use) ? get_ctrl(use) : use)) ) {
2565       worklist.push(use);
2566     }
2567   }
2568   while( worklist.size() ) {
2569     Node *use = worklist.pop();
2570     if (!has_node(use) || use->in(0) == C->top()) continue;
2571     uint j;
2572     for (j = 0; j < use->req(); j++) {
2573       if (use->in(j) == n) break;
2574     }
2575     assert(j < use->req(), "must be there");
2576 
2577     // clone "n" and insert it between the inputs of "n" and the use outside the loop
2578     Node* n_clone = n->clone();
2579     _igvn.replace_input_of(use, j, n_clone);
2580     cloned++;
2581     Node* use_c;
2582     if (!use->is_Phi()) {
2583       use_c = has_ctrl(use) ? get_ctrl(use) : use->in(0);
2584     } else {
2585       // Use in a phi is considered a use in the associated predecessor block
2586       use_c = use->in(0)->in(j);
2587     }
2588     set_ctrl(n_clone, use_c);
2589     assert(!loop->is_member(get_loop(use_c)), "should be outside loop");
2590     get_loop(use_c)->_body.push(n_clone);
2591     _igvn.register_new_node_with_optimizer(n_clone);
2592 #if !defined(PRODUCT)
2593     if (TracePartialPeeling) {
2594       tty->print_cr("loop exit cloning old: %d new: %d newbb: %d", n->_idx, n_clone->_idx, get_ctrl(n_clone)->_idx);
2595     }
2596 #endif
2597   }
2598   return cloned;
2599 }
2600 
2601 
2602 //------------------------------ clone_for_special_use_inside_loop -------------------------------------
2603 // clone "n" for special uses that are in the not_peeled region.
2604 // If these def-uses occur in separate blocks, the code generator
2605 // marks the method as not compilable.  For example, if a "BoolNode"
2606 // is in a different basic block than the "IfNode" that uses it, then
2607 // the compilation is aborted in the code generator.
2608 void PhaseIdealLoop::clone_for_special_use_inside_loop( IdealLoopTree *loop, Node* n,
2609                                                         VectorSet& not_peel, Node_List& sink_list, Node_List& worklist ) {
2610   if (n->is_Phi() || n->is_Load()) {
2611     return;
2612   }
2613   assert(worklist.size() == 0, "should be empty");
2614   for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
2615     Node* use = n->fast_out(j);
2616     if ( not_peel.test(use->_idx) &&
2617          (use->is_If() || use->is_CMove() || use->is_Bool()) &&
2618          use->in(1) == n)  {
2619       worklist.push(use);
2620     }
2621   }
2622   if (worklist.size() > 0) {
2623     // clone "n" and insert it between inputs of "n" and the use
2624     Node* n_clone = n->clone();
2625     loop->_body.push(n_clone);
2626     _igvn.register_new_node_with_optimizer(n_clone);
2627     set_ctrl(n_clone, get_ctrl(n));
2628     sink_list.push(n_clone);
2629     not_peel <<= n_clone->_idx;  // add n_clone to not_peel set.
2630 #if !defined(PRODUCT)
2631     if (TracePartialPeeling) {
2632       tty->print_cr("special not_peeled cloning old: %d new: %d", n->_idx, n_clone->_idx);
2633     }
2634 #endif
2635     while( worklist.size() ) {
2636       Node *use = worklist.pop();
2637       _igvn.rehash_node_delayed(use);
2638       for (uint j = 1; j < use->req(); j++) {
2639         if (use->in(j) == n) {
2640           use->set_req(j, n_clone);
2641         }
2642       }
2643     }
2644   }
2645 }
2646 
2647 
2648 //------------------------------ insert_phi_for_loop -------------------------------------
2649 // Insert phi(lp_entry_val, back_edge_val) at use->in(idx) for loop lp if phi does not already exist
2650 void PhaseIdealLoop::insert_phi_for_loop( Node* use, uint idx, Node* lp_entry_val, Node* back_edge_val, LoopNode* lp ) {
2651   Node *phi = PhiNode::make(lp, back_edge_val);
2652   phi->set_req(LoopNode::EntryControl, lp_entry_val);
2653   // Use existing phi if it already exists
2654   Node *hit = _igvn.hash_find_insert(phi);
2655   if( hit == NULL ) {
2656     _igvn.register_new_node_with_optimizer(phi);
2657     set_ctrl(phi, lp);
2658   } else {
2659     // Remove the new phi from the graph and use the hit
2660     _igvn.remove_dead_node(phi);
2661     phi = hit;
2662   }
2663   _igvn.replace_input_of(use, idx, phi);
2664 }
2665 
2666 #ifdef ASSERT
2667 //------------------------------ is_valid_loop_partition -------------------------------------
2668 // Validate the loop partition sets: peel and not_peel
2669 bool PhaseIdealLoop::is_valid_loop_partition( IdealLoopTree *loop, VectorSet& peel, Node_List& peel_list,
2670                                               VectorSet& not_peel ) {
2671   uint i;
2672   // Check that peel_list entries are in the peel set
2673   for (i = 0; i < peel_list.size(); i++) {
2674     if (!peel.test(peel_list.at(i)->_idx)) {
2675       return false;
2676     }
2677   }
2678   // Check at loop members are in one of peel set or not_peel set
2679   for (i = 0; i < loop->_body.size(); i++ ) {
2680     Node *def  = loop->_body.at(i);
2681     uint di = def->_idx;
2682     // Check that peel set elements are in peel_list
2683     if (peel.test(di)) {
2684       if (not_peel.test(di)) {
2685         return false;
2686       }
2687       // Must be in peel_list also
2688       bool found = false;
2689       for (uint j = 0; j < peel_list.size(); j++) {
2690         if (peel_list.at(j)->_idx == di) {
2691           found = true;
2692           break;
2693         }
2694       }
2695       if (!found) {
2696         return false;
2697       }
2698     } else if (not_peel.test(di)) {
2699       if (peel.test(di)) {
2700         return false;
2701       }
2702     } else {
2703       return false;
2704     }
2705   }
2706   return true;
2707 }
2708 
2709 //------------------------------ is_valid_clone_loop_exit_use -------------------------------------
2710 // Ensure a use outside of loop is of the right form
2711 bool PhaseIdealLoop::is_valid_clone_loop_exit_use( IdealLoopTree *loop, Node* use, uint exit_idx) {
2712   Node *use_c = has_ctrl(use) ? get_ctrl(use) : use;
2713   return (use->is_Phi() &&
2714           use_c->is_Region() && use_c->req() == 3 &&
2715           (use_c->in(exit_idx)->Opcode() == Op_IfTrue ||
2716            use_c->in(exit_idx)->Opcode() == Op_IfFalse ||
2717            use_c->in(exit_idx)->Opcode() == Op_JumpProj) &&
2718           loop->is_member( get_loop( use_c->in(exit_idx)->in(0) ) ) );
2719 }
2720 
2721 //------------------------------ is_valid_clone_loop_form -------------------------------------
2722 // Ensure that all uses outside of loop are of the right form
2723 bool PhaseIdealLoop::is_valid_clone_loop_form( IdealLoopTree *loop, Node_List& peel_list,
2724                                                uint orig_exit_idx, uint clone_exit_idx) {
2725   uint len = peel_list.size();
2726   for (uint i = 0; i < len; i++) {
2727     Node *def = peel_list.at(i);
2728 
2729     for (DUIterator_Fast jmax, j = def->fast_outs(jmax); j < jmax; j++) {
2730       Node *use = def->fast_out(j);
2731       Node *use_c = has_ctrl(use) ? get_ctrl(use) : use;
2732       if (!loop->is_member(get_loop(use_c))) {
2733         // use is not in the loop, check for correct structure
2734         if (use->in(0) == def) {
2735           // Okay
2736         } else if (!is_valid_clone_loop_exit_use(loop, use, orig_exit_idx)) {
2737           return false;
2738         }
2739       }
2740     }
2741   }
2742   return true;
2743 }
2744 #endif
2745 
2746 //------------------------------ partial_peel -------------------------------------
2747 // Partially peel (aka loop rotation) the top portion of a loop (called
2748 // the peel section below) by cloning it and placing one copy just before
2749 // the new loop head and the other copy at the bottom of the new loop.
2750 //
2751 //    before                       after                where it came from
2752 //
2753 //    stmt1                        stmt1
2754 //  loop:                          stmt2                     clone
2755 //    stmt2                        if condA goto exitA       clone
2756 //    if condA goto exitA        new_loop:                   new
2757 //    stmt3                        stmt3                     clone
2758 //    if !condB goto loop          if condB goto exitB       clone
2759 //  exitB:                         stmt2                     orig
2760 //    stmt4                        if !condA goto new_loop   orig
2761 //  exitA:                         goto exitA
2762 //                               exitB:
2763 //                                 stmt4
2764 //                               exitA:
2765 //
2766 // Step 1: find the cut point: an exit test on probable
2767 //         induction variable.
2768 // Step 2: schedule (with cloning) operations in the peel
2769 //         section that can be executed after the cut into
2770 //         the section that is not peeled.  This may need
2771 //         to clone operations into exit blocks.  For
2772 //         instance, a reference to A[i] in the not-peel
2773 //         section and a reference to B[i] in an exit block
2774 //         may cause a left-shift of i by 2 to be placed
2775 //         in the peel block.  This step will clone the left
2776 //         shift into the exit block and sink the left shift
2777 //         from the peel to the not-peel section.
2778 // Step 3: clone the loop, retarget the control, and insert
2779 //         phis for values that are live across the new loop
2780 //         head.  This is very dependent on the graph structure
2781 //         from clone_loop.  It creates region nodes for
2782 //         exit control and associated phi nodes for values
2783 //         flow out of the loop through that exit.  The region
2784 //         node is dominated by the clone's control projection.
2785 //         So the clone's peel section is placed before the
2786 //         new loop head, and the clone's not-peel section is
2787 //         forms the top part of the new loop.  The original
2788 //         peel section forms the tail of the new loop.
2789 // Step 4: update the dominator tree and recompute the
2790 //         dominator depth.
2791 //
2792 //                   orig
2793 //
2794 //                   stmt1
2795 //                     |
2796 //                     v
2797 //               loop predicate
2798 //                     |
2799 //                     v
2800 //                   loop<----+
2801 //                     |      |
2802 //                   stmt2    |
2803 //                     |      |
2804 //                     v      |
2805 //                    ifA     |
2806 //                   / |      |
2807 //                  v  v      |
2808 //               false true   ^  <-- last_peel
2809 //               /     |      |
2810 //              /   ===|==cut |
2811 //             /     stmt3    |  <-- first_not_peel
2812 //            /        |      |
2813 //            |        v      |
2814 //            v       ifB     |
2815 //          exitA:   / \      |
2816 //                  /   \     |
2817 //                 v     v    |
2818 //               false true   |
2819 //               /       \    |
2820 //              /         ----+
2821 //             |
2822 //             v
2823 //           exitB:
2824 //           stmt4
2825 //
2826 //
2827 //            after clone loop
2828 //
2829 //                   stmt1
2830 //                     |
2831 //                     v
2832 //               loop predicate
2833 //                 /       \
2834 //        clone   /         \   orig
2835 //               /           \
2836 //              /             \
2837 //             v               v
2838 //   +---->loop                loop<----+
2839 //   |      |                    |      |
2840 //   |    stmt2                stmt2    |
2841 //   |      |                    |      |
2842 //   |      v                    v      |
2843 //   |      ifA                 ifA     |
2844 //   |      | \                / |      |
2845 //   |      v  v              v  v      |
2846 //   ^    true  false      false true   ^  <-- last_peel
2847 //   |      |   ^   \       /    |      |
2848 //   | cut==|==  \   \     /  ===|==cut |
2849 //   |    stmt3   \   \   /    stmt3    |  <-- first_not_peel
2850 //   |      |    dom   | |       |      |
2851 //   |      v      \  1v v2      v      |
2852 //   |      ifB     regionA     ifB     |
2853 //   |      / \        |       / \      |
2854 //   |     /   \       v      /   \     |
2855 //   |    v     v    exitA:  v     v    |
2856 //   |    true  false      false true   |
2857 //   |    /     ^   \      /       \    |
2858 //   +----       \   \    /         ----+
2859 //               dom  \  /
2860 //                 \  1v v2
2861 //                  regionB
2862 //                     |
2863 //                     v
2864 //                   exitB:
2865 //                   stmt4
2866 //
2867 //
2868 //           after partial peel
2869 //
2870 //                  stmt1
2871 //                     |
2872 //                     v
2873 //               loop predicate
2874 //                 /
2875 //        clone   /             orig
2876 //               /          TOP
2877 //              /             \
2878 //             v               v
2879 //    TOP->loop                loop----+
2880 //          |                    |      |
2881 //        stmt2                stmt2    |
2882 //          |                    |      |
2883 //          v                    v      |
2884 //          ifA                 ifA     |
2885 //          | \                / |      |
2886 //          v  v              v  v      |
2887 //        true  false      false true   |     <-- last_peel
2888 //          |   ^   \       /    +------|---+
2889 //  +->newloop   \   \     /  === ==cut |   |
2890 //  |     stmt3   \   \   /     TOP     |   |
2891 //  |       |    dom   | |      stmt3   |   | <-- first_not_peel
2892 //  |       v      \  1v v2      v      |   |
2893 //  |       ifB     regionA     ifB     ^   v
2894 //  |       / \        |       / \      |   |
2895 //  |      /   \       v      /   \     |   |
2896 //  |     v     v    exitA:  v     v    |   |
2897 //  |     true  false      false true   |   |
2898 //  |     /     ^   \      /       \    |   |
2899 //  |    |       \   \    /         v   |   |
2900 //  |    |       dom  \  /         TOP  |   |
2901 //  |    |         \  1v v2             |   |
2902 //  ^    v          regionB             |   |
2903 //  |    |             |                |   |
2904 //  |    |             v                ^   v
2905 //  |    |           exitB:             |   |
2906 //  |    |           stmt4              |   |
2907 //  |    +------------>-----------------+   |
2908 //  |                                       |
2909 //  +-----------------<---------------------+
2910 //
2911 //
2912 //              final graph
2913 //
2914 //                  stmt1
2915 //                    |
2916 //                    v
2917 //               loop predicate
2918 //                    |
2919 //                    v
2920 //                  stmt2 clone
2921 //                    |
2922 //                    v
2923 //         ........> ifA clone
2924 //         :        / |
2925 //        dom      /  |
2926 //         :      v   v
2927 //         :  false   true
2928 //         :  |       |
2929 //         :  |       v
2930 //         :  |    newloop<-----+
2931 //         :  |        |        |
2932 //         :  |     stmt3 clone |
2933 //         :  |        |        |
2934 //         :  |        v        |
2935 //         :  |       ifB       |
2936 //         :  |      / \        |
2937 //         :  |     v   v       |
2938 //         :  |  false true     |
2939 //         :  |   |     |       |
2940 //         :  |   v    stmt2    |
2941 //         :  | exitB:  |       |
2942 //         :  | stmt4   v       |
2943 //         :  |       ifA orig  |
2944 //         :  |      /  \       |
2945 //         :  |     /    \      |
2946 //         :  |    v     v      |
2947 //         :  |  false  true    |
2948 //         :  |  /        \     |
2949 //         :  v  v         -----+
2950 //          RegionA
2951 //             |
2952 //             v
2953 //           exitA
2954 //
2955 bool PhaseIdealLoop::partial_peel( IdealLoopTree *loop, Node_List &old_new ) {
2956 
2957   assert(!loop->_head->is_CountedLoop(), "Non-counted loop only");
2958   if (!loop->_head->is_Loop()) {
2959     return false;  }
2960 
2961   LoopNode *head  = loop->_head->as_Loop();
2962 
2963   if (head->is_partial_peel_loop() || head->partial_peel_has_failed()) {
2964     return false;
2965   }
2966 
2967   // Check for complex exit control
2968   for(uint ii = 0; ii < loop->_body.size(); ii++ ) {
2969     Node *n = loop->_body.at(ii);
2970     int opc = n->Opcode();
2971     if (n->is_Call()        ||
2972         opc == Op_Catch     ||
2973         opc == Op_CatchProj ||
2974         opc == Op_Jump      ||
2975         opc == Op_JumpProj) {
2976 #if !defined(PRODUCT)
2977       if (TracePartialPeeling) {
2978         tty->print_cr("\nExit control too complex: lp: %d", head->_idx);
2979       }
2980 #endif
2981       return false;
2982     }
2983   }
2984 
2985   int dd = dom_depth(head);
2986 
2987   // Step 1: find cut point
2988 
2989   // Walk up dominators to loop head looking for first loop exit
2990   // which is executed on every path thru loop.
2991   IfNode *peel_if = NULL;
2992   IfNode *peel_if_cmpu = NULL;
2993 
2994   Node *iff = loop->tail();
2995   while( iff != head ) {
2996     if( iff->is_If() ) {
2997       Node *ctrl = get_ctrl(iff->in(1));
2998       if (ctrl->is_top()) return false; // Dead test on live IF.
2999       // If loop-varying exit-test, check for induction variable
3000       if( loop->is_member(get_loop(ctrl)) &&
3001           loop->is_loop_exit(iff) &&
3002           is_possible_iv_test(iff)) {
3003         Node* cmp = iff->in(1)->in(1);
3004         if (cmp->Opcode() == Op_CmpI) {
3005           peel_if = iff->as_If();
3006         } else {
3007           assert(cmp->Opcode() == Op_CmpU, "must be CmpI or CmpU");
3008           peel_if_cmpu = iff->as_If();
3009         }
3010       }
3011     }
3012     iff = idom(iff);
3013   }
3014   // Prefer signed compare over unsigned compare.
3015   IfNode* new_peel_if = NULL;
3016   if (peel_if == NULL) {
3017     if (!PartialPeelAtUnsignedTests || peel_if_cmpu == NULL) {
3018       return false;   // No peel point found
3019     }
3020     new_peel_if = insert_cmpi_loop_exit(peel_if_cmpu, loop);
3021     if (new_peel_if == NULL) {
3022       return false;   // No peel point found
3023     }
3024     peel_if = new_peel_if;
3025   }
3026   Node* last_peel        = stay_in_loop(peel_if, loop);
3027   Node* first_not_peeled = stay_in_loop(last_peel, loop);
3028   if (first_not_peeled == NULL || first_not_peeled == head) {
3029     return false;
3030   }
3031 
3032 #if !defined(PRODUCT)
3033   if (TraceLoopOpts) {
3034     tty->print("PartialPeel  ");
3035     loop->dump_head();
3036   }
3037 
3038   if (TracePartialPeeling) {
3039     tty->print_cr("before partial peel one iteration");
3040     Node_List wl;
3041     Node* t = head->in(2);
3042     while (true) {
3043       wl.push(t);
3044       if (t == head) break;
3045       t = idom(t);
3046     }
3047     while (wl.size() > 0) {
3048       Node* tt = wl.pop();
3049       tt->dump();
3050       if (tt == last_peel) tty->print_cr("-- cut --");
3051     }
3052   }
3053 #endif
3054   ResourceArea *area = Thread::current()->resource_area();
3055   VectorSet peel(area);
3056   VectorSet not_peel(area);
3057   Node_List peel_list(area);
3058   Node_List worklist(area);
3059   Node_List sink_list(area);
3060 
3061   // Set of cfg nodes to peel are those that are executable from
3062   // the head through last_peel.
3063   assert(worklist.size() == 0, "should be empty");
3064   worklist.push(head);
3065   peel.set(head->_idx);
3066   while (worklist.size() > 0) {
3067     Node *n = worklist.pop();
3068     if (n != last_peel) {
3069       for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
3070         Node* use = n->fast_out(j);
3071         if (use->is_CFG() &&
3072             loop->is_member(get_loop(use)) &&
3073             !peel.test_set(use->_idx)) {
3074           worklist.push(use);
3075         }
3076       }
3077     }
3078   }
3079 
3080   // Set of non-cfg nodes to peel are those that are control
3081   // dependent on the cfg nodes.
3082   uint i;
3083   for(i = 0; i < loop->_body.size(); i++ ) {
3084     Node *n = loop->_body.at(i);
3085     Node *n_c = has_ctrl(n) ? get_ctrl(n) : n;
3086     if (peel.test(n_c->_idx)) {
3087       peel.set(n->_idx);
3088     } else {
3089       not_peel.set(n->_idx);
3090     }
3091   }
3092 
3093   // Step 2: move operations from the peeled section down into the
3094   //         not-peeled section
3095 
3096   // Get a post order schedule of nodes in the peel region
3097   // Result in right-most operand.
3098   scheduled_nodelist(loop, peel, peel_list );
3099 
3100   assert(is_valid_loop_partition(loop, peel, peel_list, not_peel), "bad partition");
3101 
3102   // For future check for too many new phis
3103   uint old_phi_cnt = 0;
3104   for (DUIterator_Fast jmax, j = head->fast_outs(jmax); j < jmax; j++) {
3105     Node* use = head->fast_out(j);
3106     if (use->is_Phi()) old_phi_cnt++;
3107   }
3108 
3109 #if !defined(PRODUCT)
3110   if (TracePartialPeeling) {
3111     tty->print_cr("\npeeled list");
3112   }
3113 #endif
3114 
3115   // Evacuate nodes in peel region into the not_peeled region if possible
3116   uint new_phi_cnt = 0;
3117   uint cloned_for_outside_use = 0;
3118   for (i = 0; i < peel_list.size();) {
3119     Node* n = peel_list.at(i);
3120 #if !defined(PRODUCT)
3121   if (TracePartialPeeling) n->dump();
3122 #endif
3123     bool incr = true;
3124     if ( !n->is_CFG() ) {
3125 
3126       if ( has_use_in_set(n, not_peel) ) {
3127 
3128         // If not used internal to the peeled region,
3129         // move "n" from peeled to not_peeled region.
3130 
3131         if ( !has_use_internal_to_set(n, peel, loop) ) {
3132 
3133           // if not pinned and not a load (which maybe anti-dependent on a store)
3134           // and not a CMove (Matcher expects only bool->cmove).
3135           if ( n->in(0) == NULL && !n->is_Load() && !n->is_CMove() ) {
3136             cloned_for_outside_use += clone_for_use_outside_loop( loop, n, worklist );
3137             sink_list.push(n);
3138             peel     >>= n->_idx; // delete n from peel set.
3139             not_peel <<= n->_idx; // add n to not_peel set.
3140             peel_list.remove(i);
3141             incr = false;
3142 #if !defined(PRODUCT)
3143             if (TracePartialPeeling) {
3144               tty->print_cr("sink to not_peeled region: %d newbb: %d",
3145                             n->_idx, get_ctrl(n)->_idx);
3146             }
3147 #endif
3148           }
3149         } else {
3150           // Otherwise check for special def-use cases that span
3151           // the peel/not_peel boundary such as bool->if
3152           clone_for_special_use_inside_loop( loop, n, not_peel, sink_list, worklist );
3153           new_phi_cnt++;
3154         }
3155       }
3156     }
3157     if (incr) i++;
3158   }
3159 
3160   if (new_phi_cnt > old_phi_cnt + PartialPeelNewPhiDelta) {
3161 #if !defined(PRODUCT)
3162     if (TracePartialPeeling) {
3163       tty->print_cr("\nToo many new phis: %d  old %d new cmpi: %c",
3164                     new_phi_cnt, old_phi_cnt, new_peel_if != NULL?'T':'F');
3165     }
3166 #endif
3167     if (new_peel_if != NULL) {
3168       remove_cmpi_loop_exit(new_peel_if, loop);
3169     }
3170     // Inhibit more partial peeling on this loop
3171     assert(!head->is_partial_peel_loop(), "not partial peeled");
3172     head->mark_partial_peel_failed();
3173     if (cloned_for_outside_use > 0) {
3174       // Terminate this round of loop opts because
3175       // the graph outside this loop was changed.
3176       C->set_major_progress();
3177       return true;
3178     }
3179     return false;
3180   }
3181 
3182   // Step 3: clone loop, retarget control, and insert new phis
3183 
3184   // Create new loop head for new phis and to hang
3185   // the nodes being moved (sinked) from the peel region.
3186   LoopNode* new_head = new LoopNode(last_peel, last_peel);
3187   new_head->set_unswitch_count(head->unswitch_count()); // Preserve
3188   _igvn.register_new_node_with_optimizer(new_head);
3189   assert(first_not_peeled->in(0) == last_peel, "last_peel <- first_not_peeled");
3190   _igvn.replace_input_of(first_not_peeled, 0, new_head);
3191   set_loop(new_head, loop);
3192   loop->_body.push(new_head);
3193   not_peel.set(new_head->_idx);
3194   set_idom(new_head, last_peel, dom_depth(first_not_peeled));
3195   set_idom(first_not_peeled, new_head, dom_depth(first_not_peeled));
3196 
3197   while (sink_list.size() > 0) {
3198     Node* n = sink_list.pop();
3199     set_ctrl(n, new_head);
3200   }
3201 
3202   assert(is_valid_loop_partition(loop, peel, peel_list, not_peel), "bad partition");
3203 
3204   clone_loop(loop, old_new, dd, IgnoreStripMined);
3205 
3206   const uint clone_exit_idx = 1;
3207   const uint orig_exit_idx  = 2;
3208   assert(is_valid_clone_loop_form( loop, peel_list, orig_exit_idx, clone_exit_idx ), "bad clone loop");
3209 
3210   Node* head_clone             = old_new[head->_idx];
3211   LoopNode* new_head_clone     = old_new[new_head->_idx]->as_Loop();
3212   Node* orig_tail_clone        = head_clone->in(2);
3213 
3214   // Add phi if "def" node is in peel set and "use" is not
3215 
3216   for(i = 0; i < peel_list.size(); i++ ) {
3217     Node *def  = peel_list.at(i);
3218     if (!def->is_CFG()) {
3219       for (DUIterator_Fast jmax, j = def->fast_outs(jmax); j < jmax; j++) {
3220         Node *use = def->fast_out(j);
3221         if (has_node(use) && use->in(0) != C->top() &&
3222             (!peel.test(use->_idx) ||
3223              (use->is_Phi() && use->in(0) == head)) ) {
3224           worklist.push(use);
3225         }
3226       }
3227       while( worklist.size() ) {
3228         Node *use = worklist.pop();
3229         for (uint j = 1; j < use->req(); j++) {
3230           Node* n = use->in(j);
3231           if (n == def) {
3232 
3233             // "def" is in peel set, "use" is not in peel set
3234             // or "use" is in the entry boundary (a phi) of the peel set
3235 
3236             Node* use_c = has_ctrl(use) ? get_ctrl(use) : use;
3237 
3238             if ( loop->is_member(get_loop( use_c )) ) {
3239               // use is in loop
3240               if (old_new[use->_idx] != NULL) { // null for dead code
3241                 Node* use_clone = old_new[use->_idx];
3242                 _igvn.replace_input_of(use, j, C->top());
3243                 insert_phi_for_loop( use_clone, j, old_new[def->_idx], def, new_head_clone );
3244               }
3245             } else {
3246               assert(is_valid_clone_loop_exit_use(loop, use, orig_exit_idx), "clone loop format");
3247               // use is not in the loop, check if the live range includes the cut
3248               Node* lp_if = use_c->in(orig_exit_idx)->in(0);
3249               if (not_peel.test(lp_if->_idx)) {
3250                 assert(j == orig_exit_idx, "use from original loop");
3251                 insert_phi_for_loop( use, clone_exit_idx, old_new[def->_idx], def, new_head_clone );
3252               }
3253             }
3254           }
3255         }
3256       }
3257     }
3258   }
3259 
3260   // Step 3b: retarget control
3261 
3262   // Redirect control to the new loop head if a cloned node in
3263   // the not_peeled region has control that points into the peeled region.
3264   // This necessary because the cloned peeled region will be outside
3265   // the loop.
3266   //                            from    to
3267   //          cloned-peeled    <---+
3268   //    new_head_clone:            |    <--+
3269   //          cloned-not_peeled  in(0)    in(0)
3270   //          orig-peeled
3271 
3272   for(i = 0; i < loop->_body.size(); i++ ) {
3273     Node *n = loop->_body.at(i);
3274     if (!n->is_CFG()           && n->in(0) != NULL        &&
3275         not_peel.test(n->_idx) && peel.test(n->in(0)->_idx)) {
3276       Node* n_clone = old_new[n->_idx];
3277       _igvn.replace_input_of(n_clone, 0, new_head_clone);
3278     }
3279   }
3280 
3281   // Backedge of the surviving new_head (the clone) is original last_peel
3282   _igvn.replace_input_of(new_head_clone, LoopNode::LoopBackControl, last_peel);
3283 
3284   // Cut first node in original not_peel set
3285   _igvn.rehash_node_delayed(new_head);                     // Multiple edge updates:
3286   new_head->set_req(LoopNode::EntryControl,    C->top());  //   use rehash_node_delayed / set_req instead of
3287   new_head->set_req(LoopNode::LoopBackControl, C->top());  //   multiple replace_input_of calls
3288 
3289   // Copy head_clone back-branch info to original head
3290   // and remove original head's loop entry and
3291   // clone head's back-branch
3292   _igvn.rehash_node_delayed(head); // Multiple edge updates
3293   head->set_req(LoopNode::EntryControl,    head_clone->in(LoopNode::LoopBackControl));
3294   head->set_req(LoopNode::LoopBackControl, C->top());
3295   _igvn.replace_input_of(head_clone, LoopNode::LoopBackControl, C->top());
3296 
3297   // Similarly modify the phis
3298   for (DUIterator_Fast kmax, k = head->fast_outs(kmax); k < kmax; k++) {
3299     Node* use = head->fast_out(k);
3300     if (use->is_Phi() && use->outcnt() > 0) {
3301       Node* use_clone = old_new[use->_idx];
3302       _igvn.rehash_node_delayed(use); // Multiple edge updates
3303       use->set_req(LoopNode::EntryControl,    use_clone->in(LoopNode::LoopBackControl));
3304       use->set_req(LoopNode::LoopBackControl, C->top());
3305       _igvn.replace_input_of(use_clone, LoopNode::LoopBackControl, C->top());
3306     }
3307   }
3308 
3309   // Step 4: update dominator tree and dominator depth
3310 
3311   set_idom(head, orig_tail_clone, dd);
3312   recompute_dom_depth();
3313 
3314   // Inhibit more partial peeling on this loop
3315   new_head_clone->set_partial_peel_loop();
3316   C->set_major_progress();
3317   loop->record_for_igvn();
3318 
3319 #if !defined(PRODUCT)
3320   if (TracePartialPeeling) {
3321     tty->print_cr("\nafter partial peel one iteration");
3322     Node_List wl(area);
3323     Node* t = last_peel;
3324     while (true) {
3325       wl.push(t);
3326       if (t == head_clone) break;
3327       t = idom(t);
3328     }
3329     while (wl.size() > 0) {
3330       Node* tt = wl.pop();
3331       if (tt == head) tty->print_cr("orig head");
3332       else if (tt == new_head_clone) tty->print_cr("new head");
3333       else if (tt == head_clone) tty->print_cr("clone head");
3334       tt->dump();
3335     }
3336   }
3337 #endif
3338   return true;
3339 }
3340 
3341 //------------------------------reorg_offsets----------------------------------
3342 // Reorganize offset computations to lower register pressure.  Mostly
3343 // prevent loop-fallout uses of the pre-incremented trip counter (which are
3344 // then alive with the post-incremented trip counter forcing an extra
3345 // register move)
3346 void PhaseIdealLoop::reorg_offsets(IdealLoopTree *loop) {
3347   // Perform it only for canonical counted loops.
3348   // Loop's shape could be messed up by iteration_split_impl.
3349   if (!loop->_head->is_CountedLoop())
3350     return;
3351   if (!loop->_head->as_Loop()->is_valid_counted_loop())
3352     return;
3353 
3354   CountedLoopNode *cl = loop->_head->as_CountedLoop();
3355   CountedLoopEndNode *cle = cl->loopexit();
3356   Node *exit = cle->proj_out(false);
3357   Node *phi = cl->phi();
3358 
3359   // Check for the special case of folks using the pre-incremented
3360   // trip-counter on the fall-out path (forces the pre-incremented
3361   // and post-incremented trip counter to be live at the same time).
3362   // Fix this by adjusting to use the post-increment trip counter.
3363 
3364   bool progress = true;
3365   while (progress) {
3366     progress = false;
3367     for (DUIterator_Fast imax, i = phi->fast_outs(imax); i < imax; i++) {
3368       Node* use = phi->fast_out(i);   // User of trip-counter
3369       if (!has_ctrl(use))  continue;
3370       Node *u_ctrl = get_ctrl(use);
3371       if (use->is_Phi()) {
3372         u_ctrl = NULL;
3373         for (uint j = 1; j < use->req(); j++)
3374           if (use->in(j) == phi)
3375             u_ctrl = dom_lca(u_ctrl, use->in(0)->in(j));
3376       }
3377       IdealLoopTree *u_loop = get_loop(u_ctrl);
3378       // Look for loop-invariant use
3379       if (u_loop == loop) continue;
3380       if (loop->is_member(u_loop)) continue;
3381       // Check that use is live out the bottom.  Assuming the trip-counter
3382       // update is right at the bottom, uses of of the loop middle are ok.
3383       if (dom_lca(exit, u_ctrl) != exit) continue;
3384       // Hit!  Refactor use to use the post-incremented tripcounter.
3385       // Compute a post-increment tripcounter.
3386       Node *opaq = new Opaque2Node( C, cle->incr() );
3387       register_new_node(opaq, exit);
3388       Node *neg_stride = _igvn.intcon(-cle->stride_con());
3389       set_ctrl(neg_stride, C->root());
3390       Node *post = new AddINode( opaq, neg_stride);
3391       register_new_node(post, exit);
3392       _igvn.rehash_node_delayed(use);
3393       for (uint j = 1; j < use->req(); j++) {
3394         if (use->in(j) == phi)
3395           use->set_req(j, post);
3396       }
3397       // Since DU info changed, rerun loop
3398       progress = true;
3399       break;
3400     }
3401   }
3402 
3403 }