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 8189067
  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 int[] array4 = new int[1000];
  47     private static byte[] byte_array = new byte[10];
  48 
  49     // Array store should be moved out of the loop, value stored
  50     // should be 999, the loop should be eliminated
  51     static void test_after_1(int idx) {
  52         for (int i = 0; i < 1000; i++) {
  53             array[idx] = i;
  54         }
  55     }
  56 
  57     // Array store can't be moved out of loop because of following
  58     // non loop invariant array access
  59     static void test_after_2(int idx) {
  60         for (int i = 0; i < 1000; i++) {
  61             array[idx] = i;
  62             array2[i%10] = i;
  63         }
  64     }
  65 
  66     // Array store can't be moved out of loop because of following
  67     // use
  68     static void test_after_3(int idx) {
  69         for (int i = 0; i < 1000; i++) {
  70             array[idx] = i;
  71             if (array[0] == -1) {
  72                 break;
  73             }
  74         }
  75     }
  76 
  77     // Array store can't be moved out of loop because of preceding
  78     // use
  79     static void test_after_4(int idx) {
  80         for (int i = 0; i < 1000; i++) {
  81             if (array[0] == -2) {
  82                 break;
  83             }
  84             array[idx] = i;
  85         }
  86     }
  87 
  88     // All array stores should be moved out of the loop, one after
  89     // the other
  90     static void test_after_5(int idx) {
  91         for (int i = 0; i < 1000; i++) {
  92             array[idx] = i;
  93             array[idx+1] = i;
  94             array[idx+2] = i;
  95             array[idx+3] = i;
  96             array[idx+4] = i;
  97             array[idx+5] = i;
  98         }
  99     }
 100 
 101     // Array store can be moved after the loop but needs to be
 102     // cloned on both exit paths
 103     static void test_after_6(int idx) {
 104         for (int i = 0; i < 1000; i++) {
 105             array[idx] = i;
 106             if (array3[i]) {
 107                 return;
 108             }
 109         }
 110     }
 111 
 112     // Array store can be moved out of the inner loop
 113     static void test_after_7(int idx) {
 114         for (int i = 0; i < 1000; i++) {
 115             for (int j = 0; j <= 42; j++) {
 116                 array4[i] = j;
 117             }
 118         }
 119     }
 120 
 121     // Optimize out redundant stores
 122     static void test_stores_1(int ignored) {
 123         array[0] = 0;
 124         array[1] = 1;
 125         array[2] = 2;
 126         array[0] = 0;
 127         array[1] = 1;
 128         array[2] = 2;
 129     }
 130 
 131     static void test_stores_2(int idx) {
 132         array[idx+0] = 0;
 133         array[idx+1] = 1;
 134         array[idx+2] = 2;
 135         array[idx+0] = 0;
 136         array[idx+1] = 1;
 137         array[idx+2] = 2;
 138     }
 139 
 140     static void test_stores_3(int idx) {
 141         byte_array[idx+0] = 0;
 142         byte_array[idx+1] = 1;
 143         byte_array[idx+2] = 2;
 144         byte_array[idx+0] = 0;
 145         byte_array[idx+1] = 1;
 146         byte_array[idx+2] = 2;
 147     }
 148 
 149     // Array store can be moved out of the loop before the loop header
 150     static void test_before_1(int idx) {
 151         for (int i = 0; i < 1000; i++) {
 152             array[idx] = 999;
 153         }
 154     }
 155 
 156     // Array store can't be moved out of the loop before the loop
 157     // header because there's more than one store on this slice
 158     static void test_before_2(int idx) {
 159         for (int i = 0; i < 1000; i++) {
 160             array[idx] = 999;
 161             array[i%2] = 0;
 162         }
 163     }
 164 
 165     // Array store can't be moved out of the loop before the loop
 166     // header because of use before store
 167     static int test_before_3(int idx) {
 168         int res = 0;
 169         for (int i = 0; i < 1000; i++) {
 170             res += array[i%10];
 171             array[idx] = 999;
 172         }
 173         return res;
 174     }
 175 
 176     // Array store can't be moved out of the loop before the loop
 177     // header because of possible early exit
 178     static void test_before_4(int idx) {
 179         for (int i = 0; i < 1000; i++) {
 180             if (idx / (i+1) > 0) {
 181                 return;
 182             }
 183             array[idx] = 999;
 184         }
 185     }
 186 
 187     // Array store can't be moved out of the loop before the loop
 188     // header because it doesn't postdominate the loop head
 189     static void test_before_5(int idx) {
 190         for (int i = 0; i < 1000; i++) {
 191             if (i % 2 == 0) {
 192                 array[idx] = 999;
 193             }
 194         }
 195     }
 196 
 197     // Array store can be moved out of the loop before the loop header
 198     static int test_before_6(int idx) {
 199         int res = 0;
 200         for (int i = 0; i < 1000; i++) {
 201             if (i%2 == 1) {
 202                 res *= 2;
 203             } else {
 204                 res++;
 205             }
 206             array[idx] = 999;
 207         }
 208         return res;
 209     }
 210 
 211     final HashMap<String,Method> tests = new HashMap<>();
 212     {
 213         for (Method m : this.getClass().getDeclaredMethods()) {
 214             if (m.getName().matches("test_(before|after|stores)_[0-9]+")) {
 215                 assert(Modifier.isStatic(m.getModifiers())) : m;
 216                 tests.put(m.getName(), m);
 217             }
 218         }
 219     }
 220 
 221     boolean success = true;
 222     void doTest(String name, Runnable init, Function<String, Boolean> check) throws Exception {
 223         Method m = tests.get(name);
 224         for (int i = 0; i < 20000; i++) {
 225             init.run();
 226             m.invoke(null, 0);
 227             success = success && check.apply(name);
 228             if (!success) {
 229                 break;
 230             }
 231         }
 232     }
 233 
 234     static void array_init() {
 235         array[0] = -1;
 236     }
 237 
 238     static boolean array_check(String name) {
 239         boolean success = true;
 240         if (array[0] != 999) {
 241             success = false;
 242             System.out.println(name + " failed: array[0] = " + array[0]);
 243         }
 244         return success;
 245     }
 246 
 247     static void array_init2() {
 248         for (int i = 0; i < 6; i++) {
 249             array[i] = -1;
 250         }
 251     }
 252 
 253     static boolean array_check2(String name) {
 254         boolean success = true;
 255         for (int i = 0; i < 6; i++) {
 256             if (array[i] != 999) {
 257                 success = false;
 258                 System.out.println(name + " failed: array[" + i + "] = " + array[i]);
 259             }
 260         }
 261         return success;
 262     }
 263 
 264     static void array_init3() {
 265         for (int i = 0; i < 3; i++) {
 266             array[i] = -1;
 267         }
 268     }
 269 
 270     static boolean array_check3(String name) {
 271         boolean success = true;
 272         for (int i = 0; i < 3; i++) {
 273             if (array[i] != i) {
 274                 success = false;
 275                 System.out.println(name + " failed: array[" + i + "] = " + array[i]);
 276             }
 277         }
 278         return success;
 279     }
 280 
 281     static void array_init4() {
 282         for (int i = 0; i < 3; i++) {
 283             byte_array[i] = -1;
 284         }
 285     }
 286 
 287     static boolean array_check4(String name) {
 288         boolean success = true;
 289         for (int i = 0; i < 3; i++) {
 290             if (byte_array[i] != i) {
 291                 success = false;
 292                 System.out.println(name + " failed: byte_array[" + i + "] = " + byte_array[i]);
 293             }
 294         }
 295         return success;
 296     }
 297 
 298     static boolean array_check5(String name) {
 299         boolean success = true;
 300         for (int i = 0; i < 1000; i++) {
 301             if (array4[i] != 42) {
 302                 success = false;
 303                 System.out.println(name + " failed: array[" + i + "] = " + array4[i]);
 304             }
 305         }
 306         return success;
 307     }
 308 
 309     static public void main(String[] args) throws Exception {
 310         TestMoveStoresOutOfLoops test = new TestMoveStoresOutOfLoops();
 311         test.doTest("test_after_1", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
 312         test.doTest("test_after_2", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
 313         test.doTest("test_after_3", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
 314         test.doTest("test_after_4", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
 315         test.doTest("test_after_5", TestMoveStoresOutOfLoops::array_init2, TestMoveStoresOutOfLoops::array_check2);
 316         test.doTest("test_after_6", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
 317         array3[999] = true;
 318         test.doTest("test_after_6", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
 319         test.doTest("test_after_7", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check5);
 320 
 321         test.doTest("test_stores_1", TestMoveStoresOutOfLoops::array_init3, TestMoveStoresOutOfLoops::array_check3);
 322         test.doTest("test_stores_2", TestMoveStoresOutOfLoops::array_init3, TestMoveStoresOutOfLoops::array_check3);
 323         test.doTest("test_stores_3", TestMoveStoresOutOfLoops::array_init4, TestMoveStoresOutOfLoops::array_check4);
 324 
 325         test.doTest("test_before_1", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
 326         test.doTest("test_before_2", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
 327         test.doTest("test_before_3", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
 328         test.doTest("test_before_4", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
 329         test.doTest("test_before_5", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
 330         test.doTest("test_before_6", TestMoveStoresOutOfLoops::array_init, TestMoveStoresOutOfLoops::array_check);
 331 
 332         if (!test.success) {
 333             throw new RuntimeException("Some tests failed");
 334         }
 335     }
 336 }