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
2694 n2->set_req(0, c2);
2695 _igvn.hash_insert(n2);
2696 _igvn._worklist.push(n2);
2697 progress = true;
2698 }
2699 }
2700 }
2701 }
2702
2703 return progress;
2704 }
2705
2706
2707 //=============================================================================
2708 //----------------------------build_and_optimize-------------------------------
2709 // Create a PhaseLoop. Build the ideal Loop tree. Map each Ideal Node to
2710 // its corresponding LoopNode. If 'optimize' is true, do some loop cleanups.
2711 void PhaseIdealLoop::build_and_optimize(LoopOptsMode mode) {
2712 bool do_split_ifs = (mode == LoopOptsDefault || mode == LoopOptsLastRound);
2713 bool skip_loop_opts = (mode == LoopOptsNone);
2714
2715 ResourceMark rm;
2716
2717 int old_progress = C->major_progress();
2718 uint orig_worklist_size = _igvn._worklist.size();
2719
2720 // Reset major-progress flag for the driver's heuristics
2721 C->clear_major_progress();
2722
2723 #ifndef PRODUCT
2724 // Capture for later assert
2725 uint unique = C->unique();
2726 _loop_invokes++;
2727 _loop_work += unique;
2728 #endif
2729
2730 // True if the method has at least 1 irreducible loop
2731 _has_irreducible_loops = false;
2732
2733 _created_loop_node = false;
2758 build_loop_tree();
2759 // Check for bailout, and return
2760 if (C->failing()) {
2761 return;
2762 }
2763
2764 // No loops after all
2765 if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
2766
2767 // There should always be an outer loop containing the Root and Return nodes.
2768 // If not, we have a degenerate empty program. Bail out in this case.
2769 if (!has_node(C->root())) {
2770 if (!_verify_only) {
2771 C->clear_major_progress();
2772 C->record_method_not_compilable("empty program detected during loop optimization");
2773 }
2774 return;
2775 }
2776
2777 // Nothing to do, so get out
2778 bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !_verify_me && !_verify_only;
2779 bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
2780 if (stop_early && !do_expensive_nodes) {
2781 _igvn.optimize(); // Cleanup NeverBranches
2782 return;
2783 }
2784
2785 // Set loop nesting depth
2786 _ltree_root->set_nest( 0 );
2787
2788 // Split shared headers and insert loop landing pads.
2789 // Do not bother doing this on the Root loop of course.
2790 if( !_verify_me && !_verify_only && _ltree_root->_child ) {
2791 C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
2792 if( _ltree_root->_child->beautify_loops( this ) ) {
2793 // Re-build loop tree!
2794 _ltree_root->_child = NULL;
2795 _nodes.clear();
2796 reallocate_preorders();
2797 build_loop_tree();
2798 // Check for bailout, and return
2837
2838 // Walk the DATA nodes and place into loops. Find earliest control
2839 // node. For CFG nodes, the _nodes array starts out and remains
2840 // holding the associated IdealLoopTree pointer. For DATA nodes, the
2841 // _nodes array holds the earliest legal controlling CFG node.
2842
2843 // Allocate stack with enough space to avoid frequent realloc
2844 int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
2845 Node_Stack nstack( a, stack_size );
2846
2847 visited.Clear();
2848 Node_List worklist(a);
2849 // Don't need C->root() on worklist since
2850 // it will be processed among C->top() inputs
2851 worklist.push( C->top() );
2852 visited.set( C->top()->_idx ); // Set C->top() as visited now
2853 build_loop_early( visited, worklist, nstack );
2854
2855 // Given early legal placement, try finding counted loops. This placement
2856 // is good enough to discover most loop invariants.
2857 if( !_verify_me && !_verify_only )
2858 _ltree_root->counted_loop( this );
2859
2860 // Find latest loop placement. Find ideal loop placement.
2861 visited.Clear();
2862 init_dom_lca_tags();
2863 // Need C->root() on worklist when processing outs
2864 worklist.push( C->root() );
2865 NOT_PRODUCT( C->verify_graph_edges(); )
2866 worklist.push( C->top() );
2867 build_loop_late( visited, worklist, nstack );
2868
2869 if (_verify_only) {
2870 // restore major progress flag
2871 for (int i = 0; i < old_progress; i++)
2872 C->set_major_progress();
2873 assert(C->unique() == unique, "verification mode made Nodes? ? ?");
2874 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
2875 return;
2876 }
2877
2878 // clear out the dead code after build_loop_late
2879 while (_deadlist.size()) {
2880 _igvn.remove_globally_dead_node(_deadlist.pop());
2881 }
2882
2883 if (stop_early) {
2884 assert(do_expensive_nodes, "why are we here?");
2885 if (process_expensive_nodes()) {
2886 // If we made some progress when processing expensive nodes then
2887 // the IGVN may modify the graph in a way that will allow us to
2894 }
2895
2896 // Some parser-inserted loop predicates could never be used by loop
2897 // predication or they were moved away from loop during some optimizations.
2898 // For example, peeling. Eliminate them before next loop optimizations.
2899 eliminate_useless_predicates();
2900
2901 #ifndef PRODUCT
2902 C->verify_graph_edges();
2903 if (_verify_me) { // Nested verify pass?
2904 // Check to see if the verify mode is broken
2905 assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
2906 return;
2907 }
2908 if(VerifyLoopOptimizations) verify();
2909 if(TraceLoopOpts && C->has_loops()) {
2910 _ltree_root->dump();
2911 }
2912 #endif
2913
2914 if (skip_loop_opts) {
2915 // restore major progress flag
2916 for (int i = 0; i < old_progress; i++) {
2917 C->set_major_progress();
2918 }
2919
2920 // Cleanup any modified bits
2921 _igvn.optimize();
2922
2923 if (C->log() != NULL) {
2924 log_loop_tree(_ltree_root, _ltree_root, C->log());
2925 }
2926 return;
2927 }
2928
2929 if (ReassociateInvariants) {
2930 // Reassociate invariants and prep for split_thru_phi
2931 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
2932 IdealLoopTree* lpt = iter.current();
2933 bool is_counted = lpt->is_counted();
2934 if (!is_counted || !lpt->is_inner()) continue;
2935
2936 // check for vectorized loops, any reassociation of invariants was already done
2937 if (is_counted && lpt->_head->as_CountedLoop()->do_unroll_only()) continue;
2938
2939 lpt->reassociate_invariants(this);
2940
2941 // Because RCE opportunities can be masked by split_thru_phi,
2942 // look for RCE candidates and inhibit split_thru_phi
2943 // on just their loop-phi's for this pass of loop opts
2944 if (SplitIfBlocks && do_split_ifs) {
2945 if (lpt->policy_range_check(this)) {
2946 lpt->_rce_candidate = 1; // = true
2947 }
2948 }
3939 compute_lca_of_uses(n, early, true);
3940 }
3941 #endif
3942
3943 // if this is a load, check for anti-dependent stores
3944 // We use a conservative algorithm to identify potential interfering
3945 // instructions and for rescheduling the load. The users of the memory
3946 // input of this load are examined. Any use which is not a load and is
3947 // dominated by early is considered a potentially interfering store.
3948 // This can produce false positives.
3949 if (n->is_Load() && LCA != early) {
3950 Node_List worklist;
3951
3952 Node *mem = n->in(MemNode::Memory);
3953 for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
3954 Node* s = mem->fast_out(i);
3955 worklist.push(s);
3956 }
3957 while(worklist.size() != 0 && LCA != early) {
3958 Node* s = worklist.pop();
3959 if (s->is_Load() || s->Opcode() == Op_SafePoint ||
3960 (s->is_CallStaticJava() && s->as_CallStaticJava()->uncommon_trap_request() != 0)) {
3961 continue;
3962 } else if (s->is_MergeMem()) {
3963 for (DUIterator_Fast imax, i = s->fast_outs(imax); i < imax; i++) {
3964 Node* s1 = s->fast_out(i);
3965 worklist.push(s1);
3966 }
3967 } else {
3968 Node *sctrl = has_ctrl(s) ? get_ctrl(s) : s->in(0);
3969 assert(sctrl != NULL || s->outcnt() == 0, "must have control");
3970 if (sctrl != NULL && !sctrl->is_top() && is_dominator(early, sctrl)) {
3971 LCA = dom_lca_for_get_late_ctrl(LCA, sctrl, n);
3972 }
3973 }
3974 }
3975 }
3976
3977 assert(LCA == find_non_split_ctrl(LCA), "unexpected late control");
3978 return LCA;
3979 }
3980
3981 // true if CFG node d dominates CFG node n
3982 bool PhaseIdealLoop::is_dominator(Node *d, Node *n) {
3983 if (d == n)
3984 return true;
3985 assert(d->is_CFG() && n->is_CFG(), "must have CFG nodes");
3986 uint dd = dom_depth(d);
3987 while (dom_depth(n) >= dd) {
3988 if (n == d)
3989 return true;
4067 }
4068
4069 //------------------------------clear_dom_lca_tags------------------------------
4070 // Tag could be a node's integer index, 32bits instead of 64bits in some cases
4071 // Intended use does not involve any growth for the array, so it could
4072 // be of fixed size.
4073 void PhaseIdealLoop::clear_dom_lca_tags() {
4074 uint limit = C->unique() + 1;
4075 _dom_lca_tags.map( limit, NULL );
4076 _dom_lca_tags.clear();
4077 #ifdef ASSERT
4078 for( uint i = 0; i < limit; ++i ) {
4079 assert(_dom_lca_tags[i] == NULL, "Must be distinct from each node pointer");
4080 }
4081 #endif // ASSERT
4082 }
4083
4084 //------------------------------build_loop_late--------------------------------
4085 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
4086 // Second pass finds latest legal placement, and ideal loop placement.
4087 void PhaseIdealLoop::build_loop_late( VectorSet &visited, Node_List &worklist, Node_Stack &nstack ) {
4088 while (worklist.size() != 0) {
4089 Node *n = worklist.pop();
4090 // Only visit once
4091 if (visited.test_set(n->_idx)) continue;
4092 uint cnt = n->outcnt();
4093 uint i = 0;
4094 while (true) {
4095 assert( _nodes[n->_idx], "no dead nodes" );
4096 // Visit all children
4097 if (i < cnt) {
4098 Node* use = n->raw_out(i);
4099 ++i;
4100 // Check for dead uses. Aggressively prune such junk. It might be
4101 // dead in the global sense, but still have local uses so I cannot
4102 // easily call 'remove_dead_node'.
4103 if( _nodes[use->_idx] != NULL || use->is_top() ) { // Not dead?
4104 // Due to cycles, we might not hit the same fixed point in the verify
4105 // pass as we do in the regular pass. Instead, visit such phis as
4106 // simple uses of the loop head.
4107 if( use->in(0) && (use->is_CFG() || use->is_Phi()) ) {
4108 if( !visited.test(use->_idx) )
4109 worklist.push(use);
4110 } else if( !visited.test_set(use->_idx) ) {
4111 nstack.push(n, i); // Save parent and next use's index.
4112 n = use; // Process all children of current use.
4113 cnt = use->outcnt();
4114 i = 0;
4115 }
4116 } else {
4117 // Do not visit around the backedge of loops via data edges.
4118 // push dead code onto a worklist
4119 _deadlist.push(use);
4120 }
4121 } else {
4122 // All of n's children have been processed, complete post-processing.
4123 build_loop_late_post(n);
4124 if (nstack.is_empty()) {
4125 // Finished all nodes on stack.
4126 // Process next node on the worklist.
4127 break;
4128 }
4129 // Get saved parent node and next use's index. Visit the rest of uses.
4130 n = nstack.node();
4131 cnt = n->outcnt();
4132 i = nstack.index();
4133 nstack.pop();
4134 }
4135 }
4136 }
4137 }
4138
4139 // Verify that no data node is schedules in the outer loop of a strip
4140 // mined loop.
4141 void PhaseIdealLoop::verify_strip_mined_scheduling(Node *n, Node* least) {
4142 #ifdef ASSERT
4143 if (get_loop(least)->_nest == 0) {
4144 return;
4145 }
4146 IdealLoopTree* loop = get_loop(least);
4147 Node* head = loop->_head;
4148 if (head->is_OuterStripMinedLoop()) {
4149 Node* sfpt = head->as_Loop()->outer_safepoint();
4150 ResourceMark rm;
4151 Unique_Node_List wq;
4152 wq.push(sfpt);
4153 for (uint i = 0; i < wq.size(); i++) {
4154 Node *m = wq.at(i);
4155 for (uint i = 1; i < m->req(); i++) {
4156 Node* nn = m->in(i);
4157 if (nn == n) {
4158 return;
4159 }
4160 if (nn != NULL && has_ctrl(nn) && get_loop(get_ctrl(nn)) == loop) {
4161 wq.push(nn);
4162 }
4163 }
4164 }
4165 ShouldNotReachHere();
4166 }
4167 #endif
4168 }
4169
4170
4171 //------------------------------build_loop_late_post---------------------------
4172 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
4173 // Second pass finds latest legal placement, and ideal loop placement.
4174 void PhaseIdealLoop::build_loop_late_post( Node *n ) {
4175
4176 if (n->req() == 2 && (n->Opcode() == Op_ConvI2L || n->Opcode() == Op_CastII) && !C->major_progress() && !_verify_only) {
4177 _igvn._worklist.push(n); // Maybe we'll normalize it, if no more loops.
4178 }
4179
4180 #ifdef ASSERT
4181 if (_verify_only && !n->is_CFG()) {
4182 // Check def-use domination.
4183 compute_lca_of_uses(n, get_ctrl(n), true /* verify */);
4184 }
4185 #endif
4186
4187 // CFG and pinned nodes already handled
4188 if( n->in(0) ) {
4189 if( n->in(0)->is_top() ) return; // Dead?
4190
4191 // We'd like +VerifyLoopOptimizations to not believe that Mod's/Loads
4192 // _must_ be pinned (they have to observe their control edge of course).
4193 // Unlike Stores (which modify an unallocable resource, the memory
4194 // state), Mods/Loads can float around. So free them up.
4205 case Op_LoadUS:
4206 case Op_LoadD:
4207 case Op_LoadF:
4208 case Op_LoadI:
4209 case Op_LoadKlass:
4210 case Op_LoadNKlass:
4211 case Op_LoadL:
4212 case Op_LoadS:
4213 case Op_LoadP:
4214 case Op_LoadBarrierSlowReg:
4215 case Op_LoadBarrierWeakSlowReg:
4216 case Op_LoadN:
4217 case Op_LoadRange:
4218 case Op_LoadD_unaligned:
4219 case Op_LoadL_unaligned:
4220 case Op_StrComp: // Does a bunch of load-like effects
4221 case Op_StrEquals:
4222 case Op_StrIndexOf:
4223 case Op_StrIndexOfChar:
4224 case Op_AryEq:
4225 case Op_HasNegatives:
4226 pinned = false;
4227 }
4228 if( pinned ) {
4229 IdealLoopTree *chosen_loop = get_loop(n->is_CFG() ? n : get_ctrl(n));
4230 if( !chosen_loop->_child ) // Inner loop?
4231 chosen_loop->_body.push(n); // Collect inner loops
4232 return;
4233 }
4234 } else { // No slot zero
4235 if( n->is_CFG() ) { // CFG with no slot 0 is dead
4236 _nodes.map(n->_idx,0); // No block setting, it's globally dead
4237 return;
4238 }
4239 assert(!n->is_CFG() || n->outcnt() == 0, "");
4240 }
4241
4242 // Do I have a "safe range" I can select over?
4243 Node *early = get_ctrl(n);// Early location already computed
4244
4245 // Compute latest point this Node can go
4246 Node *LCA = get_late_ctrl( n, early );
4247 // LCA is NULL due to uses being dead
4310 }
4311 }
4312
4313 #ifdef ASSERT
4314 // If verifying, verify that 'verify_me' has a legal location
4315 // and choose it as our location.
4316 if( _verify_me ) {
4317 Node *v_ctrl = _verify_me->get_ctrl_no_update(n);
4318 Node *legal = LCA;
4319 while( early != legal ) { // While not at earliest legal
4320 if( legal == v_ctrl ) break; // Check for prior good location
4321 legal = idom(legal) ;// Bump up the IDOM tree
4322 }
4323 // Check for prior good location
4324 if( legal == v_ctrl ) least = legal; // Keep prior if found
4325 }
4326 #endif
4327
4328 // Assign discovered "here or above" point
4329 least = find_non_split_ctrl(least);
4330 verify_strip_mined_scheduling(n, least);
4331 set_ctrl(n, least);
4332
4333 // Collect inner loop bodies
4334 IdealLoopTree *chosen_loop = get_loop(least);
4335 if( !chosen_loop->_child ) // Inner loop?
4336 chosen_loop->_body.push(n);// Collect inner loops
4337 }
4338
4339 #ifdef ASSERT
4340 void PhaseIdealLoop::dump_bad_graph(const char* msg, Node* n, Node* early, Node* LCA) {
4341 tty->print_cr("%s", msg);
4342 tty->print("n: "); n->dump();
4343 tty->print("early(n): "); early->dump();
4344 if (n->in(0) != NULL && !n->in(0)->is_top() &&
4345 n->in(0) != early && !n->in(0)->is_Root()) {
4346 tty->print("n->in(0): "); n->in(0)->dump();
4347 }
4348 for (uint i = 1; i < n->req(); i++) {
4349 Node* in1 = n->in(i);
4350 if (in1 != NULL && in1 != n && !in1->is_top()) {
4351 tty->print("n->in(%d): ", i); in1->dump();
4352 Node* in1_early = get_ctrl(in1);
4353 tty->print("early(n->in(%d)): ", i); in1_early->dump();
4354 if (in1->in(0) != NULL && !in1->in(0)->is_top() &&
4355 in1->in(0) != in1_early && !in1->in(0)->is_Root()) {
4356 tty->print("n->in(%d)->in(0): ", i); in1->in(0)->dump();
4472 }
4473 // Dump nodes it controls
4474 for( uint k = 0; k < _nodes.Size(); k++ ) {
4475 // (k < C->unique() && get_ctrl(find(k)) == n)
4476 if (k < C->unique() && _nodes[k] == (Node*)((intptr_t)n + 1)) {
4477 Node *m = C->root()->find(k);
4478 if( m && m->outcnt() > 0 ) {
4479 if (!(has_ctrl(m) && get_ctrl_no_update(m) == n)) {
4480 tty->print_cr("*** BROKEN CTRL ACCESSOR! _nodes[k] is %p, ctrl is %p",
4481 _nodes[k], has_ctrl(m) ? get_ctrl_no_update(m) : NULL);
4482 }
4483 for( uint j = 0; j < loop->_nest; j++ )
4484 tty->print(" ");
4485 tty->print(" ");
4486 m->dump();
4487 }
4488 }
4489 }
4490 }
4491 }
4492
4493 // Collect a R-P-O for the whole CFG.
4494 // Result list is in post-order (scan backwards for RPO)
4495 void PhaseIdealLoop::rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const {
4496 stk.push(start, 0);
4497 visited.set(start->_idx);
4498
4499 while (stk.is_nonempty()) {
4500 Node* m = stk.node();
4501 uint idx = stk.index();
4502 if (idx < m->outcnt()) {
4503 stk.set_index(idx + 1);
4504 Node* n = m->raw_out(idx);
4505 if (n->is_CFG() && !visited.test_set(n->_idx)) {
4506 stk.push(n, 0);
4507 }
4508 } else {
4509 rpo_list.push(m);
4510 stk.pop();
4511 }
4512 }
4513 }
4514 #endif
4515
4516
4517 //=============================================================================
4518 //------------------------------LoopTreeIterator-----------------------------------
4519
4520 // Advance to next loop tree using a preorder, left-to-right traversal.
4521 void LoopTreeIterator::next() {
4522 assert(!done(), "must not be done.");
4523 if (_curnt->_child != NULL) {
4524 _curnt = _curnt->_child;
4525 } else if (_curnt->_next != NULL) {
4526 _curnt = _curnt->_next;
4527 } else {
4528 while (_curnt != _root && _curnt->_next == NULL) {
4529 _curnt = _curnt->_parent;
4530 }
4531 if (_curnt == _root) {
4532 _curnt = NULL;
4533 assert(done(), "must be done.");
4534 } 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()) {
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
2718 n2->set_req(0, c2);
2719 _igvn.hash_insert(n2);
2720 _igvn._worklist.push(n2);
2721 progress = true;
2722 }
2723 }
2724 }
2725 }
2726
2727 return progress;
2728 }
2729
2730
2731 //=============================================================================
2732 //----------------------------build_and_optimize-------------------------------
2733 // Create a PhaseLoop. Build the ideal Loop tree. Map each Ideal Node to
2734 // its corresponding LoopNode. If 'optimize' is true, do some loop cleanups.
2735 void PhaseIdealLoop::build_and_optimize(LoopOptsMode mode) {
2736 bool do_split_ifs = (mode == LoopOptsDefault || mode == LoopOptsLastRound);
2737 bool skip_loop_opts = (mode == LoopOptsNone);
2738 bool shenandoah_opts = (mode == LoopOptsShenandoahExpand ||
2739 mode == LoopOptsShenandoahPostExpand);
2740
2741 ResourceMark rm;
2742
2743 int old_progress = C->major_progress();
2744 uint orig_worklist_size = _igvn._worklist.size();
2745
2746 // Reset major-progress flag for the driver's heuristics
2747 C->clear_major_progress();
2748
2749 #ifndef PRODUCT
2750 // Capture for later assert
2751 uint unique = C->unique();
2752 _loop_invokes++;
2753 _loop_work += unique;
2754 #endif
2755
2756 // True if the method has at least 1 irreducible loop
2757 _has_irreducible_loops = false;
2758
2759 _created_loop_node = false;
2784 build_loop_tree();
2785 // Check for bailout, and return
2786 if (C->failing()) {
2787 return;
2788 }
2789
2790 // No loops after all
2791 if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false);
2792
2793 // There should always be an outer loop containing the Root and Return nodes.
2794 // If not, we have a degenerate empty program. Bail out in this case.
2795 if (!has_node(C->root())) {
2796 if (!_verify_only) {
2797 C->clear_major_progress();
2798 C->record_method_not_compilable("empty program detected during loop optimization");
2799 }
2800 return;
2801 }
2802
2803 // Nothing to do, so get out
2804 bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !_verify_me && !_verify_only && !shenandoah_opts;
2805 bool do_expensive_nodes = C->should_optimize_expensive_nodes(_igvn);
2806 if (stop_early && !do_expensive_nodes) {
2807 _igvn.optimize(); // Cleanup NeverBranches
2808 return;
2809 }
2810
2811 // Set loop nesting depth
2812 _ltree_root->set_nest( 0 );
2813
2814 // Split shared headers and insert loop landing pads.
2815 // Do not bother doing this on the Root loop of course.
2816 if( !_verify_me && !_verify_only && _ltree_root->_child ) {
2817 C->print_method(PHASE_BEFORE_BEAUTIFY_LOOPS, 3);
2818 if( _ltree_root->_child->beautify_loops( this ) ) {
2819 // Re-build loop tree!
2820 _ltree_root->_child = NULL;
2821 _nodes.clear();
2822 reallocate_preorders();
2823 build_loop_tree();
2824 // Check for bailout, and return
2863
2864 // Walk the DATA nodes and place into loops. Find earliest control
2865 // node. For CFG nodes, the _nodes array starts out and remains
2866 // holding the associated IdealLoopTree pointer. For DATA nodes, the
2867 // _nodes array holds the earliest legal controlling CFG node.
2868
2869 // Allocate stack with enough space to avoid frequent realloc
2870 int stack_size = (C->live_nodes() >> 1) + 16; // (live_nodes>>1)+16 from Java2D stats
2871 Node_Stack nstack( a, stack_size );
2872
2873 visited.Clear();
2874 Node_List worklist(a);
2875 // Don't need C->root() on worklist since
2876 // it will be processed among C->top() inputs
2877 worklist.push( C->top() );
2878 visited.set( C->top()->_idx ); // Set C->top() as visited now
2879 build_loop_early( visited, worklist, nstack );
2880
2881 // Given early legal placement, try finding counted loops. This placement
2882 // is good enough to discover most loop invariants.
2883 if (!_verify_me && !_verify_only && !shenandoah_opts) {
2884 _ltree_root->counted_loop(this);
2885 }
2886
2887 // Find latest loop placement. Find ideal loop placement.
2888 visited.Clear();
2889 init_dom_lca_tags();
2890 // Need C->root() on worklist when processing outs
2891 worklist.push( C->root() );
2892 NOT_PRODUCT( C->verify_graph_edges(); )
2893 worklist.push( C->top() );
2894 build_loop_late(visited, worklist, nstack, !shenandoah_opts);
2895
2896 if (_verify_only) {
2897 // restore major progress flag
2898 for (int i = 0; i < old_progress; i++)
2899 C->set_major_progress();
2900 assert(C->unique() == unique, "verification mode made Nodes? ? ?");
2901 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything");
2902 return;
2903 }
2904
2905 // clear out the dead code after build_loop_late
2906 while (_deadlist.size()) {
2907 _igvn.remove_globally_dead_node(_deadlist.pop());
2908 }
2909
2910 if (stop_early) {
2911 assert(do_expensive_nodes, "why are we here?");
2912 if (process_expensive_nodes()) {
2913 // If we made some progress when processing expensive nodes then
2914 // the IGVN may modify the graph in a way that will allow us to
2921 }
2922
2923 // Some parser-inserted loop predicates could never be used by loop
2924 // predication or they were moved away from loop during some optimizations.
2925 // For example, peeling. Eliminate them before next loop optimizations.
2926 eliminate_useless_predicates();
2927
2928 #ifndef PRODUCT
2929 C->verify_graph_edges();
2930 if (_verify_me) { // Nested verify pass?
2931 // Check to see if the verify mode is broken
2932 assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?");
2933 return;
2934 }
2935 if(VerifyLoopOptimizations) verify();
2936 if(TraceLoopOpts && C->has_loops()) {
2937 _ltree_root->dump();
2938 }
2939 #endif
2940
2941 #if INCLUDE_SHENANDOAHGC
2942 if (mode == LoopOptsShenandoahExpand) {
2943 assert(UseShenandoahGC, "only for shenandoah");
2944 ShenandoahWriteBarrierNode::pin_and_expand(this);
2945 } else if (mode == LoopOptsShenandoahPostExpand) {
2946 assert(UseShenandoahGC, "only for shenandoah");
2947 visited.Clear();
2948 ShenandoahWriteBarrierNode::optimize_after_expansion(visited, nstack, worklist, this);
2949 }
2950
2951 if (shenandoah_opts) {
2952 _igvn.optimize();
2953 if (C->log() != NULL) {
2954 log_loop_tree(_ltree_root, _ltree_root, C->log());
2955 }
2956 return;
2957 }
2958 #endif
2959
2960 if (skip_loop_opts) {
2961 // restore major progress flag
2962 for (int i = 0; i < old_progress; i++) {
2963 C->set_major_progress();
2964 }
2965
2966 // Cleanup any modified bits
2967 _igvn.optimize();
2968
2969 if (C->log() != NULL) {
2970 log_loop_tree(_ltree_root, _ltree_root, C->log());
2971 }
2972 return;
2973 }
2974
2975 #if INCLUDE_SHENANDOAHGC
2976 if (UseShenandoahGC) {
2977 GrowableArray<MemoryGraphFixer*> memory_graph_fixers;
2978 ShenandoahWriteBarrierNode::optimize_before_expansion(this, memory_graph_fixers, false);
2979 }
2980 #endif
2981
2982 if (ReassociateInvariants) {
2983 // Reassociate invariants and prep for split_thru_phi
2984 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) {
2985 IdealLoopTree* lpt = iter.current();
2986 bool is_counted = lpt->is_counted();
2987 if (!is_counted || !lpt->is_inner()) continue;
2988
2989 // check for vectorized loops, any reassociation of invariants was already done
2990 if (is_counted && lpt->_head->as_CountedLoop()->do_unroll_only()) continue;
2991
2992 lpt->reassociate_invariants(this);
2993
2994 // Because RCE opportunities can be masked by split_thru_phi,
2995 // look for RCE candidates and inhibit split_thru_phi
2996 // on just their loop-phi's for this pass of loop opts
2997 if (SplitIfBlocks && do_split_ifs) {
2998 if (lpt->policy_range_check(this)) {
2999 lpt->_rce_candidate = 1; // = true
3000 }
3001 }
3992 compute_lca_of_uses(n, early, true);
3993 }
3994 #endif
3995
3996 // if this is a load, check for anti-dependent stores
3997 // We use a conservative algorithm to identify potential interfering
3998 // instructions and for rescheduling the load. The users of the memory
3999 // input of this load are examined. Any use which is not a load and is
4000 // dominated by early is considered a potentially interfering store.
4001 // This can produce false positives.
4002 if (n->is_Load() && LCA != early) {
4003 Node_List worklist;
4004
4005 Node *mem = n->in(MemNode::Memory);
4006 for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) {
4007 Node* s = mem->fast_out(i);
4008 worklist.push(s);
4009 }
4010 while(worklist.size() != 0 && LCA != early) {
4011 Node* s = worklist.pop();
4012 if (s->is_Load() || s->is_ShenandoahBarrier() || s->Opcode() == Op_SafePoint ||
4013 (s->is_CallStaticJava() && s->as_CallStaticJava()->uncommon_trap_request() != 0)) {
4014 continue;
4015 } else if (s->is_MergeMem()) {
4016 for (DUIterator_Fast imax, i = s->fast_outs(imax); i < imax; i++) {
4017 Node* s1 = s->fast_out(i);
4018 worklist.push(s1);
4019 }
4020 } else {
4021 Node *sctrl = has_ctrl(s) ? get_ctrl(s) : s->in(0);
4022 assert(sctrl != NULL || s->outcnt() == 0 || s->is_ShenandoahBarrier(), "must have control");
4023 if (sctrl != NULL && !sctrl->is_top() && is_dominator(early, sctrl)) {
4024 LCA = dom_lca_for_get_late_ctrl(LCA, sctrl, n);
4025 }
4026 }
4027 }
4028 }
4029
4030 assert(LCA == find_non_split_ctrl(LCA), "unexpected late control");
4031 return LCA;
4032 }
4033
4034 // true if CFG node d dominates CFG node n
4035 bool PhaseIdealLoop::is_dominator(Node *d, Node *n) {
4036 if (d == n)
4037 return true;
4038 assert(d->is_CFG() && n->is_CFG(), "must have CFG nodes");
4039 uint dd = dom_depth(d);
4040 while (dom_depth(n) >= dd) {
4041 if (n == d)
4042 return true;
4120 }
4121
4122 //------------------------------clear_dom_lca_tags------------------------------
4123 // Tag could be a node's integer index, 32bits instead of 64bits in some cases
4124 // Intended use does not involve any growth for the array, so it could
4125 // be of fixed size.
4126 void PhaseIdealLoop::clear_dom_lca_tags() {
4127 uint limit = C->unique() + 1;
4128 _dom_lca_tags.map( limit, NULL );
4129 _dom_lca_tags.clear();
4130 #ifdef ASSERT
4131 for( uint i = 0; i < limit; ++i ) {
4132 assert(_dom_lca_tags[i] == NULL, "Must be distinct from each node pointer");
4133 }
4134 #endif // ASSERT
4135 }
4136
4137 //------------------------------build_loop_late--------------------------------
4138 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
4139 // Second pass finds latest legal placement, and ideal loop placement.
4140 void PhaseIdealLoop::build_loop_late(VectorSet &visited, Node_List &worklist, Node_Stack &nstack, bool verify_strip_mined) {
4141 while (worklist.size() != 0) {
4142 Node *n = worklist.pop();
4143 // Only visit once
4144 if (visited.test_set(n->_idx)) continue;
4145 uint cnt = n->outcnt();
4146 uint i = 0;
4147 while (true) {
4148 assert( _nodes[n->_idx], "no dead nodes" );
4149 // Visit all children
4150 if (i < cnt) {
4151 Node* use = n->raw_out(i);
4152 ++i;
4153 // Check for dead uses. Aggressively prune such junk. It might be
4154 // dead in the global sense, but still have local uses so I cannot
4155 // easily call 'remove_dead_node'.
4156 if( _nodes[use->_idx] != NULL || use->is_top() ) { // Not dead?
4157 // Due to cycles, we might not hit the same fixed point in the verify
4158 // pass as we do in the regular pass. Instead, visit such phis as
4159 // simple uses of the loop head.
4160 if( use->in(0) && (use->is_CFG() || use->is_Phi()) ) {
4161 if( !visited.test(use->_idx) )
4162 worklist.push(use);
4163 } else if( !visited.test_set(use->_idx) ) {
4164 nstack.push(n, i); // Save parent and next use's index.
4165 n = use; // Process all children of current use.
4166 cnt = use->outcnt();
4167 i = 0;
4168 }
4169 } else {
4170 // Do not visit around the backedge of loops via data edges.
4171 // push dead code onto a worklist
4172 _deadlist.push(use);
4173 }
4174 } else {
4175 // All of n's children have been processed, complete post-processing.
4176 build_loop_late_post(n, verify_strip_mined);
4177 if (nstack.is_empty()) {
4178 // Finished all nodes on stack.
4179 // Process next node on the worklist.
4180 break;
4181 }
4182 // Get saved parent node and next use's index. Visit the rest of uses.
4183 n = nstack.node();
4184 cnt = n->outcnt();
4185 i = nstack.index();
4186 nstack.pop();
4187 }
4188 }
4189 }
4190 }
4191
4192 // Verify that no data node is scheduled in the outer loop of a strip
4193 // mined loop.
4194 void PhaseIdealLoop::verify_strip_mined_scheduling(Node *n, Node* least) {
4195 #ifdef ASSERT
4196 if (get_loop(least)->_nest == 0) {
4197 return;
4198 }
4199 IdealLoopTree* loop = get_loop(least);
4200 Node* head = loop->_head;
4201 if (head->is_OuterStripMinedLoop()) {
4202 Node* sfpt = head->as_Loop()->outer_safepoint();
4203 ResourceMark rm;
4204 Unique_Node_List wq;
4205 wq.push(sfpt);
4206 for (uint i = 0; i < wq.size(); i++) {
4207 Node *m = wq.at(i);
4208 for (uint i = 1; i < m->req(); i++) {
4209 Node* nn = m->in(i);
4210 if (nn == n) {
4211 return;
4212 }
4213 if (nn != NULL && has_ctrl(nn) && get_loop(get_ctrl(nn)) == loop) {
4214 wq.push(nn);
4215 }
4216 }
4217 }
4218 ShouldNotReachHere();
4219 }
4220 #endif
4221 }
4222
4223
4224 //------------------------------build_loop_late_post---------------------------
4225 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
4226 // Second pass finds latest legal placement, and ideal loop placement.
4227 void PhaseIdealLoop::build_loop_late_post(Node *n, bool verify_strip_mined) {
4228
4229 if (n->req() == 2 && (n->Opcode() == Op_ConvI2L || n->Opcode() == Op_CastII) && !C->major_progress() && !_verify_only) {
4230 _igvn._worklist.push(n); // Maybe we'll normalize it, if no more loops.
4231 }
4232
4233 #ifdef ASSERT
4234 if (_verify_only && !n->is_CFG()) {
4235 // Check def-use domination.
4236 compute_lca_of_uses(n, get_ctrl(n), true /* verify */);
4237 }
4238 #endif
4239
4240 // CFG and pinned nodes already handled
4241 if( n->in(0) ) {
4242 if( n->in(0)->is_top() ) return; // Dead?
4243
4244 // We'd like +VerifyLoopOptimizations to not believe that Mod's/Loads
4245 // _must_ be pinned (they have to observe their control edge of course).
4246 // Unlike Stores (which modify an unallocable resource, the memory
4247 // state), Mods/Loads can float around. So free them up.
4258 case Op_LoadUS:
4259 case Op_LoadD:
4260 case Op_LoadF:
4261 case Op_LoadI:
4262 case Op_LoadKlass:
4263 case Op_LoadNKlass:
4264 case Op_LoadL:
4265 case Op_LoadS:
4266 case Op_LoadP:
4267 case Op_LoadBarrierSlowReg:
4268 case Op_LoadBarrierWeakSlowReg:
4269 case Op_LoadN:
4270 case Op_LoadRange:
4271 case Op_LoadD_unaligned:
4272 case Op_LoadL_unaligned:
4273 case Op_StrComp: // Does a bunch of load-like effects
4274 case Op_StrEquals:
4275 case Op_StrIndexOf:
4276 case Op_StrIndexOfChar:
4277 case Op_AryEq:
4278 #if INCLUDE_SHENANDOAHGC
4279 case Op_ShenandoahReadBarrier:
4280 case Op_ShenandoahWriteBarrier:
4281 case Op_ShenandoahWBMemProj:
4282 #endif
4283 case Op_HasNegatives:
4284 pinned = false;
4285 }
4286
4287 if( pinned ) {
4288 IdealLoopTree *chosen_loop = get_loop(n->is_CFG() ? n : get_ctrl(n));
4289 if( !chosen_loop->_child ) // Inner loop?
4290 chosen_loop->_body.push(n); // Collect inner loops
4291 return;
4292 }
4293 } else { // No slot zero
4294 if( n->is_CFG() ) { // CFG with no slot 0 is dead
4295 _nodes.map(n->_idx,0); // No block setting, it's globally dead
4296 return;
4297 }
4298 assert(!n->is_CFG() || n->outcnt() == 0, "");
4299 }
4300
4301 // Do I have a "safe range" I can select over?
4302 Node *early = get_ctrl(n);// Early location already computed
4303
4304 // Compute latest point this Node can go
4305 Node *LCA = get_late_ctrl( n, early );
4306 // LCA is NULL due to uses being dead
4369 }
4370 }
4371
4372 #ifdef ASSERT
4373 // If verifying, verify that 'verify_me' has a legal location
4374 // and choose it as our location.
4375 if( _verify_me ) {
4376 Node *v_ctrl = _verify_me->get_ctrl_no_update(n);
4377 Node *legal = LCA;
4378 while( early != legal ) { // While not at earliest legal
4379 if( legal == v_ctrl ) break; // Check for prior good location
4380 legal = idom(legal) ;// Bump up the IDOM tree
4381 }
4382 // Check for prior good location
4383 if( legal == v_ctrl ) least = legal; // Keep prior if found
4384 }
4385 #endif
4386
4387 // Assign discovered "here or above" point
4388 least = find_non_split_ctrl(least);
4389 if (verify_strip_mined && !_verify_only) {
4390 verify_strip_mined_scheduling(n, least);
4391 }
4392 set_ctrl(n, least);
4393
4394 // Collect inner loop bodies
4395 IdealLoopTree *chosen_loop = get_loop(least);
4396 if( !chosen_loop->_child ) // Inner loop?
4397 chosen_loop->_body.push(n);// Collect inner loops
4398
4399 if (n->Opcode() == Op_ShenandoahWriteBarrier) {
4400 // The write barrier and its memory proj must have the same
4401 // control otherwise some loop opts could put nodes (Phis) between
4402 // them
4403 Node* proj = n->find_out_with(Op_ShenandoahWBMemProj);
4404 if (proj != NULL) {
4405 set_ctrl_and_loop(proj, least);
4406 }
4407 }
4408 }
4409
4410 #ifdef ASSERT
4411 void PhaseIdealLoop::dump_bad_graph(const char* msg, Node* n, Node* early, Node* LCA) {
4412 tty->print_cr("%s", msg);
4413 tty->print("n: "); n->dump();
4414 tty->print("early(n): "); early->dump();
4415 if (n->in(0) != NULL && !n->in(0)->is_top() &&
4416 n->in(0) != early && !n->in(0)->is_Root()) {
4417 tty->print("n->in(0): "); n->in(0)->dump();
4418 }
4419 for (uint i = 1; i < n->req(); i++) {
4420 Node* in1 = n->in(i);
4421 if (in1 != NULL && in1 != n && !in1->is_top()) {
4422 tty->print("n->in(%d): ", i); in1->dump();
4423 Node* in1_early = get_ctrl(in1);
4424 tty->print("early(n->in(%d)): ", i); in1_early->dump();
4425 if (in1->in(0) != NULL && !in1->in(0)->is_top() &&
4426 in1->in(0) != in1_early && !in1->in(0)->is_Root()) {
4427 tty->print("n->in(%d)->in(0): ", i); in1->in(0)->dump();
4543 }
4544 // Dump nodes it controls
4545 for( uint k = 0; k < _nodes.Size(); k++ ) {
4546 // (k < C->unique() && get_ctrl(find(k)) == n)
4547 if (k < C->unique() && _nodes[k] == (Node*)((intptr_t)n + 1)) {
4548 Node *m = C->root()->find(k);
4549 if( m && m->outcnt() > 0 ) {
4550 if (!(has_ctrl(m) && get_ctrl_no_update(m) == n)) {
4551 tty->print_cr("*** BROKEN CTRL ACCESSOR! _nodes[k] is %p, ctrl is %p",
4552 _nodes[k], has_ctrl(m) ? get_ctrl_no_update(m) : NULL);
4553 }
4554 for( uint j = 0; j < loop->_nest; j++ )
4555 tty->print(" ");
4556 tty->print(" ");
4557 m->dump();
4558 }
4559 }
4560 }
4561 }
4562 }
4563 #endif
4564
4565 // Collect a R-P-O for the whole CFG.
4566 // Result list is in post-order (scan backwards for RPO)
4567 void PhaseIdealLoop::rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const {
4568 stk.push(start, 0);
4569 visited.set(start->_idx);
4570
4571 while (stk.is_nonempty()) {
4572 Node* m = stk.node();
4573 uint idx = stk.index();
4574 if (idx < m->outcnt()) {
4575 stk.set_index(idx + 1);
4576 Node* n = m->raw_out(idx);
4577 if (n->is_CFG() && !visited.test_set(n->_idx)) {
4578 stk.push(n, 0);
4579 }
4580 } else {
4581 rpo_list.push(m);
4582 stk.pop();
4583 }
4584 }
4585 }
4586
4587
4588 //=============================================================================
4589 //------------------------------LoopTreeIterator-----------------------------------
4590
4591 // Advance to next loop tree using a preorder, left-to-right traversal.
4592 void LoopTreeIterator::next() {
4593 assert(!done(), "must not be done.");
4594 if (_curnt->_child != NULL) {
4595 _curnt = _curnt->_child;
4596 } else if (_curnt->_next != NULL) {
4597 _curnt = _curnt->_next;
4598 } else {
4599 while (_curnt != _root && _curnt->_next == NULL) {
4600 _curnt = _curnt->_parent;
4601 }
4602 if (_curnt == _root) {
4603 _curnt = NULL;
4604 assert(done(), "must be done.");
4605 } else {
|