1 /* 2 * Copyright (c) 2000, 2018, 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 "ci/ciTypeFlow.hpp" 27 #include "memory/allocation.inline.hpp" 28 #include "memory/resourceArea.hpp" 29 #include "opto/addnode.hpp" 30 #include "opto/castnode.hpp" 31 #include "opto/cfgnode.hpp" 32 #include "opto/connode.hpp" 33 #include "opto/loopnode.hpp" 34 #include "opto/phaseX.hpp" 35 #include "opto/runtime.hpp" 36 #include "opto/rootnode.hpp" 37 #include "opto/subnode.hpp" 38 #include "utilities/macros.hpp" 39 #if INCLUDE_SHENANDOAHGC 40 #include "gc/shenandoah/shenandoahHeap.hpp" 41 #include "gc/shenandoah/c2/shenandoahSupport.hpp" 42 #endif 43 44 // Portions of code courtesy of Clifford Click 45 46 // Optimization - Graph Style 47 48 49 #ifndef PRODUCT 50 extern int explicit_null_checks_elided; 51 #endif 52 53 //============================================================================= 54 //------------------------------Value------------------------------------------ 55 // Return a tuple for whichever arm of the IF is reachable 56 const Type* IfNode::Value(PhaseGVN* phase) const { 57 if( !in(0) ) return Type::TOP; 58 if( phase->type(in(0)) == Type::TOP ) 59 return Type::TOP; 60 const Type *t = phase->type(in(1)); 61 if( t == Type::TOP ) // data is undefined 62 return TypeTuple::IFNEITHER; // unreachable altogether 63 if( t == TypeInt::ZERO ) // zero, or false 64 return TypeTuple::IFFALSE; // only false branch is reachable 65 if( t == TypeInt::ONE ) // 1, or true 66 return TypeTuple::IFTRUE; // only true branch is reachable 67 assert( t == TypeInt::BOOL, "expected boolean type" ); 68 69 return TypeTuple::IFBOTH; // No progress 70 } 71 72 const RegMask &IfNode::out_RegMask() const { 73 return RegMask::Empty; 74 } 75 76 //------------------------------split_if--------------------------------------- 77 // Look for places where we merge constants, then test on the merged value. 78 // If the IF test will be constant folded on the path with the constant, we 79 // win by splitting the IF to before the merge point. 80 static Node* split_if(IfNode *iff, PhaseIterGVN *igvn) { 81 // I could be a lot more general here, but I'm trying to squeeze this 82 // in before the Christmas '98 break so I'm gonna be kinda restrictive 83 // on the patterns I accept. CNC 84 85 // Look for a compare of a constant and a merged value 86 Node *i1 = iff->in(1); 87 if( !i1->is_Bool() ) return NULL; 88 BoolNode *b = i1->as_Bool(); 89 Node *cmp = b->in(1); 90 if( !cmp->is_Cmp() ) return NULL; 91 i1 = cmp->in(1); 92 if( i1 == NULL || !i1->is_Phi() ) return NULL; 93 PhiNode *phi = i1->as_Phi(); 94 if( phi->is_copy() ) return NULL; 95 Node *con2 = cmp->in(2); 96 if( !con2->is_Con() ) return NULL; 97 // See that the merge point contains some constants 98 Node *con1=NULL; 99 uint i4; 100 for( i4 = 1; i4 < phi->req(); i4++ ) { 101 con1 = phi->in(i4); 102 if( !con1 ) return NULL; // Do not optimize partially collapsed merges 103 if( con1->is_Con() ) break; // Found a constant 104 // Also allow null-vs-not-null checks 105 const TypePtr *tp = igvn->type(con1)->isa_ptr(); 106 if( tp && tp->_ptr == TypePtr::NotNull ) 107 break; 108 } 109 if( i4 >= phi->req() ) return NULL; // Found no constants 110 111 igvn->C->set_has_split_ifs(true); // Has chance for split-if 112 113 // Make sure that the compare can be constant folded away 114 Node *cmp2 = cmp->clone(); 115 cmp2->set_req(1,con1); 116 cmp2->set_req(2,con2); 117 const Type *t = cmp2->Value(igvn); 118 // This compare is dead, so whack it! 119 igvn->remove_dead_node(cmp2); 120 if( !t->singleton() ) return NULL; 121 122 // No intervening control, like a simple Call 123 Node *r = iff->in(0); 124 if( !r->is_Region() ) return NULL; 125 if (r->is_Loop() && r->in(LoopNode::LoopBackControl)->is_top()) return NULL; // going away anyway 126 if( phi->region() != r ) return NULL; 127 // No other users of the cmp/bool 128 if (b->outcnt() != 1 || cmp->outcnt() != 1) { 129 //tty->print_cr("many users of cmp/bool"); 130 return NULL; 131 } 132 133 // Make sure we can determine where all the uses of merged values go 134 for (DUIterator_Fast jmax, j = r->fast_outs(jmax); j < jmax; j++) { 135 Node* u = r->fast_out(j); 136 if( u == r ) continue; 137 if( u == iff ) continue; 138 if( u->outcnt() == 0 ) continue; // use is dead & ignorable 139 if( !u->is_Phi() ) { 140 /* 141 if( u->is_Start() ) { 142 tty->print_cr("Region has inlined start use"); 143 } else { 144 tty->print_cr("Region has odd use"); 145 u->dump(2); 146 }*/ 147 return NULL; 148 } 149 if( u != phi ) { 150 // CNC - do not allow any other merged value 151 //tty->print_cr("Merging another value"); 152 //u->dump(2); 153 return NULL; 154 } 155 // Make sure we can account for all Phi uses 156 for (DUIterator_Fast kmax, k = u->fast_outs(kmax); k < kmax; k++) { 157 Node* v = u->fast_out(k); // User of the phi 158 // CNC - Allow only really simple patterns. 159 // In particular I disallow AddP of the Phi, a fairly common pattern 160 if (v == cmp) continue; // The compare is OK 161 if (v->is_ConstraintCast()) { 162 // If the cast is derived from data flow edges, it may not have a control edge. 163 // If so, it should be safe to split. But follow-up code can not deal with 164 // this (l. 359). So skip. 165 if (v->in(0) == NULL) { 166 return NULL; 167 } 168 if (v->in(0)->in(0) == iff) { 169 continue; // CastPP/II of the IfNode is OK 170 } 171 } 172 // Disabled following code because I cannot tell if exactly one 173 // path dominates without a real dominator check. CNC 9/9/1999 174 //uint vop = v->Opcode(); 175 //if( vop == Op_Phi ) { // Phi from another merge point might be OK 176 // Node *r = v->in(0); // Get controlling point 177 // if( !r ) return NULL; // Degraded to a copy 178 // // Find exactly one path in (either True or False doms, but not IFF) 179 // int cnt = 0; 180 // for( uint i = 1; i < r->req(); i++ ) 181 // if( r->in(i) && r->in(i)->in(0) == iff ) 182 // cnt++; 183 // if( cnt == 1 ) continue; // Exactly one of True or False guards Phi 184 //} 185 if( !v->is_Call() ) { 186 /* 187 if( v->Opcode() == Op_AddP ) { 188 tty->print_cr("Phi has AddP use"); 189 } else if( v->Opcode() == Op_CastPP ) { 190 tty->print_cr("Phi has CastPP use"); 191 } else if( v->Opcode() == Op_CastII ) { 192 tty->print_cr("Phi has CastII use"); 193 } else { 194 tty->print_cr("Phi has use I cant be bothered with"); 195 } 196 */ 197 } 198 return NULL; 199 200 /* CNC - Cut out all the fancy acceptance tests 201 // Can we clone this use when doing the transformation? 202 // If all uses are from Phis at this merge or constants, then YES. 203 if( !v->in(0) && v != cmp ) { 204 tty->print_cr("Phi has free-floating use"); 205 v->dump(2); 206 return NULL; 207 } 208 for( uint l = 1; l < v->req(); l++ ) { 209 if( (!v->in(l)->is_Phi() || v->in(l)->in(0) != r) && 210 !v->in(l)->is_Con() ) { 211 tty->print_cr("Phi has use"); 212 v->dump(2); 213 return NULL; 214 } // End of if Phi-use input is neither Phi nor Constant 215 } // End of for all inputs to Phi-use 216 */ 217 } // End of for all uses of Phi 218 } // End of for all uses of Region 219 220 // Only do this if the IF node is in a sane state 221 if (iff->outcnt() != 2) 222 return NULL; 223 224 // Got a hit! Do the Mondo Hack! 225 // 226 //ABC a1c def ghi B 1 e h A C a c d f g i 227 // R - Phi - Phi - Phi Rc - Phi - Phi - Phi Rx - Phi - Phi - Phi 228 // cmp - 2 cmp - 2 cmp - 2 229 // bool bool_c bool_x 230 // if if_c if_x 231 // T F T F T F 232 // ..s.. ..t .. ..s.. ..t.. ..s.. ..t.. 233 // 234 // Split the paths coming into the merge point into 2 separate groups of 235 // merges. On the left will be all the paths feeding constants into the 236 // Cmp's Phi. On the right will be the remaining paths. The Cmp's Phi 237 // will fold up into a constant; this will let the Cmp fold up as well as 238 // all the control flow. Below the original IF we have 2 control 239 // dependent regions, 's' and 't'. Now we will merge the two paths 240 // just prior to 's' and 't' from the two IFs. At least 1 path (and quite 241 // likely 2 or more) will promptly constant fold away. 242 PhaseGVN *phase = igvn; 243 244 // Make a region merging constants and a region merging the rest 245 uint req_c = 0; 246 Node* predicate_proj = NULL; 247 int nb_predicate_proj = 0; 248 for (uint ii = 1; ii < r->req(); ii++) { 249 if (phi->in(ii) == con1) { 250 req_c++; 251 } 252 Node* proj = PhaseIdealLoop::find_predicate(r->in(ii)); 253 if (proj != NULL) { 254 nb_predicate_proj++; 255 predicate_proj = proj; 256 } 257 } 258 259 // If all the defs of the phi are the same constant, we already have the desired end state. 260 // Skip the split that would create empty phi and region nodes. 261 if((r->req() - req_c) == 1) { 262 return NULL; 263 } 264 265 if (nb_predicate_proj > 1) { 266 // Can happen in case of loop unswitching and when the loop is 267 // optimized out: it's not a loop anymore so we don't care about 268 // predicates. 269 assert(!r->is_Loop(), "this must not be a loop anymore"); 270 predicate_proj = NULL; 271 } 272 Node* predicate_c = NULL; 273 Node* predicate_x = NULL; 274 bool counted_loop = r->is_CountedLoop(); 275 if (counted_loop) { 276 // Ignore counted loops for now because the split-if logic does not work 277 // in all the cases (for example, with strip mined loops). Also, above 278 // checks only pass for already degraded loops without a tripcount phi 279 // and these are essentially dead and will go away during igvn. 280 return NULL; 281 } 282 283 Node *region_c = new RegionNode(req_c + 1); 284 Node *phi_c = con1; 285 uint len = r->req(); 286 Node *region_x = new RegionNode(len - req_c); 287 Node *phi_x = PhiNode::make_blank(region_x, phi); 288 for (uint i = 1, i_c = 1, i_x = 1; i < len; i++) { 289 if (phi->in(i) == con1) { 290 region_c->init_req( i_c++, r ->in(i) ); 291 if (r->in(i) == predicate_proj) 292 predicate_c = predicate_proj; 293 } else { 294 region_x->init_req( i_x, r ->in(i) ); 295 phi_x ->init_req( i_x++, phi->in(i) ); 296 if (r->in(i) == predicate_proj) 297 predicate_x = predicate_proj; 298 } 299 } 300 if (predicate_c != NULL && (req_c > 1)) { 301 assert(predicate_x == NULL, "only one predicate entry expected"); 302 predicate_c = NULL; // Do not clone predicate below merge point 303 } 304 if (predicate_x != NULL && ((len - req_c) > 2)) { 305 assert(predicate_c == NULL, "only one predicate entry expected"); 306 predicate_x = NULL; // Do not clone predicate below merge point 307 } 308 309 // Register the new RegionNodes but do not transform them. Cannot 310 // transform until the entire Region/Phi conglomerate has been hacked 311 // as a single huge transform. 312 igvn->register_new_node_with_optimizer( region_c ); 313 igvn->register_new_node_with_optimizer( region_x ); 314 // Prevent the untimely death of phi_x. Currently he has no uses. He is 315 // about to get one. If this only use goes away, then phi_x will look dead. 316 // However, he will be picking up some more uses down below. 317 Node *hook = new Node(4); 318 hook->init_req(0, phi_x); 319 hook->init_req(1, phi_c); 320 phi_x = phase->transform( phi_x ); 321 322 // Make the compare 323 Node *cmp_c = phase->makecon(t); 324 Node *cmp_x = cmp->clone(); 325 cmp_x->set_req(1,phi_x); 326 cmp_x->set_req(2,con2); 327 cmp_x = phase->transform(cmp_x); 328 // Make the bool 329 Node *b_c = phase->transform(new BoolNode(cmp_c,b->_test._test)); 330 Node *b_x = phase->transform(new BoolNode(cmp_x,b->_test._test)); 331 // Make the IfNode 332 IfNode* iff_c = iff->clone()->as_If(); 333 iff_c->set_req(0, region_c); 334 iff_c->set_req(1, b_c); 335 igvn->set_type_bottom(iff_c); 336 igvn->_worklist.push(iff_c); 337 hook->init_req(2, iff_c); 338 339 IfNode* iff_x = iff->clone()->as_If(); 340 iff_x->set_req(0, region_x); 341 iff_x->set_req(1, b_x); 342 igvn->set_type_bottom(iff_x); 343 igvn->_worklist.push(iff_x); 344 hook->init_req(3, iff_x); 345 346 // Make the true/false arms 347 Node *iff_c_t = phase->transform(new IfTrueNode (iff_c)); 348 Node *iff_c_f = phase->transform(new IfFalseNode(iff_c)); 349 if (predicate_c != NULL) { 350 assert(predicate_x == NULL, "only one predicate entry expected"); 351 // Clone loop predicates to each path 352 iff_c_t = igvn->clone_loop_predicates(predicate_c, iff_c_t, !counted_loop); 353 iff_c_f = igvn->clone_loop_predicates(predicate_c, iff_c_f, !counted_loop); 354 } 355 Node *iff_x_t = phase->transform(new IfTrueNode (iff_x)); 356 Node *iff_x_f = phase->transform(new IfFalseNode(iff_x)); 357 if (predicate_x != NULL) { 358 assert(predicate_c == NULL, "only one predicate entry expected"); 359 // Clone loop predicates to each path 360 iff_x_t = igvn->clone_loop_predicates(predicate_x, iff_x_t, !counted_loop); 361 iff_x_f = igvn->clone_loop_predicates(predicate_x, iff_x_f, !counted_loop); 362 } 363 364 // Merge the TRUE paths 365 Node *region_s = new RegionNode(3); 366 igvn->_worklist.push(region_s); 367 region_s->init_req(1, iff_c_t); 368 region_s->init_req(2, iff_x_t); 369 igvn->register_new_node_with_optimizer( region_s ); 370 371 // Merge the FALSE paths 372 Node *region_f = new RegionNode(3); 373 igvn->_worklist.push(region_f); 374 region_f->init_req(1, iff_c_f); 375 region_f->init_req(2, iff_x_f); 376 igvn->register_new_node_with_optimizer( region_f ); 377 378 igvn->hash_delete(cmp);// Remove soon-to-be-dead node from hash table. 379 cmp->set_req(1,NULL); // Whack the inputs to cmp because it will be dead 380 cmp->set_req(2,NULL); 381 // Check for all uses of the Phi and give them a new home. 382 // The 'cmp' got cloned, but CastPP/IIs need to be moved. 383 Node *phi_s = NULL; // do not construct unless needed 384 Node *phi_f = NULL; // do not construct unless needed 385 for (DUIterator_Last i2min, i2 = phi->last_outs(i2min); i2 >= i2min; --i2) { 386 Node* v = phi->last_out(i2);// User of the phi 387 igvn->rehash_node_delayed(v); // Have to fixup other Phi users 388 uint vop = v->Opcode(); 389 Node *proj = NULL; 390 if( vop == Op_Phi ) { // Remote merge point 391 Node *r = v->in(0); 392 for (uint i3 = 1; i3 < r->req(); i3++) 393 if (r->in(i3) && r->in(i3)->in(0) == iff) { 394 proj = r->in(i3); 395 break; 396 } 397 } else if( v->is_ConstraintCast() ) { 398 proj = v->in(0); // Controlling projection 399 } else { 400 assert( 0, "do not know how to handle this guy" ); 401 } 402 guarantee(proj != NULL, "sanity"); 403 404 Node *proj_path_data, *proj_path_ctrl; 405 if( proj->Opcode() == Op_IfTrue ) { 406 if( phi_s == NULL ) { 407 // Only construct phi_s if needed, otherwise provides 408 // interfering use. 409 phi_s = PhiNode::make_blank(region_s,phi); 410 phi_s->init_req( 1, phi_c ); 411 phi_s->init_req( 2, phi_x ); 412 hook->add_req(phi_s); 413 phi_s = phase->transform(phi_s); 414 } 415 proj_path_data = phi_s; 416 proj_path_ctrl = region_s; 417 } else { 418 if( phi_f == NULL ) { 419 // Only construct phi_f if needed, otherwise provides 420 // interfering use. 421 phi_f = PhiNode::make_blank(region_f,phi); 422 phi_f->init_req( 1, phi_c ); 423 phi_f->init_req( 2, phi_x ); 424 hook->add_req(phi_f); 425 phi_f = phase->transform(phi_f); 426 } 427 proj_path_data = phi_f; 428 proj_path_ctrl = region_f; 429 } 430 431 // Fixup 'v' for for the split 432 if( vop == Op_Phi ) { // Remote merge point 433 uint i; 434 for( i = 1; i < v->req(); i++ ) 435 if( v->in(i) == phi ) 436 break; 437 v->set_req(i, proj_path_data ); 438 } else if( v->is_ConstraintCast() ) { 439 v->set_req(0, proj_path_ctrl ); 440 v->set_req(1, proj_path_data ); 441 } else 442 ShouldNotReachHere(); 443 } 444 445 // Now replace the original iff's True/False with region_s/region_t. 446 // This makes the original iff go dead. 447 for (DUIterator_Last i3min, i3 = iff->last_outs(i3min); i3 >= i3min; --i3) { 448 Node* p = iff->last_out(i3); 449 assert( p->Opcode() == Op_IfTrue || p->Opcode() == Op_IfFalse, "" ); 450 Node *u = (p->Opcode() == Op_IfTrue) ? region_s : region_f; 451 // Replace p with u 452 igvn->add_users_to_worklist(p); 453 for (DUIterator_Last lmin, l = p->last_outs(lmin); l >= lmin;) { 454 Node* x = p->last_out(l); 455 igvn->hash_delete(x); 456 uint uses_found = 0; 457 for( uint j = 0; j < x->req(); j++ ) { 458 if( x->in(j) == p ) { 459 x->set_req(j, u); 460 uses_found++; 461 } 462 } 463 l -= uses_found; // we deleted 1 or more copies of this edge 464 } 465 igvn->remove_dead_node(p); 466 } 467 468 // Force the original merge dead 469 igvn->hash_delete(r); 470 // First, remove region's dead users. 471 for (DUIterator_Last lmin, l = r->last_outs(lmin); l >= lmin;) { 472 Node* u = r->last_out(l); 473 if( u == r ) { 474 r->set_req(0, NULL); 475 } else { 476 assert(u->outcnt() == 0, "only dead users"); 477 igvn->remove_dead_node(u); 478 } 479 l -= 1; 480 } 481 igvn->remove_dead_node(r); 482 483 // Now remove the bogus extra edges used to keep things alive 484 igvn->remove_dead_node( hook ); 485 486 // Must return either the original node (now dead) or a new node 487 // (Do not return a top here, since that would break the uniqueness of top.) 488 return new ConINode(TypeInt::ZERO); 489 } 490 491 // if this IfNode follows a range check pattern return the projection 492 // for the failed path 493 ProjNode* IfNode::range_check_trap_proj(int& flip_test, Node*& l, Node*& r) { 494 if (outcnt() != 2) { 495 return NULL; 496 } 497 Node* b = in(1); 498 if (b == NULL || !b->is_Bool()) return NULL; 499 BoolNode* bn = b->as_Bool(); 500 Node* cmp = bn->in(1); 501 if (cmp == NULL) return NULL; 502 if (cmp->Opcode() != Op_CmpU) return NULL; 503 504 l = cmp->in(1); 505 r = cmp->in(2); 506 flip_test = 1; 507 if (bn->_test._test == BoolTest::le) { 508 l = cmp->in(2); 509 r = cmp->in(1); 510 flip_test = 2; 511 } else if (bn->_test._test != BoolTest::lt) { 512 return NULL; 513 } 514 if (l->is_top()) return NULL; // Top input means dead test 515 if (r->Opcode() != Op_LoadRange && !is_RangeCheck()) return NULL; 516 517 // We have recognized one of these forms: 518 // Flip 1: If (Bool[<] CmpU(l, LoadRange)) ... 519 // Flip 2: If (Bool[<=] CmpU(LoadRange, l)) ... 520 521 ProjNode* iftrap = proj_out_or_null(flip_test == 2 ? true : false); 522 return iftrap; 523 } 524 525 526 //------------------------------is_range_check--------------------------------- 527 // Return 0 if not a range check. Return 1 if a range check and set index and 528 // offset. Return 2 if we had to negate the test. Index is NULL if the check 529 // is versus a constant. 530 int RangeCheckNode::is_range_check(Node* &range, Node* &index, jint &offset) { 531 int flip_test = 0; 532 Node* l = NULL; 533 Node* r = NULL; 534 ProjNode* iftrap = range_check_trap_proj(flip_test, l, r); 535 536 if (iftrap == NULL) { 537 return 0; 538 } 539 540 // Make sure it's a real range check by requiring an uncommon trap 541 // along the OOB path. Otherwise, it's possible that the user wrote 542 // something which optimized to look like a range check but behaves 543 // in some other way. 544 if (iftrap->is_uncommon_trap_proj(Deoptimization::Reason_range_check) == NULL) { 545 return 0; 546 } 547 548 // Look for index+offset form 549 Node* ind = l; 550 jint off = 0; 551 if (l->is_top()) { 552 return 0; 553 } else if (l->Opcode() == Op_AddI) { 554 if ((off = l->in(1)->find_int_con(0)) != 0) { 555 ind = l->in(2)->uncast(); 556 } else if ((off = l->in(2)->find_int_con(0)) != 0) { 557 ind = l->in(1)->uncast(); 558 } 559 } else if ((off = l->find_int_con(-1)) >= 0) { 560 // constant offset with no variable index 561 ind = NULL; 562 } else { 563 // variable index with no constant offset (or dead negative index) 564 off = 0; 565 } 566 567 // Return all the values: 568 index = ind; 569 offset = off; 570 range = r; 571 return flip_test; 572 } 573 574 //------------------------------adjust_check----------------------------------- 575 // Adjust (widen) a prior range check 576 static void adjust_check(Node* proj, Node* range, Node* index, 577 int flip, jint off_lo, PhaseIterGVN* igvn) { 578 PhaseGVN *gvn = igvn; 579 // Break apart the old check 580 Node *iff = proj->in(0); 581 Node *bol = iff->in(1); 582 if( bol->is_top() ) return; // In case a partially dead range check appears 583 // bail (or bomb[ASSERT/DEBUG]) if NOT projection-->IfNode-->BoolNode 584 DEBUG_ONLY( if( !bol->is_Bool() ) { proj->dump(3); fatal("Expect projection-->IfNode-->BoolNode"); } ) 585 if( !bol->is_Bool() ) return; 586 587 Node *cmp = bol->in(1); 588 // Compute a new check 589 Node *new_add = gvn->intcon(off_lo); 590 if( index ) { 591 new_add = off_lo ? gvn->transform(new AddINode( index, new_add )) : index; 592 } 593 Node *new_cmp = (flip == 1) 594 ? new CmpUNode( new_add, range ) 595 : new CmpUNode( range, new_add ); 596 new_cmp = gvn->transform(new_cmp); 597 // See if no need to adjust the existing check 598 if( new_cmp == cmp ) return; 599 // Else, adjust existing check 600 Node *new_bol = gvn->transform( new BoolNode( new_cmp, bol->as_Bool()->_test._test ) ); 601 igvn->rehash_node_delayed( iff ); 602 iff->set_req_X( 1, new_bol, igvn ); 603 } 604 605 //------------------------------up_one_dom------------------------------------- 606 // Walk up the dominator tree one step. Return NULL at root or true 607 // complex merges. Skips through small diamonds. 608 Node* IfNode::up_one_dom(Node *curr, bool linear_only) { 609 Node *dom = curr->in(0); 610 if( !dom ) // Found a Region degraded to a copy? 611 return curr->nonnull_req(); // Skip thru it 612 613 if( curr != dom ) // Normal walk up one step? 614 return dom; 615 616 // Use linear_only if we are still parsing, since we cannot 617 // trust the regions to be fully filled in. 618 if (linear_only) 619 return NULL; 620 621 if( dom->is_Root() ) 622 return NULL; 623 624 // Else hit a Region. Check for a loop header 625 if( dom->is_Loop() ) 626 return dom->in(1); // Skip up thru loops 627 628 // Check for small diamonds 629 Node *din1, *din2, *din3, *din4; 630 if( dom->req() == 3 && // 2-path merge point 631 (din1 = dom ->in(1)) && // Left path exists 632 (din2 = dom ->in(2)) && // Right path exists 633 (din3 = din1->in(0)) && // Left path up one 634 (din4 = din2->in(0)) ) { // Right path up one 635 if( din3->is_Call() && // Handle a slow-path call on either arm 636 (din3 = din3->in(0)) ) 637 din3 = din3->in(0); 638 if( din4->is_Call() && // Handle a slow-path call on either arm 639 (din4 = din4->in(0)) ) 640 din4 = din4->in(0); 641 if( din3 == din4 && din3->is_If() ) 642 return din3; // Skip around diamonds 643 } 644 645 // Give up the search at true merges 646 return NULL; // Dead loop? Or hit root? 647 } 648 649 650 //------------------------------filtered_int_type-------------------------------- 651 // Return a possibly more restrictive type for val based on condition control flow for an if 652 const TypeInt* IfNode::filtered_int_type(PhaseGVN* gvn, Node *val, Node* if_proj) { 653 assert(if_proj && 654 (if_proj->Opcode() == Op_IfTrue || if_proj->Opcode() == Op_IfFalse), "expecting an if projection"); 655 if (if_proj->in(0) && if_proj->in(0)->is_If()) { 656 IfNode* iff = if_proj->in(0)->as_If(); 657 if (iff->in(1) && iff->in(1)->is_Bool()) { 658 BoolNode* bol = iff->in(1)->as_Bool(); 659 if (bol->in(1) && bol->in(1)->is_Cmp()) { 660 const CmpNode* cmp = bol->in(1)->as_Cmp(); 661 if (cmp->in(1) == val) { 662 const TypeInt* cmp2_t = gvn->type(cmp->in(2))->isa_int(); 663 if (cmp2_t != NULL) { 664 jint lo = cmp2_t->_lo; 665 jint hi = cmp2_t->_hi; 666 BoolTest::mask msk = if_proj->Opcode() == Op_IfTrue ? bol->_test._test : bol->_test.negate(); 667 switch (msk) { 668 case BoolTest::ne: 669 // Can't refine type 670 return NULL; 671 case BoolTest::eq: 672 return cmp2_t; 673 case BoolTest::lt: 674 lo = TypeInt::INT->_lo; 675 if (hi - 1 < hi) { 676 hi = hi - 1; 677 } 678 break; 679 case BoolTest::le: 680 lo = TypeInt::INT->_lo; 681 break; 682 case BoolTest::gt: 683 if (lo + 1 > lo) { 684 lo = lo + 1; 685 } 686 hi = TypeInt::INT->_hi; 687 break; 688 case BoolTest::ge: 689 // lo unchanged 690 hi = TypeInt::INT->_hi; 691 break; 692 default: 693 break; 694 } 695 const TypeInt* rtn_t = TypeInt::make(lo, hi, cmp2_t->_widen); 696 return rtn_t; 697 } 698 } 699 } 700 } 701 } 702 return NULL; 703 } 704 705 //------------------------------fold_compares---------------------------- 706 // See if a pair of CmpIs can be converted into a CmpU. In some cases 707 // the direction of this if is determined by the preceding if so it 708 // can be eliminate entirely. 709 // 710 // Given an if testing (CmpI n v) check for an immediately control 711 // dependent if that is testing (CmpI n v2) and has one projection 712 // leading to this if and the other projection leading to a region 713 // that merges one of this ifs control projections. 714 // 715 // If 716 // / | 717 // / | 718 // / | 719 // If | 720 // /\ | 721 // / \ | 722 // / \ | 723 // / Region 724 // 725 // Or given an if testing (CmpI n v) check for a dominating if that is 726 // testing (CmpI n v2), both having one projection leading to an 727 // uncommon trap. Allow Another independent guard in between to cover 728 // an explicit range check: 729 // if (index < 0 || index >= array.length) { 730 // which may need a null check to guard the LoadRange 731 // 732 // If 733 // / \ 734 // / \ 735 // / \ 736 // If unc 737 // /\ 738 // / \ 739 // / \ 740 // / unc 741 // 742 743 // Is the comparison for this If suitable for folding? 744 bool IfNode::cmpi_folds(PhaseIterGVN* igvn) { 745 return in(1) != NULL && 746 in(1)->is_Bool() && 747 in(1)->in(1) != NULL && 748 in(1)->in(1)->Opcode() == Op_CmpI && 749 in(1)->in(1)->in(2) != NULL && 750 in(1)->in(1)->in(2) != igvn->C->top() && 751 (in(1)->as_Bool()->_test.is_less() || 752 in(1)->as_Bool()->_test.is_greater()); 753 } 754 755 // Is a dominating control suitable for folding with this if? 756 bool IfNode::is_ctrl_folds(Node* ctrl, PhaseIterGVN* igvn) { 757 return ctrl != NULL && 758 ctrl->is_Proj() && 759 ctrl->in(0) != NULL && 760 ctrl->in(0)->Opcode() == Op_If && 761 ctrl->in(0)->outcnt() == 2 && 762 ctrl->in(0)->as_If()->cmpi_folds(igvn) && 763 // Must compare same value 764 ctrl->in(0)->in(1)->in(1)->in(1) != NULL && 765 ctrl->in(0)->in(1)->in(1)->in(1) == in(1)->in(1)->in(1); 766 } 767 768 // Do this If and the dominating If share a region? 769 bool IfNode::has_shared_region(ProjNode* proj, ProjNode*& success, ProjNode*& fail) { 770 ProjNode* otherproj = proj->other_if_proj(); 771 Node* otherproj_ctrl_use = otherproj->unique_ctrl_out(); 772 RegionNode* region = (otherproj_ctrl_use != NULL && otherproj_ctrl_use->is_Region()) ? otherproj_ctrl_use->as_Region() : NULL; 773 success = NULL; 774 fail = NULL; 775 776 if (otherproj->outcnt() == 1 && region != NULL && !region->has_phi()) { 777 for (int i = 0; i < 2; i++) { 778 ProjNode* proj = proj_out(i); 779 if (success == NULL && proj->outcnt() == 1 && proj->unique_out() == region) { 780 success = proj; 781 } else if (fail == NULL) { 782 fail = proj; 783 } else { 784 success = fail = NULL; 785 } 786 } 787 } 788 return success != NULL && fail != NULL; 789 } 790 791 bool IfNode::is_dominator_unc(CallStaticJavaNode* dom_unc, CallStaticJavaNode* unc) { 792 // Different methods and methods containing jsrs are not supported. 793 ciMethod* method = unc->jvms()->method(); 794 ciMethod* dom_method = dom_unc->jvms()->method(); 795 if (method != dom_method || method->has_jsrs()) { 796 return false; 797 } 798 // Check that both traps are in the same activation of the method (instead 799 // of two activations being inlined through different call sites) by verifying 800 // that the call stacks are equal for both JVMStates. 801 JVMState* dom_caller = dom_unc->jvms()->caller(); 802 JVMState* caller = unc->jvms()->caller(); 803 if ((dom_caller == NULL) != (caller == NULL)) { 804 // The current method must either be inlined into both dom_caller and 805 // caller or must not be inlined at all (top method). Bail out otherwise. 806 return false; 807 } else if (dom_caller != NULL && !dom_caller->same_calls_as(caller)) { 808 return false; 809 } 810 // Check that the bci of the dominating uncommon trap dominates the bci 811 // of the dominated uncommon trap. Otherwise we may not re-execute 812 // the dominated check after deoptimization from the merged uncommon trap. 813 ciTypeFlow* flow = dom_method->get_flow_analysis(); 814 int bci = unc->jvms()->bci(); 815 int dom_bci = dom_unc->jvms()->bci(); 816 if (!flow->is_dominated_by(bci, dom_bci)) { 817 return false; 818 } 819 820 return true; 821 } 822 823 // Return projection that leads to an uncommon trap if any 824 ProjNode* IfNode::uncommon_trap_proj(CallStaticJavaNode*& call) const { 825 for (int i = 0; i < 2; i++) { 826 call = proj_out(i)->is_uncommon_trap_proj(Deoptimization::Reason_none); 827 if (call != NULL) { 828 return proj_out(i); 829 } 830 } 831 return NULL; 832 } 833 834 // Do this If and the dominating If both branch out to an uncommon trap 835 bool IfNode::has_only_uncommon_traps(ProjNode* proj, ProjNode*& success, ProjNode*& fail, PhaseIterGVN* igvn) { 836 ProjNode* otherproj = proj->other_if_proj(); 837 CallStaticJavaNode* dom_unc = otherproj->is_uncommon_trap_proj(Deoptimization::Reason_none); 838 839 if (otherproj->outcnt() == 1 && dom_unc != NULL) { 840 // We need to re-execute the folded Ifs after deoptimization from the merged traps 841 if (!dom_unc->jvms()->should_reexecute()) { 842 return false; 843 } 844 845 CallStaticJavaNode* unc = NULL; 846 ProjNode* unc_proj = uncommon_trap_proj(unc); 847 if (unc_proj != NULL && unc_proj->outcnt() == 1) { 848 if (dom_unc == unc) { 849 // Allow the uncommon trap to be shared through a region 850 RegionNode* r = unc->in(0)->as_Region(); 851 if (r->outcnt() != 2 || r->req() != 3 || r->find_edge(otherproj) == -1 || r->find_edge(unc_proj) == -1) { 852 return false; 853 } 854 assert(r->has_phi() == NULL, "simple region shouldn't have a phi"); 855 } else if (dom_unc->in(0) != otherproj || unc->in(0) != unc_proj) { 856 return false; 857 } 858 859 if (!is_dominator_unc(dom_unc, unc)) { 860 return false; 861 } 862 863 // See merge_uncommon_traps: the reason of the uncommon trap 864 // will be changed and the state of the dominating If will be 865 // used. Checked that we didn't apply this transformation in a 866 // previous compilation and it didn't cause too many traps 867 ciMethod* dom_method = dom_unc->jvms()->method(); 868 int dom_bci = dom_unc->jvms()->bci(); 869 if (!igvn->C->too_many_traps(dom_method, dom_bci, Deoptimization::Reason_unstable_fused_if) && 870 !igvn->C->too_many_traps(dom_method, dom_bci, Deoptimization::Reason_range_check)) { 871 success = unc_proj; 872 fail = unc_proj->other_if_proj(); 873 return true; 874 } 875 } 876 } 877 return false; 878 } 879 880 // Check that the 2 CmpI can be folded into as single CmpU and proceed with the folding 881 bool IfNode::fold_compares_helper(ProjNode* proj, ProjNode* success, ProjNode* fail, PhaseIterGVN* igvn) { 882 Node* this_cmp = in(1)->in(1); 883 BoolNode* this_bool = in(1)->as_Bool(); 884 IfNode* dom_iff = proj->in(0)->as_If(); 885 BoolNode* dom_bool = dom_iff->in(1)->as_Bool(); 886 Node* lo = dom_iff->in(1)->in(1)->in(2); 887 Node* hi = this_cmp->in(2); 888 Node* n = this_cmp->in(1); 889 ProjNode* otherproj = proj->other_if_proj(); 890 891 const TypeInt* lo_type = IfNode::filtered_int_type(igvn, n, otherproj); 892 const TypeInt* hi_type = IfNode::filtered_int_type(igvn, n, success); 893 894 BoolTest::mask lo_test = dom_bool->_test._test; 895 BoolTest::mask hi_test = this_bool->_test._test; 896 BoolTest::mask cond = hi_test; 897 898 // convert: 899 // 900 // dom_bool = x {<,<=,>,>=} a 901 // / \ 902 // proj = {True,False} / \ otherproj = {False,True} 903 // / 904 // this_bool = x {<,<=} b 905 // / \ 906 // fail = {True,False} / \ success = {False,True} 907 // / 908 // 909 // (Second test guaranteed canonicalized, first one may not have 910 // been canonicalized yet) 911 // 912 // into: 913 // 914 // cond = (x - lo) {<u,<=u,>u,>=u} adjusted_lim 915 // / \ 916 // fail / \ success 917 // / 918 // 919 920 // Figure out which of the two tests sets the upper bound and which 921 // sets the lower bound if any. 922 Node* adjusted_lim = NULL; 923 if (lo_type != NULL && hi_type != NULL && hi_type->_lo > lo_type->_hi && 924 hi_type->_hi == max_jint && lo_type->_lo == min_jint) { 925 assert((dom_bool->_test.is_less() && !proj->_con) || 926 (dom_bool->_test.is_greater() && proj->_con), "incorrect test"); 927 // this test was canonicalized 928 assert(this_bool->_test.is_less() && fail->_con, "incorrect test"); 929 930 // this_bool = < 931 // dom_bool = >= (proj = True) or dom_bool = < (proj = False) 932 // x in [a, b[ on the fail (= True) projection, b > a-1 (because of hi_type->_lo > lo_type->_hi test above): 933 // lo = a, hi = b, adjusted_lim = b-a, cond = <u 934 // dom_bool = > (proj = True) or dom_bool = <= (proj = False) 935 // x in ]a, b[ on the fail (= True) projection, b > a: 936 // lo = a+1, hi = b, adjusted_lim = b-a-1, cond = <u 937 // this_bool = <= 938 // dom_bool = >= (proj = True) or dom_bool = < (proj = False) 939 // x in [a, b] on the fail (= True) projection, b+1 > a-1: 940 // lo = a, hi = b, adjusted_lim = b-a+1, cond = <u 941 // lo = a, hi = b, adjusted_lim = b-a, cond = <=u doesn't work because b = a - 1 is possible, then b-a = -1 942 // dom_bool = > (proj = True) or dom_bool = <= (proj = False) 943 // x in ]a, b] on the fail (= True) projection b+1 > a: 944 // lo = a+1, hi = b, adjusted_lim = b-a, cond = <u 945 // lo = a+1, hi = b, adjusted_lim = b-a-1, cond = <=u doesn't work because a = b is possible, then b-a-1 = -1 946 947 if (hi_test == BoolTest::lt) { 948 if (lo_test == BoolTest::gt || lo_test == BoolTest::le) { 949 lo = igvn->transform(new AddINode(lo, igvn->intcon(1))); 950 } 951 } else { 952 assert(hi_test == BoolTest::le, "bad test"); 953 if (lo_test == BoolTest::ge || lo_test == BoolTest::lt) { 954 adjusted_lim = igvn->transform(new SubINode(hi, lo)); 955 adjusted_lim = igvn->transform(new AddINode(adjusted_lim, igvn->intcon(1))); 956 cond = BoolTest::lt; 957 } else { 958 assert(lo_test == BoolTest::gt || lo_test == BoolTest::le, "bad test"); 959 adjusted_lim = igvn->transform(new SubINode(hi, lo)); 960 lo = igvn->transform(new AddINode(lo, igvn->intcon(1))); 961 cond = BoolTest::lt; 962 } 963 } 964 } else if (lo_type != NULL && hi_type != NULL && lo_type->_lo > hi_type->_hi && 965 lo_type->_hi == max_jint && hi_type->_lo == min_jint) { 966 967 // this_bool = < 968 // dom_bool = < (proj = True) or dom_bool = >= (proj = False) 969 // x in [b, a[ on the fail (= False) projection, a > b-1 (because of lo_type->_lo > hi_type->_hi above): 970 // lo = b, hi = a, adjusted_lim = a-b, cond = >=u 971 // dom_bool = <= (proj = True) or dom_bool = > (proj = False) 972 // x in [b, a] on the fail (= False) projection, a+1 > b-1: 973 // lo = b, hi = a, adjusted_lim = a-b+1, cond = >=u 974 // lo = b, hi = a, adjusted_lim = a-b, cond = >u doesn't work because a = b - 1 is possible, then b-a = -1 975 // this_bool = <= 976 // dom_bool = < (proj = True) or dom_bool = >= (proj = False) 977 // x in ]b, a[ on the fail (= False) projection, a > b: 978 // lo = b+1, hi = a, adjusted_lim = a-b-1, cond = >=u 979 // dom_bool = <= (proj = True) or dom_bool = > (proj = False) 980 // x in ]b, a] on the fail (= False) projection, a+1 > b: 981 // lo = b+1, hi = a, adjusted_lim = a-b, cond = >=u 982 // lo = b+1, hi = a, adjusted_lim = a-b-1, cond = >u doesn't work because a = b is possible, then b-a-1 = -1 983 984 swap(lo, hi); 985 swap(lo_type, hi_type); 986 swap(lo_test, hi_test); 987 988 assert((dom_bool->_test.is_less() && proj->_con) || 989 (dom_bool->_test.is_greater() && !proj->_con), "incorrect test"); 990 // this test was canonicalized 991 assert(this_bool->_test.is_less() && !fail->_con, "incorrect test"); 992 993 cond = (hi_test == BoolTest::le || hi_test == BoolTest::gt) ? BoolTest::gt : BoolTest::ge; 994 995 if (lo_test == BoolTest::lt) { 996 if (hi_test == BoolTest::lt || hi_test == BoolTest::ge) { 997 cond = BoolTest::ge; 998 } else { 999 assert(hi_test == BoolTest::le || hi_test == BoolTest::gt, "bad test"); 1000 adjusted_lim = igvn->transform(new SubINode(hi, lo)); 1001 adjusted_lim = igvn->transform(new AddINode(adjusted_lim, igvn->intcon(1))); 1002 cond = BoolTest::ge; 1003 } 1004 } else if (lo_test == BoolTest::le) { 1005 if (hi_test == BoolTest::lt || hi_test == BoolTest::ge) { 1006 lo = igvn->transform(new AddINode(lo, igvn->intcon(1))); 1007 cond = BoolTest::ge; 1008 } else { 1009 assert(hi_test == BoolTest::le || hi_test == BoolTest::gt, "bad test"); 1010 adjusted_lim = igvn->transform(new SubINode(hi, lo)); 1011 lo = igvn->transform(new AddINode(lo, igvn->intcon(1))); 1012 cond = BoolTest::ge; 1013 } 1014 } 1015 } else { 1016 const TypeInt* failtype = filtered_int_type(igvn, n, proj); 1017 if (failtype != NULL) { 1018 const TypeInt* type2 = filtered_int_type(igvn, n, fail); 1019 if (type2 != NULL) { 1020 failtype = failtype->join(type2)->is_int(); 1021 if (failtype->_lo > failtype->_hi) { 1022 // previous if determines the result of this if so 1023 // replace Bool with constant 1024 igvn->_worklist.push(in(1)); 1025 igvn->replace_input_of(this, 1, igvn->intcon(success->_con)); 1026 return true; 1027 } 1028 } 1029 } 1030 lo = NULL; 1031 hi = NULL; 1032 } 1033 1034 if (lo && hi) { 1035 // Merge the two compares into a single unsigned compare by building (CmpU (n - lo) (hi - lo)) 1036 Node* adjusted_val = igvn->transform(new SubINode(n, lo)); 1037 if (adjusted_lim == NULL) { 1038 adjusted_lim = igvn->transform(new SubINode(hi, lo)); 1039 } 1040 Node* newcmp = igvn->transform(new CmpUNode(adjusted_val, adjusted_lim)); 1041 Node* newbool = igvn->transform(new BoolNode(newcmp, cond)); 1042 1043 igvn->replace_input_of(dom_iff, 1, igvn->intcon(proj->_con)); 1044 igvn->_worklist.push(in(1)); 1045 igvn->replace_input_of(this, 1, newbool); 1046 1047 return true; 1048 } 1049 return false; 1050 } 1051 1052 // Merge the branches that trap for this If and the dominating If into 1053 // a single region that branches to the uncommon trap for the 1054 // dominating If 1055 Node* IfNode::merge_uncommon_traps(ProjNode* proj, ProjNode* success, ProjNode* fail, PhaseIterGVN* igvn) { 1056 Node* res = this; 1057 assert(success->in(0) == this, "bad projection"); 1058 1059 ProjNode* otherproj = proj->other_if_proj(); 1060 1061 CallStaticJavaNode* unc = success->is_uncommon_trap_proj(Deoptimization::Reason_none); 1062 CallStaticJavaNode* dom_unc = otherproj->is_uncommon_trap_proj(Deoptimization::Reason_none); 1063 1064 if (unc != dom_unc) { 1065 Node* r = new RegionNode(3); 1066 1067 r->set_req(1, otherproj); 1068 r->set_req(2, success); 1069 r = igvn->transform(r); 1070 assert(r->is_Region(), "can't go away"); 1071 1072 // Make both If trap at the state of the first If: once the CmpI 1073 // nodes are merged, if we trap we don't know which of the CmpI 1074 // nodes would have caused the trap so we have to restart 1075 // execution at the first one 1076 igvn->replace_input_of(dom_unc, 0, r); 1077 igvn->replace_input_of(unc, 0, igvn->C->top()); 1078 } 1079 int trap_request = dom_unc->uncommon_trap_request(); 1080 Deoptimization::DeoptReason reason = Deoptimization::trap_request_reason(trap_request); 1081 Deoptimization::DeoptAction action = Deoptimization::trap_request_action(trap_request); 1082 1083 int flip_test = 0; 1084 Node* l = NULL; 1085 Node* r = NULL; 1086 1087 if (success->in(0)->as_If()->range_check_trap_proj(flip_test, l, r) != NULL) { 1088 // If this looks like a range check, change the trap to 1089 // Reason_range_check so the compiler recognizes it as a range 1090 // check and applies the corresponding optimizations 1091 trap_request = Deoptimization::make_trap_request(Deoptimization::Reason_range_check, action); 1092 1093 improve_address_types(l, r, fail, igvn); 1094 1095 res = igvn->transform(new RangeCheckNode(in(0), in(1), _prob, _fcnt)); 1096 } else if (unc != dom_unc) { 1097 // If we trap we won't know what CmpI would have caused the trap 1098 // so use a special trap reason to mark this pair of CmpI nodes as 1099 // bad candidate for folding. On recompilation we won't fold them 1100 // and we may trap again but this time we'll know what branch 1101 // traps 1102 trap_request = Deoptimization::make_trap_request(Deoptimization::Reason_unstable_fused_if, action); 1103 } 1104 igvn->replace_input_of(dom_unc, TypeFunc::Parms, igvn->intcon(trap_request)); 1105 return res; 1106 } 1107 1108 // If we are turning 2 CmpI nodes into a CmpU that follows the pattern 1109 // of a rangecheck on index i, on 64 bit the compares may be followed 1110 // by memory accesses using i as index. In that case, the CmpU tells 1111 // us something about the values taken by i that can help the compiler 1112 // (see Compile::conv_I2X_index()) 1113 void IfNode::improve_address_types(Node* l, Node* r, ProjNode* fail, PhaseIterGVN* igvn) { 1114 #ifdef _LP64 1115 ResourceMark rm; 1116 Node_Stack stack(2); 1117 1118 assert(r->Opcode() == Op_LoadRange, "unexpected range check"); 1119 const TypeInt* array_size = igvn->type(r)->is_int(); 1120 1121 stack.push(l, 0); 1122 1123 while(stack.size() > 0) { 1124 Node* n = stack.node(); 1125 uint start = stack.index(); 1126 1127 uint i = start; 1128 for (; i < n->outcnt(); i++) { 1129 Node* use = n->raw_out(i); 1130 if (stack.size() == 1) { 1131 if (use->Opcode() == Op_ConvI2L) { 1132 const TypeLong* bounds = use->as_Type()->type()->is_long(); 1133 if (bounds->_lo <= array_size->_lo && bounds->_hi >= array_size->_hi && 1134 (bounds->_lo != array_size->_lo || bounds->_hi != array_size->_hi)) { 1135 stack.set_index(i+1); 1136 stack.push(use, 0); 1137 break; 1138 } 1139 } 1140 } else if (use->is_Mem()) { 1141 Node* ctrl = use->in(0); 1142 for (int i = 0; i < 10 && ctrl != NULL && ctrl != fail; i++) { 1143 ctrl = up_one_dom(ctrl); 1144 } 1145 if (ctrl == fail) { 1146 Node* init_n = stack.node_at(1); 1147 assert(init_n->Opcode() == Op_ConvI2L, "unexpected first node"); 1148 // Create a new narrow ConvI2L node that is dependent on the range check 1149 Node* new_n = igvn->C->conv_I2X_index(igvn, l, array_size, fail); 1150 1151 // The type of the ConvI2L may be widen and so the new 1152 // ConvI2L may not be better than an existing ConvI2L 1153 if (new_n != init_n) { 1154 for (uint j = 2; j < stack.size(); j++) { 1155 Node* n = stack.node_at(j); 1156 Node* clone = n->clone(); 1157 int rep = clone->replace_edge(init_n, new_n); 1158 assert(rep > 0, "can't find expected node?"); 1159 clone = igvn->transform(clone); 1160 init_n = n; 1161 new_n = clone; 1162 } 1163 igvn->hash_delete(use); 1164 int rep = use->replace_edge(init_n, new_n); 1165 assert(rep > 0, "can't find expected node?"); 1166 igvn->transform(use); 1167 if (init_n->outcnt() == 0) { 1168 igvn->_worklist.push(init_n); 1169 } 1170 } 1171 } 1172 } else if (use->in(0) == NULL && (igvn->type(use)->isa_long() || 1173 igvn->type(use)->isa_ptr())) { 1174 stack.set_index(i+1); 1175 stack.push(use, 0); 1176 break; 1177 } 1178 } 1179 if (i == n->outcnt()) { 1180 stack.pop(); 1181 } 1182 } 1183 #endif 1184 } 1185 1186 bool IfNode::is_cmp_with_loadrange(ProjNode* proj) { 1187 if (in(1) != NULL && 1188 in(1)->in(1) != NULL && 1189 in(1)->in(1)->in(2) != NULL) { 1190 Node* other = in(1)->in(1)->in(2); 1191 if (other->Opcode() == Op_LoadRange && 1192 ((other->in(0) != NULL && other->in(0) == proj) || 1193 (other->in(0) == NULL && 1194 other->in(2) != NULL && 1195 other->in(2)->is_AddP() && 1196 other->in(2)->in(1) != NULL && 1197 other->in(2)->in(1)->Opcode() == Op_CastPP && 1198 other->in(2)->in(1)->in(0) == proj))) { 1199 return true; 1200 } 1201 } 1202 return false; 1203 } 1204 1205 bool IfNode::is_null_check(ProjNode* proj, PhaseIterGVN* igvn) { 1206 Node* other = in(1)->in(1)->in(2); 1207 if (other->in(MemNode::Address) != NULL && 1208 proj->in(0)->in(1) != NULL && 1209 proj->in(0)->in(1)->is_Bool() && 1210 proj->in(0)->in(1)->in(1) != NULL && 1211 proj->in(0)->in(1)->in(1)->Opcode() == Op_CmpP && 1212 proj->in(0)->in(1)->in(1)->in(2) != NULL && 1213 proj->in(0)->in(1)->in(1)->in(1) == other->in(MemNode::Address)->in(AddPNode::Address)->uncast() && 1214 igvn->type(proj->in(0)->in(1)->in(1)->in(2)) == TypePtr::NULL_PTR) { 1215 return true; 1216 } 1217 return false; 1218 } 1219 1220 // Check that the If that is in between the 2 integer comparisons has 1221 // no side effect 1222 bool IfNode::is_side_effect_free_test(ProjNode* proj, PhaseIterGVN* igvn) { 1223 if (proj == NULL) { 1224 return false; 1225 } 1226 CallStaticJavaNode* unc = proj->is_uncommon_trap_if_pattern(Deoptimization::Reason_none); 1227 if (unc != NULL && proj->outcnt() <= 2) { 1228 if (proj->outcnt() == 1 || 1229 // Allow simple null check from LoadRange 1230 (is_cmp_with_loadrange(proj) && is_null_check(proj, igvn))) { 1231 CallStaticJavaNode* unc = proj->is_uncommon_trap_if_pattern(Deoptimization::Reason_none); 1232 CallStaticJavaNode* dom_unc = proj->in(0)->in(0)->as_Proj()->is_uncommon_trap_if_pattern(Deoptimization::Reason_none); 1233 assert(dom_unc != NULL, "is_uncommon_trap_if_pattern returned NULL"); 1234 1235 // reroute_side_effect_free_unc changes the state of this 1236 // uncommon trap to restart execution at the previous 1237 // CmpI. Check that this change in a previous compilation didn't 1238 // cause too many traps. 1239 int trap_request = unc->uncommon_trap_request(); 1240 Deoptimization::DeoptReason reason = Deoptimization::trap_request_reason(trap_request); 1241 1242 if (igvn->C->too_many_traps(dom_unc->jvms()->method(), dom_unc->jvms()->bci(), reason)) { 1243 return false; 1244 } 1245 1246 if (!is_dominator_unc(dom_unc, unc)) { 1247 return false; 1248 } 1249 1250 return true; 1251 } 1252 } 1253 return false; 1254 } 1255 1256 // Make the If between the 2 integer comparisons trap at the state of 1257 // the first If: the last CmpI is the one replaced by a CmpU and the 1258 // first CmpI is eliminated, so the test between the 2 CmpI nodes 1259 // won't be guarded by the first CmpI anymore. It can trap in cases 1260 // where the first CmpI would have prevented it from executing: on a 1261 // trap, we need to restart execution at the state of the first CmpI 1262 void IfNode::reroute_side_effect_free_unc(ProjNode* proj, ProjNode* dom_proj, PhaseIterGVN* igvn) { 1263 CallStaticJavaNode* dom_unc = dom_proj->is_uncommon_trap_if_pattern(Deoptimization::Reason_none); 1264 ProjNode* otherproj = proj->other_if_proj(); 1265 CallStaticJavaNode* unc = proj->is_uncommon_trap_if_pattern(Deoptimization::Reason_none); 1266 Node* call_proj = dom_unc->unique_ctrl_out(); 1267 Node* halt = call_proj->unique_ctrl_out(); 1268 1269 Node* new_unc = dom_unc->clone(); 1270 call_proj = call_proj->clone(); 1271 halt = halt->clone(); 1272 Node* c = otherproj->clone(); 1273 1274 c = igvn->transform(c); 1275 new_unc->set_req(TypeFunc::Parms, unc->in(TypeFunc::Parms)); 1276 new_unc->set_req(0, c); 1277 new_unc = igvn->transform(new_unc); 1278 call_proj->set_req(0, new_unc); 1279 call_proj = igvn->transform(call_proj); 1280 halt->set_req(0, call_proj); 1281 halt = igvn->transform(halt); 1282 1283 igvn->replace_node(otherproj, igvn->C->top()); 1284 igvn->C->root()->add_req(halt); 1285 } 1286 1287 Node* IfNode::fold_compares(PhaseIterGVN* igvn) { 1288 if (Opcode() != Op_If) return NULL; 1289 1290 if (cmpi_folds(igvn)) { 1291 Node* ctrl = in(0); 1292 if (is_ctrl_folds(ctrl, igvn) && 1293 ctrl->outcnt() == 1) { 1294 // A integer comparison immediately dominated by another integer 1295 // comparison 1296 ProjNode* success = NULL; 1297 ProjNode* fail = NULL; 1298 ProjNode* dom_cmp = ctrl->as_Proj(); 1299 if (has_shared_region(dom_cmp, success, fail) && 1300 // Next call modifies graph so must be last 1301 fold_compares_helper(dom_cmp, success, fail, igvn)) { 1302 return this; 1303 } 1304 if (has_only_uncommon_traps(dom_cmp, success, fail, igvn) && 1305 // Next call modifies graph so must be last 1306 fold_compares_helper(dom_cmp, success, fail, igvn)) { 1307 return merge_uncommon_traps(dom_cmp, success, fail, igvn); 1308 } 1309 return NULL; 1310 } else if (ctrl->in(0) != NULL && 1311 ctrl->in(0)->in(0) != NULL) { 1312 ProjNode* success = NULL; 1313 ProjNode* fail = NULL; 1314 Node* dom = ctrl->in(0)->in(0); 1315 ProjNode* dom_cmp = dom->isa_Proj(); 1316 ProjNode* other_cmp = ctrl->isa_Proj(); 1317 1318 // Check if it's an integer comparison dominated by another 1319 // integer comparison with another test in between 1320 if (is_ctrl_folds(dom, igvn) && 1321 has_only_uncommon_traps(dom_cmp, success, fail, igvn) && 1322 is_side_effect_free_test(other_cmp, igvn) && 1323 // Next call modifies graph so must be last 1324 fold_compares_helper(dom_cmp, success, fail, igvn)) { 1325 reroute_side_effect_free_unc(other_cmp, dom_cmp, igvn); 1326 return merge_uncommon_traps(dom_cmp, success, fail, igvn); 1327 } 1328 } 1329 } 1330 return NULL; 1331 } 1332 1333 //------------------------------remove_useless_bool---------------------------- 1334 // Check for people making a useless boolean: things like 1335 // if( (x < y ? true : false) ) { ... } 1336 // Replace with if( x < y ) { ... } 1337 static Node *remove_useless_bool(IfNode *iff, PhaseGVN *phase) { 1338 Node *i1 = iff->in(1); 1339 if( !i1->is_Bool() ) return NULL; 1340 BoolNode *bol = i1->as_Bool(); 1341 1342 Node *cmp = bol->in(1); 1343 if( cmp->Opcode() != Op_CmpI ) return NULL; 1344 1345 // Must be comparing against a bool 1346 const Type *cmp2_t = phase->type( cmp->in(2) ); 1347 if( cmp2_t != TypeInt::ZERO && 1348 cmp2_t != TypeInt::ONE ) 1349 return NULL; 1350 1351 // Find a prior merge point merging the boolean 1352 i1 = cmp->in(1); 1353 if( !i1->is_Phi() ) return NULL; 1354 PhiNode *phi = i1->as_Phi(); 1355 if( phase->type( phi ) != TypeInt::BOOL ) 1356 return NULL; 1357 1358 // Check for diamond pattern 1359 int true_path = phi->is_diamond_phi(); 1360 if( true_path == 0 ) return NULL; 1361 1362 // Make sure that iff and the control of the phi are different. This 1363 // should really only happen for dead control flow since it requires 1364 // an illegal cycle. 1365 if (phi->in(0)->in(1)->in(0) == iff) return NULL; 1366 1367 // phi->region->if_proj->ifnode->bool->cmp 1368 BoolNode *bol2 = phi->in(0)->in(1)->in(0)->in(1)->as_Bool(); 1369 1370 // Now get the 'sense' of the test correct so we can plug in 1371 // either iff2->in(1) or its complement. 1372 int flip = 0; 1373 if( bol->_test._test == BoolTest::ne ) flip = 1-flip; 1374 else if( bol->_test._test != BoolTest::eq ) return NULL; 1375 if( cmp2_t == TypeInt::ZERO ) flip = 1-flip; 1376 1377 const Type *phi1_t = phase->type( phi->in(1) ); 1378 const Type *phi2_t = phase->type( phi->in(2) ); 1379 // Check for Phi(0,1) and flip 1380 if( phi1_t == TypeInt::ZERO ) { 1381 if( phi2_t != TypeInt::ONE ) return NULL; 1382 flip = 1-flip; 1383 } else { 1384 // Check for Phi(1,0) 1385 if( phi1_t != TypeInt::ONE ) return NULL; 1386 if( phi2_t != TypeInt::ZERO ) return NULL; 1387 } 1388 if( true_path == 2 ) { 1389 flip = 1-flip; 1390 } 1391 1392 Node* new_bol = (flip ? phase->transform( bol2->negate(phase) ) : bol2); 1393 assert(new_bol != iff->in(1), "must make progress"); 1394 iff->set_req(1, new_bol); 1395 // Intervening diamond probably goes dead 1396 phase->C->set_major_progress(); 1397 return iff; 1398 } 1399 1400 static IfNode* idealize_test(PhaseGVN* phase, IfNode* iff); 1401 1402 struct RangeCheck { 1403 Node* ctl; 1404 jint off; 1405 }; 1406 1407 Node* IfNode::Ideal_common(PhaseGVN *phase, bool can_reshape) { 1408 if (remove_dead_region(phase, can_reshape)) return this; 1409 // No Def-Use info? 1410 if (!can_reshape) return NULL; 1411 1412 // Don't bother trying to transform a dead if 1413 if (in(0)->is_top()) return NULL; 1414 // Don't bother trying to transform an if with a dead test 1415 if (in(1)->is_top()) return NULL; 1416 // Another variation of a dead test 1417 if (in(1)->is_Con()) return NULL; 1418 // Another variation of a dead if 1419 if (outcnt() < 2) return NULL; 1420 1421 // Canonicalize the test. 1422 Node* idt_if = idealize_test(phase, this); 1423 if (idt_if != NULL) return idt_if; 1424 1425 // Try to split the IF 1426 PhaseIterGVN *igvn = phase->is_IterGVN(); 1427 Node *s = split_if(this, igvn); 1428 if (s != NULL) return s; 1429 1430 return NodeSentinel; 1431 } 1432 1433 //------------------------------Ideal------------------------------------------ 1434 // Return a node which is more "ideal" than the current node. Strip out 1435 // control copies 1436 Node* IfNode::Ideal(PhaseGVN *phase, bool can_reshape) { 1437 Node* res = Ideal_common(phase, can_reshape); 1438 if (res != NodeSentinel) { 1439 return res; 1440 } 1441 1442 // Check for people making a useless boolean: things like 1443 // if( (x < y ? true : false) ) { ... } 1444 // Replace with if( x < y ) { ... } 1445 Node *bol2 = remove_useless_bool(this, phase); 1446 if( bol2 ) return bol2; 1447 1448 if (in(0) == NULL) return NULL; // Dead loop? 1449 1450 PhaseIterGVN *igvn = phase->is_IterGVN(); 1451 Node* result = fold_compares(igvn); 1452 if (result != NULL) { 1453 return result; 1454 } 1455 1456 // Scan for an equivalent test 1457 Node *cmp; 1458 int dist = 0; // Cutoff limit for search 1459 int op = Opcode(); 1460 if( op == Op_If && 1461 (cmp=in(1)->in(1))->Opcode() == Op_CmpP ) { 1462 if( cmp->in(2) != NULL && // make sure cmp is not already dead 1463 cmp->in(2)->bottom_type() == TypePtr::NULL_PTR ) { 1464 dist = 64; // Limit for null-pointer scans 1465 } else { 1466 dist = 4; // Do not bother for random pointer tests 1467 } 1468 #if INCLUDE_SHENANDOAHGC 1469 } else if (ShenandoahWriteBarrierNode::is_evacuation_in_progress_test(this)) { 1470 dist = 16; 1471 #endif 1472 } else { 1473 dist = 4; // Limit for random junky scans 1474 } 1475 1476 Node* prev_dom = search_identical(dist); 1477 1478 if (prev_dom == NULL) { 1479 return NULL; 1480 } 1481 1482 // Replace dominated IfNode 1483 return dominated_by(prev_dom, igvn); 1484 } 1485 1486 //------------------------------dominated_by----------------------------------- 1487 Node* IfNode::dominated_by(Node* prev_dom, PhaseIterGVN *igvn) { 1488 #ifndef PRODUCT 1489 if (TraceIterativeGVN) { 1490 tty->print(" Removing IfNode: "); this->dump(); 1491 } 1492 if (VerifyOpto && !igvn->allow_progress()) { 1493 // Found an equivalent dominating test, 1494 // we can not guarantee reaching a fix-point for these during iterativeGVN 1495 // since intervening nodes may not change. 1496 return NULL; 1497 } 1498 #endif 1499 1500 igvn->hash_delete(this); // Remove self to prevent spurious V-N 1501 Node *idom = in(0); 1502 // Need opcode to decide which way 'this' test goes 1503 int prev_op = prev_dom->Opcode(); 1504 Node *top = igvn->C->top(); // Shortcut to top 1505 1506 // Loop predicates may have depending checks which should not 1507 // be skipped. For example, range check predicate has two checks 1508 // for lower and upper bounds. 1509 ProjNode* unc_proj = proj_out(1 - prev_dom->as_Proj()->_con)->as_Proj(); 1510 if (unc_proj != NULL && 1511 (unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_predicate) != NULL || 1512 unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_profile_predicate) != NULL)) { 1513 prev_dom = idom; 1514 } 1515 1516 // Now walk the current IfNode's projections. 1517 // Loop ends when 'this' has no more uses. 1518 for (DUIterator_Last imin, i = last_outs(imin); i >= imin; --i) { 1519 Node *ifp = last_out(i); // Get IfTrue/IfFalse 1520 igvn->add_users_to_worklist(ifp); 1521 // Check which projection it is and set target. 1522 // Data-target is either the dominating projection of the same type 1523 // or TOP if the dominating projection is of opposite type. 1524 // Data-target will be used as the new control edge for the non-CFG 1525 // nodes like Casts and Loads. 1526 Node *data_target = (ifp->Opcode() == prev_op) ? prev_dom : top; 1527 // Control-target is just the If's immediate dominator or TOP. 1528 Node *ctrl_target = (ifp->Opcode() == prev_op) ? idom : top; 1529 1530 // For each child of an IfTrue/IfFalse projection, reroute. 1531 // Loop ends when projection has no more uses. 1532 for (DUIterator_Last jmin, j = ifp->last_outs(jmin); j >= jmin; --j) { 1533 Node* s = ifp->last_out(j); // Get child of IfTrue/IfFalse 1534 if( !s->depends_only_on_test() ) { 1535 // Find the control input matching this def-use edge. 1536 // For Regions it may not be in slot 0. 1537 uint l; 1538 for( l = 0; s->in(l) != ifp; l++ ) { } 1539 igvn->replace_input_of(s, l, ctrl_target); 1540 } else { // Else, for control producers, 1541 igvn->replace_input_of(s, 0, data_target); // Move child to data-target 1542 } 1543 } // End for each child of a projection 1544 1545 igvn->remove_dead_node(ifp); 1546 } // End for each IfTrue/IfFalse child of If 1547 1548 // Kill the IfNode 1549 igvn->remove_dead_node(this); 1550 1551 // Must return either the original node (now dead) or a new node 1552 // (Do not return a top here, since that would break the uniqueness of top.) 1553 return new ConINode(TypeInt::ZERO); 1554 } 1555 1556 Node* IfNode::search_identical(int dist) { 1557 // Setup to scan up the CFG looking for a dominating test 1558 Node* dom = in(0); 1559 Node* prev_dom = this; 1560 int op = Opcode(); 1561 #if INCLUDE_SHENANDOAHGC 1562 bool evac_in_progress = ShenandoahWriteBarrierNode::is_evacuation_in_progress_test(this); 1563 #endif 1564 // Search up the dominator tree for an If with an identical test 1565 while (dom->Opcode() != op || // Not same opcode? 1566 (dom->in(1) != in(1) SHENANDOAHGC_ONLY(&& (!evac_in_progress || !ShenandoahWriteBarrierNode::is_evacuation_in_progress_test(dom->as_If())))) || // Not same input 1? 1567 prev_dom->in(0) != dom) { // One path of test does not dominate? 1568 if (dist < 0) return NULL; 1569 1570 dist--; 1571 prev_dom = dom; 1572 dom = up_one_dom(dom); 1573 if (!dom) return NULL; 1574 } 1575 1576 // Check that we did not follow a loop back to ourselves 1577 if (this == dom) { 1578 return NULL; 1579 } 1580 1581 #ifndef PRODUCT 1582 if (dist > 2) { // Add to count of NULL checks elided 1583 explicit_null_checks_elided++; 1584 } 1585 #endif 1586 1587 return prev_dom; 1588 } 1589 1590 //------------------------------Identity--------------------------------------- 1591 // If the test is constant & we match, then we are the input Control 1592 Node* IfProjNode::Identity(PhaseGVN* phase) { 1593 // Can only optimize if cannot go the other way 1594 const TypeTuple *t = phase->type(in(0))->is_tuple(); 1595 if (t == TypeTuple::IFNEITHER || (always_taken(t) && 1596 // During parsing (GVN) we don't remove dead code aggressively. 1597 // Cut off dead branch and let PhaseRemoveUseless take care of it. 1598 (!phase->is_IterGVN() || 1599 // During IGVN, first wait for the dead branch to be killed. 1600 // Otherwise, the IfNode's control will have two control uses (the IfNode 1601 // that doesn't go away because it still has uses and this branch of the 1602 // If) which breaks other optimizations. Node::has_special_unique_user() 1603 // will cause this node to be reprocessed once the dead branch is killed. 1604 in(0)->outcnt() == 1))) { 1605 // IfNode control 1606 return in(0)->in(0); 1607 } 1608 // no progress 1609 return this; 1610 } 1611 1612 #ifndef PRODUCT 1613 //-------------------------------related--------------------------------------- 1614 // An IfProjNode's related node set consists of its input (an IfNode) including 1615 // the IfNode's condition, plus all of its outputs at level 1. In compact mode, 1616 // the restrictions for IfNode apply (see IfNode::rel). 1617 void IfProjNode::related(GrowableArray<Node*> *in_rel, GrowableArray<Node*> *out_rel, bool compact) const { 1618 Node* ifNode = this->in(0); 1619 in_rel->append(ifNode); 1620 if (compact) { 1621 ifNode->collect_nodes(in_rel, 3, false, true); 1622 } else { 1623 ifNode->collect_nodes_in_all_data(in_rel, false); 1624 } 1625 this->collect_nodes(out_rel, -1, false, false); 1626 } 1627 1628 //------------------------------dump_spec-------------------------------------- 1629 void IfNode::dump_spec(outputStream *st) const { 1630 st->print("P=%f, C=%f",_prob,_fcnt); 1631 } 1632 1633 //-------------------------------related--------------------------------------- 1634 // For an IfNode, the set of related output nodes is just the output nodes till 1635 // depth 2, i.e, the IfTrue/IfFalse projection nodes plus the nodes they refer. 1636 // The related input nodes contain no control nodes, but all data nodes 1637 // pertaining to the condition. In compact mode, the input nodes are collected 1638 // up to a depth of 3. 1639 void IfNode::related(GrowableArray <Node *> *in_rel, GrowableArray <Node *> *out_rel, bool compact) const { 1640 if (compact) { 1641 this->collect_nodes(in_rel, 3, false, true); 1642 } else { 1643 this->collect_nodes_in_all_data(in_rel, false); 1644 } 1645 this->collect_nodes(out_rel, -2, false, false); 1646 } 1647 #endif 1648 1649 //------------------------------idealize_test---------------------------------- 1650 // Try to canonicalize tests better. Peek at the Cmp/Bool/If sequence and 1651 // come up with a canonical sequence. Bools getting 'eq', 'gt' and 'ge' forms 1652 // converted to 'ne', 'le' and 'lt' forms. IfTrue/IfFalse get swapped as 1653 // needed. 1654 static IfNode* idealize_test(PhaseGVN* phase, IfNode* iff) { 1655 assert(iff->in(0) != NULL, "If must be live"); 1656 1657 if (iff->outcnt() != 2) return NULL; // Malformed projections. 1658 Node* old_if_f = iff->proj_out(false); 1659 Node* old_if_t = iff->proj_out(true); 1660 1661 // CountedLoopEnds want the back-control test to be TRUE, irregardless of 1662 // whether they are testing a 'gt' or 'lt' condition. The 'gt' condition 1663 // happens in count-down loops 1664 if (iff->is_CountedLoopEnd()) return NULL; 1665 if (!iff->in(1)->is_Bool()) return NULL; // Happens for partially optimized IF tests 1666 BoolNode *b = iff->in(1)->as_Bool(); 1667 BoolTest bt = b->_test; 1668 // Test already in good order? 1669 if( bt.is_canonical() ) 1670 return NULL; 1671 1672 // Flip test to be canonical. Requires flipping the IfFalse/IfTrue and 1673 // cloning the IfNode. 1674 Node* new_b = phase->transform( new BoolNode(b->in(1), bt.negate()) ); 1675 if( !new_b->is_Bool() ) return NULL; 1676 b = new_b->as_Bool(); 1677 1678 PhaseIterGVN *igvn = phase->is_IterGVN(); 1679 assert( igvn, "Test is not canonical in parser?" ); 1680 1681 // The IF node never really changes, but it needs to be cloned 1682 iff = iff->clone()->as_If(); 1683 iff->set_req(1, b); 1684 iff->_prob = 1.0-iff->_prob; 1685 1686 Node *prior = igvn->hash_find_insert(iff); 1687 if( prior ) { 1688 igvn->remove_dead_node(iff); 1689 iff = (IfNode*)prior; 1690 } else { 1691 // Cannot call transform on it just yet 1692 igvn->set_type_bottom(iff); 1693 } 1694 igvn->_worklist.push(iff); 1695 1696 // Now handle projections. Cloning not required. 1697 Node* new_if_f = (Node*)(new IfFalseNode( iff )); 1698 Node* new_if_t = (Node*)(new IfTrueNode ( iff )); 1699 1700 igvn->register_new_node_with_optimizer(new_if_f); 1701 igvn->register_new_node_with_optimizer(new_if_t); 1702 // Flip test, so flip trailing control 1703 igvn->replace_node(old_if_f, new_if_t); 1704 igvn->replace_node(old_if_t, new_if_f); 1705 1706 // Progress 1707 return iff; 1708 } 1709 1710 bool IfNode::is_g1_marking_if(PhaseTransform *phase) const { 1711 if (Opcode() != Op_If) { 1712 return false; 1713 } 1714 1715 Node* bol = in(1); 1716 assert(bol->is_Bool(), ""); 1717 Node* cmpx = bol->in(1); 1718 if (bol->as_Bool()->_test._test == BoolTest::ne && 1719 cmpx->is_Cmp() && cmpx->in(2) == phase->intcon(0) && 1720 cmpx->in(1)->is_g1_marking_load()) { 1721 return true; 1722 } 1723 return false; 1724 } 1725 1726 #if INCLUDE_SHENANDOAHGC 1727 bool IfNode::is_shenandoah_marking_if(PhaseTransform *phase) const { 1728 if (!UseShenandoahGC) { 1729 return false; 1730 } 1731 1732 if (Opcode() != Op_If) { 1733 return false; 1734 } 1735 1736 Node* bol = in(1); 1737 assert(bol->is_Bool(), ""); 1738 Node* cmpx = bol->in(1); 1739 if (bol->as_Bool()->_test._test == BoolTest::ne && 1740 cmpx->is_Cmp() && cmpx->in(2) == phase->intcon(0) && 1741 cmpx->in(1)->in(1)->is_shenandoah_state_load() && 1742 cmpx->in(1)->in(2)->is_Con() && 1743 cmpx->in(1)->in(2) == phase->intcon(ShenandoahHeap::MARKING)) { 1744 return true; 1745 } 1746 1747 return false; 1748 } 1749 #endif 1750 1751 1752 Node* RangeCheckNode::Ideal(PhaseGVN *phase, bool can_reshape) { 1753 Node* res = Ideal_common(phase, can_reshape); 1754 if (res != NodeSentinel) { 1755 return res; 1756 } 1757 1758 PhaseIterGVN *igvn = phase->is_IterGVN(); 1759 // Setup to scan up the CFG looking for a dominating test 1760 Node* prev_dom = this; 1761 1762 // Check for range-check vs other kinds of tests 1763 Node* index1; 1764 Node* range1; 1765 jint offset1; 1766 int flip1 = is_range_check(range1, index1, offset1); 1767 if (flip1) { 1768 Node* dom = in(0); 1769 // Try to remove extra range checks. All 'up_one_dom' gives up at merges 1770 // so all checks we inspect post-dominate the top-most check we find. 1771 // If we are going to fail the current check and we reach the top check 1772 // then we are guaranteed to fail, so just start interpreting there. 1773 // We 'expand' the top 3 range checks to include all post-dominating 1774 // checks. 1775 1776 // The top 3 range checks seen 1777 const int NRC =3; 1778 RangeCheck prev_checks[NRC]; 1779 int nb_checks = 0; 1780 1781 // Low and high offsets seen so far 1782 jint off_lo = offset1; 1783 jint off_hi = offset1; 1784 1785 bool found_immediate_dominator = false; 1786 1787 // Scan for the top checks and collect range of offsets 1788 for (int dist = 0; dist < 999; dist++) { // Range-Check scan limit 1789 if (dom->Opcode() == Op_RangeCheck && // Not same opcode? 1790 prev_dom->in(0) == dom) { // One path of test does dominate? 1791 if (dom == this) return NULL; // dead loop 1792 // See if this is a range check 1793 Node* index2; 1794 Node* range2; 1795 jint offset2; 1796 int flip2 = dom->as_RangeCheck()->is_range_check(range2, index2, offset2); 1797 // See if this is a _matching_ range check, checking against 1798 // the same array bounds. 1799 if (flip2 == flip1 && range2 == range1 && index2 == index1 && 1800 dom->outcnt() == 2) { 1801 if (nb_checks == 0 && dom->in(1) == in(1)) { 1802 // Found an immediately dominating test at the same offset. 1803 // This kind of back-to-back test can be eliminated locally, 1804 // and there is no need to search further for dominating tests. 1805 assert(offset2 == offset1, "Same test but different offsets"); 1806 found_immediate_dominator = true; 1807 break; 1808 } 1809 // Gather expanded bounds 1810 off_lo = MIN2(off_lo,offset2); 1811 off_hi = MAX2(off_hi,offset2); 1812 // Record top NRC range checks 1813 prev_checks[nb_checks%NRC].ctl = prev_dom; 1814 prev_checks[nb_checks%NRC].off = offset2; 1815 nb_checks++; 1816 } 1817 } 1818 prev_dom = dom; 1819 dom = up_one_dom(dom); 1820 if (!dom) break; 1821 } 1822 1823 if (!found_immediate_dominator) { 1824 // Attempt to widen the dominating range check to cover some later 1825 // ones. Since range checks "fail" by uncommon-trapping to the 1826 // interpreter, widening a check can make us speculatively enter 1827 // the interpreter. If we see range-check deopt's, do not widen! 1828 if (!phase->C->allow_range_check_smearing()) return NULL; 1829 1830 // Didn't find prior covering check, so cannot remove anything. 1831 if (nb_checks == 0) { 1832 return NULL; 1833 } 1834 // Constant indices only need to check the upper bound. 1835 // Non-constant indices must check both low and high. 1836 int chk0 = (nb_checks - 1) % NRC; 1837 if (index1) { 1838 if (nb_checks == 1) { 1839 return NULL; 1840 } else { 1841 // If the top range check's constant is the min or max of 1842 // all constants we widen the next one to cover the whole 1843 // range of constants. 1844 RangeCheck rc0 = prev_checks[chk0]; 1845 int chk1 = (nb_checks - 2) % NRC; 1846 RangeCheck rc1 = prev_checks[chk1]; 1847 if (rc0.off == off_lo) { 1848 adjust_check(rc1.ctl, range1, index1, flip1, off_hi, igvn); 1849 prev_dom = rc1.ctl; 1850 } else if (rc0.off == off_hi) { 1851 adjust_check(rc1.ctl, range1, index1, flip1, off_lo, igvn); 1852 prev_dom = rc1.ctl; 1853 } else { 1854 // If the top test's constant is not the min or max of all 1855 // constants, we need 3 range checks. We must leave the 1856 // top test unchanged because widening it would allow the 1857 // accesses it protects to successfully read/write out of 1858 // bounds. 1859 if (nb_checks == 2) { 1860 return NULL; 1861 } 1862 int chk2 = (nb_checks - 3) % NRC; 1863 RangeCheck rc2 = prev_checks[chk2]; 1864 // The top range check a+i covers interval: -a <= i < length-a 1865 // The second range check b+i covers interval: -b <= i < length-b 1866 if (rc1.off <= rc0.off) { 1867 // if b <= a, we change the second range check to: 1868 // -min_of_all_constants <= i < length-min_of_all_constants 1869 // Together top and second range checks now cover: 1870 // -min_of_all_constants <= i < length-a 1871 // which is more restrictive than -b <= i < length-b: 1872 // -b <= -min_of_all_constants <= i < length-a <= length-b 1873 // The third check is then changed to: 1874 // -max_of_all_constants <= i < length-max_of_all_constants 1875 // so 2nd and 3rd checks restrict allowed values of i to: 1876 // -min_of_all_constants <= i < length-max_of_all_constants 1877 adjust_check(rc1.ctl, range1, index1, flip1, off_lo, igvn); 1878 adjust_check(rc2.ctl, range1, index1, flip1, off_hi, igvn); 1879 } else { 1880 // if b > a, we change the second range check to: 1881 // -max_of_all_constants <= i < length-max_of_all_constants 1882 // Together top and second range checks now cover: 1883 // -a <= i < length-max_of_all_constants 1884 // which is more restrictive than -b <= i < length-b: 1885 // -b < -a <= i < length-max_of_all_constants <= length-b 1886 // The third check is then changed to: 1887 // -max_of_all_constants <= i < length-max_of_all_constants 1888 // so 2nd and 3rd checks restrict allowed values of i to: 1889 // -min_of_all_constants <= i < length-max_of_all_constants 1890 adjust_check(rc1.ctl, range1, index1, flip1, off_hi, igvn); 1891 adjust_check(rc2.ctl, range1, index1, flip1, off_lo, igvn); 1892 } 1893 prev_dom = rc2.ctl; 1894 } 1895 } 1896 } else { 1897 RangeCheck rc0 = prev_checks[chk0]; 1898 // 'Widen' the offset of the 1st and only covering check 1899 adjust_check(rc0.ctl, range1, index1, flip1, off_hi, igvn); 1900 // Test is now covered by prior checks, dominate it out 1901 prev_dom = rc0.ctl; 1902 } 1903 } 1904 } else { 1905 prev_dom = search_identical(4); 1906 1907 if (prev_dom == NULL) { 1908 return NULL; 1909 } 1910 } 1911 1912 // Replace dominated IfNode 1913 return dominated_by(prev_dom, igvn); 1914 }