< prev index next >

src/hotspot/share/opto/loopnode.cpp

Print this page




  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "ci/ciMethodData.hpp"
  27 #include "compiler/compileLog.hpp"
  28 #include "gc/shared/barrierSet.hpp"
  29 #include "gc/shared/c2/barrierSetC2.hpp"
  30 #include "libadt/vectset.hpp"
  31 #include "memory/allocation.inline.hpp"
  32 #include "memory/resourceArea.hpp"
  33 #include "opto/addnode.hpp"
  34 #include "opto/callnode.hpp"
  35 #include "opto/connode.hpp"
  36 #include "opto/convertnode.hpp"
  37 #include "opto/divnode.hpp"
  38 #include "opto/idealGraphPrinter.hpp"
  39 #include "opto/loopnode.hpp"
  40 #include "opto/mulnode.hpp"
  41 #include "opto/rootnode.hpp"
  42 #include "opto/superword.hpp"




  43 
  44 //=============================================================================
  45 //------------------------------is_loop_iv-------------------------------------
  46 // Determine if a node is Counted loop induction variable.
  47 // The method is declared in node.hpp.
  48 const Node* Node::is_loop_iv() const {
  49   if (this->is_Phi() && !this->as_Phi()->is_copy() &&
  50       this->as_Phi()->region()->is_CountedLoop() &&
  51       this->as_Phi()->region()->as_CountedLoop()->phi() == this) {
  52     return this;
  53   } else {
  54     return NULL;
  55   }
  56 }
  57 
  58 //=============================================================================
  59 //------------------------------dump_spec--------------------------------------
  60 // Dump special per-node info
  61 #ifndef PRODUCT
  62 void LoopNode::dump_spec(outputStream *st) const {


2696         }
2697         if (n2->in(0) != c2) {
2698           _igvn.hash_delete(n2);
2699           n2->set_req(0, c2);
2700           _igvn.hash_insert(n2);
2701           _igvn._worklist.push(n2);
2702           progress = true;
2703         }
2704       }
2705     }
2706   }
2707 
2708   return progress;
2709 }
2710 
2711 
2712 //=============================================================================
2713 //----------------------------build_and_optimize-------------------------------
2714 // Create a PhaseLoop.  Build the ideal Loop tree.  Map each Ideal Node to
2715 // its corresponding LoopNode.  If 'optimize' is true, do some loop cleanups.
2716 void PhaseIdealLoop::build_and_optimize(bool do_split_ifs, bool skip_loop_opts, bool last_round) {





2717   ResourceMark rm;
2718 
2719   int old_progress = C->major_progress();
2720   uint orig_worklist_size = _igvn._worklist.size();
2721 
2722   // Reset major-progress flag for the driver's heuristics
2723   C->clear_major_progress();
2724 
2725 #ifndef PRODUCT
2726   // Capture for later assert
2727   uint unique = C->unique();
2728   _loop_invokes++;
2729   _loop_work += unique;
2730 #endif
2731 
2732   // True if the method has at least 1 irreducible loop
2733   _has_irreducible_loops = false;
2734 
2735   _created_loop_node = false;
2736 


2760   build_loop_tree();
2761   // Check for bailout, and return
2762   if (C->failing()) {
2763     return;
2764   }
2765 
2766   // No loops after all
2767   if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
2768 
2769   // There should always be an outer loop containing the Root and Return nodes.
2770   // If not, we have a degenerate empty program.  Bail out in this case.
2771   if (!has_node(C->root())) {
2772     if (!_verify_only) {
2773       C->clear_major_progress();
2774       C->record_method_not_compilable("empty program detected during loop optimization");
2775     }
2776     return;
2777   }
2778 
2779   // Nothing to do, so get out
2780   bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !_verify_me && !_verify_only;
2781   bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
2782   if (stop_early && !do_expensive_nodes) {
2783     _igvn.optimize();           // Cleanup NeverBranches
2784     return;
2785   }
2786 
2787   // Set loop nesting depth
2788   _ltree_root->set_nest( 0 );
2789 
2790   // Split shared headers and insert loop landing pads.
2791   // Do not bother doing this on the Root loop of course.
2792   if( !_verify_me && !_verify_only && _ltree_root->_child ) {
2793     C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
2794     if( _ltree_root->_child->beautify_loops( this ) ) {
2795       // Re-build loop tree!
2796       _ltree_root->_child = NULL;
2797       _nodes.clear();
2798       reallocate_preorders();
2799       build_loop_tree();
2800       // Check for bailout, and return


2839 
2840   // Walk the DATA nodes and place into loops.  Find earliest control
2841   // node.  For CFG nodes, the _nodes array starts out and remains
2842   // holding the associated IdealLoopTree pointer.  For DATA nodes, the
2843   // _nodes array holds the earliest legal controlling CFG node.
2844 
2845   // Allocate stack with enough space to avoid frequent realloc
2846   int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
2847   Node_Stack nstack( a, stack_size );
2848 
2849   visited.Clear();
2850   Node_List worklist(a);
2851   // Don't need C->root() on worklist since
2852   // it will be processed among C->top() inputs
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 )
2860     _ltree_root->counted_loop( this );

2861 
2862   // Find latest loop placement.  Find ideal loop placement.
2863   visited.Clear();
2864   init_dom_lca_tags();
2865   // Need C->root() on worklist when processing outs
2866   worklist.push( C->root() );
2867   NOT_PRODUCT( C->verify_graph_edges(); )
2868   worklist.push( C->top() );
2869   build_loop_late( visited, worklist, nstack );
2870 
2871   if (_verify_only) {
2872     // restore major progress flag
2873     for (int i = 0; i < old_progress; i++)
2874       C->set_major_progress();
2875     assert(C->unique() == unique, "verification mode made Nodes? ? ?");
2876     assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
2877     return;
2878   }
2879 
2880   // clear out the dead code after build_loop_late


2911   if(TraceLoopOpts && C->has_loops()) {
2912     _ltree_root->dump();
2913   }
2914 #endif
2915 
2916   if (skip_loop_opts) {
2917     // restore major progress flag
2918     for (int i = 0; i < old_progress; i++) {
2919       C->set_major_progress();
2920     }
2921 
2922     // Cleanup any modified bits
2923     _igvn.optimize();
2924 
2925     if (C->log() != NULL) {
2926       log_loop_tree(_ltree_root, _ltree_root, C->log());
2927     }
2928     return;
2929   }
2930 










2931   if (ReassociateInvariants) {
2932     // Reassociate invariants and prep for split_thru_phi
2933     for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
2934       IdealLoopTree* lpt = iter.current();
2935       bool is_counted = lpt->is_counted();
2936       if (!is_counted || !lpt->is_inner()) continue;
2937 
2938       // check for vectorized loops, any reassociation of invariants was already done
2939       if (is_counted && lpt->_head->as_CountedLoop()->do_unroll_only()) continue;
2940 
2941       lpt->reassociate_invariants(this);
2942 
2943       // Because RCE opportunities can be masked by split_thru_phi,
2944       // look for RCE candidates and inhibit split_thru_phi
2945       // on just their loop-phi's for this pass of loop opts
2946       if (SplitIfBlocks && do_split_ifs) {
2947         if (lpt->policy_range_check(this)) {
2948           lpt->_rce_candidate = 1; // = true
2949         }
2950       }
2951     }
2952   }
2953 
2954   // Check for aggressive application of split-if and other transforms
2955   // that require basic-block info (like cloning through Phi's)
2956   if( SplitIfBlocks && do_split_ifs ) {
2957     visited.Clear();
2958     split_if_with_blocks( visited, nstack, last_round );
2959     NOT_PRODUCT( if( VerifyLoopOptimizations ) verify(); );
2960     if (last_round) {
2961       C->set_major_progress();
2962     }
2963   }
2964 
2965   if (!C->major_progress() && do_expensive_nodes && process_expensive_nodes()) {
2966     C->set_major_progress();
2967   }
2968 
2969   // Perform loop predication before iteration splitting
2970   if (C->has_loops() && !C->major_progress() && (C->predicate_count() > 0)) {
2971     _ltree_root->_child->loop_predication(this);
2972   }
2973 
2974   if (OptimizeFill && UseLoopPredicate && C->has_loops() && !C->major_progress()) {
2975     if (do_intrinsify_fill()) {
2976       C->set_major_progress();
2977     }
2978   }
2979 
2980   // Perform iteration-splitting on inner loops.  Split iterations to avoid


3941     compute_lca_of_uses(n, early, true);
3942   }
3943 #endif
3944 
3945   // if this is a load, check for anti-dependent stores
3946   // We use a conservative algorithm to identify potential interfering
3947   // instructions and for rescheduling the load.  The users of the memory
3948   // input of this load are examined.  Any use which is not a load and is
3949   // dominated by early is considered a potentially interfering store.
3950   // This can produce false positives.
3951   if (n->is_Load() && LCA != early) {
3952     Node_List worklist;
3953 
3954     Node *mem = n->in(MemNode::Memory);
3955     for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
3956       Node* s = mem->fast_out(i);
3957       worklist.push(s);
3958     }
3959     while(worklist.size() != 0 && LCA != early) {
3960       Node* s = worklist.pop();
3961       if (s->is_Load() || s->Opcode() == Op_SafePoint) {

3962         continue;
3963       } else if (s->is_MergeMem()) {
3964         for (DUIterator_Fast imax, i = s->fast_outs(imax); i < imax; i++) {
3965           Node* s1 = s->fast_out(i);
3966           worklist.push(s1);
3967         }
3968       } else {
3969         Node *sctrl = has_ctrl(s) ? get_ctrl(s) : s->in(0);
3970         assert(sctrl != NULL || s->outcnt() == 0, "must have control");
3971         if (sctrl != NULL && !sctrl->is_top() && is_dominator(early, sctrl)) {
3972           LCA = dom_lca_for_get_late_ctrl(LCA, sctrl, n);
3973         }
3974       }
3975     }
3976   }
3977 
3978   assert(LCA == find_non_split_ctrl(LCA), "unexpected late control");
3979   return LCA;
3980 }
3981 


4129         }
4130         // Get saved parent node and next use's index. Visit the rest of uses.
4131         n   = nstack.node();
4132         cnt = n->outcnt();
4133         i   = nstack.index();
4134         nstack.pop();
4135       }
4136     }
4137   }
4138 }
4139 
4140 // Verify that no data node is schedules in the outer loop of a strip
4141 // mined loop.
4142 void PhaseIdealLoop::verify_strip_mined_scheduling(Node *n, Node* least) {
4143 #ifdef ASSERT
4144   if (get_loop(least)->_nest == 0) {
4145     return;
4146   }
4147   IdealLoopTree* loop = get_loop(least);
4148   Node* head = loop->_head;
4149   if (head->is_OuterStripMinedLoop()) {


4150     Node* sfpt = head->as_Loop()->outer_safepoint();
4151     ResourceMark rm;
4152     Unique_Node_List wq;
4153     wq.push(sfpt);
4154     for (uint i = 0; i < wq.size(); i++) {
4155       Node *m = wq.at(i);
4156       for (uint i = 1; i < m->req(); i++) {
4157         Node* nn = m->in(i);
4158         if (nn == n) {
4159           return;
4160         }
4161         if (nn != NULL && has_ctrl(nn) && get_loop(get_ctrl(nn)) == loop) {
4162           wq.push(nn);
4163         }
4164       }
4165     }
4166     ShouldNotReachHere();
4167   }
4168 #endif
4169 }


4209     case Op_LoadI:
4210     case Op_LoadKlass:
4211     case Op_LoadNKlass:
4212     case Op_LoadL:
4213     case Op_LoadS:
4214     case Op_LoadP:
4215     case Op_LoadBarrierSlowReg:
4216     case Op_LoadBarrierWeakSlowReg:
4217     case Op_LoadN:
4218     case Op_LoadRange:
4219     case Op_LoadD_unaligned:
4220     case Op_LoadL_unaligned:
4221     case Op_StrComp:            // Does a bunch of load-like effects
4222     case Op_StrEquals:
4223     case Op_StrIndexOf:
4224     case Op_StrIndexOfChar:
4225     case Op_AryEq:
4226     case Op_HasNegatives:
4227       pinned = false;
4228     }



4229     if( pinned ) {
4230       IdealLoopTree *chosen_loop = get_loop(n->is_CFG() ? n : get_ctrl(n));
4231       if( !chosen_loop->_child )       // Inner loop?
4232         chosen_loop->_body.push(n); // Collect inner loops
4233       return;
4234     }
4235   } else {                      // No slot zero
4236     if( n->is_CFG() ) {         // CFG with no slot 0 is dead
4237       _nodes.map(n->_idx,0);    // No block setting, it's globally dead
4238       return;
4239     }
4240     assert(!n->is_CFG() || n->outcnt() == 0, "");
4241   }
4242 
4243   // Do I have a "safe range" I can select over?
4244   Node *early = get_ctrl(n);// Early location already computed
4245 
4246   // Compute latest point this Node can go
4247   Node *LCA = get_late_ctrl( n, early );
4248   // LCA is NULL due to uses being dead


4473     }
4474     // Dump nodes it controls
4475     for( uint k = 0; k < _nodes.Size(); k++ ) {
4476       // (k < C->unique() && get_ctrl(find(k)) == n)
4477       if (k < C->unique() && _nodes[k] == (Node*)((intptr_t)n + 1)) {
4478         Node *m = C->root()->find(k);
4479         if( m && m->outcnt() > 0 ) {
4480           if (!(has_ctrl(m) && get_ctrl_no_update(m) == n)) {
4481             tty->print_cr("*** BROKEN CTRL ACCESSOR!  _nodes[k] is %p, ctrl is %p",
4482                           _nodes[k], has_ctrl(m) ? get_ctrl_no_update(m) : NULL);
4483           }
4484           for( uint j = 0; j < loop->_nest; j++ )
4485             tty->print("  ");
4486           tty->print(" ");
4487           m->dump();
4488         }
4489       }
4490     }
4491   }
4492 }

4493 
4494 // Collect a R-P-O for the whole CFG.
4495 // Result list is in post-order (scan backwards for RPO)
4496 void PhaseIdealLoop::rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const {
4497   stk.push(start, 0);
4498   visited.set(start->_idx);
4499 
4500   while (stk.is_nonempty()) {
4501     Node* m   = stk.node();
4502     uint  idx = stk.index();
4503     if (idx < m->outcnt()) {
4504       stk.set_index(idx + 1);
4505       Node* n = m->raw_out(idx);
4506       if (n->is_CFG() && !visited.test_set(n->_idx)) {
4507         stk.push(n, 0);
4508       }
4509     } else {
4510       rpo_list.push(m);
4511       stk.pop();
4512     }
4513   }
4514 }
4515 #endif
4516 
4517 
4518 //=============================================================================
4519 //------------------------------LoopTreeIterator-----------------------------------
4520 
4521 // Advance to next loop tree using a preorder, left-to-right traversal.
4522 void LoopTreeIterator::next() {
4523   assert(!done(), "must not be done.");
4524   if (_curnt->_child != NULL) {
4525     _curnt = _curnt->_child;
4526   } else if (_curnt->_next != NULL) {
4527     _curnt = _curnt->_next;
4528   } else {
4529     while (_curnt != _root && _curnt->_next == NULL) {
4530       _curnt = _curnt->_parent;
4531     }
4532     if (_curnt == _root) {
4533       _curnt = NULL;
4534       assert(done(), "must be done.");
4535     } else {


  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "ci/ciMethodData.hpp"
  27 #include "compiler/compileLog.hpp"
  28 #include "gc/shared/barrierSet.hpp"
  29 #include "gc/shared/c2/barrierSetC2.hpp"
  30 #include "libadt/vectset.hpp"
  31 #include "memory/allocation.inline.hpp"
  32 #include "memory/resourceArea.hpp"
  33 #include "opto/addnode.hpp"
  34 #include "opto/callnode.hpp"
  35 #include "opto/connode.hpp"
  36 #include "opto/convertnode.hpp"
  37 #include "opto/divnode.hpp"
  38 #include "opto/idealGraphPrinter.hpp"
  39 #include "opto/loopnode.hpp"
  40 #include "opto/mulnode.hpp"
  41 #include "opto/rootnode.hpp"
  42 #include "opto/superword.hpp"
  43 #include "utilities/macros.hpp"
  44 #if INCLUDE_SHENANDOAHGC
  45 #include "gc/shenandoah/c2/shenandoahBarrierSetC2.hpp"
  46 #endif
  47 
  48 //=============================================================================
  49 //------------------------------is_loop_iv-------------------------------------
  50 // Determine if a node is Counted loop induction variable.
  51 // The method is declared in node.hpp.
  52 const Node* Node::is_loop_iv() const {
  53   if (this->is_Phi() && !this->as_Phi()->is_copy() &&
  54       this->as_Phi()->region()->is_CountedLoop() &&
  55       this->as_Phi()->region()->as_CountedLoop()->phi() == this) {
  56     return this;
  57   } else {
  58     return NULL;
  59   }
  60 }
  61 
  62 //=============================================================================
  63 //------------------------------dump_spec--------------------------------------
  64 // Dump special per-node info
  65 #ifndef PRODUCT
  66 void LoopNode::dump_spec(outputStream *st) const {


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


2769   build_loop_tree();
2770   // Check for bailout, and return
2771   if (C->failing()) {
2772     return;
2773   }
2774 
2775   // No loops after all
2776   if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
2777 
2778   // There should always be an outer loop containing the Root and Return nodes.
2779   // If not, we have a degenerate empty program.  Bail out in this case.
2780   if (!has_node(C->root())) {
2781     if (!_verify_only) {
2782       C->clear_major_progress();
2783       C->record_method_not_compilable("empty program detected during loop optimization");
2784     }
2785     return;
2786   }
2787 
2788   // Nothing to do, so get out
2789   bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !_verify_me && !_verify_only && !shenandoah_opts;
2790   bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
2791   if (stop_early && !do_expensive_nodes) {
2792     _igvn.optimize();           // Cleanup NeverBranches
2793     return;
2794   }
2795 
2796   // Set loop nesting depth
2797   _ltree_root->set_nest( 0 );
2798 
2799   // Split shared headers and insert loop landing pads.
2800   // Do not bother doing this on the Root loop of course.
2801   if( !_verify_me && !_verify_only && _ltree_root->_child ) {
2802     C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
2803     if( _ltree_root->_child->beautify_loops( this ) ) {
2804       // Re-build loop tree!
2805       _ltree_root->_child = NULL;
2806       _nodes.clear();
2807       reallocate_preorders();
2808       build_loop_tree();
2809       // Check for bailout, and return


2848 
2849   // Walk the DATA nodes and place into loops.  Find earliest control
2850   // node.  For CFG nodes, the _nodes array starts out and remains
2851   // holding the associated IdealLoopTree pointer.  For DATA nodes, the
2852   // _nodes array holds the earliest legal controlling CFG node.
2853 
2854   // Allocate stack with enough space to avoid frequent realloc
2855   int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
2856   Node_Stack nstack( a, stack_size );
2857 
2858   visited.Clear();
2859   Node_List worklist(a);
2860   // Don't need C->root() on worklist since
2861   // it will be processed among C->top() inputs
2862   worklist.push( C->top() );
2863   visited.set( C->top()->_idx ); // Set C->top() as visited now
2864   build_loop_early( visited, worklist, nstack );
2865 
2866   // Given early legal placement, try finding counted loops.  This placement
2867   // is good enough to discover most loop invariants.
2868   if (!_verify_me && !_verify_only && !shenandoah_opts) {
2869     _ltree_root->counted_loop(this);
2870   }
2871 
2872   // Find latest loop placement.  Find ideal loop placement.
2873   visited.Clear();
2874   init_dom_lca_tags();
2875   // Need C->root() on worklist when processing outs
2876   worklist.push( C->root() );
2877   NOT_PRODUCT( C->verify_graph_edges(); )
2878   worklist.push( C->top() );
2879   build_loop_late( visited, worklist, nstack );
2880 
2881   if (_verify_only) {
2882     // restore major progress flag
2883     for (int i = 0; i < old_progress; i++)
2884       C->set_major_progress();
2885     assert(C->unique() == unique, "verification mode made Nodes? ? ?");
2886     assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
2887     return;
2888   }
2889 
2890   // clear out the dead code after build_loop_late


2921   if(TraceLoopOpts && C->has_loops()) {
2922     _ltree_root->dump();
2923   }
2924 #endif
2925 
2926   if (skip_loop_opts) {
2927     // restore major progress flag
2928     for (int i = 0; i < old_progress; i++) {
2929       C->set_major_progress();
2930     }
2931 
2932     // Cleanup any modified bits
2933     _igvn.optimize();
2934 
2935     if (C->log() != NULL) {
2936       log_loop_tree(_ltree_root, _ltree_root, C->log());
2937     }
2938     return;
2939   }
2940 
2941 #if INCLUDE_SHENANDOAHGC
2942   if (UseShenandoahGC && ((ShenandoahBarrierSetC2*) BarrierSet::barrier_set()->barrier_set_c2())->optimize_loops(this, mode, visited, nstack, worklist)) {
2943     _igvn.optimize();
2944     if (C->log() != NULL) {
2945       log_loop_tree(_ltree_root, _ltree_root, C->log());
2946     }
2947     return;
2948   }
2949 #endif
2950 
2951   if (ReassociateInvariants) {
2952     // Reassociate invariants and prep for split_thru_phi
2953     for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
2954       IdealLoopTree* lpt = iter.current();
2955       bool is_counted = lpt->is_counted();
2956       if (!is_counted || !lpt->is_inner()) continue;
2957 
2958       // check for vectorized loops, any reassociation of invariants was already done
2959       if (is_counted && lpt->_head->as_CountedLoop()->do_unroll_only()) continue;
2960 
2961       lpt->reassociate_invariants(this);
2962 
2963       // Because RCE opportunities can be masked by split_thru_phi,
2964       // look for RCE candidates and inhibit split_thru_phi
2965       // on just their loop-phi's for this pass of loop opts
2966       if (SplitIfBlocks && do_split_ifs) {
2967         if (lpt->policy_range_check(this)) {
2968           lpt->_rce_candidate = 1; // = true
2969         }
2970       }
2971     }
2972   }
2973 
2974   // Check for aggressive application of split-if and other transforms
2975   // that require basic-block info (like cloning through Phi's)
2976   if( SplitIfBlocks && do_split_ifs ) {
2977     visited.Clear();
2978     split_if_with_blocks( visited, nstack, mode == LoopOptsZgcLastRound );
2979     NOT_PRODUCT( if( VerifyLoopOptimizations ) verify(); );
2980     if (mode == LoopOptsZgcLastRound) {
2981       C->set_major_progress();
2982     }
2983   }
2984 
2985   if (!C->major_progress() && do_expensive_nodes && process_expensive_nodes()) {
2986     C->set_major_progress();
2987   }
2988 
2989   // Perform loop predication before iteration splitting
2990   if (C->has_loops() && !C->major_progress() && (C->predicate_count() > 0)) {
2991     _ltree_root->_child->loop_predication(this);
2992   }
2993 
2994   if (OptimizeFill && UseLoopPredicate && C->has_loops() && !C->major_progress()) {
2995     if (do_intrinsify_fill()) {
2996       C->set_major_progress();
2997     }
2998   }
2999 
3000   // Perform iteration-splitting on inner loops.  Split iterations to avoid


3961     compute_lca_of_uses(n, early, true);
3962   }
3963 #endif
3964 
3965   // if this is a load, check for anti-dependent stores
3966   // We use a conservative algorithm to identify potential interfering
3967   // instructions and for rescheduling the load.  The users of the memory
3968   // input of this load are examined.  Any use which is not a load and is
3969   // dominated by early is considered a potentially interfering store.
3970   // This can produce false positives.
3971   if (n->is_Load() && LCA != early) {
3972     Node_List worklist;
3973 
3974     Node *mem = n->in(MemNode::Memory);
3975     for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
3976       Node* s = mem->fast_out(i);
3977       worklist.push(s);
3978     }
3979     while(worklist.size() != 0 && LCA != early) {
3980       Node* s = worklist.pop();
3981       if (s->is_Load() || s->is_ShenandoahBarrier() || s->Opcode() == Op_SafePoint ||
3982           (UseShenandoahGC && s->is_CallStaticJava() && s->as_CallStaticJava()->uncommon_trap_request() != 0)) {
3983         continue;
3984       } else if (s->is_MergeMem()) {
3985         for (DUIterator_Fast imax, i = s->fast_outs(imax); i < imax; i++) {
3986           Node* s1 = s->fast_out(i);
3987           worklist.push(s1);
3988         }
3989       } else {
3990         Node *sctrl = has_ctrl(s) ? get_ctrl(s) : s->in(0);
3991         assert(sctrl != NULL || s->outcnt() == 0, "must have control");
3992         if (sctrl != NULL && !sctrl->is_top() && is_dominator(early, sctrl)) {
3993           LCA = dom_lca_for_get_late_ctrl(LCA, sctrl, n);
3994         }
3995       }
3996     }
3997   }
3998 
3999   assert(LCA == find_non_split_ctrl(LCA), "unexpected late control");
4000   return LCA;
4001 }
4002 


4150         }
4151         // Get saved parent node and next use's index. Visit the rest of uses.
4152         n   = nstack.node();
4153         cnt = n->outcnt();
4154         i   = nstack.index();
4155         nstack.pop();
4156       }
4157     }
4158   }
4159 }
4160 
4161 // Verify that no data node is schedules in the outer loop of a strip
4162 // mined loop.
4163 void PhaseIdealLoop::verify_strip_mined_scheduling(Node *n, Node* least) {
4164 #ifdef ASSERT
4165   if (get_loop(least)->_nest == 0) {
4166     return;
4167   }
4168   IdealLoopTree* loop = get_loop(least);
4169   Node* head = loop->_head;
4170   if (head->is_OuterStripMinedLoop() &&
4171       // Verification can't be applied to fully built strip mined loops
4172       head->as_Loop()->outer_loop_end()->in(1)->find_int_con(-1) == 0) {
4173     Node* sfpt = head->as_Loop()->outer_safepoint();
4174     ResourceMark rm;
4175     Unique_Node_List wq;
4176     wq.push(sfpt);
4177     for (uint i = 0; i < wq.size(); i++) {
4178       Node *m = wq.at(i);
4179       for (uint i = 1; i < m->req(); i++) {
4180         Node* nn = m->in(i);
4181         if (nn == n) {
4182           return;
4183         }
4184         if (nn != NULL && has_ctrl(nn) && get_loop(get_ctrl(nn)) == loop) {
4185           wq.push(nn);
4186         }
4187       }
4188     }
4189     ShouldNotReachHere();
4190   }
4191 #endif
4192 }


4232     case Op_LoadI:
4233     case Op_LoadKlass:
4234     case Op_LoadNKlass:
4235     case Op_LoadL:
4236     case Op_LoadS:
4237     case Op_LoadP:
4238     case Op_LoadBarrierSlowReg:
4239     case Op_LoadBarrierWeakSlowReg:
4240     case Op_LoadN:
4241     case Op_LoadRange:
4242     case Op_LoadD_unaligned:
4243     case Op_LoadL_unaligned:
4244     case Op_StrComp:            // Does a bunch of load-like effects
4245     case Op_StrEquals:
4246     case Op_StrIndexOf:
4247     case Op_StrIndexOfChar:
4248     case Op_AryEq:
4249     case Op_HasNegatives:
4250       pinned = false;
4251     }
4252     if (UseShenandoahGC && n->is_CMove()) {
4253       pinned = false;
4254     }
4255     if( pinned ) {
4256       IdealLoopTree *chosen_loop = get_loop(n->is_CFG() ? n : get_ctrl(n));
4257       if( !chosen_loop->_child )       // Inner loop?
4258         chosen_loop->_body.push(n); // Collect inner loops
4259       return;
4260     }
4261   } else {                      // No slot zero
4262     if( n->is_CFG() ) {         // CFG with no slot 0 is dead
4263       _nodes.map(n->_idx,0);    // No block setting, it's globally dead
4264       return;
4265     }
4266     assert(!n->is_CFG() || n->outcnt() == 0, "");
4267   }
4268 
4269   // Do I have a "safe range" I can select over?
4270   Node *early = get_ctrl(n);// Early location already computed
4271 
4272   // Compute latest point this Node can go
4273   Node *LCA = get_late_ctrl( n, early );
4274   // LCA is NULL due to uses being dead


4499     }
4500     // Dump nodes it controls
4501     for( uint k = 0; k < _nodes.Size(); k++ ) {
4502       // (k < C->unique() && get_ctrl(find(k)) == n)
4503       if (k < C->unique() && _nodes[k] == (Node*)((intptr_t)n + 1)) {
4504         Node *m = C->root()->find(k);
4505         if( m && m->outcnt() > 0 ) {
4506           if (!(has_ctrl(m) && get_ctrl_no_update(m) == n)) {
4507             tty->print_cr("*** BROKEN CTRL ACCESSOR!  _nodes[k] is %p, ctrl is %p",
4508                           _nodes[k], has_ctrl(m) ? get_ctrl_no_update(m) : NULL);
4509           }
4510           for( uint j = 0; j < loop->_nest; j++ )
4511             tty->print("  ");
4512           tty->print(" ");
4513           m->dump();
4514         }
4515       }
4516     }
4517   }
4518 }
4519 #endif
4520 
4521 // Collect a R-P-O for the whole CFG.
4522 // Result list is in post-order (scan backwards for RPO)
4523 void PhaseIdealLoop::rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const {
4524   stk.push(start, 0);
4525   visited.set(start->_idx);
4526 
4527   while (stk.is_nonempty()) {
4528     Node* m   = stk.node();
4529     uint  idx = stk.index();
4530     if (idx < m->outcnt()) {
4531       stk.set_index(idx + 1);
4532       Node* n = m->raw_out(idx);
4533       if (n->is_CFG() && !visited.test_set(n->_idx)) {
4534         stk.push(n, 0);
4535       }
4536     } else {
4537       rpo_list.push(m);
4538       stk.pop();
4539     }
4540   }
4541 }

4542 
4543 
4544 //=============================================================================
4545 //------------------------------LoopTreeIterator-----------------------------------
4546 
4547 // Advance to next loop tree using a preorder, left-to-right traversal.
4548 void LoopTreeIterator::next() {
4549   assert(!done(), "must not be done.");
4550   if (_curnt->_child != NULL) {
4551     _curnt = _curnt->_child;
4552   } else if (_curnt->_next != NULL) {
4553     _curnt = _curnt->_next;
4554   } else {
4555     while (_curnt != _root && _curnt->_next == NULL) {
4556       _curnt = _curnt->_parent;
4557     }
4558     if (_curnt == _root) {
4559       _curnt = NULL;
4560       assert(done(), "must be done.");
4561     } else {
< prev index next >