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 // 18 // Test on loop optimizations. 19 // 20 public class Main { 21 22 static int sResult; 23 24 // 25 // Various sequence variables used in bound checks. 26 // 27 28 /// CHECK-START: void Main.bubble(int[]) BCE (before) 29 /// CHECK-DAG: BoundsCheck 30 /// CHECK-DAG: BoundsCheck 31 // 32 /// CHECK-START: void Main.bubble(int[]) BCE (after) 33 /// CHECK-NOT: BoundsCheck 34 // TODO: also CHECK-NOT: Deoptimize, see b/27151190 bubble(int[] a)35 private static void bubble(int[] a) { 36 for (int i = a.length; --i >= 0;) { 37 for (int j = 0; j < i; j++) { 38 if (a[j] > a[j+1]) { 39 int tmp = a[j]; 40 a[j] = a[j+1]; 41 a[j+1] = tmp; 42 } 43 } 44 } 45 } 46 47 /// CHECK-START: int Main.periodicIdiom(int) BCE (before) 48 /// CHECK-DAG: BoundsCheck 49 // 50 /// CHECK-START: int Main.periodicIdiom(int) BCE (after) 51 /// CHECK-NOT: BoundsCheck 52 /// CHECK-NOT: Deoptimize periodicIdiom(int tc)53 private static int periodicIdiom(int tc) { 54 int[] x = { 1, 3 }; 55 // Loop with periodic sequence (0, 1). 56 int k = 0; 57 int result = 0; 58 for (int i = 0; i < tc; i++) { 59 result += x[k]; 60 k = 1 - k; 61 } 62 return result; 63 } 64 65 /// CHECK-START: int Main.periodicSequence2(int) BCE (before) 66 /// CHECK-DAG: BoundsCheck 67 // 68 /// CHECK-START: int Main.periodicSequence2(int) BCE (after) 69 /// CHECK-NOT: BoundsCheck 70 /// CHECK-NOT: Deoptimize periodicSequence2(int tc)71 private static int periodicSequence2(int tc) { 72 int[] x = { 1, 3 }; 73 // Loop with periodic sequence (0, 1). 74 int k = 0; 75 int l = 1; 76 int result = 0; 77 for (int i = 0; i < tc; i++) { 78 result += x[k]; 79 int t = l; 80 l = k; 81 k = t; 82 } 83 return result; 84 } 85 86 /// CHECK-START: int Main.periodicSequence4(int) BCE (before) 87 /// CHECK-DAG: BoundsCheck 88 /// CHECK-DAG: BoundsCheck 89 /// CHECK-DAG: BoundsCheck 90 /// CHECK-DAG: BoundsCheck 91 // 92 /// CHECK-START: int Main.periodicSequence4(int) BCE (after) 93 /// CHECK-NOT: BoundsCheck 94 /// CHECK-NOT: Deoptimize periodicSequence4(int tc)95 private static int periodicSequence4(int tc) { 96 int[] x = { 1, 3, 5, 7 }; 97 // Loop with periodic sequence (0, 1, 2, 3). 98 int k = 0; 99 int l = 1; 100 int m = 2; 101 int n = 3; 102 int result = 0; 103 for (int i = 0; i < tc; i++) { 104 result += x[k] + x[l] + x[m] + x[n]; // all used at once 105 int t = n; 106 n = k; 107 k = l; 108 l = m; 109 m = t; 110 } 111 return result; 112 } 113 114 /// CHECK-START: int Main.justRightUp1() BCE (before) 115 /// CHECK-DAG: BoundsCheck 116 // 117 /// CHECK-START: int Main.justRightUp1() BCE (after) 118 /// CHECK-NOT: BoundsCheck 119 /// CHECK-NOT: Deoptimize justRightUp1()120 private static int justRightUp1() { 121 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 122 int result = 0; 123 for (int i = Integer.MAX_VALUE - 10, k = 0; i < Integer.MAX_VALUE; i++) { 124 result += x[k++]; 125 } 126 return result; 127 } 128 129 /// CHECK-START: int Main.justRightUp2() BCE (before) 130 /// CHECK-DAG: BoundsCheck 131 // 132 /// CHECK-START: int Main.justRightUp2() BCE (after) 133 /// CHECK-NOT: BoundsCheck 134 /// CHECK-NOT: Deoptimize justRightUp2()135 private static int justRightUp2() { 136 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 137 int result = 0; 138 for (int i = Integer.MAX_VALUE - 10; i < Integer.MAX_VALUE; i++) { 139 result += x[i - Integer.MAX_VALUE + 10]; 140 } 141 return result; 142 } 143 144 /// CHECK-START: int Main.justRightUp3() BCE (before) 145 /// CHECK-DAG: BoundsCheck 146 // 147 /// CHECK-START: int Main.justRightUp3() BCE (after) 148 /// CHECK-NOT: BoundsCheck 149 /// CHECK-NOT: Deoptimize justRightUp3()150 private static int justRightUp3() { 151 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 152 int result = 0; 153 for (int i = Integer.MAX_VALUE - 10, k = 0; i <= Integer.MAX_VALUE - 1; i++) { 154 result += x[k++]; 155 } 156 return result; 157 } 158 159 /// CHECK-START: int Main.justOOBUp() BCE (before) 160 /// CHECK-DAG: BoundsCheck 161 // 162 /// CHECK-START: int Main.justOOBUp() BCE (after) 163 /// CHECK-DAG: BoundsCheck 164 // 165 /// CHECK-START: int Main.justOOBUp() BCE (after) 166 /// CHECK-NOT: Deoptimize justOOBUp()167 private static int justOOBUp() { 168 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 169 int result = 0; 170 // Infinite loop! 171 for (int i = Integer.MAX_VALUE - 9, k = 0; i <= Integer.MAX_VALUE; i++) { 172 result += x[k++]; 173 } 174 return result; 175 } 176 177 /// CHECK-START: int Main.justRightDown1() BCE (before) 178 /// CHECK-DAG: BoundsCheck 179 // 180 /// CHECK-START: int Main.justRightDown1() BCE (after) 181 /// CHECK-NOT: BoundsCheck 182 /// CHECK-NOT: Deoptimize justRightDown1()183 private static int justRightDown1() { 184 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 185 int result = 0; 186 for (int i = Integer.MIN_VALUE + 10, k = 0; i > Integer.MIN_VALUE; i--) { 187 result += x[k++]; 188 } 189 return result; 190 } 191 192 /// CHECK-START: int Main.justRightDown2() BCE (before) 193 /// CHECK-DAG: BoundsCheck 194 // 195 /// CHECK-START: int Main.justRightDown2() BCE (after) 196 /// CHECK-NOT: BoundsCheck 197 /// CHECK-NOT: Deoptimize justRightDown2()198 private static int justRightDown2() { 199 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 200 int result = 0; 201 for (int i = Integer.MIN_VALUE + 10; i > Integer.MIN_VALUE; i--) { 202 result += x[Integer.MAX_VALUE + i]; 203 } 204 return result; 205 } 206 207 /// CHECK-START: int Main.justRightDown3() BCE (before) 208 /// CHECK-DAG: BoundsCheck 209 // 210 /// CHECK-START: int Main.justRightDown3() BCE (after) 211 /// CHECK-NOT: BoundsCheck 212 /// CHECK-NOT: Deoptimize justRightDown3()213 private static int justRightDown3() { 214 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 215 int result = 0; 216 for (int i = Integer.MIN_VALUE + 10, k = 0; i >= Integer.MIN_VALUE + 1; i--) { 217 result += x[k++]; 218 } 219 return result; 220 } 221 222 /// CHECK-START: int Main.justOOBDown() BCE (before) 223 /// CHECK-DAG: BoundsCheck 224 // 225 /// CHECK-START: int Main.justOOBDown() BCE (after) 226 /// CHECK-DAG: BoundsCheck 227 // 228 /// CHECK-START: int Main.justOOBDown() BCE (after) 229 /// CHECK-NOT: Deoptimize justOOBDown()230 private static int justOOBDown() { 231 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 232 int result = 0; 233 // Infinite loop! 234 for (int i = Integer.MIN_VALUE + 9, k = 0; i >= Integer.MIN_VALUE; i--) { 235 result += x[k++]; 236 } 237 return result; 238 } 239 240 /// CHECK-START: void Main.lowerOOB(int[]) BCE (before) 241 /// CHECK-DAG: BoundsCheck 242 // 243 /// CHECK-START: void Main.lowerOOB(int[]) BCE (after) 244 /// CHECK-DAG: BoundsCheck 245 // 246 /// CHECK-START: void Main.lowerOOB(int[]) BCE (after) 247 /// CHECK-NOT: Deoptimize lowerOOB(int[] x)248 private static void lowerOOB(int[] x) { 249 // OOB! 250 for (int i = -1; i < x.length; i++) { 251 sResult += x[i]; 252 } 253 } 254 255 /// CHECK-START: void Main.upperOOB(int[]) BCE (before) 256 /// CHECK-DAG: BoundsCheck 257 // 258 /// CHECK-START: void Main.upperOOB(int[]) BCE (after) 259 /// CHECK-DAG: BoundsCheck 260 // 261 /// CHECK-START: void Main.upperOOB(int[]) BCE (after) 262 /// CHECK-NOT: Deoptimize upperOOB(int[] x)263 private static void upperOOB(int[] x) { 264 // OOB! 265 for (int i = 0; i <= x.length; i++) { 266 sResult += x[i]; 267 } 268 } 269 270 /// CHECK-START: void Main.doWhileUpOOB() BCE (before) 271 /// CHECK-DAG: BoundsCheck 272 // 273 /// CHECK-START: void Main.doWhileUpOOB() BCE (after) 274 /// CHECK-DAG: BoundsCheck 275 // 276 /// CHECK-START: void Main.doWhileUpOOB() BCE (after) 277 /// CHECK-NOT: Deoptimize doWhileUpOOB()278 private static void doWhileUpOOB() { 279 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 280 int i = 0; 281 // OOB! 282 do { 283 sResult += x[i++]; 284 } while (i <= x.length); 285 } 286 287 /// CHECK-START: void Main.doWhileDownOOB() BCE (before) 288 /// CHECK-DAG: BoundsCheck 289 // 290 /// CHECK-START: void Main.doWhileDownOOB() BCE (after) 291 /// CHECK-DAG: BoundsCheck 292 // 293 /// CHECK-START: void Main.doWhileDownOOB() BCE (after) 294 /// CHECK-NOT: Deoptimize doWhileDownOOB()295 private static void doWhileDownOOB() { 296 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 297 int i = x.length - 1; 298 // OOB! 299 do { 300 sResult += x[i--]; 301 } while (-1 <= i); 302 } 303 304 /// CHECK-START: void Main.hiddenOOB1(int) BCE (before) 305 /// CHECK-DAG: BoundsCheck 306 // 307 /// CHECK-START: void Main.hiddenOOB1(int) BCE (after) 308 /// CHECK-DAG: Deoptimize 309 // 310 /// CHECK-START: void Main.hiddenOOB1(int) BCE (after) 311 /// CHECK-NOT: BoundsCheck hiddenOOB1(int lo)312 private static void hiddenOOB1(int lo) { 313 int[] a = { 1 } ; 314 for (int i = lo; i <= 10; i++) { 315 // Dangerous loop where careless static range analysis would yield strict upper bound 316 // on index j of 5. When, for instance, lo and thus i = -2147483648, the upper bound 317 // becomes really positive due to arithmetic wrap-around, causing OOB. 318 // Dynamic BCE is feasible though, since it checks the range. 319 for (int j = 4; j < i - 5; j++) { 320 sResult += a[j - 4]; 321 } 322 } 323 } 324 325 /// CHECK-START: void Main.hiddenOOB2(int) BCE (before) 326 /// CHECK-DAG: BoundsCheck 327 // 328 /// CHECK-START: void Main.hiddenOOB2(int) BCE (after) 329 /// CHECK-DAG: Deoptimize 330 // 331 /// CHECK-START: void Main.hiddenOOB2(int) BCE (after) 332 /// CHECK-NOT: BoundsCheck hiddenOOB2(int hi)333 private static void hiddenOOB2(int hi) { 334 int[] a = { 1 } ; 335 for (int i = 0; i < hi; i++) { 336 // Dangerous loop where careless static range analysis would yield strict lower bound 337 // on index j of 5. When, for instance, hi and thus i = 2147483647, the upper bound 338 // becomes really negative due to arithmetic wrap-around, causing OOB. 339 // Dynamic BCE is feasible though, since it checks the range. 340 for (int j = 6; j > i + 5; j--) { 341 sResult += a[j - 6]; 342 } 343 } 344 } 345 346 /// CHECK-START: void Main.hiddenInfiniteOOB() BCE (before) 347 /// CHECK-DAG: BoundsCheck 348 // 349 /// CHECK-START: void Main.hiddenInfiniteOOB() BCE (after) 350 /// CHECK-DAG: BoundsCheck 351 // 352 /// CHECK-START: void Main.hiddenInfiniteOOB() BCE (after) 353 /// CHECK-NOT: Deoptimize hiddenInfiniteOOB()354 private static void hiddenInfiniteOOB() { 355 int[] a = { 11 } ; 356 for (int i = -1; i <= 0; i++) { 357 // Dangerous loop where careless static range analysis would yield a safe upper bound 358 // of -3. In reality, due to arithmetic wrap-around (when i = -1, j <= 2147483647; 359 // whereas when i = 0, j <= -3), this is an infinite loop that goes OOB. 360 for (int j = -3; j <= 2147483646 * i - 3; j++) { 361 sResult += a[j + 3]; 362 } 363 } 364 } 365 366 /// CHECK-START: void Main.hiddenFiniteOOB() BCE (before) 367 /// CHECK-DAG: BoundsCheck 368 // 369 /// CHECK-START: void Main.hiddenFiniteOOB() BCE (after) 370 /// CHECK-DAG: Deoptimize 371 // 372 /// CHECK-START: void Main.hiddenFiniteOOB() BCE (after) 373 /// CHECK-NOT: BoundsCheck hiddenFiniteOOB()374 private static void hiddenFiniteOOB() { 375 int[] a = { 111 } ; 376 for (int i = -1; i <= 0; i++) { 377 // Dangerous loop similar as above where the loop is now finite, but the 378 // loop still goes out of bounds for i = -1 due to the large upper bound. 379 // Dynamic BCE is feasible though, since it checks the range. 380 for (int j = -4; j < 2147483646 * i - 3; j++) { 381 sResult += a[j + 4]; 382 } 383 } 384 } 385 386 /// CHECK-START: void Main.inductionOOB(int[]) BCE (before) 387 /// CHECK-DAG: BoundsCheck 388 // 389 /// CHECK-START: void Main.inductionOOB(int[]) BCE (after) 390 /// CHECK-DAG: BoundsCheck 391 // 392 /// CHECK-START: void Main.inductionOOB(int[]) BCE (after) 393 /// CHECK-NOT: Deoptimize inductionOOB(int[] a)394 private static void inductionOOB(int[] a) { 395 // Careless range analysis would remove the bounds check. 396 // However, the narrower induction b wraps around arithmetically 397 // before it reaches the end of arrays longer than 127. 398 byte b = 0; 399 for (int i = 0; i < a.length; i++) { 400 a[b++] = i; 401 } 402 } 403 404 /// CHECK-START: void Main.controlOOB(int[]) BCE (before) 405 /// CHECK-DAG: BoundsCheck 406 // 407 /// CHECK-START: void Main.controlOOB(int[]) BCE (after) 408 /// CHECK-DAG: BoundsCheck 409 // 410 /// CHECK-START: void Main.controlOOB(int[]) BCE (after) 411 /// CHECK-NOT: Deoptimize controlOOB(int[] a)412 private static void controlOOB(int[] a) { 413 // As above, but now the loop control also wraps around. 414 for (byte i = 0; i < a.length; i++) { 415 a[i] = -i; 416 } 417 } 418 419 /// CHECK-START: void Main.conversionOOB(int[]) BCE (before) 420 /// CHECK-DAG: BoundsCheck 421 // 422 /// CHECK-START: void Main.conversionOOB(int[]) BCE (after) 423 /// CHECK-DAG: BoundsCheck 424 // 425 /// CHECK-START: void Main.conversionOOB(int[]) BCE (after) 426 /// CHECK-NOT: Deoptimize conversionOOB(int[] a)427 private static void conversionOOB(int[] a) { 428 // As above, but with wrap around caused by an explicit conversion. 429 for (int i = 0; i < a.length; ) { 430 a[i] = i; 431 i = (byte) (i + 1); 432 } 433 } 434 435 /// CHECK-START: int[] Main.add() BCE (before) 436 /// CHECK-DAG: BoundsCheck 437 // 438 /// CHECK-START: int[] Main.add() BCE (after) 439 /// CHECK-NOT: BoundsCheck 440 /// CHECK-NOT: Deoptimize add()441 private static int[] add() { 442 int[] a = new int[10]; 443 for (int i = 0; i <= 3; i++) { 444 for (int j = 0; j <= 6; j++) { 445 a[i + j] += 1; 446 } 447 } 448 return a; 449 } 450 451 /// CHECK-START: int[] Main.multiply1() BCE (before) 452 /// CHECK-DAG: BoundsCheck 453 // 454 /// CHECK-START: int[] Main.multiply1() BCE (after) 455 /// CHECK-NOT: BoundsCheck 456 /// CHECK-NOT: Deoptimize multiply1()457 private static int[] multiply1() { 458 int[] a = new int[10]; 459 try { 460 for (int i = 0; i <= 3; i++) { 461 for (int j = 0; j <= 3; j++) { 462 // Range [0,9]: safe. 463 a[i * j] += 1; 464 } 465 } 466 } catch (Exception e) { 467 a[0] += 1000; 468 } 469 return a; 470 } 471 472 /// CHECK-START: int[] Main.multiply2() BCE (before) 473 /// CHECK-DAG: BoundsCheck 474 // 475 /// CHECK-START: int[] Main.multiply2() BCE (after) 476 /// CHECK-DAG: BoundsCheck 477 // 478 /// CHECK-START: int[] Main.multiply2() BCE (after) 479 /// CHECK-NOT: Deoptimize multiply2()480 static int[] multiply2() { 481 int[] a = new int[10]; 482 try { 483 for (int i = -3; i <= 3; i++) { 484 for (int j = -3; j <= 3; j++) { 485 // Range [-9,9]: unsafe. 486 a[i * j] += 1; 487 } 488 } 489 } catch (Exception e) { 490 a[0] += 1000; 491 } 492 return a; 493 } 494 495 /// CHECK-START: int Main.linearDynamicBCE1(int[], int, int) BCE (before) 496 /// CHECK-DAG: ArrayGet loop:<<Loop:B\d+>> 497 /// CHECK-DAG: NullCheck loop:<<Loop>> 498 /// CHECK-DAG: ArrayLength loop:<<Loop>> 499 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 500 // 501 /// CHECK-START: int Main.linearDynamicBCE1(int[], int, int) BCE (after) 502 /// CHECK-DAG: ArrayGet loop:{{B\d+}} 503 /// CHECK-DAG: Deoptimize loop:none 504 // 505 /// CHECK-START: int Main.linearDynamicBCE1(int[], int, int) BCE (after) 506 /// CHECK-NOT: NullCheck loop:{{B\d+}} 507 /// CHECK-NOT: ArrayLength loop:{{B\d+}} 508 /// CHECK-NOT: BoundsCheck loop:{{B\d+}} linearDynamicBCE1(int[] x, int lo, int hi)509 private static int linearDynamicBCE1(int[] x, int lo, int hi) { 510 int result = 0; 511 for (int i = lo; i < hi; i++) { 512 sResult += x[i]; 513 } 514 return result; 515 } 516 517 /// CHECK-START: int Main.linearDynamicBCE2(int[], int, int, int) BCE (before) 518 /// CHECK-DAG: ArrayGet loop:<<Loop:B\d+>> 519 /// CHECK-DAG: NullCheck loop:<<Loop>> 520 /// CHECK-DAG: ArrayLength loop:<<Loop>> 521 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 522 // 523 /// CHECK-START: int Main.linearDynamicBCE2(int[], int, int, int) BCE (after) 524 /// CHECK-DAG: ArrayGet loop:{{B\d+}} 525 /// CHECK-DAG: Deoptimize loop:none 526 // 527 /// CHECK-START: int Main.linearDynamicBCE2(int[], int, int, int) BCE (after) 528 /// CHECK-NOT: NullCheck loop:{{B\d+}} 529 /// CHECK-NOT: ArrayLength loop:{{B\d+}} 530 /// CHECK-NOT: BoundsCheck loop:{{B\d+}} linearDynamicBCE2(int[] x, int lo, int hi, int offset)531 private static int linearDynamicBCE2(int[] x, int lo, int hi, int offset) { 532 int result = 0; 533 for (int i = lo; i < hi; i++) { 534 sResult += x[offset + i]; 535 } 536 return result; 537 } 538 539 /// CHECK-START: int Main.wrapAroundDynamicBCE(int[]) BCE (before) 540 /// CHECK-DAG: ArrayGet loop:<<Loop:B\d+>> 541 /// CHECK-DAG: NullCheck loop:<<Loop>> 542 /// CHECK-DAG: ArrayLength loop:<<Loop>> 543 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 544 // 545 /// CHECK-START: int Main.wrapAroundDynamicBCE(int[]) BCE (after) 546 /// CHECK-DAG: ArrayGet loop:{{B\d+}} 547 /// CHECK-DAG: Deoptimize loop:none 548 // 549 /// CHECK-START: int Main.wrapAroundDynamicBCE(int[]) BCE (after) 550 /// CHECK-NOT: NullCheck loop:{{B\d+}} 551 /// CHECK-NOT: ArrayLength loop:{{B\d+}} 552 /// CHECK-NOT: BoundsCheck loop:{{B\d+}} wrapAroundDynamicBCE(int[] x)553 private static int wrapAroundDynamicBCE(int[] x) { 554 int w = 9; 555 int result = 0; 556 for (int i = 0; i < 10; i++) { 557 result += x[w]; 558 w = i; 559 } 560 return result; 561 } 562 563 /// CHECK-START: int Main.periodicDynamicBCE(int[]) BCE (before) 564 /// CHECK-DAG: ArrayGet loop:<<Loop:B\d+>> 565 /// CHECK-DAG: NullCheck loop:<<Loop>> 566 /// CHECK-DAG: ArrayLength loop:<<Loop>> 567 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 568 // 569 /// CHECK-START: int Main.periodicDynamicBCE(int[]) BCE (after) 570 /// CHECK-DAG: ArrayGet loop:{{B\d+}} 571 /// CHECK-DAG: Deoptimize loop:none 572 // 573 /// CHECK-START: int Main.periodicDynamicBCE(int[]) BCE (after) 574 /// CHECK-NOT: NullCheck loop:{{B\d+}} 575 /// CHECK-NOT: ArrayLength loop:{{B\d+}} 576 /// CHECK-NOT: BoundsCheck loop:{{B\d+}} periodicDynamicBCE(int[] x)577 private static int periodicDynamicBCE(int[] x) { 578 int k = 0; 579 int result = 0; 580 for (int i = 0; i < 10; i++) { 581 result += x[k]; 582 k = 1 - k; 583 } 584 return result; 585 } 586 587 /// CHECK-START: int Main.dynamicBCEPossiblyInfiniteLoop(int[], int, int) BCE (before) 588 /// CHECK-DAG: ArrayGet loop:<<Loop:B\d+>> 589 /// CHECK-DAG: NullCheck loop:<<Loop>> 590 /// CHECK-DAG: ArrayLength loop:<<Loop>> 591 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 592 // 593 /// CHECK-START: int Main.dynamicBCEPossiblyInfiniteLoop(int[], int, int) BCE (after) 594 /// CHECK-DAG: ArrayGet loop:{{B\d+}} 595 /// CHECK-DAG: Deoptimize loop:none 596 // 597 /// CHECK-START: int Main.dynamicBCEPossiblyInfiniteLoop(int[], int, int) BCE (after) 598 /// CHECK-NOT: NullCheck loop:{{B\d+}} 599 /// CHECK-NOT: ArrayLength loop:{{B\d+}} 600 /// CHECK-NOT: BoundsCheck loop:{{B\d+}} dynamicBCEPossiblyInfiniteLoop(int[] x, int lo, int hi)601 static int dynamicBCEPossiblyInfiniteLoop(int[] x, int lo, int hi) { 602 // This loop could be infinite for hi = max int. Since i is also used 603 // as subscript, however, dynamic bce can proceed. 604 int result = 0; 605 for (int i = lo; i <= hi; i++) { 606 result += x[i]; 607 } 608 return result; 609 } 610 611 /// CHECK-START: int Main.noDynamicBCEPossiblyInfiniteLoop(int[], int, int) BCE (before) 612 /// CHECK-DAG: ArrayGet loop:<<Loop:B\d+>> 613 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 614 // 615 /// CHECK-START: int Main.noDynamicBCEPossiblyInfiniteLoop(int[], int, int) BCE (after) 616 /// CHECK-DAG: ArrayGet loop:<<Loop:B\d+>> 617 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 618 // 619 /// CHECK-START: int Main.noDynamicBCEPossiblyInfiniteLoop(int[], int, int) BCE (after) 620 /// CHECK-NOT: Deoptimize noDynamicBCEPossiblyInfiniteLoop(int[] x, int lo, int hi)621 static int noDynamicBCEPossiblyInfiniteLoop(int[] x, int lo, int hi) { 622 // As above, but now the index is not used as subscript, 623 // and dynamic bce is not applied. 624 int result = 0; 625 for (int k = 0, i = lo; i <= hi; i++) { 626 result += x[k++]; 627 } 628 return result; 629 } 630 631 /// CHECK-START: int Main.noDynamicBCEMixedInductionTypes(int[], long, long) BCE (before) 632 /// CHECK-DAG: ArrayGet loop:<<Loop:B\d+>> 633 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 634 // 635 /// CHECK-START: int Main.noDynamicBCEMixedInductionTypes(int[], long, long) BCE (after) 636 /// CHECK-DAG: ArrayGet loop:<<Loop:B\d+>> 637 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 638 // 639 /// CHECK-START: int Main.noDynamicBCEMixedInductionTypes(int[], long, long) BCE (after) 640 /// CHECK-NOT: Deoptimize noDynamicBCEMixedInductionTypes(int[] x, long lo, long hi)641 static int noDynamicBCEMixedInductionTypes(int[] x, long lo, long hi) { 642 int result = 0; 643 // Mix of int and long induction. 644 int k = 0; 645 for (long i = lo; i < hi; i++) { 646 result += x[k++]; 647 } 648 return result; 649 } 650 651 /// CHECK-START: int Main.dynamicBCEConstantRange(int[]) BCE (before) 652 /// CHECK-DAG: BoundsCheck loop:<<InnerLoop:B\d+>> 653 /// CHECK-DAG: ArrayGet loop:<<InnerLoop>> 654 /// CHECK-DAG: If loop:<<InnerLoop>> 655 /// CHECK-DAG: If loop:<<OuterLoop:B\d+>> 656 /// CHECK-EVAL: "<<InnerLoop>>" != "<<OuterLoop>>" 657 // 658 /// CHECK-START: int Main.dynamicBCEConstantRange(int[]) BCE (after) 659 /// CHECK-DAG: ArrayGet loop:<<InnerLoop:B\d+>> 660 /// CHECK-DAG: Deoptimize loop:<<OuterLoop:B\d+>> 661 /// CHECK-EVAL: "<<InnerLoop>>" != "<<OuterLoop>>" 662 // 663 /// CHECK-START: int Main.dynamicBCEConstantRange(int[]) BCE (after) 664 /// CHECK-NOT: BoundsCheck 665 // 666 // No additional top tests were introduced. 667 /// CHECK-START: int Main.dynamicBCEConstantRange(int[]) BCE (after) 668 /// CHECK-DAG: If 669 /// CHECK-DAG: If 670 /// CHECK-NOT: If dynamicBCEConstantRange(int[] x)671 static int dynamicBCEConstantRange(int[] x) { 672 int result = 0; 673 for (int i = 2; i <= 6; i++) { 674 // Range analysis sees that innermost loop is finite and always taken. 675 for (int j = i - 2; j <= i + 2; j++) { 676 result += x[j]; 677 } 678 } 679 return result; 680 } 681 682 /// CHECK-START: int Main.dynamicBCEAndConstantIndices(int[], int[][], int, int) BCE (before) 683 /// CHECK-DAG: {{l\d+}} ArrayGet loop:<<Loop:B\d+>> 684 /// CHECK-DAG: {{l\d+}} ArrayGet loop:<<Loop>> 685 /// CHECK-DAG: {{l\d+}} ArrayGet loop:<<Loop>> 686 // 687 /// CHECK-START: int Main.dynamicBCEAndConstantIndices(int[], int[][], int, int) BCE (after) 688 // Order matters: 689 /// CHECK: Deoptimize loop:<<Loop:B\d+>> 690 // CHECK-NOT: Goto loop:<<Loop>> 691 /// CHECK-DAG: {{l\d+}} ArrayGet loop:<<Loop>> 692 /// CHECK-DAG: {{l\d+}} ArrayGet loop:<<Loop>> 693 /// CHECK-DAG: {{l\d+}} ArrayGet loop:<<Loop>> 694 /// CHECK: Goto loop:<<Loop>> 695 // 696 /// CHECK-START: int Main.dynamicBCEAndConstantIndices(int[], int[][], int, int) BCE (after) 697 /// CHECK-DAG: Deoptimize loop:none dynamicBCEAndConstantIndices(int[] x, int[][] a, int lo, int hi)698 static int dynamicBCEAndConstantIndices(int[] x, int[][] a, int lo, int hi) { 699 // Deliberately test array length on a before the loop so that only bounds checks 700 // on constant subscripts remain, making them a viable candidate for hoisting. 701 if (a.length == 0) { 702 return -1; 703 } 704 // Loop that allows BCE on x[i]. 705 int result = 0; 706 for (int i = lo; i < hi; i++) { 707 result += x[i]; 708 if ((i % 10) != 0) { 709 // None of the subscripts inside a conditional are removed by dynamic bce, 710 // making them a candidate for deoptimization based on constant indices. 711 // Compiler should ensure the array loads are not subsequently hoisted 712 // "above" the deoptimization "barrier" on the bounds. 713 a[0][i] = 1; 714 a[1][i] = 2; 715 a[99][i] = 3; 716 } 717 } 718 return result; 719 } 720 721 /// CHECK-START: int Main.dynamicBCEAndConstantIndicesAllPrimTypes(int[], boolean[], byte[], char[], short[], int[], long[], float[], double[], int, int) BCE (before) 722 /// CHECK-DAG: ArrayGet loop:<<Loop:B\d+>> 723 /// CHECK-DAG: ArrayGet loop:<<Loop>> 724 /// CHECK-DAG: ArrayGet loop:<<Loop>> 725 /// CHECK-DAG: ArrayGet loop:<<Loop>> 726 /// CHECK-DAG: ArrayGet loop:<<Loop>> 727 /// CHECK-DAG: ArrayGet loop:<<Loop>> 728 /// CHECK-DAG: ArrayGet loop:<<Loop>> 729 /// CHECK-DAG: ArrayGet loop:<<Loop>> 730 /// CHECK-DAG: ArrayGet loop:<<Loop>> 731 // For brevity, just test occurrence of at least one of each in the loop: 732 /// CHECK-DAG: NullCheck loop:<<Loop>> 733 /// CHECK-DAG: ArrayLength loop:<<Loop>> 734 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 735 // 736 /// CHECK-START: int Main.dynamicBCEAndConstantIndicesAllPrimTypes(int[], boolean[], byte[], char[], short[], int[], long[], float[], double[], int, int) BCE (after) 737 /// CHECK-DAG: ArrayGet loop:<<Loop:B\d+>> 738 /// CHECK-NOT: ArrayGet loop:<<Loop>> 739 // 740 /// CHECK-START: int Main.dynamicBCEAndConstantIndicesAllPrimTypes(int[], boolean[], byte[], char[], short[], int[], long[], float[], double[], int, int) BCE (after) 741 /// CHECK-NOT: NullCheck loop:{{B\d+}} 742 /// CHECK-NOT: ArrayLength loop:{{B\d+}} 743 /// CHECK-NOT: BoundsCheck loop:{{B\d+}} 744 // 745 /// CHECK-START: int Main.dynamicBCEAndConstantIndicesAllPrimTypes(int[], boolean[], byte[], char[], short[], int[], long[], float[], double[], int, int) BCE (after) 746 /// CHECK-DAG: Deoptimize loop:none dynamicBCEAndConstantIndicesAllPrimTypes(int[] q, boolean[] r, byte[] s, char[] t, short[] u, int[] v, long[] w, float[] x, double[] y, int lo, int hi)747 static int dynamicBCEAndConstantIndicesAllPrimTypes(int[] q, 748 boolean[] r, 749 byte[] s, 750 char[] t, 751 short[] u, 752 int[] v, 753 long[] w, 754 float[] x, 755 double[] y, int lo, int hi) { 756 int result = 0; 757 for (int i = lo; i < hi; i++) { 758 // All constant index array references can be hoisted out of the loop during BCE on q[i]. 759 result += q[i] + (r[0] ? 1 : 0) + (int) s[0] + (int) t[0] + (int) u[0] + (int) v[0] + 760 (int) w[0] + (int) x[0] + (int) y[0]; 761 } 762 return result; 763 } 764 765 /// CHECK-START: int Main.dynamicBCEAndConstantIndexRefType(int[], java.lang.Integer[], int, int) BCE (before) 766 /// CHECK-DAG: ArrayGet loop:<<Loop:B\d+>> 767 /// CHECK-DAG: NullCheck loop:<<Loop>> 768 /// CHECK-DAG: ArrayLength loop:<<Loop>> 769 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 770 /// CHECK-DAG: ArrayGet loop:<<Loop>> 771 /// CHECK-DAG: NullCheck loop:<<Loop>> 772 /// CHECK-DAG: ArrayLength loop:<<Loop>> 773 /// CHECK-DAG: BoundsCheck loop:<<Loop>> 774 // 775 /// CHECK-START: int Main.dynamicBCEAndConstantIndexRefType(int[], java.lang.Integer[], int, int) BCE (after) 776 /// CHECK-DAG: ArrayGet loop:<<Loop:B\d+>> 777 /// CHECK-DAG: Deoptimize loop:none 778 // 779 /// CHECK-START: int Main.dynamicBCEAndConstantIndexRefType(int[], java.lang.Integer[], int, int) BCE (after) 780 /// CHECK-NOT: ArrayLength loop:{{B\d+}} 781 /// CHECK-NOT: BoundsCheck loop:{{B\d+}} dynamicBCEAndConstantIndexRefType(int[] q, Integer[] z, int lo, int hi)782 static int dynamicBCEAndConstantIndexRefType(int[] q, Integer[] z, int lo, int hi) { 783 int result = 0; 784 for (int i = lo; i < hi; i++) { 785 // Similar to above, but now implicit call to intValue() may prevent hoisting 786 // z[0] itself during BCE on q[i]. Therefore, we just check BCE on q[i]. 787 result += q[i] + z[0]; 788 } 789 return result; 790 } 791 792 // 793 // Verifier. 794 // 795 main(String[] args)796 public static void main(String[] args) { 797 // Set to run expensive tests for correctness too. 798 boolean HEAVY = false; 799 800 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 801 802 int[] a200 = new int[200]; 803 804 // Sorting. 805 int[] sort = { 5, 4, 1, 9, 10, 2, 7, 6, 3, 8 }; 806 bubble(sort); 807 for (int i = 0; i < 10; i++) { 808 expectEquals(sort[i], x[i]); 809 } 810 811 // Periodic adds (1, 3), one at the time. 812 expectEquals(0, periodicIdiom(-1)); 813 for (int tc = 0; tc < 32; tc++) { 814 int expected = (tc >> 1) << 2; 815 if ((tc & 1) != 0) 816 expected += 1; 817 expectEquals(expected, periodicIdiom(tc)); 818 } 819 820 // Periodic adds (1, 3), one at the time. 821 expectEquals(0, periodicSequence2(-1)); 822 for (int tc = 0; tc < 32; tc++) { 823 int expected = (tc >> 1) << 2; 824 if ((tc & 1) != 0) 825 expected += 1; 826 expectEquals(expected, periodicSequence2(tc)); 827 } 828 829 // Periodic adds (1, 3, 5, 7), all at once. 830 expectEquals(0, periodicSequence4(-1)); 831 for (int tc = 0; tc < 32; tc++) { 832 expectEquals(tc * 16, periodicSequence4(tc)); 833 } 834 835 // Large bounds. 836 expectEquals(55, justRightUp1()); 837 expectEquals(55, justRightUp2()); 838 expectEquals(55, justRightUp3()); 839 expectEquals(55, justRightDown1()); 840 expectEquals(55, justRightDown2()); 841 expectEquals(55, justRightDown3()); 842 sResult = 0; 843 try { 844 justOOBUp(); 845 } catch (ArrayIndexOutOfBoundsException e) { 846 sResult = 1; 847 } 848 expectEquals(1, sResult); 849 sResult = 0; 850 try { 851 justOOBDown(); 852 } catch (ArrayIndexOutOfBoundsException e) { 853 sResult = 1; 854 } 855 expectEquals(1, sResult); 856 857 // Lower bound goes OOB. 858 sResult = 0; 859 try { 860 lowerOOB(x); 861 } catch (ArrayIndexOutOfBoundsException e) { 862 sResult += 1000; 863 } 864 expectEquals(1000, sResult); 865 866 // Upper bound goes OOB. 867 sResult = 0; 868 try { 869 upperOOB(x); 870 } catch (ArrayIndexOutOfBoundsException e) { 871 sResult += 1000; 872 } 873 expectEquals(1055, sResult); 874 875 // Do while up goes OOB. 876 sResult = 0; 877 try { 878 doWhileUpOOB(); 879 } catch (ArrayIndexOutOfBoundsException e) { 880 sResult += 1000; 881 } 882 expectEquals(1055, sResult); 883 884 // Do while down goes OOB. 885 sResult = 0; 886 try { 887 doWhileDownOOB(); 888 } catch (ArrayIndexOutOfBoundsException e) { 889 sResult += 1000; 890 } 891 expectEquals(1055, sResult); 892 893 // Hidden OOB. 894 sResult = 0; 895 try { 896 hiddenOOB1(10); // no OOB 897 } catch (ArrayIndexOutOfBoundsException e) { 898 sResult += 1000; 899 } 900 expectEquals(1, sResult); 901 sResult = 0; 902 try { 903 hiddenOOB1(-2147483648); // OOB 904 } catch (ArrayIndexOutOfBoundsException e) { 905 sResult += 1000; 906 } 907 expectEquals(1001, sResult); 908 sResult = 0; 909 try { 910 hiddenOOB2(1); // no OOB 911 } catch (ArrayIndexOutOfBoundsException e) { 912 sResult += 1000; 913 } 914 expectEquals(1, sResult); 915 if (HEAVY) { 916 sResult = 0; 917 try { 918 hiddenOOB2(2147483647); // OOB 919 } catch (ArrayIndexOutOfBoundsException e) { 920 sResult += 1000; 921 } 922 expectEquals(1002, sResult); 923 } 924 sResult = 0; 925 try { 926 hiddenInfiniteOOB(); 927 } catch (ArrayIndexOutOfBoundsException e) { 928 sResult += 1000; 929 } 930 expectEquals(1011, sResult); 931 sResult = 0; 932 try { 933 hiddenFiniteOOB(); 934 } catch (ArrayIndexOutOfBoundsException e) { 935 sResult += 1000; 936 } 937 expectEquals(1111, sResult); 938 sResult = 0; 939 try { 940 inductionOOB(a200); 941 } catch (ArrayIndexOutOfBoundsException e) { 942 sResult += 1000; 943 } 944 expectEquals(1000, sResult); 945 for (int i = 0; i < 200; i++) { 946 expectEquals(i < 128 ? i : 0, a200[i]); 947 } 948 sResult = 0; 949 try { 950 controlOOB(a200); 951 } catch (ArrayIndexOutOfBoundsException e) { 952 sResult += 1000; 953 } 954 expectEquals(1000, sResult); 955 for (int i = 0; i < 200; i++) { 956 expectEquals(i < 128 ? -i : 0, a200[i]); 957 } 958 sResult = 0; 959 try { 960 conversionOOB(a200); 961 } catch (ArrayIndexOutOfBoundsException e) { 962 sResult += 1000; 963 } 964 expectEquals(1000, sResult); 965 for (int i = 0; i < 200; i++) { 966 expectEquals(i < 128 ? i : 0, a200[i]); 967 } 968 969 // Addition. 970 { 971 int[] e1 ={ 1, 2, 3, 4, 4, 4, 4, 3, 2, 1 }; 972 int[] a1 = add(); 973 for (int i = 0; i < 10; i++) { 974 expectEquals(a1[i], e1[i]); 975 } 976 } 977 978 // Multiplication. 979 { 980 int[] e1 = { 7, 1, 2, 2, 1, 0, 2, 0, 0, 1 }; 981 int[] a1 = multiply1(); 982 for (int i = 0; i < 10; i++) { 983 expectEquals(a1[i], e1[i]); 984 } 985 int[] e2 = { 1001, 0, 0, 1, 0, 0, 1, 0, 0, 1 }; 986 int[] a2 = multiply2(); 987 for (int i = 0; i < 10; i++) { 988 expectEquals(a2[i], e2[i]); 989 } 990 } 991 992 // Dynamic BCE. 993 sResult = 0; 994 try { 995 linearDynamicBCE1(x, -1, x.length); 996 } catch (ArrayIndexOutOfBoundsException e) { 997 sResult += 1000; 998 } 999 expectEquals(1000, sResult); 1000 sResult = 0; 1001 linearDynamicBCE1(x, 0, x.length); 1002 expectEquals(55, sResult); 1003 sResult = 0; 1004 try { 1005 linearDynamicBCE1(x, 0, x.length + 1); 1006 } catch (ArrayIndexOutOfBoundsException e) { 1007 sResult += 1000; 1008 } 1009 expectEquals(1055, sResult); 1010 1011 // Dynamic BCE with offset. 1012 sResult = 0; 1013 try { 1014 linearDynamicBCE2(x, 0, x.length, -1); 1015 } catch (ArrayIndexOutOfBoundsException e) { 1016 sResult += 1000; 1017 } 1018 expectEquals(1000, sResult); 1019 sResult = 0; 1020 linearDynamicBCE2(x, 0, x.length, 0); 1021 expectEquals(55, sResult); 1022 sResult = 0; 1023 try { 1024 linearDynamicBCE2(x, 0, x.length, 1); 1025 } catch (ArrayIndexOutOfBoundsException e) { 1026 sResult += 1000; 1027 } 1028 expectEquals(1054, sResult); 1029 1030 // Dynamic BCE candidates. 1031 expectEquals(55, wrapAroundDynamicBCE(x)); 1032 expectEquals(15, periodicDynamicBCE(x)); 1033 expectEquals(55, dynamicBCEPossiblyInfiniteLoop(x, 0, 9)); 1034 expectEquals(55, noDynamicBCEPossiblyInfiniteLoop(x, 0, 9)); 1035 expectEquals(55, noDynamicBCEMixedInductionTypes(x, 0, 10)); 1036 expectEquals(125, dynamicBCEConstantRange(x)); 1037 1038 // Dynamic BCE combined with constant indices. 1039 int[][] a; 1040 a = new int[0][0]; 1041 expectEquals(-1, dynamicBCEAndConstantIndices(x, a, 0, 10)); 1042 a = new int[100][10]; 1043 expectEquals(55, dynamicBCEAndConstantIndices(x, a, 0, 10)); 1044 for (int i = 0; i < 10; i++) { 1045 expectEquals((i % 10) != 0 ? 1 : 0, a[0][i]); 1046 expectEquals((i % 10) != 0 ? 2 : 0, a[1][i]); 1047 expectEquals((i % 10) != 0 ? 3 : 0, a[99][i]); 1048 } 1049 a = new int[2][10]; 1050 sResult = 0; 1051 try { 1052 expectEquals(55, dynamicBCEAndConstantIndices(x, a, 0, 10)); 1053 } catch (ArrayIndexOutOfBoundsException e) { 1054 sResult = 1; 1055 } 1056 expectEquals(1, sResult); 1057 expectEquals(a[0][1], 1); 1058 expectEquals(a[1][1], 2); 1059 1060 // Dynamic BCE combined with constant indices of all types. 1061 boolean[] x1 = { true }; 1062 byte[] x2 = { 2 }; 1063 char[] x3 = { 3 }; 1064 short[] x4 = { 4 }; 1065 int[] x5 = { 5 }; 1066 long[] x6 = { 6 }; 1067 float[] x7 = { 7 }; 1068 double[] x8 = { 8 }; 1069 expectEquals(415, 1070 dynamicBCEAndConstantIndicesAllPrimTypes(x, x1, x2, x3, x4, x5, x6, x7, x8, 0, 10)); 1071 Integer[] x9 = { 9 }; 1072 expectEquals(145, dynamicBCEAndConstantIndexRefType(x, x9, 0, 10)); 1073 1074 System.out.println("passed"); 1075 } 1076 1077 private static void expectEquals(int expected, int result) { 1078 if (expected != result) { 1079 throw new Error("Expected: " + expected + ", found: " + result); 1080 } 1081 } 1082 } 1083