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 // 18 // Test on loop optimizations, in particular dynamic BCE. In all cases, 19 // bounds check on a[] is resolved statically. Bounds checks on b[] 20 // exercise various different scenarios. In all cases, loop-based 21 // dynamic BCE is better than the dominator-based BCE, since it 22 // generates the test outside the loop. 23 // 24 public class Main { 25 26 /// CHECK-START: void Main.oneConstantIndex(int[], int[]) BCE (before) 27 /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>> 28 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 29 // 30 /// CHECK-START: void Main.oneConstantIndex(int[], int[]) BCE (after) 31 /// CHECK-DAG: Deoptimize loop:none 32 /// CHECK-DAG: Deoptimize loop:none 33 /// CHECK-NOT: Deoptimize 34 // 35 /// CHECK-START: void Main.oneConstantIndex(int[], int[]) BCE (after) 36 /// CHECK-NOT: BoundsCheck 37 public static void oneConstantIndex(int[] a, int[] b) { 38 // Dynamic bce on b requires two deopts: one null and one bound. 39 for (int i = 0; i < a.length; i++) { 40 a[i] = b[1]; 41 } 42 } 43 44 /// CHECK-START: void Main.multipleConstantIndices(int[], int[]) BCE (before) 45 /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>> 46 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 47 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 48 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 49 // 50 /// CHECK-START: void Main.multipleConstantIndices(int[], int[]) BCE (after) 51 /// CHECK-DAG: Deoptimize loop:none 52 /// CHECK-DAG: Deoptimize loop:none 53 /// CHECK-NOT: Deoptimize 54 // 55 /// CHECK-START: void Main.multipleConstantIndices(int[], int[]) BCE (after) 56 /// CHECK-NOT: BoundsCheck 57 public static void multipleConstantIndices(int[] a, int[] b) { 58 // Dynamic bce on b requires two deopts: one null and one bound. 59 for (int i = 0; i < a.length; i++) { 60 a[i] = b[0] + b[1] + b[2]; 61 } 62 } 63 64 /// CHECK-START: void Main.oneInvariantIndex(int[], int[], int) BCE (before) 65 /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>> 66 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 67 // 68 /// CHECK-START: void Main.oneInvariantIndex(int[], int[], int) BCE (after) 69 /// CHECK-DAG: Deoptimize loop:none 70 /// CHECK-DAG: Deoptimize loop:none 71 /// CHECK-NOT: Deoptimize 72 // 73 /// CHECK-START: void Main.oneInvariantIndex(int[], int[], int) BCE (after) 74 /// CHECK-NOT: BoundsCheck 75 public static void oneInvariantIndex(int[] a, int[] b, int c) { 76 // Dynamic bce on b requires two deopts: one null and one bound. 77 for (int i = 0; i < a.length; i++) { 78 a[i] = b[c]; 79 } 80 } 81 82 /// CHECK-START: void Main.multipleInvariantIndices(int[], int[], int) BCE (before) 83 /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>> 84 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 85 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 86 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 87 // 88 /// CHECK-START: void Main.multipleInvariantIndices(int[], int[], int) BCE (after) 89 /// CHECK-DAG: Deoptimize loop:none 90 /// CHECK-DAG: Deoptimize loop:none 91 /// CHECK-DAG: Deoptimize loop:none 92 /// CHECK-NOT: Deoptimize 93 // 94 /// CHECK-START: void Main.multipleInvariantIndices(int[], int[], int) BCE (after) 95 /// CHECK-NOT: BoundsCheck 96 public static void multipleInvariantIndices(int[] a, int[] b, int c) { 97 // Dynamic bce on b requires three deopts: one null and two bounds. 98 for (int i = 0; i < a.length; i++) { 99 a[i] = b[c-1] + b[c] + b[c+1]; 100 } 101 } 102 103 /// CHECK-START: void Main.oneUnitStride(int[], int[]) BCE (before) 104 /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>> 105 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 106 // 107 /// CHECK-START: void Main.oneUnitStride(int[], int[]) BCE (after) 108 /// CHECK-DAG: Deoptimize loop:none 109 /// CHECK-DAG: Deoptimize loop:none 110 /// CHECK-DAG: Deoptimize loop:none 111 /// CHECK-NOT: Deoptimize 112 // 113 /// CHECK-START: void Main.oneUnitStride(int[], int[]) BCE (after) 114 /// CHECK-NOT: BoundsCheck 115 public static void oneUnitStride(int[] a, int[] b) { 116 // Dynamic bce on b requires three deopts: one null and two bounds. 117 for (int i = 0; i < a.length; i++) { 118 a[i] = b[i]; 119 } 120 } 121 122 /// CHECK-START: void Main.multipleUnitStrides(int[], int[]) BCE (before) 123 /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>> 124 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 125 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 126 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 127 // 128 /// CHECK-START: void Main.multipleUnitStrides(int[], int[]) BCE (after) 129 /// CHECK-DAG: Deoptimize loop:none 130 /// CHECK-DAG: Deoptimize loop:none 131 /// CHECK-DAG: Deoptimize loop:none 132 /// CHECK-DAG: Deoptimize loop:none 133 /// CHECK-NOT: Deoptimize 134 // 135 /// CHECK-START: void Main.multipleUnitStrides(int[], int[]) instruction_simplifier$after_bce (after) 136 /// CHECK-DAG: Deoptimize loop:none 137 /// CHECK-DAG: Deoptimize loop:none 138 /// CHECK-DAG: Deoptimize loop:none 139 /// CHECK-NOT: Deoptimize 140 // 141 /// CHECK-START: void Main.multipleUnitStrides(int[], int[]) BCE (after) 142 /// CHECK-NOT: BoundsCheck 143 public static void multipleUnitStrides(int[] a, int[] b) { 144 // Dynamic bce on b requires four deopts: one null and three bounds. 145 // One redundant deopt is removed by simplifier. 146 // TODO: range information could remove another 147 for (int i = 1; i < a.length - 1; i++) { 148 a[i] = b[i-1] + b[i] + b[i+1]; 149 } 150 } 151 152 /// CHECK-START: void Main.multipleUnitStridesConditional(int[], int[]) BCE (before) 153 /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>> 154 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 155 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 156 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 157 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 158 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 159 // 160 /// CHECK-START: void Main.multipleUnitStridesConditional(int[], int[]) BCE (after) 161 /// CHECK-DAG: Deoptimize loop:none 162 /// CHECK-DAG: Deoptimize loop:none 163 /// CHECK-DAG: Deoptimize loop:none 164 /// CHECK-DAG: Deoptimize loop:none 165 /// CHECK-NOT: Deoptimize 166 // 167 /// CHECK-START: void Main.multipleUnitStridesConditional(int[], int[]) instruction_simplifier$after_bce (after) 168 /// CHECK-DAG: Deoptimize loop:none 169 /// CHECK-DAG: Deoptimize loop:none 170 /// CHECK-DAG: Deoptimize loop:none 171 /// CHECK-NOT: Deoptimize 172 // 173 /// CHECK-START: void Main.multipleUnitStridesConditional(int[], int[]) BCE (after) 174 /// CHECK-NOT: BoundsCheck 175 public static void multipleUnitStridesConditional(int[] a, int[] b) { 176 // Dynamic bce on b requires four deopts: one null and three bounds. 177 // The two conditional references may be included, since they are in range. 178 // One redundant deopt is removed by simplifier. 179 for (int i = 2; i < a.length - 2; i++) { 180 int t = b[i-2] + b[i] + b[i+2] + (((i & 1) == 0) ? b[i+1] : b[i-1]); 181 a[i] = t; 182 } 183 } 184 185 /// CHECK-START: void Main.shifter(int[]) BCE (before) 186 /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>> 187 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 188 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 189 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 190 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 191 // 192 /// CHECK-START: void Main.shifter(int[]) BCE (after) 193 /// CHECK-DAG: Deoptimize loop:none 194 /// CHECK-DAG: Deoptimize loop:none 195 /// CHECK-DAG: Deoptimize loop:none 196 /// CHECK-DAG: Deoptimize loop:none 197 /// CHECK-NOT: Deoptimize 198 // 199 /// CHECK-START: void Main.shifter(int[]) instruction_simplifier$after_bce (after) 200 /// CHECK-DAG: Deoptimize loop:none 201 /// CHECK-DAG: Deoptimize loop:none 202 /// CHECK-NOT: Deoptimize 203 // 204 /// CHECK-START: void Main.shifter(int[]) BCE (after) 205 /// CHECK-NOT: BoundsCheck 206 public static void shifter(int[] x) { 207 // Real-life example: should have four deopts: one null and three bounds. 208 // Two redundant deopts are removed by simplifier. 209 for (int i = 16; i < 80; i++) { 210 int t = x[i - 3] ^ x[i - 8] ^ x[i - 14] ^ x[i - 16]; 211 x[i] = t << 1 | t >>> 31; 212 } 213 } 214 215 /// CHECK-START: void Main.stencil(int[], int, int) BCE (before) 216 /// CHECK-DAG: BoundsCheck loop:<<Loop:B\d+>> 217 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 218 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 219 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 220 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 221 // 222 /// CHECK-START: void Main.stencil(int[], int, int) BCE (after) 223 /// CHECK-DAG: Deoptimize loop:none 224 /// CHECK-DAG: Deoptimize loop:none 225 /// CHECK-DAG: Deoptimize loop:none 226 /// CHECK-DAG: Deoptimize loop:none 227 /// CHECK-NOT: Deoptimize 228 // 229 /// CHECK-START: void Main.stencil(int[], int, int) BCE (after) 230 /// CHECK-NOT: BoundsCheck 231 public static void stencil(int[] array, int start, int end) { 232 // Real-life example: should have four deopts: one null and three bounds. 233 for (int i = end; i >= start; i--) { 234 array[i] = (array[i-2] + array[i-1] + array[i] + array[i+1] + array[i+2]) / 5; 235 } 236 } 237 238 /// CHECK-START: void Main.shortBound1(int[], short) BCE (before) 239 /// CHECK-DAG: BoundsCheck loop:{{B\d+}} 240 // 241 /// CHECK-START: void Main.shortBound1(int[], short) BCE (after) 242 /// CHECK-DAG: Deoptimize loop:none 243 /// CHECK-DAG: Deoptimize loop:none 244 /// CHECK-DAG: Deoptimize loop:none 245 /// CHECK-NOT: Deoptimize 246 // 247 /// CHECK-START: void Main.shortBound1(int[], short) BCE (after) 248 /// CHECK-NOT: BoundsCheck 249 public static void shortBound1(int[] array, short s) { 250 // Lower precision bound will appear in deopt arithmetic 251 // and follows normal implicit widening conversion. 252 for (int i = 0; i < s; i++) { 253 array[i] = 222; 254 } 255 } 256 257 /// CHECK-START: void Main.shortBound2(int[], short) BCE (before) 258 /// CHECK-DAG: BoundsCheck loop:{{B\d+}} 259 // 260 /// CHECK-START: void Main.shortBound2(int[], short) BCE (after) 261 /// CHECK-DAG: Deoptimize loop:none 262 /// CHECK-DAG: Deoptimize loop:none 263 /// CHECK-DAG: Deoptimize loop:none 264 /// CHECK-NOT: Deoptimize 265 // 266 /// CHECK-START: void Main.shortBound2(int[], short) BCE (after) 267 /// CHECK-NOT: BoundsCheck 268 public static void shortBound2(int[] array, short s) { 269 // Lower precision bound will appear in deopt arithmetic 270 // and follows normal implicit widening conversion. 271 for (int i = 0; s > i; i++) { 272 array[i] = 444; 273 } 274 } 275 276 /// CHECK-START: void Main.narrowingFromLong(int[], int) BCE (before) 277 /// CHECK-DAG: BoundsCheck loop:{{B\d+}} 278 // 279 /// CHECK-START: void Main.narrowingFromLong(int[], int) BCE (after) 280 /// CHECK-DAG: BoundsCheck loop:{{B\d+}} 281 public static void narrowingFromLong(int[] array, int n) { 282 // Parallel induction in long precision that is narrowed provides type 283 // conversion challenges for BCE in deopt arithmetic when combined 284 // with the int loop induction. Therefore, currently skipped. 285 long l = 0; 286 for (int i = 0; i < n; i++, l++) { 287 array[(int)l] = 888; 288 } 289 } 290 291 // 292 // Verifier. 293 // 294 295 public static void main(String[] args) { 296 int[] a = new int[10]; 297 int b[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 298 int b1[] = { 100 }; 299 300 oneConstantIndex(a, b); 301 for (int i = 0; i < a.length; i++) { 302 expectEquals(2, a[i]); 303 } 304 try { 305 oneConstantIndex(a, b1); 306 throw new Error("Should throw AIOOBE"); 307 } catch (ArrayIndexOutOfBoundsException e) { 308 } 309 310 multipleConstantIndices(a, b); 311 for (int i = 0; i < a.length; i++) { 312 expectEquals(6, a[i]); 313 } 314 try { 315 multipleConstantIndices(a, b1); 316 throw new Error("Should throw AIOOBE"); 317 } catch (ArrayIndexOutOfBoundsException e) { 318 } 319 320 oneInvariantIndex(a, b, 1); 321 for (int i = 0; i < a.length; i++) { 322 expectEquals(2, a[i]); 323 } 324 try { 325 oneInvariantIndex(a, b1, 1); 326 throw new Error("Should throw AIOOBE"); 327 } catch (ArrayIndexOutOfBoundsException e) { 328 } 329 330 multipleInvariantIndices(a, b, 1); 331 for (int i = 0; i < a.length; i++) { 332 expectEquals(6, a[i]); 333 } 334 try { 335 multipleInvariantIndices(a, b1, 1); 336 throw new Error("Should throw AIOOBE"); 337 } catch (ArrayIndexOutOfBoundsException e) { 338 } 339 340 oneUnitStride(a, b); 341 for (int i = 0; i < a.length; i++) { 342 expectEquals(i + 1, a[i]); 343 } 344 try { 345 oneUnitStride(a, b1); 346 throw new Error("Should throw AIOOBE"); 347 } catch (ArrayIndexOutOfBoundsException e) { 348 expectEquals(100, a[0]); 349 } 350 351 multipleUnitStrides(a, b); 352 for (int i = 1; i < a.length - 1; i++) { 353 expectEquals(3 * i + 3, a[i]); 354 } 355 try { 356 multipleUnitStrides(a, b1); 357 throw new Error("Should throw AIOOBE"); 358 } catch (ArrayIndexOutOfBoundsException e) { 359 } 360 361 multipleUnitStridesConditional(a, b); 362 for (int i = 2; i < a.length - 2; i++) { 363 int e = 3 * i + 3 + (((i & 1) == 0) ? i + 2 : i); 364 expectEquals(e, a[i]); 365 } 366 try { 367 multipleUnitStridesConditional(a, b1); 368 throw new Error("Should throw AIOOBE"); 369 } catch (ArrayIndexOutOfBoundsException e) { 370 } 371 372 shortBound1(a, (short)a.length); 373 for (int i = 0; i < a.length; i++) { 374 expectEquals(222, a[i]); 375 } 376 shortBound2(a, (short)a.length); 377 for (int i = 0; i < a.length; i++) { 378 expectEquals(444, a[i]); 379 } 380 381 try { 382 shortBound1(a, (short)(a.length + 1)); 383 throw new Error("Should throw AIOOBE"); 384 } catch (ArrayIndexOutOfBoundsException e) { 385 } 386 for (int i = 0; i < a.length; i++) { 387 expectEquals(222, a[i]); 388 } 389 390 try { 391 shortBound2(a, (short)(a.length + 1)); 392 throw new Error("Should throw AIOOBE"); 393 } catch (ArrayIndexOutOfBoundsException e) { 394 } 395 for (int i = 0; i < a.length; i++) { 396 expectEquals(444, a[i]); 397 } 398 399 narrowingFromLong(a, a.length); 400 for (int i = 0; i < a.length; i++) { 401 expectEquals(888, a[i]); 402 } 403 404 System.out.println("passed"); 405 } 406 407 private static void expectEquals(int expected, int result) { 408 if (expected != result) { 409 throw new Error("Expected: " + expected + ", found: " + result); 410 } 411 } 412 } 413
