Debian Codegraph @

test/530-checker-loops1/src/Main.java

raw
1 /*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 //
18 // Test on loop optimizations, in particular around common induction.
19 //
20 public class Main {
21
22 static int sResult;
23
24 //
25 // Various sequence variables used in bound checks.
26 //
27
28 /// CHECK-START: int Main.linear(int[]) BCE (before)
29 /// CHECK-DAG: BoundsCheck
30 //
31 /// CHECK-START: int Main.linear(int[]) BCE (after)
32 /// CHECK-NOT: BoundsCheck
33 /// CHECK-NOT: Deoptimize
34 private static int linear(int[] x) {
35 int result = 0;
36 for (int i = 0; i < x.length; i++) {
37 result += x[i];
38 }
39 return result;
40 }
41
42 /// CHECK-START: int Main.linearDown(int[]) BCE (before)
43 /// CHECK-DAG: BoundsCheck
44 //
45 /// CHECK-START: int Main.linearDown(int[]) BCE (after)
46 /// CHECK-NOT: BoundsCheck
47 /// CHECK-NOT: Deoptimize
48 private static int linearDown(int[] x) {
49 int result = 0;
50 for (int i = x.length - 1; i >= 0; i--) {
51 result += x[i];
52 }
53 return result;
54 }
55
56 /// CHECK-START: int Main.linearObscure(int[]) BCE (before)
57 /// CHECK-DAG: BoundsCheck
58 //
59 /// CHECK-START: int Main.linearObscure(int[]) BCE (after)
60 /// CHECK-NOT: BoundsCheck
61 /// CHECK-NOT: Deoptimize
62 private static int linearObscure(int[] x) {
63 int result = 0;
64 for (int i = x.length - 1; i >= 0; i--) {
65 int k = i + 5;
66 result += x[k - 5];
67 }
68 return result;
69 }
70
71 /// CHECK-START: int Main.linearVeryObscure(int[]) BCE (before)
72 /// CHECK-DAG: BoundsCheck
73 //
74 /// CHECK-START: int Main.linearVeryObscure(int[]) BCE (after)
75 /// CHECK-NOT: BoundsCheck
76 /// CHECK-NOT: Deoptimize
77 private static int linearVeryObscure(int[] x) {
78 int result = 0;
79 for (int i = 0; i < x.length; i++) {
80 int k = (-i) + (i << 5) + i - (32 * i) + 5 + (int) i;
81 result += x[k - 5];
82 }
83 return result;
84 }
85
86 /// CHECK-START: int Main.hiddenStride(int[]) BCE (before)
87 /// CHECK-DAG: BoundsCheck
88 //
89 /// CHECK-START: int Main.hiddenStride(int[]) BCE (after)
90 /// CHECK-NOT: BoundsCheck
91 /// CHECK-NOT: Deoptimize
92 static int hiddenStride(int[] a) {
93 int result = 0;
94 for (int i = 1; i <= 1; i++) {
95 // Obscured unit stride.
96 for (int j = 0; j < a.length; j += i) {
97 result += a[j];
98 }
99 }
100 return result;
101 }
102
103 /// CHECK-START: int Main.linearWhile(int[]) BCE (before)
104 /// CHECK-DAG: BoundsCheck
105 //
106 /// CHECK-START: int Main.linearWhile(int[]) BCE (after)
107 /// CHECK-NOT: BoundsCheck
108 /// CHECK-NOT: Deoptimize
109 private static int linearWhile(int[] x) {
110 int i = 0;
111 int result = 0;
112 while (i < x.length) {
113 result += x[i++];
114 }
115 return result;
116 }
117
118 /// CHECK-START: int Main.linearThreeWayPhi(int[]) BCE (before)
119 /// CHECK-DAG: BoundsCheck
120 //
121 /// CHECK-START: int Main.linearThreeWayPhi(int[]) BCE (after)
122 /// CHECK-NOT: BoundsCheck
123 /// CHECK-NOT: Deoptimize
124 private static int linearThreeWayPhi(int[] x) {
125 int result = 0;
126 for (int i = 0; i < x.length; ) {
127 if (x[i] == 5) {
128 i++;
129 continue;
130 }
131 result += x[i++];
132 }
133 return result;
134 }
135
136 /// CHECK-START: int Main.linearFourWayPhi(int[]) BCE (before)
137 /// CHECK-DAG: BoundsCheck
138 //
139 /// CHECK-START: int Main.linearFourWayPhi(int[]) BCE (after)
140 /// CHECK-NOT: BoundsCheck
141 /// CHECK-NOT: Deoptimize
142 private static int linearFourWayPhi(int[] x) {
143 int result = 0;
144 for (int i = 0; i < x.length; ) {
145 if (x[i] == 5) {
146 i++;
147 continue;
148 } else if (x[i] == 6) {
149 i++;
150 result += 7;
151 continue;
152 }
153 result += x[i++];
154 }
155 return result;
156 }
157
158 /// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (before)
159 /// CHECK-DAG: BoundsCheck
160 //
161 /// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (after)
162 /// CHECK-NOT: BoundsCheck
163 /// CHECK-NOT: Deoptimize
164 private static int wrapAroundThenLinear(int[] x) {
165 // Loop with wrap around (length - 1, 0, 1, 2, ..).
166 int w = x.length - 1;
167 int result = 0;
168 for (int i = 0; i < x.length; i++) {
169 result += x[w];
170 w = i;
171 }
172 return result;
173 }
174
175 /// CHECK-START: int Main.wrapAroundThenLinearThreeWayPhi(int[]) BCE (before)
176 /// CHECK-DAG: BoundsCheck
177 //
178 /// CHECK-START: int Main.wrapAroundThenLinearThreeWayPhi(int[]) BCE (after)
179 /// CHECK-NOT: BoundsCheck
180 /// CHECK-NOT: Deoptimize
181 private static int wrapAroundThenLinearThreeWayPhi(int[] x) {
182 // Loop with wrap around (length - 1, 0, 1, 2, ..).
183 int w = x.length - 1;
184 int result = 0;
185 for (int i = 0; i < x.length; ) {
186 if (x[w] == 1) {
187 w = i++;
188 continue;
189 }
190 result += x[w];
191 w = i++;
192 }
193 return result;
194 }
195
196 /// CHECK-START: int[] Main.linearWithParameter(int) BCE (before)
197 /// CHECK-DAG: BoundsCheck
198 //
199 /// CHECK-START: int[] Main.linearWithParameter(int) BCE (after)
200 /// CHECK-NOT: BoundsCheck
201 /// CHECK-NOT: Deoptimize
202 private static int[] linearWithParameter(int n) {
203 int[] x = new int[n];
204 for (int i = 0; i < n; i++) {
205 x[i] = i;
206 }
207 return x;
208 }
209
210 /// CHECK-START: int[] Main.linearCopy(int[]) BCE (before)
211 /// CHECK-DAG: BoundsCheck
212 //
213 /// CHECK-START: int[] Main.linearCopy(int[]) BCE (after)
214 /// CHECK-NOT: BoundsCheck
215 /// CHECK-NOT: Deoptimize
216 private static int[] linearCopy(int x[]) {
217 int n = x.length;
218 int y[] = new int[n];
219 for (int i = 0; i < n; i++) {
220 y[i] = x[i];
221 }
222 return y;
223 }
224
225 /// CHECK-START: int Main.linearByTwo(int[]) BCE (before)
226 /// CHECK-DAG: BoundsCheck
227 /// CHECK-DAG: BoundsCheck
228 //
229 /// CHECK-START: int Main.linearByTwo(int[]) BCE (after)
230 /// CHECK-NOT: BoundsCheck
231 /// CHECK-NOT: Deoptimize
232 private static int linearByTwo(int x[]) {
233 int n = x.length / 2;
234 int result = 0;
235 for (int i = 0; i < n; i++) {
236 int ii = i << 1;
237 result += x[ii];
238 result += x[ii + 1];
239 }
240 return result;
241 }
242
243 /// CHECK-START: int Main.linearByTwoSkip1(int[]) BCE (before)
244 /// CHECK-DAG: BoundsCheck
245 //
246 /// CHECK-START: int Main.linearByTwoSkip1(int[]) BCE (after)
247 /// CHECK-NOT: BoundsCheck
248 /// CHECK-NOT: Deoptimize
249 private static int linearByTwoSkip1(int x[]) {
250 int result = 0;
251 for (int i = 0; i < x.length / 2; i++) {
252 result += x[2 * i];
253 }
254 return result;
255 }
256
257 /// CHECK-START: int Main.linearByTwoSkip2(int[]) BCE (before)
258 /// CHECK-DAG: BoundsCheck
259 //
260 /// CHECK-START: int Main.linearByTwoSkip2(int[]) BCE (after)
261 /// CHECK-DAG: BoundsCheck
262 //
263 /// CHECK-START: int Main.linearByTwoSkip2(int[]) BCE (after)
264 /// CHECK-NOT: Deoptimize
265 private static int linearByTwoSkip2(int x[]) {
266 int result = 0;
267 // This case is not optimized.
268 for (int i = 0; i < x.length; i+=2) {
269 result += x[i];
270 }
271 return result;
272 }
273
274 /// CHECK-START: int Main.linearWithCompoundStride() BCE (before)
275 /// CHECK-DAG: BoundsCheck
276 //
277 /// CHECK-START: int Main.linearWithCompoundStride() BCE (after)
278 /// CHECK-NOT: BoundsCheck
279 /// CHECK-NOT: Deoptimize
280 private static int linearWithCompoundStride() {
281 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
282 int result = 0;
283 for (int i = 0; i <= 12; ) {
284 i++;
285 result += x[i];
286 i++;
287 }
288 return result;
289 }
290
291 /// CHECK-START: int Main.linearWithLargePositiveStride() BCE (before)
292 /// CHECK-DAG: BoundsCheck
293 //
294 /// CHECK-START: int Main.linearWithLargePositiveStride() BCE (after)
295 /// CHECK-NOT: BoundsCheck
296 /// CHECK-NOT: Deoptimize
297 private static int linearWithLargePositiveStride() {
298 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
299 int result = 0;
300 int k = 0;
301 // Range analysis has no problem with a trip-count defined by a
302 // reasonably large positive stride far away from upper bound.
303 for (int i = 1; i <= 10 * 10000000 + 1; i += 10000000) {
304 result += x[k++];
305 }
306 return result;
307 }
308
309 /// CHECK-START: int Main.linearWithVeryLargePositiveStride() BCE (before)
310 /// CHECK-DAG: BoundsCheck
311 //
312 /// CHECK-START: int Main.linearWithVeryLargePositiveStride() BCE (after)
313 /// CHECK-DAG: BoundsCheck
314 //
315 /// CHECK-START: int Main.linearWithVeryLargePositiveStride() BCE (after)
316 /// CHECK-NOT: Deoptimize
317 private static int linearWithVeryLargePositiveStride() {
318 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
319 int result = 0;
320 int k = 0;
321 // Range analysis conservatively bails due to potential of wrap-around
322 // arithmetic while computing the trip-count for this very large stride.
323 for (int i = 1; i < Integer.MAX_VALUE; i += 195225786) {
324 result += x[k++];
325 }
326 return result;
327 }
328
329 /// CHECK-START: int Main.linearWithLargeNegativeStride() BCE (before)
330 /// CHECK-DAG: BoundsCheck
331 //
332 /// CHECK-START: int Main.linearWithLargeNegativeStride() BCE (after)
333 /// CHECK-NOT: BoundsCheck
334 /// CHECK-NOT: Deoptimize
335 private static int linearWithLargeNegativeStride() {
336 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
337 int result = 0;
338 int k = 0;
339 // Range analysis has no problem with a trip-count defined by a
340 // reasonably large negative stride far away from lower bound.
341 for (int i = -1; i >= -10 * 10000000 - 1; i -= 10000000) {
342 result += x[k++];
343 }
344 return result;
345 }
346
347 /// CHECK-START: int Main.linearWithVeryLargeNegativeStride() BCE (before)
348 /// CHECK-DAG: BoundsCheck
349 //
350 /// CHECK-START: int Main.linearWithVeryLargeNegativeStride() BCE (after)
351 /// CHECK-DAG: BoundsCheck
352 //
353 /// CHECK-START: int Main.linearWithVeryLargeNegativeStride() BCE (after)
354 /// CHECK-NOT: Deoptimize
355 private static int linearWithVeryLargeNegativeStride() {
356 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
357 int result = 0;
358 int k = 0;
359 // Range analysis conservatively bails due to potential of wrap-around
360 // arithmetic while computing the trip-count for this very large stride.
361 for (int i = -2; i > Integer.MIN_VALUE; i -= 195225786) {
362 result += x[k++];
363 }
364 return result;
365 }
366
367 /// CHECK-START: int Main.linearForNEUp() BCE (before)
368 /// CHECK-DAG: BoundsCheck
369 //
370 /// CHECK-START: int Main.linearForNEUp() BCE (after)
371 /// CHECK-NOT: BoundsCheck
372 /// CHECK-NOT: Deoptimize
373 private static int linearForNEUp() {
374 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
375 int result = 0;
376 for (int i = 0; i != 10; i++) {
377 result += x[i];
378 }
379 return result;
380 }
381
382 /// CHECK-START: int Main.linearForNEDown() BCE (before)
383 /// CHECK-DAG: BoundsCheck
384 //
385 /// CHECK-START: int Main.linearForNEDown() BCE (after)
386 /// CHECK-NOT: BoundsCheck
387 /// CHECK-NOT: Deoptimize
388 private static int linearForNEDown() {
389 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
390 int result = 0;
391 for (int i = 9; i != -1; i--) {
392 result += x[i];
393 }
394 return result;
395 }
396
397 /// CHECK-START: int Main.linearForNEArrayLengthUp(int[]) BCE (before)
398 /// CHECK-DAG: BoundsCheck
399 //
400 /// CHECK-START: int Main.linearForNEArrayLengthUp(int[]) BCE (after)
401 /// CHECK-NOT: BoundsCheck
402 /// CHECK-NOT: Deoptimize
403 private static int linearForNEArrayLengthUp(int[] x) {
404 int result = 0;
405 for (int i = 0; i != x.length; i++) {
406 result += x[i];
407 }
408 return result;
409 }
410
411 /// CHECK-START: int Main.linearForNEArrayLengthDown(int[]) BCE (before)
412 /// CHECK-DAG: BoundsCheck
413 //
414 /// CHECK-START: int Main.linearForNEArrayLengthDown(int[]) BCE (after)
415 /// CHECK-NOT: BoundsCheck
416 /// CHECK-NOT: Deoptimize
417 private static int linearForNEArrayLengthDown(int[] x) {
418 int result = 0;
419 for (int i = x.length - 1; i != -1; i--) {
420 result += x[i];
421 }
422 return result;
423 }
424
425 /// CHECK-START: int Main.linearDoWhileUp() BCE (before)
426 /// CHECK-DAG: BoundsCheck
427 //
428 /// CHECK-START: int Main.linearDoWhileUp() BCE (after)
429 /// CHECK-NOT: BoundsCheck
430 /// CHECK-NOT: Deoptimize
431 private static int linearDoWhileUp() {
432 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
433 int result = 0;
434 int i = 0;
435 do {
436 result += x[i++];
437 } while (i < 10);
438 return result;
439 }
440
441 /// CHECK-START: int Main.linearDoWhileDown() BCE (before)
442 /// CHECK-DAG: BoundsCheck
443 //
444 /// CHECK-START: int Main.linearDoWhileDown() BCE (after)
445 /// CHECK-NOT: BoundsCheck
446 /// CHECK-NOT: Deoptimize
447 private static int linearDoWhileDown() {
448 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
449 int result = 0;
450 int i = 9;
451 do {
452 result += x[i--];
453 } while (0 <= i);
454 return result;
455 }
456
457 /// CHECK-START: int Main.linearLong() BCE (before)
458 /// CHECK-DAG: BoundsCheck
459 //
460 /// CHECK-START: int Main.linearLong() BCE (after)
461 /// CHECK-NOT: BoundsCheck
462 /// CHECK-NOT: Deoptimize
463 private static int linearLong() {
464 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
465 int result = 0;
466 // Induction on constant interval is done in higher precision than necessary,
467 // but truncated at the use as subscript.
468 for (long i = 0; i < 10; i++) {
469 result += x[(int)i];
470 }
471 return result;
472 }
473
474 /// CHECK-START: int Main.linearLongAlt(int[]) BCE (before)
475 /// CHECK-DAG: BoundsCheck
476 //
477 /// CHECK-START: int Main.linearLongAlt(int[]) BCE (after)
478 /// CHECK-NOT: BoundsCheck
479 /// CHECK-NOT: Deoptimize
480 private static int linearLongAlt(int[] x) {
481 int result = 0;
482 // Induction on array length is done in higher precision than necessary,
483 // but truncated at the use as subscript.
484 for (long i = 0; i < x.length; i++) {
485 result += x[(int)i];
486 }
487 return result;
488 }
489
490 /// CHECK-START: int Main.linearShort() BCE (before)
491 /// CHECK-DAG: BoundsCheck
492 //
493 /// CHECK-START: int Main.linearShort() BCE (after)
494 /// CHECK-NOT: BoundsCheck
495 /// CHECK-NOT: Deoptimize
496 private static int linearShort() {
497 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
498 int result = 0;
499 // Induction is done in short precision, but fits.
500 for (short i = 0; i < 10; i++) {
501 result += x[i];
502 }
503 return result;
504 }
505
506 /// CHECK-START: int Main.linearChar() BCE (before)
507 /// CHECK-DAG: BoundsCheck
508 //
509 /// CHECK-START: int Main.linearChar() BCE (after)
510 /// CHECK-NOT: BoundsCheck
511 /// CHECK-NOT: Deoptimize
512 private static int linearChar() {
513 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
514 int result = 0;
515 // Induction is done in char precision, but fits.
516 for (char i = 0; i < 10; i++) {
517 result += x[i];
518 }
519 return result;
520 }
521
522 /// CHECK-START: int Main.linearByte() BCE (before)
523 /// CHECK-DAG: BoundsCheck
524 //
525 /// CHECK-START: int Main.linearByte() BCE (after)
526 /// CHECK-NOT: BoundsCheck
527 /// CHECK-NOT: Deoptimize
528 private static int linearByte() {
529 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
530 int result = 0;
531 // Induction is done in byte precision, but fits.
532 for (byte i = 0; i < 10; i++) {
533 result += x[i];
534 }
535 return result;
536 }
537
538 /// CHECK-START: int Main.invariantFromPreLoop(int[], int) BCE (before)
539 /// CHECK-DAG: BoundsCheck
540 //
541 /// CHECK-START: int Main.invariantFromPreLoop(int[], int) BCE (after)
542 /// CHECK-NOT: BoundsCheck
543 /// CHECK-NOT: Deoptimize
544 private static int invariantFromPreLoop(int[] x, int y) {
545 int result = 0;
546 // Strange pre-loop that sets upper bound.
547 int hi;
548 while (true) {
549 y = y % 3;
550 hi = x.length;
551 if (y != 123) break;
552 }
553 for (int i = 0; i < hi; i++) {
554 result += x[i];
555 }
556 return result;
557 }
558
559 /// CHECK-START: void Main.linearTriangularOnTwoArrayLengths(int) BCE (before)
560 /// CHECK-DAG: BoundsCheck
561 /// CHECK-DAG: BoundsCheck
562 //
563 /// CHECK-START: void Main.linearTriangularOnTwoArrayLengths(int) BCE (after)
564 /// CHECK-NOT: BoundsCheck
565 /// CHECK-NOT: Deoptimize
566 private static void linearTriangularOnTwoArrayLengths(int n) {
567 int[] a = new int[n];
568 for (int i = 0; i < a.length; i++) {
569 int[] b = new int[i];
570 for (int j = 0; j < b.length; j++) {
571 // Need to know j < b.length < a.length for static bce.
572 a[j] += 1;
573 // Need to know just j < b.length for static bce.
574 b[j] += 1;
575 }
576 verifyTriangular(a, b, i, n);
577 }
578 }
579
580 /// CHECK-START: void Main.linearTriangularOnOneArrayLength(int) BCE (before)
581 /// CHECK-DAG: BoundsCheck
582 /// CHECK-DAG: BoundsCheck
583 //
584 /// CHECK-START: void Main.linearTriangularOnOneArrayLength(int) BCE (after)
585 /// CHECK-NOT: BoundsCheck
586 /// CHECK-NOT: Deoptimize
587 private static void linearTriangularOnOneArrayLength(int n) {
588 int[] a = new int[n];
589 for (int i = 0; i < a.length; i++) {
590 int[] b = new int[i];
591 for (int j = 0; j < i; j++) {
592 // Need to know j < i < a.length for static bce.
593 a[j] += 1;
594 // Need to know just j < i for static bce.
595 b[j] += 1;
596 }
597 verifyTriangular(a, b, i, n);
598 }
599 }
600
601 /// CHECK-START: void Main.linearTriangularOnParameter(int) BCE (before)
602 /// CHECK-DAG: BoundsCheck
603 /// CHECK-DAG: BoundsCheck
604 //
605 /// CHECK-START: void Main.linearTriangularOnParameter(int) BCE (after)
606 /// CHECK-NOT: BoundsCheck
607 /// CHECK-NOT: Deoptimize
608 private static void linearTriangularOnParameter(int n) {
609 int[] a = new int[n];
610 for (int i = 0; i < n; i++) {
611 int[] b = new int[i];
612 for (int j = 0; j < i; j++) {
613 // Need to know j < i < n for static bce.
614 a[j] += 1;
615 // Need to know just j < i for static bce.
616 b[j] += 1;
617 }
618 verifyTriangular(a, b, i, n);
619 }
620 }
621
622 /// CHECK-START: void Main.linearTriangularStrictLower(int) BCE (before)
623 /// CHECK-DAG: BoundsCheck
624 /// CHECK-DAG: BoundsCheck
625 /// CHECK-DAG: BoundsCheck
626 /// CHECK-DAG: BoundsCheck
627 //
628 /// CHECK-START: void Main.linearTriangularStrictLower(int) BCE (after)
629 /// CHECK-NOT: BoundsCheck
630 /// CHECK-NOT: Deoptimize
631 private static void linearTriangularStrictLower(int n) {
632 int[] a = new int[n];
633 for (int i = 0; i < n; i++) {
634 for (int j = 0; j < i; j++) {
635 a[j] += 1;
636 }
637 for (int j = i - 1; j >= 0; j--) {
638 a[j] += 1;
639 }
640 for (int j = i; j < n; j++) {
641 a[j] += 1;
642 }
643 for (int j = n - 1; j >= i; j--) {
644 a[j] += 1;
645 }
646 }
647 verifyTriangular(a);
648 }
649
650 /// CHECK-START: void Main.linearTriangularStrictUpper(int) BCE (before)
651 /// CHECK-DAG: BoundsCheck
652 /// CHECK-DAG: BoundsCheck
653 /// CHECK-DAG: BoundsCheck
654 /// CHECK-DAG: BoundsCheck
655 //
656 /// CHECK-START: void Main.linearTriangularStrictUpper(int) BCE (after)
657 /// CHECK-NOT: BoundsCheck
658 /// CHECK-NOT: Deoptimize
659 private static void linearTriangularStrictUpper(int n) {
660 int[] a = new int[n];
661 for (int i = 0; i < n; i++) {
662 for (int j = 0; j <= i; j++) {
663 a[j] += 1;
664 }
665 for (int j = i; j >= 0; j--) {
666 a[j] += 1;
667 }
668 for (int j = i + 1; j < n; j++) {
669 a[j] += 1;
670 }
671 for (int j = n - 1; j >= i + 1; j--) {
672 a[j] += 1;
673 }
674 }
675 verifyTriangular(a);
676 }
677
678 // Verifier for triangular loops.
679 private static void verifyTriangular(int[] a, int[] b, int m, int n) {
680 expectEquals(n, a.length);
681 for (int i = 0, k = m; i < n; i++) {
682 expectEquals(a[i], k);
683 if (k > 0) k--;
684 }
685 expectEquals(m, b.length);
686 for (int i = 0; i < m; i++) {
687 expectEquals(b[i], 1);
688 }
689 }
690
691 // Verifier for triangular loops.
692 private static void verifyTriangular(int[] a) {
693 int n = a.length;
694 for (int i = 0; i < n; i++) {
695 expectEquals(a[i], n + n);
696 }
697 }
698
699 /// CHECK-START: int[] Main.linearTriangularOOB() BCE (before)
700 /// CHECK-DAG: BoundsCheck
701 //
702 /// CHECK-START: int[] Main.linearTriangularOOB() BCE (after)
703 /// CHECK-DAG: BoundsCheck
704 //
705 /// CHECK-START: int[] Main.linearTriangularOOB() BCE (after)
706 /// CHECK-NOT: Deoptimize
707 private static int[] linearTriangularOOB() {
708 int[] a = new int[200];
709 try {
710 for (int i = 0; i < 200; i++) {
711 // Lower bound must be recognized as lower precision induction with arithmetic
712 // wrap-around to -128 when i exceeds 127.
713 for (int j = (byte) i; j < 200; j++) {
714 a[j] += 1;
715 }
716 }
717 } catch (ArrayIndexOutOfBoundsException e) {
718 return a;
719 }
720 return null; // failure if this is reached
721 }
722
723 //
724 // Verifier.
725 //
726
727 public static void main(String[] args) {
728 int[] empty = { };
729 int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
730
731 // Linear and wrap-around.
732 expectEquals(0, linear(empty));
733 expectEquals(55, linear(x));
734 expectEquals(0, linearDown(empty));
735 expectEquals(55, linearDown(x));
736 expectEquals(0, linearObscure(empty));
737 expectEquals(55, linearObscure(x));
738 expectEquals(0, linearVeryObscure(empty));
739 expectEquals(55, linearVeryObscure(x));
740 expectEquals(0, hiddenStride(empty));
741 expectEquals(55, hiddenStride(x));
742 expectEquals(0, linearWhile(empty));
743 expectEquals(55, linearWhile(x));
744 expectEquals(0, linearThreeWayPhi(empty));
745 expectEquals(50, linearThreeWayPhi(x));
746 expectEquals(0, linearFourWayPhi(empty));
747 expectEquals(51, linearFourWayPhi(x));
748 expectEquals(0, wrapAroundThenLinear(empty));
749 expectEquals(55, wrapAroundThenLinear(x));
750 expectEquals(0, wrapAroundThenLinearThreeWayPhi(empty));
751 expectEquals(54, wrapAroundThenLinearThreeWayPhi(x));
752
753 // Linear with parameter.
754 sResult = 0;
755 try {
756 linearWithParameter(-1);
757 } catch (NegativeArraySizeException e) {
758 sResult = 1;
759 }
760 expectEquals(1, sResult);
761 for (int n = 0; n < 32; n++) {
762 int[] r = linearWithParameter(n);
763 expectEquals(n, r.length);
764 for (int i = 0; i < n; i++) {
765 expectEquals(i, r[i]);
766 }
767 }
768
769 // Linear copy.
770 expectEquals(0, linearCopy(empty).length);
771 {
772 int[] r = linearCopy(x);
773 expectEquals(x.length, r.length);
774 for (int i = 0; i < x.length; i++) {
775 expectEquals(x[i], r[i]);
776 }
777 }
778
779 // Linear with non-unit strides.
780 expectEquals(55, linearByTwo(x));
781 expectEquals(25, linearByTwoSkip1(x));
782 expectEquals(25, linearByTwoSkip2(x));
783 expectEquals(56, linearWithCompoundStride());
784 expectEquals(66, linearWithLargePositiveStride());
785 expectEquals(66, linearWithVeryLargePositiveStride());
786 expectEquals(66, linearWithLargeNegativeStride());
787 expectEquals(66, linearWithVeryLargeNegativeStride());
788
789 // Special forms.
790 expectEquals(55, linearForNEUp());
791 expectEquals(55, linearForNEDown());
792 expectEquals(55, linearForNEArrayLengthUp(x));
793 expectEquals(55, linearForNEArrayLengthDown(x));
794 expectEquals(55, linearDoWhileUp());
795 expectEquals(55, linearDoWhileDown());
796 expectEquals(55, linearLong());
797 expectEquals(55, linearLongAlt(x));
798 expectEquals(55, linearShort());
799 expectEquals(55, linearChar());
800 expectEquals(55, linearByte());
801 expectEquals(55, invariantFromPreLoop(x, 1));
802 linearTriangularOnTwoArrayLengths(10);
803 linearTriangularOnOneArrayLength(10);
804 linearTriangularOnParameter(10);
805 linearTriangularStrictLower(10);
806 linearTriangularStrictUpper(10);
807 {
808 int[] t = linearTriangularOOB();
809 for (int i = 0; i < 200; i++) {
810 expectEquals(i <= 127 ? i + 1 : 128, t[i]);
811 }
812 }
813
814 System.out.println("passed");
815 }
816
817 private static void expectEquals(int expected, int result) {
818 if (expected != result) {
819 throw new Error("Expected: " + expected + ", found: " + result);
820 }
821 }
822 }