1 /*
2 * Copyright (C) 2017 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 "graph_checker.h"
18 #include "nodes.h"
19 #include "optimizing_unit_test.h"
20 #include "superblock_cloner.h"
21
22 #include "gtest/gtest.h"
23
24 namespace art {
25
26 using HBasicBlockMap = SuperblockCloner::HBasicBlockMap;
27 using HInstructionMap = SuperblockCloner::HInstructionMap;
28
29 // This class provides methods and helpers for testing various cloning and copying routines:
30 // individual instruction cloning and cloning of the more coarse-grain structures.
31 class SuperblockClonerTest : public OptimizingUnitTest {
32 public:
SuperblockClonerTest()33 SuperblockClonerTest()
34 : graph_(CreateGraph()), entry_block_(nullptr), exit_block_(nullptr), parameter_(nullptr) {}
35
CreateBasicLoopControlFlow(HBasicBlock ** header_p,HBasicBlock ** body_p)36 void CreateBasicLoopControlFlow(/* out */ HBasicBlock** header_p,
37 /* out */ HBasicBlock** body_p) {
38 entry_block_ = new (GetAllocator()) HBasicBlock(graph_);
39 graph_->AddBlock(entry_block_);
40 graph_->SetEntryBlock(entry_block_);
41
42 HBasicBlock* loop_preheader = new (GetAllocator()) HBasicBlock(graph_);
43 HBasicBlock* loop_header = new (GetAllocator()) HBasicBlock(graph_);
44 HBasicBlock* loop_body = new (GetAllocator()) HBasicBlock(graph_);
45 HBasicBlock* loop_exit = new (GetAllocator()) HBasicBlock(graph_);
46
47 graph_->AddBlock(loop_preheader);
48 graph_->AddBlock(loop_header);
49 graph_->AddBlock(loop_body);
50 graph_->AddBlock(loop_exit);
51
52 exit_block_ = new (GetAllocator()) HBasicBlock(graph_);
53 graph_->AddBlock(exit_block_);
54 graph_->SetExitBlock(exit_block_);
55
56 entry_block_->AddSuccessor(loop_preheader);
57 loop_preheader->AddSuccessor(loop_header);
58 // Loop exit first to have a proper exit condition/target for HIf.
59 loop_header->AddSuccessor(loop_exit);
60 loop_header->AddSuccessor(loop_body);
61 loop_body->AddSuccessor(loop_header);
62 loop_exit->AddSuccessor(exit_block_);
63
64 *header_p = loop_header;
65 *body_p = loop_body;
66
67 parameter_ = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
68 dex::TypeIndex(0),
69 0,
70 DataType::Type::kInt32);
71 entry_block_->AddInstruction(parameter_);
72 loop_exit->AddInstruction(new (GetAllocator()) HReturnVoid());
73 exit_block_->AddInstruction(new (GetAllocator()) HExit());
74 }
75
CreateBasicLoopDataFlow(HBasicBlock * loop_header,HBasicBlock * loop_body)76 void CreateBasicLoopDataFlow(HBasicBlock* loop_header, HBasicBlock* loop_body) {
77 uint32_t dex_pc = 0;
78
79 // Entry block.
80 HIntConstant* const_0 = graph_->GetIntConstant(0);
81 HIntConstant* const_1 = graph_->GetIntConstant(1);
82 HIntConstant* const_128 = graph_->GetIntConstant(128);
83
84 // Header block.
85 HPhi* phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
86 HInstruction* suspend_check = new (GetAllocator()) HSuspendCheck();
87
88 loop_header->AddPhi(phi);
89 loop_header->AddInstruction(suspend_check);
90 loop_header->AddInstruction(new (GetAllocator()) HGreaterThanOrEqual(phi, const_128));
91 loop_header->AddInstruction(new (GetAllocator()) HIf(parameter_));
92
93 // Loop body block.
94 HInstruction* null_check = new (GetAllocator()) HNullCheck(parameter_, dex_pc);
95 HInstruction* array_length = new (GetAllocator()) HArrayLength(null_check, dex_pc);
96 HInstruction* bounds_check = new (GetAllocator()) HBoundsCheck(phi, array_length, dex_pc);
97 HInstruction* array_get =
98 new (GetAllocator()) HArrayGet(null_check, bounds_check, DataType::Type::kInt32, dex_pc);
99 HInstruction* add = new (GetAllocator()) HAdd(DataType::Type::kInt32, array_get, const_1);
100 HInstruction* array_set =
101 new (GetAllocator()) HArraySet(null_check, bounds_check, add, DataType::Type::kInt32, dex_pc);
102 HInstruction* induction_inc = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi, const_1);
103
104 loop_body->AddInstruction(null_check);
105 loop_body->AddInstruction(array_length);
106 loop_body->AddInstruction(bounds_check);
107 loop_body->AddInstruction(array_get);
108 loop_body->AddInstruction(add);
109 loop_body->AddInstruction(array_set);
110 loop_body->AddInstruction(induction_inc);
111 loop_body->AddInstruction(new (GetAllocator()) HGoto());
112
113 phi->AddInput(const_0);
114 phi->AddInput(induction_inc);
115
116 graph_->SetHasBoundsChecks(true);
117
118 // Adjust HEnvironment for each instruction which require that.
119 ArenaVector<HInstruction*> current_locals({phi, const_128, parameter_},
120 GetAllocator()->Adapter(kArenaAllocInstruction));
121
122 HEnvironment* env = ManuallyBuildEnvFor(suspend_check, ¤t_locals);
123 null_check->CopyEnvironmentFrom(env);
124 bounds_check->CopyEnvironmentFrom(env);
125 }
126
ManuallyBuildEnvFor(HInstruction * instruction,ArenaVector<HInstruction * > * current_locals)127 HEnvironment* ManuallyBuildEnvFor(HInstruction* instruction,
128 ArenaVector<HInstruction*>* current_locals) {
129 HEnvironment* environment = new (GetAllocator()) HEnvironment(
130 (GetAllocator()),
131 current_locals->size(),
132 graph_->GetArtMethod(),
133 instruction->GetDexPc(),
134 instruction);
135
136 environment->CopyFrom(ArrayRef<HInstruction* const>(*current_locals));
137 instruction->SetRawEnvironment(environment);
138 return environment;
139 }
140
CheckGraph()141 bool CheckGraph() {
142 GraphChecker checker(graph_);
143 checker.Run();
144 if (!checker.IsValid()) {
145 for (const std::string& error : checker.GetErrors()) {
146 std::cout << error << std::endl;
147 }
148 return false;
149 }
150 return true;
151 }
152
153 HGraph* graph_;
154
155 HBasicBlock* entry_block_;
156 HBasicBlock* exit_block_;
157
158 HInstruction* parameter_;
159 };
160
TEST_F(SuperblockClonerTest,IndividualInstrCloner)161 TEST_F(SuperblockClonerTest, IndividualInstrCloner) {
162 HBasicBlock* header = nullptr;
163 HBasicBlock* loop_body = nullptr;
164
165 CreateBasicLoopControlFlow(&header, &loop_body);
166 CreateBasicLoopDataFlow(header, loop_body);
167 graph_->BuildDominatorTree();
168 ASSERT_TRUE(CheckGraph());
169
170 HSuspendCheck* old_suspend_check = header->GetLoopInformation()->GetSuspendCheck();
171 CloneAndReplaceInstructionVisitor visitor(graph_);
172 // Do instruction cloning and replacement twice with different visiting order.
173
174 visitor.VisitInsertionOrder();
175 size_t instr_replaced_by_clones_count = visitor.GetInstrReplacedByClonesCount();
176 EXPECT_EQ(instr_replaced_by_clones_count, 12u);
177 EXPECT_TRUE(CheckGraph());
178
179 visitor.VisitReversePostOrder();
180 instr_replaced_by_clones_count = visitor.GetInstrReplacedByClonesCount();
181 EXPECT_EQ(instr_replaced_by_clones_count, 24u);
182 EXPECT_TRUE(CheckGraph());
183
184 HSuspendCheck* new_suspend_check = header->GetLoopInformation()->GetSuspendCheck();
185 EXPECT_NE(new_suspend_check, old_suspend_check);
186 EXPECT_NE(new_suspend_check, nullptr);
187 }
188
189 // Tests SuperblockCloner::CloneBasicBlocks - check instruction cloning and initial remapping of
190 // instructions' inputs.
TEST_F(SuperblockClonerTest,CloneBasicBlocks)191 TEST_F(SuperblockClonerTest, CloneBasicBlocks) {
192 HBasicBlock* header = nullptr;
193 HBasicBlock* loop_body = nullptr;
194 ArenaAllocator* arena = graph_->GetAllocator();
195
196 CreateBasicLoopControlFlow(&header, &loop_body);
197 CreateBasicLoopDataFlow(header, loop_body);
198 graph_->BuildDominatorTree();
199 ASSERT_TRUE(CheckGraph());
200
201 ArenaBitVector orig_bb_set(
202 arena, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner);
203 HBasicBlockMap bb_map(std::less<HBasicBlock*>(), arena->Adapter(kArenaAllocSuperblockCloner));
204 HInstructionMap hir_map(std::less<HInstruction*>(), arena->Adapter(kArenaAllocSuperblockCloner));
205
206 HLoopInformation* loop_info = header->GetLoopInformation();
207 orig_bb_set.Union(&loop_info->GetBlocks());
208
209 SuperblockCloner cloner(graph_,
210 &orig_bb_set,
211 &bb_map,
212 &hir_map);
213 EXPECT_TRUE(cloner.IsSubgraphClonable());
214
215 cloner.CloneBasicBlocks();
216
217 EXPECT_EQ(bb_map.size(), 2u);
218 EXPECT_EQ(hir_map.size(), 12u);
219
220 for (auto it : hir_map) {
221 HInstruction* orig_instr = it.first;
222 HInstruction* copy_instr = it.second;
223
224 EXPECT_EQ(cloner.GetBlockCopy(orig_instr->GetBlock()), copy_instr->GetBlock());
225 EXPECT_EQ(orig_instr->GetKind(), copy_instr->GetKind());
226 EXPECT_EQ(orig_instr->GetType(), copy_instr->GetType());
227
228 if (orig_instr->IsPhi()) {
229 continue;
230 }
231
232 EXPECT_EQ(orig_instr->InputCount(), copy_instr->InputCount());
233
234 // Check that inputs match.
235 for (size_t i = 0, e = orig_instr->InputCount(); i < e; i++) {
236 HInstruction* orig_input = orig_instr->InputAt(i);
237 HInstruction* copy_input = copy_instr->InputAt(i);
238 if (cloner.IsInOrigBBSet(orig_input->GetBlock())) {
239 EXPECT_EQ(cloner.GetInstrCopy(orig_input), copy_input);
240 } else {
241 EXPECT_EQ(orig_input, copy_input);
242 }
243 }
244
245 EXPECT_EQ(orig_instr->HasEnvironment(), copy_instr->HasEnvironment());
246
247 // Check that environments match.
248 if (orig_instr->HasEnvironment()) {
249 HEnvironment* orig_env = orig_instr->GetEnvironment();
250 HEnvironment* copy_env = copy_instr->GetEnvironment();
251
252 EXPECT_EQ(copy_env->GetParent(), nullptr);
253 EXPECT_EQ(orig_env->Size(), copy_env->Size());
254
255 for (size_t i = 0, e = orig_env->Size(); i < e; i++) {
256 HInstruction* orig_input = orig_env->GetInstructionAt(i);
257 HInstruction* copy_input = copy_env->GetInstructionAt(i);
258 if (cloner.IsInOrigBBSet(orig_input->GetBlock())) {
259 EXPECT_EQ(cloner.GetInstrCopy(orig_input), copy_input);
260 } else {
261 EXPECT_EQ(orig_input, copy_input);
262 }
263 }
264 }
265 }
266 }
267
268 // SuperblockCloner::CleanUpControlFlow - checks algorithms of local adjustments of the control
269 // flow.
TEST_F(SuperblockClonerTest,AdjustControlFlowInfo)270 TEST_F(SuperblockClonerTest, AdjustControlFlowInfo) {
271 HBasicBlock* header = nullptr;
272 HBasicBlock* loop_body = nullptr;
273 ArenaAllocator* arena = graph_->GetAllocator();
274
275 CreateBasicLoopControlFlow(&header, &loop_body);
276 CreateBasicLoopDataFlow(header, loop_body);
277 graph_->BuildDominatorTree();
278 ASSERT_TRUE(CheckGraph());
279
280 ArenaBitVector orig_bb_set(
281 arena, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner);
282
283 HLoopInformation* loop_info = header->GetLoopInformation();
284 orig_bb_set.Union(&loop_info->GetBlocks());
285
286 SuperblockCloner cloner(graph_,
287 &orig_bb_set,
288 nullptr,
289 nullptr);
290 EXPECT_TRUE(cloner.IsSubgraphClonable());
291
292 cloner.FindAndSetLocalAreaForAdjustments();
293 cloner.CleanUpControlFlow();
294
295 EXPECT_TRUE(CheckGraph());
296
297 EXPECT_TRUE(entry_block_->Dominates(header));
298 EXPECT_TRUE(entry_block_->Dominates(exit_block_));
299
300 EXPECT_EQ(header->GetLoopInformation(), loop_info);
301 EXPECT_EQ(loop_info->GetHeader(), header);
302 EXPECT_TRUE(loop_info->Contains(*loop_body));
303 EXPECT_TRUE(loop_info->IsBackEdge(*loop_body));
304 }
305
306 } // namespace art
307