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