| 428 | } |
| 429 | |
| 430 | static vector<BasicBlock*> top_sort(const vector<BasicBlock*> &bbs) { |
| 431 | edgesTy edges(bbs.size()); |
| 432 | unordered_map<const BasicBlock*, unsigned> bb_map; |
| 433 | |
| 434 | unsigned i = 0; |
| 435 | for (auto bb : bbs) { |
| 436 | bb_map.emplace(bb, i++); |
| 437 | } |
| 438 | |
| 439 | i = 0; |
| 440 | for (auto bb : bbs) { |
| 441 | for (auto &dst : bb->targets()) { |
| 442 | auto dst_I = bb_map.find(&dst); |
| 443 | if (dst_I != bb_map.end()) |
| 444 | edges[i].emplace(dst_I->second); |
| 445 | } |
| 446 | |
| 447 | // If `bb` is a loop header, we need to go through its exit block |
| 448 | // in order to account for some transitive dependencies we may have |
| 449 | // missed due to compression of its inner loops. |
| 450 | // If there are no inner loops, this is redundant and if `bb` is not |
| 451 | // a loop header, the set of its exit blocks is empty. |
| 452 | for (auto &dst : bb->getExitBlocks()) { |
| 453 | auto dst_I = bb_map.find(dst); |
| 454 | if (dst_I != bb_map.end()) |
| 455 | edges[i].emplace(dst_I->second); |
| 456 | } |
| 457 | ++i; |
| 458 | } |
| 459 | |
| 460 | vector<BasicBlock*> sorted_bbs; |
| 461 | sorted_bbs.reserve(bbs.size()); |
| 462 | for (auto v : util::top_sort(edges)) { |
| 463 | sorted_bbs.emplace_back(bbs[v]); |
| 464 | } |
| 465 | |
| 466 | assert(sorted_bbs.size() == bbs.size()); |
| 467 | return sorted_bbs; |
| 468 | } |
| 469 | |
| 470 | void Function::topSort() { |
| 471 | BB_order = top_sort(BB_order); |