Mercurial > hg > truffle
comparison src/share/vm/c1/c1_RangeCheckElimination.cpp @ 8860:46f6f063b272
7153771: array bound check elimination for c1
Summary: when possible optimize out array bound checks, inserting predicates when needed.
Reviewed-by: never, kvn, twisti
Contributed-by: thomaswue <thomas.wuerthinger@oracle.com>
author | roland |
---|---|
date | Thu, 21 Mar 2013 09:27:54 +0100 |
parents | |
children | d595e8ddadd9 |
comparison
equal
deleted
inserted
replaced
8780:98f3af397705 | 8860:46f6f063b272 |
---|---|
1 /* | |
2 * Copyright (c) 2012, 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->print_cr(""); | |
66 tty->print_cr("Range check elimination"); | |
67 ir->method()->print_name(tty); | |
68 tty->print_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 _access_indexed_info[index_instruction->id()] = NULL; | |
535 } | |
536 indices.clear(); | |
537 | |
538 if (list_constant.length() > 1) { | |
539 AccessIndexed *first = list_constant.at(0); | |
540 Instruction *insert_position = first->prev(); | |
541 ValueStack *state = first->state_before(); | |
542 // Load max Constant | |
543 Constant *constant = new Constant(new IntConstant(max_constant)); | |
544 NOT_PRODUCT(constant->set_printable_bci(first->printable_bci())); | |
545 insert_position = insert_position->insert_after(constant); | |
546 Instruction *compare_instr = constant; | |
547 Value length_instr = first->length(); | |
548 if (!length_instr) { | |
549 ArrayLength *length = new ArrayLength(array, state->copy()); | |
550 length->set_exception_state(length->state_before()); | |
551 length->set_flag(Instruction::DeoptimizeOnException, true); | |
552 insert_position = insert_position->insert_after_same_bci(length); | |
553 length_instr = length; | |
554 } | |
555 // Compare for greater or equal to array length | |
556 insert_position = predicate(compare_instr, Instruction::geq, length_instr, state, insert_position); | |
557 for (int j = 0; j<list_constant.length(); j++) { | |
558 AccessIndexed *ai = list_constant.at(j); | |
559 remove_range_check(ai); | |
560 } | |
561 } | |
562 } | |
563 } | |
564 } | |
565 | |
566 bool RangeCheckEliminator::set_process_block_flags(BlockBegin *block) { | |
567 Instruction *cur = block; | |
568 bool process = false; | |
569 | |
570 while (cur) { | |
571 process |= (cur->as_AccessIndexed() != NULL); | |
572 cur = cur->next(); | |
573 } | |
574 | |
575 BlockList *dominates = block->dominates(); | |
576 for (int i=0; i<dominates->length(); i++) { | |
577 BlockBegin *next = dominates->at(i); | |
578 process |= set_process_block_flags(next); | |
579 } | |
580 | |
581 if (!process) { | |
582 block->set(BlockBegin::donot_eliminate_range_checks); | |
583 } | |
584 return process; | |
585 } | |
586 | |
587 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) { | |
588 bool upper_check = true; | |
589 assert(lower_instr || lower >= 0, "If no lower_instr present, lower must be greater 0"); | |
590 assert(!lower_instr || lower_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller"); | |
591 assert(!upper_instr || upper_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller"); | |
592 assert(array_instr, "Array instruction must exist"); | |
593 assert(array_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller"); | |
594 assert(!length_instr || length_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller"); | |
595 | |
596 if (upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr) { | |
597 // static check | |
598 if (upper >= 0) return false; // would always trigger a deopt: | |
599 // array_length + x >= array_length, x >= 0 is always true | |
600 upper_check = false; | |
601 } | |
602 if (lower_instr && lower_instr->as_ArrayLength() && lower_instr->as_ArrayLength()->array() == array_instr) { | |
603 if (lower > 0) return false; | |
604 } | |
605 // No upper check required -> skip | |
606 if (upper_check && upper_instr && upper_instr->type()->as_ObjectType() && upper_instr == array_instr) { | |
607 // upper_instr is object means that the upper bound is the length | |
608 // of the upper_instr. | |
609 return false; | |
610 } | |
611 return true; | |
612 } | |
613 | |
614 Instruction* RangeCheckEliminator::insert_after(Instruction* insert_position, Instruction* instr, int bci) { | |
615 if (bci != -1) { | |
616 NOT_PRODUCT(instr->set_printable_bci(bci)); | |
617 return insert_position->insert_after(instr); | |
618 } else { | |
619 return insert_position->insert_after_same_bci(instr); | |
620 } | |
621 } | |
622 | |
623 Instruction* RangeCheckEliminator::predicate(Instruction* left, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) { | |
624 RangeCheckPredicate *deoptimize = new RangeCheckPredicate(left, cond, true, right, state->copy()); | |
625 return insert_after(insert_position, deoptimize, bci); | |
626 } | |
627 | |
628 Instruction* RangeCheckEliminator::predicate_cmp_with_const(Instruction* instr, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) { | |
629 Constant *const_instr = new Constant(new IntConstant(constant)); | |
630 insert_position = insert_after(insert_position, const_instr, bci); | |
631 return predicate(instr, cond, const_instr, state, insert_position); | |
632 } | |
633 | |
634 Instruction* RangeCheckEliminator::predicate_add(Instruction* left, int left_const, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) { | |
635 Constant *constant = new Constant(new IntConstant(left_const)); | |
636 insert_position = insert_after(insert_position, constant, bci); | |
637 ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, left, false, NULL); | |
638 insert_position = insert_position->insert_after_same_bci(ao); | |
639 return predicate(ao, cond, right, state, insert_position); | |
640 } | |
641 | |
642 Instruction* RangeCheckEliminator::predicate_add_cmp_with_const(Instruction* left, int left_const, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) { | |
643 Constant *const_instr = new Constant(new IntConstant(constant)); | |
644 insert_position = insert_after(insert_position, const_instr, bci); | |
645 return predicate_add(left, left_const, cond, const_instr, state, insert_position); | |
646 } | |
647 | |
648 // Insert deoptimization, returns true if sucessful or false if range check should not be removed | |
649 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) { | |
650 assert(is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, lower, upper_instr, upper), "should have been tested before"); | |
651 bool upper_check = !(upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr); | |
652 | |
653 int bci = NOT_PRODUCT(ai->printable_bci()) PRODUCT_ONLY(-1); | |
654 if (lower_instr) { | |
655 assert(!lower_instr->type()->as_ObjectType(), "Must not be object type"); | |
656 if (lower == 0) { | |
657 // Compare for less than 0 | |
658 insert_position = predicate_cmp_with_const(lower_instr, Instruction::lss, 0, state, insert_position, bci); | |
659 } else if (lower > 0) { | |
660 // Compare for smaller 0 | |
661 insert_position = predicate_add_cmp_with_const(lower_instr, lower, Instruction::lss, 0, state, insert_position, bci); | |
662 } else { | |
663 assert(lower < 0, ""); | |
664 // Add 1 | |
665 lower++; | |
666 lower = -lower; | |
667 // Compare for smaller or equal 0 | |
668 insert_position = predicate_cmp_with_const(lower_instr, Instruction::leq, lower, state, insert_position, bci); | |
669 } | |
670 } | |
671 | |
672 // We need to know length of array | |
673 if (!length_instr) { | |
674 // Load length if necessary | |
675 ArrayLength *length = new ArrayLength(array_instr, state->copy()); | |
676 NOT_PRODUCT(length->set_printable_bci(ai->printable_bci())); | |
677 length->set_exception_state(length->state_before()); | |
678 length->set_flag(Instruction::DeoptimizeOnException, true); | |
679 insert_position = insert_position->insert_after(length); | |
680 length_instr = length; | |
681 } | |
682 | |
683 // No upper check required -> skip | |
684 if (!upper_check) return; | |
685 | |
686 if (!upper_instr) { | |
687 // Compare for geq array.length | |
688 insert_position = predicate_cmp_with_const(length_instr, Instruction::leq, upper, state, insert_position, bci); | |
689 } else { | |
690 if (upper_instr->type()->as_ObjectType()) { | |
691 assert(state, "must not be null"); | |
692 assert(upper_instr != array_instr, "should be"); | |
693 ArrayLength *length = new ArrayLength(upper_instr, state->copy()); | |
694 NOT_PRODUCT(length->set_printable_bci(ai->printable_bci())); | |
695 length->set_flag(Instruction::DeoptimizeOnException, true); | |
696 length->set_exception_state(length->state_before()); | |
697 insert_position = insert_position->insert_after(length); | |
698 upper_instr = length; | |
699 } | |
700 assert(upper_instr->type()->as_IntType(), "Must not be object type!"); | |
701 | |
702 if (upper == 0) { | |
703 // Compare for geq array.length | |
704 insert_position = predicate(upper_instr, Instruction::geq, length_instr, state, insert_position, bci); | |
705 } else if (upper < 0) { | |
706 // Compare for geq array.length | |
707 insert_position = predicate_add(upper_instr, upper, Instruction::geq, length_instr, state, insert_position, bci); | |
708 } else { | |
709 assert(upper > 0, ""); | |
710 upper = -upper; | |
711 // Compare for geq array.length | |
712 insert_position = predicate_add(length_instr, upper, Instruction::leq, upper_instr, state, insert_position, bci); | |
713 } | |
714 } | |
715 } | |
716 | |
717 // Add if condition | |
718 void RangeCheckEliminator::add_if_condition(IntegerStack &pushed, Value x, Value y, Instruction::Condition condition) { | |
719 if (y->as_Constant()) return; | |
720 | |
721 int const_value = 0; | |
722 Value instr_value = x; | |
723 Constant *c = x->as_Constant(); | |
724 ArithmeticOp *ao = x->as_ArithmeticOp(); | |
725 | |
726 if (c != NULL) { | |
727 const_value = c->type()->as_IntConstant()->value(); | |
728 instr_value = NULL; | |
729 } else if (ao != NULL && (!ao->x()->as_Constant() || !ao->y()->as_Constant()) && ((ao->op() == Bytecodes::_isub && ao->y()->as_Constant()) || ao->op() == Bytecodes::_iadd)) { | |
730 assert(!ao->x()->as_Constant() || !ao->y()->as_Constant(), "At least one operator must be non-constant!"); | |
731 assert(ao->op() == Bytecodes::_isub || ao->op() == Bytecodes::_iadd, "Operation has to be add or sub!"); | |
732 c = ao->x()->as_Constant(); | |
733 if (c != NULL) { | |
734 const_value = c->type()->as_IntConstant()->value(); | |
735 instr_value = ao->y(); | |
736 } else { | |
737 c = ao->y()->as_Constant(); | |
738 if (c != NULL) { | |
739 const_value = c->type()->as_IntConstant()->value(); | |
740 instr_value = ao->x(); | |
741 } | |
742 } | |
743 if (ao->op() == Bytecodes::_isub) { | |
744 assert(ao->y()->as_Constant(), "1 - x not supported, only x - 1 is valid!"); | |
745 if (const_value > min_jint) { | |
746 const_value = -const_value; | |
747 } else { | |
748 const_value = 0; | |
749 instr_value = x; | |
750 } | |
751 } | |
752 } | |
753 | |
754 update_bound(pushed, y, condition, instr_value, const_value); | |
755 } | |
756 | |
757 // Process If | |
758 void RangeCheckEliminator::process_if(IntegerStack &pushed, BlockBegin *block, If *cond) { | |
759 // Only if we are direct true / false successor and NOT both ! (even this may occur) | |
760 if ((cond->tsux() == block || cond->fsux() == block) && cond->tsux() != cond->fsux()) { | |
761 Instruction::Condition condition = cond->cond(); | |
762 if (cond->fsux() == block) { | |
763 condition = Instruction::negate(condition); | |
764 } | |
765 Value x = cond->x(); | |
766 Value y = cond->y(); | |
767 if (x->type()->as_IntType() && y->type()->as_IntType()) { | |
768 add_if_condition(pushed, y, x, condition); | |
769 add_if_condition(pushed, x, y, Instruction::mirror(condition)); | |
770 } | |
771 } | |
772 } | |
773 | |
774 // Process access indexed | |
775 void RangeCheckEliminator::process_access_indexed(BlockBegin *loop_header, BlockBegin *block, AccessIndexed *ai) { | |
776 TRACE_RANGE_CHECK_ELIMINATION( | |
777 tty->fill_to(block->dominator_depth()*2) | |
778 ); | |
779 TRACE_RANGE_CHECK_ELIMINATION( | |
780 tty->print_cr("Access indexed: index=%d length=%d", ai->index()->id(), ai->length()->id()) | |
781 ); | |
782 | |
783 if (ai->check_flag(Instruction::NeedsRangeCheckFlag)) { | |
784 Bound *index_bound = get_bound(ai->index()); | |
785 if (!index_bound->has_lower() || !index_bound->has_upper()) { | |
786 TRACE_RANGE_CHECK_ELIMINATION( | |
787 tty->fill_to(block->dominator_depth()*2); | |
788 tty->print_cr("Index instruction %d has no lower and/or no upper bound!", ai->index()->id()) | |
789 ); | |
790 return; | |
791 } | |
792 | |
793 Bound *array_bound; | |
794 if (ai->length()) { | |
795 array_bound = get_bound(ai->length()); | |
796 } else { | |
797 array_bound = get_bound(ai->array()); | |
798 } | |
799 | |
800 if (in_array_bound(index_bound, ai->array()) || | |
801 (index_bound && array_bound && index_bound->is_smaller(array_bound) && !index_bound->lower_instr() && index_bound->lower() >= 0)) { | |
802 TRACE_RANGE_CHECK_ELIMINATION( | |
803 tty->fill_to(block->dominator_depth()*2); | |
804 tty->print_cr("Bounds check for instruction %d in block B%d can be fully eliminated!", ai->id(), ai->block()->block_id()) | |
805 ); | |
806 | |
807 remove_range_check(ai); | |
808 } else if (_optimistic && loop_header) { | |
809 assert(ai->array(), "Array must not be null!"); | |
810 assert(ai->index(), "Index must not be null!"); | |
811 | |
812 // Array instruction | |
813 Instruction *array_instr = ai->array(); | |
814 if (!loop_invariant(loop_header, array_instr)) { | |
815 TRACE_RANGE_CHECK_ELIMINATION( | |
816 tty->fill_to(block->dominator_depth()*2); | |
817 tty->print_cr("Array %d is not loop invariant to header B%d", ai->array()->id(), loop_header->block_id()) | |
818 ); | |
819 return; | |
820 } | |
821 | |
822 // Lower instruction | |
823 Value index_instr = ai->index(); | |
824 Value lower_instr = index_bound->lower_instr(); | |
825 if (!loop_invariant(loop_header, lower_instr)) { | |
826 TRACE_RANGE_CHECK_ELIMINATION( | |
827 tty->fill_to(block->dominator_depth()*2); | |
828 tty->print_cr("Lower instruction %d not loop invariant!", lower_instr->id()) | |
829 ); | |
830 return; | |
831 } | |
832 if (!lower_instr && index_bound->lower() < 0) { | |
833 TRACE_RANGE_CHECK_ELIMINATION( | |
834 tty->fill_to(block->dominator_depth()*2); | |
835 tty->print_cr("Lower bound smaller than 0 (%d)!", index_bound->lower()) | |
836 ); | |
837 return; | |
838 } | |
839 | |
840 // Upper instruction | |
841 Value upper_instr = index_bound->upper_instr(); | |
842 if (!loop_invariant(loop_header, upper_instr)) { | |
843 TRACE_RANGE_CHECK_ELIMINATION( | |
844 tty->fill_to(block->dominator_depth()*2); | |
845 tty->print_cr("Upper instruction %d not loop invariant!", upper_instr->id()) | |
846 ); | |
847 return; | |
848 } | |
849 | |
850 // Length instruction | |
851 Value length_instr = ai->length(); | |
852 if (!loop_invariant(loop_header, length_instr)) { | |
853 // Generate length instruction yourself! | |
854 length_instr = NULL; | |
855 } | |
856 | |
857 TRACE_RANGE_CHECK_ELIMINATION( | |
858 tty->fill_to(block->dominator_depth()*2); | |
859 tty->print_cr("LOOP INVARIANT access indexed %d found in block B%d!", ai->id(), ai->block()->block_id()) | |
860 ); | |
861 | |
862 BlockBegin *pred_block = loop_header->dominator(); | |
863 assert(pred_block != NULL, "Every loop header has a dominator!"); | |
864 BlockEnd *pred_block_end = pred_block->end(); | |
865 Instruction *insert_position = pred_block_end->prev(); | |
866 ValueStack *state = pred_block_end->state_before(); | |
867 if (pred_block_end->as_Goto() && state == NULL) state = pred_block_end->state(); | |
868 assert(state, "State must not be null"); | |
869 | |
870 // Add deoptimization to dominator of loop header | |
871 TRACE_RANGE_CHECK_ELIMINATION( | |
872 tty->fill_to(block->dominator_depth()*2); | |
873 tty->print_cr("Inserting deopt at bci %d in block B%d!", state->bci(), insert_position->block()->block_id()) | |
874 ); | |
875 | |
876 if (!is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper())) { | |
877 TRACE_RANGE_CHECK_ELIMINATION( | |
878 tty->fill_to(block->dominator_depth()*2); | |
879 tty->print_cr("Could not eliminate because of static analysis!") | |
880 ); | |
881 return; | |
882 } | |
883 | |
884 insert_deoptimization(state, insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper(), ai); | |
885 | |
886 // Finally remove the range check! | |
887 remove_range_check(ai); | |
888 } | |
889 } | |
890 } | |
891 | |
892 void RangeCheckEliminator::remove_range_check(AccessIndexed *ai) { | |
893 ai->set_flag(Instruction::NeedsRangeCheckFlag, false); | |
894 // no range check, no need for the length instruction anymore | |
895 ai->clear_length(); | |
896 | |
897 TRACE_RANGE_CHECK_ELIMINATION( | |
898 tty->fill_to(ai->dominator_depth()*2); | |
899 tty->print_cr("Range check for instruction %d eliminated!", ai->id()); | |
900 ); | |
901 | |
902 ASSERT_RANGE_CHECK_ELIMINATION( | |
903 Value array_length = ai->length(); | |
904 if (!array_length) { | |
905 array_length = ai->array(); | |
906 assert(array_length->type()->as_ObjectType(), "Has to be object type!"); | |
907 } | |
908 int cur_constant = -1; | |
909 Value cur_value = array_length; | |
910 if (cur_value->type()->as_IntConstant()) { | |
911 cur_constant += cur_value->type()->as_IntConstant()->value(); | |
912 cur_value = NULL; | |
913 } | |
914 Bound *new_index_bound = new Bound(0, NULL, cur_constant, cur_value); | |
915 add_assertions(new_index_bound, ai->index(), ai); | |
916 ); | |
917 } | |
918 | |
919 // Calculate bounds for instruction in this block and children blocks in the dominator tree | |
920 void RangeCheckEliminator::calc_bounds(BlockBegin *block, BlockBegin *loop_header) { | |
921 // Ensures a valid loop_header | |
922 assert(!loop_header || loop_header->is_set(BlockBegin::linear_scan_loop_header_flag), "Loop header has to be real !"); | |
923 | |
924 // Tracing output | |
925 TRACE_RANGE_CHECK_ELIMINATION( | |
926 tty->fill_to(block->dominator_depth()*2); | |
927 tty->print_cr("Block B%d", block->block_id()); | |
928 ); | |
929 | |
930 // Pushed stack for conditions | |
931 IntegerStack pushed; | |
932 // Process If | |
933 BlockBegin *parent = block->dominator(); | |
934 if (parent != NULL) { | |
935 If *cond = parent->end()->as_If(); | |
936 if (cond != NULL) { | |
937 process_if(pushed, block, cond); | |
938 } | |
939 } | |
940 | |
941 // Interate over current block | |
942 InstructionList arrays; | |
943 AccessIndexedList accessIndexed; | |
944 Instruction *cur = block; | |
945 | |
946 while (cur) { | |
947 // Ensure cur wasn't inserted during the elimination | |
948 if (cur->id() < this->_bounds.length()) { | |
949 // Process only if it is an access indexed instruction | |
950 AccessIndexed *ai = cur->as_AccessIndexed(); | |
951 if (ai != NULL) { | |
952 process_access_indexed(loop_header, block, ai); | |
953 accessIndexed.append(ai); | |
954 if (!arrays.contains(ai->array())) { | |
955 arrays.append(ai->array()); | |
956 } | |
957 Bound *b = get_bound(ai->index()); | |
958 if (!b->lower_instr()) { | |
959 // Lower bound is constant | |
960 update_bound(pushed, ai->index(), Instruction::geq, NULL, 0); | |
961 } | |
962 if (!b->has_upper()) { | |
963 if (ai->length() && ai->length()->type()->as_IntConstant()) { | |
964 int value = ai->length()->type()->as_IntConstant()->value(); | |
965 update_bound(pushed, ai->index(), Instruction::lss, NULL, value); | |
966 } else { | |
967 // Has no upper bound | |
968 Instruction *instr = ai->length(); | |
969 if (instr != NULL) instr = ai->array(); | |
970 update_bound(pushed, ai->index(), Instruction::lss, instr, 0); | |
971 } | |
972 } | |
973 } | |
974 } | |
975 cur = cur->next(); | |
976 } | |
977 | |
978 // Output current condition stack | |
979 TRACE_RANGE_CHECK_ELIMINATION(dump_condition_stack(block)); | |
980 | |
981 // Do in block motion of range checks | |
982 in_block_motion(block, accessIndexed, arrays); | |
983 | |
984 // Call all dominated blocks | |
985 for (int i=0; i<block->dominates()->length(); i++) { | |
986 BlockBegin *next = block->dominates()->at(i); | |
987 if (!next->is_set(BlockBegin::donot_eliminate_range_checks)) { | |
988 // if current block is a loop header and: | |
989 // - next block belongs to the same loop | |
990 // or | |
991 // - next block belongs to an inner loop | |
992 // then current block is the loop header for next block | |
993 if (block->is_set(BlockBegin::linear_scan_loop_header_flag) && (block->loop_index() == next->loop_index() || next->loop_depth() > block->loop_depth())) { | |
994 calc_bounds(next, block); | |
995 } else { | |
996 calc_bounds(next, loop_header); | |
997 } | |
998 } | |
999 } | |
1000 | |
1001 // Reset stack | |
1002 for (int i=0; i<pushed.length(); i++) { | |
1003 _bounds[pushed[i]]->pop(); | |
1004 } | |
1005 } | |
1006 | |
1007 #ifndef PRODUCT | |
1008 // Dump condition stack | |
1009 void RangeCheckEliminator::dump_condition_stack(BlockBegin *block) { | |
1010 for (int i=0; i<_ir->linear_scan_order()->length(); i++) { | |
1011 BlockBegin *cur_block = _ir->linear_scan_order()->at(i); | |
1012 Instruction *instr = cur_block; | |
1013 for_each_phi_fun(cur_block, phi, | |
1014 BoundStack *bound_stack = _bounds.at(phi->id()); | |
1015 if (bound_stack && bound_stack->length() > 0) { | |
1016 Bound *bound = bound_stack->top(); | |
1017 if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != phi || bound->upper_instr() != phi || bound->lower() != 0 || bound->upper() != 0)) { | |
1018 TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth()); | |
1019 tty->print("i%d", phi->id()); | |
1020 tty->print(": "); | |
1021 bound->print(); | |
1022 tty->print_cr(""); | |
1023 ); | |
1024 } | |
1025 }); | |
1026 | |
1027 while (!instr->as_BlockEnd()) { | |
1028 if (instr->id() < _bounds.length()) { | |
1029 BoundStack *bound_stack = _bounds.at(instr->id()); | |
1030 if (bound_stack && bound_stack->length() > 0) { | |
1031 Bound *bound = bound_stack->top(); | |
1032 if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != instr || bound->upper_instr() != instr || bound->lower() != 0 || bound->upper() != 0)) { | |
1033 TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth()); | |
1034 tty->print("i%d", instr->id()); | |
1035 tty->print(": "); | |
1036 bound->print(); | |
1037 tty->print_cr(""); | |
1038 ); | |
1039 } | |
1040 } | |
1041 } | |
1042 instr = instr->next(); | |
1043 } | |
1044 } | |
1045 } | |
1046 #endif | |
1047 | |
1048 // Verification or the IR | |
1049 RangeCheckEliminator::Verification::Verification(IR *ir) : _used(BlockBegin::number_of_blocks(), false) { | |
1050 this->_ir = ir; | |
1051 ir->iterate_linear_scan_order(this); | |
1052 } | |
1053 | |
1054 // Verify this block | |
1055 void RangeCheckEliminator::Verification::block_do(BlockBegin *block) { | |
1056 If *cond = block->end()->as_If(); | |
1057 // Watch out: tsux and fsux can be the same! | |
1058 if (block->number_of_sux() > 1) { | |
1059 for (int i=0; i<block->number_of_sux(); i++) { | |
1060 BlockBegin *sux = block->sux_at(i); | |
1061 BlockBegin *pred = NULL; | |
1062 for (int j=0; j<sux->number_of_preds(); j++) { | |
1063 BlockBegin *cur = sux->pred_at(j); | |
1064 assert(cur != NULL, "Predecessor must not be null"); | |
1065 if (!pred) { | |
1066 pred = cur; | |
1067 } | |
1068 assert(cur == pred, "Block must not have more than one predecessor if its predecessor has more than one successor"); | |
1069 } | |
1070 assert(sux->number_of_preds() >= 1, "Block must have at least one predecessor"); | |
1071 assert(sux->pred_at(0) == block, "Wrong successor"); | |
1072 } | |
1073 } | |
1074 | |
1075 BlockBegin *dominator = block->dominator(); | |
1076 if (dominator) { | |
1077 assert(block != _ir->start(), "Start block must not have a dominator!"); | |
1078 assert(can_reach(dominator, block), "Dominator can't reach his block !"); | |
1079 assert(can_reach(_ir->start(), dominator), "Dominator is unreachable !"); | |
1080 assert(!can_reach(_ir->start(), block, dominator), "Wrong dominator ! Block can be reached anyway !"); | |
1081 BlockList *all_blocks = _ir->linear_scan_order(); | |
1082 for (int i=0; i<all_blocks->length(); i++) { | |
1083 BlockBegin *cur = all_blocks->at(i); | |
1084 if (cur != dominator && cur != block) { | |
1085 assert(can_reach(dominator, block, cur), "There has to be another dominator!"); | |
1086 } | |
1087 } | |
1088 } else { | |
1089 assert(block == _ir->start(), "Only start block must not have a dominator"); | |
1090 } | |
1091 | |
1092 if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) { | |
1093 int loop_index = block->loop_index(); | |
1094 BlockList *all_blocks = _ir->linear_scan_order(); | |
1095 assert(block->number_of_preds() >= 1, "Block must have at least one predecessor"); | |
1096 assert(!block->is_set(BlockBegin::exception_entry_flag), "Loop header must not be exception handler!"); | |
1097 // Sometimes, the backbranch comes from an exception handler. In | |
1098 // this case, loop indexes/loop depths may not appear correct. | |
1099 bool loop_through_xhandler = false; | |
1100 for (int i = 0; i < block->number_of_exception_handlers(); i++) { | |
1101 BlockBegin *xhandler = block->exception_handler_at(i); | |
1102 for (int j = 0; j < block->number_of_preds(); j++) { | |
1103 if (dominates(xhandler, block->pred_at(j)) || xhandler == block->pred_at(j)) { | |
1104 loop_through_xhandler = true; | |
1105 } | |
1106 } | |
1107 } | |
1108 | |
1109 for (int i=0; i<block->number_of_sux(); i++) { | |
1110 BlockBegin *sux = block->sux_at(i); | |
1111 assert(sux->loop_depth() != block->loop_depth() || sux->loop_index() == block->loop_index() || loop_through_xhandler, "Loop index has to be same"); | |
1112 assert(sux->loop_depth() == block->loop_depth() || sux->loop_index() != block->loop_index(), "Loop index has to be different"); | |
1113 } | |
1114 | |
1115 for (int i=0; i<all_blocks->length(); i++) { | |
1116 BlockBegin *cur = all_blocks->at(i); | |
1117 if (cur->loop_index() == loop_index && cur != block) { | |
1118 assert(dominates(block->dominator(), cur), "Dominator of loop header must dominate all loop blocks"); | |
1119 } | |
1120 } | |
1121 } | |
1122 | |
1123 Instruction *cur = block; | |
1124 while (cur) { | |
1125 assert(cur->block() == block, "Block begin has to be set correctly!"); | |
1126 cur = cur->next(); | |
1127 } | |
1128 } | |
1129 | |
1130 // Loop header must dominate all loop blocks | |
1131 bool RangeCheckEliminator::Verification::dominates(BlockBegin *dominator, BlockBegin *block) { | |
1132 BlockBegin *cur = block->dominator(); | |
1133 while (cur && cur != dominator) { | |
1134 cur = cur->dominator(); | |
1135 } | |
1136 return cur == dominator; | |
1137 } | |
1138 | |
1139 // Try to reach Block end beginning in Block start and not using Block dont_use | |
1140 bool RangeCheckEliminator::Verification::can_reach(BlockBegin *start, BlockBegin *end, BlockBegin *dont_use /* = NULL */) { | |
1141 if (start == end) return start != dont_use; | |
1142 // Simple BSF from start to end | |
1143 // BlockBeginList _current; | |
1144 for (int i=0; i<_used.length(); i++) { | |
1145 _used[i] = false; | |
1146 } | |
1147 _current.truncate(0); | |
1148 _successors.truncate(0); | |
1149 if (start != dont_use) { | |
1150 _current.push(start); | |
1151 _used[start->block_id()] = true; | |
1152 } | |
1153 | |
1154 // BlockBeginList _successors; | |
1155 while (_current.length() > 0) { | |
1156 BlockBegin *cur = _current.pop(); | |
1157 // Add exception handlers to list | |
1158 for (int i=0; i<cur->number_of_exception_handlers(); i++) { | |
1159 BlockBegin *xhandler = cur->exception_handler_at(i); | |
1160 _successors.push(xhandler); | |
1161 // Add exception handlers of _successors to list | |
1162 for (int j=0; j<xhandler->number_of_exception_handlers(); j++) { | |
1163 BlockBegin *sux_xhandler = xhandler->exception_handler_at(j); | |
1164 _successors.push(sux_xhandler); | |
1165 } | |
1166 } | |
1167 // Add normal _successors to list | |
1168 for (int i=0; i<cur->number_of_sux(); i++) { | |
1169 BlockBegin *sux = cur->sux_at(i); | |
1170 _successors.push(sux); | |
1171 // Add exception handlers of _successors to list | |
1172 for (int j=0; j<sux->number_of_exception_handlers(); j++) { | |
1173 BlockBegin *xhandler = sux->exception_handler_at(j); | |
1174 _successors.push(xhandler); | |
1175 } | |
1176 } | |
1177 for (int i=0; i<_successors.length(); i++) { | |
1178 BlockBegin *sux = _successors[i]; | |
1179 assert(sux != NULL, "Successor must not be NULL!"); | |
1180 if (sux == end) { | |
1181 return true; | |
1182 } | |
1183 if (sux != dont_use && !_used[sux->block_id()]) { | |
1184 _used[sux->block_id()] = true; | |
1185 _current.push(sux); | |
1186 } | |
1187 } | |
1188 _successors.truncate(0); | |
1189 } | |
1190 | |
1191 return false; | |
1192 } | |
1193 | |
1194 // Bound | |
1195 RangeCheckEliminator::Bound::~Bound() { | |
1196 } | |
1197 | |
1198 // Bound constructor | |
1199 RangeCheckEliminator::Bound::Bound() { | |
1200 init(); | |
1201 this->_lower = min_jint; | |
1202 this->_upper = max_jint; | |
1203 this->_lower_instr = NULL; | |
1204 this->_upper_instr = NULL; | |
1205 } | |
1206 | |
1207 // Bound constructor | |
1208 RangeCheckEliminator::Bound::Bound(int lower, Value lower_instr, int upper, Value upper_instr) { | |
1209 init(); | |
1210 assert(!lower_instr || !lower_instr->as_Constant() || !lower_instr->type()->as_IntConstant(), "Must not be constant!"); | |
1211 assert(!upper_instr || !upper_instr->as_Constant() || !upper_instr->type()->as_IntConstant(), "Must not be constant!"); | |
1212 this->_lower = lower; | |
1213 this->_upper = upper; | |
1214 this->_lower_instr = lower_instr; | |
1215 this->_upper_instr = upper_instr; | |
1216 } | |
1217 | |
1218 // Bound constructor | |
1219 RangeCheckEliminator::Bound::Bound(Instruction::Condition cond, Value v, int constant) { | |
1220 assert(!v || (v->type() && (v->type()->as_IntType() || v->type()->as_ObjectType())), "Type must be array or integer!"); | |
1221 assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!"); | |
1222 | |
1223 init(); | |
1224 if (cond == Instruction::eql) { | |
1225 _lower = constant; | |
1226 _lower_instr = v; | |
1227 _upper = constant; | |
1228 _upper_instr = v; | |
1229 } else if (cond == Instruction::neq) { | |
1230 _lower = min_jint; | |
1231 _upper = max_jint; | |
1232 _lower_instr = NULL; | |
1233 _upper_instr = NULL; | |
1234 if (v == NULL) { | |
1235 if (constant == min_jint) { | |
1236 _lower++; | |
1237 } | |
1238 if (constant == max_jint) { | |
1239 _upper--; | |
1240 } | |
1241 } | |
1242 } else if (cond == Instruction::geq) { | |
1243 _lower = constant; | |
1244 _lower_instr = v; | |
1245 _upper = max_jint; | |
1246 _upper_instr = NULL; | |
1247 } else if (cond == Instruction::leq) { | |
1248 _lower = min_jint; | |
1249 _lower_instr = NULL; | |
1250 _upper = constant; | |
1251 _upper_instr = v; | |
1252 } else { | |
1253 ShouldNotReachHere(); | |
1254 } | |
1255 } | |
1256 | |
1257 // Set lower | |
1258 void RangeCheckEliminator::Bound::set_lower(int value, Value v) { | |
1259 assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!"); | |
1260 this->_lower = value; | |
1261 this->_lower_instr = v; | |
1262 } | |
1263 | |
1264 // Set upper | |
1265 void RangeCheckEliminator::Bound::set_upper(int value, Value v) { | |
1266 assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!"); | |
1267 this->_upper = value; | |
1268 this->_upper_instr = v; | |
1269 } | |
1270 | |
1271 // Add constant -> no overflow may occur | |
1272 void RangeCheckEliminator::Bound::add_constant(int value) { | |
1273 this->_lower += value; | |
1274 this->_upper += value; | |
1275 } | |
1276 | |
1277 // Init | |
1278 void RangeCheckEliminator::Bound::init() { | |
1279 } | |
1280 | |
1281 // or | |
1282 void RangeCheckEliminator::Bound::or_op(Bound *b) { | |
1283 // Watch out, bound is not guaranteed not to overflow! | |
1284 // Update lower bound | |
1285 if (_lower_instr != b->_lower_instr || (_lower_instr && _lower != b->_lower)) { | |
1286 _lower_instr = NULL; | |
1287 _lower = min_jint; | |
1288 } else { | |
1289 _lower = MIN2(_lower, b->_lower); | |
1290 } | |
1291 // Update upper bound | |
1292 if (_upper_instr != b->_upper_instr || (_upper_instr && _upper != b->_upper)) { | |
1293 _upper_instr = NULL; | |
1294 _upper = max_jint; | |
1295 } else { | |
1296 _upper = MAX2(_upper, b->_upper); | |
1297 } | |
1298 } | |
1299 | |
1300 // and | |
1301 void RangeCheckEliminator::Bound::and_op(Bound *b) { | |
1302 // Update lower bound | |
1303 if (_lower_instr == b->_lower_instr) { | |
1304 _lower = MAX2(_lower, b->_lower); | |
1305 } | |
1306 if (b->has_lower()) { | |
1307 bool set = true; | |
1308 if (_lower_instr != NULL && b->_lower_instr != NULL) { | |
1309 set = (_lower_instr->dominator_depth() > b->_lower_instr->dominator_depth()); | |
1310 } | |
1311 if (set) { | |
1312 _lower = b->_lower; | |
1313 _lower_instr = b->_lower_instr; | |
1314 } | |
1315 } | |
1316 // Update upper bound | |
1317 if (_upper_instr == b->_upper_instr) { | |
1318 _upper = MIN2(_upper, b->_upper); | |
1319 } | |
1320 if (b->has_upper()) { | |
1321 bool set = true; | |
1322 if (_upper_instr != NULL && b->_upper_instr != NULL) { | |
1323 set = (_upper_instr->dominator_depth() > b->_upper_instr->dominator_depth()); | |
1324 } | |
1325 if (set) { | |
1326 _upper = b->_upper; | |
1327 _upper_instr = b->_upper_instr; | |
1328 } | |
1329 } | |
1330 } | |
1331 | |
1332 // has_upper | |
1333 bool RangeCheckEliminator::Bound::has_upper() { | |
1334 return _upper_instr != NULL || _upper < max_jint; | |
1335 } | |
1336 | |
1337 // is_smaller | |
1338 bool RangeCheckEliminator::Bound::is_smaller(Bound *b) { | |
1339 if (b->_lower_instr != _upper_instr) { | |
1340 return false; | |
1341 } | |
1342 return _upper < b->_lower; | |
1343 } | |
1344 | |
1345 // has_lower | |
1346 bool RangeCheckEliminator::Bound::has_lower() { | |
1347 return _lower_instr != NULL || _lower > min_jint; | |
1348 } | |
1349 | |
1350 // in_array_bound | |
1351 bool RangeCheckEliminator::in_array_bound(Bound *bound, Value array){ | |
1352 if (!bound) return false; | |
1353 assert(array != NULL, "Must not be null!"); | |
1354 assert(bound != NULL, "Must not be null!"); | |
1355 if (bound->lower() >=0 && bound->lower_instr() == NULL && bound->upper() < 0 && bound->upper_instr() != NULL) { | |
1356 ArrayLength *len = bound->upper_instr()->as_ArrayLength(); | |
1357 if (bound->upper_instr() == array || (len != NULL && len->array() == array)) { | |
1358 return true; | |
1359 } | |
1360 } | |
1361 return false; | |
1362 } | |
1363 | |
1364 // remove_lower | |
1365 void RangeCheckEliminator::Bound::remove_lower() { | |
1366 _lower = min_jint; | |
1367 _lower_instr = NULL; | |
1368 } | |
1369 | |
1370 // remove_upper | |
1371 void RangeCheckEliminator::Bound::remove_upper() { | |
1372 _upper = max_jint; | |
1373 _upper_instr = NULL; | |
1374 } | |
1375 | |
1376 // upper | |
1377 int RangeCheckEliminator::Bound::upper() { | |
1378 return _upper; | |
1379 } | |
1380 | |
1381 // lower | |
1382 int RangeCheckEliminator::Bound::lower() { | |
1383 return _lower; | |
1384 } | |
1385 | |
1386 // upper_instr | |
1387 Value RangeCheckEliminator::Bound::upper_instr() { | |
1388 return _upper_instr; | |
1389 } | |
1390 | |
1391 // lower_instr | |
1392 Value RangeCheckEliminator::Bound::lower_instr() { | |
1393 return _lower_instr; | |
1394 } | |
1395 | |
1396 // print | |
1397 void RangeCheckEliminator::Bound::print() { | |
1398 tty->print(""); | |
1399 if (this->_lower_instr || this->_lower != min_jint) { | |
1400 if (this->_lower_instr) { | |
1401 tty->print("i%d", this->_lower_instr->id()); | |
1402 if (this->_lower > 0) { | |
1403 tty->print("+%d", _lower); | |
1404 } | |
1405 if (this->_lower < 0) { | |
1406 tty->print("%d", _lower); | |
1407 } | |
1408 } else { | |
1409 tty->print("%d", _lower); | |
1410 } | |
1411 tty->print(" <= "); | |
1412 } | |
1413 tty->print("x"); | |
1414 if (this->_upper_instr || this->_upper != max_jint) { | |
1415 tty->print(" <= "); | |
1416 if (this->_upper_instr) { | |
1417 tty->print("i%d", this->_upper_instr->id()); | |
1418 if (this->_upper > 0) { | |
1419 tty->print("+%d", _upper); | |
1420 } | |
1421 if (this->_upper < 0) { | |
1422 tty->print("%d", _upper); | |
1423 } | |
1424 } else { | |
1425 tty->print("%d", _upper); | |
1426 } | |
1427 } | |
1428 } | |
1429 | |
1430 // Copy | |
1431 RangeCheckEliminator::Bound *RangeCheckEliminator::Bound::copy() { | |
1432 Bound *b = new Bound(); | |
1433 b->_lower = _lower; | |
1434 b->_lower_instr = _lower_instr; | |
1435 b->_upper = _upper; | |
1436 b->_upper_instr = _upper_instr; | |
1437 return b; | |
1438 } | |
1439 | |
1440 #ifdef ASSERT | |
1441 // Add assertion | |
1442 void RangeCheckEliminator::Bound::add_assertion(Instruction *instruction, Instruction *position, int i, Value instr, Instruction::Condition cond) { | |
1443 Instruction *result = position; | |
1444 Instruction *compare_with = NULL; | |
1445 ValueStack *state = position->state_before(); | |
1446 if (position->as_BlockEnd() && !position->as_Goto()) { | |
1447 state = position->as_BlockEnd()->state_before(); | |
1448 } | |
1449 Instruction *instruction_before = position->prev(); | |
1450 if (position->as_Return() && Compilation::current()->method()->is_synchronized() && instruction_before->as_MonitorExit()) { | |
1451 instruction_before = instruction_before->prev(); | |
1452 } | |
1453 result = instruction_before; | |
1454 // Load constant only if needed | |
1455 Constant *constant = NULL; | |
1456 if (i != 0 || !instr) { | |
1457 constant = new Constant(new IntConstant(i)); | |
1458 NOT_PRODUCT(constant->set_printable_bci(position->printable_bci())); | |
1459 result = result->insert_after(constant); | |
1460 compare_with = constant; | |
1461 } | |
1462 | |
1463 if (instr) { | |
1464 assert(instr->type()->as_ObjectType() || instr->type()->as_IntType(), "Type must be array or integer!"); | |
1465 compare_with = instr; | |
1466 // Load array length if necessary | |
1467 Instruction *op = instr; | |
1468 if (instr->type()->as_ObjectType()) { | |
1469 assert(state, "must not be null"); | |
1470 ArrayLength *length = new ArrayLength(instr, state->copy()); | |
1471 NOT_PRODUCT(length->set_printable_bci(position->printable_bci())); | |
1472 length->set_exception_state(length->state_before()); | |
1473 result = result->insert_after(length); | |
1474 op = length; | |
1475 compare_with = length; | |
1476 } | |
1477 // Add operation only if necessary | |
1478 if (constant) { | |
1479 ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, op, false, NULL); | |
1480 NOT_PRODUCT(ao->set_printable_bci(position->printable_bci())); | |
1481 result = result->insert_after(ao); | |
1482 compare_with = ao; | |
1483 // TODO: Check that add operation does not overflow! | |
1484 } | |
1485 } | |
1486 assert(compare_with != NULL, "You have to compare with something!"); | |
1487 assert(instruction != NULL, "Instruction must not be null!"); | |
1488 | |
1489 if (instruction->type()->as_ObjectType()) { | |
1490 // Load array length if necessary | |
1491 Instruction *op = instruction; | |
1492 assert(state, "must not be null"); | |
1493 ArrayLength *length = new ArrayLength(instruction, state->copy()); | |
1494 length->set_exception_state(length->state_before()); | |
1495 NOT_PRODUCT(length->set_printable_bci(position->printable_bci())); | |
1496 result = result->insert_after(length); | |
1497 instruction = length; | |
1498 } | |
1499 | |
1500 Assert *assert = new Assert(instruction, cond, false, compare_with); | |
1501 NOT_PRODUCT(assert->set_printable_bci(position->printable_bci())); | |
1502 result->insert_after(assert); | |
1503 } | |
1504 | |
1505 // Add assertions | |
1506 void RangeCheckEliminator::add_assertions(Bound *bound, Instruction *instruction, Instruction *position) { | |
1507 // Add lower bound assertion | |
1508 if (bound->has_lower()) { | |
1509 bound->add_assertion(instruction, position, bound->lower(), bound->lower_instr(), Instruction::geq); | |
1510 } | |
1511 // Add upper bound assertion | |
1512 if (bound->has_upper()) { | |
1513 bound->add_assertion(instruction, position, bound->upper(), bound->upper_instr(), Instruction::leq); | |
1514 } | |
1515 } | |
1516 #endif | |
1517 |