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 /**

    26  * @test

    27  * @bug 8080289

    28  * @summary Sink stores out of loops if possible

    29  * @run main/othervm -XX:-UseOnStackReplacement -XX:-BackgroundCompilation -XX:+PrintCompilation -XX:CompileCommand=dontinline,TestMoveStoresOutOfLoops::test*  TestMoveStoresOutOfLoops

    30  *

    31  */

    32 

    33 import java.lang.reflect.*;

    34 import java.util.*;

    35 import java.util.function.*;

    36 

    37 public class TestMoveStoresOutOfLoops {

    38 

    39     private static long[] array = new long[10];

    40     private static long[] array2 = new long[10];

    41     private static boolean[] array3 = new boolean[1000];

    42     private static byte[] byte_array = new byte[10];

    43 

    44     // Array store should be moved out of the loop, value stored

    45     // should be 999, the loop should be eliminated

    46     static void test_after_1(int idx) {

    47         for (int i = 0; i < 1000; i++) {

    48             array[idx] = i;

    49         }

    50     }

    51 

    52     // Array store can't be moved out of loop because of following

    53     // non loop invariant array access

    54     static void test_after_2(int idx) {

    55         for (int i = 0; i < 1000; i++) {

    56             array[idx] = i;

    57             array2[i%10] = i;

    58         }

    59     }

    60 

    61     // Array store can't be moved out of loop because of following

    62     // use

    63     static void test_after_3(int idx) {

    64         for (int i = 0; i < 1000; i++) {

    65             array[idx] = i;

    66             if (array[0] == -1) {

    67                 break;

    68             }

    69         }

    70     }

    71 

    72     // Array store can't be moved out of loop because of preceding

    73     // use

    74     static void test_after_4(int idx) {

    75         for (int i = 0; i < 1000; i++) {

    76             if (array[0] == -2) {

    77                 break;

    78             }

    79             array[idx] = i;

    80         }

    81     }

    82 

    83     // All array stores should be moved out of the loop, one after

    84     // the other

    85     static void test_after_5(int idx) {

    86         for (int i = 0; i < 1000; i++) {

    87             array[idx] = i;

    88             array[idx+1] = i;

    89             array[idx+2] = i;

    90             array[idx+3] = i;

    91             array[idx+4] = i;

    92             array[idx+5] = i;

    93         }

    94     }

    95 

    96     // Array store can be moved after the loop but needs to be

    97     // cloned on both exit paths

    98     static void test_after_6(int idx) {

    99         for (int i = 0; i < 1000; i++) {

   100             array[idx] = i;

   101             if (array3[i]) {

   102                 return;

   103             }

   104         }

   105     }

   106 

   107     // Optimize out redundant stores

   108     static void test_stores_1(int ignored) {

   109         array[0] = 0;

   110         array[1] = 1;

   111         array[2] = 2;

   112         array[0] = 0;

   113         array[1] = 1;

   114         array[2] = 2;

   115     }

   116 

   117     static void test_stores_2(int idx) {

   118         array[idx+0] = 0;

   119         array[idx+1] = 1;

   120         array[idx+2] = 2;

   121         array[idx+0] = 0;

   122         array[idx+1] = 1;

   123         array[idx+2] = 2;

   124     }

   125 

   126     static void test_stores_3(int idx) {

   127         byte_array[idx+0] = 0;

   128         byte_array[idx+1] = 1;

   129         byte_array[idx+2] = 2;

   130         byte_array[idx+0] = 0;

   131         byte_array[idx+1] = 1;

   132         byte_array[idx+2] = 2;

   133     }

   134 

   135     // Array store can be moved out of the loop before the loop header

   136     static void test_before_1(int idx) {

   137         for (int i = 0; i < 1000; i++) {

   138             array[idx] = 999;

   139         }

   140     }

   141 

   142     // Array store can't be moved out of the loop before the loop

   143     // header because there's more than one store on this slice

   144     static void test_before_2(int idx) {

   145         for (int i = 0; i < 1000; i++) {

   146             array[idx] = 999;

   147             array[i%2] = 0;

   148         }

   149     }

   150 

   151     // Array store can't be moved out of the loop before the loop

   152     // header because of use before store

   153     static int test_before_3(int idx) {

   154         int res = 0;

   155         for (int i = 0; i < 1000; i++) {

   156             res += array[i%10];

   157             array[idx] = 999;

   158         }

   159         return res;

   160     }

   161 

   162     // Array store can't be moved out of the loop before the loop

   163     // header because of possible early exit

   164     static void test_before_4(int idx) {

   165         for (int i = 0; i < 1000; i++) {

   166             if (idx / (i+1) > 0) {

   167                 return;

   168             }

   169             array[idx] = 999;

   170         }

   171     }

   172 

   173     // Array store can't be moved out of the loop before the loop

   174     // header because it doesn't postdominate the loop head

   175     static void test_before_5(int idx) {

   176         for (int i = 0; i < 1000; i++) {

   177             if (i % 2 == 0) {

   178                 array[idx] = 999;

   179             }

   180         }

   181     }

   182 

   183     // Array store can be moved out of the loop before the loop header

   184     static int test_before_6(int idx) {

   185         int res = 0;

   186         for (int i = 0; i < 1000; i++) {

   187             if (i%2 == 1) {

   188                 res *= 2;

   189             } else {

   190                 res++;

   191             }

   192             array[idx] = 999;

   193         }

   194         return res;

   195     }

   196 

   197     final HashMap<String,Method> tests = new HashMap<>();

   198     {

   199         for (Method m : this.getClass().getDeclaredMethods()) {

   200             if (m.getName().matches("test_(before|after|stores)_[0-9]+")) {

   201                 assert(Modifier.isStatic(m.getModifiers())) : m;

   202                 tests.put(m.getName(), m);

   203             }

   204         }

   205     }

   206 

   207     boolean success = true;

   208     void doTest(String name, Runnable init, Function<String, Boolean> check) throws Exception {

   209         Method m = tests.get(name);

   210         for (int i = 0; i < 20000; i++) {

   211             init.run();

   212             m.invoke(null, 0);

   213             success = success && check.apply(name);

   214             if (!success) {

   215                 break;

   216             }

   217         }

   218     }

   219 

   220     static void array_init() {

   221         array[0] = -1;

   222     }

   223 

   224     static boolean array_check(String name) {

   225         boolean success = true;

   226         if (array[0] != 999) {

   227             success = false;

   228             System.out.println(name + " failed: array[0] = " + array[0]);

   229         }

   230         return success;

   231     }

   232 

   233     static void array_init2() {

   234         for (int i = 0; i < 6; i++) {

   235             array[i] = -1;

   236         }

   237     }

   238 

   239     static boolean array_check2(String name) {

   240         boolean success = true;

   241         for (int i = 0; i < 6; i++) {

   242             if (array[i] != 999) {

   243                 success = false;

   244                 System.out.println(name + " failed: array[" + i + "] = " + array[i]);

   245             }

   246         }

   247         return success;

   248     }

   249 

   250     static void array_init3() {

   251         for (int i = 0; i < 3; i++) {

   252             array[i] = -1;

   253         }

   254     }

   255 

   256     static boolean array_check3(String name) {

   257         boolean success = true;

   258         for (int i = 0; i < 3; i++) {

   259             if (array[i] != i) {

   260                 success = false;

   261                 System.out.println(name + " failed: array[" + i + "] = " + array[i]);

   262             }

   263         }

   264         return success;

   265     }

   266 

   267     static void array_init4() {

   268         for (int i = 0; i < 3; i++) {

   269             byte_array[i] = -1;

   270         }

   271     }

   272 

   273     static boolean array_check4(String name) {

   274         boolean success = true;

   275         for (int i = 0; i < 3; i++) {

   276             if (byte_array[i] != i) {

   277                 success = false;

   278                 System.out.println(name + " failed: byte_array[" + i + "] = " + byte_array[i]);

   279             }

   280         }

   281         return success;

   282     }

   283 

   284     static public void main(String[] args) throws Exception {

   285         TestMoveStoresOutOfLoops test = new TestMoveStoresOutOfLoops();

   286         test.doTest("test_after_1", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);

   287         test.doTest("test_after_2", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);

   288         test.doTest("test_after_3", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);

   289         test.doTest("test_after_4", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);

   290         test.doTest("test_after_5", TestMoveStoresOutOfLoops::array_init2, TestMoveStoresOutOfLoops::array_check2);

   291         test.doTest("test_after_6", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);

   292         array3[999] = true;

   293         test.doTest("test_after_6", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);

   294 

   295         test.doTest("test_stores_1", TestMoveStoresOutOfLoops::array_init3, TestMoveStoresOutOfLoops::array_check3);

   296         test.doTest("test_stores_2", TestMoveStoresOutOfLoops::array_init3, TestMoveStoresOutOfLoops::array_check3);

   297         test.doTest("test_stores_3", TestMoveStoresOutOfLoops::array_init4, TestMoveStoresOutOfLoops::array_check4);

   298 

   299         test.doTest("test_before_1", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);

   300         test.doTest("test_before_2", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);

   301         test.doTest("test_before_3", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);

   302         test.doTest("test_before_4", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);

   303         test.doTest("test_before_5", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);

   304         test.doTest("test_before_6", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);

   305 

   306         if (!test.success) {

   307             throw new RuntimeException("Some tests failed");

   308         }

   309     }

   310 }