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 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 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 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 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 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 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 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 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 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 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
