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 
  34 package compiler.loopopts;
  35 
  36 import java.lang.reflect.Method;
  37 import java.lang.reflect.Modifier;
  38 import java.util.HashMap;
  39 import java.util.function.Function;
  40 
  41 public 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 }