Main.java revision bca381a12965a98e3727e93986dd0a195db500a0 
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
17public 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  // Make sure this method is compiled with optimizing.
1105  // CHECK-START: void Main.main(java.lang.String[]) register (after)
1106  // CHECK: ParallelMove
1107
1108  public static void main(String[] args) {
1109    sieve(20);
1110
1111    int[] array = {5, 2, 3, 7, 0, 1, 6, 4};
1112    bubbleSort(array);
1113    for (int i = 0; i < 8; i++) {
1114      if (array[i] != i) {
1115        System.out.println("bubble sort failed!");
1116      }
1117    }
1118
1119    array = new int[7];
1120    pyramid1(array);
1121    if (!isPyramid(array)) {
1122      System.out.println("pyramid1 failed!");
1123    }
1124
1125    array = new int[8];
1126    pyramid2(array);
1127    if (!isPyramid(array)) {
1128      System.out.println("pyramid2 failed!");
1129    }
1130
1131    java.util.Arrays.fill(array, -1);
1132    pyramid3(array);
1133    if (!isPyramid(array)) {
1134      System.out.println("pyramid3 failed!");
1135    }
1136
1137    // Make sure this value is kept after deoptimization.
1138    int i = 1;
1139    if (foo() + i != 100) {
1140      System.out.println("foo failed!");
1141    };
1142
1143    testUnknownBounds();
1144  }
1145
1146}
1147