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