Mercurial > hg > truffle

comparison src/share/vm/opto/loopopts.cpp @ 2383:9dc311b8473e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
7008866: Missing loop predicate for loop with multiple entries Summary: Add predicates when loop head bytecode is parsed instead of when back branch bytecode is parsed. Reviewed-by: never
author kvn
date Mon, 21 Mar 2011 11:28:14 -0700
parents f95d63e2154a
children 1d1603768966 08eb13460b3a
comparison
equal deleted inserted replaced
2382:3ef1a1866a60 2383:9dc311b8473e
40 // ConvI2L may have type information on it which is unsafe to push up 40 // ConvI2L may have type information on it which is unsafe to push up
41 // so disable this for now 41 // so disable this for now
42 return NULL; 42 return NULL;
43 } 43 }
44 int wins = 0; 44 int wins = 0;
45 assert( !n->is_CFG(), "" ); 45 assert(!n->is_CFG(), "");
46 assert( region->is_Region(), "" ); 46 assert(region->is_Region(), "");
47 47
48 const Type* type = n->bottom_type(); 48 const Type* type = n->bottom_type();
49 const TypeOopPtr *t_oop = _igvn.type(n)->isa_oopptr(); 49 const TypeOopPtr *t_oop = _igvn.type(n)->isa_oopptr();
50 Node *phi; 50 Node *phi;
51 if( t_oop != NULL && t_oop->is_known_instance_field() ) { 51 if (t_oop != NULL && t_oop->is_known_instance_field()) {
52 int iid = t_oop->instance_id(); 52 int iid = t_oop->instance_id();
53 int index = C->get_alias_index(t_oop); 53 int index = C->get_alias_index(t_oop);
54 int offset = t_oop->offset(); 54 int offset = t_oop->offset();
55 phi = new (C,region->req()) PhiNode(region, type, NULL, iid, index, offset); 55 phi = new (C,region->req()) PhiNode(region, type, NULL, iid, index, offset);
56 } else { 56 } else {
57 phi = PhiNode::make_blank(region, n); 57 phi = PhiNode::make_blank(region, n);
58 } 58 }
59 uint old_unique = C->unique(); 59 uint old_unique = C->unique();
60 for( uint i = 1; i < region->req(); i++ ) { 60 for (uint i = 1; i < region->req(); i++) {
61 Node *x; 61 Node *x;
62 Node* the_clone = NULL; 62 Node* the_clone = NULL;
63 if( region->in(i) == C->top() ) { 63 if (region->in(i) == C->top()) {
64 x = C->top(); // Dead path? Use a dead data op 64 x = C->top(); // Dead path? Use a dead data op
65 } else { 65 } else {
66 x = n->clone(); // Else clone up the data op 66 x = n->clone(); // Else clone up the data op
67 the_clone = x; // Remember for possible deletion. 67 the_clone = x; // Remember for possible deletion.
68 // Alter data node to use pre-phi inputs 68 // Alter data node to use pre-phi inputs
69 if( n->in(0) == region ) 69 if (n->in(0) == region)
70 x->set_req( 0, region->in(i) ); 70 x->set_req( 0, region->in(i) );
71 for( uint j = 1; j < n->req(); j++ ) { 71 for (uint j = 1; j < n->req(); j++) {
72 Node *in = n->in(j); 72 Node *in = n->in(j);
73 if( in->is_Phi() && in->in(0) == region ) 73 if (in->is_Phi() && in->in(0) == region)
74 x->set_req( j, in->in(i) ); // Use pre-Phi input for the clone 74 x->set_req( j, in->in(i) ); // Use pre-Phi input for the clone
75 } 75 }
76 } 76 }
77 // Check for a 'win' on some paths 77 // Check for a 'win' on some paths
78 const Type *t = x->Value(&_igvn); 78 const Type *t = x->Value(&_igvn);
83 // along a particular edge. In most cases, this is OK, and the Phi will 83 // along a particular edge. In most cases, this is OK, and the Phi will
84 // be eliminated later in an Ideal call. However, we can't allow this to 84 // be eliminated later in an Ideal call. However, we can't allow this to
85 // happen if the singleton occurs on loop entry, as the elimination of 85 // happen if the singleton occurs on loop entry, as the elimination of
86 // the PhiNode may cause the resulting node to migrate back to a previous 86 // the PhiNode may cause the resulting node to migrate back to a previous
87 // loop iteration. 87 // loop iteration.
88 if( singleton && t == Type::TOP ) { 88 if (singleton && t == Type::TOP) {
89 // Is_Loop() == false does not confirm the absence of a loop (e.g., an 89 // Is_Loop() == false does not confirm the absence of a loop (e.g., an
90 // irreducible loop may not be indicated by an affirmative is_Loop()); 90 // irreducible loop may not be indicated by an affirmative is_Loop());
91 // therefore, the only top we can split thru a phi is on a backedge of 91 // therefore, the only top we can split thru a phi is on a backedge of
92 // a loop. 92 // a loop.
93 singleton &= region->is_Loop() && (i != LoopNode::EntryControl); 93 singleton &= region->is_Loop() && (i != LoopNode::EntryControl);
94 } 94 }
95 95
96 if( singleton ) { 96 if (singleton) {
97 wins++; 97 wins++;
98 x = ((PhaseGVN&)_igvn).makecon(t); 98 x = ((PhaseGVN&)_igvn).makecon(t);
99 } else { 99 } else {
100 // We now call Identity to try to simplify the cloned node. 100 // We now call Identity to try to simplify the cloned node.
101 // Note that some Identity methods call phase->type(this). 101 // Note that some Identity methods call phase->type(this).
106 // If x is a TypeNode, capture any more-precise type permanently into Node 106 // If x is a TypeNode, capture any more-precise type permanently into Node
107 // otherwise it will be not updated during igvn->transform since 107 // otherwise it will be not updated during igvn->transform since
108 // igvn->type(x) is set to x->Value() already. 108 // igvn->type(x) is set to x->Value() already.
109 x->raise_bottom_type(t); 109 x->raise_bottom_type(t);
110 Node *y = x->Identity(&_igvn); 110 Node *y = x->Identity(&_igvn);
111 if( y != x ) { 111 if (y != x) {
112 wins++; 112 wins++;
113 x = y; 113 x = y;
114 } else { 114 } else {
115 y = _igvn.hash_find(x); 115 y = _igvn.hash_find(x);
116 if( y ) { 116 if (y) {
117 wins++; 117 wins++;
118 x = y; 118 x = y;
119 } else { 119 } else {
120 // Else x is a new node we are keeping 120 // Else x is a new node we are keeping
121 // We do not need register_new_node_with_optimizer 121 // We do not need register_new_node_with_optimizer
127 if (x != the_clone && the_clone != NULL) 127 if (x != the_clone && the_clone != NULL)
128 _igvn.remove_dead_node(the_clone); 128 _igvn.remove_dead_node(the_clone);
129 phi->set_req( i, x ); 129 phi->set_req( i, x );
130 } 130 }
131 // Too few wins? 131 // Too few wins?
132 if( wins <= policy ) { 132 if (wins <= policy) {
133 _igvn.remove_dead_node(phi); 133 _igvn.remove_dead_node(phi);
134 return NULL; 134 return NULL;
135 } 135 }
136 136
137 // Record Phi 137 // Record Phi
138 register_new_node( phi, region ); 138 register_new_node( phi, region );
139 139
140 for( uint i2 = 1; i2 < phi->req(); i2++ ) { 140 for (uint i2 = 1; i2 < phi->req(); i2++) {
141 Node *x = phi->in(i2); 141 Node *x = phi->in(i2);
142 // If we commoned up the cloned 'x' with another existing Node, 142 // If we commoned up the cloned 'x' with another existing Node,
143 // the existing Node picks up a new use. We need to make the 143 // the existing Node picks up a new use. We need to make the
144 // existing Node occur higher up so it dominates its uses. 144 // existing Node occur higher up so it dominates its uses.
145 Node *old_ctrl; 145 Node *old_ctrl;
146 IdealLoopTree *old_loop; 146 IdealLoopTree *old_loop;
147 147
148 if (x->is_Con()) {
149 // Constant's control is always root.
150 set_ctrl(x, C->root());
151 continue;
152 }
148 // The occasional new node 153 // The occasional new node
149 if( x->_idx >= old_unique ) { // Found a new, unplaced node? 154 if (x->_idx >= old_unique) { // Found a new, unplaced node?
150 old_ctrl = x->is_Con() ? C->root() : NULL; 155 old_ctrl = NULL;
151 old_loop = NULL; // Not in any prior loop 156 old_loop = NULL; // Not in any prior loop
152 } else { 157 } else {
153 old_ctrl = x->is_Con() ? C->root() : get_ctrl(x); 158 old_ctrl = get_ctrl(x);
154 old_loop = get_loop(old_ctrl); // Get prior loop 159 old_loop = get_loop(old_ctrl); // Get prior loop
155 } 160 }
156 // New late point must dominate new use 161 // New late point must dominate new use
157 Node *new_ctrl = dom_lca( old_ctrl, region->in(i2) ); 162 Node *new_ctrl = dom_lca(old_ctrl, region->in(i2));
163 if (new_ctrl == old_ctrl) // Nothing is changed
164 continue;
165
166 IdealLoopTree *new_loop = get_loop(new_ctrl);
167
168 // Don't move x into a loop if its uses are
169 // outside of loop. Otherwise x will be cloned
170 // for each use outside of this loop.
171 IdealLoopTree *use_loop = get_loop(region);
172 if (!new_loop->is_member(use_loop) &&
173 (old_loop == NULL || !new_loop->is_member(old_loop))) {
174 // Take early control, later control will be recalculated
175 // during next iteration of loop optimizations.
176 new_ctrl = get_early_ctrl(x);
177 new_loop = get_loop(new_ctrl);
178 }
158 // Set new location 179 // Set new location
159 set_ctrl(x, new_ctrl); 180 set_ctrl(x, new_ctrl);
160 IdealLoopTree *new_loop = get_loop( new_ctrl );
161 // If changing loop bodies, see if we need to collect into new body 181 // If changing loop bodies, see if we need to collect into new body
162 if( old_loop != new_loop ) { 182 if (old_loop != new_loop) {
163 if( old_loop && !old_loop->_child ) 183 if (old_loop && !old_loop->_child)
164 old_loop->_body.yank(x); 184 old_loop->_body.yank(x);
165 if( !new_loop->_child ) 185 if (!new_loop->_child)
166 new_loop->_body.push(x); // Collect body info 186 new_loop->_body.push(x); // Collect body info
167 } 187 }
168 } 188 }
169 189
170 return phi; 190 return phi;
172 192
173 //------------------------------dominated_by------------------------------------ 193 //------------------------------dominated_by------------------------------------
174 // Replace the dominated test with an obvious true or false. Place it on the 194 // Replace the dominated test with an obvious true or false. Place it on the
175 // IGVN worklist for later cleanup. Move control-dependent data Nodes on the 195 // IGVN worklist for later cleanup. Move control-dependent data Nodes on the
176 // live path up to the dominating control. 196 // live path up to the dominating control.
177 void PhaseIdealLoop::dominated_by( Node *prevdom, Node *iff ) { 197 void PhaseIdealLoop::dominated_by( Node *prevdom, Node *iff, bool flip ) {
178 #ifndef PRODUCT 198 #ifndef PRODUCT
179 if( VerifyLoopOptimizations && PrintOpto ) tty->print_cr("dominating test"); 199 if (VerifyLoopOptimizations && PrintOpto) tty->print_cr("dominating test");
180 #endif 200 #endif
181 201
182 202
183 // prevdom is the dominating projection of the dominating test. 203 // prevdom is the dominating projection of the dominating test.
184 assert( iff->is_If(), "" ); 204 assert( iff->is_If(), "" );
185 assert( iff->Opcode() == Op_If || iff->Opcode() == Op_CountedLoopEnd, "Check this code when new subtype is added"); 205 assert( iff->Opcode() == Op_If || iff->Opcode() == Op_CountedLoopEnd, "Check this code when new subtype is added");
186 int pop = prevdom->Opcode(); 206 int pop = prevdom->Opcode();
187 assert( pop == Op_IfFalse || pop == Op_IfTrue, "" ); 207 assert( pop == Op_IfFalse || pop == Op_IfTrue, "" );
208 if (flip) {
209 if (pop == Op_IfTrue)
210 pop = Op_IfFalse;
211 else
212 pop = Op_IfTrue;
213 }
188 // 'con' is set to true or false to kill the dominated test. 214 // 'con' is set to true or false to kill the dominated test.
189 Node *con = _igvn.makecon(pop == Op_IfTrue ? TypeInt::ONE : TypeInt::ZERO); 215 Node *con = _igvn.makecon(pop == Op_IfTrue ? TypeInt::ONE : TypeInt::ZERO);
190 set_ctrl(con, C->root()); // Constant gets a new use 216 set_ctrl(con, C->root()); // Constant gets a new use
191 // Hack the dominated test 217 // Hack the dominated test
192 _igvn.hash_delete(iff); 218 _igvn.hash_delete(iff);
195 221
196 // If I dont have a reachable TRUE and FALSE path following the IfNode then 222 // If I dont have a reachable TRUE and FALSE path following the IfNode then
197 // I can assume this path reaches an infinite loop. In this case it's not 223 // I can assume this path reaches an infinite loop. In this case it's not
198 // important to optimize the data Nodes - either the whole compilation will 224 // important to optimize the data Nodes - either the whole compilation will
199 // be tossed or this path (and all data Nodes) will go dead. 225 // be tossed or this path (and all data Nodes) will go dead.
200 if( iff->outcnt() != 2 ) return; 226 if (iff->outcnt() != 2) return;
201 227
202 // Make control-dependent data Nodes on the live path (path that will remain 228 // Make control-dependent data Nodes on the live path (path that will remain
203 // once the dominated IF is removed) become control-dependent on the 229 // once the dominated IF is removed) become control-dependent on the
204 // dominating projection. 230 // dominating projection.
205 Node* dp = ((IfNode*)iff)->proj_out(pop == Op_IfTrue); 231 Node* dp = ((IfNode*)iff)->proj_out(pop == Op_IfTrue);
206 IdealLoopTree *old_loop = get_loop(dp); 232 IdealLoopTree *old_loop = get_loop(dp);
207 233
208 for (DUIterator_Fast imax, i = dp->fast_outs(imax); i < imax; i++) { 234 for (DUIterator_Fast imax, i = dp->fast_outs(imax); i < imax; i++) {
209 Node* cd = dp->fast_out(i); // Control-dependent node 235 Node* cd = dp->fast_out(i); // Control-dependent node
210 if( cd->depends_only_on_test() ) { 236 if (cd->depends_only_on_test()) {
211 assert( cd->in(0) == dp, "" ); 237 assert(cd->in(0) == dp, "");
212 _igvn.hash_delete( cd ); 238 _igvn.hash_delete(cd);
213 cd->set_req(0, prevdom); 239 cd->set_req(0, prevdom);
214 set_early_ctrl( cd ); 240 set_early_ctrl(cd);
215 _igvn._worklist.push(cd); 241 _igvn._worklist.push(cd);
216 IdealLoopTree *new_loop = get_loop(get_ctrl(cd)); 242 IdealLoopTree *new_loop = get_loop(get_ctrl(cd));
217 if( old_loop != new_loop ) { 243 if (old_loop != new_loop) {
218 if( !old_loop->_child ) old_loop->_body.yank(cd); 244 if (!old_loop->_child) old_loop->_body.yank(cd);
219 if( !new_loop->_child ) new_loop->_body.push(cd); 245 if (!new_loop->_child) new_loop->_body.push(cd);
220 } 246 }
221 --i; 247 --i;
222 --imax; 248 --imax;
223 } 249 }
224 } 250 }
2336 if (first_not_peeled == NULL || first_not_peeled == head) { 2362 if (first_not_peeled == NULL || first_not_peeled == head) {
2337 return false; 2363 return false;
2338 } 2364 }
2339 2365
2340 #if !defined(PRODUCT) 2366 #if !defined(PRODUCT)
2367 if (TraceLoopOpts) {
2368 tty->print("PartialPeel ");
2369 loop->dump_head();
2370 }
2371
2341 if (TracePartialPeeling) { 2372 if (TracePartialPeeling) {
2342 tty->print_cr("before partial peel one iteration"); 2373 tty->print_cr("before partial peel one iteration");
2343 Node_List wl; 2374 Node_List wl;
2344 Node* t = head->in(2); 2375 Node* t = head->in(2);
2345 while (true) { 2376 while (true) {
2479 // Step 3: clone loop, retarget control, and insert new phis 2510 // Step 3: clone loop, retarget control, and insert new phis
2480 2511
2481 // Create new loop head for new phis and to hang 2512 // Create new loop head for new phis and to hang
2482 // the nodes being moved (sinked) from the peel region. 2513 // the nodes being moved (sinked) from the peel region.
2483 LoopNode* new_head = new (C, 3) LoopNode(last_peel, last_peel); 2514 LoopNode* new_head = new (C, 3) LoopNode(last_peel, last_peel);
2515 new_head->set_unswitch_count(head->unswitch_count()); // Preserve
2484 _igvn.register_new_node_with_optimizer(new_head); 2516 _igvn.register_new_node_with_optimizer(new_head);
2485 assert(first_not_peeled->in(0) == last_peel, "last_peel <- first_not_peeled"); 2517 assert(first_not_peeled->in(0) == last_peel, "last_peel <- first_not_peeled");
2486 first_not_peeled->set_req(0, new_head); 2518 first_not_peeled->set_req(0, new_head);
2487 set_loop(new_head, loop); 2519 set_loop(new_head, loop);
2488 loop->_body.push(new_head); 2520 loop->_body.push(new_head);
2649 //------------------------------reorg_offsets---------------------------------- 2681 //------------------------------reorg_offsets----------------------------------
2650 // Reorganize offset computations to lower register pressure. Mostly 2682 // Reorganize offset computations to lower register pressure. Mostly
2651 // prevent loop-fallout uses of the pre-incremented trip counter (which are 2683 // prevent loop-fallout uses of the pre-incremented trip counter (which are
2652 // then alive with the post-incremented trip counter forcing an extra 2684 // then alive with the post-incremented trip counter forcing an extra
2653 // register move) 2685 // register move)
2654 void PhaseIdealLoop::reorg_offsets( IdealLoopTree *loop ) { 2686 void PhaseIdealLoop::reorg_offsets(IdealLoopTree *loop) {
2687 // Perform it only for canonical counted loops.
2688 // Loop's shape could be messed up by iteration_split_impl.
2689 if (!loop->_head->is_CountedLoop())
2690 return;
2691 if (!loop->_head->as_Loop()->is_valid_counted_loop())
2692 return;
2655 2693
2656 CountedLoopNode *cl = loop->_head->as_CountedLoop(); 2694 CountedLoopNode *cl = loop->_head->as_CountedLoop();
2657 CountedLoopEndNode *cle = cl->loopexit(); 2695 CountedLoopEndNode *cle = cl->loopexit();
2658 if( !cle ) return; // The occasional dead loop
2659 // Find loop exit control
2660 Node *exit = cle->proj_out(false); 2696 Node *exit = cle->proj_out(false);
2661 assert( exit->Opcode() == Op_IfFalse, "" ); 2697 Node *phi = cl->phi();
2662 2698
2663 // Check for the special case of folks using the pre-incremented 2699 // Check for the special case of folks using the pre-incremented
2664 // trip-counter on the fall-out path (forces the pre-incremented 2700 // trip-counter on the fall-out path (forces the pre-incremented
2665 // and post-incremented trip counter to be live at the same time). 2701 // and post-incremented trip counter to be live at the same time).
2666 // Fix this by adjusting to use the post-increment trip counter. 2702 // Fix this by adjusting to use the post-increment trip counter.
2667 Node *phi = cl->phi();
2668 if( !phi ) return; // Dead infinite loop
2669
2670 // Shape messed up, probably by iteration_split_impl
2671 if (phi->in(LoopNode::LoopBackControl) != cl->incr()) return;
2672 2703
2673 bool progress = true; 2704 bool progress = true;
2674 while (progress) { 2705 while (progress) {
2675 progress = false; 2706 progress = false;
2676 for (DUIterator_Fast imax, i = phi->fast_outs(imax); i < imax; i++) { 2707 for (DUIterator_Fast imax, i = phi->fast_outs(imax); i < imax; i++) {
2677 Node* use = phi->fast_out(i); // User of trip-counter 2708 Node* use = phi->fast_out(i); // User of trip-counter
2678 if (!has_ctrl(use)) continue; 2709 if (!has_ctrl(use)) continue;
2679 Node *u_ctrl = get_ctrl(use); 2710 Node *u_ctrl = get_ctrl(use);
2680 if( use->is_Phi() ) { 2711 if (use->is_Phi()) {
2681 u_ctrl = NULL; 2712 u_ctrl = NULL;
2682 for( uint j = 1; j < use->req(); j++ ) 2713 for (uint j = 1; j < use->req(); j++)
2683 if( use->in(j) == phi ) 2714 if (use->in(j) == phi)
2684 u_ctrl = dom_lca( u_ctrl, use->in(0)->in(j) ); 2715 u_ctrl = dom_lca(u_ctrl, use->in(0)->in(j));
2685 } 2716 }
2686 IdealLoopTree *u_loop = get_loop(u_ctrl); 2717 IdealLoopTree *u_loop = get_loop(u_ctrl);
2687 // Look for loop-invariant use 2718 // Look for loop-invariant use
2688 if( u_loop == loop ) continue; 2719 if (u_loop == loop) continue;
2689 if( loop->is_member( u_loop ) ) continue; 2720 if (loop->is_member(u_loop)) continue;
2690 // Check that use is live out the bottom. Assuming the trip-counter 2721 // Check that use is live out the bottom. Assuming the trip-counter
2691 // update is right at the bottom, uses of of the loop middle are ok. 2722 // update is right at the bottom, uses of of the loop middle are ok.
2692 if( dom_lca( exit, u_ctrl ) != exit ) continue; 2723 if (dom_lca(exit, u_ctrl) != exit) continue;
2693 // protect against stride not being a constant
2694 if( !cle->stride_is_con() ) continue;
2695 // Hit! Refactor use to use the post-incremented tripcounter. 2724 // Hit! Refactor use to use the post-incremented tripcounter.
2696 // Compute a post-increment tripcounter. 2725 // Compute a post-increment tripcounter.
2697 Node *opaq = new (C, 2) Opaque2Node( C, cle->incr() ); 2726 Node *opaq = new (C, 2) Opaque2Node( C, cle->incr() );
2698 register_new_node( opaq, u_ctrl ); 2727 register_new_node( opaq, u_ctrl );
2699 Node *neg_stride = _igvn.intcon(-cle->stride_con()); 2728 Node *neg_stride = _igvn.intcon(-cle->stride_con());
2700 set_ctrl(neg_stride, C->root()); 2729 set_ctrl(neg_stride, C->root());
2701 Node *post = new (C, 3) AddINode( opaq, neg_stride); 2730 Node *post = new (C, 3) AddINode( opaq, neg_stride);
2702 register_new_node( post, u_ctrl ); 2731 register_new_node( post, u_ctrl );
2703 _igvn.hash_delete(use); 2732 _igvn.hash_delete(use);
2704 _igvn._worklist.push(use); 2733 _igvn._worklist.push(use);
2705 for( uint j = 1; j < use->req(); j++ ) 2734 for (uint j = 1; j < use->req(); j++) {
2706 if( use->in(j) == phi ) 2735 if (use->in(j) == phi)
2707 use->set_req(j, post); 2736 use->set_req(j, post);
2737 }
2708 // Since DU info changed, rerun loop 2738 // Since DU info changed, rerun loop
2709 progress = true; 2739 progress = true;
2710 break; 2740 break;
2711 } 2741 }
2712 } 2742 }