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