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 CommonCompilerTest {
28 public:
LoopOptimizationTest()29 LoopOptimizationTest()
30 : pool_(),
31 allocator_(&pool_),
32 graph_(CreateGraph(&allocator_)),
33 iva_(new (&allocator_) HInductionVarAnalysis(graph_)),
34 loop_opt_(new (&allocator_) HLoopOptimization(graph_, nullptr, iva_)) {
35 BuildGraph();
36 }
37
~LoopOptimizationTest()38 ~LoopOptimizationTest() { }
39
40 /** Constructs bare minimum graph. */
BuildGraph()41 void BuildGraph() {
42 graph_->SetNumberOfVRegs(1);
43 entry_block_ = new (&allocator_) HBasicBlock(graph_);
44 return_block_ = new (&allocator_) HBasicBlock(graph_);
45 exit_block_ = new (&allocator_) HBasicBlock(graph_);
46 graph_->AddBlock(entry_block_);
47 graph_->AddBlock(return_block_);
48 graph_->AddBlock(exit_block_);
49 graph_->SetEntryBlock(entry_block_);
50 graph_->SetExitBlock(exit_block_);
51 parameter_ = new (&allocator_) HParameterValue(graph_->GetDexFile(),
52 dex::TypeIndex(0),
53 0,
54 Primitive::kPrimInt);
55 entry_block_->AddInstruction(parameter_);
56 return_block_->AddInstruction(new (&allocator_) HReturnVoid());
57 exit_block_->AddInstruction(new (&allocator_) HExit());
58 entry_block_->AddSuccessor(return_block_);
59 return_block_->AddSuccessor(exit_block_);
60 }
61
62 /** Adds a loop nest at given position before successor. */
AddLoop(HBasicBlock * position,HBasicBlock * successor)63 HBasicBlock* AddLoop(HBasicBlock* position, HBasicBlock* successor) {
64 HBasicBlock* header = new (&allocator_) HBasicBlock(graph_);
65 HBasicBlock* body = new (&allocator_) HBasicBlock(graph_);
66 graph_->AddBlock(header);
67 graph_->AddBlock(body);
68 // Control flow.
69 position->ReplaceSuccessor(successor, header);
70 header->AddSuccessor(body);
71 header->AddSuccessor(successor);
72 header->AddInstruction(new (&allocator_) HIf(parameter_));
73 body->AddSuccessor(header);
74 body->AddInstruction(new (&allocator_) HGoto());
75 return header;
76 }
77
78 /** Performs analysis. */
PerformAnalysis()79 void PerformAnalysis() {
80 graph_->BuildDominatorTree();
81 iva_->Run();
82 // Do not release the loop hierarchy.
83 loop_opt_->loop_allocator_ = &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 ArenaPool pool_;
105 ArenaAllocator allocator_;
106 HGraph* graph_;
107 HInductionVarAnalysis* iva_;
108 HLoopOptimization* loop_opt_;
109
110 HBasicBlock* entry_block_;
111 HBasicBlock* return_block_;
112 HBasicBlock* exit_block_;
113
114 HInstruction* parameter_;
115 };
116
117 //
118 // The actual tests.
119 //
120
TEST_F(LoopOptimizationTest,NoLoops)121 TEST_F(LoopOptimizationTest, NoLoops) {
122 PerformAnalysis();
123 EXPECT_EQ("", LoopStructure());
124 }
125
TEST_F(LoopOptimizationTest,SingleLoop)126 TEST_F(LoopOptimizationTest, SingleLoop) {
127 AddLoop(entry_block_, return_block_);
128 PerformAnalysis();
129 EXPECT_EQ("[]", LoopStructure());
130 }
131
TEST_F(LoopOptimizationTest,LoopNest10)132 TEST_F(LoopOptimizationTest, LoopNest10) {
133 HBasicBlock* b = entry_block_;
134 HBasicBlock* s = return_block_;
135 for (int i = 0; i < 10; i++) {
136 s = AddLoop(b, s);
137 b = s->GetSuccessors()[0];
138 }
139 PerformAnalysis();
140 EXPECT_EQ("[[[[[[[[[[]]]]]]]]]]", LoopStructure());
141 }
142
TEST_F(LoopOptimizationTest,LoopSequence10)143 TEST_F(LoopOptimizationTest, LoopSequence10) {
144 HBasicBlock* b = entry_block_;
145 HBasicBlock* s = return_block_;
146 for (int i = 0; i < 10; i++) {
147 b = AddLoop(b, s);
148 s = b->GetSuccessors()[1];
149 }
150 PerformAnalysis();
151 EXPECT_EQ("[][][][][][][][][][]", LoopStructure());
152 }
153
TEST_F(LoopOptimizationTest,LoopSequenceOfNests)154 TEST_F(LoopOptimizationTest, LoopSequenceOfNests) {
155 HBasicBlock* b = entry_block_;
156 HBasicBlock* s = return_block_;
157 for (int i = 0; i < 10; i++) {
158 b = AddLoop(b, s);
159 s = b->GetSuccessors()[1];
160 HBasicBlock* bi = b->GetSuccessors()[0];
161 HBasicBlock* si = b;
162 for (int j = 0; j < i; j++) {
163 si = AddLoop(bi, si);
164 bi = si->GetSuccessors()[0];
165 }
166 }
167 PerformAnalysis();
168 EXPECT_EQ("[]"
169 "[[]]"
170 "[[[]]]"
171 "[[[[]]]]"
172 "[[[[[]]]]]"
173 "[[[[[[]]]]]]"
174 "[[[[[[[]]]]]]]"
175 "[[[[[[[[]]]]]]]]"
176 "[[[[[[[[[]]]]]]]]]"
177 "[[[[[[[[[[]]]]]]]]]]",
178 LoopStructure());
179 }
180
TEST_F(LoopOptimizationTest,LoopNestWithSequence)181 TEST_F(LoopOptimizationTest, LoopNestWithSequence) {
182 HBasicBlock* b = entry_block_;
183 HBasicBlock* s = return_block_;
184 for (int i = 0; i < 10; i++) {
185 s = AddLoop(b, s);
186 b = s->GetSuccessors()[0];
187 }
188 b = s;
189 s = b->GetSuccessors()[1];
190 for (int i = 0; i < 9; i++) {
191 b = AddLoop(b, s);
192 s = b->GetSuccessors()[1];
193 }
194 PerformAnalysis();
195 EXPECT_EQ("[[[[[[[[[[][][][][][][][][][]]]]]]]]]]", LoopStructure());
196 }
197
198 } // namespace art
199