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