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 "base/macros.h"
18 #include "graph_checker.h"
19 #include "nodes.h"
20 #include "optimizing_unit_test.h"
21 #include "superblock_cloner.h"
22
23 #include "gtest/gtest.h"
24
25 namespace art HIDDEN {
26
27 using HBasicBlockMap = SuperblockCloner::HBasicBlockMap;
28 using HInstructionMap = SuperblockCloner::HInstructionMap;
29 using HBasicBlockSet = SuperblockCloner::HBasicBlockSet;
30 using HEdgeSet = SuperblockCloner::HEdgeSet;
31
32 // This class provides methods and helpers for testing various cloning and copying routines:
33 // individual instruction cloning and cloning of the more coarse-grain structures.
34 class SuperblockClonerTest : public OptimizingUnitTest {
35 protected:
InitGraphAndParameters()36 HBasicBlock* InitGraphAndParameters() {
37 HBasicBlock* return_block = InitEntryMainExitGraphWithReturnVoid();
38 param_ = MakeParam(DataType::Type::kInt32);
39 return return_block;
40 }
41
CreateBasicLoopDataFlow(HBasicBlock * loop_header,HBasicBlock * loop_body)42 void CreateBasicLoopDataFlow(HBasicBlock* loop_header, HBasicBlock* loop_body) {
43 uint32_t dex_pc = 0;
44
45 // Entry block.
46 HIntConstant* const_0 = graph_->GetIntConstant(0);
47 HIntConstant* const_1 = graph_->GetIntConstant(1);
48 HIntConstant* const_128 = graph_->GetIntConstant(128);
49
50 // Header block.
51 auto [phi, induction_inc] = MakeLinearLoopVar(loop_header, loop_body, const_0, const_1);
52 std::initializer_list<HInstruction*> common_env{phi, const_128, param_};
53 HInstruction* suspend_check = MakeSuspendCheck(loop_header, common_env);
54 HInstruction* loop_check = MakeCondition(loop_header, kCondGE, phi, const_128);
55 MakeIf(loop_header, loop_check);
56
57 // Loop body block.
58 HInstruction* null_check = MakeNullCheck(loop_body, param_, common_env, dex_pc);
59 HInstruction* array_length = MakeArrayLength(loop_body, null_check, dex_pc);
60 HInstruction* bounds_check = MakeBoundsCheck(loop_body, phi, array_length, common_env, dex_pc);
61 HInstruction* array_get =
62 MakeArrayGet(loop_body, null_check, bounds_check, DataType::Type::kInt32, dex_pc);
63 HInstruction* add = MakeBinOp<HAdd>(loop_body, DataType::Type::kInt32, array_get, const_1);
64 HInstruction* array_set =
65 MakeArraySet(loop_body, null_check, bounds_check, add, DataType::Type::kInt32, dex_pc);
66
67 graph_->SetHasBoundsChecks(true);
68 }
69
70 HParameterValue* param_ = nullptr;
71 };
72
TEST_F(SuperblockClonerTest,IndividualInstrCloner)73 TEST_F(SuperblockClonerTest, IndividualInstrCloner) {
74 HBasicBlock* return_block = InitGraphAndParameters();
75 auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
76 CreateBasicLoopDataFlow(header, loop_body);
77 graph_->BuildDominatorTree();
78 EXPECT_TRUE(CheckGraph());
79
80 HSuspendCheck* old_suspend_check = header->GetLoopInformation()->GetSuspendCheck();
81 CloneAndReplaceInstructionVisitor visitor(graph_);
82 // Do instruction cloning and replacement twice with different visiting order.
83
84 visitor.VisitInsertionOrder();
85 size_t instr_replaced_by_clones_count = visitor.GetInstrReplacedByClonesCount();
86 EXPECT_EQ(instr_replaced_by_clones_count, 14u);
87 EXPECT_TRUE(CheckGraph());
88
89 visitor.VisitReversePostOrder();
90 instr_replaced_by_clones_count = visitor.GetInstrReplacedByClonesCount();
91 EXPECT_EQ(instr_replaced_by_clones_count, 28u);
92 EXPECT_TRUE(CheckGraph());
93
94 HSuspendCheck* new_suspend_check = header->GetLoopInformation()->GetSuspendCheck();
95 EXPECT_NE(new_suspend_check, old_suspend_check);
96 EXPECT_NE(new_suspend_check, nullptr);
97 }
98
99 // Tests SuperblockCloner::CloneBasicBlocks - check instruction cloning and initial remapping of
100 // instructions' inputs.
TEST_F(SuperblockClonerTest,CloneBasicBlocks)101 TEST_F(SuperblockClonerTest, CloneBasicBlocks) {
102 ArenaAllocator* arena = GetAllocator();
103
104 HBasicBlock* return_block = InitGraphAndParameters();
105 auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
106 CreateBasicLoopDataFlow(header, loop_body);
107 graph_->BuildDominatorTree();
108 ASSERT_TRUE(CheckGraph());
109
110 ArenaBitVector orig_bb_set(
111 arena, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner);
112 HBasicBlockMap bb_map(std::less<HBasicBlock*>(), arena->Adapter(kArenaAllocSuperblockCloner));
113 HInstructionMap hir_map(std::less<HInstruction*>(), arena->Adapter(kArenaAllocSuperblockCloner));
114
115 HLoopInformation* loop_info = header->GetLoopInformation();
116 orig_bb_set.Union(&loop_info->GetBlocks());
117
118 SuperblockCloner cloner(graph_,
119 &orig_bb_set,
120 &bb_map,
121 &hir_map,
122 /* induction_range= */ nullptr);
123 EXPECT_TRUE(cloner.IsSubgraphClonable());
124
125 cloner.CloneBasicBlocks();
126
127 EXPECT_EQ(bb_map.size(), 2u);
128 EXPECT_EQ(hir_map.size(), 12u);
129
130 for (auto it : hir_map) {
131 HInstruction* orig_instr = it.first;
132 HInstruction* copy_instr = it.second;
133
134 EXPECT_EQ(cloner.GetBlockCopy(orig_instr->GetBlock()), copy_instr->GetBlock());
135 EXPECT_EQ(orig_instr->GetKind(), copy_instr->GetKind());
136 EXPECT_EQ(orig_instr->GetType(), copy_instr->GetType());
137
138 if (orig_instr->IsPhi()) {
139 continue;
140 }
141
142 EXPECT_EQ(orig_instr->InputCount(), copy_instr->InputCount());
143
144 // Check that inputs match.
145 for (size_t i = 0, e = orig_instr->InputCount(); i < e; i++) {
146 HInstruction* orig_input = orig_instr->InputAt(i);
147 HInstruction* copy_input = copy_instr->InputAt(i);
148 if (cloner.IsInOrigBBSet(orig_input->GetBlock())) {
149 EXPECT_EQ(cloner.GetInstrCopy(orig_input), copy_input);
150 } else {
151 EXPECT_EQ(orig_input, copy_input);
152 }
153 }
154
155 EXPECT_EQ(orig_instr->HasEnvironment(), copy_instr->HasEnvironment());
156
157 // Check that environments match.
158 if (orig_instr->HasEnvironment()) {
159 HEnvironment* orig_env = orig_instr->GetEnvironment();
160 HEnvironment* copy_env = copy_instr->GetEnvironment();
161
162 EXPECT_EQ(copy_env->GetParent(), nullptr);
163 EXPECT_EQ(orig_env->Size(), copy_env->Size());
164
165 for (size_t i = 0, e = orig_env->Size(); i < e; i++) {
166 HInstruction* orig_input = orig_env->GetInstructionAt(i);
167 HInstruction* copy_input = copy_env->GetInstructionAt(i);
168 if (cloner.IsInOrigBBSet(orig_input->GetBlock())) {
169 EXPECT_EQ(cloner.GetInstrCopy(orig_input), copy_input);
170 } else {
171 EXPECT_EQ(orig_input, copy_input);
172 }
173 }
174 }
175 }
176 }
177
178 // SuperblockCloner::CleanUpControlFlow - checks algorithms of local adjustments of the control
179 // flow.
TEST_F(SuperblockClonerTest,AdjustControlFlowInfo)180 TEST_F(SuperblockClonerTest, AdjustControlFlowInfo) {
181 ArenaAllocator* arena = GetAllocator();
182
183 HBasicBlock* return_block = InitGraphAndParameters();
184 auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
185 CreateBasicLoopDataFlow(header, loop_body);
186 graph_->BuildDominatorTree();
187 ASSERT_TRUE(CheckGraph());
188
189 ArenaBitVector orig_bb_set(
190 arena, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner);
191
192 HLoopInformation* loop_info = header->GetLoopInformation();
193 orig_bb_set.Union(&loop_info->GetBlocks());
194
195 SuperblockCloner cloner(graph_,
196 &orig_bb_set,
197 /* bb_map= */ nullptr,
198 /* hir_map= */ nullptr,
199 /* induction_range= */ nullptr);
200 EXPECT_TRUE(cloner.IsSubgraphClonable());
201
202 cloner.FindAndSetLocalAreaForAdjustments();
203 cloner.CleanUpControlFlow();
204
205 EXPECT_TRUE(CheckGraph());
206
207 EXPECT_TRUE(entry_block_->Dominates(header));
208 EXPECT_TRUE(entry_block_->Dominates(exit_block_));
209
210 EXPECT_EQ(header->GetLoopInformation(), loop_info);
211 EXPECT_EQ(loop_info->GetHeader(), header);
212 EXPECT_TRUE(loop_info->Contains(*loop_body));
213 EXPECT_TRUE(loop_info->IsBackEdge(*loop_body));
214 }
215
216 // Tests IsSubgraphConnected function for negative case.
TEST_F(SuperblockClonerTest,IsGraphConnected)217 TEST_F(SuperblockClonerTest, IsGraphConnected) {
218 ArenaAllocator* arena = GetAllocator();
219
220 HBasicBlock* return_block = InitGraphAndParameters();
221 auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
222 CreateBasicLoopDataFlow(header, loop_body);
223 HBasicBlock* unreachable_block = AddNewBlock();
224
225 HBasicBlockSet bb_set(
226 arena, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner);
227 bb_set.SetBit(header->GetBlockId());
228 bb_set.SetBit(loop_body->GetBlockId());
229 bb_set.SetBit(unreachable_block->GetBlockId());
230
231 EXPECT_FALSE(IsSubgraphConnected(&bb_set, graph_));
232 EXPECT_EQ(bb_set.NumSetBits(), 1u);
233 EXPECT_TRUE(bb_set.IsBitSet(unreachable_block->GetBlockId()));
234 }
235
236 // Tests SuperblockCloner for loop peeling case.
237 //
238 // See an ASCII graphics example near LoopClonerHelper::DoPeeling.
TEST_F(SuperblockClonerTest,LoopPeeling)239 TEST_F(SuperblockClonerTest, LoopPeeling) {
240 HBasicBlock* return_block = InitGraphAndParameters();
241 auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
242 CreateBasicLoopDataFlow(header, loop_body);
243 graph_->BuildDominatorTree();
244 EXPECT_TRUE(CheckGraph());
245
246 HBasicBlockMap bb_map(
247 std::less<HBasicBlock*>(), graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
248 HInstructionMap hir_map(
249 std::less<HInstruction*>(), graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
250
251 HLoopInformation* loop_info = header->GetLoopInformation();
252 LoopClonerHelper helper(loop_info, &bb_map, &hir_map, /* induction_range= */ nullptr);
253 EXPECT_TRUE(helper.IsLoopClonable());
254 HBasicBlock* new_header = helper.DoPeeling();
255 HLoopInformation* new_loop_info = new_header->GetLoopInformation();
256
257 EXPECT_TRUE(CheckGraph());
258
259 // Check loop body successors.
260 EXPECT_EQ(loop_body->GetSingleSuccessor(), header);
261 EXPECT_EQ(bb_map.Get(loop_body)->GetSingleSuccessor(), header);
262
263 // Check loop structure.
264 EXPECT_EQ(header, new_header);
265 EXPECT_EQ(new_loop_info->GetHeader(), header);
266 EXPECT_EQ(new_loop_info->GetBackEdges().size(), 1u);
267 EXPECT_EQ(new_loop_info->GetBackEdges()[0], loop_body);
268 }
269
270 // Tests SuperblockCloner for loop unrolling case.
271 //
272 // See an ASCII graphics example near LoopClonerHelper::DoUnrolling.
TEST_F(SuperblockClonerTest,LoopUnrolling)273 TEST_F(SuperblockClonerTest, LoopUnrolling) {
274 HBasicBlock* return_block = InitGraphAndParameters();
275 auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
276 CreateBasicLoopDataFlow(header, loop_body);
277 graph_->BuildDominatorTree();
278 EXPECT_TRUE(CheckGraph());
279
280 HBasicBlockMap bb_map(
281 std::less<HBasicBlock*>(), graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
282 HInstructionMap hir_map(
283 std::less<HInstruction*>(), graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
284
285 HLoopInformation* loop_info = header->GetLoopInformation();
286 LoopClonerHelper helper(loop_info, &bb_map, &hir_map, /* induction_range= */ nullptr);
287 EXPECT_TRUE(helper.IsLoopClonable());
288 HBasicBlock* new_header = helper.DoUnrolling();
289
290 EXPECT_TRUE(CheckGraph());
291
292 // Check loop body successors.
293 EXPECT_EQ(loop_body->GetSingleSuccessor(), bb_map.Get(header));
294 EXPECT_EQ(bb_map.Get(loop_body)->GetSingleSuccessor(), header);
295
296 // Check loop structure.
297 EXPECT_EQ(header, new_header);
298 EXPECT_EQ(loop_info, new_header->GetLoopInformation());
299 EXPECT_EQ(loop_info->GetHeader(), new_header);
300 EXPECT_EQ(loop_info->GetBackEdges().size(), 1u);
301 EXPECT_EQ(loop_info->GetBackEdges()[0], bb_map.Get(loop_body));
302 }
303
304 // Checks that loop unrolling works fine for a loop with multiple back edges. Tests that after
305 // the transformation the loop has a single preheader.
TEST_F(SuperblockClonerTest,LoopPeelingMultipleBackEdges)306 TEST_F(SuperblockClonerTest, LoopPeelingMultipleBackEdges) {
307 HBasicBlock* return_block = InitGraphAndParameters();
308 auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
309 CreateBasicLoopDataFlow(header, loop_body);
310
311 // Transform a basic loop to have multiple back edges.
312 HBasicBlock* latch = header->GetSuccessors()[1];
313 HBasicBlock* if_block = AddNewBlock();
314 HBasicBlock* temp1 = AddNewBlock();
315 header->ReplaceSuccessor(latch, if_block);
316 if_block->AddSuccessor(latch);
317 if_block->AddSuccessor(temp1);
318 temp1->AddSuccessor(header);
319
320 MakeIf(if_block, param_);
321
322 HInstructionIterator it(header->GetPhis());
323 DCHECK(!it.Done());
324 HPhi* loop_phi = it.Current()->AsPhi();
325 HInstruction* temp_add =
326 MakeBinOp<HAdd>(temp1, DataType::Type::kInt32, loop_phi, graph_->GetIntConstant(2));
327 MakeGoto(temp1);
328 loop_phi->AddInput(temp_add);
329
330 graph_->BuildDominatorTree();
331 EXPECT_TRUE(CheckGraph());
332
333 HLoopInformation* loop_info = header->GetLoopInformation();
334 LoopClonerSimpleHelper helper(loop_info, /* induction_range= */ nullptr);
335 HBasicBlock* new_header = helper.DoPeeling();
336 EXPECT_EQ(header, new_header);
337
338 EXPECT_TRUE(CheckGraph());
339 EXPECT_EQ(header->GetPredecessors().size(), 3u);
340 }
341
CheckLoopStructureForLoopPeelingNested(HBasicBlock * loop1_header,HBasicBlock * loop2_header,HBasicBlock * loop3_header)342 static void CheckLoopStructureForLoopPeelingNested(HBasicBlock* loop1_header,
343 HBasicBlock* loop2_header,
344 HBasicBlock* loop3_header) {
345 EXPECT_EQ(loop1_header->GetLoopInformation()->GetHeader(), loop1_header);
346 EXPECT_EQ(loop2_header->GetLoopInformation()->GetHeader(), loop2_header);
347 EXPECT_EQ(loop3_header->GetLoopInformation()->GetHeader(), loop3_header);
348 EXPECT_EQ(loop1_header->GetLoopInformation()->GetPreHeader()->GetLoopInformation(), nullptr);
349 EXPECT_EQ(loop2_header->GetLoopInformation()->GetPreHeader()->GetLoopInformation(), nullptr);
350 EXPECT_EQ(loop3_header->GetLoopInformation()->GetPreHeader()->GetLoopInformation()->GetHeader(),
351 loop2_header);
352 }
353
TEST_F(SuperblockClonerTest,LoopPeelingNested)354 TEST_F(SuperblockClonerTest, LoopPeelingNested) {
355 HBasicBlock* return_block = InitGraphAndParameters();
356
357 // Create the following nested structure of loops
358 // Headers: 1 2 3
359 // [ ], [ [ ] ]
360 auto [preheader1, header1, body1] = CreateWhileLoop(return_block);
361 CreateBasicLoopDataFlow(header1, body1);
362
363 auto [preheader2, header2, body2_end] = CreateWhileLoop(return_block);
364 CreateBasicLoopDataFlow(header2, body2_end);
365
366 auto [preheader3, header3, body3] = CreateWhileLoop(body2_end);
367 CreateBasicLoopDataFlow(header3, body3);
368
369 graph_->BuildDominatorTree();
370 EXPECT_TRUE(CheckGraph());
371
372 HLoopInformation* loop2_info_before = header2->GetLoopInformation();
373 HLoopInformation* loop3_info_before = header3->GetLoopInformation();
374
375 // Check nested loops structure.
376 CheckLoopStructureForLoopPeelingNested(header1, header2, header3);
377 LoopClonerSimpleHelper helper(header1->GetLoopInformation(), /* induction_range= */ nullptr);
378 helper.DoPeeling();
379 // Check that nested loops structure has not changed after the transformation.
380 CheckLoopStructureForLoopPeelingNested(header1, header2, header3);
381
382 // Test that the loop info is preserved.
383 EXPECT_EQ(loop2_info_before, header2->GetLoopInformation());
384 EXPECT_EQ(loop3_info_before, header3->GetLoopInformation());
385
386 EXPECT_EQ(loop3_info_before->GetPreHeader()->GetLoopInformation(), loop2_info_before);
387 EXPECT_EQ(loop2_info_before->GetPreHeader()->GetLoopInformation(), nullptr);
388
389 EXPECT_EQ(helper.GetRegionToBeAdjusted(), nullptr);
390
391 EXPECT_TRUE(CheckGraph());
392 }
393
394 // Checks that the loop population is correctly propagated after an inner loop is peeled.
TEST_F(SuperblockClonerTest,OuterLoopPopulationAfterInnerPeeled)395 TEST_F(SuperblockClonerTest, OuterLoopPopulationAfterInnerPeeled) {
396 HBasicBlock* return_block = InitGraphAndParameters();
397
398 // Create the following nested structure of loops
399 // Headers: 1 2 3 4
400 // [ [ [ ] ] ], [ ]
401 auto [preheader1, header1, body1_end] = CreateWhileLoop(return_block);
402 CreateBasicLoopDataFlow(header1, body1_end);
403
404 auto [preheader2, header2, body2_end] = CreateWhileLoop(body1_end);
405 CreateBasicLoopDataFlow(header2, body2_end);
406
407 auto [preheader3, header3, body3] = CreateWhileLoop(body2_end);
408 CreateBasicLoopDataFlow(header3, body3);
409
410 auto [preheader4, header4, body4] = CreateWhileLoop(return_block);
411 CreateBasicLoopDataFlow(header4, body4);
412
413 graph_->BuildDominatorTree();
414 EXPECT_TRUE(CheckGraph());
415
416 LoopClonerSimpleHelper helper(header3->GetLoopInformation(), /* induction_range= */ nullptr);
417 helper.DoPeeling();
418 HLoopInformation* loop1 = header1->GetLoopInformation();
419 HLoopInformation* loop2 = header2->GetLoopInformation();
420 HLoopInformation* loop3 = header3->GetLoopInformation();
421 HLoopInformation* loop4 = header4->GetLoopInformation();
422
423 EXPECT_TRUE(loop1->Contains(*header2));
424 EXPECT_TRUE(loop1->Contains(*header3));
425 EXPECT_TRUE(loop1->Contains(*header3->GetLoopInformation()->GetPreHeader()));
426
427 // Check that loop4 info has not been touched after local run of AnalyzeLoops.
428 EXPECT_EQ(loop4, header4->GetLoopInformation());
429
430 EXPECT_TRUE(loop1->IsIn(*loop1));
431 EXPECT_TRUE(loop2->IsIn(*loop1));
432 EXPECT_TRUE(loop3->IsIn(*loop1));
433 EXPECT_TRUE(loop3->IsIn(*loop2));
434 EXPECT_TRUE(!loop4->IsIn(*loop1));
435
436 EXPECT_EQ(loop4->GetPreHeader()->GetLoopInformation(), nullptr);
437
438 EXPECT_EQ(helper.GetRegionToBeAdjusted(), loop2);
439
440 EXPECT_TRUE(CheckGraph());
441 }
442
443 // Checks the case when inner loop have an exit not to its immediate outer_loop but some other loop
444 // in the hierarchy. Loop population information must be valid after loop peeling.
TEST_F(SuperblockClonerTest,NestedCaseExitToOutermost)445 TEST_F(SuperblockClonerTest, NestedCaseExitToOutermost) {
446 HBasicBlock* return_block = InitGraphAndParameters();
447
448 // Create the following nested structure of loops then peel loop3.
449 // Headers: 1 2 3
450 // [ [ [ ] ] ]
451 auto [preheader1, header1, body1_end] = CreateWhileLoop(return_block);
452 CreateBasicLoopDataFlow(header1, body1_end);
453
454 auto [preheader2, header2, body2_end] = CreateWhileLoop(body1_end);
455 CreateBasicLoopDataFlow(header2, body2_end);
456
457 auto [preheader3, header3, body3] = CreateWhileLoop(body2_end);
458 CreateBasicLoopDataFlow(header3, body3);
459
460 // Change the loop3 - insert an exit which leads to loop1.
461 HBasicBlock* loop3_extra_if_block = AddNewBlock();
462 MakeIf(loop3_extra_if_block, param_);
463
464 header3->ReplaceSuccessor(body3, loop3_extra_if_block);
465 // Note: After this, both edges to `body1_end` shall be critical edges.
466 loop3_extra_if_block->AddSuccessor(body1_end); // Long exit.
467 loop3_extra_if_block->AddSuccessor(body3);
468
469 graph_->BuildDominatorTree();
470 EXPECT_TRUE(CheckGraph());
471
472 HBasicBlock* loop3_long_exit = loop3_extra_if_block->GetSuccessors()[0];
473 EXPECT_TRUE(header1->GetLoopInformation()->Contains(*loop3_long_exit));
474
475 LoopClonerSimpleHelper helper(header3->GetLoopInformation(), /* induction_range= */ nullptr);
476 helper.DoPeeling();
477
478 HLoopInformation* loop1 = header1->GetLoopInformation();
479 // Check that after the transformation the local area for CF adjustments has been chosen
480 // correctly and loop population has been updated.
481 loop3_long_exit = loop3_extra_if_block->GetSuccessors()[0];
482 EXPECT_TRUE(loop1->Contains(*loop3_long_exit));
483
484 EXPECT_EQ(helper.GetRegionToBeAdjusted(), loop1);
485
486 EXPECT_TRUE(loop1->Contains(*header3));
487 EXPECT_TRUE(loop1->Contains(*header3->GetLoopInformation()->GetPreHeader()));
488
489 EXPECT_TRUE(CheckGraph());
490 }
491
TEST_F(SuperblockClonerTest,FastCaseCheck)492 TEST_F(SuperblockClonerTest, FastCaseCheck) {
493 ArenaAllocator* arena = GetAllocator();
494
495 HBasicBlock* return_block = InitGraphAndParameters();
496 auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
497 CreateBasicLoopDataFlow(header, loop_body);
498 graph_->BuildDominatorTree();
499
500 HLoopInformation* loop_info = header->GetLoopInformation();
501
502 ArenaBitVector orig_bb_set(
503 arena, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner);
504 orig_bb_set.Union(&loop_info->GetBlocks());
505
506 HEdgeSet remap_orig_internal(graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
507 HEdgeSet remap_copy_internal(graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
508 HEdgeSet remap_incoming(graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
509
510 CollectRemappingInfoForPeelUnroll(true,
511 loop_info,
512 &remap_orig_internal,
513 &remap_copy_internal,
514 &remap_incoming);
515
516 // Insert some extra nodes and edges.
517 ASSERT_EQ(preheader, loop_info->GetPreHeader());
518 orig_bb_set.SetBit(preheader->GetBlockId());
519
520 // Adjust incoming edges.
521 remap_incoming.clear();
522 remap_incoming.insert(HEdge(preheader->GetSinglePredecessor(), preheader));
523
524 HBasicBlockMap bb_map(std::less<HBasicBlock*>(), arena->Adapter(kArenaAllocSuperblockCloner));
525 HInstructionMap hir_map(std::less<HInstruction*>(), arena->Adapter(kArenaAllocSuperblockCloner));
526
527 SuperblockCloner cloner(graph_,
528 &orig_bb_set,
529 &bb_map,
530 &hir_map,
531 /* induction_range= */ nullptr);
532 cloner.SetSuccessorRemappingInfo(&remap_orig_internal, &remap_copy_internal, &remap_incoming);
533
534 EXPECT_FALSE(cloner.IsFastCase());
535 }
536
537 // Helper for FindCommonLoop which also check that FindCommonLoop is symmetric.
FindCommonLoopCheck(HLoopInformation * loop1,HLoopInformation * loop2)538 static HLoopInformation* FindCommonLoopCheck(HLoopInformation* loop1, HLoopInformation* loop2) {
539 HLoopInformation* common_loop12 = FindCommonLoop(loop1, loop2);
540 HLoopInformation* common_loop21 = FindCommonLoop(loop2, loop1);
541 EXPECT_EQ(common_loop21, common_loop12);
542 return common_loop12;
543 }
544
545 // Tests FindCommonLoop function on a loop nest.
TEST_F(SuperblockClonerTest,FindCommonLoop)546 TEST_F(SuperblockClonerTest, FindCommonLoop) {
547 HBasicBlock* header = nullptr;
548 HBasicBlock* loop_body = nullptr;
549
550 HBasicBlock* return_block = InitGraphAndParameters();
551
552 // Create the following nested structure of loops
553 // Headers: 1 2 3 4 5
554 // [ [ [ ] ], [ ] ], [ ]
555 auto [preheader1, header1, body1_end] = CreateWhileLoop(return_block);
556 CreateBasicLoopDataFlow(header1, body1_end);
557
558 auto [preheader2, header2, body2_end] = CreateWhileLoop(body1_end);
559 CreateBasicLoopDataFlow(header2, body2_end);
560
561 auto [preheader3, header3, body3] = CreateWhileLoop(body2_end);
562 CreateBasicLoopDataFlow(header3, body3);
563
564 auto [preheader4, header4, body4] = CreateWhileLoop(body1_end);
565 CreateBasicLoopDataFlow(header4, body4);
566
567 auto [preheader5, header5, body5] = CreateWhileLoop(return_block);
568 CreateBasicLoopDataFlow(header5, body5);
569
570 graph_->BuildDominatorTree();
571 EXPECT_TRUE(CheckGraph());
572
573 HLoopInformation* loop1 = header1->GetLoopInformation();
574 HLoopInformation* loop2 = header2->GetLoopInformation();
575 HLoopInformation* loop3 = header3->GetLoopInformation();
576 HLoopInformation* loop4 = header4->GetLoopInformation();
577 HLoopInformation* loop5 = header5->GetLoopInformation();
578
579 EXPECT_TRUE(loop1->IsIn(*loop1));
580 EXPECT_TRUE(loop2->IsIn(*loop1));
581 EXPECT_TRUE(loop3->IsIn(*loop1));
582 EXPECT_TRUE(loop3->IsIn(*loop2));
583 EXPECT_TRUE(loop4->IsIn(*loop1));
584
585 EXPECT_FALSE(loop5->IsIn(*loop1));
586 EXPECT_FALSE(loop4->IsIn(*loop2));
587 EXPECT_FALSE(loop4->IsIn(*loop3));
588
589 EXPECT_EQ(loop1->GetPreHeader()->GetLoopInformation(), nullptr);
590 EXPECT_EQ(loop4->GetPreHeader()->GetLoopInformation(), loop1);
591
592 EXPECT_EQ(FindCommonLoopCheck(nullptr, nullptr), nullptr);
593 EXPECT_EQ(FindCommonLoopCheck(loop2, nullptr), nullptr);
594
595 EXPECT_EQ(FindCommonLoopCheck(loop1, loop1), loop1);
596 EXPECT_EQ(FindCommonLoopCheck(loop1, loop2), loop1);
597 EXPECT_EQ(FindCommonLoopCheck(loop1, loop3), loop1);
598 EXPECT_EQ(FindCommonLoopCheck(loop1, loop4), loop1);
599 EXPECT_EQ(FindCommonLoopCheck(loop1, loop5), nullptr);
600
601 EXPECT_EQ(FindCommonLoopCheck(loop2, loop3), loop2);
602 EXPECT_EQ(FindCommonLoopCheck(loop2, loop4), loop1);
603 EXPECT_EQ(FindCommonLoopCheck(loop2, loop5), nullptr);
604
605 EXPECT_EQ(FindCommonLoopCheck(loop3, loop4), loop1);
606 EXPECT_EQ(FindCommonLoopCheck(loop3, loop5), nullptr);
607
608 EXPECT_EQ(FindCommonLoopCheck(loop4, loop5), nullptr);
609
610 EXPECT_EQ(FindCommonLoopCheck(loop5, loop5), loop5);
611 }
612
613 } // namespace art
614