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