1 /*
2  * Copyright (C) 2017 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 for optimizations of break-loops, i.e. loops that break
19  * out of a while-true loop when the end condition is satisfied.
20  * In particular, the tests focus on break-loops that can be
21  * rewritten into regular countable loops (this may improve certain
22  * loops generated by the Kotlin compiler for inclusive ranges).
23  */
24 public class Main {
25 
26   /// CHECK-START: int Main.breakLoop(int[]) induction_var_analysis (before)
27   /// CHECK-DAG: <<Par:l\d+>>  ParameterValue                     loop:none
28   /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0                      loop:none
29   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                      loop:none
30   /// CHECK-DAG: <<Nil:l\d+>>  NullCheck [<<Par>>]                loop:none
31   /// CHECK-DAG: <<Phi:i\d+>>  Phi [<<Zero>>,<<AddI:i\d+>>]       loop:<<Loop:B\d+>> outer_loop:none
32   /// CHECK-DAG: <<Bnd:i\d+>>  BoundsCheck [<<Phi>>,{{i\d+}}]     loop:<<Loop>>      outer_loop:none
33   /// CHECK-DAG:               ArraySet [<<Nil>>,<<Bnd>>,<<One>>] loop:<<Loop>>      outer_loop:none
34   /// CHECK-DAG: <<NE:z\d+>>   NotEqual [{{i\d+}},<<Phi>>]        loop:<<Loop>>      outer_loop:none
35   /// CHECK-DAG:               If [<<NE>>]                        loop:<<Loop>>      outer_loop:none
36   /// CHECK-DAG: <<AddI>>      Add [<<Phi>>,<<One>>]              loop:<<Loop>>      outer_loop:none
37   //
38   /// CHECK-START: int Main.breakLoop(int[]) induction_var_analysis (after)
39   /// CHECK-DAG: <<Par:l\d+>>  ParameterValue                     loop:none
40   /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0                      loop:none
41   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                      loop:none
42   /// CHECK-DAG: <<Nil:l\d+>>  NullCheck [<<Par>>]                loop:none
43   /// CHECK-DAG: <<Phi:i\d+>>  Phi [<<Zero>>,<<AddI:i\d+>>]       loop:<<Loop:B\d+>> outer_loop:none
44   /// CHECK-DAG: <<LE:z\d+>>   LessThanOrEqual [<<Phi>>,{{i\d+}}] loop:<<Loop>>      outer_loop:none
45   /// CHECK-DAG:               If [<<LE>>]                        loop:<<Loop>>      outer_loop:none
46   /// CHECK-DAG: <<Bnd:i\d+>>  BoundsCheck [<<Phi>>,{{i\d+}}]     loop:<<Loop>>      outer_loop:none
47   /// CHECK-DAG:               ArraySet [<<Nil>>,<<Bnd>>,<<One>>] loop:<<Loop>>      outer_loop:none
48   /// CHECK-DAG: <<AddI>>      Add [<<Phi>>,<<One>>]              loop:<<Loop>>      outer_loop:none
49   //
50   /// CHECK-START-ARM64: int Main.breakLoop(int[]) loop_optimization (after)
51   /// CHECK-DAG: <<Par:l\d+>>  ParameterValue                          loop:none
52   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                           loop:none
53   /// CHECK-DAG: <<Four:i\d+>> IntConstant 4                           loop:none
54   /// CHECK-DAG: <<Nil:l\d+>>  NullCheck [<<Par>>]                     loop:none
55   /// CHECK-DAG: <<Rep:d\d+>>  VecReplicateScalar [<<One>>]            loop:none
56   /// CHECK-DAG:               VecStore [<<Nil>>,<<Phi:i\d+>>,<<Rep>>] loop:<<Loop:B\d+>> outer_loop:none
57   /// CHECK-DAG:               Add [<<Phi>>,<<Four>>]                  loop:<<Loop>>      outer_loop:none
breakLoop(int[] a)58   static int breakLoop(int[] a) {
59     int l = 0;
60     int u = a.length - 1;
61     int i = l;
62     if (l <= u) {
63       while (true) {
64         a[i] = 1;
65         if (i == u) break;
66         i++;
67       }
68     }
69     return i;
70   }
71 
72   /// CHECK-START: int Main.breakLoopDown(int[]) induction_var_analysis (before)
73   /// CHECK-DAG: <<Par:l\d+>>  ParameterValue                     loop:none
74   /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0                      loop:none
75   /// CHECK-DAG: <<MOne:i\d+>> IntConstant -1                     loop:none
76   /// CHECK-DAG: <<Two:i\d+>>  IntConstant 2                      loop:none
77   /// CHECK-DAG: <<Nil:l\d+>>  NullCheck [<<Par>>]                loop:none
78   /// CHECK-DAG: <<Phi:i\d+>>  Phi [{{i\d+}},<<AddI:i\d+>>]       loop:<<Loop:B\d+>> outer_loop:none
79   /// CHECK-DAG: <<Bnd:i\d+>>  BoundsCheck [<<Phi>>,{{i\d+}}]     loop:<<Loop>>      outer_loop:none
80   /// CHECK-DAG:               ArraySet [<<Nil>>,<<Bnd>>,<<Two>>] loop:<<Loop>>      outer_loop:none
81   /// CHECK-DAG: <<NE:z\d+>>   NotEqual [<<Phi>>,<<Zero>>]        loop:<<Loop>>      outer_loop:none
82   /// CHECK-DAG:               If [<<NE>>]                        loop:<<Loop>>      outer_loop:none
83   /// CHECK-DAG: <<AddI>>      Add [<<Phi>>,<<MOne>>]             loop:<<Loop>>      outer_loop:none
84   //
85   /// CHECK-START: int Main.breakLoopDown(int[]) induction_var_analysis (after)
86   /// CHECK-DAG: <<Par:l\d+>>  ParameterValue                        loop:none
87   /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0                         loop:none
88   /// CHECK-DAG: <<MOne:i\d+>> IntConstant -1                        loop:none
89   /// CHECK-DAG: <<Two:i\d+>>  IntConstant 2                         loop:none
90   /// CHECK-DAG: <<Nil:l\d+>>  NullCheck [<<Par>>]                   loop:none
91   /// CHECK-DAG: <<Phi:i\d+>>  Phi [{{i\d+}},<<AddI:i\d+>>]          loop:<<Loop:B\d+>> outer_loop:none
92   /// CHECK-DAG: <<GE:z\d+>>   GreaterThanOrEqual [<<Phi>>,<<Zero>>] loop:<<Loop>>      outer_loop:none
93   /// CHECK-DAG:               If [<<GE>>]                           loop:<<Loop>>      outer_loop:none
94   /// CHECK-DAG: <<Bnd:i\d+>>  BoundsCheck [<<Phi>>,{{i\d+}}]        loop:<<Loop>>      outer_loop:none
95   /// CHECK-DAG:               ArraySet [<<Nil>>,<<Bnd>>,<<Two>>]    loop:<<Loop>>      outer_loop:none
96   /// CHECK-DAG: <<AddI>>      Add [<<Phi>>,<<MOne>>]                loop:<<Loop>>      outer_loop:none
breakLoopDown(int[] a)97   static int breakLoopDown(int[] a) {
98     int l = 0;
99     int u = a.length - 1;
100     int i = u;
101     if (u >= l) {
102       while (true) {
103         a[i] = 2;
104         if (i == l) break;
105         i--;
106       }
107     }
108     return i;
109   }
110 
111   /// CHECK-START: int Main.breakLoopSafeConst(int[]) induction_var_analysis (before)
112   /// CHECK-DAG: <<Par:l\d+>>   ParameterValue                       loop:none
113   /// CHECK-DAG: <<One:i\d+>>   IntConstant 1                        loop:none
114   /// CHECK-DAG: <<Three:i\d+>> IntConstant 3                        loop:none
115   /// CHECK-DAG: <<L1:i\d+>>    IntConstant 2147483631               loop:none
116   /// CHECK-DAG: <<L2:i\d+>>    IntConstant 2147483646               loop:none
117   /// CHECK-DAG: <<Phi:i\d+>>   Phi [<<L1>>,<<AddI:i\d+>>]           loop:<<Loop:B\d+>> outer_loop:none
118   /// CHECK-DAG: <<Sub:i\d+>>   Sub [<<Phi>>,<<L1>>]                 loop:<<Loop>>      outer_loop:none
119   /// CHECK-DAG: <<Nil:l\d+>>   NullCheck [<<Par>>]                  loop:<<Loop>>      outer_loop:none
120   /// CHECK-DAG: <<Bnd:i\d+>>   BoundsCheck [<<Sub>>,{{i\d+}}]       loop:<<Loop>>      outer_loop:none
121   /// CHECK-DAG:                ArraySet [<<Nil>>,<<Bnd>>,<<Three>>] loop:<<Loop>>      outer_loop:none
122   /// CHECK-DAG: <<NE:z\d+>>    NotEqual [<<Phi>>,<<L2>>]            loop:<<Loop>>      outer_loop:none
123   /// CHECK-DAG:                If [<<NE>>]                          loop:<<Loop>>      outer_loop:none
124   /// CHECK-DAG: <<AddI>>       Add [<<Phi>>,<<One>>]                loop:<<Loop>>      outer_loop:none
125   //
126   /// CHECK-START: int Main.breakLoopSafeConst(int[]) induction_var_analysis (after)
127   /// CHECK-DAG: <<Par:l\d+>>  ParameterValue                        loop:none
128   /// CHECK-DAG: <<One:i\d+>>   IntConstant 1                        loop:none
129   /// CHECK-DAG: <<Three:i\d+>> IntConstant 3                        loop:none
130   /// CHECK-DAG: <<L1:i\d+>>    IntConstant 2147483631               loop:none
131   /// CHECK-DAG: <<L2:i\d+>>    IntConstant 2147483646               loop:none
132   /// CHECK-DAG: <<Phi:i\d+>>   Phi [<<L1>>,<<AddI:i\d+>>]           loop:<<Loop:B\d+>> outer_loop:none
133   /// CHECK-DAG: <<LE:z\d+>>    LessThanOrEqual [<<Phi>>,<<L2>>]     loop:<<Loop>>      outer_loop:none
134   /// CHECK-DAG: <<Sub:i\d+>>   Sub [<<Phi>>,<<L1>>]                 loop:<<Loop>>      outer_loop:none
135   /// CHECK-DAG: <<Nil:l\d+>>   NullCheck [<<Par>>]                  loop:<<Loop>>      outer_loop:none
136   /// CHECK-DAG: <<Bnd:i\d+>>   BoundsCheck [<<Sub>>,{{i\d+}}]       loop:<<Loop>>      outer_loop:none
137   /// CHECK-DAG:                ArraySet [<<Nil>>,<<Bnd>>,<<Three>>] loop:<<Loop>>      outer_loop:none
138   /// CHECK-DAG: <<AddI>>       Add [<<Phi>>,<<One>>]                loop:<<Loop>>      outer_loop:none
139   //
140   /// CHECK-START-ARM64: int Main.breakLoopSafeConst(int[]) loop_optimization (after)
141   /// CHECK-DAG: <<Par:l\d+>>   ParameterValue                          loop:none
142   /// CHECK-DAG: <<One:i\d+>>   IntConstant 1                           loop:none
143   /// CHECK-DAG: <<Three:i\d+>> IntConstant 3                           loop:none
144   /// CHECK-DAG: <<Four:i\d+>>  IntConstant 4                           loop:none
145   /// CHECK-DAG: <<Rep:d\d+>>   VecReplicateScalar [<<Three>>]          loop:none
146   /// CHECK-DAG:                VecStore [<<Par>>,<<Phi:i\d+>>,<<Rep>>] loop:<<Loop:B\d+>> outer_loop:none
147   /// CHECK-DAG:                Add [<<Phi>>,<<Four>>]                  loop:<<Loop>>      outer_loop:none
breakLoopSafeConst(int[] a)148   static int breakLoopSafeConst(int[] a) {
149     int l = Integer.MAX_VALUE - 16;
150     int u = Integer.MAX_VALUE - 1;
151     int i = l;
152     if (l <= u) {  // will be removed by simplifier
153       while (true) {
154         a[i - l] = 3;
155         if (i == u) break;
156         i++;
157       }
158     }
159     return i;
160   }
161 
162   /// CHECK-START: int Main.breakLoopUnsafeConst(int[]) induction_var_analysis (before)
163   /// CHECK-DAG: <<Par:l\d+>>   ParameterValue                       loop:none
164   /// CHECK-DAG: <<One:i\d+>>   IntConstant 1                        loop:none
165   /// CHECK-DAG: <<Four:i\d+>>  IntConstant 4                        loop:none
166   /// CHECK-DAG: <<L1:i\d+>>    IntConstant 2147483632               loop:none
167   /// CHECK-DAG: <<L2:i\d+>>    IntConstant 2147483647               loop:none
168   /// CHECK-DAG: <<Phi:i\d+>>   Phi [<<L1>>,<<AddI:i\d+>>]           loop:<<Loop:B\d+>> outer_loop:none
169   /// CHECK-DAG: <<Sub:i\d+>>   Sub [<<Phi>>,<<L1>>]                 loop:<<Loop>>      outer_loop:none
170   /// CHECK-DAG: <<Nil:l\d+>>   NullCheck [<<Par>>]                  loop:<<Loop>>      outer_loop:none
171   /// CHECK-DAG: <<Bnd:i\d+>>   BoundsCheck [<<Sub>>,{{i\d+}}]       loop:<<Loop>>      outer_loop:none
172   /// CHECK-DAG:                ArraySet [<<Nil>>,<<Bnd>>,<<Four>>]  loop:<<Loop>>      outer_loop:none
173   /// CHECK-DAG: <<NE:z\d+>>    NotEqual [<<Phi>>,<<L2>>]            loop:<<Loop>>      outer_loop:none
174   /// CHECK-DAG:                If [<<NE>>]                          loop:<<Loop>>      outer_loop:none
175   /// CHECK-DAG: <<AddI>>       Add [<<Phi>>,<<One>>]                loop:<<Loop>>      outer_loop:none
176   //
177   /// CHECK-START: int Main.breakLoopUnsafeConst(int[]) induction_var_analysis (after)
178   /// CHECK-DAG:                NotEqual
179   /// CHECK-NOT:                LessThanOrEqual
breakLoopUnsafeConst(int[] a)180   static int breakLoopUnsafeConst(int[] a) {
181     int l = Integer.MAX_VALUE - 15;
182     int u = Integer.MAX_VALUE;
183     int i = l;
184     if (l <= u) {  // will be removed by simplifier
185       while (true) {
186         a[i - l] = 4;
187         if (i == u) break;  // rewriting exit not safe!
188         i++;
189       }
190     }
191     return i;
192   }
193 
194   /// CHECK-START: int Main.breakLoopNastyPhi(int[]) induction_var_analysis (before)
195   /// CHECK-DAG: <<Par:l\d+>>  ParameterValue                      loop:none
196   /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0                       loop:none
197   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                       loop:none
198   /// CHECK-DAG: <<Five:i\d+>> IntConstant 5                       loop:none
199   /// CHECK-DAG: <<M123:i\d+>> IntConstant -123                    loop:none
200   /// CHECK-DAG: <<Nil:l\d+>>  NullCheck [<<Par>>]                 loop:none
201   /// CHECK-DAG: <<Phi:i\d+>>  Phi [<<Zero>>,<<AddI:i\d+>>]        loop:<<Loop:B\d+>> outer_loop:none
202   /// CHECK-DAG: <<Wrap:i\d+>> Phi [<<M123>>,<<Phi>>]              loop:<<Loop>>      outer_loop:none
203   /// CHECK-DAG: <<Bnd:i\d+>>  BoundsCheck [<<Phi>>,{{i\d+}}]      loop:<<Loop>>      outer_loop:none
204   /// CHECK-DAG:               ArraySet [<<Nil>>,<<Bnd>>,<<Five>>] loop:<<Loop>>      outer_loop:none
205   /// CHECK-DAG: <<NE:z\d+>>   NotEqual [{{i\d+}},<<Phi>>]         loop:<<Loop>>      outer_loop:none
206   /// CHECK-DAG:               If [<<NE>>]                         loop:<<Loop>>      outer_loop:none
207   /// CHECK-DAG: <<AddI>>      Add [<<Phi>>,<<One>>]               loop:<<Loop>>      outer_loop:none
208   /// CHECK-DAG: <<Comb:i\d+>> Phi [<<M123>>,<<Wrap>>]             loop:none
209   /// CHECK-DAG:               Return [<<Comb>>]                   loop:none
210   //
211   /// CHECK-START: int Main.breakLoopNastyPhi(int[]) induction_var_analysis (after)
212   /// CHECK-DAG:               NotEqual
213   /// CHECK-NOT:               LessThanOrEqual
breakLoopNastyPhi(int[] a)214   static int breakLoopNastyPhi(int[] a) {
215     int l = 0;
216     int u = a.length - 1;
217     int x = -123;
218     if (l <= u) {
219       int i = l;
220       while (true) {
221         a[i] = 5;
222         if (i == u) break;
223         x = i;
224         i++;
225       }
226     }
227     return x;  // keep another phi live
228   }
229 
230   /// CHECK-START: int Main.breakLoopReduction(int[]) induction_var_analysis (before)
231   /// CHECK-DAG: <<Par:l\d+>>  ParameterValue                 loop:none
232   /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0                  loop:none
233   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                  loop:none
234   /// CHECK-DAG: <<Nil:l\d+>>  NullCheck [<<Par>>]                 loop:none
235   /// CHECK-DAG: <<Red:i\d+>>  Phi [<<Zero>>,<<RedI:i\d+>>]   loop:<<Loop:B\d+>> outer_loop:none
236   /// CHECK-DAG: <<Phi:i\d+>>  Phi [<<Zero>>,<<AddI:i\d+>>]   loop:<<Loop>>      outer_loop:none
237   /// CHECK-DAG: <<Bnd:i\d+>>  BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>>      outer_loop:none
238   /// CHECK-DAG: <<Get:i\d+>>  ArrayGet [<<Nil>>,<<Bnd>>]     loop:<<Loop>>      outer_loop:none
239   /// CHECK-DAG: <<RedI>>      Add [<<Red>>,<<Get>>]          loop:<<Loop>>      outer_loop:none
240   /// CHECK-DAG: <<NE:z\d+>>   NotEqual [{{i\d+}},<<Phi>>]    loop:<<Loop>>      outer_loop:none
241   /// CHECK-DAG:               If [<<NE>>]                    loop:<<Loop>>      outer_loop:none
242   /// CHECK-DAG: <<AddI>>      Add [<<Phi>>,<<One>>]          loop:<<Loop>>      outer_loop:none
243   /// CHECK-DAG: <<Comb:i\d+>> Phi [<<Zero>>,<<RedI>>]        loop:none
244   /// CHECK-DAG:               Return [<<Comb>>]              loop:none
245   //
246   /// CHECK-START: int Main.breakLoopReduction(int[]) induction_var_analysis (after)
247   /// CHECK-DAG: <<Par:l\d+>>  ParameterValue                     loop:none
248   /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0                      loop:none
249   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                      loop:none
250   /// CHECK-DAG: <<Nil:l\d+>>  NullCheck [<<Par>>]                loop:none
251   /// CHECK-DAG: <<Red:i\d+>>  Phi [<<Zero>>,<<RedI:i\d+>>]       loop:<<Loop:B\d+>> outer_loop:none
252   /// CHECK-DAG: <<Phi:i\d+>>  Phi [<<Zero>>,<<AddI:i\d+>>]       loop:<<Loop>>      outer_loop:none
253   /// CHECK-DAG: <<LE:z\d+>>   LessThanOrEqual [<<Phi>>,{{i\d+}}] loop:<<Loop>>      outer_loop:none
254   /// CHECK-DAG:               If [<<LE>>]                        loop:<<Loop>>      outer_loop:none
255   /// CHECK-DAG: <<Bnd:i\d+>>  BoundsCheck [<<Phi>>,{{i\d+}}]     loop:<<Loop>>      outer_loop:none
256   /// CHECK-DAG: <<Get:i\d+>>  ArrayGet [<<Nil>>,<<Bnd>>]         loop:<<Loop>>      outer_loop:none
257   /// CHECK-DAG: <<RedI>>      Add [<<Red>>,<<Get>>]              loop:<<Loop>>      outer_loop:none
258   /// CHECK-DAG: <<AddI>>      Add [<<Phi>>,<<One>>]              loop:<<Loop>>      outer_loop:none
259   /// CHECK-DAG: <<Comb:i\d+>> Phi [<<Zero>>,<<Red>>]             loop:none
260   /// CHECK-DAG:               Return [<<Comb>>]                  loop:none
261   //
262   /// CHECK-START-ARM64: int Main.breakLoopReduction(int[]) loop_optimization (after)
263   /// CHECK-DAG: <<Par:l\d+>>   ParameterValue              loop:none
264   /// CHECK-DAG: <<Zero:i\d+>>  IntConstant 0               loop:none
265   /// CHECK-DAG: <<Exp:d\d+>>   VecSetScalars [<<Zero>>]    loop:none
266   /// CHECK-DAG: <<VPhi:d\d+>>  Phi [<<Exp>>,<<VAdd:d\d+>>] loop:<<Loop:B\d+>> outer_loop:none
267   /// CHECK-DAG: <<VLoad:d\d+>> VecLoad                     loop:<<Loop>>      outer_loop:none
268   /// CHECK-DAG: <<VAdd>>       VecAdd [<<VPhi>>,<<VLoad>>] loop:<<Loop>>      outer_loop:none
breakLoopReduction(int[] a)269   static int breakLoopReduction(int[] a) {
270     int l = 0;
271     int u = a.length - 1;
272     int x = 0;
273     if (l <= u) {
274       int i = l;
275       while (true) {
276         x += a[i];
277         if (i == u) break;
278         i++;
279       }
280     }
281     return x;
282   }
283 
284   //
285   // Test driver.
286   //
287 
main(String[] args)288   public static void main(String[] args) {
289     int[] a = new int[100];
290 
291     expectEquals(99, breakLoop(a));
292     for (int i = 0; i < a.length; i++) {
293       expectEquals(1, a[i]);
294     }
295 
296     expectEquals(0, breakLoopDown(a));
297     for (int i = 0; i < a.length; i++) {
298       expectEquals(2, a[i]);
299     }
300 
301     expectEquals(Integer.MAX_VALUE - 1, breakLoopSafeConst(a));
302     for (int i = 0; i < a.length; i++) {
303       int e = i < 16 ? 3 : 2;
304       expectEquals(e, a[i]);
305     }
306 
307     expectEquals(Integer.MAX_VALUE, breakLoopUnsafeConst(a));
308     for (int i = 0; i < a.length; i++) {
309       int e = i < 16 ? 4 : 2;
310       expectEquals(e, a[i]);
311     }
312 
313     expectEquals(98, breakLoopNastyPhi(a));
314     for (int i = 0; i < a.length; i++) {
315       expectEquals(5, a[i]);
316     }
317 
318     expectEquals(500, breakLoopReduction(a));
319 
320     System.out.println("passed");
321   }
322 
323   private static void expectEquals(int expected, int result) {
324     if (expected != result) {
325       throw new Error("Expected: " + expected + ", found: " + result);
326     }
327   }
328 }
329