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 *
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(
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
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;
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
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 );
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 }
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) {
|
1 /*
2 * Copyright (c) 2012, 2016, 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 *
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(), Instruction::number_of_instructions(), NULL),
57 _access_indexed_info(Instruction::number_of_instructions(), 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(
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.at(v->id())) {
307 // First (default) bound is calculated
308 // Create BoundStack
309 _bounds.at_put(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.at(v->id())->push(bound);
316 }
317 if (_bounds.at(v->id())->length() == 0) {
318 assert(!(v->as_Constant() && v->type()->as_IntConstant()), "constants not handled here");
319 _bounds.at(v->id())->push(new Bound());
320 }
321 } else if (_bounds.at(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.at(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.at(v->id())) {
357 get_bound(v);
358 assert(_bounds.at(v->id()), "Now Stack must exist");
359 }
360 Bound *top = NULL;
361 if (_bounds.at(v->id())->length() > 0) {
362 top = _bounds.at(v->id())->top();
363 }
364 if (top) {
365 bound->and_op(top);
366 }
367 _bounds.at(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.at(id);
375 if (aii == NULL) {
376 aii = new AccessIndexedInfo();
377 _access_indexed_info.at_put(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
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.at(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;
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.at_put(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
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.at(pushed.at(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 );
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(), 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 }
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.at_put(i, false);
1151 }
1152 _current.trunc_to(0);
1153 _successors.trunc_to(0);
1154 if (start != dont_use) {
1155 _current.push(start);
1156 _used.at_put(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.at(i);
1184 assert(sux != NULL, "Successor must not be NULL!");
1185 if (sux == end) {
1186 return true;
1187 }
1188 if (sux != dont_use && !_used.at(sux->block_id())) {
1189 _used.at_put(sux->block_id(), true);
1190 _current.push(sux);
1191 }
1192 }
1193 _successors.trunc_to(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) {
|