1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/c1/c1_RangeCheckElimination.cpp Wed Apr 27 01:25:04 2016 +0800
1.3 @@ -0,0 +1,1522 @@
1.4 +/*
1.5 + * Copyright (c) 2012, 2014, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +
1.28 +#include "precompiled.hpp"
1.29 +#include "c1/c1_ValueStack.hpp"
1.30 +#include "c1/c1_RangeCheckElimination.hpp"
1.31 +#include "c1/c1_IR.hpp"
1.32 +#include "c1/c1_Canonicalizer.hpp"
1.33 +#include "c1/c1_ValueMap.hpp"
1.34 +#include "ci/ciMethodData.hpp"
1.35 +#include "runtime/deoptimization.hpp"
1.36 +
1.37 +// Macros for the Trace and the Assertion flag
1.38 +#ifdef ASSERT
1.39 +#define TRACE_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination) { code; }
1.40 +#define ASSERT_RANGE_CHECK_ELIMINATION(code) if (AssertRangeCheckElimination) { code; }
1.41 +#define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination || AssertRangeCheckElimination) { code; }
1.42 +#else
1.43 +#define TRACE_RANGE_CHECK_ELIMINATION(code)
1.44 +#define ASSERT_RANGE_CHECK_ELIMINATION(code)
1.45 +#define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code)
1.46 +#endif
1.47 +
1.48 +// Entry point for the optimization
1.49 +void RangeCheckElimination::eliminate(IR *ir) {
1.50 + bool do_elimination = ir->compilation()->has_access_indexed();
1.51 + ASSERT_RANGE_CHECK_ELIMINATION(do_elimination = true);
1.52 + if (do_elimination) {
1.53 + RangeCheckEliminator rce(ir);
1.54 + }
1.55 +}
1.56 +
1.57 +// Constructor
1.58 +RangeCheckEliminator::RangeCheckEliminator(IR *ir) :
1.59 + _bounds(Instruction::number_of_instructions(), NULL),
1.60 + _access_indexed_info(Instruction::number_of_instructions(), NULL)
1.61 +{
1.62 + _visitor.set_range_check_eliminator(this);
1.63 + _ir = ir;
1.64 + _number_of_instructions = Instruction::number_of_instructions();
1.65 + _optimistic = ir->compilation()->is_optimistic();
1.66 +
1.67 + TRACE_RANGE_CHECK_ELIMINATION(
1.68 + tty->cr();
1.69 + tty->print_cr("Range check elimination");
1.70 + ir->method()->print_name(tty);
1.71 + tty->cr();
1.72 + );
1.73 +
1.74 + TRACE_RANGE_CHECK_ELIMINATION(
1.75 + tty->print_cr("optimistic=%d", (int)_optimistic);
1.76 + );
1.77 +
1.78 +#ifdef ASSERT
1.79 + // Verifies several conditions that must be true on the IR-input. Only used for debugging purposes.
1.80 + TRACE_RANGE_CHECK_ELIMINATION(
1.81 + tty->print_cr("Verification of IR . . .");
1.82 + );
1.83 + Verification verification(ir);
1.84 +#endif
1.85 +
1.86 + // Set process block flags
1.87 + // Optimization so a blocks is only processed if it contains an access indexed instruction or if
1.88 + // one of its children in the dominator tree contains an access indexed instruction.
1.89 + set_process_block_flags(ir->start());
1.90 +
1.91 + // Pass over instructions in the dominator tree
1.92 + TRACE_RANGE_CHECK_ELIMINATION(
1.93 + tty->print_cr("Starting pass over dominator tree . . .")
1.94 + );
1.95 + calc_bounds(ir->start(), NULL);
1.96 +
1.97 + TRACE_RANGE_CHECK_ELIMINATION(
1.98 + tty->print_cr("Finished!")
1.99 + );
1.100 +}
1.101 +
1.102 +// Instruction specific work for some instructions
1.103 +// Constant
1.104 +void RangeCheckEliminator::Visitor::do_Constant(Constant *c) {
1.105 + IntConstant *ic = c->type()->as_IntConstant();
1.106 + if (ic != NULL) {
1.107 + int value = ic->value();
1.108 + _bound = new Bound(value, NULL, value, NULL);
1.109 + }
1.110 +}
1.111 +
1.112 +// LogicOp
1.113 +void RangeCheckEliminator::Visitor::do_LogicOp(LogicOp *lo) {
1.114 + if (lo->type()->as_IntType() && lo->op() == Bytecodes::_iand && (lo->x()->as_Constant() || lo->y()->as_Constant())) {
1.115 + int constant = 0;
1.116 + Constant *c = lo->x()->as_Constant();
1.117 + if (c != NULL) {
1.118 + constant = c->type()->as_IntConstant()->value();
1.119 + } else {
1.120 + constant = lo->y()->as_Constant()->type()->as_IntConstant()->value();
1.121 + }
1.122 + if (constant >= 0) {
1.123 + _bound = new Bound(0, NULL, constant, NULL);
1.124 + }
1.125 + }
1.126 +}
1.127 +
1.128 +// Phi
1.129 +void RangeCheckEliminator::Visitor::do_Phi(Phi *phi) {
1.130 + if (!phi->type()->as_IntType() && !phi->type()->as_ObjectType()) return;
1.131 +
1.132 + BlockBegin *block = phi->block();
1.133 + int op_count = phi->operand_count();
1.134 + bool has_upper = true;
1.135 + bool has_lower = true;
1.136 + assert(phi, "Phi must not be null");
1.137 + Bound *bound = NULL;
1.138 +
1.139 + // TODO: support more difficult phis
1.140 + for (int i=0; i<op_count; i++) {
1.141 + Value v = phi->operand_at(i);
1.142 +
1.143 + if (v == phi) continue;
1.144 +
1.145 + // Check if instruction is connected with phi itself
1.146 + Op2 *op2 = v->as_Op2();
1.147 + if (op2 != NULL) {
1.148 + Value x = op2->x();
1.149 + Value y = op2->y();
1.150 + if ((x == phi || y == phi)) {
1.151 + Value other = x;
1.152 + if (other == phi) {
1.153 + other = y;
1.154 + }
1.155 + ArithmeticOp *ao = v->as_ArithmeticOp();
1.156 + if (ao != NULL && ao->op() == Bytecodes::_iadd) {
1.157 + assert(ao->op() == Bytecodes::_iadd, "Has to be add!");
1.158 + if (ao->type()->as_IntType()) {
1.159 + Constant *c = other->as_Constant();
1.160 + if (c != NULL) {
1.161 + assert(c->type()->as_IntConstant(), "Constant has to be of type integer");
1.162 + int value = c->type()->as_IntConstant()->value();
1.163 + if (value == 1) {
1.164 + has_upper = false;
1.165 + } else if (value > 1) {
1.166 + // Overflow not guaranteed
1.167 + has_upper = false;
1.168 + has_lower = false;
1.169 + } else if (value < 0) {
1.170 + has_lower = false;
1.171 + }
1.172 + continue;
1.173 + }
1.174 + }
1.175 + }
1.176 + }
1.177 + }
1.178 +
1.179 + // No connection -> new bound
1.180 + Bound *v_bound = _rce->get_bound(v);
1.181 + Bound *cur_bound;
1.182 + int cur_constant = 0;
1.183 + Value cur_value = v;
1.184 +
1.185 + if (v->type()->as_IntConstant()) {
1.186 + cur_constant = v->type()->as_IntConstant()->value();
1.187 + cur_value = NULL;
1.188 + }
1.189 + if (!v_bound->has_upper() || !v_bound->has_lower()) {
1.190 + cur_bound = new Bound(cur_constant, cur_value, cur_constant, cur_value);
1.191 + } else {
1.192 + cur_bound = v_bound;
1.193 + }
1.194 + if (cur_bound) {
1.195 + if (!bound) {
1.196 + bound = cur_bound->copy();
1.197 + } else {
1.198 + bound->or_op(cur_bound);
1.199 + }
1.200 + } else {
1.201 + // No bound!
1.202 + bound = NULL;
1.203 + break;
1.204 + }
1.205 + }
1.206 +
1.207 + if (bound) {
1.208 + if (!has_upper) {
1.209 + bound->remove_upper();
1.210 + }
1.211 + if (!has_lower) {
1.212 + bound->remove_lower();
1.213 + }
1.214 + _bound = bound;
1.215 + } else {
1.216 + _bound = new Bound();
1.217 + }
1.218 +}
1.219 +
1.220 +
1.221 +// ArithmeticOp
1.222 +void RangeCheckEliminator::Visitor::do_ArithmeticOp(ArithmeticOp *ao) {
1.223 + Value x = ao->x();
1.224 + Value y = ao->y();
1.225 +
1.226 + if (ao->op() == Bytecodes::_irem) {
1.227 + Bound* x_bound = _rce->get_bound(x);
1.228 + Bound* y_bound = _rce->get_bound(y);
1.229 + if (x_bound->lower() >= 0 && x_bound->lower_instr() == NULL && y->as_ArrayLength() != NULL) {
1.230 + _bound = new Bound(0, NULL, -1, y);
1.231 + } else {
1.232 + _bound = new Bound();
1.233 + }
1.234 + } else if (!x->as_Constant() || !y->as_Constant()) {
1.235 + assert(!x->as_Constant() || !y->as_Constant(), "One of the operands must be non-constant!");
1.236 + if (((x->as_Constant() || y->as_Constant()) && (ao->op() == Bytecodes::_iadd)) || (y->as_Constant() && ao->op() == Bytecodes::_isub)) {
1.237 + assert(ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub, "Operand must be iadd or isub");
1.238 +
1.239 + if (y->as_Constant()) {
1.240 + Value tmp = x;
1.241 + x = y;
1.242 + y = tmp;
1.243 + }
1.244 + assert(x->as_Constant()->type()->as_IntConstant(), "Constant must be int constant!");
1.245 +
1.246 + // Constant now in x
1.247 + int const_value = x->as_Constant()->type()->as_IntConstant()->value();
1.248 + if (ao->op() == Bytecodes::_iadd || const_value != min_jint) {
1.249 + if (ao->op() == Bytecodes::_isub) {
1.250 + const_value = -const_value;
1.251 + }
1.252 +
1.253 + Bound * bound = _rce->get_bound(y);
1.254 + if (bound->has_upper() && bound->has_lower()) {
1.255 + int new_lower = bound->lower() + const_value;
1.256 + jlong new_lowerl = ((jlong)bound->lower()) + const_value;
1.257 + int new_upper = bound->upper() + const_value;
1.258 + jlong new_upperl = ((jlong)bound->upper()) + const_value;
1.259 +
1.260 + if (((jlong)new_lower) == new_lowerl && ((jlong)new_upper == new_upperl)) {
1.261 + Bound *newBound = new Bound(new_lower, bound->lower_instr(), new_upper, bound->upper_instr());
1.262 + _bound = newBound;
1.263 + } else {
1.264 + // overflow
1.265 + _bound = new Bound();
1.266 + }
1.267 + } else {
1.268 + _bound = new Bound();
1.269 + }
1.270 + } else {
1.271 + _bound = new Bound();
1.272 + }
1.273 + } else {
1.274 + Bound *bound = _rce->get_bound(x);
1.275 + if (ao->op() == Bytecodes::_isub) {
1.276 + if (bound->lower_instr() == y) {
1.277 + _bound = new Bound(Instruction::geq, NULL, bound->lower());
1.278 + } else {
1.279 + _bound = new Bound();
1.280 + }
1.281 + } else {
1.282 + _bound = new Bound();
1.283 + }
1.284 + }
1.285 + }
1.286 +}
1.287 +
1.288 +// IfOp
1.289 +void RangeCheckEliminator::Visitor::do_IfOp(IfOp *ifOp)
1.290 +{
1.291 + if (ifOp->tval()->type()->as_IntConstant() && ifOp->fval()->type()->as_IntConstant()) {
1.292 + int min = ifOp->tval()->type()->as_IntConstant()->value();
1.293 + int max = ifOp->fval()->type()->as_IntConstant()->value();
1.294 + if (min > max) {
1.295 + // min ^= max ^= min ^= max;
1.296 + int tmp = min;
1.297 + min = max;
1.298 + max = tmp;
1.299 + }
1.300 + _bound = new Bound(min, NULL, max, NULL);
1.301 + }
1.302 +}
1.303 +
1.304 +// Get bound. Returns the current bound on Value v. Normally this is the topmost element on the bound stack.
1.305 +RangeCheckEliminator::Bound *RangeCheckEliminator::get_bound(Value v) {
1.306 + // Wrong type or NULL -> No bound
1.307 + if (!v || (!v->type()->as_IntType() && !v->type()->as_ObjectType())) return NULL;
1.308 +
1.309 + if (!_bounds[v->id()]) {
1.310 + // First (default) bound is calculated
1.311 + // Create BoundStack
1.312 + _bounds[v->id()] = new BoundStack();
1.313 + _visitor.clear_bound();
1.314 + Value visit_value = v;
1.315 + visit_value->visit(&_visitor);
1.316 + Bound *bound = _visitor.bound();
1.317 + if (bound) {
1.318 + _bounds[v->id()]->push(bound);
1.319 + }
1.320 + if (_bounds[v->id()]->length() == 0) {
1.321 + assert(!(v->as_Constant() && v->type()->as_IntConstant()), "constants not handled here");
1.322 + _bounds[v->id()]->push(new Bound());
1.323 + }
1.324 + } else if (_bounds[v->id()]->length() == 0) {
1.325 + // To avoid endless loops, bound is currently in calculation -> nothing known about it
1.326 + return new Bound();
1.327 + }
1.328 +
1.329 + // Return bound
1.330 + return _bounds[v->id()]->top();
1.331 +}
1.332 +
1.333 +// Update bound
1.334 +void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Instruction::Condition cond, Value value, int constant) {
1.335 + if (cond == Instruction::gtr) {
1.336 + cond = Instruction::geq;
1.337 + constant++;
1.338 + } else if (cond == Instruction::lss) {
1.339 + cond = Instruction::leq;
1.340 + constant--;
1.341 + }
1.342 + Bound *bound = new Bound(cond, value, constant);
1.343 + update_bound(pushed, v, bound);
1.344 +}
1.345 +
1.346 +// Checks for loop invariance. Returns true if the instruction is outside of the loop which is identified by loop_header.
1.347 +bool RangeCheckEliminator::loop_invariant(BlockBegin *loop_header, Instruction *instruction) {
1.348 + assert(loop_header, "Loop header must not be null!");
1.349 + if (!instruction) return true;
1.350 + return instruction->dominator_depth() < loop_header->dominator_depth();
1.351 +}
1.352 +
1.353 +// Update bound. Pushes a new bound onto the stack. Tries to do a conjunction with the current bound.
1.354 +void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Bound *bound) {
1.355 + if (v->as_Constant()) {
1.356 + // No bound update for constants
1.357 + return;
1.358 + }
1.359 + if (!_bounds[v->id()]) {
1.360 + get_bound(v);
1.361 + assert(_bounds[v->id()], "Now Stack must exist");
1.362 + }
1.363 + Bound *top = NULL;
1.364 + if (_bounds[v->id()]->length() > 0) {
1.365 + top = _bounds[v->id()]->top();
1.366 + }
1.367 + if (top) {
1.368 + bound->and_op(top);
1.369 + }
1.370 + _bounds[v->id()]->push(bound);
1.371 + pushed.append(v->id());
1.372 +}
1.373 +
1.374 +// Add instruction + idx for in block motion
1.375 +void RangeCheckEliminator::add_access_indexed_info(InstructionList &indices, int idx, Value instruction, AccessIndexed *ai) {
1.376 + int id = instruction->id();
1.377 + AccessIndexedInfo *aii = _access_indexed_info[id];
1.378 + if (aii == NULL) {
1.379 + aii = new AccessIndexedInfo();
1.380 + _access_indexed_info[id] = aii;
1.381 + indices.append(instruction);
1.382 + aii->_min = idx;
1.383 + aii->_max = idx;
1.384 + aii->_list = new AccessIndexedList();
1.385 + } else if (idx >= aii->_min && idx <= aii->_max) {
1.386 + remove_range_check(ai);
1.387 + return;
1.388 + }
1.389 + aii->_min = MIN2(aii->_min, idx);
1.390 + aii->_max = MAX2(aii->_max, idx);
1.391 + aii->_list->append(ai);
1.392 +}
1.393 +
1.394 +// In block motion. Tries to reorder checks in order to reduce some of them.
1.395 +// Example:
1.396 +// a[i] = 0;
1.397 +// a[i+2] = 0;
1.398 +// a[i+1] = 0;
1.399 +// In this example the check for a[i+1] would be considered as unnecessary during the first iteration.
1.400 +// After this i is only checked once for i >= 0 and i+2 < a.length before the first array access. If this
1.401 +// check fails, deoptimization is called.
1.402 +void RangeCheckEliminator::in_block_motion(BlockBegin *block, AccessIndexedList &accessIndexed, InstructionList &arrays) {
1.403 + InstructionList indices;
1.404 +
1.405 + // Now iterate over all arrays
1.406 + for (int i=0; i<arrays.length(); i++) {
1.407 + int max_constant = -1;
1.408 + AccessIndexedList list_constant;
1.409 + Value array = arrays.at(i);
1.410 +
1.411 + // For all AccessIndexed-instructions in this block concerning the current array.
1.412 + for(int j=0; j<accessIndexed.length(); j++) {
1.413 + AccessIndexed *ai = accessIndexed.at(j);
1.414 + if (ai->array() != array || !ai->check_flag(Instruction::NeedsRangeCheckFlag)) continue;
1.415 +
1.416 + Value index = ai->index();
1.417 + Constant *c = index->as_Constant();
1.418 + if (c != NULL) {
1.419 + int constant_value = c->type()->as_IntConstant()->value();
1.420 + if (constant_value >= 0) {
1.421 + if (constant_value <= max_constant) {
1.422 + // No range check needed for this
1.423 + remove_range_check(ai);
1.424 + } else {
1.425 + max_constant = constant_value;
1.426 + list_constant.append(ai);
1.427 + }
1.428 + }
1.429 + } else {
1.430 + int last_integer = 0;
1.431 + Instruction *last_instruction = index;
1.432 + int base = 0;
1.433 + ArithmeticOp *ao = index->as_ArithmeticOp();
1.434 +
1.435 + while (ao != NULL && (ao->x()->as_Constant() || ao->y()->as_Constant()) && (ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub)) {
1.436 + c = ao->y()->as_Constant();
1.437 + Instruction *other = ao->x();
1.438 + if (!c && ao->op() == Bytecodes::_iadd) {
1.439 + c = ao->x()->as_Constant();
1.440 + other = ao->y();
1.441 + }
1.442 +
1.443 + if (c) {
1.444 + int value = c->type()->as_IntConstant()->value();
1.445 + if (value != min_jint) {
1.446 + if (ao->op() == Bytecodes::_isub) {
1.447 + value = -value;
1.448 + }
1.449 + base += value;
1.450 + last_integer = base;
1.451 + last_instruction = other;
1.452 + }
1.453 + index = other;
1.454 + } else {
1.455 + break;
1.456 + }
1.457 + ao = index->as_ArithmeticOp();
1.458 + }
1.459 + add_access_indexed_info(indices, last_integer, last_instruction, ai);
1.460 + }
1.461 + }
1.462 +
1.463 + // Iterate over all different indices
1.464 + if (_optimistic) {
1.465 + for (int i = 0; i < indices.length(); i++) {
1.466 + Instruction *index_instruction = indices.at(i);
1.467 + AccessIndexedInfo *info = _access_indexed_info[index_instruction->id()];
1.468 + assert(info != NULL, "Info must not be null");
1.469 +
1.470 + // if idx < 0, max > 0, max + idx may fall between 0 and
1.471 + // length-1 and if min < 0, min + idx may overflow and be >=
1.472 + // 0. The predicate wouldn't trigger but some accesses could
1.473 + // be with a negative index. This test guarantees that for the
1.474 + // min and max value that are kept the predicate can't let
1.475 + // some incorrect accesses happen.
1.476 + bool range_cond = (info->_max < 0 || info->_max + min_jint <= info->_min);
1.477 +
1.478 + // Generate code only if more than 2 range checks can be eliminated because of that.
1.479 + // 2 because at least 2 comparisons are done
1.480 + if (info->_list->length() > 2 && range_cond) {
1.481 + AccessIndexed *first = info->_list->at(0);
1.482 + Instruction *insert_position = first->prev();
1.483 + assert(insert_position->next() == first, "prev was calculated");
1.484 + ValueStack *state = first->state_before();
1.485 +
1.486 + // Load min Constant
1.487 + Constant *min_constant = NULL;
1.488 + if (info->_min != 0) {
1.489 + min_constant = new Constant(new IntConstant(info->_min));
1.490 + NOT_PRODUCT(min_constant->set_printable_bci(first->printable_bci()));
1.491 + insert_position = insert_position->insert_after(min_constant);
1.492 + }
1.493 +
1.494 + // Load max Constant
1.495 + Constant *max_constant = NULL;
1.496 + if (info->_max != 0) {
1.497 + max_constant = new Constant(new IntConstant(info->_max));
1.498 + NOT_PRODUCT(max_constant->set_printable_bci(first->printable_bci()));
1.499 + insert_position = insert_position->insert_after(max_constant);
1.500 + }
1.501 +
1.502 + // Load array length
1.503 + Value length_instr = first->length();
1.504 + if (!length_instr) {
1.505 + ArrayLength *length = new ArrayLength(array, first->state_before()->copy());
1.506 + length->set_exception_state(length->state_before());
1.507 + length->set_flag(Instruction::DeoptimizeOnException, true);
1.508 + insert_position = insert_position->insert_after_same_bci(length);
1.509 + length_instr = length;
1.510 + }
1.511 +
1.512 + // Calculate lower bound
1.513 + Instruction *lower_compare = index_instruction;
1.514 + if (min_constant) {
1.515 + ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, min_constant, lower_compare, false, NULL);
1.516 + insert_position = insert_position->insert_after_same_bci(ao);
1.517 + lower_compare = ao;
1.518 + }
1.519 +
1.520 + // Calculate upper bound
1.521 + Instruction *upper_compare = index_instruction;
1.522 + if (max_constant) {
1.523 + ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, max_constant, upper_compare, false, NULL);
1.524 + insert_position = insert_position->insert_after_same_bci(ao);
1.525 + upper_compare = ao;
1.526 + }
1.527 +
1.528 + // Trick with unsigned compare is done
1.529 + int bci = NOT_PRODUCT(first->printable_bci()) PRODUCT_ONLY(-1);
1.530 + insert_position = predicate(upper_compare, Instruction::aeq, length_instr, state, insert_position, bci);
1.531 + insert_position = predicate_cmp_with_const(lower_compare, Instruction::leq, -1, state, insert_position);
1.532 + for (int j = 0; j<info->_list->length(); j++) {
1.533 + AccessIndexed *ai = info->_list->at(j);
1.534 + remove_range_check(ai);
1.535 + }
1.536 + }
1.537 + }
1.538 +
1.539 + if (list_constant.length() > 1) {
1.540 + AccessIndexed *first = list_constant.at(0);
1.541 + Instruction *insert_position = first->prev();
1.542 + ValueStack *state = first->state_before();
1.543 + // Load max Constant
1.544 + Constant *constant = new Constant(new IntConstant(max_constant));
1.545 + NOT_PRODUCT(constant->set_printable_bci(first->printable_bci()));
1.546 + insert_position = insert_position->insert_after(constant);
1.547 + Instruction *compare_instr = constant;
1.548 + Value length_instr = first->length();
1.549 + if (!length_instr) {
1.550 + ArrayLength *length = new ArrayLength(array, state->copy());
1.551 + length->set_exception_state(length->state_before());
1.552 + length->set_flag(Instruction::DeoptimizeOnException, true);
1.553 + insert_position = insert_position->insert_after_same_bci(length);
1.554 + length_instr = length;
1.555 + }
1.556 + // Compare for greater or equal to array length
1.557 + insert_position = predicate(compare_instr, Instruction::geq, length_instr, state, insert_position);
1.558 + for (int j = 0; j<list_constant.length(); j++) {
1.559 + AccessIndexed *ai = list_constant.at(j);
1.560 + remove_range_check(ai);
1.561 + }
1.562 + }
1.563 + }
1.564 +
1.565 + // Clear data structures for next array
1.566 + for (int i = 0; i < indices.length(); i++) {
1.567 + Instruction *index_instruction = indices.at(i);
1.568 + _access_indexed_info[index_instruction->id()] = NULL;
1.569 + }
1.570 + indices.clear();
1.571 + }
1.572 +}
1.573 +
1.574 +bool RangeCheckEliminator::set_process_block_flags(BlockBegin *block) {
1.575 + Instruction *cur = block;
1.576 + bool process = false;
1.577 +
1.578 + while (cur) {
1.579 + process |= (cur->as_AccessIndexed() != NULL);
1.580 + cur = cur->next();
1.581 + }
1.582 +
1.583 + BlockList *dominates = block->dominates();
1.584 + for (int i=0; i<dominates->length(); i++) {
1.585 + BlockBegin *next = dominates->at(i);
1.586 + process |= set_process_block_flags(next);
1.587 + }
1.588 +
1.589 + if (!process) {
1.590 + block->set(BlockBegin::donot_eliminate_range_checks);
1.591 + }
1.592 + return process;
1.593 +}
1.594 +
1.595 +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) {
1.596 + bool upper_check = true;
1.597 + assert(lower_instr || lower >= 0, "If no lower_instr present, lower must be greater 0");
1.598 + assert(!lower_instr || lower_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
1.599 + assert(!upper_instr || upper_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
1.600 + assert(array_instr, "Array instruction must exist");
1.601 + assert(array_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
1.602 + assert(!length_instr || length_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
1.603 +
1.604 + if (upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr) {
1.605 + // static check
1.606 + if (upper >= 0) return false; // would always trigger a deopt:
1.607 + // array_length + x >= array_length, x >= 0 is always true
1.608 + upper_check = false;
1.609 + }
1.610 + if (lower_instr && lower_instr->as_ArrayLength() && lower_instr->as_ArrayLength()->array() == array_instr) {
1.611 + if (lower > 0) return false;
1.612 + }
1.613 + // No upper check required -> skip
1.614 + if (upper_check && upper_instr && upper_instr->type()->as_ObjectType() && upper_instr == array_instr) {
1.615 + // upper_instr is object means that the upper bound is the length
1.616 + // of the upper_instr.
1.617 + return false;
1.618 + }
1.619 + return true;
1.620 +}
1.621 +
1.622 +Instruction* RangeCheckEliminator::insert_after(Instruction* insert_position, Instruction* instr, int bci) {
1.623 + if (bci != -1) {
1.624 + NOT_PRODUCT(instr->set_printable_bci(bci));
1.625 + return insert_position->insert_after(instr);
1.626 + } else {
1.627 + return insert_position->insert_after_same_bci(instr);
1.628 + }
1.629 +}
1.630 +
1.631 +Instruction* RangeCheckEliminator::predicate(Instruction* left, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) {
1.632 + RangeCheckPredicate *deoptimize = new RangeCheckPredicate(left, cond, true, right, state->copy());
1.633 + return insert_after(insert_position, deoptimize, bci);
1.634 +}
1.635 +
1.636 +Instruction* RangeCheckEliminator::predicate_cmp_with_const(Instruction* instr, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) {
1.637 + Constant *const_instr = new Constant(new IntConstant(constant));
1.638 + insert_position = insert_after(insert_position, const_instr, bci);
1.639 + return predicate(instr, cond, const_instr, state, insert_position);
1.640 +}
1.641 +
1.642 +Instruction* RangeCheckEliminator::predicate_add(Instruction* left, int left_const, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) {
1.643 + Constant *constant = new Constant(new IntConstant(left_const));
1.644 + insert_position = insert_after(insert_position, constant, bci);
1.645 + ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, left, false, NULL);
1.646 + insert_position = insert_position->insert_after_same_bci(ao);
1.647 + return predicate(ao, cond, right, state, insert_position);
1.648 +}
1.649 +
1.650 +Instruction* RangeCheckEliminator::predicate_add_cmp_with_const(Instruction* left, int left_const, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) {
1.651 + Constant *const_instr = new Constant(new IntConstant(constant));
1.652 + insert_position = insert_after(insert_position, const_instr, bci);
1.653 + return predicate_add(left, left_const, cond, const_instr, state, insert_position);
1.654 +}
1.655 +
1.656 +// Insert deoptimization
1.657 +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) {
1.658 + assert(is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, lower, upper_instr, upper), "should have been tested before");
1.659 + bool upper_check = !(upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr);
1.660 +
1.661 + int bci = NOT_PRODUCT(ai->printable_bci()) PRODUCT_ONLY(-1);
1.662 + if (lower_instr) {
1.663 + assert(!lower_instr->type()->as_ObjectType(), "Must not be object type");
1.664 + if (lower == 0) {
1.665 + // Compare for less than 0
1.666 + insert_position = predicate_cmp_with_const(lower_instr, Instruction::lss, 0, state, insert_position, bci);
1.667 + } else if (lower > 0) {
1.668 + // Compare for smaller 0
1.669 + insert_position = predicate_add_cmp_with_const(lower_instr, lower, Instruction::lss, 0, state, insert_position, bci);
1.670 + } else {
1.671 + assert(lower < 0, "");
1.672 + // Add 1
1.673 + lower++;
1.674 + lower = -lower;
1.675 + // Compare for smaller or equal 0
1.676 + insert_position = predicate_cmp_with_const(lower_instr, Instruction::leq, lower, state, insert_position, bci);
1.677 + }
1.678 + }
1.679 +
1.680 + // No upper check required -> skip
1.681 + if (!upper_check) return;
1.682 +
1.683 + // We need to know length of array
1.684 + if (!length_instr) {
1.685 + // Load length if necessary
1.686 + ArrayLength *length = new ArrayLength(array_instr, state->copy());
1.687 + NOT_PRODUCT(length->set_printable_bci(ai->printable_bci()));
1.688 + length->set_exception_state(length->state_before());
1.689 + length->set_flag(Instruction::DeoptimizeOnException, true);
1.690 + insert_position = insert_position->insert_after(length);
1.691 + length_instr = length;
1.692 + }
1.693 +
1.694 + if (!upper_instr) {
1.695 + // Compare for geq array.length
1.696 + insert_position = predicate_cmp_with_const(length_instr, Instruction::leq, upper, state, insert_position, bci);
1.697 + } else {
1.698 + if (upper_instr->type()->as_ObjectType()) {
1.699 + assert(state, "must not be null");
1.700 + assert(upper_instr != array_instr, "should be");
1.701 + ArrayLength *length = new ArrayLength(upper_instr, state->copy());
1.702 + NOT_PRODUCT(length->set_printable_bci(ai->printable_bci()));
1.703 + length->set_flag(Instruction::DeoptimizeOnException, true);
1.704 + length->set_exception_state(length->state_before());
1.705 + insert_position = insert_position->insert_after(length);
1.706 + upper_instr = length;
1.707 + }
1.708 + assert(upper_instr->type()->as_IntType(), "Must not be object type!");
1.709 +
1.710 + if (upper == 0) {
1.711 + // Compare for geq array.length
1.712 + insert_position = predicate(upper_instr, Instruction::geq, length_instr, state, insert_position, bci);
1.713 + } else if (upper < 0) {
1.714 + // Compare for geq array.length
1.715 + insert_position = predicate_add(upper_instr, upper, Instruction::geq, length_instr, state, insert_position, bci);
1.716 + } else {
1.717 + assert(upper > 0, "");
1.718 + upper = -upper;
1.719 + // Compare for geq array.length
1.720 + insert_position = predicate_add(length_instr, upper, Instruction::leq, upper_instr, state, insert_position, bci);
1.721 + }
1.722 + }
1.723 +}
1.724 +
1.725 +// Add if condition
1.726 +void RangeCheckEliminator::add_if_condition(IntegerStack &pushed, Value x, Value y, Instruction::Condition condition) {
1.727 + if (y->as_Constant()) return;
1.728 +
1.729 + int const_value = 0;
1.730 + Value instr_value = x;
1.731 + Constant *c = x->as_Constant();
1.732 + ArithmeticOp *ao = x->as_ArithmeticOp();
1.733 +
1.734 + if (c != NULL) {
1.735 + const_value = c->type()->as_IntConstant()->value();
1.736 + instr_value = NULL;
1.737 + } else if (ao != NULL && (!ao->x()->as_Constant() || !ao->y()->as_Constant()) && ((ao->op() == Bytecodes::_isub && ao->y()->as_Constant()) || ao->op() == Bytecodes::_iadd)) {
1.738 + assert(!ao->x()->as_Constant() || !ao->y()->as_Constant(), "At least one operator must be non-constant!");
1.739 + assert(ao->op() == Bytecodes::_isub || ao->op() == Bytecodes::_iadd, "Operation has to be add or sub!");
1.740 + c = ao->x()->as_Constant();
1.741 + if (c != NULL) {
1.742 + const_value = c->type()->as_IntConstant()->value();
1.743 + instr_value = ao->y();
1.744 + } else {
1.745 + c = ao->y()->as_Constant();
1.746 + if (c != NULL) {
1.747 + const_value = c->type()->as_IntConstant()->value();
1.748 + instr_value = ao->x();
1.749 + }
1.750 + }
1.751 + if (ao->op() == Bytecodes::_isub) {
1.752 + assert(ao->y()->as_Constant(), "1 - x not supported, only x - 1 is valid!");
1.753 + if (const_value > min_jint) {
1.754 + const_value = -const_value;
1.755 + } else {
1.756 + const_value = 0;
1.757 + instr_value = x;
1.758 + }
1.759 + }
1.760 + }
1.761 +
1.762 + update_bound(pushed, y, condition, instr_value, const_value);
1.763 +}
1.764 +
1.765 +// Process If
1.766 +void RangeCheckEliminator::process_if(IntegerStack &pushed, BlockBegin *block, If *cond) {
1.767 + // Only if we are direct true / false successor and NOT both ! (even this may occur)
1.768 + if ((cond->tsux() == block || cond->fsux() == block) && cond->tsux() != cond->fsux()) {
1.769 + Instruction::Condition condition = cond->cond();
1.770 + if (cond->fsux() == block) {
1.771 + condition = Instruction::negate(condition);
1.772 + }
1.773 + Value x = cond->x();
1.774 + Value y = cond->y();
1.775 + if (x->type()->as_IntType() && y->type()->as_IntType()) {
1.776 + add_if_condition(pushed, y, x, condition);
1.777 + add_if_condition(pushed, x, y, Instruction::mirror(condition));
1.778 + }
1.779 + }
1.780 +}
1.781 +
1.782 +// Process access indexed
1.783 +void RangeCheckEliminator::process_access_indexed(BlockBegin *loop_header, BlockBegin *block, AccessIndexed *ai) {
1.784 + TRACE_RANGE_CHECK_ELIMINATION(
1.785 + tty->fill_to(block->dominator_depth()*2)
1.786 + );
1.787 + TRACE_RANGE_CHECK_ELIMINATION(
1.788 + tty->print_cr("Access indexed: index=%d length=%d", ai->index()->id(), (ai->length() != NULL ? ai->length()->id() :-1 ))
1.789 + );
1.790 +
1.791 + if (ai->check_flag(Instruction::NeedsRangeCheckFlag)) {
1.792 + Bound *index_bound = get_bound(ai->index());
1.793 + if (!index_bound->has_lower() || !index_bound->has_upper()) {
1.794 + TRACE_RANGE_CHECK_ELIMINATION(
1.795 + tty->fill_to(block->dominator_depth()*2);
1.796 + tty->print_cr("Index instruction %d has no lower and/or no upper bound!", ai->index()->id())
1.797 + );
1.798 + return;
1.799 + }
1.800 +
1.801 + Bound *array_bound;
1.802 + if (ai->length()) {
1.803 + array_bound = get_bound(ai->length());
1.804 + } else {
1.805 + array_bound = get_bound(ai->array());
1.806 + }
1.807 +
1.808 + if (in_array_bound(index_bound, ai->array()) ||
1.809 + (index_bound && array_bound && index_bound->is_smaller(array_bound) && !index_bound->lower_instr() && index_bound->lower() >= 0)) {
1.810 + TRACE_RANGE_CHECK_ELIMINATION(
1.811 + tty->fill_to(block->dominator_depth()*2);
1.812 + tty->print_cr("Bounds check for instruction %d in block B%d can be fully eliminated!", ai->id(), ai->block()->block_id())
1.813 + );
1.814 +
1.815 + remove_range_check(ai);
1.816 + } else if (_optimistic && loop_header) {
1.817 + assert(ai->array(), "Array must not be null!");
1.818 + assert(ai->index(), "Index must not be null!");
1.819 +
1.820 + // Array instruction
1.821 + Instruction *array_instr = ai->array();
1.822 + if (!loop_invariant(loop_header, array_instr)) {
1.823 + TRACE_RANGE_CHECK_ELIMINATION(
1.824 + tty->fill_to(block->dominator_depth()*2);
1.825 + tty->print_cr("Array %d is not loop invariant to header B%d", ai->array()->id(), loop_header->block_id())
1.826 + );
1.827 + return;
1.828 + }
1.829 +
1.830 + // Lower instruction
1.831 + Value index_instr = ai->index();
1.832 + Value lower_instr = index_bound->lower_instr();
1.833 + if (!loop_invariant(loop_header, lower_instr)) {
1.834 + TRACE_RANGE_CHECK_ELIMINATION(
1.835 + tty->fill_to(block->dominator_depth()*2);
1.836 + tty->print_cr("Lower instruction %d not loop invariant!", lower_instr->id())
1.837 + );
1.838 + return;
1.839 + }
1.840 + if (!lower_instr && index_bound->lower() < 0) {
1.841 + TRACE_RANGE_CHECK_ELIMINATION(
1.842 + tty->fill_to(block->dominator_depth()*2);
1.843 + tty->print_cr("Lower bound smaller than 0 (%d)!", index_bound->lower())
1.844 + );
1.845 + return;
1.846 + }
1.847 +
1.848 + // Upper instruction
1.849 + Value upper_instr = index_bound->upper_instr();
1.850 + if (!loop_invariant(loop_header, upper_instr)) {
1.851 + TRACE_RANGE_CHECK_ELIMINATION(
1.852 + tty->fill_to(block->dominator_depth()*2);
1.853 + tty->print_cr("Upper instruction %d not loop invariant!", upper_instr->id())
1.854 + );
1.855 + return;
1.856 + }
1.857 +
1.858 + // Length instruction
1.859 + Value length_instr = ai->length();
1.860 + if (!loop_invariant(loop_header, length_instr)) {
1.861 + // Generate length instruction yourself!
1.862 + length_instr = NULL;
1.863 + }
1.864 +
1.865 + TRACE_RANGE_CHECK_ELIMINATION(
1.866 + tty->fill_to(block->dominator_depth()*2);
1.867 + tty->print_cr("LOOP INVARIANT access indexed %d found in block B%d!", ai->id(), ai->block()->block_id())
1.868 + );
1.869 +
1.870 + BlockBegin *pred_block = loop_header->dominator();
1.871 + assert(pred_block != NULL, "Every loop header has a dominator!");
1.872 + BlockEnd *pred_block_end = pred_block->end();
1.873 + Instruction *insert_position = pred_block_end->prev();
1.874 + ValueStack *state = pred_block_end->state_before();
1.875 + if (pred_block_end->as_Goto() && state == NULL) state = pred_block_end->state();
1.876 + assert(state, "State must not be null");
1.877 +
1.878 + // Add deoptimization to dominator of loop header
1.879 + TRACE_RANGE_CHECK_ELIMINATION(
1.880 + tty->fill_to(block->dominator_depth()*2);
1.881 + tty->print_cr("Inserting deopt at bci %d in block B%d!", state->bci(), insert_position->block()->block_id())
1.882 + );
1.883 +
1.884 + if (!is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper())) {
1.885 + TRACE_RANGE_CHECK_ELIMINATION(
1.886 + tty->fill_to(block->dominator_depth()*2);
1.887 + tty->print_cr("Could not eliminate because of static analysis!")
1.888 + );
1.889 + return;
1.890 + }
1.891 +
1.892 + insert_deoptimization(state, insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper(), ai);
1.893 +
1.894 + // Finally remove the range check!
1.895 + remove_range_check(ai);
1.896 + }
1.897 + }
1.898 +}
1.899 +
1.900 +void RangeCheckEliminator::remove_range_check(AccessIndexed *ai) {
1.901 + ai->set_flag(Instruction::NeedsRangeCheckFlag, false);
1.902 + // no range check, no need for the length instruction anymore
1.903 + ai->clear_length();
1.904 +
1.905 + TRACE_RANGE_CHECK_ELIMINATION(
1.906 + tty->fill_to(ai->dominator_depth()*2);
1.907 + tty->print_cr("Range check for instruction %d eliminated!", ai->id());
1.908 + );
1.909 +
1.910 + ASSERT_RANGE_CHECK_ELIMINATION(
1.911 + Value array_length = ai->length();
1.912 + if (!array_length) {
1.913 + array_length = ai->array();
1.914 + assert(array_length->type()->as_ObjectType(), "Has to be object type!");
1.915 + }
1.916 + int cur_constant = -1;
1.917 + Value cur_value = array_length;
1.918 + if (cur_value->type()->as_IntConstant()) {
1.919 + cur_constant += cur_value->type()->as_IntConstant()->value();
1.920 + cur_value = NULL;
1.921 + }
1.922 + Bound *new_index_bound = new Bound(0, NULL, cur_constant, cur_value);
1.923 + add_assertions(new_index_bound, ai->index(), ai);
1.924 + );
1.925 +}
1.926 +
1.927 +// Calculate bounds for instruction in this block and children blocks in the dominator tree
1.928 +void RangeCheckEliminator::calc_bounds(BlockBegin *block, BlockBegin *loop_header) {
1.929 + // Ensures a valid loop_header
1.930 + assert(!loop_header || loop_header->is_set(BlockBegin::linear_scan_loop_header_flag), "Loop header has to be real !");
1.931 +
1.932 + // Tracing output
1.933 + TRACE_RANGE_CHECK_ELIMINATION(
1.934 + tty->fill_to(block->dominator_depth()*2);
1.935 + tty->print_cr("Block B%d", block->block_id());
1.936 + );
1.937 +
1.938 + // Pushed stack for conditions
1.939 + IntegerStack pushed;
1.940 + // Process If
1.941 + BlockBegin *parent = block->dominator();
1.942 + if (parent != NULL) {
1.943 + If *cond = parent->end()->as_If();
1.944 + if (cond != NULL) {
1.945 + process_if(pushed, block, cond);
1.946 + }
1.947 + }
1.948 +
1.949 + // Interate over current block
1.950 + InstructionList arrays;
1.951 + AccessIndexedList accessIndexed;
1.952 + Instruction *cur = block;
1.953 +
1.954 + while (cur) {
1.955 + // Ensure cur wasn't inserted during the elimination
1.956 + if (cur->id() < this->_bounds.length()) {
1.957 + // Process only if it is an access indexed instruction
1.958 + AccessIndexed *ai = cur->as_AccessIndexed();
1.959 + if (ai != NULL) {
1.960 + process_access_indexed(loop_header, block, ai);
1.961 + accessIndexed.append(ai);
1.962 + if (!arrays.contains(ai->array())) {
1.963 + arrays.append(ai->array());
1.964 + }
1.965 + Bound *b = get_bound(ai->index());
1.966 + if (!b->lower_instr()) {
1.967 + // Lower bound is constant
1.968 + update_bound(pushed, ai->index(), Instruction::geq, NULL, 0);
1.969 + }
1.970 + if (!b->has_upper()) {
1.971 + if (ai->length() && ai->length()->type()->as_IntConstant()) {
1.972 + int value = ai->length()->type()->as_IntConstant()->value();
1.973 + update_bound(pushed, ai->index(), Instruction::lss, NULL, value);
1.974 + } else {
1.975 + // Has no upper bound
1.976 + Instruction *instr = ai->length();
1.977 + if (instr != NULL) instr = ai->array();
1.978 + update_bound(pushed, ai->index(), Instruction::lss, instr, 0);
1.979 + }
1.980 + }
1.981 + }
1.982 + }
1.983 + cur = cur->next();
1.984 + }
1.985 +
1.986 + // Output current condition stack
1.987 + TRACE_RANGE_CHECK_ELIMINATION(dump_condition_stack(block));
1.988 +
1.989 + // Do in block motion of range checks
1.990 + in_block_motion(block, accessIndexed, arrays);
1.991 +
1.992 + // Call all dominated blocks
1.993 + for (int i=0; i<block->dominates()->length(); i++) {
1.994 + BlockBegin *next = block->dominates()->at(i);
1.995 + if (!next->is_set(BlockBegin::donot_eliminate_range_checks)) {
1.996 + // if current block is a loop header and:
1.997 + // - next block belongs to the same loop
1.998 + // or
1.999 + // - next block belongs to an inner loop
1.1000 + // then current block is the loop header for next block
1.1001 + if (block->is_set(BlockBegin::linear_scan_loop_header_flag) && (block->loop_index() == next->loop_index() || next->loop_depth() > block->loop_depth())) {
1.1002 + calc_bounds(next, block);
1.1003 + } else {
1.1004 + calc_bounds(next, loop_header);
1.1005 + }
1.1006 + }
1.1007 + }
1.1008 +
1.1009 + // Reset stack
1.1010 + for (int i=0; i<pushed.length(); i++) {
1.1011 + _bounds[pushed[i]]->pop();
1.1012 + }
1.1013 +}
1.1014 +
1.1015 +#ifndef PRODUCT
1.1016 +// Dump condition stack
1.1017 +void RangeCheckEliminator::dump_condition_stack(BlockBegin *block) {
1.1018 + for (int i=0; i<_ir->linear_scan_order()->length(); i++) {
1.1019 + BlockBegin *cur_block = _ir->linear_scan_order()->at(i);
1.1020 + Instruction *instr = cur_block;
1.1021 + for_each_phi_fun(cur_block, phi,
1.1022 + BoundStack *bound_stack = _bounds.at(phi->id());
1.1023 + if (bound_stack && bound_stack->length() > 0) {
1.1024 + Bound *bound = bound_stack->top();
1.1025 + if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != phi || bound->upper_instr() != phi || bound->lower() != 0 || bound->upper() != 0)) {
1.1026 + TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth());
1.1027 + tty->print("i%d", phi->id());
1.1028 + tty->print(": ");
1.1029 + bound->print();
1.1030 + tty->cr();
1.1031 + );
1.1032 + }
1.1033 + });
1.1034 +
1.1035 + while (!instr->as_BlockEnd()) {
1.1036 + if (instr->id() < _bounds.length()) {
1.1037 + BoundStack *bound_stack = _bounds.at(instr->id());
1.1038 + if (bound_stack && bound_stack->length() > 0) {
1.1039 + Bound *bound = bound_stack->top();
1.1040 + if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != instr || bound->upper_instr() != instr || bound->lower() != 0 || bound->upper() != 0)) {
1.1041 + TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth());
1.1042 + tty->print("i%d", instr->id());
1.1043 + tty->print(": ");
1.1044 + bound->print();
1.1045 + tty->cr();
1.1046 + );
1.1047 + }
1.1048 + }
1.1049 + }
1.1050 + instr = instr->next();
1.1051 + }
1.1052 + }
1.1053 +}
1.1054 +#endif
1.1055 +
1.1056 +// Verification or the IR
1.1057 +RangeCheckEliminator::Verification::Verification(IR *ir) : _used(BlockBegin::number_of_blocks(), false) {
1.1058 + this->_ir = ir;
1.1059 + ir->iterate_linear_scan_order(this);
1.1060 +}
1.1061 +
1.1062 +// Verify this block
1.1063 +void RangeCheckEliminator::Verification::block_do(BlockBegin *block) {
1.1064 + If *cond = block->end()->as_If();
1.1065 + // Watch out: tsux and fsux can be the same!
1.1066 + if (block->number_of_sux() > 1) {
1.1067 + for (int i=0; i<block->number_of_sux(); i++) {
1.1068 + BlockBegin *sux = block->sux_at(i);
1.1069 + BlockBegin *pred = NULL;
1.1070 + for (int j=0; j<sux->number_of_preds(); j++) {
1.1071 + BlockBegin *cur = sux->pred_at(j);
1.1072 + assert(cur != NULL, "Predecessor must not be null");
1.1073 + if (!pred) {
1.1074 + pred = cur;
1.1075 + }
1.1076 + assert(cur == pred, "Block must not have more than one predecessor if its predecessor has more than one successor");
1.1077 + }
1.1078 + assert(sux->number_of_preds() >= 1, "Block must have at least one predecessor");
1.1079 + assert(sux->pred_at(0) == block, "Wrong successor");
1.1080 + }
1.1081 + }
1.1082 +
1.1083 + BlockBegin *dominator = block->dominator();
1.1084 + if (dominator) {
1.1085 + assert(block != _ir->start(), "Start block must not have a dominator!");
1.1086 + assert(can_reach(dominator, block), "Dominator can't reach his block !");
1.1087 + assert(can_reach(_ir->start(), dominator), "Dominator is unreachable !");
1.1088 + assert(!can_reach(_ir->start(), block, dominator), "Wrong dominator ! Block can be reached anyway !");
1.1089 + BlockList *all_blocks = _ir->linear_scan_order();
1.1090 + for (int i=0; i<all_blocks->length(); i++) {
1.1091 + BlockBegin *cur = all_blocks->at(i);
1.1092 + if (cur != dominator && cur != block) {
1.1093 + assert(can_reach(dominator, block, cur), "There has to be another dominator!");
1.1094 + }
1.1095 + }
1.1096 + } else {
1.1097 + assert(block == _ir->start(), "Only start block must not have a dominator");
1.1098 + }
1.1099 +
1.1100 + if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) {
1.1101 + int loop_index = block->loop_index();
1.1102 + BlockList *all_blocks = _ir->linear_scan_order();
1.1103 + assert(block->number_of_preds() >= 1, "Block must have at least one predecessor");
1.1104 + assert(!block->is_set(BlockBegin::exception_entry_flag), "Loop header must not be exception handler!");
1.1105 + // Sometimes, the backbranch comes from an exception handler. In
1.1106 + // this case, loop indexes/loop depths may not appear correct.
1.1107 + bool loop_through_xhandler = false;
1.1108 + for (int i = 0; i < block->number_of_exception_handlers(); i++) {
1.1109 + BlockBegin *xhandler = block->exception_handler_at(i);
1.1110 + for (int j = 0; j < block->number_of_preds(); j++) {
1.1111 + if (dominates(xhandler, block->pred_at(j)) || xhandler == block->pred_at(j)) {
1.1112 + loop_through_xhandler = true;
1.1113 + }
1.1114 + }
1.1115 + }
1.1116 +
1.1117 + for (int i=0; i<block->number_of_sux(); i++) {
1.1118 + BlockBegin *sux = block->sux_at(i);
1.1119 + assert(sux->loop_depth() != block->loop_depth() || sux->loop_index() == block->loop_index() || loop_through_xhandler, "Loop index has to be same");
1.1120 + assert(sux->loop_depth() == block->loop_depth() || sux->loop_index() != block->loop_index(), "Loop index has to be different");
1.1121 + }
1.1122 +
1.1123 + for (int i=0; i<all_blocks->length(); i++) {
1.1124 + BlockBegin *cur = all_blocks->at(i);
1.1125 + if (cur->loop_index() == loop_index && cur != block) {
1.1126 + assert(dominates(block->dominator(), cur), "Dominator of loop header must dominate all loop blocks");
1.1127 + }
1.1128 + }
1.1129 + }
1.1130 +
1.1131 + Instruction *cur = block;
1.1132 + while (cur) {
1.1133 + assert(cur->block() == block, "Block begin has to be set correctly!");
1.1134 + cur = cur->next();
1.1135 + }
1.1136 +}
1.1137 +
1.1138 +// Loop header must dominate all loop blocks
1.1139 +bool RangeCheckEliminator::Verification::dominates(BlockBegin *dominator, BlockBegin *block) {
1.1140 + BlockBegin *cur = block->dominator();
1.1141 + while (cur && cur != dominator) {
1.1142 + cur = cur->dominator();
1.1143 + }
1.1144 + return cur == dominator;
1.1145 +}
1.1146 +
1.1147 +// Try to reach Block end beginning in Block start and not using Block dont_use
1.1148 +bool RangeCheckEliminator::Verification::can_reach(BlockBegin *start, BlockBegin *end, BlockBegin *dont_use /* = NULL */) {
1.1149 + if (start == end) return start != dont_use;
1.1150 + // Simple BSF from start to end
1.1151 + // BlockBeginList _current;
1.1152 + for (int i=0; i<_used.length(); i++) {
1.1153 + _used[i] = false;
1.1154 + }
1.1155 + _current.truncate(0);
1.1156 + _successors.truncate(0);
1.1157 + if (start != dont_use) {
1.1158 + _current.push(start);
1.1159 + _used[start->block_id()] = true;
1.1160 + }
1.1161 +
1.1162 + // BlockBeginList _successors;
1.1163 + while (_current.length() > 0) {
1.1164 + BlockBegin *cur = _current.pop();
1.1165 + // Add exception handlers to list
1.1166 + for (int i=0; i<cur->number_of_exception_handlers(); i++) {
1.1167 + BlockBegin *xhandler = cur->exception_handler_at(i);
1.1168 + _successors.push(xhandler);
1.1169 + // Add exception handlers of _successors to list
1.1170 + for (int j=0; j<xhandler->number_of_exception_handlers(); j++) {
1.1171 + BlockBegin *sux_xhandler = xhandler->exception_handler_at(j);
1.1172 + _successors.push(sux_xhandler);
1.1173 + }
1.1174 + }
1.1175 + // Add normal _successors to list
1.1176 + for (int i=0; i<cur->number_of_sux(); i++) {
1.1177 + BlockBegin *sux = cur->sux_at(i);
1.1178 + _successors.push(sux);
1.1179 + // Add exception handlers of _successors to list
1.1180 + for (int j=0; j<sux->number_of_exception_handlers(); j++) {
1.1181 + BlockBegin *xhandler = sux->exception_handler_at(j);
1.1182 + _successors.push(xhandler);
1.1183 + }
1.1184 + }
1.1185 + for (int i=0; i<_successors.length(); i++) {
1.1186 + BlockBegin *sux = _successors[i];
1.1187 + assert(sux != NULL, "Successor must not be NULL!");
1.1188 + if (sux == end) {
1.1189 + return true;
1.1190 + }
1.1191 + if (sux != dont_use && !_used[sux->block_id()]) {
1.1192 + _used[sux->block_id()] = true;
1.1193 + _current.push(sux);
1.1194 + }
1.1195 + }
1.1196 + _successors.truncate(0);
1.1197 + }
1.1198 +
1.1199 + return false;
1.1200 +}
1.1201 +
1.1202 +// Bound
1.1203 +RangeCheckEliminator::Bound::~Bound() {
1.1204 +}
1.1205 +
1.1206 +// Bound constructor
1.1207 +RangeCheckEliminator::Bound::Bound() {
1.1208 + init();
1.1209 + this->_lower = min_jint;
1.1210 + this->_upper = max_jint;
1.1211 + this->_lower_instr = NULL;
1.1212 + this->_upper_instr = NULL;
1.1213 +}
1.1214 +
1.1215 +// Bound constructor
1.1216 +RangeCheckEliminator::Bound::Bound(int lower, Value lower_instr, int upper, Value upper_instr) {
1.1217 + init();
1.1218 + assert(!lower_instr || !lower_instr->as_Constant() || !lower_instr->type()->as_IntConstant(), "Must not be constant!");
1.1219 + assert(!upper_instr || !upper_instr->as_Constant() || !upper_instr->type()->as_IntConstant(), "Must not be constant!");
1.1220 + this->_lower = lower;
1.1221 + this->_upper = upper;
1.1222 + this->_lower_instr = lower_instr;
1.1223 + this->_upper_instr = upper_instr;
1.1224 +}
1.1225 +
1.1226 +// Bound constructor
1.1227 +RangeCheckEliminator::Bound::Bound(Instruction::Condition cond, Value v, int constant) {
1.1228 + assert(!v || (v->type() && (v->type()->as_IntType() || v->type()->as_ObjectType())), "Type must be array or integer!");
1.1229 + assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!");
1.1230 +
1.1231 + init();
1.1232 + if (cond == Instruction::eql) {
1.1233 + _lower = constant;
1.1234 + _lower_instr = v;
1.1235 + _upper = constant;
1.1236 + _upper_instr = v;
1.1237 + } else if (cond == Instruction::neq) {
1.1238 + _lower = min_jint;
1.1239 + _upper = max_jint;
1.1240 + _lower_instr = NULL;
1.1241 + _upper_instr = NULL;
1.1242 + if (v == NULL) {
1.1243 + if (constant == min_jint) {
1.1244 + _lower++;
1.1245 + }
1.1246 + if (constant == max_jint) {
1.1247 + _upper--;
1.1248 + }
1.1249 + }
1.1250 + } else if (cond == Instruction::geq) {
1.1251 + _lower = constant;
1.1252 + _lower_instr = v;
1.1253 + _upper = max_jint;
1.1254 + _upper_instr = NULL;
1.1255 + } else if (cond == Instruction::leq) {
1.1256 + _lower = min_jint;
1.1257 + _lower_instr = NULL;
1.1258 + _upper = constant;
1.1259 + _upper_instr = v;
1.1260 + } else {
1.1261 + ShouldNotReachHere();
1.1262 + }
1.1263 +}
1.1264 +
1.1265 +// Set lower
1.1266 +void RangeCheckEliminator::Bound::set_lower(int value, Value v) {
1.1267 + assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!");
1.1268 + this->_lower = value;
1.1269 + this->_lower_instr = v;
1.1270 +}
1.1271 +
1.1272 +// Set upper
1.1273 +void RangeCheckEliminator::Bound::set_upper(int value, Value v) {
1.1274 + assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!");
1.1275 + this->_upper = value;
1.1276 + this->_upper_instr = v;
1.1277 +}
1.1278 +
1.1279 +// Add constant -> no overflow may occur
1.1280 +void RangeCheckEliminator::Bound::add_constant(int value) {
1.1281 + this->_lower += value;
1.1282 + this->_upper += value;
1.1283 +}
1.1284 +
1.1285 +// Init
1.1286 +void RangeCheckEliminator::Bound::init() {
1.1287 +}
1.1288 +
1.1289 +// or
1.1290 +void RangeCheckEliminator::Bound::or_op(Bound *b) {
1.1291 + // Watch out, bound is not guaranteed not to overflow!
1.1292 + // Update lower bound
1.1293 + if (_lower_instr != b->_lower_instr || (_lower_instr && _lower != b->_lower)) {
1.1294 + _lower_instr = NULL;
1.1295 + _lower = min_jint;
1.1296 + } else {
1.1297 + _lower = MIN2(_lower, b->_lower);
1.1298 + }
1.1299 + // Update upper bound
1.1300 + if (_upper_instr != b->_upper_instr || (_upper_instr && _upper != b->_upper)) {
1.1301 + _upper_instr = NULL;
1.1302 + _upper = max_jint;
1.1303 + } else {
1.1304 + _upper = MAX2(_upper, b->_upper);
1.1305 + }
1.1306 +}
1.1307 +
1.1308 +// and
1.1309 +void RangeCheckEliminator::Bound::and_op(Bound *b) {
1.1310 + // Update lower bound
1.1311 + if (_lower_instr == b->_lower_instr) {
1.1312 + _lower = MAX2(_lower, b->_lower);
1.1313 + }
1.1314 + if (b->has_lower()) {
1.1315 + bool set = true;
1.1316 + if (_lower_instr != NULL && b->_lower_instr != NULL) {
1.1317 + set = (_lower_instr->dominator_depth() > b->_lower_instr->dominator_depth());
1.1318 + }
1.1319 + if (set) {
1.1320 + _lower = b->_lower;
1.1321 + _lower_instr = b->_lower_instr;
1.1322 + }
1.1323 + }
1.1324 + // Update upper bound
1.1325 + if (_upper_instr == b->_upper_instr) {
1.1326 + _upper = MIN2(_upper, b->_upper);
1.1327 + }
1.1328 + if (b->has_upper()) {
1.1329 + bool set = true;
1.1330 + if (_upper_instr != NULL && b->_upper_instr != NULL) {
1.1331 + set = (_upper_instr->dominator_depth() > b->_upper_instr->dominator_depth());
1.1332 + }
1.1333 + if (set) {
1.1334 + _upper = b->_upper;
1.1335 + _upper_instr = b->_upper_instr;
1.1336 + }
1.1337 + }
1.1338 +}
1.1339 +
1.1340 +// has_upper
1.1341 +bool RangeCheckEliminator::Bound::has_upper() {
1.1342 + return _upper_instr != NULL || _upper < max_jint;
1.1343 +}
1.1344 +
1.1345 +// is_smaller
1.1346 +bool RangeCheckEliminator::Bound::is_smaller(Bound *b) {
1.1347 + if (b->_lower_instr != _upper_instr) {
1.1348 + return false;
1.1349 + }
1.1350 + return _upper < b->_lower;
1.1351 +}
1.1352 +
1.1353 +// has_lower
1.1354 +bool RangeCheckEliminator::Bound::has_lower() {
1.1355 + return _lower_instr != NULL || _lower > min_jint;
1.1356 +}
1.1357 +
1.1358 +// in_array_bound
1.1359 +bool RangeCheckEliminator::in_array_bound(Bound *bound, Value array){
1.1360 + if (!bound) return false;
1.1361 + assert(array != NULL, "Must not be null!");
1.1362 + assert(bound != NULL, "Must not be null!");
1.1363 + if (bound->lower() >=0 && bound->lower_instr() == NULL && bound->upper() < 0 && bound->upper_instr() != NULL) {
1.1364 + ArrayLength *len = bound->upper_instr()->as_ArrayLength();
1.1365 + if (bound->upper_instr() == array || (len != NULL && len->array() == array)) {
1.1366 + return true;
1.1367 + }
1.1368 + }
1.1369 + return false;
1.1370 +}
1.1371 +
1.1372 +// remove_lower
1.1373 +void RangeCheckEliminator::Bound::remove_lower() {
1.1374 + _lower = min_jint;
1.1375 + _lower_instr = NULL;
1.1376 +}
1.1377 +
1.1378 +// remove_upper
1.1379 +void RangeCheckEliminator::Bound::remove_upper() {
1.1380 + _upper = max_jint;
1.1381 + _upper_instr = NULL;
1.1382 +}
1.1383 +
1.1384 +// upper
1.1385 +int RangeCheckEliminator::Bound::upper() {
1.1386 + return _upper;
1.1387 +}
1.1388 +
1.1389 +// lower
1.1390 +int RangeCheckEliminator::Bound::lower() {
1.1391 + return _lower;
1.1392 +}
1.1393 +
1.1394 +// upper_instr
1.1395 +Value RangeCheckEliminator::Bound::upper_instr() {
1.1396 + return _upper_instr;
1.1397 +}
1.1398 +
1.1399 +// lower_instr
1.1400 +Value RangeCheckEliminator::Bound::lower_instr() {
1.1401 + return _lower_instr;
1.1402 +}
1.1403 +
1.1404 +// print
1.1405 +void RangeCheckEliminator::Bound::print() {
1.1406 + tty->print("%s", "");
1.1407 + if (this->_lower_instr || this->_lower != min_jint) {
1.1408 + if (this->_lower_instr) {
1.1409 + tty->print("i%d", this->_lower_instr->id());
1.1410 + if (this->_lower > 0) {
1.1411 + tty->print("+%d", _lower);
1.1412 + }
1.1413 + if (this->_lower < 0) {
1.1414 + tty->print("%d", _lower);
1.1415 + }
1.1416 + } else {
1.1417 + tty->print("%d", _lower);
1.1418 + }
1.1419 + tty->print(" <= ");
1.1420 + }
1.1421 + tty->print("x");
1.1422 + if (this->_upper_instr || this->_upper != max_jint) {
1.1423 + tty->print(" <= ");
1.1424 + if (this->_upper_instr) {
1.1425 + tty->print("i%d", this->_upper_instr->id());
1.1426 + if (this->_upper > 0) {
1.1427 + tty->print("+%d", _upper);
1.1428 + }
1.1429 + if (this->_upper < 0) {
1.1430 + tty->print("%d", _upper);
1.1431 + }
1.1432 + } else {
1.1433 + tty->print("%d", _upper);
1.1434 + }
1.1435 + }
1.1436 +}
1.1437 +
1.1438 +// Copy
1.1439 +RangeCheckEliminator::Bound *RangeCheckEliminator::Bound::copy() {
1.1440 + Bound *b = new Bound();
1.1441 + b->_lower = _lower;
1.1442 + b->_lower_instr = _lower_instr;
1.1443 + b->_upper = _upper;
1.1444 + b->_upper_instr = _upper_instr;
1.1445 + return b;
1.1446 +}
1.1447 +
1.1448 +#ifdef ASSERT
1.1449 +// Add assertion
1.1450 +void RangeCheckEliminator::Bound::add_assertion(Instruction *instruction, Instruction *position, int i, Value instr, Instruction::Condition cond) {
1.1451 + Instruction *result = position;
1.1452 + Instruction *compare_with = NULL;
1.1453 + ValueStack *state = position->state_before();
1.1454 + if (position->as_BlockEnd() && !position->as_Goto()) {
1.1455 + state = position->as_BlockEnd()->state_before();
1.1456 + }
1.1457 + Instruction *instruction_before = position->prev();
1.1458 + if (position->as_Return() && Compilation::current()->method()->is_synchronized() && instruction_before->as_MonitorExit()) {
1.1459 + instruction_before = instruction_before->prev();
1.1460 + }
1.1461 + result = instruction_before;
1.1462 + // Load constant only if needed
1.1463 + Constant *constant = NULL;
1.1464 + if (i != 0 || !instr) {
1.1465 + constant = new Constant(new IntConstant(i));
1.1466 + NOT_PRODUCT(constant->set_printable_bci(position->printable_bci()));
1.1467 + result = result->insert_after(constant);
1.1468 + compare_with = constant;
1.1469 + }
1.1470 +
1.1471 + if (instr) {
1.1472 + assert(instr->type()->as_ObjectType() || instr->type()->as_IntType(), "Type must be array or integer!");
1.1473 + compare_with = instr;
1.1474 + // Load array length if necessary
1.1475 + Instruction *op = instr;
1.1476 + if (instr->type()->as_ObjectType()) {
1.1477 + assert(state, "must not be null");
1.1478 + ArrayLength *length = new ArrayLength(instr, state->copy());
1.1479 + NOT_PRODUCT(length->set_printable_bci(position->printable_bci()));
1.1480 + length->set_exception_state(length->state_before());
1.1481 + result = result->insert_after(length);
1.1482 + op = length;
1.1483 + compare_with = length;
1.1484 + }
1.1485 + // Add operation only if necessary
1.1486 + if (constant) {
1.1487 + ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, op, false, NULL);
1.1488 + NOT_PRODUCT(ao->set_printable_bci(position->printable_bci()));
1.1489 + result = result->insert_after(ao);
1.1490 + compare_with = ao;
1.1491 + // TODO: Check that add operation does not overflow!
1.1492 + }
1.1493 + }
1.1494 + assert(compare_with != NULL, "You have to compare with something!");
1.1495 + assert(instruction != NULL, "Instruction must not be null!");
1.1496 +
1.1497 + if (instruction->type()->as_ObjectType()) {
1.1498 + // Load array length if necessary
1.1499 + Instruction *op = instruction;
1.1500 + assert(state, "must not be null");
1.1501 + ArrayLength *length = new ArrayLength(instruction, state->copy());
1.1502 + length->set_exception_state(length->state_before());
1.1503 + NOT_PRODUCT(length->set_printable_bci(position->printable_bci()));
1.1504 + result = result->insert_after(length);
1.1505 + instruction = length;
1.1506 + }
1.1507 +
1.1508 + Assert *assert = new Assert(instruction, cond, false, compare_with);
1.1509 + NOT_PRODUCT(assert->set_printable_bci(position->printable_bci()));
1.1510 + result->insert_after(assert);
1.1511 +}
1.1512 +
1.1513 +// Add assertions
1.1514 +void RangeCheckEliminator::add_assertions(Bound *bound, Instruction *instruction, Instruction *position) {
1.1515 + // Add lower bound assertion
1.1516 + if (bound->has_lower()) {
1.1517 + bound->add_assertion(instruction, position, bound->lower(), bound->lower_instr(), Instruction::geq);
1.1518 + }
1.1519 + // Add upper bound assertion
1.1520 + if (bound->has_upper()) {
1.1521 + bound->add_assertion(instruction, position, bound->upper(), bound->upper_instr(), Instruction::leq);
1.1522 + }
1.1523 +}
1.1524 +#endif
1.1525 +
