| 262 | |
| 263 | |
| 264 | class DomTree final { |
| 265 | const Function &f; |
| 266 | |
| 267 | struct DomTreeNode { |
| 268 | const BasicBlock &bb; |
| 269 | std::vector<DomTreeNode*> preds; |
| 270 | DomTreeNode *dominator = nullptr; |
| 271 | unsigned order; |
| 272 | |
| 273 | DomTreeNode(const BasicBlock &bb) : bb(bb) {} |
| 274 | }; |
| 275 | |
| 276 | std::unordered_map<const BasicBlock*, DomTreeNode> doms; |
| 277 | |
| 278 | void buildDominators(const CFG &cfg); |
| 279 | static DomTreeNode* intersect(DomTreeNode *b1, DomTreeNode *b2); |
| 280 | |
| 281 | public: |
| 282 | DomTree(const Function &f, const CFG &cfg) : f(f) { buildDominators(cfg); } |
| 283 | const BasicBlock* getIDominator(const BasicBlock &bb) const; |
| 284 | bool dominates(const BasicBlock *a, const BasicBlock *b) const; |
| 285 | void printDot(std::ostream &os) const; |
| 286 | }; |
| 287 | |
| 288 | |
| 289 | class LoopAnalysis final { |