Home | History | Annotate | Download | only in src 
      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 public class Main {
     18 
     19   /**
     20    * Method with an outer countable loop and an inner do-while loop.
     21    * Since all work is done in the header of the inner loop, any invariant hoisting
     22    * and deopting should be done in its proper loop preheader, not the true-block
     23    * of the newly generated taken-test after dynamic BCE.
     24    */
     25   public static int doit(int[][] x, int j) {
     26     float f = 0;
     27     int acc = 0;
     28     for (int i = 0; i < 2; i++) {
     29       // The full body of a do-while loop is the loop header.
     30       do {
     31         // Some "noise" to avoid hoisting the array reference
     32         // before the dynamic BCE phase runs.
     33         f++;
     34         // The invariant array reference with corresponding bounds check
     35         // is a candidate for hoisting when dynamic BCE runs. If it is
     36         // not moved to the proper loop preheader, the wrong values
     37         // cause the test to fail.
     38         acc += x[i][i];
     39       } while (++j < i);
     40     }
     41     return acc;
     42   }
     43 
     44   /**
     45    * Single countable loop with a clear header and a loop body. In this case,
     46    * after dynamic bce, some invariant hoisting and deopting must go to the
     47    * proper loop preheader and some must go to the true-block.
     48    */
     49   public static int foo(int[] x, int[] y, int n) {
     50     float f = 0;
     51     int acc = 0;
     52     int i = 0;
     53     while (true) {
     54       // This part is the loop header.
     55       // Some "noise" to avoid hoisting the array reference
     56       // before the dynamic BCE phase runs.
     57       f++;
     58       // The invariant array reference with corresponding bounds check
     59       // is a candidate for hoisting when dynamic BCE runs. If it is
     60       // not moved to the proper loop preheader, the wrong values
     61       // cause the test to fail.
     62       acc += y[0];
     63       if (++i > n)
     64         break;
     65       // From here on, this part is the loop body.
     66       // The unit-stride array reference is a candidate for dynamic BCE.
     67       // The deopting appears in the true-block.
     68       acc += x[i];
     69     }
     70     return acc;
     71   }
     72 
     73   /**
     74    * An artificial example with an inconsistent phi structure during
     75    * dynamic bce that is corrected afterwards. Note that only the last
     76    * assignment is really live, but the other statements set up an
     77    * interesting phi structure.
     78    */
     79   private static int doit(int[] z) {
     80     int a = 0;
     81     for (int i = 0; i < 10; ++i) {
     82       for (int j = i; j < 10; ++j) {
     83         a = z[i];
     84         for (int k = 0; k < 10; ++k) {
     85           a += z[k];
     86           a = z[i];
     87         }
     88       }
     89     }
     90     return a;
     91   }
     92 
     93   /**
     94    * Example shows that we can hoist ArrayGet to pre-header only if
     95    * its execution is guaranteed.
     96    */
     97   public static int hoistcheck(int[] c) {
     98     int i = 0, i2 = 0, i3 = 0, k = 0;
     99     int n = c.length;
    100     for (i = -100000000; i < 20; i += 10000000) {
    101       i3 = i;
    102       i2 = 0;
    103       while (i2++ < 1) {
    104         if (i3 >= 0 && i3 < n) {
    105           k += c[i3];
    106         }
    107       }
    108     }
    109     return k;
    110   }
    111 
    112   public static void main(String args[]) {
    113     int[][] x = new int[2][2];
    114     int y;
    115 
    116     x[0][0] = 1;
    117     x[1][1] = 2;
    118 
    119     expectEquals(8, doit(x, -6));
    120     expectEquals(7, doit(x, -5));
    121     expectEquals(6, doit(x, -4));
    122     expectEquals(5, doit(x, -3));
    123     expectEquals(4, doit(x, -2));
    124     expectEquals(3, doit(x, -1));
    125     expectEquals(3, doit(x,  0));
    126     expectEquals(3, doit(x,  1));
    127     expectEquals(3, doit(x, 22));
    128 
    129     int a[] = { 1, 2, 3, 5 };
    130     int b[] = { 7 };
    131 
    132     expectEquals(7,  foo(a, b, -1));
    133     expectEquals(7,  foo(a, b,  0));
    134     expectEquals(16, foo(a, b,  1));
    135     expectEquals(26, foo(a, b,  2));
    136     expectEquals(38, foo(a, b,  3));
    137 
    138     int[] z = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    139     expectEquals(10, doit(z));
    140 
    141     int c[] = { 1, 2, 3, 5 };
    142     expectEquals(1, hoistcheck(c));
    143 
    144     System.out.println("passed");
    145   }
    146 
    147   private static void expectEquals(int expected, int result) {
    148     if (expected != result) {
    149       throw new Error("Expected: " + expected + ", found: " + result);
    150     }
    151   }
    152 }
    153