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
deadSingleLoop()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
deadSingleLoopN(int n)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
potentialInfiniteLoop(int n)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
deadNestedLoops()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
deadNestedAndFollowingLoops()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
deadConditional(int n)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
deadConditionalCycle(int n)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
deadInduction()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
deadManyInduction()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
deadSequence()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
deadCycleWithException(int k)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$after_bce (after)
231   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 12395 loop:none
232   /// CHECK-DAG:               Return [<<Int>>]  loop:none
closedFormInductionUp()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$after_bce (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
closedFormInductionInAndDown(int closed)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$after_bce (after)
272   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 81    loop:none
273   /// CHECK-DAG:               Return [<<Int>>]  loop:none
closedFormInductionTrivialIf()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$after_bce (after)
299   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 100  loop:none
300   /// CHECK-DAG:               Return [<<Int>>] loop:none
closedFormNested()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$after_bce (after)
322   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 15082 loop:none
323   /// CHECK-DAG:               Return [<<Int>>]  loop:none
closedFormNestedAlt()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?
closedFormInductionUpN(int n)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?
closedFormInductionInAndDownN(int closed, int n)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?
closedFormNestedN(int n)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?
closedFormNestedNAlt(int n)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?
closedFormNestedMN(int m, int n)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?
closedFormNestedMNAlt(int m, int n)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$after_bce (after)
403   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 10   loop:none
404   /// CHECK-DAG:               Return [<<Int>>] loop:none
mainIndexReturned()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$after_bce (after)
420   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 1    loop:none
421   /// CHECK-DAG:               Return [<<Int>>] loop:none
periodicReturned9()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$after_bce (after)
439   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 0    loop:none
440   /// CHECK-DAG:               Return [<<Int>>] loop:none
periodicReturned10()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$after_bce (after)
459   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 21   loop:none
460   /// CHECK-DAG:               Return [<<Int>>] loop:none
getSum21()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.
getIncr2(int[] arr)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?
mainIndexReturnedN(int n)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?
mainIndexShort1(short s)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?
mainIndexShort2(short s)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
periodicReturnedN(int n)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!
getSumN(int n)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!
closedTwice()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$after_bce (after)
557   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 20   loop:none
558   /// CHECK-DAG:               Return [<<Int>>] loop:none
closedFeed()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$after_bce (after)
581   /// CHECK-DAG: <<Int:i\d+>>  IntConstant -10  loop:none
582   /// CHECK-DAG:               Return [<<Int>>] loop:none
closedLargeUp()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$after_bce (after)
600   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 10   loop:none
601   /// CHECK-DAG:               Return [<<Int>>] loop:none
closedLargeDown()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   /// CHECK-START: int Main.waterFall() loop_optimization (before)
611   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop1:B\d+>> outer_loop:none
612   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop2:B\d+>> outer_loop:none
613   /// CHECK-DAG: <<Phi3:i\d+>> Phi               loop:<<Loop3:B\d+>> outer_loop:none
614   /// CHECK-DAG: <<Phi4:i\d+>> Phi               loop:<<Loop4:B\d+>> outer_loop:none
615   /// CHECK-DAG: <<Phi5:i\d+>> Phi               loop:<<Loop5:B\d+>> outer_loop:none
616   /// CHECK-DAG:               Return [<<Phi5>>] loop:none
617   //
618   /// CHECK-START: int Main.waterFall() loop_optimization (after)
619   /// CHECK-NOT:               Phi
620   //
621   /// CHECK-START: int Main.waterFall() instruction_simplifier$after_bce (after)
622   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 50   loop:none
623   /// CHECK-DAG:               Return [<<Int>>] loop:none
waterFall()624   private static int waterFall() {
625     int i = 0;
626     for (; i < 10; i++);
627     for (; i < 20; i++);
628     for (; i < 30; i++);
629     for (; i < 40; i++);
630     for (; i < 50; i++);
631     return i;  // this should become just 50
632   }
633 
634   /// CHECK-START: boolean Main.periodicBoolIdiom1() loop_optimization (before)
635   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
636   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
637   /// CHECK-DAG:               Return [<<Phi1>>] loop:none
638   //
639   /// CHECK-START: boolean Main.periodicBoolIdiom1() loop_optimization (after)
640   /// CHECK-NOT:               Phi
641   //
642   /// CHECK-START: boolean Main.periodicBoolIdiom1() instruction_simplifier$after_bce (after)
643   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 0    loop:none
644   /// CHECK-DAG:               Return [<<Int>>] loop:none
periodicBoolIdiom1()645   private static boolean periodicBoolIdiom1() {
646     boolean x = true;
647     for (int i = 0; i < 7; i++) {
648       x = !x;
649     }
650     return x;
651   }
652 
653   /// CHECK-START: boolean Main.periodicBoolIdiom2() loop_optimization (before)
654   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
655   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
656   /// CHECK-DAG:               Return [<<Phi1>>] loop:none
657   //
658   /// CHECK-START: boolean Main.periodicBoolIdiom2() loop_optimization (after)
659   /// CHECK-NOT:               Phi
660   //
661   /// CHECK-START: boolean Main.periodicBoolIdiom2() instruction_simplifier$after_bce (after)
662   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 0    loop:none
663   /// CHECK-DAG:               Return [<<Int>>] loop:none
periodicBoolIdiom2()664   private static boolean periodicBoolIdiom2() {
665     boolean x = true;
666     for (int i = 0; i < 7; i++) {
667       x = (x != true);
668     }
669     return x;
670   }
671 
672   /// CHECK-START: boolean Main.periodicBoolIdiom3() loop_optimization (before)
673   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
674   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
675   /// CHECK-DAG:               Return [<<Phi1>>] loop:none
676   //
677   /// CHECK-START: boolean Main.periodicBoolIdiom3() loop_optimization (after)
678   /// CHECK-NOT:               Phi
679   //
680   /// CHECK-START: boolean Main.periodicBoolIdiom3() instruction_simplifier$after_bce (after)
681   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 0    loop:none
682   /// CHECK-DAG:               Return [<<Int>>] loop:none
periodicBoolIdiom3()683   private static boolean periodicBoolIdiom3() {
684     boolean x = true;
685     for (int i = 0; i < 7; i++) {
686       x = (x == false);
687     }
688     return x;
689   }
690 
691   /// CHECK-START: boolean Main.periodicBoolIdiom1N(boolean, int) loop_optimization (before)
692   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
693   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
694   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
695   //
696   /// CHECK-START: boolean Main.periodicBoolIdiom1N(boolean, int) loop_optimization (after)
697   /// CHECK-NOT:               Phi
periodicBoolIdiom1N(boolean x, int n)698   private static boolean periodicBoolIdiom1N(boolean x, int n) {
699     for (int i = 0; i < n; i++) {
700       x = !x;
701     }
702     return x;
703   }
704 
705   /// CHECK-START: boolean Main.periodicBoolIdiom2N(boolean, int) loop_optimization (before)
706   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
707   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
708   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
709   //
710   /// CHECK-START: boolean Main.periodicBoolIdiom2N(boolean, int) loop_optimization (after)
711   /// CHECK-NOT:               Phi
periodicBoolIdiom2N(boolean x, int n)712   private static boolean periodicBoolIdiom2N(boolean x, int n) {
713     for (int i = 0; i < n; i++) {
714       x = (x != true);
715     }
716     return x;
717   }
718 
719   /// CHECK-START: boolean Main.periodicBoolIdiom3N(boolean, int) loop_optimization (before)
720   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
721   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
722   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
723   //
724   /// CHECK-START: boolean Main.periodicBoolIdiom3N(boolean, int) loop_optimization (after)
725   /// CHECK-NOT:               Phi
periodicBoolIdiom3N(boolean x, int n)726   private static boolean periodicBoolIdiom3N(boolean x, int n) {
727     for (int i = 0; i < n; i++) {
728       x = (x == false);
729     }
730     return x;
731   }
732 
733   /// CHECK-START: float Main.periodicFloat10() loop_optimization (before)
734   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
735   /// CHECK-DAG: <<Phi2:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
736   /// CHECK-DAG: <<Phi3:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
737   /// CHECK-DAG: <<Phi4:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
738   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
739   //
740   /// CHECK-START: float Main.periodicFloat10() loop_optimization (after)
741   /// CHECK-NOT: Phi
742   //
743   /// CHECK-START: float Main.periodicFloat10() loop_optimization (after)
744   /// CHECK-DAG: <<Float:f\d+>>  FloatConstant 2    loop:none
745   /// CHECK-DAG:                 Return [<<Float>>] loop:none
periodicFloat10()746   private static float periodicFloat10() {
747     float r = 4.5f;
748     float s = 2.0f;
749     float t = -1.0f;
750     for (int i = 0; i < 10; i++) {
751       float tmp = t; t = r; r = s; s = tmp;
752     }
753     return r;
754   }
755 
756   /// CHECK-START: float Main.periodicFloat11() loop_optimization (before)
757   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
758   /// CHECK-DAG: <<Phi2:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
759   /// CHECK-DAG: <<Phi3:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
760   /// CHECK-DAG: <<Phi4:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
761   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
762   //
763   /// CHECK-START: float Main.periodicFloat11() loop_optimization (after)
764   /// CHECK-NOT: Phi
765   //
766   /// CHECK-START: float Main.periodicFloat11() loop_optimization (after)
767   /// CHECK-DAG: <<Float:f\d+>>  FloatConstant -1   loop:none
768   /// CHECK-DAG:                 Return [<<Float>>] loop:none
periodicFloat11()769   private static float periodicFloat11() {
770     float r = 4.5f;
771     float s = 2.0f;
772     float t = -1.0f;
773     for (int i = 0; i < 11; i++) {
774       float tmp = t; t = r; r = s; s = tmp;
775     }
776     return r;
777   }
778 
779   /// CHECK-START: float Main.periodicFloat12() loop_optimization (before)
780   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
781   /// CHECK-DAG: <<Phi2:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
782   /// CHECK-DAG: <<Phi3:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
783   /// CHECK-DAG: <<Phi4:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
784   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
785   //
786   /// CHECK-START: float Main.periodicFloat12() loop_optimization (after)
787   /// CHECK-NOT: Phi
788   //
789   /// CHECK-START: float Main.periodicFloat12() loop_optimization (after)
790   /// CHECK-DAG: <<Float:f\d+>>  FloatConstant 4.5  loop:none
791   /// CHECK-DAG:                 Return [<<Float>>] loop:none
periodicFloat12()792   private static float periodicFloat12() {
793     float r = 4.5f;
794     float s = 2.0f;
795     float t = -1.0f;
796     for (int i = 0; i < 12; i++) {
797       float tmp = t; t = r; r = s; s = tmp;
798     }
799     return r;
800   }
801 
exceptionExitBeforeAdd()802   private static int exceptionExitBeforeAdd() {
803     int k = 0;
804     try {
805       for (int i = 0; i < 10; i++) {
806         a[i] = 0;
807         k += 10;  // increment last
808       }
809     } catch(Exception e) {
810       // Flag error by returning current
811       // value of k negated.
812       return -k-1;
813     }
814     return k;
815   }
816 
exceptionExitAfterAdd()817   private static int exceptionExitAfterAdd() {
818     int k = 0;
819     try {
820       for (int i = 0; i < 10; i++) {
821         k += 10;  // increment first
822         a[i] = 0;
823       }
824     } catch(Exception e) {
825       // Flag error by returning current
826       // value of k negated.
827       return -k-1;
828     }
829     return k;
830   }
831 
main(String[] args)832   public static void main(String[] args) {
833     deadSingleLoop();
834     deadSingleLoopN(4);
835     potentialInfiniteLoop(4);
836     deadNestedLoops();
837     deadNestedAndFollowingLoops();
838     deadConditional(4);
839     deadConditionalCycle(4);
840 
841     deadInduction();
842     for (int i = 0; i < a.length; i++) {
843       expectEquals(1, a[i]);
844     }
845     deadManyInduction();
846     for (int i = 0; i < a.length; i++) {
847       expectEquals(2, a[i]);
848     }
849     deadSequence();
850     for (int i = 0; i < a.length; i++) {
851       expectEquals(3, a[i]);
852     }
853     try {
854       deadCycleWithException(-1);
855       throw new Error("Expected: IOOB exception");
856     } catch (IndexOutOfBoundsException e) {
857     }
858     for (int i = 0; i < a.length; i++) {
859       expectEquals(i == 0 ? 4 : 3, a[i]);
860     }
861     deadCycleWithException(0);
862     for (int i = 0; i < a.length; i++) {
863       expectEquals(4, a[i]);
864     }
865 
866     expectEquals(12395, closedFormInductionUp());
867     expectEquals(12295, closedFormInductionInAndDown(12345));
868     expectEquals(81, closedFormInductionTrivialIf());
869     expectEquals(10 * 10, closedFormNested());
870     expectEquals(12345 + 17 * 23 * 7, closedFormNestedAlt());
871     for (int n = -4; n < 10; n++) {
872       int tc = (n <= 0) ? 0 : n;
873       expectEquals(12345 + tc * 5, closedFormInductionUpN(n));
874       expectEquals(12345 - tc * 5, closedFormInductionInAndDownN(12345, n));
875       expectEquals(tc * 10, closedFormNestedN(n));
876       expectEquals(12345 + tc * 23 * 7, closedFormNestedNAlt(n));
877       expectEquals(tc * (tc + 1), closedFormNestedMN(n, n + 1));
878       expectEquals(12345 + tc * (tc + 1) * 7, closedFormNestedMNAlt(n, n + 1));
879     }
880 
881     expectEquals(10, mainIndexReturned());
882     expectEquals(1, periodicReturned9());
883     expectEquals(0, periodicReturned10());
884     expectEquals(21, getSum21());
885     expectEquals(354, getIncr2(new int[12]));
886     for (int n = -4; n < 4; n++) {
887       int tc = (n <= 0) ? 0 : n;
888       expectEquals(tc, mainIndexReturnedN(n));
889       expectEquals(tc, mainIndexShort1((short) n));
890       expectEquals(tc, mainIndexShort2((short) n));
891       expectEquals(tc & 1, periodicReturnedN(n));
892       expectEquals((tc * (tc + 1)) / 2, getSumN(n));
893     }
894 
895     expectEquals(10, closedTwice());
896     expectEquals(20, closedFeed());
897     expectEquals(-10, closedLargeUp());
898     expectEquals(10, closedLargeDown());
899     expectEquals(50, waterFall());
900 
901     expectEquals(false, periodicBoolIdiom1());
902     expectEquals(false, periodicBoolIdiom2());
903     expectEquals(false, periodicBoolIdiom3());
904     for (int n = -4; n < 10; n++) {
905       int tc = (n <= 0) ? 0 : n;
906       boolean even = (tc & 1) == 0;
907       expectEquals(even, periodicBoolIdiom1N(true, n));
908       expectEquals(!even, periodicBoolIdiom1N(false, n));
909       expectEquals(even, periodicBoolIdiom2N(true, n));
910       expectEquals(!even, periodicBoolIdiom2N(false, n));
911       expectEquals(even, periodicBoolIdiom3N(true, n));
912       expectEquals(!even, periodicBoolIdiom3N(false, n));
913     }
914 
915     expectEquals( 2.0f, periodicFloat10());
916     expectEquals(-1.0f, periodicFloat11());
917     expectEquals( 4.5f, periodicFloat12());
918 
919     expectEquals(100, exceptionExitBeforeAdd());
920     expectEquals(100, exceptionExitAfterAdd());
921     a = null;
922     expectEquals(-1, exceptionExitBeforeAdd());
923     expectEquals(-11, exceptionExitAfterAdd());
924     a = new int[4];
925     expectEquals(-41, exceptionExitBeforeAdd());
926     expectEquals(-51, exceptionExitAfterAdd());
927 
928     System.out.println("passed");
929   }
930 
expectEquals(float expected, float result)931   private static void expectEquals(float expected, float result) {
932     if (expected != result) {
933       throw new Error("Expected: " + expected + ", found: " + result);
934     }
935   }
936 
expectEquals(int expected, int result)937   private static void expectEquals(int expected, int result) {
938     if (expected != result) {
939       throw new Error("Expected: " + expected + ", found: " + result);
940     }
941   }
942 
expectEquals(boolean expected, boolean result)943   private static void expectEquals(boolean expected, boolean result) {
944     if (expected != result) {
945       throw new Error("Expected: " + expected + ", found: " + result);
946     }
947   }
948 }
949