summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
author Chris Jones <christopher.jones@linaro.org> 2022-07-21 23:37:18 +0100
committer Treehugger Robot <treehugger-gerrit@google.com> 2022-11-23 12:38:39 +0000
commit5fa73a95fcfc638c155511305382ecbe4b75fe43 (patch)
tree53b2ba341671e53d0b32d75bb61da16056283538
parent009ed7b44b535107facd4a59705e7db7aeeff357 (diff)
ART: Add two extra DCE passes
Add two DCE passes to eliminate dead instructions left by: - Loop optimization unrolling. After loop optimization, dead instructions are often left that, when removed can simplify the structure of the loop and remove basic blocks. This extra DCE pass creates an opportunity for the load store elimination pass to remove some loads/stores. - The last instruction simplification pass. Authors: Hari Limaye, Chris Jones Test: 458-checker-instruct-simplification Test: 530-checker-lse, 530-checker-lse-simd, 706-checker-scheduler Test: test-art-target, test-art-host Change-Id: I6e14cbfc3c320af5f507135a067bb7b5bc4df8f4
-rw-r--r--compiler/optimizing/optimizing_compiler.cc12
-rw-r--r--test/458-checker-instruct-simplification/src/Main.java45
-rw-r--r--test/530-checker-lse-simd/src/Main.java2
-rw-r--r--test/530-checker-lse/src/Main.java58
-rw-r--r--test/706-checker-scheduler/src/Main.java62
5 files changed, 134 insertions, 45 deletions
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index f394635ede..7cb4b29c87 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -670,17 +670,25 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph,
"constant_folding$after_bce"),
OptDef(OptimizationPass::kAggressiveInstructionSimplifier,
"instruction_simplifier$after_bce"),
+ OptDef(OptimizationPass::kDeadCodeElimination,
+ "dead_code_elimination$after_bce"),
// Other high-level optimizations.
OptDef(OptimizationPass::kLoadStoreElimination),
- OptDef(OptimizationPass::kCHAGuardOptimization),
OptDef(OptimizationPass::kDeadCodeElimination,
- "dead_code_elimination$after_bce"),
+ "dead_code_elimination$after_lse",
+ OptimizationPass::kLoadStoreElimination),
+ OptDef(OptimizationPass::kCHAGuardOptimization),
OptDef(OptimizationPass::kCodeSinking),
// The codegen has a few assumptions that only the instruction simplifier
// can satisfy. For example, the code generator does not expect to see a
// HTypeConversion from a type to the same type.
OptDef(OptimizationPass::kAggressiveInstructionSimplifier,
"instruction_simplifier$before_codegen"),
+ // Simplification may result in dead code that should be removed prior to
+ // code generation.
+ OptDef(OptimizationPass::kDeadCodeElimination,
+ "dead_code_elimination$before_codegen",
+ OptimizationPass::kAggressiveInstructionSimplifier),
// Eliminate constructor fences after code sinking to avoid
// complicated sinking logic to split a fence with many inputs.
OptDef(OptimizationPass::kConstructorFenceRedundancyElimination)
diff --git a/test/458-checker-instruct-simplification/src/Main.java b/test/458-checker-instruct-simplification/src/Main.java
index 22b6dfed54..8ab059dcbe 100644
--- a/test/458-checker-instruct-simplification/src/Main.java
+++ b/test/458-checker-instruct-simplification/src/Main.java
@@ -2751,6 +2751,49 @@ public class Main {
return (byte) ((value & mask) >> 8);
}
+ /// CHECK-START: int Main.$noinline$deadAddAfterUnrollingAndSimplification(int[]) dead_code_elimination$before_codegen (before)
+ /// CHECK-DAG: <<Param:l\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const1:i\d+>> IntConstant 1 loop:none
+ /// CHECK-DAG: <<Const2:i\d+>> IntConstant 2 loop:none
+ /// CHECK-DAG: <<IndexPhi:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none
+ // Induction variable:
+ /// CHECK-DAG: Add [<<IndexPhi>>,<<Const2>>] loop:<<Loop>> outer_loop:none
+ // Array Element Addition:
+ /// CHECK-DAG: <<Store1:i\d+>> Add [{{i\d+}},<<Const1>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: <<Store2:i\d+>> Add [{{i\d+}},<<Const2>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet [<<Param>>,<<Const0>>,<<Store2>>] loop:<<Loop>> outer_loop:none
+
+ /// CHECK-START: int Main.$noinline$deadAddAfterUnrollingAndSimplification(int[]) dead_code_elimination$before_codegen (before)
+ /// CHECK: Add
+ /// CHECK: Add
+ /// CHECK: Add
+ /// CHECK: Add
+ /// CHECK-NOT: Add
+
+ /// CHECK-START: int Main.$noinline$deadAddAfterUnrollingAndSimplification(int[]) dead_code_elimination$before_codegen (after)
+ /// CHECK-DAG: <<Param:l\d+>> ParameterValue loop:none
+ /// CHECK-DAG: <<Const0:i\d+>> IntConstant 0 loop:none
+ /// CHECK-DAG: <<Const2:i\d+>> IntConstant 2 loop:none
+ /// CHECK-DAG: <<IndexPhi:i\d+>> Phi [<<Const0>>,{{i\d+}}] loop:<<Loop:B\d+>> outer_loop:none
+ // Induction variable:
+ /// CHECK-DAG: Add [<<IndexPhi>>,<<Const2>>] loop:<<Loop>> outer_loop:none
+ // Array Element Addition:
+ /// CHECK-DAG: <<Store:i\d+>> Add [{{i\d+}},<<Const2>>] loop:<<Loop>> outer_loop:none
+ /// CHECK-DAG: ArraySet [<<Param>>,<<Const0>>,<<Store>>] loop:<<Loop>> outer_loop:none
+
+ /// CHECK-START: int Main.$noinline$deadAddAfterUnrollingAndSimplification(int[]) dead_code_elimination$before_codegen (after)
+ /// CHECK: Add
+ /// CHECK: Add
+ /// CHECK-NOT: Add
+ public static int $noinline$deadAddAfterUnrollingAndSimplification(int[] array) {
+ for (int i = 0; i < 50; ++i) {
+ // Array access prevents transformation to closed-form expression
+ array[0]++;
+ }
+ return array[0];
+ }
+
public static void main(String[] args) throws Exception {
Class smaliTests2 = Class.forName("SmaliTests2");
Method $noinline$XorAllOnes = smaliTests2.getMethod("$noinline$XorAllOnes", int.class);
@@ -3058,6 +3101,8 @@ public class Main {
assertIntEquals(-1, $noinline$redundantAndIntToByteShortAndConstant(0x7fffff45));
assertIntEquals(-1, $noinline$redundantAndIntToByteShortAndConstant(0xffffff45));
assertIntEquals(111, $noinline$redundantAndRegressionNotConstant(-1, 0x6f45));
+
+ assertIntEquals(50, $noinline$deadAddAfterUnrollingAndSimplification(new int[] { 0 }));
}
private static boolean $inline$true() { return true; }
diff --git a/test/530-checker-lse-simd/src/Main.java b/test/530-checker-lse-simd/src/Main.java
index d6049d0bd0..619ac281b3 100644
--- a/test/530-checker-lse-simd/src/Main.java
+++ b/test/530-checker-lse-simd/src/Main.java
@@ -231,7 +231,6 @@ public class Main {
/// CHECK: BoundsCheck loop:none
/// CHECK: ArrayGet
/// CHECK: Add
- /// CHECK: ArrayLength
//
/// CHECK: VecLoad loop:{{B\d+}}
/// CHECK: VecStore
@@ -244,7 +243,6 @@ public class Main {
/// CHECK-START-ARM64: double[] Main.$noinline$test06(int) load_store_elimination (after)
/// CHECK: BoundsCheck loop:none
/// CHECK: Add
- /// CHECK: ArrayLength
//
/// CHECK: VecLoad loop:{{B\d+}}
/// CHECK: VecAdd
diff --git a/test/530-checker-lse/src/Main.java b/test/530-checker-lse/src/Main.java
index 1a3708b6ac..875444941d 100644
--- a/test/530-checker-lse/src/Main.java
+++ b/test/530-checker-lse/src/Main.java
@@ -551,16 +551,15 @@ public class Main {
}
/// CHECK-START: void Main.test21(TestClass) load_store_elimination (before)
- /// CHECK: NewInstance
- /// CHECK: InstanceFieldSet
- /// CHECK: InstanceFieldSet
- /// CHECK: InstanceFieldSet
- /// CHECK: InstanceFieldGet
- /// CHECK: InstanceFieldGet
+ /// CHECK-DAG: NewInstance
+ /// CHECK-DAG: InstanceFieldSet
+ /// CHECK-DAG: InstanceFieldSet
+ /// CHECK-DAG: InstanceFieldSet
+ /// CHECK-DAG: InstanceFieldGet
+ /// CHECK-DAG: InstanceFieldGet
/// CHECK-START: void Main.test21(TestClass) load_store_elimination (after)
/// CHECK-DAG: InstanceFieldSet
- /// CHECK-DAG: Phi
/// CHECK-START: void Main.test21(TestClass) load_store_elimination (after)
/// CHECK-NOT: NewInstance
@@ -1850,14 +1849,22 @@ public class Main {
/// CHECK: ArraySet
/// CHECK: ArrayGet
- /// CHECK-START: int Main.testAllocationEliminationOfArray2() load_store_elimination (after)
+ /// CHECK-START-{ARM64,X86,X86_64}: int Main.testAllocationEliminationOfArray2() load_store_elimination (after)
+ /// CHECK-NOT: NewArray
+ /// CHECK-NOT: ArraySet
+ /// CHECK-NOT: ArraySet
+ /// CHECK-NOT: ArrayGet
+
+ // The loop optimization doesn't happen in ARM which leads to LSE not being able to optimize this
+ // case.
+ /// CHECK-START-ARM: int Main.testAllocationEliminationOfArray2() load_store_elimination (after)
/// CHECK: NewArray
/// CHECK: ArraySet
/// CHECK: ArraySet
/// CHECK: ArrayGet
private static int testAllocationEliminationOfArray2() {
- // Cannot eliminate array allocation since array is accessed with non-constant
- // index (only 3 elements to prevent vectorization of the reduction).
+ // Array can be eliminated because LSE can reduce the array accesses into
+ // integer constants.
int[] array = new int[3];
array[1] = 4;
array[2] = 7;
@@ -1921,6 +1928,36 @@ public class Main {
return array[1];
}
+ /// CHECK-START: int Main.testAllocationEliminationOfArray6(boolean) load_store_elimination (before)
+ /// CHECK: NewArray
+ /// CHECK: ArraySet
+ /// CHECK: ArraySet
+ /// CHECK: ArrayGet
+
+ /// CHECK-START: int Main.testAllocationEliminationOfArray6(boolean) load_store_elimination (after)
+ /// CHECK: NewArray
+ /// CHECK: ArraySet
+ /// CHECK: ArraySet
+ /// CHECK: ArrayGet
+ private static int testAllocationEliminationOfArray6(boolean prevent_loop_opt) {
+ // Cannot eliminate array allocation since array is accessed with non-constant
+ // index (only 3 elements to prevent vectorization of the reduction).
+ int[] array = new int[3];
+ array[1] = 4;
+ array[2] = 7;
+ int sum = 0;
+ for (int e : array) {
+ sum += e;
+
+ // Prevent the loop from being optimized away before LSE. This should
+ // never be false.
+ if (!prevent_loop_opt) {
+ return -1;
+ }
+ }
+ return sum;
+ }
+
/// CHECK-START: int Main.testExitMerge(boolean) load_store_elimination (before)
/// CHECK-DAG: NewInstance
/// CHECK-DAG: InstanceFieldSet field_name:TestClass.i
@@ -4210,6 +4247,7 @@ public class Main {
} catch (NegativeArraySizeException e) {
System.out.println("Got NegativeArraySizeException.");
}
+ assertIntEquals(testAllocationEliminationOfArray6(true), 11);
assertIntEquals(testStoreStore().i, 41);
assertIntEquals(testStoreStore().j, 43);
diff --git a/test/706-checker-scheduler/src/Main.java b/test/706-checker-scheduler/src/Main.java
index 1b8377d95e..255599de3e 100644
--- a/test/706-checker-scheduler/src/Main.java
+++ b/test/706-checker-scheduler/src/Main.java
@@ -66,23 +66,23 @@ public class Main {
}
/// CHECK-START-ARM: void Main.arrayAccessVariable(int) scheduler (before)
- /// CHECK: <<Param:i\d+>> ParameterValue
+ /// CHECK-DAG: <<Param:i\d+>> ParameterValue
/// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
/// CHECK-DAG: <<Const2:i\d+>> IntConstant 2
/// CHECK-DAG: <<Const3:i\d+>> IntConstant -1
- /// CHECK: <<Add1:i\d+>> Add [<<Param>>,<<Const1>>]
- /// CHECK: <<Add2:i\d+>> Add [<<Param>>,<<Const2>>]
- /// CHECK: <<Add3:i\d+>> Add [<<Param>>,<<Const3>>]
- /// CHECK: <<Array:i\d+>> IntermediateAddress
- /// CHECK: <<ArrayGet1:i\d+>> ArrayGet [<<Array>>,<<Add1>>]
- /// CHECK: <<AddArray1:i\d+>> Add [<<ArrayGet1>>,<<Const1>>]
- /// CHECK: <<ArraySet1:v\d+>> ArraySet [<<Array>>,<<Add1>>,<<AddArray1>>]
- /// CHECK: <<ArrayGet2:i\d+>> ArrayGet [<<Array>>,<<Add2>>]
- /// CHECK: <<AddArray2:i\d+>> Add [<<ArrayGet2>>,<<Const1>>]
- /// CHECK: <<ArraySet2:v\d+>> ArraySet [<<Array>>,<<Add2>>,<<AddArray2>>]
- /// CHECK: <<ArrayGet3:i\d+>> ArrayGet [<<Array>>,<<Add3>>]
- /// CHECK: <<AddArray3:i\d+>> Add [<<ArrayGet3>>,<<Const1>>]
- /// CHECK: <<ArraySet3:v\d+>> ArraySet [<<Array>>,<<Add3>>,<<AddArray3>>]
+ /// CHECK-DAG: <<Add1:i\d+>> Add [<<Param>>,<<Const1>>]
+ /// CHECK-DAG: <<Add2:i\d+>> Add [<<Param>>,<<Const2>>]
+ /// CHECK-DAG: <<Add3:i\d+>> Add [<<Param>>,<<Const3>>]
+ /// CHECK-DAG: <<Array:i\d+>> IntermediateAddress
+ /// CHECK-DAG: <<ArrayGet1:i\d+>> ArrayGet [<<Array>>,<<Add1>>]
+ /// CHECK-DAG: <<ArrayGet2:i\d+>> ArrayGet [<<Array>>,<<Add2>>]
+ /// CHECK-DAG: <<ArrayGet3:i\d+>> ArrayGet [<<Array>>,<<Add3>>]
+ /// CHECK-DAG: <<AddArray1:i\d+>> Add [<<ArrayGet1>>,<<Const2>>]
+ /// CHECK-DAG: {{v\d+}} ArraySet [<<Array>>,<<Add1>>,<<AddArray1>>]
+ /// CHECK-DAG: <<AddArray2:i\d+>> Add [<<ArrayGet2>>,<<Const2>>]
+ /// CHECK-DAG: {{v\d+}} ArraySet [<<Array>>,<<Add2>>,<<AddArray2>>]
+ /// CHECK-DAG: <<AddArray3:i\d+>> Add [<<ArrayGet3>>,<<Const2>>]
+ /// CHECK-DAG: {{v\d+}} ArraySet [<<Array>>,<<Add3>>,<<AddArray3>>]
/// CHECK-START-ARM: void Main.arrayAccessVariable(int) scheduler (after)
/// CHECK: <<Param:i\d+>> ParameterValue
@@ -104,23 +104,23 @@ public class Main {
/// CHECK: ArraySet
/// CHECK-START-ARM64: void Main.arrayAccessVariable(int) scheduler (before)
- /// CHECK: <<Param:i\d+>> ParameterValue
+ /// CHECK-DAG: <<Param:i\d+>> ParameterValue
/// CHECK-DAG: <<Const1:i\d+>> IntConstant 1
/// CHECK-DAG: <<Const2:i\d+>> IntConstant 2
/// CHECK-DAG: <<Const3:i\d+>> IntConstant -1
- /// CHECK: <<Add1:i\d+>> Add [<<Param>>,<<Const1>>]
- /// CHECK: <<Add2:i\d+>> Add [<<Param>>,<<Const2>>]
- /// CHECK: <<Add3:i\d+>> Add [<<Param>>,<<Const3>>]
- /// CHECK: <<Array:i\d+>> IntermediateAddress
- /// CHECK: <<ArrayGet1:i\d+>> ArrayGet [<<Array>>,<<Add1>>]
- /// CHECK: <<AddArray1:i\d+>> Add [<<ArrayGet1>>,<<Const1>>]
- /// CHECK: <<ArraySet1:v\d+>> ArraySet [<<Array>>,<<Add1>>,<<AddArray1>>]
- /// CHECK: <<ArrayGet2:i\d+>> ArrayGet [<<Array>>,<<Add2>>]
- /// CHECK: <<AddArray2:i\d+>> Add [<<ArrayGet2>>,<<Const1>>]
- /// CHECK: <<ArraySet2:v\d+>> ArraySet [<<Array>>,<<Add2>>,<<AddArray2>>]
- /// CHECK: <<ArrayGet3:i\d+>> ArrayGet [<<Array>>,<<Add3>>]
- /// CHECK: <<AddArray3:i\d+>> Add [<<ArrayGet3>>,<<Const1>>]
- /// CHECK: <<ArraySet3:v\d+>> ArraySet [<<Array>>,<<Add3>>,<<AddArray3>>]
+ /// CHECK-DAG: <<Add1:i\d+>> Add [<<Param>>,<<Const1>>]
+ /// CHECK-DAG: <<Add2:i\d+>> Add [<<Param>>,<<Const2>>]
+ /// CHECK-DAG: <<Add3:i\d+>> Add [<<Param>>,<<Const3>>]
+ /// CHECK-DAG: <<Array:i\d+>> IntermediateAddress
+ /// CHECK-DAG: <<ArrayGet1:i\d+>> ArrayGet [<<Array>>,<<Add1>>]
+ /// CHECK-DAG: <<ArrayGet2:i\d+>> ArrayGet [<<Array>>,<<Add2>>]
+ /// CHECK-DAG: <<ArrayGet3:i\d+>> ArrayGet [<<Array>>,<<Add3>>]
+ /// CHECK-DAG: <<AddArray1:i\d+>> Add [<<ArrayGet1>>,<<Const2>>]
+ /// CHECK-DAG: {{v\d+}} ArraySet [<<Array>>,<<Add1>>,<<AddArray1>>]
+ /// CHECK-DAG: <<AddArray2:i\d+>> Add [<<ArrayGet2>>,<<Const2>>]
+ /// CHECK-DAG: {{v\d+}} ArraySet [<<Array>>,<<Add2>>,<<AddArray2>>]
+ /// CHECK-DAG: <<AddArray3:i\d+>> Add [<<ArrayGet3>>,<<Const2>>]
+ /// CHECK-DAG: ArraySet [<<Array>>,<<Add3>>,<<AddArray3>>]
/// CHECK-START-ARM64: void Main.arrayAccessVariable(int) scheduler (after)
/// CHECK: <<Param:i\d+>> ParameterValue
@@ -131,9 +131,9 @@ public class Main {
/// CHECK: <<Add2:i\d+>> Add [<<Param>>,<<Const2>>]
/// CHECK: <<Add3:i\d+>> Add [<<Param>>,<<Const3>>]
/// CHECK: <<Array:i\d+>> IntermediateAddress
- /// CHECK: ArrayGet [<<Array>>,{{i\d+}}]
- /// CHECK: ArrayGet [<<Array>>,{{i\d+}}]
- /// CHECK: ArrayGet [<<Array>>,{{i\d+}}]
+ /// CHECK: ArrayGet [<<Array>>,<<Add3>>]
+ /// CHECK: ArrayGet [<<Array>>,<<Add2>>]
+ /// CHECK: ArrayGet [<<Array>>,<<Add1>>]
/// CHECK: Add
/// CHECK: Add
/// CHECK: Add