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