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