diff -r 806d87cb0cc7 -r 6807a703dd6b hotspot/src/share/vm/c1/c1_RangeCheckElimination.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/hotspot/src/share/vm/c1/c1_RangeCheckElimination.cpp Thu Mar 21 09:27:54 2013 +0100 @@ -0,0 +1,1517 @@ +/* + * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + * + */ + +#include "precompiled.hpp" +#include "c1/c1_ValueStack.hpp" +#include "c1/c1_RangeCheckElimination.hpp" +#include "c1/c1_IR.hpp" +#include "c1/c1_Canonicalizer.hpp" +#include "c1/c1_ValueMap.hpp" +#include "ci/ciMethodData.hpp" +#include "runtime/deoptimization.hpp" + +// Macros for the Trace and the Assertion flag +#ifdef ASSERT +#define TRACE_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination) { code; } +#define ASSERT_RANGE_CHECK_ELIMINATION(code) if (AssertRangeCheckElimination) { code; } +#define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination || AssertRangeCheckElimination) { code; } +#else +#define TRACE_RANGE_CHECK_ELIMINATION(code) +#define ASSERT_RANGE_CHECK_ELIMINATION(code) +#define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code) +#endif + +// Entry point for the optimization +void RangeCheckElimination::eliminate(IR *ir) { + bool do_elimination = ir->compilation()->has_access_indexed(); + ASSERT_RANGE_CHECK_ELIMINATION(do_elimination = true); + if (do_elimination) { + RangeCheckEliminator rce(ir); + } +} + +// Constructor +RangeCheckEliminator::RangeCheckEliminator(IR *ir) : + _bounds(Instruction::number_of_instructions(), NULL), + _access_indexed_info(Instruction::number_of_instructions(), NULL) +{ + _visitor.set_range_check_eliminator(this); + _ir = ir; + _number_of_instructions = Instruction::number_of_instructions(); + _optimistic = ir->compilation()->is_optimistic(); + + TRACE_RANGE_CHECK_ELIMINATION( + tty->print_cr(""); + tty->print_cr("Range check elimination"); + ir->method()->print_name(tty); + tty->print_cr(""); + ); + + TRACE_RANGE_CHECK_ELIMINATION( + tty->print_cr("optimistic=%d", (int)_optimistic); + ); + +#ifdef ASSERT + // Verifies several conditions that must be true on the IR-input. Only used for debugging purposes. + TRACE_RANGE_CHECK_ELIMINATION( + tty->print_cr("Verification of IR . . ."); + ); + Verification verification(ir); +#endif + + // Set process block flags + // Optimization so a blocks is only processed if it contains an access indexed instruction or if + // one of its children in the dominator tree contains an access indexed instruction. + set_process_block_flags(ir->start()); + + // Pass over instructions in the dominator tree + TRACE_RANGE_CHECK_ELIMINATION( + tty->print_cr("Starting pass over dominator tree . . .") + ); + calc_bounds(ir->start(), NULL); + + TRACE_RANGE_CHECK_ELIMINATION( + tty->print_cr("Finished!") + ); +} + +// Instruction specific work for some instructions +// Constant +void RangeCheckEliminator::Visitor::do_Constant(Constant *c) { + IntConstant *ic = c->type()->as_IntConstant(); + if (ic != NULL) { + int value = ic->value(); + _bound = new Bound(value, NULL, value, NULL); + } +} + +// LogicOp +void RangeCheckEliminator::Visitor::do_LogicOp(LogicOp *lo) { + if (lo->type()->as_IntType() && lo->op() == Bytecodes::_iand && (lo->x()->as_Constant() || lo->y()->as_Constant())) { + int constant = 0; + Constant *c = lo->x()->as_Constant(); + if (c != NULL) { + constant = c->type()->as_IntConstant()->value(); + } else { + constant = lo->y()->as_Constant()->type()->as_IntConstant()->value(); + } + if (constant >= 0) { + _bound = new Bound(0, NULL, constant, NULL); + } + } +} + +// Phi +void RangeCheckEliminator::Visitor::do_Phi(Phi *phi) { + if (!phi->type()->as_IntType() && !phi->type()->as_ObjectType()) return; + + BlockBegin *block = phi->block(); + int op_count = phi->operand_count(); + bool has_upper = true; + bool has_lower = true; + assert(phi, "Phi must not be null"); + Bound *bound = NULL; + + // TODO: support more difficult phis + for (int i=0; ioperand_at(i); + + if (v == phi) continue; + + // Check if instruction is connected with phi itself + Op2 *op2 = v->as_Op2(); + if (op2 != NULL) { + Value x = op2->x(); + Value y = op2->y(); + if ((x == phi || y == phi)) { + Value other = x; + if (other == phi) { + other = y; + } + ArithmeticOp *ao = v->as_ArithmeticOp(); + if (ao != NULL && ao->op() == Bytecodes::_iadd) { + assert(ao->op() == Bytecodes::_iadd, "Has to be add!"); + if (ao->type()->as_IntType()) { + Constant *c = other->as_Constant(); + if (c != NULL) { + assert(c->type()->as_IntConstant(), "Constant has to be of type integer"); + int value = c->type()->as_IntConstant()->value(); + if (value == 1) { + has_upper = false; + } else if (value > 1) { + // Overflow not guaranteed + has_upper = false; + has_lower = false; + } else if (value < 0) { + has_lower = false; + } + continue; + } + } + } + } + } + + // No connection -> new bound + Bound *v_bound = _rce->get_bound(v); + Bound *cur_bound; + int cur_constant = 0; + Value cur_value = v; + + if (v->type()->as_IntConstant()) { + cur_constant = v->type()->as_IntConstant()->value(); + cur_value = NULL; + } + if (!v_bound->has_upper() || !v_bound->has_lower()) { + cur_bound = new Bound(cur_constant, cur_value, cur_constant, cur_value); + } else { + cur_bound = v_bound; + } + if (cur_bound) { + if (!bound) { + bound = cur_bound->copy(); + } else { + bound->or_op(cur_bound); + } + } else { + // No bound! + bound = NULL; + break; + } + } + + if (bound) { + if (!has_upper) { + bound->remove_upper(); + } + if (!has_lower) { + bound->remove_lower(); + } + _bound = bound; + } else { + _bound = new Bound(); + } +} + + +// ArithmeticOp +void RangeCheckEliminator::Visitor::do_ArithmeticOp(ArithmeticOp *ao) { + Value x = ao->x(); + Value y = ao->y(); + + if (ao->op() == Bytecodes::_irem) { + Bound* x_bound = _rce->get_bound(x); + Bound* y_bound = _rce->get_bound(y); + if (x_bound->lower() >= 0 && x_bound->lower_instr() == NULL && y->as_ArrayLength() != NULL) { + _bound = new Bound(0, NULL, -1, y); + } else { + _bound = new Bound(); + } + } else if (!x->as_Constant() || !y->as_Constant()) { + assert(!x->as_Constant() || !y->as_Constant(), "One of the operands must be non-constant!"); + if (((x->as_Constant() || y->as_Constant()) && (ao->op() == Bytecodes::_iadd)) || (y->as_Constant() && ao->op() == Bytecodes::_isub)) { + assert(ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub, "Operand must be iadd or isub"); + + if (y->as_Constant()) { + Value tmp = x; + x = y; + y = tmp; + } + assert(x->as_Constant()->type()->as_IntConstant(), "Constant must be int constant!"); + + // Constant now in x + int const_value = x->as_Constant()->type()->as_IntConstant()->value(); + if (ao->op() == Bytecodes::_iadd || const_value != min_jint) { + if (ao->op() == Bytecodes::_isub) { + const_value = -const_value; + } + + Bound * bound = _rce->get_bound(y); + if (bound->has_upper() && bound->has_lower()) { + int new_lower = bound->lower() + const_value; + jlong new_lowerl = ((jlong)bound->lower()) + const_value; + int new_upper = bound->upper() + const_value; + jlong new_upperl = ((jlong)bound->upper()) + const_value; + + if (((jlong)new_lower) == new_lowerl && ((jlong)new_upper == new_upperl)) { + Bound *newBound = new Bound(new_lower, bound->lower_instr(), new_upper, bound->upper_instr()); + _bound = newBound; + } else { + // overflow + _bound = new Bound(); + } + } else { + _bound = new Bound(); + } + } else { + _bound = new Bound(); + } + } else { + Bound *bound = _rce->get_bound(x); + if (ao->op() == Bytecodes::_isub) { + if (bound->lower_instr() == y) { + _bound = new Bound(Instruction::geq, NULL, bound->lower()); + } else { + _bound = new Bound(); + } + } else { + _bound = new Bound(); + } + } + } +} + +// IfOp +void RangeCheckEliminator::Visitor::do_IfOp(IfOp *ifOp) +{ + if (ifOp->tval()->type()->as_IntConstant() && ifOp->fval()->type()->as_IntConstant()) { + int min = ifOp->tval()->type()->as_IntConstant()->value(); + int max = ifOp->fval()->type()->as_IntConstant()->value(); + if (min > max) { + // min ^= max ^= min ^= max; + int tmp = min; + min = max; + max = tmp; + } + _bound = new Bound(min, NULL, max, NULL); + } +} + +// Get bound. Returns the current bound on Value v. Normally this is the topmost element on the bound stack. +RangeCheckEliminator::Bound *RangeCheckEliminator::get_bound(Value v) { + // Wrong type or NULL -> No bound + if (!v || (!v->type()->as_IntType() && !v->type()->as_ObjectType())) return NULL; + + if (!_bounds[v->id()]) { + // First (default) bound is calculated + // Create BoundStack + _bounds[v->id()] = new BoundStack(); + _visitor.clear_bound(); + Value visit_value = v; + visit_value->visit(&_visitor); + Bound *bound = _visitor.bound(); + if (bound) { + _bounds[v->id()]->push(bound); + } + if (_bounds[v->id()]->length() == 0) { + assert(!(v->as_Constant() && v->type()->as_IntConstant()), "constants not handled here"); + _bounds[v->id()]->push(new Bound()); + } + } else if (_bounds[v->id()]->length() == 0) { + // To avoid endless loops, bound is currently in calculation -> nothing known about it + return new Bound(); + } + + // Return bound + return _bounds[v->id()]->top(); +} + +// Update bound +void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Instruction::Condition cond, Value value, int constant) { + if (cond == Instruction::gtr) { + cond = Instruction::geq; + constant++; + } else if (cond == Instruction::lss) { + cond = Instruction::leq; + constant--; + } + Bound *bound = new Bound(cond, value, constant); + update_bound(pushed, v, bound); +} + +// Checks for loop invariance. Returns true if the instruction is outside of the loop which is identified by loop_header. +bool RangeCheckEliminator::loop_invariant(BlockBegin *loop_header, Instruction *instruction) { + assert(loop_header, "Loop header must not be null!"); + if (!instruction) return true; + return instruction->dominator_depth() < loop_header->dominator_depth(); +} + +// Update bound. Pushes a new bound onto the stack. Tries to do a conjunction with the current bound. +void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Bound *bound) { + if (v->as_Constant()) { + // No bound update for constants + return; + } + if (!_bounds[v->id()]) { + get_bound(v); + assert(_bounds[v->id()], "Now Stack must exist"); + } + Bound *top = NULL; + if (_bounds[v->id()]->length() > 0) { + top = _bounds[v->id()]->top(); + } + if (top) { + bound->and_op(top); + } + _bounds[v->id()]->push(bound); + pushed.append(v->id()); +} + +// Add instruction + idx for in block motion +void RangeCheckEliminator::add_access_indexed_info(InstructionList &indices, int idx, Value instruction, AccessIndexed *ai) { + int id = instruction->id(); + AccessIndexedInfo *aii = _access_indexed_info[id]; + if (aii == NULL) { + aii = new AccessIndexedInfo(); + _access_indexed_info[id] = aii; + indices.append(instruction); + aii->_min = idx; + aii->_max = idx; + aii->_list = new AccessIndexedList(); + } else if (idx >= aii->_min && idx <= aii->_max) { + remove_range_check(ai); + return; + } + aii->_min = MIN2(aii->_min, idx); + aii->_max = MAX2(aii->_max, idx); + aii->_list->append(ai); +} + +// In block motion. Tries to reorder checks in order to reduce some of them. +// Example: +// a[i] = 0; +// a[i+2] = 0; +// a[i+1] = 0; +// In this example the check for a[i+1] would be considered as unnecessary during the first iteration. +// After this i is only checked once for i >= 0 and i+2 < a.length before the first array access. If this +// check fails, deoptimization is called. +void RangeCheckEliminator::in_block_motion(BlockBegin *block, AccessIndexedList &accessIndexed, InstructionList &arrays) { + InstructionList indices; + + // Now iterate over all arrays + for (int i=0; iarray() != array || !ai->check_flag(Instruction::NeedsRangeCheckFlag)) continue; + + Value index = ai->index(); + Constant *c = index->as_Constant(); + if (c != NULL) { + int constant_value = c->type()->as_IntConstant()->value(); + if (constant_value >= 0) { + if (constant_value <= max_constant) { + // No range check needed for this + remove_range_check(ai); + } else { + max_constant = constant_value; + list_constant.append(ai); + } + } + } else { + int last_integer = 0; + Instruction *last_instruction = index; + int base = 0; + ArithmeticOp *ao = index->as_ArithmeticOp(); + + while (ao != NULL && (ao->x()->as_Constant() || ao->y()->as_Constant()) && (ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub)) { + c = ao->y()->as_Constant(); + Instruction *other = ao->x(); + if (!c && ao->op() == Bytecodes::_iadd) { + c = ao->x()->as_Constant(); + other = ao->y(); + } + + if (c) { + int value = c->type()->as_IntConstant()->value(); + if (value != min_jint) { + if (ao->op() == Bytecodes::_isub) { + value = -value; + } + base += value; + last_integer = base; + last_instruction = other; + } + index = other; + } else { + break; + } + ao = index->as_ArithmeticOp(); + } + add_access_indexed_info(indices, last_integer, last_instruction, ai); + } + } + + // Iterate over all different indices + if (_optimistic) { + for (int i=0; iid()]; + assert(info != NULL, "Info must not be null"); + + // if idx < 0, max > 0, max + idx may fall between 0 and + // length-1 and if min < 0, min + idx may overflow and be >= + // 0. The predicate wouldn't trigger but some accesses could + // be with a negative index. This test guarantees that for the + // min and max value that are kept the predicate can't let + // some incorrect accesses happen. + bool range_cond = (info->_max < 0 || info->_max + min_jint <= info->_min); + + // Generate code only if more than 2 range checks can be eliminated because of that. + // 2 because at least 2 comparisons are done + if (info->_list->length() > 2 && range_cond) { + AccessIndexed *first = info->_list->at(0); + Instruction *insert_position = first->prev(); + assert(insert_position->next() == first, "prev was calculated"); + ValueStack *state = first->state_before(); + + // Load min Constant + Constant *min_constant = NULL; + if (info->_min != 0) { + min_constant = new Constant(new IntConstant(info->_min)); + NOT_PRODUCT(min_constant->set_printable_bci(first->printable_bci())); + insert_position = insert_position->insert_after(min_constant); + } + + // Load max Constant + Constant *max_constant = NULL; + if (info->_max != 0) { + max_constant = new Constant(new IntConstant(info->_max)); + NOT_PRODUCT(max_constant->set_printable_bci(first->printable_bci())); + insert_position = insert_position->insert_after(max_constant); + } + + // Load array length + Value length_instr = first->length(); + if (!length_instr) { + ArrayLength *length = new ArrayLength(array, first->state_before()->copy()); + length->set_exception_state(length->state_before()); + length->set_flag(Instruction::DeoptimizeOnException, true); + insert_position = insert_position->insert_after_same_bci(length); + length_instr = length; + } + + // Calculate lower bound + Instruction *lower_compare = index_instruction; + if (min_constant) { + ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, min_constant, lower_compare, false, NULL); + insert_position = insert_position->insert_after_same_bci(ao); + lower_compare = ao; + } + + // Calculate upper bound + Instruction *upper_compare = index_instruction; + if (max_constant) { + ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, max_constant, upper_compare, false, NULL); + insert_position = insert_position->insert_after_same_bci(ao); + upper_compare = ao; + } + + // Trick with unsigned compare is done + int bci = NOT_PRODUCT(first->printable_bci()) PRODUCT_ONLY(-1); + insert_position = predicate(upper_compare, Instruction::aeq, length_instr, state, insert_position, bci); + insert_position = predicate_cmp_with_const(lower_compare, Instruction::leq, -1, state, insert_position); + for (int j = 0; j_list->length(); j++) { + AccessIndexed *ai = info->_list->at(j); + remove_range_check(ai); + } + } + _access_indexed_info[index_instruction->id()] = NULL; + } + indices.clear(); + + if (list_constant.length() > 1) { + AccessIndexed *first = list_constant.at(0); + Instruction *insert_position = first->prev(); + ValueStack *state = first->state_before(); + // Load max Constant + Constant *constant = new Constant(new IntConstant(max_constant)); + NOT_PRODUCT(constant->set_printable_bci(first->printable_bci())); + insert_position = insert_position->insert_after(constant); + Instruction *compare_instr = constant; + Value length_instr = first->length(); + if (!length_instr) { + ArrayLength *length = new ArrayLength(array, state->copy()); + length->set_exception_state(length->state_before()); + length->set_flag(Instruction::DeoptimizeOnException, true); + insert_position = insert_position->insert_after_same_bci(length); + length_instr = length; + } + // Compare for greater or equal to array length + insert_position = predicate(compare_instr, Instruction::geq, length_instr, state, insert_position); + for (int j = 0; jas_AccessIndexed() != NULL); + cur = cur->next(); + } + + BlockList *dominates = block->dominates(); + for (int i=0; ilength(); i++) { + BlockBegin *next = dominates->at(i); + process |= set_process_block_flags(next); + } + + if (!process) { + block->set(BlockBegin::donot_eliminate_range_checks); + } + return process; +} + +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) { + bool upper_check = true; + assert(lower_instr || lower >= 0, "If no lower_instr present, lower must be greater 0"); + assert(!lower_instr || lower_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller"); + assert(!upper_instr || upper_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller"); + assert(array_instr, "Array instruction must exist"); + assert(array_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller"); + assert(!length_instr || length_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller"); + + if (upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr) { + // static check + if (upper >= 0) return false; // would always trigger a deopt: + // array_length + x >= array_length, x >= 0 is always true + upper_check = false; + } + if (lower_instr && lower_instr->as_ArrayLength() && lower_instr->as_ArrayLength()->array() == array_instr) { + if (lower > 0) return false; + } + // No upper check required -> skip + if (upper_check && upper_instr && upper_instr->type()->as_ObjectType() && upper_instr == array_instr) { + // upper_instr is object means that the upper bound is the length + // of the upper_instr. + return false; + } + return true; +} + +Instruction* RangeCheckEliminator::insert_after(Instruction* insert_position, Instruction* instr, int bci) { + if (bci != -1) { + NOT_PRODUCT(instr->set_printable_bci(bci)); + return insert_position->insert_after(instr); + } else { + return insert_position->insert_after_same_bci(instr); + } +} + +Instruction* RangeCheckEliminator::predicate(Instruction* left, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) { + RangeCheckPredicate *deoptimize = new RangeCheckPredicate(left, cond, true, right, state->copy()); + return insert_after(insert_position, deoptimize, bci); +} + +Instruction* RangeCheckEliminator::predicate_cmp_with_const(Instruction* instr, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) { + Constant *const_instr = new Constant(new IntConstant(constant)); + insert_position = insert_after(insert_position, const_instr, bci); + return predicate(instr, cond, const_instr, state, insert_position); +} + +Instruction* RangeCheckEliminator::predicate_add(Instruction* left, int left_const, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) { + Constant *constant = new Constant(new IntConstant(left_const)); + insert_position = insert_after(insert_position, constant, bci); + ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, left, false, NULL); + insert_position = insert_position->insert_after_same_bci(ao); + return predicate(ao, cond, right, state, insert_position); +} + +Instruction* RangeCheckEliminator::predicate_add_cmp_with_const(Instruction* left, int left_const, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) { + Constant *const_instr = new Constant(new IntConstant(constant)); + insert_position = insert_after(insert_position, const_instr, bci); + return predicate_add(left, left_const, cond, const_instr, state, insert_position); +} + +// Insert deoptimization, returns true if sucessful or false if range check should not be removed +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) { + assert(is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, lower, upper_instr, upper), "should have been tested before"); + bool upper_check = !(upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr); + + int bci = NOT_PRODUCT(ai->printable_bci()) PRODUCT_ONLY(-1); + if (lower_instr) { + assert(!lower_instr->type()->as_ObjectType(), "Must not be object type"); + if (lower == 0) { + // Compare for less than 0 + insert_position = predicate_cmp_with_const(lower_instr, Instruction::lss, 0, state, insert_position, bci); + } else if (lower > 0) { + // Compare for smaller 0 + insert_position = predicate_add_cmp_with_const(lower_instr, lower, Instruction::lss, 0, state, insert_position, bci); + } else { + assert(lower < 0, ""); + // Add 1 + lower++; + lower = -lower; + // Compare for smaller or equal 0 + insert_position = predicate_cmp_with_const(lower_instr, Instruction::leq, lower, state, insert_position, bci); + } + } + + // We need to know length of array + if (!length_instr) { + // Load length if necessary + ArrayLength *length = new ArrayLength(array_instr, state->copy()); + NOT_PRODUCT(length->set_printable_bci(ai->printable_bci())); + length->set_exception_state(length->state_before()); + length->set_flag(Instruction::DeoptimizeOnException, true); + insert_position = insert_position->insert_after(length); + length_instr = length; + } + + // No upper check required -> skip + if (!upper_check) return; + + if (!upper_instr) { + // Compare for geq array.length + insert_position = predicate_cmp_with_const(length_instr, Instruction::leq, upper, state, insert_position, bci); + } else { + if (upper_instr->type()->as_ObjectType()) { + assert(state, "must not be null"); + assert(upper_instr != array_instr, "should be"); + ArrayLength *length = new ArrayLength(upper_instr, state->copy()); + NOT_PRODUCT(length->set_printable_bci(ai->printable_bci())); + length->set_flag(Instruction::DeoptimizeOnException, true); + length->set_exception_state(length->state_before()); + insert_position = insert_position->insert_after(length); + upper_instr = length; + } + assert(upper_instr->type()->as_IntType(), "Must not be object type!"); + + if (upper == 0) { + // Compare for geq array.length + insert_position = predicate(upper_instr, Instruction::geq, length_instr, state, insert_position, bci); + } else if (upper < 0) { + // Compare for geq array.length + insert_position = predicate_add(upper_instr, upper, Instruction::geq, length_instr, state, insert_position, bci); + } else { + assert(upper > 0, ""); + upper = -upper; + // Compare for geq array.length + insert_position = predicate_add(length_instr, upper, Instruction::leq, upper_instr, state, insert_position, bci); + } + } +} + +// Add if condition +void RangeCheckEliminator::add_if_condition(IntegerStack &pushed, Value x, Value y, Instruction::Condition condition) { + if (y->as_Constant()) return; + + int const_value = 0; + Value instr_value = x; + Constant *c = x->as_Constant(); + ArithmeticOp *ao = x->as_ArithmeticOp(); + + if (c != NULL) { + const_value = c->type()->as_IntConstant()->value(); + instr_value = NULL; + } else if (ao != NULL && (!ao->x()->as_Constant() || !ao->y()->as_Constant()) && ((ao->op() == Bytecodes::_isub && ao->y()->as_Constant()) || ao->op() == Bytecodes::_iadd)) { + assert(!ao->x()->as_Constant() || !ao->y()->as_Constant(), "At least one operator must be non-constant!"); + assert(ao->op() == Bytecodes::_isub || ao->op() == Bytecodes::_iadd, "Operation has to be add or sub!"); + c = ao->x()->as_Constant(); + if (c != NULL) { + const_value = c->type()->as_IntConstant()->value(); + instr_value = ao->y(); + } else { + c = ao->y()->as_Constant(); + if (c != NULL) { + const_value = c->type()->as_IntConstant()->value(); + instr_value = ao->x(); + } + } + if (ao->op() == Bytecodes::_isub) { + assert(ao->y()->as_Constant(), "1 - x not supported, only x - 1 is valid!"); + if (const_value > min_jint) { + const_value = -const_value; + } else { + const_value = 0; + instr_value = x; + } + } + } + + update_bound(pushed, y, condition, instr_value, const_value); +} + +// Process If +void RangeCheckEliminator::process_if(IntegerStack &pushed, BlockBegin *block, If *cond) { + // Only if we are direct true / false successor and NOT both ! (even this may occur) + if ((cond->tsux() == block || cond->fsux() == block) && cond->tsux() != cond->fsux()) { + Instruction::Condition condition = cond->cond(); + if (cond->fsux() == block) { + condition = Instruction::negate(condition); + } + Value x = cond->x(); + Value y = cond->y(); + if (x->type()->as_IntType() && y->type()->as_IntType()) { + add_if_condition(pushed, y, x, condition); + add_if_condition(pushed, x, y, Instruction::mirror(condition)); + } + } +} + +// Process access indexed +void RangeCheckEliminator::process_access_indexed(BlockBegin *loop_header, BlockBegin *block, AccessIndexed *ai) { + TRACE_RANGE_CHECK_ELIMINATION( + tty->fill_to(block->dominator_depth()*2) + ); + TRACE_RANGE_CHECK_ELIMINATION( + tty->print_cr("Access indexed: index=%d length=%d", ai->index()->id(), ai->length()->id()) + ); + + if (ai->check_flag(Instruction::NeedsRangeCheckFlag)) { + Bound *index_bound = get_bound(ai->index()); + if (!index_bound->has_lower() || !index_bound->has_upper()) { + TRACE_RANGE_CHECK_ELIMINATION( + tty->fill_to(block->dominator_depth()*2); + tty->print_cr("Index instruction %d has no lower and/or no upper bound!", ai->index()->id()) + ); + return; + } + + Bound *array_bound; + if (ai->length()) { + array_bound = get_bound(ai->length()); + } else { + array_bound = get_bound(ai->array()); + } + + if (in_array_bound(index_bound, ai->array()) || + (index_bound && array_bound && index_bound->is_smaller(array_bound) && !index_bound->lower_instr() && index_bound->lower() >= 0)) { + TRACE_RANGE_CHECK_ELIMINATION( + tty->fill_to(block->dominator_depth()*2); + tty->print_cr("Bounds check for instruction %d in block B%d can be fully eliminated!", ai->id(), ai->block()->block_id()) + ); + + remove_range_check(ai); + } else if (_optimistic && loop_header) { + assert(ai->array(), "Array must not be null!"); + assert(ai->index(), "Index must not be null!"); + + // Array instruction + Instruction *array_instr = ai->array(); + if (!loop_invariant(loop_header, array_instr)) { + TRACE_RANGE_CHECK_ELIMINATION( + tty->fill_to(block->dominator_depth()*2); + tty->print_cr("Array %d is not loop invariant to header B%d", ai->array()->id(), loop_header->block_id()) + ); + return; + } + + // Lower instruction + Value index_instr = ai->index(); + Value lower_instr = index_bound->lower_instr(); + if (!loop_invariant(loop_header, lower_instr)) { + TRACE_RANGE_CHECK_ELIMINATION( + tty->fill_to(block->dominator_depth()*2); + tty->print_cr("Lower instruction %d not loop invariant!", lower_instr->id()) + ); + return; + } + if (!lower_instr && index_bound->lower() < 0) { + TRACE_RANGE_CHECK_ELIMINATION( + tty->fill_to(block->dominator_depth()*2); + tty->print_cr("Lower bound smaller than 0 (%d)!", index_bound->lower()) + ); + return; + } + + // Upper instruction + Value upper_instr = index_bound->upper_instr(); + if (!loop_invariant(loop_header, upper_instr)) { + TRACE_RANGE_CHECK_ELIMINATION( + tty->fill_to(block->dominator_depth()*2); + tty->print_cr("Upper instruction %d not loop invariant!", upper_instr->id()) + ); + return; + } + + // Length instruction + Value length_instr = ai->length(); + if (!loop_invariant(loop_header, length_instr)) { + // Generate length instruction yourself! + length_instr = NULL; + } + + TRACE_RANGE_CHECK_ELIMINATION( + tty->fill_to(block->dominator_depth()*2); + tty->print_cr("LOOP INVARIANT access indexed %d found in block B%d!", ai->id(), ai->block()->block_id()) + ); + + BlockBegin *pred_block = loop_header->dominator(); + assert(pred_block != NULL, "Every loop header has a dominator!"); + BlockEnd *pred_block_end = pred_block->end(); + Instruction *insert_position = pred_block_end->prev(); + ValueStack *state = pred_block_end->state_before(); + if (pred_block_end->as_Goto() && state == NULL) state = pred_block_end->state(); + assert(state, "State must not be null"); + + // Add deoptimization to dominator of loop header + TRACE_RANGE_CHECK_ELIMINATION( + tty->fill_to(block->dominator_depth()*2); + tty->print_cr("Inserting deopt at bci %d in block B%d!", state->bci(), insert_position->block()->block_id()) + ); + + if (!is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper())) { + TRACE_RANGE_CHECK_ELIMINATION( + tty->fill_to(block->dominator_depth()*2); + tty->print_cr("Could not eliminate because of static analysis!") + ); + return; + } + + insert_deoptimization(state, insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper(), ai); + + // Finally remove the range check! + remove_range_check(ai); + } + } +} + +void RangeCheckEliminator::remove_range_check(AccessIndexed *ai) { + ai->set_flag(Instruction::NeedsRangeCheckFlag, false); + // no range check, no need for the length instruction anymore + ai->clear_length(); + + TRACE_RANGE_CHECK_ELIMINATION( + tty->fill_to(ai->dominator_depth()*2); + tty->print_cr("Range check for instruction %d eliminated!", ai->id()); + ); + + ASSERT_RANGE_CHECK_ELIMINATION( + Value array_length = ai->length(); + if (!array_length) { + array_length = ai->array(); + assert(array_length->type()->as_ObjectType(), "Has to be object type!"); + } + int cur_constant = -1; + Value cur_value = array_length; + if (cur_value->type()->as_IntConstant()) { + cur_constant += cur_value->type()->as_IntConstant()->value(); + cur_value = NULL; + } + Bound *new_index_bound = new Bound(0, NULL, cur_constant, cur_value); + add_assertions(new_index_bound, ai->index(), ai); + ); +} + +// Calculate bounds for instruction in this block and children blocks in the dominator tree +void RangeCheckEliminator::calc_bounds(BlockBegin *block, BlockBegin *loop_header) { + // Ensures a valid loop_header + assert(!loop_header || loop_header->is_set(BlockBegin::linear_scan_loop_header_flag), "Loop header has to be real !"); + + // Tracing output + TRACE_RANGE_CHECK_ELIMINATION( + tty->fill_to(block->dominator_depth()*2); + tty->print_cr("Block B%d", block->block_id()); + ); + + // Pushed stack for conditions + IntegerStack pushed; + // Process If + BlockBegin *parent = block->dominator(); + if (parent != NULL) { + If *cond = parent->end()->as_If(); + if (cond != NULL) { + process_if(pushed, block, cond); + } + } + + // Interate over current block + InstructionList arrays; + AccessIndexedList accessIndexed; + Instruction *cur = block; + + while (cur) { + // Ensure cur wasn't inserted during the elimination + if (cur->id() < this->_bounds.length()) { + // Process only if it is an access indexed instruction + AccessIndexed *ai = cur->as_AccessIndexed(); + if (ai != NULL) { + process_access_indexed(loop_header, block, ai); + accessIndexed.append(ai); + if (!arrays.contains(ai->array())) { + arrays.append(ai->array()); + } + Bound *b = get_bound(ai->index()); + if (!b->lower_instr()) { + // Lower bound is constant + update_bound(pushed, ai->index(), Instruction::geq, NULL, 0); + } + if (!b->has_upper()) { + if (ai->length() && ai->length()->type()->as_IntConstant()) { + int value = ai->length()->type()->as_IntConstant()->value(); + update_bound(pushed, ai->index(), Instruction::lss, NULL, value); + } else { + // Has no upper bound + Instruction *instr = ai->length(); + if (instr != NULL) instr = ai->array(); + update_bound(pushed, ai->index(), Instruction::lss, instr, 0); + } + } + } + } + cur = cur->next(); + } + + // Output current condition stack + TRACE_RANGE_CHECK_ELIMINATION(dump_condition_stack(block)); + + // Do in block motion of range checks + in_block_motion(block, accessIndexed, arrays); + + // Call all dominated blocks + for (int i=0; idominates()->length(); i++) { + BlockBegin *next = block->dominates()->at(i); + if (!next->is_set(BlockBegin::donot_eliminate_range_checks)) { + // if current block is a loop header and: + // - next block belongs to the same loop + // or + // - next block belongs to an inner loop + // then current block is the loop header for next block + if (block->is_set(BlockBegin::linear_scan_loop_header_flag) && (block->loop_index() == next->loop_index() || next->loop_depth() > block->loop_depth())) { + calc_bounds(next, block); + } else { + calc_bounds(next, loop_header); + } + } + } + + // Reset stack + for (int i=0; ipop(); + } +} + +#ifndef PRODUCT +// Dump condition stack +void RangeCheckEliminator::dump_condition_stack(BlockBegin *block) { + for (int i=0; i<_ir->linear_scan_order()->length(); i++) { + BlockBegin *cur_block = _ir->linear_scan_order()->at(i); + Instruction *instr = cur_block; + for_each_phi_fun(cur_block, phi, + BoundStack *bound_stack = _bounds.at(phi->id()); + if (bound_stack && bound_stack->length() > 0) { + Bound *bound = bound_stack->top(); + if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != phi || bound->upper_instr() != phi || bound->lower() != 0 || bound->upper() != 0)) { + TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth()); + tty->print("i%d", phi->id()); + tty->print(": "); + bound->print(); + tty->print_cr(""); + ); + } + }); + + while (!instr->as_BlockEnd()) { + if (instr->id() < _bounds.length()) { + BoundStack *bound_stack = _bounds.at(instr->id()); + if (bound_stack && bound_stack->length() > 0) { + Bound *bound = bound_stack->top(); + if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != instr || bound->upper_instr() != instr || bound->lower() != 0 || bound->upper() != 0)) { + TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth()); + tty->print("i%d", instr->id()); + tty->print(": "); + bound->print(); + tty->print_cr(""); + ); + } + } + } + instr = instr->next(); + } + } +} +#endif + +// Verification or the IR +RangeCheckEliminator::Verification::Verification(IR *ir) : _used(BlockBegin::number_of_blocks(), false) { + this->_ir = ir; + ir->iterate_linear_scan_order(this); +} + +// Verify this block +void RangeCheckEliminator::Verification::block_do(BlockBegin *block) { + If *cond = block->end()->as_If(); + // Watch out: tsux and fsux can be the same! + if (block->number_of_sux() > 1) { + for (int i=0; inumber_of_sux(); i++) { + BlockBegin *sux = block->sux_at(i); + BlockBegin *pred = NULL; + for (int j=0; jnumber_of_preds(); j++) { + BlockBegin *cur = sux->pred_at(j); + assert(cur != NULL, "Predecessor must not be null"); + if (!pred) { + pred = cur; + } + assert(cur == pred, "Block must not have more than one predecessor if its predecessor has more than one successor"); + } + assert(sux->number_of_preds() >= 1, "Block must have at least one predecessor"); + assert(sux->pred_at(0) == block, "Wrong successor"); + } + } + + BlockBegin *dominator = block->dominator(); + if (dominator) { + assert(block != _ir->start(), "Start block must not have a dominator!"); + assert(can_reach(dominator, block), "Dominator can't reach his block !"); + assert(can_reach(_ir->start(), dominator), "Dominator is unreachable !"); + assert(!can_reach(_ir->start(), block, dominator), "Wrong dominator ! Block can be reached anyway !"); + BlockList *all_blocks = _ir->linear_scan_order(); + for (int i=0; ilength(); i++) { + BlockBegin *cur = all_blocks->at(i); + if (cur != dominator && cur != block) { + assert(can_reach(dominator, block, cur), "There has to be another dominator!"); + } + } + } else { + assert(block == _ir->start(), "Only start block must not have a dominator"); + } + + if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) { + int loop_index = block->loop_index(); + BlockList *all_blocks = _ir->linear_scan_order(); + assert(block->number_of_preds() >= 1, "Block must have at least one predecessor"); + assert(!block->is_set(BlockBegin::exception_entry_flag), "Loop header must not be exception handler!"); + // Sometimes, the backbranch comes from an exception handler. In + // this case, loop indexes/loop depths may not appear correct. + bool loop_through_xhandler = false; + for (int i = 0; i < block->number_of_exception_handlers(); i++) { + BlockBegin *xhandler = block->exception_handler_at(i); + for (int j = 0; j < block->number_of_preds(); j++) { + if (dominates(xhandler, block->pred_at(j)) || xhandler == block->pred_at(j)) { + loop_through_xhandler = true; + } + } + } + + for (int i=0; inumber_of_sux(); i++) { + BlockBegin *sux = block->sux_at(i); + assert(sux->loop_depth() != block->loop_depth() || sux->loop_index() == block->loop_index() || loop_through_xhandler, "Loop index has to be same"); + assert(sux->loop_depth() == block->loop_depth() || sux->loop_index() != block->loop_index(), "Loop index has to be different"); + } + + for (int i=0; ilength(); i++) { + BlockBegin *cur = all_blocks->at(i); + if (cur->loop_index() == loop_index && cur != block) { + assert(dominates(block->dominator(), cur), "Dominator of loop header must dominate all loop blocks"); + } + } + } + + Instruction *cur = block; + while (cur) { + assert(cur->block() == block, "Block begin has to be set correctly!"); + cur = cur->next(); + } +} + +// Loop header must dominate all loop blocks +bool RangeCheckEliminator::Verification::dominates(BlockBegin *dominator, BlockBegin *block) { + BlockBegin *cur = block->dominator(); + while (cur && cur != dominator) { + cur = cur->dominator(); + } + return cur == dominator; +} + +// Try to reach Block end beginning in Block start and not using Block dont_use +bool RangeCheckEliminator::Verification::can_reach(BlockBegin *start, BlockBegin *end, BlockBegin *dont_use /* = NULL */) { + if (start == end) return start != dont_use; + // Simple BSF from start to end + // BlockBeginList _current; + for (int i=0; i<_used.length(); i++) { + _used[i] = false; + } + _current.truncate(0); + _successors.truncate(0); + if (start != dont_use) { + _current.push(start); + _used[start->block_id()] = true; + } + + // BlockBeginList _successors; + while (_current.length() > 0) { + BlockBegin *cur = _current.pop(); + // Add exception handlers to list + for (int i=0; inumber_of_exception_handlers(); i++) { + BlockBegin *xhandler = cur->exception_handler_at(i); + _successors.push(xhandler); + // Add exception handlers of _successors to list + for (int j=0; jnumber_of_exception_handlers(); j++) { + BlockBegin *sux_xhandler = xhandler->exception_handler_at(j); + _successors.push(sux_xhandler); + } + } + // Add normal _successors to list + for (int i=0; inumber_of_sux(); i++) { + BlockBegin *sux = cur->sux_at(i); + _successors.push(sux); + // Add exception handlers of _successors to list + for (int j=0; jnumber_of_exception_handlers(); j++) { + BlockBegin *xhandler = sux->exception_handler_at(j); + _successors.push(xhandler); + } + } + for (int i=0; i<_successors.length(); i++) { + BlockBegin *sux = _successors[i]; + assert(sux != NULL, "Successor must not be NULL!"); + if (sux == end) { + return true; + } + if (sux != dont_use && !_used[sux->block_id()]) { + _used[sux->block_id()] = true; + _current.push(sux); + } + } + _successors.truncate(0); + } + + return false; +} + +// Bound +RangeCheckEliminator::Bound::~Bound() { +} + +// Bound constructor +RangeCheckEliminator::Bound::Bound() { + init(); + this->_lower = min_jint; + this->_upper = max_jint; + this->_lower_instr = NULL; + this->_upper_instr = NULL; +} + +// Bound constructor +RangeCheckEliminator::Bound::Bound(int lower, Value lower_instr, int upper, Value upper_instr) { + init(); + assert(!lower_instr || !lower_instr->as_Constant() || !lower_instr->type()->as_IntConstant(), "Must not be constant!"); + assert(!upper_instr || !upper_instr->as_Constant() || !upper_instr->type()->as_IntConstant(), "Must not be constant!"); + this->_lower = lower; + this->_upper = upper; + this->_lower_instr = lower_instr; + this->_upper_instr = upper_instr; +} + +// Bound constructor +RangeCheckEliminator::Bound::Bound(Instruction::Condition cond, Value v, int constant) { + assert(!v || (v->type() && (v->type()->as_IntType() || v->type()->as_ObjectType())), "Type must be array or integer!"); + assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!"); + + init(); + if (cond == Instruction::eql) { + _lower = constant; + _lower_instr = v; + _upper = constant; + _upper_instr = v; + } else if (cond == Instruction::neq) { + _lower = min_jint; + _upper = max_jint; + _lower_instr = NULL; + _upper_instr = NULL; + if (v == NULL) { + if (constant == min_jint) { + _lower++; + } + if (constant == max_jint) { + _upper--; + } + } + } else if (cond == Instruction::geq) { + _lower = constant; + _lower_instr = v; + _upper = max_jint; + _upper_instr = NULL; + } else if (cond == Instruction::leq) { + _lower = min_jint; + _lower_instr = NULL; + _upper = constant; + _upper_instr = v; + } else { + ShouldNotReachHere(); + } +} + +// Set lower +void RangeCheckEliminator::Bound::set_lower(int value, Value v) { + assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!"); + this->_lower = value; + this->_lower_instr = v; +} + +// Set upper +void RangeCheckEliminator::Bound::set_upper(int value, Value v) { + assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!"); + this->_upper = value; + this->_upper_instr = v; +} + +// Add constant -> no overflow may occur +void RangeCheckEliminator::Bound::add_constant(int value) { + this->_lower += value; + this->_upper += value; +} + +// Init +void RangeCheckEliminator::Bound::init() { +} + +// or +void RangeCheckEliminator::Bound::or_op(Bound *b) { + // Watch out, bound is not guaranteed not to overflow! + // Update lower bound + if (_lower_instr != b->_lower_instr || (_lower_instr && _lower != b->_lower)) { + _lower_instr = NULL; + _lower = min_jint; + } else { + _lower = MIN2(_lower, b->_lower); + } + // Update upper bound + if (_upper_instr != b->_upper_instr || (_upper_instr && _upper != b->_upper)) { + _upper_instr = NULL; + _upper = max_jint; + } else { + _upper = MAX2(_upper, b->_upper); + } +} + +// and +void RangeCheckEliminator::Bound::and_op(Bound *b) { + // Update lower bound + if (_lower_instr == b->_lower_instr) { + _lower = MAX2(_lower, b->_lower); + } + if (b->has_lower()) { + bool set = true; + if (_lower_instr != NULL && b->_lower_instr != NULL) { + set = (_lower_instr->dominator_depth() > b->_lower_instr->dominator_depth()); + } + if (set) { + _lower = b->_lower; + _lower_instr = b->_lower_instr; + } + } + // Update upper bound + if (_upper_instr == b->_upper_instr) { + _upper = MIN2(_upper, b->_upper); + } + if (b->has_upper()) { + bool set = true; + if (_upper_instr != NULL && b->_upper_instr != NULL) { + set = (_upper_instr->dominator_depth() > b->_upper_instr->dominator_depth()); + } + if (set) { + _upper = b->_upper; + _upper_instr = b->_upper_instr; + } + } +} + +// has_upper +bool RangeCheckEliminator::Bound::has_upper() { + return _upper_instr != NULL || _upper < max_jint; +} + +// is_smaller +bool RangeCheckEliminator::Bound::is_smaller(Bound *b) { + if (b->_lower_instr != _upper_instr) { + return false; + } + return _upper < b->_lower; +} + +// has_lower +bool RangeCheckEliminator::Bound::has_lower() { + return _lower_instr != NULL || _lower > min_jint; +} + +// in_array_bound +bool RangeCheckEliminator::in_array_bound(Bound *bound, Value array){ + if (!bound) return false; + assert(array != NULL, "Must not be null!"); + assert(bound != NULL, "Must not be null!"); + if (bound->lower() >=0 && bound->lower_instr() == NULL && bound->upper() < 0 && bound->upper_instr() != NULL) { + ArrayLength *len = bound->upper_instr()->as_ArrayLength(); + if (bound->upper_instr() == array || (len != NULL && len->array() == array)) { + return true; + } + } + return false; +} + +// remove_lower +void RangeCheckEliminator::Bound::remove_lower() { + _lower = min_jint; + _lower_instr = NULL; +} + +// remove_upper +void RangeCheckEliminator::Bound::remove_upper() { + _upper = max_jint; + _upper_instr = NULL; +} + +// upper +int RangeCheckEliminator::Bound::upper() { + return _upper; +} + +// lower +int RangeCheckEliminator::Bound::lower() { + return _lower; +} + +// upper_instr +Value RangeCheckEliminator::Bound::upper_instr() { + return _upper_instr; +} + +// lower_instr +Value RangeCheckEliminator::Bound::lower_instr() { + return _lower_instr; +} + +// print +void RangeCheckEliminator::Bound::print() { + tty->print(""); + if (this->_lower_instr || this->_lower != min_jint) { + if (this->_lower_instr) { + tty->print("i%d", this->_lower_instr->id()); + if (this->_lower > 0) { + tty->print("+%d", _lower); + } + if (this->_lower < 0) { + tty->print("%d", _lower); + } + } else { + tty->print("%d", _lower); + } + tty->print(" <= "); + } + tty->print("x"); + if (this->_upper_instr || this->_upper != max_jint) { + tty->print(" <= "); + if (this->_upper_instr) { + tty->print("i%d", this->_upper_instr->id()); + if (this->_upper > 0) { + tty->print("+%d", _upper); + } + if (this->_upper < 0) { + tty->print("%d", _upper); + } + } else { + tty->print("%d", _upper); + } + } +} + +// Copy +RangeCheckEliminator::Bound *RangeCheckEliminator::Bound::copy() { + Bound *b = new Bound(); + b->_lower = _lower; + b->_lower_instr = _lower_instr; + b->_upper = _upper; + b->_upper_instr = _upper_instr; + return b; +} + +#ifdef ASSERT +// Add assertion +void RangeCheckEliminator::Bound::add_assertion(Instruction *instruction, Instruction *position, int i, Value instr, Instruction::Condition cond) { + Instruction *result = position; + Instruction *compare_with = NULL; + ValueStack *state = position->state_before(); + if (position->as_BlockEnd() && !position->as_Goto()) { + state = position->as_BlockEnd()->state_before(); + } + Instruction *instruction_before = position->prev(); + if (position->as_Return() && Compilation::current()->method()->is_synchronized() && instruction_before->as_MonitorExit()) { + instruction_before = instruction_before->prev(); + } + result = instruction_before; + // Load constant only if needed + Constant *constant = NULL; + if (i != 0 || !instr) { + constant = new Constant(new IntConstant(i)); + NOT_PRODUCT(constant->set_printable_bci(position->printable_bci())); + result = result->insert_after(constant); + compare_with = constant; + } + + if (instr) { + assert(instr->type()->as_ObjectType() || instr->type()->as_IntType(), "Type must be array or integer!"); + compare_with = instr; + // Load array length if necessary + Instruction *op = instr; + if (instr->type()->as_ObjectType()) { + assert(state, "must not be null"); + ArrayLength *length = new ArrayLength(instr, state->copy()); + NOT_PRODUCT(length->set_printable_bci(position->printable_bci())); + length->set_exception_state(length->state_before()); + result = result->insert_after(length); + op = length; + compare_with = length; + } + // Add operation only if necessary + if (constant) { + ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, op, false, NULL); + NOT_PRODUCT(ao->set_printable_bci(position->printable_bci())); + result = result->insert_after(ao); + compare_with = ao; + // TODO: Check that add operation does not overflow! + } + } + assert(compare_with != NULL, "You have to compare with something!"); + assert(instruction != NULL, "Instruction must not be null!"); + + if (instruction->type()->as_ObjectType()) { + // Load array length if necessary + Instruction *op = instruction; + assert(state, "must not be null"); + ArrayLength *length = new ArrayLength(instruction, state->copy()); + length->set_exception_state(length->state_before()); + NOT_PRODUCT(length->set_printable_bci(position->printable_bci())); + result = result->insert_after(length); + instruction = length; + } + + Assert *assert = new Assert(instruction, cond, false, compare_with); + NOT_PRODUCT(assert->set_printable_bci(position->printable_bci())); + result->insert_after(assert); +} + +// Add assertions +void RangeCheckEliminator::add_assertions(Bound *bound, Instruction *instruction, Instruction *position) { + // Add lower bound assertion + if (bound->has_lower()) { + bound->add_assertion(instruction, position, bound->lower(), bound->lower_instr(), Instruction::geq); + } + // Add upper bound assertion + if (bound->has_upper()) { + bound->add_assertion(instruction, position, bound->upper(), bound->upper_instr(), Instruction::leq); + } +} +#endif +