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 19 // CHECK-START: int Main.sieve(int) BCE (before) 20 // CHECK: BoundsCheck 21 // CHECK: ArraySet 22 // CHECK: BoundsCheck 23 // CHECK: ArrayGet 24 // CHECK: BoundsCheck 25 // CHECK: ArraySet 26 27 // CHECK-START: int Main.sieve(int) BCE (after) 28 // CHECK-NOT: BoundsCheck 29 // CHECK: ArraySet 30 // CHECK-NOT: BoundsCheck 31 // CHECK: ArrayGet 32 // CHECK: BoundsCheck 33 // CHECK: ArraySet 34 35 static int sieve(int size) { 36 int primeCount = 0; 37 boolean[] flags = new boolean[size + 1]; 38 for (int i = 1; i < size; i++) flags[i] = true; // Can eliminate. 39 for (int i = 2; i < size; i++) { 40 if (flags[i]) { // Can eliminate. 41 primeCount++; 42 for (int k = i + 1; k <= size; k += i) 43 flags[k - 1] = false; // Can't eliminate yet due to (k+i) may overflow. 44 } 45 } 46 return primeCount; 47 } 48 49 50 // CHECK-START: void Main.narrow(int[], int) BCE (before) 51 // CHECK: BoundsCheck 52 // CHECK: ArraySet 53 // CHECK: BoundsCheck 54 // CHECK: ArraySet 55 // CHECK: BoundsCheck 56 // CHECK: ArraySet 57 58 // CHECK-START: void Main.narrow(int[], int) BCE (after) 59 // CHECK-NOT: BoundsCheck 60 // CHECK: ArraySet 61 // CHECK-NOT: BoundsCheck 62 // CHECK: ArraySet 63 // CHECK: BoundsCheck 64 // CHECK: ArraySet 65 // CHECK-NOT: BoundsCheck 66 // CHECK: ArraySet 67 // CHECK: BoundsCheck 68 // CHECK: ArraySet 69 70 static void narrow(int[] array, int offset) { 71 if (offset < 0) { 72 return; 73 } 74 if (offset < array.length) { 75 // offset is in range [0, array.length-1]. 76 // Bounds check can be eliminated. 77 array[offset] = 1; 78 79 int biased_offset1 = offset + 1; 80 // biased_offset1 is in range [1, array.length]. 81 if (biased_offset1 < array.length) { 82 // biased_offset1 is in range [1, array.length-1]. 83 // Bounds check can be eliminated. 84 array[biased_offset1] = 1; 85 } 86 87 int biased_offset2 = offset + 0x70000000; 88 // biased_offset2 is in range [0x70000000, array.length-1+0x70000000]. 89 // It may overflow and be negative. 90 if (biased_offset2 < array.length) { 91 // Even with this test, biased_offset2 can be negative so we can't 92 // eliminate this bounds check. 93 array[biased_offset2] = 1; 94 } 95 96 // offset_sub1 won't underflow since offset is no less than 0. 97 int offset_sub1 = offset - Integer.MAX_VALUE; 98 if (offset_sub1 >= 0) { 99 array[offset_sub1] = 1; // Bounds check can be eliminated. 100 } 101 102 // offset_sub2 can underflow. 103 int offset_sub2 = offset_sub1 - Integer.MAX_VALUE; 104 if (offset_sub2 >= 0) { 105 array[offset_sub2] = 1; // Bounds check can't be eliminated. 106 } 107 } 108 } 109 110 111 // CHECK-START: void Main.constantIndexing1(int[]) BCE (before) 112 // CHECK: BoundsCheck 113 // CHECK: ArraySet 114 // CHECK: BoundsCheck 115 // CHECK: ArraySet 116 117 // CHECK-START: void Main.constantIndexing1(int[]) BCE (after) 118 // CHECK-NOT: Deoptimize 119 // CHECK: BoundsCheck 120 // CHECK: ArraySet 121 // CHECK-NOT: BoundsCheck 122 // CHECK: ArraySet 123 124 static void constantIndexing1(int[] array) { 125 array[5] = 1; 126 array[4] = 1; 127 } 128 129 130 // CHECK-START: void Main.constantIndexing2(int[]) BCE (before) 131 // CHECK: BoundsCheck 132 // CHECK: ArraySet 133 // CHECK: BoundsCheck 134 // CHECK: ArraySet 135 // CHECK: BoundsCheck 136 // CHECK: ArraySet 137 // CHECK: BoundsCheck 138 // CHECK: ArraySet 139 140 // CHECK-START: void Main.constantIndexing2(int[]) BCE (after) 141 // CHECK: LessThanOrEqual 142 // CHECK: Deoptimize 143 // CHECK-NOT: BoundsCheck 144 // CHECK: ArraySet 145 // CHECK-NOT: BoundsCheck 146 // CHECK: ArraySet 147 // CHECK-NOT: BoundsCheck 148 // CHECK: ArraySet 149 // CHECK-NOT: BoundsCheck 150 // CHECK: ArraySet 151 // CHECK: BoundsCheck 152 // CHECK: ArraySet 153 154 static void constantIndexing2(int[] array) { 155 array[1] = 1; 156 array[2] = 1; 157 array[3] = 1; 158 array[4] = 1; 159 array[-1] = 1; 160 } 161 162 163 // CHECK-START: int[] Main.constantIndexing3(int[], int[], boolean) BCE (before) 164 // CHECK: BoundsCheck 165 // CHECK: ArrayGet 166 // CHECK: BoundsCheck 167 // CHECK: ArraySet 168 // CHECK: BoundsCheck 169 // CHECK: ArrayGet 170 // CHECK: BoundsCheck 171 // CHECK: ArraySet 172 // CHECK: BoundsCheck 173 // CHECK: ArrayGet 174 // CHECK: BoundsCheck 175 // CHECK: ArraySet 176 // CHECK: BoundsCheck 177 // CHECK: ArrayGet 178 // CHECK: BoundsCheck 179 // CHECK: ArraySet 180 181 // CHECK-START: int[] Main.constantIndexing3(int[], int[], boolean) BCE (after) 182 // CHECK: LessThanOrEqual 183 // CHECK: Deoptimize 184 // CHECK-NOT: BoundsCheck 185 // CHECK: ArrayGet 186 // CHECK: LessThanOrEqual 187 // CHECK: Deoptimize 188 // CHECK-NOT: BoundsCheck 189 // CHECK: ArraySet 190 // CHECK-NOT: BoundsCheck 191 // CHECK: ArrayGet 192 // CHECK-NOT: BoundsCheck 193 // CHECK: ArraySet 194 // CHECK-NOT: BoundsCheck 195 // CHECK: ArrayGet 196 // CHECK-NOT: BoundsCheck 197 // CHECK: ArraySet 198 // CHECK-NOT: BoundsCheck 199 // CHECK: ArrayGet 200 // CHECK-NOT: BoundsCheck 201 // CHECK: ArraySet 202 203 static int[] constantIndexing3(int[] array1, int[] array2, boolean copy) { 204 if (!copy) { 205 return array1; 206 } 207 array2[0] = array1[0]; 208 array2[1] = array1[1]; 209 array2[2] = array1[2]; 210 array2[3] = array1[3]; 211 return array2; 212 } 213 214 215 // CHECK-START: void Main.constantIndexing4(int[]) BCE (before) 216 // CHECK: BoundsCheck 217 // CHECK: ArraySet 218 219 // CHECK-START: void Main.constantIndexing4(int[]) BCE (after) 220 // CHECK-NOT: LessThanOrEqual 221 // CHECK: BoundsCheck 222 // CHECK: ArraySet 223 224 // There is only one array access. It's not beneficial 225 // to create a compare with deoptimization instruction. 226 static void constantIndexing4(int[] array) { 227 array[0] = 1; 228 } 229 230 231 // CHECK-START: void Main.constantIndexing5(int[]) BCE (before) 232 // CHECK: BoundsCheck 233 // CHECK: ArraySet 234 // CHECK: BoundsCheck 235 // CHECK: ArraySet 236 237 // CHECK-START: void Main.constantIndexing5(int[]) BCE (after) 238 // CHECK-NOT: Deoptimize 239 // CHECK: BoundsCheck 240 // CHECK: ArraySet 241 // CHECK: BoundsCheck 242 // CHECK: ArraySet 243 244 static void constantIndexing5(int[] array) { 245 // We don't apply the deoptimization for very large constant index 246 // since it's likely to be an anomaly and will throw AIOOBE. 247 array[Integer.MAX_VALUE - 1000] = 1; 248 array[Integer.MAX_VALUE - 999] = 1; 249 array[Integer.MAX_VALUE - 998] = 1; 250 } 251 252 // CHECK-START: void Main.loopPattern1(int[]) BCE (before) 253 // CHECK: BoundsCheck 254 // CHECK: ArraySet 255 // CHECK: BoundsCheck 256 // CHECK: ArraySet 257 // CHECK: BoundsCheck 258 // CHECK: ArraySet 259 // CHECK: BoundsCheck 260 // CHECK: ArraySet 261 // CHECK: BoundsCheck 262 // CHECK: ArraySet 263 // CHECK: BoundsCheck 264 // CHECK: ArraySet 265 // CHECK: BoundsCheck 266 // CHECK: ArraySet 267 268 // CHECK-START: void Main.loopPattern1(int[]) BCE (after) 269 // CHECK-NOT: BoundsCheck 270 // CHECK: ArraySet 271 // CHECK-NOT: BoundsCheck 272 // CHECK: ArraySet 273 // CHECK-NOT: BoundsCheck 274 // CHECK: ArraySet 275 // CHECK: BoundsCheck 276 // CHECK: ArraySet 277 // CHECK: BoundsCheck 278 // CHECK: ArraySet 279 // CHECK: BoundsCheck 280 // CHECK: ArraySet 281 // CHECK-NOT: BoundsCheck 282 // CHECK: ArraySet 283 284 static void loopPattern1(int[] array) { 285 for (int i = 0; i < array.length; i++) { 286 array[i] = 1; // Bounds check can be eliminated. 287 } 288 289 for (int i = 1; i < array.length; i++) { 290 array[i] = 1; // Bounds check can be eliminated. 291 } 292 293 for (int i = 1; i < array.length - 1; i++) { 294 array[i] = 1; // Bounds check can be eliminated. 295 } 296 297 for (int i = -1; i < array.length; i++) { 298 array[i] = 1; // Bounds check can't be eliminated. 299 } 300 301 for (int i = 0; i <= array.length; i++) { 302 array[i] = 1; // Bounds check can't be eliminated. 303 } 304 305 for (int i = 0; i < array.length; i += 2) { 306 // We don't have any assumption on max array length yet. 307 // Bounds check can't be eliminated due to overflow concern. 308 array[i] = 1; 309 } 310 311 for (int i = 1; i < array.length; i += 2) { 312 // Bounds check can be eliminated since i is odd so the last 313 // i that's less than array.length is at most (Integer.MAX_VALUE - 2). 314 array[i] = 1; 315 } 316 } 317 318 319 // CHECK-START: void Main.loopPattern2(int[]) BCE (before) 320 // CHECK: BoundsCheck 321 // CHECK: ArraySet 322 // CHECK: BoundsCheck 323 // CHECK: ArraySet 324 // CHECK: BoundsCheck 325 // CHECK: ArraySet 326 // CHECK: BoundsCheck 327 // CHECK: ArraySet 328 // CHECK: BoundsCheck 329 // CHECK: ArraySet 330 // CHECK: BoundsCheck 331 // CHECK: ArraySet 332 333 // CHECK-START: void Main.loopPattern2(int[]) BCE (after) 334 // CHECK-NOT: BoundsCheck 335 // CHECK: ArraySet 336 // CHECK-NOT: BoundsCheck 337 // CHECK: ArraySet 338 // CHECK-NOT: BoundsCheck 339 // CHECK: ArraySet 340 // CHECK: BoundsCheck 341 // CHECK: ArraySet 342 // CHECK: BoundsCheck 343 // CHECK: ArraySet 344 // CHECK-NOT: BoundsCheck 345 // CHECK: ArraySet 346 347 static void loopPattern2(int[] array) { 348 for (int i = array.length - 1; i >= 0; i--) { 349 array[i] = 1; // Bounds check can be eliminated. 350 } 351 352 for (int i = array.length; i > 0; i--) { 353 array[i - 1] = 1; // Bounds check can be eliminated. 354 } 355 356 for (int i = array.length - 1; i > 0; i--) { 357 array[i] = 1; // Bounds check can be eliminated. 358 } 359 360 for (int i = array.length; i >= 0; i--) { 361 array[i] = 1; // Bounds check can't be eliminated. 362 } 363 364 for (int i = array.length; i >= 0; i--) { 365 array[i - 1] = 1; // Bounds check can't be eliminated. 366 } 367 368 for (int i = array.length; i > 0; i -= 20) { 369 // For i >= 0, (i - 20 - 1) is guaranteed not to underflow. 370 array[i - 1] = 1; // Bounds check can be eliminated. 371 } 372 } 373 374 375 // CHECK-START: void Main.loopPattern3(int[]) BCE (before) 376 // CHECK: BoundsCheck 377 // CHECK: ArraySet 378 379 // CHECK-START: void Main.loopPattern3(int[]) BCE (after) 380 // CHECK: BoundsCheck 381 // CHECK: ArraySet 382 383 static void loopPattern3(int[] array) { 384 java.util.Random random = new java.util.Random(); 385 for (int i = 0; ; i++) { 386 if (random.nextInt() % 1000 == 0 && i < array.length) { 387 // Can't eliminate the bound check since not every i++ is 388 // matched with a array length check, so there is some chance that i 389 // overflows and is negative. 390 array[i] = 1; 391 } 392 } 393 } 394 395 396 // CHECK-START: void Main.constantNewArray() BCE (before) 397 // CHECK: BoundsCheck 398 // CHECK: ArraySet 399 // CHECK: BoundsCheck 400 // CHECK: ArraySet 401 // CHECK: BoundsCheck 402 // CHECK: ArraySet 403 // CHECK: BoundsCheck 404 // CHECK: ArraySet 405 // CHECK: BoundsCheck 406 // CHECK: ArraySet 407 408 // CHECK-START: void Main.constantNewArray() BCE (after) 409 // CHECK-NOT: BoundsCheck 410 // CHECK: ArraySet 411 // CHECK: BoundsCheck 412 // CHECK: ArraySet 413 // CHECK-NOT: BoundsCheck 414 // CHECK: ArraySet 415 // CHECK-NOT: BoundsCheck 416 // CHECK: ArraySet 417 // CHECK: BoundsCheck 418 // CHECK: ArraySet 419 420 static void constantNewArray() { 421 int[] array = new int[10]; 422 for (int i = 0; i < 10; i++) { 423 array[i] = 1; // Bounds check can be eliminated. 424 } 425 426 for (int i = 0; i <= 10; i++) { 427 array[i] = 1; // Bounds check can't be eliminated. 428 } 429 430 array[0] = 1; // Bounds check can be eliminated. 431 array[9] = 1; // Bounds check can be eliminated. 432 array[10] = 1; // Bounds check can't be eliminated. 433 } 434 435 436 static byte readData() { 437 return 1; 438 } 439 440 // CHECK-START: void Main.circularBufferProducer() BCE (before) 441 // CHECK: BoundsCheck 442 // CHECK: ArraySet 443 444 // CHECK-START: void Main.circularBufferProducer() BCE (after) 445 // CHECK-NOT: BoundsCheck 446 // CHECK: ArraySet 447 448 static void circularBufferProducer() { 449 byte[] array = new byte[4096]; 450 int i = 0; 451 while (true) { 452 array[i & (array.length - 1)] = readData(); 453 i++; 454 } 455 } 456 457 458 // CHECK-START: void Main.pyramid1(int[]) BCE (before) 459 // CHECK: BoundsCheck 460 // CHECK: ArraySet 461 // CHECK: BoundsCheck 462 // CHECK: ArraySet 463 464 // CHECK-START: void Main.pyramid1(int[]) BCE (after) 465 // CHECK-NOT: BoundsCheck 466 // CHECK: ArraySet 467 // CHECK-NOT: BoundsCheck 468 // CHECK: ArraySet 469 470 // Set array to something like {0, 1, 2, 3, 2, 1, 0}. 471 static void pyramid1(int[] array) { 472 for (int i = 0; i < (array.length + 1) / 2; i++) { 473 array[i] = i; 474 array[array.length - 1 - i] = i; 475 } 476 } 477 478 479 // CHECK-START: void Main.pyramid2(int[]) BCE (before) 480 // CHECK: BoundsCheck 481 // CHECK: ArraySet 482 // CHECK: BoundsCheck 483 // CHECK: ArraySet 484 485 // CHECK-START: void Main.pyramid2(int[]) BCE (after) 486 // CHECK-NOT: BoundsCheck 487 // CHECK: ArraySet 488 // CHECK-NOT: BoundsCheck 489 // CHECK: ArraySet 490 491 // Set array to something like {0, 1, 2, 3, 2, 1, 0}. 492 static void pyramid2(int[] array) { 493 for (int i = 0; i < (array.length + 1) >> 1; i++) { 494 array[i] = i; 495 array[array.length - 1 - i] = i; 496 } 497 } 498 499 500 // CHECK-START: void Main.pyramid3(int[]) BCE (before) 501 // CHECK: BoundsCheck 502 // CHECK: ArraySet 503 // CHECK: BoundsCheck 504 // CHECK: ArraySet 505 506 // CHECK-START: void Main.pyramid3(int[]) BCE (after) 507 // CHECK-NOT: BoundsCheck 508 // CHECK: ArraySet 509 // CHECK-NOT: BoundsCheck 510 // CHECK: ArraySet 511 512 // Set array to something like {0, 1, 2, 3, 2, 1, 0}. 513 static void pyramid3(int[] array) { 514 for (int i = 0; i < (array.length + 1) >>> 1; i++) { 515 array[i] = i; 516 array[array.length - 1 - i] = i; 517 } 518 } 519 520 521 // CHECK-START: boolean Main.isPyramid(int[]) BCE (before) 522 // CHECK: BoundsCheck 523 // CHECK: ArrayGet 524 // CHECK: BoundsCheck 525 // CHECK: ArrayGet 526 527 // CHECK-START: boolean Main.isPyramid(int[]) BCE (after) 528 // CHECK-NOT: BoundsCheck 529 // CHECK: ArrayGet 530 // CHECK-NOT: BoundsCheck 531 // CHECK: ArrayGet 532 533 static boolean isPyramid(int[] array) { 534 int i = 0; 535 int j = array.length - 1; 536 while (i <= j) { 537 if (array[i] != i) { 538 return false; 539 } 540 if (array[j] != i) { 541 return false; 542 } 543 i++; j--; 544 } 545 return true; 546 } 547 548 549 // CHECK-START: void Main.bubbleSort(int[]) GVN (before) 550 // CHECK: BoundsCheck 551 // CHECK: ArrayGet 552 // CHECK: BoundsCheck 553 // CHECK: ArrayGet 554 // CHECK: BoundsCheck 555 // CHECK: ArrayGet 556 // CHECK: BoundsCheck 557 // CHECK: ArrayGet 558 // CHECK: BoundsCheck 559 // CHECK: ArraySet 560 // CHECK: BoundsCheck 561 // CHECK: ArraySet 562 563 // CHECK-START: void Main.bubbleSort(int[]) GVN (after) 564 // CHECK: BoundsCheck 565 // CHECK: ArrayGet 566 // CHECK: BoundsCheck 567 // CHECK: ArrayGet 568 // CHECK-NOT: ArrayGet 569 // CHECK-NOT: ArrayGet 570 // CHECK-NOT: BoundsCheck 571 // CHECK: ArraySet 572 // CHECK-NOT: BoundsCheck 573 // CHECK: ArraySet 574 575 // CHECK-START: void Main.bubbleSort(int[]) BCE (after) 576 // CHECK-NOT: BoundsCheck 577 // CHECK: ArrayGet 578 // CHECK-NOT: BoundsCheck 579 // CHECK: ArrayGet 580 // CHECK-NOT: ArrayGet 581 // CHECK-NOT: ArrayGet 582 // CHECK-NOT: BoundsCheck 583 // CHECK: ArraySet 584 // CHECK-NOT: BoundsCheck 585 // CHECK: ArraySet 586 587 static void bubbleSort(int[] array) { 588 for (int i = 0; i < array.length - 1; i++) { 589 for (int j = 0; j < array.length - i - 1; j++) { 590 if (array[j] > array[j + 1]) { 591 int temp = array[j + 1]; 592 array[j + 1] = array[j]; 593 array[j] = temp; 594 } 595 } 596 } 597 } 598 599 600 static int foo() { 601 try { 602 // This will cause AIOOBE. 603 constantIndexing2(new int[3]); 604 } catch (ArrayIndexOutOfBoundsException e) { 605 return 99; 606 } 607 return 0; 608 } 609 610 611 int sum; 612 613 // CHECK-START: void Main.foo1(int[], int, int) BCE (before) 614 // CHECK: BoundsCheck 615 // CHECK: ArraySet 616 // CHECK-NOT: BoundsCheck 617 // CHECK: ArrayGet 618 619 // CHECK-START: void Main.foo1(int[], int, int) BCE (after) 620 // CHECK: Phi 621 // CHECK-NOT: BoundsCheck 622 // CHECK: ArraySet 623 // CHECK-NOT: BoundsCheck 624 // CHECK: ArrayGet 625 // Added blocks for deoptimization. 626 // CHECK: If 627 // CHECK: Goto 628 // CHECK: Deoptimize 629 // CHECK: Deoptimize 630 // CHECK: Deoptimize 631 // CHECK-NOT: Deoptimize 632 // CHECK: Goto 633 // CHECK: Phi 634 // CHECK: Goto 635 636 void foo1(int[] array, int start, int end) { 637 // Three HDeoptimize will be added. One for 638 // start >= 0, one for end <= array.length, 639 // and one for null check on array (to hoist null 640 // check and array.length out of loop). 641 for (int i = start ; i < end; i++) { 642 array[i] = 1; 643 sum += array[i]; 644 } 645 } 646 647 648 // CHECK-START: void Main.foo2(int[], int, int) BCE (before) 649 // CHECK: BoundsCheck 650 // CHECK: ArraySet 651 // CHECK-NOT: BoundsCheck 652 // CHECK: ArrayGet 653 654 // CHECK-START: void Main.foo2(int[], int, int) BCE (after) 655 // CHECK: Phi 656 // CHECK-NOT: BoundsCheck 657 // CHECK: ArraySet 658 // CHECK-NOT: BoundsCheck 659 // CHECK: ArrayGet 660 // Added blocks for deoptimization. 661 // CHECK: If 662 // CHECK: Goto 663 // CHECK: Deoptimize 664 // CHECK: Deoptimize 665 // CHECK: Deoptimize 666 // CHECK-NOT: Deoptimize 667 // CHECK: Goto 668 // CHECK: Phi 669 // CHECK: Goto 670 671 void foo2(int[] array, int start, int end) { 672 // Three HDeoptimize will be added. One for 673 // start >= 0, one for end <= array.length, 674 // and one for null check on array (to hoist null 675 // check and array.length out of loop). 676 for (int i = start ; i <= end; i++) { 677 array[i] = 1; 678 sum += array[i]; 679 } 680 } 681 682 683 // CHECK-START: void Main.foo3(int[], int) BCE (before) 684 // CHECK: BoundsCheck 685 // CHECK: ArraySet 686 // CHECK-NOT: BoundsCheck 687 // CHECK: ArrayGet 688 689 // CHECK-START: void Main.foo3(int[], int) BCE (after) 690 // CHECK: Phi 691 // CHECK-NOT: BoundsCheck 692 // CHECK: ArraySet 693 // CHECK-NOT: BoundsCheck 694 // CHECK: ArrayGet 695 // Added blocks for deoptimization. 696 // CHECK: If 697 // CHECK: Goto 698 // CHECK: Deoptimize 699 // CHECK: Deoptimize 700 // CHECK-NOT: Deoptimize 701 // CHECK: Goto 702 // CHECK: Phi 703 // CHECK: Goto 704 705 void foo3(int[] array, int end) { 706 // Two HDeoptimize will be added. One for end < array.length, 707 // and one for null check on array (to hoist null check 708 // and array.length out of loop). 709 for (int i = 3 ; i <= end; i++) { 710 array[i] = 1; 711 sum += array[i]; 712 } 713 } 714 715 716 // CHECK-START: void Main.foo4(int[], int) BCE (before) 717 // CHECK: BoundsCheck 718 // CHECK: ArraySet 719 // CHECK-NOT: BoundsCheck 720 // CHECK: ArrayGet 721 722 // CHECK-START: void Main.foo4(int[], int) BCE (after) 723 // CHECK: Phi 724 // CHECK-NOT: BoundsCheck 725 // CHECK: ArraySet 726 // CHECK-NOT: BoundsCheck 727 // CHECK: ArrayGet 728 // Added blocks for deoptimization. 729 // CHECK: If 730 // CHECK: Goto 731 // CHECK: Deoptimize 732 // CHECK: Deoptimize 733 // CHECK-NOT: Deoptimize 734 // CHECK: Goto 735 // CHECK: Phi 736 // CHECK: Goto 737 738 void foo4(int[] array, int end) { 739 // Two HDeoptimize will be added. One for end <= array.length, 740 // and one for null check on array (to hoist null check 741 // and array.length out of loop). 742 for (int i = end ; i > 0; i--) { 743 array[i - 1] = 1; 744 sum += array[i - 1]; 745 } 746 } 747 748 749 // CHECK-START: void Main.foo5(int[], int) BCE (before) 750 // CHECK: BoundsCheck 751 // CHECK: ArraySet 752 // CHECK: BoundsCheck 753 // CHECK: ArrayGet 754 // CHECK: BoundsCheck 755 // CHECK: ArrayGet 756 // CHECK: BoundsCheck 757 // CHECK: ArrayGet 758 759 // CHECK-START: void Main.foo5(int[], int) BCE (after) 760 // CHECK-NOT: BoundsCheck 761 // CHECK: ArraySet 762 // CHECK: Phi 763 // CHECK-NOT: BoundsCheck 764 // CHECK: ArrayGet 765 // CHECK-NOT: BoundsCheck 766 // CHECK: ArrayGet 767 // CHECK-NOT: BoundsCheck 768 // CHECK: ArrayGet 769 // Added blocks for deoptimization. 770 // CHECK: If 771 // CHECK: Goto 772 // CHECK: Deoptimize 773 // CHECK-NOT: Deoptimize 774 // CHECK: Goto 775 // array.length is defined before the loop header so no phi is needed. 776 // CHECK-NOT: Phi 777 // CHECK: Goto 778 779 void foo5(int[] array, int end) { 780 // Bounds check in this loop can be eliminated without deoptimization. 781 for (int i = array.length - 1 ; i >= 0; i--) { 782 array[i] = 1; 783 } 784 // One HDeoptimize will be added. 785 // It's for (end - 2 <= array.length - 2). 786 for (int i = end - 2 ; i > 0; i--) { 787 sum += array[i - 1]; 788 sum += array[i]; 789 sum += array[i + 1]; 790 } 791 } 792 793 794 // CHECK-START: void Main.foo6(int[], int, int) BCE (before) 795 // CHECK: BoundsCheck 796 // CHECK: ArrayGet 797 // CHECK: BoundsCheck 798 // CHECK: ArrayGet 799 // CHECK: BoundsCheck 800 // CHECK: ArrayGet 801 // CHECK: BoundsCheck 802 // CHECK: ArrayGet 803 // CHECK: BoundsCheck 804 // CHECK: ArrayGet 805 // CHECK-NOT: BoundsCheck 806 // CHECK: ArraySet 807 808 // CHECK-START: void Main.foo6(int[], int, int) BCE (after) 809 // CHECK: Phi 810 // CHECK-NOT: BoundsCheck 811 // CHECK: ArrayGet 812 // CHECK-NOT: BoundsCheck 813 // CHECK: ArrayGet 814 // CHECK-NOT: BoundsCheck 815 // CHECK: ArrayGet 816 // CHECK-NOT: BoundsCheck 817 // CHECK: ArrayGet 818 // CHECK-NOT: BoundsCheck 819 // CHECK: ArrayGet 820 // CHECK-NOT: BoundsCheck 821 // CHECK: ArraySet 822 // Added blocks for deoptimization. 823 // CHECK: If 824 // CHECK: Goto 825 // CHECK: Deoptimize 826 // CHECK: Deoptimize 827 // CHECK: Deoptimize 828 // CHECK-NOT: Deoptimize 829 // CHECK: Goto 830 // CHECK: Phi 831 // CHECK: Goto 832 // CHECK-NOT: Deoptimize 833 834 void foo6(int[] array, int start, int end) { 835 // Three HDeoptimize will be added. One for 836 // start >= 2, one for end <= array.length - 3, 837 // and one for null check on array (to hoist null 838 // check and array.length out of loop). 839 for (int i = end; i >= start; i--) { 840 array[i] = (array[i-2] + array[i-1] + array[i] + array[i+1] + array[i+2]) / 5; 841 } 842 } 843 844 845 // CHECK-START: void Main.foo7(int[], int, int, boolean) BCE (before) 846 // CHECK: BoundsCheck 847 // CHECK: ArrayGet 848 // CHECK: BoundsCheck 849 // CHECK: ArrayGet 850 851 // CHECK-START: void Main.foo7(int[], int, int, boolean) BCE (after) 852 // CHECK: Phi 853 // CHECK: BoundsCheck 854 // CHECK: ArrayGet 855 // CHECK-NOT: BoundsCheck 856 // CHECK: ArrayGet 857 // Added blocks for deoptimization. 858 // CHECK: If 859 // CHECK: Goto 860 // CHECK: Deoptimize 861 // CHECK: Deoptimize 862 // CHECK: Deoptimize 863 // CHECK-NOT: Deoptimize 864 // CHECK: Goto 865 // CHECK: Phi 866 // CHECK: Goto 867 868 void foo7(int[] array, int start, int end, boolean lowEnd) { 869 // Three HDeoptimize will be added. One for 870 // start >= 0, one for end <= array.length, 871 // and one for null check on array (to hoist null 872 // check and array.length out of loop). 873 for (int i = start ; i < end; i++) { 874 if (lowEnd) { 875 // This array access isn't certain. So we don't 876 // use +1000 offset in decision making for deoptimization 877 // conditions. 878 sum += array[i + 1000]; 879 } 880 sum += array[i]; 881 } 882 } 883 884 885 // CHECK-START: void Main.foo8(int[][], int, int) BCE (before) 886 // CHECK: BoundsCheck 887 // CHECK: ArrayGet 888 // CHECK: BoundsCheck 889 // CHECK: ArraySet 890 891 // CHECK-START: void Main.foo8(int[][], int, int) BCE (after) 892 // CHECK: Phi 893 // CHECK-NOT: BoundsCheck 894 // CHECK: ArrayGet 895 // CHECK: Phi 896 // CHECK-NOT: BoundsCheck 897 // CHECK: ArraySet 898 // Added blocks for deoptimization. 899 // CHECK: If 900 // CHECK: Goto 901 // CHECK: Deoptimize 902 // CHECK: Deoptimize 903 // CHECK: Deoptimize 904 // CHECK: Deoptimize 905 // CHECK: Deoptimize 906 // CHECK: Deoptimize 907 // CHECK-NOT: Deoptimize 908 // CHECK: Goto 909 // CHECK: Phi 910 // CHECK: Goto 911 912 void foo8(int[][] matrix, int start, int end) { 913 // Three HDeoptimize will be added for the outer loop. 914 // start >= 0, end <= matrix.length, and null check on matrix. 915 // Three HDeoptimize will be added for the inner loop 916 // start >= 0 (TODO: this may be optimized away), 917 // end <= row.length, and null check on row. 918 for (int i = start; i < end; i++) { 919 int[] row = matrix[i]; 920 for (int j = start; j < end; j++) { 921 row[j] = 1; 922 } 923 } 924 } 925 926 927 // CHECK-START: void Main.foo9(int[]) BCE (before) 928 // CHECK: NullCheck 929 // CHECK: BoundsCheck 930 // CHECK: ArrayGet 931 932 // CHECK-START: void Main.foo9(int[]) BCE (after) 933 // The loop is guaranteed to be entered. No need to transform the 934 // loop for loop body entry test. 935 // CHECK: Deoptimize 936 // CHECK: Deoptimize 937 // CHECK-NOT: Deoptimize 938 // CHECK: Phi 939 // CHECK-NOT: NullCheck 940 // CHECK-NOT: BoundsCheck 941 // CHECK: ArrayGet 942 943 void foo9(int[] array) { 944 // Two HDeoptimize will be added. One for 945 // 10 <= array.length, and one for null check on array. 946 for (int i = 0 ; i < 10; i++) { 947 sum += array[i]; 948 } 949 } 950 951 952 // CHECK-START: void Main.partialLooping(int[], int, int) BCE (before) 953 // CHECK: BoundsCheck 954 // CHECK: ArraySet 955 956 // CHECK-START: void Main.partialLooping(int[], int, int) BCE (after) 957 // CHECK-NOT: Deoptimize 958 // CHECK: BoundsCheck 959 // CHECK: ArraySet 960 961 void partialLooping(int[] array, int start, int end) { 962 // This loop doesn't cover the full range of [start, end) so 963 // adding deoptimization is too aggressive, since end can be 964 // greater than array.length but the loop is never going to work on 965 // more than 2 elements. 966 for (int i = start; i < end; i++) { 967 if (i == 2) { 968 return; 969 } 970 array[i] = 1; 971 } 972 } 973 974 975 static void testUnknownBounds() { 976 boolean caught = false; 977 Main main = new Main(); 978 main.foo1(new int[10], 0, 10); 979 if (main.sum != 10) { 980 System.out.println("foo1 failed!"); 981 } 982 983 caught = false; 984 main = new Main(); 985 try { 986 main.foo1(new int[10], 0, 11); 987 } catch (ArrayIndexOutOfBoundsException e) { 988 caught = true; 989 } 990 if (!caught || main.sum != 10) { 991 System.out.println("foo1 exception failed!"); 992 } 993 994 main = new Main(); 995 main.foo2(new int[10], 0, 9); 996 if (main.sum != 10) { 997 System.out.println("foo2 failed!"); 998 } 999 1000 caught = false; 1001 main = new Main(); 1002 try { 1003 main.foo2(new int[10], 0, 10); 1004 } catch (ArrayIndexOutOfBoundsException e) { 1005 caught = true; 1006 } 1007 if (!caught || main.sum != 10) { 1008 System.out.println("foo2 exception failed!"); 1009 } 1010 1011 main = new Main(); 1012 main.foo3(new int[10], 9); 1013 if (main.sum != 7) { 1014 System.out.println("foo3 failed!"); 1015 } 1016 1017 caught = false; 1018 main = new Main(); 1019 try { 1020 main.foo3(new int[10], 10); 1021 } catch (ArrayIndexOutOfBoundsException e) { 1022 caught = true; 1023 } 1024 if (!caught || main.sum != 7) { 1025 System.out.println("foo3 exception failed!"); 1026 } 1027 1028 main = new Main(); 1029 main.foo4(new int[10], 10); 1030 if (main.sum != 10) { 1031 System.out.println("foo4 failed!"); 1032 } 1033 1034 caught = false; 1035 main = new Main(); 1036 try { 1037 main.foo4(new int[10], 11); 1038 } catch (ArrayIndexOutOfBoundsException e) { 1039 caught = true; 1040 } 1041 if (!caught || main.sum != 0) { 1042 System.out.println("foo4 exception failed!"); 1043 } 1044 1045 main = new Main(); 1046 main.foo5(new int[10], 10); 1047 if (main.sum != 24) { 1048 System.out.println("foo5 failed!"); 1049 } 1050 1051 caught = false; 1052 main = new Main(); 1053 try { 1054 main.foo5(new int[10], 11); 1055 } catch (ArrayIndexOutOfBoundsException e) { 1056 caught = true; 1057 } 1058 if (!caught || main.sum != 2) { 1059 System.out.println("foo5 exception failed!"); 1060 } 1061 1062 main = new Main(); 1063 main.foo6(new int[10], 2, 7); 1064 1065 main = new Main(); 1066 int[] array9 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 1067 main.foo9(array9); 1068 if (main.sum != 45) { 1069 System.out.println("foo9 failed!"); 1070 } 1071 1072 main = new Main(); 1073 int[] array = new int[4]; 1074 main.partialLooping(new int[3], 0, 4); 1075 if ((array[0] != 1) && (array[1] != 1) && 1076 (array[2] != 0) && (array[3] != 0)) { 1077 System.out.println("partialLooping failed!"); 1078 } 1079 1080 caught = false; 1081 main = new Main(); 1082 try { 1083 main.foo6(new int[10], 2, 8); 1084 } catch (ArrayIndexOutOfBoundsException e) { 1085 caught = true; 1086 } 1087 if (!caught) { 1088 System.out.println("foo6 exception failed!"); 1089 } 1090 1091 caught = false; 1092 main = new Main(); 1093 try { 1094 main.foo6(new int[10], 1, 7); 1095 } catch (ArrayIndexOutOfBoundsException e) { 1096 caught = true; 1097 } 1098 if (!caught) { 1099 System.out.println("foo6 exception failed!"); 1100 } 1101 1102 } 1103 1104 public void testExceptionMessage() { 1105 short[] B1 = new short[5]; 1106 int[] B2 = new int[5]; 1107 Exception err = null; 1108 try { 1109 testExceptionMessage1(B1, B2, null, -1, 6); 1110 } catch (Exception e) { 1111 err = e; 1112 } 1113 System.out.println(err); 1114 } 1115 1116 void testExceptionMessage1(short[] a1, int[] a2, long a3[], int start, int finish) { 1117 int j = finish + 77; 1118 // Bug: 22665511 1119 // A deoptimization will be triggered here right before the loop. Need to make 1120 // sure the value of j is preserved for the interpreter. 1121 for (int i = start; i <= finish; i++) { 1122 a2[j - 1] = a1[i + 1]; 1123 } 1124 } 1125 1126 // Make sure this method is compiled with optimizing. 1127 // CHECK-START: void Main.main(java.lang.String[]) register (after) 1128 // CHECK: ParallelMove 1129 1130 public static void main(String[] args) { 1131 sieve(20); 1132 1133 int[] array = {5, 2, 3, 7, 0, 1, 6, 4}; 1134 bubbleSort(array); 1135 for (int i = 0; i < 8; i++) { 1136 if (array[i] != i) { 1137 System.out.println("bubble sort failed!"); 1138 } 1139 } 1140 1141 array = new int[7]; 1142 pyramid1(array); 1143 if (!isPyramid(array)) { 1144 System.out.println("pyramid1 failed!"); 1145 } 1146 1147 array = new int[8]; 1148 pyramid2(array); 1149 if (!isPyramid(array)) { 1150 System.out.println("pyramid2 failed!"); 1151 } 1152 1153 java.util.Arrays.fill(array, -1); 1154 pyramid3(array); 1155 if (!isPyramid(array)) { 1156 System.out.println("pyramid3 failed!"); 1157 } 1158 1159 // Make sure this value is kept after deoptimization. 1160 int i = 1; 1161 if (foo() + i != 100) { 1162 System.out.println("foo failed!"); 1163 }; 1164 1165 testUnknownBounds(); 1166 new Main().testExceptionMessage(); 1167 } 1168 1169 } 1170
