content: /*
   * Copyright (C) 2016 The Android Open Source Project
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  //
  // Test on loop optimizations, in particular around geometric induction.
  //
  public class Main {
  
    /// CHECK-START: int Main.geo1(int) loop_optimization (before)
    /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
    /// CHECK-DAG: Mul loop:<<Loop>>
    //
    /// CHECK-START: int Main.geo1(int) loop_optimization (after)
    /// CHECK-DAG: <<Par:i\d+>> ParameterValue         loop:none
    /// CHECK-DAG: <<Zer:i\d+>> IntConstant 0          loop:none
    /// CHECK-DAG: <<Int:i\d+>> IntConstant 1410065408 loop:none
    /// CHECK-DAG: <<Mul:i\d+>> Mul [<<Par>>,<<Int>>]  loop:none
    /// CHECK-DAG: <<Add:i\d+>> Add [<<Mul>>,<<Zer>>]  loop:none
    /// CHECK-DAG:              Return [<<Add>>]       loop:none
    //
    /// CHECK-START: int Main.geo1(int) loop_optimization (after)
    /// CHECK-NOT: Phi
    public static int geo1(int a) {
      for (int i = 0; i < 10; i++) {
        a *= 10;
      }
      return a;
    }
  
    /// CHECK-START: int Main.geo2(int) loop_optimization (before)
    /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
    /// CHECK-DAG: Shl loop:<<Loop>>
    //
    /// CHECK-START: int Main.geo2(int) loop_optimization (after)
    /// CHECK-DAG: <<Par:i\d+>> ParameterValue        loop:none
    /// CHECK-DAG: <<Zer:i\d+>> IntConstant 0         loop:none
    /// CHECK-DAG: <<Int:i\d+>> IntConstant 1024      loop:none
    /// CHECK-DAG: <<Mul:i\d+>> Mul [<<Par>>,<<Int>>] loop:none
    /// CHECK-DAG: <<Add:i\d+>> Add [<<Mul>>,<<Zer>>] loop:none
    /// CHECK-DAG:              Return [<<Add>>]      loop:none
    //
    /// CHECK-START: int Main.geo2(int) loop_optimization (after)
    /// CHECK-NOT: Phi
    public static int geo2(int a) {
      for (int i = 0; i < 10; i++) {
        a <<= 1;
      }
      return a;
    }
  
    /// CHECK-START: int Main.geo3(int) loop_optimization (before)
    /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
    /// CHECK-DAG: Div loop:<<Loop>>
    //
    /// CHECK-START: int Main.geo3(int) loop_optimization (after)
    /// CHECK-DAG: <<Par:i\d+>> ParameterValue        loop:none
    /// CHECK-DAG: <<Zer:i\d+>> IntConstant 0         loop:none
    /// CHECK-DAG: <<Int:i\d+>> IntConstant 59049     loop:none
    /// CHECK-DAG: <<Div:i\d+>> Div [<<Par>>,<<Int>>] loop:none
    /// CHECK-DAG: <<Add:i\d+>> Add [<<Div>>,<<Zer>>] loop:none
    /// CHECK-DAG:              Return [<<Add>>]      loop:none
    //
    /// CHECK-START: int Main.geo3(int) loop_optimization (after)
    /// CHECK-NOT: Phi
    public static int geo3(int a) {
      for (int i = 0; i < 10; i++) {
        a /= 3;
      }
      return a;
    }
  
    /// CHECK-START: int Main.geo4(int) loop_optimization (before)
    /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
    /// CHECK-DAG: Rem loop:<<Loop>>
    //
    /// CHECK-START: int Main.geo4(int) loop_optimization (after)
    /// CHECK-DAG: <<Par:i\d+>> ParameterValue        loop:none
    /// CHECK-DAG: <<Int:i\d+>> IntConstant 7         loop:none
    /// CHECK-DAG: <<Rem:i\d+>> Rem [<<Par>>,<<Int>>] loop:none
    /// CHECK-DAG:              Return [<<Rem>>]      loop:none
    //
    /// CHECK-START: int Main.geo4(int) loop_optimization (after)
    /// CHECK-NOT: Phi
    public static int geo4(int a) {
      for (int i = 0; i < 10; i++) {
        a %= 7;  // a wrap-around induction
      }
      return a;
    }
  
    /// CHECK-START: int Main.geo5() loop_optimization (before)
    /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
    /// CHECK-DAG: Shr loop:<<Loop>>
    //
    /// CHECK-START: int Main.geo5() loop_optimization (after)
    /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0          loop:none
    /// CHECK-DAG: <<Int1:i\d+>> IntConstant 2147483647 loop:none
    /// CHECK-DAG: <<Int2:i\d+>> IntConstant 1024       loop:none
    /// CHECK-DAG: <<Div:i\d+>>  Div [<<Int1>>,<<Int2>>] loop:none
    /// CHECK-DAG: <<Add:i\d+>>  Add [<<Div>>,<<Zero>>]  loop:none
    /// CHECK-DAG:               Return [<<Add>>]        loop:none
    //
    /// CHECK-START: int Main.geo5() loop_optimization (after)
    /// CHECK-NOT: Phi
    public static int geo5() {
      int a = 0x7fffffff;
      for (int i = 0; i < 10; i++) {
        a >>= 1;
      }
      return a;
    }
  
    // TODO: someday?
    //
    /// CHECK-START: int Main.geo1BCE() BCE (before)
    /// CHECK-DAG: BoundsCheck loop:none
    /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
    //
    /// CHECK-START: int Main.geo1BCE() BCE (after)
    /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
    //
    /// CHECK-START: int Main.geo1BCE() BCE (after)
    /// CHECK-NOT: BoundsCheck loop:none
    /// CHECK-NOT: Deoptimize
    public static int geo1BCE() {
      int[] x = {  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,
                  11, 12, 13, 14, 15, 16, 17, 19, 19, 20,
                  21, 22, 23, 24, 25, 26 };
      int a = 1;
      int r = 0;
      for (int i = 0; i < 3; i++) {
        r += x[a];
        a *= 5;
      }
      return r;
    }
  
    // TODO: someday?
    //
    /// CHECK-START: int Main.geo2BCE() BCE (before)
    /// CHECK-DAG: BoundsCheck loop:none
    /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
    //
    /// CHECK-START: int Main.geo2BCE() BCE (after)
    /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
    //
    /// CHECK-START: int Main.geo2BCE() BCE (after)
    /// CHECK-NOT: BoundsCheck loop:none
    /// CHECK-NOT: Deoptimize
    public static int geo2BCE() {
      int[] x = {  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,
                  11, 12, 13, 14, 15, 16, 17, 19, 19, 20,
                  21, 22, 23, 24, 25, 26 };
      int a = 1;
      int r = 0;
      for (int i = 0; i < 5; i++) {
        r += x[a];
        a <<= 1;
      }
      return r;
    }
  
    /// CHECK-START: int Main.geo3BCE() BCE (before)
    /// CHECK-DAG: BoundsCheck loop:none
    /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
    //
    /// CHECK-START: int Main.geo3BCE() BCE (after)
    /// CHECK-NOT: BoundsCheck
    /// CHECK-NOT: Deoptimize
    public static int geo3BCE() {
      int[] x = {  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,
                  11, 12, 13, 14, 15, 16, 17, 19, 19, 20,
                  21, 22, 23, 24, 25, 26 };
      int a = 25;
      int r = 0;
      for (int i = 0; i < 100; i++) {  // a converges to 0
        r += x[a];
        a /= 5;
      }
      return r;
    }
  
    /// CHECK-START: int Main.geo4BCE() BCE (before)
    /// CHECK-DAG: BoundsCheck loop:none
    /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
    //
    /// CHECK-START: int Main.geo4BCE() BCE (after)
    /// CHECK-NOT: BoundsCheck
    /// CHECK-NOT: Deoptimize
    public static int geo4BCE() {
      int[] x = {  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,
                  11, 12, 13, 14, 15, 16, 17, 19, 19, 20,
                  21, 22, 23, 24, 25, 26 };
      int a = 25;
      int r = 0;
      for (int i = 0; i < 100; i++) {  // a converges to 0
        r += x[a];
        a %= 5;  // a wrap-around induction
      }
      return r;
    }
  
    /// CHECK-START: int Main.geoMulBlackHole(int) loop_optimization (before)
    /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
    /// CHECK-DAG: Mul loop:<<Loop>>
    //
    /// CHECK-START: int Main.geoMulBlackHole(int) loop_optimization (after)
    /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0
    /// CHECK-DAG:               Return [<<Zero>>]
    //
    /// CHECK-START: int Main.geoMulBlackHole(int) loop_optimization (after)
    /// CHECK-NOT: Phi
    /// CHECK-NOT: Mul
    public static int geoMulBlackHole(int a) {
      for (int i = 0; i < 100; i++) {
        a *= 10;
      }
      return a;
    }
  
    /// CHECK-START: int Main.geoShlBlackHole(int) loop_optimization (before)
    /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
    /// CHECK-DAG: Shl loop:<<Loop>>
    //
    /// CHECK-START: int Main.geoShlBlackHole(int) loop_optimization (after)
    /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0
    /// CHECK-DAG:               Return [<<Zero>>]
    //
    /// CHECK-START: int Main.geoShlBlackHole(int) loop_optimization (after)
    /// CHECK-NOT: Phi
    /// CHECK-NOT: Shl
    public static int geoShlBlackHole(int a) {
      for (int i = 0; i < 100; i++) {
        a <<= 1;
      }
      return a;
    }
  
    /// CHECK-START: int Main.geoDivBlackHole(int) loop_optimization (before)
    /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
    /// CHECK-DAG: Div loop:<<Loop>>
    //
    /// CHECK-START: int Main.geoDivBlackHole(int) loop_optimization (after)
    /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0
    /// CHECK-DAG:               Return [<<Zero>>]
    //
    /// CHECK-START: int Main.geoDivBlackHole(int) loop_optimization (after)
    /// CHECK-NOT: Phi
    /// CHECK-NOT: Div
    public static int geoDivBlackHole(int a) {
      for (int i = 0; i < 100; i++) {
        a /= 10;
      }
      return a;
    }
  
    // Even though Rem is already optimized away by the time induction analysis
    // and the loop optimizer run, the loop is optimized with a trivial
    // wrap-around induction just as the wrap-around for REM would.
    //
    /// CHECK-START: int Main.geoRemBlackHole(int) loop_optimization (before)
    /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
    /// CHECK-DAG: Phi loop:<<Loop>>
    //
    /// CHECK-START: int Main.geoRemBlackHole(int) loop_optimization (after)
    /// CHECK-DAG: <<Zero:i\d+>> IntConstant 0
    /// CHECK-DAG:               Return [<<Zero>>]
    //
    /// CHECK-START: int Main.geoRemBlackHole(int) loop_optimization (after)
    /// CHECK-NOT: Phi
    public static int geoRemBlackHole(int a) {
      for (int i = 0; i < 100; i++) {
        a %= 1;
      }
      return a;
    }
  
    //
    // Verifier.
    //
  
    public static void main(String[] args) {
      int m = 1410065408;
      for (int i = -100; i <= 100; i++) {
        expectEquals(m * i, geo1(i));
      }
      for (int i = 1; i <= 1000000000; i *= 10) {
        expectEquals( m * i, geo1( i));
        expectEquals(-m * i, geo1(-i));
      }
  
      for (int i = -100; i <= 100; i++) {
        expectEquals(i << 10, geo2(i));
      }
      for (int i = 0; i < 22; i++) {
        expectEquals(1 << (i + 10), geo2(1 << i));
      }
      expectEquals(0x80000400, geo2(0x00200001));
      expectEquals(0x00000000, geo2(0x00400000));
      expectEquals(0x00000400, geo2(0x00400001));
  
      int d = 59049;
      for (int i = -100; i <= 100; i++) {
        expectEquals(0, geo3(i));
      }
      for (int i = 1; i <= 100; i++) {
        expectEquals( i, geo3( i * d));
        expectEquals( i, geo3( i * d + 1));
        expectEquals(-i, geo3(-i * d));
        expectEquals(-i, geo3(-i * d - 1));
      }
  
      for (int i = -100; i <= 100; i++) {
        expectEquals(i % 7, geo4(i));
      }
  
      expectEquals(0x1fffff, geo5());
  
      expectEquals(34,  geo1BCE());
      expectEquals(36,  geo2BCE());
      expectEquals(131, geo3BCE());
      expectEquals(125, geo4BCE());
  
      // Nothing escapes!
      expectEquals(0, geoMulBlackHole(0));
      expectEquals(0, geoShlBlackHole(0));
      expectEquals(0, geoDivBlackHole(0));
      expectEquals(0, geoRemBlackHole(0));
      for (int i = -100; i <= 100; i++) {
        expectEquals(0, geoMulBlackHole(i));
        expectEquals(0, geoShlBlackHole(i));
        expectEquals(0, geoDivBlackHole(i));
        expectEquals(0, geoRemBlackHole(i));
      }
      for (int i = 0; i < 31; i++) {
        expectEquals(0, geoMulBlackHole(1 << i));
        expectEquals(0, geoShlBlackHole(1 << i));
        expectEquals(0, geoDivBlackHole(1 << i));
        expectEquals(0, geoRemBlackHole(1 << i));
      }
      expectEquals(0, geoMulBlackHole(0x7fffffff));
      expectEquals(0, geoShlBlackHole(0x7fffffff));
      expectEquals(0, geoDivBlackHole(0x7fffffff));
      expectEquals(0, geoRemBlackHole(0x7fffffff));
      expectEquals(0, geoMulBlackHole(0x80000000));
      expectEquals(0, geoShlBlackHole(0x80000000));
      expectEquals(0, geoDivBlackHole(0x80000000));
      expectEquals(0, geoRemBlackHole(0x80000000));
  
      System.out.println("passed");
    }
  
    private static void expectEquals(int expected, int result) {
      if (expected != result) {
        throw new Error("Expected: " + expected + ", found: " + result);
      }
    }
  }
  