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 // If n's control is a predicate that was moved out of the 441 // loop, it was marked invariant but n is only invariant if 442 // it depends only on that test. Otherwise, unless that test 443 // is out of the loop, it's not invariant. 444 if (n->Opcode() == Op_ShenandoahWBMemProj || n->is_CFG() || n->depends_only_on_test() || n->in(0) == NULL || !_phase->is_member(_lpt, n->in(0))) { 445 _invariant.set(n->_idx); // I am a invariant too 446 } 447 } 448 } else { // process next input 449 _stack.set_index(idx + 1); 450 Node* m = n->in(idx); 451 if (m != NULL && !_visited.test_set(m->_idx)) { 452 visit(n, m); 453 } 454 } 455 } 456 } 457 458 // Helper function to set up _old_new map for clone_nodes. 459 // If n is a known invariant, set up directly ("clone" of n == n). 460 // Otherwise, push n onto the stack for real cloning. 461 void clone_visit(Node* n) { 462 assert(_invariant.test(n->_idx), "must be invariant"); 463 if (_lpt->is_invariant(n)) { // known invariant 464 _old_new.map(n->_idx, n); 465 } else { // to be cloned 466 assert(!n->is_CFG(), "should not see CFG here"); 467 _stack.push(n, n->in(0) == NULL ? 1 : 0); 468 } 469 } 470 471 // Clone "n" and (possibly) all its inputs recursively 472 void clone_nodes(Node* n, Node* ctrl) { 473 clone_visit(n); 474 while (_stack.is_nonempty()) { 475 Node* n = _stack.node(); 476 uint idx = _stack.index(); 477 if (idx == n->req()) { // all inputs processed, clone n! 478 _stack.pop(); 479 // clone invariant node 480 Node* n_cl = n->clone(); 481 _old_new.map(n->_idx, n_cl); 482 _phase->register_new_node(n_cl, ctrl); 483 for (uint i = 0; i < n->req(); i++) { 484 Node* in = n_cl->in(i); 485 if (in == NULL) continue; 486 n_cl->set_req(i, _old_new[in->_idx]); 487 } 488 } else { // process next input 489 _stack.set_index(idx + 1); 490 Node* m = n->in(idx); 491 if (m != NULL && !_clone_visited.test_set(m->_idx)) { 492 clone_visit(m); // visit the input 493 } 494 } 495 } 496 } 497 498 public: 499 Invariance(Arena* area, IdealLoopTree* lpt) : 500 _lpt(lpt), _phase(lpt->_phase), 501 _visited(area), _invariant(area), _stack(area, 10 /* guess */), 502 _clone_visited(area), _old_new(area) 503 {} 504 505 // Map old to n for invariance computation and clone 506 void map_ctrl(Node* old, Node* n) { 507 assert(old->is_CFG() && n->is_CFG(), "must be"); 508 _old_new.map(old->_idx, n); // "clone" of old is n 509 _invariant.set(old->_idx); // old is invariant 510 _clone_visited.set(old->_idx); 511 } 512 513 // Driver function to compute invariance 514 bool is_invariant(Node* n) { 515 if (!_visited.test_set(n->_idx)) 516 compute_invariance(n); 517 return (_invariant.test(n->_idx) != 0); 518 } 519 520 // Driver function to clone invariant 521 Node* clone(Node* n, Node* ctrl) { 522 assert(ctrl->is_CFG(), "must be"); 523 assert(_invariant.test(n->_idx), "must be an invariant"); 524 if (!_clone_visited.test(n->_idx)) 525 clone_nodes(n, ctrl); 526 return _old_new[n->_idx]; 527 } 528 }; 529 530 //------------------------------is_range_check_if ----------------------------------- 531 // Returns true if the predicate of iff is in "scale*iv + offset u< load_range(ptr)" format 532 // Note: this function is particularly designed for loop predication. We require load_range 533 // and offset to be loop invariant computed on the fly by "invar" 534 bool IdealLoopTree::is_range_check_if(IfNode *iff, PhaseIdealLoop *phase, Invariance& invar) const { 535 if (!is_loop_exit(iff)) { 536 return false; 537 } 538 if (!iff->in(1)->is_Bool()) { 539 return false; 540 } 541 const BoolNode *bol = iff->in(1)->as_Bool(); 542 if (bol->_test._test != BoolTest::lt) { 543 return false; 544 } 545 if (!bol->in(1)->is_Cmp()) { 546 return false; 547 } 548 const CmpNode *cmp = bol->in(1)->as_Cmp(); 549 if (cmp->Opcode() != Op_CmpU) { 550 return false; 551 } 552 Node* range = cmp->in(2); 553 if (range->Opcode() != Op_LoadRange) { 554 const TypeInt* tint = phase->_igvn.type(range)->isa_int(); 555 if (tint == NULL || tint->empty() || tint->_lo < 0) { 556 // Allow predication on positive values that aren't LoadRanges. 557 // This allows optimization of loops where the length of the 558 // array is a known value and doesn't need to be loaded back 559 // from the array. 560 return false; 561 } 562 } 563 if (!invar.is_invariant(range)) { 564 return false; 565 } 566 Node *iv = _head->as_CountedLoop()->phi(); 567 int scale = 0; 568 Node *offset = NULL; 569 if (!phase->is_scaled_iv_plus_offset(cmp->in(1), iv, &scale, &offset)) { 570 return false; 571 } 572 if (offset && !invar.is_invariant(offset)) { // offset must be invariant 573 return false; 574 } 575 return true; 576 } 577 578 //------------------------------rc_predicate----------------------------------- 579 // Create a range check predicate 580 // 581 // for (i = init; i < limit; i += stride) { 582 // a[scale*i+offset] 583 // } 584 // 585 // Compute max(scale*i + offset) for init <= i < limit and build the predicate 586 // as "max(scale*i + offset) u< a.length". 587 // 588 // There are two cases for max(scale*i + offset): 589 // (1) stride*scale > 0 590 // max(scale*i + offset) = scale*(limit-stride) + offset 591 // (2) stride*scale < 0 592 // max(scale*i + offset) = scale*init + offset 593 BoolNode* PhaseIdealLoop::rc_predicate(IdealLoopTree *loop, Node* ctrl, 594 int scale, Node* offset, 595 Node* init, Node* limit, Node* stride, 596 Node* range, bool upper) { 597 stringStream* predString = NULL; 598 if (TraceLoopPredicate) { 599 predString = new stringStream(); 600 predString->print("rc_predicate "); 601 } 602 603 Node* max_idx_expr = init; 604 int stride_con = stride->get_int(); 605 if ((stride_con > 0) == (scale > 0) == upper) { 606 if (LoopLimitCheck) { 607 // With LoopLimitCheck limit is not exact. 608 // Calculate exact limit here. 609 // Note, counted loop's test is '<' or '>'. 610 limit = exact_limit(loop); 611 max_idx_expr = new SubINode(limit, stride); 612 register_new_node(max_idx_expr, ctrl); 613 if (TraceLoopPredicate) predString->print("(limit - stride) "); 614 } else { 615 max_idx_expr = new SubINode(limit, stride); 616 register_new_node(max_idx_expr, ctrl); 617 if (TraceLoopPredicate) predString->print("(limit - stride) "); 618 } 619 } else { 620 if (TraceLoopPredicate) predString->print("init "); 621 } 622 623 if (scale != 1) { 624 ConNode* con_scale = _igvn.intcon(scale); 625 max_idx_expr = new MulINode(max_idx_expr, con_scale); 626 register_new_node(max_idx_expr, ctrl); 627 if (TraceLoopPredicate) predString->print("* %d ", scale); 628 } 629 630 if (offset && (!offset->is_Con() || offset->get_int() != 0)){ 631 max_idx_expr = new AddINode(max_idx_expr, offset); 632 register_new_node(max_idx_expr, ctrl); 633 if (TraceLoopPredicate) 634 if (offset->is_Con()) predString->print("+ %d ", offset->get_int()); 635 else predString->print("+ offset "); 636 } 637 638 CmpUNode* cmp = new CmpUNode(max_idx_expr, range); 639 register_new_node(cmp, ctrl); 640 BoolNode* bol = new BoolNode(cmp, BoolTest::lt); 641 register_new_node(bol, ctrl); 642 643 if (TraceLoopPredicate) { 644 predString->print_cr("<u range"); 645 tty->print("%s", predString->as_string()); 646 } 647 return bol; 648 } 649 650 //------------------------------ loop_predication_impl-------------------------- 651 // Insert loop predicates for null checks and range checks 652 bool PhaseIdealLoop::loop_predication_impl(IdealLoopTree *loop) { 653 if (!UseLoopPredicate) return false; 654 655 if (!loop->_head->is_Loop()) { 656 // Could be a simple region when irreducible loops are present. 657 return false; 658 } 659 LoopNode* head = loop->_head->as_Loop(); 660 661 if (head->unique_ctrl_out()->Opcode() == Op_NeverBranch) { 662 // do nothing for infinite loops 663 return false; 664 } 665 666 CountedLoopNode *cl = NULL; 667 if (head->is_valid_counted_loop()) { 668 cl = head->as_CountedLoop(); 669 // do nothing for iteration-splitted loops 670 if (!cl->is_normal_loop()) return false; 671 // Avoid RCE if Counted loop's test is '!='. 672 BoolTest::mask bt = cl->loopexit()->test_trip(); 673 if (bt != BoolTest::lt && bt != BoolTest::gt) 674 cl = NULL; 675 } 676 677 Node* entry = head->in(LoopNode::EntryControl); 678 ProjNode *predicate_proj = NULL; 679 // Loop limit check predicate should be near the loop. 680 if (LoopLimitCheck) { 681 predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check); 682 if (predicate_proj != NULL) 683 entry = predicate_proj->in(0)->in(0); 684 } 685 686 predicate_proj = find_predicate_insertion_point(entry, Deoptimization::Reason_predicate); 687 if (!predicate_proj) { 688 #ifndef PRODUCT 689 if (TraceLoopPredicate) { 690 tty->print("missing predicate:"); 691 loop->dump_head(); 692 head->dump(1); 693 } 694 #endif 695 return false; 696 } 697 ConNode* zero = _igvn.intcon(0); 698 set_ctrl(zero, C->root()); 699 700 ResourceArea *area = Thread::current()->resource_area(); 701 Invariance invar(area, loop); 702 703 // Create list of if-projs such that a newer proj dominates all older 704 // projs in the list, and they all dominate loop->tail() 705 Node_List if_proj_list(area); 706 Node *current_proj = loop->tail(); //start from tail 707 while (current_proj != head) { 708 if (loop == get_loop(current_proj) && // still in the loop ? 709 current_proj->is_Proj() && // is a projection ? 710 current_proj->in(0)->Opcode() == Op_If) { // is a if projection ? 711 if_proj_list.push(current_proj); 712 } 713 current_proj = idom(current_proj); 714 } 715 716 bool hoisted = false; // true if at least one proj is promoted 717 while (if_proj_list.size() > 0) { 718 // Following are changed to nonnull when a predicate can be hoisted 719 ProjNode* new_predicate_proj = NULL; 720 721 ProjNode* proj = if_proj_list.pop()->as_Proj(); 722 IfNode* iff = proj->in(0)->as_If(); 723 724 if (!proj->is_uncommon_trap_if_pattern(Deoptimization::Reason_none)) { 725 if (loop->is_loop_exit(iff)) { 726 // stop processing the remaining projs in the list because the execution of them 727 // depends on the condition of "iff" (iff->in(1)). 728 break; 729 } else { 730 // Both arms are inside the loop. There are two cases: 731 // (1) there is one backward branch. In this case, any remaining proj 732 // in the if_proj list post-dominates "iff". So, the condition of "iff" 733 // does not determine the execution the remining projs directly, and we 734 // can safely continue. 735 // (2) both arms are forwarded, i.e. a diamond shape. In this case, "proj" 736 // does not dominate loop->tail(), so it can not be in the if_proj list. 737 continue; 738 } 739 } 740 741 Node* test = iff->in(1); 742 if (!test->is_Bool()){ //Conv2B, ... 743 continue; 744 } 745 BoolNode* bol = test->as_Bool(); 746 if (invar.is_invariant(bol)) { 747 // Invariant test 748 new_predicate_proj = create_new_if_for_predicate(predicate_proj, NULL, 749 Deoptimization::Reason_predicate); 750 Node* ctrl = new_predicate_proj->in(0)->as_If()->in(0); 751 BoolNode* new_predicate_bol = invar.clone(bol, ctrl)->as_Bool(); 752 753 // Negate test if necessary 754 bool negated = false; 755 if (proj->_con != predicate_proj->_con) { 756 new_predicate_bol = new BoolNode(new_predicate_bol->in(1), new_predicate_bol->_test.negate()); 757 register_new_node(new_predicate_bol, ctrl); 758 negated = true; 759 } 760 IfNode* new_predicate_iff = new_predicate_proj->in(0)->as_If(); 761 _igvn.hash_delete(new_predicate_iff); 762 new_predicate_iff->set_req(1, new_predicate_bol); 763 #ifndef PRODUCT 764 if (TraceLoopPredicate) { 765 tty->print("Predicate invariant if%s: %d ", negated ? " negated" : "", new_predicate_iff->_idx); 766 loop->dump_head(); 767 } else if (TraceLoopOpts) { 768 tty->print("Predicate IC "); 769 loop->dump_head(); 770 } 771 #endif 772 } else if (cl != NULL && loop->is_range_check_if(iff, this, invar)) { 773 // Range check for counted loops 774 const Node* cmp = bol->in(1)->as_Cmp(); 775 Node* idx = cmp->in(1); 776 assert(!invar.is_invariant(idx), "index is variant"); 777 Node* rng = cmp->in(2); 778 assert(rng->Opcode() == Op_LoadRange || _igvn.type(rng)->is_int() >= 0, "must be"); 779 assert(invar.is_invariant(rng), "range must be invariant"); 780 int scale = 1; 781 Node* offset = zero; 782 bool ok = is_scaled_iv_plus_offset(idx, cl->phi(), &scale, &offset); 783 assert(ok, "must be index expression"); 784 785 Node* init = cl->init_trip(); 786 Node* limit = cl->limit(); 787 Node* stride = cl->stride(); 788 789 // Build if's for the upper and lower bound tests. The 790 // lower_bound test will dominate the upper bound test and all 791 // cloned or created nodes will use the lower bound test as 792 // their declared control. 793 ProjNode* lower_bound_proj = create_new_if_for_predicate(predicate_proj, NULL, Deoptimization::Reason_predicate); 794 ProjNode* upper_bound_proj = create_new_if_for_predicate(predicate_proj, NULL, Deoptimization::Reason_predicate); 795 assert(upper_bound_proj->in(0)->as_If()->in(0) == lower_bound_proj, "should dominate"); 796 Node *ctrl = lower_bound_proj->in(0)->as_If()->in(0); 797 798 // Perform cloning to keep Invariance state correct since the 799 // late schedule will place invariant things in the loop. 800 rng = invar.clone(rng, ctrl); 801 if (offset && offset != zero) { 802 assert(invar.is_invariant(offset), "offset must be loop invariant"); 803 offset = invar.clone(offset, ctrl); 804 } 805 806 // Test the lower bound 807 BoolNode* lower_bound_bol = rc_predicate(loop, ctrl, scale, offset, init, limit, stride, rng, false); 808 // Negate test if necessary 809 bool negated = false; 810 if (proj->_con != predicate_proj->_con) { 811 lower_bound_bol = new BoolNode(lower_bound_bol->in(1), lower_bound_bol->_test.negate()); 812 register_new_node(lower_bound_bol, ctrl); 813 negated = true; 814 } 815 IfNode* lower_bound_iff = lower_bound_proj->in(0)->as_If(); 816 _igvn.hash_delete(lower_bound_iff); 817 lower_bound_iff->set_req(1, lower_bound_bol); 818 if (TraceLoopPredicate) tty->print_cr("lower bound check if: %s %d ", negated ? " negated" : "", lower_bound_iff->_idx); 819 820 // Test the upper bound 821 BoolNode* upper_bound_bol = rc_predicate(loop, lower_bound_proj, scale, offset, init, limit, stride, rng, true); 822 negated = false; 823 if (proj->_con != predicate_proj->_con) { 824 upper_bound_bol = new BoolNode(upper_bound_bol->in(1), upper_bound_bol->_test.negate()); 825 register_new_node(upper_bound_bol, ctrl); 826 negated = true; 827 } 828 IfNode* upper_bound_iff = upper_bound_proj->in(0)->as_If(); 829 _igvn.hash_delete(upper_bound_iff); 830 upper_bound_iff->set_req(1, upper_bound_bol); 831 if (TraceLoopPredicate) tty->print_cr("upper bound check if: %s %d ", negated ? " negated" : "", lower_bound_iff->_idx); 832 833 // Fall through into rest of the clean up code which will move 834 // any dependent nodes onto the upper bound test. 835 new_predicate_proj = upper_bound_proj; 836 837 #ifndef PRODUCT 838 if (TraceLoopOpts && !TraceLoopPredicate) { 839 tty->print("Predicate RC "); 840 loop->dump_head(); 841 } 842 #endif 843 } else { 844 // Loop variant check (for example, range check in non-counted loop) 845 // with uncommon trap. 846 continue; 847 } 848 assert(new_predicate_proj != NULL, "sanity"); 849 // Success - attach condition (new_predicate_bol) to predicate if 850 invar.map_ctrl(proj, new_predicate_proj); // so that invariance test can be appropriate 851 852 // Eliminate the old If in the loop body 853 dominated_by( new_predicate_proj, iff, proj->_con != new_predicate_proj->_con ); 854 855 hoisted = true; 856 C->set_major_progress(); 857 } // end while 858 859 #ifndef PRODUCT 860 // report that the loop predication has been actually performed 861 // for this loop 862 if (TraceLoopPredicate && hoisted) { 863 tty->print("Loop Predication Performed:"); 864 loop->dump_head(); 865 } 866 #endif 867 868 return hoisted; 869 } 870 871 //------------------------------loop_predication-------------------------------- 872 // driver routine for loop predication optimization 873 bool IdealLoopTree::loop_predication( PhaseIdealLoop *phase) { 874 bool hoisted = false; 875 // Recursively promote predicates 876 if (_child) { 877 hoisted = _child->loop_predication( phase); 878 } 879 880 // self 881 if (!_irreducible && !tail()->is_top()) { 882 hoisted |= phase->loop_predication_impl(this); 883 } 884 885 if (_next) { //sibling 886 hoisted |= _next->loop_predication( phase); 887 } 888 889 return hoisted; 890 }