< prev index next >

src/hotspot/share/opto/loopnode.cpp

Print this page


   1 /*
   2  * Copyright (c) 1998, 2019, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *


 961     assert(inner != NULL && outer != NULL, "missing loop in strip mined nest");
 962     Node* outer_tail = outer->in(LoopNode::LoopBackControl);
 963     Node* outer_le = outer_tail->in(0);
 964     assert(outer_le->Opcode() == Op_OuterStripMinedLoopEnd, "tail of outer loop should be an If");
 965     Node* sfpt = outer_le->in(0);
 966     assert(sfpt->Opcode() == Op_SafePoint, "where's the safepoint?");
 967     Node* inner_out = sfpt->in(0);
 968     if (inner_out->outcnt() != 1) {
 969       ResourceMark rm;
 970       Unique_Node_List wq;
 971 
 972       for (DUIterator_Fast imax, i = inner_out->fast_outs(imax); i < imax; i++) {
 973         Node* u = inner_out->fast_out(i);
 974         if (u == sfpt) {
 975           continue;
 976         }
 977         wq.clear();
 978         wq.push(u);
 979         bool found_sfpt = false;
 980         for (uint next = 0; next < wq.size() && !found_sfpt; next++) {
 981           Node* n = wq.at(next);
 982           for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax && !found_sfpt; i++) {
 983             Node* u = n->fast_out(i);
 984             if (u == sfpt) {
 985               found_sfpt = true;
 986             }
 987             if (!u->is_CFG()) {
 988               wq.push(u);
 989             }
 990           }
 991         }
 992         assert(found_sfpt, "no node in loop that's not input to safepoint");
 993       }
 994     }
 995 
 996     if (UseZGC && !inner_out->in(0)->is_CountedLoopEnd()) {
 997       // In some very special cases there can be a load that has no other uses than the
 998       // counted loop safepoint. Then its loadbarrier will be placed between the inner
 999       // loop exit and the safepoint. This is very rare
1000 
1001       Node* ifnode = inner_out->in(1)->in(0);
1002       // Region->IfTrue->If == Region->Iffalse->If
1003       if (ifnode == inner_out->in(2)->in(0)) {
1004         inner_out = ifnode->in(0);
1005       }
1006     }
1007 
1008     CountedLoopEndNode* cle = inner_out->in(0)->as_CountedLoopEnd();
1009     assert(cle == inner->loopexit_or_null(), "mismatch");
1010     bool has_skeleton = outer_le->in(1)->bottom_type()->singleton() && outer_le->in(1)->bottom_type()->is_int()->get_con() == 0;
1011     if (has_skeleton) {
1012       assert(expect_skeleton == 1 || expect_skeleton == -1, "unexpected skeleton node");
1013       assert(outer->outcnt() == 2, "only phis");
1014     } else {
1015       assert(expect_skeleton == 0 || expect_skeleton == -1, "no skeleton node?");
1016       uint phis = 0;
1017       for (DUIterator_Fast imax, i = inner->fast_outs(imax); i < imax; i++) {
1018         Node* u = inner->fast_out(i);
1019         if (u->is_Phi()) {
1020           phis++;
1021         }
1022       }
1023       for (DUIterator_Fast imax, i = outer->fast_outs(imax); i < imax; i++) {
1024         Node* u = outer->fast_out(i);
1025         assert(u == outer || u == inner || u->is_Phi(), "nothing between inner and outer loop");
1026       }
1027       uint stores = 0;


2435     // Remove safepoints
2436     bool keep_one_sfpt = !(_has_call || _has_sfpt);
2437     remove_safepoints(phase, keep_one_sfpt);
2438 
2439     // Look for induction variables
2440     phase->replace_parallel_iv(this);
2441 
2442   } else if (_parent != NULL && !_irreducible) {
2443     // Not a counted loop. Keep one safepoint.
2444     bool keep_one_sfpt = true;
2445     remove_safepoints(phase, keep_one_sfpt);
2446   }
2447 
2448   // Recursively
2449   assert(loop->_child != this || (loop->_head->as_Loop()->is_OuterStripMinedLoop() && _head->as_CountedLoop()->is_strip_mined()), "what kind of loop was added?");
2450   assert(loop->_child != this || (loop->_child->_child == NULL && loop->_child->_next == NULL), "would miss some loops");
2451   if (loop->_child && loop->_child != this) loop->_child->counted_loop(phase);
2452   if (loop->_next)  loop->_next ->counted_loop(phase);
2453 }
2454 
2455 
2456 // The Estimated Loop Clone Size:
2457 //   CloneFactor * (~112% * BodySize + BC) + CC + FanOutTerm,
2458 // where  BC and  CC are  totally ad-hoc/magic  "body" and "clone" constants,
2459 // respectively, used to ensure that the node usage estimates made are on the
2460 // safe side, for the most part. The FanOutTerm is an attempt to estimate the
2461 // possible additional/excessive nodes generated due to data and control flow
2462 // merging, for edges reaching outside the loop.
2463 uint IdealLoopTree::est_loop_clone_sz(uint factor) const {
2464 
2465   precond(0 < factor && factor < 16);
2466 
2467   uint const bc = 13;
2468   uint const cc = 17;
2469   uint const sz = _body.size() + (_body.size() + 7) / 8;
2470   uint estimate = factor * (sz + bc) + cc;
2471 
2472   assert((estimate - cc) / factor == sz + bc, "overflow");
2473 
2474   uint ctrl_edge_out_cnt = 0;
2475   uint data_edge_out_cnt = 0;
2476 
2477   for (uint i = 0; i < _body.size(); i++) {
2478     Node* node = _body.at(i);
2479     uint outcnt = node->outcnt();
2480 
2481     for (uint k = 0; k < outcnt; k++) {
2482       Node* out = node->raw_out(k);
2483 
2484       if (out->is_CFG()) {
2485         if (!is_member(_phase->get_loop(out))) {
2486           ctrl_edge_out_cnt++;
2487         }
2488       } else {
2489         Node* ctrl = _phase->get_ctrl(out);
2490         assert(ctrl->is_CFG(), "must be");
2491         if (!is_member(_phase->get_loop(ctrl))) {
2492           data_edge_out_cnt++;
2493         }
2494       }
2495     }
2496   }
2497   // Add data (x1.5) and control (x1.0) count to estimate iff both are > 0.
2498   if (ctrl_edge_out_cnt > 0 && data_edge_out_cnt > 0) {
2499     estimate += ctrl_edge_out_cnt + data_edge_out_cnt + data_edge_out_cnt / 2;
2500   }
2501 
2502   return estimate;
2503 }
2504 
2505 #ifndef PRODUCT
2506 //------------------------------dump_head--------------------------------------
2507 // Dump 1 liner for loop header info
2508 void IdealLoopTree::dump_head() const {
2509   for (uint i = 0; i < _nest; i++) {
2510     tty->print("  ");
2511   }
2512   tty->print("Loop: N%d/N%d ",_head->_idx,_tail->_idx);
2513   if (_irreducible) tty->print(" IRREDUCIBLE");
2514   Node* entry = _head->is_Loop() ? _head->as_Loop()->skip_strip_mined(-1)->in(LoopNode::EntryControl) : _head->in(LoopNode::EntryControl);
2515   Node* predicate = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
2516   if (predicate != NULL ) {
2517     tty->print(" limit_check");
2518     entry = PhaseIdealLoop::skip_loop_predicates(entry);
2519   }
2520   if (UseLoopPredicate) {
2521     entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
2522     if (entry != NULL) {
2523       tty->print(" predicated");
2524       entry = PhaseIdealLoop::skip_loop_predicates(entry);
2525     }
2526   }
2527   if (UseProfiledLoopPredicate) {
2528     entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate);
2529     if (entry != NULL) {
2530       tty->print(" profile_predicated");
2531     }


2560   if (_has_call) tty->print(" has_call");
2561   if (_has_sfpt) tty->print(" has_sfpt");
2562   if (_rce_candidate) tty->print(" rce");
2563   if (_safepts != NULL && _safepts->size() > 0) {
2564     tty->print(" sfpts={"); _safepts->dump_simple(); tty->print(" }");
2565   }
2566   if (_required_safept != NULL && _required_safept->size() > 0) {
2567     tty->print(" req={"); _required_safept->dump_simple(); tty->print(" }");
2568   }
2569   if (Verbose) {
2570     tty->print(" body={"); _body.dump_simple(); tty->print(" }");
2571   }
2572   if (_head->is_Loop() && _head->as_Loop()->is_strip_mined()) {
2573     tty->print(" strip_mined");
2574   }
2575   tty->cr();
2576 }
2577 
2578 //------------------------------dump-------------------------------------------
2579 // Dump loops by loop tree
2580 void IdealLoopTree::dump() const {
2581   dump_head();
2582   if (_child) _child->dump();
2583   if (_next)  _next ->dump();
2584 }
2585 
2586 #endif
2587 
2588 static void log_loop_tree(IdealLoopTree* root, IdealLoopTree* loop, CompileLog* log) {
2589   if (loop == root) {
2590     if (loop->_child != NULL) {
2591       log->begin_head("loop_tree");
2592       log->end_head();
2593       if( loop->_child ) log_loop_tree(root, loop->_child, log);
2594       log->tail("loop_tree");
2595       assert(loop->_next == NULL, "what?");
2596     }
2597   } else {
2598     Node* head = loop->_head;
2599     log->begin_head("loop");
2600     log->print(" idx='%d' ", head->_idx);


2757         if (n2->in(0) != c2) {
2758           _igvn.hash_delete(n2);
2759           n2->set_req(0, c2);
2760           _igvn.hash_insert(n2);
2761           _igvn._worklist.push(n2);
2762           progress = true;
2763         }
2764       }
2765     }
2766   }
2767 
2768   return progress;
2769 }
2770 
2771 
2772 //=============================================================================
2773 //----------------------------build_and_optimize-------------------------------
2774 // Create a PhaseLoop.  Build the ideal Loop tree.  Map each Ideal Node to
2775 // its corresponding LoopNode.  If 'optimize' is true, do some loop cleanups.
2776 void PhaseIdealLoop::build_and_optimize(LoopOptsMode mode) {
2777   bool do_split_ifs = (mode == LoopOptsDefault);
2778   bool skip_loop_opts = (mode == LoopOptsNone);
2779 
2780   int old_progress = C->major_progress();
2781   uint orig_worklist_size = _igvn._worklist.size();
2782 
2783   // Reset major-progress flag for the driver's heuristics
2784   C->clear_major_progress();
2785 
2786 #ifndef PRODUCT
2787   // Capture for later assert
2788   uint unique = C->unique();
2789   _loop_invokes++;
2790   _loop_work += unique;
2791 #endif
2792 
2793   // True if the method has at least 1 irreducible loop
2794   _has_irreducible_loops = false;
2795 
2796   _created_loop_node = false;
2797 


2917   worklist.push( C->top() );
2918   visited.set( C->top()->_idx ); // Set C->top() as visited now
2919   build_loop_early( visited, worklist, nstack );
2920 
2921   // Given early legal placement, try finding counted loops.  This placement
2922   // is good enough to discover most loop invariants.
2923   if (!_verify_me && !_verify_only && !strip_mined_loops_expanded) {
2924     _ltree_root->counted_loop( this );
2925   }
2926 
2927   // Find latest loop placement.  Find ideal loop placement.
2928   visited.Clear();
2929   init_dom_lca_tags();
2930   // Need C->root() on worklist when processing outs
2931   worklist.push( C->root() );
2932   NOT_PRODUCT( C->verify_graph_edges(); )
2933   worklist.push( C->top() );
2934   build_loop_late( visited, worklist, nstack );
2935 
2936   if (_verify_only) {
2937     C->restore_major_progress(old_progress);


2938     assert(C->unique() == unique, "verification mode made Nodes? ? ?");
2939     assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
2940     return;
2941   }
2942 
2943   // clear out the dead code after build_loop_late
2944   while (_deadlist.size()) {
2945     _igvn.remove_globally_dead_node(_deadlist.pop());
2946   }
2947 
2948   if (stop_early) {
2949     assert(do_expensive_nodes, "why are we here?");
2950     if (process_expensive_nodes()) {
2951       // If we made some progress when processing expensive nodes then
2952       // the IGVN may modify the graph in a way that will allow us to
2953       // make some more progress: we need to try processing expensive
2954       // nodes again.
2955       C->set_major_progress();
2956     }
2957     _igvn.optimize();
2958     return;
2959   }
2960 
2961   // Some parser-inserted loop predicates could never be used by loop
2962   // predication or they were moved away from loop during some optimizations.
2963   // For example, peeling. Eliminate them before next loop optimizations.
2964   eliminate_useless_predicates();
2965 
2966 #ifndef PRODUCT
2967   C->verify_graph_edges();
2968   if (_verify_me) {             // Nested verify pass?
2969     // Check to see if the verify mode is broken
2970     assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
2971     return;
2972   }
2973   if (VerifyLoopOptimizations) verify();
2974   if (TraceLoopOpts && C->has_loops()) {
2975     _ltree_root->dump();
2976   }
2977 #endif
2978 
2979   if (skip_loop_opts) {
2980     // restore major progress flag
2981     C->restore_major_progress(old_progress);


2982 
2983     // Cleanup any modified bits
2984     _igvn.optimize();
2985 
2986     if (C->log() != NULL) {
2987       log_loop_tree(_ltree_root, _ltree_root, C->log());
2988     }
2989     return;
2990   }
2991 
2992   if (bs->optimize_loops(this, mode, visited, nstack, worklist)) {
2993     _igvn.optimize();
2994     if (C->log() != NULL) {
2995       log_loop_tree(_ltree_root, _ltree_root, C->log());
2996     }
2997     return;
2998   }
2999 
3000   if (ReassociateInvariants) {

3001     // Reassociate invariants and prep for split_thru_phi
3002     for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
3003       IdealLoopTree* lpt = iter.current();
3004       bool is_counted = lpt->is_counted();
3005       if (!is_counted || !lpt->is_innermost()) continue;
3006 
3007       // check for vectorized loops, any reassociation of invariants was already done
3008       if (is_counted && lpt->_head->as_CountedLoop()->is_unroll_only()) {
3009         continue;
3010       } else {
3011         AutoNodeBudget node_budget(this);
3012         lpt->reassociate_invariants(this);
3013       }
3014       // Because RCE opportunities can be masked by split_thru_phi,
3015       // look for RCE candidates and inhibit split_thru_phi
3016       // on just their loop-phi's for this pass of loop opts
3017       if (SplitIfBlocks && do_split_ifs) {
3018         AutoNodeBudget node_budget(this, AutoNodeBudget::NO_BUDGET_CHECK);
3019         if (lpt->policy_range_check(this)) {
3020           lpt->_rce_candidate = 1; // = true
3021         }
3022       }
3023     }
3024   }
3025 
3026   // Check for aggressive application of split-if and other transforms
3027   // that require basic-block info (like cloning through Phi's)
3028   if( SplitIfBlocks && do_split_ifs ) {
3029     visited.Clear();
3030     split_if_with_blocks( visited, nstack);
3031     NOT_PRODUCT( if( VerifyLoopOptimizations ) verify(); );



3032   }
3033 
3034   if (!C->major_progress() && do_expensive_nodes && process_expensive_nodes()) {
3035     C->set_major_progress();
3036   }
3037 
3038   // Perform loop predication before iteration splitting
3039   if (C->has_loops() && !C->major_progress() && (C->predicate_count() > 0)) {
3040     _ltree_root->_child->loop_predication(this);
3041   }
3042 
3043   if (OptimizeFill && UseLoopPredicate && C->has_loops() && !C->major_progress()) {
3044     if (do_intrinsify_fill()) {
3045       C->set_major_progress();
3046     }
3047   }
3048 
3049   // Perform iteration-splitting on inner loops.  Split iterations to avoid
3050   // range checks or one-shot null checks.
3051 


3146 void PhaseIdealLoop::print_statistics() {
3147   tty->print_cr("PhaseIdealLoop=%d, sum _unique=%d", _loop_invokes, _loop_work);
3148 }
3149 
3150 //------------------------------verify-----------------------------------------
3151 // Build a verify-only PhaseIdealLoop, and see that it agrees with me.
3152 static int fail;                // debug only, so its multi-thread dont care
3153 void PhaseIdealLoop::verify() const {
3154   int old_progress = C->major_progress();
3155   ResourceMark rm;
3156   PhaseIdealLoop loop_verify( _igvn, this );
3157   VectorSet visited(Thread::current()->resource_area());
3158 
3159   fail = 0;
3160   verify_compare( C->root(), &loop_verify, visited );
3161   assert( fail == 0, "verify loops failed" );
3162   // Verify loop structure is the same
3163   _ltree_root->verify_tree(loop_verify._ltree_root, NULL);
3164   // Reset major-progress.  It was cleared by creating a verify version of
3165   // PhaseIdealLoop.
3166   C->restore_major_progress(old_progress);

3167 }
3168 
3169 //------------------------------verify_compare---------------------------------
3170 // Make sure me and the given PhaseIdealLoop agree on key data structures
3171 void PhaseIdealLoop::verify_compare( Node *n, const PhaseIdealLoop *loop_verify, VectorSet &visited ) const {
3172   if( !n ) return;
3173   if( visited.test_set( n->_idx ) ) return;
3174   if( !_nodes[n->_idx] ) {      // Unreachable
3175     assert( !loop_verify->_nodes[n->_idx], "both should be unreachable" );
3176     return;
3177   }
3178 
3179   uint i;
3180   for( i = 0; i < n->req(); i++ )
3181     verify_compare( n->in(i), loop_verify, visited );
3182 
3183   // Check the '_nodes' block/loop structure
3184   i = n->_idx;
3185   if( has_ctrl(n) ) {           // We have control; verify has loop or ctrl
3186     if( _nodes[i] != loop_verify->_nodes[i] &&


4276     // state), Mods/Loads can float around.  So free them up.
4277     switch( n->Opcode() ) {
4278     case Op_DivI:
4279     case Op_DivF:
4280     case Op_DivD:
4281     case Op_ModI:
4282     case Op_ModF:
4283     case Op_ModD:
4284     case Op_LoadB:              // Same with Loads; they can sink
4285     case Op_LoadUB:             // during loop optimizations.
4286     case Op_LoadUS:
4287     case Op_LoadD:
4288     case Op_LoadF:
4289     case Op_LoadI:
4290     case Op_LoadKlass:
4291     case Op_LoadNKlass:
4292     case Op_LoadL:
4293     case Op_LoadS:
4294     case Op_LoadP:
4295     case Op_LoadBarrierSlowReg:

4296     case Op_LoadN:
4297     case Op_LoadRange:
4298     case Op_LoadD_unaligned:
4299     case Op_LoadL_unaligned:
4300     case Op_StrComp:            // Does a bunch of load-like effects
4301     case Op_StrEquals:
4302     case Op_StrIndexOf:
4303     case Op_StrIndexOfChar:
4304     case Op_AryEq:
4305     case Op_HasNegatives:
4306       pinned = false;
4307     }
4308     if( pinned ) {
4309       IdealLoopTree *chosen_loop = get_loop(n->is_CFG() ? n : get_ctrl(n));
4310       if( !chosen_loop->_child )       // Inner loop?
4311         chosen_loop->_body.push(n); // Collect inner loops
4312       return;
4313     }
4314   } else {                      // No slot zero
4315     if( n->is_CFG() ) {         // CFG with no slot 0 is dead


   1 /*
   2  * Copyright (c) 1998, 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *


 961     assert(inner != NULL && outer != NULL, "missing loop in strip mined nest");
 962     Node* outer_tail = outer->in(LoopNode::LoopBackControl);
 963     Node* outer_le = outer_tail->in(0);
 964     assert(outer_le->Opcode() == Op_OuterStripMinedLoopEnd, "tail of outer loop should be an If");
 965     Node* sfpt = outer_le->in(0);
 966     assert(sfpt->Opcode() == Op_SafePoint, "where's the safepoint?");
 967     Node* inner_out = sfpt->in(0);
 968     if (inner_out->outcnt() != 1) {
 969       ResourceMark rm;
 970       Unique_Node_List wq;
 971 
 972       for (DUIterator_Fast imax, i = inner_out->fast_outs(imax); i < imax; i++) {
 973         Node* u = inner_out->fast_out(i);
 974         if (u == sfpt) {
 975           continue;
 976         }
 977         wq.clear();
 978         wq.push(u);
 979         bool found_sfpt = false;
 980         for (uint next = 0; next < wq.size() && !found_sfpt; next++) {
 981           Node *n = wq.at(next);
 982           for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax && !found_sfpt; i++) {
 983             Node* u = n->fast_out(i);
 984             if (u == sfpt) {
 985               found_sfpt = true;
 986             }
 987             if (!u->is_CFG()) {
 988               wq.push(u);
 989             }
 990           }
 991         }
 992         assert(found_sfpt, "no node in loop that's not input to safepoint");
 993       }
 994     }













 995     CountedLoopEndNode* cle = inner_out->in(0)->as_CountedLoopEnd();
 996     assert(cle == inner->loopexit_or_null(), "mismatch");
 997     bool has_skeleton = outer_le->in(1)->bottom_type()->singleton() && outer_le->in(1)->bottom_type()->is_int()->get_con() == 0;
 998     if (has_skeleton) {
 999       assert(expect_skeleton == 1 || expect_skeleton == -1, "unexpected skeleton node");
1000       assert(outer->outcnt() == 2, "only phis");
1001     } else {
1002       assert(expect_skeleton == 0 || expect_skeleton == -1, "no skeleton node?");
1003       uint phis = 0;
1004       for (DUIterator_Fast imax, i = inner->fast_outs(imax); i < imax; i++) {
1005         Node* u = inner->fast_out(i);
1006         if (u->is_Phi()) {
1007           phis++;
1008         }
1009       }
1010       for (DUIterator_Fast imax, i = outer->fast_outs(imax); i < imax; i++) {
1011         Node* u = outer->fast_out(i);
1012         assert(u == outer || u == inner || u->is_Phi(), "nothing between inner and outer loop");
1013       }
1014       uint stores = 0;


2422     // Remove safepoints
2423     bool keep_one_sfpt = !(_has_call || _has_sfpt);
2424     remove_safepoints(phase, keep_one_sfpt);
2425 
2426     // Look for induction variables
2427     phase->replace_parallel_iv(this);
2428 
2429   } else if (_parent != NULL && !_irreducible) {
2430     // Not a counted loop. Keep one safepoint.
2431     bool keep_one_sfpt = true;
2432     remove_safepoints(phase, keep_one_sfpt);
2433   }
2434 
2435   // Recursively
2436   assert(loop->_child != this || (loop->_head->as_Loop()->is_OuterStripMinedLoop() && _head->as_CountedLoop()->is_strip_mined()), "what kind of loop was added?");
2437   assert(loop->_child != this || (loop->_child->_child == NULL && loop->_child->_next == NULL), "would miss some loops");
2438   if (loop->_child && loop->_child != this) loop->_child->counted_loop(phase);
2439   if (loop->_next)  loop->_next ->counted_loop(phase);
2440 }
2441 


















































2442 #ifndef PRODUCT
2443 //------------------------------dump_head--------------------------------------
2444 // Dump 1 liner for loop header info
2445 void IdealLoopTree::dump_head( ) const {
2446   for (uint i=0; i<_nest; i++)
2447     tty->print("  ");

2448   tty->print("Loop: N%d/N%d ",_head->_idx,_tail->_idx);
2449   if (_irreducible) tty->print(" IRREDUCIBLE");
2450   Node* entry = _head->is_Loop() ? _head->as_Loop()->skip_strip_mined(-1)->in(LoopNode::EntryControl) : _head->in(LoopNode::EntryControl);
2451   Node* predicate = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
2452   if (predicate != NULL ) {
2453     tty->print(" limit_check");
2454     entry = PhaseIdealLoop::skip_loop_predicates(entry);
2455   }
2456   if (UseLoopPredicate) {
2457     entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_predicate);
2458     if (entry != NULL) {
2459       tty->print(" predicated");
2460       entry = PhaseIdealLoop::skip_loop_predicates(entry);
2461     }
2462   }
2463   if (UseProfiledLoopPredicate) {
2464     entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_profile_predicate);
2465     if (entry != NULL) {
2466       tty->print(" profile_predicated");
2467     }


2496   if (_has_call) tty->print(" has_call");
2497   if (_has_sfpt) tty->print(" has_sfpt");
2498   if (_rce_candidate) tty->print(" rce");
2499   if (_safepts != NULL && _safepts->size() > 0) {
2500     tty->print(" sfpts={"); _safepts->dump_simple(); tty->print(" }");
2501   }
2502   if (_required_safept != NULL && _required_safept->size() > 0) {
2503     tty->print(" req={"); _required_safept->dump_simple(); tty->print(" }");
2504   }
2505   if (Verbose) {
2506     tty->print(" body={"); _body.dump_simple(); tty->print(" }");
2507   }
2508   if (_head->is_Loop() && _head->as_Loop()->is_strip_mined()) {
2509     tty->print(" strip_mined");
2510   }
2511   tty->cr();
2512 }
2513 
2514 //------------------------------dump-------------------------------------------
2515 // Dump loops by loop tree
2516 void IdealLoopTree::dump( ) const {
2517   dump_head();
2518   if (_child) _child->dump();
2519   if (_next)  _next ->dump();
2520 }
2521 
2522 #endif
2523 
2524 static void log_loop_tree(IdealLoopTree* root, IdealLoopTree* loop, CompileLog* log) {
2525   if (loop == root) {
2526     if (loop->_child != NULL) {
2527       log->begin_head("loop_tree");
2528       log->end_head();
2529       if( loop->_child ) log_loop_tree(root, loop->_child, log);
2530       log->tail("loop_tree");
2531       assert(loop->_next == NULL, "what?");
2532     }
2533   } else {
2534     Node* head = loop->_head;
2535     log->begin_head("loop");
2536     log->print(" idx='%d' ", head->_idx);


2693         if (n2->in(0) != c2) {
2694           _igvn.hash_delete(n2);
2695           n2->set_req(0, c2);
2696           _igvn.hash_insert(n2);
2697           _igvn._worklist.push(n2);
2698           progress = true;
2699         }
2700       }
2701     }
2702   }
2703 
2704   return progress;
2705 }
2706 
2707 
2708 //=============================================================================
2709 //----------------------------build_and_optimize-------------------------------
2710 // Create a PhaseLoop.  Build the ideal Loop tree.  Map each Ideal Node to
2711 // its corresponding LoopNode.  If 'optimize' is true, do some loop cleanups.
2712 void PhaseIdealLoop::build_and_optimize(LoopOptsMode mode) {
2713   bool do_split_ifs = (mode == LoopOptsDefault || mode == LoopOptsLastRound);
2714   bool skip_loop_opts = (mode == LoopOptsNone);
2715 
2716   int old_progress = C->major_progress();
2717   uint orig_worklist_size = _igvn._worklist.size();
2718 
2719   // Reset major-progress flag for the driver's heuristics
2720   C->clear_major_progress();
2721 
2722 #ifndef PRODUCT
2723   // Capture for later assert
2724   uint unique = C->unique();
2725   _loop_invokes++;
2726   _loop_work += unique;
2727 #endif
2728 
2729   // True if the method has at least 1 irreducible loop
2730   _has_irreducible_loops = false;
2731 
2732   _created_loop_node = false;
2733 


2853   worklist.push( C->top() );
2854   visited.set( C->top()->_idx ); // Set C->top() as visited now
2855   build_loop_early( visited, worklist, nstack );
2856 
2857   // Given early legal placement, try finding counted loops.  This placement
2858   // is good enough to discover most loop invariants.
2859   if (!_verify_me && !_verify_only && !strip_mined_loops_expanded) {
2860     _ltree_root->counted_loop( this );
2861   }
2862 
2863   // Find latest loop placement.  Find ideal loop placement.
2864   visited.Clear();
2865   init_dom_lca_tags();
2866   // Need C->root() on worklist when processing outs
2867   worklist.push( C->root() );
2868   NOT_PRODUCT( C->verify_graph_edges(); )
2869   worklist.push( C->top() );
2870   build_loop_late( visited, worklist, nstack );
2871 
2872   if (_verify_only) {
2873     // restore major progress flag
2874     for (int i = 0; i < old_progress; i++)
2875       C->set_major_progress();
2876     assert(C->unique() == unique, "verification mode made Nodes? ? ?");
2877     assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
2878     return;
2879   }
2880 
2881   // clear out the dead code after build_loop_late
2882   while (_deadlist.size()) {
2883     _igvn.remove_globally_dead_node(_deadlist.pop());
2884   }
2885 
2886   if (stop_early) {
2887     assert(do_expensive_nodes, "why are we here?");
2888     if (process_expensive_nodes()) {
2889       // If we made some progress when processing expensive nodes then
2890       // the IGVN may modify the graph in a way that will allow us to
2891       // make some more progress: we need to try processing expensive
2892       // nodes again.
2893       C->set_major_progress();
2894     }
2895     _igvn.optimize();
2896     return;
2897   }
2898 
2899   // Some parser-inserted loop predicates could never be used by loop
2900   // predication or they were moved away from loop during some optimizations.
2901   // For example, peeling. Eliminate them before next loop optimizations.
2902   eliminate_useless_predicates();
2903 
2904 #ifndef PRODUCT
2905   C->verify_graph_edges();
2906   if (_verify_me) {             // Nested verify pass?
2907     // Check to see if the verify mode is broken
2908     assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
2909     return;
2910   }
2911   if(VerifyLoopOptimizations) verify();
2912   if(TraceLoopOpts && C->has_loops()) {
2913     _ltree_root->dump();
2914   }
2915 #endif
2916 
2917   if (skip_loop_opts) {
2918     // restore major progress flag
2919     for (int i = 0; i < old_progress; i++) {
2920       C->set_major_progress();
2921     }
2922 
2923     // Cleanup any modified bits
2924     _igvn.optimize();
2925 
2926     if (C->log() != NULL) {
2927       log_loop_tree(_ltree_root, _ltree_root, C->log());
2928     }
2929     return;
2930   }
2931 
2932   if (bs->optimize_loops(this, mode, visited, nstack, worklist)) {
2933     _igvn.optimize();
2934     if (C->log() != NULL) {
2935       log_loop_tree(_ltree_root, _ltree_root, C->log());
2936     }
2937     return;
2938   }
2939 
2940   if (ReassociateInvariants) {
2941     AutoNodeBudget node_budget(this, AutoNodeBudget::NO_BUDGET_CHECK);
2942     // Reassociate invariants and prep for split_thru_phi
2943     for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
2944       IdealLoopTree* lpt = iter.current();
2945       bool is_counted = lpt->is_counted();
2946       if (!is_counted || !lpt->is_innermost()) continue;
2947 
2948       // check for vectorized loops, any reassociation of invariants was already done
2949       if (is_counted && lpt->_head->as_CountedLoop()->is_unroll_only()) continue;
2950 
2951       lpt->reassociate_invariants(this);
2952 


2953       // Because RCE opportunities can be masked by split_thru_phi,
2954       // look for RCE candidates and inhibit split_thru_phi
2955       // on just their loop-phi's for this pass of loop opts
2956       if (SplitIfBlocks && do_split_ifs) {

2957         if (lpt->policy_range_check(this)) {
2958           lpt->_rce_candidate = 1; // = true
2959         }
2960       }
2961     }
2962   }
2963 
2964   // Check for aggressive application of split-if and other transforms
2965   // that require basic-block info (like cloning through Phi's)
2966   if( SplitIfBlocks && do_split_ifs ) {
2967     visited.Clear();
2968     split_if_with_blocks( visited, nstack, mode == LoopOptsLastRound );
2969     NOT_PRODUCT( if( VerifyLoopOptimizations ) verify(); );
2970     if (mode == LoopOptsLastRound) {
2971       C->set_major_progress();
2972     }
2973   }
2974 
2975   if (!C->major_progress() && do_expensive_nodes && process_expensive_nodes()) {
2976     C->set_major_progress();
2977   }
2978 
2979   // Perform loop predication before iteration splitting
2980   if (C->has_loops() && !C->major_progress() && (C->predicate_count() > 0)) {
2981     _ltree_root->_child->loop_predication(this);
2982   }
2983 
2984   if (OptimizeFill && UseLoopPredicate && C->has_loops() && !C->major_progress()) {
2985     if (do_intrinsify_fill()) {
2986       C->set_major_progress();
2987     }
2988   }
2989 
2990   // Perform iteration-splitting on inner loops.  Split iterations to avoid
2991   // range checks or one-shot null checks.
2992 


3087 void PhaseIdealLoop::print_statistics() {
3088   tty->print_cr("PhaseIdealLoop=%d, sum _unique=%d", _loop_invokes, _loop_work);
3089 }
3090 
3091 //------------------------------verify-----------------------------------------
3092 // Build a verify-only PhaseIdealLoop, and see that it agrees with me.
3093 static int fail;                // debug only, so its multi-thread dont care
3094 void PhaseIdealLoop::verify() const {
3095   int old_progress = C->major_progress();
3096   ResourceMark rm;
3097   PhaseIdealLoop loop_verify( _igvn, this );
3098   VectorSet visited(Thread::current()->resource_area());
3099 
3100   fail = 0;
3101   verify_compare( C->root(), &loop_verify, visited );
3102   assert( fail == 0, "verify loops failed" );
3103   // Verify loop structure is the same
3104   _ltree_root->verify_tree(loop_verify._ltree_root, NULL);
3105   // Reset major-progress.  It was cleared by creating a verify version of
3106   // PhaseIdealLoop.
3107   for( int i=0; i<old_progress; i++ )
3108     C->set_major_progress();
3109 }
3110 
3111 //------------------------------verify_compare---------------------------------
3112 // Make sure me and the given PhaseIdealLoop agree on key data structures
3113 void PhaseIdealLoop::verify_compare( Node *n, const PhaseIdealLoop *loop_verify, VectorSet &visited ) const {
3114   if( !n ) return;
3115   if( visited.test_set( n->_idx ) ) return;
3116   if( !_nodes[n->_idx] ) {      // Unreachable
3117     assert( !loop_verify->_nodes[n->_idx], "both should be unreachable" );
3118     return;
3119   }
3120 
3121   uint i;
3122   for( i = 0; i < n->req(); i++ )
3123     verify_compare( n->in(i), loop_verify, visited );
3124 
3125   // Check the '_nodes' block/loop structure
3126   i = n->_idx;
3127   if( has_ctrl(n) ) {           // We have control; verify has loop or ctrl
3128     if( _nodes[i] != loop_verify->_nodes[i] &&


4218     // state), Mods/Loads can float around.  So free them up.
4219     switch( n->Opcode() ) {
4220     case Op_DivI:
4221     case Op_DivF:
4222     case Op_DivD:
4223     case Op_ModI:
4224     case Op_ModF:
4225     case Op_ModD:
4226     case Op_LoadB:              // Same with Loads; they can sink
4227     case Op_LoadUB:             // during loop optimizations.
4228     case Op_LoadUS:
4229     case Op_LoadD:
4230     case Op_LoadF:
4231     case Op_LoadI:
4232     case Op_LoadKlass:
4233     case Op_LoadNKlass:
4234     case Op_LoadL:
4235     case Op_LoadS:
4236     case Op_LoadP:
4237     case Op_LoadBarrierSlowReg:
4238     case Op_LoadBarrierWeakSlowReg:
4239     case Op_LoadN:
4240     case Op_LoadRange:
4241     case Op_LoadD_unaligned:
4242     case Op_LoadL_unaligned:
4243     case Op_StrComp:            // Does a bunch of load-like effects
4244     case Op_StrEquals:
4245     case Op_StrIndexOf:
4246     case Op_StrIndexOfChar:
4247     case Op_AryEq:
4248     case Op_HasNegatives:
4249       pinned = false;
4250     }
4251     if( pinned ) {
4252       IdealLoopTree *chosen_loop = get_loop(n->is_CFG() ? n : get_ctrl(n));
4253       if( !chosen_loop->_child )       // Inner loop?
4254         chosen_loop->_body.push(n); // Collect inner loops
4255       return;
4256     }
4257   } else {                      // No slot zero
4258     if( n->is_CFG() ) {         // CFG with no slot 0 is dead


< prev index next >