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