|
8860
|
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
|
