| 1091 | |
| 1092 | |
| 1093 | void LoopAnalysis::getDepthFirstSpanningTree() { |
| 1094 | // +1 to account for the sink BB |
| 1095 | unsigned bb_count = f.getBBs().size() + 1; |
| 1096 | node.resize(bb_count, nullptr); |
| 1097 | last.resize(bb_count, -1u); |
| 1098 | |
| 1099 | unsigned current = 0; |
| 1100 | vector<pair<BasicBlock*, bool>> worklist = { {&f.getFirstBB(), false} }; |
| 1101 | unordered_set<const BasicBlock *> visited; |
| 1102 | while(!worklist.empty()) { |
| 1103 | auto &[bb, flag] = worklist.back(); |
| 1104 | if (flag) { |
| 1105 | last[number[bb]] = current - 1; |
| 1106 | worklist.pop_back(); |
| 1107 | } else { |
| 1108 | node[current] = bb; |
| 1109 | number[bb] = current++; |
| 1110 | flag = true; |
| 1111 | |
| 1112 | for (auto &tgt : bb->targets()) |
| 1113 | if (visited.insert(&tgt).second) |
| 1114 | worklist.emplace_back(const_cast<BasicBlock*>(&tgt), false); |
| 1115 | } |
| 1116 | } |
| 1117 | } |
| 1118 | |
| 1119 | // Implementation of Tarjan-Havlak algorithm. |
| 1120 | // |