diff options
author | 2022-07-21 23:37:18 +0100 | |
---|---|---|
committer | 2022-11-23 12:38:39 +0000 | |
commit | 5fa73a95fcfc638c155511305382ecbe4b75fe43 (patch) | |
tree | 53b2ba341671e53d0b32d75bb61da16056283538 | |
parent | 009ed7b44b535107facd4a59705e7db7aeeff357 (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.cc | 12 | ||||
-rw-r--r-- | test/458-checker-instruct-simplification/src/Main.java | 45 | ||||
-rw-r--r-- | test/530-checker-lse-simd/src/Main.java | 2 | ||||
-rw-r--r-- | test/530-checker-lse/src/Main.java | 58 | ||||
-rw-r--r-- | test/706-checker-scheduler/src/Main.java | 62 |
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 |