1 /* 2 * Copyright (C) 2016 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 public class Main { 18 19 /** 20 * Method with an outer countable loop and an inner do-while loop. 21 * Since all work is done in the header of the inner loop, any invariant hoisting 22 * and deopting should be done in its proper loop preheader, not the true-block 23 * of the newly generated taken-test after dynamic BCE. 24 */ doit(int[][] x, int j)25 public static int doit(int[][] x, int j) { 26 float f = 0; 27 int acc = 0; 28 for (int i = 0; i < 2; i++) { 29 // The full body of a do-while loop is the loop header. 30 do { 31 // Some "noise" to avoid hoisting the array reference 32 // before the dynamic BCE phase runs. 33 f++; 34 // The invariant array reference with corresponding bounds check 35 // is a candidate for hoisting when dynamic BCE runs. If it is 36 // not moved to the proper loop preheader, the wrong values 37 // cause the test to fail. 38 acc += x[i][i]; 39 } while (++j < i); 40 } 41 return acc; 42 } 43 44 /** 45 * Single countable loop with a clear header and a loop body. In this case, 46 * after dynamic bce, some invariant hoisting and deopting must go to the 47 * proper loop preheader and some must go to the true-block. 48 */ foo(int[] x, int[] y, int n)49 public static int foo(int[] x, int[] y, int n) { 50 float f = 0; 51 int acc = 0; 52 int i = 0; 53 while (true) { 54 // This part is the loop header. 55 // Some "noise" to avoid hoisting the array reference 56 // before the dynamic BCE phase runs. 57 f++; 58 // The invariant array reference with corresponding bounds check 59 // is a candidate for hoisting when dynamic BCE runs. If it is 60 // not moved to the proper loop preheader, the wrong values 61 // cause the test to fail. 62 acc += y[0]; 63 if (++i > n) 64 break; 65 // From here on, this part is the loop body. 66 // The unit-stride array reference is a candidate for dynamic BCE. 67 // The deopting appears in the true-block. 68 acc += x[i]; 69 } 70 return acc; 71 } 72 73 /** 74 * An artificial example with an inconsistent phi structure during 75 * dynamic bce that is corrected afterwards. Note that only the last 76 * assignment is really live, but the other statements set up an 77 * interesting phi structure. 78 */ doit(int[] z)79 private static int doit(int[] z) { 80 int a = 0; 81 for (int i = 0; i < 10; ++i) { 82 for (int j = i; j < 10; ++j) { 83 a = z[i]; 84 for (int k = 0; k < 10; ++k) { 85 a += z[k]; 86 a = z[i]; 87 } 88 } 89 } 90 return a; 91 } 92 93 /** 94 * Example shows that we can hoist ArrayGet to pre-header only if 95 * its execution is guaranteed. 96 */ hoistcheck(int[] c)97 public static int hoistcheck(int[] c) { 98 int i = 0, i2 = 0, i3 = 0, k = 0; 99 int n = c.length; 100 for (i = -100000000; i < 20; i += 10000000) { 101 i3 = i; 102 i2 = 0; 103 while (i2++ < 1) { 104 if (i3 >= 0 && i3 < n) { 105 k += c[i3]; 106 } 107 } 108 } 109 return k; 110 } 111 main(String args[])112 public static void main(String args[]) { 113 int[][] x = new int[2][2]; 114 int y; 115 116 x[0][0] = 1; 117 x[1][1] = 2; 118 119 expectEquals(8, doit(x, -6)); 120 expectEquals(7, doit(x, -5)); 121 expectEquals(6, doit(x, -4)); 122 expectEquals(5, doit(x, -3)); 123 expectEquals(4, doit(x, -2)); 124 expectEquals(3, doit(x, -1)); 125 expectEquals(3, doit(x, 0)); 126 expectEquals(3, doit(x, 1)); 127 expectEquals(3, doit(x, 22)); 128 129 int a[] = { 1, 2, 3, 5 }; 130 int b[] = { 7 }; 131 132 expectEquals(7, foo(a, b, -1)); 133 expectEquals(7, foo(a, b, 0)); 134 expectEquals(16, foo(a, b, 1)); 135 expectEquals(26, foo(a, b, 2)); 136 expectEquals(38, foo(a, b, 3)); 137 138 int[] z = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 139 expectEquals(10, doit(z)); 140 141 int c[] = { 1, 2, 3, 5 }; 142 expectEquals(1, hoistcheck(c)); 143 144 System.out.println("passed"); 145 } 146 expectEquals(int expected, int result)147 private static void expectEquals(int expected, int result) { 148 if (expected != result) { 149 throw new Error("Expected: " + expected + ", found: " + result); 150 } 151 } 152 } 153