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  * Regression tests for loop optimizations.
19  */
20 public class Main {
21 
ensureJitCompiled(Class<?> cls, String methodName)22   private static native void ensureJitCompiled(Class<?> cls, String methodName);
23 
24   /// CHECK-START: int Main.earlyExitFirst(int) loop_optimization (before)
25   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
26   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
27   //
28   /// CHECK-START: int Main.earlyExitFirst(int) loop_optimization (after)
29   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
30   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
earlyExitFirst(int m)31   static int earlyExitFirst(int m) {
32     int k = 0;
33     for (int i = 0; i < 10; i++) {
34       if (i == m) {
35         return k;
36       }
37       k++;
38     }
39     return k;
40   }
41 
42   /// CHECK-START: int Main.earlyExitLast(int) loop_optimization (before)
43   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
44   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
45   //
46   /// CHECK-START: int Main.earlyExitLast(int) loop_optimization (after)
47   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
48   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
earlyExitLast(int m)49   static int earlyExitLast(int m) {
50     int k = 0;
51     for (int i = 0; i < 10; i++) {
52       k++;
53       if (i == m) {
54         return k;
55       }
56     }
57     return k;
58   }
59 
60   /// CHECK-START: int Main.earlyExitNested() loop_optimization (before)
61   /// CHECK-DAG: Phi loop:<<Loop1:B\d+>> outer_loop:none
62   /// CHECK-DAG: Phi loop:<<Loop1>>      outer_loop:none
63   /// CHECK-DAG: Phi loop:<<Loop2:B\d+>> outer_loop:<<Loop1>>
64   /// CHECK-DAG: Phi loop:<<Loop2>>      outer_loop:<<Loop1>>
65   //
66   /// CHECK-START: int Main.earlyExitNested() loop_optimization (after)
67   /// CHECK-DAG: Phi loop:<<Loop1:B\d+>> outer_loop:none
68   /// CHECK-DAG: Phi loop:<<Loop1>>      outer_loop:none
69   //
70   /// CHECK-START: int Main.earlyExitNested() loop_optimization (after)
71   /// CHECK-NOT: Phi loop:{{B\d+}} outer_loop:{{B\d+}}
earlyExitNested()72   static int earlyExitNested() {
73     int offset = 0;
74     for (int i = 0; i < 2; i++) {
75       int start = offset;
76       // This loop can be removed.
77       for (int j = 0; j < 2; j++) {
78         offset++;
79       }
80       if (i == 1) {
81         return start;
82       }
83     }
84     return 0;
85   }
86 
87   // Regression test for b/33774618: transfer operations involving
88   // narrowing linear induction should be done correctly.
89   //
90   /// CHECK-START: int Main.transferNarrowWrap() loop_optimization (before)
91   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
92   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
93   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
94   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
95   //
96   /// CHECK-START: int Main.transferNarrowWrap() loop_optimization (after)
97   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
98   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
99   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
100   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
transferNarrowWrap()101   static int transferNarrowWrap() {
102     short x = 0;
103     int w = 10;
104     int v = 3;
105     for (int i = 0; i < 10; i++) {
106       v = w + 1;    // transfer on wrap-around
107       w = x;   // wrap-around
108       x += 2;  // narrowing linear
109     }
110     return v;
111   }
112 
113   // Regression test for b/33774618: transfer operations involving
114   // narrowing linear induction should be done correctly
115   // (currently rejected, could be improved).
116   //
117   /// CHECK-START: int Main.polynomialShort() loop_optimization (before)
118   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
119   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
120   //
121   /// CHECK-START: int Main.polynomialShort() loop_optimization (after)
122   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
123   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
polynomialShort()124   static int polynomialShort() {
125     int x = 0;
126     for (short i = 0; i < 10; i++) {
127       x = x - i;  // polynomial on narrowing linear
128     }
129     return x;
130   }
131 
132   // Regression test for b/33774618: transfer operations involving
133   // narrowing linear induction should be done correctly
134   // (currently rejected, could be improved).
135   //
136   /// CHECK-START: int Main.polynomialIntFromLong() loop_optimization (before)
137   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
138   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
139   //
140   /// CHECK-START: int Main.polynomialIntFromLong() loop_optimization (after)
141   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
142   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
polynomialIntFromLong()143   static int polynomialIntFromLong() {
144     int x = 0;
145     for (long i = 0; i < 10; i++) {
146       x = x - (int) i;  // polynomial on narrowing linear
147     }
148     return x;
149   }
150 
151   /// CHECK-START: int Main.polynomialInt() loop_optimization (before)
152   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
153   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
154   //
155   /// CHECK-START: int Main.polynomialInt() loop_optimization (after)
156   /// CHECK-NOT: Phi
157   //
158   /// CHECK-START: int Main.polynomialInt() instruction_simplifier$after_bce (after)
159   /// CHECK-DAG: <<Int:i\d+>>  IntConstant -45  loop:none
160   /// CHECK-DAG:               Return [<<Int>>] loop:none
polynomialInt()161   static int polynomialInt() {
162     int x = 0;
163     for (int i = 0; i < 10; i++) {
164       x = x - i;
165     }
166     return x;
167   }
168 
169   // Regression test for b/34779592 (found with fuzz testing): overflow for last value
170   // of division truncates to zero, for multiplication it simply truncates.
171   //
172   /// CHECK-START: int Main.geoIntDivLastValue(int) loop_optimization (before)
173   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
174   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
175   //
176   /// CHECK-START: int Main.geoIntDivLastValue(int) loop_optimization (after)
177   /// CHECK-NOT: Phi
178   //
179   /// CHECK-START: int Main.geoIntDivLastValue(int) instruction_simplifier$after_bce (after)
180   /// CHECK-DAG: <<Int:i\d+>> IntConstant 0    loop:none
181   /// CHECK-DAG:              Return [<<Int>>] loop:none
geoIntDivLastValue(int x)182   static int geoIntDivLastValue(int x) {
183     for (int i = 0; i < 2; i++) {
184       x /= 1081788608;
185     }
186     return x;
187   }
188 
189   /// CHECK-START: int Main.geoIntMulLastValue(int) loop_optimization (before)
190   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
191   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
192   //
193   /// CHECK-START: int Main.geoIntMulLastValue(int) loop_optimization (after)
194   /// CHECK-NOT: Phi
195   //
196   /// CHECK-START: int Main.geoIntMulLastValue(int) instruction_simplifier$after_bce (after)
197   /// CHECK-DAG: <<Par:i\d+>> ParameterValue         loop:none
198   /// CHECK-DAG: <<Int:i\d+>> IntConstant -194211840 loop:none
199   /// CHECK-DAG: <<Mul:i\d+>> Mul [<<Par>>,<<Int>>]  loop:none
200   /// CHECK-DAG:              Return [<<Mul>>]       loop:none
geoIntMulLastValue(int x)201   static int geoIntMulLastValue(int x) {
202     for (int i = 0; i < 2; i++) {
203       x *= 1081788608;
204     }
205     return x;
206   }
207 
208   /// CHECK-START: long Main.geoLongDivLastValue(long) loop_optimization (before)
209   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
210   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
211   //
212   /// CHECK-START: long Main.geoLongDivLastValue(long) loop_optimization (after)
213   /// CHECK-NOT: Phi
214   //
215   /// CHECK-START: long Main.geoLongDivLastValue(long) instruction_simplifier$after_bce (after)
216   /// CHECK-DAG: <<Long:j\d+>> LongConstant 0    loop:none
217   /// CHECK-DAG:               Return [<<Long>>] loop:none
218   //
219   // Tests overflow in the divisor (while updating intermediate result).
geoLongDivLastValue(long x)220   static long geoLongDivLastValue(long x) {
221     for (int i = 0; i < 10; i++) {
222       x /= 1081788608;
223     }
224     return x;
225   }
226 
227   /// CHECK-START: long Main.geoLongDivLastValue() loop_optimization (before)
228   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
229   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
230   //
231   /// CHECK-START: long Main.geoLongDivLastValue() loop_optimization (after)
232   /// CHECK-NOT: Phi
233   //
234   /// CHECK-START: long Main.geoLongDivLastValue() instruction_simplifier$after_bce (after)
235   /// CHECK-DAG: <<Long:j\d+>> LongConstant 0    loop:none
236   /// CHECK-DAG:               Return [<<Long>>] loop:none
237   //
238   // Tests overflow in the divisor (while updating base).
geoLongDivLastValue()239   static long geoLongDivLastValue() {
240     long x = -1;
241     for (int i2 = 0; i2 < 2; i2++) {
242       x /= (Long.MAX_VALUE);
243     }
244     return x;
245   }
246 
247   /// CHECK-START: long Main.geoLongMulLastValue(long) loop_optimization (before)
248   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
249   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
250   //
251   /// CHECK-START: long Main.geoLongMulLastValue(long) loop_optimization (after)
252   /// CHECK-NOT: Phi
253   //
254   /// CHECK-START: long Main.geoLongMulLastValue(long) instruction_simplifier$after_bce (after)
255   /// CHECK-DAG: <<Par:j\d+>>  ParameterValue                    loop:none
256   /// CHECK-DAG: <<Long:j\d+>> LongConstant -8070450532247928832 loop:none
257   /// CHECK-DAG: <<Mul:j\d+>>  Mul [<<Par>>,<<Long>>]            loop:none
258   /// CHECK-DAG:               Return [<<Mul>>]                  loop:none
geoLongMulLastValue(long x)259   static long geoLongMulLastValue(long x) {
260     for (int i = 0; i < 10; i++) {
261       x *= 1081788608;
262     }
263     return x;
264   }
265 
266   // If vectorized, the narrowing subscript should not cause
267   // type inconsistencies in the synthesized code.
narrowingSubscript(float[] a)268   static void narrowingSubscript(float[] a) {
269     float val = 2.0f;
270     for (long i = 0; i < a.length; i++) {
271       a[(int) i] += val;
272     }
273   }
274 
275   // If vectorized, invariant stride should be recognized
276   // as a reduction, not a unit stride in outer loop.
reduc(int[] xx, int[] yy)277   static void reduc(int[] xx, int[] yy) {
278     for (int i0 = 0; i0 < 2; i0++) {
279       for (int i1 = 0; i1 < 469; i1++) {
280         xx[i0] -= (++yy[i1]);
281       }
282     }
283   }
284 
285   /// CHECK-START: void Main.string2Bytes(char[], java.lang.String) loop_optimization (before)
286   /// CHECK-DAG: ArrayGet loop:<<Loop:B\d+>> outer_loop:none
287   /// CHECK-DAG: ArraySet loop:<<Loop>>      outer_loop:none
288   //
289   /// CHECK-START-ARM: void Main.string2Bytes(char[], java.lang.String) loop_optimization (after)
290   /// CHECK-NOT: VecLoad
291   //
292   /// CHECK-START-ARM64: void Main.string2Bytes(char[], java.lang.String) loop_optimization (after)
293   /// CHECK-DAG: VecLoad  loop:<<Loop:B\d+>> outer_loop:none
294   /// CHECK-DAG: VecStore loop:<<Loop>>      outer_loop:none
295   //
296   // NOTE: should correctly deal with compressed and uncompressed cases.
297   //
298   /// CHECK-START-MIPS64: void Main.string2Bytes(char[], java.lang.String) loop_optimization (after)
299   /// CHECK-NOT: VecLoad
string2Bytes(char[] a, String b)300   private static void string2Bytes(char[] a, String b) {
301     int min = Math.min(a.length, b.length());
302     for (int i = 0; i < min; i++) {
303       a[i] = b.charAt(i);
304     }
305   }
306 
307   /// CHECK-START-ARM: void Main.$noinline$stringToShorts(short[], java.lang.String) loop_optimization (after)
308   /// CHECK-NOT: VecLoad
309 
310   /// CHECK-START-ARM64: void Main.$noinline$stringToShorts(short[], java.lang.String) loop_optimization (after)
311   /// CHECK-DAG: VecLoad  loop:<<Loop:B\d+>> outer_loop:none
312   /// CHECK-DAG: VecStore loop:<<Loop>>      outer_loop:none
$noinline$stringToShorts(short[] dest, String src)313   private static void $noinline$stringToShorts(short[] dest, String src) {
314     int min = Math.min(dest.length, src.length());
315     for (int i = 0; i < min; ++i) {
316       dest[i] = (short) src.charAt(i);
317     }
318   }
319 
320   // A strange function that does not inline.
$noinline$foo(boolean x, int n)321   private static void $noinline$foo(boolean x, int n) {
322     if (n < 0)
323       throw new Error("oh no");
324     if (n > 100) {
325       $noinline$foo(!x, n - 1);
326       $noinline$foo(!x, n - 2);
327       $noinline$foo(!x, n - 3);
328       $noinline$foo(!x, n - 4);
329     }
330   }
331 
332   // A loop with environment uses of x (the terminating condition). As exposed by bug
333   // b/37247891, the loop can be unrolled, but should handle the (unlikely, but clearly
334   // not impossible) environment uses of the terminating condition in a correct manner.
envUsesInCond()335   private static void envUsesInCond() {
336     boolean x = false;
337     for (int i = 0; !(x = i >= 1); i++) {
338       $noinline$foo(true, i);
339     }
340   }
341 
342   /// CHECK-START: void Main.oneBoth(short[], char[]) loop_optimization (before)
343   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                       loop:none
344   /// CHECK-DAG: <<Phi:i\d+>>  Phi                                 loop:<<Loop:B\d+>> outer_loop:none
345   /// CHECK-DAG:               ArraySet [{{l\d+}},<<Phi>>,<<One>>] loop:<<Loop>>      outer_loop:none
346   /// CHECK-DAG:               ArraySet [{{l\d+}},<<Phi>>,<<One>>] loop:<<Loop>>      outer_loop:none
347   //
348   /// CHECK-START-ARM: void Main.oneBoth(short[], char[]) loop_optimization (after)
349   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                             loop:none
350   /// CHECK-DAG: <<Repl:d\d+>> VecReplicateScalar [<<One>>]              loop:none
351   /// CHECK-DAG:               VecStore [{{l\d+}},<<Phi:i\d+>>,<<Repl>>] loop:<<Loop:B\d+>> outer_loop:none
352   /// CHECK-DAG:               VecStore [{{l\d+}},<<Phi>>,<<Repl>>]      loop:<<Loop>>      outer_loop:none
353   //
354   /// CHECK-START-ARM64: void Main.oneBoth(short[], char[]) loop_optimization (after)
355   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                             loop:none
356   /// CHECK-DAG: <<Repl:d\d+>> VecReplicateScalar [<<One>>]              loop:none
357   /// CHECK-DAG:               VecStore [{{l\d+}},<<Phi:i\d+>>,<<Repl>>] loop:<<Loop:B\d+>> outer_loop:none
358   /// CHECK-DAG:               VecStore [{{l\d+}},<<Phi>>,<<Repl>>]      loop:<<Loop>>      outer_loop:none
359   //
360   /// CHECK-START-MIPS64: void Main.oneBoth(short[], char[]) loop_optimization (after)
361   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                             loop:none
362   /// CHECK-DAG: <<Repl:d\d+>> VecReplicateScalar [<<One>>]              loop:none
363   /// CHECK-DAG:               VecStore [{{l\d+}},<<Phi:i\d+>>,<<Repl>>] loop:<<Loop:B\d+>> outer_loop:none
364   /// CHECK-DAG:               VecStore [{{l\d+}},<<Phi>>,<<Repl>>]      loop:<<Loop>>      outer_loop:none
365   //
366   // Bug b/37764324: integral same-length packed types can be mixed freely.
oneBoth(short[] a, char[] b)367   private static void oneBoth(short[] a, char[] b) {
368     for (int i = 0; i < Math.min(a.length, b.length); i++) {
369       a[i] = 1;
370       b[i] = 1;
371     }
372   }
373 
374   // Bug b/37768917: potential dynamic BCE vs. loop optimizations
375   // case should be deal with correctly (used to DCHECK fail).
arrayInTripCount(int[] a, byte[] b, int n)376   private static void arrayInTripCount(int[] a, byte[] b, int n) {
377     for (int k = 0; k < n; k++) {
378       for (int i = 0, u = a[0]; i < u; i++) {
379         b[i] += 2;
380       }
381     }
382   }
383 
384   /// CHECK-START: void Main.typeConv(byte[], byte[]) loop_optimization (before)
385   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                       loop:none
386   /// CHECK-DAG: <<Phi:i\d+>>  Phi                                 loop:<<Loop:B\d+>> outer_loop:none
387   /// CHECK-DAG: <<Get:b\d+>>  ArrayGet [{{l\d+}},<<Phi>>]         loop:<<Loop>>      outer_loop:none
388   /// CHECK-DAG: <<Add:i\d+>>  Add [<<Get>>,<<One>>]               loop:<<Loop>>      outer_loop:none
389   /// CHECK-DAG: <<Cnv:b\d+>>  TypeConversion [<<Add>>]            loop:<<Loop>>      outer_loop:none
390   /// CHECK-DAG:               ArraySet [{{l\d+}},<<Phi>>,<<Cnv>>] loop:<<Loop>>      outer_loop:none
391   //
392   /// CHECK-START-ARM: void Main.typeConv(byte[], byte[]) loop_optimization (after)
393   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                         loop:none
394   /// CHECK-DAG: <<Repl:d\d+>> VecReplicateScalar [<<One>>]          loop:none
395   /// CHECK-DAG: <<Load:d\d+>> VecLoad [{{l\d+}},<<Phi1:i\d+>>]      loop:<<Loop1:B\d+>> outer_loop:none
396   /// CHECK-DAG: <<Vadd:d\d+>> VecAdd [<<Load>>,<<Repl>>]            loop:<<Loop1>>      outer_loop:none
397   /// CHECK-DAG:               VecStore [{{l\d+}},<<Phi1>>,<<Vadd>>] loop:<<Loop1>>      outer_loop:none
398   /// CHECK-DAG: <<Get:b\d+>>  ArrayGet [{{l\d+}},<<Phi2:i\d+>>]     loop:<<Loop2:B\d+>> outer_loop:none
399   /// CHECK-DAG: <<Add:i\d+>>  Add [<<Get>>,<<One>>]                 loop:<<Loop2>>      outer_loop:none
400   /// CHECK-DAG: <<Cnv:b\d+>>  TypeConversion [<<Add>>]              loop:<<Loop2>>      outer_loop:none
401   /// CHECK-DAG:               ArraySet [{{l\d+}},<<Phi2>>,<<Cnv>>]  loop:<<Loop2>>      outer_loop:none
402   //
403   /// CHECK-START-ARM64: void Main.typeConv(byte[], byte[]) loop_optimization (after)
404   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                         loop:none
405   /// CHECK-DAG: <<Repl:d\d+>> VecReplicateScalar [<<One>>]          loop:none
406   /// CHECK-DAG: <<Load:d\d+>> VecLoad [{{l\d+}},<<Phi1:i\d+>>]      loop:<<Loop1:B\d+>> outer_loop:none
407   /// CHECK-DAG: <<Vadd:d\d+>> VecAdd [<<Load>>,<<Repl>>]            loop:<<Loop1>>      outer_loop:none
408   /// CHECK-DAG:               VecStore [{{l\d+}},<<Phi1>>,<<Vadd>>] loop:<<Loop1>>      outer_loop:none
409   /// CHECK-DAG: <<Get:b\d+>>  ArrayGet [{{l\d+}},<<Phi2:i\d+>>]     loop:<<Loop2:B\d+>> outer_loop:none
410   /// CHECK-DAG: <<Add:i\d+>>  Add [<<Get>>,<<One>>]                 loop:<<Loop2>>      outer_loop:none
411   /// CHECK-DAG: <<Cnv:b\d+>>  TypeConversion [<<Add>>]              loop:<<Loop2>>      outer_loop:none
412   /// CHECK-DAG:               ArraySet [{{l\d+}},<<Phi2>>,<<Cnv>>]  loop:<<Loop2>>      outer_loop:none
413   //
414   /// CHECK-START-MIPS64: void Main.typeConv(byte[], byte[]) loop_optimization (after)
415   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                         loop:none
416   /// CHECK-DAG: <<Repl:d\d+>> VecReplicateScalar [<<One>>]          loop:none
417   /// CHECK-DAG: <<Load:d\d+>> VecLoad [{{l\d+}},<<Phi1:i\d+>>]      loop:<<Loop1:B\d+>> outer_loop:none
418   /// CHECK-DAG: <<Vadd:d\d+>> VecAdd [<<Load>>,<<Repl>>]            loop:<<Loop1>>      outer_loop:none
419   /// CHECK-DAG:               VecStore [{{l\d+}},<<Phi1>>,<<Vadd>>] loop:<<Loop1>>      outer_loop:none
420   /// CHECK-DAG: <<Get:b\d+>>  ArrayGet [{{l\d+}},<<Phi2:i\d+>>]     loop:<<Loop2:B\d+>> outer_loop:none
421   /// CHECK-DAG: <<Add:i\d+>>  Add [<<Get>>,<<One>>]                 loop:<<Loop2>>      outer_loop:none
422   /// CHECK-DAG: <<Cnv:b\d+>>  TypeConversion [<<Add>>]              loop:<<Loop2>>      outer_loop:none
423   /// CHECK-DAG:               ArraySet [{{l\d+}},<<Phi2>>,<<Cnv>>]  loop:<<Loop2>>      outer_loop:none
424   //
425   // Scalar code in cleanup loop uses correct byte type on array get and type conversion.
typeConv(byte[] a, byte[] b)426   private static void typeConv(byte[] a, byte[] b) {
427     int len = Math.min(a.length, b.length);
428     for (int i = 0; i < len; i++) {
429       a[i] = (byte) (b[i] + 1);
430     }
431   }
432 
433   // Environment of an instruction, removed during SimplifyInduction, should be adjusted.
434   //
435   /// CHECK-START: void Main.inductionMax(int[]) loop_optimization (before)
436   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
437   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
438   //
439   /// CHECK-START: void Main.inductionMax(int[]) loop_optimization (after)
440   /// CHECK-NOT: Phi
inductionMax(int[] a)441   private static void inductionMax(int[] a) {
442    int s = 0;
443     for (int i = 0; i < 10; i++) {
444       s = Math.max(s, 5);
445     }
446   }
447 
448   /// CHECK-START: int Main.feedsIntoDeopt(int[]) loop_optimization (before)
449   /// CHECK-DAG: Phi loop:<<Loop1:B\d+>> outer_loop:none
450   /// CHECK-DAG: Phi loop:<<Loop1>>      outer_loop:none
451   /// CHECK-DAG: Phi loop:<<Loop2:B\d+>> outer_loop:none
452   //
453   /// CHECK-EVAL: "<<Loop1>>" != "<<Loop2>>"
454   //
455   /// CHECK-START: int Main.feedsIntoDeopt(int[]) loop_optimization (after)
456   /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
457   /// CHECK-NOT: Phi
feedsIntoDeopt(int[] a)458   static int feedsIntoDeopt(int[] a) {
459     // Reduction should be removed.
460     int r = 0;
461     for (int i = 0; i < 100; i++) {
462       r += 10;
463     }
464     // Even though uses feed into deopts of BCE.
465     for (int i = 1; i < 100; i++) {
466       a[i] = a[i - 1];
467     }
468     return r;
469   }
470 
absCanBeNegative(int x)471   static int absCanBeNegative(int x) {
472     int a[] = { 1, 2, 3 };
473     int y = 0;
474     for (int i = Math.abs(x); i < a.length; i++) {
475       y += a[i];
476     }
477     return y;
478   }
479 
480   // b/65478356: sum up 2-dim array.
sum(int[][] a)481   static int sum(int[][] a) {
482     int sum = 0;
483     for (int y = 0; y < a.length; y++) {
484       int[] aa = a[y];
485       for (int x = 0; x < aa.length; x++) {
486         sum += aa[x];
487       }
488     }
489     return sum;
490   }
491 
492   // Large loop body should not break unrolling computation.
largeBody(int[] x)493   static void largeBody(int[] x) {
494     for (int i = 0; i < 100; i++) {
495       x[i] = x[i] * 1 + x[i] * 2 + x[i] * 3 + x[i] * 4 + x[i] * 5 + x[i] * 6 +
496           x[i] * 7 + x[i] * 8 + x[i] * 9 + x[i] * 10 + x[i] * 11 + x[i] * 12 +
497           x[i] * 13 + x[i] * 14 + x[i] * 15 + x[i] * 1 + x[i] * 2 + x[i] * 3 + x[i] * 4 +
498           x[i] * 5 + x[i] * 6 + x[i] * 7 + x[i] * 8 + x[i] * 9 + x[i] * 10 + x[i] * 11 +
499           x[i] * 12 + x[i] * 13 + x[i] * 14 + x[i] * 15 + x[i] * 1 + x[i] * 2 + x[i] * 3 +
500           x[i] * 4 + x[i] * 5;
501     }
502   }
503 
504   // Mixed of 16-bit and 8-bit array references.
castAndNarrow(byte[] x, char[] y)505   static void castAndNarrow(byte[] x, char[] y) {
506     for (int i = 0; i < x.length; i++) {
507       x[i] = (byte) ((short) y[i] +  1);
508     }
509   }
510 
511   // Avoid bad scheduler-SIMD interaction.
doNotMoveSIMD()512   static int doNotMoveSIMD() {
513     int sum = 0;
514     for (int j = 0; j <= 8; j++) {
515       int[] a = new int[17];    // a[i] = 0;
516                                 // ConstructorFence ?
517       for (int i = 0; i < a.length; i++) {
518         a[i] += 1;              // a[i] = 1;
519       }
520       for (int i = 0; i < a.length; i++) {
521         sum += a[i];            // expect a[i] = 1;
522       }
523     }
524     return sum;
525   }
526 
527   // Ensure spilling saves full SIMD values.
reduction32Values(int[] a, int[] b, int[] c, int[] d)528   private static final int reduction32Values(int[] a, int[] b, int[] c, int[] d) {
529     int s0 = 0;
530     int s1 = 0;
531     int s2 = 0;
532     int s3 = 0;
533     int s4 = 0;
534     int s5 = 0;
535     int s6 = 0;
536     int s7 = 0;
537     int s8 = 0;
538     int s9 = 0;
539     int s10 = 0;
540     int s11 = 0;
541     int s12 = 0;
542     int s13 = 0;
543     int s14 = 0;
544     int s15 = 0;
545     int s16 = 0;
546     int s17 = 0;
547     int s18 = 0;
548     int s19 = 0;
549     int s20 = 0;
550     int s21 = 0;
551     int s22 = 0;
552     int s23 = 0;
553     int s24 = 0;
554     int s25 = 0;
555     int s26 = 0;
556     int s27 = 0;
557     int s28 = 0;
558     int s29 = 0;
559     int s30 = 0;
560     int s31 = 0;
561     for (int i = 1; i < 100; i++) {
562       s0 += a[i];
563       s1 += b[i];
564       s2 += c[i];
565       s3 += d[i];
566       s4 += a[i];
567       s5 += b[i];
568       s6 += c[i];
569       s7 += d[i];
570       s8 += a[i];
571       s9 += b[i];
572       s10 += c[i];
573       s11 += d[i];
574       s12 += a[i];
575       s13 += b[i];
576       s14 += c[i];
577       s15 += d[i];
578       s16 += a[i];
579       s17 += b[i];
580       s18 += c[i];
581       s19 += d[i];
582       s20 += a[i];
583       s21 += b[i];
584       s22 += c[i];
585       s23 += d[i];
586       s24 += a[i];
587       s25 += b[i];
588       s26 += c[i];
589       s27 += d[i];
590       s28 += a[i];
591       s29 += b[i];
592       s30 += c[i];
593       s31 += d[i];
594     }
595     return s0 + s1 + s2 + s3 + s4 + s5 + s6 + s7 + s8 + s9 + s10 + s11 + s12 + s13 + s14 + s15 +
596            s16 + s17 + s18 + s19 + s20 + s21 + s22 + s23 +
597            s24 + s25 + s26 + s27 + s28 + s29 + s30 + s31;
598   }
599 
reductionIntoReplication()600   public static int reductionIntoReplication() {
601     int[] a = { 1, 2, 3, 4 };
602     int x = 0;
603     for (int i = 0; i < 4; i++) {
604       x += a[i];
605     }
606     for (int i = 0; i < 4; i++) {
607       a[i] = x;
608     }
609     return a[3];
610   }
611 
main(String[] args)612   public static void main(String[] args) {
613     System.loadLibrary(args[0]);
614 
615     expectEquals(10, earlyExitFirst(-1));
616     for (int i = 0; i <= 10; i++) {
617       expectEquals(i, earlyExitFirst(i));
618     }
619     expectEquals(10, earlyExitFirst(11));
620 
621     expectEquals(10, earlyExitLast(-1));
622     for (int i = 0; i < 10; i++) {
623       expectEquals(i + 1, earlyExitLast(i));
624     }
625     expectEquals(10, earlyExitLast(10));
626     expectEquals(10, earlyExitLast(11));
627 
628     expectEquals(2, earlyExitNested());
629 
630     expectEquals(17, transferNarrowWrap());
631     expectEquals(-45, polynomialShort());
632     expectEquals(-45, polynomialIntFromLong());
633     expectEquals(-45, polynomialInt());
634 
635     expectEquals(0, geoIntDivLastValue(0));
636     expectEquals(0, geoIntDivLastValue(1));
637     expectEquals(0, geoIntDivLastValue(2));
638     expectEquals(0, geoIntDivLastValue(1081788608));
639     expectEquals(0, geoIntDivLastValue(-1081788608));
640     expectEquals(0, geoIntDivLastValue(2147483647));
641     expectEquals(0, geoIntDivLastValue(-2147483648));
642 
643     expectEquals(          0, geoIntMulLastValue(0));
644     expectEquals( -194211840, geoIntMulLastValue(1));
645     expectEquals( -388423680, geoIntMulLastValue(2));
646     expectEquals(-1041498112, geoIntMulLastValue(1081788608));
647     expectEquals( 1041498112, geoIntMulLastValue(-1081788608));
648     expectEquals(  194211840, geoIntMulLastValue(2147483647));
649     expectEquals(          0, geoIntMulLastValue(-2147483648));
650 
651     expectEquals(0L, geoLongDivLastValue(0L));
652     expectEquals(0L, geoLongDivLastValue(1L));
653     expectEquals(0L, geoLongDivLastValue(2L));
654     expectEquals(0L, geoLongDivLastValue(1081788608L));
655     expectEquals(0L, geoLongDivLastValue(-1081788608L));
656     expectEquals(0L, geoLongDivLastValue(2147483647L));
657     expectEquals(0L, geoLongDivLastValue(-2147483648L));
658     expectEquals(0L, geoLongDivLastValue(9223372036854775807L));
659     expectEquals(0L, geoLongDivLastValue(-9223372036854775808L));
660 
661     expectEquals(0L, geoLongDivLastValue());
662 
663     expectEquals(                   0L, geoLongMulLastValue(0L));
664     expectEquals(-8070450532247928832L, geoLongMulLastValue(1L));
665     expectEquals( 2305843009213693952L, geoLongMulLastValue(2L));
666     expectEquals(                   0L, geoLongMulLastValue(1081788608L));
667     expectEquals(                   0L, geoLongMulLastValue(-1081788608L));
668     expectEquals( 8070450532247928832L, geoLongMulLastValue(2147483647L));
669     expectEquals(                   0L, geoLongMulLastValue(-2147483648L));
670     expectEquals( 8070450532247928832L, geoLongMulLastValue(9223372036854775807L));
671     expectEquals(                   0L, geoLongMulLastValue(-9223372036854775808L));
672 
673     float[] a = new float[16];
674     narrowingSubscript(a);
675     for (int i = 0; i < 16; i++) {
676       expectEquals(2.0f, a[i]);
677     }
678 
679     int[] xx = new int[2];
680     int[] yy = new int[469];
681     reduc(xx, yy);
682     expectEquals(-469, xx[0]);
683     expectEquals(-938, xx[1]);
684     for (int i = 0; i < 469; i++) {
685       expectEquals(2, yy[i]);
686     }
687 
688     char[] aa = new char[23];
689     String bb = "hello world how are you";
690     string2Bytes(aa, bb);
691     for (int i = 0; i < aa.length; i++) {
692       expectEquals(aa[i], bb.charAt(i));
693     }
694     String cc = "\u1010\u2020llo world how are y\u3030\u4040";
695     string2Bytes(aa, cc);
696     for (int i = 0; i < aa.length; i++) {
697       expectEquals(aa[i], cc.charAt(i));
698     }
699 
700     short[] s2s = new short[12];
701     $noinline$stringToShorts(s2s, "abcdefghijkl");
702     for (int i = 0; i < s2s.length; ++i) {
703       expectEquals((short) "abcdefghijkl".charAt(i), s2s[i]);
704     }
705 
706     envUsesInCond();
707 
708     short[] dd = new short[23];
709     oneBoth(dd, aa);
710     for (int i = 0; i < aa.length; i++) {
711       expectEquals(aa[i], 1);
712       expectEquals(dd[i], 1);
713     }
714 
715     xx[0] = 10;
716     byte[] bt = new byte[10];
717     arrayInTripCount(xx, bt, 20);
718     for (int i = 0; i < bt.length; i++) {
719       expectEquals(40, bt[i]);
720     }
721 
722     byte[] b1 = new byte[259];  // few extra iterations
723     byte[] b2 = new byte[259];
724     for (int i = 0; i < 259; i++) {
725       b1[i] = 0;
726       b2[i] = (byte) i;
727     }
728     typeConv(b1, b2);
729     for (int i = 0; i < 259; i++) {
730       expectEquals((byte)(i + 1), b1[i]);
731     }
732 
733     inductionMax(yy);
734 
735     int[] f = new int[100];
736     f[0] = 11;
737     expectEquals(1000, feedsIntoDeopt(f));
738     for (int i = 0; i < 100; i++) {
739       expectEquals(11, f[i]);
740     }
741 
742     expectEquals(0, absCanBeNegative(-3));
743     expectEquals(3, absCanBeNegative(-2));
744     expectEquals(5, absCanBeNegative(-1));
745     expectEquals(6, absCanBeNegative(0));
746     expectEquals(5, absCanBeNegative(1));
747     expectEquals(3, absCanBeNegative(2));
748     expectEquals(0, absCanBeNegative(3));
749     expectEquals(0, absCanBeNegative(Integer.MAX_VALUE));
750     // Abs(min_int) = min_int.
751     int verify = 0;
752     try {
753       absCanBeNegative(Integer.MIN_VALUE);
754       verify = 1;
755     } catch (ArrayIndexOutOfBoundsException e) {
756       verify = 2;
757     }
758     expectEquals(2, verify);
759 
760     int[][] x = new int[128][128];
761     for (int i = 0; i < 128; i++) {
762       for (int j = 0; j < 128; j++) {
763         x[i][j] = -i - j;
764       }
765     }
766     expectEquals(-2080768, sum(x));
767 
768     largeBody(f);
769     for (int i = 0; i < 100; i++) {
770       expectEquals(2805, f[i]);
771     }
772 
773     char[] cx = new char[259];
774     for (int i = 0; i < 259; i++) {
775       cx[i] = (char) (i - 100);
776     }
777     castAndNarrow(b1, cx);
778     for (int i = 0; i < 259; i++) {
779       expectEquals((byte)((short) cx[i] + 1), b1[i]);
780     }
781 
782     expectEquals(153, doNotMoveSIMD());
783 
784     // This test exposed SIMDization issues on x86 and x86_64
785     // so we make sure the test runs with JIT enabled.
786     ensureJitCompiled(Main.class, "reduction32Values");
787     {
788       int[] a1 = new int[100];
789       int[] a2 = new int[100];
790       int[] a3 = new int[100];
791       int[] a4 = new int[100];
792       for (int i = 0; i < 100; i++) {
793         a1[i] = i;
794         a2[i] = 1;
795         a3[i] = 100 - i;
796         a4[i] = i % 16;
797       }
798       expectEquals(85800, reduction32Values(a1, a2, a3, a4));
799     }
800 
801     expectEquals(10, reductionIntoReplication());
802 
803     System.out.println("passed");
804   }
805 
expectEquals(int expected, int result)806   private static void expectEquals(int expected, int result) {
807     if (expected != result) {
808       throw new Error("Expected: " + expected + ", found: " + result);
809     }
810   }
811 
expectEquals(long expected, long result)812   private static void expectEquals(long expected, long result) {
813     if (expected != result) {
814       throw new Error("Expected: " + expected + ", found: " + result);
815     }
816   }
817 
expectEquals(float expected, float result)818   private static void expectEquals(float expected, float result) {
819     if (expected != result) {
820       throw new Error("Expected: " + expected + ", found: " + result);
821     }
822   }
823 }
824