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


 979           continue;
 980         }
 981         wq.clear();
 982         wq.push(u);
 983         bool found_sfpt = false;
 984         for (uint next = 0; next < wq.size() && !found_sfpt; next++) {
 985           Node *n = wq.at(next);
 986           for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax && !found_sfpt; i++) {
 987             Node* u = n->fast_out(i);
 988             if (u == sfpt) {
 989               found_sfpt = true;
 990             }
 991             if (!u->is_CFG()) {
 992               wq.push(u);
 993             }
 994           }
 995         }
 996         assert(found_sfpt, "no node in loop that's not input to safepoint");
 997       }
 998     }
 999     CountedLoopEndNode* cle = inner_out->in(0)->as_CountedLoopEnd();
1000     assert(cle == inner->loopexit_or_null(), "mismatch");
1001     bool has_skeleton = outer_le->in(1)->bottom_type()->singleton() && outer_le->in(1)->bottom_type()->is_int()->get_con() == 0;
1002     if (has_skeleton) {


1003       assert(expect_skeleton == 1 || expect_skeleton == -1, "unexpected skeleton node");
1004       assert(outer->outcnt() == 2, "only phis");
1005     } else {
1006       assert(expect_skeleton == 0 || expect_skeleton == -1, "no skeleton node?");
1007       uint phis = 0;
1008       for (DUIterator_Fast imax, i = inner->fast_outs(imax); i < imax; i++) {
1009         Node* u = inner->fast_out(i);
1010         if (u->is_Phi()) {
1011           phis++;
1012         }
1013       }
1014       for (DUIterator_Fast imax, i = outer->fast_outs(imax); i < imax; i++) {
1015         Node* u = outer->fast_out(i);
1016         assert(u == outer || u == inner || u->is_Phi(), "nothing between inner and outer loop");
1017       }

1018       uint stores = 0;
1019       for (DUIterator_Fast imax, i = inner_out->fast_outs(imax); i < imax; i++) {
1020         Node* u = inner_out->fast_out(i);
1021         if (u->is_Store()) {
1022           stores++;


1023         }

















1024       }
1025       assert(outer->outcnt() >= phis + 2 && outer->outcnt() <= phis + 2 + stores + 1, "only phis");
1026     }
1027     assert(sfpt->outcnt() == 1, "no data node");
1028     assert(outer_tail->outcnt() == 1 || !has_skeleton, "no data node");
1029   }
1030 #endif
1031 }
1032 
1033 //=============================================================================
1034 //------------------------------Ideal------------------------------------------
1035 // Return a node which is more "ideal" than the current node.
1036 // Attempt to convert into a counted-loop.
1037 Node *CountedLoopNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1038   return RegionNode::Ideal(phase, can_reshape);
1039 }
1040 
1041 //------------------------------dump_spec--------------------------------------
1042 // Dump special per-node info
1043 #ifndef PRODUCT


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
2881   while (_deadlist.size()) {
2882     _igvn.remove_globally_dead_node(_deadlist.pop());
2883   }
2884 
2885   if (stop_early) {
2886     assert(do_expensive_nodes, "why are we here?");
2887     if (process_expensive_nodes()) {
2888       // If we made some progress when processing expensive nodes then
2889       // the IGVN may modify the graph in a way that will allow us to


2896   }
2897 
2898   // Some parser-inserted loop predicates could never be used by loop
2899   // predication or they were moved away from loop during some optimizations.
2900   // For example, peeling. Eliminate them before next loop optimizations.
2901   eliminate_useless_predicates();
2902 
2903 #ifndef PRODUCT
2904   C->verify_graph_edges();
2905   if (_verify_me) {             // Nested verify pass?
2906     // Check to see if the verify mode is broken
2907     assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
2908     return;
2909   }
2910   if(VerifyLoopOptimizations) verify();
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 


4068 }
4069 
4070 //------------------------------clear_dom_lca_tags------------------------------
4071 // Tag could be a node's integer index, 32bits instead of 64bits in some cases
4072 // Intended use does not involve any growth for the array, so it could
4073 // be of fixed size.
4074 void PhaseIdealLoop::clear_dom_lca_tags() {
4075   uint limit = C->unique() + 1;
4076   _dom_lca_tags.map( limit, NULL );
4077   _dom_lca_tags.clear();
4078 #ifdef ASSERT
4079   for( uint i = 0; i < limit; ++i ) {
4080     assert(_dom_lca_tags[i] == NULL, "Must be distinct from each node pointer");
4081   }
4082 #endif // ASSERT
4083 }
4084 
4085 //------------------------------build_loop_late--------------------------------
4086 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
4087 // Second pass finds latest legal placement, and ideal loop placement.
4088 void PhaseIdealLoop::build_loop_late( VectorSet &visited, Node_List &worklist, Node_Stack &nstack ) {
4089   while (worklist.size() != 0) {
4090     Node *n = worklist.pop();
4091     // Only visit once
4092     if (visited.test_set(n->_idx)) continue;
4093     uint cnt = n->outcnt();
4094     uint   i = 0;
4095     while (true) {
4096       assert( _nodes[n->_idx], "no dead nodes" );
4097       // Visit all children
4098       if (i < cnt) {
4099         Node* use = n->raw_out(i);
4100         ++i;
4101         // Check for dead uses.  Aggressively prune such junk.  It might be
4102         // dead in the global sense, but still have local uses so I cannot
4103         // easily call 'remove_dead_node'.
4104         if( _nodes[use->_idx] != NULL || use->is_top() ) { // Not dead?
4105           // Due to cycles, we might not hit the same fixed point in the verify
4106           // pass as we do in the regular pass.  Instead, visit such phis as
4107           // simple uses of the loop head.
4108           if( use->in(0) && (use->is_CFG() || use->is_Phi()) ) {
4109             if( !visited.test(use->_idx) )
4110               worklist.push(use);
4111           } else if( !visited.test_set(use->_idx) ) {
4112             nstack.push(n, i); // Save parent and next use's index.
4113             n   = use;         // Process all children of current use.
4114             cnt = use->outcnt();
4115             i   = 0;
4116           }
4117         } else {
4118           // Do not visit around the backedge of loops via data edges.
4119           // push dead code onto a worklist
4120           _deadlist.push(use);
4121         }
4122       } else {
4123         // All of n's children have been processed, complete post-processing.
4124         build_loop_late_post(n);
4125         if (nstack.is_empty()) {
4126           // Finished all nodes on stack.
4127           // Process next node on the worklist.
4128           break;
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) {


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 }
4170 
4171 
4172 //------------------------------build_loop_late_post---------------------------
4173 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
4174 // Second pass finds latest legal placement, and ideal loop placement.
4175 void PhaseIdealLoop::build_loop_late_post( Node *n ) {
4176 
4177   if (n->req() == 2 && (n->Opcode() == Op_ConvI2L || n->Opcode() == Op_CastII) && !C->major_progress() && !_verify_only) {
4178     _igvn._worklist.push(n);  // Maybe we'll normalize it, if no more loops.
4179   }
4180 
4181 #ifdef ASSERT
4182   if (_verify_only && !n->is_CFG()) {
4183     // Check def-use domination.
4184     compute_lca_of_uses(n, get_ctrl(n), true /* verify */);
4185   }
4186 #endif
4187 
4188   // CFG and pinned nodes already handled
4189   if( n->in(0) ) {
4190     if( n->in(0)->is_top() ) return; // Dead?
4191 
4192     // We'd like +VerifyLoopOptimizations to not believe that Mod's/Loads
4193     // _must_ be pinned (they have to observe their control edge of course).
4194     // Unlike Stores (which modify an unallocable resource, the memory
4195     // state), Mods/Loads can float around.  So free them up.


4206     case Op_LoadUS:
4207     case Op_LoadD:
4208     case Op_LoadF:
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 


4311     }
4312   }
4313 
4314 #ifdef ASSERT
4315   // If verifying, verify that 'verify_me' has a legal location
4316   // and choose it as our location.
4317   if( _verify_me ) {
4318     Node *v_ctrl = _verify_me->get_ctrl_no_update(n);
4319     Node *legal = LCA;
4320     while( early != legal ) {   // While not at earliest legal
4321       if( legal == v_ctrl ) break;  // Check for prior good location
4322       legal = idom(legal)      ;// Bump up the IDOM tree
4323     }
4324     // Check for prior good location
4325     if( legal == v_ctrl ) least = legal; // Keep prior if found
4326   }
4327 #endif
4328 
4329   // Assign discovered "here or above" point
4330   least = find_non_split_ctrl(least);
4331   verify_strip_mined_scheduling(n, least);


4332   set_ctrl(n, least);
4333 
4334   // Collect inner loop bodies
4335   IdealLoopTree *chosen_loop = get_loop(least);
4336   if( !chosen_loop->_child )   // Inner loop?
4337     chosen_loop->_body.push(n);// Collect inner loops










4338 }
4339 
4340 #ifdef ASSERT
4341 void PhaseIdealLoop::dump_bad_graph(const char* msg, Node* n, Node* early, Node* LCA) {
4342   tty->print_cr("%s", msg);
4343   tty->print("n: "); n->dump();
4344   tty->print("early(n): "); early->dump();
4345   if (n->in(0) != NULL  && !n->in(0)->is_top() &&
4346       n->in(0) != early && !n->in(0)->is_Root()) {
4347     tty->print("n->in(0): "); n->in(0)->dump();
4348   }
4349   for (uint i = 1; i < n->req(); i++) {
4350     Node* in1 = n->in(i);
4351     if (in1 != NULL && in1 != n && !in1->is_top()) {
4352       tty->print("n->in(%d): ", i); in1->dump();
4353       Node* in1_early = get_ctrl(in1);
4354       tty->print("early(n->in(%d)): ", i); in1_early->dump();
4355       if (in1->in(0) != NULL     && !in1->in(0)->is_top() &&
4356           in1->in(0) != in1_early && !in1->in(0)->is_Root()) {
4357         tty->print("n->in(%d)->in(0): ", i); in1->in(0)->dump();


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 {


 983           continue;
 984         }
 985         wq.clear();
 986         wq.push(u);
 987         bool found_sfpt = false;
 988         for (uint next = 0; next < wq.size() && !found_sfpt; next++) {
 989           Node *n = wq.at(next);
 990           for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax && !found_sfpt; i++) {
 991             Node* u = n->fast_out(i);
 992             if (u == sfpt) {
 993               found_sfpt = true;
 994             }
 995             if (!u->is_CFG()) {
 996               wq.push(u);
 997             }
 998           }
 999         }
1000         assert(found_sfpt, "no node in loop that's not input to safepoint");
1001       }
1002     }


1003     bool has_skeleton = outer_le->in(1)->bottom_type()->singleton() && outer_le->in(1)->bottom_type()->is_int()->get_con() == 0;
1004     if (has_skeleton) {
1005       CountedLoopEndNode* cle = inner_out->in(0)->as_CountedLoopEnd();
1006       assert(cle == inner->loopexit_or_null(), "mismatch");
1007       assert(expect_skeleton == 1 || expect_skeleton == -1, "unexpected skeleton node");
1008       assert(outer->outcnt() == 2, "only phis");
1009     } else {
1010       assert(expect_skeleton == 0 || expect_skeleton == -1, "no skeleton node?");
1011       uint phis = 0;
1012       for (DUIterator_Fast imax, i = inner->fast_outs(imax); i < imax; i++) {
1013         Node* u = inner->fast_out(i);
1014         if (u->is_Phi()) {
1015           phis++;
1016         }
1017       }
1018       for (DUIterator_Fast imax, i = outer->fast_outs(imax); i < imax; i++) {
1019         Node* u = outer->fast_out(i);
1020         assert(u == outer || u == inner || u->is_Phi(), "nothing between inner and outer loop");
1021       }
1022       Node* c = inner_out;
1023       uint stores = 0;
1024       for (;;) {
1025         for (DUIterator_Fast imax, i = c->fast_outs(imax); i < imax; i++) {
1026           Node* u = c->fast_out(i);
1027           if (u->is_Store()) {
1028             stores++;
1029           }
1030         }
1031         if (c->in(0)->is_CountedLoopEnd() || !UseShenandoahGC) {
1032           break;
1033         }
1034 #if INCLUDE_SHENANDOAHGC
1035         assert(UseShenandoahGC, "only for shenandoah barriers");
1036         assert(c->is_Region() && c->req() == 3, "region that ends barrier");
1037         uint j = 1;
1038         uint req = c->req();
1039         for (; j < req; j++) {
1040           Node* in = c->in(j);
1041           if (in->is_IfProj() && ShenandoahWriteBarrierNode::is_heap_stable_test(in->in(0))) {
1042             c = in->in(0)->in(0);
1043             break;
1044           }
1045         }
1046         assert(j < req, "should have found heap stable test");
1047 #endif
1048       }
1049       assert(outer->outcnt() >= phis + 2 && outer->outcnt() <= phis + 2 + stores + 1, "only phis");
1050     }
1051     assert(sfpt->outcnt() == 1, "no data node");
1052     assert(outer_tail->outcnt() == 1 || !has_skeleton, "no data node");
1053   }
1054 #endif
1055 }
1056 
1057 //=============================================================================
1058 //------------------------------Ideal------------------------------------------
1059 // Return a node which is more "ideal" than the current node.
1060 // Attempt to convert into a counted-loop.
1061 Node *CountedLoopNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1062   return RegionNode::Ideal(phase, can_reshape);
1063 }
1064 
1065 //------------------------------dump_spec--------------------------------------
1066 // Dump special per-node info
1067 #ifndef PRODUCT


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


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


2868 
2869   // Walk the DATA nodes and place into loops.  Find earliest control
2870   // node.  For CFG nodes, the _nodes array starts out and remains
2871   // holding the associated IdealLoopTree pointer.  For DATA nodes, the
2872   // _nodes array holds the earliest legal controlling CFG node.
2873 
2874   // Allocate stack with enough space to avoid frequent realloc
2875   int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
2876   Node_Stack nstack( a, stack_size );
2877 
2878   visited.Clear();
2879   Node_List worklist(a);
2880   // Don't need C->root() on worklist since
2881   // it will be processed among C->top() inputs
2882   worklist.push( C->top() );
2883   visited.set( C->top()->_idx ); // Set C->top() as visited now
2884   build_loop_early( visited, worklist, nstack );
2885 
2886   // Given early legal placement, try finding counted loops.  This placement
2887   // is good enough to discover most loop invariants.
2888   if (!_verify_me && !_verify_only && !shenandoah_opts) {
2889     _ltree_root->counted_loop(this);
2890   }
2891 
2892   // Find latest loop placement.  Find ideal loop placement.
2893   visited.Clear();
2894   init_dom_lca_tags();
2895   // Need C->root() on worklist when processing outs
2896   worklist.push( C->root() );
2897   NOT_PRODUCT( C->verify_graph_edges(); )
2898   worklist.push( C->top() );
2899   build_loop_late(visited, worklist, nstack, !shenandoah_opts);
2900 
2901   if (_verify_only) {
2902     // restore major progress flag
2903     for (int i = 0; i < old_progress; i++)
2904       C->set_major_progress();
2905     assert(C->unique() == unique, "verification mode made Nodes? ? ?");
2906     assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
2907     return;
2908   }
2909 
2910   // clear out the dead code after build_loop_late
2911   while (_deadlist.size()) {
2912     _igvn.remove_globally_dead_node(_deadlist.pop());
2913   }
2914 
2915   if (stop_early) {
2916     assert(do_expensive_nodes, "why are we here?");
2917     if (process_expensive_nodes()) {
2918       // If we made some progress when processing expensive nodes then
2919       // the IGVN may modify the graph in a way that will allow us to


2926   }
2927 
2928   // Some parser-inserted loop predicates could never be used by loop
2929   // predication or they were moved away from loop during some optimizations.
2930   // For example, peeling. Eliminate them before next loop optimizations.
2931   eliminate_useless_predicates();
2932 
2933 #ifndef PRODUCT
2934   C->verify_graph_edges();
2935   if (_verify_me) {             // Nested verify pass?
2936     // Check to see if the verify mode is broken
2937     assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
2938     return;
2939   }
2940   if(VerifyLoopOptimizations) verify();
2941   if(TraceLoopOpts && C->has_loops()) {
2942     _ltree_root->dump();
2943   }
2944 #endif
2945 
2946 #if INCLUDE_SHENANDOAHGC
2947   if (mode == LoopOptsShenandoahExpand) {
2948     assert(UseShenandoahGC, "only for shenandoah");
2949     ShenandoahWriteBarrierNode::pin_and_expand(this);
2950   } else if (mode == LoopOptsShenandoahPostExpand) {
2951     assert(UseShenandoahGC, "only for shenandoah");
2952     visited.Clear();
2953     ShenandoahWriteBarrierNode::optimize_after_expansion(visited, nstack, worklist, this);
2954   }
2955 
2956   if (shenandoah_opts) {
2957     _igvn.optimize();
2958     if (C->log() != NULL) {
2959       log_loop_tree(_ltree_root, _ltree_root, C->log());
2960     }
2961     return;
2962   }
2963 #endif
2964 
2965   if (skip_loop_opts) {
2966     // restore major progress flag
2967     for (int i = 0; i < old_progress; i++) {
2968       C->set_major_progress();
2969     }
2970 
2971     // Cleanup any modified bits
2972     _igvn.optimize();
2973 
2974     if (C->log() != NULL) {
2975       log_loop_tree(_ltree_root, _ltree_root, C->log());
2976     }
2977     return;
2978   }
2979 
2980 #if INCLUDE_SHENANDOAHGC
2981   if (UseShenandoahGC) {
2982     GrowableArray<MemoryGraphFixer*> memory_graph_fixers;
2983     ShenandoahWriteBarrierNode::optimize_before_expansion(this, memory_graph_fixers, false);
2984   }
2985 #endif
2986 
2987   if (ReassociateInvariants) {
2988     // Reassociate invariants and prep for split_thru_phi
2989     for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
2990       IdealLoopTree* lpt = iter.current();
2991       bool is_counted = lpt->is_counted();
2992       if (!is_counted || !lpt->is_inner()) continue;
2993 
2994       // check for vectorized loops, any reassociation of invariants was already done
2995       if (is_counted && lpt->_head->as_CountedLoop()->do_unroll_only()) continue;
2996 
2997       lpt->reassociate_invariants(this);
2998 
2999       // Because RCE opportunities can be masked by split_thru_phi,
3000       // look for RCE candidates and inhibit split_thru_phi
3001       // on just their loop-phi's for this pass of loop opts
3002       if (SplitIfBlocks && do_split_ifs) {
3003         if (lpt->policy_range_check(this)) {
3004           lpt->_rce_candidate = 1; // = true
3005         }
3006       }
3007     }
3008   }
3009 
3010   // Check for aggressive application of split-if and other transforms
3011   // that require basic-block info (like cloning through Phi's)
3012   if( SplitIfBlocks && do_split_ifs ) {
3013     visited.Clear();
3014     split_if_with_blocks( visited, nstack, mode == LoopOptsZgcLastRound );
3015     NOT_PRODUCT( if( VerifyLoopOptimizations ) verify(); );
3016     if (mode == LoopOptsZgcLastRound) {
3017       C->set_major_progress();
3018     }
3019   }
3020 
3021   if (!C->major_progress() && do_expensive_nodes && process_expensive_nodes()) {
3022     C->set_major_progress();
3023   }
3024 
3025   // Perform loop predication before iteration splitting
3026   if (C->has_loops() && !C->major_progress() && (C->predicate_count() > 0)) {
3027     _ltree_root->_child->loop_predication(this);
3028   }
3029 
3030   if (OptimizeFill && UseLoopPredicate && C->has_loops() && !C->major_progress()) {
3031     if (do_intrinsify_fill()) {
3032       C->set_major_progress();
3033     }
3034   }
3035 
3036   // Perform iteration-splitting on inner loops.  Split iterations to avoid


3997     compute_lca_of_uses(n, early, true);
3998   }
3999 #endif
4000 
4001   // if this is a load, check for anti-dependent stores
4002   // We use a conservative algorithm to identify potential interfering
4003   // instructions and for rescheduling the load.  The users of the memory
4004   // input of this load are examined.  Any use which is not a load and is
4005   // dominated by early is considered a potentially interfering store.
4006   // This can produce false positives.
4007   if (n->is_Load() && LCA != early) {
4008     Node_List worklist;
4009 
4010     Node *mem = n->in(MemNode::Memory);
4011     for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
4012       Node* s = mem->fast_out(i);
4013       worklist.push(s);
4014     }
4015     while(worklist.size() != 0 && LCA != early) {
4016       Node* s = worklist.pop();
4017       if (s->is_Load() || s->is_ShenandoahBarrier() || s->Opcode() == Op_SafePoint ||
4018           (UseShenandoahGC && s->is_CallStaticJava() && s->as_CallStaticJava()->uncommon_trap_request() != 0)) {
4019         continue;
4020       } else if (s->is_MergeMem()) {
4021         for (DUIterator_Fast imax, i = s->fast_outs(imax); i < imax; i++) {
4022           Node* s1 = s->fast_out(i);
4023           worklist.push(s1);
4024         }
4025       } else {
4026         Node *sctrl = has_ctrl(s) ? get_ctrl(s) : s->in(0);
4027         assert(sctrl != NULL || s->outcnt() == 0, "must have control");
4028         if (sctrl != NULL && !sctrl->is_top() && is_dominator(early, sctrl)) {
4029           LCA = dom_lca_for_get_late_ctrl(LCA, sctrl, n);
4030         }
4031       }
4032     }
4033   }
4034 
4035   assert(LCA == find_non_split_ctrl(LCA), "unexpected late control");
4036   return LCA;
4037 }
4038 


4125 }
4126 
4127 //------------------------------clear_dom_lca_tags------------------------------
4128 // Tag could be a node's integer index, 32bits instead of 64bits in some cases
4129 // Intended use does not involve any growth for the array, so it could
4130 // be of fixed size.
4131 void PhaseIdealLoop::clear_dom_lca_tags() {
4132   uint limit = C->unique() + 1;
4133   _dom_lca_tags.map( limit, NULL );
4134   _dom_lca_tags.clear();
4135 #ifdef ASSERT
4136   for( uint i = 0; i < limit; ++i ) {
4137     assert(_dom_lca_tags[i] == NULL, "Must be distinct from each node pointer");
4138   }
4139 #endif // ASSERT
4140 }
4141 
4142 //------------------------------build_loop_late--------------------------------
4143 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
4144 // Second pass finds latest legal placement, and ideal loop placement.
4145 void PhaseIdealLoop::build_loop_late(VectorSet &visited, Node_List &worklist, Node_Stack &nstack, bool verify_strip_mined) {
4146   while (worklist.size() != 0) {
4147     Node *n = worklist.pop();
4148     // Only visit once
4149     if (visited.test_set(n->_idx)) continue;
4150     uint cnt = n->outcnt();
4151     uint   i = 0;
4152     while (true) {
4153       assert( _nodes[n->_idx], "no dead nodes" );
4154       // Visit all children
4155       if (i < cnt) {
4156         Node* use = n->raw_out(i);
4157         ++i;
4158         // Check for dead uses.  Aggressively prune such junk.  It might be
4159         // dead in the global sense, but still have local uses so I cannot
4160         // easily call 'remove_dead_node'.
4161         if( _nodes[use->_idx] != NULL || use->is_top() ) { // Not dead?
4162           // Due to cycles, we might not hit the same fixed point in the verify
4163           // pass as we do in the regular pass.  Instead, visit such phis as
4164           // simple uses of the loop head.
4165           if( use->in(0) && (use->is_CFG() || use->is_Phi()) ) {
4166             if( !visited.test(use->_idx) )
4167               worklist.push(use);
4168           } else if( !visited.test_set(use->_idx) ) {
4169             nstack.push(n, i); // Save parent and next use's index.
4170             n   = use;         // Process all children of current use.
4171             cnt = use->outcnt();
4172             i   = 0;
4173           }
4174         } else {
4175           // Do not visit around the backedge of loops via data edges.
4176           // push dead code onto a worklist
4177           _deadlist.push(use);
4178         }
4179       } else {
4180         // All of n's children have been processed, complete post-processing.
4181         build_loop_late_post(n, verify_strip_mined);
4182         if (nstack.is_empty()) {
4183           // Finished all nodes on stack.
4184           // Process next node on the worklist.
4185           break;
4186         }
4187         // Get saved parent node and next use's index. Visit the rest of uses.
4188         n   = nstack.node();
4189         cnt = n->outcnt();
4190         i   = nstack.index();
4191         nstack.pop();
4192       }
4193     }
4194   }
4195 }
4196 
4197 // Verify that no data node is schedules in the outer loop of a strip
4198 // mined loop.
4199 void PhaseIdealLoop::verify_strip_mined_scheduling(Node *n, Node* least) {
4200 #ifdef ASSERT
4201   if (get_loop(least)->_nest == 0) {


4212       Node *m = wq.at(i);
4213       for (uint i = 1; i < m->req(); i++) {
4214         Node* nn = m->in(i);
4215         if (nn == n) {
4216           return;
4217         }
4218         if (nn != NULL && has_ctrl(nn) && get_loop(get_ctrl(nn)) == loop) {
4219           wq.push(nn);
4220         }
4221       }
4222     }
4223     ShouldNotReachHere();
4224   }
4225 #endif
4226 }
4227 
4228 
4229 //------------------------------build_loop_late_post---------------------------
4230 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
4231 // Second pass finds latest legal placement, and ideal loop placement.
4232 void PhaseIdealLoop::build_loop_late_post(Node *n, bool verify_strip_mined) {
4233 
4234   if (n->req() == 2 && (n->Opcode() == Op_ConvI2L || n->Opcode() == Op_CastII) && !C->major_progress() && !_verify_only) {
4235     _igvn._worklist.push(n);  // Maybe we'll normalize it, if no more loops.
4236   }
4237 
4238 #ifdef ASSERT
4239   if (_verify_only && !n->is_CFG()) {
4240     // Check def-use domination.
4241     compute_lca_of_uses(n, get_ctrl(n), true /* verify */);
4242   }
4243 #endif
4244 
4245   // CFG and pinned nodes already handled
4246   if( n->in(0) ) {
4247     if( n->in(0)->is_top() ) return; // Dead?
4248 
4249     // We'd like +VerifyLoopOptimizations to not believe that Mod's/Loads
4250     // _must_ be pinned (they have to observe their control edge of course).
4251     // Unlike Stores (which modify an unallocable resource, the memory
4252     // state), Mods/Loads can float around.  So free them up.


4263     case Op_LoadUS:
4264     case Op_LoadD:
4265     case Op_LoadF:
4266     case Op_LoadI:
4267     case Op_LoadKlass:
4268     case Op_LoadNKlass:
4269     case Op_LoadL:
4270     case Op_LoadS:
4271     case Op_LoadP:
4272     case Op_LoadBarrierSlowReg:
4273     case Op_LoadBarrierWeakSlowReg:
4274     case Op_LoadN:
4275     case Op_LoadRange:
4276     case Op_LoadD_unaligned:
4277     case Op_LoadL_unaligned:
4278     case Op_StrComp:            // Does a bunch of load-like effects
4279     case Op_StrEquals:
4280     case Op_StrIndexOf:
4281     case Op_StrIndexOfChar:
4282     case Op_AryEq:
4283 #if INCLUDE_SHENANDOAHGC
4284     case Op_ShenandoahReadBarrier:
4285     case Op_ShenandoahWriteBarrier:
4286     case Op_ShenandoahWBMemProj:
4287 #endif
4288     case Op_HasNegatives:
4289       pinned = false;
4290     }
4291     if( pinned ) {
4292       IdealLoopTree *chosen_loop = get_loop(n->is_CFG() ? n : get_ctrl(n));
4293       if( !chosen_loop->_child )       // Inner loop?
4294         chosen_loop->_body.push(n); // Collect inner loops
4295       return;
4296     }
4297   } else {                      // No slot zero
4298     if( n->is_CFG() ) {         // CFG with no slot 0 is dead
4299       _nodes.map(n->_idx,0);    // No block setting, it's globally dead
4300       return;
4301     }
4302     assert(!n->is_CFG() || n->outcnt() == 0, "");
4303   }
4304 
4305   // Do I have a "safe range" I can select over?
4306   Node *early = get_ctrl(n);// Early location already computed
4307 


4373     }
4374   }
4375 
4376 #ifdef ASSERT
4377   // If verifying, verify that 'verify_me' has a legal location
4378   // and choose it as our location.
4379   if( _verify_me ) {
4380     Node *v_ctrl = _verify_me->get_ctrl_no_update(n);
4381     Node *legal = LCA;
4382     while( early != legal ) {   // While not at earliest legal
4383       if( legal == v_ctrl ) break;  // Check for prior good location
4384       legal = idom(legal)      ;// Bump up the IDOM tree
4385     }
4386     // Check for prior good location
4387     if( legal == v_ctrl ) least = legal; // Keep prior if found
4388   }
4389 #endif
4390 
4391   // Assign discovered "here or above" point
4392   least = find_non_split_ctrl(least);
4393   if (verify_strip_mined && !_verify_only) {
4394     verify_strip_mined_scheduling(n, least);
4395   }
4396   set_ctrl(n, least);
4397 
4398   // Collect inner loop bodies
4399   IdealLoopTree *chosen_loop = get_loop(least);
4400   if( !chosen_loop->_child )   // Inner loop?
4401     chosen_loop->_body.push(n);// Collect inner loops
4402 
4403   if (n->Opcode() == Op_ShenandoahWriteBarrier) {
4404     // The write barrier and its memory proj must have the same
4405     // control otherwise some loop opts could put nodes (Phis) between
4406     // them
4407     Node* proj = n->find_out_with(Op_ShenandoahWBMemProj);
4408     if (proj != NULL) {
4409       set_ctrl_and_loop(proj, least);
4410     }
4411   }
4412 }
4413 
4414 #ifdef ASSERT
4415 void PhaseIdealLoop::dump_bad_graph(const char* msg, Node* n, Node* early, Node* LCA) {
4416   tty->print_cr("%s", msg);
4417   tty->print("n: "); n->dump();
4418   tty->print("early(n): "); early->dump();
4419   if (n->in(0) != NULL  && !n->in(0)->is_top() &&
4420       n->in(0) != early && !n->in(0)->is_Root()) {
4421     tty->print("n->in(0): "); n->in(0)->dump();
4422   }
4423   for (uint i = 1; i < n->req(); i++) {
4424     Node* in1 = n->in(i);
4425     if (in1 != NULL && in1 != n && !in1->is_top()) {
4426       tty->print("n->in(%d): ", i); in1->dump();
4427       Node* in1_early = get_ctrl(in1);
4428       tty->print("early(n->in(%d)): ", i); in1_early->dump();
4429       if (in1->in(0) != NULL     && !in1->in(0)->is_top() &&
4430           in1->in(0) != in1_early && !in1->in(0)->is_Root()) {
4431         tty->print("n->in(%d)->in(0): ", i); in1->in(0)->dump();


4547     }
4548     // Dump nodes it controls
4549     for( uint k = 0; k < _nodes.Size(); k++ ) {
4550       // (k < C->unique() && get_ctrl(find(k)) == n)
4551       if (k < C->unique() && _nodes[k] == (Node*)((intptr_t)n + 1)) {
4552         Node *m = C->root()->find(k);
4553         if( m && m->outcnt() > 0 ) {
4554           if (!(has_ctrl(m) && get_ctrl_no_update(m) == n)) {
4555             tty->print_cr("*** BROKEN CTRL ACCESSOR!  _nodes[k] is %p, ctrl is %p",
4556                           _nodes[k], has_ctrl(m) ? get_ctrl_no_update(m) : NULL);
4557           }
4558           for( uint j = 0; j < loop->_nest; j++ )
4559             tty->print("  ");
4560           tty->print(" ");
4561           m->dump();
4562         }
4563       }
4564     }
4565   }
4566 }
4567 #endif
4568 
4569 // Collect a R-P-O for the whole CFG.
4570 // Result list is in post-order (scan backwards for RPO)
4571 void PhaseIdealLoop::rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const {
4572   stk.push(start, 0);
4573   visited.set(start->_idx);
4574 
4575   while (stk.is_nonempty()) {
4576     Node* m   = stk.node();
4577     uint  idx = stk.index();
4578     if (idx < m->outcnt()) {
4579       stk.set_index(idx + 1);
4580       Node* n = m->raw_out(idx);
4581       if (n->is_CFG() && !visited.test_set(n->_idx)) {
4582         stk.push(n, 0);
4583       }
4584     } else {
4585       rpo_list.push(m);
4586       stk.pop();
4587     }
4588   }
4589 }

4590 
4591 
4592 //=============================================================================
4593 //------------------------------LoopTreeIterator-----------------------------------
4594 
4595 // Advance to next loop tree using a preorder, left-to-right traversal.
4596 void LoopTreeIterator::next() {
4597   assert(!done(), "must not be done.");
4598   if (_curnt->_child != NULL) {
4599     _curnt = _curnt->_child;
4600   } else if (_curnt->_next != NULL) {
4601     _curnt = _curnt->_next;
4602   } else {
4603     while (_curnt != _root && _curnt->_next == NULL) {
4604       _curnt = _curnt->_parent;
4605     }
4606     if (_curnt == _root) {
4607       _curnt = NULL;
4608       assert(done(), "must be done.");
4609     } else {
< prev index next >