< 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 {


2711           n2->set_req(0, c2);
2712           _igvn.hash_insert(n2);
2713           _igvn._worklist.push(n2);
2714           progress = true;
2715         }
2716       }
2717     }
2718   }
2719 
2720   return progress;
2721 }
2722 
2723 
2724 //=============================================================================
2725 //----------------------------build_and_optimize-------------------------------
2726 // Create a PhaseLoop.  Build the ideal Loop tree.  Map each Ideal Node to
2727 // its corresponding LoopNode.  If 'optimize' is true, do some loop cleanups.
2728 void PhaseIdealLoop::build_and_optimize(LoopOptsMode mode) {
2729   bool do_split_ifs = (mode == LoopOptsDefault || mode == LoopOptsLastRound);
2730   bool skip_loop_opts = (mode == LoopOptsNone);


2731 
2732   ResourceMark rm;
2733 
2734   int old_progress = C->major_progress();
2735   uint orig_worklist_size = _igvn._worklist.size();
2736 
2737   // Reset major-progress flag for the driver's heuristics
2738   C->clear_major_progress();
2739 
2740 #ifndef PRODUCT
2741   // Capture for later assert
2742   uint unique = C->unique();
2743   _loop_invokes++;
2744   _loop_work += unique;
2745 #endif
2746 
2747   // True if the method has at least 1 irreducible loop
2748   _has_irreducible_loops = false;
2749 
2750   _created_loop_node = false;


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


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


2926   if(TraceLoopOpts && C->has_loops()) {
2927     _ltree_root->dump();
2928   }
2929 #endif
2930 
2931   if (skip_loop_opts) {
2932     // restore major progress flag
2933     for (int i = 0; i < old_progress; i++) {
2934       C->set_major_progress();
2935     }
2936 
2937     // Cleanup any modified bits
2938     _igvn.optimize();
2939 
2940     if (C->log() != NULL) {
2941       log_loop_tree(_ltree_root, _ltree_root, C->log());
2942     }
2943     return;
2944   }
2945 










2946   if (ReassociateInvariants) {
2947     // Reassociate invariants and prep for split_thru_phi
2948     for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
2949       IdealLoopTree* lpt = iter.current();
2950       bool is_counted = lpt->is_counted();
2951       if (!is_counted || !lpt->is_inner()) continue;
2952 
2953       // check for vectorized loops, any reassociation of invariants was already done
2954       if (is_counted && lpt->_head->as_CountedLoop()->do_unroll_only()) continue;
2955 
2956       lpt->reassociate_invariants(this);
2957 
2958       // Because RCE opportunities can be masked by split_thru_phi,
2959       // look for RCE candidates and inhibit split_thru_phi
2960       // on just their loop-phi's for this pass of loop opts
2961       if (SplitIfBlocks && do_split_ifs) {
2962         if (lpt->policy_range_check(this)) {
2963           lpt->_rce_candidate = 1; // = true
2964         }
2965       }


4149         }
4150         // Get saved parent node and next use's index. Visit the rest of uses.
4151         n   = nstack.node();
4152         cnt = n->outcnt();
4153         i   = nstack.index();
4154         nstack.pop();
4155       }
4156     }
4157   }
4158 }
4159 
4160 // Verify that no data node is schedules in the outer loop of a strip
4161 // mined loop.
4162 void PhaseIdealLoop::verify_strip_mined_scheduling(Node *n, Node* least) {
4163 #ifdef ASSERT
4164   if (get_loop(least)->_nest == 0) {
4165     return;
4166   }
4167   IdealLoopTree* loop = get_loop(least);
4168   Node* head = loop->_head;
4169   if (head->is_OuterStripMinedLoop()) {


4170     Node* sfpt = head->as_Loop()->outer_safepoint();
4171     ResourceMark rm;
4172     Unique_Node_List wq;
4173     wq.push(sfpt);
4174     for (uint i = 0; i < wq.size(); i++) {
4175       Node *m = wq.at(i);
4176       for (uint i = 1; i < m->req(); i++) {
4177         Node* nn = m->in(i);
4178         if (nn == n) {
4179           return;
4180         }
4181         if (nn != NULL && has_ctrl(nn) && get_loop(get_ctrl(nn)) == loop) {
4182           wq.push(nn);
4183         }
4184       }
4185     }
4186     ShouldNotReachHere();
4187   }
4188 #endif
4189 }


4229     case Op_LoadI:
4230     case Op_LoadKlass:
4231     case Op_LoadNKlass:
4232     case Op_LoadL:
4233     case Op_LoadS:
4234     case Op_LoadP:
4235     case Op_LoadBarrierSlowReg:
4236     case Op_LoadBarrierWeakSlowReg:
4237     case Op_LoadN:
4238     case Op_LoadRange:
4239     case Op_LoadD_unaligned:
4240     case Op_LoadL_unaligned:
4241     case Op_StrComp:            // Does a bunch of load-like effects
4242     case Op_StrEquals:
4243     case Op_StrIndexOf:
4244     case Op_StrIndexOfChar:
4245     case Op_AryEq:
4246     case Op_HasNegatives:
4247       pinned = false;
4248     }



4249     if( pinned ) {
4250       IdealLoopTree *chosen_loop = get_loop(n->is_CFG() ? n : get_ctrl(n));
4251       if( !chosen_loop->_child )       // Inner loop?
4252         chosen_loop->_body.push(n); // Collect inner loops
4253       return;
4254     }
4255   } else {                      // No slot zero
4256     if( n->is_CFG() ) {         // CFG with no slot 0 is dead
4257       _nodes.map(n->_idx,0);    // No block setting, it's globally dead
4258       return;
4259     }
4260     assert(!n->is_CFG() || n->outcnt() == 0, "");
4261   }
4262 
4263   // Do I have a "safe range" I can select over?
4264   Node *early = get_ctrl(n);// Early location already computed
4265 
4266   // Compute latest point this Node can go
4267   Node *LCA = get_late_ctrl( n, early );
4268   // LCA is NULL due to uses being dead


4493     }
4494     // Dump nodes it controls
4495     for( uint k = 0; k < _nodes.Size(); k++ ) {
4496       // (k < C->unique() && get_ctrl(find(k)) == n)
4497       if (k < C->unique() && _nodes[k] == (Node*)((intptr_t)n + 1)) {
4498         Node *m = C->root()->find(k);
4499         if( m && m->outcnt() > 0 ) {
4500           if (!(has_ctrl(m) && get_ctrl_no_update(m) == n)) {
4501             tty->print_cr("*** BROKEN CTRL ACCESSOR!  _nodes[k] is %p, ctrl is %p",
4502                           _nodes[k], has_ctrl(m) ? get_ctrl_no_update(m) : NULL);
4503           }
4504           for( uint j = 0; j < loop->_nest; j++ )
4505             tty->print("  ");
4506           tty->print(" ");
4507           m->dump();
4508         }
4509       }
4510     }
4511   }
4512 }

4513 
4514 // Collect a R-P-O for the whole CFG.
4515 // Result list is in post-order (scan backwards for RPO)
4516 void PhaseIdealLoop::rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const {
4517   stk.push(start, 0);
4518   visited.set(start->_idx);
4519 
4520   while (stk.is_nonempty()) {
4521     Node* m   = stk.node();
4522     uint  idx = stk.index();
4523     if (idx < m->outcnt()) {
4524       stk.set_index(idx + 1);
4525       Node* n = m->raw_out(idx);
4526       if (n->is_CFG() && !visited.test_set(n->_idx)) {
4527         stk.push(n, 0);
4528       }
4529     } else {
4530       rpo_list.push(m);
4531       stk.pop();
4532     }
4533   }
4534 }
4535 #endif
4536 
4537 
4538 //=============================================================================
4539 //------------------------------LoopTreeIterator-----------------------------------
4540 
4541 // Advance to next loop tree using a preorder, left-to-right traversal.
4542 void LoopTreeIterator::next() {
4543   assert(!done(), "must not be done.");
4544   if (_curnt->_child != NULL) {
4545     _curnt = _curnt->_child;
4546   } else if (_curnt->_next != NULL) {
4547     _curnt = _curnt->_next;
4548   } else {
4549     while (_curnt != _root && _curnt->_next == NULL) {
4550       _curnt = _curnt->_parent;
4551     }
4552     if (_curnt == _root) {
4553       _curnt = NULL;
4554       assert(done(), "must be done.");
4555     } 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 {


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


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


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


2932   if(TraceLoopOpts && C->has_loops()) {
2933     _ltree_root->dump();
2934   }
2935 #endif
2936 
2937   if (skip_loop_opts) {
2938     // restore major progress flag
2939     for (int i = 0; i < old_progress; i++) {
2940       C->set_major_progress();
2941     }
2942 
2943     // Cleanup any modified bits
2944     _igvn.optimize();
2945 
2946     if (C->log() != NULL) {
2947       log_loop_tree(_ltree_root, _ltree_root, C->log());
2948     }
2949     return;
2950   }
2951 
2952 #if INCLUDE_SHENANDOAHGC
2953   if (UseShenandoahGC && ((ShenandoahBarrierSetC2*) BarrierSet::barrier_set()->barrier_set_c2())->optimize_loops(this, mode, visited, nstack, worklist)) {
2954     _igvn.optimize();
2955     if (C->log() != NULL) {
2956       log_loop_tree(_ltree_root, _ltree_root, C->log());
2957     }
2958     return;
2959   }
2960 #endif
2961 
2962   if (ReassociateInvariants) {
2963     // Reassociate invariants and prep for split_thru_phi
2964     for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
2965       IdealLoopTree* lpt = iter.current();
2966       bool is_counted = lpt->is_counted();
2967       if (!is_counted || !lpt->is_inner()) continue;
2968 
2969       // check for vectorized loops, any reassociation of invariants was already done
2970       if (is_counted && lpt->_head->as_CountedLoop()->do_unroll_only()) continue;
2971 
2972       lpt->reassociate_invariants(this);
2973 
2974       // Because RCE opportunities can be masked by split_thru_phi,
2975       // look for RCE candidates and inhibit split_thru_phi
2976       // on just their loop-phi's for this pass of loop opts
2977       if (SplitIfBlocks && do_split_ifs) {
2978         if (lpt->policy_range_check(this)) {
2979           lpt->_rce_candidate = 1; // = true
2980         }
2981       }


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


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


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

4557 
4558 
4559 //=============================================================================
4560 //------------------------------LoopTreeIterator-----------------------------------
4561 
4562 // Advance to next loop tree using a preorder, left-to-right traversal.
4563 void LoopTreeIterator::next() {
4564   assert(!done(), "must not be done.");
4565   if (_curnt->_child != NULL) {
4566     _curnt = _curnt->_child;
4567   } else if (_curnt->_next != NULL) {
4568     _curnt = _curnt->_next;
4569   } else {
4570     while (_curnt != _root && _curnt->_next == NULL) {
4571       _curnt = _curnt->_parent;
4572     }
4573     if (_curnt == _root) {
4574       _curnt = NULL;
4575       assert(done(), "must be done.");
4576     } else {
< prev index next >