summaryrefslogtreecommitdiff
path: root/test/669-checker-break/src/Main.java
diff options
context:
space:
mode:
Diffstat (limited to 'test/669-checker-break/src/Main.java')
-rw-r--r--test/669-checker-break/src/Main.java328
1 files changed, 328 insertions, 0 deletions
diff --git a/test/669-checker-break/src/Main.java b/test/669-checker-break/src/Main.java
new file mode 100644
index 0000000000..e59061b1aa
--- /dev/null
+++ b/test/669-checker-break/src/Main.java
@@ -0,0 +1,328 @@
+/*
+ * 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);
+ }
+ }
+}
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-21 05:50:47 +0000