Mercurial > hg > graal-compiler
annotate src/share/vm/opto/loopnode.cpp @ 3992:d1bdeef3e3e2
7098282: G1: assert(interval >= 0) failed: Sanity check, referencePolicy.cpp: 76
Summary: There is a race between one thread successfully forwarding and copying the klass mirror for the SoftReference class (including the static master clock) and another thread attempting to use the master clock while attempting to discover a soft reference object. Maintain a shadow copy of the soft reference master clock and use the shadow during reference discovery and reference processing.
Reviewed-by: tonyp, brutisso, ysr
| author | johnc |
|---|---|
| date | Wed, 12 Oct 2011 10:25:51 -0700 |
| parents | 2c24ef16533d |
| children | 670a74b863fc |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
2248
194c9fdee631
7017240: C2: native memory leak in nsk/regression/b4675027 on windows-x86 in comp mode with G1
kvn
parents:
1972
diff
changeset
|
2 * Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved. |
| 0 | 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| 4 * | |
| 5 * This code is free software; you can redistribute it and/or modify it | |
| 6 * under the terms of the GNU General Public License version 2 only, as | |
| 7 * published by the Free Software Foundation. | |
| 8 * | |
| 9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
| 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 12 * version 2 for more details (a copy is included in the LICENSE file that | |
| 13 * accompanied this code). | |
| 14 * | |
| 15 * You should have received a copy of the GNU General Public License version | |
| 16 * 2 along with this work; if not, write to the Free Software Foundation, | |
| 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| 18 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1172
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1172
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:
1172
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 1972 | 25 #include "precompiled.hpp" |
| 26 #include "ci/ciMethodData.hpp" | |
| 27 #include "compiler/compileLog.hpp" | |
| 28 #include "libadt/vectset.hpp" | |
| 29 #include "memory/allocation.inline.hpp" | |
| 30 #include "opto/addnode.hpp" | |
| 31 #include "opto/callnode.hpp" | |
| 32 #include "opto/connode.hpp" | |
| 33 #include "opto/divnode.hpp" | |
| 34 #include "opto/idealGraphPrinter.hpp" | |
| 35 #include "opto/loopnode.hpp" | |
| 36 #include "opto/mulnode.hpp" | |
| 37 #include "opto/rootnode.hpp" | |
| 38 #include "opto/superword.hpp" | |
| 0 | 39 |
| 40 //============================================================================= | |
| 41 //------------------------------is_loop_iv------------------------------------- | |
| 42 // Determine if a node is Counted loop induction variable. | |
| 43 // The method is declared in node.hpp. | |
| 44 const Node* Node::is_loop_iv() const { | |
| 45 if (this->is_Phi() && !this->as_Phi()->is_copy() && | |
| 46 this->as_Phi()->region()->is_CountedLoop() && | |
| 47 this->as_Phi()->region()->as_CountedLoop()->phi() == this) { | |
| 48 return this; | |
| 49 } else { | |
| 50 return NULL; | |
| 51 } | |
| 52 } | |
| 53 | |
| 54 //============================================================================= | |
| 55 //------------------------------dump_spec-------------------------------------- | |
| 56 // Dump special per-node info | |
| 57 #ifndef PRODUCT | |
| 58 void LoopNode::dump_spec(outputStream *st) const { | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
59 if (is_inner_loop()) st->print( "inner " ); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
60 if (is_partial_peel_loop()) st->print( "partial_peel " ); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
61 if (partial_peel_has_failed()) st->print( "partial_peel_failed " ); |
| 0 | 62 } |
| 63 #endif | |
| 64 | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
65 //------------------------------is_valid_counted_loop------------------------- |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
66 bool LoopNode::is_valid_counted_loop() const { |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
67 if (is_CountedLoop()) { |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
68 CountedLoopNode* l = as_CountedLoop(); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
69 CountedLoopEndNode* le = l->loopexit(); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
70 if (le != NULL && |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
71 le->proj_out(1 /* true */) == l->in(LoopNode::LoopBackControl)) { |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
72 Node* phi = l->phi(); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
73 Node* exit = le->proj_out(0 /* false */); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
74 if (exit != NULL && exit->Opcode() == Op_IfFalse && |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
75 phi != NULL && phi->is_Phi() && |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
76 phi->in(LoopNode::LoopBackControl) == l->incr() && |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
77 le->loopnode() == l && le->stride_is_con()) { |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
78 return true; |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
79 } |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
80 } |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
81 } |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
82 return false; |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
83 } |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
84 |
| 0 | 85 //------------------------------get_early_ctrl--------------------------------- |
| 86 // Compute earliest legal control | |
| 87 Node *PhaseIdealLoop::get_early_ctrl( Node *n ) { | |
| 88 assert( !n->is_Phi() && !n->is_CFG(), "this code only handles data nodes" ); | |
| 89 uint i; | |
| 90 Node *early; | |
| 91 if( n->in(0) ) { | |
| 92 early = n->in(0); | |
| 93 if( !early->is_CFG() ) // Might be a non-CFG multi-def | |
| 94 early = get_ctrl(early); // So treat input as a straight data input | |
| 95 i = 1; | |
| 96 } else { | |
| 97 early = get_ctrl(n->in(1)); | |
| 98 i = 2; | |
| 99 } | |
| 100 uint e_d = dom_depth(early); | |
| 101 assert( early, "" ); | |
| 102 for( ; i < n->req(); i++ ) { | |
| 103 Node *cin = get_ctrl(n->in(i)); | |
| 104 assert( cin, "" ); | |
| 105 // Keep deepest dominator depth | |
| 106 uint c_d = dom_depth(cin); | |
| 107 if( c_d > e_d ) { // Deeper guy? | |
| 108 early = cin; // Keep deepest found so far | |
| 109 e_d = c_d; | |
| 110 } else if( c_d == e_d && // Same depth? | |
| 111 early != cin ) { // If not equal, must use slower algorithm | |
| 112 // If same depth but not equal, one _must_ dominate the other | |
| 113 // and we want the deeper (i.e., dominated) guy. | |
| 114 Node *n1 = early; | |
| 115 Node *n2 = cin; | |
| 116 while( 1 ) { | |
| 117 n1 = idom(n1); // Walk up until break cycle | |
| 118 n2 = idom(n2); | |
| 119 if( n1 == cin || // Walked early up to cin | |
| 120 dom_depth(n2) < c_d ) | |
| 121 break; // early is deeper; keep him | |
| 122 if( n2 == early || // Walked cin up to early | |
| 123 dom_depth(n1) < c_d ) { | |
| 124 early = cin; // cin is deeper; keep him | |
| 125 break; | |
| 126 } | |
| 127 } | |
| 128 e_d = dom_depth(early); // Reset depth register cache | |
| 129 } | |
| 130 } | |
| 131 | |
| 132 // Return earliest legal location | |
| 133 assert(early == find_non_split_ctrl(early), "unexpected early control"); | |
| 134 | |
| 135 return early; | |
| 136 } | |
| 137 | |
| 138 //------------------------------set_early_ctrl--------------------------------- | |
| 139 // Set earliest legal control | |
| 140 void PhaseIdealLoop::set_early_ctrl( Node *n ) { | |
| 141 Node *early = get_early_ctrl(n); | |
| 142 | |
| 143 // Record earliest legal location | |
| 144 set_ctrl(n, early); | |
| 145 } | |
| 146 | |
| 147 //------------------------------set_subtree_ctrl------------------------------- | |
| 148 // set missing _ctrl entries on new nodes | |
| 149 void PhaseIdealLoop::set_subtree_ctrl( Node *n ) { | |
| 150 // Already set? Get out. | |
| 151 if( _nodes[n->_idx] ) return; | |
| 152 // Recursively set _nodes array to indicate where the Node goes | |
| 153 uint i; | |
| 154 for( i = 0; i < n->req(); ++i ) { | |
| 155 Node *m = n->in(i); | |
| 156 if( m && m != C->root() ) | |
| 157 set_subtree_ctrl( m ); | |
| 158 } | |
| 159 | |
| 160 // Fixup self | |
| 161 set_early_ctrl( n ); | |
| 162 } | |
| 163 | |
| 164 //------------------------------is_counted_loop-------------------------------- | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
165 bool PhaseIdealLoop::is_counted_loop( Node *x, IdealLoopTree *loop ) { |
| 0 | 166 PhaseGVN *gvn = &_igvn; |
| 167 | |
| 168 // Counted loop head must be a good RegionNode with only 3 not NULL | |
| 169 // control input edges: Self, Entry, LoopBack. | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
170 if (x->in(LoopNode::Self) == NULL || x->req() != 3) |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
171 return false; |
| 0 | 172 |
| 173 Node *init_control = x->in(LoopNode::EntryControl); | |
| 174 Node *back_control = x->in(LoopNode::LoopBackControl); | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
175 if (init_control == NULL || back_control == NULL) // Partially dead |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
176 return false; |
| 0 | 177 // Must also check for TOP when looking for a dead loop |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
178 if (init_control->is_top() || back_control->is_top()) |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
179 return false; |
| 0 | 180 |
| 181 // Allow funny placement of Safepoint | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
182 if (back_control->Opcode() == Op_SafePoint) |
| 0 | 183 back_control = back_control->in(TypeFunc::Control); |
| 184 | |
| 185 // Controlling test for loop | |
| 186 Node *iftrue = back_control; | |
| 187 uint iftrue_op = iftrue->Opcode(); | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
188 if (iftrue_op != Op_IfTrue && |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
189 iftrue_op != Op_IfFalse) |
| 0 | 190 // I have a weird back-control. Probably the loop-exit test is in |
| 191 // the middle of the loop and I am looking at some trailing control-flow | |
| 192 // merge point. To fix this I would have to partially peel the loop. | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
193 return false; // Obscure back-control |
| 0 | 194 |
| 195 // Get boolean guarding loop-back test | |
| 196 Node *iff = iftrue->in(0); | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
197 if (get_loop(iff) != loop || !iff->in(1)->is_Bool()) |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
198 return false; |
| 0 | 199 BoolNode *test = iff->in(1)->as_Bool(); |
| 200 BoolTest::mask bt = test->_test._test; | |
| 201 float cl_prob = iff->as_If()->_prob; | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
202 if (iftrue_op == Op_IfFalse) { |
| 0 | 203 bt = BoolTest(bt).negate(); |
| 204 cl_prob = 1.0 - cl_prob; | |
| 205 } | |
| 206 // Get backedge compare | |
| 207 Node *cmp = test->in(1); | |
| 208 int cmp_op = cmp->Opcode(); | |
| 3345 | 209 if (cmp_op != Op_CmpI) |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
210 return false; // Avoid pointer & float compares |
| 0 | 211 |
| 212 // Find the trip-counter increment & limit. Limit must be loop invariant. | |
| 213 Node *incr = cmp->in(1); | |
| 214 Node *limit = cmp->in(2); | |
| 215 | |
| 216 // --------- | |
| 217 // need 'loop()' test to tell if limit is loop invariant | |
| 218 // --------- | |
| 219 | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
220 if (!is_member(loop, get_ctrl(incr))) { // Swapped trip counter and limit? |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
221 Node *tmp = incr; // Then reverse order into the CmpI |
| 0 | 222 incr = limit; |
| 223 limit = tmp; | |
| 224 bt = BoolTest(bt).commute(); // And commute the exit test | |
| 225 } | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
226 if (is_member(loop, get_ctrl(limit))) // Limit must be loop-invariant |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
227 return false; |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
228 if (!is_member(loop, get_ctrl(incr))) // Trip counter must be loop-variant |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
229 return false; |
| 0 | 230 |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
231 Node* phi_incr = NULL; |
| 0 | 232 // Trip-counter increment must be commutative & associative. |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
233 if (incr->is_Phi()) { |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
234 if (incr->as_Phi()->region() != x || incr->req() != 3) |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
235 return false; // Not simple trip counter expression |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
236 phi_incr = incr; |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
237 incr = phi_incr->in(LoopNode::LoopBackControl); // Assume incr is on backedge of Phi |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
238 if (!is_member(loop, get_ctrl(incr))) // Trip counter must be loop-variant |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
239 return false; |
| 0 | 240 } |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
241 |
| 0 | 242 Node* trunc1 = NULL; |
| 243 Node* trunc2 = NULL; | |
| 244 const TypeInt* iv_trunc_t = NULL; | |
| 245 if (!(incr = CountedLoopNode::match_incr_with_optional_truncation(incr, &trunc1, &trunc2, &iv_trunc_t))) { | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
246 return false; // Funny increment opcode |
| 0 | 247 } |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
248 assert(incr->Opcode() == Op_AddI, "wrong increment code"); |
| 0 | 249 |
| 250 // Get merge point | |
| 251 Node *xphi = incr->in(1); | |
| 252 Node *stride = incr->in(2); | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
253 if (!stride->is_Con()) { // Oops, swap these |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
254 if (!xphi->is_Con()) // Is the other guy a constant? |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
255 return false; // Nope, unknown stride, bail out |
| 0 | 256 Node *tmp = xphi; // 'incr' is commutative, so ok to swap |
| 257 xphi = stride; | |
| 258 stride = tmp; | |
| 259 } | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
260 // Stride must be constant |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
261 int stride_con = stride->get_int(); |
| 3345 | 262 if (stride_con == 0) |
| 263 return false; // missed some peephole opt | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
264 |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
265 if (!xphi->is_Phi()) |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
266 return false; // Too much math on the trip counter |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
267 if (phi_incr != NULL && phi_incr != xphi) |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
268 return false; |
| 0 | 269 PhiNode *phi = xphi->as_Phi(); |
| 270 | |
| 271 // Phi must be of loop header; backedge must wrap to increment | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
272 if (phi->region() != x) |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
273 return false; |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
274 if (trunc1 == NULL && phi->in(LoopNode::LoopBackControl) != incr || |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
275 trunc1 != NULL && phi->in(LoopNode::LoopBackControl) != trunc1) { |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
276 return false; |
| 0 | 277 } |
| 278 Node *init_trip = phi->in(LoopNode::EntryControl); | |
| 279 | |
| 280 // If iv trunc type is smaller than int, check for possible wrap. | |
| 281 if (!TypeInt::INT->higher_equal(iv_trunc_t)) { | |
| 282 assert(trunc1 != NULL, "must have found some truncation"); | |
| 283 | |
| 284 // Get a better type for the phi (filtered thru if's) | |
| 285 const TypeInt* phi_ft = filtered_type(phi); | |
| 286 | |
| 287 // Can iv take on a value that will wrap? | |
| 288 // | |
| 289 // Ensure iv's limit is not within "stride" of the wrap value. | |
| 290 // | |
| 291 // Example for "short" type | |
| 292 // Truncation ensures value is in the range -32768..32767 (iv_trunc_t) | |
| 293 // If the stride is +10, then the last value of the induction | |
| 294 // variable before the increment (phi_ft->_hi) must be | |
| 295 // <= 32767 - 10 and (phi_ft->_lo) must be >= -32768 to | |
| 296 // ensure no truncation occurs after the increment. | |
| 297 | |
| 298 if (stride_con > 0) { | |
| 299 if (iv_trunc_t->_hi - phi_ft->_hi < stride_con || | |
| 300 iv_trunc_t->_lo > phi_ft->_lo) { | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
301 return false; // truncation may occur |
| 0 | 302 } |
| 303 } else if (stride_con < 0) { | |
| 304 if (iv_trunc_t->_lo - phi_ft->_lo > stride_con || | |
| 305 iv_trunc_t->_hi < phi_ft->_hi) { | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
306 return false; // truncation may occur |
| 0 | 307 } |
| 308 } | |
| 309 // No possibility of wrap so truncation can be discarded | |
| 310 // Promote iv type to Int | |
| 311 } else { | |
| 312 assert(trunc1 == NULL && trunc2 == NULL, "no truncation for int"); | |
| 313 } | |
| 314 | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
315 // If the condition is inverted and we will be rolling |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
316 // through MININT to MAXINT, then bail out. |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
317 if (bt == BoolTest::eq || // Bail out, but this loop trips at most twice! |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
318 // Odd stride |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
319 bt == BoolTest::ne && stride_con != 1 && stride_con != -1 || |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
320 // Count down loop rolls through MAXINT |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
321 (bt == BoolTest::le || bt == BoolTest::lt) && stride_con < 0 || |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
322 // Count up loop rolls through MININT |
| 3345 | 323 (bt == BoolTest::ge || bt == BoolTest::gt) && stride_con > 0) { |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
324 return false; // Bail out |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
325 } |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
326 |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
327 const TypeInt* init_t = gvn->type(init_trip)->is_int(); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
328 const TypeInt* limit_t = gvn->type(limit)->is_int(); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
329 |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
330 if (stride_con > 0) { |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
331 long init_p = (long)init_t->_lo + stride_con; |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
332 if (init_p > (long)max_jint || init_p > (long)limit_t->_hi) |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
333 return false; // cyclic loop or this loop trips only once |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
334 } else { |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
335 long init_p = (long)init_t->_hi + stride_con; |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
336 if (init_p < (long)min_jint || init_p < (long)limit_t->_lo) |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
337 return false; // cyclic loop or this loop trips only once |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
338 } |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
339 |
| 0 | 340 // ================================================= |
| 341 // ---- SUCCESS! Found A Trip-Counted Loop! ----- | |
| 342 // | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
343 assert(x->Opcode() == Op_Loop, "regular loops only"); |
| 0 | 344 C->print_method("Before CountedLoop", 3); |
| 3345 | 345 |
| 346 Node *hook = new (C, 6) Node(6); | |
| 347 | |
| 348 if (LoopLimitCheck) { | |
| 349 | |
| 350 // =================================================== | |
| 351 // Generate loop limit check to avoid integer overflow | |
| 352 // in cases like next (cyclic loops): | |
| 353 // | |
| 354 // for (i=0; i <= max_jint; i++) {} | |
| 355 // for (i=0; i < max_jint; i+=2) {} | |
| 356 // | |
| 357 // | |
| 358 // Limit check predicate depends on the loop test: | |
| 359 // | |
| 360 // for(;i != limit; i++) --> limit <= (max_jint) | |
| 361 // for(;i < limit; i+=stride) --> limit <= (max_jint - stride + 1) | |
| 362 // for(;i <= limit; i+=stride) --> limit <= (max_jint - stride ) | |
| 363 // | |
| 364 | |
| 365 // Check if limit is excluded to do more precise int overflow check. | |
| 366 bool incl_limit = (bt == BoolTest::le || bt == BoolTest::ge); | |
| 367 int stride_m = stride_con - (incl_limit ? 0 : (stride_con > 0 ? 1 : -1)); | |
| 368 | |
| 369 // If compare points directly to the phi we need to adjust | |
| 370 // the compare so that it points to the incr. Limit have | |
| 371 // to be adjusted to keep trip count the same and the | |
| 372 // adjusted limit should be checked for int overflow. | |
| 373 if (phi_incr != NULL) { | |
| 374 stride_m += stride_con; | |
| 375 } | |
| 376 | |
| 377 if (limit->is_Con()) { | |
| 378 int limit_con = limit->get_int(); | |
| 379 if ((stride_con > 0 && limit_con > (max_jint - stride_m)) || | |
| 380 (stride_con < 0 && limit_con < (min_jint - stride_m))) { | |
| 381 // Bailout: it could be integer overflow. | |
| 382 return false; | |
| 383 } | |
| 384 } else if ((stride_con > 0 && limit_t->_hi <= (max_jint - stride_m)) || | |
| 385 (stride_con < 0 && limit_t->_lo >= (min_jint - stride_m))) { | |
| 386 // Limit's type may satisfy the condition, for example, | |
| 387 // when it is an array length. | |
| 388 } else { | |
| 389 // Generate loop's limit check. | |
| 390 // Loop limit check predicate should be near the loop. | |
| 391 ProjNode *limit_check_proj = find_predicate_insertion_point(init_control, Deoptimization::Reason_loop_limit_check); | |
| 392 if (!limit_check_proj) { | |
| 393 // The limit check predicate is not generated if this method trapped here before. | |
| 394 #ifdef ASSERT | |
| 395 if (TraceLoopLimitCheck) { | |
| 396 tty->print("missing loop limit check:"); | |
| 397 loop->dump_head(); | |
| 398 x->dump(1); | |
| 399 } | |
| 400 #endif | |
| 401 return false; | |
| 402 } | |
| 403 | |
| 404 IfNode* check_iff = limit_check_proj->in(0)->as_If(); | |
| 405 Node* cmp_limit; | |
| 406 Node* bol; | |
| 407 | |
| 408 if (stride_con > 0) { | |
| 409 cmp_limit = new (C, 3) CmpINode(limit, _igvn.intcon(max_jint - stride_m)); | |
| 410 bol = new (C, 2) BoolNode(cmp_limit, BoolTest::le); | |
| 411 } else { | |
| 412 cmp_limit = new (C, 3) CmpINode(limit, _igvn.intcon(min_jint - stride_m)); | |
| 413 bol = new (C, 2) BoolNode(cmp_limit, BoolTest::ge); | |
| 414 } | |
| 415 cmp_limit = _igvn.register_new_node_with_optimizer(cmp_limit); | |
| 416 bol = _igvn.register_new_node_with_optimizer(bol); | |
| 417 set_subtree_ctrl(bol); | |
| 418 | |
| 419 // Replace condition in original predicate but preserve Opaque node | |
| 420 // so that previous predicates could be found. | |
| 421 assert(check_iff->in(1)->Opcode() == Op_Conv2B && | |
| 422 check_iff->in(1)->in(1)->Opcode() == Op_Opaque1, ""); | |
| 423 Node* opq = check_iff->in(1)->in(1); | |
| 424 _igvn.hash_delete(opq); | |
| 425 opq->set_req(1, bol); | |
| 426 // Update ctrl. | |
| 427 set_ctrl(opq, check_iff->in(0)); | |
| 428 set_ctrl(check_iff->in(1), check_iff->in(0)); | |
| 429 | |
| 2445 | 430 #ifndef PRODUCT |
| 3345 | 431 // report that the loop predication has been actually performed |
| 432 // for this loop | |
| 433 if (TraceLoopLimitCheck) { | |
| 434 tty->print_cr("Counted Loop Limit Check generated:"); | |
| 435 debug_only( bol->dump(2); ) | |
| 436 } | |
| 437 #endif | |
| 438 } | |
| 439 | |
| 440 if (phi_incr != NULL) { | |
| 441 // If compare points directly to the phi we need to adjust | |
| 442 // the compare so that it points to the incr. Limit have | |
| 443 // to be adjusted to keep trip count the same and we | |
| 444 // should avoid int overflow. | |
| 445 // | |
| 446 // i = init; do {} while(i++ < limit); | |
| 447 // is converted to | |
| 448 // i = init; do {} while(++i < limit+1); | |
| 449 // | |
| 450 limit = gvn->transform(new (C, 3) AddINode(limit, stride)); | |
| 2445 | 451 } |
| 3345 | 452 |
| 453 // Now we need to canonicalize loop condition. | |
| 454 if (bt == BoolTest::ne) { | |
| 455 assert(stride_con == 1 || stride_con == -1, "simple increment only"); | |
| 3782 | 456 // 'ne' can be replaced with 'lt' only when init < limit. |
| 457 if (stride_con > 0 && init_t->_hi < limit_t->_lo) | |
| 458 bt = BoolTest::lt; | |
| 459 // 'ne' can be replaced with 'gt' only when init > limit. | |
| 460 if (stride_con < 0 && init_t->_lo > limit_t->_hi) | |
| 461 bt = BoolTest::gt; | |
| 3345 | 462 } |
| 463 | |
| 464 if (incl_limit) { | |
| 465 // The limit check guaranties that 'limit <= (max_jint - stride)' so | |
| 466 // we can convert 'i <= limit' to 'i < limit+1' since stride != 0. | |
| 467 // | |
| 468 Node* one = (stride_con > 0) ? gvn->intcon( 1) : gvn->intcon(-1); | |
| 469 limit = gvn->transform(new (C, 3) AddINode(limit, one)); | |
| 470 if (bt == BoolTest::le) | |
| 471 bt = BoolTest::lt; | |
| 472 else if (bt == BoolTest::ge) | |
| 473 bt = BoolTest::gt; | |
| 474 else | |
| 475 ShouldNotReachHere(); | |
| 476 } | |
| 477 set_subtree_ctrl( limit ); | |
| 478 | |
| 479 } else { // LoopLimitCheck | |
| 480 | |
| 0 | 481 // If compare points to incr, we are ok. Otherwise the compare |
| 482 // can directly point to the phi; in this case adjust the compare so that | |
| 605 | 483 // it points to the incr by adjusting the limit. |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
484 if (cmp->in(1) == phi || cmp->in(2) == phi) |
| 0 | 485 limit = gvn->transform(new (C, 3) AddINode(limit,stride)); |
| 486 | |
| 487 // trip-count for +-tive stride should be: (limit - init_trip + stride - 1)/stride. | |
| 488 // Final value for iterator should be: trip_count * stride + init_trip. | |
| 489 Node *one_p = gvn->intcon( 1); | |
| 490 Node *one_m = gvn->intcon(-1); | |
| 491 | |
| 492 Node *trip_count = NULL; | |
| 493 switch( bt ) { | |
| 494 case BoolTest::eq: | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
495 ShouldNotReachHere(); |
| 0 | 496 case BoolTest::ne: // Ahh, the case we desire |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
497 if (stride_con == 1) |
| 0 | 498 trip_count = gvn->transform(new (C, 3) SubINode(limit,init_trip)); |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
499 else if (stride_con == -1) |
| 0 | 500 trip_count = gvn->transform(new (C, 3) SubINode(init_trip,limit)); |
| 501 else | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
502 ShouldNotReachHere(); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
503 set_subtree_ctrl(trip_count); |
| 0 | 504 //_loop.map(trip_count->_idx,loop(limit)); |
| 505 break; | |
| 506 case BoolTest::le: // Maybe convert to '<' case | |
| 507 limit = gvn->transform(new (C, 3) AddINode(limit,one_p)); | |
| 508 set_subtree_ctrl( limit ); | |
| 509 hook->init_req(4, limit); | |
| 510 | |
| 511 bt = BoolTest::lt; | |
| 512 // Make the new limit be in the same loop nest as the old limit | |
| 513 //_loop.map(limit->_idx,limit_loop); | |
| 514 // Fall into next case | |
| 515 case BoolTest::lt: { // Maybe convert to '!=' case | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
516 if (stride_con < 0) // Count down loop rolls through MAXINT |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
517 ShouldNotReachHere(); |
| 0 | 518 Node *range = gvn->transform(new (C, 3) SubINode(limit,init_trip)); |
| 519 set_subtree_ctrl( range ); | |
| 520 hook->init_req(0, range); | |
| 521 | |
| 522 Node *bias = gvn->transform(new (C, 3) AddINode(range,stride)); | |
| 523 set_subtree_ctrl( bias ); | |
| 524 hook->init_req(1, bias); | |
| 525 | |
| 526 Node *bias1 = gvn->transform(new (C, 3) AddINode(bias,one_m)); | |
| 527 set_subtree_ctrl( bias1 ); | |
| 528 hook->init_req(2, bias1); | |
| 529 | |
| 530 trip_count = gvn->transform(new (C, 3) DivINode(0,bias1,stride)); | |
| 531 set_subtree_ctrl( trip_count ); | |
| 532 hook->init_req(3, trip_count); | |
| 533 break; | |
| 534 } | |
| 535 | |
| 536 case BoolTest::ge: // Maybe convert to '>' case | |
| 537 limit = gvn->transform(new (C, 3) AddINode(limit,one_m)); | |
| 538 set_subtree_ctrl( limit ); | |
| 539 hook->init_req(4 ,limit); | |
| 540 | |
| 541 bt = BoolTest::gt; | |
| 542 // Make the new limit be in the same loop nest as the old limit | |
| 543 //_loop.map(limit->_idx,limit_loop); | |
| 544 // Fall into next case | |
| 545 case BoolTest::gt: { // Maybe convert to '!=' case | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
546 if (stride_con > 0) // count up loop rolls through MININT |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
547 ShouldNotReachHere(); |
| 0 | 548 Node *range = gvn->transform(new (C, 3) SubINode(limit,init_trip)); |
| 549 set_subtree_ctrl( range ); | |
| 550 hook->init_req(0, range); | |
| 551 | |
| 552 Node *bias = gvn->transform(new (C, 3) AddINode(range,stride)); | |
| 553 set_subtree_ctrl( bias ); | |
| 554 hook->init_req(1, bias); | |
| 555 | |
| 556 Node *bias1 = gvn->transform(new (C, 3) AddINode(bias,one_p)); | |
| 557 set_subtree_ctrl( bias1 ); | |
| 558 hook->init_req(2, bias1); | |
| 559 | |
| 560 trip_count = gvn->transform(new (C, 3) DivINode(0,bias1,stride)); | |
| 561 set_subtree_ctrl( trip_count ); | |
| 562 hook->init_req(3, trip_count); | |
| 563 break; | |
| 564 } | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
565 } // switch( bt ) |
| 0 | 566 |
| 567 Node *span = gvn->transform(new (C, 3) MulINode(trip_count,stride)); | |
| 568 set_subtree_ctrl( span ); | |
| 569 hook->init_req(5, span); | |
| 570 | |
| 571 limit = gvn->transform(new (C, 3) AddINode(span,init_trip)); | |
| 572 set_subtree_ctrl( limit ); | |
| 573 | |
| 3345 | 574 } // LoopLimitCheck |
| 575 | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
576 // Check for SafePoint on backedge and remove |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
577 Node *sfpt = x->in(LoopNode::LoopBackControl); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
578 if (sfpt->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt)) { |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
579 lazy_replace( sfpt, iftrue ); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
580 loop->_tail = iftrue; |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
581 } |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
582 |
| 0 | 583 // Build a canonical trip test. |
| 584 // Clone code, as old values may be in use. | |
| 585 incr = incr->clone(); | |
|
3936
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
586 incr->set_req(1,phi); |
| 0 | 587 incr->set_req(2,stride); |
| 588 incr = _igvn.register_new_node_with_optimizer(incr); | |
| 589 set_early_ctrl( incr ); | |
|
3936
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
590 _igvn.hash_delete(phi); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
591 phi->set_req_X( LoopNode::LoopBackControl, incr, &_igvn ); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
592 |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
593 // If phi type is more restrictive than Int, raise to |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
594 // Int to prevent (almost) infinite recursion in igvn |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
595 // which can only handle integer types for constants or minint..maxint. |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
596 if (!TypeInt::INT->higher_equal(phi->bottom_type())) { |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
597 Node* nphi = PhiNode::make(phi->in(0), phi->in(LoopNode::EntryControl), TypeInt::INT); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
598 nphi->set_req(LoopNode::LoopBackControl, phi->in(LoopNode::LoopBackControl)); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
599 nphi = _igvn.register_new_node_with_optimizer(nphi); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
600 set_ctrl(nphi, get_ctrl(phi)); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
601 _igvn.replace_node(phi, nphi); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
602 phi = nphi->as_Phi(); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
603 } |
| 0 | 604 cmp = cmp->clone(); |
| 605 cmp->set_req(1,incr); | |
| 606 cmp->set_req(2,limit); | |
| 607 cmp = _igvn.register_new_node_with_optimizer(cmp); | |
| 608 set_ctrl(cmp, iff->in(0)); | |
| 609 | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
610 test = test->clone()->as_Bool(); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
611 (*(BoolTest*)&test->_test)._test = bt; |
| 0 | 612 test->set_req(1,cmp); |
| 613 _igvn.register_new_node_with_optimizer(test); | |
| 614 set_ctrl(test, iff->in(0)); | |
| 615 | |
| 616 // Replace the old IfNode with a new LoopEndNode | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
617 Node *lex = _igvn.register_new_node_with_optimizer(new (C, 2) CountedLoopEndNode( iff->in(0), test, cl_prob, iff->as_If()->_fcnt )); |
| 0 | 618 IfNode *le = lex->as_If(); |
| 619 uint dd = dom_depth(iff); | |
| 620 set_idom(le, le->in(0), dd); // Update dominance for loop exit | |
| 621 set_loop(le, loop); | |
| 622 | |
| 623 // Get the loop-exit control | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
624 Node *iffalse = iff->as_If()->proj_out(!(iftrue_op == Op_IfTrue)); |
| 0 | 625 |
| 626 // Need to swap loop-exit and loop-back control? | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
627 if (iftrue_op == Op_IfFalse) { |
| 0 | 628 Node *ift2=_igvn.register_new_node_with_optimizer(new (C, 1) IfTrueNode (le)); |
| 629 Node *iff2=_igvn.register_new_node_with_optimizer(new (C, 1) IfFalseNode(le)); | |
| 630 | |
| 631 loop->_tail = back_control = ift2; | |
| 632 set_loop(ift2, loop); | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
633 set_loop(iff2, get_loop(iffalse)); |
| 0 | 634 |
| 635 // Lazy update of 'get_ctrl' mechanism. | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
636 lazy_replace_proj( iffalse, iff2 ); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
637 lazy_replace_proj( iftrue, ift2 ); |
| 0 | 638 |
| 639 // Swap names | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
640 iffalse = iff2; |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
641 iftrue = ift2; |
| 0 | 642 } else { |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
643 _igvn.hash_delete(iffalse); |
| 0 | 644 _igvn.hash_delete(iftrue); |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
645 iffalse->set_req_X( 0, le, &_igvn ); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
646 iftrue ->set_req_X( 0, le, &_igvn ); |
| 0 | 647 } |
| 648 | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
649 set_idom(iftrue, le, dd+1); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
650 set_idom(iffalse, le, dd+1); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
651 assert(iff->outcnt() == 0, "should be dead now"); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
652 lazy_replace( iff, le ); // fix 'get_ctrl' |
| 0 | 653 |
| 654 // Now setup a new CountedLoopNode to replace the existing LoopNode | |
| 655 CountedLoopNode *l = new (C, 3) CountedLoopNode(init_control, back_control); | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
656 l->set_unswitch_count(x->as_Loop()->unswitch_count()); // Preserve |
| 0 | 657 // The following assert is approximately true, and defines the intention |
| 658 // of can_be_counted_loop. It fails, however, because phase->type | |
| 659 // is not yet initialized for this loop and its parts. | |
| 660 //assert(l->can_be_counted_loop(this), "sanity"); | |
| 661 _igvn.register_new_node_with_optimizer(l); | |
| 662 set_loop(l, loop); | |
| 663 loop->_head = l; | |
| 664 // Fix all data nodes placed at the old loop head. | |
| 665 // Uses the lazy-update mechanism of 'get_ctrl'. | |
| 666 lazy_replace( x, l ); | |
| 667 set_idom(l, init_control, dom_depth(x)); | |
| 668 | |
| 605 | 669 // Check for immediately preceding SafePoint and remove |
| 0 | 670 Node *sfpt2 = le->in(0); |
| 3345 | 671 if (sfpt2->Opcode() == Op_SafePoint && is_deleteable_safept(sfpt2)) |
| 0 | 672 lazy_replace( sfpt2, sfpt2->in(TypeFunc::Control)); |
| 673 | |
| 674 // Free up intermediate goo | |
| 675 _igvn.remove_dead_node(hook); | |
| 676 | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
677 #ifdef ASSERT |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
678 assert(l->is_valid_counted_loop(), "counted loop shape is messed up"); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
679 assert(l == loop->_head && l->phi() == phi && l->loopexit() == lex, "" ); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
680 #endif |
| 3345 | 681 #ifndef PRODUCT |
| 682 if (TraceLoopOpts) { | |
| 683 tty->print("Counted "); | |
| 684 loop->dump_head(); | |
| 685 } | |
| 686 #endif | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
687 |
| 0 | 688 C->print_method("After CountedLoop", 3); |
| 689 | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
690 return true; |
| 0 | 691 } |
| 692 | |
| 3345 | 693 //----------------------exact_limit------------------------------------------- |
| 694 Node* PhaseIdealLoop::exact_limit( IdealLoopTree *loop ) { | |
| 695 assert(loop->_head->is_CountedLoop(), ""); | |
| 696 CountedLoopNode *cl = loop->_head->as_CountedLoop(); | |
|
3850
6987871cfb9b
7077439: Possible reference through NULL in loopPredicate.cpp:726
kvn
parents:
3845
diff
changeset
|
697 assert(cl->is_valid_counted_loop(), ""); |
| 3345 | 698 |
| 699 if (!LoopLimitCheck || ABS(cl->stride_con()) == 1 || | |
| 700 cl->limit()->Opcode() == Op_LoopLimit) { | |
| 701 // Old code has exact limit (it could be incorrect in case of int overflow). | |
| 702 // Loop limit is exact with stride == 1. And loop may already have exact limit. | |
| 703 return cl->limit(); | |
| 704 } | |
| 705 Node *limit = NULL; | |
| 706 #ifdef ASSERT | |
| 707 BoolTest::mask bt = cl->loopexit()->test_trip(); | |
| 708 assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected"); | |
| 709 #endif | |
| 710 if (cl->has_exact_trip_count()) { | |
| 711 // Simple case: loop has constant boundaries. | |
| 712 // Use longs to avoid integer overflow. | |
| 713 int stride_con = cl->stride_con(); | |
| 714 long init_con = cl->init_trip()->get_int(); | |
| 715 long limit_con = cl->limit()->get_int(); | |
| 716 julong trip_cnt = cl->trip_count(); | |
| 717 long final_con = init_con + trip_cnt*stride_con; | |
| 718 final_con -= stride_con; | |
| 719 int final_int = (int)final_con; | |
| 720 // The final value should be in integer range since the loop | |
| 721 // is counted and the limit was checked for overflow. | |
| 722 assert(final_con == (long)final_int, "final value should be integer"); | |
| 723 limit = _igvn.intcon(final_int); | |
| 724 } else { | |
| 725 // Create new LoopLimit node to get exact limit (final iv value). | |
| 726 limit = new (C, 4) LoopLimitNode(C, cl->init_trip(), cl->limit(), cl->stride()); | |
| 727 register_new_node(limit, cl->in(LoopNode::EntryControl)); | |
| 728 } | |
| 729 assert(limit != NULL, "sanity"); | |
| 730 return limit; | |
| 731 } | |
| 0 | 732 |
| 733 //------------------------------Ideal------------------------------------------ | |
| 734 // Return a node which is more "ideal" than the current node. | |
| 735 // Attempt to convert into a counted-loop. | |
| 736 Node *LoopNode::Ideal(PhaseGVN *phase, bool can_reshape) { | |
| 737 if (!can_be_counted_loop(phase)) { | |
| 738 phase->C->set_major_progress(); | |
| 739 } | |
| 740 return RegionNode::Ideal(phase, can_reshape); | |
| 741 } | |
| 742 | |
| 743 | |
| 744 //============================================================================= | |
| 745 //------------------------------Ideal------------------------------------------ | |
| 746 // Return a node which is more "ideal" than the current node. | |
| 747 // Attempt to convert into a counted-loop. | |
| 748 Node *CountedLoopNode::Ideal(PhaseGVN *phase, bool can_reshape) { | |
| 749 return RegionNode::Ideal(phase, can_reshape); | |
| 750 } | |
| 751 | |
| 752 //------------------------------dump_spec-------------------------------------- | |
| 753 // Dump special per-node info | |
| 754 #ifndef PRODUCT | |
| 755 void CountedLoopNode::dump_spec(outputStream *st) const { | |
| 756 LoopNode::dump_spec(st); | |
| 3345 | 757 if (stride_is_con()) { |
| 0 | 758 st->print("stride: %d ",stride_con()); |
| 759 } | |
| 3345 | 760 if (is_pre_loop ()) st->print("pre of N%d" , _main_idx); |
| 761 if (is_main_loop()) st->print("main of N%d", _idx); | |
| 762 if (is_post_loop()) st->print("post of N%d", _main_idx); | |
| 0 | 763 } |
| 764 #endif | |
| 765 | |
| 766 //============================================================================= | |
| 767 int CountedLoopEndNode::stride_con() const { | |
| 768 return stride()->bottom_type()->is_int()->get_con(); | |
| 769 } | |
| 770 | |
| 3345 | 771 //============================================================================= |
| 772 //------------------------------Value----------------------------------------- | |
| 773 const Type *LoopLimitNode::Value( PhaseTransform *phase ) const { | |
| 774 const Type* init_t = phase->type(in(Init)); | |
| 775 const Type* limit_t = phase->type(in(Limit)); | |
| 776 const Type* stride_t = phase->type(in(Stride)); | |
| 777 // Either input is TOP ==> the result is TOP | |
| 778 if (init_t == Type::TOP) return Type::TOP; | |
| 779 if (limit_t == Type::TOP) return Type::TOP; | |
| 780 if (stride_t == Type::TOP) return Type::TOP; | |
| 781 | |
| 782 int stride_con = stride_t->is_int()->get_con(); | |
| 783 if (stride_con == 1) | |
| 784 return NULL; // Identity | |
| 785 | |
| 786 if (init_t->is_int()->is_con() && limit_t->is_int()->is_con()) { | |
| 787 // Use longs to avoid integer overflow. | |
| 788 long init_con = init_t->is_int()->get_con(); | |
| 789 long limit_con = limit_t->is_int()->get_con(); | |
| 790 int stride_m = stride_con - (stride_con > 0 ? 1 : -1); | |
| 791 long trip_count = (limit_con - init_con + stride_m)/stride_con; | |
| 792 long final_con = init_con + stride_con*trip_count; | |
| 793 int final_int = (int)final_con; | |
| 794 // The final value should be in integer range since the loop | |
| 795 // is counted and the limit was checked for overflow. | |
| 796 assert(final_con == (long)final_int, "final value should be integer"); | |
| 797 return TypeInt::make(final_int); | |
| 798 } | |
| 799 | |
| 800 return bottom_type(); // TypeInt::INT | |
| 801 } | |
| 802 | |
| 803 //------------------------------Ideal------------------------------------------ | |
| 804 // Return a node which is more "ideal" than the current node. | |
| 805 Node *LoopLimitNode::Ideal(PhaseGVN *phase, bool can_reshape) { | |
| 806 if (phase->type(in(Init)) == Type::TOP || | |
| 807 phase->type(in(Limit)) == Type::TOP || | |
| 808 phase->type(in(Stride)) == Type::TOP) | |
| 809 return NULL; // Dead | |
| 810 | |
| 811 int stride_con = phase->type(in(Stride))->is_int()->get_con(); | |
| 812 if (stride_con == 1) | |
| 813 return NULL; // Identity | |
| 814 | |
| 815 if (in(Init)->is_Con() && in(Limit)->is_Con()) | |
| 816 return NULL; // Value | |
| 817 | |
| 818 // Delay following optimizations until all loop optimizations | |
| 819 // done to keep Ideal graph simple. | |
| 820 if (!can_reshape || phase->C->major_progress()) | |
| 821 return NULL; | |
| 822 | |
| 823 const TypeInt* init_t = phase->type(in(Init) )->is_int(); | |
| 824 const TypeInt* limit_t = phase->type(in(Limit))->is_int(); | |
| 825 int stride_p; | |
| 826 long lim, ini; | |
| 827 julong max; | |
| 828 if (stride_con > 0) { | |
| 829 stride_p = stride_con; | |
| 830 lim = limit_t->_hi; | |
| 831 ini = init_t->_lo; | |
| 832 max = (julong)max_jint; | |
| 833 } else { | |
| 834 stride_p = -stride_con; | |
| 835 lim = init_t->_hi; | |
| 836 ini = limit_t->_lo; | |
| 837 max = (julong)min_jint; | |
| 838 } | |
| 839 julong range = lim - ini + stride_p; | |
| 840 if (range <= max) { | |
| 841 // Convert to integer expression if it is not overflow. | |
| 842 Node* stride_m = phase->intcon(stride_con - (stride_con > 0 ? 1 : -1)); | |
| 843 Node *range = phase->transform(new (phase->C, 3) SubINode(in(Limit), in(Init))); | |
| 844 Node *bias = phase->transform(new (phase->C, 3) AddINode(range, stride_m)); | |
| 845 Node *trip = phase->transform(new (phase->C, 3) DivINode(0, bias, in(Stride))); | |
| 846 Node *span = phase->transform(new (phase->C, 3) MulINode(trip, in(Stride))); | |
| 847 return new (phase->C, 3) AddINode(span, in(Init)); // exact limit | |
| 848 } | |
| 849 | |
| 850 if (is_power_of_2(stride_p) || // divisor is 2^n | |
| 851 !Matcher::has_match_rule(Op_LoopLimit)) { // or no specialized Mach node? | |
| 852 // Convert to long expression to avoid integer overflow | |
| 853 // and let igvn optimizer convert this division. | |
| 854 // | |
| 855 Node* init = phase->transform( new (phase->C, 2) ConvI2LNode(in(Init))); | |
| 856 Node* limit = phase->transform( new (phase->C, 2) ConvI2LNode(in(Limit))); | |
| 857 Node* stride = phase->longcon(stride_con); | |
| 858 Node* stride_m = phase->longcon(stride_con - (stride_con > 0 ? 1 : -1)); | |
| 859 | |
| 860 Node *range = phase->transform(new (phase->C, 3) SubLNode(limit, init)); | |
| 861 Node *bias = phase->transform(new (phase->C, 3) AddLNode(range, stride_m)); | |
| 862 Node *span; | |
| 863 if (stride_con > 0 && is_power_of_2(stride_p)) { | |
| 864 // bias >= 0 if stride >0, so if stride is 2^n we can use &(-stride) | |
| 865 // and avoid generating rounding for division. Zero trip guard should | |
| 866 // guarantee that init < limit but sometimes the guard is missing and | |
| 867 // we can get situation when init > limit. Note, for the empty loop | |
| 868 // optimization zero trip guard is generated explicitly which leaves | |
| 869 // only RCE predicate where exact limit is used and the predicate | |
| 870 // will simply fail forcing recompilation. | |
| 871 Node* neg_stride = phase->longcon(-stride_con); | |
| 872 span = phase->transform(new (phase->C, 3) AndLNode(bias, neg_stride)); | |
| 873 } else { | |
| 874 Node *trip = phase->transform(new (phase->C, 3) DivLNode(0, bias, stride)); | |
| 875 span = phase->transform(new (phase->C, 3) MulLNode(trip, stride)); | |
| 876 } | |
| 877 // Convert back to int | |
| 878 Node *span_int = phase->transform(new (phase->C, 2) ConvL2INode(span)); | |
| 879 return new (phase->C, 3) AddINode(span_int, in(Init)); // exact limit | |
| 880 } | |
| 881 | |
| 882 return NULL; // No progress | |
| 883 } | |
| 884 | |
| 885 //------------------------------Identity--------------------------------------- | |
| 886 // If stride == 1 return limit node. | |
| 887 Node *LoopLimitNode::Identity( PhaseTransform *phase ) { | |
| 888 int stride_con = phase->type(in(Stride))->is_int()->get_con(); | |
| 889 if (stride_con == 1 || stride_con == -1) | |
| 890 return in(Limit); | |
| 891 return this; | |
| 892 } | |
| 893 | |
| 894 //============================================================================= | |
| 0 | 895 //----------------------match_incr_with_optional_truncation-------------------- |
| 896 // Match increment with optional truncation: | |
| 897 // CHAR: (i+1)&0x7fff, BYTE: ((i+1)<<8)>>8, or SHORT: ((i+1)<<16)>>16 | |
| 898 // Return NULL for failure. Success returns the increment node. | |
| 899 Node* CountedLoopNode::match_incr_with_optional_truncation( | |
| 900 Node* expr, Node** trunc1, Node** trunc2, const TypeInt** trunc_type) { | |
| 901 // Quick cutouts: | |
| 902 if (expr == NULL || expr->req() != 3) return false; | |
| 903 | |
| 904 Node *t1 = NULL; | |
| 905 Node *t2 = NULL; | |
| 906 const TypeInt* trunc_t = TypeInt::INT; | |
| 907 Node* n1 = expr; | |
| 908 int n1op = n1->Opcode(); | |
| 909 | |
| 910 // Try to strip (n1 & M) or (n1 << N >> N) from n1. | |
| 911 if (n1op == Op_AndI && | |
| 912 n1->in(2)->is_Con() && | |
| 913 n1->in(2)->bottom_type()->is_int()->get_con() == 0x7fff) { | |
| 914 // %%% This check should match any mask of 2**K-1. | |
| 915 t1 = n1; | |
| 916 n1 = t1->in(1); | |
| 917 n1op = n1->Opcode(); | |
| 918 trunc_t = TypeInt::CHAR; | |
| 919 } else if (n1op == Op_RShiftI && | |
| 920 n1->in(1) != NULL && | |
| 921 n1->in(1)->Opcode() == Op_LShiftI && | |
| 922 n1->in(2) == n1->in(1)->in(2) && | |
| 923 n1->in(2)->is_Con()) { | |
| 924 jint shift = n1->in(2)->bottom_type()->is_int()->get_con(); | |
| 925 // %%% This check should match any shift in [1..31]. | |
| 926 if (shift == 16 || shift == 8) { | |
| 927 t1 = n1; | |
| 928 t2 = t1->in(1); | |
| 929 n1 = t2->in(1); | |
| 930 n1op = n1->Opcode(); | |
| 931 if (shift == 16) { | |
| 932 trunc_t = TypeInt::SHORT; | |
| 933 } else if (shift == 8) { | |
| 934 trunc_t = TypeInt::BYTE; | |
| 935 } | |
| 936 } | |
| 937 } | |
| 938 | |
| 939 // If (maybe after stripping) it is an AddI, we won: | |
| 940 if (n1op == Op_AddI) { | |
| 941 *trunc1 = t1; | |
| 942 *trunc2 = t2; | |
| 943 *trunc_type = trunc_t; | |
| 944 return n1; | |
| 945 } | |
| 946 | |
| 947 // failed | |
| 948 return NULL; | |
| 949 } | |
| 950 | |
| 951 | |
| 952 //------------------------------filtered_type-------------------------------- | |
| 953 // Return a type based on condition control flow | |
| 954 // A successful return will be a type that is restricted due | |
| 955 // to a series of dominating if-tests, such as: | |
| 956 // if (i < 10) { | |
| 957 // if (i > 0) { | |
| 958 // here: "i" type is [1..10) | |
| 959 // } | |
| 960 // } | |
| 961 // or a control flow merge | |
| 962 // if (i < 10) { | |
| 963 // do { | |
| 964 // phi( , ) -- at top of loop type is [min_int..10) | |
| 965 // i = ? | |
| 966 // } while ( i < 10) | |
| 967 // | |
| 968 const TypeInt* PhaseIdealLoop::filtered_type( Node *n, Node* n_ctrl) { | |
| 969 assert(n && n->bottom_type()->is_int(), "must be int"); | |
| 970 const TypeInt* filtered_t = NULL; | |
| 971 if (!n->is_Phi()) { | |
| 972 assert(n_ctrl != NULL || n_ctrl == C->top(), "valid control"); | |
| 973 filtered_t = filtered_type_from_dominators(n, n_ctrl); | |
| 974 | |
| 975 } else { | |
| 976 Node* phi = n->as_Phi(); | |
| 977 Node* region = phi->in(0); | |
| 978 assert(n_ctrl == NULL || n_ctrl == region, "ctrl parameter must be region"); | |
| 979 if (region && region != C->top()) { | |
| 980 for (uint i = 1; i < phi->req(); i++) { | |
| 981 Node* val = phi->in(i); | |
| 982 Node* use_c = region->in(i); | |
| 983 const TypeInt* val_t = filtered_type_from_dominators(val, use_c); | |
| 984 if (val_t != NULL) { | |
| 985 if (filtered_t == NULL) { | |
| 986 filtered_t = val_t; | |
| 987 } else { | |
| 988 filtered_t = filtered_t->meet(val_t)->is_int(); | |
| 989 } | |
| 990 } | |
| 991 } | |
| 992 } | |
| 993 } | |
| 994 const TypeInt* n_t = _igvn.type(n)->is_int(); | |
| 995 if (filtered_t != NULL) { | |
| 996 n_t = n_t->join(filtered_t)->is_int(); | |
| 997 } | |
| 998 return n_t; | |
| 999 } | |
| 1000 | |
| 1001 | |
| 1002 //------------------------------filtered_type_from_dominators-------------------------------- | |
| 1003 // Return a possibly more restrictive type for val based on condition control flow of dominators | |
| 1004 const TypeInt* PhaseIdealLoop::filtered_type_from_dominators( Node* val, Node *use_ctrl) { | |
| 1005 if (val->is_Con()) { | |
| 1006 return val->bottom_type()->is_int(); | |
| 1007 } | |
| 1008 uint if_limit = 10; // Max number of dominating if's visited | |
| 1009 const TypeInt* rtn_t = NULL; | |
| 1010 | |
| 1011 if (use_ctrl && use_ctrl != C->top()) { | |
| 1012 Node* val_ctrl = get_ctrl(val); | |
| 1013 uint val_dom_depth = dom_depth(val_ctrl); | |
| 1014 Node* pred = use_ctrl; | |
| 1015 uint if_cnt = 0; | |
| 1016 while (if_cnt < if_limit) { | |
| 1017 if ((pred->Opcode() == Op_IfTrue || pred->Opcode() == Op_IfFalse)) { | |
| 1018 if_cnt++; | |
|
17
ff5961f4c095
6395208: Elide autoboxing for calls to HashMap.get(int) and HashMap.get(long)
never
parents:
0
diff
changeset
|
1019 const TypeInt* if_t = IfNode::filtered_int_type(&_igvn, val, pred); |
| 0 | 1020 if (if_t != NULL) { |
| 1021 if (rtn_t == NULL) { | |
| 1022 rtn_t = if_t; | |
| 1023 } else { | |
| 1024 rtn_t = rtn_t->join(if_t)->is_int(); | |
| 1025 } | |
| 1026 } | |
| 1027 } | |
| 1028 pred = idom(pred); | |
| 1029 if (pred == NULL || pred == C->top()) { | |
| 1030 break; | |
| 1031 } | |
| 1032 // Stop if going beyond definition block of val | |
| 1033 if (dom_depth(pred) < val_dom_depth) { | |
| 1034 break; | |
| 1035 } | |
| 1036 } | |
| 1037 } | |
| 1038 return rtn_t; | |
| 1039 } | |
| 1040 | |
| 1041 | |
| 1042 //------------------------------dump_spec-------------------------------------- | |
| 1043 // Dump special per-node info | |
| 1044 #ifndef PRODUCT | |
| 1045 void CountedLoopEndNode::dump_spec(outputStream *st) const { | |
| 1046 if( in(TestValue)->is_Bool() ) { | |
| 1047 BoolTest bt( test_trip()); // Added this for g++. | |
| 1048 | |
| 1049 st->print("["); | |
| 1050 bt.dump_on(st); | |
| 1051 st->print("]"); | |
| 1052 } | |
| 1053 st->print(" "); | |
| 1054 IfNode::dump_spec(st); | |
| 1055 } | |
| 1056 #endif | |
| 1057 | |
| 1058 //============================================================================= | |
| 1059 //------------------------------is_member-------------------------------------- | |
| 1060 // Is 'l' a member of 'this'? | |
| 1061 int IdealLoopTree::is_member( const IdealLoopTree *l ) const { | |
| 1062 while( l->_nest > _nest ) l = l->_parent; | |
| 1063 return l == this; | |
| 1064 } | |
| 1065 | |
| 1066 //------------------------------set_nest--------------------------------------- | |
| 1067 // Set loop tree nesting depth. Accumulate _has_call bits. | |
| 1068 int IdealLoopTree::set_nest( uint depth ) { | |
| 1069 _nest = depth; | |
| 1070 int bits = _has_call; | |
| 1071 if( _child ) bits |= _child->set_nest(depth+1); | |
| 1072 if( bits ) _has_call = 1; | |
| 1073 if( _next ) bits |= _next ->set_nest(depth ); | |
| 1074 return bits; | |
| 1075 } | |
| 1076 | |
| 1077 //------------------------------split_fall_in---------------------------------- | |
| 1078 // Split out multiple fall-in edges from the loop header. Move them to a | |
| 1079 // private RegionNode before the loop. This becomes the loop landing pad. | |
| 1080 void IdealLoopTree::split_fall_in( PhaseIdealLoop *phase, int fall_in_cnt ) { | |
| 1081 PhaseIterGVN &igvn = phase->_igvn; | |
| 1082 uint i; | |
| 1083 | |
| 1084 // Make a new RegionNode to be the landing pad. | |
| 1085 Node *landing_pad = new (phase->C, fall_in_cnt+1) RegionNode( fall_in_cnt+1 ); | |
| 1086 phase->set_loop(landing_pad,_parent); | |
| 1087 // Gather all the fall-in control paths into the landing pad | |
| 1088 uint icnt = fall_in_cnt; | |
| 1089 uint oreq = _head->req(); | |
| 1090 for( i = oreq-1; i>0; i-- ) | |
| 1091 if( !phase->is_member( this, _head->in(i) ) ) | |
| 1092 landing_pad->set_req(icnt--,_head->in(i)); | |
| 1093 | |
| 1094 // Peel off PhiNode edges as well | |
| 1095 for (DUIterator_Fast jmax, j = _head->fast_outs(jmax); j < jmax; j++) { | |
| 1096 Node *oj = _head->fast_out(j); | |
| 1097 if( oj->is_Phi() ) { | |
| 1098 PhiNode* old_phi = oj->as_Phi(); | |
| 1099 assert( old_phi->region() == _head, "" ); | |
| 1100 igvn.hash_delete(old_phi); // Yank from hash before hacking edges | |
| 1101 Node *p = PhiNode::make_blank(landing_pad, old_phi); | |
| 1102 uint icnt = fall_in_cnt; | |
| 1103 for( i = oreq-1; i>0; i-- ) { | |
| 1104 if( !phase->is_member( this, _head->in(i) ) ) { | |
| 1105 p->init_req(icnt--, old_phi->in(i)); | |
| 1106 // Go ahead and clean out old edges from old phi | |
| 1107 old_phi->del_req(i); | |
| 1108 } | |
| 1109 } | |
| 1110 // Search for CSE's here, because ZKM.jar does a lot of | |
| 1111 // loop hackery and we need to be a little incremental | |
| 1112 // with the CSE to avoid O(N^2) node blow-up. | |
| 1113 Node *p2 = igvn.hash_find_insert(p); // Look for a CSE | |
| 1114 if( p2 ) { // Found CSE | |
| 1115 p->destruct(); // Recover useless new node | |
| 1116 p = p2; // Use old node | |
| 1117 } else { | |
| 1118 igvn.register_new_node_with_optimizer(p, old_phi); | |
| 1119 } | |
| 1120 // Make old Phi refer to new Phi. | |
| 1121 old_phi->add_req(p); | |
| 1122 // Check for the special case of making the old phi useless and | |
| 1123 // disappear it. In JavaGrande I have a case where this useless | |
| 1124 // Phi is the loop limit and prevents recognizing a CountedLoop | |
| 1125 // which in turn prevents removing an empty loop. | |
| 1126 Node *id_old_phi = old_phi->Identity( &igvn ); | |
| 1127 if( id_old_phi != old_phi ) { // Found a simple identity? | |
|
1621
6027dddc26c6
6677629: PhaseIterGVN::subsume_node() should call hash_delete() and add_users_to_worklist()
kvn
parents:
1552
diff
changeset
|
1128 // Note that I cannot call 'replace_node' here, because |
| 0 | 1129 // that will yank the edge from old_phi to the Region and |
| 1130 // I'm mid-iteration over the Region's uses. | |
| 1131 for (DUIterator_Last imin, i = old_phi->last_outs(imin); i >= imin; ) { | |
| 1132 Node* use = old_phi->last_out(i); | |
| 1133 igvn.hash_delete(use); | |
| 1134 igvn._worklist.push(use); | |
| 1135 uint uses_found = 0; | |
| 1136 for (uint j = 0; j < use->len(); j++) { | |
| 1137 if (use->in(j) == old_phi) { | |
| 1138 if (j < use->req()) use->set_req (j, id_old_phi); | |
| 1139 else use->set_prec(j, id_old_phi); | |
| 1140 uses_found++; | |
| 1141 } | |
| 1142 } | |
| 1143 i -= uses_found; // we deleted 1 or more copies of this edge | |
| 1144 } | |
| 1145 } | |
| 1146 igvn._worklist.push(old_phi); | |
| 1147 } | |
| 1148 } | |
| 1149 // Finally clean out the fall-in edges from the RegionNode | |
| 1150 for( i = oreq-1; i>0; i-- ) { | |
| 1151 if( !phase->is_member( this, _head->in(i) ) ) { | |
| 1152 _head->del_req(i); | |
| 1153 } | |
| 1154 } | |
| 1155 // Transform landing pad | |
| 1156 igvn.register_new_node_with_optimizer(landing_pad, _head); | |
| 1157 // Insert landing pad into the header | |
| 1158 _head->add_req(landing_pad); | |
| 1159 } | |
| 1160 | |
| 1161 //------------------------------split_outer_loop------------------------------- | |
| 1162 // Split out the outermost loop from this shared header. | |
| 1163 void IdealLoopTree::split_outer_loop( PhaseIdealLoop *phase ) { | |
| 1164 PhaseIterGVN &igvn = phase->_igvn; | |
| 1165 | |
| 1166 // Find index of outermost loop; it should also be my tail. | |
| 1167 uint outer_idx = 1; | |
| 1168 while( _head->in(outer_idx) != _tail ) outer_idx++; | |
| 1169 | |
| 1170 // Make a LoopNode for the outermost loop. | |
| 1171 Node *ctl = _head->in(LoopNode::EntryControl); | |
| 1172 Node *outer = new (phase->C, 3) LoopNode( ctl, _head->in(outer_idx) ); | |
| 1173 outer = igvn.register_new_node_with_optimizer(outer, _head); | |
| 1174 phase->set_created_loop_node(); | |
| 2445 | 1175 |
| 0 | 1176 // Outermost loop falls into '_head' loop |
|
3845
c96c3eb1efae
7068051: SIGSEGV in PhaseIdealLoop::build_loop_late_post
kvn
parents:
3782
diff
changeset
|
1177 _head->set_req(LoopNode::EntryControl, outer); |
| 0 | 1178 _head->del_req(outer_idx); |
| 1179 // Split all the Phis up between '_head' loop and 'outer' loop. | |
| 1180 for (DUIterator_Fast jmax, j = _head->fast_outs(jmax); j < jmax; j++) { | |
| 1181 Node *out = _head->fast_out(j); | |
| 1182 if( out->is_Phi() ) { | |
| 1183 PhiNode *old_phi = out->as_Phi(); | |
| 1184 assert( old_phi->region() == _head, "" ); | |
| 1185 Node *phi = PhiNode::make_blank(outer, old_phi); | |
| 1186 phi->init_req(LoopNode::EntryControl, old_phi->in(LoopNode::EntryControl)); | |
| 1187 phi->init_req(LoopNode::LoopBackControl, old_phi->in(outer_idx)); | |
| 1188 phi = igvn.register_new_node_with_optimizer(phi, old_phi); | |
| 1189 // Make old Phi point to new Phi on the fall-in path | |
| 1190 igvn.hash_delete(old_phi); | |
| 1191 old_phi->set_req(LoopNode::EntryControl, phi); | |
| 1192 old_phi->del_req(outer_idx); | |
| 1193 igvn._worklist.push(old_phi); | |
| 1194 } | |
| 1195 } | |
| 1196 | |
| 1197 // Use the new loop head instead of the old shared one | |
| 1198 _head = outer; | |
| 1199 phase->set_loop(_head, this); | |
| 1200 } | |
| 1201 | |
| 1202 //------------------------------fix_parent------------------------------------- | |
| 1203 static void fix_parent( IdealLoopTree *loop, IdealLoopTree *parent ) { | |
| 1204 loop->_parent = parent; | |
| 1205 if( loop->_child ) fix_parent( loop->_child, loop ); | |
| 1206 if( loop->_next ) fix_parent( loop->_next , parent ); | |
| 1207 } | |
| 1208 | |
| 1209 //------------------------------estimate_path_freq----------------------------- | |
| 1210 static float estimate_path_freq( Node *n ) { | |
| 1211 // Try to extract some path frequency info | |
| 1212 IfNode *iff; | |
| 1213 for( int i = 0; i < 50; i++ ) { // Skip through a bunch of uncommon tests | |
| 1214 uint nop = n->Opcode(); | |
| 1215 if( nop == Op_SafePoint ) { // Skip any safepoint | |
| 1216 n = n->in(0); | |
| 1217 continue; | |
| 1218 } | |
| 1219 if( nop == Op_CatchProj ) { // Get count from a prior call | |
| 1220 // Assume call does not always throw exceptions: means the call-site | |
| 1221 // count is also the frequency of the fall-through path. | |
| 1222 assert( n->is_CatchProj(), "" ); | |
| 1223 if( ((CatchProjNode*)n)->_con != CatchProjNode::fall_through_index ) | |
| 1224 return 0.0f; // Assume call exception path is rare | |
| 1225 Node *call = n->in(0)->in(0)->in(0); | |
| 1226 assert( call->is_Call(), "expect a call here" ); | |
| 1227 const JVMState *jvms = ((CallNode*)call)->jvms(); | |
| 1228 ciMethodData* methodData = jvms->method()->method_data(); | |
| 1229 if (!methodData->is_mature()) return 0.0f; // No call-site data | |
| 1230 ciProfileData* data = methodData->bci_to_data(jvms->bci()); | |
| 1231 if ((data == NULL) || !data->is_CounterData()) { | |
| 1232 // no call profile available, try call's control input | |
| 1233 n = n->in(0); | |
| 1234 continue; | |
| 1235 } | |
| 1236 return data->as_CounterData()->count()/FreqCountInvocations; | |
| 1237 } | |
| 1238 // See if there's a gating IF test | |
| 1239 Node *n_c = n->in(0); | |
| 1240 if( !n_c->is_If() ) break; // No estimate available | |
| 1241 iff = n_c->as_If(); | |
| 1242 if( iff->_fcnt != COUNT_UNKNOWN ) // Have a valid count? | |
| 1243 // Compute how much count comes on this path | |
| 1244 return ((nop == Op_IfTrue) ? iff->_prob : 1.0f - iff->_prob) * iff->_fcnt; | |
| 1245 // Have no count info. Skip dull uncommon-trap like branches. | |
| 1246 if( (nop == Op_IfTrue && iff->_prob < PROB_LIKELY_MAG(5)) || | |
| 1247 (nop == Op_IfFalse && iff->_prob > PROB_UNLIKELY_MAG(5)) ) | |
| 1248 break; | |
| 1249 // Skip through never-taken branch; look for a real loop exit. | |
| 1250 n = iff->in(0); | |
| 1251 } | |
| 1252 return 0.0f; // No estimate available | |
| 1253 } | |
| 1254 | |
| 1255 //------------------------------merge_many_backedges--------------------------- | |
| 1256 // Merge all the backedges from the shared header into a private Region. | |
| 1257 // Feed that region as the one backedge to this loop. | |
| 1258 void IdealLoopTree::merge_many_backedges( PhaseIdealLoop *phase ) { | |
| 1259 uint i; | |
| 1260 | |
| 1261 // Scan for the top 2 hottest backedges | |
| 1262 float hotcnt = 0.0f; | |
| 1263 float warmcnt = 0.0f; | |
| 1264 uint hot_idx = 0; | |
| 1265 // Loop starts at 2 because slot 1 is the fall-in path | |
| 1266 for( i = 2; i < _head->req(); i++ ) { | |
| 1267 float cnt = estimate_path_freq(_head->in(i)); | |
| 1268 if( cnt > hotcnt ) { // Grab hottest path | |
| 1269 warmcnt = hotcnt; | |
| 1270 hotcnt = cnt; | |
| 1271 hot_idx = i; | |
| 1272 } else if( cnt > warmcnt ) { // And 2nd hottest path | |
| 1273 warmcnt = cnt; | |
| 1274 } | |
| 1275 } | |
| 1276 | |
| 1277 // See if the hottest backedge is worthy of being an inner loop | |
| 1278 // by being much hotter than the next hottest backedge. | |
| 1279 if( hotcnt <= 0.0001 || | |
| 1280 hotcnt < 2.0*warmcnt ) hot_idx = 0;// No hot backedge | |
| 1281 | |
| 1282 // Peel out the backedges into a private merge point; peel | |
| 1283 // them all except optionally hot_idx. | |
| 1284 PhaseIterGVN &igvn = phase->_igvn; | |
| 1285 | |
| 1286 Node *hot_tail = NULL; | |
| 1287 // Make a Region for the merge point | |
| 1288 Node *r = new (phase->C, 1) RegionNode(1); | |
| 1289 for( i = 2; i < _head->req(); i++ ) { | |
| 1290 if( i != hot_idx ) | |
| 1291 r->add_req( _head->in(i) ); | |
| 1292 else hot_tail = _head->in(i); | |
| 1293 } | |
| 1294 igvn.register_new_node_with_optimizer(r, _head); | |
| 1295 // Plug region into end of loop _head, followed by hot_tail | |
| 1296 while( _head->req() > 3 ) _head->del_req( _head->req()-1 ); | |
| 1297 _head->set_req(2, r); | |
| 1298 if( hot_idx ) _head->add_req(hot_tail); | |
| 1299 | |
| 1300 // Split all the Phis up between '_head' loop and the Region 'r' | |
| 1301 for (DUIterator_Fast jmax, j = _head->fast_outs(jmax); j < jmax; j++) { | |
| 1302 Node *out = _head->fast_out(j); | |
| 1303 if( out->is_Phi() ) { | |
| 1304 PhiNode* n = out->as_Phi(); | |
| 1305 igvn.hash_delete(n); // Delete from hash before hacking edges | |
| 1306 Node *hot_phi = NULL; | |
| 1307 Node *phi = new (phase->C, r->req()) PhiNode(r, n->type(), n->adr_type()); | |
| 1308 // Check all inputs for the ones to peel out | |
| 1309 uint j = 1; | |
| 1310 for( uint i = 2; i < n->req(); i++ ) { | |
| 1311 if( i != hot_idx ) | |
| 1312 phi->set_req( j++, n->in(i) ); | |
| 1313 else hot_phi = n->in(i); | |
| 1314 } | |
| 1315 // Register the phi but do not transform until whole place transforms | |
| 1316 igvn.register_new_node_with_optimizer(phi, n); | |
| 1317 // Add the merge phi to the old Phi | |
| 1318 while( n->req() > 3 ) n->del_req( n->req()-1 ); | |
| 1319 n->set_req(2, phi); | |
| 1320 if( hot_idx ) n->add_req(hot_phi); | |
| 1321 } | |
| 1322 } | |
| 1323 | |
| 1324 | |
| 1325 // Insert a new IdealLoopTree inserted below me. Turn it into a clone | |
| 1326 // of self loop tree. Turn self into a loop headed by _head and with | |
| 1327 // tail being the new merge point. | |
| 1328 IdealLoopTree *ilt = new IdealLoopTree( phase, _head, _tail ); | |
| 1329 phase->set_loop(_tail,ilt); // Adjust tail | |
| 1330 _tail = r; // Self's tail is new merge point | |
| 1331 phase->set_loop(r,this); | |
| 1332 ilt->_child = _child; // New guy has my children | |
| 1333 _child = ilt; // Self has new guy as only child | |
| 1334 ilt->_parent = this; // new guy has self for parent | |
| 1335 ilt->_nest = _nest; // Same nesting depth (for now) | |
| 1336 | |
| 1337 // Starting with 'ilt', look for child loop trees using the same shared | |
| 1338 // header. Flatten these out; they will no longer be loops in the end. | |
| 1339 IdealLoopTree **pilt = &_child; | |
| 1340 while( ilt ) { | |
| 1341 if( ilt->_head == _head ) { | |
| 1342 uint i; | |
| 1343 for( i = 2; i < _head->req(); i++ ) | |
| 1344 if( _head->in(i) == ilt->_tail ) | |
| 1345 break; // Still a loop | |
| 1346 if( i == _head->req() ) { // No longer a loop | |
| 1347 // Flatten ilt. Hang ilt's "_next" list from the end of | |
| 1348 // ilt's '_child' list. Move the ilt's _child up to replace ilt. | |
| 1349 IdealLoopTree **cp = &ilt->_child; | |
| 1350 while( *cp ) cp = &(*cp)->_next; // Find end of child list | |
| 1351 *cp = ilt->_next; // Hang next list at end of child list | |
| 1352 *pilt = ilt->_child; // Move child up to replace ilt | |
| 1353 ilt->_head = NULL; // Flag as a loop UNIONED into parent | |
| 1354 ilt = ilt->_child; // Repeat using new ilt | |
| 1355 continue; // do not advance over ilt->_child | |
| 1356 } | |
| 1357 assert( ilt->_tail == hot_tail, "expected to only find the hot inner loop here" ); | |
| 1358 phase->set_loop(_head,ilt); | |
| 1359 } | |
| 1360 pilt = &ilt->_child; // Advance to next | |
| 1361 ilt = *pilt; | |
| 1362 } | |
| 1363 | |
| 1364 if( _child ) fix_parent( _child, this ); | |
| 1365 } | |
| 1366 | |
| 1367 //------------------------------beautify_loops--------------------------------- | |
| 1368 // Split shared headers and insert loop landing pads. | |
| 1369 // Insert a LoopNode to replace the RegionNode. | |
| 1370 // Return TRUE if loop tree is structurally changed. | |
| 1371 bool IdealLoopTree::beautify_loops( PhaseIdealLoop *phase ) { | |
| 1372 bool result = false; | |
| 1373 // Cache parts in locals for easy | |
| 1374 PhaseIterGVN &igvn = phase->_igvn; | |
| 1375 | |
| 1376 igvn.hash_delete(_head); // Yank from hash before hacking edges | |
| 1377 | |
| 1378 // Check for multiple fall-in paths. Peel off a landing pad if need be. | |
| 1379 int fall_in_cnt = 0; | |
| 1380 for( uint i = 1; i < _head->req(); i++ ) | |
| 1381 if( !phase->is_member( this, _head->in(i) ) ) | |
| 1382 fall_in_cnt++; | |
| 1383 assert( fall_in_cnt, "at least 1 fall-in path" ); | |
| 1384 if( fall_in_cnt > 1 ) // Need a loop landing pad to merge fall-ins | |
| 1385 split_fall_in( phase, fall_in_cnt ); | |
| 1386 | |
| 1387 // Swap inputs to the _head and all Phis to move the fall-in edge to | |
| 1388 // the left. | |
| 1389 fall_in_cnt = 1; | |
| 1390 while( phase->is_member( this, _head->in(fall_in_cnt) ) ) | |
| 1391 fall_in_cnt++; | |
| 1392 if( fall_in_cnt > 1 ) { | |
| 1393 // Since I am just swapping inputs I do not need to update def-use info | |
| 1394 Node *tmp = _head->in(1); | |
| 1395 _head->set_req( 1, _head->in(fall_in_cnt) ); | |
| 1396 _head->set_req( fall_in_cnt, tmp ); | |
| 1397 // Swap also all Phis | |
| 1398 for (DUIterator_Fast imax, i = _head->fast_outs(imax); i < imax; i++) { | |
| 1399 Node* phi = _head->fast_out(i); | |
| 1400 if( phi->is_Phi() ) { | |
| 1401 igvn.hash_delete(phi); // Yank from hash before hacking edges | |
| 1402 tmp = phi->in(1); | |
| 1403 phi->set_req( 1, phi->in(fall_in_cnt) ); | |
| 1404 phi->set_req( fall_in_cnt, tmp ); | |
| 1405 } | |
| 1406 } | |
| 1407 } | |
| 1408 assert( !phase->is_member( this, _head->in(1) ), "left edge is fall-in" ); | |
| 1409 assert( phase->is_member( this, _head->in(2) ), "right edge is loop" ); | |
| 1410 | |
| 1411 // If I am a shared header (multiple backedges), peel off the many | |
| 1412 // backedges into a private merge point and use the merge point as | |
| 1413 // the one true backedge. | |
| 1414 if( _head->req() > 3 ) { | |
| 2445 | 1415 // Merge the many backedges into a single backedge but leave |
| 1416 // the hottest backedge as separate edge for the following peel. | |
| 0 | 1417 merge_many_backedges( phase ); |
| 1418 result = true; | |
| 1419 } | |
| 1420 | |
| 2445 | 1421 // If I have one hot backedge, peel off myself loop. |
| 0 | 1422 // I better be the outermost loop. |
| 1423 if( _head->req() > 3 ) { | |
| 1424 split_outer_loop( phase ); | |
| 1425 result = true; | |
| 1426 | |
| 1427 } else if( !_head->is_Loop() && !_irreducible ) { | |
| 1428 // Make a new LoopNode to replace the old loop head | |
| 1429 Node *l = new (phase->C, 3) LoopNode( _head->in(1), _head->in(2) ); | |
| 1430 l = igvn.register_new_node_with_optimizer(l, _head); | |
| 1431 phase->set_created_loop_node(); | |
| 1432 // Go ahead and replace _head | |
|
1621
6027dddc26c6
6677629: PhaseIterGVN::subsume_node() should call hash_delete() and add_users_to_worklist()
kvn
parents:
1552
diff
changeset
|
1433 phase->_igvn.replace_node( _head, l ); |
| 0 | 1434 _head = l; |
| 1435 phase->set_loop(_head, this); | |
| 1436 } | |
| 1437 | |
| 1438 // Now recursively beautify nested loops | |
| 1439 if( _child ) result |= _child->beautify_loops( phase ); | |
| 1440 if( _next ) result |= _next ->beautify_loops( phase ); | |
| 1441 return result; | |
| 1442 } | |
| 1443 | |
| 1444 //------------------------------allpaths_check_safepts---------------------------- | |
| 1445 // Allpaths backwards scan from loop tail, terminating each path at first safepoint | |
| 1446 // encountered. Helper for check_safepts. | |
| 1447 void IdealLoopTree::allpaths_check_safepts(VectorSet &visited, Node_List &stack) { | |
| 1448 assert(stack.size() == 0, "empty stack"); | |
| 1449 stack.push(_tail); | |
| 1450 visited.Clear(); | |
| 1451 visited.set(_tail->_idx); | |
| 1452 while (stack.size() > 0) { | |
| 1453 Node* n = stack.pop(); | |
| 1454 if (n->is_Call() && n->as_Call()->guaranteed_safepoint()) { | |
| 1455 // Terminate this path | |
| 1456 } else if (n->Opcode() == Op_SafePoint) { | |
| 1457 if (_phase->get_loop(n) != this) { | |
| 1458 if (_required_safept == NULL) _required_safept = new Node_List(); | |
| 1459 _required_safept->push(n); // save the one closest to the tail | |
| 1460 } | |
| 1461 // Terminate this path | |
| 1462 } else { | |
| 1463 uint start = n->is_Region() ? 1 : 0; | |
| 1464 uint end = n->is_Region() && !n->is_Loop() ? n->req() : start + 1; | |
| 1465 for (uint i = start; i < end; i++) { | |
| 1466 Node* in = n->in(i); | |
| 1467 assert(in->is_CFG(), "must be"); | |
| 1468 if (!visited.test_set(in->_idx) && is_member(_phase->get_loop(in))) { | |
| 1469 stack.push(in); | |
| 1470 } | |
| 1471 } | |
| 1472 } | |
| 1473 } | |
| 1474 } | |
| 1475 | |
| 1476 //------------------------------check_safepts---------------------------- | |
| 1477 // Given dominators, try to find loops with calls that must always be | |
| 1478 // executed (call dominates loop tail). These loops do not need non-call | |
| 1479 // safepoints (ncsfpt). | |
| 1480 // | |
| 1481 // A complication is that a safepoint in a inner loop may be needed | |
| 1482 // by an outer loop. In the following, the inner loop sees it has a | |
| 1483 // call (block 3) on every path from the head (block 2) to the | |
| 1484 // backedge (arc 3->2). So it deletes the ncsfpt (non-call safepoint) | |
| 1485 // in block 2, _but_ this leaves the outer loop without a safepoint. | |
| 1486 // | |
| 1487 // entry 0 | |
| 1488 // | | |
| 1489 // v | |
| 1490 // outer 1,2 +->1 | |
| 1491 // | | | |
| 1492 // | v | |
| 1493 // | 2<---+ ncsfpt in 2 | |
| 1494 // |_/|\ | | |
| 1495 // | v | | |
| 1496 // inner 2,3 / 3 | call in 3 | |
| 1497 // / | | | |
| 1498 // v +--+ | |
| 1499 // exit 4 | |
| 1500 // | |
| 1501 // | |
| 1502 // This method creates a list (_required_safept) of ncsfpt nodes that must | |
| 1503 // be protected is created for each loop. When a ncsfpt maybe deleted, it | |
| 1504 // is first looked for in the lists for the outer loops of the current loop. | |
| 1505 // | |
| 1506 // The insights into the problem: | |
| 1507 // A) counted loops are okay | |
| 1508 // B) innermost loops are okay (only an inner loop can delete | |
| 1509 // a ncsfpt needed by an outer loop) | |
| 1510 // C) a loop is immune from an inner loop deleting a safepoint | |
| 1511 // if the loop has a call on the idom-path | |
| 1512 // D) a loop is also immune if it has a ncsfpt (non-call safepoint) on the | |
| 1513 // idom-path that is not in a nested loop | |
| 1514 // E) otherwise, an ncsfpt on the idom-path that is nested in an inner | |
| 1515 // loop needs to be prevented from deletion by an inner loop | |
| 1516 // | |
| 1517 // There are two analyses: | |
| 1518 // 1) The first, and cheaper one, scans the loop body from | |
| 1519 // tail to head following the idom (immediate dominator) | |
| 1520 // chain, looking for the cases (C,D,E) above. | |
| 1521 // Since inner loops are scanned before outer loops, there is summary | |
| 1522 // information about inner loops. Inner loops can be skipped over | |
| 1523 // when the tail of an inner loop is encountered. | |
| 1524 // | |
| 1525 // 2) The second, invoked if the first fails to find a call or ncsfpt on | |
| 1526 // the idom path (which is rare), scans all predecessor control paths | |
| 1527 // from the tail to the head, terminating a path when a call or sfpt | |
| 1528 // is encountered, to find the ncsfpt's that are closest to the tail. | |
| 1529 // | |
| 1530 void IdealLoopTree::check_safepts(VectorSet &visited, Node_List &stack) { | |
| 1531 // Bottom up traversal | |
| 1532 IdealLoopTree* ch = _child; | |
| 1533 while (ch != NULL) { | |
| 1534 ch->check_safepts(visited, stack); | |
| 1535 ch = ch->_next; | |
| 1536 } | |
| 1537 | |
| 1538 if (!_head->is_CountedLoop() && !_has_sfpt && _parent != NULL && !_irreducible) { | |
| 1539 bool has_call = false; // call on dom-path | |
| 1540 bool has_local_ncsfpt = false; // ncsfpt on dom-path at this loop depth | |
| 1541 Node* nonlocal_ncsfpt = NULL; // ncsfpt on dom-path at a deeper depth | |
| 1542 // Scan the dom-path nodes from tail to head | |
| 1543 for (Node* n = tail(); n != _head; n = _phase->idom(n)) { | |
| 1544 if (n->is_Call() && n->as_Call()->guaranteed_safepoint()) { | |
| 1545 has_call = true; | |
| 1546 _has_sfpt = 1; // Then no need for a safept! | |
| 1547 break; | |
| 1548 } else if (n->Opcode() == Op_SafePoint) { | |
| 1549 if (_phase->get_loop(n) == this) { | |
| 1550 has_local_ncsfpt = true; | |
| 1551 break; | |
| 1552 } | |
| 1553 if (nonlocal_ncsfpt == NULL) { | |
| 1554 nonlocal_ncsfpt = n; // save the one closest to the tail | |
| 1555 } | |
| 1556 } else { | |
| 1557 IdealLoopTree* nlpt = _phase->get_loop(n); | |
| 1558 if (this != nlpt) { | |
| 1559 // If at an inner loop tail, see if the inner loop has already | |
| 1560 // recorded seeing a call on the dom-path (and stop.) If not, | |
| 1561 // jump to the head of the inner loop. | |
| 1562 assert(is_member(nlpt), "nested loop"); | |
| 1563 Node* tail = nlpt->_tail; | |
| 1564 if (tail->in(0)->is_If()) tail = tail->in(0); | |
| 1565 if (n == tail) { | |
| 1566 // If inner loop has call on dom-path, so does outer loop | |
| 1567 if (nlpt->_has_sfpt) { | |
| 1568 has_call = true; | |
| 1569 _has_sfpt = 1; | |
| 1570 break; | |
| 1571 } | |
| 1572 // Skip to head of inner loop | |
| 1573 assert(_phase->is_dominator(_head, nlpt->_head), "inner head dominated by outer head"); | |
| 1574 n = nlpt->_head; | |
| 1575 } | |
| 1576 } | |
| 1577 } | |
| 1578 } | |
| 1579 // Record safept's that this loop needs preserved when an | |
| 1580 // inner loop attempts to delete it's safepoints. | |
| 1581 if (_child != NULL && !has_call && !has_local_ncsfpt) { | |
| 1582 if (nonlocal_ncsfpt != NULL) { | |
| 1583 if (_required_safept == NULL) _required_safept = new Node_List(); | |
| 1584 _required_safept->push(nonlocal_ncsfpt); | |
| 1585 } else { | |
| 1586 // Failed to find a suitable safept on the dom-path. Now use | |
| 1587 // an all paths walk from tail to head, looking for safepoints to preserve. | |
| 1588 allpaths_check_safepts(visited, stack); | |
| 1589 } | |
| 1590 } | |
| 1591 } | |
| 1592 } | |
| 1593 | |
| 1594 //---------------------------is_deleteable_safept---------------------------- | |
| 1595 // Is safept not required by an outer loop? | |
| 1596 bool PhaseIdealLoop::is_deleteable_safept(Node* sfpt) { | |
| 1597 assert(sfpt->Opcode() == Op_SafePoint, ""); | |
| 1598 IdealLoopTree* lp = get_loop(sfpt)->_parent; | |
| 1599 while (lp != NULL) { | |
| 1600 Node_List* sfpts = lp->_required_safept; | |
| 1601 if (sfpts != NULL) { | |
| 1602 for (uint i = 0; i < sfpts->size(); i++) { | |
| 1603 if (sfpt == sfpts->at(i)) | |
| 1604 return false; | |
| 1605 } | |
| 1606 } | |
| 1607 lp = lp->_parent; | |
| 1608 } | |
| 1609 return true; | |
| 1610 } | |
| 1611 | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1612 //---------------------------replace_parallel_iv------------------------------- |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1613 // Replace parallel induction variable (parallel to trip counter) |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1614 void PhaseIdealLoop::replace_parallel_iv(IdealLoopTree *loop) { |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1615 assert(loop->_head->is_CountedLoop(), ""); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1616 CountedLoopNode *cl = loop->_head->as_CountedLoop(); |
|
3850
6987871cfb9b
7077439: Possible reference through NULL in loopPredicate.cpp:726
kvn
parents:
3845
diff
changeset
|
1617 if (!cl->is_valid_counted_loop()) |
|
6987871cfb9b
7077439: Possible reference through NULL in loopPredicate.cpp:726
kvn
parents:
3845
diff
changeset
|
1618 return; // skip malformed counted loop |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1619 Node *incr = cl->incr(); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1620 if (incr == NULL) |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1621 return; // Dead loop? |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1622 Node *init = cl->init_trip(); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1623 Node *phi = cl->phi(); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1624 int stride_con = cl->stride_con(); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1625 |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1626 // Visit all children, looking for Phis |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1627 for (DUIterator i = cl->outs(); cl->has_out(i); i++) { |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1628 Node *out = cl->out(i); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1629 // Look for other phis (secondary IVs). Skip dead ones |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1630 if (!out->is_Phi() || out == phi || !has_node(out)) |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1631 continue; |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1632 PhiNode* phi2 = out->as_Phi(); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1633 Node *incr2 = phi2->in( LoopNode::LoopBackControl ); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1634 // Look for induction variables of the form: X += constant |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1635 if (phi2->region() != loop->_head || |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1636 incr2->req() != 3 || |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1637 incr2->in(1) != phi2 || |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1638 incr2 == incr || |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1639 incr2->Opcode() != Op_AddI || |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1640 !incr2->in(2)->is_Con()) |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1641 continue; |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1642 |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1643 // Check for parallel induction variable (parallel to trip counter) |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1644 // via an affine function. In particular, count-down loops with |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1645 // count-up array indices are common. We only RCE references off |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1646 // the trip-counter, so we need to convert all these to trip-counter |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1647 // expressions. |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1648 Node *init2 = phi2->in( LoopNode::EntryControl ); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1649 int stride_con2 = incr2->in(2)->get_int(); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1650 |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1651 // The general case here gets a little tricky. We want to find the |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1652 // GCD of all possible parallel IV's and make a new IV using this |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1653 // GCD for the loop. Then all possible IVs are simple multiples of |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1654 // the GCD. In practice, this will cover very few extra loops. |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1655 // Instead we require 'stride_con2' to be a multiple of 'stride_con', |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1656 // where +/-1 is the common case, but other integer multiples are |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1657 // also easy to handle. |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1658 int ratio_con = stride_con2/stride_con; |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1659 |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1660 if ((ratio_con * stride_con) == stride_con2) { // Check for exact |
|
3936
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1661 #ifndef PRODUCT |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1662 if (TraceLoopOpts) { |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1663 tty->print("Parallel IV: %d ", phi2->_idx); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1664 loop->dump_head(); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1665 } |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1666 #endif |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1667 // Convert to using the trip counter. The parallel induction |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1668 // variable differs from the trip counter by a loop-invariant |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1669 // amount, the difference between their respective initial values. |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1670 // It is scaled by the 'ratio_con'. |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1671 Node* ratio = _igvn.intcon(ratio_con); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1672 set_ctrl(ratio, C->root()); |
|
3936
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1673 Node* ratio_init = new (C, 3) MulINode(init, ratio); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1674 _igvn.register_new_node_with_optimizer(ratio_init, init); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1675 set_early_ctrl(ratio_init); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1676 Node* diff = new (C, 3) SubINode(init2, ratio_init); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1677 _igvn.register_new_node_with_optimizer(diff, init2); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1678 set_early_ctrl(diff); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1679 Node* ratio_idx = new (C, 3) MulINode(phi, ratio); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1680 _igvn.register_new_node_with_optimizer(ratio_idx, phi); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1681 set_ctrl(ratio_idx, cl); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1682 Node* add = new (C, 3) AddINode(ratio_idx, diff); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1683 _igvn.register_new_node_with_optimizer(add); |
|
2c24ef16533d
7035946: Up to 15% regression on JDK 7 b136 vs b135 on specjvm2008.crypto.rsa on x64
kvn
parents:
3850
diff
changeset
|
1684 set_ctrl(add, cl); |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1685 _igvn.replace_node( phi2, add ); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1686 // Sometimes an induction variable is unused |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1687 if (add->outcnt() == 0) { |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1688 _igvn.remove_dead_node(add); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1689 } |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1690 --i; // deleted this phi; rescan starting with next position |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1691 continue; |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1692 } |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1693 } |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1694 } |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1695 |
| 0 | 1696 //------------------------------counted_loop----------------------------------- |
| 1697 // Convert to counted loops where possible | |
| 1698 void IdealLoopTree::counted_loop( PhaseIdealLoop *phase ) { | |
| 1699 | |
| 1700 // For grins, set the inner-loop flag here | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1701 if (!_child) { |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1702 if (_head->is_Loop()) _head->as_Loop()->set_inner_loop(); |
| 0 | 1703 } |
| 1704 | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1705 if (_head->is_CountedLoop() || |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1706 phase->is_counted_loop(_head, this)) { |
| 0 | 1707 _has_sfpt = 1; // Indicate we do not need a safepoint here |
| 1708 | |
| 1709 // Look for a safepoint to remove | |
| 1710 for (Node* n = tail(); n != _head; n = phase->idom(n)) | |
| 1711 if (n->Opcode() == Op_SafePoint && phase->get_loop(n) == this && | |
| 1712 phase->is_deleteable_safept(n)) | |
| 1713 phase->lazy_replace(n,n->in(TypeFunc::Control)); | |
| 1714 | |
| 1715 // Look for induction variables | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1716 phase->replace_parallel_iv(this); |
| 0 | 1717 |
| 1718 } else if (_parent != NULL && !_irreducible) { | |
| 1719 // Not a counted loop. | |
| 1720 // Look for a safepoint on the idom-path to remove, preserving the first one | |
| 1721 bool found = false; | |
| 1722 Node* n = tail(); | |
| 1723 for (; n != _head && !found; n = phase->idom(n)) { | |
| 1724 if (n->Opcode() == Op_SafePoint && phase->get_loop(n) == this) | |
| 1725 found = true; // Found one | |
| 1726 } | |
| 1727 // Skip past it and delete the others | |
| 1728 for (; n != _head; n = phase->idom(n)) { | |
| 1729 if (n->Opcode() == Op_SafePoint && phase->get_loop(n) == this && | |
| 1730 phase->is_deleteable_safept(n)) | |
| 1731 phase->lazy_replace(n,n->in(TypeFunc::Control)); | |
| 1732 } | |
| 1733 } | |
| 1734 | |
| 1735 // Recursively | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1736 if (_child) _child->counted_loop( phase ); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1737 if (_next) _next ->counted_loop( phase ); |
| 0 | 1738 } |
| 1739 | |
| 1740 #ifndef PRODUCT | |
| 1741 //------------------------------dump_head-------------------------------------- | |
| 1742 // Dump 1 liner for loop header info | |
| 1743 void IdealLoopTree::dump_head( ) const { | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1744 for (uint i=0; i<_nest; i++) |
| 0 | 1745 tty->print(" "); |
| 1746 tty->print("Loop: N%d/N%d ",_head->_idx,_tail->_idx); | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1747 if (_irreducible) tty->print(" IRREDUCIBLE"); |
| 3345 | 1748 Node* entry = _head->in(LoopNode::EntryControl); |
| 1749 if (LoopLimitCheck) { | |
| 1750 Node* predicate = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check); | |
| 1751 if (predicate != NULL ) { | |
| 1752 tty->print(" limit_check"); | |
| 1753 entry = entry->in(0)->in(0); | |
| 1754 } | |
| 1755 } | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1756 if (UseLoopPredicate) { |
| 3345 | 1757 entry = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_predicate); |
| 2445 | 1758 if (entry != NULL) { |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1759 tty->print(" predicated"); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1760 } |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1761 } |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1762 if (_head->is_CountedLoop()) { |
| 0 | 1763 CountedLoopNode *cl = _head->as_CountedLoop(); |
| 1764 tty->print(" counted"); | |
| 2465 | 1765 |
| 1766 Node* init_n = cl->init_trip(); | |
| 1767 if (init_n != NULL && init_n->is_Con()) | |
| 1768 tty->print(" [%d,", cl->init_trip()->get_int()); | |
| 1769 else | |
| 1770 tty->print(" [int,"); | |
| 1771 Node* limit_n = cl->limit(); | |
| 1772 if (limit_n != NULL && limit_n->is_Con()) | |
| 1773 tty->print("%d),", cl->limit()->get_int()); | |
| 1774 else | |
| 1775 tty->print("int),"); | |
| 1776 int stride_con = cl->stride_con(); | |
| 1777 if (stride_con > 0) tty->print("+"); | |
| 1778 tty->print("%d", stride_con); | |
| 1779 | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1780 if (cl->is_pre_loop ()) tty->print(" pre" ); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1781 if (cl->is_main_loop()) tty->print(" main"); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1782 if (cl->is_post_loop()) tty->print(" post"); |
| 0 | 1783 } |
| 1784 tty->cr(); | |
| 1785 } | |
| 1786 | |
| 1787 //------------------------------dump------------------------------------------- | |
| 1788 // Dump loops by loop tree | |
| 1789 void IdealLoopTree::dump( ) const { | |
| 1790 dump_head(); | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1791 if (_child) _child->dump(); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1792 if (_next) _next ->dump(); |
| 0 | 1793 } |
| 1794 | |
| 1795 #endif | |
| 1796 | |
|
367
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1797 static void log_loop_tree(IdealLoopTree* root, IdealLoopTree* loop, CompileLog* log) { |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1798 if (loop == root) { |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1799 if (loop->_child != NULL) { |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1800 log->begin_head("loop_tree"); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1801 log->end_head(); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1802 if( loop->_child ) log_loop_tree(root, loop->_child, log); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1803 log->tail("loop_tree"); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1804 assert(loop->_next == NULL, "what?"); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1805 } |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1806 } else { |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1807 Node* head = loop->_head; |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1808 log->begin_head("loop"); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1809 log->print(" idx='%d' ", head->_idx); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1810 if (loop->_irreducible) log->print("irreducible='1' "); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1811 if (head->is_Loop()) { |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1812 if (head->as_Loop()->is_inner_loop()) log->print("inner_loop='1' "); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1813 if (head->as_Loop()->is_partial_peel_loop()) log->print("partial_peel_loop='1' "); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1814 } |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1815 if (head->is_CountedLoop()) { |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1816 CountedLoopNode* cl = head->as_CountedLoop(); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1817 if (cl->is_pre_loop()) log->print("pre_loop='%d' ", cl->main_idx()); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1818 if (cl->is_main_loop()) log->print("main_loop='%d' ", cl->_idx); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1819 if (cl->is_post_loop()) log->print("post_loop='%d' ", cl->main_idx()); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1820 } |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1821 log->end_head(); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1822 if( loop->_child ) log_loop_tree(root, loop->_child, log); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1823 log->tail("loop"); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1824 if( loop->_next ) log_loop_tree(root, loop->_next, log); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1825 } |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1826 } |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
1827 |
| 1172 | 1828 //---------------------collect_potentially_useful_predicates----------------------- |
| 1829 // Helper function to collect potentially useful predicates to prevent them from | |
| 1830 // being eliminated by PhaseIdealLoop::eliminate_useless_predicates | |
| 1831 void PhaseIdealLoop::collect_potentially_useful_predicates( | |
| 1832 IdealLoopTree * loop, Unique_Node_List &useful_predicates) { | |
| 1833 if (loop->_child) { // child | |
| 1834 collect_potentially_useful_predicates(loop->_child, useful_predicates); | |
| 1835 } | |
| 1836 | |
| 1837 // self (only loops that we can apply loop predication may use their predicates) | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1838 if (loop->_head->is_Loop() && |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1839 !loop->_irreducible && |
| 1172 | 1840 !loop->tail()->is_top()) { |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1841 LoopNode* lpn = loop->_head->as_Loop(); |
| 1172 | 1842 Node* entry = lpn->in(LoopNode::EntryControl); |
| 3345 | 1843 Node* predicate_proj = find_predicate(entry); // loop_limit_check first |
| 1172 | 1844 if (predicate_proj != NULL ) { // right pattern that can be used by loop predication |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1845 assert(entry->in(0)->in(1)->in(1)->Opcode() == Op_Opaque1, "must be"); |
| 1172 | 1846 useful_predicates.push(entry->in(0)->in(1)->in(1)); // good one |
| 3345 | 1847 entry = entry->in(0)->in(0); |
| 1848 } | |
| 1849 predicate_proj = find_predicate(entry); // Predicate | |
| 1850 if (predicate_proj != NULL ) { | |
| 1851 useful_predicates.push(entry->in(0)->in(1)->in(1)); // good one | |
| 1172 | 1852 } |
| 1853 } | |
| 1854 | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1855 if (loop->_next) { // sibling |
| 1172 | 1856 collect_potentially_useful_predicates(loop->_next, useful_predicates); |
| 1857 } | |
| 1858 } | |
| 1859 | |
| 1860 //------------------------eliminate_useless_predicates----------------------------- | |
| 1861 // Eliminate all inserted predicates if they could not be used by loop predication. | |
| 3345 | 1862 // Note: it will also eliminates loop limits check predicate since it also uses |
| 1863 // Opaque1 node (see Parse::add_predicate()). | |
| 1172 | 1864 void PhaseIdealLoop::eliminate_useless_predicates() { |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1865 if (C->predicate_count() == 0) |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
1866 return; // no predicate left |
| 1172 | 1867 |
| 1868 Unique_Node_List useful_predicates; // to store useful predicates | |
| 1869 if (C->has_loops()) { | |
| 1870 collect_potentially_useful_predicates(_ltree_root->_child, useful_predicates); | |
| 1871 } | |
| 1872 | |
| 1873 for (int i = C->predicate_count(); i > 0; i--) { | |
| 1874 Node * n = C->predicate_opaque1_node(i-1); | |
| 1875 assert(n->Opcode() == Op_Opaque1, "must be"); | |
| 1876 if (!useful_predicates.member(n)) { // not in the useful list | |
| 1877 _igvn.replace_node(n, n->in(1)); | |
| 1878 } | |
| 1879 } | |
| 1880 } | |
| 1881 | |
| 0 | 1882 //============================================================================= |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1883 //----------------------------build_and_optimize------------------------------- |
| 0 | 1884 // Create a PhaseLoop. Build the ideal Loop tree. Map each Ideal Node to |
| 1885 // its corresponding LoopNode. If 'optimize' is true, do some loop cleanups. | |
| 2445 | 1886 void PhaseIdealLoop::build_and_optimize(bool do_split_ifs) { |
|
2248
194c9fdee631
7017240: C2: native memory leak in nsk/regression/b4675027 on windows-x86 in comp mode with G1
kvn
parents:
1972
diff
changeset
|
1887 ResourceMark rm; |
|
194c9fdee631
7017240: C2: native memory leak in nsk/regression/b4675027 on windows-x86 in comp mode with G1
kvn
parents:
1972
diff
changeset
|
1888 |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1889 int old_progress = C->major_progress(); |
| 2403 | 1890 uint orig_worklist_size = _igvn._worklist.size(); |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1891 |
| 0 | 1892 // Reset major-progress flag for the driver's heuristics |
| 1893 C->clear_major_progress(); | |
| 1894 | |
| 1895 #ifndef PRODUCT | |
| 1896 // Capture for later assert | |
| 1897 uint unique = C->unique(); | |
| 1898 _loop_invokes++; | |
| 1899 _loop_work += unique; | |
| 1900 #endif | |
| 1901 | |
| 1902 // True if the method has at least 1 irreducible loop | |
| 1903 _has_irreducible_loops = false; | |
| 1904 | |
| 1905 _created_loop_node = false; | |
| 1906 | |
| 1907 Arena *a = Thread::current()->resource_area(); | |
| 1908 VectorSet visited(a); | |
| 1909 // Pre-grow the mapping from Nodes to IdealLoopTrees. | |
| 1910 _nodes.map(C->unique(), NULL); | |
| 1911 memset(_nodes.adr(), 0, wordSize * C->unique()); | |
| 1912 | |
| 1913 // Pre-build the top-level outermost loop tree entry | |
| 1914 _ltree_root = new IdealLoopTree( this, C->root(), C->root() ); | |
| 1915 // Do not need a safepoint at the top level | |
| 1916 _ltree_root->_has_sfpt = 1; | |
| 1917 | |
| 2445 | 1918 // Initialize Dominators. |
| 1919 // Checked in clone_loop_predicate() during beautify_loops(). | |
| 1920 _idom_size = 0; | |
| 1921 _idom = NULL; | |
| 1922 _dom_depth = NULL; | |
| 1923 _dom_stk = NULL; | |
| 1924 | |
| 0 | 1925 // Empty pre-order array |
| 1926 allocate_preorders(); | |
| 1927 | |
| 1928 // Build a loop tree on the fly. Build a mapping from CFG nodes to | |
| 1929 // IdealLoopTree entries. Data nodes are NOT walked. | |
| 1930 build_loop_tree(); | |
| 1931 // Check for bailout, and return | |
| 1932 if (C->failing()) { | |
| 1933 return; | |
| 1934 } | |
| 1935 | |
| 1936 // No loops after all | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1937 if( !_ltree_root->_child && !_verify_only ) C->set_has_loops(false); |
| 0 | 1938 |
| 1939 // There should always be an outer loop containing the Root and Return nodes. | |
| 1940 // If not, we have a degenerate empty program. Bail out in this case. | |
| 1941 if (!has_node(C->root())) { | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1942 if (!_verify_only) { |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1943 C->clear_major_progress(); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1944 C->record_method_not_compilable("empty program detected during loop optimization"); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1945 } |
| 0 | 1946 return; |
| 1947 } | |
| 1948 | |
| 1949 // Nothing to do, so get out | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1950 if( !C->has_loops() && !do_split_ifs && !_verify_me && !_verify_only ) { |
| 0 | 1951 _igvn.optimize(); // Cleanup NeverBranches |
| 1952 return; | |
| 1953 } | |
| 1954 | |
| 1955 // Set loop nesting depth | |
| 1956 _ltree_root->set_nest( 0 ); | |
| 1957 | |
| 1958 // Split shared headers and insert loop landing pads. | |
| 1959 // Do not bother doing this on the Root loop of course. | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1960 if( !_verify_me && !_verify_only && _ltree_root->_child ) { |
| 2403 | 1961 C->print_method("Before beautify loops", 3); |
| 0 | 1962 if( _ltree_root->_child->beautify_loops( this ) ) { |
| 1963 // Re-build loop tree! | |
| 1964 _ltree_root->_child = NULL; | |
| 1965 _nodes.clear(); | |
| 1966 reallocate_preorders(); | |
| 1967 build_loop_tree(); | |
| 1968 // Check for bailout, and return | |
| 1969 if (C->failing()) { | |
| 1970 return; | |
| 1971 } | |
| 1972 // Reset loop nesting depth | |
| 1973 _ltree_root->set_nest( 0 ); | |
| 222 | 1974 |
| 1975 C->print_method("After beautify loops", 3); | |
| 0 | 1976 } |
| 1977 } | |
| 1978 | |
| 1979 // Build Dominators for elision of NULL checks & loop finding. | |
| 1980 // Since nodes do not have a slot for immediate dominator, make | |
| 605 | 1981 // a persistent side array for that info indexed on node->_idx. |
| 0 | 1982 _idom_size = C->unique(); |
| 1983 _idom = NEW_RESOURCE_ARRAY( Node*, _idom_size ); | |
| 1984 _dom_depth = NEW_RESOURCE_ARRAY( uint, _idom_size ); | |
| 1985 _dom_stk = NULL; // Allocated on demand in recompute_dom_depth | |
| 1986 memset( _dom_depth, 0, _idom_size * sizeof(uint) ); | |
| 1987 | |
| 1988 Dominators(); | |
| 1989 | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1990 if (!_verify_only) { |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1991 // As a side effect, Dominators removed any unreachable CFG paths |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1992 // into RegionNodes. It doesn't do this test against Root, so |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1993 // we do it here. |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1994 for( uint i = 1; i < C->root()->req(); i++ ) { |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1995 if( !_nodes[C->root()->in(i)->_idx] ) { // Dead path into Root? |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1996 _igvn.hash_delete(C->root()); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1997 C->root()->del_req(i); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1998 _igvn._worklist.push(C->root()); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
1999 i--; // Rerun same iteration on compressed edges |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2000 } |
| 0 | 2001 } |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2002 |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2003 // Given dominators, try to find inner loops with calls that must |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2004 // always be executed (call dominates loop tail). These loops do |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2005 // not need a separate safepoint. |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2006 Node_List cisstack(a); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2007 _ltree_root->check_safepts(visited, cisstack); |
| 0 | 2008 } |
| 2009 | |
| 2010 // Walk the DATA nodes and place into loops. Find earliest control | |
| 2011 // node. For CFG nodes, the _nodes array starts out and remains | |
| 2012 // holding the associated IdealLoopTree pointer. For DATA nodes, the | |
| 2013 // _nodes array holds the earliest legal controlling CFG node. | |
| 2014 | |
| 2015 // Allocate stack with enough space to avoid frequent realloc | |
| 2016 int stack_size = (C->unique() >> 1) + 16; // (unique>>1)+16 from Java2D stats | |
| 2017 Node_Stack nstack( a, stack_size ); | |
| 2018 | |
| 2019 visited.Clear(); | |
| 2020 Node_List worklist(a); | |
| 2021 // Don't need C->root() on worklist since | |
| 2022 // it will be processed among C->top() inputs | |
| 2023 worklist.push( C->top() ); | |
| 2024 visited.set( C->top()->_idx ); // Set C->top() as visited now | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2025 build_loop_early( visited, worklist, nstack ); |
| 0 | 2026 |
| 2027 // Given early legal placement, try finding counted loops. This placement | |
| 2028 // is good enough to discover most loop invariants. | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2029 if( !_verify_me && !_verify_only ) |
| 0 | 2030 _ltree_root->counted_loop( this ); |
| 2031 | |
| 2032 // Find latest loop placement. Find ideal loop placement. | |
| 2033 visited.Clear(); | |
| 2034 init_dom_lca_tags(); | |
| 2035 // Need C->root() on worklist when processing outs | |
| 2036 worklist.push( C->root() ); | |
| 2037 NOT_PRODUCT( C->verify_graph_edges(); ) | |
| 2038 worklist.push( C->top() ); | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2039 build_loop_late( visited, worklist, nstack ); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2040 |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2041 if (_verify_only) { |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2042 // restore major progress flag |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2043 for (int i = 0; i < old_progress; i++) |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2044 C->set_major_progress(); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2045 assert(C->unique() == unique, "verification mode made Nodes? ? ?"); |
| 2403 | 2046 assert(_igvn._worklist.size() == orig_worklist_size, "shouldn't push anything"); |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2047 return; |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2048 } |
| 0 | 2049 |
| 2445 | 2050 // Some parser-inserted loop predicates could never be used by loop |
| 2051 // predication or they were moved away from loop during some optimizations. | |
| 2052 // For example, peeling. Eliminate them before next loop optimizations. | |
| 3345 | 2053 if (UseLoopPredicate || LoopLimitCheck) { |
| 1172 | 2054 eliminate_useless_predicates(); |
| 2055 } | |
| 2056 | |
| 0 | 2057 // clear out the dead code |
| 2058 while(_deadlist.size()) { | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2059 _igvn.remove_globally_dead_node(_deadlist.pop()); |
| 0 | 2060 } |
| 2061 | |
| 2062 #ifndef PRODUCT | |
| 2063 C->verify_graph_edges(); | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
2064 if (_verify_me) { // Nested verify pass? |
| 0 | 2065 // Check to see if the verify mode is broken |
| 2066 assert(C->unique() == unique, "non-optimize mode made Nodes? ? ?"); | |
| 2067 return; | |
| 2068 } | |
|
2383
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
2069 if(VerifyLoopOptimizations) verify(); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
2070 if(TraceLoopOpts && C->has_loops()) { |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
2071 _ltree_root->dump(); |
|
9dc311b8473e
7008866: Missing loop predicate for loop with multiple entries
kvn
parents:
2248
diff
changeset
|
2072 } |
| 0 | 2073 #endif |
| 2074 | |
| 2075 if (ReassociateInvariants) { | |
| 2076 // Reassociate invariants and prep for split_thru_phi | |
| 2077 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) { | |
| 2078 IdealLoopTree* lpt = iter.current(); | |
| 2079 if (!lpt->is_counted() || !lpt->is_inner()) continue; | |
| 2080 | |
| 2081 lpt->reassociate_invariants(this); | |
| 2082 | |
| 2083 // Because RCE opportunities can be masked by split_thru_phi, | |
| 2084 // look for RCE candidates and inhibit split_thru_phi | |
| 2085 // on just their loop-phi's for this pass of loop opts | |
| 1172 | 2086 if (SplitIfBlocks && do_split_ifs) { |
| 0 | 2087 if (lpt->policy_range_check(this)) { |
|
39
76256d272075
6667612: (Escape Analysis) disable loop cloning if it has a scalar replaceable allocation
kvn
parents:
17
diff
changeset
|
2088 lpt->_rce_candidate = 1; // = true |
| 0 | 2089 } |
| 2090 } | |
| 2091 } | |
| 2092 } | |
| 2093 | |
| 2094 // Check for aggressive application of split-if and other transforms | |
| 2095 // that require basic-block info (like cloning through Phi's) | |
| 2096 if( SplitIfBlocks && do_split_ifs ) { | |
| 2097 visited.Clear(); | |
| 2098 split_if_with_blocks( visited, nstack ); | |
| 2099 NOT_PRODUCT( if( VerifyLoopOptimizations ) verify(); ); | |
| 2100 } | |
| 2101 | |
| 1172 | 2102 // Perform loop predication before iteration splitting |
| 2445 | 2103 if (C->has_loops() && !C->major_progress() && (C->predicate_count() > 0)) { |
| 1172 | 2104 _ltree_root->_child->loop_predication(this); |
| 2105 } | |
| 2106 | |
| 1763 | 2107 if (OptimizeFill && UseLoopPredicate && C->has_loops() && !C->major_progress()) { |
| 2108 if (do_intrinsify_fill()) { | |
| 2109 C->set_major_progress(); | |
| 2110 } | |
| 2111 } | |
| 2112 | |
| 0 | 2113 // Perform iteration-splitting on inner loops. Split iterations to avoid |
| 2114 // range checks or one-shot null checks. | |
| 2115 | |
| 2116 // If split-if's didn't hack the graph too bad (no CFG changes) | |
| 2117 // then do loop opts. | |
| 1172 | 2118 if (C->has_loops() && !C->major_progress()) { |
| 0 | 2119 memset( worklist.adr(), 0, worklist.Size()*sizeof(Node*) ); |
| 2120 _ltree_root->_child->iteration_split( this, worklist ); | |
| 2121 // No verify after peeling! GCM has hoisted code out of the loop. | |
| 2122 // After peeling, the hoisted code could sink inside the peeled area. | |
| 2123 // The peeling code does not try to recompute the best location for | |
| 2124 // all the code before the peeled area, so the verify pass will always | |
| 2125 // complain about it. | |
| 2126 } | |
| 2127 // Do verify graph edges in any case | |
| 2128 NOT_PRODUCT( C->verify_graph_edges(); ); | |
| 2129 | |
| 1172 | 2130 if (!do_split_ifs) { |
| 0 | 2131 // We saw major progress in Split-If to get here. We forced a |
| 2132 // pass with unrolling and not split-if, however more split-if's | |
| 2133 // might make progress. If the unrolling didn't make progress | |
| 2134 // then the major-progress flag got cleared and we won't try | |
| 2135 // another round of Split-If. In particular the ever-common | |
| 2136 // instance-of/check-cast pattern requires at least 2 rounds of | |
| 2137 // Split-If to clear out. | |
| 2138 C->set_major_progress(); | |
| 2139 } | |
| 2140 | |
| 2141 // Repeat loop optimizations if new loops were seen | |
| 2142 if (created_loop_node()) { | |
| 2143 C->set_major_progress(); | |
| 2144 } | |
| 2145 | |
| 2445 | 2146 // Keep loop predicates and perform optimizations with them |
| 2147 // until no more loop optimizations could be done. | |
| 2148 // After that switch predicates off and do more loop optimizations. | |
| 2149 if (!C->major_progress() && (C->predicate_count() > 0)) { | |
| 2150 C->cleanup_loop_predicates(_igvn); | |
| 2151 #ifndef PRODUCT | |
| 2152 if (TraceLoopOpts) { | |
| 2153 tty->print_cr("PredicatesOff"); | |
| 2154 } | |
| 2155 #endif | |
| 2156 C->set_major_progress(); | |
| 2157 } | |
| 0 | 2158 |
| 2445 | 2159 // Convert scalar to superword operations at the end of all loop opts. |
| 0 | 2160 if (UseSuperWord && C->has_loops() && !C->major_progress()) { |
| 2161 // SuperWord transform | |
| 2162 SuperWord sw(this); | |
| 2163 for (LoopTreeIterator iter(_ltree_root); !iter.done(); iter.next()) { | |
| 2164 IdealLoopTree* lpt = iter.current(); | |
| 2165 if (lpt->is_counted()) { | |
| 2166 sw.transform_loop(lpt); | |
| 2167 } | |
| 2168 } | |
| 2169 } | |
| 2170 | |
| 2171 // Cleanup any modified bits | |
| 2172 _igvn.optimize(); | |
| 2173 | |
|
367
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
2174 // disable assert until issue with split_flow_path is resolved (6742111) |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
2175 // assert(!_has_irreducible_loops || C->parsed_irreducible_loop() || C->is_osr_compilation(), |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
2176 // "shouldn't introduce irreducible loops"); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
2177 |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
2178 if (C->log() != NULL) { |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
2179 log_loop_tree(_ltree_root, _ltree_root, C->log()); |
|
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
2180 } |
| 0 | 2181 } |
| 2182 | |
| 2183 #ifndef PRODUCT | |
| 2184 //------------------------------print_statistics------------------------------- | |
| 2185 int PhaseIdealLoop::_loop_invokes=0;// Count of PhaseIdealLoop invokes | |
| 2186 int PhaseIdealLoop::_loop_work=0; // Sum of PhaseIdealLoop x unique | |
| 2187 void PhaseIdealLoop::print_statistics() { | |
| 2188 tty->print_cr("PhaseIdealLoop=%d, sum _unique=%d", _loop_invokes, _loop_work); | |
| 2189 } | |
| 2190 | |
| 2191 //------------------------------verify----------------------------------------- | |
| 2192 // Build a verify-only PhaseIdealLoop, and see that it agrees with me. | |
| 2193 static int fail; // debug only, so its multi-thread dont care | |
| 2194 void PhaseIdealLoop::verify() const { | |
| 2195 int old_progress = C->major_progress(); | |
| 2196 ResourceMark rm; | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2197 PhaseIdealLoop loop_verify( _igvn, this ); |
| 0 | 2198 VectorSet visited(Thread::current()->resource_area()); |
| 2199 | |
| 2200 fail = 0; | |
| 2201 verify_compare( C->root(), &loop_verify, visited ); | |
| 2202 assert( fail == 0, "verify loops failed" ); | |
| 2203 // Verify loop structure is the same | |
| 2204 _ltree_root->verify_tree(loop_verify._ltree_root, NULL); | |
| 2205 // Reset major-progress. It was cleared by creating a verify version of | |
| 2206 // PhaseIdealLoop. | |
| 2207 for( int i=0; i<old_progress; i++ ) | |
| 2208 C->set_major_progress(); | |
| 2209 } | |
| 2210 | |
| 2211 //------------------------------verify_compare--------------------------------- | |
| 2212 // Make sure me and the given PhaseIdealLoop agree on key data structures | |
| 2213 void PhaseIdealLoop::verify_compare( Node *n, const PhaseIdealLoop *loop_verify, VectorSet &visited ) const { | |
| 2214 if( !n ) return; | |
| 2215 if( visited.test_set( n->_idx ) ) return; | |
| 2216 if( !_nodes[n->_idx] ) { // Unreachable | |
| 2217 assert( !loop_verify->_nodes[n->_idx], "both should be unreachable" ); | |
| 2218 return; | |
| 2219 } | |
| 2220 | |
| 2221 uint i; | |
| 2222 for( i = 0; i < n->req(); i++ ) | |
| 2223 verify_compare( n->in(i), loop_verify, visited ); | |
| 2224 | |
| 2225 // Check the '_nodes' block/loop structure | |
| 2226 i = n->_idx; | |
| 2227 if( has_ctrl(n) ) { // We have control; verify has loop or ctrl | |
| 2228 if( _nodes[i] != loop_verify->_nodes[i] && | |
| 2229 get_ctrl_no_update(n) != loop_verify->get_ctrl_no_update(n) ) { | |
| 2230 tty->print("Mismatched control setting for: "); | |
| 2231 n->dump(); | |
| 2232 if( fail++ > 10 ) return; | |
| 2233 Node *c = get_ctrl_no_update(n); | |
| 2234 tty->print("We have it as: "); | |
| 2235 if( c->in(0) ) c->dump(); | |
| 2236 else tty->print_cr("N%d",c->_idx); | |
| 2237 tty->print("Verify thinks: "); | |
| 2238 if( loop_verify->has_ctrl(n) ) | |
| 2239 loop_verify->get_ctrl_no_update(n)->dump(); | |
| 2240 else | |
| 2241 loop_verify->get_loop_idx(n)->dump(); | |
| 2242 tty->cr(); | |
| 2243 } | |
| 2244 } else { // We have a loop | |
| 2245 IdealLoopTree *us = get_loop_idx(n); | |
| 2246 if( loop_verify->has_ctrl(n) ) { | |
| 2247 tty->print("Mismatched loop setting for: "); | |
| 2248 n->dump(); | |
| 2249 if( fail++ > 10 ) return; | |
| 2250 tty->print("We have it as: "); | |
| 2251 us->dump(); | |
| 2252 tty->print("Verify thinks: "); | |
| 2253 loop_verify->get_ctrl_no_update(n)->dump(); | |
| 2254 tty->cr(); | |
| 2255 } else if (!C->major_progress()) { | |
| 2256 // Loop selection can be messed up if we did a major progress | |
| 2257 // operation, like split-if. Do not verify in that case. | |
| 2258 IdealLoopTree *them = loop_verify->get_loop_idx(n); | |
| 2259 if( us->_head != them->_head || us->_tail != them->_tail ) { | |
| 2260 tty->print("Unequals loops for: "); | |
| 2261 n->dump(); | |
| 2262 if( fail++ > 10 ) return; | |
| 2263 tty->print("We have it as: "); | |
| 2264 us->dump(); | |
| 2265 tty->print("Verify thinks: "); | |
| 2266 them->dump(); | |
| 2267 tty->cr(); | |
| 2268 } | |
| 2269 } | |
| 2270 } | |
| 2271 | |
| 2272 // Check for immediate dominators being equal | |
| 2273 if( i >= _idom_size ) { | |
| 2274 if( !n->is_CFG() ) return; | |
| 2275 tty->print("CFG Node with no idom: "); | |
| 2276 n->dump(); | |
| 2277 return; | |
| 2278 } | |
| 2279 if( !n->is_CFG() ) return; | |
| 2280 if( n == C->root() ) return; // No IDOM here | |
| 2281 | |
| 2282 assert(n->_idx == i, "sanity"); | |
| 2283 Node *id = idom_no_update(n); | |
| 2284 if( id != loop_verify->idom_no_update(n) ) { | |
| 2285 tty->print("Unequals idoms for: "); | |
| 2286 n->dump(); | |
| 2287 if( fail++ > 10 ) return; | |
| 2288 tty->print("We have it as: "); | |
| 2289 id->dump(); | |
| 2290 tty->print("Verify thinks: "); | |
| 2291 loop_verify->idom_no_update(n)->dump(); | |
| 2292 tty->cr(); | |
| 2293 } | |
| 2294 | |
| 2295 } | |
| 2296 | |
| 2297 //------------------------------verify_tree------------------------------------ | |
| 2298 // Verify that tree structures match. Because the CFG can change, siblings | |
| 2299 // within the loop tree can be reordered. We attempt to deal with that by | |
| 2300 // reordering the verify's loop tree if possible. | |
| 2301 void IdealLoopTree::verify_tree(IdealLoopTree *loop, const IdealLoopTree *parent) const { | |
| 2302 assert( _parent == parent, "Badly formed loop tree" ); | |
| 2303 | |
| 2304 // Siblings not in same order? Attempt to re-order. | |
| 2305 if( _head != loop->_head ) { | |
| 2306 // Find _next pointer to update | |
| 2307 IdealLoopTree **pp = &loop->_parent->_child; | |
| 2308 while( *pp != loop ) | |
| 2309 pp = &((*pp)->_next); | |
| 2310 // Find proper sibling to be next | |
| 2311 IdealLoopTree **nn = &loop->_next; | |
| 2312 while( (*nn) && (*nn)->_head != _head ) | |
| 2313 nn = &((*nn)->_next); | |
| 2314 | |
| 2315 // Check for no match. | |
| 2316 if( !(*nn) ) { | |
| 2317 // Annoyingly, irreducible loops can pick different headers | |
| 2318 // after a major_progress operation, so the rest of the loop | |
| 2319 // tree cannot be matched. | |
| 2320 if (_irreducible && Compile::current()->major_progress()) return; | |
| 2321 assert( 0, "failed to match loop tree" ); | |
| 2322 } | |
| 2323 | |
| 2324 // Move (*nn) to (*pp) | |
| 2325 IdealLoopTree *hit = *nn; | |
| 2326 *nn = hit->_next; | |
| 2327 hit->_next = loop; | |
| 2328 *pp = loop; | |
| 2329 loop = hit; | |
| 2330 // Now try again to verify | |
| 2331 } | |
| 2332 | |
| 2333 assert( _head == loop->_head , "mismatched loop head" ); | |
| 2334 Node *tail = _tail; // Inline a non-updating version of | |
| 2335 while( !tail->in(0) ) // the 'tail()' call. | |
| 2336 tail = tail->in(1); | |
| 2337 assert( tail == loop->_tail, "mismatched loop tail" ); | |
| 2338 | |
| 2339 // Counted loops that are guarded should be able to find their guards | |
| 2340 if( _head->is_CountedLoop() && _head->as_CountedLoop()->is_main_loop() ) { | |
| 2341 CountedLoopNode *cl = _head->as_CountedLoop(); | |
| 2342 Node *init = cl->init_trip(); | |
| 2343 Node *ctrl = cl->in(LoopNode::EntryControl); | |
| 2344 assert( ctrl->Opcode() == Op_IfTrue || ctrl->Opcode() == Op_IfFalse, "" ); | |
| 2345 Node *iff = ctrl->in(0); | |
| 2346 assert( iff->Opcode() == Op_If, "" ); | |
| 2347 Node *bol = iff->in(1); | |
| 2348 assert( bol->Opcode() == Op_Bool, "" ); | |
| 2349 Node *cmp = bol->in(1); | |
| 2350 assert( cmp->Opcode() == Op_CmpI, "" ); | |
| 2351 Node *add = cmp->in(1); | |
| 2352 Node *opaq; | |
| 2353 if( add->Opcode() == Op_Opaque1 ) { | |
| 2354 opaq = add; | |
| 2355 } else { | |
| 2356 assert( add->Opcode() == Op_AddI || add->Opcode() == Op_ConI , "" ); | |
| 2357 assert( add == init, "" ); | |
| 2358 opaq = cmp->in(2); | |
| 2359 } | |
| 2360 assert( opaq->Opcode() == Op_Opaque1, "" ); | |
| 2361 | |
| 2362 } | |
| 2363 | |
| 2364 if (_child != NULL) _child->verify_tree(loop->_child, this); | |
| 2365 if (_next != NULL) _next ->verify_tree(loop->_next, parent); | |
| 2366 // Innermost loops need to verify loop bodies, | |
| 2367 // but only if no 'major_progress' | |
| 2368 int fail = 0; | |
| 2369 if (!Compile::current()->major_progress() && _child == NULL) { | |
| 2370 for( uint i = 0; i < _body.size(); i++ ) { | |
| 2371 Node *n = _body.at(i); | |
| 2372 if (n->outcnt() == 0) continue; // Ignore dead | |
| 2373 uint j; | |
| 2374 for( j = 0; j < loop->_body.size(); j++ ) | |
| 2375 if( loop->_body.at(j) == n ) | |
| 2376 break; | |
| 2377 if( j == loop->_body.size() ) { // Not found in loop body | |
| 2378 // Last ditch effort to avoid assertion: Its possible that we | |
| 2379 // have some users (so outcnt not zero) but are still dead. | |
| 2380 // Try to find from root. | |
| 2381 if (Compile::current()->root()->find(n->_idx)) { | |
| 2382 fail++; | |
| 2383 tty->print("We have that verify does not: "); | |
| 2384 n->dump(); | |
| 2385 } | |
| 2386 } | |
| 2387 } | |
| 2388 for( uint i2 = 0; i2 < loop->_body.size(); i2++ ) { | |
| 2389 Node *n = loop->_body.at(i2); | |
| 2390 if (n->outcnt() == 0) continue; // Ignore dead | |
| 2391 uint j; | |
| 2392 for( j = 0; j < _body.size(); j++ ) | |
| 2393 if( _body.at(j) == n ) | |
| 2394 break; | |
| 2395 if( j == _body.size() ) { // Not found in loop body | |
| 2396 // Last ditch effort to avoid assertion: Its possible that we | |
| 2397 // have some users (so outcnt not zero) but are still dead. | |
| 2398 // Try to find from root. | |
| 2399 if (Compile::current()->root()->find(n->_idx)) { | |
| 2400 fail++; | |
| 2401 tty->print("Verify has that we do not: "); | |
| 2402 n->dump(); | |
| 2403 } | |
| 2404 } | |
| 2405 } | |
| 2406 assert( !fail, "loop body mismatch" ); | |
| 2407 } | |
| 2408 } | |
| 2409 | |
| 2410 #endif | |
| 2411 | |
| 2412 //------------------------------set_idom--------------------------------------- | |
| 2413 void PhaseIdealLoop::set_idom(Node* d, Node* n, uint dom_depth) { | |
| 2414 uint idx = d->_idx; | |
| 2415 if (idx >= _idom_size) { | |
| 2416 uint newsize = _idom_size<<1; | |
| 2417 while( idx >= newsize ) { | |
| 2418 newsize <<= 1; | |
| 2419 } | |
| 2420 _idom = REALLOC_RESOURCE_ARRAY( Node*, _idom,_idom_size,newsize); | |
| 2421 _dom_depth = REALLOC_RESOURCE_ARRAY( uint, _dom_depth,_idom_size,newsize); | |
| 2422 memset( _dom_depth + _idom_size, 0, (newsize - _idom_size) * sizeof(uint) ); | |
| 2423 _idom_size = newsize; | |
| 2424 } | |
| 2425 _idom[idx] = n; | |
| 2426 _dom_depth[idx] = dom_depth; | |
| 2427 } | |
| 2428 | |
| 2429 //------------------------------recompute_dom_depth--------------------------------------- | |
| 2430 // The dominator tree is constructed with only parent pointers. | |
| 2431 // This recomputes the depth in the tree by first tagging all | |
| 2432 // nodes as "no depth yet" marker. The next pass then runs up | |
| 2433 // the dom tree from each node marked "no depth yet", and computes | |
| 2434 // the depth on the way back down. | |
| 2435 void PhaseIdealLoop::recompute_dom_depth() { | |
| 2436 uint no_depth_marker = C->unique(); | |
| 2437 uint i; | |
| 2438 // Initialize depth to "no depth yet" | |
| 2439 for (i = 0; i < _idom_size; i++) { | |
| 2440 if (_dom_depth[i] > 0 && _idom[i] != NULL) { | |
| 2441 _dom_depth[i] = no_depth_marker; | |
| 2442 } | |
| 2443 } | |
| 2444 if (_dom_stk == NULL) { | |
| 2445 uint init_size = C->unique() / 100; // Guess that 1/100 is a reasonable initial size. | |
| 2446 if (init_size < 10) init_size = 10; | |
|
2248
194c9fdee631
7017240: C2: native memory leak in nsk/regression/b4675027 on windows-x86 in comp mode with G1
kvn
parents:
1972
diff
changeset
|
2447 _dom_stk = new GrowableArray<uint>(init_size); |
| 0 | 2448 } |
| 2449 // Compute new depth for each node. | |
| 2450 for (i = 0; i < _idom_size; i++) { | |
| 2451 uint j = i; | |
| 2452 // Run up the dom tree to find a node with a depth | |
| 2453 while (_dom_depth[j] == no_depth_marker) { | |
| 2454 _dom_stk->push(j); | |
| 2455 j = _idom[j]->_idx; | |
| 2456 } | |
| 2457 // Compute the depth on the way back down this tree branch | |
| 2458 uint dd = _dom_depth[j] + 1; | |
| 2459 while (_dom_stk->length() > 0) { | |
| 2460 uint j = _dom_stk->pop(); | |
| 2461 _dom_depth[j] = dd; | |
| 2462 dd++; | |
| 2463 } | |
| 2464 } | |
| 2465 } | |
| 2466 | |
| 2467 //------------------------------sort------------------------------------------- | |
| 2468 // Insert 'loop' into the existing loop tree. 'innermost' is a leaf of the | |
| 2469 // loop tree, not the root. | |
| 2470 IdealLoopTree *PhaseIdealLoop::sort( IdealLoopTree *loop, IdealLoopTree *innermost ) { | |
| 2471 if( !innermost ) return loop; // New innermost loop | |
| 2472 | |
| 2473 int loop_preorder = get_preorder(loop->_head); // Cache pre-order number | |
| 2474 assert( loop_preorder, "not yet post-walked loop" ); | |
| 2475 IdealLoopTree **pp = &innermost; // Pointer to previous next-pointer | |
| 2476 IdealLoopTree *l = *pp; // Do I go before or after 'l'? | |
| 2477 | |
| 2478 // Insert at start of list | |
| 2479 while( l ) { // Insertion sort based on pre-order | |
| 2480 if( l == loop ) return innermost; // Already on list! | |
| 2481 int l_preorder = get_preorder(l->_head); // Cache pre-order number | |
| 2482 assert( l_preorder, "not yet post-walked l" ); | |
| 2483 // Check header pre-order number to figure proper nesting | |
| 2484 if( loop_preorder > l_preorder ) | |
| 2485 break; // End of insertion | |
| 2486 // If headers tie (e.g., shared headers) check tail pre-order numbers. | |
| 2487 // Since I split shared headers, you'd think this could not happen. | |
| 2488 // BUT: I must first do the preorder numbering before I can discover I | |
| 2489 // have shared headers, so the split headers all get the same preorder | |
| 2490 // number as the RegionNode they split from. | |
| 2491 if( loop_preorder == l_preorder && | |
| 2492 get_preorder(loop->_tail) < get_preorder(l->_tail) ) | |
| 2493 break; // Also check for shared headers (same pre#) | |
| 2494 pp = &l->_parent; // Chain up list | |
| 2495 l = *pp; | |
| 2496 } | |
| 2497 // Link into list | |
| 2498 // Point predecessor to me | |
| 2499 *pp = loop; | |
| 2500 // Point me to successor | |
| 2501 IdealLoopTree *p = loop->_parent; | |
| 2502 loop->_parent = l; // Point me to successor | |
| 2503 if( p ) sort( p, innermost ); // Insert my parents into list as well | |
| 2504 return innermost; | |
| 2505 } | |
| 2506 | |
| 2507 //------------------------------build_loop_tree-------------------------------- | |
| 2508 // I use a modified Vick/Tarjan algorithm. I need pre- and a post- visit | |
| 2509 // bits. The _nodes[] array is mapped by Node index and holds a NULL for | |
| 2510 // not-yet-pre-walked, pre-order # for pre-but-not-post-walked and holds the | |
| 2511 // tightest enclosing IdealLoopTree for post-walked. | |
| 2512 // | |
| 2513 // During my forward walk I do a short 1-layer lookahead to see if I can find | |
| 2514 // a loop backedge with that doesn't have any work on the backedge. This | |
| 2515 // helps me construct nested loops with shared headers better. | |
| 2516 // | |
| 2517 // Once I've done the forward recursion, I do the post-work. For each child | |
| 2518 // I check to see if there is a backedge. Backedges define a loop! I | |
| 2519 // insert an IdealLoopTree at the target of the backedge. | |
| 2520 // | |
| 2521 // During the post-work I also check to see if I have several children | |
| 2522 // belonging to different loops. If so, then this Node is a decision point | |
| 2523 // where control flow can choose to change loop nests. It is at this | |
| 2524 // decision point where I can figure out how loops are nested. At this | |
| 2525 // time I can properly order the different loop nests from my children. | |
| 2526 // Note that there may not be any backedges at the decision point! | |
| 2527 // | |
| 2528 // Since the decision point can be far removed from the backedges, I can't | |
| 2529 // order my loops at the time I discover them. Thus at the decision point | |
| 2530 // I need to inspect loop header pre-order numbers to properly nest my | |
| 2531 // loops. This means I need to sort my childrens' loops by pre-order. | |
| 2532 // The sort is of size number-of-control-children, which generally limits | |
| 2533 // it to size 2 (i.e., I just choose between my 2 target loops). | |
| 2534 void PhaseIdealLoop::build_loop_tree() { | |
| 2535 // Allocate stack of size C->unique()/2 to avoid frequent realloc | |
| 2536 GrowableArray <Node *> bltstack(C->unique() >> 1); | |
| 2537 Node *n = C->root(); | |
| 2538 bltstack.push(n); | |
| 2539 int pre_order = 1; | |
| 2540 int stack_size; | |
| 2541 | |
| 2542 while ( ( stack_size = bltstack.length() ) != 0 ) { | |
| 2543 n = bltstack.top(); // Leave node on stack | |
| 2544 if ( !is_visited(n) ) { | |
| 2545 // ---- Pre-pass Work ---- | |
| 2546 // Pre-walked but not post-walked nodes need a pre_order number. | |
| 2547 | |
| 2548 set_preorder_visited( n, pre_order ); // set as visited | |
| 2549 | |
| 2550 // ---- Scan over children ---- | |
| 2551 // Scan first over control projections that lead to loop headers. | |
| 2552 // This helps us find inner-to-outer loops with shared headers better. | |
| 2553 | |
| 2554 // Scan children's children for loop headers. | |
| 2555 for ( int i = n->outcnt() - 1; i >= 0; --i ) { | |
| 2556 Node* m = n->raw_out(i); // Child | |
| 2557 if( m->is_CFG() && !is_visited(m) ) { // Only for CFG children | |
| 2558 // Scan over children's children to find loop | |
| 2559 for (DUIterator_Fast jmax, j = m->fast_outs(jmax); j < jmax; j++) { | |
| 2560 Node* l = m->fast_out(j); | |
| 2561 if( is_visited(l) && // Been visited? | |
| 2562 !is_postvisited(l) && // But not post-visited | |
| 2563 get_preorder(l) < pre_order ) { // And smaller pre-order | |
| 2564 // Found! Scan the DFS down this path before doing other paths | |
| 2565 bltstack.push(m); | |
| 2566 break; | |
| 2567 } | |
| 2568 } | |
| 2569 } | |
| 2570 } | |
| 2571 pre_order++; | |
| 2572 } | |
| 2573 else if ( !is_postvisited(n) ) { | |
| 2574 // Note: build_loop_tree_impl() adds out edges on rare occasions, | |
| 2575 // such as com.sun.rsasign.am::a. | |
| 2576 // For non-recursive version, first, process current children. | |
| 2577 // On next iteration, check if additional children were added. | |
| 2578 for ( int k = n->outcnt() - 1; k >= 0; --k ) { | |
| 2579 Node* u = n->raw_out(k); | |
| 2580 if ( u->is_CFG() && !is_visited(u) ) { | |
| 2581 bltstack.push(u); | |
| 2582 } | |
| 2583 } | |
| 2584 if ( bltstack.length() == stack_size ) { | |
| 2585 // There were no additional children, post visit node now | |
| 2586 (void)bltstack.pop(); // Remove node from stack | |
| 2587 pre_order = build_loop_tree_impl( n, pre_order ); | |
| 2588 // Check for bailout | |
| 2589 if (C->failing()) { | |
| 2590 return; | |
| 2591 } | |
| 2592 // Check to grow _preorders[] array for the case when | |
| 2593 // build_loop_tree_impl() adds new nodes. | |
| 2594 check_grow_preorders(); | |
| 2595 } | |
| 2596 } | |
| 2597 else { | |
| 2598 (void)bltstack.pop(); // Remove post-visited node from stack | |
| 2599 } | |
| 2600 } | |
| 2601 } | |
| 2602 | |
| 2603 //------------------------------build_loop_tree_impl--------------------------- | |
| 2604 int PhaseIdealLoop::build_loop_tree_impl( Node *n, int pre_order ) { | |
| 2605 // ---- Post-pass Work ---- | |
| 2606 // Pre-walked but not post-walked nodes need a pre_order number. | |
| 2607 | |
| 2608 // Tightest enclosing loop for this Node | |
| 2609 IdealLoopTree *innermost = NULL; | |
| 2610 | |
| 2611 // For all children, see if any edge is a backedge. If so, make a loop | |
| 2612 // for it. Then find the tightest enclosing loop for the self Node. | |
| 2613 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) { | |
| 2614 Node* m = n->fast_out(i); // Child | |
| 2615 if( n == m ) continue; // Ignore control self-cycles | |
| 2616 if( !m->is_CFG() ) continue;// Ignore non-CFG edges | |
| 2617 | |
| 2618 IdealLoopTree *l; // Child's loop | |
| 2619 if( !is_postvisited(m) ) { // Child visited but not post-visited? | |
| 2620 // Found a backedge | |
| 2621 assert( get_preorder(m) < pre_order, "should be backedge" ); | |
| 2622 // Check for the RootNode, which is already a LoopNode and is allowed | |
| 2623 // to have multiple "backedges". | |
| 2624 if( m == C->root()) { // Found the root? | |
| 2625 l = _ltree_root; // Root is the outermost LoopNode | |
| 2626 } else { // Else found a nested loop | |
| 2627 // Insert a LoopNode to mark this loop. | |
| 2628 l = new IdealLoopTree(this, m, n); | |
| 2629 } // End of Else found a nested loop | |
| 2630 if( !has_loop(m) ) // If 'm' does not already have a loop set | |
| 2631 set_loop(m, l); // Set loop header to loop now | |
| 2632 | |
| 2633 } else { // Else not a nested loop | |
| 2634 if( !_nodes[m->_idx] ) continue; // Dead code has no loop | |
| 2635 l = get_loop(m); // Get previously determined loop | |
| 2636 // If successor is header of a loop (nest), move up-loop till it | |
| 2637 // is a member of some outer enclosing loop. Since there are no | |
| 2638 // shared headers (I've split them already) I only need to go up | |
| 2639 // at most 1 level. | |
| 2640 while( l && l->_head == m ) // Successor heads loop? | |
| 2641 l = l->_parent; // Move up 1 for me | |
| 2642 // If this loop is not properly parented, then this loop | |
| 2643 // has no exit path out, i.e. its an infinite loop. | |
| 2644 if( !l ) { | |
| 2645 // Make loop "reachable" from root so the CFG is reachable. Basically | |
| 2646 // insert a bogus loop exit that is never taken. 'm', the loop head, | |
| 2647 // points to 'n', one (of possibly many) fall-in paths. There may be | |
| 2648 // many backedges as well. | |
| 2649 | |
| 2650 // Here I set the loop to be the root loop. I could have, after | |
| 2651 // inserting a bogus loop exit, restarted the recursion and found my | |
| 2652 // new loop exit. This would make the infinite loop a first-class | |
| 2653 // loop and it would then get properly optimized. What's the use of | |
| 2654 // optimizing an infinite loop? | |
| 2655 l = _ltree_root; // Oops, found infinite loop | |
| 2656 | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2657 if (!_verify_only) { |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2658 // Insert the NeverBranch between 'm' and it's control user. |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2659 NeverBranchNode *iff = new (C, 1) NeverBranchNode( m ); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2660 _igvn.register_new_node_with_optimizer(iff); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2661 set_loop(iff, l); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2662 Node *if_t = new (C, 1) CProjNode( iff, 0 ); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2663 _igvn.register_new_node_with_optimizer(if_t); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2664 set_loop(if_t, l); |
| 0 | 2665 |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2666 Node* cfg = NULL; // Find the One True Control User of m |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2667 for (DUIterator_Fast jmax, j = m->fast_outs(jmax); j < jmax; j++) { |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2668 Node* x = m->fast_out(j); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2669 if (x->is_CFG() && x != m && x != iff) |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2670 { cfg = x; break; } |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2671 } |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2672 assert(cfg != NULL, "must find the control user of m"); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2673 uint k = 0; // Probably cfg->in(0) |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2674 while( cfg->in(k) != m ) k++; // But check incase cfg is a Region |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2675 cfg->set_req( k, if_t ); // Now point to NeverBranch |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2676 |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2677 // Now create the never-taken loop exit |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2678 Node *if_f = new (C, 1) CProjNode( iff, 1 ); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2679 _igvn.register_new_node_with_optimizer(if_f); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2680 set_loop(if_f, l); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2681 // Find frame ptr for Halt. Relies on the optimizer |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2682 // V-N'ing. Easier and quicker than searching through |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2683 // the program structure. |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2684 Node *frame = new (C, 1) ParmNode( C->start(), TypeFunc::FramePtr ); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2685 _igvn.register_new_node_with_optimizer(frame); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2686 // Halt & Catch Fire |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2687 Node *halt = new (C, TypeFunc::Parms) HaltNode( if_f, frame ); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2688 _igvn.register_new_node_with_optimizer(halt); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2689 set_loop(halt, l); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2690 C->root()->add_req(halt); |
| 0 | 2691 } |
| 2692 set_loop(C->root(), _ltree_root); | |
| 2693 } | |
| 2694 } | |
| 2695 // Weeny check for irreducible. This child was already visited (this | |
| 2696 // IS the post-work phase). Is this child's loop header post-visited | |
| 2697 // as well? If so, then I found another entry into the loop. | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2698 if (!_verify_only) { |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2699 while( is_postvisited(l->_head) ) { |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2700 // found irreducible |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2701 l->_irreducible = 1; // = true |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2702 l = l->_parent; |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2703 _has_irreducible_loops = true; |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2704 // Check for bad CFG here to prevent crash, and bailout of compile |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2705 if (l == NULL) { |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2706 C->record_method_not_compilable("unhandled CFG detected during loop optimization"); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2707 return pre_order; |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2708 } |
| 0 | 2709 } |
| 2710 } | |
| 2711 | |
| 2712 // This Node might be a decision point for loops. It is only if | |
| 2713 // it's children belong to several different loops. The sort call | |
| 2714 // does a trivial amount of work if there is only 1 child or all | |
| 2715 // children belong to the same loop. If however, the children | |
| 2716 // belong to different loops, the sort call will properly set the | |
| 2717 // _parent pointers to show how the loops nest. | |
| 2718 // | |
| 2719 // In any case, it returns the tightest enclosing loop. | |
| 2720 innermost = sort( l, innermost ); | |
| 2721 } | |
| 2722 | |
| 2723 // Def-use info will have some dead stuff; dead stuff will have no | |
| 2724 // loop decided on. | |
| 2725 | |
| 2726 // Am I a loop header? If so fix up my parent's child and next ptrs. | |
| 2727 if( innermost && innermost->_head == n ) { | |
| 2728 assert( get_loop(n) == innermost, "" ); | |
| 2729 IdealLoopTree *p = innermost->_parent; | |
| 2730 IdealLoopTree *l = innermost; | |
| 2731 while( p && l->_head == n ) { | |
| 2732 l->_next = p->_child; // Put self on parents 'next child' | |
| 2733 p->_child = l; // Make self as first child of parent | |
| 2734 l = p; // Now walk up the parent chain | |
| 2735 p = l->_parent; | |
| 2736 } | |
| 2737 } else { | |
| 2738 // Note that it is possible for a LoopNode to reach here, if the | |
| 2739 // backedge has been made unreachable (hence the LoopNode no longer | |
| 2740 // denotes a Loop, and will eventually be removed). | |
| 2741 | |
| 2742 // Record tightest enclosing loop for self. Mark as post-visited. | |
| 2743 set_loop(n, innermost); | |
| 2744 // Also record has_call flag early on | |
| 2745 if( innermost ) { | |
| 2746 if( n->is_Call() && !n->is_CallLeaf() && !n->is_macro() ) { | |
| 2747 // Do not count uncommon calls | |
| 2748 if( !n->is_CallStaticJava() || !n->as_CallStaticJava()->_name ) { | |
| 2749 Node *iff = n->in(0)->in(0); | |
| 2750 if( !iff->is_If() || | |
| 2751 (n->in(0)->Opcode() == Op_IfFalse && | |
| 2752 (1.0 - iff->as_If()->_prob) >= 0.01) || | |
| 2753 (iff->as_If()->_prob >= 0.01) ) | |
| 2754 innermost->_has_call = 1; | |
| 2755 } | |
|
39
76256d272075
6667612: (Escape Analysis) disable loop cloning if it has a scalar replaceable allocation
kvn
parents:
17
diff
changeset
|
2756 } else if( n->is_Allocate() && n->as_Allocate()->_is_scalar_replaceable ) { |
|
76256d272075
6667612: (Escape Analysis) disable loop cloning if it has a scalar replaceable allocation
kvn
parents:
17
diff
changeset
|
2757 // Disable loop optimizations if the loop has a scalar replaceable |
|
76256d272075
6667612: (Escape Analysis) disable loop cloning if it has a scalar replaceable allocation
kvn
parents:
17
diff
changeset
|
2758 // allocation. This disabling may cause a potential performance lost |
|
76256d272075
6667612: (Escape Analysis) disable loop cloning if it has a scalar replaceable allocation
kvn
parents:
17
diff
changeset
|
2759 // if the allocation is not eliminated for some reason. |
|
76256d272075
6667612: (Escape Analysis) disable loop cloning if it has a scalar replaceable allocation
kvn
parents:
17
diff
changeset
|
2760 innermost->_allow_optimizations = false; |
|
76256d272075
6667612: (Escape Analysis) disable loop cloning if it has a scalar replaceable allocation
kvn
parents:
17
diff
changeset
|
2761 innermost->_has_call = 1; // = true |
| 0 | 2762 } |
| 2763 } | |
| 2764 } | |
| 2765 | |
| 2766 // Flag as post-visited now | |
| 2767 set_postvisited(n); | |
| 2768 return pre_order; | |
| 2769 } | |
| 2770 | |
| 2771 | |
| 2772 //------------------------------build_loop_early------------------------------- | |
| 2773 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping. | |
| 2774 // First pass computes the earliest controlling node possible. This is the | |
| 2775 // controlling input with the deepest dominating depth. | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2776 void PhaseIdealLoop::build_loop_early( VectorSet &visited, Node_List &worklist, Node_Stack &nstack ) { |
| 0 | 2777 while (worklist.size() != 0) { |
| 2778 // Use local variables nstack_top_n & nstack_top_i to cache values | |
| 2779 // on nstack's top. | |
| 2780 Node *nstack_top_n = worklist.pop(); | |
| 2781 uint nstack_top_i = 0; | |
| 2782 //while_nstack_nonempty: | |
| 2783 while (true) { | |
| 2784 // Get parent node and next input's index from stack's top. | |
| 2785 Node *n = nstack_top_n; | |
| 2786 uint i = nstack_top_i; | |
| 2787 uint cnt = n->req(); // Count of inputs | |
| 2788 if (i == 0) { // Pre-process the node. | |
| 2789 if( has_node(n) && // Have either loop or control already? | |
| 2790 !has_ctrl(n) ) { // Have loop picked out already? | |
| 2791 // During "merge_many_backedges" we fold up several nested loops | |
| 2792 // into a single loop. This makes the members of the original | |
| 2793 // loop bodies pointing to dead loops; they need to move up | |
| 2794 // to the new UNION'd larger loop. I set the _head field of these | |
| 2795 // dead loops to NULL and the _parent field points to the owning | |
| 2796 // loop. Shades of UNION-FIND algorithm. | |
| 2797 IdealLoopTree *ilt; | |
| 2798 while( !(ilt = get_loop(n))->_head ) { | |
| 2799 // Normally I would use a set_loop here. But in this one special | |
| 2800 // case, it is legal (and expected) to change what loop a Node | |
| 2801 // belongs to. | |
| 2802 _nodes.map(n->_idx, (Node*)(ilt->_parent) ); | |
| 2803 } | |
| 2804 // Remove safepoints ONLY if I've already seen I don't need one. | |
| 2805 // (the old code here would yank a 2nd safepoint after seeing a | |
| 2806 // first one, even though the 1st did not dominate in the loop body | |
| 2807 // and thus could be avoided indefinitely) | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2808 if( !_verify_only && !_verify_me && ilt->_has_sfpt && n->Opcode() == Op_SafePoint && |
| 0 | 2809 is_deleteable_safept(n)) { |
| 2810 Node *in = n->in(TypeFunc::Control); | |
| 2811 lazy_replace(n,in); // Pull safepoint now | |
| 2812 // Carry on with the recursion "as if" we are walking | |
| 2813 // only the control input | |
| 2814 if( !visited.test_set( in->_idx ) ) { | |
| 2815 worklist.push(in); // Visit this guy later, using worklist | |
| 2816 } | |
| 2817 // Get next node from nstack: | |
| 2818 // - skip n's inputs processing by setting i > cnt; | |
| 2819 // - we also will not call set_early_ctrl(n) since | |
| 2820 // has_node(n) == true (see the condition above). | |
| 2821 i = cnt + 1; | |
| 2822 } | |
| 2823 } | |
| 2824 } // if (i == 0) | |
| 2825 | |
| 2826 // Visit all inputs | |
| 2827 bool done = true; // Assume all n's inputs will be processed | |
| 2828 while (i < cnt) { | |
| 2829 Node *in = n->in(i); | |
| 2830 ++i; | |
| 2831 if (in == NULL) continue; | |
| 2832 if (in->pinned() && !in->is_CFG()) | |
| 2833 set_ctrl(in, in->in(0)); | |
| 2834 int is_visited = visited.test_set( in->_idx ); | |
| 2835 if (!has_node(in)) { // No controlling input yet? | |
| 2836 assert( !in->is_CFG(), "CFG Node with no controlling input?" ); | |
| 2837 assert( !is_visited, "visit only once" ); | |
| 2838 nstack.push(n, i); // Save parent node and next input's index. | |
| 2839 nstack_top_n = in; // Process current input now. | |
| 2840 nstack_top_i = 0; | |
| 2841 done = false; // Not all n's inputs processed. | |
| 2842 break; // continue while_nstack_nonempty; | |
| 2843 } else if (!is_visited) { | |
| 2844 // This guy has a location picked out for him, but has not yet | |
| 2845 // been visited. Happens to all CFG nodes, for instance. | |
| 2846 // Visit him using the worklist instead of recursion, to break | |
| 2847 // cycles. Since he has a location already we do not need to | |
| 2848 // find his location before proceeding with the current Node. | |
| 2849 worklist.push(in); // Visit this guy later, using worklist | |
| 2850 } | |
| 2851 } | |
| 2852 if (done) { | |
| 2853 // All of n's inputs have been processed, complete post-processing. | |
| 2854 | |
| 605 | 2855 // Compute earliest point this Node can go. |
| 0 | 2856 // CFG, Phi, pinned nodes already know their controlling input. |
| 2857 if (!has_node(n)) { | |
| 2858 // Record earliest legal location | |
| 2859 set_early_ctrl( n ); | |
| 2860 } | |
| 2861 if (nstack.is_empty()) { | |
| 2862 // Finished all nodes on stack. | |
| 2863 // Process next node on the worklist. | |
| 2864 break; | |
| 2865 } | |
| 2866 // Get saved parent node and next input's index. | |
| 2867 nstack_top_n = nstack.node(); | |
| 2868 nstack_top_i = nstack.index(); | |
| 2869 nstack.pop(); | |
| 2870 } | |
| 2871 } // while (true) | |
| 2872 } | |
| 2873 } | |
| 2874 | |
| 2875 //------------------------------dom_lca_internal-------------------------------- | |
| 2876 // Pair-wise LCA | |
| 2877 Node *PhaseIdealLoop::dom_lca_internal( Node *n1, Node *n2 ) const { | |
| 2878 if( !n1 ) return n2; // Handle NULL original LCA | |
| 2879 assert( n1->is_CFG(), "" ); | |
| 2880 assert( n2->is_CFG(), "" ); | |
| 2881 // find LCA of all uses | |
| 2882 uint d1 = dom_depth(n1); | |
| 2883 uint d2 = dom_depth(n2); | |
| 2884 while (n1 != n2) { | |
| 2885 if (d1 > d2) { | |
| 2886 n1 = idom(n1); | |
| 2887 d1 = dom_depth(n1); | |
| 2888 } else if (d1 < d2) { | |
| 2889 n2 = idom(n2); | |
| 2890 d2 = dom_depth(n2); | |
| 2891 } else { | |
| 2892 // Here d1 == d2. Due to edits of the dominator-tree, sections | |
| 2893 // of the tree might have the same depth. These sections have | |
| 2894 // to be searched more carefully. | |
| 2895 | |
| 2896 // Scan up all the n1's with equal depth, looking for n2. | |
| 2897 Node *t1 = idom(n1); | |
| 2898 while (dom_depth(t1) == d1) { | |
| 2899 if (t1 == n2) return n2; | |
| 2900 t1 = idom(t1); | |
| 2901 } | |
| 2902 // Scan up all the n2's with equal depth, looking for n1. | |
| 2903 Node *t2 = idom(n2); | |
| 2904 while (dom_depth(t2) == d2) { | |
| 2905 if (t2 == n1) return n1; | |
| 2906 t2 = idom(t2); | |
| 2907 } | |
| 2908 // Move up to a new dominator-depth value as well as up the dom-tree. | |
| 2909 n1 = t1; | |
| 2910 n2 = t2; | |
| 2911 d1 = dom_depth(n1); | |
| 2912 d2 = dom_depth(n2); | |
| 2913 } | |
| 2914 } | |
| 2915 return n1; | |
| 2916 } | |
| 2917 | |
| 2918 //------------------------------compute_idom----------------------------------- | |
| 2919 // Locally compute IDOM using dom_lca call. Correct only if the incoming | |
| 2920 // IDOMs are correct. | |
| 2921 Node *PhaseIdealLoop::compute_idom( Node *region ) const { | |
| 2922 assert( region->is_Region(), "" ); | |
| 2923 Node *LCA = NULL; | |
| 2924 for( uint i = 1; i < region->req(); i++ ) { | |
| 2925 if( region->in(i) != C->top() ) | |
| 2926 LCA = dom_lca( LCA, region->in(i) ); | |
| 2927 } | |
| 2928 return LCA; | |
| 2929 } | |
| 2930 | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2931 bool PhaseIdealLoop::verify_dominance(Node* n, Node* use, Node* LCA, Node* early) { |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2932 bool had_error = false; |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2933 #ifdef ASSERT |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2934 if (early != C->root()) { |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2935 // Make sure that there's a dominance path from use to LCA |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2936 Node* d = use; |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2937 while (d != LCA) { |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2938 d = idom(d); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2939 if (d == C->root()) { |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2940 tty->print_cr("*** Use %d isn't dominated by def %s", use->_idx, n->_idx); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2941 n->dump(); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2942 use->dump(); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2943 had_error = true; |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2944 break; |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2945 } |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2946 } |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2947 } |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2948 #endif |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2949 return had_error; |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2950 } |
| 0 | 2951 |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2952 |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2953 Node* PhaseIdealLoop::compute_lca_of_uses(Node* n, Node* early, bool verify) { |
| 0 | 2954 // Compute LCA over list of uses |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2955 bool had_error = false; |
| 0 | 2956 Node *LCA = NULL; |
| 2957 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax && LCA != early; i++) { | |
| 2958 Node* c = n->fast_out(i); | |
| 2959 if (_nodes[c->_idx] == NULL) | |
| 2960 continue; // Skip the occasional dead node | |
| 2961 if( c->is_Phi() ) { // For Phis, we must land above on the path | |
| 2962 for( uint j=1; j<c->req(); j++ ) {// For all inputs | |
| 2963 if( c->in(j) == n ) { // Found matching input? | |
| 2964 Node *use = c->in(0)->in(j); | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2965 if (_verify_only && use->is_top()) continue; |
| 0 | 2966 LCA = dom_lca_for_get_late_ctrl( LCA, use, n ); |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2967 if (verify) had_error = verify_dominance(n, use, LCA, early) || had_error; |
| 0 | 2968 } |
| 2969 } | |
| 2970 } else { | |
| 2971 // For CFG data-users, use is in the block just prior | |
| 2972 Node *use = has_ctrl(c) ? get_ctrl(c) : c->in(0); | |
| 2973 LCA = dom_lca_for_get_late_ctrl( LCA, use, n ); | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2974 if (verify) had_error = verify_dominance(n, use, LCA, early) || had_error; |
| 0 | 2975 } |
| 2976 } | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2977 assert(!had_error, "bad dominance"); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2978 return LCA; |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2979 } |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2980 |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2981 //------------------------------get_late_ctrl---------------------------------- |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2982 // Compute latest legal control. |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2983 Node *PhaseIdealLoop::get_late_ctrl( Node *n, Node *early ) { |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2984 assert(early != NULL, "early control should not be NULL"); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2985 |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2986 Node* LCA = compute_lca_of_uses(n, early); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2987 #ifdef ASSERT |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2988 if (LCA == C->root() && LCA != early) { |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2989 // def doesn't dominate uses so print some useful debugging output |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2990 compute_lca_of_uses(n, early, true); |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2991 } |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
2992 #endif |
| 0 | 2993 |
| 2994 // if this is a load, check for anti-dependent stores | |
| 2995 // We use a conservative algorithm to identify potential interfering | |
| 2996 // instructions and for rescheduling the load. The users of the memory | |
| 2997 // input of this load are examined. Any use which is not a load and is | |
| 2998 // dominated by early is considered a potentially interfering store. | |
| 2999 // This can produce false positives. | |
| 3000 if (n->is_Load() && LCA != early) { | |
| 3001 Node_List worklist; | |
| 3002 | |
| 3003 Node *mem = n->in(MemNode::Memory); | |
| 3004 for (DUIterator_Fast imax, i = mem->fast_outs(imax); i < imax; i++) { | |
| 3005 Node* s = mem->fast_out(i); | |
| 3006 worklist.push(s); | |
| 3007 } | |
| 3008 while(worklist.size() != 0 && LCA != early) { | |
| 3009 Node* s = worklist.pop(); | |
| 3010 if (s->is_Load()) { | |
| 3011 continue; | |
| 3012 } else if (s->is_MergeMem()) { | |
| 3013 for (DUIterator_Fast imax, i = s->fast_outs(imax); i < imax; i++) { | |
| 3014 Node* s1 = s->fast_out(i); | |
| 3015 worklist.push(s1); | |
| 3016 } | |
| 3017 } else { | |
| 3018 Node *sctrl = has_ctrl(s) ? get_ctrl(s) : s->in(0); | |
| 3019 assert(sctrl != NULL || s->outcnt() == 0, "must have control"); | |
| 3020 if (sctrl != NULL && !sctrl->is_top() && is_dominator(early, sctrl)) { | |
| 3021 LCA = dom_lca_for_get_late_ctrl(LCA, sctrl, n); | |
| 3022 } | |
| 3023 } | |
| 3024 } | |
| 3025 } | |
| 3026 | |
| 3027 assert(LCA == find_non_split_ctrl(LCA), "unexpected late control"); | |
| 3028 return LCA; | |
| 3029 } | |
| 3030 | |
| 3031 // true if CFG node d dominates CFG node n | |
| 3032 bool PhaseIdealLoop::is_dominator(Node *d, Node *n) { | |
| 3033 if (d == n) | |
| 3034 return true; | |
| 3035 assert(d->is_CFG() && n->is_CFG(), "must have CFG nodes"); | |
| 3036 uint dd = dom_depth(d); | |
| 3037 while (dom_depth(n) >= dd) { | |
| 3038 if (n == d) | |
| 3039 return true; | |
| 3040 n = idom(n); | |
| 3041 } | |
| 3042 return false; | |
| 3043 } | |
| 3044 | |
| 3045 //------------------------------dom_lca_for_get_late_ctrl_internal------------- | |
| 3046 // Pair-wise LCA with tags. | |
| 3047 // Tag each index with the node 'tag' currently being processed | |
| 3048 // before advancing up the dominator chain using idom(). | |
| 3049 // Later calls that find a match to 'tag' know that this path has already | |
| 3050 // been considered in the current LCA (which is input 'n1' by convention). | |
| 3051 // Since get_late_ctrl() is only called once for each node, the tag array | |
| 3052 // does not need to be cleared between calls to get_late_ctrl(). | |
| 3053 // Algorithm trades a larger constant factor for better asymptotic behavior | |
| 3054 // | |
| 3055 Node *PhaseIdealLoop::dom_lca_for_get_late_ctrl_internal( Node *n1, Node *n2, Node *tag ) { | |
| 3056 uint d1 = dom_depth(n1); | |
| 3057 uint d2 = dom_depth(n2); | |
| 3058 | |
| 3059 do { | |
| 3060 if (d1 > d2) { | |
| 3061 // current lca is deeper than n2 | |
| 3062 _dom_lca_tags.map(n1->_idx, tag); | |
| 3063 n1 = idom(n1); | |
| 3064 d1 = dom_depth(n1); | |
| 3065 } else if (d1 < d2) { | |
| 3066 // n2 is deeper than current lca | |
| 3067 Node *memo = _dom_lca_tags[n2->_idx]; | |
| 3068 if( memo == tag ) { | |
| 3069 return n1; // Return the current LCA | |
| 3070 } | |
| 3071 _dom_lca_tags.map(n2->_idx, tag); | |
| 3072 n2 = idom(n2); | |
| 3073 d2 = dom_depth(n2); | |
| 3074 } else { | |
| 3075 // Here d1 == d2. Due to edits of the dominator-tree, sections | |
| 3076 // of the tree might have the same depth. These sections have | |
| 3077 // to be searched more carefully. | |
| 3078 | |
| 3079 // Scan up all the n1's with equal depth, looking for n2. | |
| 3080 _dom_lca_tags.map(n1->_idx, tag); | |
| 3081 Node *t1 = idom(n1); | |
| 3082 while (dom_depth(t1) == d1) { | |
| 3083 if (t1 == n2) return n2; | |
| 3084 _dom_lca_tags.map(t1->_idx, tag); | |
| 3085 t1 = idom(t1); | |
| 3086 } | |
| 3087 // Scan up all the n2's with equal depth, looking for n1. | |
| 3088 _dom_lca_tags.map(n2->_idx, tag); | |
| 3089 Node *t2 = idom(n2); | |
| 3090 while (dom_depth(t2) == d2) { | |
| 3091 if (t2 == n1) return n1; | |
| 3092 _dom_lca_tags.map(t2->_idx, tag); | |
| 3093 t2 = idom(t2); | |
| 3094 } | |
| 3095 // Move up to a new dominator-depth value as well as up the dom-tree. | |
| 3096 n1 = t1; | |
| 3097 n2 = t2; | |
| 3098 d1 = dom_depth(n1); | |
| 3099 d2 = dom_depth(n2); | |
| 3100 } | |
| 3101 } while (n1 != n2); | |
| 3102 return n1; | |
| 3103 } | |
| 3104 | |
| 3105 //------------------------------init_dom_lca_tags------------------------------ | |
| 3106 // Tag could be a node's integer index, 32bits instead of 64bits in some cases | |
| 3107 // Intended use does not involve any growth for the array, so it could | |
| 3108 // be of fixed size. | |
| 3109 void PhaseIdealLoop::init_dom_lca_tags() { | |
| 3110 uint limit = C->unique() + 1; | |
| 3111 _dom_lca_tags.map( limit, NULL ); | |
| 3112 #ifdef ASSERT | |
| 3113 for( uint i = 0; i < limit; ++i ) { | |
| 3114 assert(_dom_lca_tags[i] == NULL, "Must be distinct from each node pointer"); | |
| 3115 } | |
| 3116 #endif // ASSERT | |
| 3117 } | |
| 3118 | |
| 3119 //------------------------------clear_dom_lca_tags------------------------------ | |
| 3120 // Tag could be a node's integer index, 32bits instead of 64bits in some cases | |
| 3121 // Intended use does not involve any growth for the array, so it could | |
| 3122 // be of fixed size. | |
| 3123 void PhaseIdealLoop::clear_dom_lca_tags() { | |
| 3124 uint limit = C->unique() + 1; | |
| 3125 _dom_lca_tags.map( limit, NULL ); | |
| 3126 _dom_lca_tags.clear(); | |
| 3127 #ifdef ASSERT | |
| 3128 for( uint i = 0; i < limit; ++i ) { | |
| 3129 assert(_dom_lca_tags[i] == NULL, "Must be distinct from each node pointer"); | |
| 3130 } | |
| 3131 #endif // ASSERT | |
| 3132 } | |
| 3133 | |
| 3134 //------------------------------build_loop_late-------------------------------- | |
| 3135 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping. | |
| 3136 // Second pass finds latest legal placement, and ideal loop placement. | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
3137 void PhaseIdealLoop::build_loop_late( VectorSet &visited, Node_List &worklist, Node_Stack &nstack ) { |
| 0 | 3138 while (worklist.size() != 0) { |
| 3139 Node *n = worklist.pop(); | |
| 3140 // Only visit once | |
| 3141 if (visited.test_set(n->_idx)) continue; | |
| 3142 uint cnt = n->outcnt(); | |
| 3143 uint i = 0; | |
| 3144 while (true) { | |
| 3145 assert( _nodes[n->_idx], "no dead nodes" ); | |
| 3146 // Visit all children | |
| 3147 if (i < cnt) { | |
| 3148 Node* use = n->raw_out(i); | |
| 3149 ++i; | |
| 3150 // Check for dead uses. Aggressively prune such junk. It might be | |
| 3151 // dead in the global sense, but still have local uses so I cannot | |
| 3152 // easily call 'remove_dead_node'. | |
| 3153 if( _nodes[use->_idx] != NULL || use->is_top() ) { // Not dead? | |
| 3154 // Due to cycles, we might not hit the same fixed point in the verify | |
| 3155 // pass as we do in the regular pass. Instead, visit such phis as | |
| 3156 // simple uses of the loop head. | |
| 3157 if( use->in(0) && (use->is_CFG() || use->is_Phi()) ) { | |
| 3158 if( !visited.test(use->_idx) ) | |
| 3159 worklist.push(use); | |
| 3160 } else if( !visited.test_set(use->_idx) ) { | |
| 3161 nstack.push(n, i); // Save parent and next use's index. | |
| 3162 n = use; // Process all children of current use. | |
| 3163 cnt = use->outcnt(); | |
| 3164 i = 0; | |
| 3165 } | |
| 3166 } else { | |
| 3167 // Do not visit around the backedge of loops via data edges. | |
| 3168 // push dead code onto a worklist | |
| 3169 _deadlist.push(use); | |
| 3170 } | |
| 3171 } else { | |
| 3172 // All of n's children have been processed, complete post-processing. | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
3173 build_loop_late_post(n); |
| 0 | 3174 if (nstack.is_empty()) { |
| 3175 // Finished all nodes on stack. | |
| 3176 // Process next node on the worklist. | |
| 3177 break; | |
| 3178 } | |
| 3179 // Get saved parent node and next use's index. Visit the rest of uses. | |
| 3180 n = nstack.node(); | |
| 3181 cnt = n->outcnt(); | |
| 3182 i = nstack.index(); | |
| 3183 nstack.pop(); | |
| 3184 } | |
| 3185 } | |
| 3186 } | |
| 3187 } | |
| 3188 | |
| 3189 //------------------------------build_loop_late_post--------------------------- | |
| 3190 // Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping. | |
| 3191 // Second pass finds latest legal placement, and ideal loop placement. | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
3192 void PhaseIdealLoop::build_loop_late_post( Node *n ) { |
| 0 | 3193 |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
3194 if (n->req() == 2 && n->Opcode() == Op_ConvI2L && !C->major_progress() && !_verify_only) { |
| 0 | 3195 _igvn._worklist.push(n); // Maybe we'll normalize it, if no more loops. |
| 3196 } | |
| 3197 | |
| 3198 // CFG and pinned nodes already handled | |
| 3199 if( n->in(0) ) { | |
| 3200 if( n->in(0)->is_top() ) return; // Dead? | |
| 3201 | |
| 3202 // We'd like +VerifyLoopOptimizations to not believe that Mod's/Loads | |
| 3203 // _must_ be pinned (they have to observe their control edge of course). | |
| 3204 // Unlike Stores (which modify an unallocable resource, the memory | |
| 3205 // state), Mods/Loads can float around. So free them up. | |
| 3206 bool pinned = true; | |
| 3207 switch( n->Opcode() ) { | |
| 3208 case Op_DivI: | |
| 3209 case Op_DivF: | |
| 3210 case Op_DivD: | |
| 3211 case Op_ModI: | |
| 3212 case Op_ModF: | |
| 3213 case Op_ModD: | |
| 3214 case Op_LoadB: // Same with Loads; they can sink | |
|
558
3b5ac9e7e6ea
6796746: rename LoadC (char) opcode class to LoadUS (unsigned short)
twisti
parents:
367
diff
changeset
|
3215 case Op_LoadUS: // during loop optimizations. |
| 0 | 3216 case Op_LoadD: |
| 3217 case Op_LoadF: | |
| 3218 case Op_LoadI: | |
| 3219 case Op_LoadKlass: | |
|
293
c3e045194476
6731641: assert(m->adr_type() == mach->adr_type(),"matcher should not change adr type")
kvn
parents:
235
diff
changeset
|
3220 case Op_LoadNKlass: |
| 0 | 3221 case Op_LoadL: |
| 3222 case Op_LoadS: | |
| 3223 case Op_LoadP: | |
|
293
c3e045194476
6731641: assert(m->adr_type() == mach->adr_type(),"matcher should not change adr type")
kvn
parents:
235
diff
changeset
|
3224 case Op_LoadN: |
| 0 | 3225 case Op_LoadRange: |
| 3226 case Op_LoadD_unaligned: | |
| 3227 case Op_LoadL_unaligned: | |
| 3228 case Op_StrComp: // Does a bunch of load-like effects | |
| 681 | 3229 case Op_StrEquals: |
| 3230 case Op_StrIndexOf: | |
|
169
9148c65abefc
6695049: (coll) Create an x86 intrinsic for Arrays.equals
rasbold
parents:
39
diff
changeset
|
3231 case Op_AryEq: |
| 0 | 3232 pinned = false; |
| 3233 } | |
| 3234 if( pinned ) { | |
| 605 | 3235 IdealLoopTree *chosen_loop = get_loop(n->is_CFG() ? n : get_ctrl(n)); |
| 3236 if( !chosen_loop->_child ) // Inner loop? | |
| 3237 chosen_loop->_body.push(n); // Collect inner loops | |
| 0 | 3238 return; |
| 3239 } | |
| 3240 } else { // No slot zero | |
| 3241 if( n->is_CFG() ) { // CFG with no slot 0 is dead | |
| 3242 _nodes.map(n->_idx,0); // No block setting, it's globally dead | |
| 3243 return; | |
| 3244 } | |
| 3245 assert(!n->is_CFG() || n->outcnt() == 0, ""); | |
| 3246 } | |
| 3247 | |
| 3248 // Do I have a "safe range" I can select over? | |
| 3249 Node *early = get_ctrl(n);// Early location already computed | |
| 3250 | |
| 3251 // Compute latest point this Node can go | |
| 3252 Node *LCA = get_late_ctrl( n, early ); | |
| 3253 // LCA is NULL due to uses being dead | |
| 3254 if( LCA == NULL ) { | |
| 3255 #ifdef ASSERT | |
| 3256 for (DUIterator i1 = n->outs(); n->has_out(i1); i1++) { | |
| 3257 assert( _nodes[n->out(i1)->_idx] == NULL, "all uses must also be dead"); | |
| 3258 } | |
| 3259 #endif | |
| 3260 _nodes.map(n->_idx, 0); // This node is useless | |
| 3261 _deadlist.push(n); | |
| 3262 return; | |
| 3263 } | |
| 3264 assert(LCA != NULL && !LCA->is_top(), "no dead nodes"); | |
| 3265 | |
| 3266 Node *legal = LCA; // Walk 'legal' up the IDOM chain | |
| 3267 Node *least = legal; // Best legal position so far | |
| 3268 while( early != legal ) { // While not at earliest legal | |
| 1172 | 3269 #ifdef ASSERT |
| 3270 if (legal->is_Start() && !early->is_Root()) { | |
| 3271 // Bad graph. Print idom path and fail. | |
| 3272 tty->print_cr( "Bad graph detected in build_loop_late"); | |
| 3273 tty->print("n: ");n->dump(); tty->cr(); | |
| 3274 tty->print("early: ");early->dump(); tty->cr(); | |
| 3275 int ct = 0; | |
| 3276 Node *dbg_legal = LCA; | |
| 3277 while(!dbg_legal->is_Start() && ct < 100) { | |
| 3278 tty->print("idom[%d] ",ct); dbg_legal->dump(); tty->cr(); | |
| 3279 ct++; | |
| 3280 dbg_legal = idom(dbg_legal); | |
| 3281 } | |
| 3282 assert(false, "Bad graph detected in build_loop_late"); | |
| 3283 } | |
| 3284 #endif | |
| 0 | 3285 // Find least loop nesting depth |
| 3286 legal = idom(legal); // Bump up the IDOM tree | |
| 3287 // Check for lower nesting depth | |
| 3288 if( get_loop(legal)->_nest < get_loop(least)->_nest ) | |
| 3289 least = legal; | |
| 3290 } | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
3291 assert(early == legal || legal != C->root(), "bad dominance of inputs"); |
| 0 | 3292 |
| 3293 // Try not to place code on a loop entry projection | |
| 3294 // which can inhibit range check elimination. | |
| 3295 if (least != early) { | |
| 3296 Node* ctrl_out = least->unique_ctrl_out(); | |
| 3297 if (ctrl_out && ctrl_out->is_CountedLoop() && | |
| 3298 least == ctrl_out->in(LoopNode::EntryControl)) { | |
| 3299 Node* least_dom = idom(least); | |
| 3300 if (get_loop(least_dom)->is_member(get_loop(least))) { | |
| 3301 least = least_dom; | |
| 3302 } | |
| 3303 } | |
| 3304 } | |
| 3305 | |
| 3306 #ifdef ASSERT | |
| 3307 // If verifying, verify that 'verify_me' has a legal location | |
| 3308 // and choose it as our location. | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
3309 if( _verify_me ) { |
|
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
681
diff
changeset
|
3310 Node *v_ctrl = _verify_me->get_ctrl_no_update(n); |
| 0 | 3311 Node *legal = LCA; |
| 3312 while( early != legal ) { // While not at earliest legal | |
| 3313 if( legal == v_ctrl ) break; // Check for prior good location | |
| 3314 legal = idom(legal) ;// Bump up the IDOM tree | |
| 3315 } | |
| 3316 // Check for prior good location | |
| 3317 if( legal == v_ctrl ) least = legal; // Keep prior if found | |
| 3318 } | |
| 3319 #endif | |
| 3320 | |
| 3321 // Assign discovered "here or above" point | |
| 3322 least = find_non_split_ctrl(least); | |
| 3323 set_ctrl(n, least); | |
| 3324 | |
| 3325 // Collect inner loop bodies | |
| 605 | 3326 IdealLoopTree *chosen_loop = get_loop(least); |
| 3327 if( !chosen_loop->_child ) // Inner loop? | |
| 3328 chosen_loop->_body.push(n);// Collect inner loops | |
| 0 | 3329 } |
| 3330 | |
| 3331 #ifndef PRODUCT | |
| 3332 //------------------------------dump------------------------------------------- | |
| 3333 void PhaseIdealLoop::dump( ) const { | |
| 3334 ResourceMark rm; | |
| 3335 Arena* arena = Thread::current()->resource_area(); | |
| 3336 Node_Stack stack(arena, C->unique() >> 2); | |
| 3337 Node_List rpo_list; | |
| 3338 VectorSet visited(arena); | |
| 3339 visited.set(C->top()->_idx); | |
| 3340 rpo( C->root(), stack, visited, rpo_list ); | |
| 3341 // Dump root loop indexed by last element in PO order | |
| 3342 dump( _ltree_root, rpo_list.size(), rpo_list ); | |
| 3343 } | |
| 3344 | |
| 3345 void PhaseIdealLoop::dump( IdealLoopTree *loop, uint idx, Node_List &rpo_list ) const { | |
|
367
194b8e3a2fc4
6384206: Phis which are later unneeded are impairing our ability to inline based on static types
never
parents:
293
diff
changeset
|
3346 loop->dump_head(); |
| 0 | 3347 |
| 3348 // Now scan for CFG nodes in the same loop | |
| 3349 for( uint j=idx; j > 0; j-- ) { | |
| 3350 Node *n = rpo_list[j-1]; | |
| 3351 if( !_nodes[n->_idx] ) // Skip dead nodes | |
| 3352 continue; | |
| 3353 if( get_loop(n) != loop ) { // Wrong loop nest | |
| 3354 if( get_loop(n)->_head == n && // Found nested loop? | |
| 3355 get_loop(n)->_parent == loop ) | |
| 3356 dump(get_loop(n),rpo_list.size(),rpo_list); // Print it nested-ly | |
| 3357 continue; | |
| 3358 } | |
| 3359 | |
| 3360 // Dump controlling node | |
| 3361 for( uint x = 0; x < loop->_nest; x++ ) | |
| 3362 tty->print(" "); | |
| 3363 tty->print("C"); | |
| 3364 if( n == C->root() ) { | |
| 3365 n->dump(); | |
| 3366 } else { | |
| 3367 Node* cached_idom = idom_no_update(n); | |
| 3368 Node *computed_idom = n->in(0); | |
| 3369 if( n->is_Region() ) { | |
| 3370 computed_idom = compute_idom(n); | |
| 3371 // computed_idom() will return n->in(0) when idom(n) is an IfNode (or | |
| 3372 // any MultiBranch ctrl node), so apply a similar transform to | |
| 3373 // the cached idom returned from idom_no_update. | |
| 3374 cached_idom = find_non_split_ctrl(cached_idom); | |
| 3375 } | |
| 3376 tty->print(" ID:%d",computed_idom->_idx); | |
| 3377 n->dump(); | |
| 3378 if( cached_idom != computed_idom ) { | |
| 3379 tty->print_cr("*** BROKEN IDOM! Computed as: %d, cached as: %d", | |
| 3380 computed_idom->_idx, cached_idom->_idx); | |
| 3381 } | |
| 3382 } | |
| 3383 // Dump nodes it controls | |
| 3384 for( uint k = 0; k < _nodes.Size(); k++ ) { | |
| 3385 // (k < C->unique() && get_ctrl(find(k)) == n) | |
| 3386 if (k < C->unique() && _nodes[k] == (Node*)((intptr_t)n + 1)) { | |
| 3387 Node *m = C->root()->find(k); | |
| 3388 if( m && m->outcnt() > 0 ) { | |
| 3389 if (!(has_ctrl(m) && get_ctrl_no_update(m) == n)) { | |
| 3390 tty->print_cr("*** BROKEN CTRL ACCESSOR! _nodes[k] is %p, ctrl is %p", | |
| 3391 _nodes[k], has_ctrl(m) ? get_ctrl_no_update(m) : NULL); | |
| 3392 } | |
| 3393 for( uint j = 0; j < loop->_nest; j++ ) | |
| 3394 tty->print(" "); | |
| 3395 tty->print(" "); | |
| 3396 m->dump(); | |
| 3397 } | |
| 3398 } | |
| 3399 } | |
| 3400 } | |
| 3401 } | |
| 3402 | |
| 3403 // Collect a R-P-O for the whole CFG. | |
| 3404 // Result list is in post-order (scan backwards for RPO) | |
| 3405 void PhaseIdealLoop::rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const { | |
| 3406 stk.push(start, 0); | |
| 3407 visited.set(start->_idx); | |
| 3408 | |
| 3409 while (stk.is_nonempty()) { | |
| 3410 Node* m = stk.node(); | |
| 3411 uint idx = stk.index(); | |
| 3412 if (idx < m->outcnt()) { | |
| 3413 stk.set_index(idx + 1); | |
| 3414 Node* n = m->raw_out(idx); | |
| 3415 if (n->is_CFG() && !visited.test_set(n->_idx)) { | |
| 3416 stk.push(n, 0); | |
| 3417 } | |
| 3418 } else { | |
| 3419 rpo_list.push(m); | |
| 3420 stk.pop(); | |
| 3421 } | |
| 3422 } | |
| 3423 } | |
| 3424 #endif | |
| 3425 | |
| 3426 | |
| 3427 //============================================================================= | |
| 3428 //------------------------------LoopTreeIterator----------------------------------- | |
| 3429 | |
| 3430 // Advance to next loop tree using a preorder, left-to-right traversal. | |
| 3431 void LoopTreeIterator::next() { | |
| 3432 assert(!done(), "must not be done."); | |
| 3433 if (_curnt->_child != NULL) { | |
| 3434 _curnt = _curnt->_child; | |
| 3435 } else if (_curnt->_next != NULL) { | |
| 3436 _curnt = _curnt->_next; | |
| 3437 } else { | |
| 3438 while (_curnt != _root && _curnt->_next == NULL) { | |
| 3439 _curnt = _curnt->_parent; | |
| 3440 } | |
| 3441 if (_curnt == _root) { | |
| 3442 _curnt = NULL; | |
| 3443 assert(done(), "must be done."); | |
| 3444 } else { | |
| 3445 assert(_curnt->_next != NULL, "must be more to do"); | |
| 3446 _curnt = _curnt->_next; | |
| 3447 } | |
| 3448 } | |
| 3449 } |