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