jdk

1
/*
2
 * Copyright (c) 2012, 2024, Oracle and/or its affiliates. All rights reserved.
3
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4
 *
5
 * This code is free software; you can redistribute it and/or modify it
6
 * under the terms of the GNU General Public License version 2 only, as
7
 * published by the Free Software Foundation.
8
 *
9
 * This code is distributed in the hope that it will be useful, but WITHOUT
10
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12
 * version 2 for more details (a copy is included in the LICENSE file that
13
 * accompanied this code).
14
 *
15
 * You should have received a copy of the GNU General Public License version
16
 * 2 along with this work; if not, write to the Free Software Foundation,
17
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18
 *
19
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20
 * or visit www.oracle.com if you need additional information or have any
21
 * questions.
22
 *
23
 */
24

25
#include "precompiled.hpp"
26
#include "c1/c1_ValueStack.hpp"
27
#include "c1/c1_RangeCheckElimination.hpp"
28
#include "c1/c1_IR.hpp"
29
#include "c1/c1_Canonicalizer.hpp"
30
#include "c1/c1_ValueMap.hpp"
31
#include "ci/ciMethodData.hpp"
32
#include "runtime/deoptimization.hpp"
33
#ifdef ASSERT
34
#include "utilities/bitMap.inline.hpp"
35
#endif
36

37
// Macros for the Trace and the Assertion flag
38
#ifdef ASSERT
39
#define TRACE_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination) { code; }
40
#define ASSERT_RANGE_CHECK_ELIMINATION(code) if (AssertRangeCheckElimination) { code; }
41
#define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination || AssertRangeCheckElimination) { code; }
42
#else
43
#define TRACE_RANGE_CHECK_ELIMINATION(code)
44
#define ASSERT_RANGE_CHECK_ELIMINATION(code)
45
#define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code)
46
#endif
47

48
// Entry point for the optimization
49
void RangeCheckElimination::eliminate(IR *ir) {
50
  bool do_elimination = ir->compilation()->has_access_indexed();
51
  ASSERT_RANGE_CHECK_ELIMINATION(do_elimination = true);
52
  if (do_elimination) {
53
    RangeCheckEliminator rce(ir);
54
  }
55
}
56

57
// Constructor
58
RangeCheckEliminator::RangeCheckEliminator(IR *ir) :
59
  _bounds(Instruction::number_of_instructions(), Instruction::number_of_instructions(), nullptr),
60
  _access_indexed_info(Instruction::number_of_instructions(), Instruction::number_of_instructions(), nullptr)
61
{
62
  _visitor.set_range_check_eliminator(this);
63
  _ir = ir;
64
  _number_of_instructions = Instruction::number_of_instructions();
65
  _optimistic = ir->compilation()->is_optimistic();
66

67
  TRACE_RANGE_CHECK_ELIMINATION(
68
    tty->cr();
69
    tty->print_cr("Range check elimination");
70
    ir->method()->print_name(tty);
71
    tty->cr();
72
  );
73

74
  TRACE_RANGE_CHECK_ELIMINATION(
75
    tty->print_cr("optimistic=%d", (int)_optimistic);
76
  );
77

78
#ifdef ASSERT
79
  // Verifies several conditions that must be true on the IR-input. Only used for debugging purposes.
80
  TRACE_RANGE_CHECK_ELIMINATION(
81
    tty->print_cr("Verification of IR . . .");
82
  );
83
  Verification verification(ir);
84
#endif
85

86
  // Set process block flags
87
  // Optimization so a blocks is only processed if it contains an access indexed instruction or if
88
  // one of its children in the dominator tree contains an access indexed instruction.
89
  set_process_block_flags(ir->start());
90

91
  // Pass over instructions in the dominator tree
92
  TRACE_RANGE_CHECK_ELIMINATION(
93
    tty->print_cr("Starting pass over dominator tree . . .")
94
  );
95
  calc_bounds(ir->start(), nullptr);
96

97
  TRACE_RANGE_CHECK_ELIMINATION(
98
    tty->print_cr("Finished!")
99
  );
100
}
101

102
// Instruction specific work for some instructions
103
// Constant
104
void RangeCheckEliminator::Visitor::do_Constant(Constant *c) {
105
  IntConstant *ic = c->type()->as_IntConstant();
106
  if (ic != nullptr) {
107
    int value = ic->value();
108
    _bound = new Bound(value, nullptr, value, nullptr);
109
  }
110
}
111

112
// LogicOp
113
void RangeCheckEliminator::Visitor::do_LogicOp(LogicOp *lo) {
114
  if (lo->type()->as_IntType() && lo->op() == Bytecodes::_iand && (lo->x()->as_Constant() || lo->y()->as_Constant())) {
115
    int constant = 0;
116
    Constant *c = lo->x()->as_Constant();
117
    if (c != nullptr) {
118
      constant = c->type()->as_IntConstant()->value();
119
    } else {
120
      constant = lo->y()->as_Constant()->type()->as_IntConstant()->value();
121
    }
122
    if (constant >= 0) {
123
      _bound = new Bound(0, nullptr, constant, nullptr);
124
    }
125
  }
126
}
127

128
// Phi
129
void RangeCheckEliminator::Visitor::do_Phi(Phi *phi) {
130
  if (!phi->type()->as_IntType() && !phi->type()->as_ObjectType()) return;
131

132
  BlockBegin *block = phi->block();
133
  int op_count = phi->operand_count();
134
  bool has_upper = true;
135
  bool has_lower = true;
136
  assert(phi, "Phi must not be null");
137
  Bound* bound = nullptr;
138

139
  // TODO: support more difficult phis
140
  for (int i=0; i<op_count; i++) {
141
    Value v = phi->operand_at(i);
142

143
    if (v == phi) continue;
144

145
    // Check if instruction is connected with phi itself
146
    Op2 *op2 = v->as_Op2();
147
    if (op2 != nullptr) {
148
      Value x = op2->x();
149
      Value y = op2->y();
150
      if ((x == phi || y == phi)) {
151
        Value other = x;
152
        if (other == phi) {
153
          other = y;
154
        }
155
        ArithmeticOp *ao = v->as_ArithmeticOp();
156
        if (ao != nullptr && ao->op() == Bytecodes::_iadd) {
157
          assert(ao->op() == Bytecodes::_iadd, "Has to be add!");
158
          if (ao->type()->as_IntType()) {
159
            Constant *c = other->as_Constant();
160
            if (c != nullptr) {
161
              assert(c->type()->as_IntConstant(), "Constant has to be of type integer");
162
              int value = c->type()->as_IntConstant()->value();
163
              if (value == 1) {
164
                has_upper = false;
165
              } else if (value > 1) {
166
                // Overflow not guaranteed
167
                has_upper = false;
168
                has_lower = false;
169
              } else if (value < 0) {
170
                has_lower = false;
171
              }
172
              continue;
173
            }
174
          }
175
        }
176
      }
177
    }
178

179
    // No connection -> new bound
180
    Bound *v_bound = _rce->get_bound(v);
181
    Bound *cur_bound;
182
    int cur_constant = 0;
183
    Value cur_value = v;
184

185
    if (v->type()->as_IntConstant()) {
186
      cur_constant = v->type()->as_IntConstant()->value();
187
      cur_value = nullptr;
188
    }
189
    if (!v_bound->has_upper() || !v_bound->has_lower()) {
190
      cur_bound = new Bound(cur_constant, cur_value, cur_constant, cur_value);
191
    } else {
192
      cur_bound = v_bound;
193
    }
194
    if (cur_bound) {
195
      if (!bound) {
196
        bound = cur_bound->copy();
197
      } else {
198
        bound->or_op(cur_bound);
199
      }
200
    } else {
201
      // No bound!
202
      bound = nullptr;
203
      break;
204
    }
205
  }
206

207
  if (bound) {
208
    if (!has_upper) {
209
      bound->remove_upper();
210
    }
211
    if (!has_lower) {
212
      bound->remove_lower();
213
    }
214
    _bound = bound;
215
  } else {
216
    _bound = new Bound();
217
  }
218
}
219

220

221
// ArithmeticOp
222
void RangeCheckEliminator::Visitor::do_ArithmeticOp(ArithmeticOp *ao) {
223
  Value x = ao->x();
224
  Value y = ao->y();
225

226
  if (ao->op() == Bytecodes::_irem) {
227
    Bound* x_bound = _rce->get_bound(x);
228
    Bound* y_bound = _rce->get_bound(y);
229
    if (x_bound->lower() >= 0 && x_bound->lower_instr() == nullptr && y->as_ArrayLength() != nullptr) {
230
      _bound = new Bound(0, nullptr, -1, y);
231
    } else if (x_bound->has_lower() && x_bound->lower() >= 0 && y->type()->as_IntConstant() &&
232
               y->type()->as_IntConstant()->value() != 0 && y->type()->as_IntConstant()->value() != min_jint) {
233
      // The binary % operator is said to yield the remainder of its operands from an implied division; the
234
      // left-hand operand is the dividend and the right-hand operand is the divisor.
235
      //
236
      // It follows from this rule that the result of the remainder operation can be negative only
237
      // if the dividend is negative, and can be positive only if the dividend is positive. Moreover, the
238
      // magnitude of the result is always less than the magnitude of the divisor (see JLS 15.17.3).
239
      //
240
      // So if y is a constant integer and not equal to 0, then we can deduce the bound of remainder operation:
241
      // x % -y  ==> [0, y - 1] Apply RCE
242
      // x % y   ==> [0, y - 1] Apply RCE
243
      // -x % y  ==> [-y + 1, 0]
244
      // -x % -y ==> [-y + 1, 0]
245
      //
246
      // Use the absolute value of y as an upper bound. Skip min_jint because abs(min_jint) is undefined.
247
      _bound = new Bound(0, nullptr, abs(y->type()->as_IntConstant()->value()) - 1, nullptr);
248
    } else {
249
      _bound = new Bound();
250
    }
251
  } else if (!x->as_Constant() || !y->as_Constant()) {
252
    assert(!x->as_Constant() || !y->as_Constant(), "One of the operands must be non-constant!");
253
    if (((x->as_Constant() || y->as_Constant()) && (ao->op() == Bytecodes::_iadd)) || (y->as_Constant() && ao->op() == Bytecodes::_isub)) {
254
      assert(ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub, "Operand must be iadd or isub");
255

256
      if (y->as_Constant()) {
257
        Value tmp = x;
258
        x = y;
259
        y = tmp;
260
      }
261
      assert(x->as_Constant()->type()->as_IntConstant(), "Constant must be int constant!");
262

263
      // Constant now in x
264
      int const_value = x->as_Constant()->type()->as_IntConstant()->value();
265
      if (ao->op() == Bytecodes::_iadd || const_value != min_jint) {
266
        if (ao->op() == Bytecodes::_isub) {
267
          const_value = -const_value;
268
        }
269

270
        Bound * bound = _rce->get_bound(y);
271
        if (bound->has_upper() && bound->has_lower()) {
272
          jint t_lo = bound->lower();
273
          jint t_hi = bound->upper();
274
          jint new_lower = java_add(t_lo, const_value);
275
          jint new_upper = java_add(t_hi, const_value);
276
          bool overflow = ((const_value < 0 && (new_lower > t_lo)) ||
277
                           (const_value > 0 && (new_upper < t_hi)));
278
          if (overflow) {
279
            _bound = new Bound();
280
          } else {
281
            _bound = new Bound(new_lower, bound->lower_instr(), new_upper, bound->upper_instr());
282
          }
283
        } else {
284
          _bound = new Bound();
285
        }
286
      } else {
287
        _bound = new Bound();
288
      }
289
    } else {
290
      Bound *bound = _rce->get_bound(x);
291
      if (ao->op() == Bytecodes::_isub) {
292
        if (bound->lower_instr() == y) {
293
          _bound = new Bound(Instruction::geq, nullptr, bound->lower());
294
        } else {
295
          _bound = new Bound();
296
        }
297
      } else {
298
        _bound = new Bound();
299
      }
300
    }
301
  }
302
}
303

304
// IfOp
305
void RangeCheckEliminator::Visitor::do_IfOp(IfOp *ifOp)
306
{
307
  if (ifOp->tval()->type()->as_IntConstant() && ifOp->fval()->type()->as_IntConstant()) {
308
    int min = ifOp->tval()->type()->as_IntConstant()->value();
309
    int max = ifOp->fval()->type()->as_IntConstant()->value();
310
    if (min > max) {
311
      // min ^= max ^= min ^= max;
312
      int tmp = min;
313
      min = max;
314
      max = tmp;
315
    }
316
    _bound = new Bound(min, nullptr, max, nullptr);
317
  }
318
}
319

320
// Get bound. Returns the current bound on Value v. Normally this is the topmost element on the bound stack.
321
RangeCheckEliminator::Bound *RangeCheckEliminator::get_bound(Value v) {
322
  // Wrong type or null -> No bound
323
  if (!v || (!v->type()->as_IntType() && !v->type()->as_ObjectType())) return nullptr;
324

325
  if (!_bounds.at(v->id())) {
326
    // First (default) bound is calculated
327
    // Create BoundStack
328
    _bounds.at_put(v->id(), new BoundStack());
329
    _visitor.clear_bound();
330
    Value visit_value = v;
331
    visit_value->visit(&_visitor);
332
    Bound *bound = _visitor.bound();
333
    if (bound) {
334
      _bounds.at(v->id())->push(bound);
335
    }
336
    if (_bounds.at(v->id())->length() == 0) {
337
      assert(!(v->as_Constant() && v->type()->as_IntConstant()), "constants not handled here");
338
      _bounds.at(v->id())->push(new Bound());
339
    }
340
  } else if (_bounds.at(v->id())->length() == 0) {
341
    // To avoid endless loops, bound is currently in calculation -> nothing known about it
342
    return new Bound();
343
  }
344

345
  // Return bound
346
  return _bounds.at(v->id())->top();
347
}
348

349
// Update bound
350
void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Instruction::Condition cond, Value value, int constant) {
351
  assert(sizeof(constant) == sizeof(jint), "wrong size");
352
  if (cond == Instruction::gtr) {
353
    cond = Instruction::geq;
354
    if (constant == INT_MAX) {
355
      if (value == nullptr) {
356
        // Cannot represent c > INT_MAX, do not update bounds
357
        return;
358
      }
359
      constant = java_add((jint)constant, 1); // Java wrap semantics
360
    } else {
361
      constant++;
362
    }
363
  } else if (cond == Instruction::lss) {
364
    cond = Instruction::leq;
365
    if (constant == INT_MIN) {
366
      if (value == nullptr) {
367
        // Cannot represent c < INT_MIN, do not update bounds
368
        return;
369
      }
370
      constant = java_subtract((jint)constant, 1); // Java wrap semantics
371
    } else {
372
      constant--;
373
    }
374
  }
375
  Bound *bound = new Bound(cond, value, constant);
376
  update_bound(pushed, v, bound);
377
}
378

379
// Checks for loop invariance. Returns true if the instruction is outside of the loop which is identified by loop_header.
380
bool RangeCheckEliminator::loop_invariant(BlockBegin *loop_header, Instruction *instruction) {
381
  assert(loop_header, "Loop header must not be null!");
382
  if (!instruction) return true;
383
  for (BlockBegin* d = loop_header->dominator(); d != nullptr; d = d->dominator()) {
384
    if (d == instruction->block()) {
385
      return true;
386
    }
387
  }
388
  return false;
389
}
390

391
// Update bound. Pushes a new bound onto the stack. Tries to do a conjunction with the current bound.
392
void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Bound *bound) {
393
  if (v->as_Constant()) {
394
    // No bound update for constants
395
    return;
396
  }
397
  if (!_bounds.at(v->id())) {
398
    get_bound(v);
399
    assert(_bounds.at(v->id()), "Now Stack must exist");
400
  }
401
  Bound* top = nullptr;
402
  if (_bounds.at(v->id())->length() > 0) {
403
    top = _bounds.at(v->id())->top();
404
  }
405
  if (top) {
406
    bound->and_op(top);
407
  }
408
  _bounds.at(v->id())->push(bound);
409
  pushed.append(v->id());
410
}
411

412
// Add instruction + idx for in block motion
413
void RangeCheckEliminator::add_access_indexed_info(InstructionList &indices, int idx, Value instruction, AccessIndexed *ai) {
414
  int id = instruction->id();
415
  AccessIndexedInfo *aii = _access_indexed_info.at(id);
416
  if (aii == nullptr) {
417
    aii = new AccessIndexedInfo();
418
    _access_indexed_info.at_put(id, aii);
419
    indices.append(instruction);
420
    aii->_min = idx;
421
    aii->_max = idx;
422
    aii->_list = new AccessIndexedList();
423
  } else if (idx >= aii->_min && idx <= aii->_max) {
424
    // Guard against underflow/overflow (see 'range_cond' check in RangeCheckEliminator::in_block_motion)
425
    if (aii->_max < 0 || (aii->_max + min_jint) <= aii->_min) {
426
      remove_range_check(ai);
427
      return;
428
    }
429
  }
430
  aii->_min = MIN2(aii->_min, idx);
431
  aii->_max = MAX2(aii->_max, idx);
432
  aii->_list->append(ai);
433
}
434

435
// In block motion. Tries to reorder checks in order to reduce some of them.
436
// Example:
437
// a[i] = 0;
438
// a[i+2] = 0;
439
// a[i+1] = 0;
440
// In this example the check for a[i+1] would be considered as unnecessary during the first iteration.
441
// After this i is only checked once for i >= 0 and i+2 < a.length before the first array access. If this
442
// check fails, deoptimization is called.
443
void RangeCheckEliminator::in_block_motion(BlockBegin *block, AccessIndexedList &accessIndexed, InstructionList &arrays) {
444
  InstructionList indices;
445

446
  // Now iterate over all arrays
447
  for (int i=0; i<arrays.length(); i++) {
448
    int max_constant = -1;
449
    AccessIndexedList list_constant;
450
    Value array = arrays.at(i);
451

452
    // For all AccessIndexed-instructions in this block concerning the current array.
453
    for(int j=0; j<accessIndexed.length(); j++) {
454
      AccessIndexed *ai = accessIndexed.at(j);
455
      if (ai->array() != array || !ai->check_flag(Instruction::NeedsRangeCheckFlag)) continue;
456

457
      Value index = ai->index();
458
      Constant *c = index->as_Constant();
459
      if (c != nullptr) {
460
        int constant_value = c->type()->as_IntConstant()->value();
461
        if (constant_value >= 0) {
462
          if (constant_value <= max_constant) {
463
            // No range check needed for this
464
            remove_range_check(ai);
465
          } else {
466
            max_constant = constant_value;
467
            list_constant.append(ai);
468
          }
469
        }
470
      } else {
471
        jint last_integer = 0;
472
        Instruction *last_instruction = index;
473
        jint base = 0;
474
        ArithmeticOp *ao = index->as_ArithmeticOp();
475

476
        while (ao != nullptr && (ao->x()->as_Constant() || ao->y()->as_Constant()) && (ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub)) {
477
          c = ao->y()->as_Constant();
478
          Instruction *other = ao->x();
479
          if (!c && ao->op() == Bytecodes::_iadd) {
480
            c = ao->x()->as_Constant();
481
            other = ao->y();
482
          }
483

484
          if (c) {
485
            jint value = c->type()->as_IntConstant()->value();
486
            if (ao->op() == Bytecodes::_iadd) {
487
              base = java_add(base, value);
488
            } else {
489
              assert(ao->op() == Bytecodes::_isub, "unexpected bytecode");
490
              base = java_subtract(base, value);
491
            }
492
            last_integer = base;
493
            last_instruction = other;
494
            index = other;
495
          } else {
496
            break;
497
          }
498
          ao = index->as_ArithmeticOp();
499
        }
500
        add_access_indexed_info(indices, last_integer, last_instruction, ai);
501
      }
502
    }
503

504
    // Iterate over all different indices
505
    if (_optimistic) {
506
      for (int i = 0; i < indices.length(); i++) {
507
        Instruction *index_instruction = indices.at(i);
508
        AccessIndexedInfo *info = _access_indexed_info.at(index_instruction->id());
509
        assert(info != nullptr, "Info must not be null");
510

511
        // if idx < 0, max > 0, max + idx may fall between 0 and
512
        // length-1 and if min < 0, min + idx may underflow/overflow and be >=
513
        // 0. The predicate wouldn't trigger but some accesses could
514
        // be with a negative index. This test guarantees that for the
515
        // min and max value that are kept the predicate can't let
516
        // some incorrect accesses happen.
517
        bool range_cond = (info->_max < 0 || (info->_max + min_jint) <= info->_min);
518

519
        // Generate code only if more than 2 range checks can be eliminated because of that.
520
        // 2 because at least 2 comparisons are done
521
        if (info->_list->length() > 2 && range_cond) {
522
          AccessIndexed *first = info->_list->at(0);
523
          Instruction *insert_position = first->prev();
524
          assert(insert_position->next() == first, "prev was calculated");
525
          ValueStack *state = first->state_before();
526

527
          // Load min Constant
528
          Constant *min_constant = nullptr;
529
          if (info->_min != 0) {
530
            min_constant = new Constant(new IntConstant(info->_min));
531
            NOT_PRODUCT(min_constant->set_printable_bci(first->printable_bci()));
532
            insert_position = insert_position->insert_after(min_constant);
533
          }
534

535
          // Load max Constant
536
          Constant *max_constant = nullptr;
537
          if (info->_max != 0) {
538
            max_constant = new Constant(new IntConstant(info->_max));
539
            NOT_PRODUCT(max_constant->set_printable_bci(first->printable_bci()));
540
            insert_position = insert_position->insert_after(max_constant);
541
          }
542

543
          // Load array length
544
          Value length_instr = first->length();
545
          if (!length_instr) {
546
            ArrayLength *length = new ArrayLength(array, first->state_before()->copy());
547
            length->set_exception_state(length->state_before());
548
            length->set_flag(Instruction::DeoptimizeOnException, true);
549
            insert_position = insert_position->insert_after_same_bci(length);
550
            length_instr = length;
551
          }
552

553
          // Calculate lower bound
554
          Instruction *lower_compare = index_instruction;
555
          if (min_constant) {
556
            ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, min_constant, lower_compare, nullptr);
557
            insert_position = insert_position->insert_after_same_bci(ao);
558
            lower_compare = ao;
559
          }
560

561
          // Calculate upper bound
562
          Instruction *upper_compare = index_instruction;
563
          if (max_constant) {
564
            ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, max_constant, upper_compare, nullptr);
565
            insert_position = insert_position->insert_after_same_bci(ao);
566
            upper_compare = ao;
567
          }
568

569
          // Trick with unsigned compare is done
570
          int bci = NOT_PRODUCT(first->printable_bci()) PRODUCT_ONLY(-1);
571
          insert_position = predicate(upper_compare, Instruction::aeq, length_instr, state, insert_position, bci);
572
          insert_position = predicate_cmp_with_const(lower_compare, Instruction::leq, -1, state, insert_position);
573
          for (int j = 0; j<info->_list->length(); j++) {
574
            AccessIndexed *ai = info->_list->at(j);
575
            remove_range_check(ai);
576
          }
577
        }
578
      }
579

580
      if (list_constant.length() > 1) {
581
        AccessIndexed *first = list_constant.at(0);
582
        Instruction *insert_position = first->prev();
583
        ValueStack *state = first->state_before();
584
        // Load max Constant
585
        Constant *constant = new Constant(new IntConstant(max_constant));
586
        NOT_PRODUCT(constant->set_printable_bci(first->printable_bci()));
587
        insert_position = insert_position->insert_after(constant);
588
        Instruction *compare_instr = constant;
589
        Value length_instr = first->length();
590
        if (!length_instr) {
591
          ArrayLength *length = new ArrayLength(array, state->copy());
592
          length->set_exception_state(length->state_before());
593
          length->set_flag(Instruction::DeoptimizeOnException, true);
594
          insert_position = insert_position->insert_after_same_bci(length);
595
          length_instr = length;
596
        }
597
        // Compare for greater or equal to array length
598
        insert_position = predicate(compare_instr, Instruction::geq, length_instr, state, insert_position);
599
        for (int j = 0; j<list_constant.length(); j++) {
600
          AccessIndexed *ai = list_constant.at(j);
601
          remove_range_check(ai);
602
        }
603
      }
604
    }
605

606
    // Clear data structures for next array
607
    for (int i = 0; i < indices.length(); i++) {
608
      Instruction *index_instruction = indices.at(i);
609
      _access_indexed_info.at_put(index_instruction->id(), nullptr);
610
    }
611
    indices.clear();
612
  }
613
}
614

615
bool RangeCheckEliminator::set_process_block_flags(BlockBegin *block) {
616
  Instruction *cur = block;
617
  bool process = false;
618

619
  while (cur) {
620
    process |= (cur->as_AccessIndexed() != nullptr);
621
    cur = cur->next();
622
  }
623

624
  BlockList *dominates = block->dominates();
625
  for (int i=0; i<dominates->length(); i++) {
626
    BlockBegin *next = dominates->at(i);
627
    process |= set_process_block_flags(next);
628
  }
629

630
  if (!process) {
631
    block->set(BlockBegin::donot_eliminate_range_checks);
632
  }
633
  return process;
634
}
635

636
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) {
637
  bool upper_check = true;
638
  assert(lower_instr || lower >= 0, "If no lower_instr present, lower must be greater 0");
639
  assert(!lower_instr || lower_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
640
  assert(!upper_instr || upper_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
641
  assert(array_instr, "Array instruction must exist");
642
  assert(array_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
643
  assert(!length_instr || length_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
644

645
  if (upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr) {
646
    // static check
647
    if (upper >= 0) return false; // would always trigger a deopt:
648
                                  // array_length + x >= array_length, x >= 0 is always true
649
    upper_check = false;
650
  }
651
  if (lower_instr && lower_instr->as_ArrayLength() && lower_instr->as_ArrayLength()->array() == array_instr) {
652
    if (lower > 0) return false;
653
  }
654
  // No upper check required -> skip
655
  if (upper_check && upper_instr && upper_instr->type()->as_ObjectType() && upper_instr == array_instr) {
656
    // upper_instr is object means that the upper bound is the length
657
    // of the upper_instr.
658
    return false;
659
  }
660
  return true;
661
}
662

663
Instruction* RangeCheckEliminator::insert_after(Instruction* insert_position, Instruction* instr, int bci) {
664
  if (bci != -1) {
665
    NOT_PRODUCT(instr->set_printable_bci(bci));
666
    return insert_position->insert_after(instr);
667
  } else {
668
    return insert_position->insert_after_same_bci(instr);
669
  }
670
}
671

672
Instruction* RangeCheckEliminator::predicate(Instruction* left, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) {
673
  RangeCheckPredicate *deoptimize = new RangeCheckPredicate(left, cond, true, right, state->copy());
674
  return insert_after(insert_position, deoptimize, bci);
675
}
676

677
Instruction* RangeCheckEliminator::predicate_cmp_with_const(Instruction* instr, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) {
678
  Constant *const_instr = new Constant(new IntConstant(constant));
679
  insert_position = insert_after(insert_position, const_instr, bci);
680
  return predicate(instr, cond, const_instr, state, insert_position);
681
}
682

683
Instruction* RangeCheckEliminator::predicate_add(Instruction* left, int left_const, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) {
684
  Constant *constant = new Constant(new IntConstant(left_const));
685
  insert_position = insert_after(insert_position, constant, bci);
686
  ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, left, nullptr);
687
  insert_position = insert_position->insert_after_same_bci(ao);
688
  return predicate(ao, cond, right, state, insert_position);
689
}
690

691
Instruction* RangeCheckEliminator::predicate_add_cmp_with_const(Instruction* left, int left_const, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) {
692
  Constant *const_instr = new Constant(new IntConstant(constant));
693
  insert_position = insert_after(insert_position, const_instr, bci);
694
  return predicate_add(left, left_const, cond, const_instr, state, insert_position);
695
}
696

697
// Insert deoptimization
698
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) {
699
  assert(is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, lower, upper_instr, upper), "should have been tested before");
700
  bool upper_check = !(upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr);
701

702
  int bci = NOT_PRODUCT(ai->printable_bci()) PRODUCT_ONLY(-1);
703
  if (lower_instr) {
704
    assert(!lower_instr->type()->as_ObjectType(), "Must not be object type");
705
    if (lower == 0) {
706
      // Compare for less than 0
707
      insert_position = predicate_cmp_with_const(lower_instr, Instruction::lss, 0, state, insert_position, bci);
708
    } else if (lower > 0) {
709
      // Compare for smaller 0
710
      insert_position = predicate_add_cmp_with_const(lower_instr, lower, Instruction::lss, 0, state, insert_position, bci);
711
    } else {
712
      assert(lower < 0, "");
713
      // Add 1
714
      lower = java_subtract(-1, (jint)lower); // lower++; lower = -lower;
715
      // Compare for smaller or equal 0
716
      insert_position = predicate_cmp_with_const(lower_instr, Instruction::leq, lower, state, insert_position, bci);
717
    }
718
  }
719

720
  // No upper check required -> skip
721
  if (!upper_check) return;
722

723
  // We need to know length of array
724
  if (!length_instr) {
725
    // Load length if necessary
726
    ArrayLength *length = new ArrayLength(array_instr, state->copy());
727
    NOT_PRODUCT(length->set_printable_bci(ai->printable_bci()));
728
    length->set_exception_state(length->state_before());
729
    length->set_flag(Instruction::DeoptimizeOnException, true);
730
    insert_position = insert_position->insert_after(length);
731
    length_instr = length;
732
  }
733

734
  if (!upper_instr) {
735
    // Compare for geq array.length
736
    insert_position = predicate_cmp_with_const(length_instr, Instruction::leq, upper, state, insert_position, bci);
737
  } else {
738
    if (upper_instr->type()->as_ObjectType()) {
739
      assert(state, "must not be null");
740
      assert(upper_instr != array_instr, "should be");
741
      ArrayLength *length = new ArrayLength(upper_instr, state->copy());
742
      NOT_PRODUCT(length->set_printable_bci(ai->printable_bci()));
743
      length->set_flag(Instruction::DeoptimizeOnException, true);
744
      length->set_exception_state(length->state_before());
745
      insert_position = insert_position->insert_after(length);
746
      upper_instr = length;
747
    }
748
    assert(upper_instr->type()->as_IntType(), "Must not be object type!");
749

750
    if (upper == 0) {
751
      // Compare for geq array.length
752
      insert_position = predicate(upper_instr, Instruction::geq, length_instr, state, insert_position, bci);
753
    } else if (upper < 0) {
754
      // Compare for geq array.length
755
      insert_position = predicate_add(upper_instr, upper, Instruction::geq, length_instr, state, insert_position, bci);
756
    } else {
757
      assert(upper > 0, "");
758
      upper = java_negate((jint)upper); // upper = -upper;
759
      // Compare for geq array.length
760
      insert_position = predicate_add(length_instr, upper, Instruction::leq, upper_instr, state, insert_position, bci);
761
    }
762
  }
763
}
764

765
// Add if condition
766
void RangeCheckEliminator::add_if_condition(IntegerStack &pushed, Value x, Value y, Instruction::Condition condition) {
767
  if (y->as_Constant()) return;
768

769
  int const_value = 0;
770
  Value instr_value = x;
771
  Constant *c = x->as_Constant();
772
  ArithmeticOp *ao = x->as_ArithmeticOp();
773

774
  if (c != nullptr) {
775
    const_value = c->type()->as_IntConstant()->value();
776
    instr_value = nullptr;
777
  } else if (ao != nullptr &&  (!ao->x()->as_Constant() || !ao->y()->as_Constant()) && ((ao->op() == Bytecodes::_isub && ao->y()->as_Constant()) || ao->op() == Bytecodes::_iadd)) {
778
    assert(!ao->x()->as_Constant() || !ao->y()->as_Constant(), "At least one operator must be non-constant!");
779
    assert(ao->op() == Bytecodes::_isub || ao->op() == Bytecodes::_iadd, "Operation has to be add or sub!");
780
    c = ao->x()->as_Constant();
781
    if (c != nullptr) {
782
      const_value = c->type()->as_IntConstant()->value();
783
      instr_value = ao->y();
784
    } else {
785
      c = ao->y()->as_Constant();
786
      if (c != nullptr) {
787
        const_value = c->type()->as_IntConstant()->value();
788
        instr_value = ao->x();
789
      }
790
    }
791
    if (ao->op() == Bytecodes::_isub) {
792
      assert(ao->y()->as_Constant(), "1 - x not supported, only x - 1 is valid!");
793
      if (const_value > min_jint) {
794
        const_value = -const_value;
795
      } else {
796
        const_value = 0;
797
        instr_value = x;
798
      }
799
    }
800
  }
801

802
  update_bound(pushed, y, condition, instr_value, const_value);
803
}
804

805
// Process If
806
void RangeCheckEliminator::process_if(IntegerStack &pushed, BlockBegin *block, If *cond) {
807
  // Only if we are direct true / false successor and NOT both ! (even this may occur)
808
  if ((cond->tsux() == block || cond->fsux() == block) && cond->tsux() != cond->fsux()) {
809
    Instruction::Condition condition = cond->cond();
810
    if (cond->fsux() == block) {
811
      condition = Instruction::negate(condition);
812
    }
813
    Value x = cond->x();
814
    Value y = cond->y();
815
    if (x->type()->as_IntType() && y->type()->as_IntType()) {
816
      add_if_condition(pushed, y, x, condition);
817
      add_if_condition(pushed, x, y, Instruction::mirror(condition));
818
    }
819
  }
820
}
821

822
// Process access indexed
823
void RangeCheckEliminator::process_access_indexed(BlockBegin *loop_header, BlockBegin *block, AccessIndexed *ai) {
824
  TRACE_RANGE_CHECK_ELIMINATION(
825
    tty->fill_to(block->dominator_depth()*2)
826
  );
827
  TRACE_RANGE_CHECK_ELIMINATION(
828
    tty->print_cr("Access indexed: index=%d length=%d", ai->index()->id(), (ai->length() != nullptr ? ai->length()->id() :-1 ))
829
  );
830

831
  if (ai->check_flag(Instruction::NeedsRangeCheckFlag)) {
832
    Bound *index_bound = get_bound(ai->index());
833
    if (!index_bound->has_lower() || !index_bound->has_upper()) {
834
      TRACE_RANGE_CHECK_ELIMINATION(
835
        tty->fill_to(block->dominator_depth()*2);
836
        tty->print_cr("Index instruction %d has no lower and/or no upper bound!", ai->index()->id())
837
      );
838
      return;
839
    }
840

841
    Bound *array_bound;
842
    if (ai->length()) {
843
      array_bound = get_bound(ai->length());
844
    } else {
845
      array_bound = get_bound(ai->array());
846
    }
847

848
    TRACE_RANGE_CHECK_ELIMINATION(
849
      tty->fill_to(block->dominator_depth()*2);
850
      tty->print("Index bound: ");
851
      index_bound->print();
852
      tty->print(", Array bound: ");
853
      array_bound->print();
854
      tty->cr();
855
    );
856

857
    if (in_array_bound(index_bound, ai->array()) ||
858
      (index_bound && array_bound && index_bound->is_smaller(array_bound) && !index_bound->lower_instr() && index_bound->lower() >= 0)) {
859
        TRACE_RANGE_CHECK_ELIMINATION(
860
          tty->fill_to(block->dominator_depth()*2);
861
          tty->print_cr("Bounds check for instruction %d in block B%d can be fully eliminated!", ai->id(), ai->block()->block_id())
862
        );
863

864
        remove_range_check(ai);
865
    } else if (false && _optimistic && loop_header) {
866
      assert(ai->array(), "Array must not be null!");
867
      assert(ai->index(), "Index must not be null!");
868

869
      // Array instruction
870
      Instruction *array_instr = ai->array();
871
      if (!loop_invariant(loop_header, array_instr)) {
872
        TRACE_RANGE_CHECK_ELIMINATION(
873
          tty->fill_to(block->dominator_depth()*2);
874
          tty->print_cr("Array %d is not loop invariant to header B%d", ai->array()->id(), loop_header->block_id())
875
        );
876
        return;
877
      }
878

879
      // Lower instruction
880
      Value index_instr = ai->index();
881
      Value lower_instr = index_bound->lower_instr();
882
      if (!loop_invariant(loop_header, lower_instr)) {
883
        TRACE_RANGE_CHECK_ELIMINATION(
884
          tty->fill_to(block->dominator_depth()*2);
885
          tty->print_cr("Lower instruction %d not loop invariant!", lower_instr->id())
886
        );
887
        return;
888
      }
889
      if (!lower_instr && index_bound->lower() < 0) {
890
        TRACE_RANGE_CHECK_ELIMINATION(
891
          tty->fill_to(block->dominator_depth()*2);
892
          tty->print_cr("Lower bound smaller than 0 (%d)!", index_bound->lower())
893
        );
894
        return;
895
      }
896

897
      // Upper instruction
898
      Value upper_instr = index_bound->upper_instr();
899
      if (!loop_invariant(loop_header, upper_instr)) {
900
        TRACE_RANGE_CHECK_ELIMINATION(
901
          tty->fill_to(block->dominator_depth()*2);
902
          tty->print_cr("Upper instruction %d not loop invariant!", upper_instr->id())
903
        );
904
        return;
905
      }
906

907
      // Length instruction
908
      Value length_instr = ai->length();
909
      if (!loop_invariant(loop_header, length_instr)) {
910
        // Generate length instruction yourself!
911
        length_instr = nullptr;
912
      }
913

914
      TRACE_RANGE_CHECK_ELIMINATION(
915
        tty->fill_to(block->dominator_depth()*2);
916
        tty->print_cr("LOOP INVARIANT access indexed %d found in block B%d!", ai->id(), ai->block()->block_id())
917
      );
918

919
      BlockBegin *pred_block = loop_header->dominator();
920
      assert(pred_block != nullptr, "Every loop header has a dominator!");
921
      BlockEnd *pred_block_end = pred_block->end();
922
      Instruction *insert_position = pred_block_end->prev();
923
      ValueStack *state = pred_block_end->state_before();
924
      if (pred_block_end->as_Goto() && state == nullptr) state = pred_block_end->state();
925
      assert(state, "State must not be null");
926

927
      // Add deoptimization to dominator of loop header
928
      TRACE_RANGE_CHECK_ELIMINATION(
929
        tty->fill_to(block->dominator_depth()*2);
930
        tty->print_cr("Inserting deopt at bci %d in block B%d!", state->bci(), insert_position->block()->block_id())
931
      );
932

933
      if (!is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper())) {
934
        TRACE_RANGE_CHECK_ELIMINATION(
935
          tty->fill_to(block->dominator_depth()*2);
936
          tty->print_cr("Could not eliminate because of static analysis!")
937
        );
938
        return;
939
      }
940

941
      insert_deoptimization(state, insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper(), ai);
942

943
      // Finally remove the range check!
944
      remove_range_check(ai);
945
    }
946
  }
947
}
948

949
void RangeCheckEliminator::remove_range_check(AccessIndexed *ai) {
950
  ai->set_flag(Instruction::NeedsRangeCheckFlag, false);
951
  // no range check, no need for the length instruction anymore
952
  ai->clear_length();
953

954
  TRACE_RANGE_CHECK_ELIMINATION(
955
    tty->fill_to(ai->dominator_depth()*2);
956
    tty->print_cr("Range check for instruction %d eliminated!", ai->id());
957
  );
958

959
  ASSERT_RANGE_CHECK_ELIMINATION(
960
    Value array_length = ai->length();
961
    if (!array_length) {
962
      array_length = ai->array();
963
      assert(array_length->type()->as_ObjectType(), "Has to be object type!");
964
    }
965
    int cur_constant = -1;
966
    Value cur_value = array_length;
967
    if (cur_value->type()->as_IntConstant()) {
968
      cur_constant += cur_value->type()->as_IntConstant()->value();
969
      cur_value = nullptr;
970
    }
971
    Bound* new_index_bound = new Bound(0, nullptr, cur_constant, cur_value);
972
    add_assertions(new_index_bound, ai->index(), ai);
973
  );
974
}
975

976
// Calculate bounds for instruction in this block and children blocks in the dominator tree
977
void RangeCheckEliminator::calc_bounds(BlockBegin *block, BlockBegin *loop_header) {
978
  // Ensures a valid loop_header
979
  assert(!loop_header || loop_header->is_set(BlockBegin::linear_scan_loop_header_flag), "Loop header has to be real !");
980

981
  // Tracing output
982
  TRACE_RANGE_CHECK_ELIMINATION(
983
    tty->fill_to(block->dominator_depth()*2);
984
    tty->print_cr("Block B%d", block->block_id());
985
  );
986

987
  // Pushed stack for conditions
988
  IntegerStack pushed;
989
  // Process If
990
  BlockBegin *parent = block->dominator();
991
  if (parent != nullptr) {
992
    If *cond = parent->end()->as_If();
993
    if (cond != nullptr) {
994
      process_if(pushed, block, cond);
995
    }
996
  }
997

998
  // Iterate over current block
999
  InstructionList arrays;
1000
  AccessIndexedList accessIndexed;
1001
  Instruction *cur = block;
1002

1003
  while (cur) {
1004
    // Ensure cur wasn't inserted during the elimination
1005
    if (cur->id() < this->_bounds.length()) {
1006
      // Process only if it is an access indexed instruction
1007
      AccessIndexed *ai = cur->as_AccessIndexed();
1008
      if (ai != nullptr) {
1009
        process_access_indexed(loop_header, block, ai);
1010
        accessIndexed.append(ai);
1011
        if (!arrays.contains(ai->array())) {
1012
          arrays.append(ai->array());
1013
        }
1014
        Bound *b = get_bound(ai->index());
1015
        if (!b->lower_instr()) {
1016
          // Lower bound is constant
1017
          update_bound(pushed, ai->index(), Instruction::geq, nullptr, 0);
1018
        }
1019
        if (!b->has_upper()) {
1020
          if (ai->length() && ai->length()->type()->as_IntConstant()) {
1021
            int value = ai->length()->type()->as_IntConstant()->value();
1022
            update_bound(pushed, ai->index(), Instruction::lss, nullptr, value);
1023
          } else {
1024
            // Has no upper bound
1025
            Instruction *instr = ai->length();
1026
            if (instr == nullptr) instr = ai->array();
1027
            update_bound(pushed, ai->index(), Instruction::lss, instr, 0);
1028
          }
1029
        }
1030
      }
1031
    }
1032
    cur = cur->next();
1033
  }
1034

1035
  // Output current condition stack
1036
  TRACE_RANGE_CHECK_ELIMINATION(dump_condition_stack(block));
1037

1038
  // Do in block motion of range checks
1039
  in_block_motion(block, accessIndexed, arrays);
1040

1041
  // Call all dominated blocks
1042
  for (int i=0; i<block->dominates()->length(); i++) {
1043
    BlockBegin *next = block->dominates()->at(i);
1044
    if (!next->is_set(BlockBegin::donot_eliminate_range_checks)) {
1045
      // if current block is a loop header and:
1046
      // - next block belongs to the same loop
1047
      // or
1048
      // - next block belongs to an inner loop
1049
      // then current block is the loop header for next block
1050
      if (block->is_set(BlockBegin::linear_scan_loop_header_flag) && (block->loop_index() == next->loop_index() || next->loop_depth() > block->loop_depth())) {
1051
        calc_bounds(next, block);
1052
      } else {
1053
        calc_bounds(next, loop_header);
1054
      }
1055
    }
1056
  }
1057

1058
  // Reset stack
1059
  for (int i=0; i<pushed.length(); i++) {
1060
    _bounds.at(pushed.at(i))->pop();
1061
  }
1062
}
1063

1064
#ifndef PRODUCT
1065
// Dump condition stack
1066
void RangeCheckEliminator::dump_condition_stack(BlockBegin *block) {
1067
  for (int i=0; i<_ir->linear_scan_order()->length(); i++) {
1068
    BlockBegin *cur_block = _ir->linear_scan_order()->at(i);
1069
    Instruction *instr = cur_block;
1070
    for_each_phi_fun(cur_block, phi,
1071
                     BoundStack *bound_stack = _bounds.at(phi->id());
1072
                     if (bound_stack && bound_stack->length() > 0) {
1073
                       Bound *bound = bound_stack->top();
1074
                       if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != phi || bound->upper_instr() != phi || bound->lower() != 0 || bound->upper() != 0)) {
1075
                           TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth());
1076
                                                         tty->print("i%d", phi->id());
1077
                                                         tty->print(": ");
1078
                                                         bound->print();
1079
                                                         tty->cr();
1080
                           );
1081
                         }
1082
                     });
1083

1084
    while (!instr->as_BlockEnd()) {
1085
      if (instr->id() < _bounds.length()) {
1086
        BoundStack *bound_stack = _bounds.at(instr->id());
1087
        if (bound_stack && bound_stack->length() > 0) {
1088
          Bound *bound = bound_stack->top();
1089
          if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != instr || bound->upper_instr() != instr || bound->lower() != 0 || bound->upper() != 0)) {
1090
              TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth());
1091
                                            tty->print("i%d", instr->id());
1092
                                            tty->print(": ");
1093
                                            bound->print();
1094
                                            tty->cr();
1095
              );
1096
          }
1097
        }
1098
      }
1099
      instr = instr->next();
1100
    }
1101
  }
1102
}
1103
#endif
1104

1105
#ifdef ASSERT
1106
// Verification or the IR
1107
RangeCheckEliminator::Verification::Verification(IR *ir) : _used(BlockBegin::number_of_blocks(), BlockBegin::number_of_blocks(), false) {
1108
  this->_ir = ir;
1109
  ir->iterate_linear_scan_order(this);
1110
}
1111

1112
// Verify this block
1113
void RangeCheckEliminator::Verification::block_do(BlockBegin *block) {
1114
  If *cond = block->end()->as_If();
1115
  // Watch out: tsux and fsux can be the same!
1116
  if (block->number_of_sux() > 1) {
1117
    for (int i=0; i<block->number_of_sux(); i++) {
1118
      BlockBegin* sux = block->sux_at(i);
1119
      BlockBegin* pred = nullptr;
1120
      for (int j=0; j<sux->number_of_preds(); j++) {
1121
        BlockBegin *cur = sux->pred_at(j);
1122
        assert(cur != nullptr, "Predecessor must not be null");
1123
        if (!pred) {
1124
          pred = cur;
1125
        }
1126
        assert(cur == pred, "Block must not have more than one predecessor if its predecessor has more than one successor");
1127
      }
1128
      assert(sux->number_of_preds() >= 1, "Block must have at least one predecessor");
1129
      assert(sux->pred_at(0) == block, "Wrong successor");
1130
    }
1131
  }
1132

1133
  BlockBegin *dominator = block->dominator();
1134
  if (dominator) {
1135
    assert(block != _ir->start(), "Start block must not have a dominator!");
1136
    assert(can_reach(dominator, block), "Dominator can't reach his block !");
1137
    assert(can_reach(_ir->start(), dominator), "Dominator is unreachable !");
1138
    assert(!can_reach(_ir->start(), block, dominator), "Wrong dominator ! Block can be reached anyway !");
1139
    BlockList *all_blocks = _ir->linear_scan_order();
1140
    for (int i=0; i<all_blocks->length(); i++) {
1141
      BlockBegin *cur = all_blocks->at(i);
1142
      if (cur != dominator && cur != block) {
1143
        assert(can_reach(dominator, block, cur), "There has to be another dominator!");
1144
      }
1145
    }
1146
  } else {
1147
    assert(block == _ir->start(), "Only start block must not have a dominator");
1148
  }
1149

1150
  if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) {
1151
    int loop_index = block->loop_index();
1152
    BlockList *all_blocks = _ir->linear_scan_order();
1153
    assert(block->number_of_preds() >= 1, "Block must have at least one predecessor");
1154
    assert(!block->is_set(BlockBegin::exception_entry_flag), "Loop header must not be exception handler!");
1155

1156
    bool loop_through_xhandler = false;
1157
    for (int i=0; i<block->number_of_sux(); i++) {
1158
      BlockBegin *sux = block->sux_at(i);
1159
      if (!loop_through_xhandler) {
1160
        if (sux->loop_depth() == block->loop_depth() && sux->loop_index() != block->loop_index()) {
1161
          loop_through_xhandler = is_backbranch_from_xhandler(block);
1162
          assert(loop_through_xhandler, "Loop indices have to be the same if same depths but no backbranch from xhandler");
1163
        }
1164
      }
1165
      assert(sux->loop_depth() == block->loop_depth() || sux->loop_index() != block->loop_index(), "Loop index has to be different");
1166
    }
1167

1168
    for (int i=0; i<all_blocks->length(); i++) {
1169
      BlockBegin *cur = all_blocks->at(i);
1170
      if (cur->loop_index() == loop_index && cur != block) {
1171
        assert(dominates(block->dominator(), cur), "Dominator of loop header must dominate all loop blocks");
1172
      }
1173
    }
1174
  }
1175

1176
  Instruction *cur = block;
1177
  while (cur) {
1178
    assert(cur->block() == block, "Block begin has to be set correctly!");
1179
    cur = cur->next();
1180
  }
1181
}
1182

1183
// Called when a successor of a block has the same loop depth but a different loop index. This can happen if a backbranch comes from
1184
// an exception handler of a loop head block, for example, when a loop is only executed once on the non-exceptional path but is
1185
// repeated in case of an exception. In this case, the edge block->sux is not critical and was not split before.
1186
// Check if there is such a backbranch from an xhandler of 'block'.
1187
bool RangeCheckEliminator::Verification::is_backbranch_from_xhandler(BlockBegin* block) {
1188
  for (int i = 0; i < block->number_of_exception_handlers(); i++) {
1189
    BlockBegin *xhandler = block->exception_handler_at(i);
1190
    for (int j = 0; j < block->number_of_preds(); j++) {
1191
      if (dominates(xhandler, block->pred_at(j)) || xhandler == block->pred_at(j)) {
1192
        return true;
1193
      }
1194
    }
1195
  }
1196

1197
  // In case of nested xhandlers, we need to walk through the loop (and all blocks belonging to exception handlers)
1198
  // to find an xhandler of 'block'.
1199
  if (block->number_of_exception_handlers() > 0) {
1200
    for (int i = 0; i < block->number_of_preds(); i++) {
1201
      BlockBegin* pred = block->pred_at(i);
1202
      if (pred->loop_index() == block->loop_index()) {
1203
        // Only check blocks that belong to the loop
1204
        // Do a BFS to find an xhandler block of 'block' starting from 'pred'
1205
        ResourceMark rm;
1206
        ResourceBitMap visited(BlockBegin::number_of_blocks());
1207
        BlockBeginList list;
1208
        list.push(pred);
1209
        while (!list.is_empty()) {
1210
          BlockBegin* next = list.pop();
1211
          if (!visited.at(next->block_id())) {
1212
            visited.set_bit(next->block_id());
1213
            for (int j = 0; j < block->number_of_exception_handlers(); j++) {
1214
               if (next == block->exception_handler_at(j)) {
1215
                 return true;
1216
               }
1217
            }
1218
            for (int j = 0; j < next->number_of_preds(); j++) {
1219
               if (next->pred_at(j) != block) {
1220
                 list.push(next->pred_at(j));
1221
               }
1222
            }
1223
          }
1224
        }
1225
      }
1226
    }
1227
  }
1228
  return false;
1229
}
1230

1231
// Loop header must dominate all loop blocks
1232
bool RangeCheckEliminator::Verification::dominates(BlockBegin *dominator, BlockBegin *block) {
1233
  BlockBegin *cur = block->dominator();
1234
  while (cur && cur != dominator) {
1235
    cur = cur->dominator();
1236
  }
1237
  return cur == dominator;
1238
}
1239

1240
// Try to reach Block end beginning in Block start and not using Block dont_use
1241
bool RangeCheckEliminator::Verification::can_reach(BlockBegin* start, BlockBegin* end, BlockBegin* dont_use /* = nullptr */) {
1242
  if (start == end) return start != dont_use;
1243
  // Simple BSF from start to end
1244
  //  BlockBeginList _current;
1245
  for (int i=0; i < _used.length(); i++) {
1246
    _used.at_put(i, false);
1247
  }
1248
  _current.trunc_to(0);
1249
  _successors.trunc_to(0);
1250
  if (start != dont_use) {
1251
    _current.push(start);
1252
    _used.at_put(start->block_id(), true);
1253
  }
1254

1255
  //  BlockBeginList _successors;
1256
  while (_current.length() > 0) {
1257
    BlockBegin *cur = _current.pop();
1258
    // Add exception handlers to list
1259
    for (int i=0; i<cur->number_of_exception_handlers(); i++) {
1260
      BlockBegin *xhandler = cur->exception_handler_at(i);
1261
      _successors.push(xhandler);
1262
      // Add exception handlers of _successors to list
1263
      for (int j=0; j<xhandler->number_of_exception_handlers(); j++) {
1264
        BlockBegin *sux_xhandler = xhandler->exception_handler_at(j);
1265
        _successors.push(sux_xhandler);
1266
      }
1267
    }
1268
    // Add normal _successors to list
1269
    for (int i=0; i<cur->number_of_sux(); i++) {
1270
      BlockBegin *sux = cur->sux_at(i);
1271
      _successors.push(sux);
1272
      // Add exception handlers of _successors to list
1273
      for (int j=0; j<sux->number_of_exception_handlers(); j++) {
1274
        BlockBegin *xhandler = sux->exception_handler_at(j);
1275
        _successors.push(xhandler);
1276
      }
1277
    }
1278
    for (int i=0; i<_successors.length(); i++) {
1279
      BlockBegin *sux = _successors.at(i);
1280
      assert(sux != nullptr, "Successor must not be null!");
1281
      if (sux == end) {
1282
        return true;
1283
      }
1284
      if (sux != dont_use && !_used.at(sux->block_id())) {
1285
        _used.at_put(sux->block_id(), true);
1286
        _current.push(sux);
1287
      }
1288
    }
1289
    _successors.trunc_to(0);
1290
  }
1291

1292
  return false;
1293
}
1294
#endif // ASSERT
1295

1296
// Bound
1297
RangeCheckEliminator::Bound::~Bound() {
1298
}
1299

1300
// Bound constructor
1301
RangeCheckEliminator::Bound::Bound() {
1302
  this->_lower = min_jint;
1303
  this->_upper = max_jint;
1304
  this->_lower_instr = nullptr;
1305
  this->_upper_instr = nullptr;
1306
}
1307

1308
// Bound constructor
1309
RangeCheckEliminator::Bound::Bound(int lower, Value lower_instr, int upper, Value upper_instr) {
1310
  assert(!lower_instr || !lower_instr->as_Constant() || !lower_instr->type()->as_IntConstant(), "Must not be constant!");
1311
  assert(!upper_instr || !upper_instr->as_Constant() || !upper_instr->type()->as_IntConstant(), "Must not be constant!");
1312
  this->_lower = lower;
1313
  this->_upper = upper;
1314
  this->_lower_instr = lower_instr;
1315
  this->_upper_instr = upper_instr;
1316
}
1317

1318
// Bound constructor
1319
RangeCheckEliminator::Bound::Bound(Instruction::Condition cond, Value v, int constant) {
1320
  assert(!v || (v->type() && (v->type()->as_IntType() || v->type()->as_ObjectType())), "Type must be array or integer!");
1321
  assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!");
1322

1323
  if (cond == Instruction::eql) {
1324
    _lower = constant;
1325
    _lower_instr = v;
1326
    _upper = constant;
1327
    _upper_instr = v;
1328
  } else if (cond == Instruction::neq) {
1329
    _lower = min_jint;
1330
    _upper = max_jint;
1331
    _lower_instr = nullptr;
1332
    _upper_instr = nullptr;
1333
    if (v == nullptr) {
1334
      if (constant == min_jint) {
1335
        _lower++;
1336
      }
1337
      if (constant == max_jint) {
1338
        _upper--;
1339
      }
1340
    }
1341
  } else if (cond == Instruction::geq) {
1342
    _lower = constant;
1343
    _lower_instr = v;
1344
    _upper = max_jint;
1345
    _upper_instr = nullptr;
1346
  } else if (cond == Instruction::leq) {
1347
    _lower = min_jint;
1348
    _lower_instr = nullptr;
1349
    _upper = constant;
1350
    _upper_instr = v;
1351
  } else {
1352
    ShouldNotReachHere();
1353
  }
1354
}
1355

1356
// or
1357
void RangeCheckEliminator::Bound::or_op(Bound *b) {
1358
  // Watch out, bound is not guaranteed not to overflow!
1359
  // Update lower bound
1360
  if (_lower_instr != b->_lower_instr || (_lower_instr && _lower != b->_lower)) {
1361
    _lower_instr = nullptr;
1362
    _lower = min_jint;
1363
  } else {
1364
    _lower = MIN2(_lower, b->_lower);
1365
  }
1366
  // Update upper bound
1367
  if (_upper_instr != b->_upper_instr || (_upper_instr && _upper != b->_upper)) {
1368
    _upper_instr = nullptr;
1369
    _upper = max_jint;
1370
  } else {
1371
    _upper = MAX2(_upper, b->_upper);
1372
  }
1373
}
1374

1375
// and
1376
void RangeCheckEliminator::Bound::and_op(Bound *b) {
1377
  // Update lower bound
1378
  if (_lower_instr == b->_lower_instr) {
1379
    _lower = MAX2(_lower, b->_lower);
1380
  }
1381
  if (b->has_lower()) {
1382
    bool set = true;
1383
    if (_lower_instr != nullptr && b->_lower_instr != nullptr) {
1384
      set = (_lower_instr->dominator_depth() > b->_lower_instr->dominator_depth());
1385
    }
1386
    if (set) {
1387
      _lower = b->_lower;
1388
      _lower_instr = b->_lower_instr;
1389
    }
1390
  }
1391
  // Update upper bound
1392
  if (_upper_instr == b->_upper_instr) {
1393
    _upper = MIN2(_upper, b->_upper);
1394
  }
1395
  if (b->has_upper()) {
1396
    bool set = true;
1397
    if (_upper_instr != nullptr && b->_upper_instr != nullptr) {
1398
      set = (_upper_instr->dominator_depth() > b->_upper_instr->dominator_depth());
1399
    }
1400
    if (set) {
1401
      _upper = b->_upper;
1402
      _upper_instr = b->_upper_instr;
1403
    }
1404
  }
1405
}
1406

1407
// has_upper
1408
bool RangeCheckEliminator::Bound::has_upper() {
1409
  return _upper_instr != nullptr || _upper < max_jint;
1410
}
1411

1412
// is_smaller
1413
bool RangeCheckEliminator::Bound::is_smaller(Bound *b) {
1414
  if (b->_lower_instr != _upper_instr) {
1415
    return false;
1416
  }
1417
  return _upper < b->_lower;
1418
}
1419

1420
// has_lower
1421
bool RangeCheckEliminator::Bound::has_lower() {
1422
  return _lower_instr != nullptr || _lower > min_jint;
1423
}
1424

1425
// in_array_bound
1426
bool RangeCheckEliminator::in_array_bound(Bound *bound, Value array){
1427
  if (!bound) return false;
1428
  assert(array != nullptr, "Must not be null!");
1429
  assert(bound != nullptr, "Must not be null!");
1430
  if (bound->lower() >=0 && bound->lower_instr() == nullptr && bound->upper() < 0 && bound->upper_instr() != nullptr) {
1431
    ArrayLength *len = bound->upper_instr()->as_ArrayLength();
1432
    if (bound->upper_instr() == array || (len != nullptr && len->array() == array)) {
1433
      return true;
1434
    }
1435
  }
1436
  return false;
1437
}
1438

1439
// remove_lower
1440
void RangeCheckEliminator::Bound::remove_lower() {
1441
  _lower = min_jint;
1442
  _lower_instr = nullptr;
1443
}
1444

1445
// remove_upper
1446
void RangeCheckEliminator::Bound::remove_upper() {
1447
  _upper = max_jint;
1448
  _upper_instr = nullptr;
1449
}
1450

1451
// upper
1452
int RangeCheckEliminator::Bound::upper() {
1453
  return _upper;
1454
}
1455

1456
// lower
1457
int RangeCheckEliminator::Bound::lower() {
1458
  return _lower;
1459
}
1460

1461
// upper_instr
1462
Value RangeCheckEliminator::Bound::upper_instr() {
1463
  return _upper_instr;
1464
}
1465

1466
// lower_instr
1467
Value RangeCheckEliminator::Bound::lower_instr() {
1468
  return _lower_instr;
1469
}
1470

1471
// print
1472
void RangeCheckEliminator::Bound::print() {
1473
  tty->print("%s", "");
1474
  if (this->_lower_instr || this->_lower != min_jint) {
1475
    if (this->_lower_instr) {
1476
      tty->print("i%d", this->_lower_instr->id());
1477
      if (this->_lower > 0) {
1478
        tty->print("+%d", _lower);
1479
      }
1480
      if (this->_lower < 0) {
1481
        tty->print("%d", _lower);
1482
      }
1483
    } else {
1484
      tty->print("%d", _lower);
1485
    }
1486
    tty->print(" <= ");
1487
  }
1488
  tty->print("x");
1489
  if (this->_upper_instr || this->_upper != max_jint) {
1490
    tty->print(" <= ");
1491
    if (this->_upper_instr) {
1492
      tty->print("i%d", this->_upper_instr->id());
1493
      if (this->_upper > 0) {
1494
        tty->print("+%d", _upper);
1495
      }
1496
      if (this->_upper < 0) {
1497
        tty->print("%d", _upper);
1498
      }
1499
    } else {
1500
      tty->print("%d", _upper);
1501
    }
1502
  }
1503
}
1504

1505
// Copy
1506
RangeCheckEliminator::Bound *RangeCheckEliminator::Bound::copy() {
1507
  Bound *b = new Bound();
1508
  b->_lower = _lower;
1509
  b->_lower_instr = _lower_instr;
1510
  b->_upper = _upper;
1511
  b->_upper_instr = _upper_instr;
1512
  return b;
1513
}
1514

1515
#ifdef ASSERT
1516
// Add assertion
1517
void RangeCheckEliminator::Bound::add_assertion(Instruction *instruction, Instruction *position, int i, Value instr, Instruction::Condition cond) {
1518
  Instruction* result = position;
1519
  Instruction* compare_with = nullptr;
1520
  ValueStack* state = position->state_before();
1521
  if (position->as_BlockEnd() && !position->as_Goto()) {
1522
    state = position->as_BlockEnd()->state_before();
1523
  }
1524
  Instruction* instruction_before = position->prev();
1525
  if (position->as_Return() && Compilation::current()->method()->is_synchronized() && instruction_before->as_MonitorExit()) {
1526
    instruction_before = instruction_before->prev();
1527
  }
1528
  result = instruction_before;
1529
  // Load constant only if needed
1530
  Constant* constant = nullptr;
1531
  if (i != 0 || !instr) {
1532
    constant = new Constant(new IntConstant(i));
1533
    NOT_PRODUCT(constant->set_printable_bci(position->printable_bci()));
1534
    result = result->insert_after(constant);
1535
    compare_with = constant;
1536
  }
1537

1538
  if (instr) {
1539
    assert(instr->type()->as_ObjectType() || instr->type()->as_IntType(), "Type must be array or integer!");
1540
    compare_with = instr;
1541
    // Load array length if necessary
1542
    Instruction *op = instr;
1543
    if (instr->type()->as_ObjectType()) {
1544
      assert(state, "must not be null");
1545
      ArrayLength *length = new ArrayLength(instr, state->copy());
1546
      NOT_PRODUCT(length->set_printable_bci(position->printable_bci()));
1547
      length->set_exception_state(length->state_before());
1548
      result = result->insert_after(length);
1549
      op = length;
1550
      compare_with = length;
1551
    }
1552
    // Add operation only if necessary
1553
    if (constant) {
1554
      ArithmeticOp* ao = new ArithmeticOp(Bytecodes::_iadd, constant, op, nullptr);
1555
      NOT_PRODUCT(ao->set_printable_bci(position->printable_bci()));
1556
      result = result->insert_after(ao);
1557
      compare_with = ao;
1558
    }
1559
  }
1560
  assert(compare_with != nullptr, "You have to compare with something!");
1561
  assert(instruction != nullptr, "Instruction must not be null!");
1562

1563
  if (instruction->type()->as_ObjectType()) {
1564
    // Load array length if necessary
1565
    Instruction *op = instruction;
1566
    assert(state, "must not be null");
1567
    ArrayLength *length = new ArrayLength(instruction, state->copy());
1568
    length->set_exception_state(length->state_before());
1569
    NOT_PRODUCT(length->set_printable_bci(position->printable_bci()));
1570
    result = result->insert_after(length);
1571
    instruction = length;
1572
  }
1573

1574
  Assert *assert = new Assert(instruction, cond, false, compare_with);
1575
  NOT_PRODUCT(assert->set_printable_bci(position->printable_bci()));
1576
  result->insert_after(assert);
1577
}
1578

1579
// Add assertions
1580
void RangeCheckEliminator::add_assertions(Bound *bound, Instruction *instruction, Instruction *position) {
1581
  // Add lower bound assertion
1582
  if (bound->has_lower()) {
1583
    bound->add_assertion(instruction, position, bound->lower(), bound->lower_instr(), Instruction::geq);
1584
  }
1585
  // Add upper bound assertion
1586
  if (bound->has_upper()) {
1587
    bound->add_assertion(instruction, position, bound->upper(), bound->upper_instr(), Instruction::leq);
1588
  }
1589
}
1590
#endif
1591