/*
 * 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 polynomial induction.
//
public class Main {

  /// CHECK-START: int Main.poly1() loop_optimization (before)
  /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
  /// CHECK-DAG: Add loop:<<Loop>>
  /// CHECK-DAG: Add loop:<<Loop>>
  //
  /// CHECK-START: int Main.poly1() loop_optimization (after)
  /// CHECK-DAG: <<Zer:i\d+>> IntConstant 0         loop:none
  /// CHECK-DAG: <<Int:i\d+>> IntConstant 55        loop:none
  /// CHECK-DAG: <<Add:i\d+>> Add [<<Int>>,<<Zer>>] loop:none
  /// CHECK-DAG:              Return [<<Add>>]      loop:none
  //
  /// CHECK-START: int Main.poly1() instruction_simplifier$before_codegen (after)
  /// CHECK-DAG: <<Int:i\d+>>  IntConstant 55 loop:none
  /// CHECK-DAG:               Return [<<Int>>]  loop:none
  //
  /// CHECK-START: int Main.poly1() loop_optimization (after)
  /// CHECK-NOT: Phi
  public static int poly1() {
    int a = 0;
    for (int i = 0; i <= 10; i++) {
      a += i;
    }
    return a;
  }

  // Multiplication in linear induction has been optimized earlier,
  // but that does not stop the induction variable recognition
  // and loop optimizer.
  //
  /// CHECK-START: int Main.poly2(int) loop_optimization (before)
  /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
  /// CHECK-DAG: Shl loop:<<Loop>>
  /// CHECK-DAG: Add loop:<<Loop>>
  /// CHECK-DAG: Add loop:<<Loop>>
  /// CHECK-DAG: Add loop:<<Loop>>
  /// CHECK-DAG: Add loop:<<Loop>>
  //
  /// CHECK-START: int Main.poly2(int) loop_optimization (after)
  /// CHECK-DAG: <<Par:i\d+>> ParameterValue        loop:none
  /// CHECK-DAG: <<Int:i\d+>> IntConstant 185       loop:none
  /// CHECK-DAG: <<Add:i\d+>> Add [<<Int>>,<<Par>>] loop:none
  /// CHECK-DAG:              Return [<<Add>>]      loop:none
  //
  /// CHECK-START: int Main.poly2(int) loop_optimization (after)
  /// CHECK-NOT: Phi
  public static int poly2(int a) {
    for (int i = 0; i < 10; i++) {
      int k = 3 * i + 5;
      a += k;
    }
    return a;
  }

  /// CHECK-START: int Main.poly3() loop_optimization (before)
  /// CHECK-DAG: Phi loop:<<Loop:B\d+>>
  /// CHECK-DAG: Add loop:<<Loop>>
  /// CHECK-DAG: Add loop:<<Loop>>
  //
  /// CHECK-START: int Main.poly3() loop_optimization (after)
  /// CHECK-DAG: <<Ini:i\d+>> IntConstant 12345       loop:none
  /// CHECK-DAG: <<Int:i\d+>> IntConstant -2146736968 loop:none
  /// CHECK-DAG: <<Add:i\d+>> Add [<<Int>>,<<Ini>>]   loop:none
  /// CHECK-DAG:              Return [<<Add>>]        loop:none
  //
  /// CHECK-START: int Main.poly3() instruction_simplifier$before_codegen (after)
  /// CHECK-DAG: <<Int:i\d+>>  IntConstant -2146724623 loop:none
  /// CHECK-DAG:               Return [<<Int>>]        loop:none
  //
  /// CHECK-START: int Main.poly3() loop_optimization (after)
  /// CHECK-NOT: Phi
  public static int poly3() {
    int a = 12345;
    for (int i = 0; i <= 10; i++) {
      a += (2147483646 * i + 67890);
    }
    return a;
  }

  /// CHECK-START: int Main.polyBCE1() BCE (before)
  /// CHECK-DAG: BoundsCheck loop:none
  /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
  //
  /// CHECK-START: int Main.polyBCE1() BCE (after)
  /// CHECK-NOT: BoundsCheck
  /// CHECK-NOT: Deoptimize
  public static int polyBCE1() {
    int[] x = {  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,
                11, 12, 13, 14, 15, 16, 17, 19, 19, 20,
                21, 22 };
    int a = 0;
    int r = 0;
    for (int i = 0; i < 8; i++) {
      r += x[a];
      a += i;
    }
    return r;
  }

  /// CHECK-START: int Main.polyBCE2() BCE (before)
  /// CHECK-DAG: BoundsCheck loop:none
  /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
  //
  /// CHECK-START: int Main.polyBCE2() BCE (after)
  /// CHECK-NOT: BoundsCheck
  /// CHECK-NOT: Deoptimize
  public static int polyBCE2() {
    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, 27 };
    int a = 1;
    int r = 0;
    for (int i = 0; i < 6; i++) {
      int k = 2 * i + 1;
      r -= x[a];
      a += k;
    }
    return r;
  }

  /// CHECK-START: int Main.polyBCE3() BCE (before)
  /// CHECK-DAG: BoundsCheck loop:none
  /// CHECK-DAG: BoundsCheck loop:{{B\d+}}
  //
  /// CHECK-START: int Main.polyBCE3() BCE (after)
  /// CHECK-NOT: BoundsCheck
  /// CHECK-NOT: Deoptimize
  public static int polyBCE3() {
    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, 27, 28, 29, 30,
                31, 32, 33, 34, 35, 36, 37, 38 };
    int r = 0;
    int a1 = 1;
    int a2 = 2;
    for (int i = 0; i < 5; i++) {
      int t = a1 + a2;  // two polynomials combined into new polynomial
      r -= x[t];
      a1 += (3 * i + 1);
      a2 += (2 * i);
    }
    return r;
  }

  //
  // Verifier.
  //

  public static void main(String[] args) {
    expectEquals(55, poly1());
    expectEquals(185, poly2(0));
    expectEquals(192, poly2(7));
    expectEquals(-2146724623, poly3());
    expectEquals(64, polyBCE1());
    expectEquals(-68, polyBCE2());
    expectEquals(-80, polyBCE3());

    System.out.println("passed");
  }

  private static void expectEquals(int expected, int result) {
    if (expected != result) {
      throw new Error("Expected: " + expected + ", found: " + result);
    }
  }
}