1 /*

     2  * Copyright (c) 2012, 2016, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.

     8  *

     9  * This code is distributed in the hope that it will be useful, but WITHOUT

    10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    12  * version 2 for more details (a copy is included in the LICENSE file that

    13  * accompanied this code).

    14  *

    15  * You should have received a copy of the GNU General Public License version

    16  * 2 along with this work; if not, write to the Free Software Foundation,

    17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    18  *

    19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    20  * or visit www.oracle.com if you need additional information or have any

    21  * questions.

    22  *

    23  */

    24 

    25 #include "precompiled.hpp"

    26 #include "c1/c1_ValueStack.hpp"

    27 #include "c1/c1_RangeCheckElimination.hpp"

    28 #include "c1/c1_IR.hpp"

    29 #include "c1/c1_Canonicalizer.hpp"

    30 #include "c1/c1_ValueMap.hpp"

    31 #include "ci/ciMethodData.hpp"

    32 #include "runtime/deoptimization.hpp"

    33 

    34 // Macros for the Trace and the Assertion flag

    35 #ifdef ASSERT

    36 #define TRACE_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination) { code; }

    37 #define ASSERT_RANGE_CHECK_ELIMINATION(code) if (AssertRangeCheckElimination) { code; }

    38 #define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination || AssertRangeCheckElimination) { code; }

    39 #else

    40 #define TRACE_RANGE_CHECK_ELIMINATION(code)

    41 #define ASSERT_RANGE_CHECK_ELIMINATION(code)

    42 #define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code)

    43 #endif

    44 

    45 // Entry point for the optimization

    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(), Instruction::number_of_instructions(), NULL),

    57   _access_indexed_info(Instruction::number_of_instructions(), Instruction::number_of_instructions(), NULL)

    58 {

    59   _visitor.set_range_check_eliminator(this);

    60   _ir = ir;

    61   _number_of_instructions = Instruction::number_of_instructions();

    62   _optimistic = ir->compilation()->is_optimistic();

    63 

    64   TRACE_RANGE_CHECK_ELIMINATION(

    65     tty->cr();

    66     tty->print_cr("Range check elimination");

    67     ir->method()->print_name(tty);

    68     tty->cr();

    69   );

    70 

    71   TRACE_RANGE_CHECK_ELIMINATION(

    72     tty->print_cr("optimistic=%d", (int)_optimistic);

    73   );

    74 

    75 #ifdef ASSERT

    76   // Verifies several conditions that must be true on the IR-input. Only used for debugging purposes.

    77   TRACE_RANGE_CHECK_ELIMINATION(

    78     tty->print_cr("Verification of IR . . .");

    79   );

    80   Verification verification(ir);

    81 #endif

    82 

    83   // Set process block flags

    84   // Optimization so a blocks is only processed if it contains an access indexed instruction or if

    85   // one of its children in the dominator tree contains an access indexed instruction.

    86   set_process_block_flags(ir->start());

    87 

    88   // Pass over instructions in the dominator tree

    89   TRACE_RANGE_CHECK_ELIMINATION(

    90     tty->print_cr("Starting pass over dominator tree . . .")

    91   );

    92   calc_bounds(ir->start(), NULL);

    93 

    94   TRACE_RANGE_CHECK_ELIMINATION(

    95     tty->print_cr("Finished!")

    96   );

    97 }

    98 

    99 // Instruction specific work for some instructions

   100 // Constant

   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.at(v->id())) {

   307     // First (default) bound is calculated

   308     // Create BoundStack

   309     _bounds.at_put(v->id(), new BoundStack());

   310     _visitor.clear_bound();

   311     Value visit_value = v;

   312     visit_value->visit(&_visitor);

   313     Bound *bound = _visitor.bound();

   314     if (bound) {

   315       _bounds.at(v->id())->push(bound);

   316     }

   317     if (_bounds.at(v->id())->length() == 0) {

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

   319       _bounds.at(v->id())->push(new Bound());

   320     }

   321   } else if (_bounds.at(v->id())->length() == 0) {

   322     // To avoid endless loops, bound is currently in calculation -> nothing known about it

   323     return new Bound();

   324   }

   325 

   326   // Return bound

   327   return _bounds.at(v->id())->top();

   328 }

   329 

   330 // Update bound

   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.at(v->id())) {

   357     get_bound(v);

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

   359   }

   360   Bound *top = NULL;

   361   if (_bounds.at(v->id())->length() > 0) {

   362     top = _bounds.at(v->id())->top();

   363   }

   364   if (top) {

   365     bound->and_op(top);

   366   }

   367   _bounds.at(v->id())->push(bound);

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

   369 }

   370 

   371 // Add instruction + idx for in block motion

   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.at(id);

   375   if (aii == NULL) {

   376     aii = new AccessIndexedInfo();

   377     _access_indexed_info.at_put(id, aii);

   378     indices.append(instruction);

   379     aii->_min = idx;

   380     aii->_max = idx;

   381     aii->_list = new AccessIndexedList();

   382   } else if (idx >= aii->_min && idx <= aii->_max) {

   383     remove_range_check(ai);

   384     return;

   385   }

   386   aii->_min = MIN2(aii->_min, idx);

   387   aii->_max = MAX2(aii->_max, idx);

   388   aii->_list->append(ai);

   389 }

   390 

   391 // In block motion. Tries to reorder checks in order to reduce some of them.

   392 // Example:

   393 // a[i] = 0;

   394 // a[i+2] = 0;

   395 // a[i+1] = 0;

   396 // In this example the check for a[i+1] would be considered as unnecessary during the first iteration.

   397 // After this i is only checked once for i >= 0 and i+2 < a.length before the first array access. If this

   398 // check fails, deoptimization is called.

   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.at(index_instruction->id());

   465         assert(info != NULL, "Info must not be null");

   466 

   467         // if idx < 0, max > 0, max + idx may fall between 0 and

   468         // length-1 and if min < 0, min + idx may overflow and be >=

   469         // 0. The predicate wouldn't trigger but some accesses could

   470         // be with a negative index. This test guarantees that for the

   471         // min and max value that are kept the predicate can't let

   472         // some incorrect accesses happen.

   473         bool range_cond = (info->_max < 0 || info->_max + min_jint <= info->_min);

   474 

   475         // Generate code only if more than 2 range checks can be eliminated because of that.

   476         // 2 because at least 2 comparisons are done

   477         if (info->_list->length() > 2 && range_cond) {

   478           AccessIndexed *first = info->_list->at(0);

   479           Instruction *insert_position = first->prev();

   480           assert(insert_position->next() == first, "prev was calculated");

   481           ValueStack *state = first->state_before();

   482 

   483           // Load min Constant

   484           Constant *min_constant = NULL;

   485           if (info->_min != 0) {

   486             min_constant = new Constant(new IntConstant(info->_min));

   487             NOT_PRODUCT(min_constant->set_printable_bci(first->printable_bci()));

   488             insert_position = insert_position->insert_after(min_constant);

   489           }

   490 

   491           // Load max Constant

   492           Constant *max_constant = NULL;

   493           if (info->_max != 0) {

   494             max_constant = new Constant(new IntConstant(info->_max));

   495             NOT_PRODUCT(max_constant->set_printable_bci(first->printable_bci()));

   496             insert_position = insert_position->insert_after(max_constant);

   497           }

   498 

   499           // Load array length

   500           Value length_instr = first->length();

   501           if (!length_instr) {

   502             ArrayLength *length = new ArrayLength(array, first->state_before()->copy());

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

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

   505             insert_position = insert_position->insert_after_same_bci(length);

   506             length_instr = length;

   507           }

   508 

   509           // Calculate lower bound

   510           Instruction *lower_compare = index_instruction;

   511           if (min_constant) {

   512             ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, min_constant, lower_compare, false, NULL);

   513             insert_position = insert_position->insert_after_same_bci(ao);

   514             lower_compare = ao;

   515           }

   516 

   517           // Calculate upper bound

   518           Instruction *upper_compare = index_instruction;

   519           if (max_constant) {

   520             ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, max_constant, upper_compare, false, NULL);

   521             insert_position = insert_position->insert_after_same_bci(ao);

   522             upper_compare = ao;

   523           }

   524 

   525           // Trick with unsigned compare is done

   526           int bci = NOT_PRODUCT(first->printable_bci()) PRODUCT_ONLY(-1);

   527           insert_position = predicate(upper_compare, Instruction::aeq, length_instr, state, insert_position, bci);

   528           insert_position = predicate_cmp_with_const(lower_compare, Instruction::leq, -1, state, insert_position);

   529           for (int j = 0; j<info->_list->length(); j++) {

   530             AccessIndexed *ai = info->_list->at(j);

   531             remove_range_check(ai);

   532           }

   533         }

   534       }

   535 

   536       if (list_constant.length() > 1) {

   537         AccessIndexed *first = list_constant.at(0);

   538         Instruction *insert_position = first->prev();

   539         ValueStack *state = first->state_before();

   540         // Load max Constant

   541         Constant *constant = new Constant(new IntConstant(max_constant));

   542         NOT_PRODUCT(constant->set_printable_bci(first->printable_bci()));

   543         insert_position = insert_position->insert_after(constant);

   544         Instruction *compare_instr = constant;

   545         Value length_instr = first->length();

   546         if (!length_instr) {

   547           ArrayLength *length = new ArrayLength(array, state->copy());

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

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

   550           insert_position = insert_position->insert_after_same_bci(length);

   551           length_instr = length;

   552         }

   553         // Compare for greater or equal to array length

   554         insert_position = predicate(compare_instr, Instruction::geq, length_instr, state, insert_position);

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

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

   557           remove_range_check(ai);

   558         }

   559       }

   560     }

   561 

   562     // Clear data structures for next array

   563     for (int i = 0; i < indices.length(); i++) {

   564       Instruction *index_instruction = indices.at(i);

   565       _access_indexed_info.at_put(index_instruction->id(), NULL);

   566     }

   567     indices.clear();

   568   }

   569 }

   570 

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

   572   Instruction *cur = block;

   573   bool process = false;

   574 

   575   while (cur) {

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

   577     cur = cur->next();

   578   }

   579 

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

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

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

   583     process |= set_process_block_flags(next);

   584   }

   585 

   586   if (!process) {

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

   588   }

   589   return process;

   590 }

   591 

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

   593   bool upper_check = true;

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

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

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

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

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

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

   600 

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

   602     // static check

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

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

   605     upper_check = false;

   606   }

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

   608     if (lower > 0) return false;

   609   }

   610   // No upper check required -> skip

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

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

   613     // of the upper_instr.

   614     return false;

   615   }

   616   return true;

   617 }

   618 

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

   620   if (bci != -1) {

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

   622     return insert_position->insert_after(instr);

   623   } else {

   624     return insert_position->insert_after_same_bci(instr);

   625   }

   626 }

   627 

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

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

   630   return insert_after(insert_position, deoptimize, bci);

   631 }

   632 

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

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

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

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

   637 }

   638 

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

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

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

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

   643   insert_position = insert_position->insert_after_same_bci(ao);

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

   645 }

   646 

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

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

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

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

   651 }

   652 

   653 // Insert deoptimization

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

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

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

   657 

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

   659   if (lower_instr) {

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

   661     if (lower == 0) {

   662       // Compare for less than 0

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

   664     } else if (lower > 0) {

   665       // Compare for smaller 0

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

   667     } else {

   668       assert(lower < 0, "");

   669       // Add 1

   670       lower++;

   671       lower = -lower;

   672       // Compare for smaller or equal 0

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

   674     }

   675   }

   676 

   677   // No upper check required -> skip

   678   if (!upper_check) return;

   679 

   680   // We need to know length of array

   681   if (!length_instr) {

   682     // Load length if necessary

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

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

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

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

   687     insert_position = insert_position->insert_after(length);

   688     length_instr = length;

   689   }

   690 

   691   if (!upper_instr) {

   692     // Compare for geq array.length

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

   694   } else {

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

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

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

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

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

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

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

   702       insert_position = insert_position->insert_after(length);

   703       upper_instr = length;

   704     }

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

   706 

   707     if (upper == 0) {

   708       // Compare for geq array.length

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

   710     } else if (upper < 0) {

   711       // Compare for geq array.length

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

   713     } else {

   714       assert(upper > 0, "");

   715       upper = -upper;

   716       // Compare for geq array.length

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

   718     }

   719   }

   720 }

   721 

   722 // Add if condition

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

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

   725 

   726   int const_value = 0;

   727   Value instr_value = x;

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

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

   730 

   731   if (c != NULL) {

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

   733     instr_value = NULL;

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

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

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

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

   738     if (c != NULL) {

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

   740       instr_value = ao->y();

   741     } else {

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

   743       if (c != NULL) {

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

   745         instr_value = ao->x();

   746       }

   747     }

   748     if (ao->op() == Bytecodes::_isub) {

   749       assert(ao->y()->as_Constant(), "1 - x not supported, only x - 1 is valid!");

   750       if (const_value > min_jint) {

   751         const_value = -const_value;

   752       } else {

   753         const_value = 0;

   754         instr_value = x;

   755       }

   756     }

   757   }

   758 

   759   update_bound(pushed, y, condition, instr_value, const_value);

   760 }

   761 

   762 // Process If

   763 void RangeCheckEliminator::process_if(IntegerStack &pushed, BlockBegin *block, If *cond) {

   764   // Only if we are direct true / false successor and NOT both ! (even this may occur)

   765   if ((cond->tsux() == block || cond->fsux() == block) && cond->tsux() != cond->fsux()) {

   766     Instruction::Condition condition = cond->cond();

   767     if (cond->fsux() == block) {

   768       condition = Instruction::negate(condition);

   769     }

   770     Value x = cond->x();

   771     Value y = cond->y();

   772     if (x->type()->as_IntType() && y->type()->as_IntType()) {

   773       add_if_condition(pushed, y, x, condition);

   774       add_if_condition(pushed, x, y, Instruction::mirror(condition));

   775     }

   776   }

   777 }

   778 

   779 // Process access indexed

   780 void RangeCheckEliminator::process_access_indexed(BlockBegin *loop_header, BlockBegin *block, AccessIndexed *ai) {

   781   TRACE_RANGE_CHECK_ELIMINATION(

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

   783   );

   784   TRACE_RANGE_CHECK_ELIMINATION(

   785     tty->print_cr("Access indexed: index=%d length=%d", ai->index()->id(), (ai->length() != NULL ? ai->length()->id() :-1 ))

   786   );

   787 

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

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

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

   791       TRACE_RANGE_CHECK_ELIMINATION(

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

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

   794       );

   795       return;

   796     }

   797 

   798     Bound *array_bound;

   799     if (ai->length()) {

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

   801     } else {

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

   803     }

   804 

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

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

   807         TRACE_RANGE_CHECK_ELIMINATION(

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

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

   810         );

   811 

   812         remove_range_check(ai);

   813     } else if (_optimistic && loop_header) {

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

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

   816 

   817       // Array instruction

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

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

   820         TRACE_RANGE_CHECK_ELIMINATION(

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

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

   823         );

   824         return;

   825       }

   826 

   827       // Lower instruction

   828       Value index_instr = ai->index();

   829       Value lower_instr = index_bound->lower_instr();

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

   831         TRACE_RANGE_CHECK_ELIMINATION(

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

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

   834         );

   835         return;

   836       }

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

   838         TRACE_RANGE_CHECK_ELIMINATION(

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

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

   841         );

   842         return;

   843       }

   844 

   845       // Upper instruction

   846       Value upper_instr = index_bound->upper_instr();

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

   848         TRACE_RANGE_CHECK_ELIMINATION(

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

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

   851         );

   852         return;

   853       }

   854 

   855       // Length instruction

   856       Value length_instr = ai->length();

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

   858         // Generate length instruction yourself!

   859         length_instr = NULL;

   860       }

   861 

   862       TRACE_RANGE_CHECK_ELIMINATION(

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

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

   865       );

   866 

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

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

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

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

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

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

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

   874 

   875       // Add deoptimization to dominator of loop header

   876       TRACE_RANGE_CHECK_ELIMINATION(

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

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

   879       );

   880 

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

   882         TRACE_RANGE_CHECK_ELIMINATION(

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

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

   885         );

   886         return;

   887       }

   888 

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

   890 

   891       // Finally remove the range check!

   892       remove_range_check(ai);

   893     }

   894   }

   895 }

   896 

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

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

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

   900   ai->clear_length();

   901 

   902   TRACE_RANGE_CHECK_ELIMINATION(

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

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

   905   );

   906 

   907   ASSERT_RANGE_CHECK_ELIMINATION(

   908     Value array_length = ai->length();

   909     if (!array_length) {

   910       array_length = ai->array();

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

   912     }

   913     int cur_constant = -1;

   914     Value cur_value = array_length;

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

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

   917       cur_value = NULL;

   918     }

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

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

   921   );

   922 }

   923 

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

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

   926   // Ensures a valid loop_header

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

   928 

   929   // Tracing output

   930   TRACE_RANGE_CHECK_ELIMINATION(

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

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

   933   );

   934 

   935   // Pushed stack for conditions

   936   IntegerStack pushed;

   937   // Process If

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

   939   if (parent != NULL) {

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

   941     if (cond != NULL) {

   942       process_if(pushed, block, cond);

   943     }

   944   }

   945 

   946   // Interate over current block

   947   InstructionList arrays;

   948   AccessIndexedList accessIndexed;

   949   Instruction *cur = block;

   950 

   951   while (cur) {

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

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

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

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

   956       if (ai != NULL) {

   957         process_access_indexed(loop_header, block, ai);

   958         accessIndexed.append(ai);

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

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

   961         }

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

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

   964           // Lower bound is constant

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

   966         }

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

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

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

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

   971           } else {

   972             // Has no upper bound

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

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

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

   976           }

   977         }

   978       }

   979     }

   980     cur = cur->next();

   981   }

   982 

   983   // Output current condition stack

   984   TRACE_RANGE_CHECK_ELIMINATION(dump_condition_stack(block));

   985 

   986   // Do in block motion of range checks

   987   in_block_motion(block, accessIndexed, arrays);

   988 

   989   // Call all dominated blocks

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

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

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

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

   994       // - next block belongs to the same loop

   995       // or

   996       // - next block belongs to an inner loop

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

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

   999         calc_bounds(next, block);

  1000       } else {

  1001         calc_bounds(next, loop_header);

  1002       }

  1003     }

  1004   }

  1005 

  1006   // Reset stack

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

  1008     _bounds.at(pushed.at(i))->pop();

  1009   }

  1010 }

  1011 

  1012 #ifndef PRODUCT

  1013 // Dump condition stack

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

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

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

  1017     Instruction *instr = cur_block;

  1018     for_each_phi_fun(cur_block, phi,

  1019                      BoundStack *bound_stack = _bounds.at(phi->id());

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

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

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

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

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

  1025                                                          tty->print(": ");

  1026                                                          bound->print();

  1027                                                          tty->cr();

  1028                            );

  1029                          }

  1030                      });

  1031 

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

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

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

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

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

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

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

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

  1040                                             tty->print(": ");

  1041                                             bound->print();

  1042                                             tty->cr();

  1043               );

  1044           }

  1045         }

  1046       }

  1047       instr = instr->next();

  1048     }

  1049   }

  1050 }

  1051 #endif

  1052 

  1053 // Verification or the IR

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

  1055   this->_ir = ir;

  1056   ir->iterate_linear_scan_order(this);

  1057 }

  1058 

  1059 // Verify this block

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

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

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

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

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

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

  1066       BlockBegin *pred = NULL;

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

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

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

  1070         if (!pred) {

  1071           pred = cur;

  1072         }

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

  1074       }

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

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

  1077     }

  1078   }

  1079 

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

  1081   if (dominator) {

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

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

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

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

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

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

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

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

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

  1091       }

  1092     }

  1093   } else {

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

  1095   }

  1096 

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

  1098     int loop_index = block->loop_index();

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

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

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

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

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

  1104     bool loop_through_xhandler = false;

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

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

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

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

  1109           loop_through_xhandler = true;

  1110         }

  1111       }

  1112     }

  1113 

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

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

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

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

  1118     }

  1119 

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

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

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

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

  1124       }

  1125     }

  1126   }

  1127 

  1128   Instruction *cur = block;

  1129   while (cur) {

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

  1131     cur = cur->next();

  1132   }

  1133 }

  1134 

  1135 // Loop header must dominate all loop blocks