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 [<<Phi2>>] 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 [<<Phi2>>] 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 [<<Phi3>>] 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   // TODO: handle as closed/empty eventually?
mainIndexReturnedN(int n)472   static int mainIndexReturnedN(int n) {
473     int i;
474     for (i = 0; i < n; i++);
475     return i;
476   }
477 
478   // TODO: handle as closed/empty eventually?
mainIndexShort1(short s)479   static int mainIndexShort1(short s) {
480     int i = 0;
481     for (i = 0; i < s; i++) { }
482     return i;
483   }
484 
485   // TODO: handle as closed/empty eventually?
mainIndexShort2(short s)486   static int mainIndexShort2(short s) {
487     int i = 0;
488     for (i = 0; s > i; i++) { }
489     return i;
490   }
491 
492   /// CHECK-START: int Main.periodicReturnedN(int) loop_optimization (before)
493   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
494   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
495   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
496   //
497   /// CHECK-START: int Main.periodicReturnedN(int) loop_optimization (after)
498   /// CHECK-NOT:               Phi
periodicReturnedN(int n)499   static int periodicReturnedN(int n) {
500     int k = 0;
501     for (int i = 0; i < n; i++) {
502       k = 1 - k;
503     }
504     return k;
505   }
506 
507   // If ever replaced by closed form, last value should be correct!
getSumN(int n)508   private static int getSumN(int n) {
509     int k = 0;
510     int sum = 0;
511     for (int i = 0; i < n; i++) {
512       k++;
513       sum += k;
514     }
515     return sum;
516   }
517 
518   // If ever replaced by closed form, last value should be correct!
closedTwice()519   private static int closedTwice() {
520     int closed = 0;
521     for (int i = 0; i < 10; i++) {
522       closed++;
523     }
524     // Closed form of first loop defines trip count of second loop.
525     int other_closed = 0;
526     for (int i = 0; i < closed; i++) {
527       other_closed++;
528     }
529     return other_closed;
530   }
531 
532   /// CHECK-START: int Main.closedFeed() loop_optimization (before)
533   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop1:B\d+>> outer_loop:none
534   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop1>>      outer_loop:none
535   /// CHECK-DAG: <<Phi3:i\d+>> Phi               loop:<<Loop2:B\d+>> outer_loop:none
536   /// CHECK-DAG: <<Phi4:i\d+>> Phi               loop:<<Loop2>>      outer_loop:none
537   /// CHECK-DAG:               Return [<<Phi3>>] loop:none
538   /// CHECK-EVAL: "<<Loop1>>" != "<<Loop2>>"
539   //
540   /// CHECK-START: int Main.closedFeed() loop_optimization (after)
541   /// CHECK-NOT:               Phi
542   //
543   /// CHECK-START: int Main.closedFeed() instruction_simplifier$after_bce (after)
544   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 20   loop:none
545   /// CHECK-DAG:               Return [<<Int>>] loop:none
closedFeed()546   private static int closedFeed() {
547     int closed = 0;
548     for (int i = 0; i < 10; i++) {
549       closed++;
550     }
551     // Closed form of first loop feeds into initial value of second loop,
552     // used when generating closed form for the latter.
553     for (int i = 0; i < 10; i++) {
554       closed++;
555     }
556     return closed;
557   }
558 
559   /// CHECK-START: int Main.closedLargeUp() loop_optimization (before)
560   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
561   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
562   /// CHECK-DAG:               Return [<<Phi1>>] loop:none
563   //
564   /// CHECK-START: int Main.closedLargeUp() loop_optimization (after)
565   /// CHECK-NOT:               Phi
566   //
567   /// CHECK-START: int Main.closedLargeUp() instruction_simplifier$after_bce (after)
568   /// CHECK-DAG: <<Int:i\d+>>  IntConstant -10  loop:none
569   /// CHECK-DAG:               Return [<<Int>>] loop:none
closedLargeUp()570   private static int closedLargeUp() {
571     int closed = 0;
572     for (int i = 0; i < 10; i++) {
573       closed += 0x7fffffff;
574     }
575     return closed;
576   }
577 
578   /// CHECK-START: int Main.closedLargeDown() loop_optimization (before)
579   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
580   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
581   /// CHECK-DAG:               Return [<<Phi1>>] loop:none
582   //
583   /// CHECK-START: int Main.closedLargeDown() loop_optimization (after)
584   /// CHECK-NOT:               Phi
585   //
586   /// CHECK-START: int Main.closedLargeDown() instruction_simplifier$after_bce (after)
587   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 10   loop:none
588   /// CHECK-DAG:               Return [<<Int>>] loop:none
closedLargeDown()589   private static int closedLargeDown() {
590     int closed = 0;
591     for (int i = 0; i < 10; i++) {
592       closed -= 0x7fffffff;
593     }
594     return closed;
595   }
596 
597   /// CHECK-START: int Main.waterFall() loop_optimization (before)
598   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop1:B\d+>> outer_loop:none
599   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop2:B\d+>> outer_loop:none
600   /// CHECK-DAG: <<Phi3:i\d+>> Phi               loop:<<Loop3:B\d+>> outer_loop:none
601   /// CHECK-DAG: <<Phi4:i\d+>> Phi               loop:<<Loop4:B\d+>> outer_loop:none
602   /// CHECK-DAG: <<Phi5:i\d+>> Phi               loop:<<Loop5:B\d+>> outer_loop:none
603   /// CHECK-DAG:               Return [<<Phi5>>] loop:none
604   //
605   /// CHECK-START: int Main.waterFall() loop_optimization (after)
606   /// CHECK-NOT:               Phi
607   //
608   /// CHECK-START: int Main.waterFall() instruction_simplifier$after_bce (after)
609   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 50   loop:none
610   /// CHECK-DAG:               Return [<<Int>>] loop:none
waterFall()611   private static int waterFall() {
612     int i = 0;
613     for (; i < 10; i++);
614     for (; i < 20; i++);
615     for (; i < 30; i++);
616     for (; i < 40; i++);
617     for (; i < 50; i++);
618     return i;  // this should become just 50
619   }
620 
621   /// CHECK-START: boolean Main.periodicBoolIdiom1() loop_optimization (before)
622   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
623   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
624   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
625   //
626   /// CHECK-START: boolean Main.periodicBoolIdiom1() loop_optimization (after)
627   /// CHECK-NOT:               Phi
628   //
629   /// CHECK-START: boolean Main.periodicBoolIdiom1() instruction_simplifier$after_bce (after)
630   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 0    loop:none
631   /// CHECK-DAG:               Return [<<Int>>] loop:none
periodicBoolIdiom1()632   private static boolean periodicBoolIdiom1() {
633     boolean x = true;
634     for (int i = 0; i < 7; i++) {
635       x = !x;
636     }
637     return x;
638   }
639 
640   /// CHECK-START: boolean Main.periodicBoolIdiom2() loop_optimization (before)
641   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
642   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
643   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
644   //
645   /// CHECK-START: boolean Main.periodicBoolIdiom2() loop_optimization (after)
646   /// CHECK-NOT:               Phi
647   //
648   /// CHECK-START: boolean Main.periodicBoolIdiom2() instruction_simplifier$after_bce (after)
649   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 0    loop:none
650   /// CHECK-DAG:               Return [<<Int>>] loop:none
periodicBoolIdiom2()651   private static boolean periodicBoolIdiom2() {
652     boolean x = true;
653     for (int i = 0; i < 7; i++) {
654       x = (x != true);
655     }
656     return x;
657   }
658 
659   /// CHECK-START: boolean Main.periodicBoolIdiom3() loop_optimization (before)
660   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
661   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
662   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
663   //
664   /// CHECK-START: boolean Main.periodicBoolIdiom3() loop_optimization (after)
665   /// CHECK-NOT:               Phi
666   //
667   /// CHECK-START: boolean Main.periodicBoolIdiom3() instruction_simplifier$after_bce (after)
668   /// CHECK-DAG: <<Int:i\d+>>  IntConstant 0    loop:none
669   /// CHECK-DAG:               Return [<<Int>>] loop:none
periodicBoolIdiom3()670   private static boolean periodicBoolIdiom3() {
671     boolean x = true;
672     for (int i = 0; i < 7; i++) {
673       x = (x == false);
674     }
675     return x;
676   }
677 
678   /// CHECK-START: boolean Main.periodicBoolIdiom1N(boolean, int) loop_optimization (before)
679   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
680   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
681   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
682   //
683   /// CHECK-START: boolean Main.periodicBoolIdiom1N(boolean, int) loop_optimization (after)
684   /// CHECK-NOT:               Phi
periodicBoolIdiom1N(boolean x, int n)685   private static boolean periodicBoolIdiom1N(boolean x, int n) {
686     for (int i = 0; i < n; i++) {
687       x = !x;
688     }
689     return x;
690   }
691 
692   /// CHECK-START: boolean Main.periodicBoolIdiom2N(boolean, int) loop_optimization (before)
693   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
694   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
695   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
696   //
697   /// CHECK-START: boolean Main.periodicBoolIdiom2N(boolean, int) loop_optimization (after)
698   /// CHECK-NOT:               Phi
periodicBoolIdiom2N(boolean x, int n)699   private static boolean periodicBoolIdiom2N(boolean x, int n) {
700     for (int i = 0; i < n; i++) {
701       x = (x != true);
702     }
703     return x;
704   }
705 
706   /// CHECK-START: boolean Main.periodicBoolIdiom3N(boolean, int) loop_optimization (before)
707   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
708   /// CHECK-DAG: <<Phi2:i\d+>> Phi               loop:<<Loop>>      outer_loop:none
709   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
710   //
711   /// CHECK-START: boolean Main.periodicBoolIdiom3N(boolean, int) loop_optimization (after)
712   /// CHECK-NOT:               Phi
periodicBoolIdiom3N(boolean x, int n)713   private static boolean periodicBoolIdiom3N(boolean x, int n) {
714     for (int i = 0; i < n; i++) {
715       x = (x == false);
716     }
717     return x;
718   }
719 
720   /// CHECK-START: float Main.periodicFloat10() loop_optimization (before)
721   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
722   /// CHECK-DAG: <<Phi2:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
723   /// CHECK-DAG: <<Phi3:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
724   /// CHECK-DAG: <<Phi4:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
725   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
726   //
727   /// CHECK-START: float Main.periodicFloat10() loop_optimization (after)
728   /// CHECK-NOT: Phi
729   //
730   /// CHECK-START: float Main.periodicFloat10() loop_optimization (after)
731   /// CHECK-DAG: <<Float:f\d+>>  FloatConstant 2    loop:none
732   /// CHECK-DAG:                 Return [<<Float>>] loop:none
periodicFloat10()733   private static float periodicFloat10() {
734     float r = 4.5f;
735     float s = 2.0f;
736     float t = -1.0f;
737     for (int i = 0; i < 10; i++) {
738       float tmp = t; t = r; r = s; s = tmp;
739     }
740     return r;
741   }
742 
743   /// CHECK-START: float Main.periodicFloat11() loop_optimization (before)
744   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
745   /// CHECK-DAG: <<Phi2:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
746   /// CHECK-DAG: <<Phi3:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
747   /// CHECK-DAG: <<Phi4:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
748   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
749   //
750   /// CHECK-START: float Main.periodicFloat11() loop_optimization (after)
751   /// CHECK-NOT: Phi
752   //
753   /// CHECK-START: float Main.periodicFloat11() loop_optimization (after)
754   /// CHECK-DAG: <<Float:f\d+>>  FloatConstant -1   loop:none
755   /// CHECK-DAG:                 Return [<<Float>>] loop:none
periodicFloat11()756   private static float periodicFloat11() {
757     float r = 4.5f;
758     float s = 2.0f;
759     float t = -1.0f;
760     for (int i = 0; i < 11; i++) {
761       float tmp = t; t = r; r = s; s = tmp;
762     }
763     return r;
764   }
765 
766   /// CHECK-START: float Main.periodicFloat12() loop_optimization (before)
767   /// CHECK-DAG: <<Phi1:i\d+>> Phi               loop:<<Loop:B\d+>> outer_loop:none
768   /// CHECK-DAG: <<Phi2:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
769   /// CHECK-DAG: <<Phi3:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
770   /// CHECK-DAG: <<Phi4:f\d+>> Phi               loop:<<Loop>>      outer_loop:none
771   /// CHECK-DAG:               Return [<<Phi2>>] loop:none
772   //
773   /// CHECK-START: float Main.periodicFloat12() loop_optimization (after)
774   /// CHECK-NOT: Phi
775   //
776   /// CHECK-START: float Main.periodicFloat12() loop_optimization (after)
777   /// CHECK-DAG: <<Float:f\d+>>  FloatConstant 4.5  loop:none
778   /// CHECK-DAG:                 Return [<<Float>>] loop:none
periodicFloat12()779   private static float periodicFloat12() {
780     float r = 4.5f;
781     float s = 2.0f;
782     float t = -1.0f;
783     for (int i = 0; i < 12; i++) {
784       float tmp = t; t = r; r = s; s = tmp;
785     }
786     return r;
787   }
788 
exceptionExitBeforeAdd()789   private static int exceptionExitBeforeAdd() {
790     int k = 0;
791     try {
792       for (int i = 0; i < 10; i++) {
793         a[i] = 0;
794         k += 10;  // increment last
795       }
796     } catch(Exception e) {
797       // Flag error by returning current
798       // value of k negated.
799       return -k-1;
800     }
801     return k;
802   }
803 
exceptionExitAfterAdd()804   private static int exceptionExitAfterAdd() {
805     int k = 0;
806     try {
807       for (int i = 0; i < 10; i++) {
808         k += 10;  // increment first
809         a[i] = 0;
810       }
811     } catch(Exception e) {
812       // Flag error by returning current
813       // value of k negated.
814       return -k-1;
815     }
816     return k;
817   }
818 
main(String[] args)819   public static void main(String[] args) {
820     deadSingleLoop();
821     deadSingleLoopN(4);
822     potentialInfiniteLoop(4);
823     deadNestedLoops();
824     deadNestedAndFollowingLoops();
825     deadConditional(4);
826     deadConditionalCycle(4);
827 
828     deadInduction();
829     for (int i = 0; i < a.length; i++) {
830       expectEquals(1, a[i]);
831     }
832     deadManyInduction();
833     for (int i = 0; i < a.length; i++) {
834       expectEquals(2, a[i]);
835     }
836     deadSequence();
837     for (int i = 0; i < a.length; i++) {
838       expectEquals(3, a[i]);
839     }
840     try {
841       deadCycleWithException(-1);
842       throw new Error("Expected: IOOB exception");
843     } catch (IndexOutOfBoundsException e) {
844     }
845     for (int i = 0; i < a.length; i++) {
846       expectEquals(i == 0 ? 4 : 3, a[i]);
847     }
848     deadCycleWithException(0);
849     for (int i = 0; i < a.length; i++) {
850       expectEquals(4, a[i]);
851     }
852 
853     expectEquals(12395, closedFormInductionUp());
854     expectEquals(12295, closedFormInductionInAndDown(12345));
855     expectEquals(81, closedFormInductionTrivialIf());
856     expectEquals(10 * 10, closedFormNested());
857     expectEquals(12345 + 17 * 23 * 7, closedFormNestedAlt());
858     for (int n = -4; n < 10; n++) {
859       int tc = (n <= 0) ? 0 : n;
860       expectEquals(12345 + tc * 5, closedFormInductionUpN(n));
861       expectEquals(12345 - tc * 5, closedFormInductionInAndDownN(12345, n));
862       expectEquals(tc * 10, closedFormNestedN(n));
863       expectEquals(12345 + tc * 23 * 7, closedFormNestedNAlt(n));
864       expectEquals(tc * (tc + 1), closedFormNestedMN(n, n + 1));
865       expectEquals(12345 + tc * (tc + 1) * 7, closedFormNestedMNAlt(n, n + 1));
866     }
867 
868     expectEquals(10, mainIndexReturned());
869     expectEquals(1, periodicReturned9());
870     expectEquals(0, periodicReturned10());
871     expectEquals(21, getSum21());
872     for (int n = -4; n < 4; n++) {
873       int tc = (n <= 0) ? 0 : n;
874       expectEquals(tc, mainIndexReturnedN(n));
875       expectEquals(tc, mainIndexShort1((short) n));
876       expectEquals(tc, mainIndexShort2((short) n));
877       expectEquals(tc & 1, periodicReturnedN(n));
878       expectEquals((tc * (tc + 1)) / 2, getSumN(n));
879     }
880 
881     expectEquals(10, closedTwice());
882     expectEquals(20, closedFeed());
883     expectEquals(-10, closedLargeUp());
884     expectEquals(10, closedLargeDown());
885     expectEquals(50, waterFall());
886 
887     expectEquals(false, periodicBoolIdiom1());
888     expectEquals(false, periodicBoolIdiom2());
889     expectEquals(false, periodicBoolIdiom3());
890     for (int n = -4; n < 10; n++) {
891       int tc = (n <= 0) ? 0 : n;
892       boolean even = (tc & 1) == 0;
893       expectEquals(even, periodicBoolIdiom1N(true, n));
894       expectEquals(!even, periodicBoolIdiom1N(false, n));
895       expectEquals(even, periodicBoolIdiom2N(true, n));
896       expectEquals(!even, periodicBoolIdiom2N(false, n));
897       expectEquals(even, periodicBoolIdiom3N(true, n));
898       expectEquals(!even, periodicBoolIdiom3N(false, n));
899     }
900 
901     expectEquals( 2.0f, periodicFloat10());
902     expectEquals(-1.0f, periodicFloat11());
903     expectEquals( 4.5f, periodicFloat12());
904 
905     expectEquals(100, exceptionExitBeforeAdd());
906     expectEquals(100, exceptionExitAfterAdd());
907     a = null;
908     expectEquals(-1, exceptionExitBeforeAdd());
909     expectEquals(-11, exceptionExitAfterAdd());
910     a = new int[4];
911     expectEquals(-41, exceptionExitBeforeAdd());
912     expectEquals(-51, exceptionExitAfterAdd());
913 
914     System.out.println("passed");
915   }
916 
expectEquals(float expected, float result)917   private static void expectEquals(float expected, float result) {
918     if (expected != result) {
919       throw new Error("Expected: " + expected + ", found: " + result);
920     }
921   }
922 
expectEquals(int expected, int result)923   private static void expectEquals(int expected, int result) {
924     if (expected != result) {
925       throw new Error("Expected: " + expected + ", found: " + result);
926     }
927   }
928 
expectEquals(boolean expected, boolean result)929   private static void expectEquals(boolean expected, boolean result) {
930     if (expected != result) {
931       throw new Error("Expected: " + expected + ", found: " + result);
932     }
933   }
934 }
935