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