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 "arch/x86/instruction_set_features_x86.h"
18 #include "code_generator_x86.h"
19 #include "dead_code_elimination.h"
20 #include "driver/compiler_options.h"
21 #include "graph_checker.h"
22 #include "optimizing_unit_test.h"
23 #include "pretty_printer.h"
24
25 #include "gtest/gtest.h"
26
27 namespace art {
28
TestCode(const uint16_t * data,const std::string & expected_before,const std::string & expected_after)29 static void TestCode(const uint16_t* data,
30 const std::string& expected_before,
31 const std::string& expected_after) {
32 ArenaPool pool;
33 ArenaAllocator allocator(&pool);
34 HGraph* graph = CreateCFG(&allocator, data);
35 ASSERT_NE(graph, nullptr);
36
37 graph->TryBuildingSsa();
38
39 StringPrettyPrinter printer_before(graph);
40 printer_before.VisitInsertionOrder();
41 std::string actual_before = printer_before.str();
42 ASSERT_EQ(actual_before, expected_before);
43
44 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
45 X86InstructionSetFeatures::FromCppDefines());
46 x86::CodeGeneratorX86 codegenX86(graph, *features_x86.get(), CompilerOptions());
47 HDeadCodeElimination(graph).Run();
48 SSAChecker ssa_checker(&allocator, graph);
49 ssa_checker.Run();
50 ASSERT_TRUE(ssa_checker.IsValid());
51
52 StringPrettyPrinter printer_after(graph);
53 printer_after.VisitInsertionOrder();
54 std::string actual_after = printer_after.str();
55 ASSERT_EQ(actual_after, expected_after);
56 }
57
58
59 /**
60 * Small three-register program.
61 *
62 * 16-bit
63 * offset
64 * ------
65 * v1 <- 1 0. const/4 v1, #+1
66 * v0 <- 0 1. const/4 v0, #+0
67 * if v1 >= 0 goto L1 2. if-gez v1, +3
68 * v0 <- v1 4. move v0, v1
69 * L1: v2 <- v0 + v1 5. add-int v2, v0, v1
70 * return-void 7. return
71 */
TEST(DeadCodeElimination,AdditionAndConditionalJump)72 TEST(DeadCodeElimination, AdditionAndConditionalJump) {
73 const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
74 Instruction::CONST_4 | 1 << 8 | 1 << 12,
75 Instruction::CONST_4 | 0 << 8 | 0 << 12,
76 Instruction::IF_GEZ | 1 << 8, 3,
77 Instruction::MOVE | 0 << 8 | 1 << 12,
78 Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
79 Instruction::RETURN_VOID);
80
81 std::string expected_before =
82 "BasicBlock 0, succ: 1\n"
83 " 3: IntConstant [15, 22, 8]\n"
84 " 5: IntConstant [22, 8]\n"
85 " 19: SuspendCheck\n"
86 " 20: Goto 1\n"
87 "BasicBlock 1, pred: 0, succ: 5, 2\n"
88 " 8: GreaterThanOrEqual(3, 5) [9]\n"
89 " 9: If(8)\n"
90 "BasicBlock 2, pred: 1, succ: 3\n"
91 " 12: Goto 3\n"
92 "BasicBlock 3, pred: 5, 2, succ: 4\n"
93 " 22: Phi(5, 3) [15]\n"
94 " 15: Add(22, 3)\n"
95 " 17: ReturnVoid\n"
96 "BasicBlock 4, pred: 3\n"
97 " 18: Exit\n"
98 "BasicBlock 5, pred: 1, succ: 3\n"
99 " 21: Goto 3\n";
100
101 // Expected difference after dead code elimination.
102 diff_t expected_diff = {
103 { " 3: IntConstant [15, 22, 8]\n", " 3: IntConstant [22, 8]\n" },
104 { " 22: Phi(5, 3) [15]\n", " 22: Phi(5, 3)\n" },
105 { " 15: Add(22, 3)\n", removed }
106 };
107 std::string expected_after = Patch(expected_before, expected_diff);
108
109 TestCode(data, expected_before, expected_after);
110 }
111
112 /**
113 * Three-register program with jumps leading to the creation of many
114 * blocks.
115 *
116 * The intent of this test is to ensure that all dead instructions are
117 * actually pruned at compile-time, thanks to the (backward)
118 * post-order traversal of the the dominator tree.
119 *
120 * 16-bit
121 * offset
122 * ------
123 * v0 <- 0 0. const/4 v0, #+0
124 * v1 <- 1 1. const/4 v1, #+1
125 * v2 <- v0 + v1 2. add-int v2, v0, v1
126 * goto L2 4. goto +4
127 * L1: v1 <- v0 + 3 5. add-int/lit16 v1, v0, #+3
128 * goto L3 7. goto +4
129 * L2: v0 <- v2 + 2 8. add-int/lit16 v0, v2, #+2
130 * goto L1 10. goto +(-5)
131 * L3: v2 <- v1 + 4 11. add-int/lit16 v2, v1, #+4
132 * return 13. return-void
133 */
TEST(DeadCodeElimination,AdditionsAndInconditionalJumps)134 TEST(DeadCodeElimination, AdditionsAndInconditionalJumps) {
135 const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
136 Instruction::CONST_4 | 0 << 8 | 0 << 12,
137 Instruction::CONST_4 | 1 << 8 | 1 << 12,
138 Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
139 Instruction::GOTO | 4 << 8,
140 Instruction::ADD_INT_LIT16 | 1 << 8 | 0 << 12, 3,
141 Instruction::GOTO | 4 << 8,
142 Instruction::ADD_INT_LIT16 | 0 << 8 | 2 << 12, 2,
143 static_cast<uint16_t>(Instruction::GOTO | -5 << 8),
144 Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 4,
145 Instruction::RETURN_VOID);
146
147 std::string expected_before =
148 "BasicBlock 0, succ: 1\n"
149 " 3: IntConstant [9]\n"
150 " 5: IntConstant [9]\n"
151 " 13: IntConstant [14]\n"
152 " 18: IntConstant [19]\n"
153 " 24: IntConstant [25]\n"
154 " 29: SuspendCheck\n"
155 " 30: Goto 1\n"
156 "BasicBlock 1, pred: 0, succ: 3\n"
157 " 9: Add(3, 5) [19]\n"
158 " 11: Goto 3\n"
159 "BasicBlock 2, pred: 3, succ: 4\n"
160 " 14: Add(19, 13) [25]\n"
161 " 16: Goto 4\n"
162 "BasicBlock 3, pred: 1, succ: 2\n"
163 " 19: Add(9, 18) [14]\n"
164 " 21: SuspendCheck\n"
165 " 22: Goto 2\n"
166 "BasicBlock 4, pred: 2, succ: 5\n"
167 " 25: Add(14, 24)\n"
168 " 27: ReturnVoid\n"
169 "BasicBlock 5, pred: 4\n"
170 " 28: Exit\n";
171
172 // The SuspendCheck instruction following this Add instruction
173 // inserts the latter in an environment, thus making it "used" and
174 // therefore non removable. It ensures that some other Add and
175 // IntConstant instructions cannot be removed, as they are direct
176 // or indirect inputs of the initial Add instruction.
177 std::string expected_after =
178 "BasicBlock 0, succ: 1\n"
179 " 3: IntConstant [9]\n"
180 " 5: IntConstant [9]\n"
181 " 18: IntConstant [19]\n"
182 " 29: SuspendCheck\n"
183 " 30: Goto 1\n"
184 "BasicBlock 1, pred: 0, succ: 5\n"
185 " 9: Add(3, 5) [19]\n"
186 " 19: Add(9, 18) []\n"
187 " 21: SuspendCheck\n"
188 " 27: ReturnVoid\n"
189 "BasicBlock 5, pred: 1\n"
190 " 28: Exit\n";
191
192 TestCode(data, expected_before, expected_after);
193 }
194
195 } // namespace art
196