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