1 /*
2  * Copyright (C) 2014 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 "mir_graph.h"
18 #include "gtest/gtest.h"
19 
20 namespace art {
21 
22 class TopologicalSortOrderTest : public testing::Test {
23  protected:
24   struct BBDef {
25     static constexpr size_t kMaxSuccessors = 4;
26     static constexpr size_t kMaxPredecessors = 4;
27 
28     BBType type;
29     size_t num_successors;
30     BasicBlockId successors[kMaxPredecessors];
31     size_t num_predecessors;
32     BasicBlockId predecessors[kMaxPredecessors];
33   };
34 
35 #define DEF_SUCC0() \
36     0u, { }
37 #define DEF_SUCC1(s1) \
38     1u, { s1 }
39 #define DEF_SUCC2(s1, s2) \
40     2u, { s1, s2 }
41 #define DEF_SUCC3(s1, s2, s3) \
42     3u, { s1, s2, s3 }
43 #define DEF_SUCC4(s1, s2, s3, s4) \
44     4u, { s1, s2, s3, s4 }
45 #define DEF_PRED0() \
46     0u, { }
47 #define DEF_PRED1(p1) \
48     1u, { p1 }
49 #define DEF_PRED2(p1, p2) \
50     2u, { p1, p2 }
51 #define DEF_PRED3(p1, p2, p3) \
52     3u, { p1, p2, p3 }
53 #define DEF_PRED4(p1, p2, p3, p4) \
54     4u, { p1, p2, p3, p4 }
55 #define DEF_BB(type, succ, pred) \
56     { type, succ, pred }
57 
DoPrepareBasicBlocks(const BBDef * defs,size_t count)58   void DoPrepareBasicBlocks(const BBDef* defs, size_t count) {
59     cu_.mir_graph->block_id_map_.clear();
60     cu_.mir_graph->block_list_.Reset();
61     ASSERT_LT(3u, count);  // null, entry, exit and at least one bytecode block.
62     ASSERT_EQ(kNullBlock, defs[0].type);
63     ASSERT_EQ(kEntryBlock, defs[1].type);
64     ASSERT_EQ(kExitBlock, defs[2].type);
65     for (size_t i = 0u; i != count; ++i) {
66       const BBDef* def = &defs[i];
67       BasicBlock* bb = cu_.mir_graph->NewMemBB(def->type, i);
68       cu_.mir_graph->block_list_.Insert(bb);
69       if (def->num_successors <= 2) {
70         bb->successor_block_list_type = kNotUsed;
71         bb->successor_blocks = nullptr;
72         bb->fall_through = (def->num_successors >= 1) ? def->successors[0] : 0u;
73         bb->taken = (def->num_successors >= 2) ? def->successors[1] : 0u;
74       } else {
75         bb->successor_block_list_type = kPackedSwitch;
76         bb->fall_through = 0u;
77         bb->taken = 0u;
78         bb->successor_blocks = new (&cu_.arena) GrowableArray<SuccessorBlockInfo*>(
79             &cu_.arena, def->num_successors, kGrowableArraySuccessorBlocks);
80         for (size_t j = 0u; j != def->num_successors; ++j) {
81           SuccessorBlockInfo* successor_block_info =
82               static_cast<SuccessorBlockInfo*>(cu_.arena.Alloc(sizeof(SuccessorBlockInfo),
83                                                                kArenaAllocSuccessor));
84           successor_block_info->block = j;
85           successor_block_info->key = 0u;  // Not used by class init check elimination.
86           bb->successor_blocks->Insert(successor_block_info);
87         }
88       }
89       bb->predecessors = new (&cu_.arena) GrowableArray<BasicBlockId>(
90           &cu_.arena, def->num_predecessors, kGrowableArrayPredecessors);
91       for (size_t j = 0u; j != def->num_predecessors; ++j) {
92         ASSERT_NE(0u, def->predecessors[j]);
93         bb->predecessors->Insert(def->predecessors[j]);
94       }
95       if (def->type == kDalvikByteCode || def->type == kEntryBlock || def->type == kExitBlock) {
96         bb->data_flow_info = static_cast<BasicBlockDataFlow*>(
97             cu_.arena.Alloc(sizeof(BasicBlockDataFlow), kArenaAllocDFInfo));
98       }
99     }
100     cu_.mir_graph->num_blocks_ = count;
101     ASSERT_EQ(count, cu_.mir_graph->block_list_.Size());
102     cu_.mir_graph->entry_block_ = cu_.mir_graph->block_list_.Get(1);
103     ASSERT_EQ(kEntryBlock, cu_.mir_graph->entry_block_->block_type);
104     cu_.mir_graph->exit_block_ = cu_.mir_graph->block_list_.Get(2);
105     ASSERT_EQ(kExitBlock, cu_.mir_graph->exit_block_->block_type);
106   }
107 
108   template <size_t count>
PrepareBasicBlocks(const BBDef (& defs)[count])109   void PrepareBasicBlocks(const BBDef (&defs)[count]) {
110     DoPrepareBasicBlocks(defs, count);
111   }
112 
ComputeTopologicalSortOrder()113   void ComputeTopologicalSortOrder() {
114     cu_.mir_graph->SSATransformationStart();
115     cu_.mir_graph->ComputeDFSOrders();
116     cu_.mir_graph->ComputeDominators();
117     cu_.mir_graph->ComputeTopologicalSortOrder();
118     cu_.mir_graph->SSATransformationEnd();
119     ASSERT_NE(cu_.mir_graph->topological_order_, nullptr);
120     ASSERT_NE(cu_.mir_graph->topological_order_loop_ends_, nullptr);
121     ASSERT_NE(cu_.mir_graph->topological_order_indexes_, nullptr);
122     ASSERT_EQ(cu_.mir_graph->GetNumBlocks(), cu_.mir_graph->topological_order_indexes_->Size());
123     for (size_t i = 0, size = cu_.mir_graph->GetTopologicalSortOrder()->Size(); i != size; ++i) {
124       ASSERT_LT(cu_.mir_graph->topological_order_->Get(i), cu_.mir_graph->GetNumBlocks());
125       BasicBlockId id = cu_.mir_graph->topological_order_->Get(i);
126       EXPECT_EQ(i, cu_.mir_graph->topological_order_indexes_->Get(id));
127     }
128   }
129 
DoCheckOrder(const BasicBlockId * ids,size_t count)130   void DoCheckOrder(const BasicBlockId* ids, size_t count) {
131     ASSERT_EQ(count, cu_.mir_graph->GetTopologicalSortOrder()->Size());
132     for (size_t i = 0; i != count; ++i) {
133       EXPECT_EQ(ids[i], cu_.mir_graph->GetTopologicalSortOrder()->Get(i)) << i;
134     }
135   }
136 
137   template <size_t count>
CheckOrder(const BasicBlockId (& ids)[count])138   void CheckOrder(const BasicBlockId (&ids)[count]) {
139     DoCheckOrder(ids, count);
140   }
141 
DoCheckLoopEnds(const uint16_t * ends,size_t count)142   void DoCheckLoopEnds(const uint16_t* ends, size_t count) {
143     for (size_t i = 0; i != count; ++i) {
144       ASSERT_LT(i, cu_.mir_graph->GetTopologicalSortOrderLoopEnds()->Size());
145       EXPECT_EQ(ends[i], cu_.mir_graph->GetTopologicalSortOrderLoopEnds()->Get(i)) << i;
146     }
147   }
148 
149   template <size_t count>
CheckLoopEnds(const uint16_t (& ends)[count])150   void CheckLoopEnds(const uint16_t (&ends)[count]) {
151     DoCheckLoopEnds(ends, count);
152   }
153 
TopologicalSortOrderTest()154   TopologicalSortOrderTest()
155       : pool_(),
156         cu_(&pool_) {
157     cu_.mir_graph.reset(new MIRGraph(&cu_, &cu_.arena));
158   }
159 
160   ArenaPool pool_;
161   CompilationUnit cu_;
162 };
163 
TEST_F(TopologicalSortOrderTest,DoWhile)164 TEST_F(TopologicalSortOrderTest, DoWhile) {
165   const BBDef bbs[] = {
166       DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
167       DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
168       DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)),
169       DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),
170       DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 4), DEF_PRED2(3, 4)),  // "taken" loops to self.
171       DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)),
172   };
173   const BasicBlockId expected_order[] = {
174       1, 3, 4, 5, 2
175   };
176   const uint16_t loop_ends[] = {
177       0, 0, 3, 0, 0
178   };
179 
180   PrepareBasicBlocks(bbs);
181   ComputeTopologicalSortOrder();
182   CheckOrder(expected_order);
183   CheckLoopEnds(loop_ends);
184 }
185 
TEST_F(TopologicalSortOrderTest,While)186 TEST_F(TopologicalSortOrderTest, While) {
187   const BBDef bbs[] = {
188       DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
189       DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
190       DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)),
191       DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED2(1, 4)),
192       DEF_BB(kDalvikByteCode, DEF_SUCC1(3), DEF_PRED1(3)),     // Loops to 3.
193       DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(3)),
194   };
195   const BasicBlockId expected_order[] = {
196       1, 3, 4, 5, 2
197   };
198   const uint16_t loop_ends[] = {
199       0, 3, 0, 0, 0
200   };
201 
202   PrepareBasicBlocks(bbs);
203   ComputeTopologicalSortOrder();
204   CheckOrder(expected_order);
205   CheckLoopEnds(loop_ends);
206 }
207 
TEST_F(TopologicalSortOrderTest,WhileWithTwoBackEdges)208 TEST_F(TopologicalSortOrderTest, WhileWithTwoBackEdges) {
209   const BBDef bbs[] = {
210       DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
211       DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
212       DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)),
213       DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 6), DEF_PRED3(1, 4, 5)),
214       DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 3), DEF_PRED1(3)),     // Loops to 3.
215       DEF_BB(kDalvikByteCode, DEF_SUCC1(3), DEF_PRED1(4)),        // Loops to 3.
216       DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(3)),
217   };
218   const BasicBlockId expected_order[] = {
219       1, 3, 4, 5, 6, 2
220   };
221   const uint16_t loop_ends[] = {
222       0, 4, 0, 0, 0, 0
223   };
224 
225   PrepareBasicBlocks(bbs);
226   ComputeTopologicalSortOrder();
227   CheckOrder(expected_order);
228   CheckLoopEnds(loop_ends);
229 }
230 
TEST_F(TopologicalSortOrderTest,NestedLoop)231 TEST_F(TopologicalSortOrderTest, NestedLoop) {
232   const BBDef bbs[] = {
233       DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
234       DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
235       DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(7)),
236       DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 7), DEF_PRED2(1, 6)),
237       DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 6), DEF_PRED2(3, 5)),
238       DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(4)),            // Loops to 4.
239       DEF_BB(kDalvikByteCode, DEF_SUCC1(3), DEF_PRED1(4)),            // Loops to 3.
240       DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(3)),
241   };
242   const BasicBlockId expected_order[] = {
243       1, 3, 4, 5, 6, 7, 2
244   };
245   const uint16_t loop_ends[] = {
246       0, 5, 4, 0, 0, 0, 0
247   };
248 
249   PrepareBasicBlocks(bbs);
250   ComputeTopologicalSortOrder();
251   CheckOrder(expected_order);
252   CheckLoopEnds(loop_ends);
253 }
254 
TEST_F(TopologicalSortOrderTest,NestedLoopHeadLoops)255 TEST_F(TopologicalSortOrderTest, NestedLoopHeadLoops) {
256   const BBDef bbs[] = {
257       DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
258       DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
259       DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)),
260       DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 6), DEF_PRED2(1, 4)),
261       DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 3), DEF_PRED2(3, 5)),      // Nested head, loops to 3.
262       DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(4)),            // Loops to 4.
263       DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(3)),
264   };
265   const BasicBlockId expected_order[] = {
266       1, 3, 4, 5, 6, 2
267   };
268   const uint16_t loop_ends[] = {
269       0, 4, 4, 0, 0, 0
270   };
271 
272   PrepareBasicBlocks(bbs);
273   ComputeTopologicalSortOrder();
274   CheckOrder(expected_order);
275   CheckLoopEnds(loop_ends);
276 }
277 
TEST_F(TopologicalSortOrderTest,NestedLoopSameBackBranchBlock)278 TEST_F(TopologicalSortOrderTest, NestedLoopSameBackBranchBlock) {
279   const BBDef bbs[] = {
280       DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
281       DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
282       DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)),
283       DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 6), DEF_PRED2(1, 5)),
284       DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED2(3, 5)),
285       DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 3), DEF_PRED1(4)),         // Loops to 4 and 3.
286       DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(3)),
287   };
288   const BasicBlockId expected_order[] = {
289       1, 3, 4, 5, 6, 2
290   };
291   const uint16_t loop_ends[] = {
292       0, 4, 4, 0, 0, 0
293   };
294 
295   PrepareBasicBlocks(bbs);
296   ComputeTopologicalSortOrder();
297   CheckOrder(expected_order);
298   CheckLoopEnds(loop_ends);
299 }
300 
TEST_F(TopologicalSortOrderTest,TwoReorderedInnerLoops)301 TEST_F(TopologicalSortOrderTest, TwoReorderedInnerLoops) {
302   // This is a simplified version of real code graph where the branch from 8 to 5 must prevent
303   // the block 5 from being considered a loop head before processing the loop 7-8.
304   const BBDef bbs[] = {
305       DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
306       DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
307       DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(9)),
308       DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 9), DEF_PRED2(1, 5)),
309       DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 7), DEF_PRED1(3)),         // Branch over loop in 5.
310       DEF_BB(kDalvikByteCode, DEF_SUCC2(6, 3), DEF_PRED3(4, 6, 8)),   // Loops to 4; inner loop.
311       DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(5)),            // Loops to 5.
312       DEF_BB(kDalvikByteCode, DEF_SUCC1(8), DEF_PRED2(4, 8)),         // Loop head.
313       DEF_BB(kDalvikByteCode, DEF_SUCC2(7, 5), DEF_PRED1(7)),         // Loops to 7; branches to 5.
314       DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(3)),
315   };
316   const BasicBlockId expected_order[] = {
317       1, 3, 4, 7, 8, 5, 6, 9, 2
318   };
319   const uint16_t loop_ends[] = {
320       0, 7, 0, 5, 0, 7, 0, 0, 0
321   };
322 
323   PrepareBasicBlocks(bbs);
324   ComputeTopologicalSortOrder();
325   CheckOrder(expected_order);
326   CheckLoopEnds(loop_ends);
327 }
328 
TEST_F(TopologicalSortOrderTest,NestedLoopWithBackEdgeAfterOuterLoopBackEdge)329 TEST_F(TopologicalSortOrderTest, NestedLoopWithBackEdgeAfterOuterLoopBackEdge) {
330   // This is a simplified version of real code graph. The back-edge from 7 to the inner
331   // loop head 4 comes after the back-edge from 6 to the outer loop head 3. To make this
332   // appear a bit more complex, there's also a back-edge from 5 to 4.
333   const BBDef bbs[] = {
334       DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
335       DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
336       DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(7)),
337       DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED2(1, 6)),         // Outer loop head.
338       DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 6), DEF_PRED3(3, 5, 7)),   // Inner loop head.
339       DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(4)),            // Loops to inner loop head 4.
340       DEF_BB(kDalvikByteCode, DEF_SUCC2(7, 3), DEF_PRED1(4)),         // Loops to outer loop head 3.
341       DEF_BB(kDalvikByteCode, DEF_SUCC2(2, 4), DEF_PRED1(6)),         // Loops to inner loop head 4.
342   };
343   const BasicBlockId expected_order[] = {
344       // NOTE: The 5 goes before 6 only because 5 is a "fall-through" from 4 while 6 is "taken".
345       1, 3, 4, 5, 6, 7, 2
346   };
347   const uint16_t loop_ends[] = {
348       0, 6, 6, 0, 0, 0, 0
349   };
350 
351   PrepareBasicBlocks(bbs);
352   ComputeTopologicalSortOrder();
353   CheckOrder(expected_order);
354   CheckLoopEnds(loop_ends);
355 }
356 
TEST_F(TopologicalSortOrderTest,LoopWithTwoEntryPoints)357 TEST_F(TopologicalSortOrderTest, LoopWithTwoEntryPoints) {
358   const BBDef bbs[] = {
359       DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
360       DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
361       DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(7)),
362       DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 4), DEF_PRED1(1)),
363       DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED2(3, 6)),  // Fall-back block is chosen as
364       DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED2(3, 4)),  // the earlier from these two.
365       DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 7), DEF_PRED1(5)),
366       DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(6)),
367   };
368   const BasicBlockId expected_order[] = {
369       1, 3, 4, 5, 6, 7, 2
370   };
371   const uint16_t loop_ends[] = {
372       0, 0, 5, 0, 0, 0, 0
373   };
374 
375   PrepareBasicBlocks(bbs);
376   ComputeTopologicalSortOrder();
377   CheckOrder(expected_order);
378   CheckLoopEnds(loop_ends);
379 }
380 
381 }  // namespace art
382