xref: /aosp_15_r20/art/compiler/optimizing/superblock_cloner_test.cc (revision 795d594fd825385562da6b089ea9b2033f3abf5a) 
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 // Tests SuperblockCloner for loop versioning case.
305 //
306 // See an ASCII graphics example near LoopClonerHelper::DoVersioning.
TEST_F(SuperblockClonerTest,LoopVersioning)307 TEST_F(SuperblockClonerTest, LoopVersioning) {
308   HBasicBlock* return_block = InitGraphAndParameters();
309   auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
310   CreateBasicLoopDataFlow(header, loop_body);
311   graph_->BuildDominatorTree();
312   EXPECT_TRUE(CheckGraph());
313 
314   HBasicBlockMap bb_map(
315       std::less<HBasicBlock*>(), graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
316   HInstructionMap hir_map(
317       std::less<HInstruction*>(), graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
318 
319   HLoopInformation* loop_info = header->GetLoopInformation();
320   HBasicBlock* original_preheader = loop_info->GetPreHeader();
321   LoopClonerHelper helper(loop_info, &bb_map, &hir_map, /* induction_range= */ nullptr);
322   EXPECT_TRUE(helper.IsLoopClonable());
323   HBasicBlock* new_header = helper.DoVersioning();
324   EXPECT_EQ(header, new_header);
325 
326   EXPECT_TRUE(CheckGraph());
327 
328   HBasicBlock* second_header = bb_map.Get(header);
329   HBasicBlock* second_body = bb_map.Get(loop_body);
330   HLoopInformation* second_loop_info = second_header->GetLoopInformation();
331 
332   // Check loop body successors.
333   EXPECT_EQ(loop_body->GetSingleSuccessor(), header);
334   EXPECT_EQ(second_body->GetSingleSuccessor(), second_header);
335 
336   // Check loop structure.
337   EXPECT_EQ(loop_info, header->GetLoopInformation());
338   EXPECT_EQ(loop_info->GetHeader(), header);
339   EXPECT_EQ(second_loop_info->GetHeader(), second_header);
340 
341   EXPECT_EQ(loop_info->GetBackEdges().size(), 1u);
342   EXPECT_EQ(second_loop_info->GetBackEdges().size(), 1u);
343 
344   EXPECT_EQ(loop_info->GetBackEdges()[0], loop_body);
345   EXPECT_EQ(second_loop_info->GetBackEdges()[0], second_body);
346 
347   EXPECT_EQ(original_preheader->GetSuccessors().size(), 2u);
348 }
349 
350 // Checks that loop unrolling works fine for a loop with multiple back edges. Tests that after
351 // the transformation the loop has a single preheader.
TEST_F(SuperblockClonerTest,LoopPeelingMultipleBackEdges)352 TEST_F(SuperblockClonerTest, LoopPeelingMultipleBackEdges) {
353   HBasicBlock* return_block = InitGraphAndParameters();
354   auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
355   CreateBasicLoopDataFlow(header, loop_body);
356 
357   // Transform a basic loop to have multiple back edges.
358   HBasicBlock* latch = header->GetSuccessors()[1];
359   HBasicBlock* if_block = AddNewBlock();
360   HBasicBlock* temp1 = AddNewBlock();
361   header->ReplaceSuccessor(latch, if_block);
362   if_block->AddSuccessor(latch);
363   if_block->AddSuccessor(temp1);
364   temp1->AddSuccessor(header);
365 
366   MakeIf(if_block, param_);
367 
368   HInstructionIterator it(header->GetPhis());
369   DCHECK(!it.Done());
370   HPhi* loop_phi = it.Current()->AsPhi();
371   HInstruction* temp_add =
372       MakeBinOp<HAdd>(temp1, DataType::Type::kInt32, loop_phi, graph_->GetIntConstant(2));
373   MakeGoto(temp1);
374   loop_phi->AddInput(temp_add);
375 
376   graph_->BuildDominatorTree();
377   EXPECT_TRUE(CheckGraph());
378 
379   HLoopInformation* loop_info = header->GetLoopInformation();
380   LoopClonerSimpleHelper helper(loop_info, /* induction_range= */ nullptr);
381   HBasicBlock* new_header = helper.DoPeeling();
382   EXPECT_EQ(header, new_header);
383 
384   EXPECT_TRUE(CheckGraph());
385   EXPECT_EQ(header->GetPredecessors().size(), 3u);
386 }
387 
CheckLoopStructureForLoopPeelingNested(HBasicBlock * loop1_header,HBasicBlock * loop2_header,HBasicBlock * loop3_header)388 static void CheckLoopStructureForLoopPeelingNested(HBasicBlock* loop1_header,
389                                                    HBasicBlock* loop2_header,
390                                                    HBasicBlock* loop3_header) {
391   EXPECT_EQ(loop1_header->GetLoopInformation()->GetHeader(), loop1_header);
392   EXPECT_EQ(loop2_header->GetLoopInformation()->GetHeader(), loop2_header);
393   EXPECT_EQ(loop3_header->GetLoopInformation()->GetHeader(), loop3_header);
394   EXPECT_EQ(loop1_header->GetLoopInformation()->GetPreHeader()->GetLoopInformation(), nullptr);
395   EXPECT_EQ(loop2_header->GetLoopInformation()->GetPreHeader()->GetLoopInformation(), nullptr);
396   EXPECT_EQ(loop3_header->GetLoopInformation()->GetPreHeader()->GetLoopInformation()->GetHeader(),
397             loop2_header);
398 }
399 
TEST_F(SuperblockClonerTest,LoopPeelingNested)400 TEST_F(SuperblockClonerTest, LoopPeelingNested) {
401   HBasicBlock* return_block = InitGraphAndParameters();
402 
403   // Create the following nested structure of loops
404   //   Headers:  1    2 3
405   //             [ ], [ [ ] ]
406   auto [preheader1, header1, body1] = CreateWhileLoop(return_block);
407   CreateBasicLoopDataFlow(header1, body1);
408 
409   auto [preheader2, header2, body2_end] = CreateWhileLoop(return_block);
410   CreateBasicLoopDataFlow(header2, body2_end);
411 
412   auto [preheader3, header3, body3] = CreateWhileLoop(body2_end);
413   CreateBasicLoopDataFlow(header3, body3);
414 
415   graph_->BuildDominatorTree();
416   EXPECT_TRUE(CheckGraph());
417 
418   HLoopInformation* loop2_info_before = header2->GetLoopInformation();
419   HLoopInformation* loop3_info_before = header3->GetLoopInformation();
420 
421   // Check nested loops structure.
422   CheckLoopStructureForLoopPeelingNested(header1, header2, header3);
423   LoopClonerSimpleHelper helper(header1->GetLoopInformation(), /* induction_range= */ nullptr);
424   helper.DoPeeling();
425   // Check that nested loops structure has not changed after the transformation.
426   CheckLoopStructureForLoopPeelingNested(header1, header2, header3);
427 
428   // Test that the loop info is preserved.
429   EXPECT_EQ(loop2_info_before, header2->GetLoopInformation());
430   EXPECT_EQ(loop3_info_before, header3->GetLoopInformation());
431 
432   EXPECT_EQ(loop3_info_before->GetPreHeader()->GetLoopInformation(), loop2_info_before);
433   EXPECT_EQ(loop2_info_before->GetPreHeader()->GetLoopInformation(), nullptr);
434 
435   EXPECT_EQ(helper.GetRegionToBeAdjusted(), nullptr);
436 
437   EXPECT_TRUE(CheckGraph());
438 }
439 
440 // Checks that the loop population is correctly propagated after an inner loop is peeled.
TEST_F(SuperblockClonerTest,OuterLoopPopulationAfterInnerPeeled)441 TEST_F(SuperblockClonerTest, OuterLoopPopulationAfterInnerPeeled) {
442   HBasicBlock* return_block = InitGraphAndParameters();
443 
444   // Create the following nested structure of loops
445   //   Headers:  1 2 3        4
446   //             [ [ [ ] ] ], [ ]
447   auto [preheader1, header1, body1_end] = CreateWhileLoop(return_block);
448   CreateBasicLoopDataFlow(header1, body1_end);
449 
450   auto [preheader2, header2, body2_end] = CreateWhileLoop(body1_end);
451   CreateBasicLoopDataFlow(header2, body2_end);
452 
453   auto [preheader3, header3, body3] = CreateWhileLoop(body2_end);
454   CreateBasicLoopDataFlow(header3, body3);
455 
456   auto [preheader4, header4, body4] = CreateWhileLoop(return_block);
457   CreateBasicLoopDataFlow(header4, body4);
458 
459   graph_->BuildDominatorTree();
460   EXPECT_TRUE(CheckGraph());
461 
462   LoopClonerSimpleHelper helper(header3->GetLoopInformation(), /* induction_range= */ nullptr);
463   helper.DoPeeling();
464   HLoopInformation* loop1 = header1->GetLoopInformation();
465   HLoopInformation* loop2 = header2->GetLoopInformation();
466   HLoopInformation* loop3 = header3->GetLoopInformation();
467   HLoopInformation* loop4 = header4->GetLoopInformation();
468 
469   EXPECT_TRUE(loop1->Contains(*header2));
470   EXPECT_TRUE(loop1->Contains(*header3));
471   EXPECT_TRUE(loop1->Contains(*header3->GetLoopInformation()->GetPreHeader()));
472 
473   // Check that loop4 info has not been touched after local run of AnalyzeLoops.
474   EXPECT_EQ(loop4, header4->GetLoopInformation());
475 
476   EXPECT_TRUE(loop1->IsIn(*loop1));
477   EXPECT_TRUE(loop2->IsIn(*loop1));
478   EXPECT_TRUE(loop3->IsIn(*loop1));
479   EXPECT_TRUE(loop3->IsIn(*loop2));
480   EXPECT_TRUE(!loop4->IsIn(*loop1));
481 
482   EXPECT_EQ(loop4->GetPreHeader()->GetLoopInformation(), nullptr);
483 
484   EXPECT_EQ(helper.GetRegionToBeAdjusted(), loop2);
485 
486   EXPECT_TRUE(CheckGraph());
487 }
488 
489 // Checks the case when inner loop have an exit not to its immediate outer_loop but some other loop
490 // in the hierarchy. Loop population information must be valid after loop peeling.
TEST_F(SuperblockClonerTest,NestedCaseExitToOutermost)491 TEST_F(SuperblockClonerTest, NestedCaseExitToOutermost) {
492   HBasicBlock* return_block = InitGraphAndParameters();
493 
494   // Create the following nested structure of loops then peel loop3.
495   //   Headers:  1 2 3
496   //             [ [ [ ] ] ]
497   auto [preheader1, header1, body1_end] = CreateWhileLoop(return_block);
498   CreateBasicLoopDataFlow(header1, body1_end);
499 
500   auto [preheader2, header2, body2_end] = CreateWhileLoop(body1_end);
501   CreateBasicLoopDataFlow(header2, body2_end);
502 
503   auto [preheader3, header3, body3] = CreateWhileLoop(body2_end);
504   CreateBasicLoopDataFlow(header3, body3);
505 
506   // Change the loop3 - insert an exit which leads to loop1.
507   HBasicBlock* loop3_extra_if_block = AddNewBlock();
508   MakeIf(loop3_extra_if_block, param_);
509 
510   header3->ReplaceSuccessor(body3, loop3_extra_if_block);
511   // Note: After this, both edges to `body1_end` shall be critical edges.
512   loop3_extra_if_block->AddSuccessor(body1_end);  // Long exit.
513   loop3_extra_if_block->AddSuccessor(body3);
514 
515   graph_->BuildDominatorTree();
516   EXPECT_TRUE(CheckGraph());
517 
518   HBasicBlock* loop3_long_exit = loop3_extra_if_block->GetSuccessors()[0];
519   EXPECT_TRUE(header1->GetLoopInformation()->Contains(*loop3_long_exit));
520 
521   LoopClonerSimpleHelper helper(header3->GetLoopInformation(), /* induction_range= */ nullptr);
522   helper.DoPeeling();
523 
524   HLoopInformation* loop1 = header1->GetLoopInformation();
525   // Check that after the transformation the local area for CF adjustments has been chosen
526   // correctly and loop population has been updated.
527   loop3_long_exit = loop3_extra_if_block->GetSuccessors()[0];
528   EXPECT_TRUE(loop1->Contains(*loop3_long_exit));
529 
530   EXPECT_EQ(helper.GetRegionToBeAdjusted(), loop1);
531 
532   EXPECT_TRUE(loop1->Contains(*header3));
533   EXPECT_TRUE(loop1->Contains(*header3->GetLoopInformation()->GetPreHeader()));
534 
535   EXPECT_TRUE(CheckGraph());
536 }
537 
TEST_F(SuperblockClonerTest,FastCaseCheck)538 TEST_F(SuperblockClonerTest, FastCaseCheck) {
539   ArenaAllocator* arena = GetAllocator();
540 
541   HBasicBlock* return_block = InitGraphAndParameters();
542   auto [preheader, header, loop_body] = CreateWhileLoop(return_block);
543   CreateBasicLoopDataFlow(header, loop_body);
544   graph_->BuildDominatorTree();
545 
546   HLoopInformation* loop_info = header->GetLoopInformation();
547 
548   ArenaBitVector orig_bb_set(
549       arena, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner);
550   orig_bb_set.Union(&loop_info->GetBlocks());
551 
552   HEdgeSet remap_orig_internal(graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
553   HEdgeSet remap_copy_internal(graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
554   HEdgeSet remap_incoming(graph_->GetAllocator()->Adapter(kArenaAllocSuperblockCloner));
555 
556   CollectRemappingInfoForPeelUnroll(true,
557                                     loop_info,
558                                     &remap_orig_internal,
559                                     &remap_copy_internal,
560                                     &remap_incoming);
561 
562   // Insert some extra nodes and edges.
563   ASSERT_EQ(preheader, loop_info->GetPreHeader());
564   orig_bb_set.SetBit(preheader->GetBlockId());
565 
566   // Adjust incoming edges.
567   remap_incoming.clear();
568   remap_incoming.insert(HEdge(preheader->GetSinglePredecessor(), preheader));
569 
570   HBasicBlockMap bb_map(std::less<HBasicBlock*>(), arena->Adapter(kArenaAllocSuperblockCloner));
571   HInstructionMap hir_map(std::less<HInstruction*>(), arena->Adapter(kArenaAllocSuperblockCloner));
572 
573   SuperblockCloner cloner(graph_,
574                           &orig_bb_set,
575                           &bb_map,
576                           &hir_map,
577                           /* induction_range= */ nullptr);
578   cloner.SetSuccessorRemappingInfo(&remap_orig_internal, &remap_copy_internal, &remap_incoming);
579 
580   EXPECT_FALSE(cloner.IsFastCase());
581 }
582 
583 // Helper for FindCommonLoop which also check that FindCommonLoop is symmetric.
FindCommonLoopCheck(HLoopInformation * loop1,HLoopInformation * loop2)584 static HLoopInformation* FindCommonLoopCheck(HLoopInformation* loop1, HLoopInformation* loop2) {
585   HLoopInformation* common_loop12 = FindCommonLoop(loop1, loop2);
586   HLoopInformation* common_loop21 = FindCommonLoop(loop2, loop1);
587   EXPECT_EQ(common_loop21, common_loop12);
588   return common_loop12;
589 }
590 
591 // Tests FindCommonLoop function on a loop nest.
TEST_F(SuperblockClonerTest,FindCommonLoop)592 TEST_F(SuperblockClonerTest, FindCommonLoop) {
593   HBasicBlock* header = nullptr;
594   HBasicBlock* loop_body = nullptr;
595 
596   HBasicBlock* return_block = InitGraphAndParameters();
597 
598   // Create the following nested structure of loops
599   //   Headers:  1 2 3      4      5
600   //             [ [ [ ] ], [ ] ], [ ]
601   auto [preheader1, header1, body1_end] = CreateWhileLoop(return_block);
602   CreateBasicLoopDataFlow(header1, body1_end);
603 
604   auto [preheader2, header2, body2_end] = CreateWhileLoop(body1_end);
605   CreateBasicLoopDataFlow(header2, body2_end);
606 
607   auto [preheader3, header3, body3] = CreateWhileLoop(body2_end);
608   CreateBasicLoopDataFlow(header3, body3);
609 
610   auto [preheader4, header4, body4] = CreateWhileLoop(body1_end);
611   CreateBasicLoopDataFlow(header4, body4);
612 
613   auto [preheader5, header5, body5] = CreateWhileLoop(return_block);
614   CreateBasicLoopDataFlow(header5, body5);
615 
616   graph_->BuildDominatorTree();
617   EXPECT_TRUE(CheckGraph());
618 
619   HLoopInformation* loop1 = header1->GetLoopInformation();
620   HLoopInformation* loop2 = header2->GetLoopInformation();
621   HLoopInformation* loop3 = header3->GetLoopInformation();
622   HLoopInformation* loop4 = header4->GetLoopInformation();
623   HLoopInformation* loop5 = header5->GetLoopInformation();
624 
625   EXPECT_TRUE(loop1->IsIn(*loop1));
626   EXPECT_TRUE(loop2->IsIn(*loop1));
627   EXPECT_TRUE(loop3->IsIn(*loop1));
628   EXPECT_TRUE(loop3->IsIn(*loop2));
629   EXPECT_TRUE(loop4->IsIn(*loop1));
630 
631   EXPECT_FALSE(loop5->IsIn(*loop1));
632   EXPECT_FALSE(loop4->IsIn(*loop2));
633   EXPECT_FALSE(loop4->IsIn(*loop3));
634 
635   EXPECT_EQ(loop1->GetPreHeader()->GetLoopInformation(), nullptr);
636   EXPECT_EQ(loop4->GetPreHeader()->GetLoopInformation(), loop1);
637 
638   EXPECT_EQ(FindCommonLoopCheck(nullptr, nullptr), nullptr);
639   EXPECT_EQ(FindCommonLoopCheck(loop2, nullptr), nullptr);
640 
641   EXPECT_EQ(FindCommonLoopCheck(loop1, loop1), loop1);
642   EXPECT_EQ(FindCommonLoopCheck(loop1, loop2), loop1);
643   EXPECT_EQ(FindCommonLoopCheck(loop1, loop3), loop1);
644   EXPECT_EQ(FindCommonLoopCheck(loop1, loop4), loop1);
645   EXPECT_EQ(FindCommonLoopCheck(loop1, loop5), nullptr);
646 
647   EXPECT_EQ(FindCommonLoopCheck(loop2, loop3), loop2);
648   EXPECT_EQ(FindCommonLoopCheck(loop2, loop4), loop1);
649   EXPECT_EQ(FindCommonLoopCheck(loop2, loop5), nullptr);
650 
651   EXPECT_EQ(FindCommonLoopCheck(loop3, loop4), loop1);
652   EXPECT_EQ(FindCommonLoopCheck(loop3, loop5), nullptr);
653 
654   EXPECT_EQ(FindCommonLoopCheck(loop4, loop5), nullptr);
655 
656   EXPECT_EQ(FindCommonLoopCheck(loop5, loop5), loop5);
657 }
658 
659 }  // namespace art
660