2
* Copyright (c) 2012, 2024, Oracle and/or its affiliates. All rights reserved.
3
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5
* This code is free software; you can redistribute it and/or modify it
6
* under the terms of the GNU General Public License version 2 only, as
7
* published by the Free Software Foundation.
9
* This code is distributed in the hope that it will be useful, but WITHOUT
10
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12
* version 2 for more details (a copy is included in the LICENSE file that
13
* accompanied this code).
15
* You should have received a copy of the GNU General Public License version
16
* 2 along with this work; if not, write to the Free Software Foundation,
17
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20
* or visit www.oracle.com if you need additional information or have any
25
#include "precompiled.hpp"
26
#include "c1/c1_ValueStack.hpp"
27
#include "c1/c1_RangeCheckElimination.hpp"
28
#include "c1/c1_IR.hpp"
29
#include "c1/c1_Canonicalizer.hpp"
30
#include "c1/c1_ValueMap.hpp"
31
#include "ci/ciMethodData.hpp"
32
#include "runtime/deoptimization.hpp"
34
#include "utilities/bitMap.inline.hpp"
37
// Macros for the Trace and the Assertion flag
39
#define TRACE_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination) { code; }
40
#define ASSERT_RANGE_CHECK_ELIMINATION(code) if (AssertRangeCheckElimination) { code; }
41
#define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination || AssertRangeCheckElimination) { code; }
43
#define TRACE_RANGE_CHECK_ELIMINATION(code)
44
#define ASSERT_RANGE_CHECK_ELIMINATION(code)
45
#define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code)
48
// Entry point for the optimization
49
void RangeCheckElimination::eliminate(IR *ir) {
50
bool do_elimination = ir->compilation()->has_access_indexed();
51
ASSERT_RANGE_CHECK_ELIMINATION(do_elimination = true);
53
RangeCheckEliminator rce(ir);
58
RangeCheckEliminator::RangeCheckEliminator(IR *ir) :
59
_bounds(Instruction::number_of_instructions(), Instruction::number_of_instructions(), nullptr),
60
_access_indexed_info(Instruction::number_of_instructions(), Instruction::number_of_instructions(), nullptr)
62
_visitor.set_range_check_eliminator(this);
64
_number_of_instructions = Instruction::number_of_instructions();
65
_optimistic = ir->compilation()->is_optimistic();
67
TRACE_RANGE_CHECK_ELIMINATION(
69
tty->print_cr("Range check elimination");
70
ir->method()->print_name(tty);
74
TRACE_RANGE_CHECK_ELIMINATION(
75
tty->print_cr("optimistic=%d", (int)_optimistic);
79
// Verifies several conditions that must be true on the IR-input. Only used for debugging purposes.
80
TRACE_RANGE_CHECK_ELIMINATION(
81
tty->print_cr("Verification of IR . . .");
83
Verification verification(ir);
86
// Set process block flags
87
// Optimization so a blocks is only processed if it contains an access indexed instruction or if
88
// one of its children in the dominator tree contains an access indexed instruction.
89
set_process_block_flags(ir->start());
91
// Pass over instructions in the dominator tree
92
TRACE_RANGE_CHECK_ELIMINATION(
93
tty->print_cr("Starting pass over dominator tree . . .")
95
calc_bounds(ir->start(), nullptr);
97
TRACE_RANGE_CHECK_ELIMINATION(
98
tty->print_cr("Finished!")
102
// Instruction specific work for some instructions
104
void RangeCheckEliminator::Visitor::do_Constant(Constant *c) {
105
IntConstant *ic = c->type()->as_IntConstant();
107
int value = ic->value();
108
_bound = new Bound(value, nullptr, value, nullptr);
113
void RangeCheckEliminator::Visitor::do_LogicOp(LogicOp *lo) {
114
if (lo->type()->as_IntType() && lo->op() == Bytecodes::_iand && (lo->x()->as_Constant() || lo->y()->as_Constant())) {
116
Constant *c = lo->x()->as_Constant();
118
constant = c->type()->as_IntConstant()->value();
120
constant = lo->y()->as_Constant()->type()->as_IntConstant()->value();
123
_bound = new Bound(0, nullptr, constant, nullptr);
129
void RangeCheckEliminator::Visitor::do_Phi(Phi *phi) {
130
if (!phi->type()->as_IntType() && !phi->type()->as_ObjectType()) return;
132
BlockBegin *block = phi->block();
133
int op_count = phi->operand_count();
134
bool has_upper = true;
135
bool has_lower = true;
136
assert(phi, "Phi must not be null");
137
Bound* bound = nullptr;
139
// TODO: support more difficult phis
140
for (int i=0; i<op_count; i++) {
141
Value v = phi->operand_at(i);
143
if (v == phi) continue;
145
// Check if instruction is connected with phi itself
146
Op2 *op2 = v->as_Op2();
147
if (op2 != nullptr) {
150
if ((x == phi || y == phi)) {
155
ArithmeticOp *ao = v->as_ArithmeticOp();
156
if (ao != nullptr && ao->op() == Bytecodes::_iadd) {
157
assert(ao->op() == Bytecodes::_iadd, "Has to be add!");
158
if (ao->type()->as_IntType()) {
159
Constant *c = other->as_Constant();
161
assert(c->type()->as_IntConstant(), "Constant has to be of type integer");
162
int value = c->type()->as_IntConstant()->value();
165
} else if (value > 1) {
166
// Overflow not guaranteed
169
} else if (value < 0) {
179
// No connection -> new bound
180
Bound *v_bound = _rce->get_bound(v);
182
int cur_constant = 0;
185
if (v->type()->as_IntConstant()) {
186
cur_constant = v->type()->as_IntConstant()->value();
189
if (!v_bound->has_upper() || !v_bound->has_lower()) {
190
cur_bound = new Bound(cur_constant, cur_value, cur_constant, cur_value);
196
bound = cur_bound->copy();
198
bound->or_op(cur_bound);
209
bound->remove_upper();
212
bound->remove_lower();
216
_bound = new Bound();
222
void RangeCheckEliminator::Visitor::do_ArithmeticOp(ArithmeticOp *ao) {
226
if (ao->op() == Bytecodes::_irem) {
227
Bound* x_bound = _rce->get_bound(x);
228
Bound* y_bound = _rce->get_bound(y);
229
if (x_bound->lower() >= 0 && x_bound->lower_instr() == nullptr && y->as_ArrayLength() != nullptr) {
230
_bound = new Bound(0, nullptr, -1, y);
231
} else if (x_bound->has_lower() && x_bound->lower() >= 0 && y->type()->as_IntConstant() &&
232
y->type()->as_IntConstant()->value() != 0 && y->type()->as_IntConstant()->value() != min_jint) {
233
// The binary % operator is said to yield the remainder of its operands from an implied division; the
234
// left-hand operand is the dividend and the right-hand operand is the divisor.
236
// It follows from this rule that the result of the remainder operation can be negative only
237
// if the dividend is negative, and can be positive only if the dividend is positive. Moreover, the
238
// magnitude of the result is always less than the magnitude of the divisor (see JLS 15.17.3).
240
// So if y is a constant integer and not equal to 0, then we can deduce the bound of remainder operation:
241
// x % -y ==> [0, y - 1] Apply RCE
242
// x % y ==> [0, y - 1] Apply RCE
243
// -x % y ==> [-y + 1, 0]
244
// -x % -y ==> [-y + 1, 0]
246
// Use the absolute value of y as an upper bound. Skip min_jint because abs(min_jint) is undefined.
247
_bound = new Bound(0, nullptr, abs(y->type()->as_IntConstant()->value()) - 1, nullptr);
249
_bound = new Bound();
251
} else if (!x->as_Constant() || !y->as_Constant()) {
252
assert(!x->as_Constant() || !y->as_Constant(), "One of the operands must be non-constant!");
253
if (((x->as_Constant() || y->as_Constant()) && (ao->op() == Bytecodes::_iadd)) || (y->as_Constant() && ao->op() == Bytecodes::_isub)) {
254
assert(ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub, "Operand must be iadd or isub");
256
if (y->as_Constant()) {
261
assert(x->as_Constant()->type()->as_IntConstant(), "Constant must be int constant!");
264
int const_value = x->as_Constant()->type()->as_IntConstant()->value();
265
if (ao->op() == Bytecodes::_iadd || const_value != min_jint) {
266
if (ao->op() == Bytecodes::_isub) {
267
const_value = -const_value;
270
Bound * bound = _rce->get_bound(y);
271
if (bound->has_upper() && bound->has_lower()) {
272
jint t_lo = bound->lower();
273
jint t_hi = bound->upper();
274
jint new_lower = java_add(t_lo, const_value);
275
jint new_upper = java_add(t_hi, const_value);
276
bool overflow = ((const_value < 0 && (new_lower > t_lo)) ||
277
(const_value > 0 && (new_upper < t_hi)));
279
_bound = new Bound();
281
_bound = new Bound(new_lower, bound->lower_instr(), new_upper, bound->upper_instr());
284
_bound = new Bound();
287
_bound = new Bound();
290
Bound *bound = _rce->get_bound(x);
291
if (ao->op() == Bytecodes::_isub) {
292
if (bound->lower_instr() == y) {
293
_bound = new Bound(Instruction::geq, nullptr, bound->lower());
295
_bound = new Bound();
298
_bound = new Bound();
305
void RangeCheckEliminator::Visitor::do_IfOp(IfOp *ifOp)
307
if (ifOp->tval()->type()->as_IntConstant() && ifOp->fval()->type()->as_IntConstant()) {
308
int min = ifOp->tval()->type()->as_IntConstant()->value();
309
int max = ifOp->fval()->type()->as_IntConstant()->value();
311
// min ^= max ^= min ^= max;
316
_bound = new Bound(min, nullptr, max, nullptr);
320
// Get bound. Returns the current bound on Value v. Normally this is the topmost element on the bound stack.
321
RangeCheckEliminator::Bound *RangeCheckEliminator::get_bound(Value v) {
322
// Wrong type or null -> No bound
323
if (!v || (!v->type()->as_IntType() && !v->type()->as_ObjectType())) return nullptr;
325
if (!_bounds.at(v->id())) {
326
// First (default) bound is calculated
328
_bounds.at_put(v->id(), new BoundStack());
329
_visitor.clear_bound();
330
Value visit_value = v;
331
visit_value->visit(&_visitor);
332
Bound *bound = _visitor.bound();
334
_bounds.at(v->id())->push(bound);
336
if (_bounds.at(v->id())->length() == 0) {
337
assert(!(v->as_Constant() && v->type()->as_IntConstant()), "constants not handled here");
338
_bounds.at(v->id())->push(new Bound());
340
} else if (_bounds.at(v->id())->length() == 0) {
341
// To avoid endless loops, bound is currently in calculation -> nothing known about it
346
return _bounds.at(v->id())->top();
350
void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Instruction::Condition cond, Value value, int constant) {
351
assert(sizeof(constant) == sizeof(jint), "wrong size");
352
if (cond == Instruction::gtr) {
353
cond = Instruction::geq;
354
if (constant == INT_MAX) {
355
if (value == nullptr) {
356
// Cannot represent c > INT_MAX, do not update bounds
359
constant = java_add((jint)constant, 1); // Java wrap semantics
363
} else if (cond == Instruction::lss) {
364
cond = Instruction::leq;
365
if (constant == INT_MIN) {
366
if (value == nullptr) {
367
// Cannot represent c < INT_MIN, do not update bounds
370
constant = java_subtract((jint)constant, 1); // Java wrap semantics
375
Bound *bound = new Bound(cond, value, constant);
376
update_bound(pushed, v, bound);
379
// Checks for loop invariance. Returns true if the instruction is outside of the loop which is identified by loop_header.
380
bool RangeCheckEliminator::loop_invariant(BlockBegin *loop_header, Instruction *instruction) {
381
assert(loop_header, "Loop header must not be null!");
382
if (!instruction) return true;
383
for (BlockBegin* d = loop_header->dominator(); d != nullptr; d = d->dominator()) {
384
if (d == instruction->block()) {
391
// Update bound. Pushes a new bound onto the stack. Tries to do a conjunction with the current bound.
392
void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Bound *bound) {
393
if (v->as_Constant()) {
394
// No bound update for constants
397
if (!_bounds.at(v->id())) {
399
assert(_bounds.at(v->id()), "Now Stack must exist");
401
Bound* top = nullptr;
402
if (_bounds.at(v->id())->length() > 0) {
403
top = _bounds.at(v->id())->top();
408
_bounds.at(v->id())->push(bound);
409
pushed.append(v->id());
412
// Add instruction + idx for in block motion
413
void RangeCheckEliminator::add_access_indexed_info(InstructionList &indices, int idx, Value instruction, AccessIndexed *ai) {
414
int id = instruction->id();
415
AccessIndexedInfo *aii = _access_indexed_info.at(id);
416
if (aii == nullptr) {
417
aii = new AccessIndexedInfo();
418
_access_indexed_info.at_put(id, aii);
419
indices.append(instruction);
422
aii->_list = new AccessIndexedList();
423
} else if (idx >= aii->_min && idx <= aii->_max) {
424
// Guard against underflow/overflow (see 'range_cond' check in RangeCheckEliminator::in_block_motion)
425
if (aii->_max < 0 || (aii->_max + min_jint) <= aii->_min) {
426
remove_range_check(ai);
430
aii->_min = MIN2(aii->_min, idx);
431
aii->_max = MAX2(aii->_max, idx);
432
aii->_list->append(ai);
435
// In block motion. Tries to reorder checks in order to reduce some of them.
440
// In this example the check for a[i+1] would be considered as unnecessary during the first iteration.
441
// After this i is only checked once for i >= 0 and i+2 < a.length before the first array access. If this
442
// check fails, deoptimization is called.
443
void RangeCheckEliminator::in_block_motion(BlockBegin *block, AccessIndexedList &accessIndexed, InstructionList &arrays) {
444
InstructionList indices;
446
// Now iterate over all arrays
447
for (int i=0; i<arrays.length(); i++) {
448
int max_constant = -1;
449
AccessIndexedList list_constant;
450
Value array = arrays.at(i);
452
// For all AccessIndexed-instructions in this block concerning the current array.
453
for(int j=0; j<accessIndexed.length(); j++) {
454
AccessIndexed *ai = accessIndexed.at(j);
455
if (ai->array() != array || !ai->check_flag(Instruction::NeedsRangeCheckFlag)) continue;
457
Value index = ai->index();
458
Constant *c = index->as_Constant();
460
int constant_value = c->type()->as_IntConstant()->value();
461
if (constant_value >= 0) {
462
if (constant_value <= max_constant) {
463
// No range check needed for this
464
remove_range_check(ai);
466
max_constant = constant_value;
467
list_constant.append(ai);
471
jint last_integer = 0;
472
Instruction *last_instruction = index;
474
ArithmeticOp *ao = index->as_ArithmeticOp();
476
while (ao != nullptr && (ao->x()->as_Constant() || ao->y()->as_Constant()) && (ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub)) {
477
c = ao->y()->as_Constant();
478
Instruction *other = ao->x();
479
if (!c && ao->op() == Bytecodes::_iadd) {
480
c = ao->x()->as_Constant();
485
jint value = c->type()->as_IntConstant()->value();
486
if (ao->op() == Bytecodes::_iadd) {
487
base = java_add(base, value);
489
assert(ao->op() == Bytecodes::_isub, "unexpected bytecode");
490
base = java_subtract(base, value);
493
last_instruction = other;
498
ao = index->as_ArithmeticOp();
500
add_access_indexed_info(indices, last_integer, last_instruction, ai);
504
// Iterate over all different indices
506
for (int i = 0; i < indices.length(); i++) {
507
Instruction *index_instruction = indices.at(i);
508
AccessIndexedInfo *info = _access_indexed_info.at(index_instruction->id());
509
assert(info != nullptr, "Info must not be null");
511
// if idx < 0, max > 0, max + idx may fall between 0 and
512
// length-1 and if min < 0, min + idx may underflow/overflow and be >=
513
// 0. The predicate wouldn't trigger but some accesses could
514
// be with a negative index. This test guarantees that for the
515
// min and max value that are kept the predicate can't let
516
// some incorrect accesses happen.
517
bool range_cond = (info->_max < 0 || (info->_max + min_jint) <= info->_min);
519
// Generate code only if more than 2 range checks can be eliminated because of that.
520
// 2 because at least 2 comparisons are done
521
if (info->_list->length() > 2 && range_cond) {
522
AccessIndexed *first = info->_list->at(0);
523
Instruction *insert_position = first->prev();
524
assert(insert_position->next() == first, "prev was calculated");
525
ValueStack *state = first->state_before();
528
Constant *min_constant = nullptr;
529
if (info->_min != 0) {
530
min_constant = new Constant(new IntConstant(info->_min));
531
NOT_PRODUCT(min_constant->set_printable_bci(first->printable_bci()));
532
insert_position = insert_position->insert_after(min_constant);
536
Constant *max_constant = nullptr;
537
if (info->_max != 0) {
538
max_constant = new Constant(new IntConstant(info->_max));
539
NOT_PRODUCT(max_constant->set_printable_bci(first->printable_bci()));
540
insert_position = insert_position->insert_after(max_constant);
544
Value length_instr = first->length();
546
ArrayLength *length = new ArrayLength(array, first->state_before()->copy());
547
length->set_exception_state(length->state_before());
548
length->set_flag(Instruction::DeoptimizeOnException, true);
549
insert_position = insert_position->insert_after_same_bci(length);
550
length_instr = length;
553
// Calculate lower bound
554
Instruction *lower_compare = index_instruction;
556
ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, min_constant, lower_compare, nullptr);
557
insert_position = insert_position->insert_after_same_bci(ao);
561
// Calculate upper bound
562
Instruction *upper_compare = index_instruction;
564
ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, max_constant, upper_compare, nullptr);
565
insert_position = insert_position->insert_after_same_bci(ao);
569
// Trick with unsigned compare is done
570
int bci = NOT_PRODUCT(first->printable_bci()) PRODUCT_ONLY(-1);
571
insert_position = predicate(upper_compare, Instruction::aeq, length_instr, state, insert_position, bci);
572
insert_position = predicate_cmp_with_const(lower_compare, Instruction::leq, -1, state, insert_position);
573
for (int j = 0; j<info->_list->length(); j++) {
574
AccessIndexed *ai = info->_list->at(j);
575
remove_range_check(ai);
580
if (list_constant.length() > 1) {
581
AccessIndexed *first = list_constant.at(0);
582
Instruction *insert_position = first->prev();
583
ValueStack *state = first->state_before();
585
Constant *constant = new Constant(new IntConstant(max_constant));
586
NOT_PRODUCT(constant->set_printable_bci(first->printable_bci()));
587
insert_position = insert_position->insert_after(constant);
588
Instruction *compare_instr = constant;
589
Value length_instr = first->length();
591
ArrayLength *length = new ArrayLength(array, state->copy());
592
length->set_exception_state(length->state_before());
593
length->set_flag(Instruction::DeoptimizeOnException, true);
594
insert_position = insert_position->insert_after_same_bci(length);
595
length_instr = length;
597
// Compare for greater or equal to array length
598
insert_position = predicate(compare_instr, Instruction::geq, length_instr, state, insert_position);
599
for (int j = 0; j<list_constant.length(); j++) {
600
AccessIndexed *ai = list_constant.at(j);
601
remove_range_check(ai);
606
// Clear data structures for next array
607
for (int i = 0; i < indices.length(); i++) {
608
Instruction *index_instruction = indices.at(i);
609
_access_indexed_info.at_put(index_instruction->id(), nullptr);
615
bool RangeCheckEliminator::set_process_block_flags(BlockBegin *block) {
616
Instruction *cur = block;
617
bool process = false;
620
process |= (cur->as_AccessIndexed() != nullptr);
624
BlockList *dominates = block->dominates();
625
for (int i=0; i<dominates->length(); i++) {
626
BlockBegin *next = dominates->at(i);
627
process |= set_process_block_flags(next);
631
block->set(BlockBegin::donot_eliminate_range_checks);
636
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) {
637
bool upper_check = true;
638
assert(lower_instr || lower >= 0, "If no lower_instr present, lower must be greater 0");
639
assert(!lower_instr || lower_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
640
assert(!upper_instr || upper_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
641
assert(array_instr, "Array instruction must exist");
642
assert(array_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
643
assert(!length_instr || length_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
645
if (upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr) {
647
if (upper >= 0) return false; // would always trigger a deopt:
648
// array_length + x >= array_length, x >= 0 is always true
651
if (lower_instr && lower_instr->as_ArrayLength() && lower_instr->as_ArrayLength()->array() == array_instr) {
652
if (lower > 0) return false;
654
// No upper check required -> skip
655
if (upper_check && upper_instr && upper_instr->type()->as_ObjectType() && upper_instr == array_instr) {
656
// upper_instr is object means that the upper bound is the length
657
// of the upper_instr.
663
Instruction* RangeCheckEliminator::insert_after(Instruction* insert_position, Instruction* instr, int bci) {
665
NOT_PRODUCT(instr->set_printable_bci(bci));
666
return insert_position->insert_after(instr);
668
return insert_position->insert_after_same_bci(instr);
672
Instruction* RangeCheckEliminator::predicate(Instruction* left, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) {
673
RangeCheckPredicate *deoptimize = new RangeCheckPredicate(left, cond, true, right, state->copy());
674
return insert_after(insert_position, deoptimize, bci);
677
Instruction* RangeCheckEliminator::predicate_cmp_with_const(Instruction* instr, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) {
678
Constant *const_instr = new Constant(new IntConstant(constant));
679
insert_position = insert_after(insert_position, const_instr, bci);
680
return predicate(instr, cond, const_instr, state, insert_position);
683
Instruction* RangeCheckEliminator::predicate_add(Instruction* left, int left_const, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) {
684
Constant *constant = new Constant(new IntConstant(left_const));
685
insert_position = insert_after(insert_position, constant, bci);
686
ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, left, nullptr);
687
insert_position = insert_position->insert_after_same_bci(ao);
688
return predicate(ao, cond, right, state, insert_position);
691
Instruction* RangeCheckEliminator::predicate_add_cmp_with_const(Instruction* left, int left_const, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) {
692
Constant *const_instr = new Constant(new IntConstant(constant));
693
insert_position = insert_after(insert_position, const_instr, bci);
694
return predicate_add(left, left_const, cond, const_instr, state, insert_position);
697
// Insert deoptimization
698
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) {
699
assert(is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, lower, upper_instr, upper), "should have been tested before");
700
bool upper_check = !(upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr);
702
int bci = NOT_PRODUCT(ai->printable_bci()) PRODUCT_ONLY(-1);
704
assert(!lower_instr->type()->as_ObjectType(), "Must not be object type");
706
// Compare for less than 0
707
insert_position = predicate_cmp_with_const(lower_instr, Instruction::lss, 0, state, insert_position, bci);
708
} else if (lower > 0) {
709
// Compare for smaller 0
710
insert_position = predicate_add_cmp_with_const(lower_instr, lower, Instruction::lss, 0, state, insert_position, bci);
712
assert(lower < 0, "");
714
lower = java_subtract(-1, (jint)lower); // lower++; lower = -lower;
715
// Compare for smaller or equal 0
716
insert_position = predicate_cmp_with_const(lower_instr, Instruction::leq, lower, state, insert_position, bci);
720
// No upper check required -> skip
721
if (!upper_check) return;
723
// We need to know length of array
725
// Load length if necessary
726
ArrayLength *length = new ArrayLength(array_instr, state->copy());
727
NOT_PRODUCT(length->set_printable_bci(ai->printable_bci()));
728
length->set_exception_state(length->state_before());
729
length->set_flag(Instruction::DeoptimizeOnException, true);
730
insert_position = insert_position->insert_after(length);
731
length_instr = length;
735
// Compare for geq array.length
736
insert_position = predicate_cmp_with_const(length_instr, Instruction::leq, upper, state, insert_position, bci);
738
if (upper_instr->type()->as_ObjectType()) {
739
assert(state, "must not be null");
740
assert(upper_instr != array_instr, "should be");
741
ArrayLength *length = new ArrayLength(upper_instr, state->copy());
742
NOT_PRODUCT(length->set_printable_bci(ai->printable_bci()));
743
length->set_flag(Instruction::DeoptimizeOnException, true);
744
length->set_exception_state(length->state_before());
745
insert_position = insert_position->insert_after(length);
746
upper_instr = length;
748
assert(upper_instr->type()->as_IntType(), "Must not be object type!");
751
// Compare for geq array.length
752
insert_position = predicate(upper_instr, Instruction::geq, length_instr, state, insert_position, bci);
753
} else if (upper < 0) {
754
// Compare for geq array.length
755
insert_position = predicate_add(upper_instr, upper, Instruction::geq, length_instr, state, insert_position, bci);
757
assert(upper > 0, "");
758
upper = java_negate((jint)upper); // upper = -upper;
759
// Compare for geq array.length
760
insert_position = predicate_add(length_instr, upper, Instruction::leq, upper_instr, state, insert_position, bci);
766
void RangeCheckEliminator::add_if_condition(IntegerStack &pushed, Value x, Value y, Instruction::Condition condition) {
767
if (y->as_Constant()) return;
770
Value instr_value = x;
771
Constant *c = x->as_Constant();
772
ArithmeticOp *ao = x->as_ArithmeticOp();
775
const_value = c->type()->as_IntConstant()->value();
776
instr_value = nullptr;
777
} else if (ao != nullptr && (!ao->x()->as_Constant() || !ao->y()->as_Constant()) && ((ao->op() == Bytecodes::_isub && ao->y()->as_Constant()) || ao->op() == Bytecodes::_iadd)) {
778
assert(!ao->x()->as_Constant() || !ao->y()->as_Constant(), "At least one operator must be non-constant!");
779
assert(ao->op() == Bytecodes::_isub || ao->op() == Bytecodes::_iadd, "Operation has to be add or sub!");
780
c = ao->x()->as_Constant();
782
const_value = c->type()->as_IntConstant()->value();
783
instr_value = ao->y();
785
c = ao->y()->as_Constant();
787
const_value = c->type()->as_IntConstant()->value();
788
instr_value = ao->x();
791
if (ao->op() == Bytecodes::_isub) {
792
assert(ao->y()->as_Constant(), "1 - x not supported, only x - 1 is valid!");
793
if (const_value > min_jint) {
794
const_value = -const_value;
802
update_bound(pushed, y, condition, instr_value, const_value);
806
void RangeCheckEliminator::process_if(IntegerStack &pushed, BlockBegin *block, If *cond) {
807
// Only if we are direct true / false successor and NOT both ! (even this may occur)
808
if ((cond->tsux() == block || cond->fsux() == block) && cond->tsux() != cond->fsux()) {
809
Instruction::Condition condition = cond->cond();
810
if (cond->fsux() == block) {
811
condition = Instruction::negate(condition);
815
if (x->type()->as_IntType() && y->type()->as_IntType()) {
816
add_if_condition(pushed, y, x, condition);
817
add_if_condition(pushed, x, y, Instruction::mirror(condition));
822
// Process access indexed
823
void RangeCheckEliminator::process_access_indexed(BlockBegin *loop_header, BlockBegin *block, AccessIndexed *ai) {
824
TRACE_RANGE_CHECK_ELIMINATION(
825
tty->fill_to(block->dominator_depth()*2)
827
TRACE_RANGE_CHECK_ELIMINATION(
828
tty->print_cr("Access indexed: index=%d length=%d", ai->index()->id(), (ai->length() != nullptr ? ai->length()->id() :-1 ))
831
if (ai->check_flag(Instruction::NeedsRangeCheckFlag)) {
832
Bound *index_bound = get_bound(ai->index());
833
if (!index_bound->has_lower() || !index_bound->has_upper()) {
834
TRACE_RANGE_CHECK_ELIMINATION(
835
tty->fill_to(block->dominator_depth()*2);
836
tty->print_cr("Index instruction %d has no lower and/or no upper bound!", ai->index()->id())
843
array_bound = get_bound(ai->length());
845
array_bound = get_bound(ai->array());
848
TRACE_RANGE_CHECK_ELIMINATION(
849
tty->fill_to(block->dominator_depth()*2);
850
tty->print("Index bound: ");
851
index_bound->print();
852
tty->print(", Array bound: ");
853
array_bound->print();
857
if (in_array_bound(index_bound, ai->array()) ||
858
(index_bound && array_bound && index_bound->is_smaller(array_bound) && !index_bound->lower_instr() && index_bound->lower() >= 0)) {
859
TRACE_RANGE_CHECK_ELIMINATION(
860
tty->fill_to(block->dominator_depth()*2);
861
tty->print_cr("Bounds check for instruction %d in block B%d can be fully eliminated!", ai->id(), ai->block()->block_id())
864
remove_range_check(ai);
865
} else if (false && _optimistic && loop_header) {
866
assert(ai->array(), "Array must not be null!");
867
assert(ai->index(), "Index must not be null!");
870
Instruction *array_instr = ai->array();
871
if (!loop_invariant(loop_header, array_instr)) {
872
TRACE_RANGE_CHECK_ELIMINATION(
873
tty->fill_to(block->dominator_depth()*2);
874
tty->print_cr("Array %d is not loop invariant to header B%d", ai->array()->id(), loop_header->block_id())
880
Value index_instr = ai->index();
881
Value lower_instr = index_bound->lower_instr();
882
if (!loop_invariant(loop_header, lower_instr)) {
883
TRACE_RANGE_CHECK_ELIMINATION(
884
tty->fill_to(block->dominator_depth()*2);
885
tty->print_cr("Lower instruction %d not loop invariant!", lower_instr->id())
889
if (!lower_instr && index_bound->lower() < 0) {
890
TRACE_RANGE_CHECK_ELIMINATION(
891
tty->fill_to(block->dominator_depth()*2);
892
tty->print_cr("Lower bound smaller than 0 (%d)!", index_bound->lower())
898
Value upper_instr = index_bound->upper_instr();
899
if (!loop_invariant(loop_header, upper_instr)) {
900
TRACE_RANGE_CHECK_ELIMINATION(
901
tty->fill_to(block->dominator_depth()*2);
902
tty->print_cr("Upper instruction %d not loop invariant!", upper_instr->id())
907
// Length instruction
908
Value length_instr = ai->length();
909
if (!loop_invariant(loop_header, length_instr)) {
910
// Generate length instruction yourself!
911
length_instr = nullptr;
914
TRACE_RANGE_CHECK_ELIMINATION(
915
tty->fill_to(block->dominator_depth()*2);
916
tty->print_cr("LOOP INVARIANT access indexed %d found in block B%d!", ai->id(), ai->block()->block_id())
919
BlockBegin *pred_block = loop_header->dominator();
920
assert(pred_block != nullptr, "Every loop header has a dominator!");
921
BlockEnd *pred_block_end = pred_block->end();
922
Instruction *insert_position = pred_block_end->prev();
923
ValueStack *state = pred_block_end->state_before();
924
if (pred_block_end->as_Goto() && state == nullptr) state = pred_block_end->state();
925
assert(state, "State must not be null");
927
// Add deoptimization to dominator of loop header
928
TRACE_RANGE_CHECK_ELIMINATION(
929
tty->fill_to(block->dominator_depth()*2);
930
tty->print_cr("Inserting deopt at bci %d in block B%d!", state->bci(), insert_position->block()->block_id())
933
if (!is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper())) {
934
TRACE_RANGE_CHECK_ELIMINATION(
935
tty->fill_to(block->dominator_depth()*2);
936
tty->print_cr("Could not eliminate because of static analysis!")
941
insert_deoptimization(state, insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper(), ai);
943
// Finally remove the range check!
944
remove_range_check(ai);
949
void RangeCheckEliminator::remove_range_check(AccessIndexed *ai) {
950
ai->set_flag(Instruction::NeedsRangeCheckFlag, false);
951
// no range check, no need for the length instruction anymore
954
TRACE_RANGE_CHECK_ELIMINATION(
955
tty->fill_to(ai->dominator_depth()*2);
956
tty->print_cr("Range check for instruction %d eliminated!", ai->id());
959
ASSERT_RANGE_CHECK_ELIMINATION(
960
Value array_length = ai->length();
962
array_length = ai->array();
963
assert(array_length->type()->as_ObjectType(), "Has to be object type!");
965
int cur_constant = -1;
966
Value cur_value = array_length;
967
if (cur_value->type()->as_IntConstant()) {
968
cur_constant += cur_value->type()->as_IntConstant()->value();
971
Bound* new_index_bound = new Bound(0, nullptr, cur_constant, cur_value);
972
add_assertions(new_index_bound, ai->index(), ai);
976
// Calculate bounds for instruction in this block and children blocks in the dominator tree
977
void RangeCheckEliminator::calc_bounds(BlockBegin *block, BlockBegin *loop_header) {
978
// Ensures a valid loop_header
979
assert(!loop_header || loop_header->is_set(BlockBegin::linear_scan_loop_header_flag), "Loop header has to be real !");
982
TRACE_RANGE_CHECK_ELIMINATION(
983
tty->fill_to(block->dominator_depth()*2);
984
tty->print_cr("Block B%d", block->block_id());
987
// Pushed stack for conditions
990
BlockBegin *parent = block->dominator();
991
if (parent != nullptr) {
992
If *cond = parent->end()->as_If();
993
if (cond != nullptr) {
994
process_if(pushed, block, cond);
998
// Iterate over current block
999
InstructionList arrays;
1000
AccessIndexedList accessIndexed;
1001
Instruction *cur = block;
1004
// Ensure cur wasn't inserted during the elimination
1005
if (cur->id() < this->_bounds.length()) {
1006
// Process only if it is an access indexed instruction
1007
AccessIndexed *ai = cur->as_AccessIndexed();
1008
if (ai != nullptr) {
1009
process_access_indexed(loop_header, block, ai);
1010
accessIndexed.append(ai);
1011
if (!arrays.contains(ai->array())) {
1012
arrays.append(ai->array());
1014
Bound *b = get_bound(ai->index());
1015
if (!b->lower_instr()) {
1016
// Lower bound is constant
1017
update_bound(pushed, ai->index(), Instruction::geq, nullptr, 0);
1019
if (!b->has_upper()) {
1020
if (ai->length() && ai->length()->type()->as_IntConstant()) {
1021
int value = ai->length()->type()->as_IntConstant()->value();
1022
update_bound(pushed, ai->index(), Instruction::lss, nullptr, value);
1024
// Has no upper bound
1025
Instruction *instr = ai->length();
1026
if (instr == nullptr) instr = ai->array();
1027
update_bound(pushed, ai->index(), Instruction::lss, instr, 0);
1035
// Output current condition stack
1036
TRACE_RANGE_CHECK_ELIMINATION(dump_condition_stack(block));
1038
// Do in block motion of range checks
1039
in_block_motion(block, accessIndexed, arrays);
1041
// Call all dominated blocks
1042
for (int i=0; i<block->dominates()->length(); i++) {
1043
BlockBegin *next = block->dominates()->at(i);
1044
if (!next->is_set(BlockBegin::donot_eliminate_range_checks)) {
1045
// if current block is a loop header and:
1046
// - next block belongs to the same loop
1048
// - next block belongs to an inner loop
1049
// then current block is the loop header for next block
1050
if (block->is_set(BlockBegin::linear_scan_loop_header_flag) && (block->loop_index() == next->loop_index() || next->loop_depth() > block->loop_depth())) {
1051
calc_bounds(next, block);
1053
calc_bounds(next, loop_header);
1059
for (int i=0; i<pushed.length(); i++) {
1060
_bounds.at(pushed.at(i))->pop();
1065
// Dump condition stack
1066
void RangeCheckEliminator::dump_condition_stack(BlockBegin *block) {
1067
for (int i=0; i<_ir->linear_scan_order()->length(); i++) {
1068
BlockBegin *cur_block = _ir->linear_scan_order()->at(i);
1069
Instruction *instr = cur_block;
1070
for_each_phi_fun(cur_block, phi,
1071
BoundStack *bound_stack = _bounds.at(phi->id());
1072
if (bound_stack && bound_stack->length() > 0) {
1073
Bound *bound = bound_stack->top();
1074
if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != phi || bound->upper_instr() != phi || bound->lower() != 0 || bound->upper() != 0)) {
1075
TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth());
1076
tty->print("i%d", phi->id());
1084
while (!instr->as_BlockEnd()) {
1085
if (instr->id() < _bounds.length()) {
1086
BoundStack *bound_stack = _bounds.at(instr->id());
1087
if (bound_stack && bound_stack->length() > 0) {
1088
Bound *bound = bound_stack->top();
1089
if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != instr || bound->upper_instr() != instr || bound->lower() != 0 || bound->upper() != 0)) {
1090
TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth());
1091
tty->print("i%d", instr->id());
1099
instr = instr->next();
1106
// Verification or the IR
1107
RangeCheckEliminator::Verification::Verification(IR *ir) : _used(BlockBegin::number_of_blocks(), BlockBegin::number_of_blocks(), false) {
1109
ir->iterate_linear_scan_order(this);
1113
void RangeCheckEliminator::Verification::block_do(BlockBegin *block) {
1114
If *cond = block->end()->as_If();
1115
// Watch out: tsux and fsux can be the same!
1116
if (block->number_of_sux() > 1) {
1117
for (int i=0; i<block->number_of_sux(); i++) {
1118
BlockBegin* sux = block->sux_at(i);
1119
BlockBegin* pred = nullptr;
1120
for (int j=0; j<sux->number_of_preds(); j++) {
1121
BlockBegin *cur = sux->pred_at(j);
1122
assert(cur != nullptr, "Predecessor must not be null");
1126
assert(cur == pred, "Block must not have more than one predecessor if its predecessor has more than one successor");
1128
assert(sux->number_of_preds() >= 1, "Block must have at least one predecessor");
1129
assert(sux->pred_at(0) == block, "Wrong successor");
1133
BlockBegin *dominator = block->dominator();
1135
assert(block != _ir->start(), "Start block must not have a dominator!");
1136
assert(can_reach(dominator, block), "Dominator can't reach his block !");
1137
assert(can_reach(_ir->start(), dominator), "Dominator is unreachable !");
1138
assert(!can_reach(_ir->start(), block, dominator), "Wrong dominator ! Block can be reached anyway !");
1139
BlockList *all_blocks = _ir->linear_scan_order();
1140
for (int i=0; i<all_blocks->length(); i++) {
1141
BlockBegin *cur = all_blocks->at(i);
1142
if (cur != dominator && cur != block) {
1143
assert(can_reach(dominator, block, cur), "There has to be another dominator!");
1147
assert(block == _ir->start(), "Only start block must not have a dominator");
1150
if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) {
1151
int loop_index = block->loop_index();
1152
BlockList *all_blocks = _ir->linear_scan_order();
1153
assert(block->number_of_preds() >= 1, "Block must have at least one predecessor");
1154
assert(!block->is_set(BlockBegin::exception_entry_flag), "Loop header must not be exception handler!");
1156
bool loop_through_xhandler = false;
1157
for (int i=0; i<block->number_of_sux(); i++) {
1158
BlockBegin *sux = block->sux_at(i);
1159
if (!loop_through_xhandler) {
1160
if (sux->loop_depth() == block->loop_depth() && sux->loop_index() != block->loop_index()) {
1161
loop_through_xhandler = is_backbranch_from_xhandler(block);
1162
assert(loop_through_xhandler, "Loop indices have to be the same if same depths but no backbranch from xhandler");
1165
assert(sux->loop_depth() == block->loop_depth() || sux->loop_index() != block->loop_index(), "Loop index has to be different");
1168
for (int i=0; i<all_blocks->length(); i++) {
1169
BlockBegin *cur = all_blocks->at(i);
1170
if (cur->loop_index() == loop_index && cur != block) {
1171
assert(dominates(block->dominator(), cur), "Dominator of loop header must dominate all loop blocks");
1176
Instruction *cur = block;
1178
assert(cur->block() == block, "Block begin has to be set correctly!");
1183
// 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
1184
// an exception handler of a loop head block, for example, when a loop is only executed once on the non-exceptional path but is
1185
// repeated in case of an exception. In this case, the edge block->sux is not critical and was not split before.
1186
// Check if there is such a backbranch from an xhandler of 'block'.
1187
bool RangeCheckEliminator::Verification::is_backbranch_from_xhandler(BlockBegin* block) {
1188
for (int i = 0; i < block->number_of_exception_handlers(); i++) {
1189
BlockBegin *xhandler = block->exception_handler_at(i);
1190
for (int j = 0; j < block->number_of_preds(); j++) {
1191
if (dominates(xhandler, block->pred_at(j)) || xhandler == block->pred_at(j)) {
1197
// In case of nested xhandlers, we need to walk through the loop (and all blocks belonging to exception handlers)
1198
// to find an xhandler of 'block'.
1199
if (block->number_of_exception_handlers() > 0) {
1200
for (int i = 0; i < block->number_of_preds(); i++) {
1201
BlockBegin* pred = block->pred_at(i);
1202
if (pred->loop_index() == block->loop_index()) {
1203
// Only check blocks that belong to the loop
1204
// Do a BFS to find an xhandler block of 'block' starting from 'pred'
1206
ResourceBitMap visited(BlockBegin::number_of_blocks());
1207
BlockBeginList list;
1209
while (!list.is_empty()) {
1210
BlockBegin* next = list.pop();
1211
if (!visited.at(next->block_id())) {
1212
visited.set_bit(next->block_id());
1213
for (int j = 0; j < block->number_of_exception_handlers(); j++) {
1214
if (next == block->exception_handler_at(j)) {
1218
for (int j = 0; j < next->number_of_preds(); j++) {
1219
if (next->pred_at(j) != block) {
1220
list.push(next->pred_at(j));
1231
// Loop header must dominate all loop blocks
1232
bool RangeCheckEliminator::Verification::dominates(BlockBegin *dominator, BlockBegin *block) {
1233
BlockBegin *cur = block->dominator();
1234
while (cur && cur != dominator) {
1235
cur = cur->dominator();
1237
return cur == dominator;
1240
// Try to reach Block end beginning in Block start and not using Block dont_use
1241
bool RangeCheckEliminator::Verification::can_reach(BlockBegin* start, BlockBegin* end, BlockBegin* dont_use /* = nullptr */) {
1242
if (start == end) return start != dont_use;
1243
// Simple BSF from start to end
1244
// BlockBeginList _current;
1245
for (int i=0; i < _used.length(); i++) {
1246
_used.at_put(i, false);
1248
_current.trunc_to(0);
1249
_successors.trunc_to(0);
1250
if (start != dont_use) {
1251
_current.push(start);
1252
_used.at_put(start->block_id(), true);
1255
// BlockBeginList _successors;
1256
while (_current.length() > 0) {
1257
BlockBegin *cur = _current.pop();
1258
// Add exception handlers to list
1259
for (int i=0; i<cur->number_of_exception_handlers(); i++) {
1260
BlockBegin *xhandler = cur->exception_handler_at(i);
1261
_successors.push(xhandler);
1262
// Add exception handlers of _successors to list
1263
for (int j=0; j<xhandler->number_of_exception_handlers(); j++) {
1264
BlockBegin *sux_xhandler = xhandler->exception_handler_at(j);
1265
_successors.push(sux_xhandler);
1268
// Add normal _successors to list
1269
for (int i=0; i<cur->number_of_sux(); i++) {
1270
BlockBegin *sux = cur->sux_at(i);
1271
_successors.push(sux);
1272
// Add exception handlers of _successors to list
1273
for (int j=0; j<sux->number_of_exception_handlers(); j++) {
1274
BlockBegin *xhandler = sux->exception_handler_at(j);
1275
_successors.push(xhandler);
1278
for (int i=0; i<_successors.length(); i++) {
1279
BlockBegin *sux = _successors.at(i);
1280
assert(sux != nullptr, "Successor must not be null!");
1284
if (sux != dont_use && !_used.at(sux->block_id())) {
1285
_used.at_put(sux->block_id(), true);
1289
_successors.trunc_to(0);
1297
RangeCheckEliminator::Bound::~Bound() {
1301
RangeCheckEliminator::Bound::Bound() {
1302
this->_lower = min_jint;
1303
this->_upper = max_jint;
1304
this->_lower_instr = nullptr;
1305
this->_upper_instr = nullptr;
1309
RangeCheckEliminator::Bound::Bound(int lower, Value lower_instr, int upper, Value upper_instr) {
1310
assert(!lower_instr || !lower_instr->as_Constant() || !lower_instr->type()->as_IntConstant(), "Must not be constant!");
1311
assert(!upper_instr || !upper_instr->as_Constant() || !upper_instr->type()->as_IntConstant(), "Must not be constant!");
1312
this->_lower = lower;
1313
this->_upper = upper;
1314
this->_lower_instr = lower_instr;
1315
this->_upper_instr = upper_instr;
1319
RangeCheckEliminator::Bound::Bound(Instruction::Condition cond, Value v, int constant) {
1320
assert(!v || (v->type() && (v->type()->as_IntType() || v->type()->as_ObjectType())), "Type must be array or integer!");
1321
assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!");
1323
if (cond == Instruction::eql) {
1328
} else if (cond == Instruction::neq) {
1331
_lower_instr = nullptr;
1332
_upper_instr = nullptr;
1334
if (constant == min_jint) {
1337
if (constant == max_jint) {
1341
} else if (cond == Instruction::geq) {
1345
_upper_instr = nullptr;
1346
} else if (cond == Instruction::leq) {
1348
_lower_instr = nullptr;
1352
ShouldNotReachHere();
1357
void RangeCheckEliminator::Bound::or_op(Bound *b) {
1358
// Watch out, bound is not guaranteed not to overflow!
1359
// Update lower bound
1360
if (_lower_instr != b->_lower_instr || (_lower_instr && _lower != b->_lower)) {
1361
_lower_instr = nullptr;
1364
_lower = MIN2(_lower, b->_lower);
1366
// Update upper bound
1367
if (_upper_instr != b->_upper_instr || (_upper_instr && _upper != b->_upper)) {
1368
_upper_instr = nullptr;
1371
_upper = MAX2(_upper, b->_upper);
1376
void RangeCheckEliminator::Bound::and_op(Bound *b) {
1377
// Update lower bound
1378
if (_lower_instr == b->_lower_instr) {
1379
_lower = MAX2(_lower, b->_lower);
1381
if (b->has_lower()) {
1383
if (_lower_instr != nullptr && b->_lower_instr != nullptr) {
1384
set = (_lower_instr->dominator_depth() > b->_lower_instr->dominator_depth());
1388
_lower_instr = b->_lower_instr;
1391
// Update upper bound
1392
if (_upper_instr == b->_upper_instr) {
1393
_upper = MIN2(_upper, b->_upper);
1395
if (b->has_upper()) {
1397
if (_upper_instr != nullptr && b->_upper_instr != nullptr) {
1398
set = (_upper_instr->dominator_depth() > b->_upper_instr->dominator_depth());
1402
_upper_instr = b->_upper_instr;
1408
bool RangeCheckEliminator::Bound::has_upper() {
1409
return _upper_instr != nullptr || _upper < max_jint;
1413
bool RangeCheckEliminator::Bound::is_smaller(Bound *b) {
1414
if (b->_lower_instr != _upper_instr) {
1417
return _upper < b->_lower;
1421
bool RangeCheckEliminator::Bound::has_lower() {
1422
return _lower_instr != nullptr || _lower > min_jint;
1426
bool RangeCheckEliminator::in_array_bound(Bound *bound, Value array){
1427
if (!bound) return false;
1428
assert(array != nullptr, "Must not be null!");
1429
assert(bound != nullptr, "Must not be null!");
1430
if (bound->lower() >=0 && bound->lower_instr() == nullptr && bound->upper() < 0 && bound->upper_instr() != nullptr) {
1431
ArrayLength *len = bound->upper_instr()->as_ArrayLength();
1432
if (bound->upper_instr() == array || (len != nullptr && len->array() == array)) {
1440
void RangeCheckEliminator::Bound::remove_lower() {
1442
_lower_instr = nullptr;
1446
void RangeCheckEliminator::Bound::remove_upper() {
1448
_upper_instr = nullptr;
1452
int RangeCheckEliminator::Bound::upper() {
1457
int RangeCheckEliminator::Bound::lower() {
1462
Value RangeCheckEliminator::Bound::upper_instr() {
1463
return _upper_instr;
1467
Value RangeCheckEliminator::Bound::lower_instr() {
1468
return _lower_instr;
1472
void RangeCheckEliminator::Bound::print() {
1473
tty->print("%s", "");
1474
if (this->_lower_instr || this->_lower != min_jint) {
1475
if (this->_lower_instr) {
1476
tty->print("i%d", this->_lower_instr->id());
1477
if (this->_lower > 0) {
1478
tty->print("+%d", _lower);
1480
if (this->_lower < 0) {
1481
tty->print("%d", _lower);
1484
tty->print("%d", _lower);
1489
if (this->_upper_instr || this->_upper != max_jint) {
1491
if (this->_upper_instr) {
1492
tty->print("i%d", this->_upper_instr->id());
1493
if (this->_upper > 0) {
1494
tty->print("+%d", _upper);
1496
if (this->_upper < 0) {
1497
tty->print("%d", _upper);
1500
tty->print("%d", _upper);
1506
RangeCheckEliminator::Bound *RangeCheckEliminator::Bound::copy() {
1507
Bound *b = new Bound();
1509
b->_lower_instr = _lower_instr;
1511
b->_upper_instr = _upper_instr;
1517
void RangeCheckEliminator::Bound::add_assertion(Instruction *instruction, Instruction *position, int i, Value instr, Instruction::Condition cond) {
1518
Instruction* result = position;
1519
Instruction* compare_with = nullptr;
1520
ValueStack* state = position->state_before();
1521
if (position->as_BlockEnd() && !position->as_Goto()) {
1522
state = position->as_BlockEnd()->state_before();
1524
Instruction* instruction_before = position->prev();
1525
if (position->as_Return() && Compilation::current()->method()->is_synchronized() && instruction_before->as_MonitorExit()) {
1526
instruction_before = instruction_before->prev();
1528
result = instruction_before;
1529
// Load constant only if needed
1530
Constant* constant = nullptr;
1531
if (i != 0 || !instr) {
1532
constant = new Constant(new IntConstant(i));
1533
NOT_PRODUCT(constant->set_printable_bci(position->printable_bci()));
1534
result = result->insert_after(constant);
1535
compare_with = constant;
1539
assert(instr->type()->as_ObjectType() || instr->type()->as_IntType(), "Type must be array or integer!");
1540
compare_with = instr;
1541
// Load array length if necessary
1542
Instruction *op = instr;
1543
if (instr->type()->as_ObjectType()) {
1544
assert(state, "must not be null");
1545
ArrayLength *length = new ArrayLength(instr, state->copy());
1546
NOT_PRODUCT(length->set_printable_bci(position->printable_bci()));
1547
length->set_exception_state(length->state_before());
1548
result = result->insert_after(length);
1550
compare_with = length;
1552
// Add operation only if necessary
1554
ArithmeticOp* ao = new ArithmeticOp(Bytecodes::_iadd, constant, op, nullptr);
1555
NOT_PRODUCT(ao->set_printable_bci(position->printable_bci()));
1556
result = result->insert_after(ao);
1560
assert(compare_with != nullptr, "You have to compare with something!");
1561
assert(instruction != nullptr, "Instruction must not be null!");
1563
if (instruction->type()->as_ObjectType()) {
1564
// Load array length if necessary
1565
Instruction *op = instruction;
1566
assert(state, "must not be null");
1567
ArrayLength *length = new ArrayLength(instruction, state->copy());
1568
length->set_exception_state(length->state_before());
1569
NOT_PRODUCT(length->set_printable_bci(position->printable_bci()));
1570
result = result->insert_after(length);
1571
instruction = length;
1574
Assert *assert = new Assert(instruction, cond, false, compare_with);
1575
NOT_PRODUCT(assert->set_printable_bci(position->printable_bci()));
1576
result->insert_after(assert);
1580
void RangeCheckEliminator::add_assertions(Bound *bound, Instruction *instruction, Instruction *position) {
1581
// Add lower bound assertion
1582
if (bound->has_lower()) {
1583
bound->add_assertion(instruction, position, bound->lower(), bound->lower_instr(), Instruction::geq);
1585
// Add upper bound assertion
1586
if (bound->has_upper()) {
1587
bound->add_assertion(instruction, position, bound->upper(), bound->upper_instr(), Instruction::leq);