1 /*
2 * Copyright (c) 2012, 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
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.
8 *
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).
14 *
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.
18 *
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
21 * questions.
22 *
23 */
24
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"
33
34 // Macros for the Trace and the Assertion flag
35 #ifdef ASSERT
36 #define TRACE_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination) { code; }
37 #define ASSERT_RANGE_CHECK_ELIMINATION(code) if (AssertRangeCheckElimination) { code; }
38 #define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination || AssertRangeCheckElimination) { code; }
39 #else
40 #define TRACE_RANGE_CHECK_ELIMINATION(code)
41 #define ASSERT_RANGE_CHECK_ELIMINATION(code)
42 #define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code)
43 #endif
44
45 // Entry point for the optimization
46 void RangeCheckElimination::eliminate(IR *ir) {
47 bool do_elimination = ir->compilation()->has_access_indexed();
48 ASSERT_RANGE_CHECK_ELIMINATION(do_elimination = true);
49 if (do_elimination) {
50 RangeCheckEliminator rce(ir);
51 }
52 }
53
54 // Constructor
55 RangeCheckEliminator::RangeCheckEliminator(IR *ir) :
56 _bounds(Instruction::number_of_instructions(), NULL),
57 _access_indexed_info(Instruction::number_of_instructions(), NULL)
58 {
59 _visitor.set_range_check_eliminator(this);
60 _ir = ir;
61 _number_of_instructions = Instruction::number_of_instructions();
62 _optimistic = ir->compilation()->is_optimistic();
63
64 TRACE_RANGE_CHECK_ELIMINATION(
65 tty->cr();
66 tty->print_cr("Range check elimination");
67 ir->method()->print_name(tty);
68 tty->cr();
69 );
70
71 TRACE_RANGE_CHECK_ELIMINATION(
72 tty->print_cr("optimistic=%d", (int)_optimistic);
73 );
74
75 #ifdef ASSERT
76 // Verifies several conditions that must be true on the IR-input. Only used for debugging purposes.
77 TRACE_RANGE_CHECK_ELIMINATION(
78 tty->print_cr("Verification of IR . . .");
79 );
80 Verification verification(ir);
81 #endif
82
83 // Set process block flags
84 // Optimization so a blocks is only processed if it contains an access indexed instruction or if
85 // one of its children in the dominator tree contains an access indexed instruction.
86 set_process_block_flags(ir->start());
87
88 // Pass over instructions in the dominator tree
89 TRACE_RANGE_CHECK_ELIMINATION(
90 tty->print_cr("Starting pass over dominator tree . . .")
91 );
92 calc_bounds(ir->start(), NULL);
93
94 TRACE_RANGE_CHECK_ELIMINATION(
95 tty->print_cr("Finished!")
96 );
97 }
98
99 // Instruction specific work for some instructions
100 // Constant
101 void RangeCheckEliminator::Visitor::do_Constant(Constant *c) {
102 IntConstant *ic = c->type()->as_IntConstant();
103 if (ic != NULL) {
104 int value = ic->value();
105 _bound = new Bound(value, NULL, value, NULL);
106 }
107 }
108
109 // LogicOp
110 void RangeCheckEliminator::Visitor::do_LogicOp(LogicOp *lo) {
111 if (lo->type()->as_IntType() && lo->op() == Bytecodes::_iand && (lo->x()->as_Constant() || lo->y()->as_Constant())) {
112 int constant = 0;
113 Constant *c = lo->x()->as_Constant();
114 if (c != NULL) {
115 constant = c->type()->as_IntConstant()->value();
116 } else {
117 constant = lo->y()->as_Constant()->type()->as_IntConstant()->value();
118 }
119 if (constant >= 0) {
120 _bound = new Bound(0, NULL, constant, NULL);
121 }
122 }
123 }
124
125 // Phi
126 void RangeCheckEliminator::Visitor::do_Phi(Phi *phi) {
127 if (!phi->type()->as_IntType() && !phi->type()->as_ObjectType()) return;
128
129 BlockBegin *block = phi->block();
130 int op_count = phi->operand_count();
131 bool has_upper = true;
132 bool has_lower = true;
133 assert(phi, "Phi must not be null");
134 Bound *bound = NULL;
135
136 // TODO: support more difficult phis
137 for (int i=0; i<op_count; i++) {
138 Value v = phi->operand_at(i);
139
140 if (v == phi) continue;
141
142 // Check if instruction is connected with phi itself
143 Op2 *op2 = v->as_Op2();
144 if (op2 != NULL) {
145 Value x = op2->x();
146 Value y = op2->y();
147 if ((x == phi || y == phi)) {
148 Value other = x;
149 if (other == phi) {
150 other = y;
151 }
152 ArithmeticOp *ao = v->as_ArithmeticOp();
153 if (ao != NULL && ao->op() == Bytecodes::_iadd) {
154 assert(ao->op() == Bytecodes::_iadd, "Has to be add!");
155 if (ao->type()->as_IntType()) {
156 Constant *c = other->as_Constant();
157 if (c != NULL) {
158 assert(c->type()->as_IntConstant(), "Constant has to be of type integer");
159 int value = c->type()->as_IntConstant()->value();
160 if (value == 1) {
161 has_upper = false;
162 } else if (value > 1) {
163 // Overflow not guaranteed
164 has_upper = false;
165 has_lower = false;
166 } else if (value < 0) {
167 has_lower = false;
168 }
169 continue;
170 }
171 }
172 }
173 }
174 }
175
176 // No connection -> new bound
177 Bound *v_bound = _rce->get_bound(v);
178 Bound *cur_bound;
179 int cur_constant = 0;
180 Value cur_value = v;
181
182 if (v->type()->as_IntConstant()) {
183 cur_constant = v->type()->as_IntConstant()->value();
184 cur_value = NULL;
185 }
186 if (!v_bound->has_upper() || !v_bound->has_lower()) {
187 cur_bound = new Bound(cur_constant, cur_value, cur_constant, cur_value);
188 } else {
189 cur_bound = v_bound;
190 }
191 if (cur_bound) {
192 if (!bound) {
193 bound = cur_bound->copy();
194 } else {
195 bound->or_op(cur_bound);
196 }
197 } else {
198 // No bound!
199 bound = NULL;
200 break;
201 }
202 }
203
204 if (bound) {
205 if (!has_upper) {
206 bound->remove_upper();
207 }
208 if (!has_lower) {
209 bound->remove_lower();
210 }
211 _bound = bound;
212 } else {
213 _bound = new Bound();
214 }
215 }
216
217
218 // ArithmeticOp
219 void RangeCheckEliminator::Visitor::do_ArithmeticOp(ArithmeticOp *ao) {
220 Value x = ao->x();
221 Value y = ao->y();
222
223 if (ao->op() == Bytecodes::_irem) {
224 Bound* x_bound = _rce->get_bound(x);
225 Bound* y_bound = _rce->get_bound(y);
226 if (x_bound->lower() >= 0 && x_bound->lower_instr() == NULL && y->as_ArrayLength() != NULL) {
227 _bound = new Bound(0, NULL, -1, y);
228 } else {
229 _bound = new Bound();
230 }
231 } else if (!x->as_Constant() || !y->as_Constant()) {
232 assert(!x->as_Constant() || !y->as_Constant(), "One of the operands must be non-constant!");
233 if (((x->as_Constant() || y->as_Constant()) && (ao->op() == Bytecodes::_iadd)) || (y->as_Constant() && ao->op() == Bytecodes::_isub)) {
234 assert(ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub, "Operand must be iadd or isub");
235
236 if (y->as_Constant()) {
237 Value tmp = x;
238 x = y;
239 y = tmp;
240 }
241 assert(x->as_Constant()->type()->as_IntConstant(), "Constant must be int constant!");
242
243 // Constant now in x
244 int const_value = x->as_Constant()->type()->as_IntConstant()->value();
245 if (ao->op() == Bytecodes::_iadd || const_value != min_jint) {
246 if (ao->op() == Bytecodes::_isub) {
247 const_value = -const_value;
248 }
249
250 Bound * bound = _rce->get_bound(y);
251 if (bound->has_upper() && bound->has_lower()) {
252 int new_lower = bound->lower() + const_value;
253 jlong new_lowerl = ((jlong)bound->lower()) + const_value;
254 int new_upper = bound->upper() + const_value;
255 jlong new_upperl = ((jlong)bound->upper()) + const_value;
256
257 if (((jlong)new_lower) == new_lowerl && ((jlong)new_upper == new_upperl)) {
258 Bound *newBound = new Bound(new_lower, bound->lower_instr(), new_upper, bound->upper_instr());
259 _bound = newBound;
260 } else {
261 // overflow
262 _bound = new Bound();
263 }
264 } else {
265 _bound = new Bound();
266 }
267 } else {
268 _bound = new Bound();
269 }
270 } else {
271 Bound *bound = _rce->get_bound(x);
272 if (ao->op() == Bytecodes::_isub) {
273 if (bound->lower_instr() == y) {
274 _bound = new Bound(Instruction::geq, NULL, bound->lower());
275 } else {
276 _bound = new Bound();
277 }
278 } else {
279 _bound = new Bound();
280 }
281 }
282 }
283 }
284
285 // IfOp
286 void RangeCheckEliminator::Visitor::do_IfOp(IfOp *ifOp)
287 {
288 if (ifOp->tval()->type()->as_IntConstant() && ifOp->fval()->type()->as_IntConstant()) {
289 int min = ifOp->tval()->type()->as_IntConstant()->value();
290 int max = ifOp->fval()->type()->as_IntConstant()->value();
291 if (min > max) {
292 // min ^= max ^= min ^= max;
293 int tmp = min;
294 min = max;
295 max = tmp;
296 }
297 _bound = new Bound(min, NULL, max, NULL);
298 }
299 }
300
301 // Get bound. Returns the current bound on Value v. Normally this is the topmost element on the bound stack.
302 RangeCheckEliminator::Bound *RangeCheckEliminator::get_bound(Value v) {
303 // Wrong type or NULL -> No bound
304 if (!v || (!v->type()->as_IntType() && !v->type()->as_ObjectType())) return NULL;
305
306 if (!_bounds[v->id()]) {
307 // First (default) bound is calculated
308 // Create BoundStack
309 _bounds[v->id()] = new BoundStack();
310 _visitor.clear_bound();
311 Value visit_value = v;
312 visit_value->visit(&_visitor);
313 Bound *bound = _visitor.bound();
314 if (bound) {
315 _bounds[v->id()]->push(bound);
316 }
317 if (_bounds[v->id()]->length() == 0) {
318 assert(!(v->as_Constant() && v->type()->as_IntConstant()), "constants not handled here");
319 _bounds[v->id()]->push(new Bound());
320 }
321 } else if (_bounds[v->id()]->length() == 0) {
322 // To avoid endless loops, bound is currently in calculation -> nothing known about it
323 return new Bound();
324 }
325
326 // Return bound
327 return _bounds[v->id()]->top();
328 }
329
330 // Update bound
331 void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Instruction::Condition cond, Value value, int constant) {
332 if (cond == Instruction::gtr) {
333 cond = Instruction::geq;
334 constant++;
335 } else if (cond == Instruction::lss) {
336 cond = Instruction::leq;
337 constant--;
338 }
339 Bound *bound = new Bound(cond, value, constant);
340 update_bound(pushed, v, bound);
341 }
342
343 // Checks for loop invariance. Returns true if the instruction is outside of the loop which is identified by loop_header.
344 bool RangeCheckEliminator::loop_invariant(BlockBegin *loop_header, Instruction *instruction) {
345 assert(loop_header, "Loop header must not be null!");
346 if (!instruction) return true;
347 return instruction->dominator_depth() < loop_header->dominator_depth();
348 }
349
350 // Update bound. Pushes a new bound onto the stack. Tries to do a conjunction with the current bound.
351 void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Bound *bound) {
352 if (v->as_Constant()) {
353 // No bound update for constants
354 return;
355 }
356 if (!_bounds[v->id()]) {
357 get_bound(v);
358 assert(_bounds[v->id()], "Now Stack must exist");
359 }
360 Bound *top = NULL;
361 if (_bounds[v->id()]->length() > 0) {
362 top = _bounds[v->id()]->top();
363 }
364 if (top) {
365 bound->and_op(top);
366 }
367 _bounds[v->id()]->push(bound);
368 pushed.append(v->id());
369 }
370
371 // Add instruction + idx for in block motion
372 void RangeCheckEliminator::add_access_indexed_info(InstructionList &indices, int idx, Value instruction, AccessIndexed *ai) {
373 int id = instruction->id();
374 AccessIndexedInfo *aii = _access_indexed_info[id];
375 if (aii == NULL) {
376 aii = new AccessIndexedInfo();
377 _access_indexed_info[id] = aii;
378 indices.append(instruction);
379 aii->_min = idx;
380 aii->_max = idx;
381 aii->_list = new AccessIndexedList();
382 } else if (idx >= aii->_min && idx <= aii->_max) {
383 remove_range_check(ai);
384 return;
385 }
386 aii->_min = MIN2(aii->_min, idx);
387 aii->_max = MAX2(aii->_max, idx);
388 aii->_list->append(ai);
389 }
390
391 // In block motion. Tries to reorder checks in order to reduce some of them.
392 // Example:
393 // a[i] = 0;
394 // a[i+2] = 0;
395 // a[i+1] = 0;
396 // In this example the check for a[i+1] would be considered as unnecessary during the first iteration.
397 // After this i is only checked once for i >= 0 and i+2 < a.length before the first array access. If this
398 // check fails, deoptimization is called.
399 void RangeCheckEliminator::in_block_motion(BlockBegin *block, AccessIndexedList &accessIndexed, InstructionList &arrays) {
400 InstructionList indices;
401
402 // Now iterate over all arrays
403 for (int i=0; i<arrays.length(); i++) {
404 int max_constant = -1;
405 AccessIndexedList list_constant;
406 Value array = arrays.at(i);
407
408 // For all AccessIndexed-instructions in this block concerning the current array.
409 for(int j=0; j<accessIndexed.length(); j++) {
410 AccessIndexed *ai = accessIndexed.at(j);
411 if (ai->array() != array || !ai->check_flag(Instruction::NeedsRangeCheckFlag)) continue;
412
413 Value index = ai->index();
414 Constant *c = index->as_Constant();
415 if (c != NULL) {
416 int constant_value = c->type()->as_IntConstant()->value();
417 if (constant_value >= 0) {
418 if (constant_value <= max_constant) {
419 // No range check needed for this
420 remove_range_check(ai);
421 } else {
422 max_constant = constant_value;
423 list_constant.append(ai);
424 }
425 }
426 } else {
427 int last_integer = 0;
428 Instruction *last_instruction = index;
429 int base = 0;
430 ArithmeticOp *ao = index->as_ArithmeticOp();
431
432 while (ao != NULL && (ao->x()->as_Constant() || ao->y()->as_Constant()) && (ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub)) {
433 c = ao->y()->as_Constant();
434 Instruction *other = ao->x();
435 if (!c && ao->op() == Bytecodes::_iadd) {
436 c = ao->x()->as_Constant();
437 other = ao->y();
438 }
439
440 if (c) {
441 int value = c->type()->as_IntConstant()->value();
442 if (value != min_jint) {
443 if (ao->op() == Bytecodes::_isub) {
444 value = -value;
445 }
446 base += value;
447 last_integer = base;
448 last_instruction = other;
449 }
450 index = other;
451 } else {
452 break;
453 }
454 ao = index->as_ArithmeticOp();
455 }
456 add_access_indexed_info(indices, last_integer, last_instruction, ai);
457 }
458 }
459
460 // Iterate over all different indices
461 if (_optimistic) {
462 for (int i = 0; i < indices.length(); i++) {
463 Instruction *index_instruction = indices.at(i);
464 AccessIndexedInfo *info = _access_indexed_info[index_instruction->id()];
465 assert(info != NULL, "Info must not be null");
466
467 // if idx < 0, max > 0, max + idx may fall between 0 and
468 // length-1 and if min < 0, min + idx may overflow and be >=
469 // 0. The predicate wouldn't trigger but some accesses could
470 // be with a negative index. This test guarantees that for the
471 // min and max value that are kept the predicate can't let
472 // some incorrect accesses happen.
473 bool range_cond = (info->_max < 0 || info->_max + min_jint <= info->_min);
474
475 // Generate code only if more than 2 range checks can be eliminated because of that.
476 // 2 because at least 2 comparisons are done
477 if (info->_list->length() > 2 && range_cond) {
478 AccessIndexed *first = info->_list->at(0);
479 Instruction *insert_position = first->prev();
480 assert(insert_position->next() == first, "prev was calculated");
481 ValueStack *state = first->state_before();
482
483 // Load min Constant
484 Constant *min_constant = NULL;
485 if (info->_min != 0) {
486 min_constant = new Constant(new IntConstant(info->_min));
487 NOT_PRODUCT(min_constant->set_printable_bci(first->printable_bci()));
488 insert_position = insert_position->insert_after(min_constant);
489 }
490
491 // Load max Constant
492 Constant *max_constant = NULL;
493 if (info->_max != 0) {
494 max_constant = new Constant(new IntConstant(info->_max));
495 NOT_PRODUCT(max_constant->set_printable_bci(first->printable_bci()));
496 insert_position = insert_position->insert_after(max_constant);
497 }
498
499 // Load array length
500 Value length_instr = first->length();
501 if (!length_instr) {
502 ArrayLength *length = new ArrayLength(array, first->state_before()->copy());
503 length->set_exception_state(length->state_before());
504 length->set_flag(Instruction::DeoptimizeOnException, true);
505 insert_position = insert_position->insert_after_same_bci(length);
506 length_instr = length;
507 }
508
509 // Calculate lower bound
510 Instruction *lower_compare = index_instruction;
511 if (min_constant) {
512 ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, min_constant, lower_compare, false, NULL);
513 insert_position = insert_position->insert_after_same_bci(ao);
514 lower_compare = ao;
515 }
516
517 // Calculate upper bound
518 Instruction *upper_compare = index_instruction;
519 if (max_constant) {
520 ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, max_constant, upper_compare, false, NULL);
521 insert_position = insert_position->insert_after_same_bci(ao);
522 upper_compare = ao;
523 }
524
525 // Trick with unsigned compare is done
526 int bci = NOT_PRODUCT(first->printable_bci()) PRODUCT_ONLY(-1);
527 insert_position = predicate(upper_compare, Instruction::aeq, length_instr, state, insert_position, bci);
528 insert_position = predicate_cmp_with_const(lower_compare, Instruction::leq, -1, state, insert_position);
529 for (int j = 0; j<info->_list->length(); j++) {
530 AccessIndexed *ai = info->_list->at(j);
531 remove_range_check(ai);
532 }
533 }
534 }
535
536 if (list_constant.length() > 1) {
537 AccessIndexed *first = list_constant.at(0);
538 Instruction *insert_position = first->prev();
539 ValueStack *state = first->state_before();
540 // Load max Constant
541 Constant *constant = new Constant(new IntConstant(max_constant));
542 NOT_PRODUCT(constant->set_printable_bci(first->printable_bci()));
543 insert_position = insert_position->insert_after(constant);
544 Instruction *compare_instr = constant;
545 Value length_instr = first->length();
546 if (!length_instr) {
547 ArrayLength *length = new ArrayLength(array, state->copy());
548 length->set_exception_state(length->state_before());
549 length->set_flag(Instruction::DeoptimizeOnException, true);
550 insert_position = insert_position->insert_after_same_bci(length);
551 length_instr = length;
552 }
553 // Compare for greater or equal to array length
554 insert_position = predicate(compare_instr, Instruction::geq, length_instr, state, insert_position);
555 for (int j = 0; j<list_constant.length(); j++) {
556 AccessIndexed *ai = list_constant.at(j);
557 remove_range_check(ai);
558 }
559 }
560 }
561
562 // Clear data structures for next array
563 for (int i = 0; i < indices.length(); i++) {
564 Instruction *index_instruction = indices.at(i);
565 _access_indexed_info[index_instruction->id()] = NULL;
566 }
567 indices.clear();
568 }
569 }
570
571 bool RangeCheckEliminator::set_process_block_flags(BlockBegin *block) {
572 Instruction *cur = block;
573 bool process = false;
574
575 while (cur) {
576 process |= (cur->as_AccessIndexed() != NULL);
577 cur = cur->next();
578 }
579
580 BlockList *dominates = block->dominates();
581 for (int i=0; i<dominates->length(); i++) {
582 BlockBegin *next = dominates->at(i);
583 process |= set_process_block_flags(next);
584 }
585
586 if (!process) {
587 block->set(BlockBegin::donot_eliminate_range_checks);
588 }
589 return process;
590 }
591
592 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) {
593 bool upper_check = true;
594 assert(lower_instr || lower >= 0, "If no lower_instr present, lower must be greater 0");
595 assert(!lower_instr || lower_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
596 assert(!upper_instr || upper_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
597 assert(array_instr, "Array instruction must exist");
598 assert(array_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
599 assert(!length_instr || length_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
600
601 if (upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr) {
602 // static check
603 if (upper >= 0) return false; // would always trigger a deopt:
604 // array_length + x >= array_length, x >= 0 is always true
605 upper_check = false;
606 }
607 if (lower_instr && lower_instr->as_ArrayLength() && lower_instr->as_ArrayLength()->array() == array_instr) {
608 if (lower > 0) return false;
609 }
610 // No upper check required -> skip
611 if (upper_check && upper_instr && upper_instr->type()->as_ObjectType() && upper_instr == array_instr) {
612 // upper_instr is object means that the upper bound is the length
613 // of the upper_instr.
614 return false;
615 }
616 return true;
617 }
618
619 Instruction* RangeCheckEliminator::insert_after(Instruction* insert_position, Instruction* instr, int bci) {
620 if (bci != -1) {
621 NOT_PRODUCT(instr->set_printable_bci(bci));
622 return insert_position->insert_after(instr);
623 } else {
624 return insert_position->insert_after_same_bci(instr);
625 }
626 }
627
628 Instruction* RangeCheckEliminator::predicate(Instruction* left, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) {
629 RangeCheckPredicate *deoptimize = new RangeCheckPredicate(left, cond, true, right, state->copy());
630 return insert_after(insert_position, deoptimize, bci);
631 }
632
633 Instruction* RangeCheckEliminator::predicate_cmp_with_const(Instruction* instr, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) {
634 Constant *const_instr = new Constant(new IntConstant(constant));
635 insert_position = insert_after(insert_position, const_instr, bci);
636 return predicate(instr, cond, const_instr, state, insert_position);
637 }
638
639 Instruction* RangeCheckEliminator::predicate_add(Instruction* left, int left_const, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) {
640 Constant *constant = new Constant(new IntConstant(left_const));
641 insert_position = insert_after(insert_position, constant, bci);
642 ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, left, false, NULL);
643 insert_position = insert_position->insert_after_same_bci(ao);
644 return predicate(ao, cond, right, state, insert_position);
645 }
646
647 Instruction* RangeCheckEliminator::predicate_add_cmp_with_const(Instruction* left, int left_const, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) {
648 Constant *const_instr = new Constant(new IntConstant(constant));
649 insert_position = insert_after(insert_position, const_instr, bci);
650 return predicate_add(left, left_const, cond, const_instr, state, insert_position);
651 }
652
653 // Insert deoptimization
654 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) {
655 assert(is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, lower, upper_instr, upper), "should have been tested before");
656 bool upper_check = !(upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr);
657
658 int bci = NOT_PRODUCT(ai->printable_bci()) PRODUCT_ONLY(-1);
659 if (lower_instr) {
660 assert(!lower_instr->type()->as_ObjectType(), "Must not be object type");
661 if (lower == 0) {
662 // Compare for less than 0
663 insert_position = predicate_cmp_with_const(lower_instr, Instruction::lss, 0, state, insert_position, bci);
664 } else if (lower > 0) {
665 // Compare for smaller 0
666 insert_position = predicate_add_cmp_with_const(lower_instr, lower, Instruction::lss, 0, state, insert_position, bci);
667 } else {
668 assert(lower < 0, "");
669 // Add 1
670 lower++;
671 lower = -lower;
672 // Compare for smaller or equal 0
673 insert_position = predicate_cmp_with_const(lower_instr, Instruction::leq, lower, state, insert_position, bci);
674 }
675 }
676
677 // No upper check required -> skip
678 if (!upper_check) return;
679
680 // We need to know length of array
681 if (!length_instr) {
682 // Load length if necessary
683 ArrayLength *length = new ArrayLength(array_instr, state->copy());
684 NOT_PRODUCT(length->set_printable_bci(ai->printable_bci()));
685 length->set_exception_state(length->state_before());
686 length->set_flag(Instruction::DeoptimizeOnException, true);
687 insert_position = insert_position->insert_after(length);
688 length_instr = length;
689 }
690
691 if (!upper_instr) {
692 // Compare for geq array.length
693 insert_position = predicate_cmp_with_const(length_instr, Instruction::leq, upper, state, insert_position, bci);
694 } else {
695 if (upper_instr->type()->as_ObjectType()) {
696 assert(state, "must not be null");
697 assert(upper_instr != array_instr, "should be");
698 ArrayLength *length = new ArrayLength(upper_instr, state->copy());
699 NOT_PRODUCT(length->set_printable_bci(ai->printable_bci()));
700 length->set_flag(Instruction::DeoptimizeOnException, true);
701 length->set_exception_state(length->state_before());
702 insert_position = insert_position->insert_after(length);
703 upper_instr = length;
704 }
705 assert(upper_instr->type()->as_IntType(), "Must not be object type!");
706
707 if (upper == 0) {
708 // Compare for geq array.length
709 insert_position = predicate(upper_instr, Instruction::geq, length_instr, state, insert_position, bci);
710 } else if (upper < 0) {
711 // Compare for geq array.length
712 insert_position = predicate_add(upper_instr, upper, Instruction::geq, length_instr, state, insert_position, bci);
713 } else {
714 assert(upper > 0, "");
715 upper = -upper;
716 // Compare for geq array.length
717 insert_position = predicate_add(length_instr, upper, Instruction::leq, upper_instr, state, insert_position, bci);
718 }
719 }
720 }
721
722 // Add if condition
723 void RangeCheckEliminator::add_if_condition(IntegerStack &pushed, Value x, Value y, Instruction::Condition condition) {
724 if (y->as_Constant()) return;
725
726 int const_value = 0;
727 Value instr_value = x;
728 Constant *c = x->as_Constant();
729 ArithmeticOp *ao = x->as_ArithmeticOp();
730
731 if (c != NULL) {
732 const_value = c->type()->as_IntConstant()->value();
733 instr_value = NULL;
734 } else if (ao != NULL && (!ao->x()->as_Constant() || !ao->y()->as_Constant()) && ((ao->op() == Bytecodes::_isub && ao->y()->as_Constant()) || ao->op() == Bytecodes::_iadd)) {
735 assert(!ao->x()->as_Constant() || !ao->y()->as_Constant(), "At least one operator must be non-constant!");
736 assert(ao->op() == Bytecodes::_isub || ao->op() == Bytecodes::_iadd, "Operation has to be add or sub!");
737 c = ao->x()->as_Constant();
738 if (c != NULL) {
739 const_value = c->type()->as_IntConstant()->value();
740 instr_value = ao->y();
741 } else {
742 c = ao->y()->as_Constant();
743 if (c != NULL) {
744 const_value = c->type()->as_IntConstant()->value();
745 instr_value = ao->x();
746 }
747 }
748 if (ao->op() == Bytecodes::_isub) {
749 assert(ao->y()->as_Constant(), "1 - x not supported, only x - 1 is valid!");
750 if (const_value > min_jint) {
751 const_value = -const_value;
752 } else {
753 const_value = 0;
754 instr_value = x;
755 }
756 }
757 }
758
759 update_bound(pushed, y, condition, instr_value, const_value);
760 }
761
762 // Process If
763 void RangeCheckEliminator::process_if(IntegerStack &pushed, BlockBegin *block, If *cond) {
764 // Only if we are direct true / false successor and NOT both ! (even this may occur)
765 if ((cond->tsux() == block || cond->fsux() == block) && cond->tsux() != cond->fsux()) {
766 Instruction::Condition condition = cond->cond();
767 if (cond->fsux() == block) {
768 condition = Instruction::negate(condition);
769 }
770 Value x = cond->x();
771 Value y = cond->y();
772 if (x->type()->as_IntType() && y->type()->as_IntType()) {
773 add_if_condition(pushed, y, x, condition);
774 add_if_condition(pushed, x, y, Instruction::mirror(condition));
775 }
776 }
777 }
778
779 // Process access indexed
780 void RangeCheckEliminator::process_access_indexed(BlockBegin *loop_header, BlockBegin *block, AccessIndexed *ai) {
781 TRACE_RANGE_CHECK_ELIMINATION(
782 tty->fill_to(block->dominator_depth()*2)
783 );
784 TRACE_RANGE_CHECK_ELIMINATION(
785 tty->print_cr("Access indexed: index=%d length=%d", ai->index()->id(), (ai->length() != NULL ? ai->length()->id() :-1 ))
786 );
787
788 if (ai->check_flag(Instruction::NeedsRangeCheckFlag)) {
789 Bound *index_bound = get_bound(ai->index());
790 if (!index_bound->has_lower() || !index_bound->has_upper()) {
791 TRACE_RANGE_CHECK_ELIMINATION(
792 tty->fill_to(block->dominator_depth()*2);
793 tty->print_cr("Index instruction %d has no lower and/or no upper bound!", ai->index()->id())
794 );
795 return;
796 }
797
798 Bound *array_bound;
799 if (ai->length()) {
800 array_bound = get_bound(ai->length());
801 } else {
802 array_bound = get_bound(ai->array());
803 }
804
805 if (in_array_bound(index_bound, ai->array()) ||
806 (index_bound && array_bound && index_bound->is_smaller(array_bound) && !index_bound->lower_instr() && index_bound->lower() >= 0)) {
807 TRACE_RANGE_CHECK_ELIMINATION(
808 tty->fill_to(block->dominator_depth()*2);
809 tty->print_cr("Bounds check for instruction %d in block B%d can be fully eliminated!", ai->id(), ai->block()->block_id())
810 );
811
812 remove_range_check(ai);
813 } else if (_optimistic && loop_header) {
814 assert(ai->array(), "Array must not be null!");
815 assert(ai->index(), "Index must not be null!");
816
817 // Array instruction
818 Instruction *array_instr = ai->array();
819 if (!loop_invariant(loop_header, array_instr)) {
820 TRACE_RANGE_CHECK_ELIMINATION(
821 tty->fill_to(block->dominator_depth()*2);
822 tty->print_cr("Array %d is not loop invariant to header B%d", ai->array()->id(), loop_header->block_id())
823 );
824 return;
825 }
826
827 // Lower instruction
828 Value index_instr = ai->index();
829 Value lower_instr = index_bound->lower_instr();
830 if (!loop_invariant(loop_header, lower_instr)) {
831 TRACE_RANGE_CHECK_ELIMINATION(
832 tty->fill_to(block->dominator_depth()*2);
833 tty->print_cr("Lower instruction %d not loop invariant!", lower_instr->id())
834 );
835 return;
836 }
837 if (!lower_instr && index_bound->lower() < 0) {
838 TRACE_RANGE_CHECK_ELIMINATION(
839 tty->fill_to(block->dominator_depth()*2);
840 tty->print_cr("Lower bound smaller than 0 (%d)!", index_bound->lower())
841 );
842 return;
843 }
844
845 // Upper instruction
846 Value upper_instr = index_bound->upper_instr();
847 if (!loop_invariant(loop_header, upper_instr)) {
848 TRACE_RANGE_CHECK_ELIMINATION(
849 tty->fill_to(block->dominator_depth()*2);
850 tty->print_cr("Upper instruction %d not loop invariant!", upper_instr->id())
851 );
852 return;
853 }
854
855 // Length instruction
856 Value length_instr = ai->length();
857 if (!loop_invariant(loop_header, length_instr)) {
858 // Generate length instruction yourself!
859 length_instr = NULL;
860 }
861
862 TRACE_RANGE_CHECK_ELIMINATION(
863 tty->fill_to(block->dominator_depth()*2);
864 tty->print_cr("LOOP INVARIANT access indexed %d found in block B%d!", ai->id(), ai->block()->block_id())
865 );
866
867 BlockBegin *pred_block = loop_header->dominator();
868 assert(pred_block != NULL, "Every loop header has a dominator!");
869 BlockEnd *pred_block_end = pred_block->end();
870 Instruction *insert_position = pred_block_end->prev();
871 ValueStack *state = pred_block_end->state_before();
872 if (pred_block_end->as_Goto() && state == NULL) state = pred_block_end->state();
873 assert(state, "State must not be null");
874
875 // Add deoptimization to dominator of loop header
876 TRACE_RANGE_CHECK_ELIMINATION(
877 tty->fill_to(block->dominator_depth()*2);
878 tty->print_cr("Inserting deopt at bci %d in block B%d!", state->bci(), insert_position->block()->block_id())
879 );
880
881 if (!is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper())) {
882 TRACE_RANGE_CHECK_ELIMINATION(
883 tty->fill_to(block->dominator_depth()*2);
884 tty->print_cr("Could not eliminate because of static analysis!")
885 );
886 return;
887 }
888
889 insert_deoptimization(state, insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper(), ai);
890
891 // Finally remove the range check!
892 remove_range_check(ai);
893 }
894 }
895 }
896
897 void RangeCheckEliminator::remove_range_check(AccessIndexed *ai) {
898 ai->set_flag(Instruction::NeedsRangeCheckFlag, false);
899 // no range check, no need for the length instruction anymore
900 ai->clear_length();
901
902 TRACE_RANGE_CHECK_ELIMINATION(
903 tty->fill_to(ai->dominator_depth()*2);
904 tty->print_cr("Range check for instruction %d eliminated!", ai->id());
905 );
906
907 ASSERT_RANGE_CHECK_ELIMINATION(
908 Value array_length = ai->length();
909 if (!array_length) {
910 array_length = ai->array();
911 assert(array_length->type()->as_ObjectType(), "Has to be object type!");
912 }
913 int cur_constant = -1;
914 Value cur_value = array_length;
915 if (cur_value->type()->as_IntConstant()) {
916 cur_constant += cur_value->type()->as_IntConstant()->value();
917 cur_value = NULL;
918 }
919 Bound *new_index_bound = new Bound(0, NULL, cur_constant, cur_value);
920 add_assertions(new_index_bound, ai->index(), ai);
921 );
922 }
923
924 // Calculate bounds for instruction in this block and children blocks in the dominator tree
925 void RangeCheckEliminator::calc_bounds(BlockBegin *block, BlockBegin *loop_header) {
926 // Ensures a valid loop_header
927 assert(!loop_header || loop_header->is_set(BlockBegin::linear_scan_loop_header_flag), "Loop header has to be real !");
928
929 // Tracing output
930 TRACE_RANGE_CHECK_ELIMINATION(
931 tty->fill_to(block->dominator_depth()*2);
932 tty->print_cr("Block B%d", block->block_id());
933 );
934
935 // Pushed stack for conditions
936 IntegerStack pushed;
937 // Process If
938 BlockBegin *parent = block->dominator();
939 if (parent != NULL) {
940 If *cond = parent->end()->as_If();
941 if (cond != NULL) {
942 process_if(pushed, block, cond);
943 }
944 }
945
946 // Interate over current block
947 InstructionList arrays;
948 AccessIndexedList accessIndexed;
949 Instruction *cur = block;
950
951 while (cur) {
952 // Ensure cur wasn't inserted during the elimination
953 if (cur->id() < this->_bounds.length()) {
954 // Process only if it is an access indexed instruction
955 AccessIndexed *ai = cur->as_AccessIndexed();
956 if (ai != NULL) {
957 process_access_indexed(loop_header, block, ai);
958 accessIndexed.append(ai);
959 if (!arrays.contains(ai->array())) {
960 arrays.append(ai->array());
961 }
962 Bound *b = get_bound(ai->index());
963 if (!b->lower_instr()) {
964 // Lower bound is constant
965 update_bound(pushed, ai->index(), Instruction::geq, NULL, 0);
966 }
967 if (!b->has_upper()) {
968 if (ai->length() && ai->length()->type()->as_IntConstant()) {
969 int value = ai->length()->type()->as_IntConstant()->value();
970 update_bound(pushed, ai->index(), Instruction::lss, NULL, value);
971 } else {
972 // Has no upper bound
973 Instruction *instr = ai->length();
974 if (instr != NULL) instr = ai->array();
975 update_bound(pushed, ai->index(), Instruction::lss, instr, 0);
976 }
977 }
978 }
979 }
980 cur = cur->next();
981 }
982
983 // Output current condition stack
984 TRACE_RANGE_CHECK_ELIMINATION(dump_condition_stack(block));
985
986 // Do in block motion of range checks
987 in_block_motion(block, accessIndexed, arrays);
988
989 // Call all dominated blocks
990 for (int i=0; i<block->dominates()->length(); i++) {
991 BlockBegin *next = block->dominates()->at(i);
992 if (!next->is_set(BlockBegin::donot_eliminate_range_checks)) {
993 // if current block is a loop header and:
994 // - next block belongs to the same loop
995 // or
996 // - next block belongs to an inner loop
997 // then current block is the loop header for next block
998 if (block->is_set(BlockBegin::linear_scan_loop_header_flag) && (block->loop_index() == next->loop_index() || next->loop_depth() > block->loop_depth())) {
999 calc_bounds(next, block);
1000 } else {
1001 calc_bounds(next, loop_header);
1002 }
1003 }
1004 }
1005
1006 // Reset stack
1007 for (int i=0; i<pushed.length(); i++) {
1008 _bounds[pushed[i]]->pop();
1009 }
1010 }
1011
1012 #ifndef PRODUCT
1013 // Dump condition stack
1014 void RangeCheckEliminator::dump_condition_stack(BlockBegin *block) {
1015 for (int i=0; i<_ir->linear_scan_order()->length(); i++) {
1016 BlockBegin *cur_block = _ir->linear_scan_order()->at(i);
1017 Instruction *instr = cur_block;
1018 for_each_phi_fun(cur_block, phi,
1019 BoundStack *bound_stack = _bounds.at(phi->id());
1020 if (bound_stack && bound_stack->length() > 0) {
1021 Bound *bound = bound_stack->top();
1022 if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != phi || bound->upper_instr() != phi || bound->lower() != 0 || bound->upper() != 0)) {
1023 TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth());
1024 tty->print("i%d", phi->id());
1025 tty->print(": ");
1026 bound->print();
1027 tty->cr();
1028 );
1029 }
1030 });
1031
1032 while (!instr->as_BlockEnd()) {
1033 if (instr->id() < _bounds.length()) {
1034 BoundStack *bound_stack = _bounds.at(instr->id());
1035 if (bound_stack && bound_stack->length() > 0) {
1036 Bound *bound = bound_stack->top();
1037 if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != instr || bound->upper_instr() != instr || bound->lower() != 0 || bound->upper() != 0)) {
1038 TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth());
1039 tty->print("i%d", instr->id());
1040 tty->print(": ");
1041 bound->print();
1042 tty->cr();
1043 );
1044 }
1045 }
1046 }
1047 instr = instr->next();
1048 }
1049 }
1050 }
1051 #endif
1052
1053 // Verification or the IR
1054 RangeCheckEliminator::Verification::Verification(IR *ir) : _used(BlockBegin::number_of_blocks(), false) {
1055 this->_ir = ir;
1056 ir->iterate_linear_scan_order(this);
1057 }
1058
1059 // Verify this block
1060 void RangeCheckEliminator::Verification::block_do(BlockBegin *block) {
1061 If *cond = block->end()->as_If();
1062 // Watch out: tsux and fsux can be the same!
1063 if (block->number_of_sux() > 1) {
1064 for (int i=0; i<block->number_of_sux(); i++) {
1065 BlockBegin *sux = block->sux_at(i);
1066 BlockBegin *pred = NULL;
1067 for (int j=0; j<sux->number_of_preds(); j++) {
1068 BlockBegin *cur = sux->pred_at(j);
1069 assert(cur != NULL, "Predecessor must not be null");
1070 if (!pred) {
1071 pred = cur;
1072 }
1073 assert(cur == pred, "Block must not have more than one predecessor if its predecessor has more than one successor");
1074 }
1075 assert(sux->number_of_preds() >= 1, "Block must have at least one predecessor");
1076 assert(sux->pred_at(0) == block, "Wrong successor");
1077 }
1078 }
1079
1080 BlockBegin *dominator = block->dominator();
1081 if (dominator) {
1082 assert(block != _ir->start(), "Start block must not have a dominator!");
1083 assert(can_reach(dominator, block), "Dominator can't reach his block !");
1084 assert(can_reach(_ir->start(), dominator), "Dominator is unreachable !");
1085 assert(!can_reach(_ir->start(), block, dominator), "Wrong dominator ! Block can be reached anyway !");
1086 BlockList *all_blocks = _ir->linear_scan_order();
1087 for (int i=0; i<all_blocks->length(); i++) {
1088 BlockBegin *cur = all_blocks->at(i);
1089 if (cur != dominator && cur != block) {
1090 assert(can_reach(dominator, block, cur), "There has to be another dominator!");
1091 }
1092 }
1093 } else {
1094 assert(block == _ir->start(), "Only start block must not have a dominator");
1095 }
1096
1097 if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) {
1098 int loop_index = block->loop_index();
1099 BlockList *all_blocks = _ir->linear_scan_order();
1100 assert(block->number_of_preds() >= 1, "Block must have at least one predecessor");
1101 assert(!block->is_set(BlockBegin::exception_entry_flag), "Loop header must not be exception handler!");
1102 // Sometimes, the backbranch comes from an exception handler. In
1103 // this case, loop indexes/loop depths may not appear correct.
1104 bool loop_through_xhandler = false;
1105 for (int i = 0; i < block->number_of_exception_handlers(); i++) {
1106 BlockBegin *xhandler = block->exception_handler_at(i);
1107 for (int j = 0; j < block->number_of_preds(); j++) {
1108 if (dominates(xhandler, block->pred_at(j)) || xhandler == block->pred_at(j)) {
1109 loop_through_xhandler = true;
1110 }
1111 }
1112 }
1113
1114 for (int i=0; i<block->number_of_sux(); i++) {
1115 BlockBegin *sux = block->sux_at(i);
1116 assert(sux->loop_depth() != block->loop_depth() || sux->loop_index() == block->loop_index() || loop_through_xhandler, "Loop index has to be same");
1117 assert(sux->loop_depth() == block->loop_depth() || sux->loop_index() != block->loop_index(), "Loop index has to be different");
1118 }
1119
1120 for (int i=0; i<all_blocks->length(); i++) {
1121 BlockBegin *cur = all_blocks->at(i);
1122 if (cur->loop_index() == loop_index && cur != block) {
1123 assert(dominates(block->dominator(), cur), "Dominator of loop header must dominate all loop blocks");
1124 }
1125 }
1126 }
1127
1128 Instruction *cur = block;
1129 while (cur) {
1130 assert(cur->block() == block, "Block begin has to be set correctly!");
1131 cur = cur->next();
1132 }
1133 }
1134
1135 // Loop header must dominate all loop blocks
1136 bool RangeCheckEliminator::Verification::dominates(BlockBegin *dominator, BlockBegin *block) {
1137 BlockBegin *cur = block->dominator();
1138 while (cur && cur != dominator) {
1139 cur = cur->dominator();
1140 }
1141 return cur == dominator;
1142 }
1143
1144 // Try to reach Block end beginning in Block start and not using Block dont_use
1145 bool RangeCheckEliminator::Verification::can_reach(BlockBegin *start, BlockBegin *end, BlockBegin *dont_use /* = NULL */) {
1146 if (start == end) return start != dont_use;
1147 // Simple BSF from start to end
1148 // BlockBeginList _current;
1149 for (int i=0; i<_used.length(); i++) {
1150 _used[i] = false;
1151 }
1152 _current.truncate(0);
1153 _successors.truncate(0);
1154 if (start != dont_use) {
1155 _current.push(start);
1156 _used[start->block_id()] = true;
1157 }
1158
1159 // BlockBeginList _successors;
1160 while (_current.length() > 0) {
1161 BlockBegin *cur = _current.pop();
1162 // Add exception handlers to list
1163 for (int i=0; i<cur->number_of_exception_handlers(); i++) {
1164 BlockBegin *xhandler = cur->exception_handler_at(i);
1165 _successors.push(xhandler);
1166 // Add exception handlers of _successors to list
1167 for (int j=0; j<xhandler->number_of_exception_handlers(); j++) {
1168 BlockBegin *sux_xhandler = xhandler->exception_handler_at(j);
1169 _successors.push(sux_xhandler);
1170 }
1171 }
1172 // Add normal _successors to list
1173 for (int i=0; i<cur->number_of_sux(); i++) {
1174 BlockBegin *sux = cur->sux_at(i);
1175 _successors.push(sux);
1176 // Add exception handlers of _successors to list
1177 for (int j=0; j<sux->number_of_exception_handlers(); j++) {
1178 BlockBegin *xhandler = sux->exception_handler_at(j);
1179 _successors.push(xhandler);
1180 }
1181 }
1182 for (int i=0; i<_successors.length(); i++) {
1183 BlockBegin *sux = _successors[i];
1184 assert(sux != NULL, "Successor must not be NULL!");
1185 if (sux == end) {
1186 return true;
1187 }
1188 if (sux != dont_use && !_used[sux->block_id()]) {
1189 _used[sux->block_id()] = true;
1190 _current.push(sux);
1191 }
1192 }
1193 _successors.truncate(0);
1194 }
1195
1196 return false;
1197 }
1198
1199 // Bound
1200 RangeCheckEliminator::Bound::~Bound() {
1201 }
1202
1203 // Bound constructor
1204 RangeCheckEliminator::Bound::Bound() {
1205 init();
1206 this->_lower = min_jint;
1207 this->_upper = max_jint;
1208 this->_lower_instr = NULL;
1209 this->_upper_instr = NULL;
1210 }
1211
1212 // Bound constructor
1213 RangeCheckEliminator::Bound::Bound(int lower, Value lower_instr, int upper, Value upper_instr) {
1214 init();
1215 assert(!lower_instr || !lower_instr->as_Constant() || !lower_instr->type()->as_IntConstant(), "Must not be constant!");
1216 assert(!upper_instr || !upper_instr->as_Constant() || !upper_instr->type()->as_IntConstant(), "Must not be constant!");
1217 this->_lower = lower;
1218 this->_upper = upper;
1219 this->_lower_instr = lower_instr;
1220 this->_upper_instr = upper_instr;
1221 }
1222
1223 // Bound constructor
1224 RangeCheckEliminator::Bound::Bound(Instruction::Condition cond, Value v, int constant) {
1225 assert(!v || (v->type() && (v->type()->as_IntType() || v->type()->as_ObjectType())), "Type must be array or integer!");
1226 assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!");
1227
1228 init();
1229 if (cond == Instruction::eql) {
1230 _lower = constant;
1231 _lower_instr = v;
1232 _upper = constant;
1233 _upper_instr = v;
1234 } else if (cond == Instruction::neq) {
1235 _lower = min_jint;
1236 _upper = max_jint;
1237 _lower_instr = NULL;
1238 _upper_instr = NULL;
1239 if (v == NULL) {
1240 if (constant == min_jint) {
1241 _lower++;
1242 }
1243 if (constant == max_jint) {
1244 _upper--;
1245 }
1246 }
1247 } else if (cond == Instruction::geq) {
1248 _lower = constant;
1249 _lower_instr = v;
1250 _upper = max_jint;
1251 _upper_instr = NULL;
1252 } else if (cond == Instruction::leq) {
1253 _lower = min_jint;
1254 _lower_instr = NULL;
1255 _upper = constant;
1256 _upper_instr = v;
1257 } else {
1258 ShouldNotReachHere();
1259 }
1260 }
1261
1262 // Set lower
1263 void RangeCheckEliminator::Bound::set_lower(int value, Value v) {
1264 assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!");
1265 this->_lower = value;
1266 this->_lower_instr = v;
1267 }
1268
1269 // Set upper
1270 void RangeCheckEliminator::Bound::set_upper(int value, Value v) {
1271 assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!");
1272 this->_upper = value;
1273 this->_upper_instr = v;
1274 }
1275
1276 // Add constant -> no overflow may occur
1277 void RangeCheckEliminator::Bound::add_constant(int value) {
1278 this->_lower += value;
1279 this->_upper += value;
1280 }
1281
1282 // Init
1283 void RangeCheckEliminator::Bound::init() {
1284 }
1285
1286 // or
1287 void RangeCheckEliminator::Bound::or_op(Bound *b) {
1288 // Watch out, bound is not guaranteed not to overflow!
1289 // Update lower bound
1290 if (_lower_instr != b->_lower_instr || (_lower_instr && _lower != b->_lower)) {
1291 _lower_instr = NULL;
1292 _lower = min_jint;
1293 } else {
1294 _lower = MIN2(_lower, b->_lower);
1295 }
1296 // Update upper bound
1297 if (_upper_instr != b->_upper_instr || (_upper_instr && _upper != b->_upper)) {
1298 _upper_instr = NULL;
1299 _upper = max_jint;
1300 } else {
1301 _upper = MAX2(_upper, b->_upper);
1302 }
1303 }
1304
1305 // and
1306 void RangeCheckEliminator::Bound::and_op(Bound *b) {
1307 // Update lower bound
1308 if (_lower_instr == b->_lower_instr) {
1309 _lower = MAX2(_lower, b->_lower);
1310 }
1311 if (b->has_lower()) {
1312 bool set = true;
1313 if (_lower_instr != NULL && b->_lower_instr != NULL) {
1314 set = (_lower_instr->dominator_depth() > b->_lower_instr->dominator_depth());
1315 }
1316 if (set) {
1317 _lower = b->_lower;
1318 _lower_instr = b->_lower_instr;
1319 }
1320 }
1321 // Update upper bound
1322 if (_upper_instr == b->_upper_instr) {
1323 _upper = MIN2(_upper, b->_upper);
1324 }
1325 if (b->has_upper()) {
1326 bool set = true;
1327 if (_upper_instr != NULL && b->_upper_instr != NULL) {
1328 set = (_upper_instr->dominator_depth() > b->_upper_instr->dominator_depth());
1329 }
1330 if (set) {
1331 _upper = b->_upper;
1332 _upper_instr = b->_upper_instr;
1333 }
1334 }
1335 }
1336
1337 // has_upper
1338 bool RangeCheckEliminator::Bound::has_upper() {
1339 return _upper_instr != NULL || _upper < max_jint;
1340 }
1341
1342 // is_smaller
1343 bool RangeCheckEliminator::Bound::is_smaller(Bound *b) {
1344 if (b->_lower_instr != _upper_instr) {
1345 return false;
1346 }
1347 return _upper < b->_lower;
1348 }
1349
1350 // has_lower
1351 bool RangeCheckEliminator::Bound::has_lower() {
1352 return _lower_instr != NULL || _lower > min_jint;
1353 }
1354
1355 // in_array_bound
1356 bool RangeCheckEliminator::in_array_bound(Bound *bound, Value array){
1357 if (!bound) return false;
1358 assert(array != NULL, "Must not be null!");
1359 assert(bound != NULL, "Must not be null!");
1360 if (bound->lower() >=0 && bound->lower_instr() == NULL && bound->upper() < 0 && bound->upper_instr() != NULL) {
1361 ArrayLength *len = bound->upper_instr()->as_ArrayLength();
1362 if (bound->upper_instr() == array || (len != NULL && len->array() == array)) {
1363 return true;
1364 }
1365 }
1366 return false;
1367 }
1368
1369 // remove_lower
1370 void RangeCheckEliminator::Bound::remove_lower() {
1371 _lower = min_jint;
1372 _lower_instr = NULL;
1373 }
1374
1375 // remove_upper
1376 void RangeCheckEliminator::Bound::remove_upper() {
1377 _upper = max_jint;
1378 _upper_instr = NULL;
1379 }
1380
1381 // upper
1382 int RangeCheckEliminator::Bound::upper() {
1383 return _upper;
1384 }
1385
1386 // lower
1387 int RangeCheckEliminator::Bound::lower() {
1388 return _lower;
1389 }
1390
1391 // upper_instr
1392 Value RangeCheckEliminator::Bound::upper_instr() {
1393 return _upper_instr;
1394 }
1395
1396 // lower_instr
1397 Value RangeCheckEliminator::Bound::lower_instr() {
1398 return _lower_instr;
1399 }
1400
1401 // print
1402 void RangeCheckEliminator::Bound::print() {
1403 tty->print("%s", "");
1404 if (this->_lower_instr || this->_lower != min_jint) {
1405 if (this->_lower_instr) {
1406 tty->print("i%d", this->_lower_instr->id());
1407 if (this->_lower > 0) {
1408 tty->print("+%d", _lower);
1409 }
1410 if (this->_lower < 0) {
1411 tty->print("%d", _lower);
1412 }
1413 } else {
1414 tty->print("%d", _lower);
1415 }
1416 tty->print(" <= ");
1417 }
1418 tty->print("x");
1419 if (this->_upper_instr || this->_upper != max_jint) {
1420 tty->print(" <= ");
1421 if (this->_upper_instr) {
1422 tty->print("i%d", this->_upper_instr->id());
1423 if (this->_upper > 0) {
1424 tty->print("+%d", _upper);
1425 }
1426 if (this->_upper < 0) {
1427 tty->print("%d", _upper);
1428 }
1429 } else {
1430 tty->print("%d", _upper);
1431 }
1432 }
1433 }
1434
1435 // Copy
1436 RangeCheckEliminator::Bound *RangeCheckEliminator::Bound::copy() {
1437 Bound *b = new Bound();
1438 b->_lower = _lower;
1439 b->_lower_instr = _lower_instr;
1440 b->_upper = _upper;
1441 b->_upper_instr = _upper_instr;
1442 return b;
1443 }
1444
1445 #ifdef ASSERT
1446 // Add assertion
1447 void RangeCheckEliminator::Bound::add_assertion(Instruction *instruction, Instruction *position, int i, Value instr, Instruction::Condition cond) {
1448 Instruction *result = position;
1449 Instruction *compare_with = NULL;
1450 ValueStack *state = position->state_before();
1451 if (position->as_BlockEnd() && !position->as_Goto()) {
1452 state = position->as_BlockEnd()->state_before();
1453 }
1454 Instruction *instruction_before = position->prev();
1455 if (position->as_Return() && Compilation::current()->method()->is_synchronized() && instruction_before->as_MonitorExit()) {
1456 instruction_before = instruction_before->prev();
1457 }
1458 result = instruction_before;
1459 // Load constant only if needed
1460 Constant *constant = NULL;
1461 if (i != 0 || !instr) {
1462 constant = new Constant(new IntConstant(i));
1463 NOT_PRODUCT(constant->set_printable_bci(position->printable_bci()));
1464 result = result->insert_after(constant);
1465 compare_with = constant;
1466 }
1467
1468 if (instr) {
1469 assert(instr->type()->as_ObjectType() || instr->type()->as_IntType(), "Type must be array or integer!");
1470 compare_with = instr;
1471 // Load array length if necessary
1472 Instruction *op = instr;
1473 if (instr->type()->as_ObjectType()) {
1474 assert(state, "must not be null");
1475 ArrayLength *length = new ArrayLength(instr, state->copy());
1476 NOT_PRODUCT(length->set_printable_bci(position->printable_bci()));
1477 length->set_exception_state(length->state_before());
1478 result = result->insert_after(length);
1479 op = length;
1480 compare_with = length;
1481 }
1482 // Add operation only if necessary
1483 if (constant) {
1484 ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, op, false, NULL);
1485 NOT_PRODUCT(ao->set_printable_bci(position->printable_bci()));
1486 result = result->insert_after(ao);
1487 compare_with = ao;
1488 // TODO: Check that add operation does not overflow!
1489 }
1490 }
1491 assert(compare_with != NULL, "You have to compare with something!");
1492 assert(instruction != NULL, "Instruction must not be null!");
1493
1494 if (instruction->type()->as_ObjectType()) {
1495 // Load array length if necessary
1496 Instruction *op = instruction;
1497 assert(state, "must not be null");
1498 ArrayLength *length = new ArrayLength(instruction, state->copy());
1499 length->set_exception_state(length->state_before());
1500 NOT_PRODUCT(length->set_printable_bci(position->printable_bci()));
1501 result = result->insert_after(length);
1502 instruction = length;
1503 }
1504
1505 Assert *assert = new Assert(instruction, cond, false, compare_with);
1506 NOT_PRODUCT(assert->set_printable_bci(position->printable_bci()));
1507 result->insert_after(assert);
1508 }
1509
1510 // Add assertions
1511 void RangeCheckEliminator::add_assertions(Bound *bound, Instruction *instruction, Instruction *position) {
1512 // Add lower bound assertion
1513 if (bound->has_lower()) {
1514 bound->add_assertion(instruction, position, bound->lower(), bound->lower_instr(), Instruction::geq);
1515 }
1516 // Add upper bound assertion
1517 if (bound->has_upper()) {
1518 bound->add_assertion(instruction, position, bound->upper(), bound->upper_instr(), Instruction::leq);
1519 }
1520 }
1521 #endif
1522