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