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 #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

    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(

    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

   101 void 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

   110 void 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

   126 void 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

   219 void 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

   286 void 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.

   302 RangeCheckEliminator::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[v->id()]) {

   307     // First (default) bound is calculated

   308     // Create BoundStack

   309     _bounds[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[v->id()]->push(bound);

   316     }

   317     if (_bounds[v->id()]->length() == 0) {

   318       assert(!(v->as_Constant() && v->type()->as_IntConstant()), "constants not handled here");

   319       _bounds[v->id()]->push(new Bound());

   320     }

   321   } else if (_bounds[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[v->id()]->top();

   328 }

   329 

   330 // Update bound

   331 void 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.

   344 bool 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.

   351 void 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[v->id()]) {

   357     get_bound(v);

   358     assert(_bounds[v->id()], "Now Stack must exist");

   359   }

   360   Bound *top = NULL;

   361   if (_bounds[v->id()]->length() > 0) {

   362     top = _bounds[v->id()]->top();

   363   }

   364   if (top) {

   365     bound->and_op(top);

   366   }

   367   _bounds[v->id()]->push(bound);

   368   pushed.append(v->id());

   369 }

   370 

   371 // Add instruction + idx for in block motion

   372 void RangeCheckEliminator::add_access_indexed_info(InstructionList &indices, int idx, Value instruction, AccessIndexed *ai) {

   373   int id = instruction->id();

   374   AccessIndexedInfo *aii = _access_indexed_info[id];

   375   if (aii == NULL) {

   376     aii = new AccessIndexedInfo();

   377     _access_indexed_info[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.

   399 void 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[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         _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         insert_position = predicate(compare_instr, Instruction::geq, length_instr, state, insert_position);

   557         for (int j = 0; j<list_constant.length(); j++) {

   558           AccessIndexed *ai = list_constant.at(j);

   559           remove_range_check(ai);

   560         }

   561       }

   562     }

   563   }

   564 }

   565 

   566 bool RangeCheckEliminator::set_process_block_flags(BlockBegin *block) {

   567   Instruction *cur = block;

   568   bool process = false;

   569 

   570   while (cur) {

   571     process |= (cur->as_AccessIndexed() != NULL);

   572     cur = cur->next();

   573   }

   574 

   575   BlockList *dominates = block->dominates();

   576   for (int i=0; i<dominates->length(); i++) {

   577     BlockBegin *next = dominates->at(i);

   578     process |= set_process_block_flags(next);

   579   }

   580 

   581   if (!process) {

   582     block->set(BlockBegin::donot_eliminate_range_checks);

   583   }

   584   return process;

   585 }

   586 

   587 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) {

   588   bool upper_check = true;

   589   assert(lower_instr || lower >= 0, "If no lower_instr present, lower must be greater 0");

   590   assert(!lower_instr || lower_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");

   591   assert(!upper_instr || upper_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");

   592   assert(array_instr, "Array instruction must exist");

   593   assert(array_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");

   594   assert(!length_instr || length_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");

   595 

   596   if (upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr) {

   597     // static check

   598     if (upper >= 0) return false; // would always trigger a deopt:

   599                                   // array_length + x >= array_length, x >= 0 is always true

   600     upper_check = false;

   601   }

   602   if (lower_instr && lower_instr->as_ArrayLength() && lower_instr->as_ArrayLength()->array() == array_instr) {

   603     if (lower > 0) return false;

   604   }

   605   // No upper check required -> skip

   606   if (upper_check && upper_instr && upper_instr->type()->as_ObjectType() && upper_instr == array_instr) {

   607     // upper_instr is object means that the upper bound is the length

   608     // of the upper_instr.

   609     return false;

   610   }

   611   return true;

   612 }

   613 

   614 Instruction* RangeCheckEliminator::insert_after(Instruction* insert_position, Instruction* instr, int bci) {

   615   if (bci != -1) {

   616     NOT_PRODUCT(instr->set_printable_bci(bci));

   617     return insert_position->insert_after(instr);

   618   } else {

   619     return insert_position->insert_after_same_bci(instr);

   620   }

   621 }

   622 

   623 Instruction* RangeCheckEliminator::predicate(Instruction* left, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) {

   624   RangeCheckPredicate *deoptimize = new RangeCheckPredicate(left, cond, true, right, state->copy());

   625   return insert_after(insert_position, deoptimize, bci);

   626 }

   627 

   628 Instruction* RangeCheckEliminator::predicate_cmp_with_const(Instruction* instr, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) {

   629   Constant *const_instr = new Constant(new IntConstant(constant));

   630   insert_position = insert_after(insert_position, const_instr, bci);

   631   return predicate(instr, cond, const_instr, state, insert_position);

   632 }

   633 

   634 Instruction* RangeCheckEliminator::predicate_add(Instruction* left, int left_const, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) {

   635   Constant *constant = new Constant(new IntConstant(left_const));

   636   insert_position = insert_after(insert_position, constant, bci);

   637   ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, left, false, NULL);

   638   insert_position = insert_position->insert_after_same_bci(ao);

   639   return predicate(ao, cond, right, state, insert_position);

   640 }

   641 

   642 Instruction* RangeCheckEliminator::predicate_add_cmp_with_const(Instruction* left, int left_const, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) {

   643   Constant *const_instr = new Constant(new IntConstant(constant));

   644   insert_position = insert_after(insert_position, const_instr, bci);

   645   return predicate_add(left, left_const, cond, const_instr, state, insert_position);

   646 }

   647 

   648 // Insert deoptimization, returns true if sucessful or false if range check should not be removed

   649 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) {

   650   assert(is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, lower, upper_instr, upper), "should have been tested before");

   651   bool upper_check = !(upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr);

   652 

   653   int bci = NOT_PRODUCT(ai->printable_bci()) PRODUCT_ONLY(-1);

   654   if (lower_instr) {

   655     assert(!lower_instr->type()->as_ObjectType(), "Must not be object type");

   656     if (lower == 0) {

   657       // Compare for less than 0

   658       insert_position = predicate_cmp_with_const(lower_instr, Instruction::lss, 0, state, insert_position, bci);

   659     } else if (lower > 0) {

   660       // Compare for smaller 0

   661       insert_position = predicate_add_cmp_with_const(lower_instr, lower, Instruction::lss, 0, state, insert_position, bci);

   662     } else {

   663       assert(lower < 0, "");

   664       // Add 1

   665       lower++;

   666       lower = -lower;

   667       // Compare for smaller or equal 0

   668       insert_position = predicate_cmp_with_const(lower_instr, Instruction::leq, lower, state, insert_position, bci);

   669     }

   670   }

   671 

   672   // We need to know length of array

   673   if (!length_instr) {

   674     // Load length if necessary

   675     ArrayLength *length = new ArrayLength(array_instr, state->copy());

   676     NOT_PRODUCT(length->set_printable_bci(ai->printable_bci()));

   677     length->set_exception_state(length->state_before());

   678     length->set_flag(Instruction::DeoptimizeOnException, true);

   679     insert_position = insert_position->insert_after(length);

   680     length_instr = length;

   681   }

   682 

   683   // No upper check required -> skip

   684   if (!upper_check) return;

   685 

   686   if (!upper_instr) {

   687     // Compare for geq array.length

   688     insert_position = predicate_cmp_with_const(length_instr, Instruction::leq, upper, state, insert_position, bci);

   689   } else {

   690     if (upper_instr->type()->as_ObjectType()) {

   691       assert(state, "must not be null");

   692       assert(upper_instr != array_instr, "should be");

   693       ArrayLength *length = new ArrayLength(upper_instr, state->copy());

   694       NOT_PRODUCT(length->set_printable_bci(ai->printable_bci()));

   695       length->set_flag(Instruction::DeoptimizeOnException, true);

   696       length->set_exception_state(length->state_before());

   697       insert_position = insert_position->insert_after(length);

   698       upper_instr = length;

   699     }

   700     assert(upper_instr->type()->as_IntType(), "Must not be object type!");

   701 

   702     if (upper == 0) {

   703       // Compare for geq array.length

   704       insert_position = predicate(upper_instr, Instruction::geq, length_instr, state, insert_position, bci);

   705     } else if (upper < 0) {

   706       // Compare for geq array.length

   707       insert_position = predicate_add(upper_instr, upper, Instruction::geq, length_instr, state, insert_position, bci);

   708     } else {

   709       assert(upper > 0, "");

   710       upper = -upper;

   711       // Compare for geq array.length

   712       insert_position = predicate_add(length_instr, upper, Instruction::leq, upper_instr, state, insert_position, bci);

   713     }

   714   }

   715 }

   716 

   717 // Add if condition

   718 void RangeCheckEliminator::add_if_condition(IntegerStack &pushed, Value x, Value y, Instruction::Condition condition) {

   719   if (y->as_Constant()) return;

   720 

   721   int const_value = 0;

   722   Value instr_value = x;

   723   Constant *c = x->as_Constant();

   724   ArithmeticOp *ao = x->as_ArithmeticOp();

   725 

   726   if (c != NULL) {

   727     const_value = c->type()->as_IntConstant()->value();

   728     instr_value = NULL;

   729   } else if (ao != NULL &&  (!ao->x()->as_Constant() || !ao->y()->as_Constant()) && ((ao->op() == Bytecodes::_isub && ao->y()->as_Constant()) || ao->op() == Bytecodes::_iadd)) {

   730     assert(!ao->x()->as_Constant() || !ao->y()->as_Constant(), "At least one operator must be non-constant!");

   731     assert(ao->op() == Bytecodes::_isub || ao->op() == Bytecodes::_iadd, "Operation has to be add or sub!");

   732     c = ao->x()->as_Constant();

   733     if (c != NULL) {

   734       const_value = c->type()->as_IntConstant()->value();

   735       instr_value = ao->y();

   736     } else {

   737       c = ao->y()->as_Constant();

   738       if (c != NULL) {

   739         const_value = c->type()->as_IntConstant()->value();

   740         instr_value = ao->x();

   741       }

   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(

   777     tty->fill_to(block->dominator_depth()*2)

   778   );

   779   TRACE_RANGE_CHECK_ELIMINATION(

   780     tty->print_cr("Access indexed: index=%d length=%d", ai->index()->id(), ai->length()->id())

   781   );

   782 

   783   if (ai->check_flag(Instruction::NeedsRangeCheckFlag)) {

   784     Bound *index_bound = get_bound(ai->index());

   785     if (!index_bound->has_lower() || !index_bound->has_upper()) {

   786       TRACE_RANGE_CHECK_ELIMINATION(

   787         tty->fill_to(block->dominator_depth()*2);

   788         tty->print_cr("Index instruction %d has no lower and/or no upper bound!", ai->index()->id())

   789       );

   790       return;

   791     }

   792 

   793     Bound *array_bound;

   794     if (ai->length()) {

   795       array_bound = get_bound(ai->length());

   796     } else {

   797       array_bound = get_bound(ai->array());

   798     }

   799 

   800     if (in_array_bound(index_bound, ai->array()) ||

   801       (index_bound && array_bound && index_bound->is_smaller(array_bound) && !index_bound->lower_instr() && index_bound->lower() >= 0)) {

   802         TRACE_RANGE_CHECK_ELIMINATION(

   803           tty->fill_to(block->dominator_depth()*2);

   804           tty->print_cr("Bounds check for instruction %d in block B%d can be fully eliminated!", ai->id(), ai->block()->block_id())

   805         );

   806 

   807         remove_range_check(ai);

   808     } else if (_optimistic && loop_header) {

   809       assert(ai->array(), "Array must not be null!");

   810       assert(ai->index(), "Index must not be null!");

   811 

   812       // Array instruction

   813       Instruction *array_instr = ai->array();

   814       if (!loop_invariant(loop_header, array_instr)) {

   815         TRACE_RANGE_CHECK_ELIMINATION(

   816           tty->fill_to(block->dominator_depth()*2);

   817           tty->print_cr("Array %d is not loop invariant to header B%d", ai->array()->id(), loop_header->block_id())

   818         );

   819         return;

   820       }

   821 

   822       // Lower instruction

   823       Value index_instr = ai->index();

   824       Value lower_instr = index_bound->lower_instr();

   825       if (!loop_invariant(loop_header, lower_instr)) {

   826         TRACE_RANGE_CHECK_ELIMINATION(

   827           tty->fill_to(block->dominator_depth()*2);

   828           tty->print_cr("Lower instruction %d not loop invariant!", lower_instr->id())

   829         );

   830         return;

   831       }

   832       if (!lower_instr && index_bound->lower() < 0) {

   833         TRACE_RANGE_CHECK_ELIMINATION(

   834           tty->fill_to(block->dominator_depth()*2);

   835           tty->print_cr("Lower bound smaller than 0 (%d)!", index_bound->lower())

   836         );

   837         return;

   838       }

   839 

   840       // Upper instruction

   841       Value upper_instr = index_bound->upper_instr();

   842       if (!loop_invariant(loop_header, upper_instr)) {

   843         TRACE_RANGE_CHECK_ELIMINATION(

   844           tty->fill_to(block->dominator_depth()*2);

   845           tty->print_cr("Upper instruction %d not loop invariant!", upper_instr->id())

   846         );

   847         return;

   848       }

   849 

   850       // Length instruction

   851       Value length_instr = ai->length();

   852       if (!loop_invariant(loop_header, length_instr)) {

   853         // Generate length instruction yourself!

   854         length_instr = NULL;

   855       }

   856 

   857       TRACE_RANGE_CHECK_ELIMINATION(

   858         tty->fill_to(block->dominator_depth()*2);

   859         tty->print_cr("LOOP INVARIANT access indexed %d found in block B%d!", ai->id(), ai->block()->block_id())

   860       );

   861 

   862       BlockBegin *pred_block = loop_header->dominator();

   863       assert(pred_block != NULL, "Every loop header has a dominator!");

   864       BlockEnd *pred_block_end = pred_block->end();

   865       Instruction *insert_position = pred_block_end->prev();

   866       ValueStack *state = pred_block_end->state_before();

   867       if (pred_block_end->as_Goto() && state == NULL) state = pred_block_end->state();

   868       assert(state, "State must not be null");

   869 

   870       // Add deoptimization to dominator of loop header

   871       TRACE_RANGE_CHECK_ELIMINATION(

   872         tty->fill_to(block->dominator_depth()*2);

   873         tty->print_cr("Inserting deopt at bci %d in block B%d!", state->bci(), insert_position->block()->block_id())

   874       );

   875 

   876       if (!is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper())) {

   877         TRACE_RANGE_CHECK_ELIMINATION(

   878           tty->fill_to(block->dominator_depth()*2);

   879           tty->print_cr("Could not eliminate because of static analysis!")

   880         );

   881         return;

   882       }

   883 

   884       insert_deoptimization(state, insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper(), ai);

   885 

   886       // Finally remove the range check!

   887       remove_range_check(ai);

   888     }

   889   }

   890 }

   891 

   892 void RangeCheckEliminator::remove_range_check(AccessIndexed *ai) {

   893   ai->set_flag(Instruction::NeedsRangeCheckFlag, false);

   894   // no range check, no need for the length instruction anymore

   895   ai->clear_length();

   896 

   897   TRACE_RANGE_CHECK_ELIMINATION(

   898     tty->fill_to(ai->dominator_depth()*2);

   899     tty->print_cr("Range check for instruction %d eliminated!", ai->id());

   900   );

   901 

   902   ASSERT_RANGE_CHECK_ELIMINATION(

   903     Value array_length = ai->length();

   904     if (!array_length) {

   905       array_length = ai->array();

   906       assert(array_length->type()->as_ObjectType(), "Has to be object type!");

   907     }

   908     int cur_constant = -1;

   909     Value cur_value = array_length;

   910     if (cur_value->type()->as_IntConstant()) {

   911       cur_constant += cur_value->type()->as_IntConstant()->value();

   912       cur_value = NULL;

   913     }

   914     Bound *new_index_bound = new Bound(0, NULL, cur_constant, cur_value);

   915     add_assertions(new_index_bound, ai->index(), ai);

   916   );

   917 }

   918 

   919 // Calculate bounds for instruction in this block and children blocks in the dominator tree

   920 void RangeCheckEliminator::calc_bounds(BlockBegin *block, BlockBegin *loop_header) {

   921   // Ensures a valid loop_header

   922   assert(!loop_header || loop_header->is_set(BlockBegin::linear_scan_loop_header_flag), "Loop header has to be real !");

   923 

   924   // Tracing output

   925   TRACE_RANGE_CHECK_ELIMINATION(

   926     tty->fill_to(block->dominator_depth()*2);

   927     tty->print_cr("Block B%d", block->block_id());

   928   );

   929 

   930   // Pushed stack for conditions

   931   IntegerStack pushed;

   932   // Process If

   933   BlockBegin *parent = block->dominator();

   934   if (parent != NULL) {

   935     If *cond = parent->end()->as_If();

   936     if (cond != NULL) {

   937       process_if(pushed, block, cond);

   938     }

   939   }

   940 

   941   // Interate over current block

   942   InstructionList arrays;

   943   AccessIndexedList accessIndexed;

   944   Instruction *cur = block;

   945 

   946   while (cur) {

   947     // Ensure cur wasn't inserted during the elimination

   948     if (cur->id() < this->_bounds.length()) {

   949       // Process only if it is an access indexed instruction

   950       AccessIndexed *ai = cur->as_AccessIndexed();

   951       if (ai != NULL) {

   952         process_access_indexed(loop_header, block, ai);

   953         accessIndexed.append(ai);

   954         if (!arrays.contains(ai->array())) {

   955           arrays.append(ai->array());

   956         }

   957         Bound *b = get_bound(ai->index());

   958         if (!b->lower_instr()) {

   959           // Lower bound is constant

   960           update_bound(pushed, ai->index(), Instruction::geq, NULL, 0);

   961         }

   962         if (!b->has_upper()) {

   963           if (ai->length() && ai->length()->type()->as_IntConstant()) {

   964             int value = ai->length()->type()->as_IntConstant()->value();

   965             update_bound(pushed, ai->index(), Instruction::lss, NULL, value);

   966           } else {

   967             // Has no upper bound

   968             Instruction *instr = ai->length();

   969             if (instr != NULL) instr = ai->array();

   970             update_bound(pushed, ai->index(), Instruction::lss, instr, 0);

   971           }

   972         }

   973       }

   974     }

   975     cur = cur->next();

   976   }

   977 

   978   // Output current condition stack

   979   TRACE_RANGE_CHECK_ELIMINATION(dump_condition_stack(block));

   980 

   981   // Do in block motion of range checks

   982   in_block_motion(block, accessIndexed, arrays);

   983 

   984   // Call all dominated blocks

   985   for (int i=0; i<block->dominates()->length(); i++) {

   986     BlockBegin *next = block->dominates()->at(i);

   987     if (!next->is_set(BlockBegin::donot_eliminate_range_checks)) {

   988       // if current block is a loop header and:

   989       // - next block belongs to the same loop

   990       // or

   991       // - next block belongs to an inner loop

   992       // then current block is the loop header for next block

   993       if (block->is_set(BlockBegin::linear_scan_loop_header_flag) && (block->loop_index() == next->loop_index() || next->loop_depth() > block->loop_depth())) {

   994         calc_bounds(next, block);

   995       } else {

   996         calc_bounds(next, loop_header);

   997       }

   998     }

   999   }

  1000 

  1001   // Reset stack

  1002   for (int i=0; i<pushed.length(); i++) {

  1003     _bounds[pushed[i]]->pop();

  1004   }

  1005 }

  1006 

  1007 #ifndef PRODUCT

  1008 // Dump condition stack

  1009 void RangeCheckEliminator::dump_condition_stack(BlockBegin *block) {

  1010   for (int i=0; i<_ir->linear_scan_order()->length(); i++) {

  1011     BlockBegin *cur_block = _ir->linear_scan_order()->at(i);

  1012     Instruction *instr = cur_block;

  1013     for_each_phi_fun(cur_block, phi,

  1014                      BoundStack *bound_stack = _bounds.at(phi->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() != phi || bound->upper_instr() != phi || bound->lower() != 0 || bound->upper() != 0)) {

  1018                            TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth());

  1019                                                          tty->print("i%d", phi->id());

  1020                                                          tty->print(": ");

  1021                                                          bound->print();

  1022                                                          tty->print_cr("");

  1023                            );

  1024                          }

  1025                      });

  1026 

  1027     while (!instr->as_BlockEnd()) {

  1028       if (instr->id() < _bounds.length()) {

  1029         BoundStack *bound_stack = _bounds.at(instr->id());

  1030         if (bound_stack && bound_stack->length() > 0) {

  1031           Bound *bound = bound_stack->top();

  1032           if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != instr || bound->upper_instr() != instr || bound->lower() != 0 || bound->upper() != 0)) {

  1033               TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth());

  1034                                             tty->print("i%d", instr->id());

  1035                                             tty->print(": ");

  1036                                             bound->print();

  1037                                             tty->print_cr("");

  1038               );

  1039           }

  1040         }

  1041       }

  1042       instr = instr->next();

  1043     }

  1044   }

  1045 }

  1046 #endif

  1047 

  1048 // Verification or the IR

  1049 RangeCheckEliminator::Verification::Verification(IR *ir) : _used(BlockBegin::number_of_blocks(), false) {

  1050   this->_ir = ir;

  1051   ir->iterate_linear_scan_order(this);

  1052 }

  1053 

  1054 // Verify this block

  1055 void RangeCheckEliminator::Verification::block_do(BlockBegin *block) {

  1056   If *cond = block->end()->as_If();

  1057   // Watch out: tsux and fsux can be the same!

  1058   if (block->number_of_sux() > 1) {

  1059     for (int i=0; i<block->number_of_sux(); i++) {

  1060       BlockBegin *sux = block->sux_at(i);

  1061       BlockBegin *pred = NULL;

  1062       for (int j=0; j<sux->number_of_preds(); j++) {

  1063         BlockBegin *cur = sux->pred_at(j);

  1064         assert(cur != NULL, "Predecessor must not be null");

  1065         if (!pred) {

  1066           pred = cur;

  1067         }

  1068         assert(cur == pred, "Block must not have more than one predecessor if its predecessor has more than one successor");

  1069       }

  1070       assert(sux->number_of_preds() >= 1, "Block must have at least one predecessor");

  1071       assert(sux->pred_at(0) == block, "Wrong successor");

  1072     }

  1073   }

  1074 

  1075   BlockBegin *dominator = block->dominator();

  1076   if (dominator) {

  1077     assert(block != _ir->start(), "Start block must not have a dominator!");

  1078     assert(can_reach(dominator, block), "Dominator can't reach his block !");

  1079     assert(can_reach(_ir->start(), dominator), "Dominator is unreachable !");

  1080     assert(!can_reach(_ir->start(), block, dominator), "Wrong dominator ! Block can be reached anyway !");

  1081     BlockList *all_blocks = _ir->linear_scan_order();

  1082     for (int i=0; i<all_blocks->length(); i++) {

  1083       BlockBegin *cur = all_blocks->at(i);

  1084       if (cur != dominator && cur != block) {

  1085         assert(can_reach(dominator, block, cur), "There has to be another dominator!");

  1086       }

  1087     }

  1088   } else {

  1089     assert(block == _ir->start(), "Only start block must not have a dominator");

  1090   }

  1091 

  1092   if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) {

  1093     int loop_index = block->loop_index();

  1094     BlockList *all_blocks = _ir->linear_scan_order();

  1095     assert(block->number_of_preds() >= 1, "Block must have at least one predecessor");

  1096     assert(!block->is_set(BlockBegin::exception_entry_flag), "Loop header must not be exception handler!");

  1097     // Sometimes, the backbranch comes from an exception handler. In

  1098     // this case, loop indexes/loop depths may not appear correct.

  1099     bool loop_through_xhandler = false;

  1100     for (int i = 0; i < block->number_of_exception_handlers(); i++) {

  1101       BlockBegin *xhandler = block->exception_handler_at(i);

  1102       for (int j = 0; j < block->number_of_preds(); j++) {

  1103         if (dominates(xhandler, block->pred_at(j)) || xhandler == block->pred_at(j)) {

  1104           loop_through_xhandler = true;

  1105         }

  1106       }

  1107     }

  1108 

  1109     for (int i=0; i<block->number_of_sux(); i++) {

  1110       BlockBegin *sux = block->sux_at(i);

  1111       assert(sux->loop_depth() != block->loop_depth() || sux->loop_index() == block->loop_index() || loop_through_xhandler, "Loop index has to be same");

  1112       assert(sux->loop_depth() == block->loop_depth() || sux->loop_index() != block->loop_index(), "Loop index has to be different");

  1113     }

  1114 

  1115     for (int i=0; i<all_blocks->length(); i++) {

  1116       BlockBegin *cur = all_blocks->at(i);

  1117       if (cur->loop_index() == loop_index && cur != block) {

  1118         assert(dominates(block->dominator(), cur), "Dominator of loop header must dominate all loop blocks");

  1119       }

  1120     }

  1121   }

  1122 

  1123   Instruction *cur = block;

  1124   while (cur) {

  1125     assert(cur->block() == block, "Block begin has to be set correctly!");

  1126     cur = cur->next();

  1127   }

  1128 }

  1129 

  1130 // Loop header must dominate all loop blocks

  1131 bool RangeCheckEliminator::Verification::dominates(BlockBegin *dominator, BlockBegin *block) {

  1132   BlockBegin *cur = block->dominator();

  1133   while (cur && cur != dominator) {

  1134     cur = cur->dominator();

  1135   }