1/* 2 * Copyright (c) 2012, 2016, 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 "c1/c1_ValueStack.hpp" 27#include "c1/c1_RangeCheckElimination.hpp" 28#include "c1/c1_IR.hpp" 29#include "c1/c1_Canonicalizer.hpp" 30#include "c1/c1_ValueMap.hpp" 31#include "ci/ciMethodData.hpp" 32#include "runtime/deoptimization.hpp" 33 34// Macros for the Trace and the Assertion flag 35#ifdef ASSERT 36#define TRACE_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination) { code; } 37#define ASSERT_RANGE_CHECK_ELIMINATION(code) if (AssertRangeCheckElimination) { code; } 38#define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination || AssertRangeCheckElimination) { code; } 39#else 40#define TRACE_RANGE_CHECK_ELIMINATION(code) 41#define ASSERT_RANGE_CHECK_ELIMINATION(code) 42#define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code) 43#endif 44 45// Entry point for the optimization 46void RangeCheckElimination::eliminate(IR *ir) { 47 bool do_elimination = ir->compilation()->has_access_indexed(); 48 ASSERT_RANGE_CHECK_ELIMINATION(do_elimination = true); 49 if (do_elimination) { 50 RangeCheckEliminator rce(ir); 51 } 52} 53 54// Constructor 55RangeCheckEliminator::RangeCheckEliminator(IR *ir) : 56 _bounds(Instruction::number_of_instructions(), Instruction::number_of_instructions(), NULL), 57 _access_indexed_info(Instruction::number_of_instructions(), Instruction::number_of_instructions(), NULL) 58{ 59 _visitor.set_range_check_eliminator(this); 60 _ir = ir; 61 _number_of_instructions = Instruction::number_of_instructions(); 62 _optimistic = ir->compilation()->is_optimistic(); 63 64 TRACE_RANGE_CHECK_ELIMINATION( 65 tty->cr(); 66 tty->print_cr("Range check elimination"); 67 ir->method()->print_name(tty); 68 tty->cr(); 69 ); 70 71 TRACE_RANGE_CHECK_ELIMINATION( 72 tty->print_cr("optimistic=%d", (int)_optimistic); 73 ); 74 75#ifdef ASSERT 76 // Verifies several conditions that must be true on the IR-input. Only used for debugging purposes. 77 TRACE_RANGE_CHECK_ELIMINATION( 78 tty->print_cr("Verification of IR . . ."); 79 ); 80 Verification verification(ir); 81#endif 82 83 // Set process block flags 84 // Optimization so a blocks is only processed if it contains an access indexed instruction or if 85 // one of its children in the dominator tree contains an access indexed instruction. 86 set_process_block_flags(ir->start()); 87 88 // Pass over instructions in the dominator tree 89 TRACE_RANGE_CHECK_ELIMINATION( 90 tty->print_cr("Starting pass over dominator tree . . .") 91 ); 92 calc_bounds(ir->start(), NULL); 93 94 TRACE_RANGE_CHECK_ELIMINATION( 95 tty->print_cr("Finished!") 96 ); 97} 98 99// Instruction specific work for some instructions 100// Constant 101void RangeCheckEliminator::Visitor::do_Constant(Constant *c) { 102 IntConstant *ic = c->type()->as_IntConstant(); 103 if (ic != NULL) { 104 int value = ic->value(); 105 _bound = new Bound(value, NULL, value, NULL); 106 } 107} 108 109// LogicOp 110void RangeCheckEliminator::Visitor::do_LogicOp(LogicOp *lo) { 111 if (lo->type()->as_IntType() && lo->op() == Bytecodes::_iand && (lo->x()->as_Constant() || lo->y()->as_Constant())) { 112 int constant = 0; 113 Constant *c = lo->x()->as_Constant(); 114 if (c != NULL) { 115 constant = c->type()->as_IntConstant()->value(); 116 } else { 117 constant = lo->y()->as_Constant()->type()->as_IntConstant()->value(); 118 } 119 if (constant >= 0) { 120 _bound = new Bound(0, NULL, constant, NULL); 121 } 122 } 123} 124 125// Phi 126void RangeCheckEliminator::Visitor::do_Phi(Phi *phi) { 127 if (!phi->type()->as_IntType() && !phi->type()->as_ObjectType()) return; 128 129 BlockBegin *block = phi->block(); 130 int op_count = phi->operand_count(); 131 bool has_upper = true; 132 bool has_lower = true; 133 assert(phi, "Phi must not be null"); 134 Bound *bound = NULL; 135 136 // TODO: support more difficult phis 137 for (int i=0; i<op_count; i++) { 138 Value v = phi->operand_at(i); 139 140 if (v == phi) continue; 141 142 // Check if instruction is connected with phi itself 143 Op2 *op2 = v->as_Op2(); 144 if (op2 != NULL) { 145 Value x = op2->x(); 146 Value y = op2->y(); 147 if ((x == phi || y == phi)) { 148 Value other = x; 149 if (other == phi) { 150 other = y; 151 } 152 ArithmeticOp *ao = v->as_ArithmeticOp(); 153 if (ao != NULL && ao->op() == Bytecodes::_iadd) { 154 assert(ao->op() == Bytecodes::_iadd, "Has to be add!"); 155 if (ao->type()->as_IntType()) { 156 Constant *c = other->as_Constant(); 157 if (c != NULL) { 158 assert(c->type()->as_IntConstant(), "Constant has to be of type integer"); 159 int value = c->type()->as_IntConstant()->value(); 160 if (value == 1) { 161 has_upper = false; 162 } else if (value > 1) { 163 // Overflow not guaranteed 164 has_upper = false; 165 has_lower = false; 166 } else if (value < 0) { 167 has_lower = false; 168 } 169 continue; 170 } 171 } 172 } 173 } 174 } 175 176 // No connection -> new bound 177 Bound *v_bound = _rce->get_bound(v); 178 Bound *cur_bound; 179 int cur_constant = 0; 180 Value cur_value = v; 181 182 if (v->type()->as_IntConstant()) { 183 cur_constant = v->type()->as_IntConstant()->value(); 184 cur_value = NULL; 185 } 186 if (!v_bound->has_upper() || !v_bound->has_lower()) { 187 cur_bound = new Bound(cur_constant, cur_value, cur_constant, cur_value); 188 } else { 189 cur_bound = v_bound; 190 } 191 if (cur_bound) { 192 if (!bound) { 193 bound = cur_bound->copy(); 194 } else { 195 bound->or_op(cur_bound); 196 } 197 } else { 198 // No bound! 199 bound = NULL; 200 break; 201 } 202 } 203 204 if (bound) { 205 if (!has_upper) { 206 bound->remove_upper(); 207 } 208 if (!has_lower) { 209 bound->remove_lower(); 210 } 211 _bound = bound; 212 } else { 213 _bound = new Bound(); 214 } 215} 216 217 218// ArithmeticOp 219void RangeCheckEliminator::Visitor::do_ArithmeticOp(ArithmeticOp *ao) { 220 Value x = ao->x(); 221 Value y = ao->y(); 222 223 if (ao->op() == Bytecodes::_irem) { 224 Bound* x_bound = _rce->get_bound(x); 225 Bound* y_bound = _rce->get_bound(y); 226 if (x_bound->lower() >= 0 && x_bound->lower_instr() == NULL && y->as_ArrayLength() != NULL) { 227 _bound = new Bound(0, NULL, -1, y); 228 } else { 229 _bound = new Bound(); 230 } 231 } else if (!x->as_Constant() || !y->as_Constant()) { 232 assert(!x->as_Constant() || !y->as_Constant(), "One of the operands must be non-constant!"); 233 if (((x->as_Constant() || y->as_Constant()) && (ao->op() == Bytecodes::_iadd)) || (y->as_Constant() && ao->op() == Bytecodes::_isub)) { 234 assert(ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub, "Operand must be iadd or isub"); 235 236 if (y->as_Constant()) { 237 Value tmp = x; 238 x = y; 239 y = tmp; 240 } 241 assert(x->as_Constant()->type()->as_IntConstant(), "Constant must be int constant!"); 242 243 // Constant now in x 244 int const_value = x->as_Constant()->type()->as_IntConstant()->value(); 245 if (ao->op() == Bytecodes::_iadd || const_value != min_jint) { 246 if (ao->op() == Bytecodes::_isub) { 247 const_value = -const_value; 248 } 249 250 Bound * bound = _rce->get_bound(y); 251 if (bound->has_upper() && bound->has_lower()) { 252 int new_lower = bound->lower() + const_value; 253 jlong new_lowerl = ((jlong)bound->lower()) + const_value; 254 int new_upper = bound->upper() + const_value; 255 jlong new_upperl = ((jlong)bound->upper()) + const_value; 256 257 if (((jlong)new_lower) == new_lowerl && ((jlong)new_upper == new_upperl)) { 258 Bound *newBound = new Bound(new_lower, bound->lower_instr(), new_upper, bound->upper_instr()); 259 _bound = newBound; 260 } else { 261 // overflow 262 _bound = new Bound(); 263 } 264 } else { 265 _bound = new Bound(); 266 } 267 } else { 268 _bound = new Bound(); 269 } 270 } else { 271 Bound *bound = _rce->get_bound(x); 272 if (ao->op() == Bytecodes::_isub) { 273 if (bound->lower_instr() == y) { 274 _bound = new Bound(Instruction::geq, NULL, bound->lower()); 275 } else { 276 _bound = new Bound(); 277 } 278 } else { 279 _bound = new Bound(); 280 } 281 } 282 } 283} 284 285// IfOp 286void RangeCheckEliminator::Visitor::do_IfOp(IfOp *ifOp) 287{ 288 if (ifOp->tval()->type()->as_IntConstant() && ifOp->fval()->type()->as_IntConstant()) { 289 int min = ifOp->tval()->type()->as_IntConstant()->value(); 290 int max = ifOp->fval()->type()->as_IntConstant()->value(); 291 if (min > max) { 292 // min ^= max ^= min ^= max; 293 int tmp = min; 294 min = max; 295 max = tmp; 296 } 297 _bound = new Bound(min, NULL, max, NULL); 298 } 299} 300 301// Get bound. Returns the current bound on Value v. Normally this is the topmost element on the bound stack. 302RangeCheckEliminator::Bound *RangeCheckEliminator::get_bound(Value v) { 303 // Wrong type or NULL -> No bound 304 if (!v || (!v->type()->as_IntType() && !v->type()->as_ObjectType())) return NULL; 305 306 if (!_bounds.at(v->id())) { 307 // First (default) bound is calculated 308 // Create BoundStack 309 _bounds.at_put(v->id(), new BoundStack()); 310 _visitor.clear_bound(); 311 Value visit_value = v; 312 visit_value->visit(&_visitor); 313 Bound *bound = _visitor.bound(); 314 if (bound) { 315 _bounds.at(v->id())->push(bound); 316 } 317 if (_bounds.at(v->id())->length() == 0) { 318 assert(!(v->as_Constant() && v->type()->as_IntConstant()), "constants not handled here"); 319 _bounds.at(v->id())->push(new Bound()); 320 } 321 } else if (_bounds.at(v->id())->length() == 0) { 322 // To avoid endless loops, bound is currently in calculation -> nothing known about it 323 return new Bound(); 324 } 325 326 // Return bound 327 return _bounds.at(v->id())->top(); 328} 329 330// Update bound 331void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Instruction::Condition cond, Value value, int constant) { 332 if (cond == Instruction::gtr) { 333 cond = Instruction::geq; 334 constant++; 335 } else if (cond == Instruction::lss) { 336 cond = Instruction::leq; 337 constant--; 338 } 339 Bound *bound = new Bound(cond, value, constant); 340 update_bound(pushed, v, bound); 341} 342 343// Checks for loop invariance. Returns true if the instruction is outside of the loop which is identified by loop_header. 344bool RangeCheckEliminator::loop_invariant(BlockBegin *loop_header, Instruction *instruction) { 345 assert(loop_header, "Loop header must not be null!"); 346 if (!instruction) return true; 347 return instruction->dominator_depth() < loop_header->dominator_depth(); 348} 349 350// Update bound. Pushes a new bound onto the stack. Tries to do a conjunction with the current bound. 351void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Bound *bound) { 352 if (v->as_Constant()) { 353 // No bound update for constants 354 return; 355 } 356 if (!_bounds.at(v->id())) { 357 get_bound(v); 358 assert(_bounds.at(v->id()), "Now Stack must exist"); 359 } 360 Bound *top = NULL; 361 if (_bounds.at(v->id())->length() > 0) { 362 top = _bounds.at(v->id())->top(); 363 } 364 if (top) { 365 bound->and_op(top); 366 } 367 _bounds.at(v->id())->push(bound); 368 pushed.append(v->id()); 369} 370 371// Add instruction + idx for in block motion 372void RangeCheckEliminator::add_access_indexed_info(InstructionList &indices, int idx, Value instruction, AccessIndexed *ai) { 373 int id = instruction->id(); 374 AccessIndexedInfo *aii = _access_indexed_info.at(id); 375 if (aii == NULL) { 376 aii = new AccessIndexedInfo(); 377 _access_indexed_info.at_put(id, aii); 378 indices.append(instruction); 379 aii->_min = idx; 380 aii->_max = idx; 381 aii->_list = new AccessIndexedList(); 382 } else if (idx >= aii->_min && idx <= aii->_max) { 383 remove_range_check(ai); 384 return; 385 } 386 aii->_min = MIN2(aii->_min, idx); 387 aii->_max = MAX2(aii->_max, idx); 388 aii->_list->append(ai); 389} 390 391// In block motion. Tries to reorder checks in order to reduce some of them. 392// Example: 393// a[i] = 0; 394// a[i+2] = 0; 395// a[i+1] = 0; 396// In this example the check for a[i+1] would be considered as unnecessary during the first iteration. 397// After this i is only checked once for i >= 0 and i+2 < a.length before the first array access. If this 398// check fails, deoptimization is called. 399void RangeCheckEliminator::in_block_motion(BlockBegin *block, AccessIndexedList &accessIndexed, InstructionList &arrays) { 400 InstructionList indices; 401 402 // Now iterate over all arrays 403 for (int i=0; i<arrays.length(); i++) { 404 int max_constant = -1; 405 AccessIndexedList list_constant; 406 Value array = arrays.at(i); 407 408 // For all AccessIndexed-instructions in this block concerning the current array. 409 for(int j=0; j<accessIndexed.length(); j++) { 410 AccessIndexed *ai = accessIndexed.at(j); 411 if (ai->array() != array || !ai->check_flag(Instruction::NeedsRangeCheckFlag)) continue; 412 413 Value index = ai->index(); 414 Constant *c = index->as_Constant(); 415 if (c != NULL) { 416 int constant_value = c->type()->as_IntConstant()->value(); 417 if (constant_value >= 0) { 418 if (constant_value <= max_constant) { 419 // No range check needed for this 420 remove_range_check(ai); 421 } else { 422 max_constant = constant_value; 423 list_constant.append(ai); 424 } 425 } 426 } else { 427 int last_integer = 0; 428 Instruction *last_instruction = index; 429 int base = 0; 430 ArithmeticOp *ao = index->as_ArithmeticOp(); 431 432 while (ao != NULL && (ao->x()->as_Constant() || ao->y()->as_Constant()) && (ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub)) { 433 c = ao->y()->as_Constant(); 434 Instruction *other = ao->x(); 435 if (!c && ao->op() == Bytecodes::_iadd) { 436 c = ao->x()->as_Constant(); 437 other = ao->y(); 438 } 439 440 if (c) { 441 int value = c->type()->as_IntConstant()->value(); 442 if (value != min_jint) { 443 if (ao->op() == Bytecodes::_isub) { 444 value = -value; 445 } 446 base += value; 447 last_integer = base; 448 last_instruction = other; 449 } 450 index = other; 451 } else { 452 break; 453 } 454 ao = index->as_ArithmeticOp(); 455 } 456 add_access_indexed_info(indices, last_integer, last_instruction, ai); 457 } 458 } 459 460 // Iterate over all different indices 461 if (_optimistic) { 462 for (int i = 0; i < indices.length(); i++) { 463 Instruction *index_instruction = indices.at(i); 464 AccessIndexedInfo *info = _access_indexed_info.at(index_instruction->id()); 465 assert(info != NULL, "Info must not be null"); 466 467 // if idx < 0, max > 0, max + idx may fall between 0 and 468 // length-1 and if min < 0, min + idx may overflow and be >= 469 // 0. The predicate wouldn't trigger but some accesses could 470 // be with a negative index. This test guarantees that for the 471 // min and max value that are kept the predicate can't let 472 // some incorrect accesses happen. 473 bool range_cond = (info->_max < 0 || info->_max + min_jint <= info->_min); 474 475 // Generate code only if more than 2 range checks can be eliminated because of that. 476 // 2 because at least 2 comparisons are done 477 if (info->_list->length() > 2 && range_cond) { 478 AccessIndexed *first = info->_list->at(0); 479 Instruction *insert_position = first->prev(); 480 assert(insert_position->next() == first, "prev was calculated"); 481 ValueStack *state = first->state_before(); 482 483 // Load min Constant 484 Constant *min_constant = NULL; 485 if (info->_min != 0) { 486 min_constant = new Constant(new IntConstant(info->_min)); 487 NOT_PRODUCT(min_constant->set_printable_bci(first->printable_bci())); 488 insert_position = insert_position->insert_after(min_constant); 489 } 490 491 // Load max Constant 492 Constant *max_constant = NULL; 493 if (info->_max != 0) { 494 max_constant = new Constant(new IntConstant(info->_max)); 495 NOT_PRODUCT(max_constant->set_printable_bci(first->printable_bci())); 496 insert_position = insert_position->insert_after(max_constant); 497 } 498 499 // Load array length 500 Value length_instr = first->length(); 501 if (!length_instr) { 502 ArrayLength *length = new ArrayLength(array, first->state_before()->copy()); 503 length->set_exception_state(length->state_before()); 504 length->set_flag(Instruction::DeoptimizeOnException, true); 505 insert_position = insert_position->insert_after_same_bci(length); 506 length_instr = length; 507 } 508 509 // Calculate lower bound 510 Instruction *lower_compare = index_instruction; 511 if (min_constant) { 512 ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, min_constant, lower_compare, false, NULL); 513 insert_position = insert_position->insert_after_same_bci(ao); 514 lower_compare = ao; 515 } 516 517 // Calculate upper bound 518 Instruction *upper_compare = index_instruction; 519 if (max_constant) { 520 ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, max_constant, upper_compare, false, NULL); 521 insert_position = insert_position->insert_after_same_bci(ao); 522 upper_compare = ao; 523 } 524 525 // Trick with unsigned compare is done 526 int bci = NOT_PRODUCT(first->printable_bci()) PRODUCT_ONLY(-1); 527 insert_position = predicate(upper_compare, Instruction::aeq, length_instr, state, insert_position, bci); 528 insert_position = predicate_cmp_with_const(lower_compare, Instruction::leq, -1, state, insert_position); 529 for (int j = 0; j<info->_list->length(); j++) { 530 AccessIndexed *ai = info->_list->at(j); 531 remove_range_check(ai); 532 } 533 } 534 } 535 536 if (list_constant.length() > 1) { 537 AccessIndexed *first = list_constant.at(0); 538 Instruction *insert_position = first->prev(); 539 ValueStack *state = first->state_before(); 540 // Load max Constant 541 Constant *constant = new Constant(new IntConstant(max_constant)); 542 NOT_PRODUCT(constant->set_printable_bci(first->printable_bci())); 543 insert_position = insert_position->insert_after(constant); 544 Instruction *compare_instr = constant; 545 Value length_instr = first->length(); 546 if (!length_instr) { 547 ArrayLength *length = new ArrayLength(array, state->copy()); 548 length->set_exception_state(length->state_before()); 549 length->set_flag(Instruction::DeoptimizeOnException, true); 550 insert_position = insert_position->insert_after_same_bci(length); 551 length_instr = length; 552 } 553 // Compare for greater or equal to array length 554 insert_position = predicate(compare_instr, Instruction::geq, length_instr, state, insert_position); 555 for (int j = 0; j<list_constant.length(); j++) { 556 AccessIndexed *ai = list_constant.at(j); 557 remove_range_check(ai); 558 } 559 } 560 } 561 562 // Clear data structures for next array 563 for (int i = 0; i < indices.length(); i++) { 564 Instruction *index_instruction = indices.at(i); 565 _access_indexed_info.at_put(index_instruction->id(), NULL); 566 } 567 indices.clear(); 568 } 569} 570 571bool RangeCheckEliminator::set_process_block_flags(BlockBegin *block) { 572 Instruction *cur = block; 573 bool process = false; 574 575 while (cur) { 576 process |= (cur->as_AccessIndexed() != NULL); 577 cur = cur->next(); 578 } 579 580 BlockList *dominates = block->dominates(); 581 for (int i=0; i<dominates->length(); i++) { 582 BlockBegin *next = dominates->at(i); 583 process |= set_process_block_flags(next); 584 } 585 586 if (!process) { 587 block->set(BlockBegin::donot_eliminate_range_checks); 588 } 589 return process; 590} 591 592bool RangeCheckEliminator::is_ok_for_deoptimization(Instruction *insert_position, Instruction *array_instr, Instruction *length_instr, Instruction *lower_instr, int lower, Instruction *upper_instr, int upper) { 593 bool upper_check = true; 594 assert(lower_instr || lower >= 0, "If no lower_instr present, lower must be greater 0"); 595 assert(!lower_instr || lower_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller"); 596 assert(!upper_instr || upper_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller"); 597 assert(array_instr, "Array instruction must exist"); 598 assert(array_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller"); 599 assert(!length_instr || length_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller"); 600 601 if (upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr) { 602 // static check 603 if (upper >= 0) return false; // would always trigger a deopt: 604 // array_length + x >= array_length, x >= 0 is always true 605 upper_check = false; 606 } 607 if (lower_instr && lower_instr->as_ArrayLength() && lower_instr->as_ArrayLength()->array() == array_instr) { 608 if (lower > 0) return false; 609 } 610 // No upper check required -> skip 611 if (upper_check && upper_instr && upper_instr->type()->as_ObjectType() && upper_instr == array_instr) { 612 // upper_instr is object means that the upper bound is the length 613 // of the upper_instr. 614 return false; 615 } 616 return true; 617} 618 619Instruction* RangeCheckEliminator::insert_after(Instruction* insert_position, Instruction* instr, int bci) { 620 if (bci != -1) { 621 NOT_PRODUCT(instr->set_printable_bci(bci)); 622 return insert_position->insert_after(instr); 623 } else { 624 return insert_position->insert_after_same_bci(instr); 625 } 626} 627 628Instruction* RangeCheckEliminator::predicate(Instruction* left, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) { 629 RangeCheckPredicate *deoptimize = new RangeCheckPredicate(left, cond, true, right, state->copy()); 630 return insert_after(insert_position, deoptimize, bci); 631} 632 633Instruction* RangeCheckEliminator::predicate_cmp_with_const(Instruction* instr, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) { 634 Constant *const_instr = new Constant(new IntConstant(constant)); 635 insert_position = insert_after(insert_position, const_instr, bci); 636 return predicate(instr, cond, const_instr, state, insert_position); 637} 638 639Instruction* RangeCheckEliminator::predicate_add(Instruction* left, int left_const, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) { 640 Constant *constant = new Constant(new IntConstant(left_const)); 641 insert_position = insert_after(insert_position, constant, bci); 642 ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, left, false, NULL); 643 insert_position = insert_position->insert_after_same_bci(ao); 644 return predicate(ao, cond, right, state, insert_position); 645} 646 647Instruction* RangeCheckEliminator::predicate_add_cmp_with_const(Instruction* left, int left_const, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) { 648 Constant *const_instr = new Constant(new IntConstant(constant)); 649 insert_position = insert_after(insert_position, const_instr, bci); 650 return predicate_add(left, left_const, cond, const_instr, state, insert_position); 651} 652 653// Insert deoptimization 654void RangeCheckEliminator::insert_deoptimization(ValueStack *state, Instruction *insert_position, Instruction *array_instr, Instruction *length_instr, Instruction *lower_instr, int lower, Instruction *upper_instr, int upper, AccessIndexed *ai) { 655 assert(is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, lower, upper_instr, upper), "should have been tested before"); 656 bool upper_check = !(upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr); 657 658 int bci = NOT_PRODUCT(ai->printable_bci()) PRODUCT_ONLY(-1); 659 if (lower_instr) { 660 assert(!lower_instr->type()->as_ObjectType(), "Must not be object type"); 661 if (lower == 0) { 662 // Compare for less than 0 663 insert_position = predicate_cmp_with_const(lower_instr, Instruction::lss, 0, state, insert_position, bci); 664 } else if (lower > 0) { 665 // Compare for smaller 0 666 insert_position = predicate_add_cmp_with_const(lower_instr, lower, Instruction::lss, 0, state, insert_position, bci); 667 } else { 668 assert(lower < 0, ""); 669 // Add 1 670 lower++; 671 lower = -lower; 672 // Compare for smaller or equal 0 673 insert_position = predicate_cmp_with_const(lower_instr, Instruction::leq, lower, state, insert_position, bci); 674 } 675 } 676 677 // No upper check required -> skip 678 if (!upper_check) return; 679 680 // We need to know length of array 681 if (!length_instr) { 682 // Load length if necessary 683 ArrayLength *length = new ArrayLength(array_instr, state->copy()); 684 NOT_PRODUCT(length->set_printable_bci(ai->printable_bci())); 685 length->set_exception_state(length->state_before()); 686 length->set_flag(Instruction::DeoptimizeOnException, true); 687 insert_position = insert_position->insert_after(length); 688 length_instr = length; 689 } 690 691 if (!upper_instr) { 692 // Compare for geq array.length 693 insert_position = predicate_cmp_with_const(length_instr, Instruction::leq, upper, state, insert_position, bci); 694 } else { 695 if (upper_instr->type()->as_ObjectType()) { 696 assert(state, "must not be null"); 697 assert(upper_instr != array_instr, "should be"); 698 ArrayLength *length = new ArrayLength(upper_instr, state->copy()); 699 NOT_PRODUCT(length->set_printable_bci(ai->printable_bci())); 700 length->set_flag(Instruction::DeoptimizeOnException, true); 701 length->set_exception_state(length->state_before()); 702 insert_position = insert_position->insert_after(length); 703 upper_instr = length; 704 } 705 assert(upper_instr->type()->as_IntType(), "Must not be object type!"); 706 707 if (upper == 0) { 708 // Compare for geq array.length 709 insert_position = predicate(upper_instr, Instruction::geq, length_instr, state, insert_position, bci); 710 } else if (upper < 0) { 711 // Compare for geq array.length 712 insert_position = predicate_add(upper_instr, upper, Instruction::geq, length_instr, state, insert_position, bci); 713 } else { 714 assert(upper > 0, ""); 715 upper = -upper; 716 // Compare for geq array.length 717 insert_position = predicate_add(length_instr, upper, Instruction::leq, upper_instr, state, insert_position, bci); 718 } 719 } 720} 721 722// Add if condition 723void RangeCheckEliminator::add_if_condition(IntegerStack &pushed, Value x, Value y, Instruction::Condition condition) { 724 if (y->as_Constant()) return; 725 726 int const_value = 0; 727 Value instr_value = x; 728 Constant *c = x->as_Constant(); 729 ArithmeticOp *ao = x->as_ArithmeticOp(); 730 731 if (c != NULL) { 732 const_value = c->type()->as_IntConstant()->value(); 733 instr_value = NULL; 734 } else if (ao != NULL && (!ao->x()->as_Constant() || !ao->y()->as_Constant()) && ((ao->op() == Bytecodes::_isub && ao->y()->as_Constant()) || ao->op() == Bytecodes::_iadd)) { 735 assert(!ao->x()->as_Constant() || !ao->y()->as_Constant(), "At least one operator must be non-constant!"); 736 assert(ao->op() == Bytecodes::_isub || ao->op() == Bytecodes::_iadd, "Operation has to be add or sub!"); 737 c = ao->x()->as_Constant(); 738 if (c != NULL) { 739 const_value = c->type()->as_IntConstant()->value(); 740 instr_value = ao->y(); 741 } else { 742 c = ao->y()->as_Constant(); 743 if (c != NULL) { 744 const_value = c->type()->as_IntConstant()->value(); 745 instr_value = ao->x(); 746 } 747 } 748 if (ao->op() == Bytecodes::_isub) { 749 assert(ao->y()->as_Constant(), "1 - x not supported, only x - 1 is valid!"); 750 if (const_value > min_jint) { 751 const_value = -const_value; 752 } else { 753 const_value = 0; 754 instr_value = x; 755 } 756 } 757 } 758 759 update_bound(pushed, y, condition, instr_value, const_value); 760} 761 762// Process If 763void RangeCheckEliminator::process_if(IntegerStack &pushed, BlockBegin *block, If *cond) { 764 // Only if we are direct true / false successor and NOT both ! (even this may occur) 765 if ((cond->tsux() == block || cond->fsux() == block) && cond->tsux() != cond->fsux()) { 766 Instruction::Condition condition = cond->cond(); 767 if (cond->fsux() == block) { 768 condition = Instruction::negate(condition); 769 } 770 Value x = cond->x(); 771 Value y = cond->y(); 772 if (x->type()->as_IntType() && y->type()->as_IntType()) { 773 add_if_condition(pushed, y, x, condition); 774 add_if_condition(pushed, x, y, Instruction::mirror(condition)); 775 } 776 } 777} 778 779// Process access indexed 780void RangeCheckEliminator::process_access_indexed(BlockBegin *loop_header, BlockBegin *block, AccessIndexed *ai) { 781 TRACE_RANGE_CHECK_ELIMINATION( 782 tty->fill_to(block->dominator_depth()*2) 783 ); 784 TRACE_RANGE_CHECK_ELIMINATION( 785 tty->print_cr("Access indexed: index=%d length=%d", ai->index()->id(), (ai->length() != NULL ? ai->length()->id() :-1 )) 786 ); 787 788 if (ai->check_flag(Instruction::NeedsRangeCheckFlag)) { 789 Bound *index_bound = get_bound(ai->index()); 790 if (!index_bound->has_lower() || !index_bound->has_upper()) { 791 TRACE_RANGE_CHECK_ELIMINATION( 792 tty->fill_to(block->dominator_depth()*2); 793 tty->print_cr("Index instruction %d has no lower and/or no upper bound!", ai->index()->id()) 794 ); 795 return; 796 } 797 798 Bound *array_bound; 799 if (ai->length()) { 800 array_bound = get_bound(ai->length()); 801 } else { 802 array_bound = get_bound(ai->array()); 803 } 804 805 if (in_array_bound(index_bound, ai->array()) || 806 (index_bound && array_bound && index_bound->is_smaller(array_bound) && !index_bound->lower_instr() && index_bound->lower() >= 0)) { 807 TRACE_RANGE_CHECK_ELIMINATION( 808 tty->fill_to(block->dominator_depth()*2); 809 tty->print_cr("Bounds check for instruction %d in block B%d can be fully eliminated!", ai->id(), ai->block()->block_id()) 810 ); 811 812 remove_range_check(ai); 813 } else if (_optimistic && loop_header) { 814 assert(ai->array(), "Array must not be null!"); 815 assert(ai->index(), "Index must not be null!"); 816 817 // Array instruction 818 Instruction *array_instr = ai->array(); 819 if (!loop_invariant(loop_header, array_instr)) { 820 TRACE_RANGE_CHECK_ELIMINATION( 821 tty->fill_to(block->dominator_depth()*2); 822 tty->print_cr("Array %d is not loop invariant to header B%d", ai->array()->id(), loop_header->block_id()) 823 ); 824 return; 825 } 826 827 // Lower instruction 828 Value index_instr = ai->index(); 829 Value lower_instr = index_bound->lower_instr(); 830 if (!loop_invariant(loop_header, lower_instr)) { 831 TRACE_RANGE_CHECK_ELIMINATION( 832 tty->fill_to(block->dominator_depth()*2); 833 tty->print_cr("Lower instruction %d not loop invariant!", lower_instr->id()) 834 ); 835 return; 836 } 837 if (!lower_instr && index_bound->lower() < 0) { 838 TRACE_RANGE_CHECK_ELIMINATION( 839 tty->fill_to(block->dominator_depth()*2); 840 tty->print_cr("Lower bound smaller than 0 (%d)!", index_bound->lower()) 841 ); 842 return; 843 } 844 845 // Upper instruction 846 Value upper_instr = index_bound->upper_instr(); 847 if (!loop_invariant(loop_header, upper_instr)) { 848 TRACE_RANGE_CHECK_ELIMINATION( 849 tty->fill_to(block->dominator_depth()*2); 850 tty->print_cr("Upper instruction %d not loop invariant!", upper_instr->id()) 851 ); 852 return; 853 } 854 855 // Length instruction 856 Value length_instr = ai->length(); 857 if (!loop_invariant(loop_header, length_instr)) { 858 // Generate length instruction yourself! 859 length_instr = NULL; 860 } 861 862 TRACE_RANGE_CHECK_ELIMINATION( 863 tty->fill_to(block->dominator_depth()*2); 864 tty->print_cr("LOOP INVARIANT access indexed %d found in block B%d!", ai->id(), ai->block()->block_id()) 865 ); 866 867 BlockBegin *pred_block = loop_header->dominator(); 868 assert(pred_block != NULL, "Every loop header has a dominator!"); 869 BlockEnd *pred_block_end = pred_block->end(); 870 Instruction *insert_position = pred_block_end->prev(); 871 ValueStack *state = pred_block_end->state_before(); 872 if (pred_block_end->as_Goto() && state == NULL) state = pred_block_end->state(); 873 assert(state, "State must not be null"); 874 875 // Add deoptimization to dominator of loop header 876 TRACE_RANGE_CHECK_ELIMINATION( 877 tty->fill_to(block->dominator_depth()*2); 878 tty->print_cr("Inserting deopt at bci %d in block B%d!", state->bci(), insert_position->block()->block_id()) 879 ); 880 881 if (!is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper())) { 882 TRACE_RANGE_CHECK_ELIMINATION( 883 tty->fill_to(block->dominator_depth()*2); 884 tty->print_cr("Could not eliminate because of static analysis!") 885 ); 886 return; 887 } 888 889 insert_deoptimization(state, insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper(), ai); 890 891 // Finally remove the range check! 892 remove_range_check(ai); 893 } 894 } 895} 896 897void RangeCheckEliminator::remove_range_check(AccessIndexed *ai) { 898 ai->set_flag(Instruction::NeedsRangeCheckFlag, false); 899 // no range check, no need for the length instruction anymore 900 ai->clear_length(); 901 902 TRACE_RANGE_CHECK_ELIMINATION( 903 tty->fill_to(ai->dominator_depth()*2); 904 tty->print_cr("Range check for instruction %d eliminated!", ai->id()); 905 ); 906 907 ASSERT_RANGE_CHECK_ELIMINATION( 908 Value array_length = ai->length(); 909 if (!array_length) { 910 array_length = ai->array(); 911 assert(array_length->type()->as_ObjectType(), "Has to be object type!"); 912 } 913 int cur_constant = -1; 914 Value cur_value = array_length; 915 if (cur_value->type()->as_IntConstant()) { 916 cur_constant += cur_value->type()->as_IntConstant()->value(); 917 cur_value = NULL; 918 } 919 Bound *new_index_bound = new Bound(0, NULL, cur_constant, cur_value); 920 add_assertions(new_index_bound, ai->index(), ai); 921 ); 922} 923 924// Calculate bounds for instruction in this block and children blocks in the dominator tree 925void RangeCheckEliminator::calc_bounds(BlockBegin *block, BlockBegin *loop_header) { 926 // Ensures a valid loop_header 927 assert(!loop_header || loop_header->is_set(BlockBegin::linear_scan_loop_header_flag), "Loop header has to be real !"); 928 929 // Tracing output 930 TRACE_RANGE_CHECK_ELIMINATION( 931 tty->fill_to(block->dominator_depth()*2); 932 tty->print_cr("Block B%d", block->block_id()); 933 ); 934 935 // Pushed stack for conditions 936 IntegerStack pushed; 937 // Process If 938 BlockBegin *parent = block->dominator(); 939 if (parent != NULL) { 940 If *cond = parent->end()->as_If(); 941 if (cond != NULL) { 942 process_if(pushed, block, cond); 943 } 944 } 945 946 // Interate over current block 947 InstructionList arrays; 948 AccessIndexedList accessIndexed; 949 Instruction *cur = block; 950 951 while (cur) { 952 // Ensure cur wasn't inserted during the elimination 953 if (cur->id() < this->_bounds.length()) { 954 // Process only if it is an access indexed instruction 955 AccessIndexed *ai = cur->as_AccessIndexed(); 956 if (ai != NULL) { 957 process_access_indexed(loop_header, block, ai); 958 accessIndexed.append(ai); 959 if (!arrays.contains(ai->array())) { 960 arrays.append(ai->array()); 961 } 962 Bound *b = get_bound(ai->index()); 963 if (!b->lower_instr()) { 964 // Lower bound is constant 965 update_bound(pushed, ai->index(), Instruction::geq, NULL, 0); 966 } 967 if (!b->has_upper()) { 968 if (ai->length() && ai->length()->type()->as_IntConstant()) { 969 int value = ai->length()->type()->as_IntConstant()->value(); 970 update_bound(pushed, ai->index(), Instruction::lss, NULL, value); 971 } else { 972 // Has no upper bound 973 Instruction *instr = ai->length(); 974 if (instr != NULL) instr = ai->array(); 975 update_bound(pushed, ai->index(), Instruction::lss, instr, 0); 976 } 977 } 978 } 979 } 980 cur = cur->next(); 981 } 982 983 // Output current condition stack 984 TRACE_RANGE_CHECK_ELIMINATION(dump_condition_stack(block)); 985 986 // Do in block motion of range checks 987 in_block_motion(block, accessIndexed, arrays); 988 989 // Call all dominated blocks 990 for (int i=0; i<block->dominates()->length(); i++) { 991 BlockBegin *next = block->dominates()->at(i); 992 if (!next->is_set(BlockBegin::donot_eliminate_range_checks)) { 993 // if current block is a loop header and: 994 // - next block belongs to the same loop 995 // or 996 // - next block belongs to an inner loop 997 // then current block is the loop header for next block 998 if (block->is_set(BlockBegin::linear_scan_loop_header_flag) && (block->loop_index() == next->loop_index() || next->loop_depth() > block->loop_depth())) { 999 calc_bounds(next, block); 1000 } else { 1001 calc_bounds(next, loop_header); 1002 } 1003 } 1004 } 1005 1006 // Reset stack 1007 for (int i=0; i<pushed.length(); i++) { 1008 _bounds.at(pushed.at(i))->pop(); 1009 } 1010} 1011 1012#ifndef PRODUCT 1013// Dump condition stack 1014void RangeCheckEliminator::dump_condition_stack(BlockBegin *block) { 1015 for (int i=0; i<_ir->linear_scan_order()->length(); i++) { 1016 BlockBegin *cur_block = _ir->linear_scan_order()->at(i); 1017 Instruction *instr = cur_block; 1018 for_each_phi_fun(cur_block, phi, 1019 BoundStack *bound_stack = _bounds.at(phi->id()); 1020 if (bound_stack && bound_stack->length() > 0) { 1021 Bound *bound = bound_stack->top(); 1022 if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != phi || bound->upper_instr() != phi || bound->lower() != 0 || bound->upper() != 0)) { 1023 TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth()); 1024 tty->print("i%d", phi->id()); 1025 tty->print(": "); 1026 bound->print(); 1027 tty->cr(); 1028 ); 1029 } 1030 }); 1031 1032 while (!instr->as_BlockEnd()) { 1033 if (instr->id() < _bounds.length()) { 1034 BoundStack *bound_stack = _bounds.at(instr->id()); 1035 if (bound_stack && bound_stack->length() > 0) { 1036 Bound *bound = bound_stack->top(); 1037 if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != instr || bound->upper_instr() != instr || bound->lower() != 0 || bound->upper() != 0)) { 1038 TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth()); 1039 tty->print("i%d", instr->id()); 1040 tty->print(": "); 1041 bound->print(); 1042 tty->cr(); 1043 ); 1044 } 1045 } 1046 } 1047 instr = instr->next(); 1048 } 1049 } 1050} 1051#endif 1052 1053// Verification or the IR 1054RangeCheckEliminator::Verification::Verification(IR *ir) : _used(BlockBegin::number_of_blocks(), BlockBegin::number_of_blocks(), false) { 1055 this->_ir = ir; 1056 ir->iterate_linear_scan_order(this); 1057} 1058 1059// Verify this block 1060void RangeCheckEliminator::Verification::block_do(BlockBegin *block) { 1061 If *cond = block->end()->as_If(); 1062 // Watch out: tsux and fsux can be the same! 1063 if (block->number_of_sux() > 1) { 1064 for (int i=0; i<block->number_of_sux(); i++) { 1065 BlockBegin *sux = block->sux_at(i); 1066 BlockBegin *pred = NULL; 1067 for (int j=0; j<sux->number_of_preds(); j++) { 1068 BlockBegin *cur = sux->pred_at(j); 1069 assert(cur != NULL, "Predecessor must not be null"); 1070 if (!pred) { 1071 pred = cur; 1072 } 1073 assert(cur == pred, "Block must not have more than one predecessor if its predecessor has more than one successor"); 1074 } 1075 assert(sux->number_of_preds() >= 1, "Block must have at least one predecessor"); 1076 assert(sux->pred_at(0) == block, "Wrong successor"); 1077 } 1078 } 1079 1080 BlockBegin *dominator = block->dominator(); 1081 if (dominator) { 1082 assert(block != _ir->start(), "Start block must not have a dominator!"); 1083 assert(can_reach(dominator, block), "Dominator can't reach his block !"); 1084 assert(can_reach(_ir->start(), dominator), "Dominator is unreachable !"); 1085 assert(!can_reach(_ir->start(), block, dominator), "Wrong dominator ! Block can be reached anyway !"); 1086 BlockList *all_blocks = _ir->linear_scan_order(); 1087 for (int i=0; i<all_blocks->length(); i++) { 1088 BlockBegin *cur = all_blocks->at(i); 1089 if (cur != dominator && cur != block) { 1090 assert(can_reach(dominator, block, cur), "There has to be another dominator!"); 1091 } 1092 } 1093 } else { 1094 assert(block == _ir->start(), "Only start block must not have a dominator"); 1095 } 1096 1097 if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) { 1098 int loop_index = block->loop_index(); 1099 BlockList *all_blocks = _ir->linear_scan_order(); 1100 assert(block->number_of_preds() >= 1, "Block must have at least one predecessor"); 1101 assert(!block->is_set(BlockBegin::exception_entry_flag), "Loop header must not be exception handler!"); 1102 // Sometimes, the backbranch comes from an exception handler. In 1103 // this case, loop indexes/loop depths may not appear correct. 1104 bool loop_through_xhandler = false; 1105 for (int i = 0; i < block->number_of_exception_handlers(); i++) { 1106 BlockBegin *xhandler = block->exception_handler_at(i); 1107 for (int j = 0; j < block->number_of_preds(); j++) { 1108 if (dominates(xhandler, block->pred_at(j)) || xhandler == block->pred_at(j)) { 1109 loop_through_xhandler = true; 1110 } 1111 } 1112 } 1113 1114 for (int i=0; i<block->number_of_sux(); i++) { 1115 BlockBegin *sux = block->sux_at(i); 1116 assert(sux->loop_depth() != block->loop_depth() || sux->loop_index() == block->loop_index() || loop_through_xhandler, "Loop index has to be same"); 1117 assert(sux->loop_depth() == block->loop_depth() || sux->loop_index() != block->loop_index(), "Loop index has to be different"); 1118 } 1119 1120 for (int i=0; i<all_blocks->length(); i++) { 1121 BlockBegin *cur = all_blocks->at(i); 1122 if (cur->loop_index() == loop_index && cur != block) { 1123 assert(dominates(block->dominator(), cur), "Dominator of loop header must dominate all loop blocks"); 1124 } 1125 } 1126 } 1127 1128 Instruction *cur = block; 1129 while (cur) { 1130 assert(cur->block() == block, "Block begin has to be set correctly!"); 1131 cur = cur->next(); 1132 } 1133} 1134 1135// Loop header must dominate all loop blocks 1136bool RangeCheckEliminator::Verification::dominates(BlockBegin *dominator, BlockBegin *block) { 1137 BlockBegin *cur = block->dominator(); 1138 while (cur && cur != dominator) { 1139 cur = cur->dominator(); 1140 } 1141 return cur == dominator; 1142} 1143 1144// Try to reach Block end beginning in Block start and not using Block dont_use 1145bool RangeCheckEliminator::Verification::can_reach(BlockBegin *start, BlockBegin *end, BlockBegin *dont_use /* = NULL */) { 1146 if (start == end) return start != dont_use; 1147 // Simple BSF from start to end 1148 // BlockBeginList _current; 1149 for (int i=0; i < _used.length(); i++) { 1150 _used.at_put(i, false); 1151 } 1152 _current.trunc_to(0); 1153 _successors.trunc_to(0); 1154 if (start != dont_use) { 1155 _current.push(start); 1156 _used.at_put(start->block_id(), true); 1157 } 1158 1159 // BlockBeginList _successors; 1160 while (_current.length() > 0) { 1161 BlockBegin *cur = _current.pop(); 1162 // Add exception handlers to list 1163 for (int i=0; i<cur->number_of_exception_handlers(); i++) { 1164 BlockBegin *xhandler = cur->exception_handler_at(i); 1165 _successors.push(xhandler); 1166 // Add exception handlers of _successors to list 1167 for (int j=0; j<xhandler->number_of_exception_handlers(); j++) { 1168 BlockBegin *sux_xhandler = xhandler->exception_handler_at(j); 1169 _successors.push(sux_xhandler); 1170 } 1171 } 1172 // Add normal _successors to list 1173 for (int i=0; i<cur->number_of_sux(); i++) { 1174 BlockBegin *sux = cur->sux_at(i); 1175 _successors.push(sux); 1176 // Add exception handlers of _successors to list 1177 for (int j=0; j<sux->number_of_exception_handlers(); j++) { 1178 BlockBegin *xhandler = sux->exception_handler_at(j); 1179 _successors.push(xhandler); 1180 } 1181 } 1182 for (int i=0; i<_successors.length(); i++) { 1183 BlockBegin *sux = _successors.at(i); 1184 assert(sux != NULL, "Successor must not be NULL!"); 1185 if (sux == end) { 1186 return true; 1187 } 1188 if (sux != dont_use && !_used.at(sux->block_id())) { 1189 _used.at_put(sux->block_id(), true); 1190 _current.push(sux); 1191 } 1192 } 1193 _successors.trunc_to(0); 1194 } 1195 1196 return false; 1197} 1198 1199// Bound 1200RangeCheckEliminator::Bound::~Bound() { 1201} 1202 1203// Bound constructor 1204RangeCheckEliminator::Bound::Bound() { 1205 init(); 1206 this->_lower = min_jint; 1207 this->_upper = max_jint; 1208 this->_lower_instr = NULL; 1209 this->_upper_instr = NULL; 1210} 1211 1212// Bound constructor 1213RangeCheckEliminator::Bound::Bound(int lower, Value lower_instr, int upper, Value upper_instr) { 1214 init(); 1215 assert(!lower_instr || !lower_instr->as_Constant() || !lower_instr->type()->as_IntConstant(), "Must not be constant!"); 1216 assert(!upper_instr || !upper_instr->as_Constant() || !upper_instr->type()->as_IntConstant(), "Must not be constant!"); 1217 this->_lower = lower; 1218 this->_upper = upper; 1219 this->_lower_instr = lower_instr; 1220 this->_upper_instr = upper_instr; 1221} 1222 1223// Bound constructor 1224RangeCheckEliminator::Bound::Bound(Instruction::Condition cond, Value v, int constant) { 1225 assert(!v || (v->type() && (v->type()->as_IntType() || v->type()->as_ObjectType())), "Type must be array or integer!"); 1226 assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!"); 1227 1228 init(); 1229 if (cond == Instruction::eql) { 1230 _lower = constant; 1231 _lower_instr = v; 1232 _upper = constant; 1233 _upper_instr = v; 1234 } else if (cond == Instruction::neq) { 1235 _lower = min_jint; 1236 _upper = max_jint; 1237 _lower_instr = NULL; 1238 _upper_instr = NULL; 1239 if (v == NULL) { 1240 if (constant == min_jint) { 1241 _lower++; 1242 } 1243 if (constant == max_jint) { 1244 _upper--; 1245 } 1246 } 1247 } else if (cond == Instruction::geq) { 1248 _lower = constant; 1249 _lower_instr = v; 1250 _upper = max_jint; 1251 _upper_instr = NULL; 1252 } else if (cond == Instruction::leq) { 1253 _lower = min_jint; 1254 _lower_instr = NULL; 1255 _upper = constant; 1256 _upper_instr = v; 1257 } else { 1258 ShouldNotReachHere(); 1259 } 1260} 1261 1262// Set lower 1263void RangeCheckEliminator::Bound::set_lower(int value, Value v) { 1264 assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!"); 1265 this->_lower = value; 1266 this->_lower_instr = v; 1267} 1268 1269// Set upper 1270void RangeCheckEliminator::Bound::set_upper(int value, Value v) { 1271 assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!"); 1272 this->_upper = value; 1273 this->_upper_instr = v; 1274} 1275 1276// Add constant -> no overflow may occur 1277void RangeCheckEliminator::Bound::add_constant(int value) { 1278 this->_lower += value; 1279 this->_upper += value; 1280} 1281 1282// Init 1283void RangeCheckEliminator::Bound::init() { 1284} 1285 1286// or 1287void RangeCheckEliminator::Bound::or_op(Bound *b) { 1288 // Watch out, bound is not guaranteed not to overflow! 1289 // Update lower bound 1290 if (_lower_instr != b->_lower_instr || (_lower_instr && _lower != b->_lower)) { 1291 _lower_instr = NULL; 1292 _lower = min_jint; 1293 } else { 1294 _lower = MIN2(_lower, b->_lower); 1295 } 1296 // Update upper bound 1297 if (_upper_instr != b->_upper_instr || (_upper_instr && _upper != b->_upper)) { 1298 _upper_instr = NULL; 1299 _upper = max_jint; 1300 } else { 1301 _upper = MAX2(_upper, b->_upper); 1302 } 1303} 1304 1305// and 1306void RangeCheckEliminator::Bound::and_op(Bound *b) { 1307 // Update lower bound 1308 if (_lower_instr == b->_lower_instr) { 1309 _lower = MAX2(_lower, b->_lower); 1310 } 1311 if (b->has_lower()) { 1312 bool set = true; 1313 if (_lower_instr != NULL && b->_lower_instr != NULL) { 1314 set = (_lower_instr->dominator_depth() > b->_lower_instr->dominator_depth()); 1315 } 1316 if (set) { 1317 _lower = b->_lower; 1318 _lower_instr = b->_lower_instr; 1319 } 1320 } 1321 // Update upper bound 1322 if (_upper_instr == b->_upper_instr) { 1323 _upper = MIN2(_upper, b->_upper); 1324 } 1325 if (b->has_upper()) { 1326 bool set = true; 1327 if (_upper_instr != NULL && b->_upper_instr != NULL) { 1328 set = (_upper_instr->dominator_depth() > b->_upper_instr->dominator_depth()); 1329 } 1330 if (set) { 1331 _upper = b->_upper; 1332 _upper_instr = b->_upper_instr; 1333 } 1334 } 1335} 1336 1337// has_upper 1338bool RangeCheckEliminator::Bound::has_upper() { 1339 return _upper_instr != NULL || _upper < max_jint; 1340} 1341 1342// is_smaller 1343bool RangeCheckEliminator::Bound::is_smaller(Bound *b) { 1344 if (b->_lower_instr != _upper_instr) { 1345 return false; 1346 } 1347 return _upper < b->_lower; 1348} 1349 1350// has_lower 1351bool RangeCheckEliminator::Bound::has_lower() { 1352 return _lower_instr != NULL || _lower > min_jint; 1353} 1354 1355// in_array_bound 1356bool RangeCheckEliminator::in_array_bound(Bound *bound, Value array){ 1357 if (!bound) return false; 1358 assert(array != NULL, "Must not be null!"); 1359 assert(bound != NULL, "Must not be null!"); 1360 if (bound->lower() >=0 && bound->lower_instr() == NULL && bound->upper() < 0 && bound->upper_instr() != NULL) { 1361 ArrayLength *len = bound->upper_instr()->as_ArrayLength(); 1362 if (bound->upper_instr() == array || (len != NULL && len->array() == array)) { 1363 return true; 1364 } 1365 } 1366 return false; 1367} 1368 1369// remove_lower 1370void RangeCheckEliminator::Bound::remove_lower() { 1371 _lower = min_jint; 1372 _lower_instr = NULL; 1373} 1374 1375// remove_upper 1376void RangeCheckEliminator::Bound::remove_upper() { 1377 _upper = max_jint; 1378 _upper_instr = NULL; 1379} 1380 1381// upper 1382int RangeCheckEliminator::Bound::upper() { 1383 return _upper; 1384} 1385 1386// lower 1387int RangeCheckEliminator::Bound::lower() { 1388 return _lower; 1389} 1390 1391// upper_instr 1392Value RangeCheckEliminator::Bound::upper_instr() { 1393 return _upper_instr; 1394} 1395 1396// lower_instr 1397Value RangeCheckEliminator::Bound::lower_instr() { 1398 return _lower_instr; 1399} 1400 1401// print 1402void RangeCheckEliminator::Bound::print() { 1403 tty->print("%s", ""); 1404 if (this->_lower_instr || this->_lower != min_jint) { 1405 if (this->_lower_instr) { 1406 tty->print("i%d", this->_lower_instr->id()); 1407 if (this->_lower > 0) { 1408 tty->print("+%d", _lower); 1409 } 1410 if (this->_lower < 0) { 1411 tty->print("%d", _lower); 1412 } 1413 } else { 1414 tty->print("%d", _lower); 1415 } 1416 tty->print(" <= "); 1417 } 1418 tty->print("x"); 1419 if (this->_upper_instr || this->_upper != max_jint) { 1420 tty->print(" <= "); 1421 if (this->_upper_instr) { 1422 tty->print("i%d", this->_upper_instr->id()); 1423 if (this->_upper > 0) { 1424 tty->print("+%d", _upper); 1425 } 1426 if (this->_upper < 0) { 1427 tty->print("%d", _upper); 1428 } 1429 } else { 1430 tty->print("%d", _upper); 1431 } 1432 } 1433} 1434 1435// Copy 1436RangeCheckEliminator::Bound *RangeCheckEliminator::Bound::copy() { 1437 Bound *b = new Bound(); 1438 b->_lower = _lower; 1439 b->_lower_instr = _lower_instr; 1440 b->_upper = _upper; 1441 b->_upper_instr = _upper_instr; 1442 return b; 1443} 1444 1445#ifdef ASSERT 1446// Add assertion 1447void RangeCheckEliminator::Bound::add_assertion(Instruction *instruction, Instruction *position, int i, Value instr, Instruction::Condition cond) { 1448 Instruction *result = position; 1449 Instruction *compare_with = NULL; 1450 ValueStack *state = position->state_before(); 1451 if (position->as_BlockEnd() && !position->as_Goto()) { 1452 state = position->as_BlockEnd()->state_before(); 1453 } 1454 Instruction *instruction_before = position->prev(); 1455 if (position->as_Return() && Compilation::current()->method()->is_synchronized() && instruction_before->as_MonitorExit()) { 1456 instruction_before = instruction_before->prev(); 1457 } 1458 result = instruction_before; 1459 // Load constant only if needed 1460 Constant *constant = NULL; 1461 if (i != 0 || !instr) { 1462 constant = new Constant(new IntConstant(i)); 1463 NOT_PRODUCT(constant->set_printable_bci(position->printable_bci())); 1464 result = result->insert_after(constant); 1465 compare_with = constant; 1466 } 1467 1468 if (instr) { 1469 assert(instr->type()->as_ObjectType() || instr->type()->as_IntType(), "Type must be array or integer!"); 1470 compare_with = instr; 1471 // Load array length if necessary 1472 Instruction *op = instr; 1473 if (instr->type()->as_ObjectType()) { 1474 assert(state, "must not be null"); 1475 ArrayLength *length = new ArrayLength(instr, state->copy()); 1476 NOT_PRODUCT(length->set_printable_bci(position->printable_bci())); 1477 length->set_exception_state(length->state_before()); 1478 result = result->insert_after(length); 1479 op = length; 1480 compare_with = length; 1481 } 1482 // Add operation only if necessary 1483 if (constant) { 1484 ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, op, false, NULL); 1485 NOT_PRODUCT(ao->set_printable_bci(position->printable_bci())); 1486 result = result->insert_after(ao); 1487 compare_with = ao; 1488 // TODO: Check that add operation does not overflow! 1489 } 1490 } 1491 assert(compare_with != NULL, "You have to compare with something!"); 1492 assert(instruction != NULL, "Instruction must not be null!"); 1493 1494 if (instruction->type()->as_ObjectType()) { 1495 // Load array length if necessary 1496 Instruction *op = instruction; 1497 assert(state, "must not be null"); 1498 ArrayLength *length = new ArrayLength(instruction, state->copy()); 1499 length->set_exception_state(length->state_before()); 1500 NOT_PRODUCT(length->set_printable_bci(position->printable_bci())); 1501 result = result->insert_after(length); 1502 instruction = length; 1503 } 1504 1505 Assert *assert = new Assert(instruction, cond, false, compare_with); 1506 NOT_PRODUCT(assert->set_printable_bci(position->printable_bci())); 1507 result->insert_after(assert); 1508} 1509 1510// Add assertions 1511void RangeCheckEliminator::add_assertions(Bound *bound, Instruction *instruction, Instruction *position) { 1512 // Add lower bound assertion 1513 if (bound->has_lower()) { 1514 bound->add_assertion(instruction, position, bound->lower(), bound->lower_instr(), Instruction::geq); 1515 } 1516 // Add upper bound assertion 1517 if (bound->has_upper()) { 1518 bound->add_assertion(instruction, position, bound->upper(), bound->upper_instr(), Instruction::leq); 1519 } 1520} 1521#endif 1522 1523