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