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