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