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$before_codegen (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$before_codegen (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$before_codegen (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$before_codegen (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$before_codegen (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$before_codegen (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-IF:     hasIsaFeature("sve") and os.environ.get('ART_FORCE_TRY_PREDICATED_SIMD') == 'true'
294   //
295   //      TODO: Support CharAt for SVE.
296   ///     CHECK-NOT: VecLoad
297   //
298   /// CHECK-ELSE:
299   //
300   ///     CHECK-DAG: VecLoad  loop:<<Loop:B\d+>> outer_loop:none
301   ///     CHECK-DAG: VecStore loop:<<Loop>>      outer_loop:none
302   //
303   /// CHECK-FI:
304   //
305   // NOTE: should correctly deal with compressed and uncompressed cases.
string2Bytes(char[] a, String b)306   private static void string2Bytes(char[] a, String b) {
307     int min = Math.min(a.length, b.length());
308     for (int i = 0; i < min; i++) {
309       a[i] = b.charAt(i);
310     }
311   }
312 
313   /// CHECK-START-ARM: void Main.$noinline$stringToShorts(short[], java.lang.String) loop_optimization (after)
314   /// CHECK-NOT: VecLoad
315 
316   /// CHECK-START-ARM64: void Main.$noinline$stringToShorts(short[], java.lang.String) loop_optimization (after)
317   /// CHECK-IF:     hasIsaFeature("sve") and os.environ.get('ART_FORCE_TRY_PREDICATED_SIMD') == 'true'
318   //
319   //      TODO: Support CharAt for SVE.
320   ///     CHECK-NOT: VecLoad
321   //
322   /// CHECK-ELSE:
323   //
324   ///     CHECK-DAG: VecLoad  loop:<<Loop:B\d+>> outer_loop:none
325   ///     CHECK-DAG: VecStore loop:<<Loop>>      outer_loop:none
326   //
327   /// CHECK-FI:
$noinline$stringToShorts(short[] dest, String src)328   private static void $noinline$stringToShorts(short[] dest, String src) {
329     int min = Math.min(dest.length, src.length());
330     for (int i = 0; i < min; ++i) {
331       dest[i] = (short) src.charAt(i);
332     }
333   }
334 
335   // A strange function that does not inline.
$noinline$foo(boolean x, int n)336   private static void $noinline$foo(boolean x, int n) {
337     if (n < 0)
338       throw new Error("oh no");
339     if (n > 100) {
340       $noinline$foo(!x, n - 1);
341       $noinline$foo(!x, n - 2);
342       $noinline$foo(!x, n - 3);
343       $noinline$foo(!x, n - 4);
344     }
345   }
346 
347   // A loop with environment uses of x (the terminating condition). As exposed by bug
348   // b/37247891, the loop can be unrolled, but should handle the (unlikely, but clearly
349   // not impossible) environment uses of the terminating condition in a correct manner.
envUsesInCond()350   private static void envUsesInCond() {
351     boolean x = false;
352     for (int i = 0; !(x = i >= 1); i++) {
353       $noinline$foo(true, i);
354     }
355   }
356 
357   /// CHECK-START: void Main.oneBoth(short[], char[]) loop_optimization (before)
358   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                       loop:none
359   /// CHECK-DAG: <<Phi:i\d+>>  Phi                                 loop:<<Loop:B\d+>> outer_loop:none
360   /// CHECK-DAG:               ArraySet [{{l\d+}},<<Phi>>,<<One>>] loop:<<Loop>>      outer_loop:none
361   /// CHECK-DAG:               ArraySet [{{l\d+}},<<Phi>>,<<One>>] loop:<<Loop>>      outer_loop:none
362   //
363   /// CHECK-START-ARM: void Main.oneBoth(short[], char[]) loop_optimization (after)
364   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                             loop:none
365   /// CHECK-DAG: <<Repl:d\d+>> VecReplicateScalar [<<One>>]              loop:none
366   /// CHECK-DAG:               VecStore [{{l\d+}},<<Phi:i\d+>>,<<Repl>>] loop:<<Loop:B\d+>> outer_loop:none
367   /// CHECK-DAG:               VecStore [{{l\d+}},<<Phi>>,<<Repl>>]      loop:<<Loop>>      outer_loop:none
368   //
369   /// CHECK-START-ARM64: void Main.oneBoth(short[], char[]) loop_optimization (after)
370   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                             loop:none
371   /// CHECK-IF:     hasIsaFeature("sve") and os.environ.get('ART_FORCE_TRY_PREDICATED_SIMD') == 'true'
372   //
373   ///     CHECK-DAG: <<Repl:d\d+>>  VecReplicateScalar [<<One>>,{{j\d+}}]               loop:none
374   ///     CHECK-DAG: <<LoopP:j\d+>> VecPredWhile                                        loop:<<Loop:B\d+>> outer_loop:none
375   ///     CHECK-DAG:                VecStore [{{l\d+}},<<Phi:i\d+>>,<<Repl>>,<<LoopP>>] loop:<<Loop>>      outer_loop:none
376   ///     CHECK-DAG:                VecStore [{{l\d+}},<<Phi>>,<<Repl>>,<<LoopP>>]      loop:<<Loop>>      outer_loop:none
377   //
378   /// CHECK-ELSE:
379   //
380   ///     CHECK-DAG: <<Repl:d\d+>>  VecReplicateScalar [<<One>>]              loop:none
381   ///     CHECK-DAG:                VecStore [{{l\d+}},<<Phi:i\d+>>,<<Repl>>] loop:<<Loop:B\d+>> outer_loop:none
382   ///     CHECK-DAG:                VecStore [{{l\d+}},<<Phi>>,<<Repl>>]      loop:<<Loop>>      outer_loop:none
383   //
384   /// CHECK-FI:
385   //
386   // Bug b/37764324: integral same-length packed types can be mixed freely.
oneBoth(short[] a, char[] b)387   private static void oneBoth(short[] a, char[] b) {
388     for (int i = 0; i < Math.min(a.length, b.length); i++) {
389       a[i] = 1;
390       b[i] = 1;
391     }
392   }
393 
394   // Bug b/37768917: potential dynamic BCE vs. loop optimizations
395   // case should be deal with correctly (used to DCHECK fail).
arrayInTripCount(int[] a, byte[] b, int n)396   private static void arrayInTripCount(int[] a, byte[] b, int n) {
397     for (int k = 0; k < n; k++) {
398       for (int i = 0, u = a[0]; i < u; i++) {
399         b[i] += 2;
400       }
401     }
402   }
403 
404   /// CHECK-START: void Main.typeConv(byte[], byte[]) loop_optimization (before)
405   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                       loop:none
406   /// CHECK-DAG: <<Phi:i\d+>>  Phi                                 loop:<<Loop:B\d+>> outer_loop:none
407   /// CHECK-DAG: <<Get:b\d+>>  ArrayGet [{{l\d+}},<<Phi>>]         loop:<<Loop>>      outer_loop:none
408   /// CHECK-DAG: <<Add:i\d+>>  Add [<<Get>>,<<One>>]               loop:<<Loop>>      outer_loop:none
409   /// CHECK-DAG: <<Cnv:b\d+>>  TypeConversion [<<Add>>]            loop:<<Loop>>      outer_loop:none
410   /// CHECK-DAG:               ArraySet [{{l\d+}},<<Phi>>,<<Cnv>>] loop:<<Loop>>      outer_loop:none
411   //
412   /// CHECK-START-ARM: void Main.typeConv(byte[], byte[]) loop_optimization (after)
413   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                         loop:none
414 
415   /// CHECK-DAG: <<Repl:d\d+>> VecReplicateScalar [<<One>>]          loop:none
416   /// CHECK-DAG: <<Load:d\d+>> VecLoad [{{l\d+}},<<Phi1:i\d+>>]      loop:<<Loop1:B\d+>> outer_loop:none
417   /// CHECK-DAG: <<Vadd:d\d+>> VecAdd [<<Load>>,<<Repl>>]            loop:<<Loop1>>      outer_loop:none
418   /// CHECK-DAG:               VecStore [{{l\d+}},<<Phi1>>,<<Vadd>>] loop:<<Loop1>>      outer_loop:none
419   /// CHECK-DAG: <<Get:b\d+>>  ArrayGet [{{l\d+}},<<Phi2:i\d+>>]     loop:<<Loop2:B\d+>> outer_loop:none
420   /// CHECK-DAG: <<Add:i\d+>>  Add [<<Get>>,<<One>>]                 loop:<<Loop2>>      outer_loop:none
421   /// CHECK-DAG: <<Cnv:b\d+>>  TypeConversion [<<Add>>]              loop:<<Loop2>>      outer_loop:none
422   /// CHECK-DAG:               ArraySet [{{l\d+}},<<Phi2>>,<<Cnv>>]  loop:<<Loop2>>      outer_loop:none
423   //
424   /// CHECK-START-ARM64: void Main.typeConv(byte[], byte[]) loop_optimization (after)
425   /// CHECK-DAG: <<One:i\d+>>  IntConstant 1                         loop:none
426   /// CHECK-IF:     hasIsaFeature("sve") and os.environ.get('ART_FORCE_TRY_PREDICATED_SIMD') == 'true'
427   //
428   ///     CHECK-DAG: <<Repl:d\d+>>  VecReplicateScalar [<<One>>,{{j\d+}}]           loop:none
429   ///     CHECK-DAG: <<LoopP:j\d+>> VecPredWhile                                    loop:<<Loop1:B\d+>> outer_loop:none
430   ///     CHECK-DAG: <<Load:d\d+>>  VecLoad [{{l\d+}},<<Phi1:i\d+>>,<<LoopP>>]      loop:<<Loop1>>      outer_loop:none
431   ///     CHECK-DAG: <<Vadd:d\d+>>  VecAdd [<<Load>>,<<Repl>>,<<LoopP>>]            loop:<<Loop1>>      outer_loop:none
432   ///     CHECK-DAG:                VecStore [{{l\d+}},<<Phi1>>,<<Vadd>>,<<LoopP>>] loop:<<Loop1>>      outer_loop:none
433   //
434   /// CHECK-ELSE:
435   //
436   ///     CHECK-DAG: <<Repl:d\d+>>  VecReplicateScalar [<<One>>]          loop:none
437   ///     CHECK-DAG: <<Load:d\d+>>  VecLoad [{{l\d+}},<<Phi1:i\d+>>]      loop:<<Loop1:B\d+>> outer_loop:none
438   ///     CHECK-DAG: <<Vadd:d\d+>>  VecAdd [<<Load>>,<<Repl>>]            loop:<<Loop1>>      outer_loop:none
439   ///     CHECK-DAG:                VecStore [{{l\d+}},<<Phi1>>,<<Vadd>>] loop:<<Loop1>>      outer_loop:none
440   ///     CHECK-DAG: <<Get:b\d+>>   ArrayGet [{{l\d+}},<<Phi2:i\d+>>]     loop:<<Loop2:B\d+>> outer_loop:none
441   ///     CHECK-DAG: <<Add:i\d+>>   Add [<<Get>>,<<One>>]                 loop:<<Loop2>>      outer_loop:none
442   ///     CHECK-DAG: <<Cnv:b\d+>>   TypeConversion [<<Add>>]              loop:<<Loop2>>      outer_loop:none
443   ///     CHECK-DAG:                ArraySet [{{l\d+}},<<Phi2>>,<<Cnv>>]  loop:<<Loop2>>      outer_loop:none
444   //
445   /// CHECK-FI:
446   //
447   // Scalar code in cleanup loop uses correct byte type on array get and type conversion.
typeConv(byte[] a, byte[] b)448   private static void typeConv(byte[] a, byte[] b) {
449     int len = Math.min(a.length, b.length);
450     for (int i = 0; i < len; i++) {
451       a[i] = (byte) (b[i] + 1);
452     }
453   }
454 
455   // Environment of an instruction, removed during SimplifyInduction, should be adjusted.
456   //
457   /// CHECK-START: void Main.inductionMax(int[]) loop_optimization (before)
458   /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none
459   /// CHECK-DAG: Phi loop:<<Loop>>      outer_loop:none
460   //
461   /// CHECK-START: void Main.inductionMax(int[]) loop_optimization (after)
462   /// CHECK-NOT: Phi
inductionMax(int[] a)463   private static void inductionMax(int[] a) {
464    int s = 0;
465     for (int i = 0; i < 10; i++) {
466       s = Math.max(s, 5);
467     }
468   }
469 
470   /// CHECK-START: int Main.feedsIntoDeopt(int[]) loop_optimization (before)
471   /// CHECK-DAG: Phi loop:<<Loop1:B\d+>> outer_loop:none
472   /// CHECK-DAG: Phi loop:<<Loop1>>      outer_loop:none
473   /// CHECK-DAG: Phi loop:<<Loop2:B\d+>> outer_loop:none
474   //
475   /// CHECK-EVAL: "<<Loop1>>" != "<<Loop2>>"
476   //
477   /// CHECK-START: int Main.feedsIntoDeopt(int[]) loop_optimization (after)
478   /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none
479   /// CHECK-NOT: Phi
feedsIntoDeopt(int[] a)480   static int feedsIntoDeopt(int[] a) {
481     // Reduction should be removed.
482     int r = 0;
483     for (int i = 0; i < 100; i++) {
484       r += 10;
485     }
486     // Even though uses feed into deopts of BCE.
487     for (int i = 1; i < 100; i++) {
488       a[i] = a[i - 1];
489     }
490     return r;
491   }
492 
absCanBeNegative(int x)493   static int absCanBeNegative(int x) {
494     int a[] = { 1, 2, 3 };
495     int y = 0;
496     for (int i = Math.abs(x); i < a.length; i++) {
497       y += a[i];
498     }
499     return y;
500   }
501 
502   // b/65478356: sum up 2-dim array.
sum(int[][] a)503   static int sum(int[][] a) {
504     int sum = 0;
505     for (int y = 0; y < a.length; y++) {
506       int[] aa = a[y];
507       for (int x = 0; x < aa.length; x++) {
508         sum += aa[x];
509       }
510     }
511     return sum;
512   }
513 
514   // Large loop body should not break unrolling computation.
largeBody(int[] x)515   static void largeBody(int[] x) {
516     for (int i = 0; i < 100; i++) {
517       x[i] = x[i] * 1 + x[i] * 2 + x[i] * 3 + x[i] * 4 + x[i] * 5 + x[i] * 6 +
518           x[i] * 7 + x[i] * 8 + x[i] * 9 + x[i] * 10 + x[i] * 11 + x[i] * 12 +
519           x[i] * 13 + x[i] * 14 + x[i] * 15 + x[i] * 1 + x[i] * 2 + x[i] * 3 + x[i] * 4 +
520           x[i] * 5 + x[i] * 6 + x[i] * 7 + x[i] * 8 + x[i] * 9 + x[i] * 10 + x[i] * 11 +
521           x[i] * 12 + x[i] * 13 + x[i] * 14 + x[i] * 15 + x[i] * 1 + x[i] * 2 + x[i] * 3 +
522           x[i] * 4 + x[i] * 5;
523     }
524   }
525 
526   // Mixed of 16-bit and 8-bit array references.
castAndNarrow(byte[] x, char[] y)527   static void castAndNarrow(byte[] x, char[] y) {
528     for (int i = 0; i < x.length; i++) {
529       x[i] = (byte) ((short) y[i] +  1);
530     }
531   }
532 
533   // Avoid bad scheduler-SIMD interaction.
doNotMoveSIMD()534   static int doNotMoveSIMD() {
535     int sum = 0;
536     for (int j = 0; j <= 8; j++) {
537       int[] a = new int[17];    // a[i] = 0;
538                                 // ConstructorFence ?
539       for (int i = 0; i < a.length; i++) {
540         a[i] += 1;              // a[i] = 1;
541       }
542       for (int i = 0; i < a.length; i++) {
543         sum += a[i];            // expect a[i] = 1;
544       }
545     }
546     return sum;
547   }
548 
549   // Ensure spilling saves full SIMD values.
reduction32Values(int[] a, int[] b, int[] c, int[] d)550   private static final int reduction32Values(int[] a, int[] b, int[] c, int[] d) {
551     int s0 = 0;
552     int s1 = 0;
553     int s2 = 0;
554     int s3 = 0;
555     int s4 = 0;
556     int s5 = 0;
557     int s6 = 0;
558     int s7 = 0;
559     int s8 = 0;
560     int s9 = 0;
561     int s10 = 0;
562     int s11 = 0;
563     int s12 = 0;
564     int s13 = 0;
565     int s14 = 0;
566     int s15 = 0;
567     int s16 = 0;
568     int s17 = 0;
569     int s18 = 0;
570     int s19 = 0;
571     int s20 = 0;
572     int s21 = 0;
573     int s22 = 0;
574     int s23 = 0;
575     int s24 = 0;
576     int s25 = 0;
577     int s26 = 0;
578     int s27 = 0;
579     int s28 = 0;
580     int s29 = 0;
581     int s30 = 0;
582     int s31 = 0;
583     for (int i = 1; i < 100; i++) {
584       s0 += a[i];
585       s1 += b[i];
586       s2 += c[i];
587       s3 += d[i];
588       s4 += a[i];
589       s5 += b[i];
590       s6 += c[i];
591       s7 += d[i];
592       s8 += a[i];
593       s9 += b[i];
594       s10 += c[i];
595       s11 += d[i];
596       s12 += a[i];
597       s13 += b[i];
598       s14 += c[i];
599       s15 += d[i];
600       s16 += a[i];
601       s17 += b[i];
602       s18 += c[i];
603       s19 += d[i];
604       s20 += a[i];
605       s21 += b[i];
606       s22 += c[i];
607       s23 += d[i];
608       s24 += a[i];
609       s25 += b[i];
610       s26 += c[i];
611       s27 += d[i];
612       s28 += a[i];
613       s29 += b[i];
614       s30 += c[i];
615       s31 += d[i];
616     }
617     return s0 + s1 + s2 + s3 + s4 + s5 + s6 + s7 + s8 + s9 + s10 + s11 + s12 + s13 + s14 + s15 +
618            s16 + s17 + s18 + s19 + s20 + s21 + s22 + s23 +
619            s24 + s25 + s26 + s27 + s28 + s29 + s30 + s31;
620   }
621 
622   // Ensure spilling saves regular FP values correctly when the graph HasSIMD()
623   // is true.
624   /// CHECK-START-ARM64: float Main.$noinline$ensureSlowPathFPSpillFill(float[], float[], float[], float[], int[]) loop_optimization (after)
625   //
626   //  Both regular and SIMD accesses are present.
627   /// CHECK-DAG: VecLoad
628   /// CHECK-DAG: ArrayGet
$noinline$ensureSlowPathFPSpillFill(float[] a, float[] b, float[] c, float[] d, int[] e)629   private static final float $noinline$ensureSlowPathFPSpillFill(float[] a,
630                                                                  float[] b,
631                                                                  float[] c,
632                                                                  float[] d,
633                                                                  int[] e) {
634     // This loop should be vectorized so the graph->HasSIMD() will be true.
635     // A power-of-2 number of iterations is chosen to avoid peeling/unrolling interference.
636     for (int i = 0; i < 64; i++) {
637       // The actual values of the array elements don't matter, just the
638       // presence of a SIMD loop.
639       e[i]++;
640     }
641 
642     float f0 = 0;
643     float f1 = 0;
644     float f2 = 0;
645     float f3 = 0;
646     float f4 = 0;
647     float f5 = 0;
648     float f6 = 0;
649     float f7 = 0;
650     float f8 = 0;
651     float f9 = 0;
652     float f10 = 0;
653     float f11 = 0;
654     float f12 = 0;
655     float f13 = 0;
656     float f14 = 0;
657     float f15 = 0;
658     float f16 = 0;
659     float f17 = 0;
660     float f18 = 0;
661     float f19 = 0;
662     float f20 = 0;
663     float f21 = 0;
664     float f22 = 0;
665     float f23 = 0;
666     float f24 = 0;
667     float f25 = 0;
668     float f26 = 0;
669     float f27 = 0;
670     float f28 = 0;
671     float f29 = 0;
672     float f30 = 0;
673     float f31 = 0;
674     for (int i = 0; i < 100; i++) {
675       f0 += a[i];
676       f1 += b[i];
677       f2 += c[i];
678       f3 += d[i];
679       f4 += a[i];
680       f5 += b[i];
681       f6 += c[i];
682       f7 += d[i];
683       f8 += a[i];
684       f9 += b[i];
685       f10 += c[i];
686       f11 += d[i];
687       f12 += a[i];
688       f13 += b[i];
689       f14 += c[i];
690       f15 += d[i];
691       f16 += a[i];
692       f17 += b[i];
693       f18 += c[i];
694       f19 += d[i];
695       f20 += a[i];
696       f21 += b[i];
697       f22 += c[i];
698       f23 += d[i];
699       f24 += a[i];
700       f25 += b[i];
701       f26 += c[i];
702       f27 += d[i];
703       f28 += a[i];
704       f29 += b[i];
705       f30 += c[i];
706       f31 += d[i];
707     }
708     return f0 + f1 + f2 + f3 + f4 + f5 + f6 + f7 + f8 + f9 + f10 + f11 + f12 + f13 + f14 + f15 +
709            f16 + f17 + f18 + f19 + f20 + f21 + f22 + f23 +
710            f24 + f25 + f26 + f27 + f28 + f29 + f30 + f31;
711   }
712 
reductionIntoReplication()713   public static int reductionIntoReplication() {
714     int[] a = { 1, 2, 3, 4 };
715     int x = 0;
716     for (int i = 0; i < 4; i++) {
717       x += a[i];
718     }
719     for (int i = 0; i < 4; i++) {
720       a[i] = x;
721     }
722     return a[3];
723   }
724 
725   // Dot product and SAD vectorization idioms used to have a bug when some
726   // instruction in the loop was visited twice causing a compiler crash.
727   // It happened when two vectorization idioms' matched patterns had a common
728   // sub-expression.
729 
730   // Idioms common sub-expression bug: DotProduct and ArraySet.
731   //
732   /// CHECK-START-ARM64: int Main.testDotProdAndSet(byte[], byte[], byte[]) loop_optimization (after)
733   /// CHECK-DAG:       VecDotProd
734   /// CHECK-DAG:       VecStore
testDotProdAndSet(byte[] a, byte[] b, byte[] c)735   public static final int testDotProdAndSet(byte[] a, byte[] b, byte[] c) {
736     int s = 1;
737     for (int i = 0; i < b.length; i++) {
738       int temp = a[i] * b[i];
739       c[i]= (byte)temp;
740       s += temp;
741     }
742     return s - 1;
743   }
744 
745   // Idioms common sub-expression bug: DotProduct and DotProduct.
746   //
747   /// CHECK-START-ARM64: int Main.testDotProdAndDotProd(byte[], byte[]) loop_optimization (after)
748   /// CHECK-DAG:       VecDotProd
749   /// CHECK-DAG:       VecDotProd
testDotProdAndDotProd(byte[] a, byte[] b)750   public static final int testDotProdAndDotProd(byte[] a, byte[] b) {
751     int s0 = 1;
752     int s1 = 1;
753     for (int i = 0; i < b.length; i++) {
754       int temp = a[i] * b[i];
755       s0 += temp;
756       s1 += temp;
757     }
758     return s0 + s1;
759   }
760 
761   // Idioms common sub-expression bug: SAD and ArraySet.
762   //
763   /// CHECK-START-ARM: int Main.testSADAndSet(int[], int[], int[]) loop_optimization (after)
764   /// CHECK-DAG:       VecSADAccumulate
765   /// CHECK-DAG:       VecStore
766   //
767   /// CHECK-START-ARM64: int Main.testSADAndSet(int[], int[], int[]) loop_optimization (after)
768   /// CHECK-IF:     hasIsaFeature("sve") and os.environ.get('ART_FORCE_TRY_PREDICATED_SIMD') == 'true'
769   //
770   //      VecSADAccumulate is not supported for SVE.
771   ///     CHECK-NOT:       VecSADAccumulate
772   //
773   /// CHECK-ELSE:
774   //
775   ///     CHECK-DAG:       VecSADAccumulate
776   ///     CHECK-DAG:       VecStore
777   //
778   /// CHECK-FI:
testSADAndSet(int[] x, int[] y, int[] z)779   public static int testSADAndSet(int[] x, int[] y, int[] z) {
780     int min_length = Math.min(x.length, y.length);
781     int sad = 0;
782     for (int i = 0; i < min_length; i++) {
783       int temp = Math.abs(x[i] - y[i]);
784       z[i] = temp;
785       sad += temp;
786     }
787     return sad;
788   }
789 
790   // Idioms common sub-expression bug: SAD and SAD.
791   /// CHECK-START-ARM: int Main.testSADAndSAD(int[], int[]) loop_optimization (after)
792   /// CHECK-DAG:       VecSADAccumulate
793   /// CHECK-DAG:       VecSADAccumulate
794   //
795   /// CHECK-START-ARM64: int Main.testSADAndSAD(int[], int[]) loop_optimization (after)
796   /// CHECK-IF:     hasIsaFeature("sve") and os.environ.get('ART_FORCE_TRY_PREDICATED_SIMD') == 'true'
797   //
798   //      VecSADAccumulate is not supported for SVE.
799   ///     CHECK-NOT:       VecSADAccumulate
800   //
801   /// CHECK-ELSE:
802   //
803   ///     CHECK-DAG:       VecSADAccumulate
804   ///     CHECK-DAG:       VecSADAccumulate
805   //
806   /// CHECK-FI:
testSADAndSAD(int[] x, int[] y)807   public static final int testSADAndSAD(int[] x, int[] y) {
808     int s0 = 1;
809     int s1 = 1;
810     for (int i = 0; i < x.length; i++) {
811       int temp = Math.abs(x[i] - y[i]);
812       s0 += temp;
813       s1 += temp;
814     }
815     return s0 + s1;
816   }
817 
818   // Idioms common sub-expression bug: DotProd and DotProd with extra mul.
819   //
820   /// CHECK-START-ARM64: int Main.testDotProdAndDotProdExtraMul0(byte[], byte[]) loop_optimization (after)
821   /// CHECK-DAG:       VecMul
822   /// CHECK-DAG:       VecDotProd
823   /// CHECK-DAG:       VecDotProd
testDotProdAndDotProdExtraMul0(byte[] a, byte[] b)824   public static final int testDotProdAndDotProdExtraMul0(byte[] a, byte[] b) {
825     int s0 = 1;
826     int s1 = 1;
827     for (int i = 0; i < b.length; i++) {
828       int temp0 = a[i] * b[i];
829       int temp1 = (byte)(temp0) * a[i];
830       s0 += temp1;
831       s1 += temp0;
832     }
833     return s0 + s1;
834   }
835 
836   // Idioms common sub-expression bug: DotProd and DotProd with extra mul (reversed order).
837   //
838   /// CHECK-START-ARM64: int Main.testDotProdAndDotProdExtraMul1(byte[], byte[]) loop_optimization (after)
839   /// CHECK-DAG:       VecMul
840   /// CHECK-DAG:       VecDotProd
841   /// CHECK-DAG:       VecDotProd
testDotProdAndDotProdExtraMul1(byte[] a, byte[] b)842   public static final int testDotProdAndDotProdExtraMul1(byte[] a, byte[] b) {
843     int s0 = 1;
844     int s1 = 1;
845     for (int i = 0; i < b.length; i++) {
846       int temp0 = a[i] * b[i];
847       int temp1 = (byte)(temp0) * a[i];
848       s0 += temp0;
849       s1 += temp1;
850     }
851     return s0 + s1;
852   }
853 
854   // Idioms common sub-expression bug: SAD and SAD with extra abs.
855   //
856   /// CHECK-START-ARM: int Main.testSADAndSADExtraAbs0(int[], int[]) loop_optimization (after)
857   /// CHECK-DAG:       VecSub
858   /// CHECK-DAG:       VecAbs
859   /// CHECK-DAG:       VecSADAccumulate
860   /// CHECK-DAG:       VecSADAccumulate
861   //
862   /// CHECK-START-ARM64: int Main.testSADAndSADExtraAbs0(int[], int[]) loop_optimization (after)
863   /// CHECK-IF:     hasIsaFeature("sve") and os.environ.get('ART_FORCE_TRY_PREDICATED_SIMD') == 'true'
864   //
865   //      VecSADAccumulate is not supported for SVE.
866   ///     CHECK-NOT:       VecSADAccumulate
867   //
868   /// CHECK-ELSE:
869   //
870   ///     CHECK-DAG:       VecSub
871   ///     CHECK-DAG:       VecAbs
872   ///     CHECK-DAG:       VecSADAccumulate
873   ///     CHECK-DAG:       VecSADAccumulate
874   //
875   /// CHECK-FI:
testSADAndSADExtraAbs0(int[] x, int[] y)876   public static final int testSADAndSADExtraAbs0(int[] x, int[] y) {
877     int s0 = 1;
878     int s1 = 1;
879     for (int i = 0; i < x.length; i++) {
880       int temp0 = Math.abs(x[i] - y[i]);
881       int temp1 = Math.abs(temp0 - y[i]);
882       s0 += temp1;
883       s1 += temp0;
884     }
885     return s0 + s1;
886   }
887 
888   // Idioms common sub-expression bug: SAD and SAD with extra abs (reversed order).
889   //
890   /// CHECK-START-ARM: int Main.testSADAndSADExtraAbs1(int[], int[]) loop_optimization (after)
891   /// CHECK-DAG:       VecSub
892   /// CHECK-DAG:       VecAbs
893   /// CHECK-DAG:       VecSADAccumulate
894   /// CHECK-DAG:       VecSADAccumulate
895   //
896   /// CHECK-START-ARM64: int Main.testSADAndSADExtraAbs1(int[], int[]) loop_optimization (after)
897   /// CHECK-IF:     hasIsaFeature("sve") and os.environ.get('ART_FORCE_TRY_PREDICATED_SIMD') == 'true'
898   //
899   //      VecSADAccumulate is not supported for SVE.
900   ///     CHECK-NOT:       VecSADAccumulate
901   //
902   /// CHECK-ELSE:
903   //
904   ///     CHECK-DAG:       VecSub
905   ///     CHECK-DAG:       VecAbs
906   ///     CHECK-DAG:       VecSADAccumulate
907   ///     CHECK-DAG:       VecSADAccumulate
908   //
909   /// CHECK-FI:
testSADAndSADExtraAbs1(int[] x, int[] y)910   public static final int testSADAndSADExtraAbs1(int[] x, int[] y) {
911     int s0 = 1;
912     int s1 = 1;
913     for (int i = 0; i < x.length; i++) {
914       int temp0 = Math.abs(x[i] - y[i]);
915       int temp1 = Math.abs(temp0 - y[i]);
916       s0 += temp0;
917       s1 += temp1;
918     }
919     return s0 + s1;
920   }
921 
922 
923   // Idioms common sub-expression bug: SAD and DotProd combined.
924   //
925   /// CHECK-START-ARM64: int Main.testSADAndDotProdCombined0(byte[], byte[]) loop_optimization (after)
926   /// CHECK-IF:     hasIsaFeature("sve") and os.environ.get('ART_FORCE_TRY_PREDICATED_SIMD') == 'true'
927   //
928   //      VecSADAccumulate is not supported for SVE.
929   ///     CHECK-NOT:       VecSADAccumulate
930   //
931   /// CHECK-ELSE:
932   //
933   ///     CHECK-DAG:       VecSub
934   ///     CHECK-DAG:       VecSADAccumulate
935   ///     CHECK-DAG:       VecDotProd
936   //
937   /// CHECK-FI:
testSADAndDotProdCombined0(byte[] x, byte[] y)938   public static final int testSADAndDotProdCombined0(byte[] x, byte[] y) {
939     int s0 = 1;
940     int s1 = 1;
941     for (int i = 0; i < x.length; i++) {
942       int temp0 = x[i] - y[i];
943       int temp1 = Math.abs(temp0);
944       int temp2 = x[i] * (byte)(temp0);
945 
946       s0 += temp1;
947       s1 += temp2;
948     }
949     return s0 + s1;
950   }
951 
952   // Idioms common sub-expression bug: SAD and DotProd combined (reversed order).
953   /// CHECK-START-ARM64: int Main.testSADAndDotProdCombined1(byte[], byte[]) loop_optimization (after)
954   /// CHECK-IF:     hasIsaFeature("sve") and os.environ.get('ART_FORCE_TRY_PREDICATED_SIMD') == 'true'
955   //
956   //      VecSADAccumulate is not supported for SVE.
957   ///     CHECK-NOT:       VecSADAccumulate
958   //
959   /// CHECK-ELSE:
960   //
961   ///     CHECK-DAG:       VecSub
962   ///     CHECK-DAG:       VecSADAccumulate
963   ///     CHECK-DAG:       VecDotProd
964   //
965   /// CHECK-FI:
testSADAndDotProdCombined1(byte[] x, byte[] y)966   public static final int testSADAndDotProdCombined1(byte[] x, byte[] y) {
967     int s0 = 1;
968     int s1 = 1;
969     for (int i = 0; i < x.length; i++) {
970       int temp0 = x[i] - y[i];
971       int temp1 = Math.abs(temp0);
972       int temp2 = x[i] * (byte)(temp0);
973 
974       s0 += temp2;
975       s1 += temp1;
976     }
977     return s0 + s1;
978   }
979 
980   // Regression test for the case, where a loop is vectorized in predicated mode, and there is
981   // a disambiguation scalar loop added. Make sure that the set, which records instructions
982   // inserted outside of new loops, is not reset until the full vectorization process has
983   // happened.
984   //
985   // Based on void android.util.Spline$MonotoneCubicSpline.<init>(float[], float[]).
986   //
987   /// CHECK-START-ARM64: void Main.$noinline$testExternalSetForLoopWithDisambiguation(int[], int[]) loop_optimization (after)
988   /// CHECK-IF:     hasIsaFeature("sve") and os.environ.get('ART_FORCE_TRY_PREDICATED_SIMD') == 'true'
989   //
990   ///     CHECK-DAG: <<Pred:j\d+>>    VecPredSetAll                          loop:none
991   ///     CHECK-DAG:                  VecReplicateScalar [{{i\d+}},<<Pred>>] loop:none
992   //
993   /// CHECK-ELSE:
994   //
995   ///     CHECK-DAG:                  VecReplicateScalar                     loop:none
996   //
997   /// CHECK-FI:
998   //
999   // Vector loop.
1000   /// CHECK-DAG:       Phi                    loop:<<VectorLoop:B\d+>> outer_loop:none
1001   /// CHECK-DAG:       VecLoad                loop:<<VectorLoop>>      outer_loop:none
1002   //
1003   // Backup scalar loop.
1004   /// CHECK-DAG:       Phi                    loop:<<ScalarLoop:B\d+>> outer_loop:none
1005   /// CHECK-DAG:       ArrayGet               loop:<<ScalarLoop>>      outer_loop:none
$noinline$testExternalSetForLoopWithDisambiguation(int[] d, int[] m)1006   public static void $noinline$testExternalSetForLoopWithDisambiguation(int[] d, int[] m) {
1007     m[0] = d[0];
1008     for (int i = 1; i < m.length; i++) {
1009       m[i] = (d[i - 1] + d[i]) * 53;
1010     }
1011   }
1012 
1013   public static final int ARRAY_SIZE = 512;
1014 
createAndInitByteArray(int x)1015   private static byte[] createAndInitByteArray(int x) {
1016     byte[] a = new byte[ARRAY_SIZE];
1017     for (int i = 0; i < a.length; i++) {
1018       a[i] = (byte)((~i) + x);
1019     }
1020     return a;
1021   }
1022 
createAndInitIntArray(int x)1023   private static int[] createAndInitIntArray(int x) {
1024     int[] a = new int[ARRAY_SIZE];
1025     for (int i = 0; i < a.length; i++) {
1026       a[i] = (~i) + x;
1027     }
1028     return a;
1029   }
1030 
main(String[] args)1031   public static void main(String[] args) {
1032     System.loadLibrary(args[0]);
1033 
1034     expectEquals(10, earlyExitFirst(-1));
1035     for (int i = 0; i <= 10; i++) {
1036       expectEquals(i, earlyExitFirst(i));
1037     }
1038     expectEquals(10, earlyExitFirst(11));
1039 
1040     expectEquals(10, earlyExitLast(-1));
1041     for (int i = 0; i < 10; i++) {
1042       expectEquals(i + 1, earlyExitLast(i));
1043     }
1044     expectEquals(10, earlyExitLast(10));
1045     expectEquals(10, earlyExitLast(11));
1046 
1047     expectEquals(2, earlyExitNested());
1048 
1049     expectEquals(17, transferNarrowWrap());
1050     expectEquals(-45, polynomialShort());
1051     expectEquals(-45, polynomialIntFromLong());
1052     expectEquals(-45, polynomialInt());
1053 
1054     expectEquals(0, geoIntDivLastValue(0));
1055     expectEquals(0, geoIntDivLastValue(1));
1056     expectEquals(0, geoIntDivLastValue(2));
1057     expectEquals(0, geoIntDivLastValue(1081788608));
1058     expectEquals(0, geoIntDivLastValue(-1081788608));
1059     expectEquals(0, geoIntDivLastValue(2147483647));
1060     expectEquals(0, geoIntDivLastValue(-2147483648));
1061 
1062     expectEquals(          0, geoIntMulLastValue(0));
1063     expectEquals( -194211840, geoIntMulLastValue(1));
1064     expectEquals( -388423680, geoIntMulLastValue(2));
1065     expectEquals(-1041498112, geoIntMulLastValue(1081788608));
1066     expectEquals( 1041498112, geoIntMulLastValue(-1081788608));
1067     expectEquals(  194211840, geoIntMulLastValue(2147483647));
1068     expectEquals(          0, geoIntMulLastValue(-2147483648));
1069 
1070     expectEquals(0L, geoLongDivLastValue(0L));
1071     expectEquals(0L, geoLongDivLastValue(1L));
1072     expectEquals(0L, geoLongDivLastValue(2L));
1073     expectEquals(0L, geoLongDivLastValue(1081788608L));
1074     expectEquals(0L, geoLongDivLastValue(-1081788608L));
1075     expectEquals(0L, geoLongDivLastValue(2147483647L));
1076     expectEquals(0L, geoLongDivLastValue(-2147483648L));
1077     expectEquals(0L, geoLongDivLastValue(9223372036854775807L));
1078     expectEquals(0L, geoLongDivLastValue(-9223372036854775808L));
1079 
1080     expectEquals(0L, geoLongDivLastValue());
1081 
1082     expectEquals(                   0L, geoLongMulLastValue(0L));
1083     expectEquals(-8070450532247928832L, geoLongMulLastValue(1L));
1084     expectEquals( 2305843009213693952L, geoLongMulLastValue(2L));
1085     expectEquals(                   0L, geoLongMulLastValue(1081788608L));
1086     expectEquals(                   0L, geoLongMulLastValue(-1081788608L));
1087     expectEquals( 8070450532247928832L, geoLongMulLastValue(2147483647L));
1088     expectEquals(                   0L, geoLongMulLastValue(-2147483648L));
1089     expectEquals( 8070450532247928832L, geoLongMulLastValue(9223372036854775807L));
1090     expectEquals(                   0L, geoLongMulLastValue(-9223372036854775808L));
1091 
1092     float[] a = new float[16];
1093     narrowingSubscript(a);
1094     for (int i = 0; i < 16; i++) {
1095       expectEquals(2.0f, a[i]);
1096     }
1097 
1098     int[] xx = new int[2];
1099     int[] yy = new int[469];
1100     reduc(xx, yy);
1101     expectEquals(-469, xx[0]);
1102     expectEquals(-938, xx[1]);
1103     for (int i = 0; i < 469; i++) {
1104       expectEquals(2, yy[i]);
1105     }
1106 
1107     char[] aa = new char[23];
1108     String bb = "hello world how are you";
1109     string2Bytes(aa, bb);
1110     for (int i = 0; i < aa.length; i++) {
1111       expectEquals(aa[i], bb.charAt(i));
1112     }
1113     String cc = "\u1010\u2020llo world how are y\u3030\u4040";
1114     string2Bytes(aa, cc);
1115     for (int i = 0; i < aa.length; i++) {
1116       expectEquals(aa[i], cc.charAt(i));
1117     }
1118 
1119     short[] s2s = new short[12];
1120     $noinline$stringToShorts(s2s, "abcdefghijkl");
1121     for (int i = 0; i < s2s.length; ++i) {
1122       expectEquals((short) "abcdefghijkl".charAt(i), s2s[i]);
1123     }
1124 
1125     envUsesInCond();
1126 
1127     short[] dd = new short[23];
1128     oneBoth(dd, aa);
1129     for (int i = 0; i < aa.length; i++) {
1130       expectEquals(aa[i], 1);
1131       expectEquals(dd[i], 1);
1132     }
1133 
1134     xx[0] = 10;
1135     byte[] bt = new byte[10];
1136     arrayInTripCount(xx, bt, 20);
1137     for (int i = 0; i < bt.length; i++) {
1138       expectEquals(40, bt[i]);
1139     }
1140 
1141     byte[] b1 = new byte[259];  // few extra iterations
1142     byte[] b2 = new byte[259];
1143     for (int i = 0; i < 259; i++) {
1144       b1[i] = 0;
1145       b2[i] = (byte) i;
1146     }
1147     typeConv(b1, b2);
1148     for (int i = 0; i < 259; i++) {
1149       expectEquals((byte)(i + 1), b1[i]);
1150     }
1151 
1152     inductionMax(yy);
1153 
1154     int[] f = new int[100];
1155     f[0] = 11;
1156     expectEquals(1000, feedsIntoDeopt(f));
1157     for (int i = 0; i < 100; i++) {
1158       expectEquals(11, f[i]);
1159     }
1160 
1161     expectEquals(0, absCanBeNegative(-3));
1162     expectEquals(3, absCanBeNegative(-2));
1163     expectEquals(5, absCanBeNegative(-1));
1164     expectEquals(6, absCanBeNegative(0));
1165     expectEquals(5, absCanBeNegative(1));
1166     expectEquals(3, absCanBeNegative(2));
1167     expectEquals(0, absCanBeNegative(3));
1168     expectEquals(0, absCanBeNegative(Integer.MAX_VALUE));
1169     // Abs(min_int) = min_int.
1170     int verify = 0;
1171     try {
1172       absCanBeNegative(Integer.MIN_VALUE);
1173       verify = 1;
1174     } catch (ArrayIndexOutOfBoundsException e) {
1175       verify = 2;
1176     }
1177     expectEquals(2, verify);
1178 
1179     int[][] x = new int[128][128];
1180     for (int i = 0; i < 128; i++) {
1181       for (int j = 0; j < 128; j++) {
1182         x[i][j] = -i - j;
1183       }
1184     }
1185     expectEquals(-2080768, sum(x));
1186 
1187     largeBody(f);
1188     for (int i = 0; i < 100; i++) {
1189       expectEquals(2805, f[i]);
1190     }
1191 
1192     char[] cx = new char[259];
1193     for (int i = 0; i < 259; i++) {
1194       cx[i] = (char) (i - 100);
1195     }
1196     castAndNarrow(b1, cx);
1197     for (int i = 0; i < 259; i++) {
1198       expectEquals((byte)((short) cx[i] + 1), b1[i]);
1199     }
1200 
1201     expectEquals(153, doNotMoveSIMD());
1202 
1203     // This test exposed SIMDization issues on x86 and x86_64
1204     // so we make sure the test runs with JIT enabled.
1205     ensureJitCompiled(Main.class, "reduction32Values");
1206     {
1207       int[] a1 = new int[100];
1208       int[] a2 = new int[100];
1209       int[] a3 = new int[100];
1210       int[] a4 = new int[100];
1211       for (int i = 0; i < 100; i++) {
1212         a1[i] = i;
1213         a2[i] = 1;
1214         a3[i] = 100 - i;
1215         a4[i] = i % 16;
1216       }
1217       expectEquals(85800, reduction32Values(a1, a2, a3, a4));
1218     }
1219     {
1220       float[] a1 = new float[100];
1221       float[] a2 = new float[100];
1222       float[] a3 = new float[100];
1223       float[] a4 = new float[100];
1224       int[] a5 = new int[100];
1225 
1226       for (int i = 0; i < 100; i++) {
1227         a1[i] = (float)i;
1228         a2[i] = (float)1;
1229         a3[i] = (float)(100 - i);
1230         a4[i] = (i % 16);
1231       }
1232       expectEquals(86608.0f, $noinline$ensureSlowPathFPSpillFill(a1, a2, a3, a4, a5));
1233     }
1234 
1235     expectEquals(10, reductionIntoReplication());
1236 
1237     {
1238         byte[] b_a = createAndInitByteArray(1);
1239         byte[] b_b = createAndInitByteArray(2);
1240         byte[] b_c = createAndInitByteArray(3);
1241         expectEquals(2731008, testDotProdAndSet(b_a, b_b, b_c));
1242     }
1243     {
1244         byte[] b_a = createAndInitByteArray(1);
1245         byte[] b_b = createAndInitByteArray(2);
1246         expectEquals(5462018, testDotProdAndDotProd(b_a, b_b));
1247     }
1248     {
1249         int[] i_a = createAndInitIntArray(1);
1250         int[] i_b = createAndInitIntArray(2);
1251         int[] i_c = createAndInitIntArray(3);
1252         expectEquals(512, testSADAndSet(i_a, i_b, i_c));
1253     }
1254     {
1255         int[] i_a = createAndInitIntArray(1);
1256         int[] i_b = createAndInitIntArray(2);
1257         expectEquals(1026, testSADAndSAD(i_a, i_b));
1258     }
1259     {
1260         byte[] b_a = createAndInitByteArray(1);
1261         byte[] b_b = createAndInitByteArray(2);
1262         expectEquals(2731266, testDotProdAndDotProdExtraMul0(b_a, b_b));
1263     }
1264     {
1265         byte[] b_a = createAndInitByteArray(1);
1266         byte[] b_b = createAndInitByteArray(2);
1267         expectEquals(2731266, testDotProdAndDotProdExtraMul1(b_a, b_b));
1268     }
1269     {
1270         int[] i_a = createAndInitIntArray(1);
1271         int[] i_b = createAndInitIntArray(2);
1272         expectEquals(131330, testSADAndSADExtraAbs0(i_a, i_b));
1273     }
1274     {
1275         int[] i_a = createAndInitIntArray(1);
1276         int[] i_b = createAndInitIntArray(2);
1277         expectEquals(131330, testSADAndSADExtraAbs1(i_a, i_b));
1278     }
1279     {
1280         byte[] b_a = createAndInitByteArray(1);
1281         byte[] b_b = createAndInitByteArray(2);
1282         expectEquals(1278, testSADAndDotProdCombined0(b_a, b_b));
1283     }
1284     {
1285         byte[] b_a = createAndInitByteArray(1);
1286         byte[] b_b = createAndInitByteArray(2);
1287         expectEquals(1278, testSADAndDotProdCombined1(b_a, b_b));
1288     }
1289     {
1290         int[] i_a = createAndInitIntArray(1);
1291         int[] i_b = createAndInitIntArray(2);
1292         $noinline$testExternalSetForLoopWithDisambiguation(i_a, i_b);
1293 
1294         int sum = 0;
1295         for (int i = 0; i < i_b.length; i++) {
1296           sum += i_b[i];
1297         }
1298         expectEquals(-13839413, sum);
1299     }
1300 
1301     System.out.println("passed");
1302   }
1303 
expectEquals(int expected, int result)1304   private static void expectEquals(int expected, int result) {
1305     if (expected != result) {
1306       throw new Error("Expected: " + expected + ", found: " + result);
1307     }
1308   }
1309 
expectEquals(long expected, long result)1310   private static void expectEquals(long expected, long result) {
1311     if (expected != result) {
1312       throw new Error("Expected: " + expected + ", found: " + result);
1313     }
1314   }
1315 
expectEquals(float expected, float result)1316   private static void expectEquals(float expected, float result) {
1317     if (expected != result) {
1318       throw new Error("Expected: " + expected + ", found: " + result);
1319     }
1320   }
1321 }
1322