| /* |
| * Copyright (c) 2012, 2014, 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->cr(); |
| tty->print_cr("Range check elimination"); |
| ir->method()->print_name(tty); |
| tty->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; i<op_count; i++) { |
| Value v = phi->operand_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; i<arrays.length(); i++) { |
| int max_constant = -1; |
| AccessIndexedList list_constant; |
| Value array = arrays.at(i); |
| |
| // For all AccessIndexed-instructions in this block concerning the current array. |
| for(int j=0; j<accessIndexed.length(); j++) { |
| AccessIndexed *ai = accessIndexed.at(j); |
| if (ai->array() != 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; i < indices.length(); i++) { |
| Instruction *index_instruction = indices.at(i); |
| AccessIndexedInfo *info = _access_indexed_info[index_instruction->id()]; |
| 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<info->_list->length(); j++) { |
| AccessIndexed *ai = info->_list->at(j); |
| remove_range_check(ai); |
| } |
| } |
| } |
| |
| 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; j<list_constant.length(); j++) { |
| AccessIndexed *ai = list_constant.at(j); |
| remove_range_check(ai); |
| } |
| } |
| } |
| |
| // Clear data structures for next array |
| for (int i = 0; i < indices.length(); i++) { |
| Instruction *index_instruction = indices.at(i); |
| _access_indexed_info[index_instruction->id()] = NULL; |
| } |
| indices.clear(); |
| } |
| } |
| |
| bool RangeCheckEliminator::set_process_block_flags(BlockBegin *block) { |
| Instruction *cur = block; |
| bool process = false; |
| |
| while (cur) { |
| process |= (cur->as_AccessIndexed() != NULL); |
| cur = cur->next(); |
| } |
| |
| BlockList *dominates = block->dominates(); |
| for (int i=0; i<dominates->length(); 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 |
| 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); |
| } |
| } |
| |
| // No upper check required -> skip |
| if (!upper_check) return; |
| |
| // 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; |
| } |
| |
| 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() != NULL ? ai->length()->id() :-1 )) |
| ); |
| |
| 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; i<block->dominates()->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; i<pushed.length(); i++) { |
| _bounds[pushed[i]]->pop(); |
| } |
| } |
| |
| #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->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->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; i<block->number_of_sux(); i++) { |
| BlockBegin *sux = block->sux_at(i); |
| BlockBegin *pred = NULL; |
| for (int j=0; j<sux->number_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; i<all_blocks->length(); 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; i<block->number_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; i<all_blocks->length(); 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; i<cur->number_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; j<xhandler->number_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; i<cur->number_of_sux(); i++) { |
| BlockBegin *sux = cur->sux_at(i); |
| _successors.push(sux); |
| // Add exception handlers of _successors to list |
| for (int j=0; j<sux->number_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("%s", ""); |
| 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 |
| |
