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 using HBasicBlockSet = SuperblockCloner::HBasicBlockSet;
29 using HEdgeSet = SuperblockCloner::HEdgeSet;
30
31 // This class provides methods and helpers for testing various cloning and copying routines:
32 // individual instruction cloning and cloning of the more coarse-grain structures.
33 class SuperblockClonerTest : public ImprovedOptimizingUnitTest {
34 public:
CreateBasicLoopControlFlow(HBasicBlock * position,HBasicBlock * successor,HBasicBlock ** header_p,HBasicBlock ** body_p)35 void CreateBasicLoopControlFlow(HBasicBlock* position,
36 HBasicBlock* successor,
37 /* out */ HBasicBlock** header_p,
38 /* out */ HBasicBlock** body_p) {
39 HBasicBlock* loop_preheader = new (GetAllocator()) HBasicBlock(graph_);
40 HBasicBlock* loop_header = new (GetAllocator()) HBasicBlock(graph_);
41 HBasicBlock* loop_body = new (GetAllocator()) HBasicBlock(graph_);
42
43 graph_->AddBlock(loop_preheader);
44 graph_->AddBlock(loop_header);
45 graph_->AddBlock(loop_body);
46
47 position->ReplaceSuccessor(successor, loop_preheader);
48
49 loop_preheader->AddSuccessor(loop_header);
50 // Loop exit first to have a proper exit condition/target for HIf.
51 loop_header->AddSuccessor(successor);
52 loop_header->AddSuccessor(loop_body);
53 loop_body->AddSuccessor(loop_header);
54
55 *header_p = loop_header;
56 *body_p = loop_body;
57 }
58
CreateBasicLoopDataFlow(HBasicBlock * loop_header,HBasicBlock * loop_body)59 void CreateBasicLoopDataFlow(HBasicBlock* loop_header, HBasicBlock* loop_body) {
60 uint32_t dex_pc = 0;
61
62 // Entry block.
63 HIntConstant* const_0 = graph_->GetIntConstant(0);
64 HIntConstant* const_1 = graph_->GetIntConstant(1);
65 HIntConstant* const_128 = graph_->GetIntConstant(128);
66
67 // Header block.
68 HPhi* phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
69 HInstruction* suspend_check = new (GetAllocator()) HSuspendCheck();
70 HInstruction* loop_check = new (GetAllocator()) HGreaterThanOrEqual(phi, const_128);
71
72 loop_header->AddPhi(phi);
73 loop_header->AddInstruction(suspend_check);
74 loop_header->AddInstruction(loop_check);
75 loop_header->AddInstruction(new (GetAllocator()) HIf(loop_check));
76
77 // Loop body block.
78 HInstruction* null_check = new (GetAllocator()) HNullCheck(parameter_, dex_pc);
79 HInstruction* array_length = new (GetAllocator()) HArrayLength(null_check, dex_pc);
80 HInstruction* bounds_check = new (GetAllocator()) HBoundsCheck(phi, array_length, dex_pc);
81 HInstruction* array_get =
82 new (GetAllocator()) HArrayGet(null_check, bounds_check, DataType::Type::kInt32, dex_pc);
83 HInstruction* add = new (GetAllocator()) HAdd(DataType::Type::kInt32, array_get, const_1);
84 HInstruction* array_set = new (GetAllocator()) HArraySet(
85 null_check, bounds_check, add, DataType::Type::kInt32, dex_pc);
86 HInstruction* induction_inc = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi, const_1);
87
88 loop_body->AddInstruction(null_check);
89 loop_body->AddInstruction(array_length);
90 loop_body->AddInstruction(bounds_check);
91 loop_body->AddInstruction(array_get);
92 loop_body->AddInstruction(add);
93 loop_body->AddInstruction(array_set);
94 loop_body->AddInstruction(induction_inc);
95 loop_body->AddInstruction(new (GetAllocator()) HGoto());
96
97 phi->AddInput(const_0);
98 phi->AddInput(induction_inc);
99
100 graph_->SetHasBoundsChecks(true);
101
102 // Adjust HEnvironment for each instruction which require that.
103 ArenaVector<HInstruction*> current_locals({phi, const_128, parameter_},
104 GetAllocator()->Adapter(kArenaAllocInstruction));
105
106 HEnvironment* env = ManuallyBuildEnvFor(suspend_check, ¤t_locals);
107 null_check->CopyEnvironmentFrom(env);
108 bounds_check->CopyEnvironmentFrom(env);
109 }
110 };
111
TEST_F(SuperblockClonerTest,IndividualInstrCloner)112 TEST_F(SuperblockClonerTest, IndividualInstrCloner) {
113 HBasicBlock* header = nullptr;
114 HBasicBlock* loop_body = nullptr;
115
116 InitGraph();
117 CreateBasicLoopControlFlow(entry_block_, return_block_, &header, &loop_body);
118 CreateBasicLoopDataFlow(header, loop_body);
119 graph_->BuildDominatorTree();
120 EXPECT_TRUE(CheckGraph());
121
122 HSuspendCheck* old_suspend_check = header->GetLoopInformation()->GetSuspendCheck();
123 CloneAndReplaceInstructionVisitor visitor(graph_);
124 // Do instruction cloning and replacement twice with different visiting order.
125
126 visitor.VisitInsertionOrder();
127 size_t instr_replaced_by_clones_count = visitor.GetInstrReplacedByClonesCount();
128 EXPECT_EQ(instr_replaced_by_clones_count, 12u);
129 EXPECT_TRUE(CheckGraph());
130
131 visitor.VisitReversePostOrder();
132 instr_replaced_by_clones_count = visitor.GetInstrReplacedByClonesCount();
133 EXPECT_EQ(instr_replaced_by_clones_count, 24u);
134 EXPECT_TRUE(CheckGraph());
135
136 HSuspendCheck* new_suspend_check = header->GetLoopInformation()->GetSuspendCheck();
137 EXPECT_NE(new_suspend_check, old_suspend_check);
138 EXPECT_NE(new_suspend_check, nullptr);
139 }
140
141 // Tests SuperblockCloner::CloneBasicBlocks - check instruction cloning and initial remapping of
142 // instructions' inputs.
TEST_F(SuperblockClonerTest,CloneBasicBlocks)143 TEST_F(SuperblockClonerTest, CloneBasicBlocks) {
144 HBasicBlock* header = nullptr;
145 HBasicBlock* loop_body = nullptr;
146 ArenaAllocator* arena = graph_->GetAllocator();
147
148 InitGraph();
149 CreateBasicLoopControlFlow(entry_block_, return_block_, &header, &loop_body);
150 CreateBasicLoopDataFlow(header, loop_body);
151 graph_->BuildDominatorTree();
152 ASSERT_TRUE(CheckGraph());
153
154 ArenaBitVector orig_bb_set(
155 arena, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner);
156 HBasicBlockMap bb_map(std::less<HBasicBlock*>(), arena->Adapter(kArenaAllocSuperblockCloner));
157 HInstructionMap hir_map(std::less<HInstruction*>(), arena->Adapter(kArenaAllocSuperblockCloner));
158
159 HLoopInformation* loop_info = header->GetLoopInformation();
160 orig_bb_set.Union(&loop_info->GetBlocks());
161
162 SuperblockCloner cloner(graph_,
163 &orig_bb_set,
164 &bb_map,
165 &hir_map,
166 /* induction_range= */ nullptr);
167 EXPECT_TRUE(cloner.IsSubgraphClonable());
168
169 cloner.CloneBasicBlocks();
170
171 EXPECT_EQ(bb_map.size(), 2u);
172 EXPECT_EQ(hir_map.size(), 12u);
173
174 for (auto it : hir_map) {
175 HInstruction* orig_instr = it.first;
176 HInstruction* copy_instr = it.second;
177
178 EXPECT_EQ(cloner.GetBlockCopy(orig_instr->GetBlock()), copy_instr->GetBlock());
179 EXPECT_EQ(orig_instr->GetKind(), copy_instr->GetKind());
180 EXPECT_EQ(orig_instr->GetType(), copy_instr->GetType());
181
182 if (orig_instr->IsPhi()) {
183 continue;
184 }
185
186 EXPECT_EQ(orig_instr->InputCount(), copy_instr->InputCount());
187
188 // Check that inputs match.
189 for (size_t i = 0, e = orig_instr->InputCount(); i < e; i++) {
190 HInstruction* orig_input = orig_instr->InputAt(i);
191 HInstruction* copy_input = copy_instr->InputAt(i);
192 if (cloner.IsInOrigBBSet(orig_input->GetBlock())) {
193 EXPECT_EQ(cloner.GetInstrCopy(orig_input), copy_input);
194 } else {
195 EXPECT_EQ(orig_input, copy_input);
196 }
197 }
198
199 EXPECT_EQ(orig_instr->HasEnvironment(), copy_instr->HasEnvironment());
200
201 // Check that environments match.
202 if (orig_instr->HasEnvironment()) {
203 HEnvironment* orig_env = orig_instr->GetEnvironment();
204 HEnvironment* copy_env = copy_instr->GetEnvironment();
205
206 EXPECT_EQ(copy_env->GetParent(), nullptr);
207 EXPECT_EQ(orig_env->Size(), copy_env->Size());
208
209 for (size_t i = 0, e = orig_env->Size(); i < e; i++) {
210 HInstruction* orig_input = orig_env->GetInstructionAt(i);
211 HInstruction* copy_input = copy_env->GetInstructionAt(i);
212 if (cloner.IsInOrigBBSet(orig_input->GetBlock())) {
213 EXPECT_EQ(cloner.GetInstrCopy(orig_input), copy_input);
214 } else {
215 EXPECT_EQ(orig_input, copy_input);
216 }
217 }
218 }
219 }
220 }
221
222 // SuperblockCloner::CleanUpControlFlow - checks algorithms of local adjustments of the control
223 // flow.
TEST_F(SuperblockClonerTest,AdjustControlFlowInfo)224 TEST_F(SuperblockClonerTest, AdjustControlFlowInfo) {
225 HBasicBlock* header = nullptr;
226 HBasicBlock* loop_body = nullptr;
227 ArenaAllocator* arena = graph_->GetAllocator();
228
229 InitGraph();
230 CreateBasicLoopControlFlow(entry_block_, return_block_, &header, &loop_body);
231 CreateBasicLoopDataFlow(header, loop_body);
232 graph_->BuildDominatorTree();
233 ASSERT_TRUE(CheckGraph());
234
235 ArenaBitVector orig_bb_set(
236 arena, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner);
237
238 HLoopInformation* loop_info = header->GetLoopInformation();
239 orig_bb_set.Union(&loop_info->GetBlocks());
240
241 SuperblockCloner cloner(graph_,
242 &orig_bb_set,
243 /* bb_map= */ nullptr,
244 /* hir_map= */ nullptr,
245 /* induction_range= */ nullptr);
246 EXPECT_TRUE(cloner.IsSubgraphClonable());
247
248 cloner.FindAndSetLocalAreaForAdjustments();
249 cloner.CleanUpControlFlow();
250
251 EXPECT_TRUE(CheckGraph());
252
253 EXPECT_TRUE(entry_block_->Dominates(header));
254 EXPECT_TRUE(entry_block_->Dominates(exit_block_));
255
256 EXPECT_EQ(header->GetLoopInformation(), loop_info);
257 EXPECT_EQ(loop_info->GetHeader(), header);
258 EXPECT_TRUE(loop_info->Contains(*loop_body));
259 EXPECT_TRUE(loop_info->IsBackEdge(*loop_body));
260 }
261
262 // Tests IsSubgraphConnected function for negative case.
TEST_F(SuperblockClonerTest,IsGraphConnected)263 TEST_F(SuperblockClonerTest, IsGraphConnected) {
264 HBasicBlock* header = nullptr;
265 HBasicBlock* loop_body = nullptr;
266 ArenaAllocator* arena = graph_->GetAllocator();
267
268 InitGraph();
269 CreateBasicLoopControlFlow(entry_block_, return_block_, &header, &loop_body);
270 CreateBasicLoopDataFlow(header, loop_body);
271 HBasicBlock* unreachable_block = new (GetAllocator()) HBasicBlock(graph_);
272 graph_->AddBlock(unreachable_block);
273
274 HBasicBlockSet bb_set(
275 arena, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner);
276 bb_set.SetBit(header->GetBlockId());
277 bb_set.SetBit(loop_body->GetBlockId());
278 bb_set.SetBit(unreachable_block->GetBlockId());
279
280 EXPECT_FALSE(IsSubgraphConnected(&bb_set, graph_));
281 EXPECT_EQ(bb_set.NumSetBits(), 1u);
282 EXPECT_TRUE(bb_set.IsBitSet(unreachable_block->GetBlockId()));
283 }
284
285 // Tests SuperblockCloner for loop peeling case.
286 //
287 // Control Flow of the example (ignoring critical edges splitting).
288 //
289 // Before After
290 //
291 // |B| |B|
292 // | |
293 // v v
294 // |1| |1|
295 // | |
296 // v v
297 // |2|<-\ (6) |2A|
298 // / \ / / \
299 // v v/ / v
300 // |4| |3| / |3A| (7)
301 // | / /
302 // v | v
303 // |E| \ |2|<-\
304 // \ / \ /
305 // v v /
306 // |4| |3|
307 // |
308 // v
309 // |E|
TEST_F(SuperblockClonerTest,LoopPeeling)310 TEST_F(SuperblockClonerTest, LoopPeeling) {
311 HBasicBlock* header = nullptr;
312 HBasicBlock* loop_body = nullptr;
313
314 InitGraph();
315 CreateBasicLoopControlFlow(entry_block_, return_block_, &header, &loop_body);
316 CreateBasicLoopDataFlow(header, loop_body);
317 graph_->BuildDominatorTree();
318 EXPECT_TRUE(CheckGraph());
319
320 HBasicBlockMap bb_map(
321 std::less<HBasicBlock*>(), graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
322 HInstructionMap hir_map(
323 std::less<HInstruction*>(), graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
324
325 HLoopInformation* loop_info = header->GetLoopInformation();
326 PeelUnrollHelper helper(loop_info, &bb_map, &hir_map, /* induction_range= */ nullptr);
327 EXPECT_TRUE(helper.IsLoopClonable());
328 HBasicBlock* new_header = helper.DoPeeling();
329 HLoopInformation* new_loop_info = new_header->GetLoopInformation();
330
331 EXPECT_TRUE(CheckGraph());
332
333 // Check loop body successors.
334 EXPECT_EQ(loop_body->GetSingleSuccessor(), header);
335 EXPECT_EQ(bb_map.Get(loop_body)->GetSingleSuccessor(), header);
336
337 // Check loop structure.
338 EXPECT_EQ(header, new_header);
339 EXPECT_EQ(new_loop_info->GetHeader(), header);
340 EXPECT_EQ(new_loop_info->GetBackEdges().size(), 1u);
341 EXPECT_EQ(new_loop_info->GetBackEdges()[0], loop_body);
342 }
343
344 // Tests SuperblockCloner for loop unrolling case.
345 //
346 // Control Flow of the example (ignoring critical edges splitting).
347 //
348 // Before After
349 //
350 // |B| |B|
351 // | |
352 // v v
353 // |1| |1|
354 // | |
355 // v v
356 // |2|<-\ (6) |2A|<-\
357 // / \ / / \ \
358 // v v/ / v \
359 // |4| |3| /(7)|3A| |
360 // | / / /
361 // v | v /
362 // |E| \ |2| /
363 // \ / \ /
364 // v v/
365 // |4| |3|
366 // |
367 // v
368 // |E|
TEST_F(SuperblockClonerTest,LoopUnrolling)369 TEST_F(SuperblockClonerTest, LoopUnrolling) {
370 HBasicBlock* header = nullptr;
371 HBasicBlock* loop_body = nullptr;
372
373 InitGraph();
374 CreateBasicLoopControlFlow(entry_block_, return_block_, &header, &loop_body);
375 CreateBasicLoopDataFlow(header, loop_body);
376 graph_->BuildDominatorTree();
377 EXPECT_TRUE(CheckGraph());
378
379 HBasicBlockMap bb_map(
380 std::less<HBasicBlock*>(), graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
381 HInstructionMap hir_map(
382 std::less<HInstruction*>(), graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
383
384 HLoopInformation* loop_info = header->GetLoopInformation();
385 PeelUnrollHelper helper(loop_info, &bb_map, &hir_map, /* induction_range= */ nullptr);
386 EXPECT_TRUE(helper.IsLoopClonable());
387 HBasicBlock* new_header = helper.DoUnrolling();
388
389 EXPECT_TRUE(CheckGraph());
390
391 // Check loop body successors.
392 EXPECT_EQ(loop_body->GetSingleSuccessor(), bb_map.Get(header));
393 EXPECT_EQ(bb_map.Get(loop_body)->GetSingleSuccessor(), header);
394
395 // Check loop structure.
396 EXPECT_EQ(header, new_header);
397 EXPECT_EQ(loop_info, new_header->GetLoopInformation());
398 EXPECT_EQ(loop_info->GetHeader(), new_header);
399 EXPECT_EQ(loop_info->GetBackEdges().size(), 1u);
400 EXPECT_EQ(loop_info->GetBackEdges()[0], bb_map.Get(loop_body));
401 }
402
403 // Checks that loop unrolling works fine for a loop with multiple back edges. Tests that after
404 // the transformation the loop has a single preheader.
TEST_F(SuperblockClonerTest,LoopPeelingMultipleBackEdges)405 TEST_F(SuperblockClonerTest, LoopPeelingMultipleBackEdges) {
406 HBasicBlock* header = nullptr;
407 HBasicBlock* loop_body = nullptr;
408
409 InitGraph();
410 CreateBasicLoopControlFlow(entry_block_, return_block_, &header, &loop_body);
411 CreateBasicLoopDataFlow(header, loop_body);
412
413 // Transform a basic loop to have multiple back edges.
414 HBasicBlock* latch = header->GetSuccessors()[1];
415 HBasicBlock* if_block = new (GetAllocator()) HBasicBlock(graph_);
416 HBasicBlock* temp1 = new (GetAllocator()) HBasicBlock(graph_);
417 graph_->AddBlock(if_block);
418 graph_->AddBlock(temp1);
419 header->ReplaceSuccessor(latch, if_block);
420 if_block->AddSuccessor(latch);
421 if_block->AddSuccessor(temp1);
422 temp1->AddSuccessor(header);
423
424 if_block->AddInstruction(new (GetAllocator()) HIf(parameter_));
425
426 HInstructionIterator it(header->GetPhis());
427 DCHECK(!it.Done());
428 HPhi* loop_phi = it.Current()->AsPhi();
429 HInstruction* temp_add = new (GetAllocator()) HAdd(DataType::Type::kInt32,
430 loop_phi,
431 graph_->GetIntConstant(2));
432 temp1->AddInstruction(temp_add);
433 temp1->AddInstruction(new (GetAllocator()) HGoto());
434 loop_phi->AddInput(temp_add);
435
436 graph_->BuildDominatorTree();
437 EXPECT_TRUE(CheckGraph());
438
439 HLoopInformation* loop_info = header->GetLoopInformation();
440 PeelUnrollSimpleHelper helper(loop_info, /* induction_range= */ nullptr);
441 HBasicBlock* new_header = helper.DoPeeling();
442 EXPECT_EQ(header, new_header);
443
444 EXPECT_TRUE(CheckGraph());
445 EXPECT_EQ(header->GetPredecessors().size(), 3u);
446 }
447
CheckLoopStructureForLoopPeelingNested(HBasicBlock * loop1_header,HBasicBlock * loop2_header,HBasicBlock * loop3_header)448 static void CheckLoopStructureForLoopPeelingNested(HBasicBlock* loop1_header,
449 HBasicBlock* loop2_header,
450 HBasicBlock* loop3_header) {
451 EXPECT_EQ(loop1_header->GetLoopInformation()->GetHeader(), loop1_header);
452 EXPECT_EQ(loop2_header->GetLoopInformation()->GetHeader(), loop2_header);
453 EXPECT_EQ(loop3_header->GetLoopInformation()->GetHeader(), loop3_header);
454 EXPECT_EQ(loop1_header->GetLoopInformation()->GetPreHeader()->GetLoopInformation(), nullptr);
455 EXPECT_EQ(loop2_header->GetLoopInformation()->GetPreHeader()->GetLoopInformation(), nullptr);
456 EXPECT_EQ(loop3_header->GetLoopInformation()->GetPreHeader()->GetLoopInformation()->GetHeader(),
457 loop2_header);
458 }
459
TEST_F(SuperblockClonerTest,LoopPeelingNested)460 TEST_F(SuperblockClonerTest, LoopPeelingNested) {
461 HBasicBlock* header = nullptr;
462 HBasicBlock* loop_body = nullptr;
463
464 InitGraph();
465
466 // Create the following nested structure of loops
467 // Headers: 1 2 3
468 // [ ], [ [ ] ]
469 CreateBasicLoopControlFlow(entry_block_, return_block_, &header, &loop_body);
470 CreateBasicLoopDataFlow(header, loop_body);
471 HBasicBlock* loop1_header = header;
472
473 CreateBasicLoopControlFlow(header, return_block_, &header, &loop_body);
474 CreateBasicLoopDataFlow(header, loop_body);
475 HBasicBlock* loop2_header = header;
476
477 CreateBasicLoopControlFlow(header, header->GetSuccessors()[1], &header, &loop_body);
478 CreateBasicLoopDataFlow(header, loop_body);
479 HBasicBlock* loop3_header = header;
480
481 graph_->BuildDominatorTree();
482 EXPECT_TRUE(CheckGraph());
483
484 HLoopInformation* loop2_info_before = loop2_header->GetLoopInformation();
485 HLoopInformation* loop3_info_before = loop3_header->GetLoopInformation();
486
487 // Check nested loops structure.
488 CheckLoopStructureForLoopPeelingNested(loop1_header, loop2_header, loop3_header);
489 PeelUnrollSimpleHelper helper(loop1_header->GetLoopInformation(), /* induction_range= */ nullptr);
490 helper.DoPeeling();
491 // Check that nested loops structure has not changed after the transformation.
492 CheckLoopStructureForLoopPeelingNested(loop1_header, loop2_header, loop3_header);
493
494 // Test that the loop info is preserved.
495 EXPECT_EQ(loop2_info_before, loop2_header->GetLoopInformation());
496 EXPECT_EQ(loop3_info_before, loop3_header->GetLoopInformation());
497
498 EXPECT_EQ(loop3_info_before->GetPreHeader()->GetLoopInformation(), loop2_info_before);
499 EXPECT_EQ(loop2_info_before->GetPreHeader()->GetLoopInformation(), nullptr);
500
501 EXPECT_EQ(helper.GetRegionToBeAdjusted(), nullptr);
502
503 EXPECT_TRUE(CheckGraph());
504 }
505
506 // Checks that the loop population is correctly propagated after an inner loop is peeled.
TEST_F(SuperblockClonerTest,OuterLoopPopulationAfterInnerPeeled)507 TEST_F(SuperblockClonerTest, OuterLoopPopulationAfterInnerPeeled) {
508 HBasicBlock* header = nullptr;
509 HBasicBlock* loop_body = nullptr;
510
511 InitGraph();
512
513 // Create the following nested structure of loops
514 // Headers: 1 2 3 4
515 // [ [ [ ] ] ], [ ]
516 CreateBasicLoopControlFlow(entry_block_, return_block_, &header, &loop_body);
517 CreateBasicLoopDataFlow(header, loop_body);
518 HBasicBlock* loop1_header = header;
519
520 CreateBasicLoopControlFlow(header, header->GetSuccessors()[1], &header, &loop_body);
521 CreateBasicLoopDataFlow(header, loop_body);
522 HBasicBlock* loop2_header = header;
523
524 CreateBasicLoopControlFlow(header, header->GetSuccessors()[1], &header, &loop_body);
525 CreateBasicLoopDataFlow(header, loop_body);
526 HBasicBlock* loop3_header = header;
527
528 CreateBasicLoopControlFlow(loop1_header, return_block_, &header, &loop_body);
529 CreateBasicLoopDataFlow(header, loop_body);
530 HBasicBlock* loop4_header = header;
531
532 graph_->BuildDominatorTree();
533 EXPECT_TRUE(CheckGraph());
534
535 PeelUnrollSimpleHelper helper(loop3_header->GetLoopInformation(), /* induction_range= */ nullptr);
536 helper.DoPeeling();
537 HLoopInformation* loop1 = loop1_header->GetLoopInformation();
538 HLoopInformation* loop2 = loop2_header->GetLoopInformation();
539 HLoopInformation* loop3 = loop3_header->GetLoopInformation();
540 HLoopInformation* loop4 = loop4_header->GetLoopInformation();
541
542 EXPECT_TRUE(loop1->Contains(*loop2_header));
543 EXPECT_TRUE(loop1->Contains(*loop3_header));
544 EXPECT_TRUE(loop1->Contains(*loop3_header->GetLoopInformation()->GetPreHeader()));
545
546 // Check that loop4 info has not been touched after local run of AnalyzeLoops.
547 EXPECT_EQ(loop4, loop4_header->GetLoopInformation());
548
549 EXPECT_TRUE(loop1->IsIn(*loop1));
550 EXPECT_TRUE(loop2->IsIn(*loop1));
551 EXPECT_TRUE(loop3->IsIn(*loop1));
552 EXPECT_TRUE(loop3->IsIn(*loop2));
553 EXPECT_TRUE(!loop4->IsIn(*loop1));
554
555 EXPECT_EQ(loop4->GetPreHeader()->GetLoopInformation(), nullptr);
556
557 EXPECT_EQ(helper.GetRegionToBeAdjusted(), loop2);
558
559 EXPECT_TRUE(CheckGraph());
560 }
561
562 // Checks the case when inner loop have an exit not to its immediate outer_loop but some other loop
563 // in the hierarchy. Loop population information must be valid after loop peeling.
TEST_F(SuperblockClonerTest,NestedCaseExitToOutermost)564 TEST_F(SuperblockClonerTest, NestedCaseExitToOutermost) {
565 HBasicBlock* header = nullptr;
566 HBasicBlock* loop_body = nullptr;
567
568 InitGraph();
569
570 // Create the following nested structure of loops then peel loop3.
571 // Headers: 1 2 3
572 // [ [ [ ] ] ]
573 CreateBasicLoopControlFlow(entry_block_, return_block_, &header, &loop_body);
574 CreateBasicLoopDataFlow(header, loop_body);
575 HBasicBlock* loop1_header = header;
576 HBasicBlock* loop_body1 = loop_body;
577
578 CreateBasicLoopControlFlow(header, header->GetSuccessors()[1], &header, &loop_body);
579 CreateBasicLoopDataFlow(header, loop_body);
580
581 CreateBasicLoopControlFlow(header, header->GetSuccessors()[1], &header, &loop_body);
582 CreateBasicLoopDataFlow(header, loop_body);
583 HBasicBlock* loop3_header = header;
584 HBasicBlock* loop_body3 = loop_body;
585
586 // Change the loop3 - insert an exit which leads to loop1.
587 HBasicBlock* loop3_extra_if_block = new (GetAllocator()) HBasicBlock(graph_);
588 graph_->AddBlock(loop3_extra_if_block);
589 loop3_extra_if_block->AddInstruction(new (GetAllocator()) HIf(parameter_));
590
591 loop3_header->ReplaceSuccessor(loop_body3, loop3_extra_if_block);
592 loop3_extra_if_block->AddSuccessor(loop_body1); // Long exit.
593 loop3_extra_if_block->AddSuccessor(loop_body3);
594
595 graph_->BuildDominatorTree();
596 EXPECT_TRUE(CheckGraph());
597
598 HBasicBlock* loop3_long_exit = loop3_extra_if_block->GetSuccessors()[0];
599 EXPECT_TRUE(loop1_header->GetLoopInformation()->Contains(*loop3_long_exit));
600
601 PeelUnrollSimpleHelper helper(loop3_header->GetLoopInformation(), /* induction_range= */ nullptr);
602 helper.DoPeeling();
603
604 HLoopInformation* loop1 = loop1_header->GetLoopInformation();
605 // Check that after the transformation the local area for CF adjustments has been chosen
606 // correctly and loop population has been updated.
607 loop3_long_exit = loop3_extra_if_block->GetSuccessors()[0];
608 EXPECT_TRUE(loop1->Contains(*loop3_long_exit));
609
610 EXPECT_EQ(helper.GetRegionToBeAdjusted(), loop1);
611
612 EXPECT_TRUE(loop1->Contains(*loop3_header));
613 EXPECT_TRUE(loop1->Contains(*loop3_header->GetLoopInformation()->GetPreHeader()));
614
615 EXPECT_TRUE(CheckGraph());
616 }
617
TEST_F(SuperblockClonerTest,FastCaseCheck)618 TEST_F(SuperblockClonerTest, FastCaseCheck) {
619 HBasicBlock* header = nullptr;
620 HBasicBlock* loop_body = nullptr;
621 ArenaAllocator* arena = graph_->GetAllocator();
622
623 InitGraph();
624 CreateBasicLoopControlFlow(entry_block_, return_block_, &header, &loop_body);
625 CreateBasicLoopDataFlow(header, loop_body);
626 graph_->BuildDominatorTree();
627
628 HLoopInformation* loop_info = header->GetLoopInformation();
629
630 ArenaBitVector orig_bb_set(
631 arena, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner);
632 orig_bb_set.Union(&loop_info->GetBlocks());
633
634 HEdgeSet remap_orig_internal(graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
635 HEdgeSet remap_copy_internal(graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
636 HEdgeSet remap_incoming(graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
637
638 CollectRemappingInfoForPeelUnroll(true,
639 loop_info,
640 &remap_orig_internal,
641 &remap_copy_internal,
642 &remap_incoming);
643
644 // Insert some extra nodes and edges.
645 HBasicBlock* preheader = loop_info->GetPreHeader();
646 orig_bb_set.SetBit(preheader->GetBlockId());
647
648 // Adjust incoming edges.
649 remap_incoming.clear();
650 remap_incoming.insert(HEdge(preheader->GetSinglePredecessor(), preheader));
651
652 HBasicBlockMap bb_map(std::less<HBasicBlock*>(), arena->Adapter(kArenaAllocSuperblockCloner));
653 HInstructionMap hir_map(std::less<HInstruction*>(), arena->Adapter(kArenaAllocSuperblockCloner));
654
655 SuperblockCloner cloner(graph_,
656 &orig_bb_set,
657 &bb_map,
658 &hir_map,
659 /* induction_range= */ nullptr);
660 cloner.SetSuccessorRemappingInfo(&remap_orig_internal, &remap_copy_internal, &remap_incoming);
661
662 EXPECT_FALSE(cloner.IsFastCase());
663 }
664
665 // Helper for FindCommonLoop which also check that FindCommonLoop is symmetric.
FindCommonLoopCheck(HLoopInformation * loop1,HLoopInformation * loop2)666 static HLoopInformation* FindCommonLoopCheck(HLoopInformation* loop1, HLoopInformation* loop2) {
667 HLoopInformation* common_loop12 = FindCommonLoop(loop1, loop2);
668 HLoopInformation* common_loop21 = FindCommonLoop(loop2, loop1);
669 EXPECT_EQ(common_loop21, common_loop12);
670 return common_loop12;
671 }
672
673 // Tests FindCommonLoop function on a loop nest.
TEST_F(SuperblockClonerTest,FindCommonLoop)674 TEST_F(SuperblockClonerTest, FindCommonLoop) {
675 HBasicBlock* header = nullptr;
676 HBasicBlock* loop_body = nullptr;
677
678 InitGraph();
679
680 // Create the following nested structure of loops
681 // Headers: 1 2 3 4 5
682 // [ [ [ ] ], [ ] ], [ ]
683 CreateBasicLoopControlFlow(entry_block_, return_block_, &header, &loop_body);
684 CreateBasicLoopDataFlow(header, loop_body);
685 HBasicBlock* loop1_header = header;
686
687 CreateBasicLoopControlFlow(header, header->GetSuccessors()[1], &header, &loop_body);
688 CreateBasicLoopDataFlow(header, loop_body);
689 HBasicBlock* loop2_header = header;
690
691 CreateBasicLoopControlFlow(header, header->GetSuccessors()[1], &header, &loop_body);
692 CreateBasicLoopDataFlow(header, loop_body);
693 HBasicBlock* loop3_header = header;
694
695 CreateBasicLoopControlFlow(loop2_header, loop2_header->GetSuccessors()[0], &header, &loop_body);
696 CreateBasicLoopDataFlow(header, loop_body);
697 HBasicBlock* loop4_header = header;
698
699 CreateBasicLoopControlFlow(loop1_header, return_block_, &header, &loop_body);
700 CreateBasicLoopDataFlow(header, loop_body);
701 HBasicBlock* loop5_header = header;
702
703 graph_->BuildDominatorTree();
704 EXPECT_TRUE(CheckGraph());
705
706 HLoopInformation* loop1 = loop1_header->GetLoopInformation();
707 HLoopInformation* loop2 = loop2_header->GetLoopInformation();
708 HLoopInformation* loop3 = loop3_header->GetLoopInformation();
709 HLoopInformation* loop4 = loop4_header->GetLoopInformation();
710 HLoopInformation* loop5 = loop5_header->GetLoopInformation();
711
712 EXPECT_TRUE(loop1->IsIn(*loop1));
713 EXPECT_TRUE(loop2->IsIn(*loop1));
714 EXPECT_TRUE(loop3->IsIn(*loop1));
715 EXPECT_TRUE(loop3->IsIn(*loop2));
716 EXPECT_TRUE(loop4->IsIn(*loop1));
717
718 EXPECT_FALSE(loop5->IsIn(*loop1));
719 EXPECT_FALSE(loop4->IsIn(*loop2));
720 EXPECT_FALSE(loop4->IsIn(*loop3));
721
722 EXPECT_EQ(loop1->GetPreHeader()->GetLoopInformation(), nullptr);
723 EXPECT_EQ(loop4->GetPreHeader()->GetLoopInformation(), loop1);
724
725 EXPECT_EQ(FindCommonLoopCheck(nullptr, nullptr), nullptr);
726 EXPECT_EQ(FindCommonLoopCheck(loop2, nullptr), nullptr);
727
728 EXPECT_EQ(FindCommonLoopCheck(loop1, loop1), loop1);
729 EXPECT_EQ(FindCommonLoopCheck(loop1, loop2), loop1);
730 EXPECT_EQ(FindCommonLoopCheck(loop1, loop3), loop1);
731 EXPECT_EQ(FindCommonLoopCheck(loop1, loop4), loop1);
732 EXPECT_EQ(FindCommonLoopCheck(loop1, loop5), nullptr);
733
734 EXPECT_EQ(FindCommonLoopCheck(loop2, loop3), loop2);
735 EXPECT_EQ(FindCommonLoopCheck(loop2, loop4), loop1);
736 EXPECT_EQ(FindCommonLoopCheck(loop2, loop5), nullptr);
737
738 EXPECT_EQ(FindCommonLoopCheck(loop3, loop4), loop1);
739 EXPECT_EQ(FindCommonLoopCheck(loop3, loop5), nullptr);
740
741 EXPECT_EQ(FindCommonLoopCheck(loop4, loop5), nullptr);
742
743 EXPECT_EQ(FindCommonLoopCheck(loop5, loop5), loop5);
744 }
745
746 } // namespace art
747