| /* |
| * 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. |
| */ |
| |
| /** |
| * Tests on loop optimizations related to induction. |
| */ |
| public class Main { |
| |
| static int[] a = new int[10]; |
| |
| static int[] novec = new int[20]; // to prevent vectorization |
| |
| /// CHECK-START: void Main.deadSingleLoop() loop_optimization (before) |
| /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none |
| // |
| /// CHECK-START: void Main.deadSingleLoop() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| static void deadSingleLoop() { |
| for (int i = 0; i < 4; i++) { |
| } |
| } |
| |
| /// CHECK-START: void Main.deadSingleLoop() loop_optimization (before) |
| /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none |
| // |
| /// CHECK-START: void Main.deadSingleLoop() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| static void deadSingleLoopN(int n) { |
| for (int i = 0; i < n; i++) { |
| } |
| } |
| |
| /// CHECK-START: void Main.potentialInfiniteLoop(int) loop_optimization (before) |
| /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none |
| // |
| /// CHECK-START: void Main.potentialInfiniteLoop(int) loop_optimization (after) |
| /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none |
| static void potentialInfiniteLoop(int n) { |
| for (int i = 0; i <= n; i++) { // loops forever when n = MAX_INT |
| } |
| } |
| |
| /// CHECK-START: void Main.deadNestedLoops() loop_optimization (before) |
| /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop>> |
| // |
| /// CHECK-START: void Main.deadNestedLoops() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| static void deadNestedLoops() { |
| for (int i = 0; i < 4; i++) { |
| for (int j = 0; j < 4; j++) { |
| } |
| } |
| } |
| |
| /// CHECK-START: void Main.deadNestedAndFollowingLoops() loop_optimization (before) |
| /// CHECK-DAG: Phi loop:<<Loop1:B\d+>> outer_loop:none |
| /// CHECK-DAG: Phi loop:<<Loop2:B\d+>> outer_loop:<<Loop1>> |
| /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop2>> |
| /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop2>> |
| /// CHECK-DAG: Phi loop:<<Loop3:B\d+>> outer_loop:<<Loop1>> |
| /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:<<Loop3>> |
| /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none |
| // |
| /// CHECK-START: void Main.deadNestedAndFollowingLoops() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| static void deadNestedAndFollowingLoops() { |
| for (int i = 0; i < 4; i++) { |
| for (int j = 0; j < 4; j++) { |
| for (int k = 0; k < 4; k++) { |
| } |
| for (int k = 0; k < 4; k++) { |
| } |
| } |
| for (int j = 0; j < 4; j++) { |
| for (int k = 0; k < 4; k++) { |
| } |
| } |
| } |
| for (int i = 0; i < 4; i++) { |
| } |
| } |
| |
| /// CHECK-START: void Main.deadConditional(int) loop_optimization (before) |
| /// CHECK-DAG: Phi loop:{{B\d+}} outer_loop:none |
| // |
| /// CHECK-START: void Main.deadConditional(int) loop_optimization (after) |
| /// CHECK-NOT: Phi |
| public static void deadConditional(int n) { |
| int k = 0; |
| int m = 0; |
| for (int i = 0; i < n; i++) { |
| if (i == 3) |
| k = i; |
| else |
| m = i; |
| } |
| } |
| |
| /// CHECK-START: void Main.deadConditionalCycle(int) loop_optimization (before) |
| /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none |
| // |
| /// CHECK-START: void Main.deadConditionalCycle(int) loop_optimization (after) |
| /// CHECK-NOT: Phi |
| public static void deadConditionalCycle(int n) { |
| int k = 0; |
| int m = 0; |
| for (int i = 0; i < n; i++) { |
| if (i == 3) |
| k--; |
| else |
| m++; |
| } |
| } |
| |
| |
| /// CHECK-START: void Main.deadInduction() loop_optimization (before) |
| /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none |
| // |
| /// CHECK-START: void Main.deadInduction() loop_optimization (after) |
| /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-NOT: Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none |
| static void deadInduction() { |
| int dead = 0; |
| for (int i = 0; i < a.length; i++) { |
| a[i] = novec[2 * i] + 1; |
| dead += 5; |
| } |
| } |
| |
| /// CHECK-START: void Main.deadManyInduction() loop_optimization (before) |
| /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none |
| // |
| /// CHECK-START: void Main.deadManyInduction() loop_optimization (after) |
| /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-NOT: Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none |
| static void deadManyInduction() { |
| int dead1 = 0, dead2 = 1, dead3 = 3; |
| for (int i = 0; i < a.length; i++) { |
| dead1 += 5; |
| a[i] = novec[2 * i] + 2; |
| dead2 += 10; |
| dead3 += 100; |
| } |
| } |
| |
| /// CHECK-START: void Main.deadSequence() loop_optimization (before) |
| /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none |
| // |
| /// CHECK-START: void Main.deadSequence() loop_optimization (after) |
| /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-NOT: Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none |
| static void deadSequence() { |
| int dead = 0; |
| for (int i = 0; i < a.length; i++) { |
| a[i] = novec[2 * i] + 3; |
| // Increment value defined inside loop, |
| // but sequence itself not used anywhere. |
| dead += i; |
| } |
| } |
| |
| /// CHECK-START: void Main.deadCycleWithException(int) loop_optimization (before) |
| /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none |
| /// CHECK-NOT: BoundsCheck |
| // |
| /// CHECK-START: void Main.deadCycleWithException(int) loop_optimization (after) |
| /// CHECK-DAG: Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-NOT: Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArraySet loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: ArrayGet loop:<<Loop>> outer_loop:none |
| /// CHECK-NOT: ArrayGet loop:<<Loop>> outer_loop:none |
| static void deadCycleWithException(int k) { |
| int dead = 0; |
| for (int i = 0; i < a.length; i++) { |
| a[i] = novec[2 * i] + 4; |
| // Increment value of dead cycle may throw exception. Dynamic |
| // BCE takes care of the bounds check though, which enables |
| // removing the ArrayGet after removing the dead cycle. |
| dead += a[k]; |
| } |
| } |
| |
| /// CHECK-START: int Main.closedFormInductionUp() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi1>>] loop:none |
| // |
| /// CHECK-START: int Main.closedFormInductionUp() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: int Main.closedFormInductionUp() instruction_simplifier$after_bce (after) |
| /// CHECK-DAG: <<Int:i\d+>> IntConstant 12395 loop:none |
| /// CHECK-DAG: Return [<<Int>>] loop:none |
| static int closedFormInductionUp() { |
| int closed = 12345; |
| for (int i = 0; i < 10; i++) { |
| closed += 5; |
| } |
| return closed; // only needs last value |
| } |
| |
| /// CHECK-START: int Main.closedFormInductionInAndDown(int) loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi2>>] loop:none |
| // |
| /// CHECK-START: int Main.closedFormInductionInAndDown(int) loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: int Main.closedFormInductionInAndDown(int) instruction_simplifier$after_bce (after) |
| /// CHECK-DAG: <<Par:i\d+>> ParameterValue loop:none |
| /// CHECK-DAG: <<Int:i\d+>> IntConstant -50 loop:none |
| /// CHECK-DAG: <<Add:i\d+>> Add [<<Int>>,<<Par>>] loop:none |
| /// CHECK-DAG: Return [<<Add>>] loop:none |
| static int closedFormInductionInAndDown(int closed) { |
| for (int i = 0; i < 10; i++) { |
| closed -= 5; |
| } |
| return closed; // only needs last value |
| } |
| |
| /// CHECK-START: int Main.closedFormInductionTrivialIf() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Select loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi1>>] loop:none |
| // |
| /// CHECK-START: int Main.closedFormInductionTrivialIf() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| /// CHECK-NOT: Select |
| // |
| /// CHECK-START: int Main.closedFormInductionTrivialIf() instruction_simplifier$after_bce (after) |
| /// CHECK-DAG: <<Int:i\d+>> IntConstant 81 loop:none |
| /// CHECK-DAG: Return [<<Int>>] loop:none |
| static int closedFormInductionTrivialIf() { |
| int closed = 11; |
| for (int i = 0; i < 10; i++) { |
| // Trivial if becomes trivial select at HIR level. |
| // Make sure this is still recognized as induction. |
| if (i < 5) { |
| closed += 7; |
| } else { |
| closed += 7; |
| } |
| } |
| return closed; // only needs last value |
| } |
| |
| /// CHECK-START: int Main.closedFormNested() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop1>> outer_loop:none |
| /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop2:B\d+>> outer_loop:<<Loop1>> |
| /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop2>> outer_loop:<<Loop1>> |
| /// CHECK-DAG: Return [<<Phi2>>] loop:none |
| // |
| /// CHECK-START: int Main.closedFormNested() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: int Main.closedFormNested() instruction_simplifier$after_bce (after) |
| /// CHECK-DAG: <<Int:i\d+>> IntConstant 100 loop:none |
| /// CHECK-DAG: Return [<<Int>>] loop:none |
| static int closedFormNested() { |
| int closed = 0; |
| for (int i = 0; i < 10; i++) { |
| for (int j = 0; j < 10; j++) { |
| closed++; |
| } |
| } |
| return closed; // only needs last-value |
| } |
| |
| /// CHECK-START: int Main.closedFormNestedAlt() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop1>> outer_loop:none |
| /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop2:B\d+>> outer_loop:<<Loop1>> |
| /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop2>> outer_loop:<<Loop1>> |
| /// CHECK-DAG: Return [<<Phi2>>] loop:none |
| // |
| /// CHECK-START: int Main.closedFormNestedAlt() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: int Main.closedFormNestedAlt() instruction_simplifier$after_bce (after) |
| /// CHECK-DAG: <<Int:i\d+>> IntConstant 15082 loop:none |
| /// CHECK-DAG: Return [<<Int>>] loop:none |
| static int closedFormNestedAlt() { |
| int closed = 12345; |
| for (int i = 0; i < 17; i++) { |
| for (int j = 0; j < 23; j++) { |
| closed += 7; |
| } |
| } |
| return closed; // only needs last-value |
| } |
| |
| // TODO: taken test around closed form? |
| static int closedFormInductionUpN(int n) { |
| int closed = 12345; |
| for (int i = 0; i < n; i++) { |
| closed += 5; |
| } |
| return closed; // only needs last value |
| } |
| |
| // TODO: taken test around closed form? |
| static int closedFormInductionInAndDownN(int closed, int n) { |
| for (int i = 0; i < n; i++) { |
| closed -= 5; |
| } |
| return closed; // only needs last value |
| } |
| |
| // TODO: move closed form even further out? |
| static int closedFormNestedN(int n) { |
| int closed = 0; |
| for (int i = 0; i < n; i++) { |
| for (int j = 0; j < 10; j++) { |
| closed++; |
| } |
| } |
| return closed; // only needs last-value |
| } |
| |
| // TODO: move closed form even further out? |
| static int closedFormNestedNAlt(int n) { |
| int closed = 12345; |
| for (int i = 0; i < n; i++) { |
| for (int j = 0; j < 23; j++) { |
| closed += 7; |
| } |
| } |
| return closed; // only needs last-value |
| } |
| |
| // TODO: move closed form even further out? |
| static int closedFormNestedMN(int m, int n) { |
| int closed = 0; |
| for (int i = 0; i < m; i++) { |
| for (int j = 0; j < n; j++) { |
| closed++; |
| } |
| } |
| return closed; // only needs last-value |
| } |
| |
| // TODO: move closed form even further out? |
| static int closedFormNestedMNAlt(int m, int n) { |
| int closed = 12345; |
| for (int i = 0; i < m; i++) { |
| for (int j = 0; j < n; j++) { |
| closed += 7; |
| } |
| } |
| return closed; // only needs last-value |
| } |
| |
| /// CHECK-START: int Main.mainIndexReturned() loop_optimization (before) |
| /// CHECK-DAG: <<Phi:i\d+>> Phi loop:{{B\d+}} outer_loop:none |
| /// CHECK-DAG: Return [<<Phi>>] loop:none |
| // |
| /// CHECK-START: int Main.mainIndexReturned() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: int Main.mainIndexReturned() instruction_simplifier$after_bce (after) |
| /// CHECK-DAG: <<Int:i\d+>> IntConstant 10 loop:none |
| /// CHECK-DAG: Return [<<Int>>] loop:none |
| static int mainIndexReturned() { |
| int i; |
| for (i = 0; i < 10; i++); |
| return i; |
| } |
| |
| /// CHECK-START: int Main.periodicReturned9() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi1>>] loop:none |
| // |
| /// CHECK-START: int Main.periodicReturned9() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: int Main.periodicReturned9() instruction_simplifier$after_bce (after) |
| /// CHECK-DAG: <<Int:i\d+>> IntConstant 1 loop:none |
| /// CHECK-DAG: Return [<<Int>>] loop:none |
| static int periodicReturned9() { |
| int k = 0; |
| for (int i = 0; i < 9; i++) { |
| k = 1 - k; |
| } |
| return k; |
| } |
| |
| /// CHECK-START: int Main.periodicReturned10() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi1>>] loop:none |
| // |
| /// CHECK-START: int Main.periodicReturned10() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: int Main.periodicReturned10() instruction_simplifier$after_bce (after) |
| /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none |
| /// CHECK-DAG: Return [<<Int>>] loop:none |
| static int periodicReturned10() { |
| int k = 0; |
| for (int i = 0; i < 10; i++) { |
| k = 1 - k; |
| } |
| return k; |
| } |
| |
| /// CHECK-START: int Main.getSum21() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi2>>] loop:none |
| // |
| /// CHECK-START: int Main.getSum21() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: int Main.getSum21() instruction_simplifier$after_bce (after) |
| /// CHECK-DAG: <<Int:i\d+>> IntConstant 21 loop:none |
| /// CHECK-DAG: Return [<<Int>>] loop:none |
| private static int getSum21() { |
| int k = 0; |
| int sum = 0; |
| for (int i = 0; i < 6; i++) { |
| k++; |
| sum += k; |
| } |
| return sum; |
| } |
| |
| // Ensure double induction does not "overshoot" the subscript range. |
| private static int getIncr2(int[] arr) { |
| for (int i = 0; i < 12; ) { |
| arr[i++] = 30; |
| arr[i++] = 29; |
| } |
| int sum = 0; |
| for (int i = 0; i < 12; i++) { |
| sum += arr[i]; |
| } |
| return sum; |
| } |
| |
| // TODO: handle as closed/empty eventually? |
| static int mainIndexReturnedN(int n) { |
| int i; |
| for (i = 0; i < n; i++); |
| return i; |
| } |
| |
| // TODO: handle as closed/empty eventually? |
| static int mainIndexShort1(short s) { |
| int i = 0; |
| for (i = 0; i < s; i++) { } |
| return i; |
| } |
| |
| // TODO: handle as closed/empty eventually? |
| static int mainIndexShort2(short s) { |
| int i = 0; |
| for (i = 0; s > i; i++) { } |
| return i; |
| } |
| |
| /// CHECK-START: int Main.periodicReturnedN(int) loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi1>>] loop:none |
| // |
| /// CHECK-START: int Main.periodicReturnedN(int) loop_optimization (after) |
| /// CHECK-NOT: Phi |
| static int periodicReturnedN(int n) { |
| int k = 0; |
| for (int i = 0; i < n; i++) { |
| k = 1 - k; |
| } |
| return k; |
| } |
| |
| // If ever replaced by closed form, last value should be correct! |
| private static int getSumN(int n) { |
| int k = 0; |
| int sum = 0; |
| for (int i = 0; i < n; i++) { |
| k++; |
| sum += k; |
| } |
| return sum; |
| } |
| |
| // If ever replaced by closed form, last value should be correct! |
| private static int closedTwice() { |
| int closed = 0; |
| for (int i = 0; i < 10; i++) { |
| closed++; |
| } |
| // Closed form of first loop defines trip count of second loop. |
| int other_closed = 0; |
| for (int i = 0; i < closed; i++) { |
| other_closed++; |
| } |
| return other_closed; |
| } |
| |
| /// CHECK-START: int Main.closedFeed() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop1>> outer_loop:none |
| /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop2:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop2>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi4>>] loop:none |
| /// CHECK-EVAL: "<<Loop1>>" != "<<Loop2>>" |
| // |
| /// CHECK-START: int Main.closedFeed() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: int Main.closedFeed() instruction_simplifier$after_bce (after) |
| /// CHECK-DAG: <<Int:i\d+>> IntConstant 20 loop:none |
| /// CHECK-DAG: Return [<<Int>>] loop:none |
| private static int closedFeed() { |
| int closed = 0; |
| for (int i = 0; i < 10; i++) { |
| closed++; |
| } |
| // Closed form of first loop feeds into initial value of second loop, |
| // used when generating closed form for the latter. |
| for (int i = 0; i < 10; i++) { |
| closed++; |
| } |
| return closed; |
| } |
| |
| /// CHECK-START: int Main.closedLargeUp() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi1>>] loop:none |
| // |
| /// CHECK-START: int Main.closedLargeUp() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: int Main.closedLargeUp() instruction_simplifier$after_bce (after) |
| /// CHECK-DAG: <<Int:i\d+>> IntConstant -10 loop:none |
| /// CHECK-DAG: Return [<<Int>>] loop:none |
| private static int closedLargeUp() { |
| int closed = 0; |
| for (int i = 0; i < 10; i++) { |
| closed += 0x7fffffff; |
| } |
| return closed; |
| } |
| |
| /// CHECK-START: int Main.closedLargeDown() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi1>>] loop:none |
| // |
| /// CHECK-START: int Main.closedLargeDown() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: int Main.closedLargeDown() instruction_simplifier$after_bce (after) |
| /// CHECK-DAG: <<Int:i\d+>> IntConstant 10 loop:none |
| /// CHECK-DAG: Return [<<Int>>] loop:none |
| private static int closedLargeDown() { |
| int closed = 0; |
| for (int i = 0; i < 10; i++) { |
| closed -= 0x7fffffff; |
| } |
| return closed; |
| } |
| |
| /// CHECK-START: int Main.waterFall() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop1:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop2:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi3:i\d+>> Phi loop:<<Loop3:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi4:i\d+>> Phi loop:<<Loop4:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi5:i\d+>> Phi loop:<<Loop5:B\d+>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi5>>] loop:none |
| // |
| /// CHECK-START: int Main.waterFall() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: int Main.waterFall() instruction_simplifier$after_bce (after) |
| /// CHECK-DAG: <<Int:i\d+>> IntConstant 50 loop:none |
| /// CHECK-DAG: Return [<<Int>>] loop:none |
| private static int waterFall() { |
| int i = 0; |
| for (; i < 10; i++); |
| for (; i < 20; i++); |
| for (; i < 30; i++); |
| for (; i < 40; i++); |
| for (; i < 50; i++); |
| return i; // this should become just 50 |
| } |
| |
| /// CHECK-START: boolean Main.periodicBoolIdiom1() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi2>>] loop:none |
| // |
| /// CHECK-START: boolean Main.periodicBoolIdiom1() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: boolean Main.periodicBoolIdiom1() instruction_simplifier$after_bce (after) |
| /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none |
| /// CHECK-DAG: Return [<<Int>>] loop:none |
| private static boolean periodicBoolIdiom1() { |
| boolean x = true; |
| for (int i = 0; i < 7; i++) { |
| x = !x; |
| } |
| return x; |
| } |
| |
| /// CHECK-START: boolean Main.periodicBoolIdiom2() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi2>>] loop:none |
| // |
| /// CHECK-START: boolean Main.periodicBoolIdiom2() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: boolean Main.periodicBoolIdiom2() instruction_simplifier$after_bce (after) |
| /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none |
| /// CHECK-DAG: Return [<<Int>>] loop:none |
| private static boolean periodicBoolIdiom2() { |
| boolean x = true; |
| for (int i = 0; i < 7; i++) { |
| x = (x != true); |
| } |
| return x; |
| } |
| |
| /// CHECK-START: boolean Main.periodicBoolIdiom3() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi2>>] loop:none |
| // |
| /// CHECK-START: boolean Main.periodicBoolIdiom3() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: boolean Main.periodicBoolIdiom3() instruction_simplifier$after_bce (after) |
| /// CHECK-DAG: <<Int:i\d+>> IntConstant 0 loop:none |
| /// CHECK-DAG: Return [<<Int>>] loop:none |
| private static boolean periodicBoolIdiom3() { |
| boolean x = true; |
| for (int i = 0; i < 7; i++) { |
| x = (x == false); |
| } |
| return x; |
| } |
| |
| /// CHECK-START: boolean Main.periodicBoolIdiom1N(boolean, int) loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi1>>] loop:none |
| // |
| /// CHECK-START: boolean Main.periodicBoolIdiom1N(boolean, int) loop_optimization (after) |
| /// CHECK-NOT: Phi |
| private static boolean periodicBoolIdiom1N(boolean x, int n) { |
| for (int i = 0; i < n; i++) { |
| x = !x; |
| } |
| return x; |
| } |
| |
| /// CHECK-START: boolean Main.periodicBoolIdiom2N(boolean, int) loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi1>>] loop:none |
| // |
| /// CHECK-START: boolean Main.periodicBoolIdiom2N(boolean, int) loop_optimization (after) |
| /// CHECK-NOT: Phi |
| private static boolean periodicBoolIdiom2N(boolean x, int n) { |
| for (int i = 0; i < n; i++) { |
| x = (x != true); |
| } |
| return x; |
| } |
| |
| /// CHECK-START: boolean Main.periodicBoolIdiom3N(boolean, int) loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:i\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi1>>] loop:none |
| // |
| /// CHECK-START: boolean Main.periodicBoolIdiom3N(boolean, int) loop_optimization (after) |
| /// CHECK-NOT: Phi |
| private static boolean periodicBoolIdiom3N(boolean x, int n) { |
| for (int i = 0; i < n; i++) { |
| x = (x == false); |
| } |
| return x; |
| } |
| |
| /// CHECK-START: float Main.periodicFloat10() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:f\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: <<Phi3:f\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: <<Phi4:f\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi2>>] loop:none |
| // |
| /// CHECK-START: float Main.periodicFloat10() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: float Main.periodicFloat10() loop_optimization (after) |
| /// CHECK-DAG: <<Float:f\d+>> FloatConstant 2 loop:none |
| /// CHECK-DAG: Return [<<Float>>] loop:none |
| private static float periodicFloat10() { |
| float r = 4.5f; |
| float s = 2.0f; |
| float t = -1.0f; |
| for (int i = 0; i < 10; i++) { |
| float tmp = t; t = r; r = s; s = tmp; |
| } |
| return r; |
| } |
| |
| /// CHECK-START: float Main.periodicFloat11() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:f\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: <<Phi3:f\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: <<Phi4:f\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi2>>] loop:none |
| // |
| /// CHECK-START: float Main.periodicFloat11() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: float Main.periodicFloat11() loop_optimization (after) |
| /// CHECK-DAG: <<Float:f\d+>> FloatConstant -1 loop:none |
| /// CHECK-DAG: Return [<<Float>>] loop:none |
| private static float periodicFloat11() { |
| float r = 4.5f; |
| float s = 2.0f; |
| float t = -1.0f; |
| for (int i = 0; i < 11; i++) { |
| float tmp = t; t = r; r = s; s = tmp; |
| } |
| return r; |
| } |
| |
| /// CHECK-START: float Main.periodicFloat12() loop_optimization (before) |
| /// CHECK-DAG: <<Phi1:i\d+>> Phi loop:<<Loop:B\d+>> outer_loop:none |
| /// CHECK-DAG: <<Phi2:f\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: <<Phi3:f\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: <<Phi4:f\d+>> Phi loop:<<Loop>> outer_loop:none |
| /// CHECK-DAG: Return [<<Phi2>>] loop:none |
| // |
| /// CHECK-START: float Main.periodicFloat12() loop_optimization (after) |
| /// CHECK-NOT: Phi |
| // |
| /// CHECK-START: float Main.periodicFloat12() loop_optimization (after) |
| /// CHECK-DAG: <<Float:f\d+>> FloatConstant 4.5 loop:none |
| /// CHECK-DAG: Return [<<Float>>] loop:none |
| private static float periodicFloat12() { |
| float r = 4.5f; |
| float s = 2.0f; |
| float t = -1.0f; |
| for (int i = 0; i < 12; i++) { |
| float tmp = t; t = r; r = s; s = tmp; |
| } |
| return r; |
| } |
| |
| private static int exceptionExitBeforeAdd() { |
| int k = 0; |
| try { |
| for (int i = 0; i < 10; i++) { |
| a[i] = 0; |
| k += 10; // increment last |
| } |
| } catch(Exception e) { |
| // Flag error by returning current |
| // value of k negated. |
| return -k-1; |
| } |
| return k; |
| } |
| |
| private static int exceptionExitAfterAdd() { |
| int k = 0; |
| try { |
| for (int i = 0; i < 10; i++) { |
| k += 10; // increment first |
| a[i] = 0; |
| } |
| } catch(Exception e) { |
| // Flag error by returning current |
| // value of k negated. |
| return -k-1; |
| } |
| return k; |
| } |
| |
| public static void main(String[] args) { |
| deadSingleLoop(); |
| deadSingleLoopN(4); |
| potentialInfiniteLoop(4); |
| deadNestedLoops(); |
| deadNestedAndFollowingLoops(); |
| deadConditional(4); |
| deadConditionalCycle(4); |
| |
| deadInduction(); |
| for (int i = 0; i < a.length; i++) { |
| expectEquals(1, a[i]); |
| } |
| deadManyInduction(); |
| for (int i = 0; i < a.length; i++) { |
| expectEquals(2, a[i]); |
| } |
| deadSequence(); |
| for (int i = 0; i < a.length; i++) { |
| expectEquals(3, a[i]); |
| } |
| try { |
| deadCycleWithException(-1); |
| throw new Error("Expected: IOOB exception"); |
| } catch (IndexOutOfBoundsException e) { |
| } |
| for (int i = 0; i < a.length; i++) { |
| expectEquals(i == 0 ? 4 : 3, a[i]); |
| } |
| deadCycleWithException(0); |
| for (int i = 0; i < a.length; i++) { |
| expectEquals(4, a[i]); |
| } |
| |
| expectEquals(12395, closedFormInductionUp()); |
| expectEquals(12295, closedFormInductionInAndDown(12345)); |
| expectEquals(81, closedFormInductionTrivialIf()); |
| expectEquals(10 * 10, closedFormNested()); |
| expectEquals(12345 + 17 * 23 * 7, closedFormNestedAlt()); |
| for (int n = -4; n < 10; n++) { |
| int tc = (n <= 0) ? 0 : n; |
| expectEquals(12345 + tc * 5, closedFormInductionUpN(n)); |
| expectEquals(12345 - tc * 5, closedFormInductionInAndDownN(12345, n)); |
| expectEquals(tc * 10, closedFormNestedN(n)); |
| expectEquals(12345 + tc * 23 * 7, closedFormNestedNAlt(n)); |
| expectEquals(tc * (tc + 1), closedFormNestedMN(n, n + 1)); |
| expectEquals(12345 + tc * (tc + 1) * 7, closedFormNestedMNAlt(n, n + 1)); |
| } |
| |
| expectEquals(10, mainIndexReturned()); |
| expectEquals(1, periodicReturned9()); |
| expectEquals(0, periodicReturned10()); |
| expectEquals(21, getSum21()); |
| expectEquals(354, getIncr2(new int[12])); |
| for (int n = -4; n < 4; n++) { |
| int tc = (n <= 0) ? 0 : n; |
| expectEquals(tc, mainIndexReturnedN(n)); |
| expectEquals(tc, mainIndexShort1((short) n)); |
| expectEquals(tc, mainIndexShort2((short) n)); |
| expectEquals(tc & 1, periodicReturnedN(n)); |
| expectEquals((tc * (tc + 1)) / 2, getSumN(n)); |
| } |
| |
| expectEquals(10, closedTwice()); |
| expectEquals(20, closedFeed()); |
| expectEquals(-10, closedLargeUp()); |
| expectEquals(10, closedLargeDown()); |
| expectEquals(50, waterFall()); |
| |
| expectEquals(false, periodicBoolIdiom1()); |
| expectEquals(false, periodicBoolIdiom2()); |
| expectEquals(false, periodicBoolIdiom3()); |
| for (int n = -4; n < 10; n++) { |
| int tc = (n <= 0) ? 0 : n; |
| boolean even = (tc & 1) == 0; |
| expectEquals(even, periodicBoolIdiom1N(true, n)); |
| expectEquals(!even, periodicBoolIdiom1N(false, n)); |
| expectEquals(even, periodicBoolIdiom2N(true, n)); |
| expectEquals(!even, periodicBoolIdiom2N(false, n)); |
| expectEquals(even, periodicBoolIdiom3N(true, n)); |
| expectEquals(!even, periodicBoolIdiom3N(false, n)); |
| } |
| |
| expectEquals( 2.0f, periodicFloat10()); |
| expectEquals(-1.0f, periodicFloat11()); |
| expectEquals( 4.5f, periodicFloat12()); |
| |
| expectEquals(100, exceptionExitBeforeAdd()); |
| expectEquals(100, exceptionExitAfterAdd()); |
| a = null; |
| expectEquals(-1, exceptionExitBeforeAdd()); |
| expectEquals(-11, exceptionExitAfterAdd()); |
| a = new int[4]; |
| expectEquals(-41, exceptionExitBeforeAdd()); |
| expectEquals(-51, exceptionExitAfterAdd()); |
| |
| System.out.println("passed"); |
| } |
| |
| private static void expectEquals(float expected, float result) { |
| if (expected != result) { |
| throw new Error("Expected: " + expected + ", found: " + result); |
| } |
| } |
| |
| private static void expectEquals(int expected, int result) { |
| if (expected != result) { |
| throw new Error("Expected: " + expected + ", found: " + result); |
| } |
| } |
| |
| private static void expectEquals(boolean expected, boolean result) { |
| if (expected != result) { |
| throw new Error("Expected: " + expected + ", found: " + result); |
| } |
| } |
| } |
