/*
* 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);
}
}
}