Mercurial > hg > truffle
annotate src/share/vm/c1/c1_RangeCheckElimination.cpp @ 17467:55fb97c4c58d hs25-b65
8029233: Update copyright year to match last edit in jdk8 hotspot repository for 2013
Summary: Copyright year updated for files modified during 2013
Reviewed-by: twisti, iveresov
| author | mikael |
|---|---|
| date | Tue, 24 Dec 2013 11:48:39 -0800 |
| parents | 6a3629cf7075 |
| children | 4ca6dc0799b6 78bbf4d43a14 |
| rev | line source |
|---|---|
| 8860 | 1 /* |
|
17467
55fb97c4c58d
8029233: Update copyright year to match last edit in jdk8 hotspot repository for 2013
mikael
parents:
10140
diff
changeset
|
2 * Copyright (c) 2012, 2013, 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( | |
| 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) { | |
| 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(); | |
| 1027 tty->print_cr(""); | |
| 1028 ); | |
| 1029 } | |
| 1030 }); | |
| 1031 | |
| 1032 while (!instr->as_BlockEnd()) { | |
| 1033 if (instr->id() < _bounds.length()) { | |
| 1034 BoundStack *bound_stack = _bounds.at(instr->id()); | |
| 1035 if (bound_stack && bound_stack->length() > 0) { | |
| 1036 Bound *bound = bound_stack->top(); | |
| 1037 if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != instr || bound->upper_instr() != instr || bound->lower() != 0 || bound->upper() != 0)) { | |
| 1038 TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth()); | |
| 1039 tty->print("i%d", instr->id()); | |
| 1040 tty->print(": "); | |
| 1041 bound->print(); | |
| 1042 tty->print_cr(""); | |
| 1043 ); | |
| 1044 } | |
| 1045 } | |
| 1046 } | |
| 1047 instr = instr->next(); | |
| 1048 } | |
| 1049 } | |
| 1050 } | |
| 1051 #endif | |
| 1052 | |
| 1053 // Verification or the IR | |
| 1054 RangeCheckEliminator::Verification::Verification(IR *ir) : _used(BlockBegin::number_of_blocks(), false) { | |
| 1055 this->_ir = ir; | |
| 1056 ir->iterate_linear_scan_order(this); | |
| 1057 } | |
| 1058 | |
| 1059 // Verify this block | |
| 1060 void RangeCheckEliminator::Verification::block_do(BlockBegin *block) { | |
| 1061 If *cond = block->end()->as_If(); | |
| 1062 // Watch out: tsux and fsux can be the same! | |
| 1063 if (block->number_of_sux() > 1) { | |
| 1064 for (int i=0; i<block->number_of_sux(); i++) { | |
| 1065 BlockBegin *sux = block->sux_at(i); | |
| 1066 BlockBegin *pred = NULL; | |
| 1067 for (int j=0; j<sux->number_of_preds(); j++) { | |
| 1068 BlockBegin *cur = sux->pred_at(j); | |
| 1069 assert(cur != NULL, "Predecessor must not be null"); | |
| 1070 if (!pred) { | |
| 1071 pred = cur; | |
| 1072 } | |
| 1073 assert(cur == pred, "Block must not have more than one predecessor if its predecessor has more than one successor"); | |
| 1074 } | |
| 1075 assert(sux->number_of_preds() >= 1, "Block must have at least one predecessor"); | |
| 1076 assert(sux->pred_at(0) == block, "Wrong successor"); | |
| 1077 } | |
| 1078 } | |
| 1079 | |
| 1080 BlockBegin *dominator = block->dominator(); | |
| 1081 if (dominator) { | |
| 1082 assert(block != _ir->start(), "Start block must not have a dominator!"); | |
| 1083 assert(can_reach(dominator, block), "Dominator can't reach his block !"); | |
| 1084 assert(can_reach(_ir->start(), dominator), "Dominator is unreachable !"); | |
| 1085 assert(!can_reach(_ir->start(), block, dominator), "Wrong dominator ! Block can be reached anyway !"); | |
| 1086 BlockList *all_blocks = _ir->linear_scan_order(); | |
| 1087 for (int i=0; i<all_blocks->length(); i++) { | |
| 1088 BlockBegin *cur = all_blocks->at(i); | |
| 1089 if (cur != dominator && cur != block) { | |
| 1090 assert(can_reach(dominator, block, cur), "There has to be another dominator!"); | |
| 1091 } | |
| 1092 } | |
| 1093 } else { | |
| 1094 assert(block == _ir->start(), "Only start block must not have a dominator"); | |
| 1095 } | |
| 1096 | |
| 1097 if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) { | |
| 1098 int loop_index = block->loop_index(); | |
| 1099 BlockList *all_blocks = _ir->linear_scan_order(); | |
| 1100 assert(block->number_of_preds() >= 1, "Block must have at least one predecessor"); | |
| 1101 assert(!block->is_set(BlockBegin::exception_entry_flag), "Loop header must not be exception handler!"); | |
| 1102 // Sometimes, the backbranch comes from an exception handler. In | |
| 1103 // this case, loop indexes/loop depths may not appear correct. | |
| 1104 bool loop_through_xhandler = false; | |
| 1105 for (int i = 0; i < block->number_of_exception_handlers(); i++) { | |
| 1106 BlockBegin *xhandler = block->exception_handler_at(i); | |
| 1107 for (int j = 0; j < block->number_of_preds(); j++) { | |
| 1108 if (dominates(xhandler, block->pred_at(j)) || xhandler == block->pred_at(j)) { | |
| 1109 loop_through_xhandler = true; | |
| 1110 } | |
| 1111 } | |
| 1112 } | |
| 1113 | |
| 1114 for (int i=0; i<block->number_of_sux(); i++) { | |
| 1115 BlockBegin *sux = block->sux_at(i); | |
| 1116 assert(sux->loop_depth() != block->loop_depth() || sux->loop_index() == block->loop_index() || loop_through_xhandler, "Loop index has to be same"); | |
| 1117 assert(sux->loop_depth() == block->loop_depth() || sux->loop_index() != block->loop_index(), "Loop index has to be different"); | |
| 1118 } | |
| 1119 | |
| 1120 for (int i=0; i<all_blocks->length(); i++) { | |
| 1121 BlockBegin *cur = all_blocks->at(i); | |
| 1122 if (cur->loop_index() == loop_index && cur != block) { | |
| 1123 assert(dominates(block->dominator(), cur), "Dominator of loop header must dominate all loop blocks"); | |
| 1124 } | |
| 1125 } | |
| 1126 } | |
| 1127 | |
| 1128 Instruction *cur = block; | |
| 1129 while (cur) { | |
| 1130 assert(cur->block() == block, "Block begin has to be set correctly!"); | |
| 1131 cur = cur->next(); | |
| 1132 } | |
| 1133 } | |
| 1134 | |
| 1135 // Loop header must dominate all loop blocks | |
| 1136 bool RangeCheckEliminator::Verification::dominates(BlockBegin *dominator, BlockBegin *block) { | |
| 1137 BlockBegin *cur = block->dominator(); | |
| 1138 while (cur && cur != dominator) { | |
| 1139 cur = cur->dominator(); | |
| 1140 } | |
| 1141 return cur == dominator; | |
| 1142 } | |
| 1143 | |
| 1144 // Try to reach Block end beginning in Block start and not using Block dont_use | |
| 1145 bool RangeCheckEliminator::Verification::can_reach(BlockBegin *start, BlockBegin *end, BlockBegin *dont_use /* = NULL */) { | |
| 1146 if (start == end) return start != dont_use; | |
| 1147 // Simple BSF from start to end | |
| 1148 // BlockBeginList _current; | |
| 1149 for (int i=0; i<_used.length(); i++) { | |
| 1150 _used[i] = false; | |
| 1151 } | |
| 1152 _current.truncate(0); | |
| 1153 _successors.truncate(0); | |
| 1154 if (start != dont_use) { | |
| 1155 _current.push(start); | |
| 1156 _used[start->block_id()] = true; | |
| 1157 } | |
| 1158 | |
| 1159 // BlockBeginList _successors; | |
| 1160 while (_current.length() > 0) { | |
| 1161 BlockBegin *cur = _current.pop(); | |
| 1162 // Add exception handlers to list | |
| 1163 for (int i=0; i<cur->number_of_exception_handlers(); i++) { | |
| 1164 BlockBegin *xhandler = cur->exception_handler_at(i); | |
| 1165 _successors.push(xhandler); | |
| 1166 // Add exception handlers of _successors to list | |
| 1167 for (int j=0; j<xhandler->number_of_exception_handlers(); j++) { | |
| 1168 BlockBegin *sux_xhandler = xhandler->exception_handler_at(j); | |
| 1169 _successors.push(sux_xhandler); | |
| 1170 } | |
| 1171 } | |
| 1172 // Add normal _successors to list | |
| 1173 for (int i=0; i<cur->number_of_sux(); i++) { | |
| 1174 BlockBegin *sux = cur->sux_at(i); | |
| 1175 _successors.push(sux); | |
| 1176 // Add exception handlers of _successors to list | |
| 1177 for (int j=0; j<sux->number_of_exception_handlers(); j++) { | |
| 1178 BlockBegin *xhandler = sux->exception_handler_at(j); | |
| 1179 _successors.push(xhandler); | |
| 1180 } | |
| 1181 } | |
| 1182 for (int i=0; i<_successors.length(); i++) { | |
| 1183 BlockBegin *sux = _successors[i]; | |
| 1184 assert(sux != NULL, "Successor must not be NULL!"); | |
| 1185 if (sux == end) { | |
| 1186 return true; | |
| 1187 } | |
| 1188 if (sux != dont_use && !_used[sux->block_id()]) { | |
| 1189 _used[sux->block_id()] = true; | |
| 1190 _current.push(sux); | |
| 1191 } | |
| 1192 } | |
| 1193 _successors.truncate(0); | |
| 1194 } | |
| 1195 | |
| 1196 return false; | |
| 1197 } | |
| 1198 | |
| 1199 // Bound | |
| 1200 RangeCheckEliminator::Bound::~Bound() { | |
| 1201 } | |
| 1202 | |
| 1203 // Bound constructor | |
| 1204 RangeCheckEliminator::Bound::Bound() { | |
| 1205 init(); | |
| 1206 this->_lower = min_jint; | |
| 1207 this->_upper = max_jint; | |
| 1208 this->_lower_instr = NULL; | |
| 1209 this->_upper_instr = NULL; | |
| 1210 } | |
| 1211 | |
| 1212 // Bound constructor | |
| 1213 RangeCheckEliminator::Bound::Bound(int lower, Value lower_instr, int upper, Value upper_instr) { | |
| 1214 init(); | |
| 1215 assert(!lower_instr || !lower_instr->as_Constant() || !lower_instr->type()->as_IntConstant(), "Must not be constant!"); | |
| 1216 assert(!upper_instr || !upper_instr->as_Constant() || !upper_instr->type()->as_IntConstant(), "Must not be constant!"); | |
| 1217 this->_lower = lower; | |
| 1218 this->_upper = upper; | |
| 1219 this->_lower_instr = lower_instr; | |
| 1220 this->_upper_instr = upper_instr; | |
| 1221 } | |
| 1222 | |
| 1223 // Bound constructor | |
| 1224 RangeCheckEliminator::Bound::Bound(Instruction::Condition cond, Value v, int constant) { | |
| 1225 assert(!v || (v->type() && (v->type()->as_IntType() || v->type()->as_ObjectType())), "Type must be array or integer!"); | |
| 1226 assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!"); | |
| 1227 | |
| 1228 init(); | |
| 1229 if (cond == Instruction::eql) { | |
| 1230 _lower = constant; | |
| 1231 _lower_instr = v; | |
| 1232 _upper = constant; | |
| 1233 _upper_instr = v; | |
| 1234 } else if (cond == Instruction::neq) { | |
| 1235 _lower = min_jint; | |
| 1236 _upper = max_jint; | |
| 1237 _lower_instr = NULL; | |
| 1238 _upper_instr = NULL; | |
| 1239 if (v == NULL) { | |
| 1240 if (constant == min_jint) { | |
| 1241 _lower++; | |
| 1242 } | |
| 1243 if (constant == max_jint) { | |
| 1244 _upper--; | |
| 1245 } | |
| 1246 } | |
| 1247 } else if (cond == Instruction::geq) { | |
| 1248 _lower = constant; | |
| 1249 _lower_instr = v; | |
| 1250 _upper = max_jint; | |
| 1251 _upper_instr = NULL; | |
| 1252 } else if (cond == Instruction::leq) { | |
| 1253 _lower = min_jint; | |
| 1254 _lower_instr = NULL; | |
| 1255 _upper = constant; | |
| 1256 _upper_instr = v; | |
| 1257 } else { | |
| 1258 ShouldNotReachHere(); | |
| 1259 } | |
| 1260 } | |
| 1261 | |
| 1262 // Set lower | |
| 1263 void RangeCheckEliminator::Bound::set_lower(int value, Value v) { | |
| 1264 assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!"); | |
| 1265 this->_lower = value; | |
| 1266 this->_lower_instr = v; | |
| 1267 } | |
| 1268 | |
| 1269 // Set upper | |
| 1270 void RangeCheckEliminator::Bound::set_upper(int value, Value v) { | |
| 1271 assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!"); | |
| 1272 this->_upper = value; | |
| 1273 this->_upper_instr = v; | |
| 1274 } | |
| 1275 | |
| 1276 // Add constant -> no overflow may occur | |
| 1277 void RangeCheckEliminator::Bound::add_constant(int value) { | |
| 1278 this->_lower += value; | |
| 1279 this->_upper += value; | |
| 1280 } | |
| 1281 | |
| 1282 // Init | |
| 1283 void RangeCheckEliminator::Bound::init() { | |
| 1284 } | |
| 1285 | |
| 1286 // or | |
| 1287 void RangeCheckEliminator::Bound::or_op(Bound *b) { | |
| 1288 // Watch out, bound is not guaranteed not to overflow! | |
| 1289 // Update lower bound | |
| 1290 if (_lower_instr != b->_lower_instr || (_lower_instr && _lower != b->_lower)) { | |
| 1291 _lower_instr = NULL; | |
| 1292 _lower = min_jint; | |
| 1293 } else { | |
| 1294 _lower = MIN2(_lower, b->_lower); | |
| 1295 } | |
| 1296 // Update upper bound | |
| 1297 if (_upper_instr != b->_upper_instr || (_upper_instr && _upper != b->_upper)) { | |
| 1298 _upper_instr = NULL; | |
| 1299 _upper = max_jint; | |
| 1300 } else { | |
| 1301 _upper = MAX2(_upper, b->_upper); | |
| 1302 } | |
| 1303 } | |
| 1304 | |
| 1305 // and | |
| 1306 void RangeCheckEliminator::Bound::and_op(Bound *b) { | |
| 1307 // Update lower bound | |
| 1308 if (_lower_instr == b->_lower_instr) { | |
| 1309 _lower = MAX2(_lower, b->_lower); | |
| 1310 } | |
| 1311 if (b->has_lower()) { | |
| 1312 bool set = true; | |
| 1313 if (_lower_instr != NULL && b->_lower_instr != NULL) { | |
| 1314 set = (_lower_instr->dominator_depth() > b->_lower_instr->dominator_depth()); | |
| 1315 } | |
| 1316 if (set) { | |
| 1317 _lower = b->_lower; | |
| 1318 _lower_instr = b->_lower_instr; | |
| 1319 } | |
| 1320 } | |
| 1321 // Update upper bound | |
| 1322 if (_upper_instr == b->_upper_instr) { | |
| 1323 _upper = MIN2(_upper, b->_upper); | |
| 1324 } | |
| 1325 if (b->has_upper()) { | |
| 1326 bool set = true; | |
| 1327 if (_upper_instr != NULL && b->_upper_instr != NULL) { | |
| 1328 set = (_upper_instr->dominator_depth() > b->_upper_instr->dominator_depth()); | |
| 1329 } | |
| 1330 if (set) { | |
| 1331 _upper = b->_upper; | |
| 1332 _upper_instr = b->_upper_instr; | |
| 1333 } | |
| 1334 } | |
| 1335 } | |
| 1336 | |
| 1337 // has_upper | |
| 1338 bool RangeCheckEliminator::Bound::has_upper() { | |
| 1339 return _upper_instr != NULL || _upper < max_jint; | |
| 1340 } | |
| 1341 | |
| 1342 // is_smaller | |
| 1343 bool RangeCheckEliminator::Bound::is_smaller(Bound *b) { | |
| 1344 if (b->_lower_instr != _upper_instr) { | |
| 1345 return false; | |
| 1346 } | |
| 1347 return _upper < b->_lower; | |
| 1348 } | |
| 1349 | |
| 1350 // has_lower | |
| 1351 bool RangeCheckEliminator::Bound::has_lower() { | |
| 1352 return _lower_instr != NULL || _lower > min_jint; | |
| 1353 } | |
| 1354 | |
| 1355 // in_array_bound | |
| 1356 bool RangeCheckEliminator::in_array_bound(Bound *bound, Value array){ | |
| 1357 if (!bound) return false; | |
| 1358 assert(array != NULL, "Must not be null!"); | |
| 1359 assert(bound != NULL, "Must not be null!"); | |
| 1360 if (bound->lower() >=0 && bound->lower_instr() == NULL && bound->upper() < 0 && bound->upper_instr() != NULL) { | |
| 1361 ArrayLength *len = bound->upper_instr()->as_ArrayLength(); | |
| 1362 if (bound->upper_instr() == array || (len != NULL && len->array() == array)) { | |
| 1363 return true; | |
| 1364 } | |
| 1365 } | |
| 1366 return false; | |
| 1367 } | |
| 1368 | |
| 1369 // remove_lower | |
| 1370 void RangeCheckEliminator::Bound::remove_lower() { | |
| 1371 _lower = min_jint; | |
| 1372 _lower_instr = NULL; | |
| 1373 } | |
| 1374 | |
| 1375 // remove_upper | |
| 1376 void RangeCheckEliminator::Bound::remove_upper() { | |
| 1377 _upper = max_jint; | |
| 1378 _upper_instr = NULL; | |
| 1379 } | |
| 1380 | |
| 1381 // upper | |
| 1382 int RangeCheckEliminator::Bound::upper() { | |
| 1383 return _upper; | |
| 1384 } | |
| 1385 | |
| 1386 // lower | |
| 1387 int RangeCheckEliminator::Bound::lower() { | |
| 1388 return _lower; | |
| 1389 } | |
| 1390 | |
| 1391 // upper_instr | |
| 1392 Value RangeCheckEliminator::Bound::upper_instr() { | |
| 1393 return _upper_instr; | |
| 1394 } | |
| 1395 | |
| 1396 // lower_instr | |
| 1397 Value RangeCheckEliminator::Bound::lower_instr() { | |
| 1398 return _lower_instr; | |
| 1399 } | |
| 1400 | |
| 1401 // print | |
| 1402 void RangeCheckEliminator::Bound::print() { | |
| 1403 tty->print(""); | |
| 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 |