< prev index next >

src/share/vm/opto/loopopts.cpp

Print this page




  25 #include "precompiled.hpp"
  26 #include "memory/allocation.inline.hpp"
  27 #include "memory/resourceArea.hpp"
  28 #include "opto/addnode.hpp"
  29 #include "opto/castnode.hpp"
  30 #include "opto/connode.hpp"
  31 #include "opto/castnode.hpp"
  32 #include "opto/divnode.hpp"
  33 #include "opto/loopnode.hpp"
  34 #include "opto/matcher.hpp"
  35 #include "opto/mulnode.hpp"
  36 #include "opto/movenode.hpp"
  37 #include "opto/opaquenode.hpp"
  38 #include "opto/rootnode.hpp"
  39 #include "opto/subnode.hpp"
  40 
  41 //=============================================================================
  42 //------------------------------split_thru_phi---------------------------------
  43 // Split Node 'n' through merge point if there is enough win.
  44 Node *PhaseIdealLoop::split_thru_phi( Node *n, Node *region, int policy ) {
  45   if (n->Opcode() == Op_ConvI2L && n->bottom_type() != TypeLong::LONG) {
  46     // ConvI2L may have type information on it which is unsafe to push up
  47     // so disable this for now
  48     return NULL;
  49   }
  50 
  51   // Splitting range check CastIIs through a loop induction Phi can
  52   // cause new Phis to be created that are left unrelated to the loop
  53   // induction Phi and prevent optimizations (vectorization)
  54   if (n->Opcode() == Op_CastII && n->as_CastII()->has_range_check() &&
  55       region->is_CountedLoop() && n->in(1) == region->as_CountedLoop()->phi()) {
  56     return NULL;
  57   }
  58 
  59   int wins = 0;
  60   assert(!n->is_CFG(), "");
  61   assert(region->is_Region(), "");
  62 
  63   const Type* type = n->bottom_type();
  64   const TypeOopPtr *t_oop = _igvn.type(n)->isa_oopptr();
  65   Node *phi;
  66   if (t_oop != NULL && t_oop->is_known_instance_field()) {
  67     int iid    = t_oop->instance_id();
  68     int index  = C->get_alias_index(t_oop);
  69     int offset = t_oop->offset();
  70     phi = new PhiNode(region, type, NULL, iid, index, offset);
  71   } else {
  72     phi = PhiNode::make_blank(region, n);
  73   }
  74   uint old_unique = C->unique();


 197     if (old_loop != new_loop) {
 198       if (old_loop && !old_loop->_child)
 199         old_loop->_body.yank(x);
 200       if (!new_loop->_child)
 201         new_loop->_body.push(x);  // Collect body info
 202     }
 203   }
 204 
 205   return phi;
 206 }
 207 
 208 //------------------------------dominated_by------------------------------------
 209 // Replace the dominated test with an obvious true or false.  Place it on the
 210 // IGVN worklist for later cleanup.  Move control-dependent data Nodes on the
 211 // live path up to the dominating control.
 212 void PhaseIdealLoop::dominated_by( Node *prevdom, Node *iff, bool flip, bool exclude_loop_predicate ) {
 213   if (VerifyLoopOptimizations && PrintOpto) { tty->print_cr("dominating test"); }
 214 
 215   // prevdom is the dominating projection of the dominating test.
 216   assert( iff->is_If(), "" );
 217   assert(iff->Opcode() == Op_If || iff->Opcode() == Op_CountedLoopEnd || iff->Opcode() == Op_RangeCheck, "Check this code when new subtype is added");
 218   int pop = prevdom->Opcode();
 219   assert( pop == Op_IfFalse || pop == Op_IfTrue, "" );
 220   if (flip) {
 221     if (pop == Op_IfTrue)
 222       pop = Op_IfFalse;
 223     else
 224       pop = Op_IfTrue;
 225   }
 226   // 'con' is set to true or false to kill the dominated test.
 227   Node *con = _igvn.makecon(pop == Op_IfTrue ? TypeInt::ONE : TypeInt::ZERO);
 228   set_ctrl(con, C->root()); // Constant gets a new use
 229   // Hack the dominated test
 230   _igvn.replace_input_of(iff, 1, con);
 231 
 232   // If I dont have a reachable TRUE and FALSE path following the IfNode then
 233   // I can assume this path reaches an infinite loop.  In this case it's not
 234   // important to optimize the data Nodes - either the whole compilation will
 235   // be tossed or this path (and all data Nodes) will go dead.
 236   if (iff->outcnt() != 2) return;
 237 
 238   // Make control-dependent data Nodes on the live path (path that will remain
 239   // once the dominated IF is removed) become control-dependent on the
 240   // dominating projection.
 241   Node* dp = iff->as_If()->proj_out(pop == Op_IfTrue);
 242 
 243   // Loop predicates may have depending checks which should not
 244   // be skipped. For example, range check predicate has two checks
 245   // for lower and upper bounds.
 246   if (dp == NULL)
 247     return;
 248 
 249   ProjNode* dp_proj  = dp->as_Proj();
 250   ProjNode* unc_proj = iff->as_If()->proj_out(1 - dp_proj->_con)->as_Proj();
 251   if (exclude_loop_predicate &&
 252       (unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_predicate) != NULL ||
 253        unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_range_check) != NULL)) {
 254     // If this is a range check (IfNode::is_range_check), do not
 255     // reorder because Compile::allow_range_check_smearing might have
 256     // changed the check.
 257     return; // Let IGVN transformation change control dependence.
 258   }
 259 
 260   IdealLoopTree *old_loop = get_loop(dp);
 261 


 334   Node *n1_ctrl = get_ctrl(n->in(                    1));
 335   Node *n2_ctrl = get_ctrl(n->in(                    2));
 336   Node *n3_ctrl = get_ctrl(n->in(n->req() == 3 ? 2 : 3));
 337   IdealLoopTree *n1_loop = get_loop( n1_ctrl );
 338   IdealLoopTree *n2_loop = get_loop( n2_ctrl );
 339   IdealLoopTree *n3_loop = get_loop( n3_ctrl );
 340 
 341   // Does one of my inputs spin in a tighter loop than self?
 342   if( (n_loop->is_member( n1_loop ) && n_loop != n1_loop) ||
 343       (n_loop->is_member( n2_loop ) && n_loop != n2_loop) ||
 344       (n_loop->is_member( n3_loop ) && n_loop != n3_loop) )
 345     return NULL;                // Leave well enough alone
 346 
 347   // Is at least one of my inputs loop-invariant?
 348   if( n1_loop == n_loop &&
 349       n2_loop == n_loop &&
 350       n3_loop == n_loop )
 351     return NULL;                // No loop-invariant inputs
 352 
 353 
 354   int n_op = n->Opcode();
 355 
 356   // Replace expressions like ((V+I) << 2) with (V<<2 + I<<2).
 357   if( n_op == Op_LShiftI ) {
 358     // Scale is loop invariant
 359     Node *scale = n->in(2);
 360     Node *scale_ctrl = get_ctrl(scale);
 361     IdealLoopTree *scale_loop = get_loop(scale_ctrl );
 362     if( n_loop == scale_loop || !scale_loop->is_member( n_loop ) )
 363       return NULL;
 364     const TypeInt *scale_t = scale->bottom_type()->isa_int();
 365     if( scale_t && scale_t->is_con() && scale_t->get_con() >= 16 )
 366       return NULL;              // Dont bother with byte/short masking
 367     // Add must vary with loop (else shift would be loop-invariant)
 368     Node *add = n->in(1);
 369     Node *add_ctrl = get_ctrl(add);
 370     IdealLoopTree *add_loop = get_loop(add_ctrl);
 371     //assert( n_loop == add_loop, "" );
 372     if( n_loop != add_loop ) return NULL;  // happens w/ evil ZKM loops
 373 
 374     // Convert I-V into I+ (0-V); same for V-I
 375     if( add->Opcode() == Op_SubI &&
 376         _igvn.type( add->in(1) ) != TypeInt::ZERO ) {
 377       Node *zero = _igvn.intcon(0);
 378       set_ctrl(zero, C->root());
 379       Node *neg = new SubINode( _igvn.intcon(0), add->in(2) );
 380       register_new_node( neg, get_ctrl(add->in(2) ) );
 381       add = new AddINode( add->in(1), neg );
 382       register_new_node( add, add_ctrl );
 383     }
 384     if( add->Opcode() != Op_AddI ) return NULL;
 385     // See if one add input is loop invariant
 386     Node *add_var = add->in(1);
 387     Node *add_var_ctrl = get_ctrl(add_var);
 388     IdealLoopTree *add_var_loop = get_loop(add_var_ctrl );
 389     Node *add_invar = add->in(2);
 390     Node *add_invar_ctrl = get_ctrl(add_invar);
 391     IdealLoopTree *add_invar_loop = get_loop(add_invar_ctrl );
 392     if( add_var_loop == n_loop ) {
 393     } else if( add_invar_loop == n_loop ) {
 394       // Swap to find the invariant part
 395       add_invar = add_var;
 396       add_invar_ctrl = add_var_ctrl;
 397       add_invar_loop = add_var_loop;
 398       add_var = add->in(2);
 399       Node *add_var_ctrl = get_ctrl(add_var);
 400       IdealLoopTree *add_var_loop = get_loop(add_var_ctrl );
 401     } else                      // Else neither input is loop invariant
 402       return NULL;
 403     if( n_loop == add_invar_loop || !add_invar_loop->is_member( n_loop ) )
 404       return NULL;              // No invariant part of the add?
 405 
 406     // Yes!  Reshape address expression!
 407     Node *inv_scale = new LShiftINode( add_invar, scale );
 408     Node *inv_scale_ctrl =
 409       dom_depth(add_invar_ctrl) > dom_depth(scale_ctrl) ?
 410       add_invar_ctrl : scale_ctrl;
 411     register_new_node( inv_scale, inv_scale_ctrl );
 412     Node *var_scale = new LShiftINode( add_var, scale );
 413     register_new_node( var_scale, n_ctrl );
 414     Node *var_add = new AddINode( var_scale, inv_scale );
 415     register_new_node( var_add, n_ctrl );
 416     _igvn.replace_node( n, var_add );
 417     return var_add;
 418   }
 419 
 420   // Replace (I+V) with (V+I)
 421   if( n_op == Op_AddI ||
 422       n_op == Op_AddL ||
 423       n_op == Op_AddF ||
 424       n_op == Op_AddD ||
 425       n_op == Op_MulI ||
 426       n_op == Op_MulL ||
 427       n_op == Op_MulF ||
 428       n_op == Op_MulD ) {
 429     if( n2_loop == n_loop ) {
 430       assert( n1_loop != n_loop, "" );
 431       n->swap_edges(1, 2);
 432     }
 433   }
 434 
 435   // Replace ((I1 +p V) +p I2) with ((I1 +p I2) +p V),
 436   // but not if I2 is a constant.
 437   if( n_op == Op_AddP ) {
 438     if( n2_loop == n_loop && n3_loop != n_loop ) {
 439       if( n->in(2)->Opcode() == Op_AddP && !n->in(3)->is_Con() ) {
 440         Node *n22_ctrl = get_ctrl(n->in(2)->in(2));
 441         Node *n23_ctrl = get_ctrl(n->in(2)->in(3));
 442         IdealLoopTree *n22loop = get_loop( n22_ctrl );
 443         IdealLoopTree *n23_loop = get_loop( n23_ctrl );
 444         if( n22loop != n_loop && n22loop->is_member(n_loop) &&
 445             n23_loop == n_loop ) {
 446           Node *add1 = new AddPNode( n->in(1), n->in(2)->in(2), n->in(3) );
 447           // Stuff new AddP in the loop preheader
 448           register_new_node( add1, n_loop->_head->in(LoopNode::EntryControl) );
 449           Node *add2 = new AddPNode( n->in(1), add1, n->in(2)->in(3) );
 450           register_new_node( add2, n_ctrl );
 451           _igvn.replace_node( n, add2 );
 452           return add2;
 453         }
 454       }
 455     }
 456 
 457     // Replace (I1 +p (I2 + V)) with ((I1 +p I2) +p V)
 458     if (n2_loop != n_loop && n3_loop == n_loop) {
 459       if (n->in(3)->Opcode() == Op_AddX) {
 460         Node *V = n->in(3)->in(1);
 461         Node *I = n->in(3)->in(2);
 462         if (is_member(n_loop,get_ctrl(V))) {
 463         } else {
 464           Node *tmp = V; V = I; I = tmp;
 465         }
 466         if (!is_member(n_loop,get_ctrl(I))) {
 467           Node *add1 = new AddPNode(n->in(1), n->in(2), I);
 468           // Stuff new AddP in the loop preheader
 469           register_new_node(add1, n_loop->_head->in(LoopNode::EntryControl));
 470           Node *add2 = new AddPNode(n->in(1), add1, V);
 471           register_new_node(add2, n_ctrl);
 472           _igvn.replace_node(n, add2);
 473           return add2;
 474         }
 475       }
 476     }
 477   }
 478 
 479   return NULL;


 569             cost += ConditionalMoveLimit; // Too much speculative goo
 570       }
 571     }
 572     // See if the Phi is used by a Cmp or Narrow oop Decode/Encode.
 573     // This will likely Split-If, a higher-payoff operation.
 574     for (DUIterator_Fast kmax, k = phi->fast_outs(kmax); k < kmax; k++) {
 575       Node* use = phi->fast_out(k);
 576       if (use->is_Cmp() || use->is_DecodeNarrowPtr() || use->is_EncodeNarrowPtr())
 577         cost += ConditionalMoveLimit;
 578       // Is there a use inside the loop?
 579       // Note: check only basic types since CMoveP is pinned.
 580       if (!used_inside_loop && is_java_primitive(bt)) {
 581         IdealLoopTree* u_loop = get_loop(has_ctrl(use) ? get_ctrl(use) : use);
 582         if (r_loop == u_loop || r_loop->is_member(u_loop)) {
 583           used_inside_loop = true;
 584         }
 585       }
 586     }
 587   }//for
 588   Node* bol = iff->in(1);
 589   assert(bol->Opcode() == Op_Bool, "");
 590   int cmp_op = bol->in(1)->Opcode();
 591   // It is expensive to generate flags from a float compare.
 592   // Avoid duplicated float compare.
 593   if (phis > 1 && (cmp_op == Op_CmpF || cmp_op == Op_CmpD)) return NULL;
 594 
 595   float infrequent_prob = PROB_UNLIKELY_MAG(3);
 596   // Ignore cost and blocks frequency if CMOVE can be moved outside the loop.
 597   if (used_inside_loop) {
 598     if (cost >= ConditionalMoveLimit) return NULL; // Too much goo
 599 
 600     // BlockLayoutByFrequency optimization moves infrequent branch
 601     // from hot path. No point in CMOV'ing in such case (110 is used
 602     // instead of 100 to take into account not exactness of float value).
 603     if (BlockLayoutByFrequency) {
 604       infrequent_prob = MAX2(infrequent_prob, (float)BlockLayoutMinDiamondPercentage/110.0f);
 605     }
 606   }
 607   // Check for highly predictable branch.  No point in CMOV'ing if
 608   // we are going to predict accurately all the time.
 609   if (C->use_cmove() && cmp_op == Op_CmpD) ;//keep going
 610   else if (iff->_prob < infrequent_prob ||
 611       iff->_prob > (1.0f - infrequent_prob))
 612     return NULL;
 613 
 614   // --------------
 615   // Now replace all Phis with CMOV's
 616   Node *cmov_ctrl = iff->in(0);
 617   uint flip = (lp->Opcode() == Op_IfTrue);
 618   while (1) {
 619     PhiNode* phi = NULL;
 620     for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
 621       Node *out = region->fast_out(i);
 622       if (out->is_Phi()) {
 623         phi = out->as_Phi();
 624         break;
 625       }
 626     }
 627     if (phi == NULL)  break;
 628     if (PrintOpto && VerifyLoopOptimizations) { tty->print_cr("CMOV"); }
 629     // Move speculative ops
 630     for (uint j = 1; j < region->req(); j++) {
 631       Node *proj = region->in(j);
 632       Node *inp = phi->in(j);
 633       if (get_ctrl(inp) == proj) { // Found local op
 634 #ifndef PRODUCT
 635         if (PrintOpto && VerifyLoopOptimizations) {
 636           tty->print("  speculate: ");
 637           inp->dump();


 650       if (Verbose) {
 651         bol->in(1)->dump(1);
 652         cmov->dump(1);
 653       }
 654     }
 655     if (VerifyLoopOptimizations) verify();
 656 #endif
 657   }
 658 
 659   // The useless CFG diamond will fold up later; see the optimization in
 660   // RegionNode::Ideal.
 661   _igvn._worklist.push(region);
 662 
 663   return iff->in(1);
 664 }
 665 
 666 static void enqueue_cfg_uses(Node* m, Unique_Node_List& wq) {
 667   for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax; i++) {
 668     Node* u = m->fast_out(i);
 669     if (u->is_CFG()) {
 670       if (u->Opcode() == Op_NeverBranch) {
 671         u = ((NeverBranchNode*)u)->proj_out(0);
 672         enqueue_cfg_uses(u, wq);
 673       } else {
 674         wq.push(u);
 675       }
 676     }
 677   }
 678 }
 679 
 680 // Try moving a store out of a loop, right before the loop
 681 Node* PhaseIdealLoop::try_move_store_before_loop(Node* n, Node *n_ctrl) {
 682   // Store has to be first in the loop body
 683   IdealLoopTree *n_loop = get_loop(n_ctrl);
 684   if (n->is_Store() && n_loop != _ltree_root && n_loop->is_loop() && n->in(0) != NULL) {
 685     Node* address = n->in(MemNode::Address);
 686     Node* value = n->in(MemNode::ValueIn);
 687     Node* mem = n->in(MemNode::Memory);
 688     IdealLoopTree* address_loop = get_loop(get_ctrl(address));
 689     IdealLoopTree* value_loop = get_loop(get_ctrl(value));
 690 


 860             assert(n->outcnt() == 0, "all uses should be gone");
 861             _igvn.replace_input_of(n, MemNode::Memory, C->top());
 862             // Disconnect the phi now. An empty phi can confuse other
 863             // optimizations in this pass of loop opts..
 864             if (phi->in(LoopNode::LoopBackControl) == phi) {
 865               _igvn.replace_node(phi, phi->in(LoopNode::EntryControl));
 866               n_loop->_body.yank(phi);
 867             }
 868           }
 869         }
 870       }
 871     }
 872   }
 873 }
 874 
 875 //------------------------------split_if_with_blocks_pre-----------------------
 876 // Do the real work in a non-recursive function.  Data nodes want to be
 877 // cloned in the pre-order so they can feed each other nicely.
 878 Node *PhaseIdealLoop::split_if_with_blocks_pre( Node *n ) {
 879   // Cloning these guys is unlikely to win
 880   int n_op = n->Opcode();
 881   if( n_op == Op_MergeMem ) return n;
 882   if( n->is_Proj() ) return n;
 883   // Do not clone-up CmpFXXX variations, as these are always
 884   // followed by a CmpI
 885   if( n->is_Cmp() ) return n;
 886   // Attempt to use a conditional move instead of a phi/branch
 887   if( ConditionalMoveLimit > 0 && n_op == Op_Region ) {
 888     Node *cmov = conditional_move( n );
 889     if( cmov ) return cmov;
 890   }
 891   if( n->is_CFG() || n->is_LoadStore() )
 892     return n;
 893   if( n_op == Op_Opaque1 ||     // Opaque nodes cannot be mod'd
 894       n_op == Op_Opaque2 ) {
 895     if( !C->major_progress() )   // If chance of no more loop opts...
 896       _igvn._worklist.push(n);  // maybe we'll remove them
 897     return n;
 898   }
 899 
 900   if( n->is_Con() ) return n;   // No cloning for Con nodes
 901 
 902   Node *n_ctrl = get_ctrl(n);
 903   if( !n_ctrl ) return n;       // Dead node
 904 
 905   Node* res = try_move_store_before_loop(n, n_ctrl);
 906   if (res != NULL) {
 907     return n;
 908   }
 909 
 910   // Attempt to remix address expressions for loop invariants
 911   Node *m = remix_address_expressions( n );
 912   if( m ) return m;
 913 
 914   if (n->is_ConstraintCast()) {
 915     Node* dom_cast = n->as_ConstraintCast()->dominating_cast(this);
 916     if (dom_cast != NULL) {
 917       _igvn.replace_node(n, dom_cast);
 918       return dom_cast;
 919     }
 920   }
 921 
 922   // Determine if the Node has inputs from some local Phi.
 923   // Returns the block to clone thru.
 924   Node *n_blk = has_local_phi_input( n );
 925   if( !n_blk ) return n;
 926 
 927   // Do not clone the trip counter through on a CountedLoop
 928   // (messes up the canonical shape).
 929   if( n_blk->is_CountedLoop() && n->Opcode() == Op_AddI ) return n;
 930 
 931   // Check for having no control input; not pinned.  Allow
 932   // dominating control.
 933   if (n->in(0)) {
 934     Node *dom = idom(n_blk);
 935     if (dom_lca(n->in(0), dom) != n->in(0)) {
 936       return n;
 937     }
 938   }
 939   // Policy: when is it profitable.  You must get more wins than
 940   // policy before it is considered profitable.  Policy is usually 0,
 941   // so 1 win is considered profitable.  Big merges will require big
 942   // cloning, so get a larger policy.
 943   int policy = n_blk->req() >> 2;
 944 
 945   // If the loop is a candidate for range check elimination,
 946   // delay splitting through it's phi until a later loop optimization
 947   if (n_blk->is_CountedLoop()) {
 948     IdealLoopTree *lp = get_loop(n_blk);
 949     if (lp && lp->_rce_candidate) {


 988 
 989 static bool merge_point_safe(Node* region) {
 990   // 4799512: Stop split_if_with_blocks from splitting a block with a ConvI2LNode
 991   // having a PhiNode input. This sidesteps the dangerous case where the split
 992   // ConvI2LNode may become TOP if the input Value() does not
 993   // overlap the ConvI2L range, leaving a node which may not dominate its
 994   // uses.
 995   // A better fix for this problem can be found in the BugTraq entry, but
 996   // expediency for Mantis demands this hack.
 997   // 6855164: If the merge point has a FastLockNode with a PhiNode input, we stop
 998   // split_if_with_blocks from splitting a block because we could not move around
 999   // the FastLockNode.
1000   for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
1001     Node* n = region->fast_out(i);
1002     if (n->is_Phi()) {
1003       for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
1004         Node* m = n->fast_out(j);
1005         if (m->is_FastLock())
1006           return false;
1007 #ifdef _LP64
1008         if (m->Opcode() == Op_ConvI2L)
1009           return false;
1010         if (m->is_CastII() && m->isa_CastII()->has_range_check()) {
1011           return false;
1012         }
1013 #endif
1014       }
1015     }
1016   }
1017   return true;
1018 }
1019 
1020 
1021 //------------------------------place_near_use---------------------------------
1022 // Place some computation next to use but not inside inner loops.
1023 // For inner loop uses move it to the preheader area.
1024 Node *PhaseIdealLoop::place_near_use( Node *useblock ) const {
1025   IdealLoopTree *u_loop = get_loop( useblock );
1026   return (u_loop->_irreducible || u_loop->_child)
1027     ? useblock
1028     : u_loop->_head->in(LoopNode::EntryControl);


1204     Node* con_false = _igvn.makecon(TypeInt::ZERO);
1205 
1206     for (uint i = 1; i < n_ctrl->req(); i++) {
1207       if (is_dominator(proj_true, n_ctrl->in(i))) {
1208         bolphi->init_req(i, con_true);
1209       } else {
1210         assert(is_dominator(proj_false, n_ctrl->in(i)), "bad if");
1211         bolphi->init_req(i, con_false);
1212       }
1213     }
1214     register_new_node(bolphi, n_ctrl);
1215     _igvn.replace_input_of(n, 1, bolphi);
1216 
1217     // Now split the IF
1218     do_split_if(n);
1219     return;
1220   }
1221 
1222   // Check for an IF ready to split; one that has its
1223   // condition codes input coming from a Phi at the block start.
1224   int n_op = n->Opcode();
1225 
1226   // Check for an IF being dominated by another IF same test
1227   if (n_op == Op_If ||
1228       n_op == Op_RangeCheck) {
1229     Node *bol = n->in(1);
1230     uint max = bol->outcnt();
1231     // Check for same test used more than once?
1232     if (max > 1 && bol->is_Bool()) {
1233       // Search up IDOMs to see if this IF is dominated.
1234       Node *cutoff = get_ctrl(bol);
1235 
1236       // Now search up IDOMs till cutoff, looking for a dominating test
1237       Node *prevdom = n;
1238       Node *dom = idom(prevdom);
1239       while (dom != cutoff) {
1240         if (dom->req() > 1 && dom->in(1) == bol && prevdom->in(0) == dom) {
1241           // Replace the dominated test with an obvious true or false.
1242           // Place it on the IGVN worklist for later cleanup.
1243           C->set_major_progress();
1244           dominated_by(prevdom, n, false, true);
1245 #ifndef PRODUCT
1246           if( VerifyLoopOptimizations ) verify();
1247 #endif
1248           return;


1251         dom = idom(prevdom);
1252       }
1253     }
1254   }
1255 
1256   // See if a shared loop-varying computation has no loop-varying uses.
1257   // Happens if something is only used for JVM state in uncommon trap exits,
1258   // like various versions of induction variable+offset.  Clone the
1259   // computation per usage to allow it to sink out of the loop.
1260   if (has_ctrl(n) && !n->in(0)) {// n not dead and has no control edge (can float about)
1261     Node *n_ctrl = get_ctrl(n);
1262     IdealLoopTree *n_loop = get_loop(n_ctrl);
1263     if( n_loop != _ltree_root ) {
1264       DUIterator_Fast imax, i = n->fast_outs(imax);
1265       for (; i < imax; i++) {
1266         Node* u = n->fast_out(i);
1267         if( !has_ctrl(u) )     break; // Found control user
1268         IdealLoopTree *u_loop = get_loop(get_ctrl(u));
1269         if( u_loop == n_loop ) break; // Found loop-varying use
1270         if( n_loop->is_member( u_loop ) ) break; // Found use in inner loop
1271         if( u->Opcode() == Op_Opaque1 ) break; // Found loop limit, bugfix for 4677003
1272       }
1273       bool did_break = (i < imax);  // Did we break out of the previous loop?
1274       if (!did_break && n->outcnt() > 1) { // All uses in outer loops!
1275         Node *late_load_ctrl = NULL;
1276         if (n->is_Load()) {
1277           // If n is a load, get and save the result from get_late_ctrl(),
1278           // to be later used in calculating the control for n's clones.
1279           clear_dom_lca_tags();
1280           late_load_ctrl = get_late_ctrl(n, n_ctrl);
1281         }
1282         // If n is a load, and the late control is the same as the current
1283         // control, then the cloning of n is a pointless exercise, because
1284         // GVN will ensure that we end up where we started.
1285         if (!n->is_Load() || late_load_ctrl != n_ctrl) {
1286           for (DUIterator_Last jmin, j = n->last_outs(jmin); j >= jmin; ) {
1287             Node *u = n->last_out(j); // Clone private computation per use
1288             _igvn.rehash_node_delayed(u);
1289             Node *x = n->clone(); // Clone computation
1290             Node *x_ctrl = NULL;
1291             if( u->is_Phi() ) {


1338             // cloned x's will common up and undo this optimization and
1339             // be forced back in the loop.  This is annoying because it
1340             // makes +VerifyOpto report false-positives on progress.  I
1341             // tried setting control edges on the x's to force them to
1342             // not combine, but the matching gets worried when it tries
1343             // to fold a StoreP and an AddP together (as part of an
1344             // address expression) and the AddP and StoreP have
1345             // different controls.
1346             if (!x->is_Load() && !x->is_DecodeNarrowPtr()) _igvn._worklist.yank(x);
1347           }
1348           _igvn.remove_dead_node(n);
1349         }
1350       }
1351     }
1352   }
1353 
1354   try_move_store_after_loop(n);
1355 
1356   // Check for Opaque2's who's loop has disappeared - who's input is in the
1357   // same loop nest as their output.  Remove 'em, they are no longer useful.
1358   if( n_op == Op_Opaque2 &&
1359       n->in(1) != NULL &&
1360       get_loop(get_ctrl(n)) == get_loop(get_ctrl(n->in(1))) ) {
1361     _igvn.replace_node( n, n->in(1) );
1362   }
1363 }
1364 
1365 //------------------------------split_if_with_blocks---------------------------
1366 // Check for aggressive application of 'split-if' optimization,
1367 // using basic block level info.
1368 void PhaseIdealLoop::split_if_with_blocks( VectorSet &visited, Node_Stack &nstack ) {
1369   Node *n = C->root();
1370   visited.set(n->_idx); // first, mark node as visited
1371   // Do pre-visit work for root
1372   n = split_if_with_blocks_pre( n );
1373   uint cnt = n->outcnt();
1374   uint i   = 0;
1375   while (true) {
1376     // Visit all children
1377     if (i < cnt) {
1378       Node* use = n->raw_out(i);


1753       if( !loop->is_member( use_loop ) && (!old->is_CFG() || !use->is_CFG())) {
1754 
1755         // If the Data use is an IF, that means we have an IF outside of the
1756         // loop that is switching on a condition that is set inside of the
1757         // loop.  Happens if people set a loop-exit flag; then test the flag
1758         // in the loop to break the loop, then test is again outside of the
1759         // loop to determine which way the loop exited.
1760         // Loop predicate If node connects to Bool node through Opaque1 node.
1761         if (use->is_If() || use->is_CMove() || C->is_predicate_opaq(use)) {
1762           // Since this code is highly unlikely, we lazily build the worklist
1763           // of such Nodes to go split.
1764           if( !split_if_set )
1765             split_if_set = new Node_List(area);
1766           split_if_set->push(use);
1767         }
1768         if( use->is_Bool() ) {
1769           if( !split_bool_set )
1770             split_bool_set = new Node_List(area);
1771           split_bool_set->push(use);
1772         }
1773         if( use->Opcode() == Op_CreateEx ) {
1774           if( !split_cex_set )
1775             split_cex_set = new Node_List(area);
1776           split_cex_set->push(use);
1777         }
1778 
1779 
1780         // Get "block" use is in
1781         uint idx = 0;
1782         while( use->in(idx) != old ) idx++;
1783         Node *prev = use->is_CFG() ? use : get_ctrl(use);
1784         assert( !loop->is_member( get_loop( prev ) ), "" );
1785         Node *cfg = prev->_idx >= new_counter
1786           ? prev->in(2)
1787           : idom(prev);
1788         if( use->is_Phi() )     // Phi use is in prior block
1789           cfg = prev->in(idx);  // NOT in block of Phi itself
1790         if (cfg->is_top()) {    // Use is dead?
1791           _igvn.replace_input_of(use, idx, C->top());
1792           continue;
1793         }


1889     }
1890   }
1891 
1892 }
1893 
1894 
1895 //---------------------- stride_of_possible_iv -------------------------------------
1896 // Looks for an iff/bool/comp with one operand of the compare
1897 // being a cycle involving an add and a phi,
1898 // with an optional truncation (left-shift followed by a right-shift)
1899 // of the add. Returns zero if not an iv.
1900 int PhaseIdealLoop::stride_of_possible_iv(Node* iff) {
1901   Node* trunc1 = NULL;
1902   Node* trunc2 = NULL;
1903   const TypeInt* ttype = NULL;
1904   if (!iff->is_If() || iff->in(1) == NULL || !iff->in(1)->is_Bool()) {
1905     return 0;
1906   }
1907   BoolNode* bl = iff->in(1)->as_Bool();
1908   Node* cmp = bl->in(1);
1909   if (!cmp || cmp->Opcode() != Op_CmpI && cmp->Opcode() != Op_CmpU) {
1910     return 0;
1911   }
1912   // Must have an invariant operand
1913   if (is_member(get_loop(iff), get_ctrl(cmp->in(2)))) {
1914     return 0;
1915   }
1916   Node* add2 = NULL;
1917   Node* cmp1 = cmp->in(1);
1918   if (cmp1->is_Phi()) {
1919     // (If (Bool (CmpX phi:(Phi ...(Optional-trunc(AddI phi add2))) )))
1920     Node* phi = cmp1;
1921     for (uint i = 1; i < phi->req(); i++) {
1922       Node* in = phi->in(i);
1923       Node* add = CountedLoopNode::match_incr_with_optional_truncation(in,
1924                                 &trunc1, &trunc2, &ttype);
1925       if (add && add->in(1) == phi) {
1926         add2 = add->in(2);
1927         break;
1928       }
1929     }


2028 //
2029 ProjNode* PhaseIdealLoop::insert_if_before_proj(Node* left, bool Signed, BoolTest::mask relop, Node* right, ProjNode* proj) {
2030   IfNode* iff = proj->in(0)->as_If();
2031   IdealLoopTree *loop = get_loop(proj);
2032   ProjNode *other_proj = iff->proj_out(!proj->is_IfTrue())->as_Proj();
2033   int ddepth = dom_depth(proj);
2034 
2035   _igvn.rehash_node_delayed(iff);
2036   _igvn.rehash_node_delayed(proj);
2037 
2038   proj->set_req(0, NULL);  // temporary disconnect
2039   ProjNode* proj2 = proj_clone(proj, iff);
2040   register_node(proj2, loop, iff, ddepth);
2041 
2042   Node* cmp = Signed ? (Node*) new CmpINode(left, right) : (Node*) new CmpUNode(left, right);
2043   register_node(cmp, loop, proj2, ddepth);
2044 
2045   BoolNode* bol = new BoolNode(cmp, relop);
2046   register_node(bol, loop, proj2, ddepth);
2047 
2048   int opcode = iff->Opcode();
2049   assert(opcode == Op_If || opcode == Op_RangeCheck, "unexpected opcode");
2050   IfNode* new_if = (opcode == Op_If) ? new IfNode(proj2, bol, iff->_prob, iff->_fcnt):
2051     new RangeCheckNode(proj2, bol, iff->_prob, iff->_fcnt);
2052   register_node(new_if, loop, proj2, ddepth);
2053 
2054   proj->set_req(0, new_if); // reattach
2055   set_idom(proj, new_if, ddepth);
2056 
2057   ProjNode* new_exit = proj_clone(other_proj, new_if)->as_Proj();
2058   guarantee(new_exit != NULL, "null exit node");
2059   register_node(new_exit, get_loop(other_proj), new_if, ddepth);
2060 
2061   return new_exit;
2062 }
2063 
2064 //------------------------------ insert_region_before_proj -------------------------------------
2065 // Insert a region before an if projection (* - new node)
2066 //
2067 // before
2068 //           if(test)
2069 //          /      |
2070 //         v       |


2142 //      /  /       |
2143 //     /  /        v
2144 //    /  /  if(i <u limit)    new cloned unsigned test
2145 //   /  /   /      |
2146 //   v  v  v       |
2147 //    region       |
2148 //        |        |
2149 //      dum-if     |
2150 //     /  |        |
2151 // ether  |        |
2152 //        v        v
2153 //   exit-proj   stay-in-loop-proj
2154 //
2155 IfNode* PhaseIdealLoop::insert_cmpi_loop_exit(IfNode* if_cmpu, IdealLoopTree *loop) {
2156   const bool Signed   = true;
2157   const bool Unsigned = false;
2158 
2159   BoolNode* bol = if_cmpu->in(1)->as_Bool();
2160   if (bol->_test._test != BoolTest::lt) return NULL;
2161   CmpNode* cmpu = bol->in(1)->as_Cmp();
2162   if (cmpu->Opcode() != Op_CmpU) return NULL;
2163   int stride = stride_of_possible_iv(if_cmpu);
2164   if (stride == 0) return NULL;
2165 
2166   Node* lp_proj = stay_in_loop(if_cmpu, loop);
2167   guarantee(lp_proj != NULL, "null loop node");
2168 
2169   ProjNode* lp_continue = lp_proj->as_Proj();
2170   ProjNode* lp_exit     = if_cmpu->proj_out(!lp_continue->is_IfTrue())->as_Proj();
2171 
2172   Node* limit = NULL;
2173   if (stride > 0) {
2174     limit = cmpu->in(2);
2175   } else {
2176     limit = _igvn.makecon(TypeInt::ZERO);
2177     set_ctrl(limit, C->root());
2178   }
2179   // Create a new region on the exit path
2180   RegionNode* reg = insert_region_before_proj(lp_exit);
2181   guarantee(reg != NULL, "null region node");
2182 
2183   // Clone the if-cmpu-true-false using a signed compare
2184   BoolTest::mask rel_i = stride > 0 ? bol->_test._test : BoolTest::ge;
2185   ProjNode* cmpi_exit = insert_if_before_proj(cmpu->in(1), Signed, rel_i, limit, lp_continue);
2186   reg->add_req(cmpi_exit);
2187 
2188   // Clone the if-cmpu-true-false
2189   BoolTest::mask rel_u = bol->_test._test;
2190   ProjNode* cmpu_exit = insert_if_before_proj(cmpu->in(1), Unsigned, rel_u, cmpu->in(2), lp_continue);
2191   reg->add_req(cmpu_exit);
2192 
2193   // Force original if to stay in loop.
2194   short_circuit_if(if_cmpu, lp_continue);
2195 
2196   return cmpi_exit->in(0)->as_If();
2197 }
2198 
2199 //------------------------------ remove_cmpi_loop_exit -------------------------------------
2200 // Remove a previously inserted signed compare loop exit.
2201 void PhaseIdealLoop::remove_cmpi_loop_exit(IfNode* if_cmp, IdealLoopTree *loop) {
2202   Node* lp_proj = stay_in_loop(if_cmp, loop);
2203   assert(if_cmp->in(1)->in(1)->Opcode() == Op_CmpI &&
2204          stay_in_loop(lp_proj, loop)->is_If() &&
2205          stay_in_loop(lp_proj, loop)->in(1)->in(1)->Opcode() == Op_CmpU, "inserted cmpi before cmpu");
2206   Node *con = _igvn.makecon(lp_proj->is_IfTrue() ? TypeInt::ONE : TypeInt::ZERO);
2207   set_ctrl(con, C->root());
2208   if_cmp->set_req(1, con);
2209 }
2210 
2211 //------------------------------ scheduled_nodelist -------------------------------------
2212 // Create a post order schedule of nodes that are in the
2213 // "member" set.  The list is returned in "sched".
2214 // The first node in "sched" is the loop head, followed by
2215 // nodes which have no inputs in the "member" set, and then
2216 // followed by the nodes that have an immediate input dependence
2217 // on a node in "sched".
2218 void PhaseIdealLoop::scheduled_nodelist( IdealLoopTree *loop, VectorSet& member, Node_List &sched ) {
2219 
2220   assert(member.test(loop->_head->_idx), "loop head must be in member set");
2221   Arena *a = Thread::current()->resource_area();
2222   VectorSet visited(a);
2223   Node_Stack nstack(a, loop->_body.size());
2224 
2225   Node* n  = loop->_head;  // top of stack is cached in "n"


2439       if (!found) {
2440         return false;
2441       }
2442     } else if (not_peel.test(di)) {
2443       if (peel.test(di)) {
2444         return false;
2445       }
2446     } else {
2447       return false;
2448     }
2449   }
2450   return true;
2451 }
2452 
2453 //------------------------------ is_valid_clone_loop_exit_use -------------------------------------
2454 // Ensure a use outside of loop is of the right form
2455 bool PhaseIdealLoop::is_valid_clone_loop_exit_use( IdealLoopTree *loop, Node* use, uint exit_idx) {
2456   Node *use_c = has_ctrl(use) ? get_ctrl(use) : use;
2457   return (use->is_Phi() &&
2458           use_c->is_Region() && use_c->req() == 3 &&
2459           (use_c->in(exit_idx)->Opcode() == Op_IfTrue ||
2460            use_c->in(exit_idx)->Opcode() == Op_IfFalse ||
2461            use_c->in(exit_idx)->Opcode() == Op_JumpProj) &&
2462           loop->is_member( get_loop( use_c->in(exit_idx)->in(0) ) ) );
2463 }
2464 
2465 //------------------------------ is_valid_clone_loop_form -------------------------------------
2466 // Ensure that all uses outside of loop are of the right form
2467 bool PhaseIdealLoop::is_valid_clone_loop_form( IdealLoopTree *loop, Node_List& peel_list,
2468                                                uint orig_exit_idx, uint clone_exit_idx) {
2469   uint len = peel_list.size();
2470   for (uint i = 0; i < len; i++) {
2471     Node *def = peel_list.at(i);
2472 
2473     for (DUIterator_Fast jmax, j = def->fast_outs(jmax); j < jmax; j++) {
2474       Node *use = def->fast_out(j);
2475       Node *use_c = has_ctrl(use) ? get_ctrl(use) : use;
2476       if (!loop->is_member(get_loop(use_c))) {
2477         // use is not in the loop, check for correct structure
2478         if (use->in(0) == def) {
2479           // Okay
2480         } else if (!is_valid_clone_loop_exit_use(loop, use, orig_exit_idx)) {
2481           return false;


2694 //          RegionA
2695 //             |
2696 //             v
2697 //           exitA
2698 //
2699 bool PhaseIdealLoop::partial_peel( IdealLoopTree *loop, Node_List &old_new ) {
2700 
2701   assert(!loop->_head->is_CountedLoop(), "Non-counted loop only");
2702   if (!loop->_head->is_Loop()) {
2703     return false;  }
2704 
2705   LoopNode *head  = loop->_head->as_Loop();
2706 
2707   if (head->is_partial_peel_loop() || head->partial_peel_has_failed()) {
2708     return false;
2709   }
2710 
2711   // Check for complex exit control
2712   for(uint ii = 0; ii < loop->_body.size(); ii++ ) {
2713     Node *n = loop->_body.at(ii);
2714     int opc = n->Opcode();
2715     if (n->is_Call()        ||
2716         opc == Op_Catch     ||
2717         opc == Op_CatchProj ||
2718         opc == Op_Jump      ||
2719         opc == Op_JumpProj) {
2720 #if !defined(PRODUCT)
2721       if (TracePartialPeeling) {
2722         tty->print_cr("\nExit control too complex: lp: %d", head->_idx);
2723       }
2724 #endif
2725       return false;
2726     }
2727   }
2728 
2729   int dd = dom_depth(head);
2730 
2731   // Step 1: find cut point
2732 
2733   // Walk up dominators to loop head looking for first loop exit
2734   // which is executed on every path thru loop.
2735   IfNode *peel_if = NULL;
2736   IfNode *peel_if_cmpu = NULL;
2737 
2738   Node *iff = loop->tail();
2739   while( iff != head ) {
2740     if( iff->is_If() ) {
2741       Node *ctrl = get_ctrl(iff->in(1));
2742       if (ctrl->is_top()) return false; // Dead test on live IF.
2743       // If loop-varying exit-test, check for induction variable
2744       if( loop->is_member(get_loop(ctrl)) &&
2745           loop->is_loop_exit(iff) &&
2746           is_possible_iv_test(iff)) {
2747         Node* cmp = iff->in(1)->in(1);
2748         if (cmp->Opcode() == Op_CmpI) {
2749           peel_if = iff->as_If();
2750         } else {
2751           assert(cmp->Opcode() == Op_CmpU, "must be CmpI or CmpU");
2752           peel_if_cmpu = iff->as_If();
2753         }
2754       }
2755     }
2756     iff = idom(iff);
2757   }
2758   // Prefer signed compare over unsigned compare.
2759   IfNode* new_peel_if = NULL;
2760   if (peel_if == NULL) {
2761     if (!PartialPeelAtUnsignedTests || peel_if_cmpu == NULL) {
2762       return false;   // No peel point found
2763     }
2764     new_peel_if = insert_cmpi_loop_exit(peel_if_cmpu, loop);
2765     if (new_peel_if == NULL) {
2766       return false;   // No peel point found
2767     }
2768     peel_if = new_peel_if;
2769   }
2770   Node* last_peel        = stay_in_loop(peel_if, loop);
2771   Node* first_not_peeled = stay_in_loop(last_peel, loop);




  25 #include "precompiled.hpp"
  26 #include "memory/allocation.inline.hpp"
  27 #include "memory/resourceArea.hpp"
  28 #include "opto/addnode.hpp"
  29 #include "opto/castnode.hpp"
  30 #include "opto/connode.hpp"
  31 #include "opto/castnode.hpp"
  32 #include "opto/divnode.hpp"
  33 #include "opto/loopnode.hpp"
  34 #include "opto/matcher.hpp"
  35 #include "opto/mulnode.hpp"
  36 #include "opto/movenode.hpp"
  37 #include "opto/opaquenode.hpp"
  38 #include "opto/rootnode.hpp"
  39 #include "opto/subnode.hpp"
  40 
  41 //=============================================================================
  42 //------------------------------split_thru_phi---------------------------------
  43 // Split Node 'n' through merge point if there is enough win.
  44 Node *PhaseIdealLoop::split_thru_phi( Node *n, Node *region, int policy ) {
  45   if (n->Opcode() == Opcodes::Op_ConvI2L && n->bottom_type() != TypeLong::LONG) {
  46     // ConvI2L may have type information on it which is unsafe to push up
  47     // so disable this for now
  48     return NULL;
  49   }
  50 
  51   // Splitting range check CastIIs through a loop induction Phi can
  52   // cause new Phis to be created that are left unrelated to the loop
  53   // induction Phi and prevent optimizations (vectorization)
  54   if (n->Opcode() == Opcodes::Op_CastII && n->as_CastII()->has_range_check() &&
  55       region->is_CountedLoop() && n->in(1) == region->as_CountedLoop()->phi()) {
  56     return NULL;
  57   }
  58 
  59   int wins = 0;
  60   assert(!n->is_CFG(), "");
  61   assert(region->is_Region(), "");
  62 
  63   const Type* type = n->bottom_type();
  64   const TypeOopPtr *t_oop = _igvn.type(n)->isa_oopptr();
  65   Node *phi;
  66   if (t_oop != NULL && t_oop->is_known_instance_field()) {
  67     int iid    = t_oop->instance_id();
  68     int index  = C->get_alias_index(t_oop);
  69     int offset = t_oop->offset();
  70     phi = new PhiNode(region, type, NULL, iid, index, offset);
  71   } else {
  72     phi = PhiNode::make_blank(region, n);
  73   }
  74   uint old_unique = C->unique();


 197     if (old_loop != new_loop) {
 198       if (old_loop && !old_loop->_child)
 199         old_loop->_body.yank(x);
 200       if (!new_loop->_child)
 201         new_loop->_body.push(x);  // Collect body info
 202     }
 203   }
 204 
 205   return phi;
 206 }
 207 
 208 //------------------------------dominated_by------------------------------------
 209 // Replace the dominated test with an obvious true or false.  Place it on the
 210 // IGVN worklist for later cleanup.  Move control-dependent data Nodes on the
 211 // live path up to the dominating control.
 212 void PhaseIdealLoop::dominated_by( Node *prevdom, Node *iff, bool flip, bool exclude_loop_predicate ) {
 213   if (VerifyLoopOptimizations && PrintOpto) { tty->print_cr("dominating test"); }
 214 
 215   // prevdom is the dominating projection of the dominating test.
 216   assert( iff->is_If(), "" );
 217   assert(iff->Opcode() == Opcodes::Op_If || iff->Opcode() == Opcodes::Op_CountedLoopEnd || iff->Opcode() == Opcodes::Op_RangeCheck, "Check this code when new subtype is added");
 218   Opcodes pop = prevdom->Opcode();
 219   assert( pop == Opcodes::Op_IfFalse || pop == Opcodes::Op_IfTrue, "" );
 220   if (flip) {
 221     if (pop == Opcodes::Op_IfTrue)
 222       pop = Opcodes::Op_IfFalse;
 223     else
 224       pop = Opcodes::Op_IfTrue;
 225   }
 226   // 'con' is set to true or false to kill the dominated test.
 227   Node *con = _igvn.makecon(pop == Opcodes::Op_IfTrue ? TypeInt::ONE : TypeInt::ZERO);
 228   set_ctrl(con, C->root()); // Constant gets a new use
 229   // Hack the dominated test
 230   _igvn.replace_input_of(iff, 1, con);
 231 
 232   // If I dont have a reachable TRUE and FALSE path following the IfNode then
 233   // I can assume this path reaches an infinite loop.  In this case it's not
 234   // important to optimize the data Nodes - either the whole compilation will
 235   // be tossed or this path (and all data Nodes) will go dead.
 236   if (iff->outcnt() != 2) return;
 237 
 238   // Make control-dependent data Nodes on the live path (path that will remain
 239   // once the dominated IF is removed) become control-dependent on the
 240   // dominating projection.
 241   Node* dp = iff->as_If()->proj_out(pop == Opcodes::Op_IfTrue);
 242 
 243   // Loop predicates may have depending checks which should not
 244   // be skipped. For example, range check predicate has two checks
 245   // for lower and upper bounds.
 246   if (dp == NULL)
 247     return;
 248 
 249   ProjNode* dp_proj  = dp->as_Proj();
 250   ProjNode* unc_proj = iff->as_If()->proj_out(1 - dp_proj->_con)->as_Proj();
 251   if (exclude_loop_predicate &&
 252       (unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_predicate) != NULL ||
 253        unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_range_check) != NULL)) {
 254     // If this is a range check (IfNode::is_range_check), do not
 255     // reorder because Compile::allow_range_check_smearing might have
 256     // changed the check.
 257     return; // Let IGVN transformation change control dependence.
 258   }
 259 
 260   IdealLoopTree *old_loop = get_loop(dp);
 261 


 334   Node *n1_ctrl = get_ctrl(n->in(                    1));
 335   Node *n2_ctrl = get_ctrl(n->in(                    2));
 336   Node *n3_ctrl = get_ctrl(n->in(n->req() == 3 ? 2 : 3));
 337   IdealLoopTree *n1_loop = get_loop( n1_ctrl );
 338   IdealLoopTree *n2_loop = get_loop( n2_ctrl );
 339   IdealLoopTree *n3_loop = get_loop( n3_ctrl );
 340 
 341   // Does one of my inputs spin in a tighter loop than self?
 342   if( (n_loop->is_member( n1_loop ) && n_loop != n1_loop) ||
 343       (n_loop->is_member( n2_loop ) && n_loop != n2_loop) ||
 344       (n_loop->is_member( n3_loop ) && n_loop != n3_loop) )
 345     return NULL;                // Leave well enough alone
 346 
 347   // Is at least one of my inputs loop-invariant?
 348   if( n1_loop == n_loop &&
 349       n2_loop == n_loop &&
 350       n3_loop == n_loop )
 351     return NULL;                // No loop-invariant inputs
 352 
 353 
 354   Opcodes n_op = n->Opcode();
 355 
 356   // Replace expressions like ((V+I) << 2) with (V<<2 + I<<2).
 357   if( n_op == Opcodes::Op_LShiftI ) {
 358     // Scale is loop invariant
 359     Node *scale = n->in(2);
 360     Node *scale_ctrl = get_ctrl(scale);
 361     IdealLoopTree *scale_loop = get_loop(scale_ctrl );
 362     if( n_loop == scale_loop || !scale_loop->is_member( n_loop ) )
 363       return NULL;
 364     const TypeInt *scale_t = scale->bottom_type()->isa_int();
 365     if( scale_t && scale_t->is_con() && scale_t->get_con() >= 16 )
 366       return NULL;              // Dont bother with byte/short masking
 367     // Add must vary with loop (else shift would be loop-invariant)
 368     Node *add = n->in(1);
 369     Node *add_ctrl = get_ctrl(add);
 370     IdealLoopTree *add_loop = get_loop(add_ctrl);
 371     //assert( n_loop == add_loop, "" );
 372     if( n_loop != add_loop ) return NULL;  // happens w/ evil ZKM loops
 373 
 374     // Convert I-V into I+ (0-V); same for V-I
 375     if( add->Opcode() == Opcodes::Op_SubI &&
 376         _igvn.type( add->in(1) ) != TypeInt::ZERO ) {
 377       Node *zero = _igvn.intcon(0);
 378       set_ctrl(zero, C->root());
 379       Node *neg = new SubINode( _igvn.intcon(0), add->in(2) );
 380       register_new_node( neg, get_ctrl(add->in(2) ) );
 381       add = new AddINode( add->in(1), neg );
 382       register_new_node( add, add_ctrl );
 383     }
 384     if( add->Opcode() != Opcodes::Op_AddI ) return NULL;
 385     // See if one add input is loop invariant
 386     Node *add_var = add->in(1);
 387     Node *add_var_ctrl = get_ctrl(add_var);
 388     IdealLoopTree *add_var_loop = get_loop(add_var_ctrl );
 389     Node *add_invar = add->in(2);
 390     Node *add_invar_ctrl = get_ctrl(add_invar);
 391     IdealLoopTree *add_invar_loop = get_loop(add_invar_ctrl );
 392     if( add_var_loop == n_loop ) {
 393     } else if( add_invar_loop == n_loop ) {
 394       // Swap to find the invariant part
 395       add_invar = add_var;
 396       add_invar_ctrl = add_var_ctrl;
 397       add_invar_loop = add_var_loop;
 398       add_var = add->in(2);
 399       Node *add_var_ctrl = get_ctrl(add_var);
 400       IdealLoopTree *add_var_loop = get_loop(add_var_ctrl );
 401     } else                      // Else neither input is loop invariant
 402       return NULL;
 403     if( n_loop == add_invar_loop || !add_invar_loop->is_member( n_loop ) )
 404       return NULL;              // No invariant part of the add?
 405 
 406     // Yes!  Reshape address expression!
 407     Node *inv_scale = new LShiftINode( add_invar, scale );
 408     Node *inv_scale_ctrl =
 409       dom_depth(add_invar_ctrl) > dom_depth(scale_ctrl) ?
 410       add_invar_ctrl : scale_ctrl;
 411     register_new_node( inv_scale, inv_scale_ctrl );
 412     Node *var_scale = new LShiftINode( add_var, scale );
 413     register_new_node( var_scale, n_ctrl );
 414     Node *var_add = new AddINode( var_scale, inv_scale );
 415     register_new_node( var_add, n_ctrl );
 416     _igvn.replace_node( n, var_add );
 417     return var_add;
 418   }
 419 
 420   // Replace (I+V) with (V+I)
 421   if( n_op == Opcodes::Op_AddI ||
 422       n_op == Opcodes::Op_AddL ||
 423       n_op == Opcodes::Op_AddF ||
 424       n_op == Opcodes::Op_AddD ||
 425       n_op == Opcodes::Op_MulI ||
 426       n_op == Opcodes::Op_MulL ||
 427       n_op == Opcodes::Op_MulF ||
 428       n_op == Opcodes::Op_MulD ) {
 429     if( n2_loop == n_loop ) {
 430       assert( n1_loop != n_loop, "" );
 431       n->swap_edges(1, 2);
 432     }
 433   }
 434 
 435   // Replace ((I1 +p V) +p I2) with ((I1 +p I2) +p V),
 436   // but not if I2 is a constant.
 437   if( n_op == Opcodes::Op_AddP ) {
 438     if( n2_loop == n_loop && n3_loop != n_loop ) {
 439       if( n->in(2)->Opcode() == Opcodes::Op_AddP && !n->in(3)->is_Con() ) {
 440         Node *n22_ctrl = get_ctrl(n->in(2)->in(2));
 441         Node *n23_ctrl = get_ctrl(n->in(2)->in(3));
 442         IdealLoopTree *n22loop = get_loop( n22_ctrl );
 443         IdealLoopTree *n23_loop = get_loop( n23_ctrl );
 444         if( n22loop != n_loop && n22loop->is_member(n_loop) &&
 445             n23_loop == n_loop ) {
 446           Node *add1 = new AddPNode( n->in(1), n->in(2)->in(2), n->in(3) );
 447           // Stuff new AddP in the loop preheader
 448           register_new_node( add1, n_loop->_head->in(LoopNode::EntryControl) );
 449           Node *add2 = new AddPNode( n->in(1), add1, n->in(2)->in(3) );
 450           register_new_node( add2, n_ctrl );
 451           _igvn.replace_node( n, add2 );
 452           return add2;
 453         }
 454       }
 455     }
 456 
 457     // Replace (I1 +p (I2 + V)) with ((I1 +p I2) +p V)
 458     if (n2_loop != n_loop && n3_loop == n_loop) {
 459       if (n->in(3)->Opcode() == Opcodes::Op_AddX) {
 460         Node *V = n->in(3)->in(1);
 461         Node *I = n->in(3)->in(2);
 462         if (is_member(n_loop,get_ctrl(V))) {
 463         } else {
 464           Node *tmp = V; V = I; I = tmp;
 465         }
 466         if (!is_member(n_loop,get_ctrl(I))) {
 467           Node *add1 = new AddPNode(n->in(1), n->in(2), I);
 468           // Stuff new AddP in the loop preheader
 469           register_new_node(add1, n_loop->_head->in(LoopNode::EntryControl));
 470           Node *add2 = new AddPNode(n->in(1), add1, V);
 471           register_new_node(add2, n_ctrl);
 472           _igvn.replace_node(n, add2);
 473           return add2;
 474         }
 475       }
 476     }
 477   }
 478 
 479   return NULL;


 569             cost += ConditionalMoveLimit; // Too much speculative goo
 570       }
 571     }
 572     // See if the Phi is used by a Cmp or Narrow oop Decode/Encode.
 573     // This will likely Split-If, a higher-payoff operation.
 574     for (DUIterator_Fast kmax, k = phi->fast_outs(kmax); k < kmax; k++) {
 575       Node* use = phi->fast_out(k);
 576       if (use->is_Cmp() || use->is_DecodeNarrowPtr() || use->is_EncodeNarrowPtr())
 577         cost += ConditionalMoveLimit;
 578       // Is there a use inside the loop?
 579       // Note: check only basic types since CMoveP is pinned.
 580       if (!used_inside_loop && is_java_primitive(bt)) {
 581         IdealLoopTree* u_loop = get_loop(has_ctrl(use) ? get_ctrl(use) : use);
 582         if (r_loop == u_loop || r_loop->is_member(u_loop)) {
 583           used_inside_loop = true;
 584         }
 585       }
 586     }
 587   }//for
 588   Node* bol = iff->in(1);
 589   assert(bol->Opcode() == Opcodes::Op_Bool, "");
 590   Opcodes cmp_op = bol->in(1)->Opcode();
 591   // It is expensive to generate flags from a float compare.
 592   // Avoid duplicated float compare.
 593   if (phis > 1 && (cmp_op == Opcodes::Op_CmpF || cmp_op == Opcodes::Op_CmpD)) return NULL;
 594 
 595   float infrequent_prob = PROB_UNLIKELY_MAG(3);
 596   // Ignore cost and blocks frequency if CMOVE can be moved outside the loop.
 597   if (used_inside_loop) {
 598     if (cost >= ConditionalMoveLimit) return NULL; // Too much goo
 599 
 600     // BlockLayoutByFrequency optimization moves infrequent branch
 601     // from hot path. No point in CMOV'ing in such case (110 is used
 602     // instead of 100 to take into account not exactness of float value).
 603     if (BlockLayoutByFrequency) {
 604       infrequent_prob = MAX2(infrequent_prob, (float)BlockLayoutMinDiamondPercentage/110.0f);
 605     }
 606   }
 607   // Check for highly predictable branch.  No point in CMOV'ing if
 608   // we are going to predict accurately all the time.
 609   if (C->use_cmove() && cmp_op == Opcodes::Op_CmpD) ;//keep going
 610   else if (iff->_prob < infrequent_prob ||
 611       iff->_prob > (1.0f - infrequent_prob))
 612     return NULL;
 613 
 614   // --------------
 615   // Now replace all Phis with CMOV's
 616   Node *cmov_ctrl = iff->in(0);
 617   uint flip = (lp->Opcode() == Opcodes::Op_IfTrue);
 618   while (1) {
 619     PhiNode* phi = NULL;
 620     for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
 621       Node *out = region->fast_out(i);
 622       if (out->is_Phi()) {
 623         phi = out->as_Phi();
 624         break;
 625       }
 626     }
 627     if (phi == NULL)  break;
 628     if (PrintOpto && VerifyLoopOptimizations) { tty->print_cr("CMOV"); }
 629     // Move speculative ops
 630     for (uint j = 1; j < region->req(); j++) {
 631       Node *proj = region->in(j);
 632       Node *inp = phi->in(j);
 633       if (get_ctrl(inp) == proj) { // Found local op
 634 #ifndef PRODUCT
 635         if (PrintOpto && VerifyLoopOptimizations) {
 636           tty->print("  speculate: ");
 637           inp->dump();


 650       if (Verbose) {
 651         bol->in(1)->dump(1);
 652         cmov->dump(1);
 653       }
 654     }
 655     if (VerifyLoopOptimizations) verify();
 656 #endif
 657   }
 658 
 659   // The useless CFG diamond will fold up later; see the optimization in
 660   // RegionNode::Ideal.
 661   _igvn._worklist.push(region);
 662 
 663   return iff->in(1);
 664 }
 665 
 666 static void enqueue_cfg_uses(Node* m, Unique_Node_List& wq) {
 667   for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax; i++) {
 668     Node* u = m->fast_out(i);
 669     if (u->is_CFG()) {
 670       if (u->Opcode() == Opcodes::Op_NeverBranch) {
 671         u = ((NeverBranchNode*)u)->proj_out(0);
 672         enqueue_cfg_uses(u, wq);
 673       } else {
 674         wq.push(u);
 675       }
 676     }
 677   }
 678 }
 679 
 680 // Try moving a store out of a loop, right before the loop
 681 Node* PhaseIdealLoop::try_move_store_before_loop(Node* n, Node *n_ctrl) {
 682   // Store has to be first in the loop body
 683   IdealLoopTree *n_loop = get_loop(n_ctrl);
 684   if (n->is_Store() && n_loop != _ltree_root && n_loop->is_loop() && n->in(0) != NULL) {
 685     Node* address = n->in(MemNode::Address);
 686     Node* value = n->in(MemNode::ValueIn);
 687     Node* mem = n->in(MemNode::Memory);
 688     IdealLoopTree* address_loop = get_loop(get_ctrl(address));
 689     IdealLoopTree* value_loop = get_loop(get_ctrl(value));
 690 


 860             assert(n->outcnt() == 0, "all uses should be gone");
 861             _igvn.replace_input_of(n, MemNode::Memory, C->top());
 862             // Disconnect the phi now. An empty phi can confuse other
 863             // optimizations in this pass of loop opts..
 864             if (phi->in(LoopNode::LoopBackControl) == phi) {
 865               _igvn.replace_node(phi, phi->in(LoopNode::EntryControl));
 866               n_loop->_body.yank(phi);
 867             }
 868           }
 869         }
 870       }
 871     }
 872   }
 873 }
 874 
 875 //------------------------------split_if_with_blocks_pre-----------------------
 876 // Do the real work in a non-recursive function.  Data nodes want to be
 877 // cloned in the pre-order so they can feed each other nicely.
 878 Node *PhaseIdealLoop::split_if_with_blocks_pre( Node *n ) {
 879   // Cloning these guys is unlikely to win
 880   Opcodes n_op = n->Opcode();
 881   if( n_op == Opcodes::Op_MergeMem ) return n;
 882   if( n->is_Proj() ) return n;
 883   // Do not clone-up CmpFXXX variations, as these are always
 884   // followed by a CmpI
 885   if( n->is_Cmp() ) return n;
 886   // Attempt to use a conditional move instead of a phi/branch
 887   if( ConditionalMoveLimit > 0 && n_op == Opcodes::Op_Region ) {
 888     Node *cmov = conditional_move( n );
 889     if( cmov ) return cmov;
 890   }
 891   if( n->is_CFG() || n->is_LoadStore() )
 892     return n;
 893   if( n_op == Opcodes::Op_Opaque1 ||     // Opaque nodes cannot be mod'd
 894       n_op == Opcodes::Op_Opaque2 ) {
 895     if( !C->major_progress() )   // If chance of no more loop opts...
 896       _igvn._worklist.push(n);  // maybe we'll remove them
 897     return n;
 898   }
 899 
 900   if( n->is_Con() ) return n;   // No cloning for Con nodes
 901 
 902   Node *n_ctrl = get_ctrl(n);
 903   if( !n_ctrl ) return n;       // Dead node
 904 
 905   Node* res = try_move_store_before_loop(n, n_ctrl);
 906   if (res != NULL) {
 907     return n;
 908   }
 909 
 910   // Attempt to remix address expressions for loop invariants
 911   Node *m = remix_address_expressions( n );
 912   if( m ) return m;
 913 
 914   if (n->is_ConstraintCast()) {
 915     Node* dom_cast = n->as_ConstraintCast()->dominating_cast(this);
 916     if (dom_cast != NULL) {
 917       _igvn.replace_node(n, dom_cast);
 918       return dom_cast;
 919     }
 920   }
 921 
 922   // Determine if the Node has inputs from some local Phi.
 923   // Returns the block to clone thru.
 924   Node *n_blk = has_local_phi_input( n );
 925   if( !n_blk ) return n;
 926 
 927   // Do not clone the trip counter through on a CountedLoop
 928   // (messes up the canonical shape).
 929   if( n_blk->is_CountedLoop() && n->Opcode() == Opcodes::Op_AddI ) return n;
 930 
 931   // Check for having no control input; not pinned.  Allow
 932   // dominating control.
 933   if (n->in(0)) {
 934     Node *dom = idom(n_blk);
 935     if (dom_lca(n->in(0), dom) != n->in(0)) {
 936       return n;
 937     }
 938   }
 939   // Policy: when is it profitable.  You must get more wins than
 940   // policy before it is considered profitable.  Policy is usually 0,
 941   // so 1 win is considered profitable.  Big merges will require big
 942   // cloning, so get a larger policy.
 943   int policy = n_blk->req() >> 2;
 944 
 945   // If the loop is a candidate for range check elimination,
 946   // delay splitting through it's phi until a later loop optimization
 947   if (n_blk->is_CountedLoop()) {
 948     IdealLoopTree *lp = get_loop(n_blk);
 949     if (lp && lp->_rce_candidate) {


 988 
 989 static bool merge_point_safe(Node* region) {
 990   // 4799512: Stop split_if_with_blocks from splitting a block with a ConvI2LNode
 991   // having a PhiNode input. This sidesteps the dangerous case where the split
 992   // ConvI2LNode may become TOP if the input Value() does not
 993   // overlap the ConvI2L range, leaving a node which may not dominate its
 994   // uses.
 995   // A better fix for this problem can be found in the BugTraq entry, but
 996   // expediency for Mantis demands this hack.
 997   // 6855164: If the merge point has a FastLockNode with a PhiNode input, we stop
 998   // split_if_with_blocks from splitting a block because we could not move around
 999   // the FastLockNode.
1000   for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
1001     Node* n = region->fast_out(i);
1002     if (n->is_Phi()) {
1003       for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
1004         Node* m = n->fast_out(j);
1005         if (m->is_FastLock())
1006           return false;
1007 #ifdef _LP64
1008         if (m->Opcode() == Opcodes::Op_ConvI2L)
1009           return false;
1010         if (m->is_CastII() && m->isa_CastII()->has_range_check()) {
1011           return false;
1012         }
1013 #endif
1014       }
1015     }
1016   }
1017   return true;
1018 }
1019 
1020 
1021 //------------------------------place_near_use---------------------------------
1022 // Place some computation next to use but not inside inner loops.
1023 // For inner loop uses move it to the preheader area.
1024 Node *PhaseIdealLoop::place_near_use( Node *useblock ) const {
1025   IdealLoopTree *u_loop = get_loop( useblock );
1026   return (u_loop->_irreducible || u_loop->_child)
1027     ? useblock
1028     : u_loop->_head->in(LoopNode::EntryControl);


1204     Node* con_false = _igvn.makecon(TypeInt::ZERO);
1205 
1206     for (uint i = 1; i < n_ctrl->req(); i++) {
1207       if (is_dominator(proj_true, n_ctrl->in(i))) {
1208         bolphi->init_req(i, con_true);
1209       } else {
1210         assert(is_dominator(proj_false, n_ctrl->in(i)), "bad if");
1211         bolphi->init_req(i, con_false);
1212       }
1213     }
1214     register_new_node(bolphi, n_ctrl);
1215     _igvn.replace_input_of(n, 1, bolphi);
1216 
1217     // Now split the IF
1218     do_split_if(n);
1219     return;
1220   }
1221 
1222   // Check for an IF ready to split; one that has its
1223   // condition codes input coming from a Phi at the block start.
1224   Opcodes n_op = n->Opcode();
1225 
1226   // Check for an IF being dominated by another IF same test
1227   if (n_op == Opcodes::Op_If ||
1228       n_op == Opcodes::Op_RangeCheck) {
1229     Node *bol = n->in(1);
1230     uint max = bol->outcnt();
1231     // Check for same test used more than once?
1232     if (max > 1 && bol->is_Bool()) {
1233       // Search up IDOMs to see if this IF is dominated.
1234       Node *cutoff = get_ctrl(bol);
1235 
1236       // Now search up IDOMs till cutoff, looking for a dominating test
1237       Node *prevdom = n;
1238       Node *dom = idom(prevdom);
1239       while (dom != cutoff) {
1240         if (dom->req() > 1 && dom->in(1) == bol && prevdom->in(0) == dom) {
1241           // Replace the dominated test with an obvious true or false.
1242           // Place it on the IGVN worklist for later cleanup.
1243           C->set_major_progress();
1244           dominated_by(prevdom, n, false, true);
1245 #ifndef PRODUCT
1246           if( VerifyLoopOptimizations ) verify();
1247 #endif
1248           return;


1251         dom = idom(prevdom);
1252       }
1253     }
1254   }
1255 
1256   // See if a shared loop-varying computation has no loop-varying uses.
1257   // Happens if something is only used for JVM state in uncommon trap exits,
1258   // like various versions of induction variable+offset.  Clone the
1259   // computation per usage to allow it to sink out of the loop.
1260   if (has_ctrl(n) && !n->in(0)) {// n not dead and has no control edge (can float about)
1261     Node *n_ctrl = get_ctrl(n);
1262     IdealLoopTree *n_loop = get_loop(n_ctrl);
1263     if( n_loop != _ltree_root ) {
1264       DUIterator_Fast imax, i = n->fast_outs(imax);
1265       for (; i < imax; i++) {
1266         Node* u = n->fast_out(i);
1267         if( !has_ctrl(u) )     break; // Found control user
1268         IdealLoopTree *u_loop = get_loop(get_ctrl(u));
1269         if( u_loop == n_loop ) break; // Found loop-varying use
1270         if( n_loop->is_member( u_loop ) ) break; // Found use in inner loop
1271         if( u->Opcode() == Opcodes::Op_Opaque1 ) break; // Found loop limit, bugfix for 4677003
1272       }
1273       bool did_break = (i < imax);  // Did we break out of the previous loop?
1274       if (!did_break && n->outcnt() > 1) { // All uses in outer loops!
1275         Node *late_load_ctrl = NULL;
1276         if (n->is_Load()) {
1277           // If n is a load, get and save the result from get_late_ctrl(),
1278           // to be later used in calculating the control for n's clones.
1279           clear_dom_lca_tags();
1280           late_load_ctrl = get_late_ctrl(n, n_ctrl);
1281         }
1282         // If n is a load, and the late control is the same as the current
1283         // control, then the cloning of n is a pointless exercise, because
1284         // GVN will ensure that we end up where we started.
1285         if (!n->is_Load() || late_load_ctrl != n_ctrl) {
1286           for (DUIterator_Last jmin, j = n->last_outs(jmin); j >= jmin; ) {
1287             Node *u = n->last_out(j); // Clone private computation per use
1288             _igvn.rehash_node_delayed(u);
1289             Node *x = n->clone(); // Clone computation
1290             Node *x_ctrl = NULL;
1291             if( u->is_Phi() ) {


1338             // cloned x's will common up and undo this optimization and
1339             // be forced back in the loop.  This is annoying because it
1340             // makes +VerifyOpto report false-positives on progress.  I
1341             // tried setting control edges on the x's to force them to
1342             // not combine, but the matching gets worried when it tries
1343             // to fold a StoreP and an AddP together (as part of an
1344             // address expression) and the AddP and StoreP have
1345             // different controls.
1346             if (!x->is_Load() && !x->is_DecodeNarrowPtr()) _igvn._worklist.yank(x);
1347           }
1348           _igvn.remove_dead_node(n);
1349         }
1350       }
1351     }
1352   }
1353 
1354   try_move_store_after_loop(n);
1355 
1356   // Check for Opaque2's who's loop has disappeared - who's input is in the
1357   // same loop nest as their output.  Remove 'em, they are no longer useful.
1358   if( n_op == Opcodes::Op_Opaque2 &&
1359       n->in(1) != NULL &&
1360       get_loop(get_ctrl(n)) == get_loop(get_ctrl(n->in(1))) ) {
1361     _igvn.replace_node( n, n->in(1) );
1362   }
1363 }
1364 
1365 //------------------------------split_if_with_blocks---------------------------
1366 // Check for aggressive application of 'split-if' optimization,
1367 // using basic block level info.
1368 void PhaseIdealLoop::split_if_with_blocks( VectorSet &visited, Node_Stack &nstack ) {
1369   Node *n = C->root();
1370   visited.set(n->_idx); // first, mark node as visited
1371   // Do pre-visit work for root
1372   n = split_if_with_blocks_pre( n );
1373   uint cnt = n->outcnt();
1374   uint i   = 0;
1375   while (true) {
1376     // Visit all children
1377     if (i < cnt) {
1378       Node* use = n->raw_out(i);


1753       if( !loop->is_member( use_loop ) && (!old->is_CFG() || !use->is_CFG())) {
1754 
1755         // If the Data use is an IF, that means we have an IF outside of the
1756         // loop that is switching on a condition that is set inside of the
1757         // loop.  Happens if people set a loop-exit flag; then test the flag
1758         // in the loop to break the loop, then test is again outside of the
1759         // loop to determine which way the loop exited.
1760         // Loop predicate If node connects to Bool node through Opaque1 node.
1761         if (use->is_If() || use->is_CMove() || C->is_predicate_opaq(use)) {
1762           // Since this code is highly unlikely, we lazily build the worklist
1763           // of such Nodes to go split.
1764           if( !split_if_set )
1765             split_if_set = new Node_List(area);
1766           split_if_set->push(use);
1767         }
1768         if( use->is_Bool() ) {
1769           if( !split_bool_set )
1770             split_bool_set = new Node_List(area);
1771           split_bool_set->push(use);
1772         }
1773         if( use->Opcode() == Opcodes::Op_CreateEx ) {
1774           if( !split_cex_set )
1775             split_cex_set = new Node_List(area);
1776           split_cex_set->push(use);
1777         }
1778 
1779 
1780         // Get "block" use is in
1781         uint idx = 0;
1782         while( use->in(idx) != old ) idx++;
1783         Node *prev = use->is_CFG() ? use : get_ctrl(use);
1784         assert( !loop->is_member( get_loop( prev ) ), "" );
1785         Node *cfg = prev->_idx >= new_counter
1786           ? prev->in(2)
1787           : idom(prev);
1788         if( use->is_Phi() )     // Phi use is in prior block
1789           cfg = prev->in(idx);  // NOT in block of Phi itself
1790         if (cfg->is_top()) {    // Use is dead?
1791           _igvn.replace_input_of(use, idx, C->top());
1792           continue;
1793         }


1889     }
1890   }
1891 
1892 }
1893 
1894 
1895 //---------------------- stride_of_possible_iv -------------------------------------
1896 // Looks for an iff/bool/comp with one operand of the compare
1897 // being a cycle involving an add and a phi,
1898 // with an optional truncation (left-shift followed by a right-shift)
1899 // of the add. Returns zero if not an iv.
1900 int PhaseIdealLoop::stride_of_possible_iv(Node* iff) {
1901   Node* trunc1 = NULL;
1902   Node* trunc2 = NULL;
1903   const TypeInt* ttype = NULL;
1904   if (!iff->is_If() || iff->in(1) == NULL || !iff->in(1)->is_Bool()) {
1905     return 0;
1906   }
1907   BoolNode* bl = iff->in(1)->as_Bool();
1908   Node* cmp = bl->in(1);
1909   if (!cmp || cmp->Opcode() != Opcodes::Op_CmpI && cmp->Opcode() != Opcodes::Op_CmpU) {
1910     return 0;
1911   }
1912   // Must have an invariant operand
1913   if (is_member(get_loop(iff), get_ctrl(cmp->in(2)))) {
1914     return 0;
1915   }
1916   Node* add2 = NULL;
1917   Node* cmp1 = cmp->in(1);
1918   if (cmp1->is_Phi()) {
1919     // (If (Bool (CmpX phi:(Phi ...(Optional-trunc(AddI phi add2))) )))
1920     Node* phi = cmp1;
1921     for (uint i = 1; i < phi->req(); i++) {
1922       Node* in = phi->in(i);
1923       Node* add = CountedLoopNode::match_incr_with_optional_truncation(in,
1924                                 &trunc1, &trunc2, &ttype);
1925       if (add && add->in(1) == phi) {
1926         add2 = add->in(2);
1927         break;
1928       }
1929     }


2028 //
2029 ProjNode* PhaseIdealLoop::insert_if_before_proj(Node* left, bool Signed, BoolTest::mask relop, Node* right, ProjNode* proj) {
2030   IfNode* iff = proj->in(0)->as_If();
2031   IdealLoopTree *loop = get_loop(proj);
2032   ProjNode *other_proj = iff->proj_out(!proj->is_IfTrue())->as_Proj();
2033   int ddepth = dom_depth(proj);
2034 
2035   _igvn.rehash_node_delayed(iff);
2036   _igvn.rehash_node_delayed(proj);
2037 
2038   proj->set_req(0, NULL);  // temporary disconnect
2039   ProjNode* proj2 = proj_clone(proj, iff);
2040   register_node(proj2, loop, iff, ddepth);
2041 
2042   Node* cmp = Signed ? (Node*) new CmpINode(left, right) : (Node*) new CmpUNode(left, right);
2043   register_node(cmp, loop, proj2, ddepth);
2044 
2045   BoolNode* bol = new BoolNode(cmp, relop);
2046   register_node(bol, loop, proj2, ddepth);
2047 
2048   Opcodes opcode = iff->Opcode();
2049   assert(opcode == Opcodes::Op_If || opcode == Opcodes::Op_RangeCheck, "unexpected opcode");
2050   IfNode* new_if = (opcode == Opcodes::Op_If) ? new IfNode(proj2, bol, iff->_prob, iff->_fcnt):
2051     new RangeCheckNode(proj2, bol, iff->_prob, iff->_fcnt);
2052   register_node(new_if, loop, proj2, ddepth);
2053 
2054   proj->set_req(0, new_if); // reattach
2055   set_idom(proj, new_if, ddepth);
2056 
2057   ProjNode* new_exit = proj_clone(other_proj, new_if)->as_Proj();
2058   guarantee(new_exit != NULL, "null exit node");
2059   register_node(new_exit, get_loop(other_proj), new_if, ddepth);
2060 
2061   return new_exit;
2062 }
2063 
2064 //------------------------------ insert_region_before_proj -------------------------------------
2065 // Insert a region before an if projection (* - new node)
2066 //
2067 // before
2068 //           if(test)
2069 //          /      |
2070 //         v       |


2142 //      /  /       |
2143 //     /  /        v
2144 //    /  /  if(i <u limit)    new cloned unsigned test
2145 //   /  /   /      |
2146 //   v  v  v       |
2147 //    region       |
2148 //        |        |
2149 //      dum-if     |
2150 //     /  |        |
2151 // ether  |        |
2152 //        v        v
2153 //   exit-proj   stay-in-loop-proj
2154 //
2155 IfNode* PhaseIdealLoop::insert_cmpi_loop_exit(IfNode* if_cmpu, IdealLoopTree *loop) {
2156   const bool Signed   = true;
2157   const bool Unsigned = false;
2158 
2159   BoolNode* bol = if_cmpu->in(1)->as_Bool();
2160   if (bol->_test._test != BoolTest::lt) return NULL;
2161   CmpNode* cmpu = bol->in(1)->as_Cmp();
2162   if (cmpu->Opcode() != Opcodes::Op_CmpU) return NULL;
2163   int stride = stride_of_possible_iv(if_cmpu);
2164   if (stride == 0) return NULL;
2165 
2166   Node* lp_proj = stay_in_loop(if_cmpu, loop);
2167   guarantee(lp_proj != NULL, "null loop node");
2168 
2169   ProjNode* lp_continue = lp_proj->as_Proj();
2170   ProjNode* lp_exit     = if_cmpu->proj_out(!lp_continue->is_IfTrue())->as_Proj();
2171 
2172   Node* limit = NULL;
2173   if (stride > 0) {
2174     limit = cmpu->in(2);
2175   } else {
2176     limit = _igvn.makecon(TypeInt::ZERO);
2177     set_ctrl(limit, C->root());
2178   }
2179   // Create a new region on the exit path
2180   RegionNode* reg = insert_region_before_proj(lp_exit);
2181   guarantee(reg != NULL, "null region node");
2182 
2183   // Clone the if-cmpu-true-false using a signed compare
2184   BoolTest::mask rel_i = stride > 0 ? bol->_test._test : BoolTest::ge;
2185   ProjNode* cmpi_exit = insert_if_before_proj(cmpu->in(1), Signed, rel_i, limit, lp_continue);
2186   reg->add_req(cmpi_exit);
2187 
2188   // Clone the if-cmpu-true-false
2189   BoolTest::mask rel_u = bol->_test._test;
2190   ProjNode* cmpu_exit = insert_if_before_proj(cmpu->in(1), Unsigned, rel_u, cmpu->in(2), lp_continue);
2191   reg->add_req(cmpu_exit);
2192 
2193   // Force original if to stay in loop.
2194   short_circuit_if(if_cmpu, lp_continue);
2195 
2196   return cmpi_exit->in(0)->as_If();
2197 }
2198 
2199 //------------------------------ remove_cmpi_loop_exit -------------------------------------
2200 // Remove a previously inserted signed compare loop exit.
2201 void PhaseIdealLoop::remove_cmpi_loop_exit(IfNode* if_cmp, IdealLoopTree *loop) {
2202   Node* lp_proj = stay_in_loop(if_cmp, loop);
2203   assert(if_cmp->in(1)->in(1)->Opcode() == Opcodes::Op_CmpI &&
2204          stay_in_loop(lp_proj, loop)->is_If() &&
2205          stay_in_loop(lp_proj, loop)->in(1)->in(1)->Opcode() == Opcodes::Op_CmpU, "inserted cmpi before cmpu");
2206   Node *con = _igvn.makecon(lp_proj->is_IfTrue() ? TypeInt::ONE : TypeInt::ZERO);
2207   set_ctrl(con, C->root());
2208   if_cmp->set_req(1, con);
2209 }
2210 
2211 //------------------------------ scheduled_nodelist -------------------------------------
2212 // Create a post order schedule of nodes that are in the
2213 // "member" set.  The list is returned in "sched".
2214 // The first node in "sched" is the loop head, followed by
2215 // nodes which have no inputs in the "member" set, and then
2216 // followed by the nodes that have an immediate input dependence
2217 // on a node in "sched".
2218 void PhaseIdealLoop::scheduled_nodelist( IdealLoopTree *loop, VectorSet& member, Node_List &sched ) {
2219 
2220   assert(member.test(loop->_head->_idx), "loop head must be in member set");
2221   Arena *a = Thread::current()->resource_area();
2222   VectorSet visited(a);
2223   Node_Stack nstack(a, loop->_body.size());
2224 
2225   Node* n  = loop->_head;  // top of stack is cached in "n"


2439       if (!found) {
2440         return false;
2441       }
2442     } else if (not_peel.test(di)) {
2443       if (peel.test(di)) {
2444         return false;
2445       }
2446     } else {
2447       return false;
2448     }
2449   }
2450   return true;
2451 }
2452 
2453 //------------------------------ is_valid_clone_loop_exit_use -------------------------------------
2454 // Ensure a use outside of loop is of the right form
2455 bool PhaseIdealLoop::is_valid_clone_loop_exit_use( IdealLoopTree *loop, Node* use, uint exit_idx) {
2456   Node *use_c = has_ctrl(use) ? get_ctrl(use) : use;
2457   return (use->is_Phi() &&
2458           use_c->is_Region() && use_c->req() == 3 &&
2459           (use_c->in(exit_idx)->Opcode() == Opcodes::Op_IfTrue ||
2460            use_c->in(exit_idx)->Opcode() == Opcodes::Op_IfFalse ||
2461            use_c->in(exit_idx)->Opcode() == Opcodes::Op_JumpProj) &&
2462           loop->is_member( get_loop( use_c->in(exit_idx)->in(0) ) ) );
2463 }
2464 
2465 //------------------------------ is_valid_clone_loop_form -------------------------------------
2466 // Ensure that all uses outside of loop are of the right form
2467 bool PhaseIdealLoop::is_valid_clone_loop_form( IdealLoopTree *loop, Node_List& peel_list,
2468                                                uint orig_exit_idx, uint clone_exit_idx) {
2469   uint len = peel_list.size();
2470   for (uint i = 0; i < len; i++) {
2471     Node *def = peel_list.at(i);
2472 
2473     for (DUIterator_Fast jmax, j = def->fast_outs(jmax); j < jmax; j++) {
2474       Node *use = def->fast_out(j);
2475       Node *use_c = has_ctrl(use) ? get_ctrl(use) : use;
2476       if (!loop->is_member(get_loop(use_c))) {
2477         // use is not in the loop, check for correct structure
2478         if (use->in(0) == def) {
2479           // Okay
2480         } else if (!is_valid_clone_loop_exit_use(loop, use, orig_exit_idx)) {
2481           return false;


2694 //          RegionA
2695 //             |
2696 //             v
2697 //           exitA
2698 //
2699 bool PhaseIdealLoop::partial_peel( IdealLoopTree *loop, Node_List &old_new ) {
2700 
2701   assert(!loop->_head->is_CountedLoop(), "Non-counted loop only");
2702   if (!loop->_head->is_Loop()) {
2703     return false;  }
2704 
2705   LoopNode *head  = loop->_head->as_Loop();
2706 
2707   if (head->is_partial_peel_loop() || head->partial_peel_has_failed()) {
2708     return false;
2709   }
2710 
2711   // Check for complex exit control
2712   for(uint ii = 0; ii < loop->_body.size(); ii++ ) {
2713     Node *n = loop->_body.at(ii);
2714     Opcodes opc = n->Opcode();
2715     if (n->is_Call()        ||
2716         opc == Opcodes::Op_Catch     ||
2717         opc == Opcodes::Op_CatchProj ||
2718         opc == Opcodes::Op_Jump      ||
2719         opc == Opcodes::Op_JumpProj) {
2720 #if !defined(PRODUCT)
2721       if (TracePartialPeeling) {
2722         tty->print_cr("\nExit control too complex: lp: %d", head->_idx);
2723       }
2724 #endif
2725       return false;
2726     }
2727   }
2728 
2729   int dd = dom_depth(head);
2730 
2731   // Step 1: find cut point
2732 
2733   // Walk up dominators to loop head looking for first loop exit
2734   // which is executed on every path thru loop.
2735   IfNode *peel_if = NULL;
2736   IfNode *peel_if_cmpu = NULL;
2737 
2738   Node *iff = loop->tail();
2739   while( iff != head ) {
2740     if( iff->is_If() ) {
2741       Node *ctrl = get_ctrl(iff->in(1));
2742       if (ctrl->is_top()) return false; // Dead test on live IF.
2743       // If loop-varying exit-test, check for induction variable
2744       if( loop->is_member(get_loop(ctrl)) &&
2745           loop->is_loop_exit(iff) &&
2746           is_possible_iv_test(iff)) {
2747         Node* cmp = iff->in(1)->in(1);
2748         if (cmp->Opcode() == Opcodes::Op_CmpI) {
2749           peel_if = iff->as_If();
2750         } else {
2751           assert(cmp->Opcode() == Opcodes::Op_CmpU, "must be CmpI or CmpU");
2752           peel_if_cmpu = iff->as_If();
2753         }
2754       }
2755     }
2756     iff = idom(iff);
2757   }
2758   // Prefer signed compare over unsigned compare.
2759   IfNode* new_peel_if = NULL;
2760   if (peel_if == NULL) {
2761     if (!PartialPeelAtUnsignedTests || peel_if_cmpu == NULL) {
2762       return false;   // No peel point found
2763     }
2764     new_peel_if = insert_cmpi_loop_exit(peel_if_cmpu, loop);
2765     if (new_peel_if == NULL) {
2766       return false;   // No peel point found
2767     }
2768     peel_if = new_peel_if;
2769   }
2770   Node* last_peel        = stay_in_loop(peel_if, loop);
2771   Node* first_not_peeled = stay_in_loop(last_peel, loop);


< prev index next >