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
20namespace art {
21
22class 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
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>
109  void PrepareBasicBlocks(const BBDef (&defs)[count]) {
110    DoPrepareBasicBlocks(defs, count);
111  }
112
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
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>
138  void CheckOrder(const BasicBlockId (&ids)[count]) {
139    DoCheckOrder(ids, count);
140  }
141
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>
150  void CheckLoopEnds(const uint16_t (&ends)[count]) {
151    DoCheckLoopEnds(ends, count);
152  }
153
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
164TEST_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
186TEST_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
208TEST_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
231TEST_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
255TEST_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
278TEST_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
301TEST_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
329TEST_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
357TEST_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