Mercurial > hg > truffle
annotate src/share/vm/opto/loopopts.cpp @ 1721:413ad0331a0c
6977924: Changes for 6975078 produce build error with certain gcc versions
Summary: The changes introduced for 6975078 assign badHeapOopVal to the _allocation field in the ResourceObj class. In 32 bit linux builds with certain versions of gcc this assignment will be flagged as an error while compiling allocation.cpp. In 32 bit builds the constant value badHeapOopVal (which is cast to an intptr_t) is negative. The _allocation field is typed as an unsigned intptr_t and gcc catches this as an error.
Reviewed-by: jcoomes, ysr, phh
author | johnc |
---|---|
date | Wed, 18 Aug 2010 10:59:06 -0700 |
parents | 6027dddc26c6 |
children | f95d63e2154a |
rev | line source |
---|---|
0 | 1 /* |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1254
diff
changeset
|
2 * Copyright (c) 1999, 2010, Oracle and/or its affiliates. All rights reserved. |
0 | 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 * | |
5 * This code is free software; you can redistribute it and/or modify it | |
6 * under the terms of the GNU General Public License version 2 only, as | |
7 * published by the Free Software Foundation. | |
8 * | |
9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
12 * version 2 for more details (a copy is included in the LICENSE file that | |
13 * accompanied this code). | |
14 * | |
15 * You should have received a copy of the GNU General Public License version | |
16 * 2 along with this work; if not, write to the Free Software Foundation, | |
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
18 * | |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1254
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1254
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1254
diff
changeset
|
21 * questions. |
0 | 22 * |
23 */ | |
24 | |
25 #include "incls/_precompiled.incl" | |
26 #include "incls/_loopopts.cpp.incl" | |
27 | |
28 //============================================================================= | |
29 //------------------------------split_thru_phi--------------------------------- | |
30 // Split Node 'n' through merge point if there is enough win. | |
31 Node *PhaseIdealLoop::split_thru_phi( Node *n, Node *region, int policy ) { | |
69 | 32 if (n->Opcode() == Op_ConvI2L && n->bottom_type() != TypeLong::LONG) { |
33 // ConvI2L may have type information on it which is unsafe to push up | |
34 // so disable this for now | |
35 return NULL; | |
36 } | |
0 | 37 int wins = 0; |
38 assert( !n->is_CFG(), "" ); | |
39 assert( region->is_Region(), "" ); | |
64
b8f5ba577b02
6673473: (Escape Analysis) Add the instance's field information to PhiNode
kvn
parents:
35
diff
changeset
|
40 |
b8f5ba577b02
6673473: (Escape Analysis) Add the instance's field information to PhiNode
kvn
parents:
35
diff
changeset
|
41 const Type* type = n->bottom_type(); |
b8f5ba577b02
6673473: (Escape Analysis) Add the instance's field information to PhiNode
kvn
parents:
35
diff
changeset
|
42 const TypeOopPtr *t_oop = _igvn.type(n)->isa_oopptr(); |
b8f5ba577b02
6673473: (Escape Analysis) Add the instance's field information to PhiNode
kvn
parents:
35
diff
changeset
|
43 Node *phi; |
223 | 44 if( t_oop != NULL && t_oop->is_known_instance_field() ) { |
64
b8f5ba577b02
6673473: (Escape Analysis) Add the instance's field information to PhiNode
kvn
parents:
35
diff
changeset
|
45 int iid = t_oop->instance_id(); |
b8f5ba577b02
6673473: (Escape Analysis) Add the instance's field information to PhiNode
kvn
parents:
35
diff
changeset
|
46 int index = C->get_alias_index(t_oop); |
b8f5ba577b02
6673473: (Escape Analysis) Add the instance's field information to PhiNode
kvn
parents:
35
diff
changeset
|
47 int offset = t_oop->offset(); |
b8f5ba577b02
6673473: (Escape Analysis) Add the instance's field information to PhiNode
kvn
parents:
35
diff
changeset
|
48 phi = new (C,region->req()) PhiNode(region, type, NULL, iid, index, offset); |
b8f5ba577b02
6673473: (Escape Analysis) Add the instance's field information to PhiNode
kvn
parents:
35
diff
changeset
|
49 } else { |
1254
4ee1c645110e
6924097: assert((_type == Type::MEMORY) == (_adr_type != 0),"adr_type for memory phis only")
kvn
parents:
866
diff
changeset
|
50 phi = PhiNode::make_blank(region, n); |
64
b8f5ba577b02
6673473: (Escape Analysis) Add the instance's field information to PhiNode
kvn
parents:
35
diff
changeset
|
51 } |
0 | 52 uint old_unique = C->unique(); |
53 for( uint i = 1; i < region->req(); i++ ) { | |
54 Node *x; | |
55 Node* the_clone = NULL; | |
56 if( region->in(i) == C->top() ) { | |
57 x = C->top(); // Dead path? Use a dead data op | |
58 } else { | |
59 x = n->clone(); // Else clone up the data op | |
60 the_clone = x; // Remember for possible deletion. | |
61 // Alter data node to use pre-phi inputs | |
62 if( n->in(0) == region ) | |
63 x->set_req( 0, region->in(i) ); | |
64 for( uint j = 1; j < n->req(); j++ ) { | |
65 Node *in = n->in(j); | |
66 if( in->is_Phi() && in->in(0) == region ) | |
67 x->set_req( j, in->in(i) ); // Use pre-Phi input for the clone | |
68 } | |
69 } | |
70 // Check for a 'win' on some paths | |
71 const Type *t = x->Value(&_igvn); | |
72 | |
73 bool singleton = t->singleton(); | |
74 | |
75 // A TOP singleton indicates that there are no possible values incoming | |
76 // along a particular edge. In most cases, this is OK, and the Phi will | |
77 // be eliminated later in an Ideal call. However, we can't allow this to | |
78 // happen if the singleton occurs on loop entry, as the elimination of | |
79 // the PhiNode may cause the resulting node to migrate back to a previous | |
80 // loop iteration. | |
81 if( singleton && t == Type::TOP ) { | |
82 // Is_Loop() == false does not confirm the absence of a loop (e.g., an | |
83 // irreducible loop may not be indicated by an affirmative is_Loop()); | |
84 // therefore, the only top we can split thru a phi is on a backedge of | |
85 // a loop. | |
86 singleton &= region->is_Loop() && (i != LoopNode::EntryControl); | |
87 } | |
88 | |
89 if( singleton ) { | |
90 wins++; | |
91 x = ((PhaseGVN&)_igvn).makecon(t); | |
92 } else { | |
93 // We now call Identity to try to simplify the cloned node. | |
94 // Note that some Identity methods call phase->type(this). | |
95 // Make sure that the type array is big enough for | |
96 // our new node, even though we may throw the node away. | |
97 // (Note: This tweaking with igvn only works because x is a new node.) | |
98 _igvn.set_type(x, t); | |
293
c3e045194476
6731641: assert(m->adr_type() == mach->adr_type(),"matcher should not change adr type")
kvn
parents:
253
diff
changeset
|
99 // If x is a TypeNode, capture any more-precise type permanently into Node |
605 | 100 // otherwise it will be not updated during igvn->transform since |
293
c3e045194476
6731641: assert(m->adr_type() == mach->adr_type(),"matcher should not change adr type")
kvn
parents:
253
diff
changeset
|
101 // igvn->type(x) is set to x->Value() already. |
c3e045194476
6731641: assert(m->adr_type() == mach->adr_type(),"matcher should not change adr type")
kvn
parents:
253
diff
changeset
|
102 x->raise_bottom_type(t); |
0 | 103 Node *y = x->Identity(&_igvn); |
104 if( y != x ) { | |
105 wins++; | |
106 x = y; | |
107 } else { | |
108 y = _igvn.hash_find(x); | |
109 if( y ) { | |
110 wins++; | |
111 x = y; | |
112 } else { | |
113 // Else x is a new node we are keeping | |
114 // We do not need register_new_node_with_optimizer | |
115 // because set_type has already been called. | |
116 _igvn._worklist.push(x); | |
117 } | |
118 } | |
119 } | |
120 if (x != the_clone && the_clone != NULL) | |
121 _igvn.remove_dead_node(the_clone); | |
122 phi->set_req( i, x ); | |
123 } | |
124 // Too few wins? | |
125 if( wins <= policy ) { | |
126 _igvn.remove_dead_node(phi); | |
127 return NULL; | |
128 } | |
129 | |
130 // Record Phi | |
131 register_new_node( phi, region ); | |
132 | |
133 for( uint i2 = 1; i2 < phi->req(); i2++ ) { | |
134 Node *x = phi->in(i2); | |
135 // If we commoned up the cloned 'x' with another existing Node, | |
136 // the existing Node picks up a new use. We need to make the | |
137 // existing Node occur higher up so it dominates its uses. | |
138 Node *old_ctrl; | |
139 IdealLoopTree *old_loop; | |
140 | |
141 // The occasional new node | |
142 if( x->_idx >= old_unique ) { // Found a new, unplaced node? | |
143 old_ctrl = x->is_Con() ? C->root() : NULL; | |
144 old_loop = NULL; // Not in any prior loop | |
145 } else { | |
146 old_ctrl = x->is_Con() ? C->root() : get_ctrl(x); | |
147 old_loop = get_loop(old_ctrl); // Get prior loop | |
148 } | |
149 // New late point must dominate new use | |
150 Node *new_ctrl = dom_lca( old_ctrl, region->in(i2) ); | |
151 // Set new location | |
152 set_ctrl(x, new_ctrl); | |
153 IdealLoopTree *new_loop = get_loop( new_ctrl ); | |
154 // If changing loop bodies, see if we need to collect into new body | |
155 if( old_loop != new_loop ) { | |
156 if( old_loop && !old_loop->_child ) | |
157 old_loop->_body.yank(x); | |
158 if( !new_loop->_child ) | |
159 new_loop->_body.push(x); // Collect body info | |
160 } | |
161 } | |
162 | |
163 return phi; | |
164 } | |
165 | |
166 //------------------------------dominated_by------------------------------------ | |
167 // Replace the dominated test with an obvious true or false. Place it on the | |
168 // IGVN worklist for later cleanup. Move control-dependent data Nodes on the | |
169 // live path up to the dominating control. | |
170 void PhaseIdealLoop::dominated_by( Node *prevdom, Node *iff ) { | |
171 #ifndef PRODUCT | |
172 if( VerifyLoopOptimizations && PrintOpto ) tty->print_cr("dominating test"); | |
173 #endif | |
174 | |
175 | |
176 // prevdom is the dominating projection of the dominating test. | |
177 assert( iff->is_If(), "" ); | |
178 assert( iff->Opcode() == Op_If || iff->Opcode() == Op_CountedLoopEnd, "Check this code when new subtype is added"); | |
179 int pop = prevdom->Opcode(); | |
180 assert( pop == Op_IfFalse || pop == Op_IfTrue, "" ); | |
181 // 'con' is set to true or false to kill the dominated test. | |
182 Node *con = _igvn.makecon(pop == Op_IfTrue ? TypeInt::ONE : TypeInt::ZERO); | |
183 set_ctrl(con, C->root()); // Constant gets a new use | |
184 // Hack the dominated test | |
185 _igvn.hash_delete(iff); | |
186 iff->set_req(1, con); | |
187 _igvn._worklist.push(iff); | |
188 | |
189 // If I dont have a reachable TRUE and FALSE path following the IfNode then | |
190 // I can assume this path reaches an infinite loop. In this case it's not | |
191 // important to optimize the data Nodes - either the whole compilation will | |
192 // be tossed or this path (and all data Nodes) will go dead. | |
193 if( iff->outcnt() != 2 ) return; | |
194 | |
195 // Make control-dependent data Nodes on the live path (path that will remain | |
196 // once the dominated IF is removed) become control-dependent on the | |
197 // dominating projection. | |
198 Node* dp = ((IfNode*)iff)->proj_out(pop == Op_IfTrue); | |
199 IdealLoopTree *old_loop = get_loop(dp); | |
200 | |
201 for (DUIterator_Fast imax, i = dp->fast_outs(imax); i < imax; i++) { | |
202 Node* cd = dp->fast_out(i); // Control-dependent node | |
203 if( cd->depends_only_on_test() ) { | |
204 assert( cd->in(0) == dp, "" ); | |
205 _igvn.hash_delete( cd ); | |
206 cd->set_req(0, prevdom); | |
207 set_early_ctrl( cd ); | |
208 _igvn._worklist.push(cd); | |
209 IdealLoopTree *new_loop = get_loop(get_ctrl(cd)); | |
210 if( old_loop != new_loop ) { | |
211 if( !old_loop->_child ) old_loop->_body.yank(cd); | |
212 if( !new_loop->_child ) new_loop->_body.push(cd); | |
213 } | |
214 --i; | |
215 --imax; | |
216 } | |
217 } | |
218 } | |
219 | |
220 //------------------------------has_local_phi_input---------------------------- | |
221 // Return TRUE if 'n' has Phi inputs from its local block and no other | |
222 // block-local inputs (all non-local-phi inputs come from earlier blocks) | |
223 Node *PhaseIdealLoop::has_local_phi_input( Node *n ) { | |
224 Node *n_ctrl = get_ctrl(n); | |
225 // See if some inputs come from a Phi in this block, or from before | |
226 // this block. | |
227 uint i; | |
228 for( i = 1; i < n->req(); i++ ) { | |
229 Node *phi = n->in(i); | |
230 if( phi->is_Phi() && phi->in(0) == n_ctrl ) | |
231 break; | |
232 } | |
233 if( i >= n->req() ) | |
234 return NULL; // No Phi inputs; nowhere to clone thru | |
235 | |
236 // Check for inputs created between 'n' and the Phi input. These | |
237 // must split as well; they have already been given the chance | |
238 // (courtesy of a post-order visit) and since they did not we must | |
239 // recover the 'cost' of splitting them by being very profitable | |
240 // when splitting 'n'. Since this is unlikely we simply give up. | |
241 for( i = 1; i < n->req(); i++ ) { | |
242 Node *m = n->in(i); | |
243 if( get_ctrl(m) == n_ctrl && !m->is_Phi() ) { | |
244 // We allow the special case of AddP's with no local inputs. | |
245 // This allows us to split-up address expressions. | |
246 if (m->is_AddP() && | |
247 get_ctrl(m->in(2)) != n_ctrl && | |
248 get_ctrl(m->in(3)) != n_ctrl) { | |
249 // Move the AddP up to dominating point | |
250 set_ctrl_and_loop(m, find_non_split_ctrl(idom(n_ctrl))); | |
251 continue; | |
252 } | |
253 return NULL; | |
254 } | |
255 } | |
256 | |
257 return n_ctrl; | |
258 } | |
259 | |
260 //------------------------------remix_address_expressions---------------------- | |
261 // Rework addressing expressions to get the most loop-invariant stuff | |
262 // moved out. We'd like to do all associative operators, but it's especially | |
263 // important (common) to do address expressions. | |
264 Node *PhaseIdealLoop::remix_address_expressions( Node *n ) { | |
265 if (!has_ctrl(n)) return NULL; | |
266 Node *n_ctrl = get_ctrl(n); | |
267 IdealLoopTree *n_loop = get_loop(n_ctrl); | |
268 | |
269 // See if 'n' mixes loop-varying and loop-invariant inputs and | |
270 // itself is loop-varying. | |
271 | |
272 // Only interested in binary ops (and AddP) | |
273 if( n->req() < 3 || n->req() > 4 ) return NULL; | |
274 | |
275 Node *n1_ctrl = get_ctrl(n->in( 1)); | |
276 Node *n2_ctrl = get_ctrl(n->in( 2)); | |
277 Node *n3_ctrl = get_ctrl(n->in(n->req() == 3 ? 2 : 3)); | |
278 IdealLoopTree *n1_loop = get_loop( n1_ctrl ); | |
279 IdealLoopTree *n2_loop = get_loop( n2_ctrl ); | |
280 IdealLoopTree *n3_loop = get_loop( n3_ctrl ); | |
281 | |
282 // Does one of my inputs spin in a tighter loop than self? | |
283 if( (n_loop->is_member( n1_loop ) && n_loop != n1_loop) || | |
284 (n_loop->is_member( n2_loop ) && n_loop != n2_loop) || | |
285 (n_loop->is_member( n3_loop ) && n_loop != n3_loop) ) | |
286 return NULL; // Leave well enough alone | |
287 | |
288 // Is at least one of my inputs loop-invariant? | |
289 if( n1_loop == n_loop && | |
290 n2_loop == n_loop && | |
291 n3_loop == n_loop ) | |
292 return NULL; // No loop-invariant inputs | |
293 | |
294 | |
295 int n_op = n->Opcode(); | |
296 | |
297 // Replace expressions like ((V+I) << 2) with (V<<2 + I<<2). | |
298 if( n_op == Op_LShiftI ) { | |
299 // Scale is loop invariant | |
300 Node *scale = n->in(2); | |
301 Node *scale_ctrl = get_ctrl(scale); | |
302 IdealLoopTree *scale_loop = get_loop(scale_ctrl ); | |
303 if( n_loop == scale_loop || !scale_loop->is_member( n_loop ) ) | |
304 return NULL; | |
305 const TypeInt *scale_t = scale->bottom_type()->isa_int(); | |
306 if( scale_t && scale_t->is_con() && scale_t->get_con() >= 16 ) | |
307 return NULL; // Dont bother with byte/short masking | |
308 // Add must vary with loop (else shift would be loop-invariant) | |
309 Node *add = n->in(1); | |
310 Node *add_ctrl = get_ctrl(add); | |
311 IdealLoopTree *add_loop = get_loop(add_ctrl); | |
312 //assert( n_loop == add_loop, "" ); | |
313 if( n_loop != add_loop ) return NULL; // happens w/ evil ZKM loops | |
314 | |
315 // Convert I-V into I+ (0-V); same for V-I | |
316 if( add->Opcode() == Op_SubI && | |
317 _igvn.type( add->in(1) ) != TypeInt::ZERO ) { | |
318 Node *zero = _igvn.intcon(0); | |
319 set_ctrl(zero, C->root()); | |
320 Node *neg = new (C, 3) SubINode( _igvn.intcon(0), add->in(2) ); | |
321 register_new_node( neg, get_ctrl(add->in(2) ) ); | |
322 add = new (C, 3) AddINode( add->in(1), neg ); | |
323 register_new_node( add, add_ctrl ); | |
324 } | |
325 if( add->Opcode() != Op_AddI ) return NULL; | |
326 // See if one add input is loop invariant | |
327 Node *add_var = add->in(1); | |
328 Node *add_var_ctrl = get_ctrl(add_var); | |
329 IdealLoopTree *add_var_loop = get_loop(add_var_ctrl ); | |
330 Node *add_invar = add->in(2); | |
331 Node *add_invar_ctrl = get_ctrl(add_invar); | |
332 IdealLoopTree *add_invar_loop = get_loop(add_invar_ctrl ); | |
333 if( add_var_loop == n_loop ) { | |
334 } else if( add_invar_loop == n_loop ) { | |
335 // Swap to find the invariant part | |
336 add_invar = add_var; | |
337 add_invar_ctrl = add_var_ctrl; | |
338 add_invar_loop = add_var_loop; | |
339 add_var = add->in(2); | |
340 Node *add_var_ctrl = get_ctrl(add_var); | |
341 IdealLoopTree *add_var_loop = get_loop(add_var_ctrl ); | |
342 } else // Else neither input is loop invariant | |
343 return NULL; | |
344 if( n_loop == add_invar_loop || !add_invar_loop->is_member( n_loop ) ) | |
345 return NULL; // No invariant part of the add? | |
346 | |
347 // Yes! Reshape address expression! | |
348 Node *inv_scale = new (C, 3) LShiftINode( add_invar, scale ); | |
850
fd50a67f97d1
6860469: remix_address_expressions sets incorrect control causing crash in split_if_with_block_post
never
parents:
834
diff
changeset
|
349 Node *inv_scale_ctrl = |
fd50a67f97d1
6860469: remix_address_expressions sets incorrect control causing crash in split_if_with_block_post
never
parents:
834
diff
changeset
|
350 dom_depth(add_invar_ctrl) > dom_depth(scale_ctrl) ? |
fd50a67f97d1
6860469: remix_address_expressions sets incorrect control causing crash in split_if_with_block_post
never
parents:
834
diff
changeset
|
351 add_invar_ctrl : scale_ctrl; |
fd50a67f97d1
6860469: remix_address_expressions sets incorrect control causing crash in split_if_with_block_post
never
parents:
834
diff
changeset
|
352 register_new_node( inv_scale, inv_scale_ctrl ); |
0 | 353 Node *var_scale = new (C, 3) LShiftINode( add_var, scale ); |
354 register_new_node( var_scale, n_ctrl ); | |
355 Node *var_add = new (C, 3) AddINode( var_scale, inv_scale ); | |
356 register_new_node( var_add, n_ctrl ); | |
1621
6027dddc26c6
6677629: PhaseIterGVN::subsume_node() should call hash_delete() and add_users_to_worklist()
kvn
parents:
1552
diff
changeset
|
357 _igvn.replace_node( n, var_add ); |
0 | 358 return var_add; |
359 } | |
360 | |
361 // Replace (I+V) with (V+I) | |
362 if( n_op == Op_AddI || | |
363 n_op == Op_AddL || | |
364 n_op == Op_AddF || | |
365 n_op == Op_AddD || | |
366 n_op == Op_MulI || | |
367 n_op == Op_MulL || | |
368 n_op == Op_MulF || | |
369 n_op == Op_MulD ) { | |
370 if( n2_loop == n_loop ) { | |
371 assert( n1_loop != n_loop, "" ); | |
372 n->swap_edges(1, 2); | |
373 } | |
374 } | |
375 | |
376 // Replace ((I1 +p V) +p I2) with ((I1 +p I2) +p V), | |
377 // but not if I2 is a constant. | |
378 if( n_op == Op_AddP ) { | |
379 if( n2_loop == n_loop && n3_loop != n_loop ) { | |
380 if( n->in(2)->Opcode() == Op_AddP && !n->in(3)->is_Con() ) { | |
381 Node *n22_ctrl = get_ctrl(n->in(2)->in(2)); | |
382 Node *n23_ctrl = get_ctrl(n->in(2)->in(3)); | |
383 IdealLoopTree *n22loop = get_loop( n22_ctrl ); | |
384 IdealLoopTree *n23_loop = get_loop( n23_ctrl ); | |
385 if( n22loop != n_loop && n22loop->is_member(n_loop) && | |
386 n23_loop == n_loop ) { | |
387 Node *add1 = new (C, 4) AddPNode( n->in(1), n->in(2)->in(2), n->in(3) ); | |
388 // Stuff new AddP in the loop preheader | |
389 register_new_node( add1, n_loop->_head->in(LoopNode::EntryControl) ); | |
390 Node *add2 = new (C, 4) AddPNode( n->in(1), add1, n->in(2)->in(3) ); | |
391 register_new_node( add2, n_ctrl ); | |
1621
6027dddc26c6
6677629: PhaseIterGVN::subsume_node() should call hash_delete() and add_users_to_worklist()
kvn
parents:
1552
diff
changeset
|
392 _igvn.replace_node( n, add2 ); |
0 | 393 return add2; |
394 } | |
395 } | |
396 } | |
397 | |
398 // Replace (I1 +p (I2 + V)) with ((I1 +p I2) +p V) | |
399 if( n2_loop != n_loop && n3_loop == n_loop ) { | |
400 if( n->in(3)->Opcode() == Op_AddI ) { | |
401 Node *V = n->in(3)->in(1); | |
402 Node *I = n->in(3)->in(2); | |
403 if( is_member(n_loop,get_ctrl(V)) ) { | |
404 } else { | |
405 Node *tmp = V; V = I; I = tmp; | |
406 } | |
407 if( !is_member(n_loop,get_ctrl(I)) ) { | |
408 Node *add1 = new (C, 4) AddPNode( n->in(1), n->in(2), I ); | |
409 // Stuff new AddP in the loop preheader | |
410 register_new_node( add1, n_loop->_head->in(LoopNode::EntryControl) ); | |
411 Node *add2 = new (C, 4) AddPNode( n->in(1), add1, V ); | |
412 register_new_node( add2, n_ctrl ); | |
1621
6027dddc26c6
6677629: PhaseIterGVN::subsume_node() should call hash_delete() and add_users_to_worklist()
kvn
parents:
1552
diff
changeset
|
413 _igvn.replace_node( n, add2 ); |
0 | 414 return add2; |
415 } | |
416 } | |
417 } | |
418 } | |
419 | |
420 return NULL; | |
421 } | |
422 | |
423 //------------------------------conditional_move------------------------------- | |
424 // Attempt to replace a Phi with a conditional move. We have some pretty | |
425 // strict profitability requirements. All Phis at the merge point must | |
426 // be converted, so we can remove the control flow. We need to limit the | |
427 // number of c-moves to a small handful. All code that was in the side-arms | |
428 // of the CFG diamond is now speculatively executed. This code has to be | |
429 // "cheap enough". We are pretty much limited to CFG diamonds that merge | |
430 // 1 or 2 items with a total of 1 or 2 ops executed speculatively. | |
431 Node *PhaseIdealLoop::conditional_move( Node *region ) { | |
432 | |
433 assert( region->is_Region(), "sanity check" ); | |
434 if( region->req() != 3 ) return NULL; | |
435 | |
436 // Check for CFG diamond | |
437 Node *lp = region->in(1); | |
438 Node *rp = region->in(2); | |
439 if( !lp || !rp ) return NULL; | |
440 Node *lp_c = lp->in(0); | |
441 if( lp_c == NULL || lp_c != rp->in(0) || !lp_c->is_If() ) return NULL; | |
442 IfNode *iff = lp_c->as_If(); | |
443 | |
444 // Check for highly predictable branch. No point in CMOV'ing if | |
445 // we are going to predict accurately all the time. | |
446 // %%% This hides patterns produced by utility methods like Math.min. | |
447 if( iff->_prob < PROB_UNLIKELY_MAG(3) || | |
448 iff->_prob > PROB_LIKELY_MAG(3) ) | |
449 return NULL; | |
450 | |
451 // Check for ops pinned in an arm of the diamond. | |
452 // Can't remove the control flow in this case | |
453 if( lp->outcnt() > 1 ) return NULL; | |
454 if( rp->outcnt() > 1 ) return NULL; | |
455 | |
456 // Check profitability | |
457 int cost = 0; | |
35
e2ae28d2ce91
6667588: Don't generate duplicated CMP for float/double values
kvn
parents:
0
diff
changeset
|
458 int phis = 0; |
0 | 459 for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) { |
460 Node *out = region->fast_out(i); | |
461 if( !out->is_Phi() ) continue; // Ignore other control edges, etc | |
35
e2ae28d2ce91
6667588: Don't generate duplicated CMP for float/double values
kvn
parents:
0
diff
changeset
|
462 phis++; |
0 | 463 PhiNode* phi = out->as_Phi(); |
464 switch (phi->type()->basic_type()) { | |
465 case T_LONG: | |
466 cost++; // Probably encodes as 2 CMOV's | |
467 case T_INT: // These all CMOV fine | |
468 case T_FLOAT: | |
469 case T_DOUBLE: | |
470 case T_ADDRESS: // (RawPtr) | |
471 cost++; | |
472 break; | |
293
c3e045194476
6731641: assert(m->adr_type() == mach->adr_type(),"matcher should not change adr type")
kvn
parents:
253
diff
changeset
|
473 case T_NARROWOOP: // Fall through |
0 | 474 case T_OBJECT: { // Base oops are OK, but not derived oops |
293
c3e045194476
6731641: assert(m->adr_type() == mach->adr_type(),"matcher should not change adr type")
kvn
parents:
253
diff
changeset
|
475 const TypeOopPtr *tp = phi->type()->make_ptr()->isa_oopptr(); |
0 | 476 // Derived pointers are Bad (tm): what's the Base (for GC purposes) of a |
477 // CMOVE'd derived pointer? It's a CMOVE'd derived base. Thus | |
478 // CMOVE'ing a derived pointer requires we also CMOVE the base. If we | |
479 // have a Phi for the base here that we convert to a CMOVE all is well | |
480 // and good. But if the base is dead, we'll not make a CMOVE. Later | |
481 // the allocator will have to produce a base by creating a CMOVE of the | |
482 // relevant bases. This puts the allocator in the business of | |
483 // manufacturing expensive instructions, generally a bad plan. | |
484 // Just Say No to Conditionally-Moved Derived Pointers. | |
485 if( tp && tp->offset() != 0 ) | |
486 return NULL; | |
487 cost++; | |
488 break; | |
489 } | |
490 default: | |
491 return NULL; // In particular, can't do memory or I/O | |
492 } | |
493 // Add in cost any speculative ops | |
494 for( uint j = 1; j < region->req(); j++ ) { | |
495 Node *proj = region->in(j); | |
496 Node *inp = phi->in(j); | |
497 if (get_ctrl(inp) == proj) { // Found local op | |
498 cost++; | |
499 // Check for a chain of dependent ops; these will all become | |
500 // speculative in a CMOV. | |
501 for( uint k = 1; k < inp->req(); k++ ) | |
502 if (get_ctrl(inp->in(k)) == proj) | |
503 return NULL; // Too much speculative goo | |
504 } | |
505 } | |
293
c3e045194476
6731641: assert(m->adr_type() == mach->adr_type(),"matcher should not change adr type")
kvn
parents:
253
diff
changeset
|
506 // See if the Phi is used by a Cmp or Narrow oop Decode/Encode. |
c3e045194476
6731641: assert(m->adr_type() == mach->adr_type(),"matcher should not change adr type")
kvn
parents:
253
diff
changeset
|
507 // This will likely Split-If, a higher-payoff operation. |
0 | 508 for (DUIterator_Fast kmax, k = phi->fast_outs(kmax); k < kmax; k++) { |
509 Node* use = phi->fast_out(k); | |
293
c3e045194476
6731641: assert(m->adr_type() == mach->adr_type(),"matcher should not change adr type")
kvn
parents:
253
diff
changeset
|
510 if( use->is_Cmp() || use->is_DecodeN() || use->is_EncodeP() ) |
0 | 511 return NULL; |
512 } | |
513 } | |
514 if( cost >= ConditionalMoveLimit ) return NULL; // Too much goo | |
35
e2ae28d2ce91
6667588: Don't generate duplicated CMP for float/double values
kvn
parents:
0
diff
changeset
|
515 Node* bol = iff->in(1); |
e2ae28d2ce91
6667588: Don't generate duplicated CMP for float/double values
kvn
parents:
0
diff
changeset
|
516 assert( bol->Opcode() == Op_Bool, "" ); |
e2ae28d2ce91
6667588: Don't generate duplicated CMP for float/double values
kvn
parents:
0
diff
changeset
|
517 int cmp_op = bol->in(1)->Opcode(); |
e2ae28d2ce91
6667588: Don't generate duplicated CMP for float/double values
kvn
parents:
0
diff
changeset
|
518 // It is expensive to generate flags from a float compare. |
e2ae28d2ce91
6667588: Don't generate duplicated CMP for float/double values
kvn
parents:
0
diff
changeset
|
519 // Avoid duplicated float compare. |
e2ae28d2ce91
6667588: Don't generate duplicated CMP for float/double values
kvn
parents:
0
diff
changeset
|
520 if( phis > 1 && (cmp_op == Op_CmpF || cmp_op == Op_CmpD)) return NULL; |
0 | 521 |
522 // -------------- | |
523 // Now replace all Phis with CMOV's | |
524 Node *cmov_ctrl = iff->in(0); | |
525 uint flip = (lp->Opcode() == Op_IfTrue); | |
526 while( 1 ) { | |
527 PhiNode* phi = NULL; | |
528 for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) { | |
529 Node *out = region->fast_out(i); | |
530 if (out->is_Phi()) { | |
531 phi = out->as_Phi(); | |
532 break; | |
533 } | |
534 } | |
535 if (phi == NULL) break; | |
536 #ifndef PRODUCT | |
537 if( PrintOpto && VerifyLoopOptimizations ) tty->print_cr("CMOV"); | |
538 #endif | |
539 // Move speculative ops | |
540 for( uint j = 1; j < region->req(); j++ ) { | |
541 Node *proj = region->in(j); | |
542 Node *inp = phi->in(j); | |
543 if (get_ctrl(inp) == proj) { // Found local op | |
544 #ifndef PRODUCT | |
545 if( PrintOpto && VerifyLoopOptimizations ) { | |
546 tty->print(" speculate: "); | |
547 inp->dump(); | |
548 } | |
549 #endif | |
550 set_ctrl(inp, cmov_ctrl); | |
551 } | |
552 } | |
553 Node *cmov = CMoveNode::make( C, cmov_ctrl, iff->in(1), phi->in(1+flip), phi->in(2-flip), _igvn.type(phi) ); | |
554 register_new_node( cmov, cmov_ctrl ); | |
1621
6027dddc26c6
6677629: PhaseIterGVN::subsume_node() should call hash_delete() and add_users_to_worklist()
kvn
parents:
1552
diff
changeset
|
555 _igvn.replace_node( phi, cmov ); |
0 | 556 #ifndef PRODUCT |
557 if( VerifyLoopOptimizations ) verify(); | |
558 #endif | |
559 } | |
560 | |
561 // The useless CFG diamond will fold up later; see the optimization in | |
562 // RegionNode::Ideal. | |
563 _igvn._worklist.push(region); | |
564 | |
565 return iff->in(1); | |
566 } | |
567 | |
568 //------------------------------split_if_with_blocks_pre----------------------- | |
569 // Do the real work in a non-recursive function. Data nodes want to be | |
570 // cloned in the pre-order so they can feed each other nicely. | |
571 Node *PhaseIdealLoop::split_if_with_blocks_pre( Node *n ) { | |
572 // Cloning these guys is unlikely to win | |
573 int n_op = n->Opcode(); | |
574 if( n_op == Op_MergeMem ) return n; | |
575 if( n->is_Proj() ) return n; | |
576 // Do not clone-up CmpFXXX variations, as these are always | |
577 // followed by a CmpI | |
578 if( n->is_Cmp() ) return n; | |
579 // Attempt to use a conditional move instead of a phi/branch | |
580 if( ConditionalMoveLimit > 0 && n_op == Op_Region ) { | |
581 Node *cmov = conditional_move( n ); | |
582 if( cmov ) return cmov; | |
583 } | |
253
b0fe4deeb9fb
6726999: nsk/stress/jck12a/jck12a010 assert(n != null,"Bad immediate dominator info.")
kvn
parents:
251
diff
changeset
|
584 if( n->is_CFG() || n->is_LoadStore() ) |
b0fe4deeb9fb
6726999: nsk/stress/jck12a/jck12a010 assert(n != null,"Bad immediate dominator info.")
kvn
parents:
251
diff
changeset
|
585 return n; |
0 | 586 if( n_op == Op_Opaque1 || // Opaque nodes cannot be mod'd |
587 n_op == Op_Opaque2 ) { | |
588 if( !C->major_progress() ) // If chance of no more loop opts... | |
589 _igvn._worklist.push(n); // maybe we'll remove them | |
590 return n; | |
591 } | |
592 | |
593 if( n->is_Con() ) return n; // No cloning for Con nodes | |
594 | |
595 Node *n_ctrl = get_ctrl(n); | |
596 if( !n_ctrl ) return n; // Dead node | |
597 | |
598 // Attempt to remix address expressions for loop invariants | |
599 Node *m = remix_address_expressions( n ); | |
600 if( m ) return m; | |
601 | |
602 // Determine if the Node has inputs from some local Phi. | |
603 // Returns the block to clone thru. | |
604 Node *n_blk = has_local_phi_input( n ); | |
605 if( !n_blk ) return n; | |
606 // Do not clone the trip counter through on a CountedLoop | |
607 // (messes up the canonical shape). | |
608 if( n_blk->is_CountedLoop() && n->Opcode() == Op_AddI ) return n; | |
609 | |
610 // Check for having no control input; not pinned. Allow | |
611 // dominating control. | |
612 if( n->in(0) ) { | |
613 Node *dom = idom(n_blk); | |
614 if( dom_lca( n->in(0), dom ) != n->in(0) ) | |
615 return n; | |
616 } | |
617 // Policy: when is it profitable. You must get more wins than | |
618 // policy before it is considered profitable. Policy is usually 0, | |
619 // so 1 win is considered profitable. Big merges will require big | |
620 // cloning, so get a larger policy. | |
621 int policy = n_blk->req() >> 2; | |
622 | |
623 // If the loop is a candidate for range check elimination, | |
624 // delay splitting through it's phi until a later loop optimization | |
625 if (n_blk->is_CountedLoop()) { | |
626 IdealLoopTree *lp = get_loop(n_blk); | |
627 if (lp && lp->_rce_candidate) { | |
628 return n; | |
629 } | |
630 } | |
631 | |
632 // Use same limit as split_if_with_blocks_post | |
633 if( C->unique() > 35000 ) return n; // Method too big | |
634 | |
635 // Split 'n' through the merge point if it is profitable | |
636 Node *phi = split_thru_phi( n, n_blk, policy ); | |
637 if( !phi ) return n; | |
638 | |
639 // Found a Phi to split thru! | |
640 // Replace 'n' with the new phi | |
1621
6027dddc26c6
6677629: PhaseIterGVN::subsume_node() should call hash_delete() and add_users_to_worklist()
kvn
parents:
1552
diff
changeset
|
641 _igvn.replace_node( n, phi ); |
0 | 642 // Moved a load around the loop, 'en-registering' something. |
643 if( n_blk->Opcode() == Op_Loop && n->is_Load() && | |
644 !phi->in(LoopNode::LoopBackControl)->is_Load() ) | |
645 C->set_major_progress(); | |
646 | |
647 return phi; | |
648 } | |
649 | |
650 static bool merge_point_too_heavy(Compile* C, Node* region) { | |
651 // Bail out if the region and its phis have too many users. | |
652 int weight = 0; | |
653 for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) { | |
654 weight += region->fast_out(i)->outcnt(); | |
655 } | |
656 int nodes_left = MaxNodeLimit - C->unique(); | |
657 if (weight * 8 > nodes_left) { | |
658 #ifndef PRODUCT | |
659 if (PrintOpto) | |
660 tty->print_cr("*** Split-if bails out: %d nodes, region weight %d", C->unique(), weight); | |
661 #endif | |
662 return true; | |
663 } else { | |
664 return false; | |
665 } | |
666 } | |
667 | |
668 static bool merge_point_safe(Node* region) { | |
669 // 4799512: Stop split_if_with_blocks from splitting a block with a ConvI2LNode | |
670 // having a PhiNode input. This sidesteps the dangerous case where the split | |
671 // ConvI2LNode may become TOP if the input Value() does not | |
672 // overlap the ConvI2L range, leaving a node which may not dominate its | |
673 // uses. | |
674 // A better fix for this problem can be found in the BugTraq entry, but | |
675 // expediency for Mantis demands this hack. | |
834
0f2d888530e7
6855164: SIGSEGV during compilation of method involving loop over CharSequence.
cfang
parents:
605
diff
changeset
|
676 // 6855164: If the merge point has a FastLockNode with a PhiNode input, we stop |
0f2d888530e7
6855164: SIGSEGV during compilation of method involving loop over CharSequence.
cfang
parents:
605
diff
changeset
|
677 // split_if_with_blocks from splitting a block because we could not move around |
0f2d888530e7
6855164: SIGSEGV during compilation of method involving loop over CharSequence.
cfang
parents:
605
diff
changeset
|
678 // the FastLockNode. |
0 | 679 for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) { |
680 Node* n = region->fast_out(i); | |
681 if (n->is_Phi()) { | |
682 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) { | |
683 Node* m = n->fast_out(j); | |
834
0f2d888530e7
6855164: SIGSEGV during compilation of method involving loop over CharSequence.
cfang
parents:
605
diff
changeset
|
684 if (m->is_FastLock()) |
0 | 685 return false; |
834
0f2d888530e7
6855164: SIGSEGV during compilation of method involving loop over CharSequence.
cfang
parents:
605
diff
changeset
|
686 #ifdef _LP64 |
0f2d888530e7
6855164: SIGSEGV during compilation of method involving loop over CharSequence.
cfang
parents:
605
diff
changeset
|
687 if (m->Opcode() == Op_ConvI2L) |
0f2d888530e7
6855164: SIGSEGV during compilation of method involving loop over CharSequence.
cfang
parents:
605
diff
changeset
|
688 return false; |
0f2d888530e7
6855164: SIGSEGV during compilation of method involving loop over CharSequence.
cfang
parents:
605
diff
changeset
|
689 #endif |
0 | 690 } |
691 } | |
692 } | |
693 return true; | |
694 } | |
695 | |
696 | |
697 //------------------------------place_near_use--------------------------------- | |
698 // Place some computation next to use but not inside inner loops. | |
699 // For inner loop uses move it to the preheader area. | |
700 Node *PhaseIdealLoop::place_near_use( Node *useblock ) const { | |
701 IdealLoopTree *u_loop = get_loop( useblock ); | |
702 return (u_loop->_irreducible || u_loop->_child) | |
703 ? useblock | |
704 : u_loop->_head->in(LoopNode::EntryControl); | |
705 } | |
706 | |
707 | |
708 //------------------------------split_if_with_blocks_post---------------------- | |
709 // Do the real work in a non-recursive function. CFG hackery wants to be | |
710 // in the post-order, so it can dirty the I-DOM info and not use the dirtied | |
711 // info. | |
712 void PhaseIdealLoop::split_if_with_blocks_post( Node *n ) { | |
713 | |
714 // Cloning Cmp through Phi's involves the split-if transform. | |
715 // FastLock is not used by an If | |
716 if( n->is_Cmp() && !n->is_FastLock() ) { | |
717 if( C->unique() > 35000 ) return; // Method too big | |
718 | |
719 // Do not do 'split-if' if irreducible loops are present. | |
720 if( _has_irreducible_loops ) | |
721 return; | |
722 | |
723 Node *n_ctrl = get_ctrl(n); | |
724 // Determine if the Node has inputs from some local Phi. | |
725 // Returns the block to clone thru. | |
726 Node *n_blk = has_local_phi_input( n ); | |
727 if( n_blk != n_ctrl ) return; | |
728 | |
729 if( merge_point_too_heavy(C, n_ctrl) ) | |
730 return; | |
731 | |
732 if( n->outcnt() != 1 ) return; // Multiple bool's from 1 compare? | |
733 Node *bol = n->unique_out(); | |
734 assert( bol->is_Bool(), "expect a bool here" ); | |
735 if( bol->outcnt() != 1 ) return;// Multiple branches from 1 compare? | |
736 Node *iff = bol->unique_out(); | |
737 | |
738 // Check some safety conditions | |
739 if( iff->is_If() ) { // Classic split-if? | |
740 if( iff->in(0) != n_ctrl ) return; // Compare must be in same blk as if | |
741 } else if (iff->is_CMove()) { // Trying to split-up a CMOVE | |
742 if( get_ctrl(iff->in(2)) == n_ctrl || | |
743 get_ctrl(iff->in(3)) == n_ctrl ) | |
744 return; // Inputs not yet split-up | |
745 if ( get_loop(n_ctrl) != get_loop(get_ctrl(iff)) ) { | |
746 return; // Loop-invar test gates loop-varying CMOVE | |
747 } | |
748 } else { | |
749 return; // some other kind of node, such as an Allocate | |
750 } | |
751 | |
752 // Do not do 'split-if' if some paths are dead. First do dead code | |
753 // elimination and then see if its still profitable. | |
754 for( uint i = 1; i < n_ctrl->req(); i++ ) | |
755 if( n_ctrl->in(i) == C->top() ) | |
756 return; | |
757 | |
758 // When is split-if profitable? Every 'win' on means some control flow | |
759 // goes dead, so it's almost always a win. | |
760 int policy = 0; | |
761 // If trying to do a 'Split-If' at the loop head, it is only | |
762 // profitable if the cmp folds up on BOTH paths. Otherwise we | |
763 // risk peeling a loop forever. | |
764 | |
765 // CNC - Disabled for now. Requires careful handling of loop | |
766 // body selection for the cloned code. Also, make sure we check | |
767 // for any input path not being in the same loop as n_ctrl. For | |
768 // irreducible loops we cannot check for 'n_ctrl->is_Loop()' | |
769 // because the alternative loop entry points won't be converted | |
770 // into LoopNodes. | |
771 IdealLoopTree *n_loop = get_loop(n_ctrl); | |
772 for( uint j = 1; j < n_ctrl->req(); j++ ) | |
773 if( get_loop(n_ctrl->in(j)) != n_loop ) | |
774 return; | |
775 | |
776 // Check for safety of the merge point. | |
777 if( !merge_point_safe(n_ctrl) ) { | |
778 return; | |
779 } | |
780 | |
781 // Split compare 'n' through the merge point if it is profitable | |
782 Node *phi = split_thru_phi( n, n_ctrl, policy ); | |
783 if( !phi ) return; | |
784 | |
785 // Found a Phi to split thru! | |
786 // Replace 'n' with the new phi | |
1621
6027dddc26c6
6677629: PhaseIterGVN::subsume_node() should call hash_delete() and add_users_to_worklist()
kvn
parents:
1552
diff
changeset
|
787 _igvn.replace_node( n, phi ); |
0 | 788 |
789 // Now split the bool up thru the phi | |
790 Node *bolphi = split_thru_phi( bol, n_ctrl, -1 ); | |
1621
6027dddc26c6
6677629: PhaseIterGVN::subsume_node() should call hash_delete() and add_users_to_worklist()
kvn
parents:
1552
diff
changeset
|
791 _igvn.replace_node( bol, bolphi ); |
0 | 792 assert( iff->in(1) == bolphi, "" ); |
793 if( bolphi->Value(&_igvn)->singleton() ) | |
794 return; | |
795 | |
796 // Conditional-move? Must split up now | |
797 if( !iff->is_If() ) { | |
798 Node *cmovphi = split_thru_phi( iff, n_ctrl, -1 ); | |
1621
6027dddc26c6
6677629: PhaseIterGVN::subsume_node() should call hash_delete() and add_users_to_worklist()
kvn
parents:
1552
diff
changeset
|
799 _igvn.replace_node( iff, cmovphi ); |
0 | 800 return; |
801 } | |
802 | |
803 // Now split the IF | |
804 do_split_if( iff ); | |
805 return; | |
806 } | |
807 | |
808 // Check for an IF ready to split; one that has its | |
809 // condition codes input coming from a Phi at the block start. | |
810 int n_op = n->Opcode(); | |
811 | |
812 // Check for an IF being dominated by another IF same test | |
813 if( n_op == Op_If ) { | |
814 Node *bol = n->in(1); | |
815 uint max = bol->outcnt(); | |
816 // Check for same test used more than once? | |
817 if( n_op == Op_If && max > 1 && bol->is_Bool() ) { | |
818 // Search up IDOMs to see if this IF is dominated. | |
819 Node *cutoff = get_ctrl(bol); | |
820 | |
821 // Now search up IDOMs till cutoff, looking for a dominating test | |
822 Node *prevdom = n; | |
823 Node *dom = idom(prevdom); | |
824 while( dom != cutoff ) { | |
825 if( dom->req() > 1 && dom->in(1) == bol && prevdom->in(0) == dom ) { | |
826 // Replace the dominated test with an obvious true or false. | |
827 // Place it on the IGVN worklist for later cleanup. | |
828 C->set_major_progress(); | |
829 dominated_by( prevdom, n ); | |
830 #ifndef PRODUCT | |
831 if( VerifyLoopOptimizations ) verify(); | |
832 #endif | |
833 return; | |
834 } | |
835 prevdom = dom; | |
836 dom = idom(prevdom); | |
837 } | |
838 } | |
839 } | |
840 | |
841 // See if a shared loop-varying computation has no loop-varying uses. | |
842 // Happens if something is only used for JVM state in uncommon trap exits, | |
843 // like various versions of induction variable+offset. Clone the | |
844 // computation per usage to allow it to sink out of the loop. | |
845 if (has_ctrl(n) && !n->in(0)) {// n not dead and has no control edge (can float about) | |
846 Node *n_ctrl = get_ctrl(n); | |
847 IdealLoopTree *n_loop = get_loop(n_ctrl); | |
848 if( n_loop != _ltree_root ) { | |
849 DUIterator_Fast imax, i = n->fast_outs(imax); | |
850 for (; i < imax; i++) { | |
851 Node* u = n->fast_out(i); | |
852 if( !has_ctrl(u) ) break; // Found control user | |
853 IdealLoopTree *u_loop = get_loop(get_ctrl(u)); | |
854 if( u_loop == n_loop ) break; // Found loop-varying use | |
855 if( n_loop->is_member( u_loop ) ) break; // Found use in inner loop | |
856 if( u->Opcode() == Op_Opaque1 ) break; // Found loop limit, bugfix for 4677003 | |
857 } | |
858 bool did_break = (i < imax); // Did we break out of the previous loop? | |
859 if (!did_break && n->outcnt() > 1) { // All uses in outer loops! | |
860 Node *late_load_ctrl; | |
861 if (n->is_Load()) { | |
862 // If n is a load, get and save the result from get_late_ctrl(), | |
863 // to be later used in calculating the control for n's clones. | |
864 clear_dom_lca_tags(); | |
865 late_load_ctrl = get_late_ctrl(n, n_ctrl); | |
866 } | |
867 // If n is a load, and the late control is the same as the current | |
868 // control, then the cloning of n is a pointless exercise, because | |
869 // GVN will ensure that we end up where we started. | |
870 if (!n->is_Load() || late_load_ctrl != n_ctrl) { | |
871 for (DUIterator_Last jmin, j = n->last_outs(jmin); j >= jmin; ) { | |
872 Node *u = n->last_out(j); // Clone private computation per use | |
873 _igvn.hash_delete(u); | |
874 _igvn._worklist.push(u); | |
875 Node *x = n->clone(); // Clone computation | |
876 Node *x_ctrl = NULL; | |
877 if( u->is_Phi() ) { | |
878 // Replace all uses of normal nodes. Replace Phi uses | |
605 | 879 // individually, so the separate Nodes can sink down |
0 | 880 // different paths. |
881 uint k = 1; | |
882 while( u->in(k) != n ) k++; | |
883 u->set_req( k, x ); | |
884 // x goes next to Phi input path | |
885 x_ctrl = u->in(0)->in(k); | |
886 --j; | |
887 } else { // Normal use | |
888 // Replace all uses | |
889 for( uint k = 0; k < u->req(); k++ ) { | |
890 if( u->in(k) == n ) { | |
891 u->set_req( k, x ); | |
892 --j; | |
893 } | |
894 } | |
895 x_ctrl = get_ctrl(u); | |
896 } | |
897 | |
898 // Find control for 'x' next to use but not inside inner loops. | |
899 // For inner loop uses get the preheader area. | |
900 x_ctrl = place_near_use(x_ctrl); | |
901 | |
902 if (n->is_Load()) { | |
903 // For loads, add a control edge to a CFG node outside of the loop | |
904 // to force them to not combine and return back inside the loop | |
905 // during GVN optimization (4641526). | |
906 // | |
907 // Because we are setting the actual control input, factor in | |
908 // the result from get_late_ctrl() so we respect any | |
909 // anti-dependences. (6233005). | |
910 x_ctrl = dom_lca(late_load_ctrl, x_ctrl); | |
911 | |
912 // Don't allow the control input to be a CFG splitting node. | |
913 // Such nodes should only have ProjNodes as outs, e.g. IfNode | |
914 // should only have IfTrueNode and IfFalseNode (4985384). | |
915 x_ctrl = find_non_split_ctrl(x_ctrl); | |
916 assert(dom_depth(n_ctrl) <= dom_depth(x_ctrl), "n is later than its clone"); | |
917 | |
918 x->set_req(0, x_ctrl); | |
919 } | |
920 register_new_node(x, x_ctrl); | |
921 | |
922 // Some institutional knowledge is needed here: 'x' is | |
923 // yanked because if the optimizer runs GVN on it all the | |
924 // cloned x's will common up and undo this optimization and | |
925 // be forced back in the loop. This is annoying because it | |
926 // makes +VerifyOpto report false-positives on progress. I | |
927 // tried setting control edges on the x's to force them to | |
928 // not combine, but the matching gets worried when it tries | |
929 // to fold a StoreP and an AddP together (as part of an | |
930 // address expression) and the AddP and StoreP have | |
931 // different controls. | |
318
60bc5071073f
6738933: assert with base pointers must match with compressed oops enabled
never
parents:
293
diff
changeset
|
932 if( !x->is_Load() && !x->is_DecodeN() ) _igvn._worklist.yank(x); |
0 | 933 } |
934 _igvn.remove_dead_node(n); | |
935 } | |
936 } | |
937 } | |
938 } | |
939 | |
940 // Check for Opaque2's who's loop has disappeared - who's input is in the | |
941 // same loop nest as their output. Remove 'em, they are no longer useful. | |
942 if( n_op == Op_Opaque2 && | |
943 n->in(1) != NULL && | |
944 get_loop(get_ctrl(n)) == get_loop(get_ctrl(n->in(1))) ) { | |
1621
6027dddc26c6
6677629: PhaseIterGVN::subsume_node() should call hash_delete() and add_users_to_worklist()
kvn
parents:
1552
diff
changeset
|
945 _igvn.replace_node( n, n->in(1) ); |
0 | 946 } |
947 } | |
948 | |
949 //------------------------------split_if_with_blocks--------------------------- | |
950 // Check for aggressive application of 'split-if' optimization, | |
951 // using basic block level info. | |
952 void PhaseIdealLoop::split_if_with_blocks( VectorSet &visited, Node_Stack &nstack ) { | |
953 Node *n = C->root(); | |
954 visited.set(n->_idx); // first, mark node as visited | |
955 // Do pre-visit work for root | |
956 n = split_if_with_blocks_pre( n ); | |
957 uint cnt = n->outcnt(); | |
958 uint i = 0; | |
959 while (true) { | |
960 // Visit all children | |
961 if (i < cnt) { | |
962 Node* use = n->raw_out(i); | |
963 ++i; | |
964 if (use->outcnt() != 0 && !visited.test_set(use->_idx)) { | |
965 // Now do pre-visit work for this use | |
966 use = split_if_with_blocks_pre( use ); | |
967 nstack.push(n, i); // Save parent and next use's index. | |
968 n = use; // Process all children of current use. | |
969 cnt = use->outcnt(); | |
970 i = 0; | |
971 } | |
972 } | |
973 else { | |
974 // All of n's children have been processed, complete post-processing. | |
975 if (cnt != 0 && !n->is_Con()) { | |
976 assert(has_node(n), "no dead nodes"); | |
977 split_if_with_blocks_post( n ); | |
978 } | |
979 if (nstack.is_empty()) { | |
980 // Finished all nodes on stack. | |
981 break; | |
982 } | |
983 // Get saved parent node and next use's index. Visit the rest of uses. | |
984 n = nstack.node(); | |
985 cnt = n->outcnt(); | |
986 i = nstack.index(); | |
987 nstack.pop(); | |
988 } | |
989 } | |
990 } | |
991 | |
992 | |
993 //============================================================================= | |
994 // | |
995 // C L O N E A L O O P B O D Y | |
996 // | |
997 | |
998 //------------------------------clone_iff-------------------------------------- | |
999 // Passed in a Phi merging (recursively) some nearly equivalent Bool/Cmps. | |
1000 // "Nearly" because all Nodes have been cloned from the original in the loop, | |
1001 // but the fall-in edges to the Cmp are different. Clone bool/Cmp pairs | |
1002 // through the Phi recursively, and return a Bool. | |
1003 BoolNode *PhaseIdealLoop::clone_iff( PhiNode *phi, IdealLoopTree *loop ) { | |
1004 | |
1005 // Convert this Phi into a Phi merging Bools | |
1006 uint i; | |
1007 for( i = 1; i < phi->req(); i++ ) { | |
1008 Node *b = phi->in(i); | |
1009 if( b->is_Phi() ) { | |
1010 _igvn.hash_delete(phi); | |
1011 _igvn._worklist.push(phi); | |
1012 phi->set_req(i, clone_iff( b->as_Phi(), loop )); | |
1013 } else { | |
1014 assert( b->is_Bool(), "" ); | |
1015 } | |
1016 } | |
1017 | |
1018 Node *sample_bool = phi->in(1); | |
1019 Node *sample_cmp = sample_bool->in(1); | |
1020 | |
1021 // Make Phis to merge the Cmp's inputs. | |
1022 int size = phi->in(0)->req(); | |
1023 PhiNode *phi1 = new (C, size) PhiNode( phi->in(0), Type::TOP ); | |
1024 PhiNode *phi2 = new (C, size) PhiNode( phi->in(0), Type::TOP ); | |
1025 for( i = 1; i < phi->req(); i++ ) { | |
1026 Node *n1 = phi->in(i)->in(1)->in(1); | |
1027 Node *n2 = phi->in(i)->in(1)->in(2); | |
1028 phi1->set_req( i, n1 ); | |
1029 phi2->set_req( i, n2 ); | |
1030 phi1->set_type( phi1->type()->meet(n1->bottom_type()) ); | |
1031 phi2->set_type( phi2->type()->meet(n2->bottom_type()) ); | |
1032 } | |
1033 // See if these Phis have been made before. | |
1034 // Register with optimizer | |
1035 Node *hit1 = _igvn.hash_find_insert(phi1); | |
1036 if( hit1 ) { // Hit, toss just made Phi | |
1037 _igvn.remove_dead_node(phi1); // Remove new phi | |
1038 assert( hit1->is_Phi(), "" ); | |
1039 phi1 = (PhiNode*)hit1; // Use existing phi | |
1040 } else { // Miss | |
1041 _igvn.register_new_node_with_optimizer(phi1); | |
1042 } | |
1043 Node *hit2 = _igvn.hash_find_insert(phi2); | |
1044 if( hit2 ) { // Hit, toss just made Phi | |
1045 _igvn.remove_dead_node(phi2); // Remove new phi | |
1046 assert( hit2->is_Phi(), "" ); | |
1047 phi2 = (PhiNode*)hit2; // Use existing phi | |
1048 } else { // Miss | |
1049 _igvn.register_new_node_with_optimizer(phi2); | |
1050 } | |
1051 // Register Phis with loop/block info | |
1052 set_ctrl(phi1, phi->in(0)); | |
1053 set_ctrl(phi2, phi->in(0)); | |
1054 // Make a new Cmp | |
1055 Node *cmp = sample_cmp->clone(); | |
1056 cmp->set_req( 1, phi1 ); | |
1057 cmp->set_req( 2, phi2 ); | |
1058 _igvn.register_new_node_with_optimizer(cmp); | |
1059 set_ctrl(cmp, phi->in(0)); | |
1060 | |
1061 // Make a new Bool | |
1062 Node *b = sample_bool->clone(); | |
1063 b->set_req(1,cmp); | |
1064 _igvn.register_new_node_with_optimizer(b); | |
1065 set_ctrl(b, phi->in(0)); | |
1066 | |
1067 assert( b->is_Bool(), "" ); | |
1068 return (BoolNode*)b; | |
1069 } | |
1070 | |
1071 //------------------------------clone_bool------------------------------------- | |
1072 // Passed in a Phi merging (recursively) some nearly equivalent Bool/Cmps. | |
1073 // "Nearly" because all Nodes have been cloned from the original in the loop, | |
1074 // but the fall-in edges to the Cmp are different. Clone bool/Cmp pairs | |
1075 // through the Phi recursively, and return a Bool. | |
1076 CmpNode *PhaseIdealLoop::clone_bool( PhiNode *phi, IdealLoopTree *loop ) { | |
1077 uint i; | |
1078 // Convert this Phi into a Phi merging Bools | |
1079 for( i = 1; i < phi->req(); i++ ) { | |
1080 Node *b = phi->in(i); | |
1081 if( b->is_Phi() ) { | |
1082 _igvn.hash_delete(phi); | |
1083 _igvn._worklist.push(phi); | |
1084 phi->set_req(i, clone_bool( b->as_Phi(), loop )); | |
1085 } else { | |
1086 assert( b->is_Cmp() || b->is_top(), "inputs are all Cmp or TOP" ); | |
1087 } | |
1088 } | |
1089 | |
1090 Node *sample_cmp = phi->in(1); | |
1091 | |
1092 // Make Phis to merge the Cmp's inputs. | |
1093 int size = phi->in(0)->req(); | |
1094 PhiNode *phi1 = new (C, size) PhiNode( phi->in(0), Type::TOP ); | |
1095 PhiNode *phi2 = new (C, size) PhiNode( phi->in(0), Type::TOP ); | |
1096 for( uint j = 1; j < phi->req(); j++ ) { | |
1097 Node *cmp_top = phi->in(j); // Inputs are all Cmp or TOP | |
1098 Node *n1, *n2; | |
1099 if( cmp_top->is_Cmp() ) { | |
1100 n1 = cmp_top->in(1); | |
1101 n2 = cmp_top->in(2); | |
1102 } else { | |
1103 n1 = n2 = cmp_top; | |
1104 } | |
1105 phi1->set_req( j, n1 ); | |
1106 phi2->set_req( j, n2 ); | |
1107 phi1->set_type( phi1->type()->meet(n1->bottom_type()) ); | |
1108 phi2->set_type( phi2->type()->meet(n2->bottom_type()) ); | |
1109 } | |
1110 | |
1111 // See if these Phis have been made before. | |
1112 // Register with optimizer | |
1113 Node *hit1 = _igvn.hash_find_insert(phi1); | |
1114 if( hit1 ) { // Hit, toss just made Phi | |
1115 _igvn.remove_dead_node(phi1); // Remove new phi | |
1116 assert( hit1->is_Phi(), "" ); | |
1117 phi1 = (PhiNode*)hit1; // Use existing phi | |
1118 } else { // Miss | |
1119 _igvn.register_new_node_with_optimizer(phi1); | |
1120 } | |
1121 Node *hit2 = _igvn.hash_find_insert(phi2); | |
1122 if( hit2 ) { // Hit, toss just made Phi | |
1123 _igvn.remove_dead_node(phi2); // Remove new phi | |
1124 assert( hit2->is_Phi(), "" ); | |
1125 phi2 = (PhiNode*)hit2; // Use existing phi | |
1126 } else { // Miss | |
1127 _igvn.register_new_node_with_optimizer(phi2); | |
1128 } | |
1129 // Register Phis with loop/block info | |
1130 set_ctrl(phi1, phi->in(0)); | |
1131 set_ctrl(phi2, phi->in(0)); | |
1132 // Make a new Cmp | |
1133 Node *cmp = sample_cmp->clone(); | |
1134 cmp->set_req( 1, phi1 ); | |
1135 cmp->set_req( 2, phi2 ); | |
1136 _igvn.register_new_node_with_optimizer(cmp); | |
1137 set_ctrl(cmp, phi->in(0)); | |
1138 | |
1139 assert( cmp->is_Cmp(), "" ); | |
1140 return (CmpNode*)cmp; | |
1141 } | |
1142 | |
1143 //------------------------------sink_use--------------------------------------- | |
1144 // If 'use' was in the loop-exit block, it now needs to be sunk | |
1145 // below the post-loop merge point. | |
1146 void PhaseIdealLoop::sink_use( Node *use, Node *post_loop ) { | |
1147 if (!use->is_CFG() && get_ctrl(use) == post_loop->in(2)) { | |
1148 set_ctrl(use, post_loop); | |
1149 for (DUIterator j = use->outs(); use->has_out(j); j++) | |
1150 sink_use(use->out(j), post_loop); | |
1151 } | |
1152 } | |
1153 | |
1154 //------------------------------clone_loop------------------------------------- | |
1155 // | |
1156 // C L O N E A L O O P B O D Y | |
1157 // | |
1158 // This is the basic building block of the loop optimizations. It clones an | |
1159 // entire loop body. It makes an old_new loop body mapping; with this mapping | |
1160 // you can find the new-loop equivalent to an old-loop node. All new-loop | |
1161 // nodes are exactly equal to their old-loop counterparts, all edges are the | |
1162 // same. All exits from the old-loop now have a RegionNode that merges the | |
1163 // equivalent new-loop path. This is true even for the normal "loop-exit" | |
1164 // condition. All uses of loop-invariant old-loop values now come from (one | |
1165 // or more) Phis that merge their new-loop equivalents. | |
1166 // | |
1167 // This operation leaves the graph in an illegal state: there are two valid | |
1168 // control edges coming from the loop pre-header to both loop bodies. I'll | |
1169 // definitely have to hack the graph after running this transform. | |
1170 // | |
1171 // From this building block I will further edit edges to perform loop peeling | |
1172 // or loop unrolling or iteration splitting (Range-Check-Elimination), etc. | |
1173 // | |
1174 // Parameter side_by_size_idom: | |
1175 // When side_by_size_idom is NULL, the dominator tree is constructed for | |
1176 // the clone loop to dominate the original. Used in construction of | |
1177 // pre-main-post loop sequence. | |
1178 // When nonnull, the clone and original are side-by-side, both are | |
1179 // dominated by the side_by_side_idom node. Used in construction of | |
1180 // unswitched loops. | |
1181 void PhaseIdealLoop::clone_loop( IdealLoopTree *loop, Node_List &old_new, int dd, | |
1182 Node* side_by_side_idom) { | |
1183 | |
1184 // Step 1: Clone the loop body. Make the old->new mapping. | |
1185 uint i; | |
1186 for( i = 0; i < loop->_body.size(); i++ ) { | |
1187 Node *old = loop->_body.at(i); | |
1188 Node *nnn = old->clone(); | |
1189 old_new.map( old->_idx, nnn ); | |
1190 _igvn.register_new_node_with_optimizer(nnn); | |
1191 } | |
1192 | |
1193 | |
1194 // Step 2: Fix the edges in the new body. If the old input is outside the | |
1195 // loop use it. If the old input is INside the loop, use the corresponding | |
1196 // new node instead. | |
1197 for( i = 0; i < loop->_body.size(); i++ ) { | |
1198 Node *old = loop->_body.at(i); | |
1199 Node *nnn = old_new[old->_idx]; | |
1200 // Fix CFG/Loop controlling the new node | |
1201 if (has_ctrl(old)) { | |
1202 set_ctrl(nnn, old_new[get_ctrl(old)->_idx]); | |
1203 } else { | |
1204 set_loop(nnn, loop->_parent); | |
1205 if (old->outcnt() > 0) { | |
1206 set_idom( nnn, old_new[idom(old)->_idx], dd ); | |
1207 } | |
1208 } | |
1209 // Correct edges to the new node | |
1210 for( uint j = 0; j < nnn->req(); j++ ) { | |
1211 Node *n = nnn->in(j); | |
1212 if( n ) { | |
1213 IdealLoopTree *old_in_loop = get_loop( has_ctrl(n) ? get_ctrl(n) : n ); | |
1214 if( loop->is_member( old_in_loop ) ) | |
1215 nnn->set_req(j, old_new[n->_idx]); | |
1216 } | |
1217 } | |
1218 _igvn.hash_find_insert(nnn); | |
1219 } | |
1220 Node *newhead = old_new[loop->_head->_idx]; | |
1221 set_idom(newhead, newhead->in(LoopNode::EntryControl), dd); | |
1222 | |
1223 | |
1224 // Step 3: Now fix control uses. Loop varying control uses have already | |
1225 // been fixed up (as part of all input edges in Step 2). Loop invariant | |
1226 // control uses must be either an IfFalse or an IfTrue. Make a merge | |
1227 // point to merge the old and new IfFalse/IfTrue nodes; make the use | |
1228 // refer to this. | |
1229 ResourceArea *area = Thread::current()->resource_area(); | |
1230 Node_List worklist(area); | |
1231 uint new_counter = C->unique(); | |
1232 for( i = 0; i < loop->_body.size(); i++ ) { | |
1233 Node* old = loop->_body.at(i); | |
1234 if( !old->is_CFG() ) continue; | |
1235 Node* nnn = old_new[old->_idx]; | |
1236 | |
1237 // Copy uses to a worklist, so I can munge the def-use info | |
1238 // with impunity. | |
1239 for (DUIterator_Fast jmax, j = old->fast_outs(jmax); j < jmax; j++) | |
1240 worklist.push(old->fast_out(j)); | |
1241 | |
1242 while( worklist.size() ) { // Visit all uses | |
1243 Node *use = worklist.pop(); | |
1244 if (!has_node(use)) continue; // Ignore dead nodes | |
1245 IdealLoopTree *use_loop = get_loop( has_ctrl(use) ? get_ctrl(use) : use ); | |
1246 if( !loop->is_member( use_loop ) && use->is_CFG() ) { | |
1247 // Both OLD and USE are CFG nodes here. | |
1248 assert( use->is_Proj(), "" ); | |
1249 | |
1250 // Clone the loop exit control projection | |
1251 Node *newuse = use->clone(); | |
1252 newuse->set_req(0,nnn); | |
1253 _igvn.register_new_node_with_optimizer(newuse); | |
1254 set_loop(newuse, use_loop); | |
1255 set_idom(newuse, nnn, dom_depth(nnn) + 1 ); | |
1256 | |
1257 // We need a Region to merge the exit from the peeled body and the | |
1258 // exit from the old loop body. | |
1259 RegionNode *r = new (C, 3) RegionNode(3); | |
1260 // Map the old use to the new merge point | |
1261 old_new.map( use->_idx, r ); | |
1262 uint dd_r = MIN2(dom_depth(newuse),dom_depth(use)); | |
1263 assert( dd_r >= dom_depth(dom_lca(newuse,use)), "" ); | |
1264 | |
1265 // The original user of 'use' uses 'r' instead. | |
1266 for (DUIterator_Last lmin, l = use->last_outs(lmin); l >= lmin;) { | |
1267 Node* useuse = use->last_out(l); | |
1268 _igvn.hash_delete(useuse); | |
1269 _igvn._worklist.push(useuse); | |
1270 uint uses_found = 0; | |
1271 if( useuse->in(0) == use ) { | |
1272 useuse->set_req(0, r); | |
1273 uses_found++; | |
1274 if( useuse->is_CFG() ) { | |
1275 assert( dom_depth(useuse) > dd_r, "" ); | |
1276 set_idom(useuse, r, dom_depth(useuse)); | |
1277 } | |
1278 } | |
1279 for( uint k = 1; k < useuse->req(); k++ ) { | |
1280 if( useuse->in(k) == use ) { | |
1281 useuse->set_req(k, r); | |
1282 uses_found++; | |
1283 } | |
1284 } | |
1285 l -= uses_found; // we deleted 1 or more copies of this edge | |
1286 } | |
1287 | |
1288 // Now finish up 'r' | |
1289 r->set_req( 1, newuse ); | |
1290 r->set_req( 2, use ); | |
1291 _igvn.register_new_node_with_optimizer(r); | |
1292 set_loop(r, use_loop); | |
1293 set_idom(r, !side_by_side_idom ? newuse->in(0) : side_by_side_idom, dd_r); | |
1294 } // End of if a loop-exit test | |
1295 } | |
1296 } | |
1297 | |
1298 // Step 4: If loop-invariant use is not control, it must be dominated by a | |
1299 // loop exit IfFalse/IfTrue. Find "proper" loop exit. Make a Region | |
1300 // there if needed. Make a Phi there merging old and new used values. | |
1301 Node_List *split_if_set = NULL; | |
1302 Node_List *split_bool_set = NULL; | |
1303 Node_List *split_cex_set = NULL; | |
1304 for( i = 0; i < loop->_body.size(); i++ ) { | |
1305 Node* old = loop->_body.at(i); | |
1306 Node* nnn = old_new[old->_idx]; | |
1307 // Copy uses to a worklist, so I can munge the def-use info | |
1308 // with impunity. | |
1309 for (DUIterator_Fast jmax, j = old->fast_outs(jmax); j < jmax; j++) | |
1310 worklist.push(old->fast_out(j)); | |
1311 | |
1312 while( worklist.size() ) { | |
1313 Node *use = worklist.pop(); | |
1314 if (!has_node(use)) continue; // Ignore dead nodes | |
1315 if (use->in(0) == C->top()) continue; | |
1316 IdealLoopTree *use_loop = get_loop( has_ctrl(use) ? get_ctrl(use) : use ); | |
1317 // Check for data-use outside of loop - at least one of OLD or USE | |
1318 // must not be a CFG node. | |
1319 if( !loop->is_member( use_loop ) && (!old->is_CFG() || !use->is_CFG())) { | |
1320 | |
1321 // If the Data use is an IF, that means we have an IF outside of the | |
1322 // loop that is switching on a condition that is set inside of the | |
1323 // loop. Happens if people set a loop-exit flag; then test the flag | |
1324 // in the loop to break the loop, then test is again outside of the | |
1325 // loop to determine which way the loop exited. | |
1326 if( use->is_If() || use->is_CMove() ) { | |
1327 // Since this code is highly unlikely, we lazily build the worklist | |
1328 // of such Nodes to go split. | |
1329 if( !split_if_set ) | |
1330 split_if_set = new Node_List(area); | |
1331 split_if_set->push(use); | |
1332 } | |
1333 if( use->is_Bool() ) { | |
1334 if( !split_bool_set ) | |
1335 split_bool_set = new Node_List(area); | |
1336 split_bool_set->push(use); | |
1337 } | |
1338 if( use->Opcode() == Op_CreateEx ) { | |
1339 if( !split_cex_set ) | |
1340 split_cex_set = new Node_List(area); | |
1341 split_cex_set->push(use); | |
1342 } | |
1343 | |
1344 | |
1345 // Get "block" use is in | |
1346 uint idx = 0; | |
1347 while( use->in(idx) != old ) idx++; | |
1348 Node *prev = use->is_CFG() ? use : get_ctrl(use); | |
1349 assert( !loop->is_member( get_loop( prev ) ), "" ); | |
1350 Node *cfg = prev->_idx >= new_counter | |
1351 ? prev->in(2) | |
1352 : idom(prev); | |
1353 if( use->is_Phi() ) // Phi use is in prior block | |
1354 cfg = prev->in(idx); // NOT in block of Phi itself | |
1355 if (cfg->is_top()) { // Use is dead? | |
1356 _igvn.hash_delete(use); | |
1357 _igvn._worklist.push(use); | |
1358 use->set_req(idx, C->top()); | |
1359 continue; | |
1360 } | |
1361 | |
1362 while( !loop->is_member( get_loop( cfg ) ) ) { | |
1363 prev = cfg; | |
1364 cfg = cfg->_idx >= new_counter ? cfg->in(2) : idom(cfg); | |
1365 } | |
1366 // If the use occurs after merging several exits from the loop, then | |
1367 // old value must have dominated all those exits. Since the same old | |
1368 // value was used on all those exits we did not need a Phi at this | |
1369 // merge point. NOW we do need a Phi here. Each loop exit value | |
1370 // is now merged with the peeled body exit; each exit gets its own | |
1371 // private Phi and those Phis need to be merged here. | |
1372 Node *phi; | |
1373 if( prev->is_Region() ) { | |
1374 if( idx == 0 ) { // Updating control edge? | |
1375 phi = prev; // Just use existing control | |
1376 } else { // Else need a new Phi | |
1377 phi = PhiNode::make( prev, old ); | |
1378 // Now recursively fix up the new uses of old! | |
1379 for( uint i = 1; i < prev->req(); i++ ) { | |
1380 worklist.push(phi); // Onto worklist once for each 'old' input | |
1381 } | |
1382 } | |
1383 } else { | |
1384 // Get new RegionNode merging old and new loop exits | |
1385 prev = old_new[prev->_idx]; | |
1386 assert( prev, "just made this in step 7" ); | |
1387 if( idx == 0 ) { // Updating control edge? | |
1388 phi = prev; // Just use existing control | |
1389 } else { // Else need a new Phi | |
1390 // Make a new Phi merging data values properly | |
1391 phi = PhiNode::make( prev, old ); | |
1392 phi->set_req( 1, nnn ); | |
1393 } | |
1394 } | |
1395 // If inserting a new Phi, check for prior hits | |
1396 if( idx != 0 ) { | |
1397 Node *hit = _igvn.hash_find_insert(phi); | |
1398 if( hit == NULL ) { | |
1399 _igvn.register_new_node_with_optimizer(phi); // Register new phi | |
1400 } else { // or | |
1401 // Remove the new phi from the graph and use the hit | |
1402 _igvn.remove_dead_node(phi); | |
1403 phi = hit; // Use existing phi | |
1404 } | |
1405 set_ctrl(phi, prev); | |
1406 } | |
1407 // Make 'use' use the Phi instead of the old loop body exit value | |
1408 _igvn.hash_delete(use); | |
1409 _igvn._worklist.push(use); | |
1410 use->set_req(idx, phi); | |
1411 if( use->_idx >= new_counter ) { // If updating new phis | |
1412 // Not needed for correctness, but prevents a weak assert | |
1413 // in AddPNode from tripping (when we end up with different | |
1414 // base & derived Phis that will become the same after | |
1415 // IGVN does CSE). | |
1416 Node *hit = _igvn.hash_find_insert(use); | |
1417 if( hit ) // Go ahead and re-hash for hits. | |
1621
6027dddc26c6
6677629: PhaseIterGVN::subsume_node() should call hash_delete() and add_users_to_worklist()
kvn
parents:
1552
diff
changeset
|
1418 _igvn.replace_node( use, hit ); |
0 | 1419 } |
1420 | |
1421 // If 'use' was in the loop-exit block, it now needs to be sunk | |
1422 // below the post-loop merge point. | |
1423 sink_use( use, prev ); | |
1424 } | |
1425 } | |
1426 } | |
1427 | |
1428 // Check for IFs that need splitting/cloning. Happens if an IF outside of | |
1429 // the loop uses a condition set in the loop. The original IF probably | |
1430 // takes control from one or more OLD Regions (which in turn get from NEW | |
1431 // Regions). In any case, there will be a set of Phis for each merge point | |
1432 // from the IF up to where the original BOOL def exists the loop. | |
1433 if( split_if_set ) { | |
1434 while( split_if_set->size() ) { | |
1435 Node *iff = split_if_set->pop(); | |
1436 if( iff->in(1)->is_Phi() ) { | |
1437 BoolNode *b = clone_iff( iff->in(1)->as_Phi(), loop ); | |
1438 _igvn.hash_delete(iff); | |
1439 _igvn._worklist.push(iff); | |
1440 iff->set_req(1, b); | |
1441 } | |
1442 } | |
1443 } | |
1444 if( split_bool_set ) { | |
1445 while( split_bool_set->size() ) { | |
1446 Node *b = split_bool_set->pop(); | |
1447 Node *phi = b->in(1); | |
1448 assert( phi->is_Phi(), "" ); | |
1449 CmpNode *cmp = clone_bool( (PhiNode*)phi, loop ); | |
1450 _igvn.hash_delete(b); | |
1451 _igvn._worklist.push(b); | |
1452 b->set_req(1, cmp); | |
1453 } | |
1454 } | |
1455 if( split_cex_set ) { | |
1456 while( split_cex_set->size() ) { | |
1457 Node *b = split_cex_set->pop(); | |
1458 assert( b->in(0)->is_Region(), "" ); | |
1459 assert( b->in(1)->is_Phi(), "" ); | |
1460 assert( b->in(0)->in(0) == b->in(1)->in(0), "" ); | |
1461 split_up( b, b->in(0), NULL ); | |
1462 } | |
1463 } | |
1464 | |
1465 } | |
1466 | |
1467 | |
1468 //---------------------- stride_of_possible_iv ------------------------------------- | |
1469 // Looks for an iff/bool/comp with one operand of the compare | |
1470 // being a cycle involving an add and a phi, | |
1471 // with an optional truncation (left-shift followed by a right-shift) | |
1472 // of the add. Returns zero if not an iv. | |
1473 int PhaseIdealLoop::stride_of_possible_iv(Node* iff) { | |
1474 Node* trunc1 = NULL; | |
1475 Node* trunc2 = NULL; | |
1476 const TypeInt* ttype = NULL; | |
1477 if (!iff->is_If() || iff->in(1) == NULL || !iff->in(1)->is_Bool()) { | |
1478 return 0; | |
1479 } | |
1480 BoolNode* bl = iff->in(1)->as_Bool(); | |
1481 Node* cmp = bl->in(1); | |
1482 if (!cmp || cmp->Opcode() != Op_CmpI && cmp->Opcode() != Op_CmpU) { | |
1483 return 0; | |
1484 } | |
1485 // Must have an invariant operand | |
1486 if (is_member(get_loop(iff), get_ctrl(cmp->in(2)))) { | |
1487 return 0; | |
1488 } | |
1489 Node* add2 = NULL; | |
1490 Node* cmp1 = cmp->in(1); | |
1491 if (cmp1->is_Phi()) { | |
1492 // (If (Bool (CmpX phi:(Phi ...(Optional-trunc(AddI phi add2))) ))) | |
1493 Node* phi = cmp1; | |
1494 for (uint i = 1; i < phi->req(); i++) { | |
1495 Node* in = phi->in(i); | |
1496 Node* add = CountedLoopNode::match_incr_with_optional_truncation(in, | |
1497 &trunc1, &trunc2, &ttype); | |
1498 if (add && add->in(1) == phi) { | |
1499 add2 = add->in(2); | |
1500 break; | |
1501 } | |
1502 } | |
1503 } else { | |
1504 // (If (Bool (CmpX addtrunc:(Optional-trunc((AddI (Phi ...addtrunc...) add2)) ))) | |
1505 Node* addtrunc = cmp1; | |
1506 Node* add = CountedLoopNode::match_incr_with_optional_truncation(addtrunc, | |
1507 &trunc1, &trunc2, &ttype); | |
1508 if (add && add->in(1)->is_Phi()) { | |
1509 Node* phi = add->in(1); | |
1510 for (uint i = 1; i < phi->req(); i++) { | |
1511 if (phi->in(i) == addtrunc) { | |
1512 add2 = add->in(2); | |
1513 break; | |
1514 } | |
1515 } | |
1516 } | |
1517 } | |
1518 if (add2 != NULL) { | |
1519 const TypeInt* add2t = _igvn.type(add2)->is_int(); | |
1520 if (add2t->is_con()) { | |
1521 return add2t->get_con(); | |
1522 } | |
1523 } | |
1524 return 0; | |
1525 } | |
1526 | |
1527 | |
1528 //---------------------- stay_in_loop ------------------------------------- | |
1529 // Return the (unique) control output node that's in the loop (if it exists.) | |
1530 Node* PhaseIdealLoop::stay_in_loop( Node* n, IdealLoopTree *loop) { | |
1531 Node* unique = NULL; | |
1532 if (!n) return NULL; | |
1533 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) { | |
1534 Node* use = n->fast_out(i); | |
1535 if (!has_ctrl(use) && loop->is_member(get_loop(use))) { | |
1536 if (unique != NULL) { | |
1537 return NULL; | |
1538 } | |
1539 unique = use; | |
1540 } | |
1541 } | |
1542 return unique; | |
1543 } | |
1544 | |
1545 //------------------------------ register_node ------------------------------------- | |
1546 // Utility to register node "n" with PhaseIdealLoop | |
1547 void PhaseIdealLoop::register_node(Node* n, IdealLoopTree *loop, Node* pred, int ddepth) { | |
1548 _igvn.register_new_node_with_optimizer(n); | |
1549 loop->_body.push(n); | |
1550 if (n->is_CFG()) { | |
1551 set_loop(n, loop); | |
1552 set_idom(n, pred, ddepth); | |
1553 } else { | |
1554 set_ctrl(n, pred); | |
1555 } | |
1556 } | |
1557 | |
1558 //------------------------------ proj_clone ------------------------------------- | |
1559 // Utility to create an if-projection | |
1560 ProjNode* PhaseIdealLoop::proj_clone(ProjNode* p, IfNode* iff) { | |
1561 ProjNode* c = p->clone()->as_Proj(); | |
1562 c->set_req(0, iff); | |
1563 return c; | |
1564 } | |
1565 | |
1566 //------------------------------ short_circuit_if ------------------------------------- | |
1567 // Force the iff control output to be the live_proj | |
1568 Node* PhaseIdealLoop::short_circuit_if(IfNode* iff, ProjNode* live_proj) { | |
1569 int proj_con = live_proj->_con; | |
1570 assert(proj_con == 0 || proj_con == 1, "false or true projection"); | |
1571 Node *con = _igvn.intcon(proj_con); | |
1572 set_ctrl(con, C->root()); | |
1573 if (iff) { | |
1574 iff->set_req(1, con); | |
1575 } | |
1576 return con; | |
1577 } | |
1578 | |
1579 //------------------------------ insert_if_before_proj ------------------------------------- | |
1580 // Insert a new if before an if projection (* - new node) | |
1581 // | |
1582 // before | |
1583 // if(test) | |
1584 // / \ | |
1585 // v v | |
1586 // other-proj proj (arg) | |
1587 // | |
1588 // after | |
1589 // if(test) | |
1590 // / \ | |
1591 // / v | |
1592 // | * proj-clone | |
1593 // v | | |
1594 // other-proj v | |
1595 // * new_if(relop(cmp[IU](left,right))) | |
1596 // / \ | |
1597 // v v | |
1598 // * new-proj proj | |
1599 // (returned) | |
1600 // | |
1601 ProjNode* PhaseIdealLoop::insert_if_before_proj(Node* left, bool Signed, BoolTest::mask relop, Node* right, ProjNode* proj) { | |
1602 IfNode* iff = proj->in(0)->as_If(); | |
1603 IdealLoopTree *loop = get_loop(proj); | |
1604 ProjNode *other_proj = iff->proj_out(!proj->is_IfTrue())->as_Proj(); | |
1605 int ddepth = dom_depth(proj); | |
1606 | |
1607 _igvn.hash_delete(iff); | |
1608 _igvn._worklist.push(iff); | |
1609 _igvn.hash_delete(proj); | |
1610 _igvn._worklist.push(proj); | |
1611 | |
1612 proj->set_req(0, NULL); // temporary disconnect | |
1613 ProjNode* proj2 = proj_clone(proj, iff); | |
1614 register_node(proj2, loop, iff, ddepth); | |
1615 | |
1616 Node* cmp = Signed ? (Node*) new (C,3)CmpINode(left, right) : (Node*) new (C,3)CmpUNode(left, right); | |
1617 register_node(cmp, loop, proj2, ddepth); | |
1618 | |
1619 BoolNode* bol = new (C,2)BoolNode(cmp, relop); | |
1620 register_node(bol, loop, proj2, ddepth); | |
1621 | |
1622 IfNode* new_if = new (C,2)IfNode(proj2, bol, iff->_prob, iff->_fcnt); | |
1623 register_node(new_if, loop, proj2, ddepth); | |
1624 | |
1625 proj->set_req(0, new_if); // reattach | |
1626 set_idom(proj, new_if, ddepth); | |
1627 | |
1628 ProjNode* new_exit = proj_clone(other_proj, new_if)->as_Proj(); | |
1629 register_node(new_exit, get_loop(other_proj), new_if, ddepth); | |
1630 | |
1631 return new_exit; | |
1632 } | |
1633 | |
1634 //------------------------------ insert_region_before_proj ------------------------------------- | |
1635 // Insert a region before an if projection (* - new node) | |
1636 // | |
1637 // before | |
1638 // if(test) | |
1639 // / | | |
1640 // v | | |
1641 // proj v | |
1642 // other-proj | |
1643 // | |
1644 // after | |
1645 // if(test) | |
1646 // / | | |
1647 // v | | |
1648 // * proj-clone v | |
1649 // | other-proj | |
1650 // v | |
1651 // * new-region | |
1652 // | | |
1653 // v | |
1654 // * dum_if | |
1655 // / \ | |
1656 // v \ | |
1657 // * dum-proj v | |
1658 // proj | |
1659 // | |
1660 RegionNode* PhaseIdealLoop::insert_region_before_proj(ProjNode* proj) { | |
1661 IfNode* iff = proj->in(0)->as_If(); | |
1662 IdealLoopTree *loop = get_loop(proj); | |
1663 ProjNode *other_proj = iff->proj_out(!proj->is_IfTrue())->as_Proj(); | |
1664 int ddepth = dom_depth(proj); | |
1665 | |
1666 _igvn.hash_delete(iff); | |
1667 _igvn._worklist.push(iff); | |
1668 _igvn.hash_delete(proj); | |
1669 _igvn._worklist.push(proj); | |
1670 | |
1671 proj->set_req(0, NULL); // temporary disconnect | |
1672 ProjNode* proj2 = proj_clone(proj, iff); | |
1673 register_node(proj2, loop, iff, ddepth); | |
1674 | |
1675 RegionNode* reg = new (C,2)RegionNode(2); | |
1676 reg->set_req(1, proj2); | |
1677 register_node(reg, loop, iff, ddepth); | |
1678 | |
1679 IfNode* dum_if = new (C,2)IfNode(reg, short_circuit_if(NULL, proj), iff->_prob, iff->_fcnt); | |
1680 register_node(dum_if, loop, reg, ddepth); | |
1681 | |
1682 proj->set_req(0, dum_if); // reattach | |
1683 set_idom(proj, dum_if, ddepth); | |
1684 | |
1685 ProjNode* dum_proj = proj_clone(other_proj, dum_if); | |
1686 register_node(dum_proj, loop, dum_if, ddepth); | |
1687 | |
1688 return reg; | |
1689 } | |
1690 | |
1691 //------------------------------ insert_cmpi_loop_exit ------------------------------------- | |
1692 // Clone a signed compare loop exit from an unsigned compare and | |
1693 // insert it before the unsigned cmp on the stay-in-loop path. | |
1694 // All new nodes inserted in the dominator tree between the original | |
1695 // if and it's projections. The original if test is replaced with | |
1696 // a constant to force the stay-in-loop path. | |
1697 // | |
1698 // This is done to make sure that the original if and it's projections | |
1699 // still dominate the same set of control nodes, that the ctrl() relation | |
1700 // from data nodes to them is preserved, and that their loop nesting is | |
1701 // preserved. | |
1702 // | |
1703 // before | |
1704 // if(i <u limit) unsigned compare loop exit | |
1705 // / | | |
1706 // v v | |
1707 // exit-proj stay-in-loop-proj | |
1708 // | |
1709 // after | |
1710 // if(stay-in-loop-const) original if | |
1711 // / | | |
1712 // / v | |
1713 // / if(i < limit) new signed test | |
1714 // / / | | |
1715 // / / v | |
1716 // / / if(i <u limit) new cloned unsigned test | |
1717 // / / / | | |
1718 // v v v | | |
1719 // region | | |
1720 // | | | |
1721 // dum-if | | |
1722 // / | | | |
1723 // ether | | | |
1724 // v v | |
1725 // exit-proj stay-in-loop-proj | |
1726 // | |
1727 IfNode* PhaseIdealLoop::insert_cmpi_loop_exit(IfNode* if_cmpu, IdealLoopTree *loop) { | |
1728 const bool Signed = true; | |
1729 const bool Unsigned = false; | |
1730 | |
1731 BoolNode* bol = if_cmpu->in(1)->as_Bool(); | |
1732 if (bol->_test._test != BoolTest::lt) return NULL; | |
1733 CmpNode* cmpu = bol->in(1)->as_Cmp(); | |
1734 if (cmpu->Opcode() != Op_CmpU) return NULL; | |
1735 int stride = stride_of_possible_iv(if_cmpu); | |
1736 if (stride == 0) return NULL; | |
1737 | |
1738 ProjNode* lp_continue = stay_in_loop(if_cmpu, loop)->as_Proj(); | |
1739 ProjNode* lp_exit = if_cmpu->proj_out(!lp_continue->is_IfTrue())->as_Proj(); | |
1740 | |
1741 Node* limit = NULL; | |
1742 if (stride > 0) { | |
1743 limit = cmpu->in(2); | |
1744 } else { | |
1745 limit = _igvn.makecon(TypeInt::ZERO); | |
1746 set_ctrl(limit, C->root()); | |
1747 } | |
1748 // Create a new region on the exit path | |
1749 RegionNode* reg = insert_region_before_proj(lp_exit); | |
1750 | |
1751 // Clone the if-cmpu-true-false using a signed compare | |
1752 BoolTest::mask rel_i = stride > 0 ? bol->_test._test : BoolTest::ge; | |
1753 ProjNode* cmpi_exit = insert_if_before_proj(cmpu->in(1), Signed, rel_i, limit, lp_continue); | |
1754 reg->add_req(cmpi_exit); | |
1755 | |
1756 // Clone the if-cmpu-true-false | |
1757 BoolTest::mask rel_u = bol->_test._test; | |
1758 ProjNode* cmpu_exit = insert_if_before_proj(cmpu->in(1), Unsigned, rel_u, cmpu->in(2), lp_continue); | |
1759 reg->add_req(cmpu_exit); | |
1760 | |
1761 // Force original if to stay in loop. | |
1762 short_circuit_if(if_cmpu, lp_continue); | |
1763 | |
1764 return cmpi_exit->in(0)->as_If(); | |
1765 } | |
1766 | |
1767 //------------------------------ remove_cmpi_loop_exit ------------------------------------- | |
1768 // Remove a previously inserted signed compare loop exit. | |
1769 void PhaseIdealLoop::remove_cmpi_loop_exit(IfNode* if_cmp, IdealLoopTree *loop) { | |
1770 Node* lp_proj = stay_in_loop(if_cmp, loop); | |
1771 assert(if_cmp->in(1)->in(1)->Opcode() == Op_CmpI && | |
1772 stay_in_loop(lp_proj, loop)->is_If() && | |
1773 stay_in_loop(lp_proj, loop)->in(1)->in(1)->Opcode() == Op_CmpU, "inserted cmpi before cmpu"); | |
1774 Node *con = _igvn.makecon(lp_proj->is_IfTrue() ? TypeInt::ONE : TypeInt::ZERO); | |
1775 set_ctrl(con, C->root()); | |
1776 if_cmp->set_req(1, con); | |
1777 } | |
1778 | |
1779 //------------------------------ scheduled_nodelist ------------------------------------- | |
1780 // Create a post order schedule of nodes that are in the | |
1781 // "member" set. The list is returned in "sched". | |
1782 // The first node in "sched" is the loop head, followed by | |
1783 // nodes which have no inputs in the "member" set, and then | |
1784 // followed by the nodes that have an immediate input dependence | |
1785 // on a node in "sched". | |
1786 void PhaseIdealLoop::scheduled_nodelist( IdealLoopTree *loop, VectorSet& member, Node_List &sched ) { | |
1787 | |
1788 assert(member.test(loop->_head->_idx), "loop head must be in member set"); | |
1789 Arena *a = Thread::current()->resource_area(); | |
1790 VectorSet visited(a); | |
1791 Node_Stack nstack(a, loop->_body.size()); | |
1792 | |
1793 Node* n = loop->_head; // top of stack is cached in "n" | |
1794 uint idx = 0; | |
1795 visited.set(n->_idx); | |
1796 | |
1797 // Initially push all with no inputs from within member set | |
1798 for(uint i = 0; i < loop->_body.size(); i++ ) { | |
1799 Node *elt = loop->_body.at(i); | |
1800 if (member.test(elt->_idx)) { | |
1801 bool found = false; | |
1802 for (uint j = 0; j < elt->req(); j++) { | |
1803 Node* def = elt->in(j); | |
1804 if (def && member.test(def->_idx) && def != elt) { | |
1805 found = true; | |
1806 break; | |
1807 } | |
1808 } | |
1809 if (!found && elt != loop->_head) { | |
1810 nstack.push(n, idx); | |
1811 n = elt; | |
1812 assert(!visited.test(n->_idx), "not seen yet"); | |
1813 visited.set(n->_idx); | |
1814 } | |
1815 } | |
1816 } | |
1817 | |
1818 // traverse out's that are in the member set | |
1819 while (true) { | |
1820 if (idx < n->outcnt()) { | |
1821 Node* use = n->raw_out(idx); | |
1822 idx++; | |
1823 if (!visited.test_set(use->_idx)) { | |
1824 if (member.test(use->_idx)) { | |
1825 nstack.push(n, idx); | |
1826 n = use; | |
1827 idx = 0; | |
1828 } | |
1829 } | |
1830 } else { | |
1831 // All outputs processed | |
1832 sched.push(n); | |
1833 if (nstack.is_empty()) break; | |
1834 n = nstack.node(); | |
1835 idx = nstack.index(); | |
1836 nstack.pop(); | |
1837 } | |
1838 } | |
1839 } | |
1840 | |
1841 | |
1842 //------------------------------ has_use_in_set ------------------------------------- | |
1843 // Has a use in the vector set | |
1844 bool PhaseIdealLoop::has_use_in_set( Node* n, VectorSet& vset ) { | |
1845 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) { | |
1846 Node* use = n->fast_out(j); | |
1847 if (vset.test(use->_idx)) { | |
1848 return true; | |
1849 } | |
1850 } | |
1851 return false; | |
1852 } | |
1853 | |
1854 | |
1855 //------------------------------ has_use_internal_to_set ------------------------------------- | |
1856 // Has use internal to the vector set (ie. not in a phi at the loop head) | |
1857 bool PhaseIdealLoop::has_use_internal_to_set( Node* n, VectorSet& vset, IdealLoopTree *loop ) { | |
1858 Node* head = loop->_head; | |
1859 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) { | |
1860 Node* use = n->fast_out(j); | |
1861 if (vset.test(use->_idx) && !(use->is_Phi() && use->in(0) == head)) { | |
1862 return true; | |
1863 } | |
1864 } | |
1865 return false; | |
1866 } | |
1867 | |
1868 | |
1869 //------------------------------ clone_for_use_outside_loop ------------------------------------- | |
1870 // clone "n" for uses that are outside of loop | |
1871 void PhaseIdealLoop::clone_for_use_outside_loop( IdealLoopTree *loop, Node* n, Node_List& worklist ) { | |
1872 | |
1873 assert(worklist.size() == 0, "should be empty"); | |
1874 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) { | |
1875 Node* use = n->fast_out(j); | |
1876 if( !loop->is_member(get_loop(has_ctrl(use) ? get_ctrl(use) : use)) ) { | |
1877 worklist.push(use); | |
1878 } | |
1879 } | |
1880 while( worklist.size() ) { | |
1881 Node *use = worklist.pop(); | |
1882 if (!has_node(use) || use->in(0) == C->top()) continue; | |
1883 uint j; | |
1884 for (j = 0; j < use->req(); j++) { | |
1885 if (use->in(j) == n) break; | |
1886 } | |
1887 assert(j < use->req(), "must be there"); | |
1888 | |
1889 // clone "n" and insert it between the inputs of "n" and the use outside the loop | |
1890 Node* n_clone = n->clone(); | |
1891 _igvn.hash_delete(use); | |
1892 use->set_req(j, n_clone); | |
1893 _igvn._worklist.push(use); | |
251 | 1894 Node* use_c; |
0 | 1895 if (!use->is_Phi()) { |
251 | 1896 use_c = has_ctrl(use) ? get_ctrl(use) : use->in(0); |
0 | 1897 } else { |
1898 // Use in a phi is considered a use in the associated predecessor block | |
251 | 1899 use_c = use->in(0)->in(j); |
0 | 1900 } |
251 | 1901 set_ctrl(n_clone, use_c); |
1902 assert(!loop->is_member(get_loop(use_c)), "should be outside loop"); | |
1903 get_loop(use_c)->_body.push(n_clone); | |
0 | 1904 _igvn.register_new_node_with_optimizer(n_clone); |
1905 #if !defined(PRODUCT) | |
1906 if (TracePartialPeeling) { | |
1907 tty->print_cr("loop exit cloning old: %d new: %d newbb: %d", n->_idx, n_clone->_idx, get_ctrl(n_clone)->_idx); | |
1908 } | |
1909 #endif | |
1910 } | |
1911 } | |
1912 | |
1913 | |
1914 //------------------------------ clone_for_special_use_inside_loop ------------------------------------- | |
1915 // clone "n" for special uses that are in the not_peeled region. | |
1916 // If these def-uses occur in separate blocks, the code generator | |
1917 // marks the method as not compilable. For example, if a "BoolNode" | |
1918 // is in a different basic block than the "IfNode" that uses it, then | |
1919 // the compilation is aborted in the code generator. | |
1920 void PhaseIdealLoop::clone_for_special_use_inside_loop( IdealLoopTree *loop, Node* n, | |
1921 VectorSet& not_peel, Node_List& sink_list, Node_List& worklist ) { | |
1922 if (n->is_Phi() || n->is_Load()) { | |
1923 return; | |
1924 } | |
1925 assert(worklist.size() == 0, "should be empty"); | |
1926 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) { | |
1927 Node* use = n->fast_out(j); | |
1928 if ( not_peel.test(use->_idx) && | |
1929 (use->is_If() || use->is_CMove() || use->is_Bool()) && | |
1930 use->in(1) == n) { | |
1931 worklist.push(use); | |
1932 } | |
1933 } | |
1934 if (worklist.size() > 0) { | |
1935 // clone "n" and insert it between inputs of "n" and the use | |
1936 Node* n_clone = n->clone(); | |
1937 loop->_body.push(n_clone); | |
1938 _igvn.register_new_node_with_optimizer(n_clone); | |
1939 set_ctrl(n_clone, get_ctrl(n)); | |
1940 sink_list.push(n_clone); | |
1941 not_peel <<= n_clone->_idx; // add n_clone to not_peel set. | |
1942 #if !defined(PRODUCT) | |
1943 if (TracePartialPeeling) { | |
1944 tty->print_cr("special not_peeled cloning old: %d new: %d", n->_idx, n_clone->_idx); | |
1945 } | |
1946 #endif | |
1947 while( worklist.size() ) { | |
1948 Node *use = worklist.pop(); | |
1949 _igvn.hash_delete(use); | |
1950 _igvn._worklist.push(use); | |
1951 for (uint j = 1; j < use->req(); j++) { | |
1952 if (use->in(j) == n) { | |
1953 use->set_req(j, n_clone); | |
1954 } | |
1955 } | |
1956 } | |
1957 } | |
1958 } | |
1959 | |
1960 | |
1961 //------------------------------ insert_phi_for_loop ------------------------------------- | |
1962 // Insert phi(lp_entry_val, back_edge_val) at use->in(idx) for loop lp if phi does not already exist | |
1963 void PhaseIdealLoop::insert_phi_for_loop( Node* use, uint idx, Node* lp_entry_val, Node* back_edge_val, LoopNode* lp ) { | |
1964 Node *phi = PhiNode::make(lp, back_edge_val); | |
1965 phi->set_req(LoopNode::EntryControl, lp_entry_val); | |
1966 // Use existing phi if it already exists | |
1967 Node *hit = _igvn.hash_find_insert(phi); | |
1968 if( hit == NULL ) { | |
1969 _igvn.register_new_node_with_optimizer(phi); | |
1970 set_ctrl(phi, lp); | |
1971 } else { | |
1972 // Remove the new phi from the graph and use the hit | |
1973 _igvn.remove_dead_node(phi); | |
1974 phi = hit; | |
1975 } | |
1976 _igvn.hash_delete(use); | |
1977 _igvn._worklist.push(use); | |
1978 use->set_req(idx, phi); | |
1979 } | |
1980 | |
1981 #ifdef ASSERT | |
1982 //------------------------------ is_valid_loop_partition ------------------------------------- | |
1983 // Validate the loop partition sets: peel and not_peel | |
1984 bool PhaseIdealLoop::is_valid_loop_partition( IdealLoopTree *loop, VectorSet& peel, Node_List& peel_list, | |
1985 VectorSet& not_peel ) { | |
1986 uint i; | |
1987 // Check that peel_list entries are in the peel set | |
1988 for (i = 0; i < peel_list.size(); i++) { | |
1989 if (!peel.test(peel_list.at(i)->_idx)) { | |
1990 return false; | |
1991 } | |
1992 } | |
1993 // Check at loop members are in one of peel set or not_peel set | |
1994 for (i = 0; i < loop->_body.size(); i++ ) { | |
1995 Node *def = loop->_body.at(i); | |
1996 uint di = def->_idx; | |
1997 // Check that peel set elements are in peel_list | |
1998 if (peel.test(di)) { | |
1999 if (not_peel.test(di)) { | |
2000 return false; | |
2001 } | |
2002 // Must be in peel_list also | |
2003 bool found = false; | |
2004 for (uint j = 0; j < peel_list.size(); j++) { | |
2005 if (peel_list.at(j)->_idx == di) { | |
2006 found = true; | |
2007 break; | |
2008 } | |
2009 } | |
2010 if (!found) { | |
2011 return false; | |
2012 } | |
2013 } else if (not_peel.test(di)) { | |
2014 if (peel.test(di)) { | |
2015 return false; | |
2016 } | |
2017 } else { | |
2018 return false; | |
2019 } | |
2020 } | |
2021 return true; | |
2022 } | |
2023 | |
2024 //------------------------------ is_valid_clone_loop_exit_use ------------------------------------- | |
2025 // Ensure a use outside of loop is of the right form | |
2026 bool PhaseIdealLoop::is_valid_clone_loop_exit_use( IdealLoopTree *loop, Node* use, uint exit_idx) { | |
2027 Node *use_c = has_ctrl(use) ? get_ctrl(use) : use; | |
2028 return (use->is_Phi() && | |
2029 use_c->is_Region() && use_c->req() == 3 && | |
2030 (use_c->in(exit_idx)->Opcode() == Op_IfTrue || | |
2031 use_c->in(exit_idx)->Opcode() == Op_IfFalse || | |
2032 use_c->in(exit_idx)->Opcode() == Op_JumpProj) && | |
2033 loop->is_member( get_loop( use_c->in(exit_idx)->in(0) ) ) ); | |
2034 } | |
2035 | |
2036 //------------------------------ is_valid_clone_loop_form ------------------------------------- | |
2037 // Ensure that all uses outside of loop are of the right form | |
2038 bool PhaseIdealLoop::is_valid_clone_loop_form( IdealLoopTree *loop, Node_List& peel_list, | |
2039 uint orig_exit_idx, uint clone_exit_idx) { | |
2040 uint len = peel_list.size(); | |
2041 for (uint i = 0; i < len; i++) { | |
2042 Node *def = peel_list.at(i); | |
2043 | |
2044 for (DUIterator_Fast jmax, j = def->fast_outs(jmax); j < jmax; j++) { | |
2045 Node *use = def->fast_out(j); | |
2046 Node *use_c = has_ctrl(use) ? get_ctrl(use) : use; | |
2047 if (!loop->is_member(get_loop(use_c))) { | |
2048 // use is not in the loop, check for correct structure | |
2049 if (use->in(0) == def) { | |
2050 // Okay | |
2051 } else if (!is_valid_clone_loop_exit_use(loop, use, orig_exit_idx)) { | |
2052 return false; | |
2053 } | |
2054 } | |
2055 } | |
2056 } | |
2057 return true; | |
2058 } | |
2059 #endif | |
2060 | |
2061 //------------------------------ partial_peel ------------------------------------- | |
2062 // Partially peel (aka loop rotation) the top portion of a loop (called | |
2063 // the peel section below) by cloning it and placing one copy just before | |
2064 // the new loop head and the other copy at the bottom of the new loop. | |
2065 // | |
2066 // before after where it came from | |
2067 // | |
2068 // stmt1 stmt1 | |
2069 // loop: stmt2 clone | |
2070 // stmt2 if condA goto exitA clone | |
2071 // if condA goto exitA new_loop: new | |
2072 // stmt3 stmt3 clone | |
2073 // if !condB goto loop if condB goto exitB clone | |
2074 // exitB: stmt2 orig | |
2075 // stmt4 if !condA goto new_loop orig | |
2076 // exitA: goto exitA | |
2077 // exitB: | |
2078 // stmt4 | |
2079 // exitA: | |
2080 // | |
2081 // Step 1: find the cut point: an exit test on probable | |
2082 // induction variable. | |
2083 // Step 2: schedule (with cloning) operations in the peel | |
2084 // section that can be executed after the cut into | |
2085 // the section that is not peeled. This may need | |
2086 // to clone operations into exit blocks. For | |
2087 // instance, a reference to A[i] in the not-peel | |
2088 // section and a reference to B[i] in an exit block | |
2089 // may cause a left-shift of i by 2 to be placed | |
2090 // in the peel block. This step will clone the left | |
2091 // shift into the exit block and sink the left shift | |
2092 // from the peel to the not-peel section. | |
2093 // Step 3: clone the loop, retarget the control, and insert | |
2094 // phis for values that are live across the new loop | |
2095 // head. This is very dependent on the graph structure | |
2096 // from clone_loop. It creates region nodes for | |
2097 // exit control and associated phi nodes for values | |
2098 // flow out of the loop through that exit. The region | |
2099 // node is dominated by the clone's control projection. | |
2100 // So the clone's peel section is placed before the | |
2101 // new loop head, and the clone's not-peel section is | |
2102 // forms the top part of the new loop. The original | |
2103 // peel section forms the tail of the new loop. | |
2104 // Step 4: update the dominator tree and recompute the | |
2105 // dominator depth. | |
2106 // | |
2107 // orig | |
2108 // | |
2109 // stmt1 | |
2110 // | | |
2111 // v | |
2112 // loop<----+ | |
2113 // | | | |
2114 // stmt2 | | |
2115 // | | | |
2116 // v | | |
2117 // ifA | | |
2118 // / | | | |
2119 // v v | | |
2120 // false true ^ <-- last_peel | |
2121 // / | | | |
2122 // / ===|==cut | | |
2123 // / stmt3 | <-- first_not_peel | |
2124 // / | | | |
2125 // | v | | |
2126 // v ifB | | |
2127 // exitA: / \ | | |
2128 // / \ | | |
2129 // v v | | |
2130 // false true | | |
2131 // / \ | | |
2132 // / ----+ | |
2133 // | | |
2134 // v | |
2135 // exitB: | |
2136 // stmt4 | |
2137 // | |
2138 // | |
2139 // after clone loop | |
2140 // | |
2141 // stmt1 | |
2142 // / \ | |
2143 // clone / \ orig | |
2144 // / \ | |
2145 // / \ | |
2146 // v v | |
2147 // +---->loop loop<----+ | |
2148 // | | | | | |
2149 // | stmt2 stmt2 | | |
2150 // | | | | | |
2151 // | v v | | |
2152 // | ifA ifA | | |
2153 // | | \ / | | | |
2154 // | v v v v | | |
2155 // ^ true false false true ^ <-- last_peel | |
2156 // | | ^ \ / | | | |
2157 // | cut==|== \ \ / ===|==cut | | |
2158 // | stmt3 \ \ / stmt3 | <-- first_not_peel | |
2159 // | | dom | | | | | |
2160 // | v \ 1v v2 v | | |
2161 // | ifB regionA ifB | | |
2162 // | / \ | / \ | | |
2163 // | / \ v / \ | | |
2164 // | v v exitA: v v | | |
2165 // | true false false true | | |
2166 // | / ^ \ / \ | | |
2167 // +---- \ \ / ----+ | |
2168 // dom \ / | |
2169 // \ 1v v2 | |
2170 // regionB | |
2171 // | | |
2172 // v | |
2173 // exitB: | |
2174 // stmt4 | |
2175 // | |
2176 // | |
2177 // after partial peel | |
2178 // | |
2179 // stmt1 | |
2180 // / | |
2181 // clone / orig | |
2182 // / TOP | |
2183 // / \ | |
2184 // v v | |
2185 // TOP->region region----+ | |
2186 // | | | | |
2187 // stmt2 stmt2 | | |
2188 // | | | | |
2189 // v v | | |
2190 // ifA ifA | | |
2191 // | \ / | | | |
2192 // v v v v | | |
2193 // true false false true | <-- last_peel | |
2194 // | ^ \ / +------|---+ | |
2195 // +->newloop \ \ / === ==cut | | | |
2196 // | stmt3 \ \ / TOP | | | |
2197 // | | dom | | stmt3 | | <-- first_not_peel | |
2198 // | v \ 1v v2 v | | | |
2199 // | ifB regionA ifB ^ v | |
2200 // | / \ | / \ | | | |
2201 // | / \ v / \ | | | |
2202 // | v v exitA: v v | | | |
2203 // | true false false true | | | |
2204 // | / ^ \ / \ | | | |
2205 // | | \ \ / v | | | |
2206 // | | dom \ / TOP | | | |
2207 // | | \ 1v v2 | | | |
2208 // ^ v regionB | | | |
2209 // | | | | | | |
2210 // | | v ^ v | |
2211 // | | exitB: | | | |
2212 // | | stmt4 | | | |
2213 // | +------------>-----------------+ | | |
2214 // | | | |
2215 // +-----------------<---------------------+ | |
2216 // | |
2217 // | |
2218 // final graph | |
2219 // | |
2220 // stmt1 | |
2221 // | | |
2222 // v | |
2223 // ........> ifA clone | |
2224 // : / | | |
2225 // dom / | | |
2226 // : v v | |
2227 // : false true | |
2228 // : | | | |
2229 // : | stmt2 clone | |
2230 // : | | | |
2231 // : | v | |
2232 // : | newloop<-----+ | |
2233 // : | | | | |
2234 // : | stmt3 clone | | |
2235 // : | | | | |
2236 // : | v | | |
2237 // : | ifB | | |
2238 // : | / \ | | |
2239 // : | v v | | |
2240 // : | false true | | |
2241 // : | | | | | |
2242 // : | v stmt2 | | |
2243 // : | exitB: | | | |
2244 // : | stmt4 v | | |
2245 // : | ifA orig | | |
2246 // : | / \ | | |
2247 // : | / \ | | |
2248 // : | v v | | |
2249 // : | false true | | |
2250 // : | / \ | | |
2251 // : v v -----+ | |
2252 // RegionA | |
2253 // | | |
2254 // v | |
2255 // exitA | |
2256 // | |
2257 bool PhaseIdealLoop::partial_peel( IdealLoopTree *loop, Node_List &old_new ) { | |
2258 | |
108 | 2259 if (!loop->_head->is_Loop()) { |
2260 return false; } | |
2261 | |
0 | 2262 LoopNode *head = loop->_head->as_Loop(); |
2263 | |
2264 if (head->is_partial_peel_loop() || head->partial_peel_has_failed()) { | |
2265 return false; | |
2266 } | |
2267 | |
2268 // Check for complex exit control | |
2269 for(uint ii = 0; ii < loop->_body.size(); ii++ ) { | |
2270 Node *n = loop->_body.at(ii); | |
2271 int opc = n->Opcode(); | |
2272 if (n->is_Call() || | |
2273 opc == Op_Catch || | |
2274 opc == Op_CatchProj || | |
2275 opc == Op_Jump || | |
2276 opc == Op_JumpProj) { | |
2277 #if !defined(PRODUCT) | |
2278 if (TracePartialPeeling) { | |
2279 tty->print_cr("\nExit control too complex: lp: %d", head->_idx); | |
2280 } | |
2281 #endif | |
2282 return false; | |
2283 } | |
2284 } | |
2285 | |
2286 int dd = dom_depth(head); | |
2287 | |
2288 // Step 1: find cut point | |
2289 | |
2290 // Walk up dominators to loop head looking for first loop exit | |
2291 // which is executed on every path thru loop. | |
2292 IfNode *peel_if = NULL; | |
2293 IfNode *peel_if_cmpu = NULL; | |
2294 | |
2295 Node *iff = loop->tail(); | |
2296 while( iff != head ) { | |
2297 if( iff->is_If() ) { | |
2298 Node *ctrl = get_ctrl(iff->in(1)); | |
2299 if (ctrl->is_top()) return false; // Dead test on live IF. | |
2300 // If loop-varying exit-test, check for induction variable | |
2301 if( loop->is_member(get_loop(ctrl)) && | |
2302 loop->is_loop_exit(iff) && | |
2303 is_possible_iv_test(iff)) { | |
2304 Node* cmp = iff->in(1)->in(1); | |
2305 if (cmp->Opcode() == Op_CmpI) { | |
2306 peel_if = iff->as_If(); | |
2307 } else { | |
2308 assert(cmp->Opcode() == Op_CmpU, "must be CmpI or CmpU"); | |
2309 peel_if_cmpu = iff->as_If(); | |
2310 } | |
2311 } | |
2312 } | |
2313 iff = idom(iff); | |
2314 } | |
2315 // Prefer signed compare over unsigned compare. | |
2316 IfNode* new_peel_if = NULL; | |
2317 if (peel_if == NULL) { | |
2318 if (!PartialPeelAtUnsignedTests || peel_if_cmpu == NULL) { | |
2319 return false; // No peel point found | |
2320 } | |
2321 new_peel_if = insert_cmpi_loop_exit(peel_if_cmpu, loop); | |
2322 if (new_peel_if == NULL) { | |
2323 return false; // No peel point found | |
2324 } | |
2325 peel_if = new_peel_if; | |
2326 } | |
2327 Node* last_peel = stay_in_loop(peel_if, loop); | |
2328 Node* first_not_peeled = stay_in_loop(last_peel, loop); | |
2329 if (first_not_peeled == NULL || first_not_peeled == head) { | |
2330 return false; | |
2331 } | |
2332 | |
2333 #if !defined(PRODUCT) | |
2334 if (TracePartialPeeling) { | |
2335 tty->print_cr("before partial peel one iteration"); | |
2336 Node_List wl; | |
2337 Node* t = head->in(2); | |
2338 while (true) { | |
2339 wl.push(t); | |
2340 if (t == head) break; | |
2341 t = idom(t); | |
2342 } | |
2343 while (wl.size() > 0) { | |
2344 Node* tt = wl.pop(); | |
2345 tt->dump(); | |
2346 if (tt == last_peel) tty->print_cr("-- cut --"); | |
2347 } | |
2348 } | |
2349 #endif | |
2350 ResourceArea *area = Thread::current()->resource_area(); | |
2351 VectorSet peel(area); | |
2352 VectorSet not_peel(area); | |
2353 Node_List peel_list(area); | |
2354 Node_List worklist(area); | |
2355 Node_List sink_list(area); | |
2356 | |
2357 // Set of cfg nodes to peel are those that are executable from | |
2358 // the head through last_peel. | |
2359 assert(worklist.size() == 0, "should be empty"); | |
2360 worklist.push(head); | |
2361 peel.set(head->_idx); | |
2362 while (worklist.size() > 0) { | |
2363 Node *n = worklist.pop(); | |
2364 if (n != last_peel) { | |
2365 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) { | |
2366 Node* use = n->fast_out(j); | |
2367 if (use->is_CFG() && | |
2368 loop->is_member(get_loop(use)) && | |
2369 !peel.test_set(use->_idx)) { | |
2370 worklist.push(use); | |
2371 } | |
2372 } | |
2373 } | |
2374 } | |
2375 | |
2376 // Set of non-cfg nodes to peel are those that are control | |
2377 // dependent on the cfg nodes. | |
2378 uint i; | |
2379 for(i = 0; i < loop->_body.size(); i++ ) { | |
2380 Node *n = loop->_body.at(i); | |
2381 Node *n_c = has_ctrl(n) ? get_ctrl(n) : n; | |
2382 if (peel.test(n_c->_idx)) { | |
2383 peel.set(n->_idx); | |
2384 } else { | |
2385 not_peel.set(n->_idx); | |
2386 } | |
2387 } | |
2388 | |
2389 // Step 2: move operations from the peeled section down into the | |
2390 // not-peeled section | |
2391 | |
2392 // Get a post order schedule of nodes in the peel region | |
2393 // Result in right-most operand. | |
2394 scheduled_nodelist(loop, peel, peel_list ); | |
2395 | |
2396 assert(is_valid_loop_partition(loop, peel, peel_list, not_peel), "bad partition"); | |
2397 | |
2398 // For future check for too many new phis | |
2399 uint old_phi_cnt = 0; | |
2400 for (DUIterator_Fast jmax, j = head->fast_outs(jmax); j < jmax; j++) { | |
2401 Node* use = head->fast_out(j); | |
2402 if (use->is_Phi()) old_phi_cnt++; | |
2403 } | |
2404 | |
2405 #if !defined(PRODUCT) | |
2406 if (TracePartialPeeling) { | |
2407 tty->print_cr("\npeeled list"); | |
2408 } | |
2409 #endif | |
2410 | |
2411 // Evacuate nodes in peel region into the not_peeled region if possible | |
2412 uint new_phi_cnt = 0; | |
2413 for (i = 0; i < peel_list.size();) { | |
2414 Node* n = peel_list.at(i); | |
2415 #if !defined(PRODUCT) | |
2416 if (TracePartialPeeling) n->dump(); | |
2417 #endif | |
2418 bool incr = true; | |
2419 if ( !n->is_CFG() ) { | |
2420 | |
2421 if ( has_use_in_set(n, not_peel) ) { | |
2422 | |
2423 // If not used internal to the peeled region, | |
2424 // move "n" from peeled to not_peeled region. | |
2425 | |
2426 if ( !has_use_internal_to_set(n, peel, loop) ) { | |
2427 | |
2428 // if not pinned and not a load (which maybe anti-dependent on a store) | |
2429 // and not a CMove (Matcher expects only bool->cmove). | |
2430 if ( n->in(0) == NULL && !n->is_Load() && !n->is_CMove() ) { | |
2431 clone_for_use_outside_loop( loop, n, worklist ); | |
2432 | |
2433 sink_list.push(n); | |
2434 peel >>= n->_idx; // delete n from peel set. | |
2435 not_peel <<= n->_idx; // add n to not_peel set. | |
2436 peel_list.remove(i); | |
2437 incr = false; | |
2438 #if !defined(PRODUCT) | |
2439 if (TracePartialPeeling) { | |
2440 tty->print_cr("sink to not_peeled region: %d newbb: %d", | |
2441 n->_idx, get_ctrl(n)->_idx); | |
2442 } | |
2443 #endif | |
2444 } | |
2445 } else { | |
2446 // Otherwise check for special def-use cases that span | |
2447 // the peel/not_peel boundary such as bool->if | |
2448 clone_for_special_use_inside_loop( loop, n, not_peel, sink_list, worklist ); | |
2449 new_phi_cnt++; | |
2450 } | |
2451 } | |
2452 } | |
2453 if (incr) i++; | |
2454 } | |
2455 | |
2456 if (new_phi_cnt > old_phi_cnt + PartialPeelNewPhiDelta) { | |
2457 #if !defined(PRODUCT) | |
2458 if (TracePartialPeeling) { | |
2459 tty->print_cr("\nToo many new phis: %d old %d new cmpi: %c", | |
2460 new_phi_cnt, old_phi_cnt, new_peel_if != NULL?'T':'F'); | |
2461 } | |
2462 #endif | |
2463 if (new_peel_if != NULL) { | |
2464 remove_cmpi_loop_exit(new_peel_if, loop); | |
2465 } | |
2466 // Inhibit more partial peeling on this loop | |
2467 assert(!head->is_partial_peel_loop(), "not partial peeled"); | |
2468 head->mark_partial_peel_failed(); | |
2469 return false; | |
2470 } | |
2471 | |
2472 // Step 3: clone loop, retarget control, and insert new phis | |
2473 | |
2474 // Create new loop head for new phis and to hang | |
2475 // the nodes being moved (sinked) from the peel region. | |
2476 LoopNode* new_head = new (C, 3) LoopNode(last_peel, last_peel); | |
2477 _igvn.register_new_node_with_optimizer(new_head); | |
2478 assert(first_not_peeled->in(0) == last_peel, "last_peel <- first_not_peeled"); | |
2479 first_not_peeled->set_req(0, new_head); | |
2480 set_loop(new_head, loop); | |
2481 loop->_body.push(new_head); | |
2482 not_peel.set(new_head->_idx); | |
2483 set_idom(new_head, last_peel, dom_depth(first_not_peeled)); | |
2484 set_idom(first_not_peeled, new_head, dom_depth(first_not_peeled)); | |
2485 | |
2486 while (sink_list.size() > 0) { | |
2487 Node* n = sink_list.pop(); | |
2488 set_ctrl(n, new_head); | |
2489 } | |
2490 | |
2491 assert(is_valid_loop_partition(loop, peel, peel_list, not_peel), "bad partition"); | |
2492 | |
2493 clone_loop( loop, old_new, dd ); | |
2494 | |
2495 const uint clone_exit_idx = 1; | |
2496 const uint orig_exit_idx = 2; | |
2497 assert(is_valid_clone_loop_form( loop, peel_list, orig_exit_idx, clone_exit_idx ), "bad clone loop"); | |
2498 | |
2499 Node* head_clone = old_new[head->_idx]; | |
2500 LoopNode* new_head_clone = old_new[new_head->_idx]->as_Loop(); | |
2501 Node* orig_tail_clone = head_clone->in(2); | |
2502 | |
2503 // Add phi if "def" node is in peel set and "use" is not | |
2504 | |
2505 for(i = 0; i < peel_list.size(); i++ ) { | |
2506 Node *def = peel_list.at(i); | |
2507 if (!def->is_CFG()) { | |
2508 for (DUIterator_Fast jmax, j = def->fast_outs(jmax); j < jmax; j++) { | |
2509 Node *use = def->fast_out(j); | |
2510 if (has_node(use) && use->in(0) != C->top() && | |
2511 (!peel.test(use->_idx) || | |
2512 (use->is_Phi() && use->in(0) == head)) ) { | |
2513 worklist.push(use); | |
2514 } | |
2515 } | |
2516 while( worklist.size() ) { | |
2517 Node *use = worklist.pop(); | |
2518 for (uint j = 1; j < use->req(); j++) { | |
2519 Node* n = use->in(j); | |
2520 if (n == def) { | |
2521 | |
2522 // "def" is in peel set, "use" is not in peel set | |
2523 // or "use" is in the entry boundary (a phi) of the peel set | |
2524 | |
2525 Node* use_c = has_ctrl(use) ? get_ctrl(use) : use; | |
2526 | |
2527 if ( loop->is_member(get_loop( use_c )) ) { | |
2528 // use is in loop | |
2529 if (old_new[use->_idx] != NULL) { // null for dead code | |
2530 Node* use_clone = old_new[use->_idx]; | |
2531 _igvn.hash_delete(use); | |
2532 use->set_req(j, C->top()); | |
2533 _igvn._worklist.push(use); | |
2534 insert_phi_for_loop( use_clone, j, old_new[def->_idx], def, new_head_clone ); | |
2535 } | |
2536 } else { | |
2537 assert(is_valid_clone_loop_exit_use(loop, use, orig_exit_idx), "clone loop format"); | |
2538 // use is not in the loop, check if the live range includes the cut | |
2539 Node* lp_if = use_c->in(orig_exit_idx)->in(0); | |
2540 if (not_peel.test(lp_if->_idx)) { | |
2541 assert(j == orig_exit_idx, "use from original loop"); | |
2542 insert_phi_for_loop( use, clone_exit_idx, old_new[def->_idx], def, new_head_clone ); | |
2543 } | |
2544 } | |
2545 } | |
2546 } | |
2547 } | |
2548 } | |
2549 } | |
2550 | |
2551 // Step 3b: retarget control | |
2552 | |
2553 // Redirect control to the new loop head if a cloned node in | |
2554 // the not_peeled region has control that points into the peeled region. | |
2555 // This necessary because the cloned peeled region will be outside | |
2556 // the loop. | |
2557 // from to | |
2558 // cloned-peeled <---+ | |
2559 // new_head_clone: | <--+ | |
2560 // cloned-not_peeled in(0) in(0) | |
2561 // orig-peeled | |
2562 | |
2563 for(i = 0; i < loop->_body.size(); i++ ) { | |
2564 Node *n = loop->_body.at(i); | |
2565 if (!n->is_CFG() && n->in(0) != NULL && | |
2566 not_peel.test(n->_idx) && peel.test(n->in(0)->_idx)) { | |
2567 Node* n_clone = old_new[n->_idx]; | |
2568 _igvn.hash_delete(n_clone); | |
2569 n_clone->set_req(0, new_head_clone); | |
2570 _igvn._worklist.push(n_clone); | |
2571 } | |
2572 } | |
2573 | |
2574 // Backedge of the surviving new_head (the clone) is original last_peel | |
2575 _igvn.hash_delete(new_head_clone); | |
2576 new_head_clone->set_req(LoopNode::LoopBackControl, last_peel); | |
2577 _igvn._worklist.push(new_head_clone); | |
2578 | |
2579 // Cut first node in original not_peel set | |
2580 _igvn.hash_delete(new_head); | |
2581 new_head->set_req(LoopNode::EntryControl, C->top()); | |
2582 new_head->set_req(LoopNode::LoopBackControl, C->top()); | |
2583 _igvn._worklist.push(new_head); | |
2584 | |
2585 // Copy head_clone back-branch info to original head | |
2586 // and remove original head's loop entry and | |
2587 // clone head's back-branch | |
2588 _igvn.hash_delete(head); | |
2589 _igvn.hash_delete(head_clone); | |
2590 head->set_req(LoopNode::EntryControl, head_clone->in(LoopNode::LoopBackControl)); | |
2591 head->set_req(LoopNode::LoopBackControl, C->top()); | |
2592 head_clone->set_req(LoopNode::LoopBackControl, C->top()); | |
2593 _igvn._worklist.push(head); | |
2594 _igvn._worklist.push(head_clone); | |
2595 | |
2596 // Similarly modify the phis | |
2597 for (DUIterator_Fast kmax, k = head->fast_outs(kmax); k < kmax; k++) { | |
2598 Node* use = head->fast_out(k); | |
2599 if (use->is_Phi() && use->outcnt() > 0) { | |
2600 Node* use_clone = old_new[use->_idx]; | |
2601 _igvn.hash_delete(use); | |
2602 _igvn.hash_delete(use_clone); | |
2603 use->set_req(LoopNode::EntryControl, use_clone->in(LoopNode::LoopBackControl)); | |
2604 use->set_req(LoopNode::LoopBackControl, C->top()); | |
2605 use_clone->set_req(LoopNode::LoopBackControl, C->top()); | |
2606 _igvn._worklist.push(use); | |
2607 _igvn._worklist.push(use_clone); | |
2608 } | |
2609 } | |
2610 | |
2611 // Step 4: update dominator tree and dominator depth | |
2612 | |
2613 set_idom(head, orig_tail_clone, dd); | |
2614 recompute_dom_depth(); | |
2615 | |
2616 // Inhibit more partial peeling on this loop | |
2617 new_head_clone->set_partial_peel_loop(); | |
2618 C->set_major_progress(); | |
2619 | |
2620 #if !defined(PRODUCT) | |
2621 if (TracePartialPeeling) { | |
2622 tty->print_cr("\nafter partial peel one iteration"); | |
2623 Node_List wl(area); | |
2624 Node* t = last_peel; | |
2625 while (true) { | |
2626 wl.push(t); | |
2627 if (t == head_clone) break; | |
2628 t = idom(t); | |
2629 } | |
2630 while (wl.size() > 0) { | |
2631 Node* tt = wl.pop(); | |
2632 if (tt == head) tty->print_cr("orig head"); | |
2633 else if (tt == new_head_clone) tty->print_cr("new head"); | |
2634 else if (tt == head_clone) tty->print_cr("clone head"); | |
2635 tt->dump(); | |
2636 } | |
2637 } | |
2638 #endif | |
2639 return true; | |
2640 } | |
2641 | |
2642 //------------------------------reorg_offsets---------------------------------- | |
2643 // Reorganize offset computations to lower register pressure. Mostly | |
2644 // prevent loop-fallout uses of the pre-incremented trip counter (which are | |
2645 // then alive with the post-incremented trip counter forcing an extra | |
2646 // register move) | |
2647 void PhaseIdealLoop::reorg_offsets( IdealLoopTree *loop ) { | |
2648 | |
2649 CountedLoopNode *cl = loop->_head->as_CountedLoop(); | |
2650 CountedLoopEndNode *cle = cl->loopexit(); | |
2651 if( !cle ) return; // The occasional dead loop | |
2652 // Find loop exit control | |
2653 Node *exit = cle->proj_out(false); | |
2654 assert( exit->Opcode() == Op_IfFalse, "" ); | |
2655 | |
2656 // Check for the special case of folks using the pre-incremented | |
2657 // trip-counter on the fall-out path (forces the pre-incremented | |
2658 // and post-incremented trip counter to be live at the same time). | |
2659 // Fix this by adjusting to use the post-increment trip counter. | |
2660 Node *phi = cl->phi(); | |
2661 if( !phi ) return; // Dead infinite loop | |
367
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
318
diff
changeset
|
2662 |
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
318
diff
changeset
|
2663 // Shape messed up, probably by iteration_split_impl |
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
318
diff
changeset
|
2664 if (phi->in(LoopNode::LoopBackControl) != cl->incr()) return; |
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
318
diff
changeset
|
2665 |
0 | 2666 bool progress = true; |
2667 while (progress) { | |
2668 progress = false; | |
2669 for (DUIterator_Fast imax, i = phi->fast_outs(imax); i < imax; i++) { | |
2670 Node* use = phi->fast_out(i); // User of trip-counter | |
2671 if (!has_ctrl(use)) continue; | |
2672 Node *u_ctrl = get_ctrl(use); | |
2673 if( use->is_Phi() ) { | |
2674 u_ctrl = NULL; | |
2675 for( uint j = 1; j < use->req(); j++ ) | |
2676 if( use->in(j) == phi ) | |
2677 u_ctrl = dom_lca( u_ctrl, use->in(0)->in(j) ); | |
2678 } | |
2679 IdealLoopTree *u_loop = get_loop(u_ctrl); | |
2680 // Look for loop-invariant use | |
2681 if( u_loop == loop ) continue; | |
2682 if( loop->is_member( u_loop ) ) continue; | |
2683 // Check that use is live out the bottom. Assuming the trip-counter | |
2684 // update is right at the bottom, uses of of the loop middle are ok. | |
2685 if( dom_lca( exit, u_ctrl ) != exit ) continue; | |
2686 // protect against stride not being a constant | |
2687 if( !cle->stride_is_con() ) continue; | |
2688 // Hit! Refactor use to use the post-incremented tripcounter. | |
2689 // Compute a post-increment tripcounter. | |
216
8d191a7697e2
6715633: when matching a memory node the adr_type should not change
kvn
parents:
164
diff
changeset
|
2690 Node *opaq = new (C, 2) Opaque2Node( C, cle->incr() ); |
0 | 2691 register_new_node( opaq, u_ctrl ); |
2692 Node *neg_stride = _igvn.intcon(-cle->stride_con()); | |
2693 set_ctrl(neg_stride, C->root()); | |
2694 Node *post = new (C, 3) AddINode( opaq, neg_stride); | |
2695 register_new_node( post, u_ctrl ); | |
2696 _igvn.hash_delete(use); | |
2697 _igvn._worklist.push(use); | |
2698 for( uint j = 1; j < use->req(); j++ ) | |
2699 if( use->in(j) == phi ) | |
2700 use->set_req(j, post); | |
2701 // Since DU info changed, rerun loop | |
2702 progress = true; | |
2703 break; | |
2704 } | |
2705 } | |
2706 | |
2707 } |