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