1 /*
2 * Copyright (c) 1999, 2017, Oracle and/or its affiliates. All rights reserved.
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 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "memory/allocation.inline.hpp"
27 #include "memory/resourceArea.hpp"
28 #include "opto/addnode.hpp"
29 #include "opto/castnode.hpp"
30 #include "opto/connode.hpp"
31 #include "opto/castnode.hpp"
32 #include "opto/divnode.hpp"
33 #include "opto/loopnode.hpp"
34 #include "opto/matcher.hpp"
35 #include "opto/mulnode.hpp"
36 #include "opto/movenode.hpp"
37 #include "opto/opaquenode.hpp"
38 #include "opto/rootnode.hpp"
39 #include "opto/subnode.hpp"
40
41 //=============================================================================
42 //------------------------------split_thru_phi---------------------------------
43 // Split Node 'n' through merge point if there is enough win.
44 Node *PhaseIdealLoop::split_thru_phi( Node *n, Node *region, int policy ) {
45 if (n->Opcode() == Op_ConvI2L && n->bottom_type() != TypeLong::LONG) {
46 // ConvI2L may have type information on it which is unsafe to push up
47 // so disable this for now
48 return NULL;
49 }
50
51 // Splitting range check CastIIs through a loop induction Phi can
52 // cause new Phis to be created that are left unrelated to the loop
53 // induction Phi and prevent optimizations (vectorization)
54 if (n->Opcode() == Op_CastII && n->as_CastII()->has_range_check() &&
55 region->is_CountedLoop() && n->in(1) == region->as_CountedLoop()->phi()) {
56 return NULL;
57 }
58
59 int wins = 0;
60 assert(!n->is_CFG(), "");
61 assert(region->is_Region(), "");
62
63 const Type* type = n->bottom_type();
64 const TypeOopPtr *t_oop = _igvn.type(n)->isa_oopptr();
65 Node *phi;
66 if (t_oop != NULL && t_oop->is_known_instance_field()) {
67 int iid = t_oop->instance_id();
68 int index = C->get_alias_index(t_oop);
69 int offset = t_oop->offset();
70 phi = new PhiNode(region, type, NULL, iid, index, offset);
71 } else {
72 phi = PhiNode::make_blank(region, n);
73 }
74 uint old_unique = C->unique();
75 for (uint i = 1; i < region->req(); i++) {
76 Node *x;
77 Node* the_clone = NULL;
78 if (region->in(i) == C->top()) {
79 x = C->top(); // Dead path? Use a dead data op
80 } else {
81 x = n->clone(); // Else clone up the data op
82 the_clone = x; // Remember for possible deletion.
83 // Alter data node to use pre-phi inputs
84 if (n->in(0) == region)
85 x->set_req( 0, region->in(i) );
86 for (uint j = 1; j < n->req(); j++) {
87 Node *in = n->in(j);
88 if (in->is_Phi() && in->in(0) == region)
89 x->set_req( j, in->in(i) ); // Use pre-Phi input for the clone
90 }
91 }
92 // Check for a 'win' on some paths
93 const Type *t = x->Value(&_igvn);
94
95 bool singleton = t->singleton();
96
97 // A TOP singleton indicates that there are no possible values incoming
98 // along a particular edge. In most cases, this is OK, and the Phi will
99 // be eliminated later in an Ideal call. However, we can't allow this to
100 // happen if the singleton occurs on loop entry, as the elimination of
101 // the PhiNode may cause the resulting node to migrate back to a previous
102 // loop iteration.
103 if (singleton && t == Type::TOP) {
104 // Is_Loop() == false does not confirm the absence of a loop (e.g., an
105 // irreducible loop may not be indicated by an affirmative is_Loop());
106 // therefore, the only top we can split thru a phi is on a backedge of
107 // a loop.
108 singleton &= region->is_Loop() && (i != LoopNode::EntryControl);
109 }
110
111 if (singleton) {
112 wins++;
113 x = ((PhaseGVN&)_igvn).makecon(t);
114 } else {
115 // We now call Identity to try to simplify the cloned node.
116 // Note that some Identity methods call phase->type(this).
117 // Make sure that the type array is big enough for
118 // our new node, even though we may throw the node away.
119 // (Note: This tweaking with igvn only works because x is a new node.)
120 _igvn.set_type(x, t);
121 // If x is a TypeNode, capture any more-precise type permanently into Node
122 // otherwise it will be not updated during igvn->transform since
123 // igvn->type(x) is set to x->Value() already.
124 x->raise_bottom_type(t);
125 Node *y = x->Identity(&_igvn);
126 if (y != x) {
127 wins++;
128 x = y;
129 } else {
130 y = _igvn.hash_find(x);
131 if (y) {
132 wins++;
133 x = y;
134 } else {
135 // Else x is a new node we are keeping
136 // We do not need register_new_node_with_optimizer
137 // because set_type has already been called.
138 _igvn._worklist.push(x);
139 }
140 }
141 }
142 if (x != the_clone && the_clone != NULL)
143 _igvn.remove_dead_node(the_clone);
144 phi->set_req( i, x );
145 }
146 // Too few wins?
147 if (wins <= policy) {
148 _igvn.remove_dead_node(phi);
149 return NULL;
150 }
151
152 // Record Phi
153 register_new_node( phi, region );
154
155 for (uint i2 = 1; i2 < phi->req(); i2++) {
156 Node *x = phi->in(i2);
157 // If we commoned up the cloned 'x' with another existing Node,
158 // the existing Node picks up a new use. We need to make the
159 // existing Node occur higher up so it dominates its uses.
160 Node *old_ctrl;
161 IdealLoopTree *old_loop;
162
163 if (x->is_Con()) {
164 // Constant's control is always root.
165 set_ctrl(x, C->root());
166 continue;
167 }
168 // The occasional new node
169 if (x->_idx >= old_unique) { // Found a new, unplaced node?
170 old_ctrl = NULL;
171 old_loop = NULL; // Not in any prior loop
172 } else {
173 old_ctrl = get_ctrl(x);
174 old_loop = get_loop(old_ctrl); // Get prior loop
175 }
176 // New late point must dominate new use
177 Node *new_ctrl = dom_lca(old_ctrl, region->in(i2));
178 if (new_ctrl == old_ctrl) // Nothing is changed
179 continue;
180
181 IdealLoopTree *new_loop = get_loop(new_ctrl);
182
183 // Don't move x into a loop if its uses are
184 // outside of loop. Otherwise x will be cloned
185 // for each use outside of this loop.
186 IdealLoopTree *use_loop = get_loop(region);
187 if (!new_loop->is_member(use_loop) &&
188 (old_loop == NULL || !new_loop->is_member(old_loop))) {
189 // Take early control, later control will be recalculated
190 // during next iteration of loop optimizations.
191 new_ctrl = get_early_ctrl(x);
192 new_loop = get_loop(new_ctrl);
193 }
194 // Set new location
195 set_ctrl(x, new_ctrl);
196 // If changing loop bodies, see if we need to collect into new body
197 if (old_loop != new_loop) {
198 if (old_loop && !old_loop->_child)
199 old_loop->_body.yank(x);
200 if (!new_loop->_child)
201 new_loop->_body.push(x); // Collect body info
202 }
203 }
204
205 return phi;
206 }
207
208 //------------------------------dominated_by------------------------------------
209 // Replace the dominated test with an obvious true or false. Place it on the
210 // IGVN worklist for later cleanup. Move control-dependent data Nodes on the
211 // live path up to the dominating control.
212 void PhaseIdealLoop::dominated_by( Node *prevdom, Node *iff, bool flip, bool exclude_loop_predicate ) {
213 if (VerifyLoopOptimizations && PrintOpto) { tty->print_cr("dominating test"); }
214
215 // prevdom is the dominating projection of the dominating test.
216 assert( iff->is_If(), "" );
217 assert(iff->Opcode() == Op_If || iff->Opcode() == Op_CountedLoopEnd || iff->Opcode() == Op_RangeCheck, "Check this code when new subtype is added");
218 int pop = prevdom->Opcode();
219 assert( pop == Op_IfFalse || pop == Op_IfTrue, "" );
220 if (flip) {
221 if (pop == Op_IfTrue)
222 pop = Op_IfFalse;
223 else
224 pop = Op_IfTrue;
225 }
226 // 'con' is set to true or false to kill the dominated test.
227 Node *con = _igvn.makecon(pop == Op_IfTrue ? TypeInt::ONE : TypeInt::ZERO);
228 set_ctrl(con, C->root()); // Constant gets a new use
229 // Hack the dominated test
230 _igvn.replace_input_of(iff, 1, con);
231
232 // If I dont have a reachable TRUE and FALSE path following the IfNode then
233 // I can assume this path reaches an infinite loop. In this case it's not
234 // important to optimize the data Nodes - either the whole compilation will
235 // be tossed or this path (and all data Nodes) will go dead.
236 if (iff->outcnt() != 2) return;
237
238 // Make control-dependent data Nodes on the live path (path that will remain
239 // once the dominated IF is removed) become control-dependent on the
240 // dominating projection.
241 Node* dp = iff->as_If()->proj_out(pop == Op_IfTrue);
242
243 // Loop predicates may have depending checks which should not
244 // be skipped. For example, range check predicate has two checks
245 // for lower and upper bounds.
246 if (dp == NULL)
247 return;
248
249 ProjNode* dp_proj = dp->as_Proj();
250 ProjNode* unc_proj = iff->as_If()->proj_out(1 - dp_proj->_con)->as_Proj();
251 if (exclude_loop_predicate &&
252 (unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_predicate) != NULL ||
253 unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_range_check) != NULL)) {
254 // If this is a range check (IfNode::is_range_check), do not
255 // reorder because Compile::allow_range_check_smearing might have
256 // changed the check.
257 return; // Let IGVN transformation change control dependence.
258 }
259
260 IdealLoopTree *old_loop = get_loop(dp);
261
262 for (DUIterator_Fast imax, i = dp->fast_outs(imax); i < imax; i++) {
263 Node* cd = dp->fast_out(i); // Control-dependent node
264 if (cd->depends_only_on_test()) {
265 assert(cd->in(0) == dp, "");
266 _igvn.replace_input_of(cd, 0, prevdom);
267 set_early_ctrl(cd);
268 IdealLoopTree *new_loop = get_loop(get_ctrl(cd));
269 if (old_loop != new_loop) {
270 if (!old_loop->_child) old_loop->_body.yank(cd);
271 if (!new_loop->_child) new_loop->_body.push(cd);
272 }
273 --i;
274 --imax;
275 }
276 }
277 }
278
279 //------------------------------has_local_phi_input----------------------------
280 // Return TRUE if 'n' has Phi inputs from its local block and no other
281 // block-local inputs (all non-local-phi inputs come from earlier blocks)
282 Node *PhaseIdealLoop::has_local_phi_input( Node *n ) {
283 Node *n_ctrl = get_ctrl(n);
284 // See if some inputs come from a Phi in this block, or from before
285 // this block.
286 uint i;
287 for( i = 1; i < n->req(); i++ ) {
288 Node *phi = n->in(i);
289 if( phi->is_Phi() && phi->in(0) == n_ctrl )
290 break;
291 }
292 if( i >= n->req() )
293 return NULL; // No Phi inputs; nowhere to clone thru
294
295 // Check for inputs created between 'n' and the Phi input. These
296 // must split as well; they have already been given the chance
297 // (courtesy of a post-order visit) and since they did not we must
298 // recover the 'cost' of splitting them by being very profitable
299 // when splitting 'n'. Since this is unlikely we simply give up.
300 for( i = 1; i < n->req(); i++ ) {
301 Node *m = n->in(i);
302 if( get_ctrl(m) == n_ctrl && !m->is_Phi() ) {
303 // We allow the special case of AddP's with no local inputs.
304 // This allows us to split-up address expressions.
305 if (m->is_AddP() &&
306 get_ctrl(m->in(2)) != n_ctrl &&
307 get_ctrl(m->in(3)) != n_ctrl) {
308 // Move the AddP up to dominating point
309 Node* c = find_non_split_ctrl(idom(n_ctrl));
310 if (c->Opcode() == Op_Loop && c->as_Loop()->is_strip_mined()) {
311 c->as_Loop()->verify_strip_mined(1);
312 c = c->in(LoopNode::EntryControl);
313 }
314 set_ctrl_and_loop(m, c);
315 continue;
316 }
317 return NULL;
318 }
319 }
320
321 return n_ctrl;
322 }
323
324 //------------------------------remix_address_expressions----------------------
325 // Rework addressing expressions to get the most loop-invariant stuff
326 // moved out. We'd like to do all associative operators, but it's especially
327 // important (common) to do address expressions.
328 Node *PhaseIdealLoop::remix_address_expressions( Node *n ) {
329 if (!has_ctrl(n)) return NULL;
330 Node *n_ctrl = get_ctrl(n);
331 IdealLoopTree *n_loop = get_loop(n_ctrl);
332
333 // See if 'n' mixes loop-varying and loop-invariant inputs and
334 // itself is loop-varying.
335
336 // Only interested in binary ops (and AddP)
337 if( n->req() < 3 || n->req() > 4 ) return NULL;
338
339 Node *n1_ctrl = get_ctrl(n->in( 1));
340 Node *n2_ctrl = get_ctrl(n->in( 2));
341 Node *n3_ctrl = get_ctrl(n->in(n->req() == 3 ? 2 : 3));
342 IdealLoopTree *n1_loop = get_loop( n1_ctrl );
343 IdealLoopTree *n2_loop = get_loop( n2_ctrl );
344 IdealLoopTree *n3_loop = get_loop( n3_ctrl );
345
346 // Does one of my inputs spin in a tighter loop than self?
347 if( (n_loop->is_member( n1_loop ) && n_loop != n1_loop) ||
348 (n_loop->is_member( n2_loop ) && n_loop != n2_loop) ||
349 (n_loop->is_member( n3_loop ) && n_loop != n3_loop) )
350 return NULL; // Leave well enough alone
351
352 // Is at least one of my inputs loop-invariant?
353 if( n1_loop == n_loop &&
354 n2_loop == n_loop &&
355 n3_loop == n_loop )
356 return NULL; // No loop-invariant inputs
357
358
359 int n_op = n->Opcode();
360
361 // Replace expressions like ((V+I) << 2) with (V<<2 + I<<2).
362 if( n_op == Op_LShiftI ) {
363 // Scale is loop invariant
364 Node *scale = n->in(2);
365 Node *scale_ctrl = get_ctrl(scale);
366 IdealLoopTree *scale_loop = get_loop(scale_ctrl );
367 if( n_loop == scale_loop || !scale_loop->is_member( n_loop ) )
368 return NULL;
369 const TypeInt *scale_t = scale->bottom_type()->isa_int();
370 if( scale_t && scale_t->is_con() && scale_t->get_con() >= 16 )
371 return NULL; // Dont bother with byte/short masking
372 // Add must vary with loop (else shift would be loop-invariant)
373 Node *add = n->in(1);
374 Node *add_ctrl = get_ctrl(add);
375 IdealLoopTree *add_loop = get_loop(add_ctrl);
376 //assert( n_loop == add_loop, "" );
377 if( n_loop != add_loop ) return NULL; // happens w/ evil ZKM loops
378
379 // Convert I-V into I+ (0-V); same for V-I
380 if( add->Opcode() == Op_SubI &&
381 _igvn.type( add->in(1) ) != TypeInt::ZERO ) {
382 Node *zero = _igvn.intcon(0);
383 set_ctrl(zero, C->root());
384 Node *neg = new SubINode( _igvn.intcon(0), add->in(2) );
385 register_new_node( neg, get_ctrl(add->in(2) ) );
386 add = new AddINode( add->in(1), neg );
387 register_new_node( add, add_ctrl );
388 }
389 if( add->Opcode() != Op_AddI ) return NULL;
390 // See if one add input is loop invariant
391 Node *add_var = add->in(1);
392 Node *add_var_ctrl = get_ctrl(add_var);
393 IdealLoopTree *add_var_loop = get_loop(add_var_ctrl );
394 Node *add_invar = add->in(2);
395 Node *add_invar_ctrl = get_ctrl(add_invar);
396 IdealLoopTree *add_invar_loop = get_loop(add_invar_ctrl );
397 if( add_var_loop == n_loop ) {
398 } else if( add_invar_loop == n_loop ) {
399 // Swap to find the invariant part
400 add_invar = add_var;
401 add_invar_ctrl = add_var_ctrl;
402 add_invar_loop = add_var_loop;
403 add_var = add->in(2);
404 Node *add_var_ctrl = get_ctrl(add_var);
405 IdealLoopTree *add_var_loop = get_loop(add_var_ctrl );
406 } else // Else neither input is loop invariant
407 return NULL;
408 if( n_loop == add_invar_loop || !add_invar_loop->is_member( n_loop ) )
409 return NULL; // No invariant part of the add?
410
411 // Yes! Reshape address expression!
412 Node *inv_scale = new LShiftINode( add_invar, scale );
413 Node *inv_scale_ctrl =
414 dom_depth(add_invar_ctrl) > dom_depth(scale_ctrl) ?
415 add_invar_ctrl : scale_ctrl;
416 register_new_node( inv_scale, inv_scale_ctrl );
417 Node *var_scale = new LShiftINode( add_var, scale );
418 register_new_node( var_scale, n_ctrl );
419 Node *var_add = new AddINode( var_scale, inv_scale );
420 register_new_node( var_add, n_ctrl );
421 _igvn.replace_node( n, var_add );
422 return var_add;
423 }
424
425 // Replace (I+V) with (V+I)
426 if( n_op == Op_AddI ||
427 n_op == Op_AddL ||
428 n_op == Op_AddF ||
429 n_op == Op_AddD ||
430 n_op == Op_MulI ||
431 n_op == Op_MulL ||
432 n_op == Op_MulF ||
433 n_op == Op_MulD ) {
434 if( n2_loop == n_loop ) {
435 assert( n1_loop != n_loop, "" );
436 n->swap_edges(1, 2);
437 }
438 }
439
440 // Replace ((I1 +p V) +p I2) with ((I1 +p I2) +p V),
441 // but not if I2 is a constant.
442 if( n_op == Op_AddP ) {
443 if( n2_loop == n_loop && n3_loop != n_loop ) {
444 if( n->in(2)->Opcode() == Op_AddP && !n->in(3)->is_Con() ) {
445 Node *n22_ctrl = get_ctrl(n->in(2)->in(2));
446 Node *n23_ctrl = get_ctrl(n->in(2)->in(3));
447 IdealLoopTree *n22loop = get_loop( n22_ctrl );
448 IdealLoopTree *n23_loop = get_loop( n23_ctrl );
449 if( n22loop != n_loop && n22loop->is_member(n_loop) &&
450 n23_loop == n_loop ) {
451 Node *add1 = new AddPNode( n->in(1), n->in(2)->in(2), n->in(3) );
452 // Stuff new AddP in the loop preheader
453 register_new_node( add1, n_loop->_head->in(LoopNode::EntryControl) );
454 Node *add2 = new AddPNode( n->in(1), add1, n->in(2)->in(3) );
455 register_new_node( add2, n_ctrl );
456 _igvn.replace_node( n, add2 );
457 return add2;
458 }
459 }
460 }
461
462 // Replace (I1 +p (I2 + V)) with ((I1 +p I2) +p V)
463 if (n2_loop != n_loop && n3_loop == n_loop) {
464 if (n->in(3)->Opcode() == Op_AddX) {
465 Node *V = n->in(3)->in(1);
466 Node *I = n->in(3)->in(2);
467 if (is_member(n_loop,get_ctrl(V))) {
468 } else {
469 Node *tmp = V; V = I; I = tmp;
470 }
471 if (!is_member(n_loop,get_ctrl(I))) {
472 Node *add1 = new AddPNode(n->in(1), n->in(2), I);
473 // Stuff new AddP in the loop preheader
474 register_new_node(add1, n_loop->_head->in(LoopNode::EntryControl));
475 Node *add2 = new AddPNode(n->in(1), add1, V);
476 register_new_node(add2, n_ctrl);
477 _igvn.replace_node(n, add2);
478 return add2;
479 }
480 }
481 }
482 }
483
484 return NULL;
485 }
486
487 //------------------------------conditional_move-------------------------------
488 // Attempt to replace a Phi with a conditional move. We have some pretty
489 // strict profitability requirements. All Phis at the merge point must
490 // be converted, so we can remove the control flow. We need to limit the
491 // number of c-moves to a small handful. All code that was in the side-arms
492 // of the CFG diamond is now speculatively executed. This code has to be
493 // "cheap enough". We are pretty much limited to CFG diamonds that merge
494 // 1 or 2 items with a total of 1 or 2 ops executed speculatively.
495 Node *PhaseIdealLoop::conditional_move( Node *region ) {
496
497 assert(region->is_Region(), "sanity check");
498 if (region->req() != 3) return NULL;
499
500 // Check for CFG diamond
501 Node *lp = region->in(1);
502 Node *rp = region->in(2);
503 if (!lp || !rp) return NULL;
504 Node *lp_c = lp->in(0);
505 if (lp_c == NULL || lp_c != rp->in(0) || !lp_c->is_If()) return NULL;
506 IfNode *iff = lp_c->as_If();
507
508 // Check for ops pinned in an arm of the diamond.
509 // Can't remove the control flow in this case
510 if (lp->outcnt() > 1) return NULL;
511 if (rp->outcnt() > 1) return NULL;
512
513 IdealLoopTree* r_loop = get_loop(region);
514 assert(r_loop == get_loop(iff), "sanity");
515 // Always convert to CMOVE if all results are used only outside this loop.
516 bool used_inside_loop = (r_loop == _ltree_root);
517
518 // Check profitability
519 int cost = 0;
520 int phis = 0;
521 for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
522 Node *out = region->fast_out(i);
523 if (!out->is_Phi()) continue; // Ignore other control edges, etc
524 phis++;
525 PhiNode* phi = out->as_Phi();
526 BasicType bt = phi->type()->basic_type();
527 switch (bt) {
528 case T_DOUBLE:
529 if (C->use_cmove()) {
530 continue; //TODO: maybe we want to add some cost
531 }
532 case T_FLOAT: {
533 cost += Matcher::float_cmove_cost(); // Could be very expensive
534 break;
535 }
536 case T_LONG: {
537 cost += Matcher::long_cmove_cost(); // May encodes as 2 CMOV's
538 }
539 case T_INT: // These all CMOV fine
540 case T_ADDRESS: { // (RawPtr)
541 cost++;
542 break;
543 }
544 case T_NARROWOOP: // Fall through
545 case T_OBJECT: { // Base oops are OK, but not derived oops
546 const TypeOopPtr *tp = phi->type()->make_ptr()->isa_oopptr();
547 // Derived pointers are Bad (tm): what's the Base (for GC purposes) of a
548 // CMOVE'd derived pointer? It's a CMOVE'd derived base. Thus
549 // CMOVE'ing a derived pointer requires we also CMOVE the base. If we
550 // have a Phi for the base here that we convert to a CMOVE all is well
551 // and good. But if the base is dead, we'll not make a CMOVE. Later
552 // the allocator will have to produce a base by creating a CMOVE of the
553 // relevant bases. This puts the allocator in the business of
554 // manufacturing expensive instructions, generally a bad plan.
555 // Just Say No to Conditionally-Moved Derived Pointers.
556 if (tp && tp->offset() != 0)
557 return NULL;
558 cost++;
559 break;
560 }
561 default:
562 return NULL; // In particular, can't do memory or I/O
563 }
564 // Add in cost any speculative ops
565 for (uint j = 1; j < region->req(); j++) {
566 Node *proj = region->in(j);
567 Node *inp = phi->in(j);
568 if (get_ctrl(inp) == proj) { // Found local op
569 cost++;
570 // Check for a chain of dependent ops; these will all become
571 // speculative in a CMOV.
572 for (uint k = 1; k < inp->req(); k++)
573 if (get_ctrl(inp->in(k)) == proj)
574 cost += ConditionalMoveLimit; // Too much speculative goo
575 }
576 }
577 // See if the Phi is used by a Cmp or Narrow oop Decode/Encode.
578 // This will likely Split-If, a higher-payoff operation.
579 for (DUIterator_Fast kmax, k = phi->fast_outs(kmax); k < kmax; k++) {
580 Node* use = phi->fast_out(k);
581 if (use->is_Cmp() || use->is_DecodeNarrowPtr() || use->is_EncodeNarrowPtr())
582 cost += ConditionalMoveLimit;
583 // Is there a use inside the loop?
584 // Note: check only basic types since CMoveP is pinned.
585 if (!used_inside_loop && is_java_primitive(bt)) {
586 IdealLoopTree* u_loop = get_loop(has_ctrl(use) ? get_ctrl(use) : use);
587 if (r_loop == u_loop || r_loop->is_member(u_loop)) {
588 used_inside_loop = true;
589 }
590 }
591 }
592 }//for
593 Node* bol = iff->in(1);
594 assert(bol->Opcode() == Op_Bool, "");
595 int cmp_op = bol->in(1)->Opcode();
596 // It is expensive to generate flags from a float compare.
597 // Avoid duplicated float compare.
598 if (phis > 1 && (cmp_op == Op_CmpF || cmp_op == Op_CmpD)) return NULL;
599
600 float infrequent_prob = PROB_UNLIKELY_MAG(3);
601 // Ignore cost and blocks frequency if CMOVE can be moved outside the loop.
602 if (used_inside_loop) {
603 if (cost >= ConditionalMoveLimit) return NULL; // Too much goo
604
605 // BlockLayoutByFrequency optimization moves infrequent branch
606 // from hot path. No point in CMOV'ing in such case (110 is used
607 // instead of 100 to take into account not exactness of float value).
608 if (BlockLayoutByFrequency) {
609 infrequent_prob = MAX2(infrequent_prob, (float)BlockLayoutMinDiamondPercentage/110.0f);
610 }
611 }
612 // Check for highly predictable branch. No point in CMOV'ing if
613 // we are going to predict accurately all the time.
614 if (C->use_cmove() && cmp_op == Op_CmpD) ;//keep going
615 else if (iff->_prob < infrequent_prob ||
616 iff->_prob > (1.0f - infrequent_prob))
617 return NULL;
618
619 // --------------
620 // Now replace all Phis with CMOV's
621 Node *cmov_ctrl = iff->in(0);
622 uint flip = (lp->Opcode() == Op_IfTrue);
623 while (1) {
624 PhiNode* phi = NULL;
625 for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
626 Node *out = region->fast_out(i);
627 if (out->is_Phi()) {
628 phi = out->as_Phi();
629 break;
630 }
631 }
632 if (phi == NULL) break;
633 if (PrintOpto && VerifyLoopOptimizations) { tty->print_cr("CMOV"); }
634 // Move speculative ops
635 for (uint j = 1; j < region->req(); j++) {
636 Node *proj = region->in(j);
637 Node *inp = phi->in(j);
638 if (get_ctrl(inp) == proj) { // Found local op
639 #ifndef PRODUCT
640 if (PrintOpto && VerifyLoopOptimizations) {
641 tty->print(" speculate: ");
642 inp->dump();
643 }
644 #endif
645 set_ctrl(inp, cmov_ctrl);
646 }
647 }
648 Node *cmov = CMoveNode::make(cmov_ctrl, iff->in(1), phi->in(1+flip), phi->in(2-flip), _igvn.type(phi));
649 register_new_node( cmov, cmov_ctrl );
650 _igvn.replace_node( phi, cmov );
651 #ifndef PRODUCT
652 if (TraceLoopOpts) {
653 tty->print("CMOV ");
654 r_loop->dump_head();
655 if (Verbose) {
656 bol->in(1)->dump(1);
657 cmov->dump(1);
658 }
659 }
660 if (VerifyLoopOptimizations) verify();
661 #endif
662 }
663
664 // The useless CFG diamond will fold up later; see the optimization in
665 // RegionNode::Ideal.
666 _igvn._worklist.push(region);
667
668 return iff->in(1);
669 }
670
671 static void enqueue_cfg_uses(Node* m, Unique_Node_List& wq) {
672 for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax; i++) {
673 Node* u = m->fast_out(i);
674 if (u->is_CFG()) {
675 if (u->Opcode() == Op_NeverBranch) {
676 u = ((NeverBranchNode*)u)->proj_out(0);
677 enqueue_cfg_uses(u, wq);
678 } else {
679 wq.push(u);
680 }
681 }
682 }
683 }
684
685 // Try moving a store out of a loop, right before the loop
686 Node* PhaseIdealLoop::try_move_store_before_loop(Node* n, Node *n_ctrl) {
687 // Store has to be first in the loop body
688 IdealLoopTree *n_loop = get_loop(n_ctrl);
689 if (n->is_Store() && n_loop != _ltree_root && n_loop->is_loop() && n->in(0) != NULL) {
690 Node* address = n->in(MemNode::Address);
691 Node* value = n->in(MemNode::ValueIn);
692 Node* mem = n->in(MemNode::Memory);
693 IdealLoopTree* address_loop = get_loop(get_ctrl(address));
694 IdealLoopTree* value_loop = get_loop(get_ctrl(value));
695
696 // - address and value must be loop invariant
697 // - memory must be a memory Phi for the loop
698 // - Store must be the only store on this memory slice in the
699 // loop: if there's another store following this one then value
700 // written at iteration i by the second store could be overwritten
701 // at iteration i+n by the first store: it's not safe to move the
702 // first store out of the loop
703 // - nothing must observe the memory Phi: it guarantees no read
704 // before the store, we are also guaranteed the store post
705 // dominates the loop head (ignoring a possible early
706 // exit). Otherwise there would be extra Phi involved between the
707 // loop's Phi and the store.
708 // - there must be no early exit from the loop before the Store
709 // (such an exit most of the time would be an extra use of the
710 // memory Phi but sometimes is a bottom memory Phi that takes the
711 // store as input).
712
713 if (!n_loop->is_member(address_loop) &&
714 !n_loop->is_member(value_loop) &&
715 mem->is_Phi() && mem->in(0) == n_loop->_head &&
716 mem->outcnt() == 1 &&
717 mem->in(LoopNode::LoopBackControl) == n) {
718
719 assert(n_loop->_tail != NULL, "need a tail");
720 assert(is_dominator(n_ctrl, n_loop->_tail), "store control must not be in a branch in the loop");
721
722 // Verify that there's no early exit of the loop before the store.
723 bool ctrl_ok = false;
724 {
725 // Follow control from loop head until n, we exit the loop or
726 // we reach the tail
727 ResourceMark rm;
728 Unique_Node_List wq;
729 wq.push(n_loop->_head);
730
731 for (uint next = 0; next < wq.size(); ++next) {
732 Node *m = wq.at(next);
733 if (m == n->in(0)) {
734 ctrl_ok = true;
735 continue;
736 }
737 assert(!has_ctrl(m), "should be CFG");
738 if (!n_loop->is_member(get_loop(m)) || m == n_loop->_tail) {
739 ctrl_ok = false;
740 break;
741 }
742 enqueue_cfg_uses(m, wq);
743 if (wq.size() > 10) {
744 ctrl_ok = false;
745 break;
746 }
747 }
748 }
749 if (ctrl_ok) {
750 // move the Store
751 _igvn.replace_input_of(mem, LoopNode::LoopBackControl, mem);
752 _igvn.replace_input_of(n, 0, n_loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl));
753 _igvn.replace_input_of(n, MemNode::Memory, mem->in(LoopNode::EntryControl));
754 // Disconnect the phi now. An empty phi can confuse other
755 // optimizations in this pass of loop opts.
756 _igvn.replace_node(mem, mem->in(LoopNode::EntryControl));
757 n_loop->_body.yank(mem);
758
759 set_ctrl_and_loop(n, n->in(0));
760
761 return n;
762 }
763 }
764 }
765 return NULL;
766 }
767
768 // Try moving a store out of a loop, right after the loop
769 void PhaseIdealLoop::try_move_store_after_loop(Node* n) {
770 if (n->is_Store() && n->in(0) != NULL) {
771 Node *n_ctrl = get_ctrl(n);
772 IdealLoopTree *n_loop = get_loop(n_ctrl);
773 // Store must be in a loop
774 if (n_loop != _ltree_root && !n_loop->_irreducible) {
775 Node* address = n->in(MemNode::Address);
776 Node* value = n->in(MemNode::ValueIn);
777 IdealLoopTree* address_loop = get_loop(get_ctrl(address));
778 // address must be loop invariant
779 if (!n_loop->is_member(address_loop)) {
780 // Store must be last on this memory slice in the loop and
781 // nothing in the loop must observe it
782 Node* phi = NULL;
783 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
784 Node* u = n->fast_out(i);
785 if (has_ctrl(u)) { // control use?
786 IdealLoopTree *u_loop = get_loop(get_ctrl(u));
787 if (!n_loop->is_member(u_loop)) {
788 continue;
789 }
790 if (u->is_Phi() && u->in(0) == n_loop->_head) {
791 assert(_igvn.type(u) == Type::MEMORY, "bad phi");
792 // multiple phis on the same slice are possible
793 if (phi != NULL) {
794 return;
795 }
796 phi = u;
797 continue;
798 }
799 }
800 return;
801 }
802 if (phi != NULL) {
803 // Nothing in the loop before the store (next iteration)
804 // must observe the stored value
805 bool mem_ok = true;
806 {
807 ResourceMark rm;
808 Unique_Node_List wq;
809 wq.push(phi);
810 for (uint next = 0; next < wq.size() && mem_ok; ++next) {
811 Node *m = wq.at(next);
812 for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax && mem_ok; i++) {
813 Node* u = m->fast_out(i);
814 if (u->is_Store() || u->is_Phi()) {
815 if (u != n) {
816 wq.push(u);
817 mem_ok = (wq.size() <= 10);
818 }
819 } else {
820 mem_ok = false;
821 break;
822 }
823 }
824 }
825 }
826 if (mem_ok) {
827 // Move the Store out of the loop creating clones along
828 // all paths out of the loop that observe the stored value
829 _igvn.rehash_node_delayed(phi);
830 IdealLoopTree* outer_loop = n_loop;
831 if (n_loop->_head->is_Loop() && n_loop->_head->as_Loop()->is_strip_mined()) {
832 assert(n_loop->_head->Opcode() == Op_CountedLoop, "outer loop is a strip mined");
833 n_loop->_head->as_Loop()->verify_strip_mined(1);
834 Node* outer = n_loop->_head->as_CountedLoop()->outer_loop();
835 outer_loop = get_loop(outer);
836 assert(n_loop->_parent == outer_loop, "broken loop tree");
837 }
838 int count = phi->replace_edge(n, n->in(MemNode::Memory));
839 assert(count > 0, "inconsistent phi");
840 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
841 Node* u = n->fast_out(i);
842 Node* c = get_ctrl(u);
843
844 if (u->is_Phi()) {
845 c = u->in(0)->in(u->find_edge(n));
846 }
847 IdealLoopTree *u_loop = get_loop(c);
848 assert (!n_loop->is_member(u_loop), "only the phi should have been a use in the loop");
849 while(true) {
850 Node* next_c = find_non_split_ctrl(idom(c));
851 if (outer_loop->is_member(get_loop(next_c))) {
852 break;
853 }
854 c = next_c;
855 }
856
857 Node* st = n->clone();
858 st->set_req(0, c);
859 _igvn.register_new_node_with_optimizer(st);
860
861 set_ctrl(st, c);
862 IdealLoopTree* new_loop = get_loop(c);
863 assert(new_loop != n_loop, "should be moved out of loop");
864 if (new_loop->_child == NULL) new_loop->_body.push(st);
865
866 _igvn.replace_input_of(u, u->find_edge(n), st);
867 --imax;
868 --i;
869 }
870
871
872 assert(n->outcnt() == 0, "all uses should be gone");
873 _igvn.replace_input_of(n, MemNode::Memory, C->top());
874 // Disconnect the phi now. An empty phi can confuse other
875 // optimizations in this pass of loop opts..
876 if (phi->in(LoopNode::LoopBackControl) == phi) {
877 _igvn.replace_node(phi, phi->in(LoopNode::EntryControl));
878 n_loop->_body.yank(phi);
879 }
880 }
881 }
882 }
883 }
884 }
885 }
886
887 //------------------------------split_if_with_blocks_pre-----------------------
888 // Do the real work in a non-recursive function. Data nodes want to be
889 // cloned in the pre-order so they can feed each other nicely.
890 Node *PhaseIdealLoop::split_if_with_blocks_pre( Node *n ) {
891 // Cloning these guys is unlikely to win
892 int n_op = n->Opcode();
893 if( n_op == Op_MergeMem ) return n;
894 if( n->is_Proj() ) return n;
895 // Do not clone-up CmpFXXX variations, as these are always
896 // followed by a CmpI
897 if( n->is_Cmp() ) return n;
898 // Attempt to use a conditional move instead of a phi/branch
899 if( ConditionalMoveLimit > 0 && n_op == Op_Region ) {
900 Node *cmov = conditional_move( n );
901 if( cmov ) return cmov;
902 }
903 if( n->is_CFG() || n->is_LoadStore() )
904 return n;
905 if( n_op == Op_Opaque1 || // Opaque nodes cannot be mod'd
906 n_op == Op_Opaque2 ||
907 n_op == Op_Opaque5) {
908 if( !C->major_progress() ) // If chance of no more loop opts...
909 _igvn._worklist.push(n); // maybe we'll remove them
910 return n;
911 }
912
913 if( n->is_Con() ) return n; // No cloning for Con nodes
914
915 Node *n_ctrl = get_ctrl(n);
916 if( !n_ctrl ) return n; // Dead node
917
918 Node* res = try_move_store_before_loop(n, n_ctrl);
919 if (res != NULL) {
920 return n;
921 }
922
923 // Attempt to remix address expressions for loop invariants
924 Node *m = remix_address_expressions( n );
925 if( m ) return m;
926
927 if (n->is_ConstraintCast()) {
928 Node* dom_cast = n->as_ConstraintCast()->dominating_cast(&_igvn, this);
929 // ConstraintCastNode::dominating_cast() uses node control input to determine domination.
930 // Node control inputs don't necessarily agree with loop control info (due to
931 // transformations happened in between), thus additional dominance check is needed
932 // to keep loop info valid.
933 if (dom_cast != NULL && is_dominator(get_ctrl(dom_cast), get_ctrl(n))) {
934 _igvn.replace_node(n, dom_cast);
935 return dom_cast;
936 }
937 }
938
939 // Determine if the Node has inputs from some local Phi.
940 // Returns the block to clone thru.
941 Node *n_blk = has_local_phi_input( n );
942 if( !n_blk ) return n;
943
944 // Do not clone the trip counter through on a CountedLoop
945 // (messes up the canonical shape).
946 if( n_blk->is_CountedLoop() && n->Opcode() == Op_AddI ) return n;
947
948 // Check for having no control input; not pinned. Allow
949 // dominating control.
950 if (n->in(0)) {
951 Node *dom = idom(n_blk);
952 if (dom_lca(n->in(0), dom) != n->in(0)) {
953 return n;
954 }
955 }
956 // Policy: when is it profitable. You must get more wins than
957 // policy before it is considered profitable. Policy is usually 0,
958 // so 1 win is considered profitable. Big merges will require big
959 // cloning, so get a larger policy.
960 int policy = n_blk->req() >> 2;
961
962 // If the loop is a candidate for range check elimination,
963 // delay splitting through it's phi until a later loop optimization
964 if (n_blk->is_CountedLoop()) {
965 IdealLoopTree *lp = get_loop(n_blk);
966 if (lp && lp->_rce_candidate) {
967 return n;
968 }
969 }
970
971 // Use same limit as split_if_with_blocks_post
972 if( C->live_nodes() > 35000 ) return n; // Method too big
973
974 // Split 'n' through the merge point if it is profitable
975 Node *phi = split_thru_phi( n, n_blk, policy );
976 if (!phi) return n;
977
978 // Found a Phi to split thru!
979 // Replace 'n' with the new phi
980 _igvn.replace_node( n, phi );
981 // Moved a load around the loop, 'en-registering' something.
982 if (n_blk->is_Loop() && n->is_Load() &&
983 !phi->in(LoopNode::LoopBackControl)->is_Load())
984 C->set_major_progress();
985
986 return phi;
987 }
988
989 static bool merge_point_too_heavy(Compile* C, Node* region) {
990 // Bail out if the region and its phis have too many users.
991 int weight = 0;
992 for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
993 weight += region->fast_out(i)->outcnt();
994 }
995 int nodes_left = C->max_node_limit() - C->live_nodes();
996 if (weight * 8 > nodes_left) {
997 if (PrintOpto) {
998 tty->print_cr("*** Split-if bails out: %d nodes, region weight %d", C->unique(), weight);
999 }
1000 return true;
1001 } else {
1002 return false;
1003 }
1004 }
1005
1006 static bool merge_point_safe(Node* region) {
1007 // 4799512: Stop split_if_with_blocks from splitting a block with a ConvI2LNode
1008 // having a PhiNode input. This sidesteps the dangerous case where the split
1009 // ConvI2LNode may become TOP if the input Value() does not
1010 // overlap the ConvI2L range, leaving a node which may not dominate its
1011 // uses.
1012 // A better fix for this problem can be found in the BugTraq entry, but
1013 // expediency for Mantis demands this hack.
1014 // 6855164: If the merge point has a FastLockNode with a PhiNode input, we stop
1015 // split_if_with_blocks from splitting a block because we could not move around
1016 // the FastLockNode.
1017 for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
1018 Node* n = region->fast_out(i);
1019 if (n->is_Phi()) {
1020 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
1021 Node* m = n->fast_out(j);
1022 if (m->is_FastLock())
1023 return false;
1024 #ifdef _LP64
1025 if (m->Opcode() == Op_ConvI2L)
1026 return false;
1027 if (m->is_CastII() && m->isa_CastII()->has_range_check()) {
1028 return false;
1029 }
1030 #endif
1031 }
1032 }
1033 }
1034 return true;
1035 }
1036
1037
1038 //------------------------------place_near_use---------------------------------
1039 // Place some computation next to use but not inside inner loops.
1040 // For inner loop uses move it to the preheader area.
1041 Node *PhaseIdealLoop::place_near_use( Node *useblock ) const {
1042 IdealLoopTree *u_loop = get_loop( useblock );
1043 return (u_loop->_irreducible || u_loop->_child)
1044 ? useblock
1045 : u_loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode::EntryControl);
1046 }
1047
1048
1049 bool PhaseIdealLoop::identical_backtoback_ifs(Node *n) {
1050 if (!n->is_If()) {
1051 return false;
1052 }
1053 if (!n->in(0)->is_Region()) {
1054 return false;
1055 }
1056 Node* region = n->in(0);
1057 Node* dom = idom(region);
1058 if (!dom->is_If() || dom->in(1) != n->in(1)) {
1059 return false;
1060 }
1061 IfNode* dom_if = dom->as_If();
1062 Node* proj_true = dom_if->proj_out(1);
1063 Node* proj_false = dom_if->proj_out(0);
1064
1065 for (uint i = 1; i < region->req(); i++) {
1066 if (is_dominator(proj_true, region->in(i))) {
1067 continue;
1068 }
1069 if (is_dominator(proj_false, region->in(i))) {
1070 continue;
1071 }
1072 return false;
1073 }
1074
1075 return true;
1076 }
1077
1078 bool PhaseIdealLoop::can_split_if(Node *n_ctrl) {
1079 if (C->live_nodes() > 35000) {
1080 return false; // Method too big
1081 }
1082
1083 // Do not do 'split-if' if irreducible loops are present.
1084 if (_has_irreducible_loops) {
1085 return false;
1086 }
1087
1088 if (merge_point_too_heavy(C, n_ctrl)) {
1089 return false;
1090 }
1091
1092 // Do not do 'split-if' if some paths are dead. First do dead code
1093 // elimination and then see if its still profitable.
1094 for (uint i = 1; i < n_ctrl->req(); i++) {
1095 if (n_ctrl->in(i) == C->top()) {
1096 return false;
1097 }
1098 }
1099
1100 // If trying to do a 'Split-If' at the loop head, it is only
1101 // profitable if the cmp folds up on BOTH paths. Otherwise we
1102 // risk peeling a loop forever.
1103
1104 // CNC - Disabled for now. Requires careful handling of loop
1105 // body selection for the cloned code. Also, make sure we check
1106 // for any input path not being in the same loop as n_ctrl. For
1107 // irreducible loops we cannot check for 'n_ctrl->is_Loop()'
1108 // because the alternative loop entry points won't be converted
1109 // into LoopNodes.
1110 IdealLoopTree *n_loop = get_loop(n_ctrl);
1111 for (uint j = 1; j < n_ctrl->req(); j++) {
1112 if (get_loop(n_ctrl->in(j)) != n_loop) {
1113 return false;
1114 }
1115 }
1116
1117 // Check for safety of the merge point.
1118 if (!merge_point_safe(n_ctrl)) {
1119 return false;
1120 }
1121
1122 return true;
1123 }
1124
1125 //------------------------------split_if_with_blocks_post----------------------
1126 // Do the real work in a non-recursive function. CFG hackery wants to be
1127 // in the post-order, so it can dirty the I-DOM info and not use the dirtied
1128 // info.
1129 void PhaseIdealLoop::split_if_with_blocks_post(Node *n) {
1130
1131 // Cloning Cmp through Phi's involves the split-if transform.
1132 // FastLock is not used by an If
1133 if (n->is_Cmp() && !n->is_FastLock()) {
1134 Node *n_ctrl = get_ctrl(n);
1135 // Determine if the Node has inputs from some local Phi.
1136 // Returns the block to clone thru.
1137 Node *n_blk = has_local_phi_input(n);
1138 if (n_blk != n_ctrl) {
1139 return;
1140 }
1141
1142 if (!can_split_if(n_ctrl)) {
1143 return;
1144 }
1145
1146 if (n->outcnt() != 1) {
1147 return; // Multiple bool's from 1 compare?
1148 }
1149 Node *bol = n->unique_out();
1150 assert(bol->is_Bool(), "expect a bool here");
1151 if (bol->outcnt() != 1) {
1152 return;// Multiple branches from 1 compare?
1153 }
1154 Node *iff = bol->unique_out();
1155
1156 // Check some safety conditions
1157 if (iff->is_If()) { // Classic split-if?
1158 if (iff->in(0) != n_ctrl) {
1159 return; // Compare must be in same blk as if
1160 }
1161 } else if (iff->is_CMove()) { // Trying to split-up a CMOVE
1162 // Can't split CMove with different control edge.
1163 if (iff->in(0) != NULL && iff->in(0) != n_ctrl ) {
1164 return;
1165 }
1166 if (get_ctrl(iff->in(2)) == n_ctrl ||
1167 get_ctrl(iff->in(3)) == n_ctrl) {
1168 return; // Inputs not yet split-up
1169 }
1170 if (get_loop(n_ctrl) != get_loop(get_ctrl(iff))) {
1171 return; // Loop-invar test gates loop-varying CMOVE
1172 }
1173 } else {
1174 return; // some other kind of node, such as an Allocate
1175 }
1176
1177 // When is split-if profitable? Every 'win' on means some control flow
1178 // goes dead, so it's almost always a win.
1179 int policy = 0;
1180 // Split compare 'n' through the merge point if it is profitable
1181 Node *phi = split_thru_phi( n, n_ctrl, policy);
1182 if (!phi) {
1183 return;
1184 }
1185
1186 // Found a Phi to split thru!
1187 // Replace 'n' with the new phi
1188 _igvn.replace_node(n, phi);
1189
1190 // Now split the bool up thru the phi
1191 Node *bolphi = split_thru_phi(bol, n_ctrl, -1);
1192 guarantee(bolphi != NULL, "null boolean phi node");
1193
1194 _igvn.replace_node(bol, bolphi);
1195 assert(iff->in(1) == bolphi, "");
1196
1197 if (bolphi->Value(&_igvn)->singleton()) {
1198 return;
1199 }
1200
1201 // Conditional-move? Must split up now
1202 if (!iff->is_If()) {
1203 Node *cmovphi = split_thru_phi(iff, n_ctrl, -1);
1204 _igvn.replace_node(iff, cmovphi);
1205 return;
1206 }
1207
1208 // Now split the IF
1209 do_split_if(iff);
1210 return;
1211 }
1212
1213 // Two identical ifs back to back can be merged
1214 if (identical_backtoback_ifs(n) && can_split_if(n->in(0))) {
1215 Node *n_ctrl = n->in(0);
1216 PhiNode* bolphi = PhiNode::make_blank(n_ctrl, n->in(1));
1217 IfNode* dom_if = idom(n_ctrl)->as_If();
1218 Node* proj_true = dom_if->proj_out(1);
1219 Node* proj_false = dom_if->proj_out(0);
1220 Node* con_true = _igvn.makecon(TypeInt::ONE);
1221 Node* con_false = _igvn.makecon(TypeInt::ZERO);
1222
1223 for (uint i = 1; i < n_ctrl->req(); i++) {
1224 if (is_dominator(proj_true, n_ctrl->in(i))) {
1225 bolphi->init_req(i, con_true);
1226 } else {
1227 assert(is_dominator(proj_false, n_ctrl->in(i)), "bad if");
1228 bolphi->init_req(i, con_false);
1229 }
1230 }
1231 register_new_node(bolphi, n_ctrl);
1232 _igvn.replace_input_of(n, 1, bolphi);
1233
1234 // Now split the IF
1235 do_split_if(n);
1236 return;
1237 }
1238
1239 // Check for an IF ready to split; one that has its
1240 // condition codes input coming from a Phi at the block start.
1241 int n_op = n->Opcode();
1242
1243 // Check for an IF being dominated by another IF same test
1244 if (n_op == Op_If ||
1245 n_op == Op_RangeCheck) {
1246 Node *bol = n->in(1);
1247 uint max = bol->outcnt();
1248 // Check for same test used more than once?
1249 if (max > 1 && bol->is_Bool()) {
1250 // Search up IDOMs to see if this IF is dominated.
1251 Node *cutoff = get_ctrl(bol);
1252
1253 // Now search up IDOMs till cutoff, looking for a dominating test
1254 Node *prevdom = n;
1255 Node *dom = idom(prevdom);
1256 while (dom != cutoff) {
1257 if (dom->req() > 1 && dom->in(1) == bol && prevdom->in(0) == dom) {
1258 // Replace the dominated test with an obvious true or false.
1259 // Place it on the IGVN worklist for later cleanup.
1260 C->set_major_progress();
1261 dominated_by(prevdom, n, false, true);
1262 #ifndef PRODUCT
1263 if( VerifyLoopOptimizations ) verify();
1264 #endif
1265 return;
1266 }
1267 prevdom = dom;
1268 dom = idom(prevdom);
1269 }
1270 }
1271 }
1272
1273 // See if a shared loop-varying computation has no loop-varying uses.
1274 // Happens if something is only used for JVM state in uncommon trap exits,
1275 // like various versions of induction variable+offset. Clone the
1276 // computation per usage to allow it to sink out of the loop.
1277 if (has_ctrl(n) && !n->in(0)) {// n not dead and has no control edge (can float about)
1278 Node *n_ctrl = get_ctrl(n);
1279 IdealLoopTree *n_loop = get_loop(n_ctrl);
1280 if( n_loop != _ltree_root ) {
1281 DUIterator_Fast imax, i = n->fast_outs(imax);
1282 for (; i < imax; i++) {
1283 Node* u = n->fast_out(i);
1284 if( !has_ctrl(u) ) break; // Found control user
1285 IdealLoopTree *u_loop = get_loop(get_ctrl(u));
1286 if( u_loop == n_loop ) break; // Found loop-varying use
1287 if( n_loop->is_member( u_loop ) ) break; // Found use in inner loop
1288 if( u->Opcode() == Op_Opaque1 ) break; // Found loop limit, bugfix for 4677003
1289 }
1290 bool did_break = (i < imax); // Did we break out of the previous loop?
1291 if (!did_break && n->outcnt() > 1) { // All uses in outer loops!
1292 Node *late_load_ctrl = NULL;
1293 if (n->is_Load()) {
1294 // If n is a load, get and save the result from get_late_ctrl(),
1295 // to be later used in calculating the control for n's clones.
1296 clear_dom_lca_tags();
1297 late_load_ctrl = get_late_ctrl(n, n_ctrl);
1298 }
1299 // If n is a load, and the late control is the same as the current
1300 // control, then the cloning of n is a pointless exercise, because
1301 // GVN will ensure that we end up where we started.
1302 if (!n->is_Load() || late_load_ctrl != n_ctrl) {
1303 for (DUIterator_Last jmin, j = n->last_outs(jmin); j >= jmin; ) {
1304 Node *u = n->last_out(j); // Clone private computation per use
1305 _igvn.rehash_node_delayed(u);
1306 Node *x = n->clone(); // Clone computation
1307 Node *x_ctrl = NULL;
1308 if( u->is_Phi() ) {
1309 // Replace all uses of normal nodes. Replace Phi uses
1310 // individually, so the separate Nodes can sink down
1311 // different paths.
1312 uint k = 1;
1313 while( u->in(k) != n ) k++;
1314 u->set_req( k, x );
1315 // x goes next to Phi input path
1316 x_ctrl = u->in(0)->in(k);
1317 --j;
1318 } else { // Normal use
1319 // Replace all uses
1320 for( uint k = 0; k < u->req(); k++ ) {
1321 if( u->in(k) == n ) {
1322 u->set_req( k, x );
1323 --j;
1324 }
1325 }
1326 x_ctrl = get_ctrl(u);
1327 }
1328
1329 // Find control for 'x' next to use but not inside inner loops.
1330 // For inner loop uses get the preheader area.
1331 x_ctrl = place_near_use(x_ctrl);
1332
1333 if (n->is_Load()) {
1334 // For loads, add a control edge to a CFG node outside of the loop
1335 // to force them to not combine and return back inside the loop
1336 // during GVN optimization (4641526).
1337 //
1338 // Because we are setting the actual control input, factor in
1339 // the result from get_late_ctrl() so we respect any
1340 // anti-dependences. (6233005).
1341 x_ctrl = dom_lca(late_load_ctrl, x_ctrl);
1342
1343 // Don't allow the control input to be a CFG splitting node.
1344 // Such nodes should only have ProjNodes as outs, e.g. IfNode
1345 // should only have IfTrueNode and IfFalseNode (4985384).
1346 x_ctrl = find_non_split_ctrl(x_ctrl);
1347 assert(dom_depth(n_ctrl) <= dom_depth(x_ctrl), "n is later than its clone");
1348
1349 x->set_req(0, x_ctrl);
1350 }
1351 register_new_node(x, x_ctrl);
1352
1353 // Some institutional knowledge is needed here: 'x' is
1354 // yanked because if the optimizer runs GVN on it all the
1355 // cloned x's will common up and undo this optimization and
1356 // be forced back in the loop. This is annoying because it
1357 // makes +VerifyOpto report false-positives on progress. I
1358 // tried setting control edges on the x's to force them to
1359 // not combine, but the matching gets worried when it tries
1360 // to fold a StoreP and an AddP together (as part of an
1361 // address expression) and the AddP and StoreP have
1362 // different controls.
1363 if (!x->is_Load() && !x->is_DecodeNarrowPtr()) _igvn._worklist.yank(x);
1364 }
1365 _igvn.remove_dead_node(n);
1366 }
1367 }
1368 }
1369 }
1370
1371 try_move_store_after_loop(n);
1372
1373 // Check for Opaque2's who's loop has disappeared - who's input is in the
1374 // same loop nest as their output. Remove 'em, they are no longer useful.
1375 if( n_op == Op_Opaque2 &&
1376 n->in(1) != NULL &&
1377 get_loop(get_ctrl(n)) == get_loop(get_ctrl(n->in(1))) ) {
1378 _igvn.replace_node( n, n->in(1) );
1379 }
1380 }
1381
1382 //------------------------------split_if_with_blocks---------------------------
1383 // Check for aggressive application of 'split-if' optimization,
1384 // using basic block level info.
1385 void PhaseIdealLoop::split_if_with_blocks( VectorSet &visited, Node_Stack &nstack ) {
1386 Node *n = C->root();
1387 visited.set(n->_idx); // first, mark node as visited
1388 // Do pre-visit work for root
1389 n = split_if_with_blocks_pre( n );
1390 uint cnt = n->outcnt();
1391 uint i = 0;
1392 while (true) {
1393 // Visit all children
1394 if (i < cnt) {
1395 Node* use = n->raw_out(i);
1396 ++i;
1397 if (use->outcnt() != 0 && !visited.test_set(use->_idx)) {
1398 // Now do pre-visit work for this use
1399 use = split_if_with_blocks_pre( use );
1400 nstack.push(n, i); // Save parent and next use's index.
1401 n = use; // Process all children of current use.
1402 cnt = use->outcnt();
1403 i = 0;
1404 }
1405 }
1406 else {
1407 // All of n's children have been processed, complete post-processing.
1408 if (cnt != 0 && !n->is_Con()) {
1409 assert(has_node(n), "no dead nodes");
1410 split_if_with_blocks_post( n );
1411 }
1412 if (nstack.is_empty()) {
1413 // Finished all nodes on stack.
1414 break;
1415 }
1416 // Get saved parent node and next use's index. Visit the rest of uses.
1417 n = nstack.node();
1418 cnt = n->outcnt();
1419 i = nstack.index();
1420 nstack.pop();
1421 }
1422 }
1423 }
1424
1425
1426 //=============================================================================
1427 //
1428 // C L O N E A L O O P B O D Y
1429 //
1430
1431 //------------------------------clone_iff--------------------------------------
1432 // Passed in a Phi merging (recursively) some nearly equivalent Bool/Cmps.
1433 // "Nearly" because all Nodes have been cloned from the original in the loop,
1434 // but the fall-in edges to the Cmp are different. Clone bool/Cmp pairs
1435 // through the Phi recursively, and return a Bool.
1436 BoolNode *PhaseIdealLoop::clone_iff( PhiNode *phi, IdealLoopTree *loop ) {
1437
1438 // Convert this Phi into a Phi merging Bools
1439 uint i;
1440 for( i = 1; i < phi->req(); i++ ) {
1441 Node *b = phi->in(i);
1442 if( b->is_Phi() ) {
1443 _igvn.replace_input_of(phi, i, clone_iff( b->as_Phi(), loop ));
1444 } else {
1445 assert( b->is_Bool(), "" );
1446 }
1447 }
1448
1449 Node *sample_bool = phi->in(1);
1450 Node *sample_cmp = sample_bool->in(1);
1451
1452 // Make Phis to merge the Cmp's inputs.
1453 PhiNode *phi1 = new PhiNode( phi->in(0), Type::TOP );
1454 PhiNode *phi2 = new PhiNode( phi->in(0), Type::TOP );
1455 for( i = 1; i < phi->req(); i++ ) {
1456 Node *n1 = phi->in(i)->in(1)->in(1);
1457 Node *n2 = phi->in(i)->in(1)->in(2);
1458 phi1->set_req( i, n1 );
1459 phi2->set_req( i, n2 );
1460 phi1->set_type( phi1->type()->meet_speculative(n1->bottom_type()));
1461 phi2->set_type( phi2->type()->meet_speculative(n2->bottom_type()));
1462 }
1463 // See if these Phis have been made before.
1464 // Register with optimizer
1465 Node *hit1 = _igvn.hash_find_insert(phi1);
1466 if( hit1 ) { // Hit, toss just made Phi
1467 _igvn.remove_dead_node(phi1); // Remove new phi
1468 assert( hit1->is_Phi(), "" );
1469 phi1 = (PhiNode*)hit1; // Use existing phi
1470 } else { // Miss
1471 _igvn.register_new_node_with_optimizer(phi1);
1472 }
1473 Node *hit2 = _igvn.hash_find_insert(phi2);
1474 if( hit2 ) { // Hit, toss just made Phi
1475 _igvn.remove_dead_node(phi2); // Remove new phi
1476 assert( hit2->is_Phi(), "" );
1477 phi2 = (PhiNode*)hit2; // Use existing phi
1478 } else { // Miss
1479 _igvn.register_new_node_with_optimizer(phi2);
1480 }
1481 // Register Phis with loop/block info
1482 set_ctrl(phi1, phi->in(0));
1483 set_ctrl(phi2, phi->in(0));
1484 // Make a new Cmp
1485 Node *cmp = sample_cmp->clone();
1486 cmp->set_req( 1, phi1 );
1487 cmp->set_req( 2, phi2 );
1488 _igvn.register_new_node_with_optimizer(cmp);
1489 set_ctrl(cmp, phi->in(0));
1490
1491 // Make a new Bool
1492 Node *b = sample_bool->clone();
1493 b->set_req(1,cmp);
1494 _igvn.register_new_node_with_optimizer(b);
1495 set_ctrl(b, phi->in(0));
1496
1497 assert( b->is_Bool(), "" );
1498 return (BoolNode*)b;
1499 }
1500
1501 //------------------------------clone_bool-------------------------------------
1502 // Passed in a Phi merging (recursively) some nearly equivalent Bool/Cmps.
1503 // "Nearly" because all Nodes have been cloned from the original in the loop,
1504 // but the fall-in edges to the Cmp are different. Clone bool/Cmp pairs
1505 // through the Phi recursively, and return a Bool.
1506 CmpNode *PhaseIdealLoop::clone_bool( PhiNode *phi, IdealLoopTree *loop ) {
1507 uint i;
1508 // Convert this Phi into a Phi merging Bools
1509 for( i = 1; i < phi->req(); i++ ) {
1510 Node *b = phi->in(i);
1511 if( b->is_Phi() ) {
1512 _igvn.replace_input_of(phi, i, clone_bool( b->as_Phi(), loop ));
1513 } else {
1514 assert( b->is_Cmp() || b->is_top(), "inputs are all Cmp or TOP" );
1515 }
1516 }
1517
1518 Node *sample_cmp = phi->in(1);
1519
1520 // Make Phis to merge the Cmp's inputs.
1521 PhiNode *phi1 = new PhiNode( phi->in(0), Type::TOP );
1522 PhiNode *phi2 = new PhiNode( phi->in(0), Type::TOP );
1523 for( uint j = 1; j < phi->req(); j++ ) {
1524 Node *cmp_top = phi->in(j); // Inputs are all Cmp or TOP
1525 Node *n1, *n2;
1526 if( cmp_top->is_Cmp() ) {
1527 n1 = cmp_top->in(1);
1528 n2 = cmp_top->in(2);
1529 } else {
1530 n1 = n2 = cmp_top;
1531 }
1532 phi1->set_req( j, n1 );
1533 phi2->set_req( j, n2 );
1534 phi1->set_type(phi1->type()->meet_speculative(n1->bottom_type()));
1535 phi2->set_type(phi2->type()->meet_speculative(n2->bottom_type()));
1536 }
1537
1538 // See if these Phis have been made before.
1539 // Register with optimizer
1540 Node *hit1 = _igvn.hash_find_insert(phi1);
1541 if( hit1 ) { // Hit, toss just made Phi
1542 _igvn.remove_dead_node(phi1); // Remove new phi
1543 assert( hit1->is_Phi(), "" );
1544 phi1 = (PhiNode*)hit1; // Use existing phi
1545 } else { // Miss
1546 _igvn.register_new_node_with_optimizer(phi1);
1547 }
1548 Node *hit2 = _igvn.hash_find_insert(phi2);
1549 if( hit2 ) { // Hit, toss just made Phi
1550 _igvn.remove_dead_node(phi2); // Remove new phi
1551 assert( hit2->is_Phi(), "" );
1552 phi2 = (PhiNode*)hit2; // Use existing phi
1553 } else { // Miss
1554 _igvn.register_new_node_with_optimizer(phi2);
1555 }
1556 // Register Phis with loop/block info
1557 set_ctrl(phi1, phi->in(0));
1558 set_ctrl(phi2, phi->in(0));
1559 // Make a new Cmp
1560 Node *cmp = sample_cmp->clone();
1561 cmp->set_req( 1, phi1 );
1562 cmp->set_req( 2, phi2 );
1563 _igvn.register_new_node_with_optimizer(cmp);
1564 set_ctrl(cmp, phi->in(0));
1565
1566 assert( cmp->is_Cmp(), "" );
1567 return (CmpNode*)cmp;
1568 }
1569
1570 //------------------------------sink_use---------------------------------------
1571 // If 'use' was in the loop-exit block, it now needs to be sunk
1572 // below the post-loop merge point.
1573 void PhaseIdealLoop::sink_use( Node *use, Node *post_loop ) {
1574 if (!use->is_CFG() && get_ctrl(use) == post_loop->in(2)) {
1575 set_ctrl(use, post_loop);
1576 for (DUIterator j = use->outs(); use->has_out(j); j++)
1577 sink_use(use->out(j), post_loop);
1578 }
1579 }
1580
1581 void PhaseIdealLoop::clone_loop_handle_data_uses(Node* old, Node_List &old_new,
1582 IdealLoopTree* loop, IdealLoopTree* outer_loop,
1583 Node_List*& split_if_set, Node_List*& split_bool_set,
1584 Node_List*& split_cex_set, Node_List& worklist,
1585 uint new_counter, CloneLoopMode mode) {
1586 Node* nnn = old_new[old->_idx];
1587 // Copy uses to a worklist, so I can munge the def-use info
1588 // with impunity.
1589 for (DUIterator_Fast jmax, j = old->fast_outs(jmax); j < jmax; j++)
1590 worklist.push(old->fast_out(j));
1591
1592 while( worklist.size() ) {
1593 Node *use = worklist.pop();
1594 if (!has_node(use)) continue; // Ignore dead nodes
1595 if (use->in(0) == C->top()) continue;
1596 IdealLoopTree *use_loop = get_loop( has_ctrl(use) ? get_ctrl(use) : use );
1597 // Check for data-use outside of loop - at least one of OLD or USE
1598 // must not be a CFG node.
1599 #ifdef ASSERT
1600 if (loop->_head->as_Loop()->is_strip_mined() && outer_loop->is_member(use_loop) && !loop->is_member(use_loop) && old_new[use->_idx] == NULL) {
1601 Node* cmp = loop->_head->as_CountedLoop()->outer_cmp();
1602 Node* sfpt = loop->_head->as_CountedLoop()->outer_safepoint();
1603 assert(mode == ControlAroundStripMined && (use == cmp || use == sfpt), "missed a node");
1604 }
1605 #endif
1606 if (!loop->is_member(use_loop) && !outer_loop->is_member(use_loop) && (!old->is_CFG() || !use->is_CFG())) {
1607
1608 // If the Data use is an IF, that means we have an IF outside of the
1609 // loop that is switching on a condition that is set inside of the
1610 // loop. Happens if people set a loop-exit flag; then test the flag
1611 // in the loop to break the loop, then test is again outside of the
1612 // loop to determine which way the loop exited.
1613 // Loop predicate If node connects to Bool node through Opaque1 node.
1614 if (use->is_If() || use->is_CMove() || C->is_predicate_opaq(use)) {
1615 // Since this code is highly unlikely, we lazily build the worklist
1616 // of such Nodes to go split.
1617 if (!split_if_set) {
1618 ResourceArea *area = Thread::current()->resource_area();
1619 split_if_set = new Node_List(area);
1620 }
1621 split_if_set->push(use);
1622 }
1623 if (use->is_Bool()) {
1624 if (!split_bool_set) {
1625 ResourceArea *area = Thread::current()->resource_area();
1626 split_bool_set = new Node_List(area);
1627 }
1628 split_bool_set->push(use);
1629 }
1630 if (use->Opcode() == Op_CreateEx) {
1631 if (!split_cex_set) {
1632 ResourceArea *area = Thread::current()->resource_area();
1633 split_cex_set = new Node_List(area);
1634 }
1635 split_cex_set->push(use);
1636 }
1637
1638
1639 // Get "block" use is in
1640 uint idx = 0;
1641 while( use->in(idx) != old ) idx++;
1642 Node *prev = use->is_CFG() ? use : get_ctrl(use);
1643 assert(!loop->is_member(get_loop(prev)) && !outer_loop->is_member(get_loop(prev)), "" );
1644 Node *cfg = prev->_idx >= new_counter
1645 ? prev->in(2)
1646 : idom(prev);
1647 if( use->is_Phi() ) // Phi use is in prior block
1648 cfg = prev->in(idx); // NOT in block of Phi itself
1649 if (cfg->is_top()) { // Use is dead?
1650 _igvn.replace_input_of(use, idx, C->top());
1651 continue;
1652 }
1653
1654 while(!outer_loop->is_member(get_loop(cfg))) {
1655 prev = cfg;
1656 cfg = cfg->_idx >= new_counter ? cfg->in(2) : idom(cfg);
1657 }
1658 // If the use occurs after merging several exits from the loop, then
1659 // old value must have dominated all those exits. Since the same old
1660 // value was used on all those exits we did not need a Phi at this
1661 // merge point. NOW we do need a Phi here. Each loop exit value
1662 // is now merged with the peeled body exit; each exit gets its own
1663 // private Phi and those Phis need to be merged here.
1664 Node *phi;
1665 if( prev->is_Region() ) {
1666 if( idx == 0 ) { // Updating control edge?
1667 phi = prev; // Just use existing control
1668 } else { // Else need a new Phi
1669 phi = PhiNode::make( prev, old );
1670 // Now recursively fix up the new uses of old!
1671 for( uint i = 1; i < prev->req(); i++ ) {
1672 worklist.push(phi); // Onto worklist once for each 'old' input
1673 }
1674 }
1675 } else {
1676 // Get new RegionNode merging old and new loop exits
1677 prev = old_new[prev->_idx];
1678 assert( prev, "just made this in step 7" );
1679 if( idx == 0) { // Updating control edge?
1680 phi = prev; // Just use existing control
1681 } else { // Else need a new Phi
1682 // Make a new Phi merging data values properly
1683 phi = PhiNode::make( prev, old );
1684 phi->set_req( 1, nnn );
1685 }
1686 }
1687 // If inserting a new Phi, check for prior hits
1688 if( idx != 0 ) {
1689 Node *hit = _igvn.hash_find_insert(phi);
1690 if( hit == NULL ) {
1691 _igvn.register_new_node_with_optimizer(phi); // Register new phi
1692 } else { // or
1693 // Remove the new phi from the graph and use the hit
1694 _igvn.remove_dead_node(phi);
1695 phi = hit; // Use existing phi
1696 }
1697 set_ctrl(phi, prev);
1698 }
1699 // Make 'use' use the Phi instead of the old loop body exit value
1700 _igvn.replace_input_of(use, idx, phi);
1701 if( use->_idx >= new_counter ) { // If updating new phis
1702 // Not needed for correctness, but prevents a weak assert
1703 // in AddPNode from tripping (when we end up with different
1704 // base & derived Phis that will become the same after
1705 // IGVN does CSE).
1706 Node *hit = _igvn.hash_find_insert(use);
1707 if( hit ) // Go ahead and re-hash for hits.
1708 _igvn.replace_node( use, hit );
1709 }
1710
1711 // If 'use' was in the loop-exit block, it now needs to be sunk
1712 // below the post-loop merge point.
1713 sink_use( use, prev );
1714 }
1715 }
1716 }
1717
1718 void PhaseIdealLoop::clone_outer_loop(LoopNode* head, CloneLoopMode mode, IdealLoopTree *loop,
1719 IdealLoopTree* outer_loop, int dd, Node_List &old_new,
1720 Node_List& extra_data_nodes) {
1721 if (head->is_strip_mined() && mode != IgnoreStripMined) {
1722 CountedLoopNode* cl = head->as_CountedLoop();
1723 Node* l = cl->outer_loop();
1724 Node* tail = cl->outer_loop_tail();
1725 IfNode* le = cl->outer_loop_end();
1726 Node* sfpt = cl->outer_safepoint();
1727 Node* bol = cl->outer_bol();
1728 Node* cmp = cl->outer_cmp();
1729 Node* opaq = cl->outer_opaq();
1730 CountedLoopEndNode* cle = cl->loopexit();
1731 CountedLoopNode* new_cl = old_new[cl->_idx]->as_CountedLoop();
1732 CountedLoopEndNode* new_cle = new_cl->as_CountedLoop()->loopexit();
1733 Node* cle_out = cle->proj_out(false);
1734
1735 Node* new_sfpt = NULL;
1736 Node* new_cle_out = cle_out->clone();
1737 old_new.map(cle_out->_idx, new_cle_out);
1738 if (mode == CloneIncludesStripMined) {
1739 // clone outer loop body
1740 Node* new_l = l->clone();
1741 Node* new_tail = tail->clone();
1742 IfNode* new_le = le->clone()->as_If();
1743 new_sfpt = sfpt->clone();
1744 Node* new_bol = bol->clone();
1745 Node* new_cmp = cmp->clone();
1746 Node* new_opaq = opaq->clone();
1747
1748 set_loop(new_l, outer_loop->_parent);
1749 set_idom(new_l, new_l->in(LoopNode::EntryControl), dd);
1750 set_loop(new_cle_out, outer_loop->_parent);
1751 set_idom(new_cle_out, new_cle, dd);
1752 set_loop(new_sfpt, outer_loop->_parent);
1753 set_idom(new_sfpt, new_cle_out, dd);
1754 set_loop(new_le, outer_loop->_parent);
1755 set_idom(new_le, new_sfpt, dd);
1756 set_loop(new_tail, outer_loop->_parent);
1757 set_idom(new_tail, new_le, dd);
1758 set_ctrl(new_bol, new_sfpt);
1759 set_ctrl(new_cmp, new_sfpt);
1760 set_ctrl(new_cmp, new_sfpt);
1761 set_idom(new_cl, new_l, dd);
1762
1763 old_new.map(l->_idx, new_l);
1764 old_new.map(tail->_idx, new_tail);
1765 old_new.map(le->_idx, new_le);
1766 old_new.map(sfpt->_idx, new_sfpt);
1767 old_new.map(bol->_idx, new_bol);
1768 old_new.map(cmp->_idx, new_cmp);
1769 old_new.map(opaq->_idx, new_opaq);
1770
1771 new_l->set_req(LoopNode::LoopBackControl, new_tail);
1772 new_l->set_req(0, new_l);
1773 new_tail->set_req(0, new_le);
1774 new_le->set_req(0, new_sfpt);
1775 new_sfpt->set_req(0, new_cle_out);
1776 new_le->set_req(1, new_bol);
1777 new_bol->set_req(1, new_cmp);
1778 new_cmp->set_req(2, new_opaq);
1779 new_cmp->set_req(1, new_cle->incr());
1780 new_cle_out->set_req(0, new_cle);
1781 new_cl->set_req(LoopNode::EntryControl, new_l);
1782 new_opaq->set_req(0, new_sfpt);
1783
1784 _igvn.register_new_node_with_optimizer(new_l);
1785 _igvn.register_new_node_with_optimizer(new_tail);
1786 _igvn.register_new_node_with_optimizer(new_le);
1787 _igvn.register_new_node_with_optimizer(new_bol);
1788 _igvn.register_new_node_with_optimizer(new_cmp);
1789 _igvn.register_new_node_with_optimizer(new_opaq);
1790 } else {
1791 Node *newhead = old_new[loop->_head->_idx];
1792 newhead->as_Loop()->clear_strip_mined();
1793 _igvn.replace_input_of(newhead, LoopNode::EntryControl, newhead->in(LoopNode::EntryControl)->in(LoopNode::EntryControl));
1794 set_idom(newhead, newhead->in(LoopNode::EntryControl), dd);
1795 }
1796 // Look at data node that were assigned a control in the outer
1797 // loop: they are kept in the outer loop by the safepoint so start
1798 // from the safepoint node's inputs.
1799 IdealLoopTree* outer_loop = get_loop(l);
1800 Node_Stack stack(2);
1801 stack.push(sfpt, 1);
1802 uint new_counter = C->unique();
1803 while (stack.size() > 0) {
1804 Node* n = stack.node();
1805 uint i = stack.index();
1806 while (i < n->req() &&
1807 (n->in(i) == NULL ||
1808 !has_ctrl(n->in(i)) ||
1809 get_loop(get_ctrl(n->in(i))) != outer_loop ||
1810 (old_new[n->in(i)->_idx] != NULL && old_new[n->in(i)->_idx]->_idx >= new_counter))) {
1811 i++;
1812 }
1813 if (i < n->req()) {
1814 stack.set_index(i+1);
1815 stack.push(n->in(i), 0);
1816 } else {
1817 assert(old_new[n->_idx] == NULL || n == sfpt || old_new[n->_idx]->_idx < new_counter, "no clone yet");
1818 Node* m = n == sfpt ? new_sfpt : n->clone();
1819 if (m != NULL) {
1820 for (uint i = 0; i < n->req(); i++) {
1821 if (m->in(i) != NULL && old_new[m->in(i)->_idx] != NULL) {
1822 m->set_req(i, old_new[m->in(i)->_idx]);
1823 }
1824 }
1825 } else {
1826 assert(n == sfpt && mode != CloneIncludesStripMined, "where's the safepoint clone?");
1827 }
1828 if (n != sfpt) {
1829 extra_data_nodes.push(n);
1830 _igvn.register_new_node_with_optimizer(m);
1831 assert(get_ctrl(n) == cle_out, "what other control?");
1832 set_ctrl(m, new_cle_out);
1833 old_new.map(n->_idx, m);
1834 }
1835 stack.pop();
1836 }
1837 }
1838 if (mode == CloneIncludesStripMined) {
1839 _igvn.register_new_node_with_optimizer(new_sfpt);
1840 _igvn.register_new_node_with_optimizer(new_cle_out);
1841 }
1842 } else {
1843 Node *newhead = old_new[loop->_head->_idx];
1844 set_idom(newhead, newhead->in(LoopNode::EntryControl), dd);
1845 }
1846 }
1847
1848 //------------------------------clone_loop-------------------------------------
1849 //
1850 // C L O N E A L O O P B O D Y
1851 //
1852 // This is the basic building block of the loop optimizations. It clones an
1853 // entire loop body. It makes an old_new loop body mapping; with this mapping
1854 // you can find the new-loop equivalent to an old-loop node. All new-loop
1855 // nodes are exactly equal to their old-loop counterparts, all edges are the
1856 // same. All exits from the old-loop now have a RegionNode that merges the
1857 // equivalent new-loop path. This is true even for the normal "loop-exit"
1858 // condition. All uses of loop-invariant old-loop values now come from (one
1859 // or more) Phis that merge their new-loop equivalents.
1860 //
1861 // This operation leaves the graph in an illegal state: there are two valid
1862 // control edges coming from the loop pre-header to both loop bodies. I'll
1863 // definitely have to hack the graph after running this transform.
1864 //
1865 // From this building block I will further edit edges to perform loop peeling
1866 // or loop unrolling or iteration splitting (Range-Check-Elimination), etc.
1867 //
1868 // Parameter side_by_size_idom:
1869 // When side_by_size_idom is NULL, the dominator tree is constructed for
1870 // the clone loop to dominate the original. Used in construction of
1871 // pre-main-post loop sequence.
1872 // When nonnull, the clone and original are side-by-side, both are
1873 // dominated by the side_by_side_idom node. Used in construction of
1874 // unswitched loops.
1875 void PhaseIdealLoop::clone_loop( IdealLoopTree *loop, Node_List &old_new, int dd,
1876 CloneLoopMode mode, Node* side_by_side_idom) {
1877
1878 LoopNode* head = loop->_head->as_Loop();
1879 head->verify_strip_mined(1);
1880
1881 if (C->do_vector_loop() && PrintOpto) {
1882 const char* mname = C->method()->name()->as_quoted_ascii();
1883 if (mname != NULL) {
1884 tty->print("PhaseIdealLoop::clone_loop: for vectorize method %s\n", mname);
1885 }
1886 }
1887
1888 CloneMap& cm = C->clone_map();
1889 Dict* dict = cm.dict();
1890 if (C->do_vector_loop()) {
1891 cm.set_clone_idx(cm.max_gen()+1);
1892 #ifndef PRODUCT
1893 if (PrintOpto) {
1894 tty->print_cr("PhaseIdealLoop::clone_loop: _clone_idx %d", cm.clone_idx());
1895 loop->dump_head();
1896 }
1897 #endif
1898 }
1899
1900 // Step 1: Clone the loop body. Make the old->new mapping.
1901 uint i;
1902 for( i = 0; i < loop->_body.size(); i++ ) {
1903 Node *old = loop->_body.at(i);
1904 Node *nnn = old->clone();
1905 old_new.map( old->_idx, nnn );
1906 if (C->do_vector_loop()) {
1907 cm.verify_insert_and_clone(old, nnn, cm.clone_idx());
1908 }
1909 _igvn.register_new_node_with_optimizer(nnn);
1910 }
1911
1912 IdealLoopTree* outer_loop = (head->is_strip_mined() && mode != IgnoreStripMined) ? get_loop(head->as_CountedLoop()->outer_loop()) : loop;
1913
1914 // Step 2: Fix the edges in the new body. If the old input is outside the
1915 // loop use it. If the old input is INside the loop, use the corresponding
1916 // new node instead.
1917 for( i = 0; i < loop->_body.size(); i++ ) {
1918 Node *old = loop->_body.at(i);
1919 Node *nnn = old_new[old->_idx];
1920 // Fix CFG/Loop controlling the new node
1921 if (has_ctrl(old)) {
1922 set_ctrl(nnn, old_new[get_ctrl(old)->_idx]);
1923 } else {
1924 set_loop(nnn, outer_loop->_parent);
1925 if (old->outcnt() > 0) {
1926 set_idom( nnn, old_new[idom(old)->_idx], dd );
1927 }
1928 }
1929 // Correct edges to the new node
1930 for( uint j = 0; j < nnn->req(); j++ ) {
1931 Node *n = nnn->in(j);
1932 if( n ) {
1933 IdealLoopTree *old_in_loop = get_loop( has_ctrl(n) ? get_ctrl(n) : n );
1934 if( loop->is_member( old_in_loop ) )
1935 nnn->set_req(j, old_new[n->_idx]);
1936 }
1937 }
1938 _igvn.hash_find_insert(nnn);
1939 }
1940
1941 ResourceArea *area = Thread::current()->resource_area();
1942 Node_List extra_data_nodes(area);
1943 clone_outer_loop(head, mode, loop, outer_loop, dd, old_new, extra_data_nodes);
1944
1945 // Step 3: Now fix control uses. Loop varying control uses have already
1946 // been fixed up (as part of all input edges in Step 2). Loop invariant
1947 // control uses must be either an IfFalse or an IfTrue. Make a merge
1948 // point to merge the old and new IfFalse/IfTrue nodes; make the use
1949 // refer to this.
1950 Node_List worklist(area);
1951 uint new_counter = C->unique();
1952 for( i = 0; i < loop->_body.size(); i++ ) {
1953 Node* old = loop->_body.at(i);
1954 if( !old->is_CFG() ) continue;
1955
1956 // Copy uses to a worklist, so I can munge the def-use info
1957 // with impunity.
1958 for (DUIterator_Fast jmax, j = old->fast_outs(jmax); j < jmax; j++)
1959 worklist.push(old->fast_out(j));
1960
1961 while( worklist.size() ) { // Visit all uses
1962 Node *use = worklist.pop();
1963 if (!has_node(use)) continue; // Ignore dead nodes
1964 IdealLoopTree *use_loop = get_loop( has_ctrl(use) ? get_ctrl(use) : use );
1965 if( !loop->is_member( use_loop ) && use->is_CFG() ) {
1966 // Both OLD and USE are CFG nodes here.
1967 assert( use->is_Proj(), "" );
1968 Node* nnn = old_new[old->_idx];
1969
1970 Node* newuse = NULL;
1971 if (head->is_strip_mined() && mode != IgnoreStripMined) {
1972 CountedLoopNode* cl = head->as_CountedLoop();
1973 CountedLoopEndNode* cle = cl->loopexit();
1974 Node* cle_out = cle->proj_out(false);
1975 if (use == cle_out) {
1976 IfNode* le = cl->outer_loop_end();
1977 use = le->proj_out(false);
1978 use_loop = get_loop(use);
1979 if (mode == CloneIncludesStripMined) {
1980 nnn = old_new[le->_idx];
1981 } else {
1982 newuse = old_new[cle_out->_idx];
1983 }
1984 }
1985 }
1986 if (newuse == NULL) {
1987 newuse = use->clone();
1988 }
1989
1990 // Clone the loop exit control projection
1991 if (C->do_vector_loop()) {
1992 cm.verify_insert_and_clone(use, newuse, cm.clone_idx());
1993 }
1994 newuse->set_req(0,nnn);
1995 _igvn.register_new_node_with_optimizer(newuse);
1996 set_loop(newuse, use_loop);
1997 set_idom(newuse, nnn, dom_depth(nnn) + 1 );
1998
1999 // We need a Region to merge the exit from the peeled body and the
2000 // exit from the old loop body.
2001 RegionNode *r = new RegionNode(3);
2002 // Map the old use to the new merge point
2003 old_new.map( use->_idx, r );
2004 uint dd_r = MIN2(dom_depth(newuse),dom_depth(use));
2005 assert( dd_r >= dom_depth(dom_lca(newuse,use)), "" );
2006
2007 // The original user of 'use' uses 'r' instead.
2008 for (DUIterator_Last lmin, l = use->last_outs(lmin); l >= lmin;) {
2009 Node* useuse = use->last_out(l);
2010 _igvn.rehash_node_delayed(useuse);
2011 uint uses_found = 0;
2012 if( useuse->in(0) == use ) {
2013 useuse->set_req(0, r);
2014 uses_found++;
2015 if( useuse->is_CFG() ) {
2016 assert( dom_depth(useuse) > dd_r, "" );
2017 set_idom(useuse, r, dom_depth(useuse));
2018 }
2019 }
2020 for( uint k = 1; k < useuse->req(); k++ ) {
2021 if( useuse->in(k) == use ) {
2022 useuse->set_req(k, r);
2023 uses_found++;
2024 if (useuse->is_Loop() && k == LoopNode::EntryControl) {
2025 assert(dom_depth(useuse) > dd_r , "");
2026 set_idom(useuse, r, dom_depth(useuse));
2027 }
2028 }
2029 }
2030 l -= uses_found; // we deleted 1 or more copies of this edge
2031 }
2032
2033 // Now finish up 'r'
2034 r->set_req( 1, newuse );
2035 r->set_req( 2, use );
2036 _igvn.register_new_node_with_optimizer(r);
2037 set_loop(r, use_loop);
2038 set_idom(r, !side_by_side_idom ? newuse->in(0) : side_by_side_idom, dd_r);
2039 } // End of if a loop-exit test
2040 }
2041 }
2042
2043 // Step 4: If loop-invariant use is not control, it must be dominated by a
2044 // loop exit IfFalse/IfTrue. Find "proper" loop exit. Make a Region
2045 // there if needed. Make a Phi there merging old and new used values.
2046 Node_List *split_if_set = NULL;
2047 Node_List *split_bool_set = NULL;
2048 Node_List *split_cex_set = NULL;
2049 for( i = 0; i < loop->_body.size(); i++ ) {
2050 Node* old = loop->_body.at(i);
2051 clone_loop_handle_data_uses(old, old_new, loop, outer_loop, split_if_set,
2052 split_bool_set, split_cex_set, worklist, new_counter,
2053 mode);
2054 }
2055
2056 for (i = 0; i < extra_data_nodes.size(); i++) {
2057 Node* old = extra_data_nodes.at(i);
2058 clone_loop_handle_data_uses(old, old_new, loop, outer_loop, split_if_set,
2059 split_bool_set, split_cex_set, worklist, new_counter,
2060 mode);
2061 }
2062
2063 // Check for IFs that need splitting/cloning. Happens if an IF outside of
2064 // the loop uses a condition set in the loop. The original IF probably
2065 // takes control from one or more OLD Regions (which in turn get from NEW
2066 // Regions). In any case, there will be a set of Phis for each merge point
2067 // from the IF up to where the original BOOL def exists the loop.
2068 if( split_if_set ) {
2069 while( split_if_set->size() ) {
2070 Node *iff = split_if_set->pop();
2071 if( iff->in(1)->is_Phi() ) {
2072 BoolNode *b = clone_iff( iff->in(1)->as_Phi(), loop );
2073 _igvn.replace_input_of(iff, 1, b);
2074 }
2075 }
2076 }
2077 if( split_bool_set ) {
2078 while( split_bool_set->size() ) {
2079 Node *b = split_bool_set->pop();
2080 Node *phi = b->in(1);
2081 assert( phi->is_Phi(), "" );
2082 CmpNode *cmp = clone_bool( (PhiNode*)phi, loop );
2083 _igvn.replace_input_of(b, 1, cmp);
2084 }
2085 }
2086 if( split_cex_set ) {
2087 while( split_cex_set->size() ) {
2088 Node *b = split_cex_set->pop();
2089 assert( b->in(0)->is_Region(), "" );
2090 assert( b->in(1)->is_Phi(), "" );
2091 assert( b->in(0)->in(0) == b->in(1)->in(0), "" );
2092 split_up( b, b->in(0), NULL );
2093 }
2094 }
2095
2096 }
2097
2098
2099 //---------------------- stride_of_possible_iv -------------------------------------
2100 // Looks for an iff/bool/comp with one operand of the compare
2101 // being a cycle involving an add and a phi,
2102 // with an optional truncation (left-shift followed by a right-shift)
2103 // of the add. Returns zero if not an iv.
2104 int PhaseIdealLoop::stride_of_possible_iv(Node* iff) {
2105 Node* trunc1 = NULL;
2106 Node* trunc2 = NULL;
2107 const TypeInt* ttype = NULL;
2108 if (!iff->is_If() || iff->in(1) == NULL || !iff->in(1)->is_Bool()) {
2109 return 0;
2110 }
2111 BoolNode* bl = iff->in(1)->as_Bool();
2112 Node* cmp = bl->in(1);
2113 if (!cmp || (cmp->Opcode() != Op_CmpI && cmp->Opcode() != Op_CmpU)) {
2114 return 0;
2115 }
2116 // Must have an invariant operand
2117 if (is_member(get_loop(iff), get_ctrl(cmp->in(2)))) {
2118 return 0;
2119 }
2120 Node* add2 = NULL;
2121 Node* cmp1 = cmp->in(1);
2122 if (cmp1->is_Phi()) {
2123 // (If (Bool (CmpX phi:(Phi ...(Optional-trunc(AddI phi add2))) )))
2124 Node* phi = cmp1;
2125 for (uint i = 1; i < phi->req(); i++) {
2126 Node* in = phi->in(i);
2127 Node* add = CountedLoopNode::match_incr_with_optional_truncation(in,
2128 &trunc1, &trunc2, &ttype);
2129 if (add && add->in(1) == phi) {
2130 add2 = add->in(2);
2131 break;
2132 }
2133 }
2134 } else {
2135 // (If (Bool (CmpX addtrunc:(Optional-trunc((AddI (Phi ...addtrunc...) add2)) )))
2136 Node* addtrunc = cmp1;
2137 Node* add = CountedLoopNode::match_incr_with_optional_truncation(addtrunc,
2138 &trunc1, &trunc2, &ttype);
2139 if (add && add->in(1)->is_Phi()) {
2140 Node* phi = add->in(1);
2141 for (uint i = 1; i < phi->req(); i++) {
2142 if (phi->in(i) == addtrunc) {
2143 add2 = add->in(2);
2144 break;
2145 }
2146 }
2147 }
2148 }
2149 if (add2 != NULL) {
2150 const TypeInt* add2t = _igvn.type(add2)->is_int();
2151 if (add2t->is_con()) {
2152 return add2t->get_con();
2153 }
2154 }
2155 return 0;
2156 }
2157
2158
2159 //---------------------- stay_in_loop -------------------------------------
2160 // Return the (unique) control output node that's in the loop (if it exists.)
2161 Node* PhaseIdealLoop::stay_in_loop( Node* n, IdealLoopTree *loop) {
2162 Node* unique = NULL;
2163 if (!n) return NULL;
2164 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2165 Node* use = n->fast_out(i);
2166 if (!has_ctrl(use) && loop->is_member(get_loop(use))) {
2167 if (unique != NULL) {
2168 return NULL;
2169 }
2170 unique = use;
2171 }
2172 }
2173 return unique;
2174 }
2175
2176 //------------------------------ register_node -------------------------------------
2177 // Utility to register node "n" with PhaseIdealLoop
2178 void PhaseIdealLoop::register_node(Node* n, IdealLoopTree *loop, Node* pred, int ddepth) {
2179 _igvn.register_new_node_with_optimizer(n);
2180 loop->_body.push(n);
2181 if (n->is_CFG()) {
2182 set_loop(n, loop);
2183 set_idom(n, pred, ddepth);
2184 } else {
2185 set_ctrl(n, pred);
2186 }
2187 }
2188
2189 //------------------------------ proj_clone -------------------------------------
2190 // Utility to create an if-projection
2191 ProjNode* PhaseIdealLoop::proj_clone(ProjNode* p, IfNode* iff) {
2192 ProjNode* c = p->clone()->as_Proj();
2193 c->set_req(0, iff);
2194 return c;
2195 }
2196
2197 //------------------------------ short_circuit_if -------------------------------------
2198 // Force the iff control output to be the live_proj
2199 Node* PhaseIdealLoop::short_circuit_if(IfNode* iff, ProjNode* live_proj) {
2200 guarantee(live_proj != NULL, "null projection");
2201 int proj_con = live_proj->_con;
2202 assert(proj_con == 0 || proj_con == 1, "false or true projection");
2203 Node *con = _igvn.intcon(proj_con);
2204 set_ctrl(con, C->root());
2205 if (iff) {
2206 iff->set_req(1, con);
2207 }
2208 return con;
2209 }
2210
2211 //------------------------------ insert_if_before_proj -------------------------------------
2212 // Insert a new if before an if projection (* - new node)
2213 //
2214 // before
2215 // if(test)
2216 // / \
2217 // v v
2218 // other-proj proj (arg)
2219 //
2220 // after
2221 // if(test)
2222 // / \
2223 // / v
2224 // | * proj-clone
2225 // v |
2226 // other-proj v
2227 // * new_if(relop(cmp[IU](left,right)))
2228 // / \
2229 // v v
2230 // * new-proj proj
2231 // (returned)
2232 //
2233 ProjNode* PhaseIdealLoop::insert_if_before_proj(Node* left, bool Signed, BoolTest::mask relop, Node* right, ProjNode* proj) {
2234 IfNode* iff = proj->in(0)->as_If();
2235 IdealLoopTree *loop = get_loop(proj);
2236 ProjNode *other_proj = iff->proj_out(!proj->is_IfTrue())->as_Proj();
2237 int ddepth = dom_depth(proj);
2238
2239 _igvn.rehash_node_delayed(iff);
2240 _igvn.rehash_node_delayed(proj);
2241
2242 proj->set_req(0, NULL); // temporary disconnect
2243 ProjNode* proj2 = proj_clone(proj, iff);
2244 register_node(proj2, loop, iff, ddepth);
2245
2246 Node* cmp = Signed ? (Node*) new CmpINode(left, right) : (Node*) new CmpUNode(left, right);
2247 register_node(cmp, loop, proj2, ddepth);
2248
2249 BoolNode* bol = new BoolNode(cmp, relop);
2250 register_node(bol, loop, proj2, ddepth);
2251
2252 int opcode = iff->Opcode();
2253 assert(opcode == Op_If || opcode == Op_RangeCheck, "unexpected opcode");
2254 IfNode* new_if = (opcode == Op_If) ? new IfNode(proj2, bol, iff->_prob, iff->_fcnt):
2255 new RangeCheckNode(proj2, bol, iff->_prob, iff->_fcnt);
2256 register_node(new_if, loop, proj2, ddepth);
2257
2258 proj->set_req(0, new_if); // reattach
2259 set_idom(proj, new_if, ddepth);
2260
2261 ProjNode* new_exit = proj_clone(other_proj, new_if)->as_Proj();
2262 guarantee(new_exit != NULL, "null exit node");
2263 register_node(new_exit, get_loop(other_proj), new_if, ddepth);
2264
2265 return new_exit;
2266 }
2267
2268 //------------------------------ insert_region_before_proj -------------------------------------
2269 // Insert a region before an if projection (* - new node)
2270 //
2271 // before
2272 // if(test)
2273 // / |
2274 // v |
2275 // proj v
2276 // other-proj
2277 //
2278 // after
2279 // if(test)
2280 // / |
2281 // v |
2282 // * proj-clone v
2283 // | other-proj
2284 // v
2285 // * new-region
2286 // |
2287 // v
2288 // * dum_if
2289 // / \
2290 // v \
2291 // * dum-proj v
2292 // proj
2293 //
2294 RegionNode* PhaseIdealLoop::insert_region_before_proj(ProjNode* proj) {
2295 IfNode* iff = proj->in(0)->as_If();
2296 IdealLoopTree *loop = get_loop(proj);
2297 ProjNode *other_proj = iff->proj_out(!proj->is_IfTrue())->as_Proj();
2298 int ddepth = dom_depth(proj);
2299
2300 _igvn.rehash_node_delayed(iff);
2301 _igvn.rehash_node_delayed(proj);
2302
2303 proj->set_req(0, NULL); // temporary disconnect
2304 ProjNode* proj2 = proj_clone(proj, iff);
2305 register_node(proj2, loop, iff, ddepth);
2306
2307 RegionNode* reg = new RegionNode(2);
2308 reg->set_req(1, proj2);
2309 register_node(reg, loop, iff, ddepth);
2310
2311 IfNode* dum_if = new IfNode(reg, short_circuit_if(NULL, proj), iff->_prob, iff->_fcnt);
2312 register_node(dum_if, loop, reg, ddepth);
2313
2314 proj->set_req(0, dum_if); // reattach
2315 set_idom(proj, dum_if, ddepth);
2316
2317 ProjNode* dum_proj = proj_clone(other_proj, dum_if);
2318 register_node(dum_proj, loop, dum_if, ddepth);
2319
2320 return reg;
2321 }
2322
2323 //------------------------------ insert_cmpi_loop_exit -------------------------------------
2324 // Clone a signed compare loop exit from an unsigned compare and
2325 // insert it before the unsigned cmp on the stay-in-loop path.
2326 // All new nodes inserted in the dominator tree between the original
2327 // if and it's projections. The original if test is replaced with
2328 // a constant to force the stay-in-loop path.
2329 //
2330 // This is done to make sure that the original if and it's projections
2331 // still dominate the same set of control nodes, that the ctrl() relation
2332 // from data nodes to them is preserved, and that their loop nesting is
2333 // preserved.
2334 //
2335 // before
2336 // if(i <u limit) unsigned compare loop exit
2337 // / |
2338 // v v
2339 // exit-proj stay-in-loop-proj
2340 //
2341 // after
2342 // if(stay-in-loop-const) original if
2343 // / |
2344 // / v
2345 // / if(i < limit) new signed test
2346 // / / |
2347 // / / v
2348 // / / if(i <u limit) new cloned unsigned test
2349 // / / / |
2350 // v v v |
2351 // region |
2352 // | |
2353 // dum-if |
2354 // / | |
2355 // ether | |
2356 // v v
2357 // exit-proj stay-in-loop-proj
2358 //
2359 IfNode* PhaseIdealLoop::insert_cmpi_loop_exit(IfNode* if_cmpu, IdealLoopTree *loop) {
2360 const bool Signed = true;
2361 const bool Unsigned = false;
2362
2363 BoolNode* bol = if_cmpu->in(1)->as_Bool();
2364 if (bol->_test._test != BoolTest::lt) return NULL;
2365 CmpNode* cmpu = bol->in(1)->as_Cmp();
2366 if (cmpu->Opcode() != Op_CmpU) return NULL;
2367 int stride = stride_of_possible_iv(if_cmpu);
2368 if (stride == 0) return NULL;
2369
2370 Node* lp_proj = stay_in_loop(if_cmpu, loop);
2371 guarantee(lp_proj != NULL, "null loop node");
2372
2373 ProjNode* lp_continue = lp_proj->as_Proj();
2374 ProjNode* lp_exit = if_cmpu->proj_out(!lp_continue->is_IfTrue())->as_Proj();
2375
2376 Node* limit = NULL;
2377 if (stride > 0) {
2378 limit = cmpu->in(2);
2379 } else {
2380 limit = _igvn.makecon(TypeInt::ZERO);
2381 set_ctrl(limit, C->root());
2382 }
2383 // Create a new region on the exit path
2384 RegionNode* reg = insert_region_before_proj(lp_exit);
2385 guarantee(reg != NULL, "null region node");
2386
2387 // Clone the if-cmpu-true-false using a signed compare
2388 BoolTest::mask rel_i = stride > 0 ? bol->_test._test : BoolTest::ge;
2389 ProjNode* cmpi_exit = insert_if_before_proj(cmpu->in(1), Signed, rel_i, limit, lp_continue);
2390 reg->add_req(cmpi_exit);
2391
2392 // Clone the if-cmpu-true-false
2393 BoolTest::mask rel_u = bol->_test._test;
2394 ProjNode* cmpu_exit = insert_if_before_proj(cmpu->in(1), Unsigned, rel_u, cmpu->in(2), lp_continue);
2395 reg->add_req(cmpu_exit);
2396
2397 // Force original if to stay in loop.
2398 short_circuit_if(if_cmpu, lp_continue);
2399
2400 return cmpi_exit->in(0)->as_If();
2401 }
2402
2403 //------------------------------ remove_cmpi_loop_exit -------------------------------------
2404 // Remove a previously inserted signed compare loop exit.
2405 void PhaseIdealLoop::remove_cmpi_loop_exit(IfNode* if_cmp, IdealLoopTree *loop) {
2406 Node* lp_proj = stay_in_loop(if_cmp, loop);
2407 assert(if_cmp->in(1)->in(1)->Opcode() == Op_CmpI &&
2408 stay_in_loop(lp_proj, loop)->is_If() &&
2409 stay_in_loop(lp_proj, loop)->in(1)->in(1)->Opcode() == Op_CmpU, "inserted cmpi before cmpu");
2410 Node *con = _igvn.makecon(lp_proj->is_IfTrue() ? TypeInt::ONE : TypeInt::ZERO);
2411 set_ctrl(con, C->root());
2412 if_cmp->set_req(1, con);
2413 }
2414
2415 //------------------------------ scheduled_nodelist -------------------------------------
2416 // Create a post order schedule of nodes that are in the
2417 // "member" set. The list is returned in "sched".
2418 // The first node in "sched" is the loop head, followed by
2419 // nodes which have no inputs in the "member" set, and then
2420 // followed by the nodes that have an immediate input dependence
2421 // on a node in "sched".
2422 void PhaseIdealLoop::scheduled_nodelist( IdealLoopTree *loop, VectorSet& member, Node_List &sched ) {
2423
2424 assert(member.test(loop->_head->_idx), "loop head must be in member set");
2425 Arena *a = Thread::current()->resource_area();
2426 VectorSet visited(a);
2427 Node_Stack nstack(a, loop->_body.size());
2428
2429 Node* n = loop->_head; // top of stack is cached in "n"
2430 uint idx = 0;
2431 visited.set(n->_idx);
2432
2433 // Initially push all with no inputs from within member set
2434 for(uint i = 0; i < loop->_body.size(); i++ ) {
2435 Node *elt = loop->_body.at(i);
2436 if (member.test(elt->_idx)) {
2437 bool found = false;
2438 for (uint j = 0; j < elt->req(); j++) {
2439 Node* def = elt->in(j);
2440 if (def && member.test(def->_idx) && def != elt) {
2441 found = true;
2442 break;
2443 }
2444 }
2445 if (!found && elt != loop->_head) {
2446 nstack.push(n, idx);
2447 n = elt;
2448 assert(!visited.test(n->_idx), "not seen yet");
2449 visited.set(n->_idx);
2450 }
2451 }
2452 }
2453
2454 // traverse out's that are in the member set
2455 while (true) {
2456 if (idx < n->outcnt()) {
2457 Node* use = n->raw_out(idx);
2458 idx++;
2459 if (!visited.test_set(use->_idx)) {
2460 if (member.test(use->_idx)) {
2461 nstack.push(n, idx);
2462 n = use;
2463 idx = 0;
2464 }
2465 }
2466 } else {
2467 // All outputs processed
2468 sched.push(n);
2469 if (nstack.is_empty()) break;
2470 n = nstack.node();
2471 idx = nstack.index();
2472 nstack.pop();
2473 }
2474 }
2475 }
2476
2477
2478 //------------------------------ has_use_in_set -------------------------------------
2479 // Has a use in the vector set
2480 bool PhaseIdealLoop::has_use_in_set( Node* n, VectorSet& vset ) {
2481 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
2482 Node* use = n->fast_out(j);
2483 if (vset.test(use->_idx)) {
2484 return true;
2485 }
2486 }
2487 return false;
2488 }
2489
2490
2491 //------------------------------ has_use_internal_to_set -------------------------------------
2492 // Has use internal to the vector set (ie. not in a phi at the loop head)
2493 bool PhaseIdealLoop::has_use_internal_to_set( Node* n, VectorSet& vset, IdealLoopTree *loop ) {
2494 Node* head = loop->_head;
2495 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
2496 Node* use = n->fast_out(j);
2497 if (vset.test(use->_idx) && !(use->is_Phi() && use->in(0) == head)) {
2498 return true;
2499 }
2500 }
2501 return false;
2502 }
2503
2504
2505 //------------------------------ clone_for_use_outside_loop -------------------------------------
2506 // clone "n" for uses that are outside of loop
2507 int PhaseIdealLoop::clone_for_use_outside_loop( IdealLoopTree *loop, Node* n, Node_List& worklist ) {
2508 int cloned = 0;
2509 assert(worklist.size() == 0, "should be empty");
2510 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
2511 Node* use = n->fast_out(j);
2512 if( !loop->is_member(get_loop(has_ctrl(use) ? get_ctrl(use) : use)) ) {
2513 worklist.push(use);
2514 }
2515 }
2516 while( worklist.size() ) {
2517 Node *use = worklist.pop();
2518 if (!has_node(use) || use->in(0) == C->top()) continue;
2519 uint j;
2520 for (j = 0; j < use->req(); j++) {
2521 if (use->in(j) == n) break;
2522 }
2523 assert(j < use->req(), "must be there");
2524
2525 // clone "n" and insert it between the inputs of "n" and the use outside the loop
2526 Node* n_clone = n->clone();
2527 _igvn.replace_input_of(use, j, n_clone);
2528 cloned++;
2529 Node* use_c;
2530 if (!use->is_Phi()) {
2531 use_c = has_ctrl(use) ? get_ctrl(use) : use->in(0);
2532 } else {
2533 // Use in a phi is considered a use in the associated predecessor block
2534 use_c = use->in(0)->in(j);
2535 }
2536 set_ctrl(n_clone, use_c);
2537 assert(!loop->is_member(get_loop(use_c)), "should be outside loop");
2538 get_loop(use_c)->_body.push(n_clone);
2539 _igvn.register_new_node_with_optimizer(n_clone);
2540 #if !defined(PRODUCT)
2541 if (TracePartialPeeling) {
2542 tty->print_cr("loop exit cloning old: %d new: %d newbb: %d", n->_idx, n_clone->_idx, get_ctrl(n_clone)->_idx);
2543 }
2544 #endif
2545 }
2546 return cloned;
2547 }
2548
2549
2550 //------------------------------ clone_for_special_use_inside_loop -------------------------------------
2551 // clone "n" for special uses that are in the not_peeled region.
2552 // If these def-uses occur in separate blocks, the code generator
2553 // marks the method as not compilable. For example, if a "BoolNode"
2554 // is in a different basic block than the "IfNode" that uses it, then
2555 // the compilation is aborted in the code generator.
2556 void PhaseIdealLoop::clone_for_special_use_inside_loop( IdealLoopTree *loop, Node* n,
2557 VectorSet& not_peel, Node_List& sink_list, Node_List& worklist ) {
2558 if (n->is_Phi() || n->is_Load()) {
2559 return;
2560 }
2561 assert(worklist.size() == 0, "should be empty");
2562 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
2563 Node* use = n->fast_out(j);
2564 if ( not_peel.test(use->_idx) &&
2565 (use->is_If() || use->is_CMove() || use->is_Bool()) &&
2566 use->in(1) == n) {
2567 worklist.push(use);
2568 }
2569 }
2570 if (worklist.size() > 0) {
2571 // clone "n" and insert it between inputs of "n" and the use
2572 Node* n_clone = n->clone();
2573 loop->_body.push(n_clone);
2574 _igvn.register_new_node_with_optimizer(n_clone);
2575 set_ctrl(n_clone, get_ctrl(n));
2576 sink_list.push(n_clone);
2577 not_peel <<= n_clone->_idx; // add n_clone to not_peel set.
2578 #if !defined(PRODUCT)
2579 if (TracePartialPeeling) {
2580 tty->print_cr("special not_peeled cloning old: %d new: %d", n->_idx, n_clone->_idx);
2581 }
2582 #endif
2583 while( worklist.size() ) {
2584 Node *use = worklist.pop();
2585 _igvn.rehash_node_delayed(use);
2586 for (uint j = 1; j < use->req(); j++) {
2587 if (use->in(j) == n) {
2588 use->set_req(j, n_clone);
2589 }
2590 }
2591 }
2592 }
2593 }
2594
2595
2596 //------------------------------ insert_phi_for_loop -------------------------------------
2597 // Insert phi(lp_entry_val, back_edge_val) at use->in(idx) for loop lp if phi does not already exist
2598 void PhaseIdealLoop::insert_phi_for_loop( Node* use, uint idx, Node* lp_entry_val, Node* back_edge_val, LoopNode* lp ) {
2599 Node *phi = PhiNode::make(lp, back_edge_val);
2600 phi->set_req(LoopNode::EntryControl, lp_entry_val);
2601 // Use existing phi if it already exists
2602 Node *hit = _igvn.hash_find_insert(phi);
2603 if( hit == NULL ) {
2604 _igvn.register_new_node_with_optimizer(phi);
2605 set_ctrl(phi, lp);
2606 } else {
2607 // Remove the new phi from the graph and use the hit
2608 _igvn.remove_dead_node(phi);
2609 phi = hit;
2610 }
2611 _igvn.replace_input_of(use, idx, phi);
2612 }
2613
2614 #ifdef ASSERT
2615 //------------------------------ is_valid_loop_partition -------------------------------------
2616 // Validate the loop partition sets: peel and not_peel
2617 bool PhaseIdealLoop::is_valid_loop_partition( IdealLoopTree *loop, VectorSet& peel, Node_List& peel_list,
2618 VectorSet& not_peel ) {
2619 uint i;
2620 // Check that peel_list entries are in the peel set
2621 for (i = 0; i < peel_list.size(); i++) {
2622 if (!peel.test(peel_list.at(i)->_idx)) {
2623 return false;
2624 }
2625 }
2626 // Check at loop members are in one of peel set or not_peel set
2627 for (i = 0; i < loop->_body.size(); i++ ) {
2628 Node *def = loop->_body.at(i);
2629 uint di = def->_idx;
2630 // Check that peel set elements are in peel_list
2631 if (peel.test(di)) {
2632 if (not_peel.test(di)) {
2633 return false;
2634 }
2635 // Must be in peel_list also
2636 bool found = false;
2637 for (uint j = 0; j < peel_list.size(); j++) {
2638 if (peel_list.at(j)->_idx == di) {
2639 found = true;
2640 break;
2641 }
2642 }
2643 if (!found) {
2644 return false;
2645 }
2646 } else if (not_peel.test(di)) {
2647 if (peel.test(di)) {
2648 return false;
2649 }
2650 } else {
2651 return false;
2652 }
2653 }
2654 return true;
2655 }
2656
2657 //------------------------------ is_valid_clone_loop_exit_use -------------------------------------
2658 // Ensure a use outside of loop is of the right form
2659 bool PhaseIdealLoop::is_valid_clone_loop_exit_use( IdealLoopTree *loop, Node* use, uint exit_idx) {
2660 Node *use_c = has_ctrl(use) ? get_ctrl(use) : use;
2661 return (use->is_Phi() &&
2662 use_c->is_Region() && use_c->req() == 3 &&
2663 (use_c->in(exit_idx)->Opcode() == Op_IfTrue ||
2664 use_c->in(exit_idx)->Opcode() == Op_IfFalse ||
2665 use_c->in(exit_idx)->Opcode() == Op_JumpProj) &&
2666 loop->is_member( get_loop( use_c->in(exit_idx)->in(0) ) ) );
2667 }
2668
2669 //------------------------------ is_valid_clone_loop_form -------------------------------------
2670 // Ensure that all uses outside of loop are of the right form
2671 bool PhaseIdealLoop::is_valid_clone_loop_form( IdealLoopTree *loop, Node_List& peel_list,
2672 uint orig_exit_idx, uint clone_exit_idx) {
2673 uint len = peel_list.size();
2674 for (uint i = 0; i < len; i++) {
2675 Node *def = peel_list.at(i);
2676
2677 for (DUIterator_Fast jmax, j = def->fast_outs(jmax); j < jmax; j++) {
2678 Node *use = def->fast_out(j);
2679 Node *use_c = has_ctrl(use) ? get_ctrl(use) : use;
2680 if (!loop->is_member(get_loop(use_c))) {
2681 // use is not in the loop, check for correct structure
2682 if (use->in(0) == def) {
2683 // Okay
2684 } else if (!is_valid_clone_loop_exit_use(loop, use, orig_exit_idx)) {
2685 return false;
2686 }
2687 }
2688 }
2689 }
2690 return true;
2691 }
2692 #endif
2693
2694 //------------------------------ partial_peel -------------------------------------
2695 // Partially peel (aka loop rotation) the top portion of a loop (called
2696 // the peel section below) by cloning it and placing one copy just before
2697 // the new loop head and the other copy at the bottom of the new loop.
2698 //
2699 // before after where it came from
2700 //
2701 // stmt1 stmt1
2702 // loop: stmt2 clone
2703 // stmt2 if condA goto exitA clone
2704 // if condA goto exitA new_loop: new
2705 // stmt3 stmt3 clone
2706 // if !condB goto loop if condB goto exitB clone
2707 // exitB: stmt2 orig
2708 // stmt4 if !condA goto new_loop orig
2709 // exitA: goto exitA
2710 // exitB:
2711 // stmt4
2712 // exitA:
2713 //
2714 // Step 1: find the cut point: an exit test on probable
2715 // induction variable.
2716 // Step 2: schedule (with cloning) operations in the peel
2717 // section that can be executed after the cut into
2718 // the section that is not peeled. This may need
2719 // to clone operations into exit blocks. For
2720 // instance, a reference to A[i] in the not-peel
2721 // section and a reference to B[i] in an exit block
2722 // may cause a left-shift of i by 2 to be placed
2723 // in the peel block. This step will clone the left
2724 // shift into the exit block and sink the left shift
2725 // from the peel to the not-peel section.
2726 // Step 3: clone the loop, retarget the control, and insert
2727 // phis for values that are live across the new loop
2728 // head. This is very dependent on the graph structure
2729 // from clone_loop. It creates region nodes for
2730 // exit control and associated phi nodes for values
2731 // flow out of the loop through that exit. The region
2732 // node is dominated by the clone's control projection.
2733 // So the clone's peel section is placed before the
2734 // new loop head, and the clone's not-peel section is
2735 // forms the top part of the new loop. The original
2736 // peel section forms the tail of the new loop.
2737 // Step 4: update the dominator tree and recompute the
2738 // dominator depth.
2739 //
2740 // orig
2741 //
2742 // stmt1
2743 // |
2744 // v
2745 // loop predicate
2746 // |
2747 // v
2748 // loop<----+
2749 // | |
2750 // stmt2 |
2751 // | |
2752 // v |
2753 // ifA |
2754 // / | |
2755 // v v |
2756 // false true ^ <-- last_peel
2757 // / | |
2758 // / ===|==cut |
2759 // / stmt3 | <-- first_not_peel
2760 // / | |
2761 // | v |
2762 // v ifB |
2763 // exitA: / \ |
2764 // / \ |
2765 // v v |
2766 // false true |
2767 // / \ |
2768 // / ----+
2769 // |
2770 // v
2771 // exitB:
2772 // stmt4
2773 //
2774 //
2775 // after clone loop
2776 //
2777 // stmt1
2778 // |
2779 // v
2780 // loop predicate
2781 // / \
2782 // clone / \ orig
2783 // / \
2784 // / \
2785 // v v
2786 // +---->loop loop<----+
2787 // | | | |
2788 // | stmt2 stmt2 |
2789 // | | | |
2790 // | v v |
2791 // | ifA ifA |
2792 // | | \ / | |
2793 // | v v v v |
2794 // ^ true false false true ^ <-- last_peel
2795 // | | ^ \ / | |
2796 // | cut==|== \ \ / ===|==cut |
2797 // | stmt3 \ \ / stmt3 | <-- first_not_peel
2798 // | | dom | | | |
2799 // | v \ 1v v2 v |
2800 // | ifB regionA ifB |
2801 // | / \ | / \ |
2802 // | / \ v / \ |
2803 // | v v exitA: v v |
2804 // | true false false true |
2805 // | / ^ \ / \ |
2806 // +---- \ \ / ----+
2807 // dom \ /
2808 // \ 1v v2
2809 // regionB
2810 // |
2811 // v
2812 // exitB:
2813 // stmt4
2814 //
2815 //
2816 // after partial peel
2817 //
2818 // stmt1
2819 // |
2820 // v
2821 // loop predicate
2822 // /
2823 // clone / orig
2824 // / TOP
2825 // / \
2826 // v v
2827 // TOP->loop loop----+
2828 // | | |
2829 // stmt2 stmt2 |
2830 // | | |
2831 // v v |
2832 // ifA ifA |
2833 // | \ / | |
2834 // v v v v |
2835 // true false false true | <-- last_peel
2836 // | ^ \ / +------|---+
2837 // +->newloop \ \ / === ==cut | |
2838 // | stmt3 \ \ / TOP | |
2839 // | | dom | | stmt3 | | <-- first_not_peel
2840 // | v \ 1v v2 v | |
2841 // | ifB regionA ifB ^ v
2842 // | / \ | / \ | |
2843 // | / \ v / \ | |
2844 // | v v exitA: v v | |
2845 // | true false false true | |
2846 // | / ^ \ / \ | |
2847 // | | \ \ / v | |
2848 // | | dom \ / TOP | |
2849 // | | \ 1v v2 | |
2850 // ^ v regionB | |
2851 // | | | | |
2852 // | | v ^ v
2853 // | | exitB: | |
2854 // | | stmt4 | |
2855 // | +------------>-----------------+ |
2856 // | |
2857 // +-----------------<---------------------+
2858 //
2859 //
2860 // final graph
2861 //
2862 // stmt1
2863 // |
2864 // v
2865 // loop predicate
2866 // |
2867 // v
2868 // stmt2 clone
2869 // |
2870 // v
2871 // ........> ifA clone
2872 // : / |
2873 // dom / |
2874 // : v v
2875 // : false true
2876 // : | |
2877 // : | v
2878 // : | newloop<-----+
2879 // : | | |
2880 // : | stmt3 clone |
2881 // : | | |
2882 // : | v |
2883 // : | ifB |
2884 // : | / \ |
2885 // : | v v |
2886 // : | false true |
2887 // : | | | |
2888 // : | v stmt2 |
2889 // : | exitB: | |
2890 // : | stmt4 v |
2891 // : | ifA orig |
2892 // : | / \ |
2893 // : | / \ |
2894 // : | v v |
2895 // : | false true |
2896 // : | / \ |
2897 // : v v -----+
2898 // RegionA
2899 // |
2900 // v
2901 // exitA
2902 //
2903 bool PhaseIdealLoop::partial_peel( IdealLoopTree *loop, Node_List &old_new ) {
2904
2905 assert(!loop->_head->is_CountedLoop(), "Non-counted loop only");
2906 if (!loop->_head->is_Loop()) {
2907 return false; }
2908
2909 LoopNode *head = loop->_head->as_Loop();
2910
2911 if (head->is_partial_peel_loop() || head->partial_peel_has_failed()) {
2912 return false;
2913 }
2914
2915 // Check for complex exit control
2916 for(uint ii = 0; ii < loop->_body.size(); ii++ ) {
2917 Node *n = loop->_body.at(ii);
2918 int opc = n->Opcode();
2919 if (n->is_Call() ||
2920 opc == Op_Catch ||
2921 opc == Op_CatchProj ||
2922 opc == Op_Jump ||
2923 opc == Op_JumpProj) {
2924 #if !defined(PRODUCT)
2925 if (TracePartialPeeling) {
2926 tty->print_cr("\nExit control too complex: lp: %d", head->_idx);
2927 }
2928 #endif
2929 return false;
2930 }
2931 }
2932
2933 int dd = dom_depth(head);
2934
2935 // Step 1: find cut point
2936
2937 // Walk up dominators to loop head looking for first loop exit
2938 // which is executed on every path thru loop.
2939 IfNode *peel_if = NULL;
2940 IfNode *peel_if_cmpu = NULL;
2941
2942 Node *iff = loop->tail();
2943 while( iff != head ) {
2944 if( iff->is_If() ) {
2945 Node *ctrl = get_ctrl(iff->in(1));
2946 if (ctrl->is_top()) return false; // Dead test on live IF.
2947 // If loop-varying exit-test, check for induction variable
2948 if( loop->is_member(get_loop(ctrl)) &&
2949 loop->is_loop_exit(iff) &&
2950 is_possible_iv_test(iff)) {
2951 Node* cmp = iff->in(1)->in(1);
2952 if (cmp->Opcode() == Op_CmpI) {
2953 peel_if = iff->as_If();
2954 } else {
2955 assert(cmp->Opcode() == Op_CmpU, "must be CmpI or CmpU");
2956 peel_if_cmpu = iff->as_If();
2957 }
2958 }
2959 }
2960 iff = idom(iff);
2961 }
2962 // Prefer signed compare over unsigned compare.
2963 IfNode* new_peel_if = NULL;
2964 if (peel_if == NULL) {
2965 if (!PartialPeelAtUnsignedTests || peel_if_cmpu == NULL) {
2966 return false; // No peel point found
2967 }
2968 new_peel_if = insert_cmpi_loop_exit(peel_if_cmpu, loop);
2969 if (new_peel_if == NULL) {
2970 return false; // No peel point found
2971 }
2972 peel_if = new_peel_if;
2973 }
2974 Node* last_peel = stay_in_loop(peel_if, loop);
2975 Node* first_not_peeled = stay_in_loop(last_peel, loop);
2976 if (first_not_peeled == NULL || first_not_peeled == head) {
2977 return false;
2978 }
2979
2980 #if !defined(PRODUCT)
2981 if (TraceLoopOpts) {
2982 tty->print("PartialPeel ");
2983 loop->dump_head();
2984 }
2985
2986 if (TracePartialPeeling) {
2987 tty->print_cr("before partial peel one iteration");
2988 Node_List wl;
2989 Node* t = head->in(2);
2990 while (true) {
2991 wl.push(t);
2992 if (t == head) break;
2993 t = idom(t);
2994 }
2995 while (wl.size() > 0) {
2996 Node* tt = wl.pop();
2997 tt->dump();
2998 if (tt == last_peel) tty->print_cr("-- cut --");
2999 }
3000 }
3001 #endif
3002 ResourceArea *area = Thread::current()->resource_area();
3003 VectorSet peel(area);
3004 VectorSet not_peel(area);
3005 Node_List peel_list(area);
3006 Node_List worklist(area);
3007 Node_List sink_list(area);
3008
3009 // Set of cfg nodes to peel are those that are executable from
3010 // the head through last_peel.
3011 assert(worklist.size() == 0, "should be empty");
3012 worklist.push(head);
3013 peel.set(head->_idx);
3014 while (worklist.size() > 0) {
3015 Node *n = worklist.pop();
3016 if (n != last_peel) {
3017 for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) {
3018 Node* use = n->fast_out(j);
3019 if (use->is_CFG() &&
3020 loop->is_member(get_loop(use)) &&
3021 !peel.test_set(use->_idx)) {
3022 worklist.push(use);
3023 }
3024 }
3025 }
3026 }
3027
3028 // Set of non-cfg nodes to peel are those that are control
3029 // dependent on the cfg nodes.
3030 uint i;
3031 for(i = 0; i < loop->_body.size(); i++ ) {
3032 Node *n = loop->_body.at(i);
3033 Node *n_c = has_ctrl(n) ? get_ctrl(n) : n;
3034 if (peel.test(n_c->_idx)) {
3035 peel.set(n->_idx);
3036 } else {
3037 not_peel.set(n->_idx);
3038 }
3039 }
3040
3041 // Step 2: move operations from the peeled section down into the
3042 // not-peeled section
3043
3044 // Get a post order schedule of nodes in the peel region
3045 // Result in right-most operand.
3046 scheduled_nodelist(loop, peel, peel_list );
3047
3048 assert(is_valid_loop_partition(loop, peel, peel_list, not_peel), "bad partition");
3049
3050 // For future check for too many new phis
3051 uint old_phi_cnt = 0;
3052 for (DUIterator_Fast jmax, j = head->fast_outs(jmax); j < jmax; j++) {
3053 Node* use = head->fast_out(j);
3054 if (use->is_Phi()) old_phi_cnt++;
3055 }
3056
3057 #if !defined(PRODUCT)
3058 if (TracePartialPeeling) {
3059 tty->print_cr("\npeeled list");
3060 }
3061 #endif
3062
3063 // Evacuate nodes in peel region into the not_peeled region if possible
3064 uint new_phi_cnt = 0;
3065 uint cloned_for_outside_use = 0;
3066 for (i = 0; i < peel_list.size();) {
3067 Node* n = peel_list.at(i);
3068 #if !defined(PRODUCT)
3069 if (TracePartialPeeling) n->dump();
3070 #endif
3071 bool incr = true;
3072 if ( !n->is_CFG() ) {
3073
3074 if ( has_use_in_set(n, not_peel) ) {
3075
3076 // If not used internal to the peeled region,
3077 // move "n" from peeled to not_peeled region.
3078
3079 if ( !has_use_internal_to_set(n, peel, loop) ) {
3080
3081 // if not pinned and not a load (which maybe anti-dependent on a store)
3082 // and not a CMove (Matcher expects only bool->cmove).
3083 if ( n->in(0) == NULL && !n->is_Load() && !n->is_CMove() ) {
3084 cloned_for_outside_use += clone_for_use_outside_loop( loop, n, worklist );
3085 sink_list.push(n);
3086 peel >>= n->_idx; // delete n from peel set.
3087 not_peel <<= n->_idx; // add n to not_peel set.
3088 peel_list.remove(i);
3089 incr = false;
3090 #if !defined(PRODUCT)
3091 if (TracePartialPeeling) {
3092 tty->print_cr("sink to not_peeled region: %d newbb: %d",
3093 n->_idx, get_ctrl(n)->_idx);
3094 }
3095 #endif
3096 }
3097 } else {
3098 // Otherwise check for special def-use cases that span
3099 // the peel/not_peel boundary such as bool->if
3100 clone_for_special_use_inside_loop( loop, n, not_peel, sink_list, worklist );
3101 new_phi_cnt++;
3102 }
3103 }
3104 }
3105 if (incr) i++;
3106 }
3107
3108 if (new_phi_cnt > old_phi_cnt + PartialPeelNewPhiDelta) {
3109 #if !defined(PRODUCT)
3110 if (TracePartialPeeling) {
3111 tty->print_cr("\nToo many new phis: %d old %d new cmpi: %c",
3112 new_phi_cnt, old_phi_cnt, new_peel_if != NULL?'T':'F');
3113 }
3114 #endif
3115 if (new_peel_if != NULL) {
3116 remove_cmpi_loop_exit(new_peel_if, loop);
3117 }
3118 // Inhibit more partial peeling on this loop
3119 assert(!head->is_partial_peel_loop(), "not partial peeled");
3120 head->mark_partial_peel_failed();
3121 if (cloned_for_outside_use > 0) {
3122 // Terminate this round of loop opts because
3123 // the graph outside this loop was changed.
3124 C->set_major_progress();
3125 return true;
3126 }
3127 return false;
3128 }
3129
3130 // Step 3: clone loop, retarget control, and insert new phis
3131
3132 // Create new loop head for new phis and to hang
3133 // the nodes being moved (sinked) from the peel region.
3134 LoopNode* new_head = new LoopNode(last_peel, last_peel);
3135 new_head->set_unswitch_count(head->unswitch_count()); // Preserve
3136 _igvn.register_new_node_with_optimizer(new_head);
3137 assert(first_not_peeled->in(0) == last_peel, "last_peel <- first_not_peeled");
3138 _igvn.replace_input_of(first_not_peeled, 0, new_head);
3139 set_loop(new_head, loop);
3140 loop->_body.push(new_head);
3141 not_peel.set(new_head->_idx);
3142 set_idom(new_head, last_peel, dom_depth(first_not_peeled));
3143 set_idom(first_not_peeled, new_head, dom_depth(first_not_peeled));
3144
3145 while (sink_list.size() > 0) {
3146 Node* n = sink_list.pop();
3147 set_ctrl(n, new_head);
3148 }
3149
3150 assert(is_valid_loop_partition(loop, peel, peel_list, not_peel), "bad partition");
3151
3152 clone_loop(loop, old_new, dd, IgnoreStripMined);
3153
3154 const uint clone_exit_idx = 1;
3155 const uint orig_exit_idx = 2;
3156 assert(is_valid_clone_loop_form( loop, peel_list, orig_exit_idx, clone_exit_idx ), "bad clone loop");
3157
3158 Node* head_clone = old_new[head->_idx];
3159 LoopNode* new_head_clone = old_new[new_head->_idx]->as_Loop();
3160 Node* orig_tail_clone = head_clone->in(2);
3161
3162 // Add phi if "def" node is in peel set and "use" is not
3163
3164 for(i = 0; i < peel_list.size(); i++ ) {
3165 Node *def = peel_list.at(i);
3166 if (!def->is_CFG()) {
3167 for (DUIterator_Fast jmax, j = def->fast_outs(jmax); j < jmax; j++) {
3168 Node *use = def->fast_out(j);
3169 if (has_node(use) && use->in(0) != C->top() &&
3170 (!peel.test(use->_idx) ||
3171 (use->is_Phi() && use->in(0) == head)) ) {
3172 worklist.push(use);
3173 }
3174 }
3175 while( worklist.size() ) {
3176 Node *use = worklist.pop();
3177 for (uint j = 1; j < use->req(); j++) {
3178 Node* n = use->in(j);
3179 if (n == def) {
3180
3181 // "def" is in peel set, "use" is not in peel set
3182 // or "use" is in the entry boundary (a phi) of the peel set
3183
3184 Node* use_c = has_ctrl(use) ? get_ctrl(use) : use;
3185
3186 if ( loop->is_member(get_loop( use_c )) ) {
3187 // use is in loop
3188 if (old_new[use->_idx] != NULL) { // null for dead code
3189 Node* use_clone = old_new[use->_idx];
3190 _igvn.replace_input_of(use, j, C->top());
3191 insert_phi_for_loop( use_clone, j, old_new[def->_idx], def, new_head_clone );
3192 }
3193 } else {
3194 assert(is_valid_clone_loop_exit_use(loop, use, orig_exit_idx), "clone loop format");
3195 // use is not in the loop, check if the live range includes the cut
3196 Node* lp_if = use_c->in(orig_exit_idx)->in(0);
3197 if (not_peel.test(lp_if->_idx)) {
3198 assert(j == orig_exit_idx, "use from original loop");
3199 insert_phi_for_loop( use, clone_exit_idx, old_new[def->_idx], def, new_head_clone );
3200 }
3201 }
3202 }
3203 }
3204 }
3205 }
3206 }
3207
3208 // Step 3b: retarget control
3209
3210 // Redirect control to the new loop head if a cloned node in
3211 // the not_peeled region has control that points into the peeled region.
3212 // This necessary because the cloned peeled region will be outside
3213 // the loop.
3214 // from to
3215 // cloned-peeled <---+
3216 // new_head_clone: | <--+
3217 // cloned-not_peeled in(0) in(0)
3218 // orig-peeled
3219
3220 for(i = 0; i < loop->_body.size(); i++ ) {
3221 Node *n = loop->_body.at(i);
3222 if (!n->is_CFG() && n->in(0) != NULL &&
3223 not_peel.test(n->_idx) && peel.test(n->in(0)->_idx)) {
3224 Node* n_clone = old_new[n->_idx];
3225 _igvn.replace_input_of(n_clone, 0, new_head_clone);
3226 }
3227 }
3228
3229 // Backedge of the surviving new_head (the clone) is original last_peel
3230 _igvn.replace_input_of(new_head_clone, LoopNode::LoopBackControl, last_peel);
3231
3232 // Cut first node in original not_peel set
3233 _igvn.rehash_node_delayed(new_head); // Multiple edge updates:
3234 new_head->set_req(LoopNode::EntryControl, C->top()); // use rehash_node_delayed / set_req instead of
3235 new_head->set_req(LoopNode::LoopBackControl, C->top()); // multiple replace_input_of calls
3236
3237 // Copy head_clone back-branch info to original head
3238 // and remove original head's loop entry and
3239 // clone head's back-branch
3240 _igvn.rehash_node_delayed(head); // Multiple edge updates
3241 head->set_req(LoopNode::EntryControl, head_clone->in(LoopNode::LoopBackControl));
3242 head->set_req(LoopNode::LoopBackControl, C->top());
3243 _igvn.replace_input_of(head_clone, LoopNode::LoopBackControl, C->top());
3244
3245 // Similarly modify the phis
3246 for (DUIterator_Fast kmax, k = head->fast_outs(kmax); k < kmax; k++) {
3247 Node* use = head->fast_out(k);
3248 if (use->is_Phi() && use->outcnt() > 0) {
3249 Node* use_clone = old_new[use->_idx];
3250 _igvn.rehash_node_delayed(use); // Multiple edge updates
3251 use->set_req(LoopNode::EntryControl, use_clone->in(LoopNode::LoopBackControl));
3252 use->set_req(LoopNode::LoopBackControl, C->top());
3253 _igvn.replace_input_of(use_clone, LoopNode::LoopBackControl, C->top());
3254 }
3255 }
3256
3257 // Step 4: update dominator tree and dominator depth
3258
3259 set_idom(head, orig_tail_clone, dd);
3260 recompute_dom_depth();
3261
3262 // Inhibit more partial peeling on this loop
3263 new_head_clone->set_partial_peel_loop();
3264 C->set_major_progress();
3265 loop->record_for_igvn();
3266
3267 #if !defined(PRODUCT)
3268 if (TracePartialPeeling) {
3269 tty->print_cr("\nafter partial peel one iteration");
3270 Node_List wl(area);
3271 Node* t = last_peel;
3272 while (true) {
3273 wl.push(t);
3274 if (t == head_clone) break;
3275 t = idom(t);
3276 }
3277 while (wl.size() > 0) {
3278 Node* tt = wl.pop();
3279 if (tt == head) tty->print_cr("orig head");
3280 else if (tt == new_head_clone) tty->print_cr("new head");
3281 else if (tt == head_clone) tty->print_cr("clone head");
3282 tt->dump();
3283 }
3284 }
3285 #endif
3286 return true;
3287 }
3288
3289 //------------------------------reorg_offsets----------------------------------
3290 // Reorganize offset computations to lower register pressure. Mostly
3291 // prevent loop-fallout uses of the pre-incremented trip counter (which are
3292 // then alive with the post-incremented trip counter forcing an extra
3293 // register move)
3294 void PhaseIdealLoop::reorg_offsets(IdealLoopTree *loop) {
3295 // Perform it only for canonical counted loops.
3296 // Loop's shape could be messed up by iteration_split_impl.
3297 if (!loop->_head->is_CountedLoop())
3298 return;
3299 if (!loop->_head->as_Loop()->is_valid_counted_loop())
3300 return;
3301
3302 CountedLoopNode *cl = loop->_head->as_CountedLoop();
3303 CountedLoopEndNode *cle = cl->loopexit();
3304 Node *exit = cle->proj_out(false);
3305 Node *phi = cl->phi();
3306
3307 // Check for the special case of folks using the pre-incremented
3308 // trip-counter on the fall-out path (forces the pre-incremented
3309 // and post-incremented trip counter to be live at the same time).
3310 // Fix this by adjusting to use the post-increment trip counter.
3311
3312 bool progress = true;
3313 while (progress) {
3314 progress = false;
3315 for (DUIterator_Fast imax, i = phi->fast_outs(imax); i < imax; i++) {
3316 Node* use = phi->fast_out(i); // User of trip-counter
3317 if (!has_ctrl(use)) continue;
3318 Node *u_ctrl = get_ctrl(use);
3319 if (use->is_Phi()) {
3320 u_ctrl = NULL;
3321 for (uint j = 1; j < use->req(); j++)
3322 if (use->in(j) == phi)
3323 u_ctrl = dom_lca(u_ctrl, use->in(0)->in(j));
3324 }
3325 IdealLoopTree *u_loop = get_loop(u_ctrl);
3326 // Look for loop-invariant use
3327 if (u_loop == loop) continue;
3328 if (loop->is_member(u_loop)) continue;
3329 // Check that use is live out the bottom. Assuming the trip-counter
3330 // update is right at the bottom, uses of of the loop middle are ok.
3331 if (dom_lca(exit, u_ctrl) != exit) continue;
3332 // Hit! Refactor use to use the post-incremented tripcounter.
3333 // Compute a post-increment tripcounter.
3334 Node *opaq = new Opaque2Node( C, cle->incr() );
3335 register_new_node(opaq, exit);
3336 Node *neg_stride = _igvn.intcon(-cle->stride_con());
3337 set_ctrl(neg_stride, C->root());
3338 Node *post = new AddINode( opaq, neg_stride);
3339 register_new_node(post, exit);
3340 _igvn.rehash_node_delayed(use);
3341 for (uint j = 1; j < use->req(); j++) {
3342 if (use->in(j) == phi)
3343 use->set_req(j, post);
3344 }
3345 // Since DU info changed, rerun loop
3346 progress = true;
3347 break;
3348 }
3349 }
3350
3351 }