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