/*
* Copyright (C) 2017 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.
*/
/**
* Tests for optimizations of break-loops, i.e. loops that break
* out of a while-true loop when the end condition is satisfied.
* In particular, the tests focus on break-loops that can be
* rewritten into regular countable loops (this may improve certain
* loops generated by the Kotlin compiler for inclusive ranges).
*/
public class Main {
/// CHECK-START: int Main.breakLoop(int[]) induction_var_analysis (before)
/// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none
/// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none
/// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none
/// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none
/// CHECK-DAG: <<Phi:i\d+>> Phi [<<Zero>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none
/// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<One>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<NE:z\d+>> NotEqual [{{i\d+}},<<Phi>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none
//
/// CHECK-START: int Main.breakLoop(int[]) induction_var_analysis (after)
/// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none
/// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none
/// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none
/// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none
/// CHECK-DAG: <<Phi:i\d+>> Phi [<<Zero>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none
/// CHECK-DAG: <<LE:z\d+>> LessThanOrEqual [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: If [<<LE>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<One>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none
//
/// CHECK-START-ARM64: int Main.breakLoop(int[]) loop_optimization (after)
/// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none
/// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none
/// CHECK-DAG: <<Four:i\d+>> IntConstant 4 loop:none
/// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none
/// CHECK-DAG: <<Rep:d\d+>> VecReplicateScalar [<<One>>] loop:none
/// CHECK-DAG: VecStore [<<Nil>>,<<Phi:i\d+>>,<<Rep>>] loop:<<Loop:B\d+>> outer_loop:none
/// CHECK-DAG: Add [<<Phi>>,<<Four>>] loop:<<Loop>> outer_loop:none
static int breakLoop(int[] a) {
int l = 0;
int u = a.length - 1;
int i = l;
if (l <= u) {
while (true) {
a[i] = 1;
if (i == u) break;
i++;
}
}
return i;
}
/// CHECK-START: int Main.breakLoopDown(int[]) induction_var_analysis (before)
/// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none
/// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none
/// CHECK-DAG: <<MOne:i\d+>> IntConstant -1 loop:none
/// CHECK-DAG: <<Two:i\d+>> IntConstant 2 loop:none
/// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none
/// CHECK-DAG: <<Phi:i\d+>> Phi [{{i\d+}},<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none
/// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Two>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<NE:z\d+>> NotEqual [<<Phi>>,<<Zero>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<MOne>>] loop:<<Loop>> outer_loop:none
//
/// CHECK-START: int Main.breakLoopDown(int[]) induction_var_analysis (after)
/// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none
/// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none
/// CHECK-DAG: <<MOne:i\d+>> IntConstant -1 loop:none
/// CHECK-DAG: <<Two:i\d+>> IntConstant 2 loop:none
/// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none
/// CHECK-DAG: <<Phi:i\d+>> Phi [{{i\d+}},<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none
/// CHECK-DAG: <<GE:z\d+>> GreaterThanOrEqual [<<Phi>>,<<Zero>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: If [<<GE>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Two>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<MOne>>] loop:<<Loop>> outer_loop:none
static int breakLoopDown(int[] a) {
int l = 0;
int u = a.length - 1;
int i = u;
if (u >= l) {
while (true) {
a[i] = 2;
if (i == l) break;
i--;
}
}
return i;
}
/// CHECK-START: int Main.breakLoopSafeConst(int[]) induction_var_analysis (before)
/// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none
/// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none
/// CHECK-DAG: <<Three:i\d+>> IntConstant 3 loop:none
/// CHECK-DAG: <<L1:i\d+>> IntConstant 2147483631 loop:none
/// CHECK-DAG: <<L2:i\d+>> IntConstant 2147483646 loop:none
/// CHECK-DAG: <<Phi:i\d+>> Phi [<<L1>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none
/// CHECK-DAG: <<Sub:i\d+>> Sub [<<Phi>>,<<L1>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Sub>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Three>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<NE:z\d+>> NotEqual [<<Phi>>,<<L2>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none
//
/// CHECK-START: int Main.breakLoopSafeConst(int[]) induction_var_analysis (after)
/// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none
/// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none
/// CHECK-DAG: <<Three:i\d+>> IntConstant 3 loop:none
/// CHECK-DAG: <<L1:i\d+>> IntConstant 2147483631 loop:none
/// CHECK-DAG: <<L2:i\d+>> IntConstant 2147483646 loop:none
/// CHECK-DAG: <<Phi:i\d+>> Phi [<<L1>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none
/// CHECK-DAG: <<LE:z\d+>> LessThanOrEqual [<<Phi>>,<<L2>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Sub:i\d+>> Sub [<<Phi>>,<<L1>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Sub>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Three>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none
//
/// CHECK-START-ARM64: int Main.breakLoopSafeConst(int[]) loop_optimization (after)
/// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none
/// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none
/// CHECK-DAG: <<Three:i\d+>> IntConstant 3 loop:none
/// CHECK-DAG: <<Four:i\d+>> IntConstant 4 loop:none
/// CHECK-DAG: <<Rep:d\d+>> VecReplicateScalar [<<Three>>] loop:none
/// CHECK-DAG: VecStore [<<Par>>,<<Phi:i\d+>>,<<Rep>>] loop:<<Loop:B\d+>> outer_loop:none
/// CHECK-DAG: Add [<<Phi>>,<<Four>>] loop:<<Loop>> outer_loop:none
static int breakLoopSafeConst(int[] a) {
int l = Integer.MAX_VALUE - 16;
int u = Integer.MAX_VALUE - 1;
int i = l;
if (l <= u) { // will be removed by simplifier
while (true) {
a[i - l] = 3;
if (i == u) break;
i++;
}
}
return i;
}
/// CHECK-START: int Main.breakLoopUnsafeConst(int[]) induction_var_analysis (before)
/// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none
/// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none
/// CHECK-DAG: <<Four:i\d+>> IntConstant 4 loop:none
/// CHECK-DAG: <<L1:i\d+>> IntConstant 2147483632 loop:none
/// CHECK-DAG: <<L2:i\d+>> IntConstant 2147483647 loop:none
/// CHECK-DAG: <<Phi:i\d+>> Phi [<<L1>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none
/// CHECK-DAG: <<Sub:i\d+>> Sub [<<Phi>>,<<L1>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Sub>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Four>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<NE:z\d+>> NotEqual [<<Phi>>,<<L2>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none
//
/// CHECK-START: int Main.breakLoopUnsafeConst(int[]) induction_var_analysis (after)
/// CHECK-DAG: NotEqual
/// CHECK-NOT: LessThanOrEqual
static int breakLoopUnsafeConst(int[] a) {
int l = Integer.MAX_VALUE - 15;
int u = Integer.MAX_VALUE;
int i = l;
if (l <= u) { // will be removed by simplifier
while (true) {
a[i - l] = 4;
if (i == u) break; // rewriting exit not safe!
i++;
}
}
return i;
}
/// CHECK-START: int Main.breakLoopNastyPhi(int[]) induction_var_analysis (before)
/// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none
/// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none
/// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none
/// CHECK-DAG: <<Five:i\d+>> IntConstant 5 loop:none
/// CHECK-DAG: <<M123:i\d+>> IntConstant -123 loop:none
/// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none
/// CHECK-DAG: <<Phi:i\d+>> Phi [<<Zero>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none
/// CHECK-DAG: <<Wrap:i\d+>> Phi [<<M123>>,<<Phi>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: ArraySet [<<Nil>>,<<Bnd>>,<<Five>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<NE:z\d+>> NotEqual [{{i\d+}},<<Phi>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Comb:i\d+>> Phi [<<M123>>,<<Wrap>>] loop:none
/// CHECK-DAG: Return [<<Comb>>] loop:none
//
/// CHECK-START: int Main.breakLoopNastyPhi(int[]) induction_var_analysis (after)
/// CHECK-DAG: NotEqual
/// CHECK-NOT: LessThanOrEqual
static int breakLoopNastyPhi(int[] a) {
int l = 0;
int u = a.length - 1;
int x = -123;
if (l <= u) {
int i = l;
while (true) {
a[i] = 5;
if (i == u) break;
x = i;
i++;
}
}
return x; // keep another phi live
}
/// CHECK-START: int Main.breakLoopReduction(int[]) induction_var_analysis (before)
/// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none
/// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none
/// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none
/// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none
/// CHECK-DAG: <<Phi:i\d+>> Phi [<<Zero>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none
/// CHECK-DAG: <<Red:i\d+>> Phi [<<Zero>>,<<RedI:i\d+>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Get:i\d+>> ArrayGet [<<Nil>>,<<Bnd>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<RedI>> Add [<<Red>>,<<Get>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<NE:z\d+>> NotEqual [{{i\d+}},<<Phi>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: If [<<NE>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Comb:i\d+>> Phi [<<Zero>>,<<RedI>>] loop:none
/// CHECK-DAG: Return [<<Comb>>] loop:none
//
/// CHECK-START: int Main.breakLoopReduction(int[]) induction_var_analysis (after)
/// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none
/// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none
/// CHECK-DAG: <<One:i\d+>> IntConstant 1 loop:none
/// CHECK-DAG: <<Nil:l\d+>> NullCheck [<<Par>>] loop:none
/// CHECK-DAG: <<Phi:i\d+>> Phi [<<Zero>>,<<AddI:i\d+>>] loop:<<Loop:B\d+>> outer_loop:none
/// CHECK-DAG: <<Red:i\d+>> Phi [<<Zero>>,<<RedI:i\d+>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<LE:z\d+>> LessThanOrEqual [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: If [<<LE>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Bnd:i\d+>> BoundsCheck [<<Phi>>,{{i\d+}}] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Get:i\d+>> ArrayGet [<<Nil>>,<<Bnd>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<RedI>> Add [<<Red>>,<<Get>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<AddI>> Add [<<Phi>>,<<One>>] loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<Comb:i\d+>> Phi [<<Zero>>,<<Red>>] loop:none
/// CHECK-DAG: Return [<<Comb>>] loop:none
//
/// CHECK-START-ARM64: int Main.breakLoopReduction(int[]) loop_optimization (after)
/// CHECK-DAG: <<Par:l\d+>> ParameterValue loop:none
/// CHECK-DAG: <<Zero:i\d+>> IntConstant 0 loop:none
/// CHECK-DAG: <<Exp:d\d+>> VecSetScalars [<<Zero>>] loop:none
/// CHECK-DAG: <<VPhi:d\d+>> Phi [<<Exp>>,<<VAdd:d\d+>>] loop:<<Loop:B\d+>> outer_loop:none
/// CHECK-DAG: <<VLoad:d\d+>> VecLoad loop:<<Loop>> outer_loop:none
/// CHECK-DAG: <<VAdd>> VecAdd [<<VPhi>>,<<VLoad>>] loop:<<Loop>> outer_loop:none
static int breakLoopReduction(int[] a) {
int l = 0;
int u = a.length - 1;
int x = 0;
if (l <= u) {
int i = l;
while (true) {
x += a[i];
if (i == u) break;
i++;
}
}
return x;
}
//
// Test driver.
//
public static void main(String[] args) {
int[] a = new int[100];
expectEquals(99, breakLoop(a));
for (int i = 0; i < a.length; i++) {
expectEquals(1, a[i]);
}
expectEquals(0, breakLoopDown(a));
for (int i = 0; i < a.length; i++) {
expectEquals(2, a[i]);
}
expectEquals(Integer.MAX_VALUE - 1, breakLoopSafeConst(a));
for (int i = 0; i < a.length; i++) {
int e = i < 16 ? 3 : 2;
expectEquals(e, a[i]);
}
expectEquals(Integer.MAX_VALUE, breakLoopUnsafeConst(a));
for (int i = 0; i < a.length; i++) {
int e = i < 16 ? 4 : 2;
expectEquals(e, a[i]);
}
expectEquals(98, breakLoopNastyPhi(a));
for (int i = 0; i < a.length; i++) {
expectEquals(5, a[i]);
}
expectEquals(500, breakLoopReduction(a));
System.out.println("passed");
}
private static void expectEquals(int expected, int result) {
if (expected != result) {
throw new Error("Expected: " + expected + ", found: " + result);
}
}
}