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 
sieve(int size)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 
narrow(int[] array, int offset)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 
constantIndexing1(int[] array)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 
constantIndexing2(int[] array)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 
constantIndexing3(int[] array1, int[] array2, boolean copy)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.
constantIndexing4(int[] array)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 
constantIndexing5(int[] array)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 
loopPattern1(int[] array)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 
loopPattern2(int[] array)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 
loopPattern3(int[] array)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 
constantNewArray()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 
readData()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 
circularBufferProducer()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}.
pyramid1(int[] array)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}.
pyramid2(int[] array)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}.
pyramid3(int[] array)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 
isPyramid(int[] array)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 
bubbleSort(int[] array)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 
foo()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 
foo1(int[] array, int start, int end)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 
foo2(int[] array, int start, int end)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 
foo3(int[] array, int end)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 
foo4(int[] array, int end)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 
foo5(int[] array, int end)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 
foo6(int[] array, int start, int end)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 
foo7(int[] array, int start, int end, boolean lowEnd)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 
foo8(int[][] matrix, int start, int end)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 
foo9(int[] array)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 
partialLooping(int[] array, int start, int end)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 
testUnknownBounds()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 
testExceptionMessage()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 
testExceptionMessage1(short[] a1, int[] a2, long a3[], int start, int finish)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 
main(String[] args)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