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