1 /* 2 * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved. 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 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25 #include "precompiled.hpp" 26 #include "opto/loopnode.hpp" 27 #include "opto/addnode.hpp" 28 #include "opto/callnode.hpp" 29 #include "opto/connode.hpp" 30 #include "opto/convertnode.hpp" 31 #include "opto/loopnode.hpp" 32 #include "opto/mulnode.hpp" 33 #include "opto/opaquenode.hpp" 34 #include "opto/rootnode.hpp" 35 #include "opto/subnode.hpp" 36 37 /* 38 * The general idea of Loop Predication is to insert a predicate on the entry 39 * path to a loop, and raise a uncommon trap if the check of the condition fails. 40 * The condition checks are promoted from inside the loop body, and thus 41 * the checks inside the loop could be eliminated. Currently, loop predication 42 * optimization has been applied to remove array range check and loop invariant 43 * checks (such as null checks). 44 */ 45 46 //-------------------------------register_control------------------------- 47 void PhaseIdealLoop::register_control(Node* n, IdealLoopTree *loop, Node* pred) { 48 assert(n->is_CFG(), "must be control node"); 49 _igvn.register_new_node_with_optimizer(n); 50 loop->_body.push(n); 51 set_loop(n, loop); 52 // When called from beautify_loops() idom is not constructed yet. 53 if (_idom != NULL) { 54 set_idom(n, pred, dom_depth(pred)); 55 } 56 } 57 58 //------------------------------create_new_if_for_predicate------------------------ 59 // create a new if above the uct_if_pattern for the predicate to be promoted. 60 // 61 // before after 62 // ---------- ---------- 63 // ctrl ctrl 64 // | | 65 // | | 66 // v v 67 // iff new_iff 68 // / \ / \ 69 // / \ / \ 70 // v v v v 71 // uncommon_proj cont_proj if_uct if_cont 72 // \ | | | | 73 // \ | | | | 74 // v v v | v 75 // rgn loop | iff 76 // | | / \ 77 // | | / \ 78 // v | v v 79 // uncommon_trap | uncommon_proj cont_proj 80 // \ \ | | 81 // \ \ | | 82 // v v v v 83 // rgn loop 84 // | 85 // | 86 // v 87 // uncommon_trap 88 // 89 // 90 // We will create a region to guard the uct call if there is no one there. 91 // The true projecttion (if_cont) of the new_iff is returned. 92 // This code is also used to clone predicates to cloned loops. 93 ProjNode* PhaseIdealLoop::create_new_if_for_predicate(ProjNode* cont_proj, Node* new_entry, 94 Deoptimization::DeoptReason reason) { 95 assert(cont_proj->is_uncommon_trap_if_pattern(reason), "must be a uct if pattern!"); 96 IfNode* iff = cont_proj->in(0)->as_If(); 97 98 ProjNode *uncommon_proj = iff->proj_out(1 - cont_proj->_con); 99 Node *rgn = uncommon_proj->unique_ctrl_out(); 100 assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct"); 101 102 uint proj_index = 1; // region's edge corresponding to uncommon_proj 103 if (!rgn->is_Region()) { // create a region to guard the call 104 assert(rgn->is_Call(), "must be call uct"); 105 CallNode* call = rgn->as_Call(); 106 IdealLoopTree* loop = get_loop(call); 107 rgn = new RegionNode(1); 108 rgn->add_req(uncommon_proj); 109 register_control(rgn, loop, uncommon_proj); 110 _igvn.replace_input_of(call, 0, rgn); 111 // When called from beautify_loops() idom is not constructed yet. 112 if (_idom != NULL) { 113 set_idom(call, rgn, dom_depth(rgn)); 114 } 115 } else { 116 // Find region's edge corresponding to uncommon_proj 117 for (; proj_index < rgn->req(); proj_index++) 118 if (rgn->in(proj_index) == uncommon_proj) break; 119 assert(proj_index < rgn->req(), "sanity"); 120 } 121 122 Node* entry = iff->in(0); 123 if (new_entry != NULL) { 124 // Clonning the predicate to new location. 125 entry = new_entry; 126 } 127 // Create new_iff 128 IdealLoopTree* lp = get_loop(entry); 129 IfNode *new_iff = iff->clone()->as_If(); 130 new_iff->set_req(0, entry); 131 register_control(new_iff, lp, entry); 132 Node *if_cont = new IfTrueNode(new_iff); 133 Node *if_uct = new IfFalseNode(new_iff); 134 if (cont_proj->is_IfFalse()) { 135 // Swap 136 Node* tmp = if_uct; if_uct = if_cont; if_cont = tmp; 137 } 138 register_control(if_cont, lp, new_iff); 139 register_control(if_uct, get_loop(rgn), new_iff); 140 141 // if_uct to rgn 142 _igvn.hash_delete(rgn); 143 rgn->add_req(if_uct); 144 // When called from beautify_loops() idom is not constructed yet. 145 if (_idom != NULL) { 146 Node* ridom = idom(rgn); 147 Node* nrdom = dom_lca(ridom, new_iff); 148 set_idom(rgn, nrdom, dom_depth(rgn)); 149 } 150 151 // If rgn has phis add new edges which has the same 152 // value as on original uncommon_proj pass. 153 assert(rgn->in(rgn->req() -1) == if_uct, "new edge should be last"); 154 bool has_phi = false; 155 for (DUIterator_Fast imax, i = rgn->fast_outs(imax); i < imax; i++) { 156 Node* use = rgn->fast_out(i); 157 if (use->is_Phi() && use->outcnt() > 0) { 158 assert(use->in(0) == rgn, ""); 159 _igvn.rehash_node_delayed(use); 160 use->add_req(use->in(proj_index)); 161 has_phi = true; 162 } 163 } 164 assert(!has_phi || rgn->req() > 3, "no phis when region is created"); 165 166 if (new_entry == NULL) { 167 // Attach if_cont to iff 168 _igvn.replace_input_of(iff, 0, if_cont); 169 if (_idom != NULL) { 170 set_idom(iff, if_cont, dom_depth(iff)); 171 } 172 } 173 return if_cont->as_Proj(); 174 } 175 176 //------------------------------create_new_if_for_predicate------------------------ 177 // Create a new if below new_entry for the predicate to be cloned (IGVN optimization) 178 ProjNode* PhaseIterGVN::create_new_if_for_predicate(ProjNode* cont_proj, Node* new_entry, 179 Deoptimization::DeoptReason reason) { 180 assert(new_entry != 0, "only used for clone predicate"); 181 assert(cont_proj->is_uncommon_trap_if_pattern(reason), "must be a uct if pattern!"); 182 IfNode* iff = cont_proj->in(0)->as_If(); 183 184 ProjNode *uncommon_proj = iff->proj_out(1 - cont_proj->_con); 185 Node *rgn = uncommon_proj->unique_ctrl_out(); 186 assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct"); 187 188 uint proj_index = 1; // region's edge corresponding to uncommon_proj 189 if (!rgn->is_Region()) { // create a region to guard the call 190 assert(rgn->is_Call(), "must be call uct"); 191 CallNode* call = rgn->as_Call(); 192 rgn = new RegionNode(1); 193 register_new_node_with_optimizer(rgn); 194 rgn->add_req(uncommon_proj); 195 replace_input_of(call, 0, rgn); 196 } else { 197 // Find region's edge corresponding to uncommon_proj 198 for (; proj_index < rgn->req(); proj_index++) 199 if (rgn->in(proj_index) == uncommon_proj) break; 200 assert(proj_index < rgn->req(), "sanity"); 201 } 202 203 // Create new_iff in new location. 204 IfNode *new_iff = iff->clone()->as_If(); 205 new_iff->set_req(0, new_entry); 206 207 register_new_node_with_optimizer(new_iff); 208 Node *if_cont = new IfTrueNode(new_iff); 209 Node *if_uct = new IfFalseNode(new_iff); 210 if (cont_proj->is_IfFalse()) { 211 // Swap 212 Node* tmp = if_uct; if_uct = if_cont; if_cont = tmp; 213 } 214 register_new_node_with_optimizer(if_cont); 215 register_new_node_with_optimizer(if_uct); 216 217 // if_uct to rgn 218 hash_delete(rgn); 219 rgn->add_req(if_uct); 220 221 // If rgn has phis add corresponding new edges which has the same 222 // value as on original uncommon_proj pass. 223 assert(rgn->in(rgn->req() -1) == if_uct, "new edge should be last"); 224 bool has_phi = false; 225 for (DUIterator_Fast imax, i = rgn->fast_outs(imax); i < imax; i++) { 226 Node* use = rgn->fast_out(i); 227 if (use->is_Phi() && use->outcnt() > 0) { 228 rehash_node_delayed(use); 229 use->add_req(use->in(proj_index)); 230 has_phi = true; 231 } 232 } 233 assert(!has_phi || rgn->req() > 3, "no phis when region is created"); 234 235 return if_cont->as_Proj(); 236 } 237 238 //--------------------------clone_predicate----------------------- 239 ProjNode* PhaseIdealLoop::clone_predicate(ProjNode* predicate_proj, Node* new_entry, 240 Deoptimization::DeoptReason reason, 241 PhaseIdealLoop* loop_phase, 242 PhaseIterGVN* igvn) { 243 ProjNode* new_predicate_proj; 244 if (loop_phase != NULL) { 245 new_predicate_proj = loop_phase->create_new_if_for_predicate(predicate_proj, new_entry, reason); 246 } else { 247 new_predicate_proj = igvn->create_new_if_for_predicate(predicate_proj, new_entry, reason); 248 } 249 IfNode* iff = new_predicate_proj->in(0)->as_If(); 250 Node* ctrl = iff->in(0); 251 252 // Match original condition since predicate's projections could be swapped. 253 assert(predicate_proj->in(0)->in(1)->in(1)->Opcode()==Op_Opaque1, "must be"); 254 Node* opq = new Opaque1Node(igvn->C, predicate_proj->in(0)->in(1)->in(1)->in(1)); 255 igvn->C->add_predicate_opaq(opq); 256 257 Node* bol = new Conv2BNode(opq); 258 if (loop_phase != NULL) { 259 loop_phase->register_new_node(opq, ctrl); 260 loop_phase->register_new_node(bol, ctrl); 261 } else { 262 igvn->register_new_node_with_optimizer(opq); 263 igvn->register_new_node_with_optimizer(bol); 264 } 265 igvn->hash_delete(iff); 266 iff->set_req(1, bol); 267 return new_predicate_proj; 268 } 269 270 271 //--------------------------clone_loop_predicates----------------------- 272 // Interface from IGVN 273 Node* PhaseIterGVN::clone_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check) { 274 return PhaseIdealLoop::clone_loop_predicates(old_entry, new_entry, clone_limit_check, NULL, this); 275 } 276 277 // Interface from PhaseIdealLoop 278 Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry, bool clone_limit_check) { 279 return clone_loop_predicates(old_entry, new_entry, clone_limit_check, this, &this->_igvn); 280 } 281 282 // Clone loop predicates to cloned loops (peeled, unswitched, split_if). 283 Node* PhaseIdealLoop::clone_loop_predicates(Node* old_entry, Node* new_entry, 284 bool clone_limit_check, 285 PhaseIdealLoop* loop_phase, 286 PhaseIterGVN* igvn) { 287 #ifdef ASSERT 288 if (new_entry == NULL || !(new_entry->is_Proj() || new_entry->is_Region() || new_entry->is_SafePoint())) { 289 if (new_entry != NULL) 290 new_entry->dump(); 291 assert(false, "not IfTrue, IfFalse, Region or SafePoint"); 292 } 293 #endif 294 // Search original predicates 295 Node* entry = old_entry; 296 ProjNode* limit_check_proj = NULL; 297 if (LoopLimitCheck) { 298 limit_check_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check); 299 if (limit_check_proj != NULL) { 300 entry = entry->in(0)->in(0); 301 } 302 } 303 if (UseLoopPredicate) { 304 ProjNode* predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate); 305 if (predicate_proj != NULL) { // right pattern that can be used by loop predication 306 // clone predicate 307 new_entry = clone_predicate(predicate_proj, new_entry, 308 Deoptimization::Reason_predicate, 309 loop_phase, igvn); 310 assert(new_entry != NULL && new_entry->is_Proj(), "IfTrue or IfFalse after clone predicate"); 311 if (TraceLoopPredicate) { 312 tty->print("Loop Predicate cloned: "); 313 debug_only( new_entry->in(0)->dump(); ) 314 } 315 } 316 } 317 if (limit_check_proj != NULL && clone_limit_check) { 318 // Clone loop limit check last to insert it before loop. 319 // Don't clone a limit check which was already finalized 320 // for this counted loop (only one limit check is needed). 321 new_entry = clone_predicate(limit_check_proj, new_entry, 322 Deoptimization::Reason_loop_limit_check, 323 loop_phase, igvn); 324 assert(new_entry != NULL && new_entry->is_Proj(), "IfTrue or IfFalse after clone limit check"); 325 if (TraceLoopLimitCheck) { 326 tty->print("Loop Limit Check cloned: "); 327 debug_only( new_entry->in(0)->dump(); ) 328 } 329 } 330 return new_entry; 331 } 332 333 //--------------------------skip_loop_predicates------------------------------ 334 // Skip related predicates. 335 Node* PhaseIdealLoop::skip_loop_predicates(Node* entry) { 336 Node* predicate = NULL; 337 if (LoopLimitCheck) { 338 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check); 339 if (predicate != NULL) { 340 entry = entry->in(0)->in(0); 341 } 342 } 343 if (UseLoopPredicate) { 344 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate); 345 if (predicate != NULL) { // right pattern that can be used by loop predication 346 IfNode* iff = entry->in(0)->as_If(); 347 ProjNode* uncommon_proj = iff->proj_out(1 - entry->as_Proj()->_con); 348 Node* rgn = uncommon_proj->unique_ctrl_out(); 349 assert(rgn->is_Region() || rgn->is_Call(), "must be a region or call uct"); 350 entry = entry->in(0)->in(0); 351 while (entry != NULL && entry->is_Proj() && entry->in(0)->is_If()) { 352 uncommon_proj = entry->in(0)->as_If()->proj_out(1 - entry->as_Proj()->_con); 353 if (uncommon_proj->unique_ctrl_out() != rgn) 354 break; 355 entry = entry->in(0)->in(0); 356 } 357 } 358 } 359 return entry; 360 } 361 362 //--------------------------find_predicate_insertion_point------------------- 363 // Find a good location to insert a predicate 364 ProjNode* PhaseIdealLoop::find_predicate_insertion_point(Node* start_c, Deoptimization::DeoptReason reason) { 365 if (start_c == NULL || !start_c->is_Proj()) 366 return NULL; 367 if (start_c->as_Proj()->is_uncommon_trap_if_pattern(reason)) { 368 return start_c->as_Proj(); 369 } 370 return NULL; 371 } 372 373 //--------------------------find_predicate------------------------------------ 374 // Find a predicate 375 Node* PhaseIdealLoop::find_predicate(Node* entry) { 376 Node* predicate = NULL; 377 if (LoopLimitCheck) { 378 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check); 379 if (predicate != NULL) { // right pattern that can be used by loop predication 380 return entry; 381 } 382 } 383 if (UseLoopPredicate) { 384 predicate = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate); 385 if (predicate != NULL) { // right pattern that can be used by loop predication 386 return entry; 387 } 388 } 389 return NULL; 390 } 391 392 //------------------------------Invariance----------------------------------- 393 // Helper class for loop_predication_impl to compute invariance on the fly and 394 // clone invariants. 395 class Invariance : public StackObj { 396 VectorSet _visited, _invariant; 397 Node_Stack _stack; 398 VectorSet _clone_visited; 399 Node_List _old_new; // map of old to new (clone) 400 IdealLoopTree* _lpt; 401 PhaseIdealLoop* _phase; 402 403 // Helper function to set up the invariance for invariance computation 404 // If n is a known invariant, set up directly. Otherwise, look up the 405 // the possibility to push n onto the stack for further processing. 406 void visit(Node* use, Node* n) { 407 if (_lpt->is_invariant(n)) { // known invariant 408 _invariant.set(n->_idx); 409 } else if (!n->is_CFG()) { 410 Node *n_ctrl = _phase->ctrl_or_self(n); 411 Node *u_ctrl = _phase->ctrl_or_self(use); // self if use is a CFG 412 if (_phase->is_dominator(n_ctrl, u_ctrl)) { 413 _stack.push(n, n->in(0) == NULL ? 1 : 0); 414 } 415 } 416 } 417 418 // Compute invariance for "the_node" and (possibly) all its inputs recursively 419 // on the fly 420 void compute_invariance(Node* n) { 421 assert(_visited.test(n->_idx), "must be"); 422 visit(n, n); 423 while (_stack.is_nonempty()) { 424 Node* n = _stack.node(); 425 uint idx = _stack.index(); 426 if (idx == n->req()) { // all inputs are processed 427 _stack.pop(); 428 // n is invariant if it's inputs are all invariant 429 bool all_inputs_invariant = true; 430 for (uint i = 0; i < n->req(); i++) { 431 Node* in = n->in(i); 432 if (in == NULL) continue; 433 assert(_visited.test(in->_idx), "must have visited input"); 434 if (!_invariant.test(in->_idx)) { // bad guy 435 all_inputs_invariant = false; 436 break; 437 } 438 } 439 if (all_inputs_invariant) { 440 _invariant.set(n->_idx); // I am a invariant too 441 } 442 } else { // process next input 443 _stack.set_index(idx + 1); 444 Node* m = n->in(idx); 445 if (m != NULL && !_visited.test_set(m->_idx)) { 446 visit(n, m); 447 } 448 } 449 } 450 } 451 452 // Helper function to set up _old_new map for clone_nodes. 453 // If n is a known invariant, set up directly ("clone" of n == n). 454 // Otherwise, push n onto the stack for real cloning. 455 void clone_visit(Node* n) { 456 assert(_invariant.test(n->_idx), "must be invariant"); 457 if (_lpt->is_invariant(n)) { // known invariant 458 _old_new.map(n->_idx, n); 459 } else { // to be cloned 460 assert(!n->is_CFG(), "should not see CFG here"); 461 _stack.push(n, n->in(0) == NULL ? 1 : 0); 462 } 463 } 464 465 // Clone "n" and (possibly) all its inputs recursively 466 void clone_nodes(Node* n, Node* ctrl) { 467 clone_visit(n); 468 while (_stack.is_nonempty()) { 469 Node* n = _stack.node(); 470 uint idx = _stack.index(); 471 if (idx == n->req()) { // all inputs processed, clone n! 472 _stack.pop(); 473 // clone invariant node 474 Node* n_cl = n->clone(); 475 _old_new.map(n->_idx, n_cl); 476 _phase->register_new_node(n_cl, ctrl); 477 for (uint i = 0; i < n->req(); i++) { 478 Node* in = n_cl->in(i); 479 if (in == NULL) continue; 480 n_cl->set_req(i, _old_new[in->_idx]); 481 } 482 } else { // process next input 483 _stack.set_index(idx + 1); 484 Node* m = n->in(idx); 485 if (m != NULL && !_clone_visited.test_set(m->_idx)) { 486 clone_visit(m); // visit the input 487 } 488 } 489 } 490 } 491 492 public: 493 Invariance(Arena* area, IdealLoopTree* lpt) : 494 _lpt(lpt), _phase(lpt->_phase), 495 _visited(area), _invariant(area), _stack(area, 10 /* guess */), 496 _clone_visited(area), _old_new(area) 497 {} 498 499 // Map old to n for invariance computation and clone 500 void map_ctrl(Node* old, Node* n) { 501 assert(old->is_CFG() && n->is_CFG(), "must be"); 502 _old_new.map(old->_idx, n); // "clone" of old is n 503 _invariant.set(old->_idx); // old is invariant 504 _clone_visited.set(old->_idx); 505 } 506 507 // Driver function to compute invariance 508 bool is_invariant(Node* n) { 509 if (!_visited.test_set(n->_idx)) 510 compute_invariance(n); 511 return (_invariant.test(n->_idx) != 0); 512 } 513 514 // Driver function to clone invariant 515 Node* clone(Node* n, Node* ctrl) { 516 assert(ctrl->is_CFG(), "must be"); 517 assert(_invariant.test(n->_idx), "must be an invariant"); 518 if (!_clone_visited.test(n->_idx)) 519 clone_nodes(n, ctrl); 520 return _old_new[n->_idx]; 521 } 522 }; 523 524 //------------------------------is_range_check_if ----------------------------------- 525 // Returns true if the predicate of iff is in "scale*iv + offset u< load_range(ptr)" format 526 // Note: this function is particularly designed for loop predication. We require load_range 527 // and offset to be loop invariant computed on the fly by "invar" 528 bool IdealLoopTree::is_range_check_if(IfNode *iff, PhaseIdealLoop *phase, Invariance& invar) const { 529 if (!is_loop_exit(iff)) { 530 return false; 531 } 532 if (!iff->in(1)->is_Bool()) { 533 return false; 534 } 535 const BoolNode *bol = iff->in(1)->as_Bool(); 536 if (bol->_test._test != BoolTest::lt) { 537 return false; 538 } 539 if (!bol->in(1)->is_Cmp()) { 540 return false; 541 } 542 const CmpNode *cmp = bol->in(1)->as_Cmp(); 543 if (cmp->Opcode() != Op_CmpU) { 544 return false; 545 } 546 Node* range = cmp->in(2); 547 if (range->Opcode() != Op_LoadRange) { 548 const TypeInt* tint = phase->_igvn.type(range)->isa_int(); 549 if (tint == NULL || tint->empty() || tint->_lo < 0) { 550 // Allow predication on positive values that aren't LoadRanges. 551 // This allows optimization of loops where the length of the 552 // array is a known value and doesn't need to be loaded back 553 // from the array. 554 return false; 555 } 556 } 557 if (!invar.is_invariant(range)) { 558 return false; 559 } 560 Node *iv = _head->as_CountedLoop()->phi(); 561 int scale = 0; 562 Node *offset = NULL; 563 if (!phase->is_scaled_iv_plus_offset(cmp->in(1), iv, &scale, &offset)) { 564 return false; 565 } 566 if (offset && !invar.is_invariant(offset)) { // offset must be invariant 567 return false; 568 } 569 return true; 570 } 571 572 //------------------------------rc_predicate----------------------------------- 573 // Create a range check predicate 574 // 575 // for (i = init; i < limit; i += stride) { 576 // a[scale*i+offset] 577 // } 578 // 579 // Compute max(scale*i + offset) for init <= i < limit and build the predicate 580 // as "max(scale*i + offset) u< a.length". 581 // 582 // There are two cases for max(scale*i + offset): 583 // (1) stride*scale > 0 584 // max(scale*i + offset) = scale*(limit-stride) + offset 585 // (2) stride*scale < 0 586 // max(scale*i + offset) = scale*init + offset 587 BoolNode* PhaseIdealLoop::rc_predicate(IdealLoopTree *loop, Node* ctrl, 588 int scale, Node* offset, 589 Node* init, Node* limit, Node* stride, 590 Node* range, bool upper) { 591 stringStream* predString = NULL; 592 if (TraceLoopPredicate) { 593 predString = new stringStream(); 594 predString->print("rc_predicate "); 595 } 596 597 Node* max_idx_expr = init; 598 int stride_con = stride->get_int(); 599 if ((stride_con > 0) == (scale > 0) == upper) { 600 if (LoopLimitCheck) { 601 // With LoopLimitCheck limit is not exact. 602 // Calculate exact limit here. 603 // Note, counted loop's test is '<' or '>'. 604 limit = exact_limit(loop); 605 max_idx_expr = new SubINode(limit, stride); 606 register_new_node(max_idx_expr, ctrl); 607 if (TraceLoopPredicate) predString->print("(limit - stride) "); 608 } else { 609 max_idx_expr = new SubINode(limit, stride); 610 register_new_node(max_idx_expr, ctrl); 611 if (TraceLoopPredicate) predString->print("(limit - stride) "); 612 } 613 } else { 614 if (TraceLoopPredicate) predString->print("init "); 615 } 616 617 if (scale != 1) { 618 ConNode* con_scale = _igvn.intcon(scale); 619 max_idx_expr = new MulINode(max_idx_expr, con_scale); 620 register_new_node(max_idx_expr, ctrl); 621 if (TraceLoopPredicate) predString->print("* %d ", scale); 622 } 623 624 if (offset && (!offset->is_Con() || offset->get_int() != 0)){ 625 max_idx_expr = new AddINode(max_idx_expr, offset); 626 register_new_node(max_idx_expr, ctrl); 627 if (TraceLoopPredicate) 628 if (offset->is_Con()) predString->print("+ %d ", offset->get_int()); 629 else predString->print("+ offset "); 630 } 631 632 CmpUNode* cmp = new CmpUNode(max_idx_expr, range); 633 register_new_node(cmp, ctrl); 634 BoolNode* bol = new BoolNode(cmp, BoolTest::lt); 635 register_new_node(bol, ctrl); 636 637 if (TraceLoopPredicate) { 638 predString->print_cr("<u range"); 639 tty->print("%s", predString->as_string()); 640 } 641 return bol; 642 } 643 644 //------------------------------ loop_predication_impl-------------------------- 645 // Insert loop predicates for null checks and range checks 646 bool PhaseIdealLoop::loop_predication_impl(IdealLoopTree *loop) { 647 if (!UseLoopPredicate) return false; 648 649 if (!loop->_head->is_Loop()) { 650 // Could be a simple region when irreducible loops are present. 651 return false; 652 } 653 LoopNode* head = loop->_head->as_Loop(); 654 655 if (head->unique_ctrl_out()->Opcode() == Op_NeverBranch) { 656 // do nothing for infinite loops 657 return false; 658 } 659 660 CountedLoopNode *cl = NULL; 661 if (head->is_valid_counted_loop()) { 662 cl = head->as_CountedLoop(); 663 // do nothing for iteration-splitted loops 664 if (!cl->is_normal_loop()) return false; 665 // Avoid RCE if Counted loop's test is '!='. 666 BoolTest::mask bt = cl->loopexit()->test_trip(); 667 if (bt != BoolTest::lt && bt != BoolTest::gt) 668 cl = NULL; 669 } 670 671 Node* entry = head->in(LoopNode::EntryControl); 672 ProjNode *predicate_proj = NULL; 673 // Loop limit check predicate should be near the loop. 674 if (LoopLimitCheck) { 675 predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check); 676 if (predicate_proj != NULL) 677 entry = predicate_proj->in(0)->in(0); 678 } 679 680 predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate); 681 if (!predicate_proj) { 682 #ifndef PRODUCT 683 if (TraceLoopPredicate) { 684 tty->print("missing predicate:"); 685 loop->dump_head(); 686 head->dump(1); 687 } 688 #endif 689 return false; 690 } 691 ConNode* zero = _igvn.intcon(0); 692 set_ctrl(zero, C->root()); 693 694 ResourceArea *area = Thread::current()->resource_area(); 695 Invariance invar(area, loop); 696 697 // Create list of if-projs such that a newer proj dominates all older 698 // projs in the list, and they all dominate loop->tail() 699 Node_List if_proj_list(area); 700 Node *current_proj = loop->tail(); //start from tail 701 while (current_proj != head) { 702 if (loop == get_loop(current_proj) && // still in the loop ? 703 current_proj->is_Proj() && // is a projection ? 704 current_proj->in(0)->Opcode() == Op_If) { // is a if projection ? 705 if_proj_list.push(current_proj); 706 } 707 current_proj = idom(current_proj); 708 } 709 710 bool hoisted = false; // true if at least one proj is promoted 711 while (if_proj_list.size() > 0) { 712 // Following are changed to nonnull when a predicate can be hoisted 713 ProjNode* new_predicate_proj = NULL; 714 715 ProjNode* proj = if_proj_list.pop()->as_Proj(); 716 IfNode* iff = proj->in(0)->as_If(); 717 718 if (!proj->is_uncommon_trap_if_pattern(Deoptimization::Reason_none)) { 719 if (loop->is_loop_exit(iff)) { 720 // stop processing the remaining projs in the list because the execution of them 721 // depends on the condition of "iff" (iff->in(1)). 722 break; 723 } else { 724 // Both arms are inside the loop. There are two cases: 725 // (1) there is one backward branch. In this case, any remaining proj 726 // in the if_proj list post-dominates "iff". So, the condition of "iff" 727 // does not determine the execution the remining projs directly, and we 728 // can safely continue. 729 // (2) both arms are forwarded, i.e. a diamond shape. In this case, "proj" 730 // does not dominate loop->tail(), so it can not be in the if_proj list. 731 continue; 732 } 733 } 734 735 Node* test = iff->in(1); 736 if (!test->is_Bool()){ //Conv2B, ... 737 continue; 738 } 739 BoolNode* bol = test->as_Bool(); 740 if (invar.is_invariant(bol)) { 741 // Invariant test 742 new_predicate_proj = create_new_if_for_predicate(predicate_proj, NULL, 743 Deoptimization::Reason_predicate); 744 Node* ctrl = new_predicate_proj->in(0)->as_If()->in(0); 745 BoolNode* new_predicate_bol = invar.clone(bol, ctrl)->as_Bool(); 746 747 // Negate test if necessary 748 bool negated = false; 749 if (proj->_con != predicate_proj->_con) { 750 new_predicate_bol = new BoolNode(new_predicate_bol->in(1), new_predicate_bol->_test.negate()); 751 register_new_node(new_predicate_bol, ctrl); 752 negated = true; 753 } 754 IfNode* new_predicate_iff = new_predicate_proj->in(0)->as_If(); 755 _igvn.hash_delete(new_predicate_iff); 756 new_predicate_iff->set_req(1, new_predicate_bol); 757 #ifndef PRODUCT 758 if (TraceLoopPredicate) { 759 tty->print("Predicate invariant if%s: %d ", negated ? " negated" : "", new_predicate_iff->_idx); 760 loop->dump_head(); 761 } else if (TraceLoopOpts) { 762 tty->print("Predicate IC "); 763 loop->dump_head(); 764 } 765 #endif 766 } else if (cl != NULL && loop->is_range_check_if(iff, this, invar)) { 767 // Range check for counted loops 768 const Node* cmp = bol->in(1)->as_Cmp(); 769 Node* idx = cmp->in(1); 770 assert(!invar.is_invariant(idx), "index is variant"); 771 Node* rng = cmp->in(2); 772 assert(rng->Opcode() == Op_LoadRange || _igvn.type(rng)->is_int() >= 0, "must be"); 773 assert(invar.is_invariant(rng), "range must be invariant"); 774 int scale = 1; 775 Node* offset = zero; 776 bool ok = is_scaled_iv_plus_offset(idx, cl->phi(), &scale, &offset); 777 assert(ok, "must be index expression"); 778 779 Node* init = cl->init_trip(); 780 Node* limit = cl->limit(); 781 Node* stride = cl->stride(); 782 783 // Build if's for the upper and lower bound tests. The 784 // lower_bound test will dominate the upper bound test and all 785 // cloned or created nodes will use the lower bound test as 786 // their declared control. 787 ProjNode* lower_bound_proj = create_new_if_for_predicate(predicate_proj, NULL, Deoptimization::Reason_predicate); 788 ProjNode* upper_bound_proj = create_new_if_for_predicate(predicate_proj, NULL, Deoptimization::Reason_predicate); 789 assert(upper_bound_proj->in(0)->as_If()->in(0) == lower_bound_proj, "should dominate"); 790 Node *ctrl = lower_bound_proj->in(0)->as_If()->in(0); 791 792 // Perform cloning to keep Invariance state correct since the 793 // late schedule will place invariant things in the loop. 794 rng = invar.clone(rng, ctrl); 795 if (offset && offset != zero) { 796 assert(invar.is_invariant(offset), "offset must be loop invariant"); 797 offset = invar.clone(offset, ctrl); 798 } 799 800 // Test the lower bound 801 BoolNode* lower_bound_bol = rc_predicate(loop, ctrl, scale, offset, init, limit, stride, rng, false); 802 // Negate test if necessary 803 bool negated = false; 804 if (proj->_con != predicate_proj->_con) { 805 lower_bound_bol = new BoolNode(lower_bound_bol->in(1), lower_bound_bol->_test.negate()); 806 register_new_node(lower_bound_bol, ctrl); 807 negated = true; 808 } 809 IfNode* lower_bound_iff = lower_bound_proj->in(0)->as_If(); 810 _igvn.hash_delete(lower_bound_iff); 811 lower_bound_iff->set_req(1, lower_bound_bol); 812 if (TraceLoopPredicate) tty->print_cr("lower bound check if: %s %d ", negated ? " negated" : "", lower_bound_iff->_idx); 813 814 // Test the upper bound 815 BoolNode* upper_bound_bol = rc_predicate(loop, lower_bound_proj, scale, offset, init, limit, stride, rng, true); 816 negated = false; 817 if (proj->_con != predicate_proj->_con) { 818 upper_bound_bol = new BoolNode(upper_bound_bol->in(1), upper_bound_bol->_test.negate()); 819 register_new_node(upper_bound_bol, ctrl); 820 negated = true; 821 } 822 IfNode* upper_bound_iff = upper_bound_proj->in(0)->as_If(); 823 _igvn.hash_delete(upper_bound_iff); 824 upper_bound_iff->set_req(1, upper_bound_bol); 825 if (TraceLoopPredicate) tty->print_cr("upper bound check if: %s %d ", negated ? " negated" : "", lower_bound_iff->_idx); 826 827 // Fall through into rest of the clean up code which will move 828 // any dependent nodes onto the upper bound test. 829 new_predicate_proj = upper_bound_proj; 830 831 #ifndef PRODUCT 832 if (TraceLoopOpts && !TraceLoopPredicate) { 833 tty->print("Predicate RC "); 834 loop->dump_head(); 835 } 836 #endif 837 } else { 838 // Loop variant check (for example, range check in non-counted loop) 839 // with uncommon trap. 840 continue; 841 } 842 assert(new_predicate_proj != NULL, "sanity"); 843 // Success - attach condition (new_predicate_bol) to predicate if 844 invar.map_ctrl(proj, new_predicate_proj); // so that invariance test can be appropriate 845 846 // Eliminate the old If in the loop body 847 dominated_by( new_predicate_proj, iff, proj->_con != new_predicate_proj->_con ); 848 849 hoisted = true; 850 C->set_major_progress(); 851 } // end while 852 853 #ifndef PRODUCT 854 // report that the loop predication has been actually performed 855 // for this loop 856 if (TraceLoopPredicate && hoisted) { 857 tty->print("Loop Predication Performed:"); 858 loop->dump_head(); 859 } 860 #endif 861 862 return hoisted; 863 } 864 865 //------------------------------loop_predication-------------------------------- 866 // driver routine for loop predication optimization 867 bool IdealLoopTree::loop_predication( PhaseIdealLoop *phase) { 868 bool hoisted = false; 869 // Recursively promote predicates 870 if (_child) { 871 hoisted = _child->loop_predication( phase); 872 } 873 874 // self 875 if (!_irreducible && !tail()->is_top()) { 876 hoisted |= phase->loop_predication_impl(this); 877 } 878 879 if (_next) { //sibling 880 hoisted |= _next->loop_predication( phase); 881 } 882 883 return hoisted; 884 }