hotspot/src/share/vm/c1/c1_RangeCheckElimination.cpp
author drchase
Fri, 09 May 2014 16:50:54 -0400
changeset 24424 2658d7834c6e
parent 22234 da823d78ad65
child 38031 e0b822facc03
permissions -rw-r--r--
8037816: Fix for 8036122 breaks build with Xcode5/clang Summary: Repaired or selectively disabled offending formats; future-proofed with additional checking Reviewed-by: kvn, jrose, stefank
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
16611
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
     1
/*
24424
2658d7834c6e 8037816: Fix for 8036122 breaks build with Xcode5/clang
drchase
parents: 22234
diff changeset
     2
 * Copyright (c) 2012, 2014, Oracle and/or its affiliates. All rights reserved.
16611
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
     3
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
     4
 *
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
     5
 * This code is free software; you can redistribute it and/or modify it
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
     6
 * under the terms of the GNU General Public License version 2 only, as
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
     7
 * published by the Free Software Foundation.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
     8
 *
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
     9
 * This code is distributed in the hope that it will be useful, but WITHOUT
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    10
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    11
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    12
 * version 2 for more details (a copy is included in the LICENSE file that
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    13
 * accompanied this code).
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    14
 *
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    15
 * You should have received a copy of the GNU General Public License version
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    16
 * 2 along with this work; if not, write to the Free Software Foundation,
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    17
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    18
 *
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    19
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    20
 * or visit www.oracle.com if you need additional information or have any
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    21
 * questions.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    22
 *
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    23
 */
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    24
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    25
#include "precompiled.hpp"
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    26
#include "c1/c1_ValueStack.hpp"
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    27
#include "c1/c1_RangeCheckElimination.hpp"
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    28
#include "c1/c1_IR.hpp"
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    29
#include "c1/c1_Canonicalizer.hpp"
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    30
#include "c1/c1_ValueMap.hpp"
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    31
#include "ci/ciMethodData.hpp"
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    32
#include "runtime/deoptimization.hpp"
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    33
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    34
// Macros for the Trace and the Assertion flag
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    35
#ifdef ASSERT
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    36
#define TRACE_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination) { code; }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    37
#define ASSERT_RANGE_CHECK_ELIMINATION(code) if (AssertRangeCheckElimination) { code; }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    38
#define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination || AssertRangeCheckElimination) { code; }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    39
#else
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    40
#define TRACE_RANGE_CHECK_ELIMINATION(code)
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    41
#define ASSERT_RANGE_CHECK_ELIMINATION(code)
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    42
#define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code)
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    43
#endif
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    44
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    45
// Entry point for the optimization
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    46
void RangeCheckElimination::eliminate(IR *ir) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    47
  bool do_elimination = ir->compilation()->has_access_indexed();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    48
  ASSERT_RANGE_CHECK_ELIMINATION(do_elimination = true);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    49
  if (do_elimination) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    50
    RangeCheckEliminator rce(ir);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    51
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    52
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    53
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    54
// Constructor
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    55
RangeCheckEliminator::RangeCheckEliminator(IR *ir) :
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    56
  _bounds(Instruction::number_of_instructions(), NULL),
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    57
  _access_indexed_info(Instruction::number_of_instructions(), NULL)
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    58
{
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    59
  _visitor.set_range_check_eliminator(this);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    60
  _ir = ir;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    61
  _number_of_instructions = Instruction::number_of_instructions();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    62
  _optimistic = ir->compilation()->is_optimistic();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    63
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    64
  TRACE_RANGE_CHECK_ELIMINATION(
24424
2658d7834c6e 8037816: Fix for 8036122 breaks build with Xcode5/clang
drchase
parents: 22234
diff changeset
    65
    tty->cr();
16611
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    66
    tty->print_cr("Range check elimination");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    67
    ir->method()->print_name(tty);
24424
2658d7834c6e 8037816: Fix for 8036122 breaks build with Xcode5/clang
drchase
parents: 22234
diff changeset
    68
    tty->cr();
16611
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    69
  );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    70
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    71
  TRACE_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    72
    tty->print_cr("optimistic=%d", (int)_optimistic);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    73
  );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    74
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    75
#ifdef ASSERT
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    76
  // Verifies several conditions that must be true on the IR-input. Only used for debugging purposes.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    77
  TRACE_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    78
    tty->print_cr("Verification of IR . . .");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    79
  );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    80
  Verification verification(ir);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    81
#endif
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    82
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    83
  // Set process block flags
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    84
  // Optimization so a blocks is only processed if it contains an access indexed instruction or if
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    85
  // one of its children in the dominator tree contains an access indexed instruction.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    86
  set_process_block_flags(ir->start());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    87
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    88
  // Pass over instructions in the dominator tree
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    89
  TRACE_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    90
    tty->print_cr("Starting pass over dominator tree . . .")
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    91
  );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    92
  calc_bounds(ir->start(), NULL);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    93
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    94
  TRACE_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    95
    tty->print_cr("Finished!")
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    96
  );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    97
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    98
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
    99
// Instruction specific work for some instructions
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   100
// Constant
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   101
void RangeCheckEliminator::Visitor::do_Constant(Constant *c) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   102
  IntConstant *ic = c->type()->as_IntConstant();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   103
  if (ic != NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   104
    int value = ic->value();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   105
    _bound = new Bound(value, NULL, value, NULL);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   106
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   107
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   108
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   109
// LogicOp
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   110
void RangeCheckEliminator::Visitor::do_LogicOp(LogicOp *lo) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   111
  if (lo->type()->as_IntType() && lo->op() == Bytecodes::_iand && (lo->x()->as_Constant() || lo->y()->as_Constant())) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   112
    int constant = 0;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   113
    Constant *c = lo->x()->as_Constant();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   114
    if (c != NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   115
      constant = c->type()->as_IntConstant()->value();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   116
    } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   117
      constant = lo->y()->as_Constant()->type()->as_IntConstant()->value();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   118
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   119
    if (constant >= 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   120
      _bound = new Bound(0, NULL, constant, NULL);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   121
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   122
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   123
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   124
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   125
// Phi
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   126
void RangeCheckEliminator::Visitor::do_Phi(Phi *phi) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   127
  if (!phi->type()->as_IntType() && !phi->type()->as_ObjectType()) return;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   128
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   129
  BlockBegin *block = phi->block();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   130
  int op_count = phi->operand_count();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   131
  bool has_upper = true;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   132
  bool has_lower = true;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   133
  assert(phi, "Phi must not be null");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   134
  Bound *bound = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   135
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   136
  // TODO: support more difficult phis
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   137
  for (int i=0; i<op_count; i++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   138
    Value v = phi->operand_at(i);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   139
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   140
    if (v == phi) continue;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   141
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   142
    // Check if instruction is connected with phi itself
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   143
    Op2 *op2 = v->as_Op2();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   144
    if (op2 != NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   145
      Value x = op2->x();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   146
      Value y = op2->y();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   147
      if ((x == phi || y == phi)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   148
        Value other = x;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   149
        if (other == phi) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   150
          other = y;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   151
        }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   152
        ArithmeticOp *ao = v->as_ArithmeticOp();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   153
        if (ao != NULL && ao->op() == Bytecodes::_iadd) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   154
          assert(ao->op() == Bytecodes::_iadd, "Has to be add!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   155
          if (ao->type()->as_IntType()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   156
            Constant *c = other->as_Constant();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   157
            if (c != NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   158
              assert(c->type()->as_IntConstant(), "Constant has to be of type integer");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   159
              int value = c->type()->as_IntConstant()->value();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   160
              if (value == 1) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   161
                has_upper = false;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   162
              } else if (value > 1) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   163
                // Overflow not guaranteed
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   164
                has_upper = false;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   165
                has_lower = false;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   166
              } else if (value < 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   167
                has_lower = false;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   168
              }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   169
              continue;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   170
            }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   171
          }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   172
        }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   173
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   174
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   175
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   176
    // No connection -> new bound
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   177
    Bound *v_bound = _rce->get_bound(v);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   178
    Bound *cur_bound;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   179
    int cur_constant = 0;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   180
    Value cur_value = v;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   181
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   182
    if (v->type()->as_IntConstant()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   183
      cur_constant = v->type()->as_IntConstant()->value();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   184
      cur_value = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   185
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   186
    if (!v_bound->has_upper() || !v_bound->has_lower()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   187
      cur_bound = new Bound(cur_constant, cur_value, cur_constant, cur_value);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   188
    } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   189
      cur_bound = v_bound;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   190
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   191
    if (cur_bound) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   192
      if (!bound) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   193
        bound = cur_bound->copy();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   194
      } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   195
        bound->or_op(cur_bound);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   196
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   197
    } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   198
      // No bound!
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   199
      bound = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   200
      break;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   201
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   202
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   203
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   204
  if (bound) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   205
    if (!has_upper) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   206
      bound->remove_upper();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   207
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   208
    if (!has_lower) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   209
      bound->remove_lower();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   210
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   211
    _bound = bound;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   212
  } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   213
    _bound = new Bound();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   214
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   215
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   216
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   217
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   218
// ArithmeticOp
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   219
void RangeCheckEliminator::Visitor::do_ArithmeticOp(ArithmeticOp *ao) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   220
  Value x = ao->x();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   221
  Value y = ao->y();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   222
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   223
  if (ao->op() == Bytecodes::_irem) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   224
    Bound* x_bound = _rce->get_bound(x);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   225
    Bound* y_bound = _rce->get_bound(y);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   226
    if (x_bound->lower() >= 0 && x_bound->lower_instr() == NULL && y->as_ArrayLength() != NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   227
      _bound = new Bound(0, NULL, -1, y);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   228
    } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   229
      _bound = new Bound();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   230
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   231
  } else if (!x->as_Constant() || !y->as_Constant()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   232
    assert(!x->as_Constant() || !y->as_Constant(), "One of the operands must be non-constant!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   233
    if (((x->as_Constant() || y->as_Constant()) && (ao->op() == Bytecodes::_iadd)) || (y->as_Constant() && ao->op() == Bytecodes::_isub)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   234
      assert(ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub, "Operand must be iadd or isub");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   235
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   236
      if (y->as_Constant()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   237
        Value tmp = x;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   238
        x = y;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   239
        y = tmp;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   240
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   241
      assert(x->as_Constant()->type()->as_IntConstant(), "Constant must be int constant!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   242
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   243
      // Constant now in x
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   244
      int const_value = x->as_Constant()->type()->as_IntConstant()->value();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   245
      if (ao->op() == Bytecodes::_iadd || const_value != min_jint) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   246
        if (ao->op() == Bytecodes::_isub) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   247
          const_value = -const_value;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   248
        }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   249
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   250
        Bound * bound = _rce->get_bound(y);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   251
        if (bound->has_upper() && bound->has_lower()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   252
          int new_lower = bound->lower() + const_value;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   253
          jlong new_lowerl = ((jlong)bound->lower()) + const_value;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   254
          int new_upper = bound->upper() + const_value;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   255
          jlong new_upperl = ((jlong)bound->upper()) + const_value;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   256
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   257
          if (((jlong)new_lower) == new_lowerl && ((jlong)new_upper == new_upperl)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   258
            Bound *newBound = new Bound(new_lower, bound->lower_instr(), new_upper, bound->upper_instr());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   259
            _bound = newBound;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   260
          } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   261
            // overflow
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   262
            _bound = new Bound();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   263
          }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   264
        } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   265
          _bound = new Bound();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   266
        }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   267
      } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   268
        _bound = new Bound();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   269
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   270
    } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   271
      Bound *bound = _rce->get_bound(x);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   272
      if (ao->op() == Bytecodes::_isub) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   273
        if (bound->lower_instr() == y) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   274
          _bound = new Bound(Instruction::geq, NULL, bound->lower());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   275
        } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   276
          _bound = new Bound();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   277
        }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   278
      } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   279
        _bound = new Bound();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   280
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   281
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   282
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   283
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   284
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   285
// IfOp
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   286
void RangeCheckEliminator::Visitor::do_IfOp(IfOp *ifOp)
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   287
{
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   288
  if (ifOp->tval()->type()->as_IntConstant() && ifOp->fval()->type()->as_IntConstant()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   289
    int min = ifOp->tval()->type()->as_IntConstant()->value();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   290
    int max = ifOp->fval()->type()->as_IntConstant()->value();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   291
    if (min > max) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   292
      // min ^= max ^= min ^= max;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   293
      int tmp = min;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   294
      min = max;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   295
      max = tmp;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   296
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   297
    _bound = new Bound(min, NULL, max, NULL);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   298
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   299
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   300
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   301
// Get bound. Returns the current bound on Value v. Normally this is the topmost element on the bound stack.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   302
RangeCheckEliminator::Bound *RangeCheckEliminator::get_bound(Value v) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   303
  // Wrong type or NULL -> No bound
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   304
  if (!v || (!v->type()->as_IntType() && !v->type()->as_ObjectType())) return NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   305
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   306
  if (!_bounds[v->id()]) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   307
    // First (default) bound is calculated
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   308
    // Create BoundStack
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   309
    _bounds[v->id()] = new BoundStack();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   310
    _visitor.clear_bound();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   311
    Value visit_value = v;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   312
    visit_value->visit(&_visitor);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   313
    Bound *bound = _visitor.bound();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   314
    if (bound) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   315
      _bounds[v->id()]->push(bound);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   316
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   317
    if (_bounds[v->id()]->length() == 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   318
      assert(!(v->as_Constant() && v->type()->as_IntConstant()), "constants not handled here");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   319
      _bounds[v->id()]->push(new Bound());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   320
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   321
  } else if (_bounds[v->id()]->length() == 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   322
    // To avoid endless loops, bound is currently in calculation -> nothing known about it
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   323
    return new Bound();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   324
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   325
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   326
  // Return bound
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   327
  return _bounds[v->id()]->top();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   328
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   329
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   330
// Update bound
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   331
void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Instruction::Condition cond, Value value, int constant) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   332
  if (cond == Instruction::gtr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   333
    cond = Instruction::geq;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   334
    constant++;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   335
  } else if (cond == Instruction::lss) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   336
    cond = Instruction::leq;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   337
    constant--;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   338
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   339
  Bound *bound = new Bound(cond, value, constant);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   340
  update_bound(pushed, v, bound);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   341
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   342
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   343
// Checks for loop invariance. Returns true if the instruction is outside of the loop which is identified by loop_header.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   344
bool RangeCheckEliminator::loop_invariant(BlockBegin *loop_header, Instruction *instruction) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   345
  assert(loop_header, "Loop header must not be null!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   346
  if (!instruction) return true;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   347
  return instruction->dominator_depth() < loop_header->dominator_depth();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   348
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   349
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   350
// Update bound. Pushes a new bound onto the stack. Tries to do a conjunction with the current bound.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   351
void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Bound *bound) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   352
  if (v->as_Constant()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   353
    // No bound update for constants
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   354
    return;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   355
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   356
  if (!_bounds[v->id()]) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   357
    get_bound(v);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   358
    assert(_bounds[v->id()], "Now Stack must exist");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   359
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   360
  Bound *top = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   361
  if (_bounds[v->id()]->length() > 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   362
    top = _bounds[v->id()]->top();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   363
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   364
  if (top) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   365
    bound->and_op(top);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   366
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   367
  _bounds[v->id()]->push(bound);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   368
  pushed.append(v->id());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   369
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   370
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   371
// Add instruction + idx for in block motion
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   372
void RangeCheckEliminator::add_access_indexed_info(InstructionList &indices, int idx, Value instruction, AccessIndexed *ai) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   373
  int id = instruction->id();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   374
  AccessIndexedInfo *aii = _access_indexed_info[id];
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   375
  if (aii == NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   376
    aii = new AccessIndexedInfo();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   377
    _access_indexed_info[id] = aii;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   378
    indices.append(instruction);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   379
    aii->_min = idx;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   380
    aii->_max = idx;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   381
    aii->_list = new AccessIndexedList();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   382
  } else if (idx >= aii->_min && idx <= aii->_max) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   383
    remove_range_check(ai);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   384
    return;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   385
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   386
  aii->_min = MIN2(aii->_min, idx);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   387
  aii->_max = MAX2(aii->_max, idx);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   388
  aii->_list->append(ai);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   389
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   390
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   391
// In block motion. Tries to reorder checks in order to reduce some of them.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   392
// Example:
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   393
// a[i] = 0;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   394
// a[i+2] = 0;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   395
// a[i+1] = 0;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   396
// In this example the check for a[i+1] would be considered as unnecessary during the first iteration.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   397
// After this i is only checked once for i >= 0 and i+2 < a.length before the first array access. If this
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   398
// check fails, deoptimization is called.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   399
void RangeCheckEliminator::in_block_motion(BlockBegin *block, AccessIndexedList &accessIndexed, InstructionList &arrays) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   400
  InstructionList indices;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   401
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   402
  // Now iterate over all arrays
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   403
  for (int i=0; i<arrays.length(); i++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   404
    int max_constant = -1;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   405
    AccessIndexedList list_constant;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   406
    Value array = arrays.at(i);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   407
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   408
    // For all AccessIndexed-instructions in this block concerning the current array.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   409
    for(int j=0; j<accessIndexed.length(); j++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   410
      AccessIndexed *ai = accessIndexed.at(j);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   411
      if (ai->array() != array || !ai->check_flag(Instruction::NeedsRangeCheckFlag)) continue;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   412
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   413
      Value index = ai->index();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   414
      Constant *c = index->as_Constant();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   415
      if (c != NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   416
        int constant_value = c->type()->as_IntConstant()->value();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   417
        if (constant_value >= 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   418
          if (constant_value <= max_constant) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   419
            // No range check needed for this
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   420
            remove_range_check(ai);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   421
          } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   422
            max_constant = constant_value;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   423
            list_constant.append(ai);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   424
          }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   425
        }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   426
      } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   427
        int last_integer = 0;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   428
        Instruction *last_instruction = index;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   429
        int base = 0;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   430
        ArithmeticOp *ao = index->as_ArithmeticOp();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   431
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   432
        while (ao != NULL && (ao->x()->as_Constant() || ao->y()->as_Constant()) && (ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   433
          c = ao->y()->as_Constant();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   434
          Instruction *other = ao->x();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   435
          if (!c && ao->op() == Bytecodes::_iadd) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   436
            c = ao->x()->as_Constant();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   437
            other = ao->y();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   438
          }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   439
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   440
          if (c) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   441
            int value = c->type()->as_IntConstant()->value();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   442
            if (value != min_jint) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   443
              if (ao->op() == Bytecodes::_isub) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   444
                value = -value;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   445
              }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   446
              base += value;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   447
              last_integer = base;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   448
              last_instruction = other;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   449
            }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   450
            index = other;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   451
          } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   452
            break;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   453
          }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   454
          ao = index->as_ArithmeticOp();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   455
        }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   456
        add_access_indexed_info(indices, last_integer, last_instruction, ai);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   457
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   458
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   459
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   460
    // Iterate over all different indices
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   461
    if (_optimistic) {
17036
4818f717d362 8011771: runThese crashed with EAV
roland
parents: 16620
diff changeset
   462
      for (int i = 0; i < indices.length(); i++) {
16611
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   463
        Instruction *index_instruction = indices.at(i);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   464
        AccessIndexedInfo *info = _access_indexed_info[index_instruction->id()];
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   465
        assert(info != NULL, "Info must not be null");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   466
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   467
        // if idx < 0, max > 0, max + idx may fall between 0 and
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   468
        // length-1 and if min < 0, min + idx may overflow and be >=
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   469
        // 0. The predicate wouldn't trigger but some accesses could
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   470
        // be with a negative index. This test guarantees that for the
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   471
        // min and max value that are kept the predicate can't let
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   472
        // some incorrect accesses happen.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   473
        bool range_cond = (info->_max < 0 || info->_max + min_jint <= info->_min);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   474
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   475
        // Generate code only if more than 2 range checks can be eliminated because of that.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   476
        // 2 because at least 2 comparisons are done
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   477
        if (info->_list->length() > 2 && range_cond) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   478
          AccessIndexed *first = info->_list->at(0);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   479
          Instruction *insert_position = first->prev();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   480
          assert(insert_position->next() == first, "prev was calculated");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   481
          ValueStack *state = first->state_before();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   482
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   483
          // Load min Constant
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   484
          Constant *min_constant = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   485
          if (info->_min != 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   486
            min_constant = new Constant(new IntConstant(info->_min));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   487
            NOT_PRODUCT(min_constant->set_printable_bci(first->printable_bci()));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   488
            insert_position = insert_position->insert_after(min_constant);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   489
          }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   490
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   491
          // Load max Constant
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   492
          Constant *max_constant = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   493
          if (info->_max != 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   494
            max_constant = new Constant(new IntConstant(info->_max));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   495
            NOT_PRODUCT(max_constant->set_printable_bci(first->printable_bci()));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   496
            insert_position = insert_position->insert_after(max_constant);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   497
          }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   498
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   499
          // Load array length
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   500
          Value length_instr = first->length();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   501
          if (!length_instr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   502
            ArrayLength *length = new ArrayLength(array, first->state_before()->copy());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   503
            length->set_exception_state(length->state_before());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   504
            length->set_flag(Instruction::DeoptimizeOnException, true);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   505
            insert_position = insert_position->insert_after_same_bci(length);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   506
            length_instr = length;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   507
          }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   508
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   509
          // Calculate lower bound
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   510
          Instruction *lower_compare = index_instruction;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   511
          if (min_constant) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   512
            ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, min_constant, lower_compare, false, NULL);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   513
            insert_position = insert_position->insert_after_same_bci(ao);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   514
            lower_compare = ao;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   515
          }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   516
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   517
          // Calculate upper bound
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   518
          Instruction *upper_compare = index_instruction;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   519
          if (max_constant) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   520
            ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, max_constant, upper_compare, false, NULL);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   521
            insert_position = insert_position->insert_after_same_bci(ao);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   522
            upper_compare = ao;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   523
          }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   524
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   525
          // Trick with unsigned compare is done
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   526
          int bci = NOT_PRODUCT(first->printable_bci()) PRODUCT_ONLY(-1);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   527
          insert_position = predicate(upper_compare, Instruction::aeq, length_instr, state, insert_position, bci);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   528
          insert_position = predicate_cmp_with_const(lower_compare, Instruction::leq, -1, state, insert_position);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   529
          for (int j = 0; j<info->_list->length(); j++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   530
            AccessIndexed *ai = info->_list->at(j);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   531
            remove_range_check(ai);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   532
          }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   533
        }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   534
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   535
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   536
      if (list_constant.length() > 1) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   537
        AccessIndexed *first = list_constant.at(0);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   538
        Instruction *insert_position = first->prev();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   539
        ValueStack *state = first->state_before();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   540
        // Load max Constant
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   541
        Constant *constant = new Constant(new IntConstant(max_constant));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   542
        NOT_PRODUCT(constant->set_printable_bci(first->printable_bci()));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   543
        insert_position = insert_position->insert_after(constant);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   544
        Instruction *compare_instr = constant;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   545
        Value length_instr = first->length();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   546
        if (!length_instr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   547
          ArrayLength *length = new ArrayLength(array, state->copy());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   548
          length->set_exception_state(length->state_before());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   549
          length->set_flag(Instruction::DeoptimizeOnException, true);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   550
          insert_position = insert_position->insert_after_same_bci(length);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   551
          length_instr = length;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   552
        }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   553
        // Compare for greater or equal to array length
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   554
        insert_position = predicate(compare_instr, Instruction::geq, length_instr, state, insert_position);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   555
        for (int j = 0; j<list_constant.length(); j++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   556
          AccessIndexed *ai = list_constant.at(j);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   557
          remove_range_check(ai);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   558
        }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   559
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   560
    }
17036
4818f717d362 8011771: runThese crashed with EAV
roland
parents: 16620
diff changeset
   561
4818f717d362 8011771: runThese crashed with EAV
roland
parents: 16620
diff changeset
   562
    // Clear data structures for next array
4818f717d362 8011771: runThese crashed with EAV
roland
parents: 16620
diff changeset
   563
    for (int i = 0; i < indices.length(); i++) {
4818f717d362 8011771: runThese crashed with EAV
roland
parents: 16620
diff changeset
   564
      Instruction *index_instruction = indices.at(i);
4818f717d362 8011771: runThese crashed with EAV
roland
parents: 16620
diff changeset
   565
      _access_indexed_info[index_instruction->id()] = NULL;
4818f717d362 8011771: runThese crashed with EAV
roland
parents: 16620
diff changeset
   566
    }
4818f717d362 8011771: runThese crashed with EAV
roland
parents: 16620
diff changeset
   567
    indices.clear();
16611
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   568
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   569
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   570
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   571
bool RangeCheckEliminator::set_process_block_flags(BlockBegin *block) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   572
  Instruction *cur = block;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   573
  bool process = false;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   574
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   575
  while (cur) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   576
    process |= (cur->as_AccessIndexed() != NULL);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   577
    cur = cur->next();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   578
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   579
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   580
  BlockList *dominates = block->dominates();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   581
  for (int i=0; i<dominates->length(); i++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   582
    BlockBegin *next = dominates->at(i);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   583
    process |= set_process_block_flags(next);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   584
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   585
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   586
  if (!process) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   587
    block->set(BlockBegin::donot_eliminate_range_checks);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   588
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   589
  return process;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   590
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   591
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   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) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   593
  bool upper_check = true;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   594
  assert(lower_instr || lower >= 0, "If no lower_instr present, lower must be greater 0");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   595
  assert(!lower_instr || lower_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   596
  assert(!upper_instr || upper_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   597
  assert(array_instr, "Array instruction must exist");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   598
  assert(array_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   599
  assert(!length_instr || length_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   600
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   601
  if (upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   602
    // static check
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   603
    if (upper >= 0) return false; // would always trigger a deopt:
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   604
                                  // array_length + x >= array_length, x >= 0 is always true
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   605
    upper_check = false;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   606
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   607
  if (lower_instr && lower_instr->as_ArrayLength() && lower_instr->as_ArrayLength()->array() == array_instr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   608
    if (lower > 0) return false;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   609
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   610
  // No upper check required -> skip
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   611
  if (upper_check && upper_instr && upper_instr->type()->as_ObjectType() && upper_instr == array_instr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   612
    // upper_instr is object means that the upper bound is the length
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   613
    // of the upper_instr.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   614
    return false;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   615
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   616
  return true;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   617
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   618
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   619
Instruction* RangeCheckEliminator::insert_after(Instruction* insert_position, Instruction* instr, int bci) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   620
  if (bci != -1) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   621
    NOT_PRODUCT(instr->set_printable_bci(bci));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   622
    return insert_position->insert_after(instr);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   623
  } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   624
    return insert_position->insert_after_same_bci(instr);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   625
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   626
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   627
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   628
Instruction* RangeCheckEliminator::predicate(Instruction* left, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   629
  RangeCheckPredicate *deoptimize = new RangeCheckPredicate(left, cond, true, right, state->copy());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   630
  return insert_after(insert_position, deoptimize, bci);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   631
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   632
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   633
Instruction* RangeCheckEliminator::predicate_cmp_with_const(Instruction* instr, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   634
  Constant *const_instr = new Constant(new IntConstant(constant));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   635
  insert_position = insert_after(insert_position, const_instr, bci);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   636
  return predicate(instr, cond, const_instr, state, insert_position);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   637
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   638
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   639
Instruction* RangeCheckEliminator::predicate_add(Instruction* left, int left_const, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   640
  Constant *constant = new Constant(new IntConstant(left_const));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   641
  insert_position = insert_after(insert_position, constant, bci);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   642
  ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, left, false, NULL);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   643
  insert_position = insert_position->insert_after_same_bci(ao);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   644
  return predicate(ao, cond, right, state, insert_position);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   645
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   646
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   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) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   648
  Constant *const_instr = new Constant(new IntConstant(constant));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   649
  insert_position = insert_after(insert_position, const_instr, bci);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   650
  return predicate_add(left, left_const, cond, const_instr, state, insert_position);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   651
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   652
16620
294771974de2 8010934: assert failure in c1_LinearScan.cpp: "asumption: non-Constant instructions have only virtual operands"
roland
parents: 16611
diff changeset
   653
// Insert deoptimization
16611
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   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) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   655
  assert(is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, lower, upper_instr, upper), "should have been tested before");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   656
  bool upper_check = !(upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   657
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   658
  int bci = NOT_PRODUCT(ai->printable_bci()) PRODUCT_ONLY(-1);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   659
  if (lower_instr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   660
    assert(!lower_instr->type()->as_ObjectType(), "Must not be object type");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   661
    if (lower == 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   662
      // Compare for less than 0
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   663
      insert_position = predicate_cmp_with_const(lower_instr, Instruction::lss, 0, state, insert_position, bci);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   664
    } else if (lower > 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   665
      // Compare for smaller 0
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   666
      insert_position = predicate_add_cmp_with_const(lower_instr, lower, Instruction::lss, 0, state, insert_position, bci);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   667
    } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   668
      assert(lower < 0, "");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   669
      // Add 1
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   670
      lower++;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   671
      lower = -lower;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   672
      // Compare for smaller or equal 0
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   673
      insert_position = predicate_cmp_with_const(lower_instr, Instruction::leq, lower, state, insert_position, bci);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   674
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   675
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   676
16620
294771974de2 8010934: assert failure in c1_LinearScan.cpp: "asumption: non-Constant instructions have only virtual operands"
roland
parents: 16611
diff changeset
   677
  // No upper check required -> skip
294771974de2 8010934: assert failure in c1_LinearScan.cpp: "asumption: non-Constant instructions have only virtual operands"
roland
parents: 16611
diff changeset
   678
  if (!upper_check) return;
294771974de2 8010934: assert failure in c1_LinearScan.cpp: "asumption: non-Constant instructions have only virtual operands"
roland
parents: 16611
diff changeset
   679
16611
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   680
  // We need to know length of array
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   681
  if (!length_instr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   682
    // Load length if necessary
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   683
    ArrayLength *length = new ArrayLength(array_instr, state->copy());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   684
    NOT_PRODUCT(length->set_printable_bci(ai->printable_bci()));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   685
    length->set_exception_state(length->state_before());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   686
    length->set_flag(Instruction::DeoptimizeOnException, true);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   687
    insert_position = insert_position->insert_after(length);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   688
    length_instr = length;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   689
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   690
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   691
  if (!upper_instr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   692
    // Compare for geq array.length
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   693
    insert_position = predicate_cmp_with_const(length_instr, Instruction::leq, upper, state, insert_position, bci);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   694
  } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   695
    if (upper_instr->type()->as_ObjectType()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   696
      assert(state, "must not be null");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   697
      assert(upper_instr != array_instr, "should be");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   698
      ArrayLength *length = new ArrayLength(upper_instr, state->copy());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   699
      NOT_PRODUCT(length->set_printable_bci(ai->printable_bci()));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   700
      length->set_flag(Instruction::DeoptimizeOnException, true);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   701
      length->set_exception_state(length->state_before());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   702
      insert_position = insert_position->insert_after(length);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   703
      upper_instr = length;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   704
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   705
    assert(upper_instr->type()->as_IntType(), "Must not be object type!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   706
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   707
    if (upper == 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   708
      // Compare for geq array.length
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   709
      insert_position = predicate(upper_instr, Instruction::geq, length_instr, state, insert_position, bci);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   710
    } else if (upper < 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   711
      // Compare for geq array.length
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   712
      insert_position = predicate_add(upper_instr, upper, Instruction::geq, length_instr, state, insert_position, bci);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   713
    } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   714
      assert(upper > 0, "");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   715
      upper = -upper;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   716
      // Compare for geq array.length
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   717
      insert_position = predicate_add(length_instr, upper, Instruction::leq, upper_instr, state, insert_position, bci);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   718
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   719
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   720
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   721
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   722
// Add if condition
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   723
void RangeCheckEliminator::add_if_condition(IntegerStack &pushed, Value x, Value y, Instruction::Condition condition) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   724
  if (y->as_Constant()) return;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   725
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   726
  int const_value = 0;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   727
  Value instr_value = x;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   728
  Constant *c = x->as_Constant();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   729
  ArithmeticOp *ao = x->as_ArithmeticOp();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   730
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   731
  if (c != NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   732
    const_value = c->type()->as_IntConstant()->value();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   733
    instr_value = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   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)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   735
    assert(!ao->x()->as_Constant() || !ao->y()->as_Constant(), "At least one operator must be non-constant!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   736
    assert(ao->op() == Bytecodes::_isub || ao->op() == Bytecodes::_iadd, "Operation has to be add or sub!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   737
    c = ao->x()->as_Constant();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   738
    if (c != NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   739
      const_value = c->type()->as_IntConstant()->value();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   740
      instr_value = ao->y();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   741
    } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   742
      c = ao->y()->as_Constant();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   743
      if (c != NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   744
        const_value = c->type()->as_IntConstant()->value();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   745
        instr_value = ao->x();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   746
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   747
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   748
    if (ao->op() == Bytecodes::_isub) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   749
      assert(ao->y()->as_Constant(), "1 - x not supported, only x - 1 is valid!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   750
      if (const_value > min_jint) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   751
        const_value = -const_value;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   752
      } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   753
        const_value = 0;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   754
        instr_value = x;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   755
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   756
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   757
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   758
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   759
  update_bound(pushed, y, condition, instr_value, const_value);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   760
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   761
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   762
// Process If
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   763
void RangeCheckEliminator::process_if(IntegerStack &pushed, BlockBegin *block, If *cond) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   764
  // Only if we are direct true / false successor and NOT both ! (even this may occur)
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   765
  if ((cond->tsux() == block || cond->fsux() == block) && cond->tsux() != cond->fsux()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   766
    Instruction::Condition condition = cond->cond();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   767
    if (cond->fsux() == block) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   768
      condition = Instruction::negate(condition);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   769
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   770
    Value x = cond->x();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   771
    Value y = cond->y();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   772
    if (x->type()->as_IntType() && y->type()->as_IntType()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   773
      add_if_condition(pushed, y, x, condition);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   774
      add_if_condition(pushed, x, y, Instruction::mirror(condition));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   775
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   776
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   777
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   778
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   779
// Process access indexed
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   780
void RangeCheckEliminator::process_access_indexed(BlockBegin *loop_header, BlockBegin *block, AccessIndexed *ai) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   781
  TRACE_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   782
    tty->fill_to(block->dominator_depth()*2)
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   783
  );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   784
  TRACE_RANGE_CHECK_ELIMINATION(
16620
294771974de2 8010934: assert failure in c1_LinearScan.cpp: "asumption: non-Constant instructions have only virtual operands"
roland
parents: 16611
diff changeset
   785
    tty->print_cr("Access indexed: index=%d length=%d", ai->index()->id(), (ai->length() != NULL ? ai->length()->id() :-1 ))
16611
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   786
  );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   787
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   788
  if (ai->check_flag(Instruction::NeedsRangeCheckFlag)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   789
    Bound *index_bound = get_bound(ai->index());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   790
    if (!index_bound->has_lower() || !index_bound->has_upper()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   791
      TRACE_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   792
        tty->fill_to(block->dominator_depth()*2);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   793
        tty->print_cr("Index instruction %d has no lower and/or no upper bound!", ai->index()->id())
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   794
      );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   795
      return;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   796
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   797
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   798
    Bound *array_bound;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   799
    if (ai->length()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   800
      array_bound = get_bound(ai->length());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   801
    } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   802
      array_bound = get_bound(ai->array());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   803
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   804
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   805
    if (in_array_bound(index_bound, ai->array()) ||
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   806
      (index_bound && array_bound && index_bound->is_smaller(array_bound) && !index_bound->lower_instr() && index_bound->lower() >= 0)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   807
        TRACE_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   808
          tty->fill_to(block->dominator_depth()*2);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   809
          tty->print_cr("Bounds check for instruction %d in block B%d can be fully eliminated!", ai->id(), ai->block()->block_id())
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   810
        );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   811
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   812
        remove_range_check(ai);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   813
    } else if (_optimistic && loop_header) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   814
      assert(ai->array(), "Array must not be null!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   815
      assert(ai->index(), "Index must not be null!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   816
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   817
      // Array instruction
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   818
      Instruction *array_instr = ai->array();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   819
      if (!loop_invariant(loop_header, array_instr)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   820
        TRACE_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   821
          tty->fill_to(block->dominator_depth()*2);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   822
          tty->print_cr("Array %d is not loop invariant to header B%d", ai->array()->id(), loop_header->block_id())
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   823
        );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   824
        return;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   825
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   826
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   827
      // Lower instruction
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   828
      Value index_instr = ai->index();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   829
      Value lower_instr = index_bound->lower_instr();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   830
      if (!loop_invariant(loop_header, lower_instr)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   831
        TRACE_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   832
          tty->fill_to(block->dominator_depth()*2);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   833
          tty->print_cr("Lower instruction %d not loop invariant!", lower_instr->id())
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   834
        );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   835
        return;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   836
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   837
      if (!lower_instr && index_bound->lower() < 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   838
        TRACE_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   839
          tty->fill_to(block->dominator_depth()*2);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   840
          tty->print_cr("Lower bound smaller than 0 (%d)!", index_bound->lower())
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   841
        );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   842
        return;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   843
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   844
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   845
      // Upper instruction
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   846
      Value upper_instr = index_bound->upper_instr();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   847
      if (!loop_invariant(loop_header, upper_instr)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   848
        TRACE_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   849
          tty->fill_to(block->dominator_depth()*2);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   850
          tty->print_cr("Upper instruction %d not loop invariant!", upper_instr->id())
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   851
        );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   852
        return;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   853
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   854
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   855
      // Length instruction
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   856
      Value length_instr = ai->length();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   857
      if (!loop_invariant(loop_header, length_instr)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   858
        // Generate length instruction yourself!
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   859
        length_instr = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   860
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   861
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   862
      TRACE_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   863
        tty->fill_to(block->dominator_depth()*2);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   864
        tty->print_cr("LOOP INVARIANT access indexed %d found in block B%d!", ai->id(), ai->block()->block_id())
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   865
      );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   866
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   867
      BlockBegin *pred_block = loop_header->dominator();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   868
      assert(pred_block != NULL, "Every loop header has a dominator!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   869
      BlockEnd *pred_block_end = pred_block->end();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   870
      Instruction *insert_position = pred_block_end->prev();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   871
      ValueStack *state = pred_block_end->state_before();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   872
      if (pred_block_end->as_Goto() && state == NULL) state = pred_block_end->state();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   873
      assert(state, "State must not be null");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   874
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   875
      // Add deoptimization to dominator of loop header
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   876
      TRACE_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   877
        tty->fill_to(block->dominator_depth()*2);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   878
        tty->print_cr("Inserting deopt at bci %d in block B%d!", state->bci(), insert_position->block()->block_id())
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   879
      );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   880
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   881
      if (!is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper())) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   882
        TRACE_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   883
          tty->fill_to(block->dominator_depth()*2);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   884
          tty->print_cr("Could not eliminate because of static analysis!")
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   885
        );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   886
        return;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   887
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   888
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   889
      insert_deoptimization(state, insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper(), ai);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   890
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   891
      // Finally remove the range check!
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   892
      remove_range_check(ai);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   893
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   894
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   895
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   896
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   897
void RangeCheckEliminator::remove_range_check(AccessIndexed *ai) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   898
  ai->set_flag(Instruction::NeedsRangeCheckFlag, false);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   899
  // no range check, no need for the length instruction anymore
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   900
  ai->clear_length();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   901
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   902
  TRACE_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   903
    tty->fill_to(ai->dominator_depth()*2);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   904
    tty->print_cr("Range check for instruction %d eliminated!", ai->id());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   905
  );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   906
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   907
  ASSERT_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   908
    Value array_length = ai->length();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   909
    if (!array_length) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   910
      array_length = ai->array();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   911
      assert(array_length->type()->as_ObjectType(), "Has to be object type!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   912
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   913
    int cur_constant = -1;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   914
    Value cur_value = array_length;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   915
    if (cur_value->type()->as_IntConstant()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   916
      cur_constant += cur_value->type()->as_IntConstant()->value();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   917
      cur_value = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   918
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   919
    Bound *new_index_bound = new Bound(0, NULL, cur_constant, cur_value);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   920
    add_assertions(new_index_bound, ai->index(), ai);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   921
  );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   922
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   923
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   924
// Calculate bounds for instruction in this block and children blocks in the dominator tree
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   925
void RangeCheckEliminator::calc_bounds(BlockBegin *block, BlockBegin *loop_header) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   926
  // Ensures a valid loop_header
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   927
  assert(!loop_header || loop_header->is_set(BlockBegin::linear_scan_loop_header_flag), "Loop header has to be real !");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   928
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   929
  // Tracing output
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   930
  TRACE_RANGE_CHECK_ELIMINATION(
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   931
    tty->fill_to(block->dominator_depth()*2);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   932
    tty->print_cr("Block B%d", block->block_id());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   933
  );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   934
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   935
  // Pushed stack for conditions
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   936
  IntegerStack pushed;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   937
  // Process If
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   938
  BlockBegin *parent = block->dominator();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   939
  if (parent != NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   940
    If *cond = parent->end()->as_If();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   941
    if (cond != NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   942
      process_if(pushed, block, cond);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   943
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   944
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   945
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   946
  // Interate over current block
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   947
  InstructionList arrays;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   948
  AccessIndexedList accessIndexed;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   949
  Instruction *cur = block;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   950
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   951
  while (cur) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   952
    // Ensure cur wasn't inserted during the elimination
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   953
    if (cur->id() < this->_bounds.length()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   954
      // Process only if it is an access indexed instruction
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   955
      AccessIndexed *ai = cur->as_AccessIndexed();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   956
      if (ai != NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   957
        process_access_indexed(loop_header, block, ai);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   958
        accessIndexed.append(ai);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   959
        if (!arrays.contains(ai->array())) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   960
          arrays.append(ai->array());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   961
        }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   962
        Bound *b = get_bound(ai->index());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   963
        if (!b->lower_instr()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   964
          // Lower bound is constant
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   965
          update_bound(pushed, ai->index(), Instruction::geq, NULL, 0);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   966
        }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   967
        if (!b->has_upper()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   968
          if (ai->length() && ai->length()->type()->as_IntConstant()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   969
            int value = ai->length()->type()->as_IntConstant()->value();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   970
            update_bound(pushed, ai->index(), Instruction::lss, NULL, value);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   971
          } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   972
            // Has no upper bound
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   973
            Instruction *instr = ai->length();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   974
            if (instr != NULL) instr = ai->array();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   975
            update_bound(pushed, ai->index(), Instruction::lss, instr, 0);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   976
          }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   977
        }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   978
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   979
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   980
    cur = cur->next();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   981
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   982
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   983
  // Output current condition stack
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   984
  TRACE_RANGE_CHECK_ELIMINATION(dump_condition_stack(block));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   985
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   986
  // Do in block motion of range checks
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   987
  in_block_motion(block, accessIndexed, arrays);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   988
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   989
  // Call all dominated blocks
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   990
  for (int i=0; i<block->dominates()->length(); i++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   991
    BlockBegin *next = block->dominates()->at(i);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   992
    if (!next->is_set(BlockBegin::donot_eliminate_range_checks)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   993
      // if current block is a loop header and:
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   994
      // - next block belongs to the same loop
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   995
      // or
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   996
      // - next block belongs to an inner loop
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   997
      // then current block is the loop header for next block
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   998
      if (block->is_set(BlockBegin::linear_scan_loop_header_flag) && (block->loop_index() == next->loop_index() || next->loop_depth() > block->loop_depth())) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
   999
        calc_bounds(next, block);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1000
      } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1001
        calc_bounds(next, loop_header);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1002
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1003
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1004
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1005
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1006
  // Reset stack
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1007
  for (int i=0; i<pushed.length(); i++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1008
    _bounds[pushed[i]]->pop();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1009
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1010
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1011
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1012
#ifndef PRODUCT
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1013
// Dump condition stack
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1014
void RangeCheckEliminator::dump_condition_stack(BlockBegin *block) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1015
  for (int i=0; i<_ir->linear_scan_order()->length(); i++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1016
    BlockBegin *cur_block = _ir->linear_scan_order()->at(i);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1017
    Instruction *instr = cur_block;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1018
    for_each_phi_fun(cur_block, phi,
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1019
                     BoundStack *bound_stack = _bounds.at(phi->id());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1020
                     if (bound_stack && bound_stack->length() > 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1021
                       Bound *bound = bound_stack->top();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1022
                       if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != phi || bound->upper_instr() != phi || bound->lower() != 0 || bound->upper() != 0)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1023
                           TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1024
                                                         tty->print("i%d", phi->id());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1025
                                                         tty->print(": ");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1026
                                                         bound->print();
24424
2658d7834c6e 8037816: Fix for 8036122 breaks build with Xcode5/clang
drchase
parents: 22234
diff changeset
  1027
                                                         tty->cr();
16611
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1028
                           );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1029
                         }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1030
                     });
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1031
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1032
    while (!instr->as_BlockEnd()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1033
      if (instr->id() < _bounds.length()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1034
        BoundStack *bound_stack = _bounds.at(instr->id());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1035
        if (bound_stack && bound_stack->length() > 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1036
          Bound *bound = bound_stack->top();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1037
          if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != instr || bound->upper_instr() != instr || bound->lower() != 0 || bound->upper() != 0)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1038
              TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1039
                                            tty->print("i%d", instr->id());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1040
                                            tty->print(": ");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1041
                                            bound->print();
24424
2658d7834c6e 8037816: Fix for 8036122 breaks build with Xcode5/clang
drchase
parents: 22234
diff changeset
  1042
                                            tty->cr();
16611
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1043
              );
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1044
          }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1045
        }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1046
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1047
      instr = instr->next();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1048
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1049
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1050
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1051
#endif
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1052
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1053
// Verification or the IR
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1054
RangeCheckEliminator::Verification::Verification(IR *ir) : _used(BlockBegin::number_of_blocks(), false) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1055
  this->_ir = ir;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1056
  ir->iterate_linear_scan_order(this);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1057
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1058
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1059
// Verify this block
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1060
void RangeCheckEliminator::Verification::block_do(BlockBegin *block) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1061
  If *cond = block->end()->as_If();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1062
  // Watch out: tsux and fsux can be the same!
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1063
  if (block->number_of_sux() > 1) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1064
    for (int i=0; i<block->number_of_sux(); i++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1065
      BlockBegin *sux = block->sux_at(i);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1066
      BlockBegin *pred = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1067
      for (int j=0; j<sux->number_of_preds(); j++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1068
        BlockBegin *cur = sux->pred_at(j);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1069
        assert(cur != NULL, "Predecessor must not be null");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1070
        if (!pred) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1071
          pred = cur;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1072
        }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1073
        assert(cur == pred, "Block must not have more than one predecessor if its predecessor has more than one successor");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1074
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1075
      assert(sux->number_of_preds() >= 1, "Block must have at least one predecessor");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1076
      assert(sux->pred_at(0) == block, "Wrong successor");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1077
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1078
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1079
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1080
  BlockBegin *dominator = block->dominator();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1081
  if (dominator) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1082
    assert(block != _ir->start(), "Start block must not have a dominator!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1083
    assert(can_reach(dominator, block), "Dominator can't reach his block !");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1084
    assert(can_reach(_ir->start(), dominator), "Dominator is unreachable !");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1085
    assert(!can_reach(_ir->start(), block, dominator), "Wrong dominator ! Block can be reached anyway !");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1086
    BlockList *all_blocks = _ir->linear_scan_order();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1087
    for (int i=0; i<all_blocks->length(); i++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1088
      BlockBegin *cur = all_blocks->at(i);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1089
      if (cur != dominator && cur != block) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1090
        assert(can_reach(dominator, block, cur), "There has to be another dominator!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1091
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1092
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1093
  } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1094
    assert(block == _ir->start(), "Only start block must not have a dominator");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1095
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1096
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1097
  if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1098
    int loop_index = block->loop_index();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1099
    BlockList *all_blocks = _ir->linear_scan_order();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1100
    assert(block->number_of_preds() >= 1, "Block must have at least one predecessor");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1101
    assert(!block->is_set(BlockBegin::exception_entry_flag), "Loop header must not be exception handler!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1102
    // Sometimes, the backbranch comes from an exception handler. In
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1103
    // this case, loop indexes/loop depths may not appear correct.
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1104
    bool loop_through_xhandler = false;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1105
    for (int i = 0; i < block->number_of_exception_handlers(); i++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1106
      BlockBegin *xhandler = block->exception_handler_at(i);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1107
      for (int j = 0; j < block->number_of_preds(); j++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1108
        if (dominates(xhandler, block->pred_at(j)) || xhandler == block->pred_at(j)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1109
          loop_through_xhandler = true;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1110
        }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1111
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1112
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1113
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1114
    for (int i=0; i<block->number_of_sux(); i++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1115
      BlockBegin *sux = block->sux_at(i);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1116
      assert(sux->loop_depth() != block->loop_depth() || sux->loop_index() == block->loop_index() || loop_through_xhandler, "Loop index has to be same");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1117
      assert(sux->loop_depth() == block->loop_depth() || sux->loop_index() != block->loop_index(), "Loop index has to be different");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1118
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1119
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1120
    for (int i=0; i<all_blocks->length(); i++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1121
      BlockBegin *cur = all_blocks->at(i);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1122
      if (cur->loop_index() == loop_index && cur != block) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1123
        assert(dominates(block->dominator(), cur), "Dominator of loop header must dominate all loop blocks");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1124
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1125
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1126
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1127
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1128
  Instruction *cur = block;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1129
  while (cur) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1130
    assert(cur->block() == block, "Block begin has to be set correctly!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1131
    cur = cur->next();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1132
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1133
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1134
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1135
// Loop header must dominate all loop blocks
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1136
bool RangeCheckEliminator::Verification::dominates(BlockBegin *dominator, BlockBegin *block) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1137
  BlockBegin *cur = block->dominator();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1138
  while (cur && cur != dominator) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1139
    cur = cur->dominator();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1140
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1141
  return cur == dominator;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1142
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1143
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1144
// Try to reach Block end beginning in Block start and not using Block dont_use
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1145
bool RangeCheckEliminator::Verification::can_reach(BlockBegin *start, BlockBegin *end, BlockBegin *dont_use /* = NULL */) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1146
  if (start == end) return start != dont_use;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1147
  // Simple BSF from start to end
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1148
  //  BlockBeginList _current;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1149
  for (int i=0; i<_used.length(); i++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1150
    _used[i] = false;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1151
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1152
  _current.truncate(0);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1153
  _successors.truncate(0);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1154
  if (start != dont_use) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1155
    _current.push(start);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1156
    _used[start->block_id()] = true;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1157
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1158
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1159
  //  BlockBeginList _successors;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1160
  while (_current.length() > 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1161
    BlockBegin *cur = _current.pop();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1162
    // Add exception handlers to list
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1163
    for (int i=0; i<cur->number_of_exception_handlers(); i++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1164
      BlockBegin *xhandler = cur->exception_handler_at(i);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1165
      _successors.push(xhandler);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1166
      // Add exception handlers of _successors to list
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1167
      for (int j=0; j<xhandler->number_of_exception_handlers(); j++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1168
        BlockBegin *sux_xhandler = xhandler->exception_handler_at(j);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1169
        _successors.push(sux_xhandler);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1170
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1171
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1172
    // Add normal _successors to list
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1173
    for (int i=0; i<cur->number_of_sux(); i++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1174
      BlockBegin *sux = cur->sux_at(i);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1175
      _successors.push(sux);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1176
      // Add exception handlers of _successors to list
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1177
      for (int j=0; j<sux->number_of_exception_handlers(); j++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1178
        BlockBegin *xhandler = sux->exception_handler_at(j);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1179
        _successors.push(xhandler);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1180
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1181
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1182
    for (int i=0; i<_successors.length(); i++) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1183
      BlockBegin *sux = _successors[i];
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1184
      assert(sux != NULL, "Successor must not be NULL!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1185
      if (sux == end) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1186
        return true;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1187
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1188
      if (sux != dont_use && !_used[sux->block_id()]) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1189
        _used[sux->block_id()] = true;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1190
        _current.push(sux);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1191
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1192
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1193
    _successors.truncate(0);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1194
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1195
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1196
  return false;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1197
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1198
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1199
// Bound
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1200
RangeCheckEliminator::Bound::~Bound() {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1201
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1202
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1203
// Bound constructor
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1204
RangeCheckEliminator::Bound::Bound() {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1205
  init();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1206
  this->_lower = min_jint;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1207
  this->_upper = max_jint;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1208
  this->_lower_instr = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1209
  this->_upper_instr = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1210
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1211
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1212
// Bound constructor
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1213
RangeCheckEliminator::Bound::Bound(int lower, Value lower_instr, int upper, Value upper_instr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1214
  init();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1215
  assert(!lower_instr || !lower_instr->as_Constant() || !lower_instr->type()->as_IntConstant(), "Must not be constant!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1216
  assert(!upper_instr || !upper_instr->as_Constant() || !upper_instr->type()->as_IntConstant(), "Must not be constant!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1217
  this->_lower = lower;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1218
  this->_upper = upper;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1219
  this->_lower_instr = lower_instr;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1220
  this->_upper_instr = upper_instr;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1221
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1222
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1223
// Bound constructor
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1224
RangeCheckEliminator::Bound::Bound(Instruction::Condition cond, Value v, int constant) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1225
  assert(!v || (v->type() && (v->type()->as_IntType() || v->type()->as_ObjectType())), "Type must be array or integer!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1226
  assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1227
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1228
  init();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1229
  if (cond == Instruction::eql) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1230
    _lower = constant;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1231
    _lower_instr = v;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1232
    _upper = constant;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1233
    _upper_instr = v;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1234
  } else if (cond == Instruction::neq) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1235
    _lower = min_jint;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1236
    _upper = max_jint;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1237
    _lower_instr = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1238
    _upper_instr = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1239
    if (v == NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1240
      if (constant == min_jint) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1241
        _lower++;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1242
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1243
      if (constant == max_jint) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1244
        _upper--;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1245
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1246
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1247
  } else if (cond == Instruction::geq) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1248
    _lower = constant;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1249
    _lower_instr = v;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1250
    _upper = max_jint;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1251
    _upper_instr = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1252
  } else if (cond == Instruction::leq) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1253
    _lower = min_jint;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1254
    _lower_instr = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1255
    _upper = constant;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1256
    _upper_instr = v;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1257
  } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1258
    ShouldNotReachHere();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1259
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1260
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1261
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1262
// Set lower
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1263
void RangeCheckEliminator::Bound::set_lower(int value, Value v) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1264
  assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1265
  this->_lower = value;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1266
  this->_lower_instr = v;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1267
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1268
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1269
// Set upper
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1270
void RangeCheckEliminator::Bound::set_upper(int value, Value v) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1271
  assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1272
  this->_upper = value;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1273
  this->_upper_instr = v;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1274
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1275
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1276
// Add constant -> no overflow may occur
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1277
void RangeCheckEliminator::Bound::add_constant(int value) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1278
  this->_lower += value;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1279
  this->_upper += value;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1280
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1281
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1282
// Init
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1283
void RangeCheckEliminator::Bound::init() {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1284
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1285
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1286
// or
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1287
void RangeCheckEliminator::Bound::or_op(Bound *b) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1288
  // Watch out, bound is not guaranteed not to overflow!
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1289
  // Update lower bound
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1290
  if (_lower_instr != b->_lower_instr || (_lower_instr && _lower != b->_lower)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1291
    _lower_instr = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1292
    _lower = min_jint;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1293
  } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1294
    _lower = MIN2(_lower, b->_lower);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1295
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1296
  // Update upper bound
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1297
  if (_upper_instr != b->_upper_instr || (_upper_instr && _upper != b->_upper)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1298
    _upper_instr = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1299
    _upper = max_jint;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1300
  } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1301
    _upper = MAX2(_upper, b->_upper);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1302
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1303
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1304
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1305
// and
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1306
void RangeCheckEliminator::Bound::and_op(Bound *b) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1307
  // Update lower bound
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1308
  if (_lower_instr == b->_lower_instr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1309
    _lower = MAX2(_lower, b->_lower);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1310
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1311
  if (b->has_lower()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1312
    bool set = true;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1313
    if (_lower_instr != NULL && b->_lower_instr != NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1314
      set = (_lower_instr->dominator_depth() > b->_lower_instr->dominator_depth());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1315
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1316
    if (set) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1317
      _lower = b->_lower;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1318
      _lower_instr = b->_lower_instr;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1319
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1320
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1321
  // Update upper bound
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1322
  if (_upper_instr == b->_upper_instr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1323
    _upper = MIN2(_upper, b->_upper);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1324
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1325
  if (b->has_upper()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1326
    bool set = true;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1327
    if (_upper_instr != NULL && b->_upper_instr != NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1328
      set = (_upper_instr->dominator_depth() > b->_upper_instr->dominator_depth());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1329
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1330
    if (set) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1331
      _upper = b->_upper;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1332
      _upper_instr = b->_upper_instr;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1333
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1334
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1335
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1336
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1337
// has_upper
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1338
bool RangeCheckEliminator::Bound::has_upper() {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1339
  return _upper_instr != NULL || _upper < max_jint;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1340
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1341
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1342
// is_smaller
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1343
bool RangeCheckEliminator::Bound::is_smaller(Bound *b) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1344
  if (b->_lower_instr != _upper_instr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1345
    return false;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1346
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1347
  return _upper < b->_lower;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1348
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1349
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1350
// has_lower
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1351
bool RangeCheckEliminator::Bound::has_lower() {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1352
  return _lower_instr != NULL || _lower > min_jint;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1353
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1354
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1355
// in_array_bound
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1356
bool RangeCheckEliminator::in_array_bound(Bound *bound, Value array){
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1357
  if (!bound) return false;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1358
  assert(array != NULL, "Must not be null!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1359
  assert(bound != NULL, "Must not be null!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1360
  if (bound->lower() >=0 && bound->lower_instr() == NULL && bound->upper() < 0 && bound->upper_instr() != NULL) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1361
    ArrayLength *len = bound->upper_instr()->as_ArrayLength();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1362
    if (bound->upper_instr() == array || (len != NULL && len->array() == array)) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1363
      return true;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1364
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1365
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1366
  return false;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1367
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1368
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1369
// remove_lower
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1370
void RangeCheckEliminator::Bound::remove_lower() {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1371
  _lower = min_jint;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1372
  _lower_instr = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1373
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1374
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1375
// remove_upper
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1376
void RangeCheckEliminator::Bound::remove_upper() {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1377
  _upper = max_jint;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1378
  _upper_instr = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1379
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1380
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1381
// upper
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1382
int RangeCheckEliminator::Bound::upper() {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1383
  return _upper;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1384
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1385
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1386
// lower
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1387
int RangeCheckEliminator::Bound::lower() {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1388
  return _lower;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1389
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1390
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1391
// upper_instr
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1392
Value RangeCheckEliminator::Bound::upper_instr() {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1393
  return _upper_instr;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1394
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1395
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1396
// lower_instr
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1397
Value RangeCheckEliminator::Bound::lower_instr() {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1398
  return _lower_instr;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1399
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1400
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1401
// print
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1402
void RangeCheckEliminator::Bound::print() {
24424
2658d7834c6e 8037816: Fix for 8036122 breaks build with Xcode5/clang
drchase
parents: 22234
diff changeset
  1403
  tty->print("%s", "");
16611
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1404
  if (this->_lower_instr || this->_lower != min_jint) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1405
    if (this->_lower_instr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1406
      tty->print("i%d", this->_lower_instr->id());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1407
      if (this->_lower > 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1408
        tty->print("+%d", _lower);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1409
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1410
      if (this->_lower < 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1411
        tty->print("%d", _lower);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1412
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1413
    } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1414
      tty->print("%d", _lower);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1415
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1416
    tty->print(" <= ");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1417
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1418
  tty->print("x");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1419
  if (this->_upper_instr || this->_upper != max_jint) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1420
    tty->print(" <= ");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1421
    if (this->_upper_instr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1422
      tty->print("i%d", this->_upper_instr->id());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1423
      if (this->_upper > 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1424
        tty->print("+%d", _upper);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1425
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1426
      if (this->_upper < 0) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1427
        tty->print("%d", _upper);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1428
      }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1429
    } else {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1430
      tty->print("%d", _upper);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1431
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1432
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1433
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1434
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1435
// Copy
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1436
RangeCheckEliminator::Bound *RangeCheckEliminator::Bound::copy() {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1437
  Bound *b = new Bound();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1438
  b->_lower = _lower;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1439
  b->_lower_instr = _lower_instr;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1440
  b->_upper = _upper;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1441
  b->_upper_instr = _upper_instr;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1442
  return b;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1443
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1444
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1445
#ifdef ASSERT
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1446
// Add assertion
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1447
void RangeCheckEliminator::Bound::add_assertion(Instruction *instruction, Instruction *position, int i, Value instr, Instruction::Condition cond) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1448
  Instruction *result = position;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1449
  Instruction *compare_with = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1450
  ValueStack *state = position->state_before();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1451
  if (position->as_BlockEnd() && !position->as_Goto()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1452
    state = position->as_BlockEnd()->state_before();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1453
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1454
  Instruction *instruction_before = position->prev();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1455
  if (position->as_Return() && Compilation::current()->method()->is_synchronized() && instruction_before->as_MonitorExit()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1456
    instruction_before = instruction_before->prev();
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1457
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1458
  result = instruction_before;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1459
  // Load constant only if needed
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1460
  Constant *constant = NULL;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1461
  if (i != 0 || !instr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1462
    constant = new Constant(new IntConstant(i));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1463
    NOT_PRODUCT(constant->set_printable_bci(position->printable_bci()));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1464
    result = result->insert_after(constant);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1465
    compare_with = constant;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1466
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1467
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1468
  if (instr) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1469
    assert(instr->type()->as_ObjectType() || instr->type()->as_IntType(), "Type must be array or integer!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1470
    compare_with = instr;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1471
    // Load array length if necessary
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1472
    Instruction *op = instr;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1473
    if (instr->type()->as_ObjectType()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1474
      assert(state, "must not be null");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1475
      ArrayLength *length = new ArrayLength(instr, state->copy());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1476
      NOT_PRODUCT(length->set_printable_bci(position->printable_bci()));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1477
      length->set_exception_state(length->state_before());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1478
      result = result->insert_after(length);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1479
      op = length;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1480
      compare_with = length;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1481
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1482
    // Add operation only if necessary
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1483
    if (constant) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1484
      ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, op, false, NULL);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1485
      NOT_PRODUCT(ao->set_printable_bci(position->printable_bci()));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1486
      result = result->insert_after(ao);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1487
      compare_with = ao;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1488
      // TODO: Check that add operation does not overflow!
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1489
    }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1490
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1491
  assert(compare_with != NULL, "You have to compare with something!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1492
  assert(instruction != NULL, "Instruction must not be null!");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1493
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1494
  if (instruction->type()->as_ObjectType()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1495
    // Load array length if necessary
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1496
    Instruction *op = instruction;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1497
    assert(state, "must not be null");
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1498
    ArrayLength *length = new ArrayLength(instruction, state->copy());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1499
    length->set_exception_state(length->state_before());
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1500
    NOT_PRODUCT(length->set_printable_bci(position->printable_bci()));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1501
    result = result->insert_after(length);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1502
    instruction = length;
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1503
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1504
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1505
  Assert *assert = new Assert(instruction, cond, false, compare_with);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1506
  NOT_PRODUCT(assert->set_printable_bci(position->printable_bci()));
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1507
  result->insert_after(assert);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1508
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1509
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1510
// Add assertions
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1511
void RangeCheckEliminator::add_assertions(Bound *bound, Instruction *instruction, Instruction *position) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1512
  // Add lower bound assertion
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1513
  if (bound->has_lower()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1514
    bound->add_assertion(instruction, position, bound->lower(), bound->lower_instr(), Instruction::geq);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1515
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1516
  // Add upper bound assertion
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1517
  if (bound->has_upper()) {
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1518
    bound->add_assertion(instruction, position, bound->upper(), bound->upper_instr(), Instruction::leq);
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1519
  }
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1520
}
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1521
#endif
6807a703dd6b 7153771: array bound check elimination for c1
roland
parents:
diff changeset
  1522