< prev index next >

src/hotspot/share/opto/loopopts.cpp

Print this page




  27 #include "gc/shared/c2/barrierSetC2.hpp"
  28 #include "memory/allocation.inline.hpp"
  29 #include "memory/resourceArea.hpp"
  30 #include "opto/addnode.hpp"
  31 #include "opto/callnode.hpp"
  32 #include "opto/castnode.hpp"
  33 #include "opto/connode.hpp"
  34 #include "opto/castnode.hpp"
  35 #include "opto/divnode.hpp"
  36 #include "opto/loopnode.hpp"
  37 #include "opto/matcher.hpp"
  38 #include "opto/mulnode.hpp"
  39 #include "opto/movenode.hpp"
  40 #include "opto/opaquenode.hpp"
  41 #include "opto/rootnode.hpp"
  42 #include "opto/subnode.hpp"
  43 #include "utilities/macros.hpp"
  44 #if INCLUDE_ZGC
  45 #include "gc/z/c2/zBarrierSetC2.hpp"
  46 #endif



  47 
  48 //=============================================================================
  49 //------------------------------split_thru_phi---------------------------------
  50 // Split Node 'n' through merge point if there is enough win.
  51 Node *PhaseIdealLoop::split_thru_phi( Node *n, Node *region, int policy ) {
  52   if (n->Opcode() == Op_ConvI2L && n->bottom_type() != TypeLong::LONG) {
  53     // ConvI2L may have type information on it which is unsafe to push up
  54     // so disable this for now
  55     return NULL;
  56   }
  57 
  58   // Splitting range check CastIIs through a loop induction Phi can
  59   // cause new Phis to be created that are left unrelated to the loop
  60   // induction Phi and prevent optimizations (vectorization)
  61   if (n->Opcode() == Op_CastII && n->as_CastII()->has_range_check() &&
  62       region->is_CountedLoop() && n->in(1) == region->as_CountedLoop()->phi()) {
  63     return NULL;
  64   }
  65 
  66   int wins = 0;


 112       // irreducible loop may not be indicated by an affirmative is_Loop());
 113       // therefore, the only top we can split thru a phi is on a backedge of
 114       // a loop.
 115       singleton &= region->is_Loop() && (i != LoopNode::EntryControl);
 116     }
 117 
 118     if (singleton) {
 119       wins++;
 120       x = ((PhaseGVN&)_igvn).makecon(t);
 121     } else {
 122       // We now call Identity to try to simplify the cloned node.
 123       // Note that some Identity methods call phase->type(this).
 124       // Make sure that the type array is big enough for
 125       // our new node, even though we may throw the node away.
 126       // (Note: This tweaking with igvn only works because x is a new node.)
 127       _igvn.set_type(x, t);
 128       // If x is a TypeNode, capture any more-precise type permanently into Node
 129       // otherwise it will be not updated during igvn->transform since
 130       // igvn->type(x) is set to x->Value() already.
 131       x->raise_bottom_type(t);
 132       Node *y = x->Identity(&_igvn);
 133       if (y != x) {
 134         wins++;
 135         x = y;
 136       } else {
 137         y = _igvn.hash_find(x);
 138         if (y) {
 139           wins++;
 140           x = y;
 141         } else {
 142           // Else x is a new node we are keeping
 143           // We do not need register_new_node_with_optimizer
 144           // because set_type has already been called.
 145           _igvn._worklist.push(x);






 146         }


 147       }
 148     }
 149     if (x != the_clone && the_clone != NULL)
 150       _igvn.remove_dead_node(the_clone);
 151     phi->set_req( i, x );
 152   }
 153   // Too few wins?
 154   if (wins <= policy) {
 155     _igvn.remove_dead_node(phi);
 156     return NULL;
 157   }
 158 
 159   // Record Phi
 160   register_new_node( phi, region );
 161 
 162   for (uint i2 = 1; i2 < phi->req(); i2++) {
 163     Node *x = phi->in(i2);
 164     // If we commoned up the cloned 'x' with another existing Node,
 165     // the existing Node picks up a new use.  We need to make the
 166     // existing Node occur higher up so it dominates its uses.


 195         (old_loop == NULL || !new_loop->is_member(old_loop))) {
 196       // Take early control, later control will be recalculated
 197       // during next iteration of loop optimizations.
 198       new_ctrl = get_early_ctrl(x);
 199       new_loop = get_loop(new_ctrl);
 200     }
 201     // Set new location
 202     set_ctrl(x, new_ctrl);
 203     // If changing loop bodies, see if we need to collect into new body
 204     if (old_loop != new_loop) {
 205       if (old_loop && !old_loop->_child)
 206         old_loop->_body.yank(x);
 207       if (!new_loop->_child)
 208         new_loop->_body.push(x);  // Collect body info
 209     }
 210   }
 211 
 212   return phi;
 213 }
 214 








































 215 //------------------------------dominated_by------------------------------------
 216 // Replace the dominated test with an obvious true or false.  Place it on the
 217 // IGVN worklist for later cleanup.  Move control-dependent data Nodes on the
 218 // live path up to the dominating control.
 219 void PhaseIdealLoop::dominated_by( Node *prevdom, Node *iff, bool flip, bool exclude_loop_predicate ) {
 220   if (VerifyLoopOptimizations && PrintOpto) { tty->print_cr("dominating test"); }
 221 
 222   // prevdom is the dominating projection of the dominating test.
 223   assert( iff->is_If(), "" );
 224   assert(iff->Opcode() == Op_If || iff->Opcode() == Op_CountedLoopEnd || iff->Opcode() == Op_RangeCheck, "Check this code when new subtype is added");
 225   int pop = prevdom->Opcode();
 226   assert( pop == Op_IfFalse || pop == Op_IfTrue, "" );
 227   if (flip) {
 228     if (pop == Op_IfTrue)
 229       pop = Op_IfFalse;
 230     else
 231       pop = Op_IfTrue;
 232   }
 233   // 'con' is set to true or false to kill the dominated test.
 234   Node *con = _igvn.makecon(pop == Op_IfTrue ? TypeInt::ONE : TypeInt::ZERO);


 901   }
 902   if( n->is_CFG() || n->is_LoadStore() )
 903     return n;
 904   if( n_op == Op_Opaque1 ||     // Opaque nodes cannot be mod'd
 905       n_op == Op_Opaque2 ) {
 906     if( !C->major_progress() )   // If chance of no more loop opts...
 907       _igvn._worklist.push(n);  // maybe we'll remove them
 908     return n;
 909   }
 910 
 911   if( n->is_Con() ) return n;   // No cloning for Con nodes
 912 
 913   Node *n_ctrl = get_ctrl(n);
 914   if( !n_ctrl ) return n;       // Dead node
 915 
 916   Node* res = try_move_store_before_loop(n, n_ctrl);
 917   if (res != NULL) {
 918     return n;
 919   }
 920 






 921   // Attempt to remix address expressions for loop invariants
 922   Node *m = remix_address_expressions( n );
 923   if( m ) return m;
 924 
 925   if (n->is_ConstraintCast()) {
 926     Node* dom_cast = n->as_ConstraintCast()->dominating_cast(&_igvn, this);
 927     // ConstraintCastNode::dominating_cast() uses node control input to determine domination.
 928     // Node control inputs don't necessarily agree with loop control info (due to
 929     // transformations happened in between), thus additional dominance check is needed
 930     // to keep loop info valid.
 931     if (dom_cast != NULL && is_dominator(get_ctrl(dom_cast), get_ctrl(n))) {
 932       _igvn.replace_node(n, dom_cast);
 933       return dom_cast;
 934     }
 935   }
 936 
 937   // Determine if the Node has inputs from some local Phi.
 938   // Returns the block to clone thru.
 939   Node *n_blk = has_local_phi_input( n );
 940   if( !n_blk ) return n;


 958   int policy = n_blk->req() >> 2;
 959 
 960   // If the loop is a candidate for range check elimination,
 961   // delay splitting through it's phi until a later loop optimization
 962   if (n_blk->is_CountedLoop()) {
 963     IdealLoopTree *lp = get_loop(n_blk);
 964     if (lp && lp->_rce_candidate) {
 965       return n;
 966     }
 967   }
 968 
 969   // Use same limit as split_if_with_blocks_post
 970   if( C->live_nodes() > 35000 ) return n; // Method too big
 971 
 972   // Split 'n' through the merge point if it is profitable
 973   Node *phi = split_thru_phi( n, n_blk, policy );
 974   if (!phi) return n;
 975 
 976   // Found a Phi to split thru!
 977   // Replace 'n' with the new phi

 978   _igvn.replace_node( n, phi );
 979   // Moved a load around the loop, 'en-registering' something.
 980   if (n_blk->is_Loop() && n->is_Load() &&
 981       !phi->in(LoopNode::LoopBackControl)->is_Load())
 982     C->set_major_progress();
 983 





 984   return phi;
 985 }
 986 
 987 static bool merge_point_too_heavy(Compile* C, Node* region) {
 988   // Bail out if the region and its phis have too many users.
 989   int weight = 0;
 990   for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
 991     weight += region->fast_out(i)->outcnt();
 992   }
 993   int nodes_left = C->max_node_limit() - C->live_nodes();
 994   if (weight * 8 > nodes_left) {
 995     if (PrintOpto) {
 996       tty->print_cr("*** Split-if bails out:  %d nodes, region weight %d", C->unique(), weight);
 997     }
 998     return true;
 999   } else {
1000     return false;
1001   }
1002 }
1003 























1004 static bool merge_point_safe(Node* region) {
1005   // 4799512: Stop split_if_with_blocks from splitting a block with a ConvI2LNode
1006   // having a PhiNode input. This sidesteps the dangerous case where the split
1007   // ConvI2LNode may become TOP if the input Value() does not
1008   // overlap the ConvI2L range, leaving a node which may not dominate its
1009   // uses.
1010   // A better fix for this problem can be found in the BugTraq entry, but
1011   // expediency for Mantis demands this hack.
1012   // 6855164: If the merge point has a FastLockNode with a PhiNode input, we stop
1013   // split_if_with_blocks from splitting a block because we could not move around
1014   // the FastLockNode.
1015   for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
1016     Node* n = region->fast_out(i);
1017     if (n->is_Phi()) {
1018       for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
1019         Node* m = n->fast_out(j);
1020         if (m->is_FastLock())
1021           return false;
1022 #ifdef _LP64
1023         if (m->Opcode() == Op_ConvI2L)
1024           return false;
1025         if (m->is_CastII() && m->isa_CastII()->has_range_check()) {
1026           return false;
1027         }
1028 #endif
1029       }
1030     }
1031   }
1032   return true;
1033 }
1034 
1035 
1036 //------------------------------place_near_use---------------------------------
1037 // Place some computation next to use but not inside inner loops.
1038 // For inner loop uses move it to the preheader area.
1039 Node *PhaseIdealLoop::place_near_use(Node *useblock) const {
1040   IdealLoopTree *u_loop = get_loop( useblock );
1041   if (u_loop->_irreducible) {
1042     return useblock;
1043   }
1044   if (u_loop->_child) {
1045     if (useblock == u_loop->_head && u_loop->_head->is_OuterStripMinedLoop()) {
1046       return u_loop->_head->in(LoopNode::EntryControl);
1047     }
1048     return useblock;
1049   }
1050   return u_loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl);
1051 }
1052 
1053 
1054 bool PhaseIdealLoop::identical_backtoback_ifs(Node *n) {
1055   if (!n->is_If() || n->is_CountedLoopEnd()) {
1056     return false;
1057   }
1058   if (!n->in(0)->is_Region()) {


1059     return false;
1060   }
1061   Node* region = n->in(0);
1062   Node* dom = idom(region);
1063   if (!dom->is_If() || dom->in(1) != n->in(1)) {
1064     return false;
1065   }














1066   IfNode* dom_if = dom->as_If();
1067   Node* proj_true = dom_if->proj_out(1);
1068   Node* proj_false = dom_if->proj_out(0);
1069 
1070   for (uint i = 1; i < region->req(); i++) {
1071     if (is_dominator(proj_true, region->in(i))) {
1072       continue;
1073     }
1074     if (is_dominator(proj_false, region->in(i))) {
1075       continue;
1076     }
1077     return false;
1078   }
1079 
1080   return true;
1081 }
1082 
1083 bool PhaseIdealLoop::can_split_if(Node *n_ctrl) {

1084   if (C->live_nodes() > 35000) {
1085     return false; // Method too big
1086   }
1087 
1088   // Do not do 'split-if' if irreducible loops are present.
1089   if (_has_irreducible_loops) {
1090     return false;
1091   }
1092 
1093   if (merge_point_too_heavy(C, n_ctrl)) {
1094     return false;
1095   }
1096 
1097   // Do not do 'split-if' if some paths are dead.  First do dead code
1098   // elimination and then see if its still profitable.
1099   for (uint i = 1; i < n_ctrl->req(); i++) {
1100     if (n_ctrl->in(i) == C->top()) {
1101       return false;
1102     }
1103   }


1318               while( u->in(k) != n ) k++;
1319               u->set_req( k, x );
1320               // x goes next to Phi input path
1321               x_ctrl = u->in(0)->in(k);
1322               --j;
1323             } else {              // Normal use
1324               // Replace all uses
1325               for( uint k = 0; k < u->req(); k++ ) {
1326                 if( u->in(k) == n ) {
1327                   u->set_req( k, x );
1328                   --j;
1329                 }
1330               }
1331               x_ctrl = get_ctrl(u);
1332             }
1333 
1334             // Find control for 'x' next to use but not inside inner loops.
1335             // For inner loop uses get the preheader area.
1336             x_ctrl = place_near_use(x_ctrl);
1337 
1338             if (n->is_Load()) {
1339               // For loads, add a control edge to a CFG node outside of the loop
1340               // to force them to not combine and return back inside the loop
1341               // during GVN optimization (4641526).
1342               //
1343               // Because we are setting the actual control input, factor in
1344               // the result from get_late_ctrl() so we respect any
1345               // anti-dependences. (6233005).
1346               x_ctrl = dom_lca(late_load_ctrl, x_ctrl);


1347 
1348               // Don't allow the control input to be a CFG splitting node.
1349               // Such nodes should only have ProjNodes as outs, e.g. IfNode
1350               // should only have IfTrueNode and IfFalseNode (4985384).
1351               x_ctrl = find_non_split_ctrl(x_ctrl);
1352               assert(dom_depth(n_ctrl) <= dom_depth(x_ctrl), "n is later than its clone");
1353 
1354               x->set_req(0, x_ctrl);
1355             }
1356             register_new_node(x, x_ctrl);
1357 
1358             // Some institutional knowledge is needed here: 'x' is
1359             // yanked because if the optimizer runs GVN on it all the
1360             // cloned x's will common up and undo this optimization and
1361             // be forced back in the loop.  This is annoying because it
1362             // makes +VerifyOpto report false-positives on progress.  I
1363             // tried setting control edges on the x's to force them to
1364             // not combine, but the matching gets worried when it tries
1365             // to fold a StoreP and an AddP together (as part of an
1366             // address expression) and the AddP and StoreP have
1367             // different controls.
1368             if (!x->is_Load() && !x->is_DecodeNarrowPtr()) _igvn._worklist.yank(x);
1369           }
1370           _igvn.remove_dead_node(n);
1371         }
1372       }
1373     }
1374   }
1375 
1376   try_move_store_after_loop(n);
1377 
1378   // Check for Opaque2's who's loop has disappeared - who's input is in the
1379   // same loop nest as their output.  Remove 'em, they are no longer useful.
1380   if( n_op == Op_Opaque2 &&
1381       n->in(1) != NULL &&
1382       get_loop(get_ctrl(n)) == get_loop(get_ctrl(n->in(1))) ) {
1383     _igvn.replace_node( n, n->in(1) );
1384   }
1385 
1386 #if INCLUDE_ZGC
1387   if (UseZGC) {
1388     ZBarrierSetC2::loop_optimize_gc_barrier(this, n, last_round);


1685           // That node is outside the inner loop, leave it outside the
1686           // outer loop as well to not confuse verification code.
1687           assert(!loop->_parent->is_member(use_loop), "should be out of the outer loop");
1688           _igvn.replace_input_of(use, 0, head->outer_loop_exit());
1689           continue;
1690         }
1691       }
1692 
1693       while(!outer_loop->is_member(get_loop(cfg))) {
1694         prev = cfg;
1695         cfg = cfg->_idx >= new_counter ? cfg->in(2) : idom(cfg);
1696       }
1697       // If the use occurs after merging several exits from the loop, then
1698       // old value must have dominated all those exits.  Since the same old
1699       // value was used on all those exits we did not need a Phi at this
1700       // merge point.  NOW we do need a Phi here.  Each loop exit value
1701       // is now merged with the peeled body exit; each exit gets its own
1702       // private Phi and those Phis need to be merged here.
1703       Node *phi;
1704       if( prev->is_Region() ) {
1705         if( idx == 0 ) {      // Updating control edge?
1706           phi = prev;         // Just use existing control
1707         } else {              // Else need a new Phi
1708           phi = PhiNode::make( prev, old );
1709           // Now recursively fix up the new uses of old!
1710           for( uint i = 1; i < prev->req(); i++ ) {

1711             worklist.push(phi); // Onto worklist once for each 'old' input
1712           }
1713         }
1714       } else {
1715         // Get new RegionNode merging old and new loop exits
1716         prev = old_new[prev->_idx];
1717         assert( prev, "just made this in step 7" );
1718         if( idx == 0) {      // Updating control edge?
1719           phi = prev;         // Just use existing control
1720         } else {              // Else need a new Phi
1721           // Make a new Phi merging data values properly
1722           phi = PhiNode::make( prev, old );
1723           phi->set_req( 1, nnn );
1724         }
1725       }
1726       // If inserting a new Phi, check for prior hits
1727       if( idx != 0 ) {
1728         Node *hit = _igvn.hash_find_insert(phi);
1729         if( hit == NULL ) {
1730           _igvn.register_new_node_with_optimizer(phi); // Register new phi
1731         } else {                                      // or
1732           // Remove the new phi from the graph and use the hit
1733           _igvn.remove_dead_node(phi);
1734           phi = hit;                                  // Use existing phi
1735         }
1736         set_ctrl(phi, prev);
1737       }
1738       // Make 'use' use the Phi instead of the old loop body exit value
1739       _igvn.replace_input_of(use, idx, phi);
1740       if( use->_idx >= new_counter ) { // If updating new phis
1741         // Not needed for correctness, but prevents a weak assert
1742         // in AddPNode from tripping (when we end up with different
1743         // base & derived Phis that will become the same after
1744         // IGVN does CSE).
1745         Node *hit = _igvn.hash_find_insert(use);
1746         if( hit )             // Go ahead and re-hash for hits.
1747           _igvn.replace_node( use, hit );


3115   // Evacuate nodes in peel region into the not_peeled region if possible
3116   uint new_phi_cnt = 0;
3117   uint cloned_for_outside_use = 0;
3118   for (i = 0; i < peel_list.size();) {
3119     Node* n = peel_list.at(i);
3120 #if !defined(PRODUCT)
3121   if (TracePartialPeeling) n->dump();
3122 #endif
3123     bool incr = true;
3124     if ( !n->is_CFG() ) {
3125 
3126       if ( has_use_in_set(n, not_peel) ) {
3127 
3128         // If not used internal to the peeled region,
3129         // move "n" from peeled to not_peeled region.
3130 
3131         if ( !has_use_internal_to_set(n, peel, loop) ) {
3132 
3133           // if not pinned and not a load (which maybe anti-dependent on a store)
3134           // and not a CMove (Matcher expects only bool->cmove).
3135           if ( n->in(0) == NULL && !n->is_Load() && !n->is_CMove() ) {
3136             cloned_for_outside_use += clone_for_use_outside_loop( loop, n, worklist );
3137             sink_list.push(n);
3138             peel     >>= n->_idx; // delete n from peel set.
3139             not_peel <<= n->_idx; // add n to not_peel set.
3140             peel_list.remove(i);
3141             incr = false;
3142 #if !defined(PRODUCT)
3143             if (TracePartialPeeling) {
3144               tty->print_cr("sink to not_peeled region: %d newbb: %d",
3145                             n->_idx, get_ctrl(n)->_idx);
3146             }
3147 #endif
3148           }
3149         } else {
3150           // Otherwise check for special def-use cases that span
3151           // the peel/not_peel boundary such as bool->if
3152           clone_for_special_use_inside_loop( loop, n, not_peel, sink_list, worklist );
3153           new_phi_cnt++;
3154         }
3155       }




  27 #include "gc/shared/c2/barrierSetC2.hpp"
  28 #include "memory/allocation.inline.hpp"
  29 #include "memory/resourceArea.hpp"
  30 #include "opto/addnode.hpp"
  31 #include "opto/callnode.hpp"
  32 #include "opto/castnode.hpp"
  33 #include "opto/connode.hpp"
  34 #include "opto/castnode.hpp"
  35 #include "opto/divnode.hpp"
  36 #include "opto/loopnode.hpp"
  37 #include "opto/matcher.hpp"
  38 #include "opto/mulnode.hpp"
  39 #include "opto/movenode.hpp"
  40 #include "opto/opaquenode.hpp"
  41 #include "opto/rootnode.hpp"
  42 #include "opto/subnode.hpp"
  43 #include "utilities/macros.hpp"
  44 #if INCLUDE_ZGC
  45 #include "gc/z/c2/zBarrierSetC2.hpp"
  46 #endif
  47 #if INCLUDE_SHENANDOAHGC
  48 #include "gc/shenandoah/c2/shenandoahBarrierSetC2.hpp"
  49 #endif
  50 
  51 //=============================================================================
  52 //------------------------------split_thru_phi---------------------------------
  53 // Split Node 'n' through merge point if there is enough win.
  54 Node *PhaseIdealLoop::split_thru_phi( Node *n, Node *region, int policy ) {
  55   if (n->Opcode() == Op_ConvI2L && n->bottom_type() != TypeLong::LONG) {
  56     // ConvI2L may have type information on it which is unsafe to push up
  57     // so disable this for now
  58     return NULL;
  59   }
  60 
  61   // Splitting range check CastIIs through a loop induction Phi can
  62   // cause new Phis to be created that are left unrelated to the loop
  63   // induction Phi and prevent optimizations (vectorization)
  64   if (n->Opcode() == Op_CastII && n->as_CastII()->has_range_check() &&
  65       region->is_CountedLoop() && n->in(1) == region->as_CountedLoop()->phi()) {
  66     return NULL;
  67   }
  68 
  69   int wins = 0;


 115       // irreducible loop may not be indicated by an affirmative is_Loop());
 116       // therefore, the only top we can split thru a phi is on a backedge of
 117       // a loop.
 118       singleton &= region->is_Loop() && (i != LoopNode::EntryControl);
 119     }
 120 
 121     if (singleton) {
 122       wins++;
 123       x = ((PhaseGVN&)_igvn).makecon(t);
 124     } else {
 125       // We now call Identity to try to simplify the cloned node.
 126       // Note that some Identity methods call phase->type(this).
 127       // Make sure that the type array is big enough for
 128       // our new node, even though we may throw the node away.
 129       // (Note: This tweaking with igvn only works because x is a new node.)
 130       _igvn.set_type(x, t);
 131       // If x is a TypeNode, capture any more-precise type permanently into Node
 132       // otherwise it will be not updated during igvn->transform since
 133       // igvn->type(x) is set to x->Value() already.
 134       x->raise_bottom_type(t);
 135       if (x->Opcode() != Op_ShenandoahWriteBarrier) {
 136         Node *y = x->Identity(&_igvn);
 137         if (y != x) {




 138           wins++;
 139           x = y;
 140         } else {
 141           y = _igvn.hash_find(x);
 142           if (y) {
 143             wins++;
 144             x = y;
 145           } else {
 146             // Else x is a new node we are keeping
 147             // We do not need register_new_node_with_optimizer
 148             // because set_type has already been called.
 149             _igvn._worklist.push(x);
 150           }
 151         }
 152       } else {
 153         _igvn._worklist.push(x);
 154       }
 155     }
 156     if (x != the_clone && the_clone != NULL)
 157       _igvn.remove_dead_node(the_clone);
 158     phi->set_req( i, x );
 159   }
 160   // Too few wins?
 161   if (wins <= policy) {
 162     _igvn.remove_dead_node(phi);
 163     return NULL;
 164   }
 165 
 166   // Record Phi
 167   register_new_node( phi, region );
 168 
 169   for (uint i2 = 1; i2 < phi->req(); i2++) {
 170     Node *x = phi->in(i2);
 171     // If we commoned up the cloned 'x' with another existing Node,
 172     // the existing Node picks up a new use.  We need to make the
 173     // existing Node occur higher up so it dominates its uses.


 202         (old_loop == NULL || !new_loop->is_member(old_loop))) {
 203       // Take early control, later control will be recalculated
 204       // during next iteration of loop optimizations.
 205       new_ctrl = get_early_ctrl(x);
 206       new_loop = get_loop(new_ctrl);
 207     }
 208     // Set new location
 209     set_ctrl(x, new_ctrl);
 210     // If changing loop bodies, see if we need to collect into new body
 211     if (old_loop != new_loop) {
 212       if (old_loop && !old_loop->_child)
 213         old_loop->_body.yank(x);
 214       if (!new_loop->_child)
 215         new_loop->_body.push(x);  // Collect body info
 216     }
 217   }
 218 
 219   return phi;
 220 }
 221 
 222 /**
 223  * When splitting a Shenandoah write barrier through a phi, we
 224  * can not replace the write-barrier input of the ShenandoahWBMemProj
 225  * with the phi. We must also split the ShenandoahWBMemProj through the
 226  * phi and generate a new memory phi for it.
 227  */
 228 void PhaseIdealLoop::split_mem_thru_phi(Node* n, Node* r, Node* phi) {
 229 #if INCLUDE_SHENANDOAHGC
 230   if (n->Opcode() == Op_ShenandoahWriteBarrier) {
 231     if (n->has_out_with(Op_ShenandoahWBMemProj)) {
 232       Node* old_mem_phi = n->in(ShenandoahBarrierNode::Memory);
 233       assert(r->is_Region(), "need region to control phi");
 234       assert(phi->is_Phi(), "expect phi");
 235       Node* memphi = PhiNode::make(r, old_mem_phi, Type::MEMORY, C->alias_type(n->adr_type())->adr_type());
 236       for (uint i = 1; i < r->req(); i++) {
 237         Node* wb = phi->in(i);
 238         if (wb->Opcode() == Op_ShenandoahWriteBarrier) {
 239           // assert(! wb->has_out_with(Op_ShenandoahWBMemProj), "new clone does not have mem proj");
 240           Node* new_proj = new ShenandoahWBMemProjNode(wb);
 241           register_new_node(new_proj, r->in(i));
 242           memphi->set_req(i, new_proj);
 243         } else {
 244           if (old_mem_phi->is_Phi() && old_mem_phi->in(0) == r) {
 245             memphi->set_req(i, old_mem_phi->in(i));
 246           }
 247         }
 248       }
 249       register_new_node(memphi, r);
 250       Node* old_mem_out = n->find_out_with(Op_ShenandoahWBMemProj);
 251       while (old_mem_out != NULL) {
 252         assert(old_mem_out != NULL, "expect memory projection");
 253         _igvn.replace_node(old_mem_out, memphi);
 254         old_mem_out = n->find_out_with(Op_ShenandoahWBMemProj);
 255       }
 256     }
 257     assert(! n->has_out_with(Op_ShenandoahWBMemProj), "no more memory outs");
 258   }
 259 #endif
 260 }
 261 
 262 //------------------------------dominated_by------------------------------------
 263 // Replace the dominated test with an obvious true or false.  Place it on the
 264 // IGVN worklist for later cleanup.  Move control-dependent data Nodes on the
 265 // live path up to the dominating control.
 266 void PhaseIdealLoop::dominated_by( Node *prevdom, Node *iff, bool flip, bool exclude_loop_predicate ) {
 267   if (VerifyLoopOptimizations && PrintOpto) { tty->print_cr("dominating test"); }
 268 
 269   // prevdom is the dominating projection of the dominating test.
 270   assert( iff->is_If(), "" );
 271   assert(iff->Opcode() == Op_If || iff->Opcode() == Op_CountedLoopEnd || iff->Opcode() == Op_RangeCheck, "Check this code when new subtype is added");
 272   int pop = prevdom->Opcode();
 273   assert( pop == Op_IfFalse || pop == Op_IfTrue, "" );
 274   if (flip) {
 275     if (pop == Op_IfTrue)
 276       pop = Op_IfFalse;
 277     else
 278       pop = Op_IfTrue;
 279   }
 280   // 'con' is set to true or false to kill the dominated test.
 281   Node *con = _igvn.makecon(pop == Op_IfTrue ? TypeInt::ONE : TypeInt::ZERO);


 948   }
 949   if( n->is_CFG() || n->is_LoadStore() )
 950     return n;
 951   if( n_op == Op_Opaque1 ||     // Opaque nodes cannot be mod'd
 952       n_op == Op_Opaque2 ) {
 953     if( !C->major_progress() )   // If chance of no more loop opts...
 954       _igvn._worklist.push(n);  // maybe we'll remove them
 955     return n;
 956   }
 957 
 958   if( n->is_Con() ) return n;   // No cloning for Con nodes
 959 
 960   Node *n_ctrl = get_ctrl(n);
 961   if( !n_ctrl ) return n;       // Dead node
 962 
 963   Node* res = try_move_store_before_loop(n, n_ctrl);
 964   if (res != NULL) {
 965     return n;
 966   }
 967 
 968 #if INCLUDE_SHENANDOAHGC
 969   if (n->Opcode() == Op_ShenandoahReadBarrier) {
 970     ((ShenandoahReadBarrierNode*)n)->try_move(n_ctrl, this);
 971   }
 972 #endif
 973 
 974   // Attempt to remix address expressions for loop invariants
 975   Node *m = remix_address_expressions( n );
 976   if( m ) return m;
 977 
 978   if (n->is_ConstraintCast()) {
 979     Node* dom_cast = n->as_ConstraintCast()->dominating_cast(&_igvn, this);
 980     // ConstraintCastNode::dominating_cast() uses node control input to determine domination.
 981     // Node control inputs don't necessarily agree with loop control info (due to
 982     // transformations happened in between), thus additional dominance check is needed
 983     // to keep loop info valid.
 984     if (dom_cast != NULL && is_dominator(get_ctrl(dom_cast), get_ctrl(n))) {
 985       _igvn.replace_node(n, dom_cast);
 986       return dom_cast;
 987     }
 988   }
 989 
 990   // Determine if the Node has inputs from some local Phi.
 991   // Returns the block to clone thru.
 992   Node *n_blk = has_local_phi_input( n );
 993   if( !n_blk ) return n;


1011   int policy = n_blk->req() >> 2;
1012 
1013   // If the loop is a candidate for range check elimination,
1014   // delay splitting through it's phi until a later loop optimization
1015   if (n_blk->is_CountedLoop()) {
1016     IdealLoopTree *lp = get_loop(n_blk);
1017     if (lp && lp->_rce_candidate) {
1018       return n;
1019     }
1020   }
1021 
1022   // Use same limit as split_if_with_blocks_post
1023   if( C->live_nodes() > 35000 ) return n; // Method too big
1024 
1025   // Split 'n' through the merge point if it is profitable
1026   Node *phi = split_thru_phi( n, n_blk, policy );
1027   if (!phi) return n;
1028 
1029   // Found a Phi to split thru!
1030   // Replace 'n' with the new phi
1031   split_mem_thru_phi(n, n_blk, phi);
1032   _igvn.replace_node( n, phi );
1033   // Moved a load around the loop, 'en-registering' something.
1034   if (n_blk->is_Loop() && n->is_Load() &&
1035       !phi->in(LoopNode::LoopBackControl)->is_Load())
1036     C->set_major_progress();
1037 
1038   // Moved a barrier around the loop, 'en-registering' something.
1039   if (n_blk->is_Loop() && n->is_ShenandoahBarrier() &&
1040       !phi->in(LoopNode::LoopBackControl)->is_ShenandoahBarrier())
1041     C->set_major_progress();
1042 
1043   return phi;
1044 }
1045 
1046 static bool merge_point_too_heavy(Compile* C, Node* region) {
1047   // Bail out if the region and its phis have too many users.
1048   int weight = 0;
1049   for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
1050     weight += region->fast_out(i)->outcnt();
1051   }
1052   int nodes_left = C->max_node_limit() - C->live_nodes();
1053   if (weight * 8 > nodes_left) {
1054     if (PrintOpto) {
1055       tty->print_cr("*** Split-if bails out:  %d nodes, region weight %d", C->unique(), weight);
1056     }
1057     return true;
1058   } else {
1059     return false;
1060   }
1061 }
1062 
1063 static bool merge_point_safe_helper(Node* m) {
1064   if (m->is_FastLock()) {
1065     return false;
1066   }
1067 #ifdef _LP64
1068   if (m->Opcode() == Op_ConvI2L) {
1069     return false;
1070   }
1071   if (m->is_CastII() && m->isa_CastII()->has_range_check()) {
1072     return false;
1073   }
1074 #endif
1075   if (m->is_ShenandoahBarrier()) {
1076     for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax; i++) {
1077       Node* n = m->fast_out(i);
1078       if (!merge_point_safe_helper(n)) {
1079         return false;
1080       }
1081     }
1082   }
1083   return true;
1084 }
1085 
1086 static bool merge_point_safe(Node* region) {
1087   // 4799512: Stop split_if_with_blocks from splitting a block with a ConvI2LNode
1088   // having a PhiNode input. This sidesteps the dangerous case where the split
1089   // ConvI2LNode may become TOP if the input Value() does not
1090   // overlap the ConvI2L range, leaving a node which may not dominate its
1091   // uses.
1092   // A better fix for this problem can be found in the BugTraq entry, but
1093   // expediency for Mantis demands this hack.
1094   // 6855164: If the merge point has a FastLockNode with a PhiNode input, we stop
1095   // split_if_with_blocks from splitting a block because we could not move around
1096   // the FastLockNode.
1097   for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
1098     Node* n = region->fast_out(i);
1099     if (n->is_Phi()) {
1100       for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
1101         Node* m = n->fast_out(j);
1102         if (!merge_point_safe_helper(m)) {





1103           return false;
1104         }

1105       }
1106     }
1107   }
1108   return true;
1109 }
1110 
1111 
1112 //------------------------------place_near_use---------------------------------
1113 // Place some computation next to use but not inside inner loops.
1114 // For inner loop uses move it to the preheader area.
1115 Node *PhaseIdealLoop::place_near_use(Node *useblock) const {
1116   IdealLoopTree *u_loop = get_loop( useblock );
1117   if (u_loop->_irreducible) {
1118     return useblock;
1119   }
1120   if (u_loop->_child) {
1121     if (useblock == u_loop->_head && u_loop->_head->is_OuterStripMinedLoop()) {
1122       return u_loop->_head->in(LoopNode::EntryControl);
1123     }
1124     return useblock;
1125   }
1126   return u_loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl);
1127 }
1128 
1129 
1130 bool PhaseIdealLoop::identical_backtoback_ifs(Node *n) {
1131   if (!n->is_If() || n->is_CountedLoopEnd()) {
1132     return false;
1133   }
1134   Node* region = n->in(0);
1135 
1136   if (!region->is_Region()) {
1137     return false;
1138   }

1139   Node* dom = idom(region);
1140   if (!dom->is_If()) {
1141     return false;
1142   }
1143 
1144 #if INCLUDE_SHENANDOAHGC
1145   bool shenandoah_heap_stable = ShenandoahWriteBarrierNode::is_heap_stable_test(n);
1146   if (shenandoah_heap_stable) {
1147     if (!ShenandoahWriteBarrierNode::is_heap_stable_test(dom)) {
1148       return false;
1149     }
1150   } else
1151 #endif
1152   {
1153     if (dom->in(1) != n->in(1)) {
1154       return false;
1155     }
1156   }
1157   IfNode* dom_if = dom->as_If();
1158   Node* proj_true = dom_if->proj_out(1);
1159   Node* proj_false = dom_if->proj_out(0);
1160 
1161   for (uint i = 1; i < region->req(); i++) {
1162     if (is_dominator(proj_true, region->in(i))) {
1163       continue;
1164     }
1165     if (is_dominator(proj_false, region->in(i))) {
1166       continue;
1167     }
1168     return false;
1169   }
1170 
1171   return true;
1172 }
1173 
1174 bool PhaseIdealLoop::can_split_if(Node *n_ctrl) {
1175   assert(n_ctrl->is_Region(), "broken");
1176   if (C->live_nodes() > 35000) {
1177     return false; // Method too big
1178   }
1179 
1180   // Do not do 'split-if' if irreducible loops are present.
1181   if (_has_irreducible_loops) {
1182     return false;
1183   }
1184 
1185   if (merge_point_too_heavy(C, n_ctrl)) {
1186     return false;
1187   }
1188 
1189   // Do not do 'split-if' if some paths are dead.  First do dead code
1190   // elimination and then see if its still profitable.
1191   for (uint i = 1; i < n_ctrl->req(); i++) {
1192     if (n_ctrl->in(i) == C->top()) {
1193       return false;
1194     }
1195   }


1410               while( u->in(k) != n ) k++;
1411               u->set_req( k, x );
1412               // x goes next to Phi input path
1413               x_ctrl = u->in(0)->in(k);
1414               --j;
1415             } else {              // Normal use
1416               // Replace all uses
1417               for( uint k = 0; k < u->req(); k++ ) {
1418                 if( u->in(k) == n ) {
1419                   u->set_req( k, x );
1420                   --j;
1421                 }
1422               }
1423               x_ctrl = get_ctrl(u);
1424             }
1425 
1426             // Find control for 'x' next to use but not inside inner loops.
1427             // For inner loop uses get the preheader area.
1428             x_ctrl = place_near_use(x_ctrl);
1429 
1430             if (n->is_Load() || n->Opcode() == Op_ShenandoahReadBarrier) {
1431               // For loads, add a control edge to a CFG node outside of the loop
1432               // to force them to not combine and return back inside the loop
1433               // during GVN optimization (4641526).
1434               //
1435               // Because we are setting the actual control input, factor in
1436               // the result from get_late_ctrl() so we respect any
1437               // anti-dependences. (6233005).
1438               if (n->is_Load()) {
1439                 x_ctrl = dom_lca(late_load_ctrl, x_ctrl);
1440               }
1441 
1442               // Don't allow the control input to be a CFG splitting node.
1443               // Such nodes should only have ProjNodes as outs, e.g. IfNode
1444               // should only have IfTrueNode and IfFalseNode (4985384).
1445               x_ctrl = find_non_split_ctrl(x_ctrl);
1446               assert(dom_depth(n_ctrl) <= dom_depth(x_ctrl), "n is later than its clone");
1447 
1448               x->set_req(0, x_ctrl);
1449             }
1450             register_new_node(x, x_ctrl);
1451 
1452             // Some institutional knowledge is needed here: 'x' is
1453             // yanked because if the optimizer runs GVN on it all the
1454             // cloned x's will common up and undo this optimization and
1455             // be forced back in the loop.  This is annoying because it
1456             // makes +VerifyOpto report false-positives on progress.  I
1457             // tried setting control edges on the x's to force them to
1458             // not combine, but the matching gets worried when it tries
1459             // to fold a StoreP and an AddP together (as part of an
1460             // address expression) and the AddP and StoreP have
1461             // different controls.
1462             if (!x->is_Load() && !x->is_DecodeNarrowPtr() && !x->is_ShenandoahBarrier() && !x->is_MergeMem()) _igvn._worklist.yank(x);
1463           }
1464           _igvn.remove_dead_node(n);
1465         }
1466       }
1467     }
1468   }
1469 
1470   try_move_store_after_loop(n);
1471 
1472   // Check for Opaque2's who's loop has disappeared - who's input is in the
1473   // same loop nest as their output.  Remove 'em, they are no longer useful.
1474   if( n_op == Op_Opaque2 &&
1475       n->in(1) != NULL &&
1476       get_loop(get_ctrl(n)) == get_loop(get_ctrl(n->in(1))) ) {
1477     _igvn.replace_node( n, n->in(1) );
1478   }
1479 
1480 #if INCLUDE_ZGC
1481   if (UseZGC) {
1482     ZBarrierSetC2::loop_optimize_gc_barrier(this, n, last_round);


1779           // That node is outside the inner loop, leave it outside the
1780           // outer loop as well to not confuse verification code.
1781           assert(!loop->_parent->is_member(use_loop), "should be out of the outer loop");
1782           _igvn.replace_input_of(use, 0, head->outer_loop_exit());
1783           continue;
1784         }
1785       }
1786 
1787       while(!outer_loop->is_member(get_loop(cfg))) {
1788         prev = cfg;
1789         cfg = cfg->_idx >= new_counter ? cfg->in(2) : idom(cfg);
1790       }
1791       // If the use occurs after merging several exits from the loop, then
1792       // old value must have dominated all those exits.  Since the same old
1793       // value was used on all those exits we did not need a Phi at this
1794       // merge point.  NOW we do need a Phi here.  Each loop exit value
1795       // is now merged with the peeled body exit; each exit gets its own
1796       // private Phi and those Phis need to be merged here.
1797       Node *phi;
1798       if( prev->is_Region() ) {
1799         if (idx == 0 && use->Opcode() != Op_ShenandoahWBMemProj) {      // Updating control edge?
1800           phi = prev;         // Just use existing control
1801         } else {              // Else need a new Phi
1802           phi = PhiNode::make( prev, old );
1803           // Now recursively fix up the new uses of old!
1804           uint first = use->Opcode() != Op_ShenandoahWBMemProj ? 1 : 0;
1805           for (uint i = first; i < prev->req(); i++) {
1806             worklist.push(phi); // Onto worklist once for each 'old' input
1807           }
1808         }
1809       } else {
1810         // Get new RegionNode merging old and new loop exits
1811         prev = old_new[prev->_idx];
1812         assert( prev, "just made this in step 7" );
1813         if( idx == 0) {      // Updating control edge?
1814           phi = prev;         // Just use existing control
1815         } else {              // Else need a new Phi
1816           // Make a new Phi merging data values properly
1817           phi = PhiNode::make( prev, old );
1818           phi->set_req( 1, nnn );
1819         }
1820       }
1821       // If inserting a new Phi, check for prior hits
1822       if (idx != 0 && use->Opcode() != Op_ShenandoahWBMemProj) {
1823         Node *hit = _igvn.hash_find_insert(phi);
1824         if( hit == NULL ) {
1825           _igvn.register_new_node_with_optimizer(phi); // Register new phi
1826         } else {                                      // or
1827           // Remove the new phi from the graph and use the hit
1828           _igvn.remove_dead_node(phi);
1829           phi = hit;                                  // Use existing phi
1830         }
1831         set_ctrl(phi, prev);
1832       }
1833       // Make 'use' use the Phi instead of the old loop body exit value
1834       _igvn.replace_input_of(use, idx, phi);
1835       if( use->_idx >= new_counter ) { // If updating new phis
1836         // Not needed for correctness, but prevents a weak assert
1837         // in AddPNode from tripping (when we end up with different
1838         // base & derived Phis that will become the same after
1839         // IGVN does CSE).
1840         Node *hit = _igvn.hash_find_insert(use);
1841         if( hit )             // Go ahead and re-hash for hits.
1842           _igvn.replace_node( use, hit );


3210   // Evacuate nodes in peel region into the not_peeled region if possible
3211   uint new_phi_cnt = 0;
3212   uint cloned_for_outside_use = 0;
3213   for (i = 0; i < peel_list.size();) {
3214     Node* n = peel_list.at(i);
3215 #if !defined(PRODUCT)
3216   if (TracePartialPeeling) n->dump();
3217 #endif
3218     bool incr = true;
3219     if ( !n->is_CFG() ) {
3220 
3221       if ( has_use_in_set(n, not_peel) ) {
3222 
3223         // If not used internal to the peeled region,
3224         // move "n" from peeled to not_peeled region.
3225 
3226         if ( !has_use_internal_to_set(n, peel, loop) ) {
3227 
3228           // if not pinned and not a load (which maybe anti-dependent on a store)
3229           // and not a CMove (Matcher expects only bool->cmove).
3230           if (n->in(0) == NULL && !n->is_Load() && !n->is_CMove() && n->Opcode() != Op_ShenandoahWBMemProj) {
3231             cloned_for_outside_use += clone_for_use_outside_loop( loop, n, worklist );
3232             sink_list.push(n);
3233             peel     >>= n->_idx; // delete n from peel set.
3234             not_peel <<= n->_idx; // add n to not_peel set.
3235             peel_list.remove(i);
3236             incr = false;
3237 #if !defined(PRODUCT)
3238             if (TracePartialPeeling) {
3239               tty->print_cr("sink to not_peeled region: %d newbb: %d",
3240                             n->_idx, get_ctrl(n)->_idx);
3241             }
3242 #endif
3243           }
3244         } else {
3245           // Otherwise check for special def-use cases that span
3246           // the peel/not_peel boundary such as bool->if
3247           clone_for_special_use_inside_loop( loop, n, not_peel, sink_list, worklist );
3248           new_phi_cnt++;
3249         }
3250       }


< prev index next >