1/*
2 * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24/**
25 * @test
26 * @bug 8080289
27 * @summary Move stores out of loops if possible
28 *
29 * @run main/othervm -XX:-UseOnStackReplacement -XX:-BackgroundCompilation
30 *      -XX:CompileCommand=dontinline,compiler.loopopts.TestMoveStoresOutOfLoops::test*
31 *      compiler.loopopts.TestMoveStoresOutOfLoops
32 */
33
34package compiler.loopopts;
35
36import java.lang.reflect.Method;
37import java.lang.reflect.Modifier;
38import java.util.HashMap;
39import java.util.function.Function;
40
41public class TestMoveStoresOutOfLoops {
42
43    private static long[] array = new long[10];
44    private static long[] array2 = new long[10];
45    private static boolean[] array3 = new boolean[1000];
46    private static byte[] byte_array = new byte[10];
47
48    // Array store should be moved out of the loop, value stored
49    // should be 999, the loop should be eliminated
50    static void test_after_1(int idx) {
51        for (int i = 0; i < 1000; i++) {
52            array[idx] = i;
53        }
54    }
55
56    // Array store can't be moved out of loop because of following
57    // non loop invariant array access
58    static void test_after_2(int idx) {
59        for (int i = 0; i < 1000; i++) {
60            array[idx] = i;
61            array2[i%10] = i;
62        }
63    }
64
65    // Array store can't be moved out of loop because of following
66    // use
67    static void test_after_3(int idx) {
68        for (int i = 0; i < 1000; i++) {
69            array[idx] = i;
70            if (array[0] == -1) {
71                break;
72            }
73        }
74    }
75
76    // Array store can't be moved out of loop because of preceding
77    // use
78    static void test_after_4(int idx) {
79        for (int i = 0; i < 1000; i++) {
80            if (array[0] == -2) {
81                break;
82            }
83            array[idx] = i;
84        }
85    }
86
87    // All array stores should be moved out of the loop, one after
88    // the other
89    static void test_after_5(int idx) {
90        for (int i = 0; i < 1000; i++) {
91            array[idx] = i;
92            array[idx+1] = i;
93            array[idx+2] = i;
94            array[idx+3] = i;
95            array[idx+4] = i;
96            array[idx+5] = i;
97        }
98    }
99
100    // Array store can be moved after the loop but needs to be
101    // cloned on both exit paths
102    static void test_after_6(int idx) {
103        for (int i = 0; i < 1000; i++) {
104            array[idx] = i;
105            if (array3[i]) {
106                return;
107            }
108        }
109    }
110
111    // Optimize out redundant stores
112    static void test_stores_1(int ignored) {
113        array[0] = 0;
114        array[1] = 1;
115        array[2] = 2;
116        array[0] = 0;
117        array[1] = 1;
118        array[2] = 2;
119    }
120
121    static void test_stores_2(int idx) {
122        array[idx+0] = 0;
123        array[idx+1] = 1;
124        array[idx+2] = 2;
125        array[idx+0] = 0;
126        array[idx+1] = 1;
127        array[idx+2] = 2;
128    }
129
130    static void test_stores_3(int idx) {
131        byte_array[idx+0] = 0;
132        byte_array[idx+1] = 1;
133        byte_array[idx+2] = 2;
134        byte_array[idx+0] = 0;
135        byte_array[idx+1] = 1;
136        byte_array[idx+2] = 2;
137    }
138
139    // Array store can be moved out of the loop before the loop header
140    static void test_before_1(int idx) {
141        for (int i = 0; i < 1000; i++) {
142            array[idx] = 999;
143        }
144    }
145
146    // Array store can't be moved out of the loop before the loop
147    // header because there's more than one store on this slice
148    static void test_before_2(int idx) {
149        for (int i = 0; i < 1000; i++) {
150            array[idx] = 999;
151            array[i%2] = 0;
152        }
153    }
154
155    // Array store can't be moved out of the loop before the loop
156    // header because of use before store
157    static int test_before_3(int idx) {
158        int res = 0;
159        for (int i = 0; i < 1000; i++) {
160            res += array[i%10];
161            array[idx] = 999;
162        }
163        return res;
164    }
165
166    // Array store can't be moved out of the loop before the loop
167    // header because of possible early exit
168    static void test_before_4(int idx) {
169        for (int i = 0; i < 1000; i++) {
170            if (idx / (i+1) > 0) {
171                return;
172            }
173            array[idx] = 999;
174        }
175    }
176
177    // Array store can't be moved out of the loop before the loop
178    // header because it doesn't postdominate the loop head
179    static void test_before_5(int idx) {
180        for (int i = 0; i < 1000; i++) {
181            if (i % 2 == 0) {
182                array[idx] = 999;
183            }
184        }
185    }
186
187    // Array store can be moved out of the loop before the loop header
188    static int test_before_6(int idx) {
189        int res = 0;
190        for (int i = 0; i < 1000; i++) {
191            if (i%2 == 1) {
192                res *= 2;
193            } else {
194                res++;
195            }
196            array[idx] = 999;
197        }
198        return res;
199    }
200
201    final HashMap<String,Method> tests = new HashMap<>();
202    {
203        for (Method m : this.getClass().getDeclaredMethods()) {
204            if (m.getName().matches("test_(before|after|stores)_[0-9]+")) {
205                assert(Modifier.isStatic(m.getModifiers())) : m;
206                tests.put(m.getName(), m);
207            }
208        }
209    }
210
211    boolean success = true;
212    void doTest(String name, Runnable init, Function<String, Boolean> check) throws Exception {
213        Method m = tests.get(name);
214        for (int i = 0; i < 20000; i++) {
215            init.run();
216            m.invoke(null, 0);
217            success = success && check.apply(name);
218            if (!success) {
219                break;
220            }
221        }
222    }
223
224    static void array_init() {
225        array[0] = -1;
226    }
227
228    static boolean array_check(String name) {
229        boolean success = true;
230        if (array[0] != 999) {
231            success = false;
232            System.out.println(name + " failed: array[0] = " + array[0]);
233        }
234        return success;
235    }
236
237    static void array_init2() {
238        for (int i = 0; i < 6; i++) {
239            array[i] = -1;
240        }
241    }
242
243    static boolean array_check2(String name) {
244        boolean success = true;
245        for (int i = 0; i < 6; i++) {
246            if (array[i] != 999) {
247                success = false;
248                System.out.println(name + " failed: array[" + i + "] = " + array[i]);
249            }
250        }
251        return success;
252    }
253
254    static void array_init3() {
255        for (int i = 0; i < 3; i++) {
256            array[i] = -1;
257        }
258    }
259
260    static boolean array_check3(String name) {
261        boolean success = true;
262        for (int i = 0; i < 3; i++) {
263            if (array[i] != i) {
264                success = false;
265                System.out.println(name + " failed: array[" + i + "] = " + array[i]);
266            }
267        }
268        return success;
269    }
270
271    static void array_init4() {
272        for (int i = 0; i < 3; i++) {
273            byte_array[i] = -1;
274        }
275    }
276
277    static boolean array_check4(String name) {
278        boolean success = true;
279        for (int i = 0; i < 3; i++) {
280            if (byte_array[i] != i) {
281                success = false;
282                System.out.println(name + " failed: byte_array[" + i + "] = " + byte_array[i]);
283            }
284        }
285        return success;
286    }
287
288    static public void main(String[] args) throws Exception {
289        TestMoveStoresOutOfLoops test = new TestMoveStoresOutOfLoops();
290        test.doTest("test_after_1", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
291        test.doTest("test_after_2", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
292        test.doTest("test_after_3", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
293        test.doTest("test_after_4", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
294        test.doTest("test_after_5", TestMoveStoresOutOfLoops::array_init2, TestMoveStoresOutOfLoops::array_check2);
295        test.doTest("test_after_6", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
296        array3[999] = true;
297        test.doTest("test_after_6", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
298
299        test.doTest("test_stores_1", TestMoveStoresOutOfLoops::array_init3, TestMoveStoresOutOfLoops::array_check3);
300        test.doTest("test_stores_2", TestMoveStoresOutOfLoops::array_init3, TestMoveStoresOutOfLoops::array_check3);
301        test.doTest("test_stores_3", TestMoveStoresOutOfLoops::array_init4, TestMoveStoresOutOfLoops::array_check4);
302
303        test.doTest("test_before_1", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
304        test.doTest("test_before_2", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
305        test.doTest("test_before_3", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
306        test.doTest("test_before_4", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
307        test.doTest("test_before_5", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
308        test.doTest("test_before_6", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
309
310        if (!test.success) {
311            throw new RuntimeException("Some tests failed");
312        }
313    }
314}
315