Deoptimization-based bce.

A mechanism is introduced that a runtime method can be called
from code compiled with optimizing compiler to deoptimize into
interpreter. This can be used to establish invariants in the managed code
If the invariant does not hold at runtime, we will deoptimize and continue
execution in the interpreter. This allows to optimize the managed code as
if the invariant was proven during compile time. However, the exception
will be thrown according to the semantics demanded by the spec.

The invariant and optimization included in this patch are based on the
length of an array. Given a set of array accesses with constant indices
{c1, ..., cn}, we can optimize away all bounds checks iff all 0 <= min(ci) and
max(ci) < array-length. The first can be proven statically. The second can be
established with a deoptimization-based invariant. This replaces n bounds
checks with one invariant check (plus slow-path code).

Change-Id: I8c6e34b56c85d25b91074832d13dba1db0a81569

2 files changed, 144 insertions, 5 deletions

diff --git a/test/449-checker-bce/expected.txt b/test/449-checker-bce/expected.txt
index e69de29bb2..29d6383b52 100644
--- a/test/449-checker-bce/expected.txt
+++ b/test/449-checker-bce/expected.txt
@@ -0,0 +1 @@
+100
diff --git a/test/449-checker-bce/src/Main.java b/test/449-checker-bce/src/Main.java
index 30aa870acb..17039a3492 100644
--- a/test/449-checker-bce/src/Main.java
+++ b/test/449-checker-bce/src/Main.java
@@ -108,29 +108,147 @@ public class Main {
   }
 
 
-  // CHECK-START: void Main.constantIndexing(int[]) BCE (before)
+  // CHECK-START: void Main.constantIndexing1(int[]) BCE (before)
   // CHECK: BoundsCheck
   // CHECK: ArraySet
   // CHECK: BoundsCheck
   // CHECK: ArraySet
+
+  // CHECK-START: void Main.constantIndexing1(int[]) BCE (after)
+  // CHECK-NOT: Deoptimize
   // CHECK: BoundsCheck
   // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
 
-  // CHECK-START: void Main.constantIndexing(int[]) BCE (after)
+  static void constantIndexing1(int[] array) {
+    array[5] = 1;
+    array[4] = 1;
+  }
+
+
+  // CHECK-START: void Main.constantIndexing2(int[]) BCE (before)
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
   // CHECK: BoundsCheck
   // CHECK: ArraySet
+
+  // CHECK-START: void Main.constantIndexing2(int[]) BCE (after)
+  // CHECK: LessThanOrEqual
+  // CHECK: Deoptimize
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
   // CHECK-NOT: BoundsCheck
   // CHECK: ArraySet
   // CHECK: BoundsCheck
   // CHECK: ArraySet
 
-  static void constantIndexing(int[] array) {
-    array[5] = 1;
+  static void constantIndexing2(int[] array) {
+    array[1] = 1;
+    array[2] = 1;
+    array[3] = 1;
     array[4] = 1;
-    array[6] = 1;
+    array[-1] = 1;
+  }
+
+
+  // CHECK-START: int[] Main.constantIndexing3(int[], int[], boolean) BCE (before)
+  // CHECK: BoundsCheck
+  // CHECK: ArrayGet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArrayGet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArrayGet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArrayGet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  // CHECK-START: int[] Main.constantIndexing3(int[], int[], boolean) BCE (after)
+  // CHECK: LessThanOrEqual
+  // CHECK: Deoptimize
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArrayGet
+  // CHECK: LessThanOrEqual
+  // CHECK: Deoptimize
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArrayGet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArrayGet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArrayGet
+  // CHECK-NOT: BoundsCheck
+  // CHECK: ArraySet
+
+  static int[] constantIndexing3(int[] array1, int[] array2, boolean copy) {
+    if (!copy) {
+      return array1;
+    }
+    array2[0] = array1[0];
+    array2[1] = array1[1];
+    array2[2] = array1[2];
+    array2[3] = array1[3];
+    return array2;
+  }
+
+
+  // CHECK-START: void Main.constantIndexing4(int[]) BCE (before)
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  // CHECK-START: void Main.constantIndexing4(int[]) BCE (after)
+  // CHECK-NOT: LessThanOrEqual
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  // There is only one array access. It's not beneficial
+  // to create a compare with deoptimization instruction.
+  static void constantIndexing4(int[] array) {
+    array[0] = 1;
   }
 
 
+  // CHECK-START: void Main.constantIndexing5(int[]) BCE (before)
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  // CHECK-START: void Main.constantIndexing5(int[]) BCE (after)
+  // CHECK-NOT: Deoptimize
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+  // CHECK: BoundsCheck
+  // CHECK: ArraySet
+
+  static void constantIndexing5(int[] array) {
+    // We don't apply the deoptimization for very large constant index
+    // since it's likely to be an anomaly and will throw AIOOBE.
+    array[Integer.MAX_VALUE - 1000] = 1;
+    array[Integer.MAX_VALUE - 999] = 1;
+    array[Integer.MAX_VALUE - 998] = 1;
+  }
+
   // CHECK-START: void Main.loopPattern1(int[]) BCE (before)
   // CHECK: BoundsCheck
   // CHECK: ArraySet
@@ -479,6 +597,21 @@ public class Main {
   }
 
 
+  static int foo() {
+    try {
+      // This will cause AIOOBE.
+      constantIndexing2(new int[3]);
+    } catch (ArrayIndexOutOfBoundsException e) {
+      return 99;
+    }
+    return 0;
+  }
+
+
+  // Make sure this method is compiled with optimizing.
+  // CHECK-START: void Main.main(java.lang.String[]) register (after)
+  // CHECK: ParallelMove
+
   public static void main(String[] args) {
     sieve(20);
 
@@ -507,5 +640,10 @@ public class Main {
     if (!isPyramid(array)) {
       System.out.println("pyramid3 failed!");
     }
+
+    // Make sure this value is kept after deoptimization.
+    int i = 1;
+    System.out.println(foo() + i);
   }
+
 }