1 /* 2 * Copyright (C) 2015 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 static class Dummy { getValue()19 static int getValue() { 20 return 1; 21 } 22 } 23 24 /// CHECK-START: int Main.div() licm (before) 25 /// CHECK-DAG: Div loop:{{B\d+}} 26 27 /// CHECK-START: int Main.div() licm (after) 28 /// CHECK-NOT: Div loop:{{B\d+}} 29 30 /// CHECK-START: int Main.div() licm (after) 31 /// CHECK-DAG: Div loop:none 32 div()33 public static int div() { 34 int result = 0; 35 for (int i = 0; i < 10; ++i) { 36 result += staticField / 42; 37 } 38 return result; 39 } 40 41 /// CHECK-START: int Main.innerDiv() licm (before) 42 /// CHECK-DAG: Div loop:{{B\d+}} 43 44 /// CHECK-START: int Main.innerDiv() licm (after) 45 /// CHECK-NOT: Div loop:{{B\d+}} 46 47 /// CHECK-START: int Main.innerDiv() licm (after) 48 /// CHECK-DAG: Div loop:none 49 innerDiv()50 public static int innerDiv() { 51 int result = 0; 52 for (int i = 0; i < 10; ++i) { 53 for (int j = 0; j < 10; ++j) { 54 result += staticField / 42; 55 } 56 } 57 return result; 58 } 59 60 /// CHECK-START: int Main.innerMul() licm (before) 61 /// CHECK-DAG: Mul loop:B4 62 63 /// CHECK-START: int Main.innerMul() licm (after) 64 /// CHECK-DAG: Mul loop:B2 65 innerMul()66 public static int innerMul() { 67 int result = 0; 68 for (int i = 0; i < 10; ++i) { 69 for (int j = 0; j < 10; ++j) { 70 // The operation has been hoisted out of the inner loop. 71 // Note that we depend on the compiler's block numbering to 72 // check if it has been moved. 73 result += staticField * i; 74 } 75 } 76 return result; 77 } 78 79 /// CHECK-START: int Main.divByA(int, int) licm (before) 80 /// CHECK-DAG: Div loop:{{B\d+}} 81 82 /// CHECK-START: int Main.divByA(int, int) licm (after) 83 /// CHECK-DAG: Div loop:{{B\d+}} 84 divByA(int a, int b)85 public static int divByA(int a, int b) { 86 int result = 0; 87 while (b < 5) { 88 // a might be null, so we can't hoist the operation. 89 result += staticField / a; 90 b++; 91 } 92 return result; 93 } 94 95 /// CHECK-START: int Main.arrayLength(int[]) licm (before) 96 /// CHECK-DAG: <<NullCheck:l\d+>> NullCheck loop:{{B\d+}} 97 /// CHECK-DAG: ArrayLength [<<NullCheck>>] loop:{{B\d+}} 98 99 /// CHECK-START: int Main.arrayLength(int[]) licm (after) 100 /// CHECK-NOT: NullCheck loop:{{B\d+}} 101 /// CHECK-NOT: ArrayLength loop:{{B\d+}} 102 103 /// CHECK-START: int Main.arrayLength(int[]) licm (after) 104 /// CHECK-DAG: <<NullCheck:l\d+>> NullCheck loop:none 105 /// CHECK-DAG: ArrayLength [<<NullCheck>>] loop:none 106 arrayLength(int[] array)107 public static int arrayLength(int[] array) { 108 int result = 0; 109 for (int i = 0; i < array.length; ++i) { 110 result += array[i]; 111 } 112 return result; 113 } 114 115 /// CHECK-START: int Main.clinitCheck() licm (before) 116 /// CHECK-DAG: <<LoadClass:l\d+>> LoadClass loop:<<Loop:B\d+>> 117 /// CHECK-DAG: ClinitCheck [<<LoadClass>>] loop:<<Loop>> 118 119 /// CHECK-START: int Main.clinitCheck() licm (after) 120 /// CHECK-NOT: LoadClass loop:{{B\d+}} 121 /// CHECK-NOT: ClinitCheck loop:{{B\d+}} 122 123 /// CHECK-START: int Main.clinitCheck() licm (after) 124 /// CHECK-DAG: <<LoadClass:l\d+>> LoadClass loop:none 125 /// CHECK-DAG: ClinitCheck [<<LoadClass>>] loop:none 126 clinitCheck()127 public static int clinitCheck() { 128 int i = 0; 129 int sum = 0; 130 do { 131 sum += Dummy.getValue(); 132 i++; 133 } while (i < 10); 134 return sum; 135 } 136 137 /// CHECK-START: int Main.divAndIntrinsic(int[]) licm (before) 138 /// CHECK-DAG: Div loop:{{B\d+}} 139 140 /// CHECK-START: int Main.divAndIntrinsic(int[]) licm (after) 141 /// CHECK-NOT: Div loop:{{B\d+}} 142 143 /// CHECK-START: int Main.divAndIntrinsic(int[]) licm (after) 144 /// CHECK-DAG: Div loop:none 145 divAndIntrinsic(int[] array)146 public static int divAndIntrinsic(int[] array) { 147 int result = 0; 148 for (int i = 0; i < array.length; i++) { 149 // An intrinsic call, unlike a general method call, cannot modify the field value. 150 // As a result, the invariant division on the field can be moved out of the loop. 151 result += (staticField / 42) + Math.abs(array[i]); 152 } 153 return result; 154 } 155 156 /// CHECK-START: int Main.invariantBoundIntrinsic(int) instruction_simplifier (before) 157 /// CHECK-DAG: InvokeStaticOrDirect loop:{{B\d+}} 158 // 159 /// CHECK-START: int Main.invariantBoundIntrinsic(int) licm (before) 160 /// CHECK-DAG: Abs loop:{{B\d+}} 161 162 /// CHECK-START: int Main.invariantBoundIntrinsic(int) licm (after) 163 /// CHECK-NOT: Abs loop:{{B\d+}} 164 165 /// CHECK-START: int Main.invariantBoundIntrinsic(int) licm (after) 166 /// CHECK-DAG: Abs loop:none 167 invariantBoundIntrinsic(int x)168 public static int invariantBoundIntrinsic(int x) { 169 int result = 0; 170 // The intrinsic call to abs used as loop bound is invariant. 171 // As a result, the call itself can be moved out of the loop header. 172 for (int i = 0; i < Math.abs(x); i++) { 173 result += i; 174 } 175 return result; 176 } 177 178 /// CHECK-START: int Main.invariantBodyIntrinsic(int, int) instruction_simplifier (before) 179 /// CHECK-DAG: InvokeStaticOrDirect loop:{{B\d+}} 180 181 /// CHECK-START: int Main.invariantBodyIntrinsic(int, int) licm (before) 182 /// CHECK-DAG: Max loop:{{B\d+}} 183 184 /// CHECK-START: int Main.invariantBodyIntrinsic(int, int) licm (after) 185 /// CHECK-NOT: Max loop:{{B\d+}} 186 187 /// CHECK-START: int Main.invariantBodyIntrinsic(int, int) licm (after) 188 /// CHECK-DAG: Max loop:none 189 invariantBodyIntrinsic(int x, int y)190 public static int invariantBodyIntrinsic(int x, int y) { 191 int result = 0; 192 for (int i = 0; i < 10; i++) { 193 // The intrinsic call to max used inside the loop is invariant. 194 // As a result, the call itself can be moved out of the loop body. 195 result += Math.max(x, y); 196 } 197 return result; 198 } 199 200 // 201 // All operations up to the null check can be hoisted out of the 202 // loop. The null check itself sees the induction in its environment. 203 // 204 /// CHECK-START: int Main.doWhile(int) licm (before) 205 /// CHECK-DAG: <<Add:i\d+>> Add loop:<<Loop:B\d+>> outer_loop:none 206 /// CHECK-DAG: LoadClass loop:<<Loop>> outer_loop:none 207 /// CHECK-DAG: <<Get:l\d+>> StaticFieldGet loop:<<Loop>> outer_loop:none 208 /// CHECK-DAG: NullCheck [<<Get>>] env:[[<<Add>>,<<Get>>,{{i\d+}}]] loop:<<Loop>> outer_loop:none 209 /// CHECK-DAG: ArrayLength loop:<<Loop>> outer_loop:none 210 /// CHECK-DAG: BoundsCheck loop:<<Loop>> outer_loop:none 211 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none 212 // 213 /// CHECK-START: int Main.doWhile(int) licm (after) 214 /// CHECK-NOT: LoadClass loop:{{B\d+}} 215 /// CHECK-NOT: StaticFieldGet loop:{{B\d+}} 216 // 217 /// CHECK-START: int Main.doWhile(int) licm (after) 218 /// CHECK-DAG: LoadClass loop:none 219 /// CHECK-DAG: <<Get:l\d+>> StaticFieldGet loop:none 220 /// CHECK-DAG: <<Add:i\d+>> Add loop:<<Loop:B\d+>> outer_loop:none 221 /// CHECK-DAG: NullCheck [<<Get>>] env:[[<<Add>>,<<Get>>,{{i\d+}}]] loop:<<Loop>> outer_loop:none 222 /// CHECK-DAG: ArrayLength loop:<<Loop>> outer_loop:none 223 /// CHECK-DAG: BoundsCheck loop:<<Loop>> outer_loop:none 224 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none doWhile(int k)225 public static int doWhile(int k) { 226 int i = k; 227 do { 228 i += 2; 229 } while (staticArray[i] == 0); 230 return i; 231 } 232 233 public static int staticField = 42; 234 235 public static int[] staticArray = null; 236 assertEquals(int expected, int actual)237 public static void assertEquals(int expected, int actual) { 238 if (expected != actual) { 239 throw new Error("Expected " + expected + ", got " + actual); 240 } 241 } 242 main(String[] args)243 public static void main(String[] args) { 244 assertEquals(10, div()); 245 assertEquals(100, innerDiv()); 246 assertEquals(18900, innerMul()); 247 assertEquals(105, divByA(2, 0)); 248 assertEquals(12, arrayLength(new int[] { 4, 8 })); 249 assertEquals(10, clinitCheck()); 250 assertEquals(21, divAndIntrinsic(new int[] { 4, -2, 8, -3 })); 251 assertEquals(45, invariantBoundIntrinsic(-10)); 252 assertEquals(30, invariantBodyIntrinsic(2, 3)); 253 254 staticArray = null; 255 try { 256 doWhile(0); 257 throw new Error("Expected NPE"); 258 } catch (NullPointerException e) { 259 } 260 staticArray = new int[5]; 261 staticArray[4] = 1; 262 assertEquals(4, doWhile(-2)); 263 assertEquals(4, doWhile(0)); 264 assertEquals(4, doWhile(2)); 265 try { 266 doWhile(1); 267 throw new Error("Expected IOOBE"); 268 } catch (IndexOutOfBoundsException e) { 269 } 270 271 System.out.println("passed"); 272 } 273 } 274