Mercurial > jdk8-mips64-public > hotspot / changeset

     1.1 --- a/src/cpu/sparc/vm/c1_CodeStubs_sparc.cpp	Wed Mar 20 17:04:45 2013 -0700
     1.2 +++ b/src/cpu/sparc/vm/c1_CodeStubs_sparc.cpp	Thu Mar 21 09:27:54 2013 +0100
     1.3 @@ -51,6 +51,16 @@
     1.4  void RangeCheckStub::emit_code(LIR_Assembler* ce) {
     1.5    __ bind(_entry);
     1.6  
     1.7 +  if (_info->deoptimize_on_exception()) {
     1.8 +    address a = Runtime1::entry_for(Runtime1::predicate_failed_trap_id);
     1.9 +    __ call(a, relocInfo::runtime_call_type);
    1.10 +    __ delayed()->nop();
    1.11 +    ce->add_call_info_here(_info);
    1.12 +    ce->verify_oop_map(_info);
    1.13 +    debug_only(__ should_not_reach_here());
    1.14 +    return;
    1.15 +  }
    1.16 +
    1.17    if (_index->is_register()) {
    1.18      __ mov(_index->as_register(), G4);
    1.19    } else {
    1.20 @@ -64,11 +74,22 @@
    1.21    __ delayed()->nop();
    1.22    ce->add_call_info_here(_info);
    1.23    ce->verify_oop_map(_info);
    1.24 -#ifdef ASSERT
    1.25 -  __ should_not_reach_here();
    1.26 -#endif
    1.27 +  debug_only(__ should_not_reach_here());
    1.28  }
    1.29  
    1.30 +PredicateFailedStub::PredicateFailedStub(CodeEmitInfo* info) {
    1.31 +  _info = new CodeEmitInfo(info);
    1.32 +}
    1.33 +
    1.34 +void PredicateFailedStub::emit_code(LIR_Assembler* ce) {
    1.35 +  __ bind(_entry);
    1.36 +  address a = Runtime1::entry_for(Runtime1::predicate_failed_trap_id);
    1.37 +  __ call(a, relocInfo::runtime_call_type);
    1.38 +  __ delayed()->nop();
    1.39 +  ce->add_call_info_here(_info);
    1.40 +  ce->verify_oop_map(_info);
    1.41 +  debug_only(__ should_not_reach_here());
    1.42 +}
    1.43  
    1.44  void CounterOverflowStub::emit_code(LIR_Assembler* ce) {
    1.45    __ bind(_entry);
    1.46 @@ -99,10 +120,17 @@
    1.47  
    1.48  
    1.49  void ImplicitNullCheckStub::emit_code(LIR_Assembler* ce) {
    1.50 +  address a;
    1.51 +  if (_info->deoptimize_on_exception()) {
    1.52 +    // Deoptimize, do not throw the exception, because it is probably wrong to do it here.
    1.53 +    a = Runtime1::entry_for(Runtime1::predicate_failed_trap_id);
    1.54 +  } else {
    1.55 +    a = Runtime1::entry_for(Runtime1::throw_null_pointer_exception_id);
    1.56 +  }
    1.57 +
    1.58    ce->compilation()->implicit_exception_table()->append(_offset, __ offset());
    1.59    __ bind(_entry);
    1.60 -  __ call(Runtime1::entry_for(Runtime1::throw_null_pointer_exception_id),
    1.61 -          relocInfo::runtime_call_type);
    1.62 +  __ call(a, relocInfo::runtime_call_type);
    1.63    __ delayed()->nop();
    1.64    ce->add_call_info_here(_info);
    1.65    ce->verify_oop_map(_info);

     2.1 --- a/src/cpu/sparc/vm/c1_LIRAssembler_sparc.cpp	Wed Mar 20 17:04:45 2013 -0700
     2.2 +++ b/src/cpu/sparc/vm/c1_LIRAssembler_sparc.cpp	Thu Mar 21 09:27:54 2013 +0100
     2.3 @@ -3361,6 +3361,45 @@
     2.4    __ mov(G2_thread, result_reg->as_register());
     2.5  }
     2.6  
     2.7 +#ifdef ASSERT
     2.8 +// emit run-time assertion
     2.9 +void LIR_Assembler::emit_assert(LIR_OpAssert* op) {
    2.10 +  assert(op->code() == lir_assert, "must be");
    2.11 +
    2.12 +  if (op->in_opr1()->is_valid()) {
    2.13 +    assert(op->in_opr2()->is_valid(), "both operands must be valid");
    2.14 +    comp_op(op->condition(), op->in_opr1(), op->in_opr2(), op);
    2.15 +  } else {
    2.16 +    assert(op->in_opr2()->is_illegal(), "both operands must be illegal");
    2.17 +    assert(op->condition() == lir_cond_always, "no other conditions allowed");
    2.18 +  }
    2.19 +
    2.20 +  Label ok;
    2.21 +  if (op->condition() != lir_cond_always) {
    2.22 +    Assembler::Condition acond;
    2.23 +    switch (op->condition()) {
    2.24 +      case lir_cond_equal:        acond = Assembler::equal;                break;
    2.25 +      case lir_cond_notEqual:     acond = Assembler::notEqual;             break;
    2.26 +      case lir_cond_less:         acond = Assembler::less;                 break;
    2.27 +      case lir_cond_lessEqual:    acond = Assembler::lessEqual;            break;
    2.28 +      case lir_cond_greaterEqual: acond = Assembler::greaterEqual;         break;
    2.29 +      case lir_cond_greater:      acond = Assembler::greater;              break;
    2.30 +      case lir_cond_aboveEqual:   acond = Assembler::greaterEqualUnsigned; break;
    2.31 +      case lir_cond_belowEqual:   acond = Assembler::lessEqualUnsigned;    break;
    2.32 +      default:                         ShouldNotReachHere();
    2.33 +    };
    2.34 +    __ br(acond, false, Assembler::pt, ok);
    2.35 +    __ delayed()->nop();
    2.36 +  }
    2.37 +  if (op->halt()) {
    2.38 +    const char* str = __ code_string(op->msg());
    2.39 +    __ stop(str);
    2.40 +  } else {
    2.41 +    breakpoint();
    2.42 +  }
    2.43 +  __ bind(ok);
    2.44 +}
    2.45 +#endif
    2.46  
    2.47  void LIR_Assembler::peephole(LIR_List* lir) {
    2.48    LIR_OpList* inst = lir->instructions_list();

     3.1 --- a/src/cpu/sparc/vm/c1_LIRGenerator_sparc.cpp	Wed Mar 20 17:04:45 2013 -0700
     3.2 +++ b/src/cpu/sparc/vm/c1_LIRGenerator_sparc.cpp	Thu Mar 21 09:27:54 2013 +0100
     3.3 @@ -324,7 +324,7 @@
     3.4  
     3.5  void LIRGenerator::do_StoreIndexed(StoreIndexed* x) {
     3.6    assert(x->is_pinned(),"");
     3.7 -  bool needs_range_check = true;
     3.8 +  bool needs_range_check = x->compute_needs_range_check();
     3.9    bool use_length = x->length() != NULL;
    3.10    bool obj_store = x->elt_type() == T_ARRAY || x->elt_type() == T_OBJECT;
    3.11    bool needs_store_check = obj_store && (x->value()->as_Constant() == NULL ||
    3.12 @@ -339,12 +339,9 @@
    3.13    array.load_item();
    3.14    index.load_nonconstant();
    3.15  
    3.16 -  if (use_length) {
    3.17 -    needs_range_check = x->compute_needs_range_check();
    3.18 -    if (needs_range_check) {
    3.19 -      length.set_instruction(x->length());
    3.20 -      length.load_item();
    3.21 -    }
    3.22 +  if (use_length && needs_range_check) {
    3.23 +    length.set_instruction(x->length());
    3.24 +    length.load_item();
    3.25    }
    3.26    if (needs_store_check) {
    3.27      value.load_item();

     4.1 --- a/src/cpu/sparc/vm/c1_Runtime1_sparc.cpp	Wed Mar 20 17:04:45 2013 -0700
     4.2 +++ b/src/cpu/sparc/vm/c1_Runtime1_sparc.cpp	Thu Mar 21 09:27:54 2013 +0100
     4.3 @@ -987,6 +987,25 @@
     4.4        break;
     4.5  #endif // INCLUDE_ALL_GCS
     4.6  
     4.7 +    case predicate_failed_trap_id:
     4.8 +      {
     4.9 +        __ set_info("predicate_failed_trap", dont_gc_arguments);
    4.10 +        OopMap* oop_map = save_live_registers(sasm);
    4.11 +
    4.12 +        int call_offset = __ call_RT(noreg, noreg, CAST_FROM_FN_PTR(address, predicate_failed_trap));
    4.13 +
    4.14 +        oop_maps = new OopMapSet();
    4.15 +        oop_maps->add_gc_map(call_offset, oop_map);
    4.16 +
    4.17 +        DeoptimizationBlob* deopt_blob = SharedRuntime::deopt_blob();
    4.18 +        assert(deopt_blob != NULL, "deoptimization blob must have been created");
    4.19 +        restore_live_registers(sasm);
    4.20 +        __ restore();
    4.21 +        __ br(Assembler::always, false, Assembler::pt, deopt_blob->unpack_with_reexecution(), relocInfo::runtime_call_type);
    4.22 +        __ delayed()->nop();
    4.23 +      }
    4.24 +      break;
    4.25 +
    4.26      default:
    4.27        { __ set_info("unimplemented entry", dont_gc_arguments);
    4.28          __ save_frame(0);

     5.1 --- a/src/cpu/x86/vm/c1_CodeStubs_x86.cpp	Wed Mar 20 17:04:45 2013 -0700
     5.2 +++ b/src/cpu/x86/vm/c1_CodeStubs_x86.cpp	Thu Mar 21 09:27:54 2013 +0100
     5.3 @@ -101,6 +101,15 @@
     5.4  
     5.5  void RangeCheckStub::emit_code(LIR_Assembler* ce) {
     5.6    __ bind(_entry);
     5.7 +  if (_info->deoptimize_on_exception()) {
     5.8 +    address a = Runtime1::entry_for(Runtime1::predicate_failed_trap_id);
     5.9 +    __ call(RuntimeAddress(a));
    5.10 +    ce->add_call_info_here(_info);
    5.11 +    ce->verify_oop_map(_info);
    5.12 +    debug_only(__ should_not_reach_here());
    5.13 +    return;
    5.14 +  }
    5.15 +
    5.16    // pass the array index on stack because all registers must be preserved
    5.17    if (_index->is_cpu_register()) {
    5.18      ce->store_parameter(_index->as_register(), 0);
    5.19 @@ -115,9 +124,22 @@
    5.20    }
    5.21    __ call(RuntimeAddress(Runtime1::entry_for(stub_id)));
    5.22    ce->add_call_info_here(_info);
    5.23 +  ce->verify_oop_map(_info);
    5.24    debug_only(__ should_not_reach_here());
    5.25  }
    5.26  
    5.27 +PredicateFailedStub::PredicateFailedStub(CodeEmitInfo* info) {
    5.28 +  _info = new CodeEmitInfo(info);
    5.29 +}
    5.30 +
    5.31 +void PredicateFailedStub::emit_code(LIR_Assembler* ce) {
    5.32 +  __ bind(_entry);
    5.33 +  address a = Runtime1::entry_for(Runtime1::predicate_failed_trap_id);
    5.34 +  __ call(RuntimeAddress(a));
    5.35 +  ce->add_call_info_here(_info);
    5.36 +  ce->verify_oop_map(_info);
    5.37 +  debug_only(__ should_not_reach_here());
    5.38 +}
    5.39  
    5.40  void DivByZeroStub::emit_code(LIR_Assembler* ce) {
    5.41    if (_offset != -1) {
    5.42 @@ -414,10 +436,19 @@
    5.43  
    5.44  
    5.45  void ImplicitNullCheckStub::emit_code(LIR_Assembler* ce) {
    5.46 +  address a;
    5.47 +  if (_info->deoptimize_on_exception()) {
    5.48 +    // Deoptimize, do not throw the exception, because it is probably wrong to do it here.
    5.49 +    a = Runtime1::entry_for(Runtime1::predicate_failed_trap_id);
    5.50 +  } else {
    5.51 +    a = Runtime1::entry_for(Runtime1::throw_null_pointer_exception_id);
    5.52 +  }
    5.53 +
    5.54    ce->compilation()->implicit_exception_table()->append(_offset, __ offset());
    5.55    __ bind(_entry);
    5.56 -  __ call(RuntimeAddress(Runtime1::entry_for(Runtime1::throw_null_pointer_exception_id)));
    5.57 +  __ call(RuntimeAddress(a));
    5.58    ce->add_call_info_here(_info);
    5.59 +  ce->verify_oop_map(_info);
    5.60    debug_only(__ should_not_reach_here());
    5.61  }
    5.62  

     6.1 --- a/src/cpu/x86/vm/c1_LIRAssembler_x86.cpp	Wed Mar 20 17:04:45 2013 -0700
     6.2 +++ b/src/cpu/x86/vm/c1_LIRAssembler_x86.cpp	Thu Mar 21 09:27:54 2013 +0100
     6.3 @@ -3755,6 +3755,44 @@
     6.4    }
     6.5  }
     6.6  
     6.7 +#ifdef ASSERT
     6.8 +// emit run-time assertion
     6.9 +void LIR_Assembler::emit_assert(LIR_OpAssert* op) {
    6.10 +  assert(op->code() == lir_assert, "must be");
    6.11 +
    6.12 +  if (op->in_opr1()->is_valid()) {
    6.13 +    assert(op->in_opr2()->is_valid(), "both operands must be valid");
    6.14 +    comp_op(op->condition(), op->in_opr1(), op->in_opr2(), op);
    6.15 +  } else {
    6.16 +    assert(op->in_opr2()->is_illegal(), "both operands must be illegal");
    6.17 +    assert(op->condition() == lir_cond_always, "no other conditions allowed");
    6.18 +  }
    6.19 +
    6.20 +  Label ok;
    6.21 +  if (op->condition() != lir_cond_always) {
    6.22 +    Assembler::Condition acond = Assembler::zero;
    6.23 +    switch (op->condition()) {
    6.24 +      case lir_cond_equal:        acond = Assembler::equal;       break;
    6.25 +      case lir_cond_notEqual:     acond = Assembler::notEqual;    break;
    6.26 +      case lir_cond_less:         acond = Assembler::less;        break;
    6.27 +      case lir_cond_lessEqual:    acond = Assembler::lessEqual;   break;
    6.28 +      case lir_cond_greaterEqual: acond = Assembler::greaterEqual;break;
    6.29 +      case lir_cond_greater:      acond = Assembler::greater;     break;
    6.30 +      case lir_cond_belowEqual:   acond = Assembler::belowEqual;  break;
    6.31 +      case lir_cond_aboveEqual:   acond = Assembler::aboveEqual;  break;
    6.32 +      default:                    ShouldNotReachHere();
    6.33 +    }
    6.34 +    __ jcc(acond, ok);
    6.35 +  }
    6.36 +  if (op->halt()) {
    6.37 +    const char* str = __ code_string(op->msg());
    6.38 +    __ stop(str);
    6.39 +  } else {
    6.40 +    breakpoint();
    6.41 +  }
    6.42 +  __ bind(ok);
    6.43 +}
    6.44 +#endif
    6.45  
    6.46  void LIR_Assembler::membar() {
    6.47    // QQQ sparc TSO uses this,

     7.1 --- a/src/cpu/x86/vm/c1_LIRGenerator_x86.cpp	Wed Mar 20 17:04:45 2013 -0700
     7.2 +++ b/src/cpu/x86/vm/c1_LIRGenerator_x86.cpp	Thu Mar 21 09:27:54 2013 +0100
     7.3 @@ -263,7 +263,7 @@
     7.4  
     7.5  void LIRGenerator::do_StoreIndexed(StoreIndexed* x) {
     7.6    assert(x->is_pinned(),"");
     7.7 -  bool needs_range_check = true;
     7.8 +  bool needs_range_check = x->compute_needs_range_check();
     7.9    bool use_length = x->length() != NULL;
    7.10    bool obj_store = x->elt_type() == T_ARRAY || x->elt_type() == T_OBJECT;
    7.11    bool needs_store_check = obj_store && (x->value()->as_Constant() == NULL ||
    7.12 @@ -278,12 +278,10 @@
    7.13    array.load_item();
    7.14    index.load_nonconstant();
    7.15  
    7.16 -  if (use_length) {
    7.17 -    needs_range_check = x->compute_needs_range_check();
    7.18 -    if (needs_range_check) {
    7.19 -      length.set_instruction(x->length());
    7.20 -      length.load_item();
    7.21 -    }
    7.22 +  if (use_length && needs_range_check) {
    7.23 +    length.set_instruction(x->length());
    7.24 +    length.load_item();
    7.25 +
    7.26    }
    7.27    if (needs_store_check) {
    7.28      value.load_item();

     8.1 --- a/src/cpu/x86/vm/c1_LinearScan_x86.cpp	Wed Mar 20 17:04:45 2013 -0700
     8.2 +++ b/src/cpu/x86/vm/c1_LinearScan_x86.cpp	Thu Mar 21 09:27:54 2013 +0100
     8.3 @@ -675,7 +675,8 @@
     8.4    switch (op2->code()) {
     8.5      case lir_cmp:
     8.6      case lir_cmp_fd2i:
     8.7 -    case lir_ucmp_fd2i: {
     8.8 +    case lir_ucmp_fd2i:
     8.9 +    case lir_assert: {
    8.10        assert(left->is_fpu_register(), "invalid LIR");
    8.11        assert(right->is_fpu_register(), "invalid LIR");
    8.12  

     9.1 --- a/src/cpu/x86/vm/c1_Runtime1_x86.cpp	Wed Mar 20 17:04:45 2013 -0700
     9.2 +++ b/src/cpu/x86/vm/c1_Runtime1_x86.cpp	Thu Mar 21 09:27:54 2013 +0100
     9.3 @@ -1807,6 +1807,24 @@
     9.4        break;
     9.5  #endif // INCLUDE_ALL_GCS
     9.6  
     9.7 +    case predicate_failed_trap_id:
     9.8 +      {
     9.9 +        StubFrame f(sasm, "predicate_failed_trap", dont_gc_arguments);
    9.10 +
    9.11 +        OopMap* map = save_live_registers(sasm, 1);
    9.12 +
    9.13 +        int call_offset = __ call_RT(noreg, noreg, CAST_FROM_FN_PTR(address, predicate_failed_trap));
    9.14 +        oop_maps = new OopMapSet();
    9.15 +        oop_maps->add_gc_map(call_offset, map);
    9.16 +        restore_live_registers(sasm);
    9.17 +        __ leave();
    9.18 +        DeoptimizationBlob* deopt_blob = SharedRuntime::deopt_blob();
    9.19 +        assert(deopt_blob != NULL, "deoptimization blob must have been created");
    9.20 +
    9.21 +        __ jump(RuntimeAddress(deopt_blob->unpack_with_reexecution()));
    9.22 +      }
    9.23 +      break;
    9.24 +
    9.25      default:
    9.26        { StubFrame f(sasm, "unimplemented entry", dont_gc_arguments);
    9.27          __ movptr(rax, (int)id);

    10.1 --- a/src/share/vm/c1/c1_Canonicalizer.cpp	Wed Mar 20 17:04:45 2013 -0700
    10.2 +++ b/src/share/vm/c1/c1_Canonicalizer.cpp	Thu Mar 21 09:27:54 2013 +0100
    10.3 @@ -937,4 +937,6 @@
    10.4  void Canonicalizer::do_ProfileCall(ProfileCall* x) {}
    10.5  void Canonicalizer::do_ProfileInvoke(ProfileInvoke* x) {}
    10.6  void Canonicalizer::do_RuntimeCall(RuntimeCall* x) {}
    10.7 +void Canonicalizer::do_RangeCheckPredicate(RangeCheckPredicate* x) {}
    10.8 +void Canonicalizer::do_Assert(Assert* x) {}
    10.9  void Canonicalizer::do_MemBar(MemBar* x) {}

    11.1 --- a/src/share/vm/c1/c1_Canonicalizer.hpp	Wed Mar 20 17:04:45 2013 -0700
    11.2 +++ b/src/share/vm/c1/c1_Canonicalizer.hpp	Thu Mar 21 09:27:54 2013 +0100
    11.3 @@ -107,6 +107,8 @@
    11.4    virtual void do_ProfileInvoke  (ProfileInvoke*   x);
    11.5    virtual void do_RuntimeCall    (RuntimeCall*     x);
    11.6    virtual void do_MemBar         (MemBar*          x);
    11.7 +  virtual void do_RangeCheckPredicate(RangeCheckPredicate* x);
    11.8 +  virtual void do_Assert         (Assert*          x);
    11.9  };
   11.10  
   11.11  #endif // SHARE_VM_C1_C1_CANONICALIZER_HPP

    12.1 --- a/src/share/vm/c1/c1_CodeStubs.hpp	Wed Mar 20 17:04:45 2013 -0700
    12.2 +++ b/src/share/vm/c1/c1_CodeStubs.hpp	Thu Mar 21 09:27:54 2013 +0100
    12.3 @@ -166,6 +166,22 @@
    12.4  #endif // PRODUCT
    12.5  };
    12.6  
    12.7 +// stub used when predicate fails and deoptimization is needed
    12.8 +class PredicateFailedStub: public CodeStub {
    12.9 + private:
   12.10 +  CodeEmitInfo* _info;
   12.11 +
   12.12 + public:
   12.13 +  PredicateFailedStub(CodeEmitInfo* info);
   12.14 +  virtual void emit_code(LIR_Assembler* e);
   12.15 +  virtual CodeEmitInfo* info() const             { return _info; }
   12.16 +  virtual void visit(LIR_OpVisitState* visitor) {
   12.17 +    visitor->do_slow_case(_info);
   12.18 +  }
   12.19 +#ifndef PRODUCT
   12.20 +  virtual void print_name(outputStream* out) const { out->print("PredicateFailedStub"); }
   12.21 +#endif // PRODUCT
   12.22 +};
   12.23  
   12.24  class DivByZeroStub: public CodeStub {
   12.25   private:

    13.1 --- a/src/share/vm/c1/c1_Compilation.cpp	Wed Mar 20 17:04:45 2013 -0700
    13.2 +++ b/src/share/vm/c1/c1_Compilation.cpp	Thu Mar 21 09:27:54 2013 +0100
    13.3 @@ -33,13 +33,16 @@
    13.4  #include "c1/c1_ValueStack.hpp"
    13.5  #include "code/debugInfoRec.hpp"
    13.6  #include "compiler/compileLog.hpp"
    13.7 +#include "c1/c1_RangeCheckElimination.hpp"
    13.8  
    13.9  
   13.10  typedef enum {
   13.11    _t_compile,
   13.12    _t_setup,
   13.13 -  _t_optimizeIR,
   13.14    _t_buildIR,
   13.15 +  _t_optimize_blocks,
   13.16 +  _t_optimize_null_checks,
   13.17 +  _t_rangeCheckElimination,
   13.18    _t_emit_lir,
   13.19    _t_linearScan,
   13.20    _t_lirGeneration,
   13.21 @@ -52,8 +55,10 @@
   13.22  static const char * timer_name[] = {
   13.23    "compile",
   13.24    "setup",
   13.25 -  "optimizeIR",
   13.26    "buildIR",
   13.27 +  "optimize_blocks",
   13.28 +  "optimize_null_checks",
   13.29 +  "rangeCheckElimination",
   13.30    "emit_lir",
   13.31    "linearScan",
   13.32    "lirGeneration",
   13.33 @@ -159,9 +164,9 @@
   13.34    if (UseC1Optimizations) {
   13.35      NEEDS_CLEANUP
   13.36      // optimization
   13.37 -    PhaseTraceTime timeit(_t_optimizeIR);
   13.38 +    PhaseTraceTime timeit(_t_optimize_blocks);
   13.39  
   13.40 -    _hir->optimize();
   13.41 +    _hir->optimize_blocks();
   13.42    }
   13.43  
   13.44    _hir->verify();
   13.45 @@ -180,13 +185,47 @@
   13.46    _hir->compute_code();
   13.47  
   13.48    if (UseGlobalValueNumbering) {
   13.49 -    ResourceMark rm;
   13.50 +    // No resource mark here! LoopInvariantCodeMotion can allocate ValueStack objects.
   13.51      int instructions = Instruction::number_of_instructions();
   13.52      GlobalValueNumbering gvn(_hir);
   13.53      assert(instructions == Instruction::number_of_instructions(),
   13.54             "shouldn't have created an instructions");
   13.55    }
   13.56  
   13.57 +  _hir->verify();
   13.58 +
   13.59 +#ifndef PRODUCT
   13.60 +  if (PrintCFGToFile) {
   13.61 +    CFGPrinter::print_cfg(_hir, "Before RangeCheckElimination", true, false);
   13.62 +  }
   13.63 +#endif
   13.64 +
   13.65 +  if (RangeCheckElimination) {
   13.66 +    if (_hir->osr_entry() == NULL) {
   13.67 +      PhaseTraceTime timeit(_t_rangeCheckElimination);
   13.68 +      RangeCheckElimination::eliminate(_hir);
   13.69 +    }
   13.70 +  }
   13.71 +
   13.72 +#ifndef PRODUCT
   13.73 +  if (PrintCFGToFile) {
   13.74 +    CFGPrinter::print_cfg(_hir, "After RangeCheckElimination", true, false);
   13.75 +  }
   13.76 +#endif
   13.77 +
   13.78 +  if (UseC1Optimizations) {
   13.79 +    // loop invariant code motion reorders instructions and range
   13.80 +    // check elimination adds new instructions so do null check
   13.81 +    // elimination after.
   13.82 +    NEEDS_CLEANUP
   13.83 +    // optimization
   13.84 +    PhaseTraceTime timeit(_t_optimize_null_checks);
   13.85 +
   13.86 +    _hir->eliminate_null_checks();
   13.87 +  }
   13.88 +
   13.89 +  _hir->verify();
   13.90 +
   13.91    // compute use counts after global value numbering
   13.92    _hir->compute_use_counts();
   13.93  
   13.94 @@ -502,6 +541,7 @@
   13.95  , _next_id(0)
   13.96  , _next_block_id(0)
   13.97  , _code(buffer_blob)
   13.98 +, _has_access_indexed(false)
   13.99  , _current_instruction(NULL)
  13.100  #ifndef PRODUCT
  13.101  , _last_instruction_printed(NULL)
  13.102 @@ -567,7 +607,9 @@
  13.103    tty->print_cr("    Detailed C1 Timings");
  13.104    tty->print_cr("       Setup time:        %6.3f s (%4.1f%%)",    timers[_t_setup].seconds(),           (timers[_t_setup].seconds() / total) * 100.0);
  13.105    tty->print_cr("       Build IR:          %6.3f s (%4.1f%%)",    timers[_t_buildIR].seconds(),         (timers[_t_buildIR].seconds() / total) * 100.0);
  13.106 -  tty->print_cr("         Optimize:           %6.3f s (%4.1f%%)", timers[_t_optimizeIR].seconds(),      (timers[_t_optimizeIR].seconds() / total) * 100.0);
  13.107 +  float t_optimizeIR = timers[_t_optimize_blocks].seconds() + timers[_t_optimize_null_checks].seconds();
  13.108 +  tty->print_cr("         Optimize:           %6.3f s (%4.1f%%)", t_optimizeIR,                         (t_optimizeIR / total) * 100.0);
  13.109 +  tty->print_cr("         RCE:                %6.3f s (%4.1f%%)", timers[_t_rangeCheckElimination].seconds(),      (timers[_t_rangeCheckElimination].seconds() / total) * 100.0);
  13.110    tty->print_cr("       Emit LIR:          %6.3f s (%4.1f%%)",    timers[_t_emit_lir].seconds(),        (timers[_t_emit_lir].seconds() / total) * 100.0);
  13.111    tty->print_cr("         LIR Gen:          %6.3f s (%4.1f%%)",   timers[_t_lirGeneration].seconds(), (timers[_t_lirGeneration].seconds() / total) * 100.0);
  13.112    tty->print_cr("         Linear Scan:      %6.3f s (%4.1f%%)",   timers[_t_linearScan].seconds(),    (timers[_t_linearScan].seconds() / total) * 100.0);

    14.1 --- a/src/share/vm/c1/c1_Compilation.hpp	Wed Mar 20 17:04:45 2013 -0700
    14.2 +++ b/src/share/vm/c1/c1_Compilation.hpp	Thu Mar 21 09:27:54 2013 +0100
    14.3 @@ -26,8 +26,10 @@
    14.4  #define SHARE_VM_C1_C1_COMPILATION_HPP
    14.5  
    14.6  #include "ci/ciEnv.hpp"
    14.7 +#include "ci/ciMethodData.hpp"
    14.8  #include "code/exceptionHandlerTable.hpp"
    14.9  #include "memory/resourceArea.hpp"
   14.10 +#include "runtime/deoptimization.hpp"
   14.11  
   14.12  class CompilationResourceObj;
   14.13  class XHandlers;
   14.14 @@ -85,6 +87,7 @@
   14.15    LinearScan*        _allocator;
   14.16    CodeOffsets        _offsets;
   14.17    CodeBuffer         _code;
   14.18 +  bool               _has_access_indexed;
   14.19  
   14.20    // compilation helpers
   14.21    void initialize();
   14.22 @@ -140,6 +143,7 @@
   14.23    C1_MacroAssembler* masm() const                { return _masm; }
   14.24    CodeOffsets* offsets()                         { return &_offsets; }
   14.25    Arena* arena()                                 { return _arena; }
   14.26 +  bool has_access_indexed()                      { return _has_access_indexed; }
   14.27  
   14.28    // Instruction ids
   14.29    int get_next_id()                              { return _next_id++; }
   14.30 @@ -154,6 +158,7 @@
   14.31    void set_has_fpu_code(bool f)                  { _has_fpu_code = f; }
   14.32    void set_has_unsafe_access(bool f)             { _has_unsafe_access = f; }
   14.33    void set_would_profile(bool f)                 { _would_profile = f; }
   14.34 +  void set_has_access_indexed(bool f)            { _has_access_indexed = f; }
   14.35    // Add a set of exception handlers covering the given PC offset
   14.36    void add_exception_handlers_for_pco(int pco, XHandlers* exception_handlers);
   14.37    // Statistics gathering
   14.38 @@ -233,6 +238,14 @@
   14.39      return env()->comp_level() == CompLevel_full_profile &&
   14.40        C1UpdateMethodData && C1ProfileCheckcasts;
   14.41    }
   14.42 +
   14.43 +  // will compilation make optimistic assumptions that might lead to
   14.44 +  // deoptimization and that the runtime will account for?
   14.45 +  bool is_optimistic() const                             {
   14.46 +    return !TieredCompilation &&
   14.47 +      (RangeCheckElimination || UseLoopInvariantCodeMotion) &&
   14.48 +      method()->method_data()->trap_count(Deoptimization::Reason_none) == 0;
   14.49 +  }
   14.50  };
   14.51  
   14.52  

    15.1 --- a/src/share/vm/c1/c1_GraphBuilder.cpp	Wed Mar 20 17:04:45 2013 -0700
    15.2 +++ b/src/share/vm/c1/c1_GraphBuilder.cpp	Thu Mar 21 09:27:54 2013 +0100
    15.3 @@ -947,7 +947,9 @@
    15.4  
    15.5  
    15.6  void GraphBuilder::load_indexed(BasicType type) {
    15.7 -  ValueStack* state_before = copy_state_for_exception();
    15.8 +  // In case of in block code motion in range check elimination
    15.9 +  ValueStack* state_before = copy_state_indexed_access();
   15.10 +  compilation()->set_has_access_indexed(true);
   15.11    Value index = ipop();
   15.12    Value array = apop();
   15.13    Value length = NULL;
   15.14 @@ -961,7 +963,9 @@
   15.15  
   15.16  
   15.17  void GraphBuilder::store_indexed(BasicType type) {
   15.18 -  ValueStack* state_before = copy_state_for_exception();
   15.19 +  // In case of in block code motion in range check elimination
   15.20 +  ValueStack* state_before = copy_state_indexed_access();
   15.21 +  compilation()->set_has_access_indexed(true);
   15.22    Value value = pop(as_ValueType(type));
   15.23    Value index = ipop();
   15.24    Value array = apop();
   15.25 @@ -1179,7 +1183,9 @@
   15.26    BlockBegin* tsux = block_at(stream()->get_dest());
   15.27    BlockBegin* fsux = block_at(stream()->next_bci());
   15.28    bool is_bb = tsux->bci() < stream()->cur_bci() || fsux->bci() < stream()->cur_bci();
   15.29 -  Instruction *i = append(new If(x, cond, false, y, tsux, fsux, is_bb ? state_before : NULL, is_bb));
   15.30 +  // In case of loop invariant code motion or predicate insertion
   15.31 +  // before the body of a loop the state is needed
   15.32 +  Instruction *i = append(new If(x, cond, false, y, tsux, fsux, (is_bb || compilation()->is_optimistic()) ? state_before : NULL, is_bb));
   15.33  
   15.34    assert(i->as_Goto() == NULL ||
   15.35           (i->as_Goto()->sux_at(0) == tsux  && i->as_Goto()->is_safepoint() == tsux->bci() < stream()->cur_bci()) ||
   15.36 @@ -1294,7 +1300,9 @@
   15.37      BlockBegin* tsux = block_at(bci() + sw.dest_offset_at(0));
   15.38      BlockBegin* fsux = block_at(bci() + sw.default_offset());
   15.39      bool is_bb = tsux->bci() < bci() || fsux->bci() < bci();
   15.40 -    ValueStack* state_before = is_bb ? copy_state_before() : NULL;
   15.41 +    // In case of loop invariant code motion or predicate insertion
   15.42 +    // before the body of a loop the state is needed
   15.43 +    ValueStack* state_before = copy_state_if_bb(is_bb);
   15.44      append(new If(ipop(), If::eql, true, key, tsux, fsux, state_before, is_bb));
   15.45    } else {
   15.46      // collect successors
   15.47 @@ -1308,7 +1316,9 @@
   15.48      // add default successor
   15.49      if (sw.default_offset() < 0) has_bb = true;
   15.50      sux->at_put(i, block_at(bci() + sw.default_offset()));
   15.51 -    ValueStack* state_before = has_bb ? copy_state_before() : NULL;
   15.52 +    // In case of loop invariant code motion or predicate insertion
   15.53 +    // before the body of a loop the state is needed
   15.54 +    ValueStack* state_before = copy_state_if_bb(has_bb);
   15.55      Instruction* res = append(new TableSwitch(ipop(), sux, sw.low_key(), state_before, has_bb));
   15.56  #ifdef ASSERT
   15.57      if (res->as_Goto()) {
   15.58 @@ -1336,7 +1346,9 @@
   15.59      BlockBegin* tsux = block_at(bci() + pair.offset());
   15.60      BlockBegin* fsux = block_at(bci() + sw.default_offset());
   15.61      bool is_bb = tsux->bci() < bci() || fsux->bci() < bci();
   15.62 -    ValueStack* state_before = is_bb ? copy_state_before() : NULL;
   15.63 +    // In case of loop invariant code motion or predicate insertion
   15.64 +    // before the body of a loop the state is needed
   15.65 +    ValueStack* state_before = copy_state_if_bb(is_bb);;
   15.66      append(new If(ipop(), If::eql, true, key, tsux, fsux, state_before, is_bb));
   15.67    } else {
   15.68      // collect successors & keys
   15.69 @@ -1353,7 +1365,9 @@
   15.70      // add default successor
   15.71      if (sw.default_offset() < 0) has_bb = true;
   15.72      sux->at_put(i, block_at(bci() + sw.default_offset()));
   15.73 -    ValueStack* state_before = has_bb ? copy_state_before() : NULL;
   15.74 +    // In case of loop invariant code motion or predicate insertion
   15.75 +    // before the body of a loop the state is needed
   15.76 +    ValueStack* state_before = copy_state_if_bb(has_bb);
   15.77      Instruction* res = append(new LookupSwitch(ipop(), sux, keys, state_before, has_bb));
   15.78  #ifdef ASSERT
   15.79      if (res->as_Goto()) {

    16.1 --- a/src/share/vm/c1/c1_GraphBuilder.hpp	Wed Mar 20 17:04:45 2013 -0700
    16.2 +++ b/src/share/vm/c1/c1_GraphBuilder.hpp	Thu Mar 21 09:27:54 2013 +0100
    16.3 @@ -301,6 +301,8 @@
    16.4    ValueStack* copy_state_exhandling();
    16.5    ValueStack* copy_state_for_exception_with_bci(int bci);
    16.6    ValueStack* copy_state_for_exception();
    16.7 +  ValueStack* copy_state_if_bb(bool is_bb) { return (is_bb || compilation()->is_optimistic()) ? copy_state_before() : NULL; }
    16.8 +  ValueStack* copy_state_indexed_access() { return compilation()->is_optimistic() ? copy_state_before() : copy_state_for_exception(); }
    16.9  
   16.10    //
   16.11    // Inlining support

    17.1 --- a/src/share/vm/c1/c1_IR.cpp	Wed Mar 20 17:04:45 2013 -0700
    17.2 +++ b/src/share/vm/c1/c1_IR.cpp	Thu Mar 21 09:27:54 2013 +0100
    17.3 @@ -182,13 +182,14 @@
    17.4  // Implementation of CodeEmitInfo
    17.5  
    17.6  // Stack must be NON-null
    17.7 -CodeEmitInfo::CodeEmitInfo(ValueStack* stack, XHandlers* exception_handlers)
    17.8 +CodeEmitInfo::CodeEmitInfo(ValueStack* stack, XHandlers* exception_handlers, bool deoptimize_on_exception)
    17.9    : _scope(stack->scope())
   17.10    , _scope_debug_info(NULL)
   17.11    , _oop_map(NULL)
   17.12    , _stack(stack)
   17.13    , _exception_handlers(exception_handlers)
   17.14 -  , _is_method_handle_invoke(false) {
   17.15 +  , _is_method_handle_invoke(false)
   17.16 +  , _deoptimize_on_exception(deoptimize_on_exception) {
   17.17    assert(_stack != NULL, "must be non null");
   17.18  }
   17.19  
   17.20 @@ -199,7 +200,8 @@
   17.21    , _scope_debug_info(NULL)
   17.22    , _oop_map(NULL)
   17.23    , _stack(stack == NULL ? info->_stack : stack)
   17.24 -  , _is_method_handle_invoke(info->_is_method_handle_invoke) {
   17.25 +  , _is_method_handle_invoke(info->_is_method_handle_invoke)
   17.26 +  , _deoptimize_on_exception(info->_deoptimize_on_exception) {
   17.27  
   17.28    // deep copy of exception handlers
   17.29    if (info->_exception_handlers != NULL) {
   17.30 @@ -239,7 +241,7 @@
   17.31  }
   17.32  
   17.33  
   17.34 -void IR::optimize() {
   17.35 +void IR::optimize_blocks() {
   17.36    Optimizer opt(this);
   17.37    if (!compilation()->profile_branches()) {
   17.38      if (DoCEE) {
   17.39 @@ -257,6 +259,10 @@
   17.40  #endif
   17.41      }
   17.42    }
   17.43 +}
   17.44 +
   17.45 +void IR::eliminate_null_checks() {
   17.46 +  Optimizer opt(this);
   17.47    if (EliminateNullChecks) {
   17.48      opt.eliminate_null_checks();
   17.49  #ifndef PRODUCT
   17.50 @@ -429,6 +435,7 @@
   17.51    BlockList  _loop_end_blocks;     // list of all loop end blocks collected during count_edges
   17.52    BitMap2D   _loop_map;            // two-dimensional bit set: a bit is set if a block is contained in a loop
   17.53    BlockList  _work_list;           // temporary list (used in mark_loops and compute_order)
   17.54 +  BlockList  _loop_headers;
   17.55  
   17.56    Compilation* _compilation;
   17.57  
   17.58 @@ -594,6 +601,7 @@
   17.59      TRACE_LINEAR_SCAN(3, tty->print_cr("Block B%d is loop header of loop %d", cur->block_id(), _num_loops));
   17.60  
   17.61      cur->set_loop_index(_num_loops);
   17.62 +    _loop_headers.append(cur);
   17.63      _num_loops++;
   17.64    }
   17.65  
   17.66 @@ -656,6 +664,16 @@
   17.67        // -> this is not a natural loop, so ignore it
   17.68        TRACE_LINEAR_SCAN(2, tty->print_cr("Loop %d is non-natural, so it is ignored", i));
   17.69  
   17.70 +      BlockBegin *loop_header = _loop_headers.at(i);
   17.71 +      assert(loop_header->is_set(BlockBegin::linear_scan_loop_header_flag), "Must be loop header");
   17.72 +
   17.73 +      for (int j = 0; j < loop_header->number_of_preds(); j++) {
   17.74 +        BlockBegin *pred = loop_header->pred_at(j);
   17.75 +        pred->clear(BlockBegin::linear_scan_loop_end_flag);
   17.76 +      }
   17.77 +
   17.78 +      loop_header->clear(BlockBegin::linear_scan_loop_header_flag);
   17.79 +
   17.80        for (int block_id = _max_block_id - 1; block_id >= 0; block_id--) {
   17.81          clear_block_in_loop(i, block_id);
   17.82        }
   17.83 @@ -729,9 +747,20 @@
   17.84  
   17.85    } else if (!(cur->is_set(BlockBegin::linear_scan_loop_header_flag) && parent->is_set(BlockBegin::linear_scan_loop_end_flag))) {
   17.86      TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: computing dominator of B%d: common dominator of B%d and B%d is B%d", cur->block_id(), parent->block_id(), cur->dominator()->block_id(), common_dominator(cur->dominator(), parent)->block_id()));
   17.87 -    assert(cur->number_of_preds() > 1, "");
   17.88 +    // Does not hold for exception blocks
   17.89 +    assert(cur->number_of_preds() > 1 || cur->is_set(BlockBegin::exception_entry_flag), "");
   17.90      cur->set_dominator(common_dominator(cur->dominator(), parent));
   17.91    }
   17.92 +
   17.93 +  // Additional edge to xhandler of all our successors
   17.94 +  // range check elimination needs that the state at the end of a
   17.95 +  // block be valid in every block it dominates so cur must dominate
   17.96 +  // the exception handlers of its successors.
   17.97 +  int num_cur_xhandler = cur->number_of_exception_handlers();
   17.98 +  for (int j = 0; j < num_cur_xhandler; j++) {
   17.99 +    BlockBegin* xhandler = cur->exception_handler_at(j);
  17.100 +    compute_dominator(xhandler, parent);
  17.101 +  }
  17.102  }
  17.103  
  17.104  
  17.105 @@ -898,7 +927,6 @@
  17.106      num_sux = cur->number_of_exception_handlers();
  17.107      for (i = 0; i < num_sux; i++) {
  17.108        BlockBegin* sux = cur->exception_handler_at(i);
  17.109 -      compute_dominator(sux, cur);
  17.110        if (ready_for_processing(sux)) {
  17.111          sort_into_work_list(sux);
  17.112        }
  17.113 @@ -918,8 +946,23 @@
  17.114  
  17.115      BlockBegin* dominator = block->pred_at(0);
  17.116      int num_preds = block->number_of_preds();
  17.117 -    for (int i = 1; i < num_preds; i++) {
  17.118 -      dominator = common_dominator(dominator, block->pred_at(i));
  17.119 +
  17.120 +    TRACE_LINEAR_SCAN(4, tty->print_cr("DOM: Processing B%d", block->block_id()));
  17.121 +
  17.122 +    for (int j = 0; j < num_preds; j++) {
  17.123 +
  17.124 +      BlockBegin *pred = block->pred_at(j);
  17.125 +      TRACE_LINEAR_SCAN(4, tty->print_cr("   DOM: Subrocessing B%d", pred->block_id()));
  17.126 +
  17.127 +      if (block->is_set(BlockBegin::exception_entry_flag)) {
  17.128 +        dominator = common_dominator(dominator, pred);
  17.129 +        int num_pred_preds = pred->number_of_preds();
  17.130 +        for (int k = 0; k < num_pred_preds; k++) {
  17.131 +          dominator = common_dominator(dominator, pred->pred_at(k));
  17.132 +        }
  17.133 +      } else {
  17.134 +        dominator = common_dominator(dominator, pred);
  17.135 +      }
  17.136      }
  17.137  
  17.138      if (dominator != block->dominator()) {
  17.139 @@ -946,6 +989,21 @@
  17.140  
  17.141    // check that dominators are correct
  17.142    assert(!compute_dominators_iter(), "fix point not reached");
  17.143 +
  17.144 +  // Add Blocks to dominates-Array
  17.145 +  int num_blocks = _linear_scan_order->length();
  17.146 +  for (int i = 0; i < num_blocks; i++) {
  17.147 +    BlockBegin* block = _linear_scan_order->at(i);
  17.148 +
  17.149 +    BlockBegin *dom = block->dominator();
  17.150 +    if (dom) {
  17.151 +      assert(dom->dominator_depth() != -1, "Dominator must have been visited before");
  17.152 +      dom->dominates()->append(block);
  17.153 +      block->set_dominator_depth(dom->dominator_depth() + 1);
  17.154 +    } else {
  17.155 +      block->set_dominator_depth(0);
  17.156 +    }
  17.157 +  }
  17.158  }
  17.159  
  17.160  
  17.161 @@ -1032,7 +1090,7 @@
  17.162        BlockBegin* sux = cur->sux_at(j);
  17.163  
  17.164        assert(sux->linear_scan_number() >= 0 && sux->linear_scan_number() == _linear_scan_order->index_of(sux), "incorrect linear_scan_number");
  17.165 -      if (!cur->is_set(BlockBegin::linear_scan_loop_end_flag)) {
  17.166 +      if (!sux->is_set(BlockBegin::backward_branch_target_flag)) {
  17.167          assert(cur->linear_scan_number() < sux->linear_scan_number(), "invalid order");
  17.168        }
  17.169        if (cur->loop_depth() == sux->loop_depth()) {
  17.170 @@ -1044,7 +1102,7 @@
  17.171        BlockBegin* pred = cur->pred_at(j);
  17.172  
  17.173        assert(pred->linear_scan_number() >= 0 && pred->linear_scan_number() == _linear_scan_order->index_of(pred), "incorrect linear_scan_number");
  17.174 -      if (!cur->is_set(BlockBegin::linear_scan_loop_header_flag)) {
  17.175 +      if (!cur->is_set(BlockBegin::backward_branch_target_flag)) {
  17.176          assert(cur->linear_scan_number() > pred->linear_scan_number(), "invalid order");
  17.177        }
  17.178        if (cur->loop_depth() == pred->loop_depth()) {
  17.179 @@ -1060,7 +1118,8 @@
  17.180      } else {
  17.181        assert(cur->dominator() != NULL, "all but first block must have dominator");
  17.182      }
  17.183 -    assert(cur->number_of_preds() != 1 || cur->dominator() == cur->pred_at(0), "Single predecessor must also be dominator");
  17.184 +    // Assertion does not hold for exception handlers
  17.185 +    assert(cur->number_of_preds() != 1 || cur->dominator() == cur->pred_at(0) || cur->is_set(BlockBegin::exception_entry_flag), "Single predecessor must also be dominator");
  17.186    }
  17.187  
  17.188    // check that all loops are continuous
  17.189 @@ -1249,9 +1308,22 @@
  17.190    }
  17.191  };
  17.192  
  17.193 +class VerifyBlockBeginField : public BlockClosure {
  17.194 +
  17.195 +public:
  17.196 +
  17.197 +  virtual void block_do(BlockBegin *block) {
  17.198 +    for ( Instruction *cur = block; cur != NULL; cur = cur->next()) {
  17.199 +      assert(cur->block() == block, "Block begin is not correct");
  17.200 +    }
  17.201 +  }
  17.202 +};
  17.203 +
  17.204  void IR::verify() {
  17.205  #ifdef ASSERT
  17.206    PredecessorValidator pv(this);
  17.207 +  VerifyBlockBeginField verifier;
  17.208 +  this->iterate_postorder(&verifier);
  17.209  #endif
  17.210  }
  17.211  

    18.1 --- a/src/share/vm/c1/c1_IR.hpp	Wed Mar 20 17:04:45 2013 -0700
    18.2 +++ b/src/share/vm/c1/c1_IR.hpp	Thu Mar 21 09:27:54 2013 +0100
    18.3 @@ -254,6 +254,7 @@
    18.4    OopMap*           _oop_map;
    18.5    ValueStack*       _stack;                      // used by deoptimization (contains also monitors
    18.6    bool              _is_method_handle_invoke;    // true if the associated call site is a MethodHandle call site.
    18.7 +  bool              _deoptimize_on_exception;
    18.8  
    18.9    FrameMap*     frame_map() const                { return scope()->compilation()->frame_map(); }
   18.10    Compilation*  compilation() const              { return scope()->compilation(); }
   18.11 @@ -261,7 +262,7 @@
   18.12   public:
   18.13  
   18.14    // use scope from ValueStack
   18.15 -  CodeEmitInfo(ValueStack* stack, XHandlers* exception_handlers);
   18.16 +  CodeEmitInfo(ValueStack* stack, XHandlers* exception_handlers, bool deoptimize_on_exception = false);
   18.17  
   18.18    // make a copy
   18.19    CodeEmitInfo(CodeEmitInfo* info, ValueStack* stack = NULL);
   18.20 @@ -272,6 +273,7 @@
   18.21    IRScope* scope() const                         { return _scope; }
   18.22    XHandlers* exception_handlers() const          { return _exception_handlers; }
   18.23    ValueStack* stack() const                      { return _stack; }
   18.24 +  bool deoptimize_on_exception() const           { return _deoptimize_on_exception; }
   18.25  
   18.26    void add_register_oop(LIR_Opr opr);
   18.27    void record_debug_info(DebugInformationRecorder* recorder, int pc_offset);
   18.28 @@ -309,7 +311,8 @@
   18.29    int              max_stack() const             { return top_scope()->max_stack(); } // expensive
   18.30  
   18.31    // ir manipulation
   18.32 -  void optimize();
   18.33 +  void optimize_blocks();
   18.34 +  void eliminate_null_checks();
   18.35    void compute_predecessors();
   18.36    void split_critical_edges();
   18.37    void compute_code();

    19.1 --- a/src/share/vm/c1/c1_Instruction.cpp	Wed Mar 20 17:04:45 2013 -0700
    19.2 +++ b/src/share/vm/c1/c1_Instruction.cpp	Thu Mar 21 09:27:54 2013 +0100
    19.3 @@ -34,6 +34,15 @@
    19.4  // Implementation of Instruction
    19.5  
    19.6  
    19.7 +int Instruction::dominator_depth() {
    19.8 +  int result = -1;
    19.9 +  if (block()) {
   19.10 +    result = block()->dominator_depth();
   19.11 +  }
   19.12 +  assert(result != -1 || this->as_Local(), "Only locals have dominator depth -1");
   19.13 +  return result;
   19.14 +}
   19.15 +
   19.16  Instruction::Condition Instruction::mirror(Condition cond) {
   19.17    switch (cond) {
   19.18      case eql: return eql;
   19.19 @@ -42,6 +51,8 @@
   19.20      case leq: return geq;
   19.21      case gtr: return lss;
   19.22      case geq: return leq;
   19.23 +    case aeq: return beq;
   19.24 +    case beq: return aeq;
   19.25    }
   19.26    ShouldNotReachHere();
   19.27    return eql;
   19.28 @@ -56,6 +67,8 @@
   19.29      case leq: return gtr;
   19.30      case gtr: return leq;
   19.31      case geq: return lss;
   19.32 +    case aeq: assert(false, "Above equal cannot be negated");
   19.33 +    case beq: assert(false, "Below equal cannot be negated");
   19.34    }
   19.35    ShouldNotReachHere();
   19.36    return eql;
   19.37 @@ -70,10 +83,10 @@
   19.38    }
   19.39  }
   19.40  
   19.41 -
   19.42 -Instruction* Instruction::prev(BlockBegin* block) {
   19.43 +// Prev without need to have BlockBegin
   19.44 +Instruction* Instruction::prev() {
   19.45    Instruction* p = NULL;
   19.46 -  Instruction* q = block;
   19.47 +  Instruction* q = block();
   19.48    while (q != this) {
   19.49      assert(q != NULL, "this is not in the block's instruction list");
   19.50      p = q; q = q->next();
   19.51 @@ -122,15 +135,24 @@
   19.52  
   19.53  // perform constant and interval tests on index value
   19.54  bool AccessIndexed::compute_needs_range_check() {
   19.55 -  Constant* clength = length()->as_Constant();
   19.56 -  Constant* cindex = index()->as_Constant();
   19.57 -  if (clength && cindex) {
   19.58 -    IntConstant* l = clength->type()->as_IntConstant();
   19.59 -    IntConstant* i = cindex->type()->as_IntConstant();
   19.60 -    if (l && i && i->value() < l->value() && i->value() >= 0) {
   19.61 -      return false;
   19.62 +
   19.63 +  if (length()) {
   19.64 +
   19.65 +    Constant* clength = length()->as_Constant();
   19.66 +    Constant* cindex = index()->as_Constant();
   19.67 +    if (clength && cindex) {
   19.68 +      IntConstant* l = clength->type()->as_IntConstant();
   19.69 +      IntConstant* i = cindex->type()->as_IntConstant();
   19.70 +      if (l && i && i->value() < l->value() && i->value() >= 0) {
   19.71 +        return false;
   19.72 +      }
   19.73      }
   19.74    }
   19.75 +
   19.76 +  if (!this->check_flag(NeedsRangeCheckFlag)) {
   19.77 +    return false;
   19.78 +  }
   19.79 +
   19.80    return true;
   19.81  }
   19.82  
   19.83 @@ -631,19 +653,25 @@
   19.84  // of the inserted block, without recomputing the values of the other blocks
   19.85  // in the CFG. Therefore the value of "depth_first_number" in BlockBegin becomes meaningless.
   19.86  BlockBegin* BlockBegin::insert_block_between(BlockBegin* sux) {
   19.87 -  BlockBegin* new_sux = new BlockBegin(end()->state()->bci());
   19.88 +  int bci = sux->bci();
   19.89 +  // critical edge splitting may introduce a goto after a if and array
   19.90 +  // bound check elimination may insert a predicate between the if and
   19.91 +  // goto. The bci of the goto can't be the one of the if otherwise
   19.92 +  // the state and bci are inconsistent and a deoptimization triggered
   19.93 +  // by the predicate would lead to incorrect execution/a crash.
   19.94 +  BlockBegin* new_sux = new BlockBegin(bci);
   19.95  
   19.96    // mark this block (special treatment when block order is computed)
   19.97    new_sux->set(critical_edge_split_flag);
   19.98  
   19.99    // This goto is not a safepoint.
  19.100    Goto* e = new Goto(sux, false);
  19.101 -  new_sux->set_next(e, end()->state()->bci());
  19.102 +  new_sux->set_next(e, bci);
  19.103    new_sux->set_end(e);
  19.104    // setup states
  19.105    ValueStack* s = end()->state();
  19.106 -  new_sux->set_state(s->copy());
  19.107 -  e->set_state(s->copy());
  19.108 +  new_sux->set_state(s->copy(s->kind(), bci));
  19.109 +  e->set_state(s->copy(s->kind(), bci));
  19.110    assert(new_sux->state()->locals_size() == s->locals_size(), "local size mismatch!");
  19.111    assert(new_sux->state()->stack_size() == s->stack_size(), "stack size mismatch!");
  19.112    assert(new_sux->state()->locks_size() == s->locks_size(), "locks size mismatch!");
  19.113 @@ -960,15 +988,14 @@
  19.114    BlockList* sux = NULL;
  19.115    if (begin != NULL) {
  19.116      sux = begin->successors();
  19.117 -  } else if (_begin != NULL) {
  19.118 +  } else if (this->begin() != NULL) {
  19.119      // copy our sux list
  19.120 -    BlockList* sux = new BlockList(_begin->number_of_sux());
  19.121 -    for (int i = 0; i < _begin->number_of_sux(); i++) {
  19.122 -      sux->append(_begin->sux_at(i));
  19.123 +    BlockList* sux = new BlockList(this->begin()->number_of_sux());
  19.124 +    for (int i = 0; i < this->begin()->number_of_sux(); i++) {
  19.125 +      sux->append(this->begin()->sux_at(i));
  19.126      }
  19.127    }
  19.128    _sux = sux;
  19.129 -  _begin = begin;
  19.130  }
  19.131  
  19.132  
  19.133 @@ -1008,7 +1035,38 @@
  19.134    }
  19.135  }
  19.136  
  19.137 +#ifdef ASSERT
  19.138 +// Constructor of Assert
  19.139 +Assert::Assert(Value x, Condition cond, bool unordered_is_true, Value y) : Instruction(illegalType)
  19.140 +  , _x(x)
  19.141 +  , _cond(cond)
  19.142 +  , _y(y)
  19.143 +{
  19.144 +  set_flag(UnorderedIsTrueFlag, unordered_is_true);
  19.145 +  assert(x->type()->tag() == y->type()->tag(), "types must match");
  19.146 +  pin();
  19.147  
  19.148 +  stringStream strStream;
  19.149 +  Compilation::current()->method()->print_name(&strStream);
  19.150 +
  19.151 +  stringStream strStream1;
  19.152 +  InstructionPrinter ip1(1, &strStream1);
  19.153 +  ip1.print_instr(x);
  19.154 +
  19.155 +  stringStream strStream2;
  19.156 +  InstructionPrinter ip2(1, &strStream2);
  19.157 +  ip2.print_instr(y);
  19.158 +
  19.159 +  stringStream ss;
  19.160 +  ss.print("Assertion %s %s %s in method %s", strStream1.as_string(), ip2.cond_name(cond), strStream2.as_string(), strStream.as_string());
  19.161 +
  19.162 +  _message = ss.as_string();
  19.163 +}
  19.164 +#endif
  19.165 +
  19.166 +void RangeCheckPredicate::check_state() {
  19.167 +  assert(state()->kind() != ValueStack::EmptyExceptionState && state()->kind() != ValueStack::ExceptionState, "will deopt with empty state");
  19.168 +}
  19.169  
  19.170  void ProfileInvoke::state_values_do(ValueVisitor* f) {
  19.171    if (state() != NULL) state()->values_do(f);

    20.1 --- a/src/share/vm/c1/c1_Instruction.hpp	Wed Mar 20 17:04:45 2013 -0700
    20.2 +++ b/src/share/vm/c1/c1_Instruction.hpp	Thu Mar 21 09:27:54 2013 +0100
    20.3 @@ -110,6 +110,8 @@
    20.4  class   ProfileInvoke;
    20.5  class   RuntimeCall;
    20.6  class   MemBar;
    20.7 +class   RangeCheckPredicate;
    20.8 +class   Assert;
    20.9  
   20.10  // A Value is a reference to the instruction creating the value
   20.11  typedef Instruction* Value;
   20.12 @@ -210,6 +212,10 @@
   20.13    virtual void do_ProfileInvoke  (ProfileInvoke*   x) = 0;
   20.14    virtual void do_RuntimeCall    (RuntimeCall*     x) = 0;
   20.15    virtual void do_MemBar         (MemBar*          x) = 0;
   20.16 +  virtual void do_RangeCheckPredicate(RangeCheckPredicate* x) = 0;
   20.17 +#ifdef ASSERT
   20.18 +  virtual void do_Assert         (Assert*          x) = 0;
   20.19 +#endif
   20.20  };
   20.21  
   20.22  
   20.23 @@ -306,8 +312,9 @@
   20.24  
   20.25    void update_exception_state(ValueStack* state);
   20.26  
   20.27 - //protected:
   20.28 - public:
   20.29 + protected:
   20.30 +  BlockBegin*  _block;                           // Block that contains this instruction
   20.31 +
   20.32    void set_type(ValueType* type) {
   20.33      assert(type != NULL, "type must exist");
   20.34      _type = type;
   20.35 @@ -342,6 +349,9 @@
   20.36      ThrowIncompatibleClassChangeErrorFlag,
   20.37      ProfileMDOFlag,
   20.38      IsLinkedInBlockFlag,
   20.39 +    NeedsRangeCheckFlag,
   20.40 +    InWorkListFlag,
   20.41 +    DeoptimizeOnException,
   20.42      InstructionLastFlag
   20.43    };
   20.44  
   20.45 @@ -351,7 +361,7 @@
   20.46  
   20.47    // 'globally' used condition values
   20.48    enum Condition {
   20.49 -    eql, neq, lss, leq, gtr, geq
   20.50 +    eql, neq, lss, leq, gtr, geq, aeq, beq
   20.51    };
   20.52  
   20.53    // Instructions may be pinned for many reasons and under certain conditions
   20.54 @@ -381,6 +391,7 @@
   20.55    , _pin_state(0)
   20.56    , _type(type)
   20.57    , _next(NULL)
   20.58 +  , _block(NULL)
   20.59    , _subst(NULL)
   20.60    , _flags(0)
   20.61    , _operand(LIR_OprFact::illegalOpr)
   20.62 @@ -399,11 +410,13 @@
   20.63    int printable_bci() const                      { assert(has_printable_bci(), "_printable_bci should have been set"); return _printable_bci; }
   20.64    void set_printable_bci(int bci)                { _printable_bci = bci; }
   20.65  #endif
   20.66 +  int dominator_depth();
   20.67    int use_count() const                          { return _use_count; }
   20.68    int pin_state() const                          { return _pin_state; }
   20.69    bool is_pinned() const                         { return _pin_state != 0 || PinAllInstructions; }
   20.70    ValueType* type() const                        { return _type; }
   20.71 -  Instruction* prev(BlockBegin* block);          // use carefully, expensive operation
   20.72 +  BlockBegin *block() const                      { return _block; }
   20.73 +  Instruction* prev();                           // use carefully, expensive operation
   20.74    Instruction* next() const                      { return _next; }
   20.75    bool has_subst() const                         { return _subst != NULL; }
   20.76    Instruction* subst()                           { return _subst == NULL ? this : _subst->subst(); }
   20.77 @@ -432,6 +445,9 @@
   20.78      assert(as_BlockEnd() == NULL, "BlockEnd instructions must have no next");
   20.79      assert(next->can_be_linked(), "shouldn't link these instructions into list");
   20.80  
   20.81 +    BlockBegin *block = this->block();
   20.82 +    next->_block = block;
   20.83 +
   20.84      next->set_flag(Instruction::IsLinkedInBlockFlag, true);
   20.85      _next = next;
   20.86      return next;
   20.87 @@ -444,6 +460,29 @@
   20.88      return set_next(next);
   20.89    }
   20.90  
   20.91 +  // when blocks are merged
   20.92 +  void fixup_block_pointers() {
   20.93 +    Instruction *cur = next()->next(); // next()'s block is set in set_next
   20.94 +    while (cur && cur->_block != block()) {
   20.95 +      cur->_block = block();
   20.96 +      cur = cur->next();
   20.97 +    }
   20.98 +  }
   20.99 +
  20.100 +  Instruction *insert_after(Instruction *i) {
  20.101 +    Instruction* n = _next;
  20.102 +    set_next(i);
  20.103 +    i->set_next(n);
  20.104 +    return _next;
  20.105 +  }
  20.106 +
  20.107 +  Instruction *insert_after_same_bci(Instruction *i) {
  20.108 +#ifndef PRODUCT
  20.109 +    i->set_printable_bci(printable_bci());
  20.110 +#endif
  20.111 +    return insert_after(i);
  20.112 +  }
  20.113 +
  20.114    void set_subst(Instruction* subst)             {
  20.115      assert(subst == NULL ||
  20.116             type()->base() == subst->type()->base() ||
  20.117 @@ -452,6 +491,7 @@
  20.118    }
  20.119    void set_exception_handlers(XHandlers *xhandlers) { _exception_handlers = xhandlers; }
  20.120    void set_exception_state(ValueStack* s)        { check_state(s); _exception_state = s; }
  20.121 +  void set_state_before(ValueStack* s)           { check_state(s); _state_before = s; }
  20.122  
  20.123    // machine-specifics
  20.124    void set_operand(LIR_Opr operand)              { assert(operand != LIR_OprFact::illegalOpr, "operand must exist"); _operand = operand; }
  20.125 @@ -509,6 +549,11 @@
  20.126    virtual ExceptionObject*  as_ExceptionObject() { return NULL; }
  20.127    virtual UnsafeOp*         as_UnsafeOp()        { return NULL; }
  20.128    virtual ProfileInvoke*    as_ProfileInvoke()   { return NULL; }
  20.129 +  virtual RangeCheckPredicate* as_RangeCheckPredicate() { return NULL; }
  20.130 +
  20.131 +#ifdef ASSERT
  20.132 +  virtual Assert*           as_Assert()          { return NULL; }
  20.133 +#endif
  20.134  
  20.135    virtual void visit(InstructionVisitor* v)      = 0;
  20.136  
  20.137 @@ -570,7 +615,6 @@
  20.138  
  20.139  LEAF(Phi, Instruction)
  20.140   private:
  20.141 -  BlockBegin* _block;    // the block to which the phi function belongs
  20.142    int         _pf_flags; // the flags of the phi function
  20.143    int         _index;    // to value on operand stack (index < 0) or to local
  20.144   public:
  20.145 @@ -578,9 +622,9 @@
  20.146    Phi(ValueType* type, BlockBegin* b, int index)
  20.147    : Instruction(type->base())
  20.148    , _pf_flags(0)
  20.149 -  , _block(b)
  20.150    , _index(index)
  20.151    {
  20.152 +    _block = b;
  20.153      NOT_PRODUCT(set_printable_bci(Value(b)->printable_bci()));
  20.154      if (type->is_illegal()) {
  20.155        make_illegal();
  20.156 @@ -603,8 +647,6 @@
  20.157    Value operand_at(int i) const;
  20.158    int   operand_count() const;
  20.159  
  20.160 -  BlockBegin* block() const       { return _block; }
  20.161 -
  20.162    void   set(Flag f)              { _pf_flags |=  f; }
  20.163    void   clear(Flag f)            { _pf_flags &= ~f; }
  20.164    bool   is_set(Flag f) const     { return (_pf_flags & f) != 0; }
  20.165 @@ -670,6 +712,7 @@
  20.166      pin();
  20.167    }
  20.168  
  20.169 +  // generic
  20.170    virtual bool can_trap() const                  { return state_before() != NULL; }
  20.171    virtual void input_values_do(ValueVisitor* f)   { /* no values */ }
  20.172  
  20.173 @@ -852,6 +895,7 @@
  20.174    , _length(length)
  20.175    , _elt_type(elt_type)
  20.176    {
  20.177 +    set_flag(Instruction::NeedsRangeCheckFlag, true);
  20.178      ASSERT_VALUES
  20.179    }
  20.180  
  20.181 @@ -860,6 +904,7 @@
  20.182    Value length() const                           { return _length; }
  20.183    BasicType elt_type() const                     { return _elt_type; }
  20.184  
  20.185 +  void clear_length()                            { _length = NULL; }
  20.186    // perform elimination of range checks involving constants
  20.187    bool compute_needs_range_check();
  20.188  
  20.189 @@ -1524,6 +1569,7 @@
  20.190    int        _bci;                               // start-bci of block
  20.191    int        _depth_first_number;                // number of this block in a depth-first ordering
  20.192    int        _linear_scan_number;                // number of this block in linear-scan ordering
  20.193 +  int        _dominator_depth;
  20.194    int        _loop_depth;                        // the loop nesting level of this block
  20.195    int        _loop_index;                        // number of the innermost loop of this block
  20.196    int        _flags;                             // the flags associated with this block
  20.197 @@ -1535,6 +1581,7 @@
  20.198    // SSA specific fields: (factor out later)
  20.199    BlockList   _successors;                       // the successors of this block
  20.200    BlockList   _predecessors;                     // the predecessors of this block
  20.201 +  BlockList   _dominates;                        // list of blocks that are dominated by this block
  20.202    BlockBegin* _dominator;                        // the dominator of this block
  20.203    // SSA specific ends
  20.204    BlockEnd*  _end;                               // the last instruction of this block
  20.205 @@ -1583,10 +1630,12 @@
  20.206    , _linear_scan_number(-1)
  20.207    , _loop_depth(0)
  20.208    , _flags(0)
  20.209 +  , _dominator_depth(-1)
  20.210    , _dominator(NULL)
  20.211    , _end(NULL)
  20.212    , _predecessors(2)
  20.213    , _successors(2)
  20.214 +  , _dominates(2)
  20.215    , _exception_handlers(1)
  20.216    , _exception_states(NULL)
  20.217    , _exception_handler_pco(-1)
  20.218 @@ -1603,6 +1652,7 @@
  20.219    , _total_preds(0)
  20.220    , _stores_to_locals()
  20.221    {
  20.222 +    _block = this;
  20.223  #ifndef PRODUCT
  20.224      set_printable_bci(bci);
  20.225  #endif
  20.226 @@ -1612,8 +1662,10 @@
  20.227    int block_id() const                           { return _block_id; }
  20.228    int bci() const                                { return _bci; }
  20.229    BlockList* successors()                        { return &_successors; }
  20.230 +  BlockList* dominates()                         { return &_dominates; }
  20.231    BlockBegin* dominator() const                  { return _dominator; }
  20.232    int loop_depth() const                         { return _loop_depth; }
  20.233 +  int dominator_depth() const                    { return _dominator_depth; }
  20.234    int depth_first_number() const                 { return _depth_first_number; }
  20.235    int linear_scan_number() const                 { return _linear_scan_number; }
  20.236    BlockEnd* end() const                          { return _end; }
  20.237 @@ -1634,6 +1686,7 @@
  20.238    // manipulation
  20.239    void set_dominator(BlockBegin* dom)            { _dominator = dom; }
  20.240    void set_loop_depth(int d)                     { _loop_depth = d; }
  20.241 +  void set_dominator_depth(int d)                { _dominator_depth = d; }
  20.242    void set_depth_first_number(int dfn)           { _depth_first_number = dfn; }
  20.243    void set_linear_scan_number(int lsn)           { _linear_scan_number = lsn; }
  20.244    void set_end(BlockEnd* end);
  20.245 @@ -1695,7 +1748,8 @@
  20.246      parser_loop_header_flag       = 1 << 7,  // set by parser to identify blocks where phi functions can not be created on demand
  20.247      critical_edge_split_flag      = 1 << 8, // set for all blocks that are introduced when critical edges are split
  20.248      linear_scan_loop_header_flag  = 1 << 9, // set during loop-detection for LinearScan
  20.249 -    linear_scan_loop_end_flag     = 1 << 10  // set during loop-detection for LinearScan
  20.250 +    linear_scan_loop_end_flag     = 1 << 10, // set during loop-detection for LinearScan
  20.251 +    donot_eliminate_range_checks  = 1 << 11  // Should be try to eliminate range checks in this block
  20.252    };
  20.253  
  20.254    void set(Flag f)                               { _flags |= f; }
  20.255 @@ -1728,7 +1782,6 @@
  20.256  
  20.257  BASE(BlockEnd, StateSplit)
  20.258   private:
  20.259 -  BlockBegin* _begin;
  20.260    BlockList*  _sux;
  20.261  
  20.262   protected:
  20.263 @@ -1746,7 +1799,6 @@
  20.264    // creation
  20.265    BlockEnd(ValueType* type, ValueStack* state_before, bool is_safepoint)
  20.266    : StateSplit(type, state_before)
  20.267 -  , _begin(NULL)
  20.268    , _sux(NULL)
  20.269    {
  20.270      set_flag(IsSafepointFlag, is_safepoint);
  20.271 @@ -1754,7 +1806,8 @@
  20.272  
  20.273    // accessors
  20.274    bool is_safepoint() const                      { return check_flag(IsSafepointFlag); }
  20.275 -  BlockBegin* begin() const                      { return _begin; }
  20.276 +  // For compatibility with old code, for new code use block()
  20.277 +  BlockBegin* begin() const                      { return _block; }
  20.278  
  20.279    // manipulation
  20.280    void set_begin(BlockBegin* begin);
  20.281 @@ -1811,6 +1864,74 @@
  20.282    void set_direction(Direction d)                { _direction = d; }
  20.283  };
  20.284  
  20.285 +#ifdef ASSERT
  20.286 +LEAF(Assert, Instruction)
  20.287 +  private:
  20.288 +  Value       _x;
  20.289 +  Condition   _cond;
  20.290 +  Value       _y;
  20.291 +  char        *_message;
  20.292 +
  20.293 + public:
  20.294 +  // creation
  20.295 +  // unordered_is_true is valid for float/double compares only
  20.296 +   Assert(Value x, Condition cond, bool unordered_is_true, Value y);
  20.297 +
  20.298 +  // accessors
  20.299 +  Value x() const                                { return _x; }
  20.300 +  Condition cond() const                         { return _cond; }
  20.301 +  bool unordered_is_true() const                 { return check_flag(UnorderedIsTrueFlag); }
  20.302 +  Value y() const                                { return _y; }
  20.303 +  const char *message() const                    { return _message; }
  20.304 +
  20.305 +  // generic
  20.306 +  virtual void input_values_do(ValueVisitor* f)  { f->visit(&_x); f->visit(&_y); }
  20.307 +};
  20.308 +#endif
  20.309 +
  20.310 +LEAF(RangeCheckPredicate, StateSplit)
  20.311 + private:
  20.312 +  Value       _x;
  20.313 +  Condition   _cond;
  20.314 +  Value       _y;
  20.315 +
  20.316 +  void check_state();
  20.317 +
  20.318 + public:
  20.319 +  // creation
  20.320 +  // unordered_is_true is valid for float/double compares only
  20.321 +   RangeCheckPredicate(Value x, Condition cond, bool unordered_is_true, Value y, ValueStack* state) : StateSplit(illegalType)
  20.322 +  , _x(x)
  20.323 +  , _cond(cond)
  20.324 +  , _y(y)
  20.325 +  {
  20.326 +    ASSERT_VALUES
  20.327 +    set_flag(UnorderedIsTrueFlag, unordered_is_true);
  20.328 +    assert(x->type()->tag() == y->type()->tag(), "types must match");
  20.329 +    this->set_state(state);
  20.330 +    check_state();
  20.331 +  }
  20.332 +
  20.333 +  // Always deoptimize
  20.334 +  RangeCheckPredicate(ValueStack* state) : StateSplit(illegalType)
  20.335 +  {
  20.336 +    this->set_state(state);
  20.337 +    _x = _y = NULL;
  20.338 +    check_state();
  20.339 +  }
  20.340 +
  20.341 +  // accessors
  20.342 +  Value x() const                                { return _x; }
  20.343 +  Condition cond() const                         { return _cond; }
  20.344 +  bool unordered_is_true() const                 { return check_flag(UnorderedIsTrueFlag); }
  20.345 +  Value y() const                                { return _y; }
  20.346 +
  20.347 +  void always_fail()                             { _x = _y = NULL; }
  20.348 +
  20.349 +  // generic
  20.350 +  virtual void input_values_do(ValueVisitor* f)  { StateSplit::input_values_do(f); f->visit(&_x); f->visit(&_y); }
  20.351 +  HASHING3(RangeCheckPredicate, true, x()->subst(), y()->subst(), cond())
  20.352 +};
  20.353  
  20.354  LEAF(If, BlockEnd)
  20.355   private:

    21.1 --- a/src/share/vm/c1/c1_InstructionPrinter.cpp	Wed Mar 20 17:04:45 2013 -0700
    21.2 +++ b/src/share/vm/c1/c1_InstructionPrinter.cpp	Thu Mar 21 09:27:54 2013 +0100
    21.3 @@ -57,6 +57,8 @@
    21.4      case If::leq: return "<=";
    21.5      case If::gtr: return ">";
    21.6      case If::geq: return ">=";
    21.7 +    case If::aeq: return "|>=|";
    21.8 +    case If::beq: return "|<=|";
    21.9    }
   21.10    ShouldNotReachHere();
   21.11    return NULL;
   21.12 @@ -181,6 +183,11 @@
   21.13    output()->put('[');
   21.14    print_value(indexed->index());
   21.15    output()->put(']');
   21.16 +  if (indexed->length() != NULL) {
   21.17 +    output()->put('(');
   21.18 +    print_value(indexed->length());
   21.19 +    output()->put(')');
   21.20 +  }
   21.21  }
   21.22  
   21.23  
   21.24 @@ -373,6 +380,7 @@
   21.25  void InstructionPrinter::do_LoadField(LoadField* x) {
   21.26    print_field(x);
   21.27    output()->print(" (%c)", type2char(x->field()->type()->basic_type()));
   21.28 +  output()->print(" %s", x->field()->name()->as_utf8());
   21.29  }
   21.30  
   21.31  
   21.32 @@ -381,6 +389,7 @@
   21.33    output()->print(" := ");
   21.34    print_value(x->value());
   21.35    output()->print(" (%c)", type2char(x->field()->type()->basic_type()));
   21.36 +  output()->print(" %s", x->field()->name()->as_utf8());
   21.37  }
   21.38  
   21.39  
   21.40 @@ -393,6 +402,9 @@
   21.41  void InstructionPrinter::do_LoadIndexed(LoadIndexed* x) {
   21.42    print_indexed(x);
   21.43    output()->print(" (%c)", type2char(x->elt_type()));
   21.44 +  if (x->check_flag(Instruction::NeedsRangeCheckFlag)) {
   21.45 +    output()->print(" [rc]");
   21.46 +  }
   21.47  }
   21.48  
   21.49  
   21.50 @@ -401,6 +413,9 @@
   21.51    output()->print(" := ");
   21.52    print_value(x->value());
   21.53    output()->print(" (%c)", type2char(x->elt_type()));
   21.54 +  if (x->check_flag(Instruction::NeedsRangeCheckFlag)) {
   21.55 +    output()->print(" [rc]");
   21.56 +  }
   21.57  }
   21.58  
   21.59  void InstructionPrinter::do_NegateOp(NegateOp* x) {
   21.60 @@ -843,6 +858,25 @@
   21.61    output()->put(')');
   21.62  }
   21.63  
   21.64 +void InstructionPrinter::do_RangeCheckPredicate(RangeCheckPredicate* x) {
   21.65 +
   21.66 +  if (x->x() != NULL && x->y() != NULL) {
   21.67 +    output()->print("if ");
   21.68 +    print_value(x->x());
   21.69 +    output()->print(" %s ", cond_name(x->cond()));
   21.70 +    print_value(x->y());
   21.71 +    output()->print(" then deoptimize!");
   21.72 +  } else {
   21.73 +    output()->print("always deoptimize!");
   21.74 +  }
   21.75 +}
   21.76 +
   21.77 +void InstructionPrinter::do_Assert(Assert* x) {
   21.78 +  output()->print("assert ");
   21.79 +  print_value(x->x());
   21.80 +  output()->print(" %s ", cond_name(x->cond()));
   21.81 +  print_value(x->y());
   21.82 +}
   21.83  
   21.84  void InstructionPrinter::do_UnsafePrefetchWrite(UnsafePrefetchWrite* x) {
   21.85    print_unsafe_object_op(x, "UnsafePrefetchWrite");

    22.1 --- a/src/share/vm/c1/c1_InstructionPrinter.hpp	Wed Mar 20 17:04:45 2013 -0700
    22.2 +++ b/src/share/vm/c1/c1_InstructionPrinter.hpp	Thu Mar 21 09:27:54 2013 +0100
    22.3 @@ -135,6 +135,8 @@
    22.4    virtual void do_ProfileInvoke  (ProfileInvoke*   x);
    22.5    virtual void do_RuntimeCall    (RuntimeCall*     x);
    22.6    virtual void do_MemBar         (MemBar*          x);
    22.7 +  virtual void do_RangeCheckPredicate(RangeCheckPredicate* x);
    22.8 +  virtual void do_Assert         (Assert*          x);
    22.9  };
   22.10  #endif // PRODUCT
   22.11  

    23.1 --- a/src/share/vm/c1/c1_LIR.cpp	Wed Mar 20 17:04:45 2013 -0700
    23.2 +++ b/src/share/vm/c1/c1_LIR.cpp	Thu Mar 21 09:27:54 2013 +0100
    23.3 @@ -633,6 +633,7 @@
    23.4      case lir_ushr:
    23.5      case lir_xadd:
    23.6      case lir_xchg:
    23.7 +    case lir_assert:
    23.8      {
    23.9        assert(op->as_Op2() != NULL, "must be");
   23.10        LIR_Op2* op2 = (LIR_Op2*)op;
   23.11 @@ -1112,6 +1113,11 @@
   23.12    }
   23.13  }
   23.14  
   23.15 +#ifdef ASSERT
   23.16 +void LIR_OpAssert::emit_code(LIR_Assembler* masm) {
   23.17 +  masm->emit_assert(this);
   23.18 +}
   23.19 +#endif
   23.20  
   23.21  void LIR_OpDelay::emit_code(LIR_Assembler* masm) {
   23.22    masm->emit_delay(this);
   23.23 @@ -1771,6 +1777,8 @@
   23.24       case lir_cas_int:               s = "cas_int";      break;
   23.25       // LIR_OpProfileCall
   23.26       case lir_profile_call:          s = "profile_call";  break;
   23.27 +     // LIR_OpAssert
   23.28 +     case lir_assert:                s = "assert";        break;
   23.29       case lir_none:                  ShouldNotReachHere();break;
   23.30      default:                         s = "illegal_op";    break;
   23.31    }
   23.32 @@ -2017,6 +2025,13 @@
   23.33    out->print("[lbl:0x%x]", stub()->entry());
   23.34  }
   23.35  
   23.36 +void LIR_OpAssert::print_instr(outputStream* out) const {
   23.37 +  print_condition(out, condition()); out->print(" ");
   23.38 +  in_opr1()->print(out);             out->print(" ");
   23.39 +  in_opr2()->print(out);             out->print(", \"");
   23.40 +  out->print(msg());                 out->print("\"");
   23.41 +}
   23.42 +
   23.43  
   23.44  void LIR_OpDelay::print_instr(outputStream* out) const {
   23.45    _op->print_on(out);

    24.1 --- a/src/share/vm/c1/c1_LIR.hpp	Wed Mar 20 17:04:45 2013 -0700
    24.2 +++ b/src/share/vm/c1/c1_LIR.hpp	Thu Mar 21 09:27:54 2013 +0100
    24.3 @@ -881,6 +881,7 @@
    24.4  class    LIR_OpTypeCheck;
    24.5  class    LIR_OpCompareAndSwap;
    24.6  class    LIR_OpProfileCall;
    24.7 +class    LIR_OpAssert;
    24.8  
    24.9  
   24.10  // LIR operation codes
   24.11 @@ -1000,6 +1001,9 @@
   24.12    , begin_opMDOProfile
   24.13      , lir_profile_call
   24.14    , end_opMDOProfile
   24.15 +  , begin_opAssert
   24.16 +    , lir_assert
   24.17 +  , end_opAssert
   24.18  };
   24.19  
   24.20  
   24.21 @@ -1135,6 +1139,7 @@
   24.22    virtual LIR_OpTypeCheck* as_OpTypeCheck() { return NULL; }
   24.23    virtual LIR_OpCompareAndSwap* as_OpCompareAndSwap() { return NULL; }
   24.24    virtual LIR_OpProfileCall* as_OpProfileCall() { return NULL; }
   24.25 +  virtual LIR_OpAssert* as_OpAssert() { return NULL; }
   24.26  
   24.27    virtual void verify() const {}
   24.28  };
   24.29 @@ -1623,7 +1628,7 @@
   24.30      , _tmp3(LIR_OprFact::illegalOpr)
   24.31      , _tmp4(LIR_OprFact::illegalOpr)
   24.32      , _tmp5(LIR_OprFact::illegalOpr) {
   24.33 -    assert(code == lir_cmp, "code check");
   24.34 +    assert(code == lir_cmp || code == lir_assert, "code check");
   24.35    }
   24.36  
   24.37    LIR_Op2(LIR_Code code, LIR_Condition condition, LIR_Opr opr1, LIR_Opr opr2, LIR_Opr result, BasicType type)
   24.38 @@ -1683,7 +1688,7 @@
   24.39    LIR_Opr tmp4_opr() const                       { return _tmp4; }
   24.40    LIR_Opr tmp5_opr() const                       { return _tmp5; }
   24.41    LIR_Condition condition() const  {
   24.42 -    assert(code() == lir_cmp || code() == lir_cmove, "only valid for cmp and cmove"); return _condition;
   24.43 +    assert(code() == lir_cmp || code() == lir_cmove || code() == lir_assert, "only valid for cmp and cmove and assert"); return _condition;
   24.44    }
   24.45    void set_condition(LIR_Condition condition) {
   24.46      assert(code() == lir_cmp || code() == lir_cmove, "only valid for cmp and cmove");  _condition = condition;
   24.47 @@ -1823,6 +1828,30 @@
   24.48    CodeEmitInfo* call_info() const { return info(); }
   24.49  };
   24.50  
   24.51 +#ifdef ASSERT
   24.52 +// LIR_OpAssert
   24.53 +class LIR_OpAssert : public LIR_Op2 {
   24.54 + friend class LIR_OpVisitState;
   24.55 +
   24.56 + private:
   24.57 +  const char* _msg;
   24.58 +  bool        _halt;
   24.59 +
   24.60 + public:
   24.61 +  LIR_OpAssert(LIR_Condition condition, LIR_Opr opr1, LIR_Opr opr2, const char* msg, bool halt)
   24.62 +    : LIR_Op2(lir_assert, condition, opr1, opr2)
   24.63 +    , _halt(halt)
   24.64 +    , _msg(msg) {
   24.65 +  }
   24.66 +
   24.67 +  const char* msg() const                        { return _msg; }
   24.68 +  bool        halt() const                       { return _halt; }
   24.69 +
   24.70 +  virtual void emit_code(LIR_Assembler* masm);
   24.71 +  virtual LIR_OpAssert* as_OpAssert()            { return this; }
   24.72 +  virtual void print_instr(outputStream* out) const PRODUCT_RETURN;
   24.73 +};
   24.74 +#endif
   24.75  
   24.76  // LIR_OpCompareAndSwap
   24.77  class LIR_OpCompareAndSwap : public LIR_Op {
   24.78 @@ -2196,6 +2225,9 @@
   24.79  
   24.80    void xadd(LIR_Opr src, LIR_Opr add, LIR_Opr res, LIR_Opr tmp) { append(new LIR_Op2(lir_xadd, src, add, res, tmp)); }
   24.81    void xchg(LIR_Opr src, LIR_Opr set, LIR_Opr res, LIR_Opr tmp) { append(new LIR_Op2(lir_xchg, src, set, res, tmp)); }
   24.82 +#ifdef ASSERT
   24.83 +  void lir_assert(LIR_Condition condition, LIR_Opr opr1, LIR_Opr opr2, const char* msg, bool halt) { append(new LIR_OpAssert(condition, opr1, opr2, msg, halt)); }
   24.84 +#endif
   24.85  };
   24.86  
   24.87  void print_LIR(BlockList* blocks);

    25.1 --- a/src/share/vm/c1/c1_LIRAssembler.hpp	Wed Mar 20 17:04:45 2013 -0700
    25.2 +++ b/src/share/vm/c1/c1_LIRAssembler.hpp	Thu Mar 21 09:27:54 2013 +0100
    25.3 @@ -210,6 +210,9 @@
    25.4    void arith_op(LIR_Code code, LIR_Opr left, LIR_Opr right, LIR_Opr dest, CodeEmitInfo* info, bool pop_fpu_stack);
    25.5    void arithmetic_idiv(LIR_Code code, LIR_Opr left, LIR_Opr right, LIR_Opr temp, LIR_Opr result, CodeEmitInfo* info);
    25.6    void intrinsic_op(LIR_Code code, LIR_Opr value, LIR_Opr unused, LIR_Opr dest, LIR_Op* op);
    25.7 +#ifdef ASSERT
    25.8 +  void emit_assert(LIR_OpAssert* op);
    25.9 +#endif
   25.10  
   25.11    void logic_op(LIR_Code code, LIR_Opr left, LIR_Opr right, LIR_Opr dest);
   25.12  

    26.1 --- a/src/share/vm/c1/c1_LIRGenerator.cpp	Wed Mar 20 17:04:45 2013 -0700
    26.2 +++ b/src/share/vm/c1/c1_LIRGenerator.cpp	Thu Mar 21 09:27:54 2013 +0100
    26.3 @@ -403,6 +403,10 @@
    26.4  CodeEmitInfo* LIRGenerator::state_for(Instruction* x, ValueStack* state, bool ignore_xhandler) {
    26.5    assert(state != NULL, "state must be defined");
    26.6  
    26.7 +#ifndef PRODUCT
    26.8 +  state->verify();
    26.9 +#endif
   26.10 +
   26.11    ValueStack* s = state;
   26.12    for_each_state(s) {
   26.13      if (s->kind() == ValueStack::EmptyExceptionState) {
   26.14 @@ -453,7 +457,7 @@
   26.15      }
   26.16    }
   26.17  
   26.18 -  return new CodeEmitInfo(state, ignore_xhandler ? NULL : x->exception_handlers());
   26.19 +  return new CodeEmitInfo(state, ignore_xhandler ? NULL : x->exception_handlers(), x->check_flag(Instruction::DeoptimizeOnException));
   26.20  }
   26.21  
   26.22  
   26.23 @@ -1792,11 +1796,18 @@
   26.24    }
   26.25  #endif
   26.26  
   26.27 +  bool stress_deopt = StressLoopInvariantCodeMotion && info && info->deoptimize_on_exception();
   26.28    if (x->needs_null_check() &&
   26.29        (needs_patching ||
   26.30 -       MacroAssembler::needs_explicit_null_check(x->offset()))) {
   26.31 +       MacroAssembler::needs_explicit_null_check(x->offset()) ||
   26.32 +       stress_deopt)) {
   26.33 +    LIR_Opr obj = object.result();
   26.34 +    if (stress_deopt) {
   26.35 +      obj = new_register(T_OBJECT);
   26.36 +      __ move(LIR_OprFact::oopConst(NULL), obj);
   26.37 +    }
   26.38      // emit an explicit null check because the offset is too large
   26.39 -    __ null_check(object.result(), new CodeEmitInfo(info));
   26.40 +    __ null_check(obj, new CodeEmitInfo(info));
   26.41    }
   26.42  
   26.43    LIR_Opr reg = rlock_result(x, field_type);
   26.44 @@ -1861,6 +1872,8 @@
   26.45  
   26.46  
   26.47  void LIRGenerator::do_ArrayLength(ArrayLength* x) {
   26.48 +  if (x->use_count() == 0 && !x->can_trap()) return;
   26.49 +
   26.50    LIRItem array(x->array(), this);
   26.51    array.load_item();
   26.52    LIR_Opr reg = rlock_result(x);
   26.53 @@ -1873,6 +1886,11 @@
   26.54      } else {
   26.55        info = state_for(nc);
   26.56      }
   26.57 +    if (StressLoopInvariantCodeMotion && info->deoptimize_on_exception()) {
   26.58 +      LIR_Opr obj = new_register(T_OBJECT);
   26.59 +      __ move(LIR_OprFact::oopConst(NULL), obj);
   26.60 +      __ null_check(obj, new CodeEmitInfo(info));
   26.61 +    }
   26.62    }
   26.63    __ load(new LIR_Address(array.result(), arrayOopDesc::length_offset_in_bytes(), T_INT), reg, info, lir_patch_none);
   26.64  }
   26.65 @@ -1883,14 +1901,11 @@
   26.66    LIRItem array(x->array(), this);
   26.67    LIRItem index(x->index(), this);
   26.68    LIRItem length(this);
   26.69 -  bool needs_range_check = true;
   26.70 -
   26.71 -  if (use_length) {
   26.72 -    needs_range_check = x->compute_needs_range_check();
   26.73 -    if (needs_range_check) {
   26.74 -      length.set_instruction(x->length());
   26.75 -      length.load_item();
   26.76 -    }
   26.77 +  bool needs_range_check = x->compute_needs_range_check();
   26.78 +
   26.79 +  if (use_length && needs_range_check) {
   26.80 +    length.set_instruction(x->length());
   26.81 +    length.load_item();
   26.82    }
   26.83  
   26.84    array.load_item();
   26.85 @@ -1910,13 +1925,20 @@
   26.86      } else {
   26.87        null_check_info = range_check_info;
   26.88      }
   26.89 +    if (StressLoopInvariantCodeMotion && null_check_info->deoptimize_on_exception()) {
   26.90 +      LIR_Opr obj = new_register(T_OBJECT);
   26.91 +      __ move(LIR_OprFact::oopConst(NULL), obj);
   26.92 +      __ null_check(obj, new CodeEmitInfo(null_check_info));
   26.93 +    }
   26.94    }
   26.95  
   26.96    // emit array address setup early so it schedules better
   26.97    LIR_Address* array_addr = emit_array_address(array.result(), index.result(), x->elt_type(), false);
   26.98  
   26.99    if (GenerateRangeChecks && needs_range_check) {
  26.100 -    if (use_length) {
  26.101 +    if (StressLoopInvariantCodeMotion && range_check_info->deoptimize_on_exception()) {
  26.102 +      __ branch(lir_cond_always, T_ILLEGAL, new RangeCheckStub(range_check_info, index.result()));
  26.103 +    } else if (use_length) {
  26.104        // TODO: use a (modified) version of array_range_check that does not require a
  26.105        //       constant length to be loaded to a register
  26.106        __ cmp(lir_cond_belowEqual, length.result(), index.result());
  26.107 @@ -2634,7 +2656,7 @@
  26.108        LIR_Opr lock = new_register(T_INT);
  26.109        __ load_stack_address_monitor(0, lock);
  26.110  
  26.111 -      CodeEmitInfo* info = new CodeEmitInfo(scope()->start()->state()->copy(ValueStack::StateBefore, SynchronizationEntryBCI), NULL);
  26.112 +      CodeEmitInfo* info = new CodeEmitInfo(scope()->start()->state()->copy(ValueStack::StateBefore, SynchronizationEntryBCI), NULL, x->check_flag(Instruction::DeoptimizeOnException));
  26.113        CodeStub* slow_path = new MonitorEnterStub(obj, lock, info);
  26.114  
  26.115        // receiver is guaranteed non-NULL so don't need CodeEmitInfo
  26.116 @@ -2644,7 +2666,7 @@
  26.117  
  26.118    // increment invocation counters if needed
  26.119    if (!method()->is_accessor()) { // Accessors do not have MDOs, so no counting.
  26.120 -    CodeEmitInfo* info = new CodeEmitInfo(scope()->start()->state()->copy(ValueStack::StateBefore, SynchronizationEntryBCI), NULL);
  26.121 +    CodeEmitInfo* info = new CodeEmitInfo(scope()->start()->state()->copy(ValueStack::StateBefore, SynchronizationEntryBCI), NULL, false);
  26.122      increment_invocation_counter(info);
  26.123    }
  26.124  
  26.125 @@ -3102,6 +3124,95 @@
  26.126    }
  26.127  }
  26.128  
  26.129 +void LIRGenerator::do_Assert(Assert *x) {
  26.130 +#ifdef ASSERT
  26.131 +  ValueTag tag = x->x()->type()->tag();
  26.132 +  If::Condition cond = x->cond();
  26.133 +
  26.134 +  LIRItem xitem(x->x(), this);
  26.135 +  LIRItem yitem(x->y(), this);
  26.136 +  LIRItem* xin = &xitem;
  26.137 +  LIRItem* yin = &yitem;
  26.138 +
  26.139 +  assert(tag == intTag, "Only integer assertions are valid!");
  26.140 +
  26.141 +  xin->load_item();
  26.142 +  yin->dont_load_item();
  26.143 +
  26.144 +  set_no_result(x);
  26.145 +
  26.146 +  LIR_Opr left = xin->result();
  26.147 +  LIR_Opr right = yin->result();
  26.148 +
  26.149 +  __ lir_assert(lir_cond(x->cond()), left, right, x->message(), true);
  26.150 +#endif
  26.151 +}
  26.152 +
  26.153 +
  26.154 +void LIRGenerator::do_RangeCheckPredicate(RangeCheckPredicate *x) {
  26.155 +
  26.156 +
  26.157 +  Instruction *a = x->x();
  26.158 +  Instruction *b = x->y();
  26.159 +  if (!a || StressRangeCheckElimination) {
  26.160 +    assert(!b || StressRangeCheckElimination, "B must also be null");
  26.161 +
  26.162 +    CodeEmitInfo *info = state_for(x, x->state());
  26.163 +    CodeStub* stub = new PredicateFailedStub(info);
  26.164 +
  26.165 +    __ jump(stub);
  26.166 +  } else if (a->type()->as_IntConstant() && b->type()->as_IntConstant()) {
  26.167 +    int a_int = a->type()->as_IntConstant()->value();
  26.168 +    int b_int = b->type()->as_IntConstant()->value();
  26.169 +
  26.170 +    bool ok = false;
  26.171 +
  26.172 +    switch(x->cond()) {
  26.173 +      case Instruction::eql: ok = (a_int == b_int); break;
  26.174 +      case Instruction::neq: ok = (a_int != b_int); break;
  26.175 +      case Instruction::lss: ok = (a_int < b_int); break;
  26.176 +      case Instruction::leq: ok = (a_int <= b_int); break;
  26.177 +      case Instruction::gtr: ok = (a_int > b_int); break;
  26.178 +      case Instruction::geq: ok = (a_int >= b_int); break;
  26.179 +      case Instruction::aeq: ok = ((unsigned int)a_int >= (unsigned int)b_int); break;
  26.180 +      case Instruction::beq: ok = ((unsigned int)a_int <= (unsigned int)b_int); break;
  26.181 +      default: ShouldNotReachHere();
  26.182 +    }
  26.183 +
  26.184 +    if (ok) {
  26.185 +
  26.186 +      CodeEmitInfo *info = state_for(x, x->state());
  26.187 +      CodeStub* stub = new PredicateFailedStub(info);
  26.188 +
  26.189 +      __ jump(stub);
  26.190 +    }
  26.191 +  } else {
  26.192 +
  26.193 +    ValueTag tag = x->x()->type()->tag();
  26.194 +    If::Condition cond = x->cond();
  26.195 +    LIRItem xitem(x->x(), this);
  26.196 +    LIRItem yitem(x->y(), this);
  26.197 +    LIRItem* xin = &xitem;
  26.198 +    LIRItem* yin = &yitem;
  26.199 +
  26.200 +    assert(tag == intTag, "Only integer deoptimizations are valid!");
  26.201 +
  26.202 +    xin->load_item();
  26.203 +    yin->dont_load_item();
  26.204 +    set_no_result(x);
  26.205 +
  26.206 +    LIR_Opr left = xin->result();
  26.207 +    LIR_Opr right = yin->result();
  26.208 +
  26.209 +    CodeEmitInfo *info = state_for(x, x->state());
  26.210 +    CodeStub* stub = new PredicateFailedStub(info);
  26.211 +
  26.212 +    __ cmp(lir_cond(cond), left, right);
  26.213 +    __ branch(lir_cond(cond), right->type(), stub);
  26.214 +  }
  26.215 +}
  26.216 +
  26.217 +
  26.218  LIR_Opr LIRGenerator::call_runtime(Value arg1, address entry, ValueType* result_type, CodeEmitInfo* info) {
  26.219    LIRItemList args(1);
  26.220    LIRItem value(arg1, this);

    27.1 --- a/src/share/vm/c1/c1_LIRGenerator.hpp	Wed Mar 20 17:04:45 2013 -0700
    27.2 +++ b/src/share/vm/c1/c1_LIRGenerator.hpp	Thu Mar 21 09:27:54 2013 +0100
    27.3 @@ -412,6 +412,8 @@
    27.4      case If::leq: l = lir_cond_lessEqual;    break;
    27.5      case If::geq: l = lir_cond_greaterEqual; break;
    27.6      case If::gtr: l = lir_cond_greater;      break;
    27.7 +    case If::aeq: l = lir_cond_aboveEqual;   break;
    27.8 +    case If::beq: l = lir_cond_belowEqual;   break;
    27.9      };
   27.10      return l;
   27.11    }
   27.12 @@ -534,6 +536,8 @@
   27.13    virtual void do_ProfileInvoke  (ProfileInvoke*   x);
   27.14    virtual void do_RuntimeCall    (RuntimeCall*     x);
   27.15    virtual void do_MemBar         (MemBar*          x);
   27.16 +  virtual void do_RangeCheckPredicate(RangeCheckPredicate* x);
   27.17 +  virtual void do_Assert         (Assert*          x);
   27.18  };
   27.19  
   27.20  

    28.1 --- a/src/share/vm/c1/c1_LinearScan.cpp	Wed Mar 20 17:04:45 2013 -0700
    28.2 +++ b/src/share/vm/c1/c1_LinearScan.cpp	Thu Mar 21 09:27:54 2013 +0100
    28.3 @@ -6231,26 +6231,29 @@
    28.4              assert(prev_op->as_OpBranch() != NULL, "branch must be of type LIR_OpBranch");
    28.5              LIR_OpBranch* prev_branch = (LIR_OpBranch*)prev_op;
    28.6  
    28.7 -            LIR_Op2* prev_cmp = NULL;
    28.8 -
    28.9 -            for(int j = instructions->length() - 3; j >= 0 && prev_cmp == NULL; j--) {
   28.10 -              prev_op = instructions->at(j);
   28.11 -              if(prev_op->code() == lir_cmp) {
   28.12 -                assert(prev_op->as_Op2() != NULL, "branch must be of type LIR_Op2");
   28.13 -                prev_cmp = (LIR_Op2*)prev_op;
   28.14 -                assert(prev_branch->cond() == prev_cmp->condition(), "should be the same");
   28.15 +            if (prev_branch->stub() == NULL) {
   28.16 +
   28.17 +              LIR_Op2* prev_cmp = NULL;
   28.18 +
   28.19 +              for(int j = instructions->length() - 3; j >= 0 && prev_cmp == NULL; j--) {
   28.20 +                prev_op = instructions->at(j);
   28.21 +                if (prev_op->code() == lir_cmp) {
   28.22 +                  assert(prev_op->as_Op2() != NULL, "branch must be of type LIR_Op2");
   28.23 +                  prev_cmp = (LIR_Op2*)prev_op;
   28.24 +                  assert(prev_branch->cond() == prev_cmp->condition(), "should be the same");
   28.25 +                }
   28.26                }
   28.27 -            }
   28.28 -            assert(prev_cmp != NULL, "should have found comp instruction for branch");
   28.29 -            if (prev_branch->block() == code->at(i + 1) && prev_branch->info() == NULL) {
   28.30 -
   28.31 -              TRACE_LINEAR_SCAN(3, tty->print_cr("Negating conditional branch and deleting unconditional branch at end of block B%d", block->block_id()));
   28.32 -
   28.33 -              // eliminate a conditional branch to the immediate successor
   28.34 -              prev_branch->change_block(last_branch->block());
   28.35 -              prev_branch->negate_cond();
   28.36 -              prev_cmp->set_condition(prev_branch->cond());
   28.37 -              instructions->truncate(instructions->length() - 1);
   28.38 +              assert(prev_cmp != NULL, "should have found comp instruction for branch");
   28.39 +              if (prev_branch->block() == code->at(i + 1) && prev_branch->info() == NULL) {
   28.40 +
   28.41 +                TRACE_LINEAR_SCAN(3, tty->print_cr("Negating conditional branch and deleting unconditional branch at end of block B%d", block->block_id()));
   28.42 +
   28.43 +                // eliminate a conditional branch to the immediate successor
   28.44 +                prev_branch->change_block(last_branch->block());
   28.45 +                prev_branch->negate_cond();
   28.46 +                prev_cmp->set_condition(prev_branch->cond());
   28.47 +                instructions->truncate(instructions->length() - 1);
   28.48 +              }
   28.49              }
   28.50            }
   28.51          }

    29.1 --- a/src/share/vm/c1/c1_Optimizer.cpp	Wed Mar 20 17:04:45 2013 -0700
    29.2 +++ b/src/share/vm/c1/c1_Optimizer.cpp	Thu Mar 21 09:27:54 2013 +0100
    29.3 @@ -178,7 +178,7 @@
    29.4    // 2) substitute conditional expression
    29.5    //    with an IfOp followed by a Goto
    29.6    // cut if_ away and get node before
    29.7 -  Instruction* cur_end = if_->prev(block);
    29.8 +  Instruction* cur_end = if_->prev();
    29.9  
   29.10    // append constants of true- and false-block if necessary
   29.11    // clone constants because original block must not be destroyed
   29.12 @@ -202,7 +202,7 @@
   29.13    }
   29.14  
   29.15    // append Goto to successor
   29.16 -  ValueStack* state_before = if_->is_safepoint() ? if_->state_before() : NULL;
   29.17 +  ValueStack* state_before = if_->state_before();
   29.18    Goto* goto_ = new Goto(sux, state_before, if_->is_safepoint() || t_goto->is_safepoint() || f_goto->is_safepoint());
   29.19  
   29.20    // prepare state for Goto
   29.21 @@ -367,10 +367,11 @@
   29.22  #endif
   29.23  
   29.24          // find instruction before end & append first instruction of sux block
   29.25 -        Instruction* prev = end->prev(block);
   29.26 +        Instruction* prev = end->prev();
   29.27          Instruction* next = sux->next();
   29.28          assert(prev->as_BlockEnd() == NULL, "must not be a BlockEnd");
   29.29          prev->set_next(next);
   29.30 +        prev->fixup_block_pointers();
   29.31          sux->disconnect_from_graph();
   29.32          block->set_end(sux->end());
   29.33          // add exception handlers of deleted block, if any
   29.34 @@ -533,6 +534,8 @@
   29.35    void do_ProfileInvoke  (ProfileInvoke*   x);
   29.36    void do_RuntimeCall    (RuntimeCall*     x);
   29.37    void do_MemBar         (MemBar*          x);
   29.38 +  void do_RangeCheckPredicate(RangeCheckPredicate* x);
   29.39 +  void do_Assert         (Assert*          x);
   29.40  };
   29.41  
   29.42  
   29.43 @@ -714,6 +717,8 @@
   29.44  void NullCheckVisitor::do_ProfileInvoke  (ProfileInvoke*   x) {}
   29.45  void NullCheckVisitor::do_RuntimeCall    (RuntimeCall*     x) {}
   29.46  void NullCheckVisitor::do_MemBar         (MemBar*          x) {}
   29.47 +void NullCheckVisitor::do_RangeCheckPredicate(RangeCheckPredicate* x) {}
   29.48 +void NullCheckVisitor::do_Assert         (Assert*          x) {}
   29.49  
   29.50  
   29.51  void NullCheckEliminator::visit(Value* p) {

    30.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    30.2 +++ b/src/share/vm/c1/c1_RangeCheckElimination.cpp	Thu Mar 21 09:27:54 2013 +0100
    30.3 @@ -0,0 +1,1517 @@
    30.4 +/*
    30.5 + * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
    30.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
    30.7 + *
    30.8 + * This code is free software; you can redistribute it and/or modify it
    30.9 + * under the terms of the GNU General Public License version 2 only, as
   30.10 + * published by the Free Software Foundation.
   30.11 + *
   30.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
   30.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   30.14 + * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   30.15 + * version 2 for more details (a copy is included in the LICENSE file that
   30.16 + * accompanied this code).
   30.17 + *
   30.18 + * You should have received a copy of the GNU General Public License version
   30.19 + * 2 along with this work; if not, write to the Free Software Foundation,
   30.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   30.21 + *
   30.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   30.23 + * or visit www.oracle.com if you need additional information or have any
   30.24 + * questions.
   30.25 + *
   30.26 + */
   30.27 +
   30.28 +#include "precompiled.hpp"
   30.29 +#include "c1/c1_ValueStack.hpp"
   30.30 +#include "c1/c1_RangeCheckElimination.hpp"
   30.31 +#include "c1/c1_IR.hpp"
   30.32 +#include "c1/c1_Canonicalizer.hpp"
   30.33 +#include "c1/c1_ValueMap.hpp"
   30.34 +#include "ci/ciMethodData.hpp"
   30.35 +#include "runtime/deoptimization.hpp"
   30.36 +
   30.37 +// Macros for the Trace and the Assertion flag
   30.38 +#ifdef ASSERT
   30.39 +#define TRACE_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination) { code; }
   30.40 +#define ASSERT_RANGE_CHECK_ELIMINATION(code) if (AssertRangeCheckElimination) { code; }
   30.41 +#define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code) if (TraceRangeCheckElimination || AssertRangeCheckElimination) { code; }
   30.42 +#else
   30.43 +#define TRACE_RANGE_CHECK_ELIMINATION(code)
   30.44 +#define ASSERT_RANGE_CHECK_ELIMINATION(code)
   30.45 +#define TRACE_OR_ASSERT_RANGE_CHECK_ELIMINATION(code)
   30.46 +#endif
   30.47 +
   30.48 +// Entry point for the optimization
   30.49 +void RangeCheckElimination::eliminate(IR *ir) {
   30.50 +  bool do_elimination = ir->compilation()->has_access_indexed();
   30.51 +  ASSERT_RANGE_CHECK_ELIMINATION(do_elimination = true);
   30.52 +  if (do_elimination) {
   30.53 +    RangeCheckEliminator rce(ir);
   30.54 +  }
   30.55 +}
   30.56 +
   30.57 +// Constructor
   30.58 +RangeCheckEliminator::RangeCheckEliminator(IR *ir) :
   30.59 +  _bounds(Instruction::number_of_instructions(), NULL),
   30.60 +  _access_indexed_info(Instruction::number_of_instructions(), NULL)
   30.61 +{
   30.62 +  _visitor.set_range_check_eliminator(this);
   30.63 +  _ir = ir;
   30.64 +  _number_of_instructions = Instruction::number_of_instructions();
   30.65 +  _optimistic = ir->compilation()->is_optimistic();
   30.66 +
   30.67 +  TRACE_RANGE_CHECK_ELIMINATION(
   30.68 +    tty->print_cr("");
   30.69 +    tty->print_cr("Range check elimination");
   30.70 +    ir->method()->print_name(tty);
   30.71 +    tty->print_cr("");
   30.72 +  );
   30.73 +
   30.74 +  TRACE_RANGE_CHECK_ELIMINATION(
   30.75 +    tty->print_cr("optimistic=%d", (int)_optimistic);
   30.76 +  );
   30.77 +
   30.78 +#ifdef ASSERT
   30.79 +  // Verifies several conditions that must be true on the IR-input. Only used for debugging purposes.
   30.80 +  TRACE_RANGE_CHECK_ELIMINATION(
   30.81 +    tty->print_cr("Verification of IR . . .");
   30.82 +  );
   30.83 +  Verification verification(ir);
   30.84 +#endif
   30.85 +
   30.86 +  // Set process block flags
   30.87 +  // Optimization so a blocks is only processed if it contains an access indexed instruction or if
   30.88 +  // one of its children in the dominator tree contains an access indexed instruction.
   30.89 +  set_process_block_flags(ir->start());
   30.90 +
   30.91 +  // Pass over instructions in the dominator tree
   30.92 +  TRACE_RANGE_CHECK_ELIMINATION(
   30.93 +    tty->print_cr("Starting pass over dominator tree . . .")
   30.94 +  );
   30.95 +  calc_bounds(ir->start(), NULL);
   30.96 +
   30.97 +  TRACE_RANGE_CHECK_ELIMINATION(
   30.98 +    tty->print_cr("Finished!")
   30.99 +  );
  30.100 +}
  30.101 +
  30.102 +// Instruction specific work for some instructions
  30.103 +// Constant
  30.104 +void RangeCheckEliminator::Visitor::do_Constant(Constant *c) {
  30.105 +  IntConstant *ic = c->type()->as_IntConstant();
  30.106 +  if (ic != NULL) {
  30.107 +    int value = ic->value();
  30.108 +    _bound = new Bound(value, NULL, value, NULL);
  30.109 +  }
  30.110 +}
  30.111 +
  30.112 +// LogicOp
  30.113 +void RangeCheckEliminator::Visitor::do_LogicOp(LogicOp *lo) {
  30.114 +  if (lo->type()->as_IntType() && lo->op() == Bytecodes::_iand && (lo->x()->as_Constant() || lo->y()->as_Constant())) {
  30.115 +    int constant = 0;
  30.116 +    Constant *c = lo->x()->as_Constant();
  30.117 +    if (c != NULL) {
  30.118 +      constant = c->type()->as_IntConstant()->value();
  30.119 +    } else {
  30.120 +      constant = lo->y()->as_Constant()->type()->as_IntConstant()->value();
  30.121 +    }
  30.122 +    if (constant >= 0) {
  30.123 +      _bound = new Bound(0, NULL, constant, NULL);
  30.124 +    }
  30.125 +  }
  30.126 +}
  30.127 +
  30.128 +// Phi
  30.129 +void RangeCheckEliminator::Visitor::do_Phi(Phi *phi) {
  30.130 +  if (!phi->type()->as_IntType() && !phi->type()->as_ObjectType()) return;
  30.131 +
  30.132 +  BlockBegin *block = phi->block();
  30.133 +  int op_count = phi->operand_count();
  30.134 +  bool has_upper = true;
  30.135 +  bool has_lower = true;
  30.136 +  assert(phi, "Phi must not be null");
  30.137 +  Bound *bound = NULL;
  30.138 +
  30.139 +  // TODO: support more difficult phis
  30.140 +  for (int i=0; i<op_count; i++) {
  30.141 +    Value v = phi->operand_at(i);
  30.142 +
  30.143 +    if (v == phi) continue;
  30.144 +
  30.145 +    // Check if instruction is connected with phi itself
  30.146 +    Op2 *op2 = v->as_Op2();
  30.147 +    if (op2 != NULL) {
  30.148 +      Value x = op2->x();
  30.149 +      Value y = op2->y();
  30.150 +      if ((x == phi || y == phi)) {
  30.151 +        Value other = x;
  30.152 +        if (other == phi) {
  30.153 +          other = y;
  30.154 +        }
  30.155 +        ArithmeticOp *ao = v->as_ArithmeticOp();
  30.156 +        if (ao != NULL && ao->op() == Bytecodes::_iadd) {
  30.157 +          assert(ao->op() == Bytecodes::_iadd, "Has to be add!");
  30.158 +          if (ao->type()->as_IntType()) {
  30.159 +            Constant *c = other->as_Constant();
  30.160 +            if (c != NULL) {
  30.161 +              assert(c->type()->as_IntConstant(), "Constant has to be of type integer");
  30.162 +              int value = c->type()->as_IntConstant()->value();
  30.163 +              if (value == 1) {
  30.164 +                has_upper = false;
  30.165 +              } else if (value > 1) {
  30.166 +                // Overflow not guaranteed
  30.167 +                has_upper = false;
  30.168 +                has_lower = false;
  30.169 +              } else if (value < 0) {
  30.170 +                has_lower = false;
  30.171 +              }
  30.172 +              continue;
  30.173 +            }
  30.174 +          }
  30.175 +        }
  30.176 +      }
  30.177 +    }
  30.178 +
  30.179 +    // No connection -> new bound
  30.180 +    Bound *v_bound = _rce->get_bound(v);
  30.181 +    Bound *cur_bound;
  30.182 +    int cur_constant = 0;
  30.183 +    Value cur_value = v;
  30.184 +
  30.185 +    if (v->type()->as_IntConstant()) {
  30.186 +      cur_constant = v->type()->as_IntConstant()->value();
  30.187 +      cur_value = NULL;
  30.188 +    }
  30.189 +    if (!v_bound->has_upper() || !v_bound->has_lower()) {
  30.190 +      cur_bound = new Bound(cur_constant, cur_value, cur_constant, cur_value);
  30.191 +    } else {
  30.192 +      cur_bound = v_bound;
  30.193 +    }
  30.194 +    if (cur_bound) {
  30.195 +      if (!bound) {
  30.196 +        bound = cur_bound->copy();
  30.197 +      } else {
  30.198 +        bound->or_op(cur_bound);
  30.199 +      }
  30.200 +    } else {
  30.201 +      // No bound!
  30.202 +      bound = NULL;
  30.203 +      break;
  30.204 +    }
  30.205 +  }
  30.206 +
  30.207 +  if (bound) {
  30.208 +    if (!has_upper) {
  30.209 +      bound->remove_upper();
  30.210 +    }
  30.211 +    if (!has_lower) {
  30.212 +      bound->remove_lower();
  30.213 +    }
  30.214 +    _bound = bound;
  30.215 +  } else {
  30.216 +    _bound = new Bound();
  30.217 +  }
  30.218 +}
  30.219 +
  30.220 +
  30.221 +// ArithmeticOp
  30.222 +void RangeCheckEliminator::Visitor::do_ArithmeticOp(ArithmeticOp *ao) {
  30.223 +  Value x = ao->x();
  30.224 +  Value y = ao->y();
  30.225 +
  30.226 +  if (ao->op() == Bytecodes::_irem) {
  30.227 +    Bound* x_bound = _rce->get_bound(x);
  30.228 +    Bound* y_bound = _rce->get_bound(y);
  30.229 +    if (x_bound->lower() >= 0 && x_bound->lower_instr() == NULL && y->as_ArrayLength() != NULL) {
  30.230 +      _bound = new Bound(0, NULL, -1, y);
  30.231 +    } else {
  30.232 +      _bound = new Bound();
  30.233 +    }
  30.234 +  } else if (!x->as_Constant() || !y->as_Constant()) {
  30.235 +    assert(!x->as_Constant() || !y->as_Constant(), "One of the operands must be non-constant!");
  30.236 +    if (((x->as_Constant() || y->as_Constant()) && (ao->op() == Bytecodes::_iadd)) || (y->as_Constant() && ao->op() == Bytecodes::_isub)) {
  30.237 +      assert(ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub, "Operand must be iadd or isub");
  30.238 +
  30.239 +      if (y->as_Constant()) {
  30.240 +        Value tmp = x;
  30.241 +        x = y;
  30.242 +        y = tmp;
  30.243 +      }
  30.244 +      assert(x->as_Constant()->type()->as_IntConstant(), "Constant must be int constant!");
  30.245 +
  30.246 +      // Constant now in x
  30.247 +      int const_value = x->as_Constant()->type()->as_IntConstant()->value();
  30.248 +      if (ao->op() == Bytecodes::_iadd || const_value != min_jint) {
  30.249 +        if (ao->op() == Bytecodes::_isub) {
  30.250 +          const_value = -const_value;
  30.251 +        }
  30.252 +
  30.253 +        Bound * bound = _rce->get_bound(y);
  30.254 +        if (bound->has_upper() && bound->has_lower()) {
  30.255 +          int new_lower = bound->lower() + const_value;
  30.256 +          jlong new_lowerl = ((jlong)bound->lower()) + const_value;
  30.257 +          int new_upper = bound->upper() + const_value;
  30.258 +          jlong new_upperl = ((jlong)bound->upper()) + const_value;
  30.259 +
  30.260 +          if (((jlong)new_lower) == new_lowerl && ((jlong)new_upper == new_upperl)) {
  30.261 +            Bound *newBound = new Bound(new_lower, bound->lower_instr(), new_upper, bound->upper_instr());
  30.262 +            _bound = newBound;
  30.263 +          } else {
  30.264 +            // overflow
  30.265 +            _bound = new Bound();
  30.266 +          }
  30.267 +        } else {
  30.268 +          _bound = new Bound();
  30.269 +        }
  30.270 +      } else {
  30.271 +        _bound = new Bound();
  30.272 +      }
  30.273 +    } else {
  30.274 +      Bound *bound = _rce->get_bound(x);
  30.275 +      if (ao->op() == Bytecodes::_isub) {
  30.276 +        if (bound->lower_instr() == y) {
  30.277 +          _bound = new Bound(Instruction::geq, NULL, bound->lower());
  30.278 +        } else {
  30.279 +          _bound = new Bound();
  30.280 +        }
  30.281 +      } else {
  30.282 +        _bound = new Bound();
  30.283 +      }
  30.284 +    }
  30.285 +  }
  30.286 +}
  30.287 +
  30.288 +// IfOp
  30.289 +void RangeCheckEliminator::Visitor::do_IfOp(IfOp *ifOp)
  30.290 +{
  30.291 +  if (ifOp->tval()->type()->as_IntConstant() && ifOp->fval()->type()->as_IntConstant()) {
  30.292 +    int min = ifOp->tval()->type()->as_IntConstant()->value();
  30.293 +    int max = ifOp->fval()->type()->as_IntConstant()->value();
  30.294 +    if (min > max) {
  30.295 +      // min ^= max ^= min ^= max;
  30.296 +      int tmp = min;
  30.297 +      min = max;
  30.298 +      max = tmp;
  30.299 +    }
  30.300 +    _bound = new Bound(min, NULL, max, NULL);
  30.301 +  }
  30.302 +}
  30.303 +
  30.304 +// Get bound. Returns the current bound on Value v. Normally this is the topmost element on the bound stack.
  30.305 +RangeCheckEliminator::Bound *RangeCheckEliminator::get_bound(Value v) {
  30.306 +  // Wrong type or NULL -> No bound
  30.307 +  if (!v || (!v->type()->as_IntType() && !v->type()->as_ObjectType())) return NULL;
  30.308 +
  30.309 +  if (!_bounds[v->id()]) {
  30.310 +    // First (default) bound is calculated
  30.311 +    // Create BoundStack
  30.312 +    _bounds[v->id()] = new BoundStack();
  30.313 +    _visitor.clear_bound();
  30.314 +    Value visit_value = v;
  30.315 +    visit_value->visit(&_visitor);
  30.316 +    Bound *bound = _visitor.bound();
  30.317 +    if (bound) {
  30.318 +      _bounds[v->id()]->push(bound);
  30.319 +    }
  30.320 +    if (_bounds[v->id()]->length() == 0) {
  30.321 +      assert(!(v->as_Constant() && v->type()->as_IntConstant()), "constants not handled here");
  30.322 +      _bounds[v->id()]->push(new Bound());
  30.323 +    }
  30.324 +  } else if (_bounds[v->id()]->length() == 0) {
  30.325 +    // To avoid endless loops, bound is currently in calculation -> nothing known about it
  30.326 +    return new Bound();
  30.327 +  }
  30.328 +
  30.329 +  // Return bound
  30.330 +  return _bounds[v->id()]->top();
  30.331 +}
  30.332 +
  30.333 +// Update bound
  30.334 +void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Instruction::Condition cond, Value value, int constant) {
  30.335 +  if (cond == Instruction::gtr) {
  30.336 +    cond = Instruction::geq;
  30.337 +    constant++;
  30.338 +  } else if (cond == Instruction::lss) {
  30.339 +    cond = Instruction::leq;
  30.340 +    constant--;
  30.341 +  }
  30.342 +  Bound *bound = new Bound(cond, value, constant);
  30.343 +  update_bound(pushed, v, bound);
  30.344 +}
  30.345 +
  30.346 +// Checks for loop invariance. Returns true if the instruction is outside of the loop which is identified by loop_header.
  30.347 +bool RangeCheckEliminator::loop_invariant(BlockBegin *loop_header, Instruction *instruction) {
  30.348 +  assert(loop_header, "Loop header must not be null!");
  30.349 +  if (!instruction) return true;
  30.350 +  return instruction->dominator_depth() < loop_header->dominator_depth();
  30.351 +}
  30.352 +
  30.353 +// Update bound. Pushes a new bound onto the stack. Tries to do a conjunction with the current bound.
  30.354 +void RangeCheckEliminator::update_bound(IntegerStack &pushed, Value v, Bound *bound) {
  30.355 +  if (v->as_Constant()) {
  30.356 +    // No bound update for constants
  30.357 +    return;
  30.358 +  }
  30.359 +  if (!_bounds[v->id()]) {
  30.360 +    get_bound(v);
  30.361 +    assert(_bounds[v->id()], "Now Stack must exist");
  30.362 +  }
  30.363 +  Bound *top = NULL;
  30.364 +  if (_bounds[v->id()]->length() > 0) {
  30.365 +    top = _bounds[v->id()]->top();
  30.366 +  }
  30.367 +  if (top) {
  30.368 +    bound->and_op(top);
  30.369 +  }
  30.370 +  _bounds[v->id()]->push(bound);
  30.371 +  pushed.append(v->id());
  30.372 +}
  30.373 +
  30.374 +// Add instruction + idx for in block motion
  30.375 +void RangeCheckEliminator::add_access_indexed_info(InstructionList &indices, int idx, Value instruction, AccessIndexed *ai) {
  30.376 +  int id = instruction->id();
  30.377 +  AccessIndexedInfo *aii = _access_indexed_info[id];
  30.378 +  if (aii == NULL) {
  30.379 +    aii = new AccessIndexedInfo();
  30.380 +    _access_indexed_info[id] = aii;
  30.381 +    indices.append(instruction);
  30.382 +    aii->_min = idx;
  30.383 +    aii->_max = idx;
  30.384 +    aii->_list = new AccessIndexedList();
  30.385 +  } else if (idx >= aii->_min && idx <= aii->_max) {
  30.386 +    remove_range_check(ai);
  30.387 +    return;
  30.388 +  }
  30.389 +  aii->_min = MIN2(aii->_min, idx);
  30.390 +  aii->_max = MAX2(aii->_max, idx);
  30.391 +  aii->_list->append(ai);
  30.392 +}
  30.393 +
  30.394 +// In block motion. Tries to reorder checks in order to reduce some of them.
  30.395 +// Example:
  30.396 +// a[i] = 0;
  30.397 +// a[i+2] = 0;
  30.398 +// a[i+1] = 0;
  30.399 +// In this example the check for a[i+1] would be considered as unnecessary during the first iteration.
  30.400 +// After this i is only checked once for i >= 0 and i+2 < a.length before the first array access. If this
  30.401 +// check fails, deoptimization is called.
  30.402 +void RangeCheckEliminator::in_block_motion(BlockBegin *block, AccessIndexedList &accessIndexed, InstructionList &arrays) {
  30.403 +  InstructionList indices;
  30.404 +
  30.405 +  // Now iterate over all arrays
  30.406 +  for (int i=0; i<arrays.length(); i++) {
  30.407 +    int max_constant = -1;
  30.408 +    AccessIndexedList list_constant;
  30.409 +    Value array = arrays.at(i);
  30.410 +
  30.411 +    // For all AccessIndexed-instructions in this block concerning the current array.
  30.412 +    for(int j=0; j<accessIndexed.length(); j++) {
  30.413 +      AccessIndexed *ai = accessIndexed.at(j);
  30.414 +      if (ai->array() != array || !ai->check_flag(Instruction::NeedsRangeCheckFlag)) continue;
  30.415 +
  30.416 +      Value index = ai->index();
  30.417 +      Constant *c = index->as_Constant();
  30.418 +      if (c != NULL) {
  30.419 +        int constant_value = c->type()->as_IntConstant()->value();
  30.420 +        if (constant_value >= 0) {
  30.421 +          if (constant_value <= max_constant) {
  30.422 +            // No range check needed for this
  30.423 +            remove_range_check(ai);
  30.424 +          } else {
  30.425 +            max_constant = constant_value;
  30.426 +            list_constant.append(ai);
  30.427 +          }
  30.428 +        }
  30.429 +      } else {
  30.430 +        int last_integer = 0;
  30.431 +        Instruction *last_instruction = index;
  30.432 +        int base = 0;
  30.433 +        ArithmeticOp *ao = index->as_ArithmeticOp();
  30.434 +
  30.435 +        while (ao != NULL && (ao->x()->as_Constant() || ao->y()->as_Constant()) && (ao->op() == Bytecodes::_iadd || ao->op() == Bytecodes::_isub)) {
  30.436 +          c = ao->y()->as_Constant();
  30.437 +          Instruction *other = ao->x();
  30.438 +          if (!c && ao->op() == Bytecodes::_iadd) {
  30.439 +            c = ao->x()->as_Constant();
  30.440 +            other = ao->y();
  30.441 +          }
  30.442 +
  30.443 +          if (c) {
  30.444 +            int value = c->type()->as_IntConstant()->value();
  30.445 +            if (value != min_jint) {
  30.446 +              if (ao->op() == Bytecodes::_isub) {
  30.447 +                value = -value;
  30.448 +              }
  30.449 +              base += value;
  30.450 +              last_integer = base;
  30.451 +              last_instruction = other;
  30.452 +            }
  30.453 +            index = other;
  30.454 +          } else {
  30.455 +            break;
  30.456 +          }
  30.457 +          ao = index->as_ArithmeticOp();
  30.458 +        }
  30.459 +        add_access_indexed_info(indices, last_integer, last_instruction, ai);
  30.460 +      }
  30.461 +    }
  30.462 +
  30.463 +    // Iterate over all different indices
  30.464 +    if (_optimistic) {
  30.465 +      for (int i=0; i<indices.length(); i++) {
  30.466 +        Instruction *index_instruction = indices.at(i);
  30.467 +        AccessIndexedInfo *info = _access_indexed_info[index_instruction->id()];
  30.468 +        assert(info != NULL, "Info must not be null");
  30.469 +
  30.470 +        // if idx < 0, max > 0, max + idx may fall between 0 and
  30.471 +        // length-1 and if min < 0, min + idx may overflow and be >=
  30.472 +        // 0. The predicate wouldn't trigger but some accesses could
  30.473 +        // be with a negative index. This test guarantees that for the
  30.474 +        // min and max value that are kept the predicate can't let
  30.475 +        // some incorrect accesses happen.
  30.476 +        bool range_cond = (info->_max < 0 || info->_max + min_jint <= info->_min);
  30.477 +
  30.478 +        // Generate code only if more than 2 range checks can be eliminated because of that.
  30.479 +        // 2 because at least 2 comparisons are done
  30.480 +        if (info->_list->length() > 2 && range_cond) {
  30.481 +          AccessIndexed *first = info->_list->at(0);
  30.482 +          Instruction *insert_position = first->prev();
  30.483 +          assert(insert_position->next() == first, "prev was calculated");
  30.484 +          ValueStack *state = first->state_before();
  30.485 +
  30.486 +          // Load min Constant
  30.487 +          Constant *min_constant = NULL;
  30.488 +          if (info->_min != 0) {
  30.489 +            min_constant = new Constant(new IntConstant(info->_min));
  30.490 +            NOT_PRODUCT(min_constant->set_printable_bci(first->printable_bci()));
  30.491 +            insert_position = insert_position->insert_after(min_constant);
  30.492 +          }
  30.493 +
  30.494 +          // Load max Constant
  30.495 +          Constant *max_constant = NULL;
  30.496 +          if (info->_max != 0) {
  30.497 +            max_constant = new Constant(new IntConstant(info->_max));
  30.498 +            NOT_PRODUCT(max_constant->set_printable_bci(first->printable_bci()));
  30.499 +            insert_position = insert_position->insert_after(max_constant);
  30.500 +          }
  30.501 +
  30.502 +          // Load array length
  30.503 +          Value length_instr = first->length();
  30.504 +          if (!length_instr) {
  30.505 +            ArrayLength *length = new ArrayLength(array, first->state_before()->copy());
  30.506 +            length->set_exception_state(length->state_before());
  30.507 +            length->set_flag(Instruction::DeoptimizeOnException, true);
  30.508 +            insert_position = insert_position->insert_after_same_bci(length);
  30.509 +            length_instr = length;
  30.510 +          }
  30.511 +
  30.512 +          // Calculate lower bound
  30.513 +          Instruction *lower_compare = index_instruction;
  30.514 +          if (min_constant) {
  30.515 +            ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, min_constant, lower_compare, false, NULL);
  30.516 +            insert_position = insert_position->insert_after_same_bci(ao);
  30.517 +            lower_compare = ao;
  30.518 +          }
  30.519 +
  30.520 +          // Calculate upper bound
  30.521 +          Instruction *upper_compare = index_instruction;
  30.522 +          if (max_constant) {
  30.523 +            ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, max_constant, upper_compare, false, NULL);
  30.524 +            insert_position = insert_position->insert_after_same_bci(ao);
  30.525 +            upper_compare = ao;
  30.526 +          }
  30.527 +
  30.528 +          // Trick with unsigned compare is done
  30.529 +          int bci = NOT_PRODUCT(first->printable_bci()) PRODUCT_ONLY(-1);
  30.530 +          insert_position = predicate(upper_compare, Instruction::aeq, length_instr, state, insert_position, bci);
  30.531 +          insert_position = predicate_cmp_with_const(lower_compare, Instruction::leq, -1, state, insert_position);
  30.532 +          for (int j = 0; j<info->_list->length(); j++) {
  30.533 +            AccessIndexed *ai = info->_list->at(j);
  30.534 +            remove_range_check(ai);
  30.535 +          }
  30.536 +        }
  30.537 +        _access_indexed_info[index_instruction->id()] = NULL;
  30.538 +      }
  30.539 +      indices.clear();
  30.540 +
  30.541 +      if (list_constant.length() > 1) {
  30.542 +        AccessIndexed *first = list_constant.at(0);
  30.543 +        Instruction *insert_position = first->prev();
  30.544 +        ValueStack *state = first->state_before();
  30.545 +        // Load max Constant
  30.546 +        Constant *constant = new Constant(new IntConstant(max_constant));
  30.547 +        NOT_PRODUCT(constant->set_printable_bci(first->printable_bci()));
  30.548 +        insert_position = insert_position->insert_after(constant);
  30.549 +        Instruction *compare_instr = constant;
  30.550 +        Value length_instr = first->length();
  30.551 +        if (!length_instr) {
  30.552 +          ArrayLength *length = new ArrayLength(array, state->copy());
  30.553 +          length->set_exception_state(length->state_before());
  30.554 +          length->set_flag(Instruction::DeoptimizeOnException, true);
  30.555 +          insert_position = insert_position->insert_after_same_bci(length);
  30.556 +          length_instr = length;
  30.557 +        }
  30.558 +        // Compare for greater or equal to array length
  30.559 +        insert_position = predicate(compare_instr, Instruction::geq, length_instr, state, insert_position);
  30.560 +        for (int j = 0; j<list_constant.length(); j++) {
  30.561 +          AccessIndexed *ai = list_constant.at(j);
  30.562 +          remove_range_check(ai);
  30.563 +        }
  30.564 +      }
  30.565 +    }
  30.566 +  }
  30.567 +}
  30.568 +
  30.569 +bool RangeCheckEliminator::set_process_block_flags(BlockBegin *block) {
  30.570 +  Instruction *cur = block;
  30.571 +  bool process = false;
  30.572 +
  30.573 +  while (cur) {
  30.574 +    process |= (cur->as_AccessIndexed() != NULL);
  30.575 +    cur = cur->next();
  30.576 +  }
  30.577 +
  30.578 +  BlockList *dominates = block->dominates();
  30.579 +  for (int i=0; i<dominates->length(); i++) {
  30.580 +    BlockBegin *next = dominates->at(i);
  30.581 +    process |= set_process_block_flags(next);
  30.582 +  }
  30.583 +
  30.584 +  if (!process) {
  30.585 +    block->set(BlockBegin::donot_eliminate_range_checks);
  30.586 +  }
  30.587 +  return process;
  30.588 +}
  30.589 +
  30.590 +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) {
  30.591 +  bool upper_check = true;
  30.592 +  assert(lower_instr || lower >= 0, "If no lower_instr present, lower must be greater 0");
  30.593 +  assert(!lower_instr || lower_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
  30.594 +  assert(!upper_instr || upper_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
  30.595 +  assert(array_instr, "Array instruction must exist");
  30.596 +  assert(array_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
  30.597 +  assert(!length_instr || length_instr->dominator_depth() <= insert_position->dominator_depth(), "Dominator depth must be smaller");
  30.598 +
  30.599 +  if (upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr) {
  30.600 +    // static check
  30.601 +    if (upper >= 0) return false; // would always trigger a deopt:
  30.602 +                                  // array_length + x >= array_length, x >= 0 is always true
  30.603 +    upper_check = false;
  30.604 +  }
  30.605 +  if (lower_instr && lower_instr->as_ArrayLength() && lower_instr->as_ArrayLength()->array() == array_instr) {
  30.606 +    if (lower > 0) return false;
  30.607 +  }
  30.608 +  // No upper check required -> skip
  30.609 +  if (upper_check && upper_instr && upper_instr->type()->as_ObjectType() && upper_instr == array_instr) {
  30.610 +    // upper_instr is object means that the upper bound is the length
  30.611 +    // of the upper_instr.
  30.612 +    return false;
  30.613 +  }
  30.614 +  return true;
  30.615 +}
  30.616 +
  30.617 +Instruction* RangeCheckEliminator::insert_after(Instruction* insert_position, Instruction* instr, int bci) {
  30.618 +  if (bci != -1) {
  30.619 +    NOT_PRODUCT(instr->set_printable_bci(bci));
  30.620 +    return insert_position->insert_after(instr);
  30.621 +  } else {
  30.622 +    return insert_position->insert_after_same_bci(instr);
  30.623 +  }
  30.624 +}
  30.625 +
  30.626 +Instruction* RangeCheckEliminator::predicate(Instruction* left, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) {
  30.627 +  RangeCheckPredicate *deoptimize = new RangeCheckPredicate(left, cond, true, right, state->copy());
  30.628 +  return insert_after(insert_position, deoptimize, bci);
  30.629 +}
  30.630 +
  30.631 +Instruction* RangeCheckEliminator::predicate_cmp_with_const(Instruction* instr, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) {
  30.632 +  Constant *const_instr = new Constant(new IntConstant(constant));
  30.633 +  insert_position = insert_after(insert_position, const_instr, bci);
  30.634 +  return predicate(instr, cond, const_instr, state, insert_position);
  30.635 +}
  30.636 +
  30.637 +Instruction* RangeCheckEliminator::predicate_add(Instruction* left, int left_const, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci) {
  30.638 +  Constant *constant = new Constant(new IntConstant(left_const));
  30.639 +  insert_position = insert_after(insert_position, constant, bci);
  30.640 +  ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, left, false, NULL);
  30.641 +  insert_position = insert_position->insert_after_same_bci(ao);
  30.642 +  return predicate(ao, cond, right, state, insert_position);
  30.643 +}
  30.644 +
  30.645 +Instruction* RangeCheckEliminator::predicate_add_cmp_with_const(Instruction* left, int left_const, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci) {
  30.646 +  Constant *const_instr = new Constant(new IntConstant(constant));
  30.647 +  insert_position = insert_after(insert_position, const_instr, bci);
  30.648 +  return predicate_add(left, left_const, cond, const_instr, state, insert_position);
  30.649 +}
  30.650 +
  30.651 +// Insert deoptimization, returns true if sucessful or false if range check should not be removed
  30.652 +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) {
  30.653 +  assert(is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, lower, upper_instr, upper), "should have been tested before");
  30.654 +  bool upper_check = !(upper_instr && upper_instr->as_ArrayLength() && upper_instr->as_ArrayLength()->array() == array_instr);
  30.655 +
  30.656 +  int bci = NOT_PRODUCT(ai->printable_bci()) PRODUCT_ONLY(-1);
  30.657 +  if (lower_instr) {
  30.658 +    assert(!lower_instr->type()->as_ObjectType(), "Must not be object type");
  30.659 +    if (lower == 0) {
  30.660 +      // Compare for less than 0
  30.661 +      insert_position = predicate_cmp_with_const(lower_instr, Instruction::lss, 0, state, insert_position, bci);
  30.662 +    } else if (lower > 0) {
  30.663 +      // Compare for smaller 0
  30.664 +      insert_position = predicate_add_cmp_with_const(lower_instr, lower, Instruction::lss, 0, state, insert_position, bci);
  30.665 +    } else {
  30.666 +      assert(lower < 0, "");
  30.667 +      // Add 1
  30.668 +      lower++;
  30.669 +      lower = -lower;
  30.670 +      // Compare for smaller or equal 0
  30.671 +      insert_position = predicate_cmp_with_const(lower_instr, Instruction::leq, lower, state, insert_position, bci);
  30.672 +    }
  30.673 +  }
  30.674 +
  30.675 +  // We need to know length of array
  30.676 +  if (!length_instr) {
  30.677 +    // Load length if necessary
  30.678 +    ArrayLength *length = new ArrayLength(array_instr, state->copy());
  30.679 +    NOT_PRODUCT(length->set_printable_bci(ai->printable_bci()));
  30.680 +    length->set_exception_state(length->state_before());
  30.681 +    length->set_flag(Instruction::DeoptimizeOnException, true);
  30.682 +    insert_position = insert_position->insert_after(length);
  30.683 +    length_instr = length;
  30.684 +  }
  30.685 +
  30.686 +  // No upper check required -> skip
  30.687 +  if (!upper_check) return;
  30.688 +
  30.689 +  if (!upper_instr) {
  30.690 +    // Compare for geq array.length
  30.691 +    insert_position = predicate_cmp_with_const(length_instr, Instruction::leq, upper, state, insert_position, bci);
  30.692 +  } else {
  30.693 +    if (upper_instr->type()->as_ObjectType()) {
  30.694 +      assert(state, "must not be null");
  30.695 +      assert(upper_instr != array_instr, "should be");
  30.696 +      ArrayLength *length = new ArrayLength(upper_instr, state->copy());
  30.697 +      NOT_PRODUCT(length->set_printable_bci(ai->printable_bci()));
  30.698 +      length->set_flag(Instruction::DeoptimizeOnException, true);
  30.699 +      length->set_exception_state(length->state_before());
  30.700 +      insert_position = insert_position->insert_after(length);
  30.701 +      upper_instr = length;
  30.702 +    }
  30.703 +    assert(upper_instr->type()->as_IntType(), "Must not be object type!");
  30.704 +
  30.705 +    if (upper == 0) {
  30.706 +      // Compare for geq array.length
  30.707 +      insert_position = predicate(upper_instr, Instruction::geq, length_instr, state, insert_position, bci);
  30.708 +    } else if (upper < 0) {
  30.709 +      // Compare for geq array.length
  30.710 +      insert_position = predicate_add(upper_instr, upper, Instruction::geq, length_instr, state, insert_position, bci);
  30.711 +    } else {
  30.712 +      assert(upper > 0, "");
  30.713 +      upper = -upper;
  30.714 +      // Compare for geq array.length
  30.715 +      insert_position = predicate_add(length_instr, upper, Instruction::leq, upper_instr, state, insert_position, bci);
  30.716 +    }
  30.717 +  }
  30.718 +}
  30.719 +
  30.720 +// Add if condition
  30.721 +void RangeCheckEliminator::add_if_condition(IntegerStack &pushed, Value x, Value y, Instruction::Condition condition) {
  30.722 +  if (y->as_Constant()) return;
  30.723 +
  30.724 +  int const_value = 0;
  30.725 +  Value instr_value = x;
  30.726 +  Constant *c = x->as_Constant();
  30.727 +  ArithmeticOp *ao = x->as_ArithmeticOp();
  30.728 +
  30.729 +  if (c != NULL) {
  30.730 +    const_value = c->type()->as_IntConstant()->value();
  30.731 +    instr_value = NULL;
  30.732 +  } else if (ao != NULL &&  (!ao->x()->as_Constant() || !ao->y()->as_Constant()) && ((ao->op() == Bytecodes::_isub && ao->y()->as_Constant()) || ao->op() == Bytecodes::_iadd)) {
  30.733 +    assert(!ao->x()->as_Constant() || !ao->y()->as_Constant(), "At least one operator must be non-constant!");
  30.734 +    assert(ao->op() == Bytecodes::_isub || ao->op() == Bytecodes::_iadd, "Operation has to be add or sub!");
  30.735 +    c = ao->x()->as_Constant();
  30.736 +    if (c != NULL) {
  30.737 +      const_value = c->type()->as_IntConstant()->value();
  30.738 +      instr_value = ao->y();
  30.739 +    } else {
  30.740 +      c = ao->y()->as_Constant();
  30.741 +      if (c != NULL) {
  30.742 +        const_value = c->type()->as_IntConstant()->value();
  30.743 +        instr_value = ao->x();
  30.744 +      }
  30.745 +    }
  30.746 +    if (ao->op() == Bytecodes::_isub) {
  30.747 +      assert(ao->y()->as_Constant(), "1 - x not supported, only x - 1 is valid!");
  30.748 +      if (const_value > min_jint) {
  30.749 +        const_value = -const_value;
  30.750 +      } else {
  30.751 +        const_value = 0;
  30.752 +        instr_value = x;
  30.753 +      }
  30.754 +    }
  30.755 +  }
  30.756 +
  30.757 +  update_bound(pushed, y, condition, instr_value, const_value);
  30.758 +}
  30.759 +
  30.760 +// Process If
  30.761 +void RangeCheckEliminator::process_if(IntegerStack &pushed, BlockBegin *block, If *cond) {
  30.762 +  // Only if we are direct true / false successor and NOT both ! (even this may occur)
  30.763 +  if ((cond->tsux() == block || cond->fsux() == block) && cond->tsux() != cond->fsux()) {
  30.764 +    Instruction::Condition condition = cond->cond();
  30.765 +    if (cond->fsux() == block) {
  30.766 +      condition = Instruction::negate(condition);
  30.767 +    }
  30.768 +    Value x = cond->x();
  30.769 +    Value y = cond->y();
  30.770 +    if (x->type()->as_IntType() && y->type()->as_IntType()) {
  30.771 +      add_if_condition(pushed, y, x, condition);
  30.772 +      add_if_condition(pushed, x, y, Instruction::mirror(condition));
  30.773 +    }
  30.774 +  }
  30.775 +}
  30.776 +
  30.777 +// Process access indexed
  30.778 +void RangeCheckEliminator::process_access_indexed(BlockBegin *loop_header, BlockBegin *block, AccessIndexed *ai) {
  30.779 +  TRACE_RANGE_CHECK_ELIMINATION(
  30.780 +    tty->fill_to(block->dominator_depth()*2)
  30.781 +  );
  30.782 +  TRACE_RANGE_CHECK_ELIMINATION(
  30.783 +    tty->print_cr("Access indexed: index=%d length=%d", ai->index()->id(), ai->length()->id())
  30.784 +  );
  30.785 +
  30.786 +  if (ai->check_flag(Instruction::NeedsRangeCheckFlag)) {
  30.787 +    Bound *index_bound = get_bound(ai->index());
  30.788 +    if (!index_bound->has_lower() || !index_bound->has_upper()) {
  30.789 +      TRACE_RANGE_CHECK_ELIMINATION(
  30.790 +        tty->fill_to(block->dominator_depth()*2);
  30.791 +        tty->print_cr("Index instruction %d has no lower and/or no upper bound!", ai->index()->id())
  30.792 +      );
  30.793 +      return;
  30.794 +    }
  30.795 +
  30.796 +    Bound *array_bound;
  30.797 +    if (ai->length()) {
  30.798 +      array_bound = get_bound(ai->length());
  30.799 +    } else {
  30.800 +      array_bound = get_bound(ai->array());
  30.801 +    }
  30.802 +
  30.803 +    if (in_array_bound(index_bound, ai->array()) ||
  30.804 +      (index_bound && array_bound && index_bound->is_smaller(array_bound) && !index_bound->lower_instr() && index_bound->lower() >= 0)) {
  30.805 +        TRACE_RANGE_CHECK_ELIMINATION(
  30.806 +          tty->fill_to(block->dominator_depth()*2);
  30.807 +          tty->print_cr("Bounds check for instruction %d in block B%d can be fully eliminated!", ai->id(), ai->block()->block_id())
  30.808 +        );
  30.809 +
  30.810 +        remove_range_check(ai);
  30.811 +    } else if (_optimistic && loop_header) {
  30.812 +      assert(ai->array(), "Array must not be null!");
  30.813 +      assert(ai->index(), "Index must not be null!");
  30.814 +
  30.815 +      // Array instruction
  30.816 +      Instruction *array_instr = ai->array();
  30.817 +      if (!loop_invariant(loop_header, array_instr)) {
  30.818 +        TRACE_RANGE_CHECK_ELIMINATION(
  30.819 +          tty->fill_to(block->dominator_depth()*2);
  30.820 +          tty->print_cr("Array %d is not loop invariant to header B%d", ai->array()->id(), loop_header->block_id())
  30.821 +        );
  30.822 +        return;
  30.823 +      }
  30.824 +
  30.825 +      // Lower instruction
  30.826 +      Value index_instr = ai->index();
  30.827 +      Value lower_instr = index_bound->lower_instr();
  30.828 +      if (!loop_invariant(loop_header, lower_instr)) {
  30.829 +        TRACE_RANGE_CHECK_ELIMINATION(
  30.830 +          tty->fill_to(block->dominator_depth()*2);
  30.831 +          tty->print_cr("Lower instruction %d not loop invariant!", lower_instr->id())
  30.832 +        );
  30.833 +        return;
  30.834 +      }
  30.835 +      if (!lower_instr && index_bound->lower() < 0) {
  30.836 +        TRACE_RANGE_CHECK_ELIMINATION(
  30.837 +          tty->fill_to(block->dominator_depth()*2);
  30.838 +          tty->print_cr("Lower bound smaller than 0 (%d)!", index_bound->lower())
  30.839 +        );
  30.840 +        return;
  30.841 +      }
  30.842 +
  30.843 +      // Upper instruction
  30.844 +      Value upper_instr = index_bound->upper_instr();
  30.845 +      if (!loop_invariant(loop_header, upper_instr)) {
  30.846 +        TRACE_RANGE_CHECK_ELIMINATION(
  30.847 +          tty->fill_to(block->dominator_depth()*2);
  30.848 +          tty->print_cr("Upper instruction %d not loop invariant!", upper_instr->id())
  30.849 +        );
  30.850 +        return;
  30.851 +      }
  30.852 +
  30.853 +      // Length instruction
  30.854 +      Value length_instr = ai->length();
  30.855 +      if (!loop_invariant(loop_header, length_instr)) {
  30.856 +        // Generate length instruction yourself!
  30.857 +        length_instr = NULL;
  30.858 +      }
  30.859 +
  30.860 +      TRACE_RANGE_CHECK_ELIMINATION(
  30.861 +        tty->fill_to(block->dominator_depth()*2);
  30.862 +        tty->print_cr("LOOP INVARIANT access indexed %d found in block B%d!", ai->id(), ai->block()->block_id())
  30.863 +      );
  30.864 +
  30.865 +      BlockBegin *pred_block = loop_header->dominator();
  30.866 +      assert(pred_block != NULL, "Every loop header has a dominator!");
  30.867 +      BlockEnd *pred_block_end = pred_block->end();
  30.868 +      Instruction *insert_position = pred_block_end->prev();
  30.869 +      ValueStack *state = pred_block_end->state_before();
  30.870 +      if (pred_block_end->as_Goto() && state == NULL) state = pred_block_end->state();
  30.871 +      assert(state, "State must not be null");
  30.872 +
  30.873 +      // Add deoptimization to dominator of loop header
  30.874 +      TRACE_RANGE_CHECK_ELIMINATION(
  30.875 +        tty->fill_to(block->dominator_depth()*2);
  30.876 +        tty->print_cr("Inserting deopt at bci %d in block B%d!", state->bci(), insert_position->block()->block_id())
  30.877 +      );
  30.878 +
  30.879 +      if (!is_ok_for_deoptimization(insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper())) {
  30.880 +        TRACE_RANGE_CHECK_ELIMINATION(
  30.881 +          tty->fill_to(block->dominator_depth()*2);
  30.882 +          tty->print_cr("Could not eliminate because of static analysis!")
  30.883 +        );
  30.884 +        return;
  30.885 +      }
  30.886 +
  30.887 +      insert_deoptimization(state, insert_position, array_instr, length_instr, lower_instr, index_bound->lower(), upper_instr, index_bound->upper(), ai);
  30.888 +
  30.889 +      // Finally remove the range check!
  30.890 +      remove_range_check(ai);
  30.891 +    }
  30.892 +  }
  30.893 +}
  30.894 +
  30.895 +void RangeCheckEliminator::remove_range_check(AccessIndexed *ai) {
  30.896 +  ai->set_flag(Instruction::NeedsRangeCheckFlag, false);
  30.897 +  // no range check, no need for the length instruction anymore
  30.898 +  ai->clear_length();
  30.899 +
  30.900 +  TRACE_RANGE_CHECK_ELIMINATION(
  30.901 +    tty->fill_to(ai->dominator_depth()*2);
  30.902 +    tty->print_cr("Range check for instruction %d eliminated!", ai->id());
  30.903 +  );
  30.904 +
  30.905 +  ASSERT_RANGE_CHECK_ELIMINATION(
  30.906 +    Value array_length = ai->length();
  30.907 +    if (!array_length) {
  30.908 +      array_length = ai->array();
  30.909 +      assert(array_length->type()->as_ObjectType(), "Has to be object type!");
  30.910 +    }
  30.911 +    int cur_constant = -1;
  30.912 +    Value cur_value = array_length;
  30.913 +    if (cur_value->type()->as_IntConstant()) {
  30.914 +      cur_constant += cur_value->type()->as_IntConstant()->value();
  30.915 +      cur_value = NULL;
  30.916 +    }
  30.917 +    Bound *new_index_bound = new Bound(0, NULL, cur_constant, cur_value);
  30.918 +    add_assertions(new_index_bound, ai->index(), ai);
  30.919 +  );
  30.920 +}
  30.921 +
  30.922 +// Calculate bounds for instruction in this block and children blocks in the dominator tree
  30.923 +void RangeCheckEliminator::calc_bounds(BlockBegin *block, BlockBegin *loop_header) {
  30.924 +  // Ensures a valid loop_header
  30.925 +  assert(!loop_header || loop_header->is_set(BlockBegin::linear_scan_loop_header_flag), "Loop header has to be real !");
  30.926 +
  30.927 +  // Tracing output
  30.928 +  TRACE_RANGE_CHECK_ELIMINATION(
  30.929 +    tty->fill_to(block->dominator_depth()*2);
  30.930 +    tty->print_cr("Block B%d", block->block_id());
  30.931 +  );
  30.932 +
  30.933 +  // Pushed stack for conditions
  30.934 +  IntegerStack pushed;
  30.935 +  // Process If
  30.936 +  BlockBegin *parent = block->dominator();
  30.937 +  if (parent != NULL) {
  30.938 +    If *cond = parent->end()->as_If();
  30.939 +    if (cond != NULL) {
  30.940 +      process_if(pushed, block, cond);
  30.941 +    }
  30.942 +  }
  30.943 +
  30.944 +  // Interate over current block
  30.945 +  InstructionList arrays;
  30.946 +  AccessIndexedList accessIndexed;
  30.947 +  Instruction *cur = block;
  30.948 +
  30.949 +  while (cur) {
  30.950 +    // Ensure cur wasn't inserted during the elimination
  30.951 +    if (cur->id() < this->_bounds.length()) {
  30.952 +      // Process only if it is an access indexed instruction
  30.953 +      AccessIndexed *ai = cur->as_AccessIndexed();
  30.954 +      if (ai != NULL) {
  30.955 +        process_access_indexed(loop_header, block, ai);
  30.956 +        accessIndexed.append(ai);
  30.957 +        if (!arrays.contains(ai->array())) {
  30.958 +          arrays.append(ai->array());
  30.959 +        }
  30.960 +        Bound *b = get_bound(ai->index());
  30.961 +        if (!b->lower_instr()) {
  30.962 +          // Lower bound is constant
  30.963 +          update_bound(pushed, ai->index(), Instruction::geq, NULL, 0);
  30.964 +        }
  30.965 +        if (!b->has_upper()) {
  30.966 +          if (ai->length() && ai->length()->type()->as_IntConstant()) {
  30.967 +            int value = ai->length()->type()->as_IntConstant()->value();
  30.968 +            update_bound(pushed, ai->index(), Instruction::lss, NULL, value);
  30.969 +          } else {
  30.970 +            // Has no upper bound
  30.971 +            Instruction *instr = ai->length();
  30.972 +            if (instr != NULL) instr = ai->array();
  30.973 +            update_bound(pushed, ai->index(), Instruction::lss, instr, 0);
  30.974 +          }
  30.975 +        }
  30.976 +      }
  30.977 +    }
  30.978 +    cur = cur->next();
  30.979 +  }
  30.980 +
  30.981 +  // Output current condition stack
  30.982 +  TRACE_RANGE_CHECK_ELIMINATION(dump_condition_stack(block));
  30.983 +
  30.984 +  // Do in block motion of range checks
  30.985 +  in_block_motion(block, accessIndexed, arrays);
  30.986 +
  30.987 +  // Call all dominated blocks
  30.988 +  for (int i=0; i<block->dominates()->length(); i++) {
  30.989 +    BlockBegin *next = block->dominates()->at(i);
  30.990 +    if (!next->is_set(BlockBegin::donot_eliminate_range_checks)) {
  30.991 +      // if current block is a loop header and:
  30.992 +      // - next block belongs to the same loop
  30.993 +      // or
  30.994 +      // - next block belongs to an inner loop
  30.995 +      // then current block is the loop header for next block
  30.996 +      if (block->is_set(BlockBegin::linear_scan_loop_header_flag) && (block->loop_index() == next->loop_index() || next->loop_depth() > block->loop_depth())) {
  30.997 +        calc_bounds(next, block);
  30.998 +      } else {
  30.999 +        calc_bounds(next, loop_header);
 30.1000 +      }
 30.1001 +    }
 30.1002 +  }
 30.1003 +
 30.1004 +  // Reset stack
 30.1005 +  for (int i=0; i<pushed.length(); i++) {
 30.1006 +    _bounds[pushed[i]]->pop();
 30.1007 +  }
 30.1008 +}
 30.1009 +
 30.1010 +#ifndef PRODUCT
 30.1011 +// Dump condition stack
 30.1012 +void RangeCheckEliminator::dump_condition_stack(BlockBegin *block) {
 30.1013 +  for (int i=0; i<_ir->linear_scan_order()->length(); i++) {
 30.1014 +    BlockBegin *cur_block = _ir->linear_scan_order()->at(i);
 30.1015 +    Instruction *instr = cur_block;
 30.1016 +    for_each_phi_fun(cur_block, phi,
 30.1017 +                     BoundStack *bound_stack = _bounds.at(phi->id());
 30.1018 +                     if (bound_stack && bound_stack->length() > 0) {
 30.1019 +                       Bound *bound = bound_stack->top();
 30.1020 +                       if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != phi || bound->upper_instr() != phi || bound->lower() != 0 || bound->upper() != 0)) {
 30.1021 +                           TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth());
 30.1022 +                                                         tty->print("i%d", phi->id());
 30.1023 +                                                         tty->print(": ");
 30.1024 +                                                         bound->print();
 30.1025 +                                                         tty->print_cr("");
 30.1026 +                           );
 30.1027 +                         }
 30.1028 +                     });
 30.1029 +
 30.1030 +    while (!instr->as_BlockEnd()) {
 30.1031 +      if (instr->id() < _bounds.length()) {
 30.1032 +        BoundStack *bound_stack = _bounds.at(instr->id());
 30.1033 +        if (bound_stack && bound_stack->length() > 0) {
 30.1034 +          Bound *bound = bound_stack->top();
 30.1035 +          if ((bound->has_lower() || bound->has_upper()) && (bound->lower_instr() != instr || bound->upper_instr() != instr || bound->lower() != 0 || bound->upper() != 0)) {
 30.1036 +              TRACE_RANGE_CHECK_ELIMINATION(tty->fill_to(2*block->dominator_depth());
 30.1037 +                                            tty->print("i%d", instr->id());
 30.1038 +                                            tty->print(": ");
 30.1039 +                                            bound->print();
 30.1040 +                                            tty->print_cr("");
 30.1041 +              );
 30.1042 +          }
 30.1043 +        }
 30.1044 +      }
 30.1045 +      instr = instr->next();
 30.1046 +    }
 30.1047 +  }
 30.1048 +}
 30.1049 +#endif
 30.1050 +
 30.1051 +// Verification or the IR
 30.1052 +RangeCheckEliminator::Verification::Verification(IR *ir) : _used(BlockBegin::number_of_blocks(), false) {
 30.1053 +  this->_ir = ir;
 30.1054 +  ir->iterate_linear_scan_order(this);
 30.1055 +}
 30.1056 +
 30.1057 +// Verify this block
 30.1058 +void RangeCheckEliminator::Verification::block_do(BlockBegin *block) {
 30.1059 +  If *cond = block->end()->as_If();
 30.1060 +  // Watch out: tsux and fsux can be the same!
 30.1061 +  if (block->number_of_sux() > 1) {
 30.1062 +    for (int i=0; i<block->number_of_sux(); i++) {
 30.1063 +      BlockBegin *sux = block->sux_at(i);
 30.1064 +      BlockBegin *pred = NULL;
 30.1065 +      for (int j=0; j<sux->number_of_preds(); j++) {
 30.1066 +        BlockBegin *cur = sux->pred_at(j);
 30.1067 +        assert(cur != NULL, "Predecessor must not be null");
 30.1068 +        if (!pred) {
 30.1069 +          pred = cur;
 30.1070 +        }
 30.1071 +        assert(cur == pred, "Block must not have more than one predecessor if its predecessor has more than one successor");
 30.1072 +      }
 30.1073 +      assert(sux->number_of_preds() >= 1, "Block must have at least one predecessor");
 30.1074 +      assert(sux->pred_at(0) == block, "Wrong successor");
 30.1075 +    }
 30.1076 +  }
 30.1077 +
 30.1078 +  BlockBegin *dominator = block->dominator();
 30.1079 +  if (dominator) {
 30.1080 +    assert(block != _ir->start(), "Start block must not have a dominator!");
 30.1081 +    assert(can_reach(dominator, block), "Dominator can't reach his block !");
 30.1082 +    assert(can_reach(_ir->start(), dominator), "Dominator is unreachable !");
 30.1083 +    assert(!can_reach(_ir->start(), block, dominator), "Wrong dominator ! Block can be reached anyway !");
 30.1084 +    BlockList *all_blocks = _ir->linear_scan_order();
 30.1085 +    for (int i=0; i<all_blocks->length(); i++) {
 30.1086 +      BlockBegin *cur = all_blocks->at(i);
 30.1087 +      if (cur != dominator && cur != block) {
 30.1088 +        assert(can_reach(dominator, block, cur), "There has to be another dominator!");
 30.1089 +      }
 30.1090 +    }
 30.1091 +  } else {
 30.1092 +    assert(block == _ir->start(), "Only start block must not have a dominator");
 30.1093 +  }
 30.1094 +
 30.1095 +  if (block->is_set(BlockBegin::linear_scan_loop_header_flag)) {
 30.1096 +    int loop_index = block->loop_index();
 30.1097 +    BlockList *all_blocks = _ir->linear_scan_order();
 30.1098 +    assert(block->number_of_preds() >= 1, "Block must have at least one predecessor");
 30.1099 +    assert(!block->is_set(BlockBegin::exception_entry_flag), "Loop header must not be exception handler!");
 30.1100 +    // Sometimes, the backbranch comes from an exception handler. In
 30.1101 +    // this case, loop indexes/loop depths may not appear correct.
 30.1102 +    bool loop_through_xhandler = false;
 30.1103 +    for (int i = 0; i < block->number_of_exception_handlers(); i++) {
 30.1104 +      BlockBegin *xhandler = block->exception_handler_at(i);
 30.1105 +      for (int j = 0; j < block->number_of_preds(); j++) {
 30.1106 +        if (dominates(xhandler, block->pred_at(j)) || xhandler == block->pred_at(j)) {
 30.1107 +          loop_through_xhandler = true;
 30.1108 +        }
 30.1109 +      }
 30.1110 +    }
 30.1111 +
 30.1112 +    for (int i=0; i<block->number_of_sux(); i++) {
 30.1113 +      BlockBegin *sux = block->sux_at(i);
 30.1114 +      assert(sux->loop_depth() != block->loop_depth() || sux->loop_index() == block->loop_index() || loop_through_xhandler, "Loop index has to be same");
 30.1115 +      assert(sux->loop_depth() == block->loop_depth() || sux->loop_index() != block->loop_index(), "Loop index has to be different");
 30.1116 +    }
 30.1117 +
 30.1118 +    for (int i=0; i<all_blocks->length(); i++) {
 30.1119 +      BlockBegin *cur = all_blocks->at(i);
 30.1120 +      if (cur->loop_index() == loop_index && cur != block) {
 30.1121 +        assert(dominates(block->dominator(), cur), "Dominator of loop header must dominate all loop blocks");
 30.1122 +      }
 30.1123 +    }
 30.1124 +  }
 30.1125 +
 30.1126 +  Instruction *cur = block;
 30.1127 +  while (cur) {
 30.1128 +    assert(cur->block() == block, "Block begin has to be set correctly!");
 30.1129 +    cur = cur->next();
 30.1130 +  }
 30.1131 +}
 30.1132 +
 30.1133 +// Loop header must dominate all loop blocks
 30.1134 +bool RangeCheckEliminator::Verification::dominates(BlockBegin *dominator, BlockBegin *block) {
 30.1135 +  BlockBegin *cur = block->dominator();
 30.1136 +  while (cur && cur != dominator) {
 30.1137 +    cur = cur->dominator();
 30.1138 +  }
 30.1139 +  return cur == dominator;
 30.1140 +}
 30.1141 +
 30.1142 +// Try to reach Block end beginning in Block start and not using Block dont_use
 30.1143 +bool RangeCheckEliminator::Verification::can_reach(BlockBegin *start, BlockBegin *end, BlockBegin *dont_use /* = NULL */) {
 30.1144 +  if (start == end) return start != dont_use;
 30.1145 +  // Simple BSF from start to end
 30.1146 +  //  BlockBeginList _current;
 30.1147 +  for (int i=0; i<_used.length(); i++) {
 30.1148 +    _used[i] = false;
 30.1149 +  }
 30.1150 +  _current.truncate(0);
 30.1151 +  _successors.truncate(0);
 30.1152 +  if (start != dont_use) {
 30.1153 +    _current.push(start);
 30.1154 +    _used[start->block_id()] = true;
 30.1155 +  }
 30.1156 +
 30.1157 +  //  BlockBeginList _successors;
 30.1158 +  while (_current.length() > 0) {
 30.1159 +    BlockBegin *cur = _current.pop();
 30.1160 +    // Add exception handlers to list
 30.1161 +    for (int i=0; i<cur->number_of_exception_handlers(); i++) {
 30.1162 +      BlockBegin *xhandler = cur->exception_handler_at(i);
 30.1163 +      _successors.push(xhandler);
 30.1164 +      // Add exception handlers of _successors to list
 30.1165 +      for (int j=0; j<xhandler->number_of_exception_handlers(); j++) {
 30.1166 +        BlockBegin *sux_xhandler = xhandler->exception_handler_at(j);
 30.1167 +        _successors.push(sux_xhandler);
 30.1168 +      }
 30.1169 +    }
 30.1170 +    // Add normal _successors to list
 30.1171 +    for (int i=0; i<cur->number_of_sux(); i++) {
 30.1172 +      BlockBegin *sux = cur->sux_at(i);
 30.1173 +      _successors.push(sux);
 30.1174 +      // Add exception handlers of _successors to list
 30.1175 +      for (int j=0; j<sux->number_of_exception_handlers(); j++) {
 30.1176 +        BlockBegin *xhandler = sux->exception_handler_at(j);
 30.1177 +        _successors.push(xhandler);
 30.1178 +      }
 30.1179 +    }
 30.1180 +    for (int i=0; i<_successors.length(); i++) {
 30.1181 +      BlockBegin *sux = _successors[i];
 30.1182 +      assert(sux != NULL, "Successor must not be NULL!");
 30.1183 +      if (sux == end) {
 30.1184 +        return true;
 30.1185 +      }
 30.1186 +      if (sux != dont_use && !_used[sux->block_id()]) {
 30.1187 +        _used[sux->block_id()] = true;
 30.1188 +        _current.push(sux);
 30.1189 +      }
 30.1190 +    }
 30.1191 +    _successors.truncate(0);
 30.1192 +  }
 30.1193 +
 30.1194 +  return false;
 30.1195 +}
 30.1196 +
 30.1197 +// Bound
 30.1198 +RangeCheckEliminator::Bound::~Bound() {
 30.1199 +}
 30.1200 +
 30.1201 +// Bound constructor
 30.1202 +RangeCheckEliminator::Bound::Bound() {
 30.1203 +  init();
 30.1204 +  this->_lower = min_jint;
 30.1205 +  this->_upper = max_jint;
 30.1206 +  this->_lower_instr = NULL;
 30.1207 +  this->_upper_instr = NULL;
 30.1208 +}
 30.1209 +
 30.1210 +// Bound constructor
 30.1211 +RangeCheckEliminator::Bound::Bound(int lower, Value lower_instr, int upper, Value upper_instr) {
 30.1212 +  init();
 30.1213 +  assert(!lower_instr || !lower_instr->as_Constant() || !lower_instr->type()->as_IntConstant(), "Must not be constant!");
 30.1214 +  assert(!upper_instr || !upper_instr->as_Constant() || !upper_instr->type()->as_IntConstant(), "Must not be constant!");
 30.1215 +  this->_lower = lower;
 30.1216 +  this->_upper = upper;
 30.1217 +  this->_lower_instr = lower_instr;
 30.1218 +  this->_upper_instr = upper_instr;
 30.1219 +}
 30.1220 +
 30.1221 +// Bound constructor
 30.1222 +RangeCheckEliminator::Bound::Bound(Instruction::Condition cond, Value v, int constant) {
 30.1223 +  assert(!v || (v->type() && (v->type()->as_IntType() || v->type()->as_ObjectType())), "Type must be array or integer!");
 30.1224 +  assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!");
 30.1225 +
 30.1226 +  init();
 30.1227 +  if (cond == Instruction::eql) {
 30.1228 +    _lower = constant;
 30.1229 +    _lower_instr = v;
 30.1230 +    _upper = constant;
 30.1231 +    _upper_instr = v;
 30.1232 +  } else if (cond == Instruction::neq) {
 30.1233 +    _lower = min_jint;
 30.1234 +    _upper = max_jint;
 30.1235 +    _lower_instr = NULL;
 30.1236 +    _upper_instr = NULL;
 30.1237 +    if (v == NULL) {
 30.1238 +      if (constant == min_jint) {
 30.1239 +        _lower++;
 30.1240 +      }
 30.1241 +      if (constant == max_jint) {
 30.1242 +        _upper--;
 30.1243 +      }
 30.1244 +    }
 30.1245 +  } else if (cond == Instruction::geq) {
 30.1246 +    _lower = constant;
 30.1247 +    _lower_instr = v;
 30.1248 +    _upper = max_jint;
 30.1249 +    _upper_instr = NULL;
 30.1250 +  } else if (cond == Instruction::leq) {
 30.1251 +    _lower = min_jint;
 30.1252 +    _lower_instr = NULL;
 30.1253 +    _upper = constant;
 30.1254 +    _upper_instr = v;
 30.1255 +  } else {
 30.1256 +    ShouldNotReachHere();
 30.1257 +  }
 30.1258 +}
 30.1259 +
 30.1260 +// Set lower
 30.1261 +void RangeCheckEliminator::Bound::set_lower(int value, Value v) {
 30.1262 +  assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!");
 30.1263 +  this->_lower = value;
 30.1264 +  this->_lower_instr = v;
 30.1265 +}
 30.1266 +
 30.1267 +// Set upper
 30.1268 +void RangeCheckEliminator::Bound::set_upper(int value, Value v) {
 30.1269 +  assert(!v || !v->as_Constant() || !v->type()->as_IntConstant(), "Must not be constant!");
 30.1270 +  this->_upper = value;
 30.1271 +  this->_upper_instr = v;
 30.1272 +}
 30.1273 +
 30.1274 +// Add constant -> no overflow may occur
 30.1275 +void RangeCheckEliminator::Bound::add_constant(int value) {
 30.1276 +  this->_lower += value;
 30.1277 +  this->_upper += value;
 30.1278 +}
 30.1279 +
 30.1280 +// Init
 30.1281 +void RangeCheckEliminator::Bound::init() {
 30.1282 +}
 30.1283 +
 30.1284 +// or
 30.1285 +void RangeCheckEliminator::Bound::or_op(Bound *b) {
 30.1286 +  // Watch out, bound is not guaranteed not to overflow!
 30.1287 +  // Update lower bound
 30.1288 +  if (_lower_instr != b->_lower_instr || (_lower_instr && _lower != b->_lower)) {
 30.1289 +    _lower_instr = NULL;
 30.1290 +    _lower = min_jint;
 30.1291 +  } else {
 30.1292 +    _lower = MIN2(_lower, b->_lower);
 30.1293 +  }
 30.1294 +  // Update upper bound
 30.1295 +  if (_upper_instr != b->_upper_instr || (_upper_instr && _upper != b->_upper)) {
 30.1296 +    _upper_instr = NULL;
 30.1297 +    _upper = max_jint;
 30.1298 +  } else {
 30.1299 +    _upper = MAX2(_upper, b->_upper);
 30.1300 +  }
 30.1301 +}
 30.1302 +
 30.1303 +// and
 30.1304 +void RangeCheckEliminator::Bound::and_op(Bound *b) {
 30.1305 +  // Update lower bound
 30.1306 +  if (_lower_instr == b->_lower_instr) {
 30.1307 +    _lower = MAX2(_lower, b->_lower);
 30.1308 +  }
 30.1309 +  if (b->has_lower()) {
 30.1310 +    bool set = true;
 30.1311 +    if (_lower_instr != NULL && b->_lower_instr != NULL) {
 30.1312 +      set = (_lower_instr->dominator_depth() > b->_lower_instr->dominator_depth());
 30.1313 +    }
 30.1314 +    if (set) {
 30.1315 +      _lower = b->_lower;
 30.1316 +      _lower_instr = b->_lower_instr;
 30.1317 +    }
 30.1318 +  }
 30.1319 +  // Update upper bound
 30.1320 +  if (_upper_instr == b->_upper_instr) {
 30.1321 +    _upper = MIN2(_upper, b->_upper);
 30.1322 +  }
 30.1323 +  if (b->has_upper()) {
 30.1324 +    bool set = true;
 30.1325 +    if (_upper_instr != NULL && b->_upper_instr != NULL) {
 30.1326 +      set = (_upper_instr->dominator_depth() > b->_upper_instr->dominator_depth());
 30.1327 +    }
 30.1328 +    if (set) {
 30.1329 +      _upper = b->_upper;
 30.1330 +      _upper_instr = b->_upper_instr;
 30.1331 +    }
 30.1332 +  }
 30.1333 +}
 30.1334 +
 30.1335 +// has_upper
 30.1336 +bool RangeCheckEliminator::Bound::has_upper() {
 30.1337 +  return _upper_instr != NULL || _upper < max_jint;
 30.1338 +}
 30.1339 +
 30.1340 +// is_smaller
 30.1341 +bool RangeCheckEliminator::Bound::is_smaller(Bound *b) {
 30.1342 +  if (b->_lower_instr != _upper_instr) {
 30.1343 +    return false;
 30.1344 +  }
 30.1345 +  return _upper < b->_lower;
 30.1346 +}
 30.1347 +
 30.1348 +// has_lower
 30.1349 +bool RangeCheckEliminator::Bound::has_lower() {
 30.1350 +  return _lower_instr != NULL || _lower > min_jint;
 30.1351 +}
 30.1352 +
 30.1353 +// in_array_bound
 30.1354 +bool RangeCheckEliminator::in_array_bound(Bound *bound, Value array){
 30.1355 +  if (!bound) return false;
 30.1356 +  assert(array != NULL, "Must not be null!");
 30.1357 +  assert(bound != NULL, "Must not be null!");
 30.1358 +  if (bound->lower() >=0 && bound->lower_instr() == NULL && bound->upper() < 0 && bound->upper_instr() != NULL) {
 30.1359 +    ArrayLength *len = bound->upper_instr()->as_ArrayLength();
 30.1360 +    if (bound->upper_instr() == array || (len != NULL && len->array() == array)) {
 30.1361 +      return true;
 30.1362 +    }
 30.1363 +  }
 30.1364 +  return false;
 30.1365 +}
 30.1366 +
 30.1367 +// remove_lower
 30.1368 +void RangeCheckEliminator::Bound::remove_lower() {
 30.1369 +  _lower = min_jint;
 30.1370 +  _lower_instr = NULL;
 30.1371 +}
 30.1372 +
 30.1373 +// remove_upper
 30.1374 +void RangeCheckEliminator::Bound::remove_upper() {
 30.1375 +  _upper = max_jint;
 30.1376 +  _upper_instr = NULL;
 30.1377 +}
 30.1378 +
 30.1379 +// upper
 30.1380 +int RangeCheckEliminator::Bound::upper() {
 30.1381 +  return _upper;
 30.1382 +}
 30.1383 +
 30.1384 +// lower
 30.1385 +int RangeCheckEliminator::Bound::lower() {
 30.1386 +  return _lower;
 30.1387 +}
 30.1388 +
 30.1389 +// upper_instr
 30.1390 +Value RangeCheckEliminator::Bound::upper_instr() {
 30.1391 +  return _upper_instr;
 30.1392 +}
 30.1393 +
 30.1394 +// lower_instr
 30.1395 +Value RangeCheckEliminator::Bound::lower_instr() {
 30.1396 +  return _lower_instr;
 30.1397 +}
 30.1398 +
 30.1399 +// print
 30.1400 +void RangeCheckEliminator::Bound::print() {
 30.1401 +  tty->print("");
 30.1402 +  if (this->_lower_instr || this->_lower != min_jint) {
 30.1403 +    if (this->_lower_instr) {
 30.1404 +      tty->print("i%d", this->_lower_instr->id());
 30.1405 +      if (this->_lower > 0) {
 30.1406 +        tty->print("+%d", _lower);
 30.1407 +      }
 30.1408 +      if (this->_lower < 0) {
 30.1409 +        tty->print("%d", _lower);
 30.1410 +      }
 30.1411 +    } else {
 30.1412 +      tty->print("%d", _lower);
 30.1413 +    }
 30.1414 +    tty->print(" <= ");
 30.1415 +  }
 30.1416 +  tty->print("x");
 30.1417 +  if (this->_upper_instr || this->_upper != max_jint) {
 30.1418 +    tty->print(" <= ");
 30.1419 +    if (this->_upper_instr) {
 30.1420 +      tty->print("i%d", this->_upper_instr->id());
 30.1421 +      if (this->_upper > 0) {
 30.1422 +        tty->print("+%d", _upper);
 30.1423 +      }
 30.1424 +      if (this->_upper < 0) {
 30.1425 +        tty->print("%d", _upper);
 30.1426 +      }
 30.1427 +    } else {
 30.1428 +      tty->print("%d", _upper);
 30.1429 +    }
 30.1430 +  }
 30.1431 +}
 30.1432 +
 30.1433 +// Copy
 30.1434 +RangeCheckEliminator::Bound *RangeCheckEliminator::Bound::copy() {
 30.1435 +  Bound *b = new Bound();
 30.1436 +  b->_lower = _lower;
 30.1437 +  b->_lower_instr = _lower_instr;
 30.1438 +  b->_upper = _upper;
 30.1439 +  b->_upper_instr = _upper_instr;
 30.1440 +  return b;
 30.1441 +}
 30.1442 +
 30.1443 +#ifdef ASSERT
 30.1444 +// Add assertion
 30.1445 +void RangeCheckEliminator::Bound::add_assertion(Instruction *instruction, Instruction *position, int i, Value instr, Instruction::Condition cond) {
 30.1446 +  Instruction *result = position;
 30.1447 +  Instruction *compare_with = NULL;
 30.1448 +  ValueStack *state = position->state_before();
 30.1449 +  if (position->as_BlockEnd() && !position->as_Goto()) {
 30.1450 +    state = position->as_BlockEnd()->state_before();
 30.1451 +  }
 30.1452 +  Instruction *instruction_before = position->prev();
 30.1453 +  if (position->as_Return() && Compilation::current()->method()->is_synchronized() && instruction_before->as_MonitorExit()) {
 30.1454 +    instruction_before = instruction_before->prev();
 30.1455 +  }
 30.1456 +  result = instruction_before;
 30.1457 +  // Load constant only if needed
 30.1458 +  Constant *constant = NULL;
 30.1459 +  if (i != 0 || !instr) {
 30.1460 +    constant = new Constant(new IntConstant(i));
 30.1461 +    NOT_PRODUCT(constant->set_printable_bci(position->printable_bci()));
 30.1462 +    result = result->insert_after(constant);
 30.1463 +    compare_with = constant;
 30.1464 +  }
 30.1465 +
 30.1466 +  if (instr) {
 30.1467 +    assert(instr->type()->as_ObjectType() || instr->type()->as_IntType(), "Type must be array or integer!");
 30.1468 +    compare_with = instr;
 30.1469 +    // Load array length if necessary
 30.1470 +    Instruction *op = instr;
 30.1471 +    if (instr->type()->as_ObjectType()) {
 30.1472 +      assert(state, "must not be null");
 30.1473 +      ArrayLength *length = new ArrayLength(instr, state->copy());
 30.1474 +      NOT_PRODUCT(length->set_printable_bci(position->printable_bci()));
 30.1475 +      length->set_exception_state(length->state_before());
 30.1476 +      result = result->insert_after(length);
 30.1477 +      op = length;
 30.1478 +      compare_with = length;
 30.1479 +    }
 30.1480 +    // Add operation only if necessary
 30.1481 +    if (constant) {
 30.1482 +      ArithmeticOp *ao = new ArithmeticOp(Bytecodes::_iadd, constant, op, false, NULL);
 30.1483 +      NOT_PRODUCT(ao->set_printable_bci(position->printable_bci()));
 30.1484 +      result = result->insert_after(ao);
 30.1485 +      compare_with = ao;
 30.1486 +      // TODO: Check that add operation does not overflow!
 30.1487 +    }
 30.1488 +  }
 30.1489 +  assert(compare_with != NULL, "You have to compare with something!");
 30.1490 +  assert(instruction != NULL, "Instruction must not be null!");
 30.1491 +
 30.1492 +  if (instruction->type()->as_ObjectType()) {
 30.1493 +    // Load array length if necessary
 30.1494 +    Instruction *op = instruction;
 30.1495 +    assert(state, "must not be null");
 30.1496 +    ArrayLength *length = new ArrayLength(instruction, state->copy());
 30.1497 +    length->set_exception_state(length->state_before());
 30.1498 +    NOT_PRODUCT(length->set_printable_bci(position->printable_bci()));
 30.1499 +    result = result->insert_after(length);
 30.1500 +    instruction = length;
 30.1501 +  }
 30.1502 +
 30.1503 +  Assert *assert = new Assert(instruction, cond, false, compare_with);
 30.1504 +  NOT_PRODUCT(assert->set_printable_bci(position->printable_bci()));
 30.1505 +  result->insert_after(assert);
 30.1506 +}
 30.1507 +
 30.1508 +// Add assertions
 30.1509 +void RangeCheckEliminator::add_assertions(Bound *bound, Instruction *instruction, Instruction *position) {
 30.1510 +  // Add lower bound assertion
 30.1511 +  if (bound->has_lower()) {
 30.1512 +    bound->add_assertion(instruction, position, bound->lower(), bound->lower_instr(), Instruction::geq);
 30.1513 +  }
 30.1514 +  // Add upper bound assertion
 30.1515 +  if (bound->has_upper()) {
 30.1516 +    bound->add_assertion(instruction, position, bound->upper(), bound->upper_instr(), Instruction::leq);
 30.1517 +  }
 30.1518 +}
 30.1519 +#endif
 30.1520 +

    31.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    31.2 +++ b/src/share/vm/c1/c1_RangeCheckElimination.hpp	Thu Mar 21 09:27:54 2013 +0100
    31.3 @@ -0,0 +1,241 @@
    31.4 +/*
    31.5 + * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
    31.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
    31.7 + *
    31.8 + * This code is free software; you can redistribute it and/or modify it
    31.9 + * under the terms of the GNU General Public License version 2 only, as
   31.10 + * published by the Free Software Foundation.
   31.11 + *
   31.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
   31.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   31.14 + * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   31.15 + * version 2 for more details (a copy is included in the LICENSE file that
   31.16 + * accompanied this code).
   31.17 + *
   31.18 + * You should have received a copy of the GNU General Public License version
   31.19 + * 2 along with this work; if not, write to the Free Software Foundation,
   31.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   31.21 + *
   31.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   31.23 + * or visit www.oracle.com if you need additional information or have any
   31.24 + * questions.
   31.25 + *
   31.26 + */
   31.27 +
   31.28 +#ifndef SHARE_VM_C1_C1_RANGECHECKELIMINATION_HPP
   31.29 +#define SHARE_VM_C1_C1_RANGECHECKELIMINATION_HPP
   31.30 +
   31.31 +#include "c1/c1_Instruction.hpp"
   31.32 +
   31.33 +// Base class for range check elimination
   31.34 +class RangeCheckElimination : AllStatic {
   31.35 +public:
   31.36 +  static void eliminate(IR *ir);
   31.37 +};
   31.38 +
   31.39 +// Implementation
   31.40 +class RangeCheckEliminator VALUE_OBJ_CLASS_SPEC {
   31.41 +private:
   31.42 +  int _number_of_instructions;
   31.43 +  bool _optimistic; // Insert predicates and deoptimize when they fail
   31.44 +  IR *_ir;
   31.45 +
   31.46 +  define_array(BlockBeginArray, BlockBegin*)
   31.47 +  define_stack(BlockBeginList, BlockBeginArray)
   31.48 +  define_stack(IntegerStack, intArray)
   31.49 +  define_array(IntegerMap, IntegerStack*)
   31.50 +
   31.51 +  class Verification : public _ValueObj /*VALUE_OBJ_CLASS_SPEC*/, public BlockClosure {
   31.52 +  private:
   31.53 +    IR *_ir;
   31.54 +    boolArray _used;
   31.55 +    BlockBeginList _current;
   31.56 +    BlockBeginList _successors;
   31.57 +
   31.58 +  public:
   31.59 +    Verification(IR *ir);
   31.60 +    virtual void block_do(BlockBegin *block);
   31.61 +    bool can_reach(BlockBegin *start, BlockBegin *end, BlockBegin *dont_use = NULL);
   31.62 +    bool dominates(BlockBegin *dominator, BlockBegin *block);
   31.63 +  };
   31.64 +
   31.65 +public:
   31.66 +  // Bounds for an instruction in the form x + c which c integer
   31.67 +  // constant and x another instruction
   31.68 +  class Bound : public CompilationResourceObj {
   31.69 +  private:
   31.70 +    int _upper;
   31.71 +    Value _upper_instr;
   31.72 +    int _lower;
   31.73 +    Value _lower_instr;
   31.74 +
   31.75 +  public:
   31.76 +    Bound();
   31.77 +    Bound(Value v);
   31.78 +    Bound(Instruction::Condition cond, Value v, int constant = 0);
   31.79 +    Bound(int lower, Value lower_instr, int upper, Value upper_instr);
   31.80 +    ~Bound();
   31.81 +
   31.82 +#ifdef ASSERT
   31.83 +    void add_assertion(Instruction *instruction, Instruction *position, int i, Value instr, Instruction::Condition cond);
   31.84 +#endif
   31.85 +    int upper();
   31.86 +    Value upper_instr();
   31.87 +    int lower();
   31.88 +    Value lower_instr();
   31.89 +    void print();
   31.90 +    bool check_no_overflow(int const_value);
   31.91 +    void or_op(Bound *b);
   31.92 +    void and_op(Bound *b);
   31.93 +    bool has_upper();
   31.94 +    bool has_lower();
   31.95 +    void set_upper(int upper, Value upper_instr);
   31.96 +    void set_lower(int lower, Value lower_instr);
   31.97 +    bool is_smaller(Bound *b);
   31.98 +    void remove_upper();
   31.99 +    void remove_lower();
  31.100 +    void add_constant(int value);
  31.101 +    Bound *copy();
  31.102 +
  31.103 +  private:
  31.104 +    void init();
  31.105 +  };
  31.106 +
  31.107 +
  31.108 +  class Visitor : public InstructionVisitor {
  31.109 +  private:
  31.110 +    Bound *_bound;
  31.111 +    RangeCheckEliminator *_rce;
  31.112 +
  31.113 +  public:
  31.114 +    void set_range_check_eliminator(RangeCheckEliminator *rce) { _rce = rce; }
  31.115 +    Bound *bound() const { return _bound; }
  31.116 +    void clear_bound() { _bound = NULL; }
  31.117 +
  31.118 +  protected:
  31.119 +    // visitor functions
  31.120 +    void do_Constant       (Constant*        x);
  31.121 +    void do_IfOp           (IfOp*            x);
  31.122 +    void do_LogicOp        (LogicOp*         x);
  31.123 +    void do_ArithmeticOp   (ArithmeticOp*    x);
  31.124 +    void do_Phi            (Phi*             x);
  31.125 +
  31.126 +    void do_StoreField     (StoreField*      x) { /* nothing to do */ };
  31.127 +    void do_StoreIndexed   (StoreIndexed*    x) { /* nothing to do */ };
  31.128 +    void do_MonitorEnter   (MonitorEnter*    x) { /* nothing to do */ };
  31.129 +    void do_MonitorExit    (MonitorExit*     x) { /* nothing to do */ };
  31.130 +    void do_Invoke         (Invoke*          x) { /* nothing to do */ };
  31.131 +    void do_UnsafePutRaw   (UnsafePutRaw*    x) { /* nothing to do */ };
  31.132 +    void do_UnsafePutObject(UnsafePutObject* x) { /* nothing to do */ };
  31.133 +    void do_Intrinsic      (Intrinsic*       x) { /* nothing to do */ };
  31.134 +    void do_Local          (Local*           x) { /* nothing to do */ };
  31.135 +    void do_LoadField      (LoadField*       x) { /* nothing to do */ };
  31.136 +    void do_ArrayLength    (ArrayLength*     x) { /* nothing to do */ };
  31.137 +    void do_LoadIndexed    (LoadIndexed*     x) { /* nothing to do */ };
  31.138 +    void do_NegateOp       (NegateOp*        x) { /* nothing to do */ };
  31.139 +    void do_ShiftOp        (ShiftOp*         x) { /* nothing to do */ };
  31.140 +    void do_CompareOp      (CompareOp*       x) { /* nothing to do */ };
  31.141 +    void do_Convert        (Convert*         x) { /* nothing to do */ };
  31.142 +    void do_NullCheck      (NullCheck*       x) { /* nothing to do */ };
  31.143 +    void do_TypeCast       (TypeCast*        x) { /* nothing to do */ };
  31.144 +    void do_NewInstance    (NewInstance*     x) { /* nothing to do */ };
  31.145 +    void do_NewTypeArray   (NewTypeArray*    x) { /* nothing to do */ };
  31.146 +    void do_NewObjectArray (NewObjectArray*  x) { /* nothing to do */ };
  31.147 +    void do_NewMultiArray  (NewMultiArray*   x) { /* nothing to do */ };
  31.148 +    void do_CheckCast      (CheckCast*       x) { /* nothing to do */ };
  31.149 +    void do_InstanceOf     (InstanceOf*      x) { /* nothing to do */ };
  31.150 +    void do_BlockBegin     (BlockBegin*      x) { /* nothing to do */ };
  31.151 +    void do_Goto           (Goto*            x) { /* nothing to do */ };
  31.152 +    void do_If             (If*              x) { /* nothing to do */ };
  31.153 +    void do_IfInstanceOf   (IfInstanceOf*    x) { /* nothing to do */ };
  31.154 +    void do_TableSwitch    (TableSwitch*     x) { /* nothing to do */ };
  31.155 +    void do_LookupSwitch   (LookupSwitch*    x) { /* nothing to do */ };
  31.156 +    void do_Return         (Return*          x) { /* nothing to do */ };
  31.157 +    void do_Throw          (Throw*           x) { /* nothing to do */ };
  31.158 +    void do_Base           (Base*            x) { /* nothing to do */ };
  31.159 +    void do_OsrEntry       (OsrEntry*        x) { /* nothing to do */ };
  31.160 +    void do_ExceptionObject(ExceptionObject* x) { /* nothing to do */ };
  31.161 +    void do_RoundFP        (RoundFP*         x) { /* nothing to do */ };
  31.162 +    void do_UnsafeGetRaw   (UnsafeGetRaw*    x) { /* nothing to do */ };
  31.163 +    void do_UnsafeGetObject(UnsafeGetObject* x) { /* nothing to do */ };
  31.164 +    void do_UnsafeGetAndSetObject(UnsafeGetAndSetObject* x) { /* nothing to do */ };
  31.165 +    void do_UnsafePrefetchRead (UnsafePrefetchRead*  x) { /* nothing to do */ };
  31.166 +    void do_UnsafePrefetchWrite(UnsafePrefetchWrite* x) { /* nothing to do */ };
  31.167 +    void do_ProfileCall    (ProfileCall*     x) { /* nothing to do */ };
  31.168 +    void do_ProfileInvoke  (ProfileInvoke*  x)  { /* nothing to do */ };
  31.169 +    void do_RuntimeCall    (RuntimeCall*     x) { /* nothing to do */ };
  31.170 +    void do_MemBar         (MemBar*          x) { /* nothing to do */ };
  31.171 +    void do_RangeCheckPredicate(RangeCheckPredicate* x) { /* nothing to do */ };
  31.172 +    void do_Assert         (Assert*          x) { /* nothing to do */ };
  31.173 +  };
  31.174 +
  31.175 +#ifdef ASSERT
  31.176 +  void add_assertions(Bound *bound, Instruction *instruction, Instruction *position);
  31.177 +#endif
  31.178 +
  31.179 +  define_array(BoundArray, Bound *)
  31.180 +  define_stack(BoundStack, BoundArray)
  31.181 +  define_array(BoundMap, BoundStack *)
  31.182 +  define_array(AccessIndexedArray, AccessIndexed *)
  31.183 +  define_stack(AccessIndexedList, AccessIndexedArray)
  31.184 +  define_array(InstructionArray, Instruction *)
  31.185 +  define_stack(InstructionList, InstructionArray)
  31.186 +
  31.187 +  class AccessIndexedInfo : public CompilationResourceObj  {
  31.188 +  public:
  31.189 +    AccessIndexedList *_list;
  31.190 +    int _min;
  31.191 +    int _max;
  31.192 +  };
  31.193 +
  31.194 +  define_array(AccessIndexedInfoArray, AccessIndexedInfo *)
  31.195 +  BoundMap _bounds; // Mapping from Instruction's id to current bound
  31.196 +  AccessIndexedInfoArray _access_indexed_info; // Mapping from Instruction's id to AccessIndexedInfo for in block motion
  31.197 +  Visitor _visitor;
  31.198 +
  31.199 +public:
  31.200 +  RangeCheckEliminator(IR *ir);
  31.201 +
  31.202 +  IR *ir() const { return _ir; }
  31.203 +
  31.204 +  // Pass over the dominator tree to identify blocks where there's an oppportunity for optimization
  31.205 +  bool set_process_block_flags(BlockBegin *block);
  31.206 +  // The core of the optimization work: pass over the dominator tree
  31.207 +  // to propagate bound information, insert predicate out of loops,
  31.208 +  // eliminate bound checks when possible and perform in block motion
  31.209 +  void calc_bounds(BlockBegin *block, BlockBegin *loop_header);
  31.210 +  // reorder bound checks within a block in order to eliminate some of them
  31.211 +  void in_block_motion(BlockBegin *block, AccessIndexedList &accessIndexed, InstructionList &arrays);
  31.212 +
  31.213 +  // update/access current bound
  31.214 +  void update_bound(IntegerStack &pushed, Value v, Instruction::Condition cond, Value value, int constant);
  31.215 +  void update_bound(IntegerStack &pushed, Value v, Bound *bound);
  31.216 +  Bound *get_bound(Value v);
  31.217 +
  31.218 +  bool loop_invariant(BlockBegin *loop_header, Instruction *instruction);                                    // check for loop invariance
  31.219 +  void add_access_indexed_info(InstructionList &indices, int i, Value instruction, AccessIndexed *ai); // record indexed access for in block motion
  31.220 +  void remove_range_check(AccessIndexed *ai);                                                                // Mark this instructions as not needing a range check
  31.221 +  void add_if_condition(IntegerStack &pushed, Value x, Value y, Instruction::Condition condition);           // Update bound for an If
  31.222 +  bool in_array_bound(Bound *bound, Value array);                                                            // Check whether bound is known to fall within array
  31.223 +
  31.224 +  // helper functions to work with predicates
  31.225 +  Instruction* insert_after(Instruction* insert_position, Instruction* instr, int bci);
  31.226 +  Instruction* predicate(Instruction* left, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci=-1);
  31.227 +  Instruction* predicate_cmp_with_const(Instruction* instr, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci=1);
  31.228 +  Instruction* predicate_add(Instruction* left, int left_const, Instruction::Condition cond, Instruction* right, ValueStack* state, Instruction *insert_position, int bci=-1);
  31.229 +  Instruction* predicate_add_cmp_with_const(Instruction* left, int left_const, Instruction::Condition cond, int constant, ValueStack* state, Instruction *insert_position, int bci=-1);
  31.230 +
  31.231 +  void insert_deoptimization(ValueStack *state, Instruction *insert_position, Instruction *array_instr,      // Add predicate
  31.232 +                             Instruction *length_instruction, Instruction *lower_instr, int lower,
  31.233 +                             Instruction *upper_instr, int upper, AccessIndexed *ai);
  31.234 +  bool is_ok_for_deoptimization(Instruction *insert_position, Instruction *array_instr,                      // Can we safely add a predicate?
  31.235 +                                Instruction *length_instr, Instruction *lower_instr,
  31.236 +                                int lower, Instruction *upper_instr, int upper);
  31.237 +  void process_if(IntegerStack &pushed, BlockBegin *block, If *cond);                                        // process If Instruction
  31.238 +  void process_access_indexed(BlockBegin *loop_header, BlockBegin *block, AccessIndexed *ai);                // process indexed access
  31.239 +
  31.240 +  void dump_condition_stack(BlockBegin *cur_block);
  31.241 +  static void print_statistics();
  31.242 +};
  31.243 +
  31.244 +#endif // SHARE_VM_C1_C1_RANGECHECKELIMINATION_HPP