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 
22 namespace art {
23 
24 class 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 
DoPrepareBasicBlocks(const BBDef * defs,size_t count)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>
PrepareBasicBlocks(const BBDef (& defs)[count])106   void PrepareBasicBlocks(const BBDef (&defs)[count]) {
107     DoPrepareBasicBlocks(defs, count);
108   }
109 
ComputeTopologicalSortOrder()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 
DoCheckOrder(const BasicBlockId * ids,size_t count)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>
CheckOrder(const BasicBlockId (& ids)[count])135   void CheckOrder(const BasicBlockId (&ids)[count]) {
136     DoCheckOrder(ids, count);
137   }
138 
DoCheckLoopEnds(const uint16_t * ends,size_t count)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>
CheckLoopEnds(const uint16_t (& ends)[count])147   void CheckLoopEnds(const uint16_t (&ends)[count]) {
148     DoCheckLoopEnds(ends, count);
149   }
150 
TopologicalSortOrderTest()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 
TEST_F(TopologicalSortOrderTest,DoWhile)161 TEST_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 
TEST_F(TopologicalSortOrderTest,While)183 TEST_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 
TEST_F(TopologicalSortOrderTest,WhileWithTwoBackEdges)205 TEST_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 
TEST_F(TopologicalSortOrderTest,NestedLoop)228 TEST_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 
TEST_F(TopologicalSortOrderTest,NestedLoopHeadLoops)252 TEST_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 
TEST_F(TopologicalSortOrderTest,NestedLoopSameBackBranchBlock)275 TEST_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 
TEST_F(TopologicalSortOrderTest,TwoReorderedInnerLoops)298 TEST_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 
TEST_F(TopologicalSortOrderTest,NestedLoopWithBackEdgeAfterOuterLoopBackEdge)326 TEST_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 
TEST_F(TopologicalSortOrderTest,LoopWithTwoEntryPoints)354 TEST_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 
TEST_F(TopologicalSortOrderTest,UnnaturalLoops)378 TEST_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