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