Debian Codegraph @

test/618-checker-induction/src/Main.java

raw
1 /*
2 * Copyright (C) 2016 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 * Tests on loop optimizations related to induction.
19 */
20 public class Main {
21
22 static int[] a = new int[10];
23
24 static int[] novec = new int[20]; // to prevent vectorization
25
26 /// CHECK-START: void Main.deadSingleLoop() loop_optimization (before)
27 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
28 //
29 /// CHECK-START: void Main.deadSingleLoop() loop_optimization (after)
30 /// CHECK-NOT: Phi
31 static void deadSingleLoop() {
32 for (int i = 0; i < 4; i++) {
33 }
34 }
35
36 /// CHECK-START: void Main.deadSingleLoop() loop_optimization (before)
37 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
38 //
39 /// CHECK-START: void Main.deadSingleLoop() loop_optimization (after)
40 /// CHECK-NOT: Phi
41 static void deadSingleLoopN(int n) {
42 for (int i = 0; i < n; i++) {
43 }
44 }
45
46 /// CHECK-START: void Main.potentialInfiniteLoop(int) loop_optimization (before)
47 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
48 //
49 /// CHECK-START: void Main.potentialInfiniteLoop(int) loop_optimization (after)
50 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
51 static void potentialInfiniteLoop(int n) {
52 for (int i = 0; i <= n; i++) { // loops forever when n = MAX_INT
53 }
54 }
55
56 /// CHECK-START: void Main.deadNestedLoops() loop_optimization (before)
57 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
58 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop>>
59 //
60 /// CHECK-START: void Main.deadNestedLoops() loop_optimization (after)
61 /// CHECK-NOT: Phi
62 static void deadNestedLoops() {
63 for (int i = 0; i < 4; i++) {
64 for (int j = 0; j < 4; j++) {
65 }
66 }
67 }
68
69 /// CHECK-START: void Main.deadNestedAndFollowingLoops() loop_optimization (before)
70 /// CHECK-DAG: Phi loop:<<Loop1:B\d+>> outer_loop:none
71 /// CHECK-DAG: Phi loop:<<Loop2:B\d+>> outer_loop:<<Loop1>>
72 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop2>>
73 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop2>>
74 /// CHECK-DAG: Phi loop:<<Loop3:B\d+>> outer_loop:<<Loop1>>
75 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop3>>
76 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
77 //
78 /// CHECK-START: void Main.deadNestedAndFollowingLoops() loop_optimization (after)
79 /// CHECK-NOT: Phi
80 static void deadNestedAndFollowingLoops() {
81 for (int i = 0; i < 4; i++) {
82 for (int j = 0; j < 4; j++) {
83 for (int k = 0; k < 4; k++) {
84 }
85 for (int k = 0; k < 4; k++) {
86 }
87 }
88 for (int j = 0; j < 4; j++) {
89 for (int k = 0; k < 4; k++) {
90 }
91 }
92 }
93 for (int i = 0; i < 4; i++) {
94 }
95 }
96
97 /// CHECK-START: void Main.deadConditional(int) loop_optimization (before)
98 /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
99 //
100 /// CHECK-START: void Main.deadConditional(int) loop_optimization (after)
101 /// CHECK-NOT: Phi
102 public static void deadConditional(int n) {
103 int k = 0;
104 int m = 0;
105 for (int i = 0; i < n; i++) {
106 if (i == 3)
107 k = i;
108 else
109 m = i;
110 }
111 }
112
113 /// CHECK-START: void Main.deadConditionalCycle(int) loop_optimization (before)
114 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
115 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
116 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
117 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
118 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
119 //
120 /// CHECK-START: void Main.deadConditionalCycle(int) loop_optimization (after)
121 /// CHECK-NOT: Phi
122 public static void deadConditionalCycle(int n) {
123 int k = 0;
124 int m = 0;
125 for (int i = 0; i < n; i++) {
126 if (i == 3)
127 k--;
128 else
129 m++;
130 }
131 }
132
133
134 /// CHECK-START: void Main.deadInduction() loop_optimization (before)
135 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
136 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
137 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
138 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
139 //
140 /// CHECK-START: void Main.deadInduction() loop_optimization (after)
141 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
142 /// CHECK-NOT: Phi loop:<<Loop>> outer_loop:none
143 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
144 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
145 static void deadInduction() {
146 int dead = 0;
147 for (int i = 0; i < a.length; i++) {
148 a[i] = novec[2 * i] + 1;
149 dead += 5;
150 }
151 }
152
153 /// CHECK-START: void Main.deadManyInduction() loop_optimization (before)
154 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
155 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
156 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
157 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
158 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
159 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
160 //
161 /// CHECK-START: void Main.deadManyInduction() loop_optimization (after)
162 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
163 /// CHECK-NOT: Phi loop:<<Loop>> outer_loop:none
164 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
165 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
166 static void deadManyInduction() {
167 int dead1 = 0, dead2 = 1, dead3 = 3;
168 for (int i = 0; i < a.length; i++) {
169 dead1 += 5;
170 a[i] = novec[2 * i] + 2;
171 dead2 += 10;
172 dead3 += 100;
173 }
174 }
175
176 /// CHECK-START: void Main.deadSequence() loop_optimization (before)
177 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
178 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
179 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
180 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
181 //
182 /// CHECK-START: void Main.deadSequence() loop_optimization (after)
183 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
184 /// CHECK-NOT: Phi loop:<<Loop>> outer_loop:none
185 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
186 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
187 static void deadSequence() {
188 int dead = 0;
189 for (int i = 0; i < a.length; i++) {
190 a[i] = novec[2 * i] + 3;
191 // Increment value defined inside loop,
192 // but sequence itself not used anywhere.
193 dead += i;
194 }
195 }
196
197 /// CHECK-START: void Main.deadCycleWithException(int) loop_optimization (before)
198 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
199 /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none
200 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
201 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
202 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
203 /// CHECK-NOT: BoundsCheck
204 //
205 /// CHECK-START: void Main.deadCycleWithException(int) loop_optimization (after)
206 /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
207 /// CHECK-NOT: Phi loop:<<Loop>> outer_loop:none
208 /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none
209 /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none
210 /// CHECK-NOT: ArrayGet loop:<<Loop>> outer_loop:none
211 static void deadCycleWithException(int k) {
212 int dead = 0;
213 for (int i = 0; i < a.length; i++) {
214 a[i] = novec[2 * i] + 4;
215 // Increment value of dead cycle may throw exception. Dynamic
216 // BCE takes care of the bounds check though, which enables
217 // removing the ArrayGet after removing the dead cycle.
218 dead += a[k];
219 }
220 }
221
222 /// CHECK-START: int Main.closedFormInductionUp() loop_optimization (before)
223 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
224 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
225 /// CHECK-DAG: Return [<<Phi1>>] loop:none
226 //
227 /// CHECK-START: int Main.closedFormInductionUp() loop_optimization (after)
228 /// CHECK-NOT: Phi
229 //
230 /// CHECK-START: int Main.closedFormInductionUp() instruction_simplifier$before_codegen (after)
231 /// CHECK-DAG: <<Int:i\d+>> IntConstant 12395 loop:none
232 /// CHECK-DAG: Return [<<Int>>] loop:none
233 static int closedFormInductionUp() {
234 int closed = 12345;
235 for (int i = 0; i < 10; i++) {
236 closed += 5;
237 }
238 return closed; // only needs last value
239 }
240
241 /// CHECK-START: int Main.closedFormInductionInAndDown(int) loop_optimization (before)
242 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
243 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
244 /// CHECK-DAG: Return [<<Phi2>>] loop:none
245 //
246 /// CHECK-START: int Main.closedFormInductionInAndDown(int) loop_optimization (after)
247 /// CHECK-NOT: Phi
248 //
249 /// CHECK-START: int Main.closedFormInductionInAndDown(int) instruction_simplifier$before_codegen (after)
250 /// CHECK-DAG: <<Par:i\d+>> ParameterValue loop:none
251 /// CHECK-DAG: <<Int:i\d+>> IntConstant -50 loop:none
252 /// CHECK-DAG: <<Add:i\d+>> Add [<<Int>>,<<Par>>] loop:none
253 /// CHECK-DAG: Return [<<Add>>] loop:none
254 static int closedFormInductionInAndDown(int closed) {
255 for (int i = 0; i < 10; i++) {
256 closed -= 5;
257 }
258 return closed; // only needs last value
259 }
260
261 /// CHECK-START: int Main.closedFormInductionTrivialIf() loop_optimization (before)
262 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
263 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
264 /// CHECK-DAG: Select loop:<<Loop>> outer_loop:none
265 /// CHECK-DAG: Return [<<Phi1>>] loop:none
266 //
267 /// CHECK-START: int Main.closedFormInductionTrivialIf() loop_optimization (after)
268 /// CHECK-NOT: Phi
269 /// CHECK-NOT: Select
270 //
271 /// CHECK-START: int Main.closedFormInductionTrivialIf() instruction_simplifier$before_codegen (after)
272 /// CHECK-DAG: <<Int:i\d+>> IntConstant 81 loop:none
273 /// CHECK-DAG: Return [<<Int>>] loop:none
274 static int closedFormInductionTrivialIf() {
275 int closed = 11;
276 for (int i = 0; i < 10; i++) {
277 // Trivial if becomes trivial select at HIR level.
278 // Make sure this is still recognized as induction.
279 if (i < 5) {
280 closed += 7;
281 } else {
282 closed += 7;
283 }
284 }
285 return closed; // only needs last value
286 }
287
288 /// CHECK-START: int Main.closedFormNested() loop_optimization (before)
289 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none
290 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop1>> outer_loop:none
291 /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop2:B\d+>> outer_loop:<<Loop1>>
292 /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop2>> outer_loop:<<Loop1>>
293 /// CHECK-DAG: Return [<<Phi1>>] loop:none
294 //
295 /// CHECK-START: int Main.closedFormNested() loop_optimization (after)
296 /// CHECK-NOT: Phi
297 //
298 /// CHECK-START: int Main.closedFormNested() instruction_simplifier$before_codegen (after)
299 /// CHECK-DAG: <<Int:i\d+>> IntConstant 100 loop:none
300 /// CHECK-DAG: Return [<<Int>>] loop:none
301 static int closedFormNested() {
302 int closed = 0;
303 for (int i = 0; i < 10; i++) {
304 for (int j = 0; j < 10; j++) {
305 closed++;
306 }
307 }
308 return closed; // only needs last-value
309 }
310
311 /// CHECK-START: int Main.closedFormNestedAlt() loop_optimization (before)
312 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none
313 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop1>> outer_loop:none
314 /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop2:B\d+>> outer_loop:<<Loop1>>
315 /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop2>> outer_loop:<<Loop1>>
316 /// CHECK-DAG: Return [<<Phi1>>] loop:none
317 //
318 /// CHECK-START: int Main.closedFormNestedAlt() loop_optimization (after)
319 /// CHECK-NOT: Phi
320 //
321 /// CHECK-START: int Main.closedFormNestedAlt() instruction_simplifier$before_codegen (after)
322 /// CHECK-DAG: <<Int:i\d+>> IntConstant 15082 loop:none
323 /// CHECK-DAG: Return [<<Int>>] loop:none
324 static int closedFormNestedAlt() {
325 int closed = 12345;
326 for (int i = 0; i < 17; i++) {
327 for (int j = 0; j < 23; j++) {
328 closed += 7;
329 }
330 }
331 return closed; // only needs last-value
332 }
333
334 // TODO: taken test around closed form?
335 static int closedFormInductionUpN(int n) {
336 int closed = 12345;
337 for (int i = 0; i < n; i++) {
338 closed += 5;
339 }
340 return closed; // only needs last value
341 }
342
343 // TODO: taken test around closed form?
344 static int closedFormInductionInAndDownN(int closed, int n) {
345 for (int i = 0; i < n; i++) {
346 closed -= 5;
347 }
348 return closed; // only needs last value
349 }
350
351 // TODO: move closed form even further out?
352 static int closedFormNestedN(int n) {
353 int closed = 0;
354 for (int i = 0; i < n; i++) {
355 for (int j = 0; j < 10; j++) {
356 closed++;
357 }
358 }
359 return closed; // only needs last-value
360 }
361
362 // TODO: move closed form even further out?
363 static int closedFormNestedNAlt(int n) {
364 int closed = 12345;
365 for (int i = 0; i < n; i++) {
366 for (int j = 0; j < 23; j++) {
367 closed += 7;
368 }
369 }
370 return closed; // only needs last-value
371 }
372
373 // TODO: move closed form even further out?
374 static int closedFormNestedMN(int m, int n) {
375 int closed = 0;
376 for (int i = 0; i < m; i++) {
377 for (int j = 0; j < n; j++) {
378 closed++;
379 }
380 }
381 return closed; // only needs last-value
382 }
383
384 // TODO: move closed form even further out?
385 static int closedFormNestedMNAlt(int m, int n) {
386 int closed = 12345;
387 for (int i = 0; i < m; i++) {
388 for (int j = 0; j < n; j++) {
389 closed += 7;
390 }
391 }
392 return closed; // only needs last-value
393 }
394
395 /// CHECK-START: int Main.mainIndexReturned() loop_optimization (before)
396 /// CHECK-DAG: <<Phi:i\d+>> Phi loop:{{B\d+}} outer_loop:none
397 /// CHECK-DAG: Return [<<Phi>>] loop:none
398 //
399 /// CHECK-START: int Main.mainIndexReturned() loop_optimization (after)
400 /// CHECK-NOT: Phi
401 //
402 /// CHECK-START: int Main.mainIndexReturned() instruction_simplifier$before_codegen (after)
403 /// CHECK-DAG: <<Int:i\d+>> IntConstant 10 loop:none
404 /// CHECK-DAG: Return [<<Int>>] loop:none
405 static int mainIndexReturned() {
406 int i;
407 for (i = 0; i < 10; i++);
408 return i;
409 }
410
411 /// CHECK-START: int Main.periodicReturned9() loop_optimization (before)
412 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
413 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
414 /// CHECK-DAG: Return [<<Phi1>>] loop:none
415 //
416 /// CHECK-START: int Main.periodicReturned9() loop_optimization (after)
417 /// CHECK-NOT: Phi
418 //
419 /// CHECK-START: int Main.periodicReturned9() instruction_simplifier$before_codegen (after)
420 /// CHECK-DAG: <<Int:i\d+>> IntConstant 1 loop:none
421 /// CHECK-DAG: Return [<<Int>>] loop:none
422 static int periodicReturned9() {
423 int k = 0;
424 for (int i = 0; i < 9; i++) {
425 k = 1 - k;
426 }
427 return k;
428 }
429
430 /// CHECK-START: int Main.periodicReturned10() loop_optimization (before)
431 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
432 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
433 /// CHECK-DAG: Return [<<Phi1>>] loop:none
434 //
435 /// CHECK-START: int Main.periodicReturned10() loop_optimization (after)
436 /// CHECK-NOT: Phi
437 //
438 /// CHECK-START: int Main.periodicReturned10() instruction_simplifier$before_codegen (after)
439 /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none
440 /// CHECK-DAG: Return [<<Int>>] loop:none
441 static int periodicReturned10() {
442 int k = 0;
443 for (int i = 0; i < 10; i++) {
444 k = 1 - k;
445 }
446 return k;
447 }
448
449 /// CHECK-START: int Main.getSum21() loop_optimization (before)
450 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
451 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
452 /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop>> outer_loop:none
453 /// CHECK-DAG: Return [<<Phi2>>] loop:none
454 //
455 /// CHECK-START: int Main.getSum21() loop_optimization (after)
456 /// CHECK-NOT: Phi
457 //
458 /// CHECK-START: int Main.getSum21() instruction_simplifier$before_codegen (after)
459 /// CHECK-DAG: <<Int:i\d+>> IntConstant 21 loop:none
460 /// CHECK-DAG: Return [<<Int>>] loop:none
461 private static int getSum21() {
462 int k = 0;
463 int sum = 0;
464 for (int i = 0; i < 6; i++) {
465 k++;
466 sum += k;
467 }
468 return sum;
469 }
470
471 // Ensure double induction does not "overshoot" the subscript range.
472 private static int getIncr2(int[] arr) {
473 for (int i = 0; i < 12; ) {
474 arr[i++] = 30;
475 arr[i++] = 29;
476 }
477 int sum = 0;
478 for (int i = 0; i < 12; i++) {
479 sum += arr[i];
480 }
481 return sum;
482 }
483
484 // TODO: handle as closed/empty eventually?
485 static int mainIndexReturnedN(int n) {
486 int i;
487 for (i = 0; i < n; i++);
488 return i;
489 }
490
491 // TODO: handle as closed/empty eventually?
492 static int mainIndexShort1(short s) {
493 int i = 0;
494 for (i = 0; i < s; i++) { }
495 return i;
496 }
497
498 // TODO: handle as closed/empty eventually?
499 static int mainIndexShort2(short s) {
500 int i = 0;
501 for (i = 0; s > i; i++) { }
502 return i;
503 }
504
505 /// CHECK-START: int Main.periodicReturnedN(int) loop_optimization (before)
506 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
507 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
508 /// CHECK-DAG: Return [<<Phi1>>] loop:none
509 //
510 /// CHECK-START: int Main.periodicReturnedN(int) loop_optimization (after)
511 /// CHECK-NOT: Phi
512 static int periodicReturnedN(int n) {
513 int k = 0;
514 for (int i = 0; i < n; i++) {
515 k = 1 - k;
516 }
517 return k;
518 }
519
520 // If ever replaced by closed form, last value should be correct!
521 private static int getSumN(int n) {
522 int k = 0;
523 int sum = 0;
524 for (int i = 0; i < n; i++) {
525 k++;
526 sum += k;
527 }
528 return sum;
529 }
530
531 // If ever replaced by closed form, last value should be correct!
532 private static int closedTwice() {
533 int closed = 0;
534 for (int i = 0; i < 10; i++) {
535 closed++;
536 }
537 // Closed form of first loop defines trip count of second loop.
538 int other_closed = 0;
539 for (int i = 0; i < closed; i++) {
540 other_closed++;
541 }
542 return other_closed;
543 }
544
545 /// CHECK-START: int Main.closedFeed() loop_optimization (before)
546 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none
547 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop1>> outer_loop:none
548 /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop2:B\d+>> outer_loop:none
549 /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop2>> outer_loop:none
550 /// CHECK-DAG: Return [<<Phi3>>] loop:none
551 /// CHECK-EVAL: "<<Loop1>>" != "<<Loop2>>"
552 //
553 /// CHECK-START: int Main.closedFeed() loop_optimization (after)
554 /// CHECK-NOT: Phi
555 //
556 /// CHECK-START: int Main.closedFeed() instruction_simplifier$before_codegen (after)
557 /// CHECK-DAG: <<Int:i\d+>> IntConstant 20 loop:none
558 /// CHECK-DAG: Return [<<Int>>] loop:none
559 private static int closedFeed() {
560 int closed = 0;
561 for (int i = 0; i < 10; i++) {
562 closed++;
563 }
564 // Closed form of first loop feeds into initial value of second loop,
565 // used when generating closed form for the latter.
566 for (int i = 0; i < 10; i++) {
567 closed++;
568 }
569 return closed;
570 }
571
572 /// CHECK-START: int Main.closedLargeUp() loop_optimization (before)
573 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
574 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
575 /// CHECK-DAG: Return [<<Phi1>>] loop:none
576 //
577 /// CHECK-START: int Main.closedLargeUp() loop_optimization (after)
578 /// CHECK-NOT: Phi
579 //
580 /// CHECK-START: int Main.closedLargeUp() instruction_simplifier$before_codegen (after)
581 /// CHECK-DAG: <<Int:i\d+>> IntConstant -10 loop:none
582 /// CHECK-DAG: Return [<<Int>>] loop:none
583 private static int closedLargeUp() {
584 int closed = 0;
585 for (int i = 0; i < 10; i++) {
586 closed += 0x7fffffff;
587 }
588 return closed;
589 }
590
591 /// CHECK-START: int Main.closedLargeDown() loop_optimization (before)
592 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
593 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
594 /// CHECK-DAG: Return [<<Phi1>>] loop:none
595 //
596 /// CHECK-START: int Main.closedLargeDown() loop_optimization (after)
597 /// CHECK-NOT: Phi
598 //
599 /// CHECK-START: int Main.closedLargeDown() instruction_simplifier$before_codegen (after)
600 /// CHECK-DAG: <<Int:i\d+>> IntConstant 10 loop:none
601 /// CHECK-DAG: Return [<<Int>>] loop:none
602 private static int closedLargeDown() {
603 int closed = 0;
604 for (int i = 0; i < 10; i++) {
605 closed -= 0x7fffffff;
606 }
607 return closed;
608 }
609
610 // Checks that we do not loop optimize if the calculation of the trip count would overflow.
611 /// CHECK-START: int Main.closedLinearStepOverflow() loop_optimization (before)
612 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
613 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
614 /// CHECK-DAG: Return [<<Phi1>>] loop:none
615 //
616 /// CHECK-START: int Main.closedLinearStepOverflow() loop_optimization (after)
617 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
618 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
619 /// CHECK-DAG: Return [<<Phi1>>] loop:none
620 private static int closedLinearStepOverflow() {
621 int closed = 0;
622 // Note that this isn't a "one-off" error.
623 // We are using MIN and MAX to make sure we overflow.
624 for (int i = Integer.MIN_VALUE; i < (Integer.MAX_VALUE - 80); i += 79) {
625 closed++;
626 }
627 return closed;
628 }
629
630 // Since we cannot guarantee that the start/end wouldn't overflow we do not perform loop
631 // optimization.
632 /// CHECK-START: int Main.$inline$closedByParameters(int, int) loop_optimization (before)
633 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
634 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
635 /// CHECK-DAG: Return [<<Phi1>>] loop:none
636 //
637 /// CHECK-START: int Main.$inline$closedByParameters(int, int) loop_optimization (after)
638 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
639 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
640 /// CHECK-DAG: Return [<<Phi1>>] loop:none
641 private static int $inline$closedByParameters(int start, int end) {
642 int closed = 0;
643 for (int i = start; i < end; i++) {
644 closed++;
645 }
646 return closed;
647 }
648
649 // Since we are inlining `closedByParameters` we know that the parameters are fixed and
650 // therefore we can perform loop optimization.
651 /// CHECK-START: int Main.closedByParametersWithInline() loop_optimization (before)
652 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
653 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
654 /// CHECK-DAG: Return [<<Phi1>>] loop:none
655 //
656 /// CHECK-START: int Main.closedByParametersWithInline() loop_optimization (after)
657 /// CHECK-NOT: Phi
658 //
659 /// CHECK-START: int Main.closedByParametersWithInline() instruction_simplifier$before_codegen (after)
660 /// CHECK-DAG: <<Int:i\d+>> IntConstant 10 loop:none
661 /// CHECK-DAG: Return [<<Int>>] loop:none
662 private static int closedByParametersWithInline() {
663 return $inline$closedByParameters(0, 10);
664 }
665
666 /// CHECK-START: int Main.waterFall() loop_optimization (before)
667 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none
668 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop2:B\d+>> outer_loop:none
669 /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop3:B\d+>> outer_loop:none
670 /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop4:B\d+>> outer_loop:none
671 /// CHECK-DAG: <<Phi5:i\d+>> Phi loop:<<Loop5:B\d+>> outer_loop:none
672 /// CHECK-DAG: Return [<<Phi5>>] loop:none
673 //
674 /// CHECK-START: int Main.waterFall() loop_optimization (after)
675 /// CHECK-NOT: Phi
676 //
677 /// CHECK-START: int Main.waterFall() instruction_simplifier$before_codegen (after)
678 /// CHECK-DAG: <<Int:i\d+>> IntConstant 50 loop:none
679 /// CHECK-DAG: Return [<<Int>>] loop:none
680 private static int waterFall() {
681 int i = 0;
682 for (; i < 10; i++);
683 for (; i < 20; i++);
684 for (; i < 30; i++);
685 for (; i < 40; i++);
686 for (; i < 50; i++);
687 return i; // this should become just 50
688 }
689
690 /// CHECK-START: boolean Main.periodicBoolIdiom1() loop_optimization (before)
691 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
692 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
693 /// CHECK-DAG: Return [<<Phi1>>] loop:none
694 //
695 /// CHECK-START: boolean Main.periodicBoolIdiom1() loop_optimization (after)
696 /// CHECK-NOT: Phi
697 //
698 /// CHECK-START: boolean Main.periodicBoolIdiom1() instruction_simplifier$before_codegen (after)
699 /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none
700 /// CHECK-DAG: Return [<<Int>>] loop:none
701 private static boolean periodicBoolIdiom1() {
702 boolean x = true;
703 for (int i = 0; i < 7; i++) {
704 x = !x;
705 }
706 return x;
707 }
708
709 /// CHECK-START: boolean Main.periodicBoolIdiom2() loop_optimization (before)
710 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
711 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
712 /// CHECK-DAG: Return [<<Phi1>>] loop:none
713 //
714 /// CHECK-START: boolean Main.periodicBoolIdiom2() loop_optimization (after)
715 /// CHECK-NOT: Phi
716 //
717 /// CHECK-START: boolean Main.periodicBoolIdiom2() instruction_simplifier$before_codegen (after)
718 /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none
719 /// CHECK-DAG: Return [<<Int>>] loop:none
720 private static boolean periodicBoolIdiom2() {
721 boolean x = true;
722 for (int i = 0; i < 7; i++) {
723 x = (x != true);
724 }
725 return x;
726 }
727
728 /// CHECK-START: boolean Main.periodicBoolIdiom3() loop_optimization (before)
729 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
730 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
731 /// CHECK-DAG: Return [<<Phi1>>] loop:none
732 //
733 /// CHECK-START: boolean Main.periodicBoolIdiom3() loop_optimization (after)
734 /// CHECK-NOT: Phi
735 //
736 /// CHECK-START: boolean Main.periodicBoolIdiom3() instruction_simplifier$before_codegen (after)
737 /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none
738 /// CHECK-DAG: Return [<<Int>>] loop:none
739 private static boolean periodicBoolIdiom3() {
740 boolean x = true;
741 for (int i = 0; i < 7; i++) {
742 x = (x == false);
743 }
744 return x;
745 }
746
747 /// CHECK-START: boolean Main.periodicBoolIdiom1N(boolean, int) loop_optimization (before)
748 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
749 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
750 /// CHECK-DAG: Return [<<Phi2>>] loop:none
751 //
752 /// CHECK-START: boolean Main.periodicBoolIdiom1N(boolean, int) loop_optimization (after)
753 /// CHECK-NOT: Phi
754 private static boolean periodicBoolIdiom1N(boolean x, int n) {
755 for (int i = 0; i < n; i++) {
756 x = !x;
757 }
758 return x;
759 }
760
761 /// CHECK-START: boolean Main.periodicBoolIdiom2N(boolean, int) loop_optimization (before)
762 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
763 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
764 /// CHECK-DAG: Return [<<Phi2>>] loop:none
765 //
766 /// CHECK-START: boolean Main.periodicBoolIdiom2N(boolean, int) loop_optimization (after)
767 /// CHECK-NOT: Phi
768 private static boolean periodicBoolIdiom2N(boolean x, int n) {
769 for (int i = 0; i < n; i++) {
770 x = (x != true);
771 }
772 return x;
773 }
774
775 /// CHECK-START: boolean Main.periodicBoolIdiom3N(boolean, int) loop_optimization (before)
776 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
777 /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none
778 /// CHECK-DAG: Return [<<Phi2>>] loop:none
779 //
780 /// CHECK-START: boolean Main.periodicBoolIdiom3N(boolean, int) loop_optimization (after)
781 /// CHECK-NOT: Phi
782 private static boolean periodicBoolIdiom3N(boolean x, int n) {
783 for (int i = 0; i < n; i++) {
784 x = (x == false);
785 }
786 return x;
787 }
788
789 /// CHECK-START: float Main.periodicFloat10() loop_optimization (before)
790 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
791 /// CHECK-DAG: <<Phi2:f\d+>> Phi loop:<<Loop>> outer_loop:none
792 /// CHECK-DAG: <<Phi3:f\d+>> Phi loop:<<Loop>> outer_loop:none
793 /// CHECK-DAG: <<Phi4:f\d+>> Phi loop:<<Loop>> outer_loop:none
794 /// CHECK-DAG: Return [<<Phi2>>] loop:none
795 //
796 /// CHECK-START: float Main.periodicFloat10() loop_optimization (after)
797 /// CHECK-NOT: Phi
798 //
799 /// CHECK-START: float Main.periodicFloat10() loop_optimization (after)
800 /// CHECK-DAG: <<Float:f\d+>> FloatConstant 2 loop:none
801 /// CHECK-DAG: Return [<<Float>>] loop:none
802 private static float periodicFloat10() {
803 float r = 4.5f;
804 float s = 2.0f;
805 float t = -1.0f;
806 for (int i = 0; i < 10; i++) {
807 float tmp = t;
808 t = r;
809 r = s;
810 s = tmp;
811 }
812 return r;
813 }
814
815 /// CHECK-START: float Main.periodicFloat11() loop_optimization (before)
816 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
817 /// CHECK-DAG: <<Phi2:f\d+>> Phi loop:<<Loop>> outer_loop:none
818 /// CHECK-DAG: <<Phi3:f\d+>> Phi loop:<<Loop>> outer_loop:none
819 /// CHECK-DAG: <<Phi4:f\d+>> Phi loop:<<Loop>> outer_loop:none
820 /// CHECK-DAG: Return [<<Phi2>>] loop:none
821 //
822 /// CHECK-START: float Main.periodicFloat11() loop_optimization (after)
823 /// CHECK-NOT: Phi
824 //
825 /// CHECK-START: float Main.periodicFloat11() loop_optimization (after)
826 /// CHECK-DAG: <<Float:f\d+>> FloatConstant -1 loop:none
827 /// CHECK-DAG: Return [<<Float>>] loop:none
828 private static float periodicFloat11() {
829 float r = 4.5f;
830 float s = 2.0f;
831 float t = -1.0f;
832 for (int i = 0; i < 11; i++) {
833 float tmp = t;
834 t = r;
835 r = s;
836 s = tmp;
837 }
838 return r;
839 }
840
841 /// CHECK-START: float Main.periodicFloat12() loop_optimization (before)
842 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
843 /// CHECK-DAG: <<Phi2:f\d+>> Phi loop:<<Loop>> outer_loop:none
844 /// CHECK-DAG: <<Phi3:f\d+>> Phi loop:<<Loop>> outer_loop:none
845 /// CHECK-DAG: <<Phi4:f\d+>> Phi loop:<<Loop>> outer_loop:none
846 /// CHECK-DAG: Return [<<Phi2>>] loop:none
847 //
848 /// CHECK-START: float Main.periodicFloat12() loop_optimization (after)
849 /// CHECK-NOT: Phi
850 //
851 /// CHECK-START: float Main.periodicFloat12() loop_optimization (after)
852 /// CHECK-DAG: <<Float:f\d+>> FloatConstant 4.5 loop:none
853 /// CHECK-DAG: Return [<<Float>>] loop:none
854 private static float periodicFloat12() {
855 float r = 4.5f;
856 float s = 2.0f;
857 float t = -1.0f;
858 for (int i = 0; i < 12; i++) {
859 float tmp = t;
860 t = r;
861 r = s;
862 s = tmp;
863 }
864 return r;
865 }
866
867 private static int exceptionExitBeforeAdd() {
868 int k = 0;
869 try {
870 for (int i = 0; i < 10; i++) {
871 a[i] = 0;
872 k += 10; // increment last
873 }
874 } catch (Exception e) {
875 // Flag error by returning current
876 // value of k negated.
877 return -k - 1;
878 }
879 return k;
880 }
881
882 private static int exceptionExitAfterAdd() {
883 int k = 0;
884 try {
885 for (int i = 0; i < 10; i++) {
886 k += 10; // increment first
887 a[i] = 0;
888 }
889 } catch (Exception e) {
890 // Flag error by returning current
891 // value of k negated.
892 return -k - 1;
893 }
894 return k;
895 }
896
897 /// CHECK-START: long Main.closedLinearInductionUnmatchedTypesNotOptimized() loop_optimization (before)
898 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
899 /// CHECK-DAG: <<Phi2:j\d+>> Phi loop:<<Loop>> outer_loop:none
900 //
901 /// CHECK-START: long Main.closedLinearInductionUnmatchedTypesNotOptimized() loop_optimization (after)
902 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
903 /// CHECK-DAG: <<Phi2:j\d+>> Phi loop:<<Loop>> outer_loop:none
904 private static long closedLinearInductionUnmatchedTypesNotOptimized() {
905 long sum = 0;
906 for (int i = 0; i < 10; ++i) {
907 ++sum;
908 }
909 return sum;
910 }
911
912 /// CHECK-START: short Main.closedLinearInductionNarrowingNotOptimized() loop_optimization (before)
913 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
914 //
915 /// CHECK-START: short Main.closedLinearInductionNarrowingNotOptimized() loop_optimization (after)
916 /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none
917 private static short closedLinearInductionNarrowingNotOptimized() {
918 short i = 0;
919 for (; i < 10; ++i);
920 return i;
921 }
922
923 public static void main(String[] args) {
924 deadSingleLoop();
925 deadSingleLoopN(4);
926 potentialInfiniteLoop(4);
927 deadNestedLoops();
928 deadNestedAndFollowingLoops();
929 deadConditional(4);
930 deadConditionalCycle(4);
931
932 deadInduction();
933 for (int i = 0; i < a.length; i++) {
934 expectEquals(1, a[i]);
935 }
936 deadManyInduction();
937 for (int i = 0; i < a.length; i++) {
938 expectEquals(2, a[i]);
939 }
940 deadSequence();
941 for (int i = 0; i < a.length; i++) {
942 expectEquals(3, a[i]);
943 }
944 try {
945 deadCycleWithException(-1);
946 throw new Error("Expected: IOOB exception");
947 } catch (IndexOutOfBoundsException e) {
948 }
949 for (int i = 0; i < a.length; i++) {
950 expectEquals(i == 0 ? 4 : 3, a[i]);
951 }
952 deadCycleWithException(0);
953 for (int i = 0; i < a.length; i++) {
954 expectEquals(4, a[i]);
955 }
956
957 expectEquals(12395, closedFormInductionUp());
958 expectEquals(12295, closedFormInductionInAndDown(12345));
959 expectEquals(81, closedFormInductionTrivialIf());
960 expectEquals(10 * 10, closedFormNested());
961 expectEquals(12345 + 17 * 23 * 7, closedFormNestedAlt());
962 for (int n = -4; n < 10; n++) {
963 int tc = (n <= 0) ? 0 : n;
964 expectEquals(12345 + tc * 5, closedFormInductionUpN(n));
965 expectEquals(12345 - tc * 5, closedFormInductionInAndDownN(12345, n));
966 expectEquals(tc * 10, closedFormNestedN(n));
967 expectEquals(12345 + tc * 23 * 7, closedFormNestedNAlt(n));
968 expectEquals(tc * (tc + 1), closedFormNestedMN(n, n + 1));
969 expectEquals(12345 + tc * (tc + 1) * 7, closedFormNestedMNAlt(n, n + 1));
970 }
971
972 expectEquals(10, mainIndexReturned());
973 expectEquals(1, periodicReturned9());
974 expectEquals(0, periodicReturned10());
975 expectEquals(21, getSum21());
976 expectEquals(354, getIncr2(new int[12]));
977 for (int n = -4; n < 4; n++) {
978 int tc = (n <= 0) ? 0 : n;
979 expectEquals(tc, mainIndexReturnedN(n));
980 expectEquals(tc, mainIndexShort1((short) n));
981 expectEquals(tc, mainIndexShort2((short) n));
982 expectEquals(tc & 1, periodicReturnedN(n));
983 expectEquals((tc * (tc + 1)) / 2, getSumN(n));
984 }
985
986 expectEquals(10, closedTwice());
987 expectEquals(20, closedFeed());
988 expectEquals(-10, closedLargeUp());
989 expectEquals(10, closedLargeDown());
990 expectEquals(54366674, closedLinearStepOverflow());
991 expectEquals(10, $inline$closedByParameters(0, 10));
992 expectEquals(10, closedByParametersWithInline());
993 expectEquals(50, waterFall());
994
995 expectEquals(false, periodicBoolIdiom1());
996 expectEquals(false, periodicBoolIdiom2());
997 expectEquals(false, periodicBoolIdiom3());
998 for (int n = -4; n < 10; n++) {
999 int tc = (n <= 0) ? 0 : n;
1000 boolean even = (tc & 1) == 0;
1001 expectEquals(even, periodicBoolIdiom1N(true, n));
1002 expectEquals(!even, periodicBoolIdiom1N(false, n));
1003 expectEquals(even, periodicBoolIdiom2N(true, n));
1004 expectEquals(!even, periodicBoolIdiom2N(false, n));
1005 expectEquals(even, periodicBoolIdiom3N(true, n));
1006 expectEquals(!even, periodicBoolIdiom3N(false, n));
1007 }
1008
1009 expectEquals( 2.0f, periodicFloat10());
1010 expectEquals(-1.0f, periodicFloat11());
1011 expectEquals( 4.5f, periodicFloat12());
1012
1013 expectEquals(100, exceptionExitBeforeAdd());
1014 expectEquals(100, exceptionExitAfterAdd());
1015 a = null;
1016 expectEquals(-1, exceptionExitBeforeAdd());
1017 expectEquals(-11, exceptionExitAfterAdd());
1018 a = new int[4];
1019 expectEquals(-41, exceptionExitBeforeAdd());
1020 expectEquals(-51, exceptionExitAfterAdd());
1021
1022 expectEquals(10, closedLinearInductionUnmatchedTypesNotOptimized());
1023 expectEquals(10, closedLinearInductionNarrowingNotOptimized());
1024
1025 System.out.println("passed");
1026 }
1027
1028 private static void expectEquals(float expected, float result) {
1029 if (expected != result) {
1030 throw new Error("Expected: " + expected + ", found: " + result);
1031 }
1032 }
1033
1034 private static void expectEquals(int expected, int result) {
1035 if (expected != result) {
1036 throw new Error("Expected: " + expected + ", found: " + result);
1037 }
1038 }
1039
1040 private static void expectEquals(boolean expected, boolean result) {
1041 if (expected != result) {
1042 throw new Error("Expected: " + expected + ", found: " + result);
1043 }
1044 }
1045 }