1 /*
2  * Copyright (C) 2016 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 "code_generator.h"
18 #include "driver/compiler_options.h"
19 #include "loop_optimization.h"
20 #include "optimizing_unit_test.h"
21 
22 namespace art {
23 
24 /**
25  * Fixture class for the loop optimization tests. These unit tests focus
26  * constructing the loop hierarchy. Actual optimizations are tested
27  * through the checker tests.
28  */
29 class LoopOptimizationTest : public OptimizingUnitTest {
30  protected:
SetUp()31   void SetUp() override {
32     OptimizingUnitTest::SetUp();
33 
34     graph_ = CreateGraph();
35     BuildGraph();
36     iva_  = new (GetAllocator()) HInductionVarAnalysis(graph_);
37     compiler_options_ = CommonCompilerTest::CreateCompilerOptions(kRuntimeISA, "default");
38     DCHECK(compiler_options_ != nullptr);
39     codegen_ = CodeGenerator::Create(graph_, *compiler_options_);
40     DCHECK(codegen_.get() != nullptr);
41     loop_opt_ = new (GetAllocator()) HLoopOptimization(
42         graph_, *codegen_.get(), iva_, /* stats= */ nullptr);
43   }
44 
TearDown()45   void TearDown() override {
46     codegen_.reset();
47     compiler_options_.reset();
48     graph_ = nullptr;
49     ResetPoolAndAllocator();
50     OptimizingUnitTest::TearDown();
51   }
52 
~LoopOptimizationTest()53   virtual ~LoopOptimizationTest() {}
54 
55   /** Constructs bare minimum graph. */
BuildGraph()56   void BuildGraph() {
57     graph_->SetNumberOfVRegs(1);
58     entry_block_ = new (GetAllocator()) HBasicBlock(graph_);
59     return_block_ = new (GetAllocator()) HBasicBlock(graph_);
60     exit_block_ = new (GetAllocator()) HBasicBlock(graph_);
61     graph_->AddBlock(entry_block_);
62     graph_->AddBlock(return_block_);
63     graph_->AddBlock(exit_block_);
64     graph_->SetEntryBlock(entry_block_);
65     graph_->SetExitBlock(exit_block_);
66     parameter_ = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
67                                                       dex::TypeIndex(0),
68                                                       0,
69                                                       DataType::Type::kInt32);
70     entry_block_->AddInstruction(parameter_);
71     return_block_->AddInstruction(new (GetAllocator()) HReturnVoid());
72     exit_block_->AddInstruction(new (GetAllocator()) HExit());
73     entry_block_->AddSuccessor(return_block_);
74     return_block_->AddSuccessor(exit_block_);
75   }
76 
77   /** Adds a loop nest at given position before successor. */
AddLoop(HBasicBlock * position,HBasicBlock * successor)78   HBasicBlock* AddLoop(HBasicBlock* position, HBasicBlock* successor) {
79     HBasicBlock* header = new (GetAllocator()) HBasicBlock(graph_);
80     HBasicBlock* body = new (GetAllocator()) HBasicBlock(graph_);
81     graph_->AddBlock(header);
82     graph_->AddBlock(body);
83     // Control flow.
84     position->ReplaceSuccessor(successor, header);
85     header->AddSuccessor(body);
86     header->AddSuccessor(successor);
87     header->AddInstruction(new (GetAllocator()) HIf(parameter_));
88     body->AddSuccessor(header);
89     body->AddInstruction(new (GetAllocator()) HGoto());
90     return header;
91   }
92 
93   /** Performs analysis. */
PerformAnalysis()94   void PerformAnalysis() {
95     graph_->BuildDominatorTree();
96     iva_->Run();
97     // Do not release the loop hierarchy.
98     ScopedArenaAllocator loop_allocator(GetArenaStack());
99     loop_opt_->loop_allocator_ = &loop_allocator;
100     loop_opt_->LocalRun();
101   }
102 
103   /** Constructs string representation of computed loop hierarchy. */
LoopStructure()104   std::string LoopStructure() {
105     return LoopStructureRecurse(loop_opt_->top_loop_);
106   }
107 
108   // Helper method
LoopStructureRecurse(HLoopOptimization::LoopNode * node)109   std::string LoopStructureRecurse(HLoopOptimization::LoopNode* node) {
110     std::string s;
111     for ( ; node != nullptr; node = node->next) {
112       s.append("[");
113       s.append(LoopStructureRecurse(node->inner));
114       s.append("]");
115     }
116     return s;
117   }
118 
119   // General building fields.
120   HGraph* graph_;
121 
122   std::unique_ptr<CompilerOptions> compiler_options_;
123   std::unique_ptr<CodeGenerator> codegen_;
124   HInductionVarAnalysis* iva_;
125   HLoopOptimization* loop_opt_;
126 
127   HBasicBlock* entry_block_;
128   HBasicBlock* return_block_;
129   HBasicBlock* exit_block_;
130 
131   HInstruction* parameter_;
132 };
133 
134 //
135 // The actual tests.
136 //
137 
TEST_F(LoopOptimizationTest,NoLoops)138 TEST_F(LoopOptimizationTest, NoLoops) {
139   PerformAnalysis();
140   EXPECT_EQ("", LoopStructure());
141 }
142 
TEST_F(LoopOptimizationTest,SingleLoop)143 TEST_F(LoopOptimizationTest, SingleLoop) {
144   AddLoop(entry_block_, return_block_);
145   PerformAnalysis();
146   EXPECT_EQ("[]", LoopStructure());
147 }
148 
TEST_F(LoopOptimizationTest,LoopNest10)149 TEST_F(LoopOptimizationTest, LoopNest10) {
150   HBasicBlock* b = entry_block_;
151   HBasicBlock* s = return_block_;
152   for (int i = 0; i < 10; i++) {
153     s = AddLoop(b, s);
154     b = s->GetSuccessors()[0];
155   }
156   PerformAnalysis();
157   EXPECT_EQ("[[[[[[[[[[]]]]]]]]]]", LoopStructure());
158 }
159 
TEST_F(LoopOptimizationTest,LoopSequence10)160 TEST_F(LoopOptimizationTest, LoopSequence10) {
161   HBasicBlock* b = entry_block_;
162   HBasicBlock* s = return_block_;
163   for (int i = 0; i < 10; i++) {
164     b = AddLoop(b, s);
165     s = b->GetSuccessors()[1];
166   }
167   PerformAnalysis();
168   EXPECT_EQ("[][][][][][][][][][]", LoopStructure());
169 }
170 
TEST_F(LoopOptimizationTest,LoopSequenceOfNests)171 TEST_F(LoopOptimizationTest, LoopSequenceOfNests) {
172   HBasicBlock* b = entry_block_;
173   HBasicBlock* s = return_block_;
174   for (int i = 0; i < 10; i++) {
175     b = AddLoop(b, s);
176     s = b->GetSuccessors()[1];
177     HBasicBlock* bi = b->GetSuccessors()[0];
178     HBasicBlock* si = b;
179     for (int j = 0; j < i; j++) {
180       si = AddLoop(bi, si);
181       bi = si->GetSuccessors()[0];
182     }
183   }
184   PerformAnalysis();
185   EXPECT_EQ("[]"
186             "[[]]"
187             "[[[]]]"
188             "[[[[]]]]"
189             "[[[[[]]]]]"
190             "[[[[[[]]]]]]"
191             "[[[[[[[]]]]]]]"
192             "[[[[[[[[]]]]]]]]"
193             "[[[[[[[[[]]]]]]]]]"
194             "[[[[[[[[[[]]]]]]]]]]",
195             LoopStructure());
196 }
197 
TEST_F(LoopOptimizationTest,LoopNestWithSequence)198 TEST_F(LoopOptimizationTest, LoopNestWithSequence) {
199   HBasicBlock* b = entry_block_;
200   HBasicBlock* s = return_block_;
201   for (int i = 0; i < 10; i++) {
202     s = AddLoop(b, s);
203     b = s->GetSuccessors()[0];
204   }
205   b = s;
206   s = b->GetSuccessors()[1];
207   for (int i = 0; i < 9; i++) {
208     b = AddLoop(b, s);
209     s = b->GetSuccessors()[1];
210   }
211   PerformAnalysis();
212   EXPECT_EQ("[[[[[[[[[[][][][][][][][][][]]]]]]]]]]", LoopStructure());
213 }
214 
215 // Check that SimplifyLoop() doesn't invalidate data flow when ordering loop headers'
216 // predecessors.
217 //
218 // This is a test for nodes.cc functionality - HGraph::SimplifyLoop.
TEST_F(LoopOptimizationTest,SimplifyLoopReoderPredecessors)219 TEST_F(LoopOptimizationTest, SimplifyLoopReoderPredecessors) {
220   // Can't use AddLoop as we want special order for blocks predecessors.
221   HBasicBlock* header = new (GetAllocator()) HBasicBlock(graph_);
222   HBasicBlock* body = new (GetAllocator()) HBasicBlock(graph_);
223   graph_->AddBlock(header);
224   graph_->AddBlock(body);
225 
226   // Control flow: make a loop back edge first in the list of predecessors.
227   entry_block_->RemoveSuccessor(return_block_);
228   body->AddSuccessor(header);
229   entry_block_->AddSuccessor(header);
230   header->AddSuccessor(body);
231   header->AddSuccessor(return_block_);
232   DCHECK(header->GetSuccessors()[1] == return_block_);
233 
234   // Data flow.
235   header->AddInstruction(new (GetAllocator()) HIf(parameter_));
236   body->AddInstruction(new (GetAllocator()) HGoto());
237 
238   HPhi* phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
239   HInstruction* add = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi, parameter_);
240   header->AddPhi(phi);
241   body->AddInstruction(add);
242 
243   phi->AddInput(add);
244   phi->AddInput(parameter_);
245 
246   graph_->ClearLoopInformation();
247   graph_->ClearDominanceInformation();
248   graph_->BuildDominatorTree();
249 
250   // BuildDominatorTree inserts a block beetween loop header and entry block.
251   EXPECT_EQ(header->GetPredecessors()[0]->GetSinglePredecessor(), entry_block_);
252 
253   // Check that after optimizations in BuildDominatorTree()/SimplifyCFG() phi inputs
254   // are still mapped correctly to the block predecessors.
255   for (size_t i = 0, e = phi->InputCount(); i < e; i++) {
256     HInstruction* input = phi->InputAt(i);
257     EXPECT_TRUE(input->GetBlock()->Dominates(header->GetPredecessors()[i]));
258   }
259 }
260 
261 // Test that SimplifyLoop() processes the multiple-preheaders loops correctly.
262 //
263 // This is a test for nodes.cc functionality - HGraph::SimplifyLoop.
TEST_F(LoopOptimizationTest,SimplifyLoopSinglePreheader)264 TEST_F(LoopOptimizationTest, SimplifyLoopSinglePreheader) {
265   HBasicBlock* header = AddLoop(entry_block_, return_block_);
266 
267   header->InsertInstructionBefore(
268       new (GetAllocator()) HSuspendCheck(), header->GetLastInstruction());
269 
270   // Insert an if construct before the loop so it will have two preheaders.
271   HBasicBlock* if_block = new (GetAllocator()) HBasicBlock(graph_);
272   HBasicBlock* preheader0 = new (GetAllocator()) HBasicBlock(graph_);
273   HBasicBlock* preheader1 = new (GetAllocator()) HBasicBlock(graph_);
274 
275   graph_->AddBlock(if_block);
276   graph_->AddBlock(preheader0);
277   graph_->AddBlock(preheader1);
278 
279   // Fix successors/predecessors.
280   entry_block_->ReplaceSuccessor(header, if_block);
281   if_block->AddSuccessor(preheader0);
282   if_block->AddSuccessor(preheader1);
283   preheader0->AddSuccessor(header);
284   preheader1->AddSuccessor(header);
285 
286   if_block->AddInstruction(new (GetAllocator()) HIf(parameter_));
287   preheader0->AddInstruction(new (GetAllocator()) HGoto());
288   preheader1->AddInstruction(new (GetAllocator()) HGoto());
289 
290   HBasicBlock* body = header->GetSuccessors()[0];
291   DCHECK(body != return_block_);
292 
293   // Add some data flow.
294   HIntConstant* const_0 = graph_->GetIntConstant(0);
295   HIntConstant* const_1 = graph_->GetIntConstant(1);
296   HIntConstant* const_2 = graph_->GetIntConstant(2);
297 
298   HAdd* preheader0_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, parameter_, const_0);
299   preheader0->AddInstruction(preheader0_add);
300   HAdd* preheader1_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, parameter_, const_1);
301   preheader1->AddInstruction(preheader1_add);
302 
303   HPhi* header_phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
304   header->AddPhi(header_phi);
305 
306   HAdd* body_add = new (GetAllocator()) HAdd(DataType::Type::kInt32, parameter_, const_2);
307   body->AddInstruction(body_add);
308 
309   DCHECK(header->GetPredecessors()[0] == body);
310   DCHECK(header->GetPredecessors()[1] == preheader0);
311   DCHECK(header->GetPredecessors()[2] == preheader1);
312 
313   header_phi->AddInput(body_add);
314   header_phi->AddInput(preheader0_add);
315   header_phi->AddInput(preheader1_add);
316 
317   graph_->ClearLoopInformation();
318   graph_->ClearDominanceInformation();
319   graph_->BuildDominatorTree();
320 
321   EXPECT_EQ(header->GetPredecessors().size(), 2u);
322   EXPECT_EQ(header->GetPredecessors()[1], body);
323 
324   HBasicBlock* new_preheader = header->GetLoopInformation()->GetPreHeader();
325   EXPECT_EQ(preheader0->GetSingleSuccessor(), new_preheader);
326   EXPECT_EQ(preheader1->GetSingleSuccessor(), new_preheader);
327 
328   EXPECT_EQ(new_preheader->GetPhis().CountSize(), 1u);
329   HPhi* new_preheader_phi = new_preheader->GetFirstPhi()->AsPhi();
330   EXPECT_EQ(new_preheader_phi->InputCount(), 2u);
331   EXPECT_EQ(new_preheader_phi->InputAt(0), preheader0_add);
332   EXPECT_EQ(new_preheader_phi->InputAt(1), preheader1_add);
333 
334   EXPECT_EQ(header_phi->InputCount(), 2u);
335   EXPECT_EQ(header_phi->InputAt(0), new_preheader_phi);
336   EXPECT_EQ(header_phi->InputAt(1), body_add);
337 }
338 
339 }  // namespace art
340