/* * Copyright (c) 2012, 2022, 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. *
*/
#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);
// 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);
}
}
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;
} elseif (value > 1) { // Overflow not guaranteed
has_upper = false;
has_lower = false;
} elseif (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);
} elseif (y->type()->as_IntConstant() && y->type()->as_IntConstant()->value() != 0) { // The binary % operator is said to yield the remainder of its operands from an implied division; the // left-hand operand is the dividend and the right-hand operand is the divisor. // // % operator follows from this rule that the result of the remainder operation can be negative only // if the dividend is negative, and can be positive only if the dividend is positive. Moreover, the // magnitude of the result is always less than the magnitude of the divisor(See JLS 15.17.3). // // So if y is a constant integer and not equal to 0, then we can deduce the bound of remainder operation: // x % -y ==> [0, y - 1] Apply RCE // x % y ==> [0, y - 1] Apply RCE // -x % y ==> [-y + 1, 0] // -x % -y ==> [-y + 1, 0] if (x_bound->has_lower() && x_bound->lower() >= 0) {
_bound = new Bound(0, NULL, y->type()->as_IntConstant()->value() - 1, NULL);
} else {
_bound = new Bound();
}
} else {
_bound = new Bound();
}
} elseif (!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;
}
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.at(v->id())) { // First (default) bound is calculated // Create BoundStack
_bounds.at_put(v->id(), new BoundStack());
_visitor.clear_bound();
Value visit_value = v;
visit_value->visit(&_visitor);
Bound *bound = _visitor.bound(); if (bound) {
_bounds.at(v->id())->push(bound);
} if (_bounds.at(v->id())->length() == 0) {
assert(!(v->as_Constant() && v->type()->as_IntConstant()), "constants not handled here");
_bounds.at(v->id())->push(new Bound());
}
} elseif (_bounds.at(v->id())->length() == 0) { // To avoid endless loops, bound is currently in calculation -> nothing known about it returnnew Bound();
}
// 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++;
} elseif (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) returntrue; for (BlockBegin *d = loop_header->dominator(); d != NULL; d = d->dominator()) { if (d == instruction->block()) { returntrue;
}
} returnfalse;
}
// 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.at(v->id())) {
get_bound(v);
assert(_bounds.at(v->id()), "Now Stack must exist");
}
Bound *top = NULL; if (_bounds.at(v->id())->length() > 0) {
top = _bounds.at(v->id())->top();
} if (top) {
bound->and_op(top);
}
_bounds.at(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.at(id); if (aii == NULL) {
aii = new AccessIndexedInfo();
_access_indexed_info.at_put(id, aii);
indices.append(instruction);
aii->_min = idx;
aii->_max = idx;
aii->_list = new AccessIndexedList();
} elseif (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.at(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;
}
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.at_put(index_instruction->id(), NULL);
}
indices.clear();
}
}
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) returnfalse; // 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) returnfalse;
} // 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. returnfalse;
} returntrue;
}
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);
} elseif (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!");
// 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;
} elseif (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));
}
}
}
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);
} elseif (_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;
}
// 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 !");
// 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);
}
}
// Iterate 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);
}
}
}
#ifdef ASSERT // Verification or the IR
RangeCheckEliminator::Verification::Verification(IR *ir) : _used(BlockBegin::number_of_blocks(), 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!");
bool loop_through_xhandler = false; for (int i=0; i<block->number_of_sux(); i++) {
BlockBegin *sux = block->sux_at(i); if (!loop_through_xhandler) { if (sux->loop_depth() == block->loop_depth() && sux->loop_index() != block->loop_index()) {
loop_through_xhandler = is_backbranch_from_xhandler(block);
assert(loop_through_xhandler, "Loop indices have to be the same if same depths but no backbranch from xhandler");
}
}
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();
}
}
// Called when a successor of a block has the same loop depth but a different loop index. This can happen if a backbranch comes from // an exception handler of a loop head block, for example, when a loop is only executed once on the non-exceptional path but is // repeated in case of an exception. In this case, the edge block->sux is not critical and was not split before. // Check if there is such a backbranch from an xhandler of 'block'. bool RangeCheckEliminator::Verification::is_backbranch_from_xhandler(BlockBegin* block) { 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)) { returntrue;
}
}
}
// In case of nested xhandlers, we need to walk through the loop (and all blocks belonging to exception handlers) // to find an xhandler of 'block'. if (block->number_of_exception_handlers() > 0) { for (int i = 0; i < block->number_of_preds(); i++) {
BlockBegin* pred = block->pred_at(i); if (pred->loop_index() == block->loop_index()) { // Only check blocks that belong to the loop // Do a BFS to find an xhandler block of 'block' starting from 'pred'
ResourceMark rm;
ResourceBitMap visited(BlockBegin::number_of_blocks());
BlockBeginList list;
list.push(pred); while (!list.is_empty()) {
BlockBegin* next = list.pop(); if (!visited.at(next->block_id())) {
visited.set_bit(next->block_id()); for (int j = 0; j < block->number_of_exception_handlers(); j++) { if (next == block->exception_handler_at(j)) { returntrue;
}
} for (int j = 0; j < next->number_of_preds(); j++) { if (next->pred_at(j) != block) {
list.push(next->pred_at(j));
}
}
}
}
}
}
} returnfalse;
}
// 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.at_put(i, false);
}
_current.trunc_to(0);
_successors.trunc_to(0); if (start != dont_use) {
_current.push(start);
_used.at_put(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.at(i);
assert(sux != NULL, "Successor must not be NULL!"); if (sux == end) { returntrue;
} if (sux != dont_use && !_used.at(sux->block_id())) {
_used.at_put(sux->block_id(), true);
_current.push(sux);
}
}
_successors.trunc_to(0);
}
// Bound constructor
RangeCheckEliminator::Bound::Bound(int lower, Value lower_instr, int upper, Value upper_instr) {
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!");
#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, 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;
}
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
