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