Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 1 | /* |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 2 | * Copyright (c) 2012, 2016, Oracle and/or its affiliates. All rights reserved. |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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) : |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 56 | _bounds(Instruction::number_of_instructions(), Instruction::number_of_instructions(), NULL), |
| 57 | _access_indexed_info(Instruction::number_of_instructions(), Instruction::number_of_instructions(), NULL) |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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( |
David Chase | 305ec3b | 2014-05-09 16:50:54 -0400 | [diff] [blame] | 65 | tty->cr(); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 66 | tty->print_cr("Range check elimination"); |
| 67 | ir->method()->print_name(tty); |
David Chase | 305ec3b | 2014-05-09 16:50:54 -0400 | [diff] [blame] | 68 | tty->cr(); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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 | |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 306 | if (!_bounds.at(v->id())) { |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 307 | // First (default) bound is calculated |
| 308 | // Create BoundStack |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 309 | _bounds.at_put(v->id(), new BoundStack()); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 310 | _visitor.clear_bound(); |
| 311 | Value visit_value = v; |
| 312 | visit_value->visit(&_visitor); |
| 313 | Bound *bound = _visitor.bound(); |
| 314 | if (bound) { |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 315 | _bounds.at(v->id())->push(bound); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 316 | } |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 317 | if (_bounds.at(v->id())->length() == 0) { |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 318 | assert(!(v->as_Constant() && v->type()->as_IntConstant()), "constants not handled here"); |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 319 | _bounds.at(v->id())->push(new Bound()); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 320 | } |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 321 | } else if (_bounds.at(v->id())->length() == 0) { |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 322 | // To avoid endless loops, bound is currently in calculation -> nothing known about it |
| 323 | return new Bound(); |
| 324 | } |
| 325 | |
| 326 | // Return bound |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 327 | return _bounds.at(v->id())->top(); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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 | } |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 356 | if (!_bounds.at(v->id())) { |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 357 | get_bound(v); |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 358 | assert(_bounds.at(v->id()), "Now Stack must exist"); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 359 | } |
| 360 | Bound *top = NULL; |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 361 | if (_bounds.at(v->id())->length() > 0) { |
| 362 | top = _bounds.at(v->id())->top(); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 363 | } |
| 364 | if (top) { |
| 365 | bound->and_op(top); |
| 366 | } |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 367 | _bounds.at(v->id())->push(bound); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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(); |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 374 | AccessIndexedInfo *aii = _access_indexed_info.at(id); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 375 | if (aii == NULL) { |
| 376 | aii = new AccessIndexedInfo(); |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 377 | _access_indexed_info.at_put(id, aii); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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) { |
Roland Westrelin | 95ce391 | 2013-04-24 09:42:08 +0200 | [diff] [blame] | 462 | for (int i = 0; i < indices.length(); i++) { |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 463 | Instruction *index_instruction = indices.at(i); |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 464 | AccessIndexedInfo *info = _access_indexed_info.at(index_instruction->id()); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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 | } |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 534 | } |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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 | } |
Roland Westrelin | 95ce391 | 2013-04-24 09:42:08 +0200 | [diff] [blame] | 561 | |
| 562 | // Clear data structures for next array |
| 563 | for (int i = 0; i < indices.length(); i++) { |
| 564 | Instruction *index_instruction = indices.at(i); |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 565 | _access_indexed_info.at_put(index_instruction->id(), NULL); |
Roland Westrelin | 95ce391 | 2013-04-24 09:42:08 +0200 | [diff] [blame] | 566 | } |
| 567 | indices.clear(); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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 | |
Roland Westrelin | 3c586e8 | 2013-03-29 17:25:27 +0100 | [diff] [blame] | 653 | // Insert deoptimization |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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 | |
Roland Westrelin | 3c586e8 | 2013-03-29 17:25:27 +0100 | [diff] [blame] | 677 | // No upper check required -> skip |
| 678 | if (!upper_check) return; |
| 679 | |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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 | |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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( |
Roland Westrelin | 3c586e8 | 2013-03-29 17:25:27 +0100 | [diff] [blame] | 785 | tty->print_cr("Access indexed: index=%d length=%d", ai->index()->id(), (ai->length() != NULL ? ai->length()->id() :-1 )) |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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++) { |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 1008 | _bounds.at(pushed.at(i))->pop(); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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(); |
David Chase | 305ec3b | 2014-05-09 16:50:54 -0400 | [diff] [blame] | 1027 | tty->cr(); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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(); |
David Chase | 305ec3b | 2014-05-09 16:50:54 -0400 | [diff] [blame] | 1042 | tty->cr(); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 1043 | ); |
| 1044 | } |
| 1045 | } |
| 1046 | } |
| 1047 | instr = instr->next(); |
| 1048 | } |
| 1049 | } |
| 1050 | } |
| 1051 | #endif |
| 1052 | |
| 1053 | // Verification or the IR |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 1054 | RangeCheckEliminator::Verification::Verification(IR *ir) : _used(BlockBegin::number_of_blocks(), BlockBegin::number_of_blocks(), false) { |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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; |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 1149 | for (int i=0; i < _used.length(); i++) { |
| 1150 | _used.at_put(i, false); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 1151 | } |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 1152 | _current.trunc_to(0); |
| 1153 | _successors.trunc_to(0); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 1154 | if (start != dont_use) { |
| 1155 | _current.push(start); |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 1156 | _used.at_put(start->block_id(), true); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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++) { |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 1183 | BlockBegin *sux = _successors.at(i); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 1184 | assert(sux != NULL, "Successor must not be NULL!"); |
| 1185 | if (sux == end) { |
| 1186 | return true; |
| 1187 | } |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 1188 | if (sux != dont_use && !_used.at(sux->block_id())) { |
| 1189 | _used.at_put(sux->block_id(), true); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 1190 | _current.push(sux); |
| 1191 | } |
| 1192 | } |
Filipp Zhinkin | 6b6686b | 2016-04-06 18:51:03 +0300 | [diff] [blame] | 1193 | _successors.trunc_to(0); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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() { |
David Chase | 305ec3b | 2014-05-09 16:50:54 -0400 | [diff] [blame] | 1403 | tty->print("%s", ""); |
Thomas Wuerthinger | 06ef4cd | 2013-03-21 09:27:54 +0100 | [diff] [blame] | 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 | |