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