1 /*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "dead_code_elimination.h"
18
19 #include "driver/compiler_options.h"
20 #include "graph_checker.h"
21 #include "optimizing_unit_test.h"
22 #include "pretty_printer.h"
23
24 #include "gtest/gtest.h"
25
26 namespace art {
27
28 class DeadCodeEliminationTest : public OptimizingUnitTest {
29 protected:
30 void TestCode(const std::vector<uint16_t>& data,
31 const std::string& expected_before,
32 const std::string& expected_after);
33 };
34
TestCode(const std::vector<uint16_t> & data,const std::string & expected_before,const std::string & expected_after)35 void DeadCodeEliminationTest::TestCode(const std::vector<uint16_t>& data,
36 const std::string& expected_before,
37 const std::string& expected_after) {
38 HGraph* graph = CreateCFG(data);
39 ASSERT_NE(graph, nullptr);
40
41 StringPrettyPrinter printer_before(graph);
42 printer_before.VisitInsertionOrder();
43 std::string actual_before = printer_before.str();
44 ASSERT_EQ(actual_before, expected_before);
45
46 HDeadCodeElimination(graph, /* stats= */ nullptr, "dead_code_elimination").Run();
47 GraphChecker graph_checker(graph);
48 graph_checker.Run();
49 ASSERT_TRUE(graph_checker.IsValid());
50
51 StringPrettyPrinter printer_after(graph);
52 printer_after.VisitInsertionOrder();
53 std::string actual_after = printer_after.str();
54 ASSERT_EQ(actual_after, expected_after);
55 }
56
57 /**
58 * Small three-register program.
59 *
60 * 16-bit
61 * offset
62 * ------
63 * v1 <- 1 0. const/4 v1, #+1
64 * v0 <- 0 1. const/4 v0, #+0
65 * if v1 >= 0 goto L1 2. if-gez v1, +3
66 * v0 <- v1 4. move v0, v1
67 * L1: v2 <- v0 + v1 5. add-int v2, v0, v1
68 * return-void 7. return
69 */
TEST_F(DeadCodeEliminationTest,AdditionAndConditionalJump)70 TEST_F(DeadCodeEliminationTest, AdditionAndConditionalJump) {
71 const std::vector<uint16_t> data = THREE_REGISTERS_CODE_ITEM(
72 Instruction::CONST_4 | 1 << 8 | 1 << 12,
73 Instruction::CONST_4 | 0 << 8 | 0 << 12,
74 Instruction::IF_GEZ | 1 << 8, 3,
75 Instruction::MOVE | 0 << 8 | 1 << 12,
76 Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
77 Instruction::RETURN_VOID);
78
79 std::string expected_before =
80 "BasicBlock 0, succ: 1\n"
81 " 3: IntConstant [9, 8, 5]\n"
82 " 4: IntConstant [8, 5]\n"
83 " 1: SuspendCheck\n"
84 " 2: Goto 1\n"
85 "BasicBlock 1, pred: 0, succ: 5, 2\n"
86 " 5: GreaterThanOrEqual(3, 4) [6]\n"
87 " 6: If(5)\n"
88 "BasicBlock 2, pred: 1, succ: 3\n"
89 " 7: Goto 3\n"
90 "BasicBlock 3, pred: 5, 2, succ: 4\n"
91 " 8: Phi(4, 3) [9]\n"
92 " 9: Add(8, 3)\n"
93 " 10: ReturnVoid\n"
94 "BasicBlock 4, pred: 3\n"
95 " 11: Exit\n"
96 "BasicBlock 5, pred: 1, succ: 3\n"
97 " 0: Goto 3\n";
98
99 // Expected difference after dead code elimination.
100 diff_t expected_diff = {
101 { " 3: IntConstant [9, 8, 5]\n", " 3: IntConstant [8, 5]\n" },
102 { " 8: Phi(4, 3) [9]\n", " 8: Phi(4, 3)\n" },
103 { " 9: Add(8, 3)\n", removed }
104 };
105 std::string expected_after = Patch(expected_before, expected_diff);
106
107 TestCode(data, expected_before, expected_after);
108 }
109
110 /**
111 * Three-register program with jumps leading to the creation of many
112 * blocks.
113 *
114 * The intent of this test is to ensure that all dead instructions are
115 * actually pruned at compile-time, thanks to the (backward)
116 * post-order traversal of the the dominator tree.
117 *
118 * 16-bit
119 * offset
120 * ------
121 * v0 <- 0 0. const/4 v0, #+0
122 * v1 <- 1 1. const/4 v1, #+1
123 * v2 <- v0 + v1 2. add-int v2, v0, v1
124 * goto L2 4. goto +4
125 * L1: v1 <- v0 + 3 5. add-int/lit16 v1, v0, #+3
126 * goto L3 7. goto +4
127 * L2: v0 <- v2 + 2 8. add-int/lit16 v0, v2, #+2
128 * goto L1 10. goto +(-5)
129 * L3: v2 <- v1 + 4 11. add-int/lit16 v2, v1, #+4
130 * return 13. return-void
131 */
TEST_F(DeadCodeEliminationTest,AdditionsAndInconditionalJumps)132 TEST_F(DeadCodeEliminationTest, AdditionsAndInconditionalJumps) {
133 const std::vector<uint16_t> data = THREE_REGISTERS_CODE_ITEM(
134 Instruction::CONST_4 | 0 << 8 | 0 << 12,
135 Instruction::CONST_4 | 1 << 8 | 1 << 12,
136 Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
137 Instruction::GOTO | 4 << 8,
138 Instruction::ADD_INT_LIT16 | 1 << 8 | 0 << 12, 3,
139 Instruction::GOTO | 4 << 8,
140 Instruction::ADD_INT_LIT16 | 0 << 8 | 2 << 12, 2,
141 static_cast<uint16_t>(Instruction::GOTO | 0xFFFFFFFB << 8),
142 Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 4,
143 Instruction::RETURN_VOID);
144
145 std::string expected_before =
146 "BasicBlock 0, succ: 1\n"
147 " 2: IntConstant [4]\n"
148 " 3: IntConstant [4]\n"
149 " 6: IntConstant [7]\n"
150 " 9: IntConstant [10]\n"
151 " 12: IntConstant [13]\n"
152 " 0: SuspendCheck\n"
153 " 1: Goto 1\n"
154 "BasicBlock 1, pred: 0, succ: 3\n"
155 " 4: Add(2, 3) [7]\n"
156 " 5: Goto 3\n"
157 "BasicBlock 2, pred: 3, succ: 4\n"
158 " 10: Add(7, 9) [13]\n"
159 " 11: Goto 4\n"
160 "BasicBlock 3, pred: 1, succ: 2\n"
161 " 7: Add(4, 6) [10]\n"
162 " 8: Goto 2\n"
163 "BasicBlock 4, pred: 2, succ: 5\n"
164 " 13: Add(10, 12)\n"
165 " 14: ReturnVoid\n"
166 "BasicBlock 5, pred: 4\n"
167 " 15: Exit\n";
168
169 std::string expected_after =
170 "BasicBlock 0, succ: 1\n"
171 " 0: SuspendCheck\n"
172 " 1: Goto 1\n"
173 "BasicBlock 1, pred: 0, succ: 5\n"
174 " 14: ReturnVoid\n"
175 "BasicBlock 5, pred: 1\n"
176 " 15: Exit\n";
177
178 TestCode(data, expected_before, expected_after);
179 }
180
181 } // namespace art
182