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