1 //===- IteratedDominanceFrontier.cpp - Compute IDF ------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Compute iterated dominance frontiers using a linear time algorithm.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Analysis/IteratedDominanceFrontier.h"
15 #include "llvm/IR/CFG.h"
16 #include "llvm/IR/Dominators.h"
20 template <class NodeTy, bool IsPostDom>
21 void IDFCalculator<NodeTy, IsPostDom>::calculate(
22 SmallVectorImpl<BasicBlock *> &PHIBlocks) {
23 // Use a priority queue keyed on dominator tree level so that inserted nodes
24 // are handled from the bottom of the dominator tree upwards.
25 typedef std::pair<DomTreeNode *, unsigned> DomTreeNodePair;
26 typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
27 less_second> IDFPriorityQueue;
30 for (BasicBlock *BB : *DefBlocks) {
31 if (DomTreeNode *Node = DT.getNode(BB))
32 PQ.push({Node, Node->getLevel()});
35 SmallVector<DomTreeNode *, 32> Worklist;
36 SmallPtrSet<DomTreeNode *, 32> VisitedPQ;
37 SmallPtrSet<DomTreeNode *, 32> VisitedWorklist;
40 DomTreeNodePair RootPair = PQ.top();
42 DomTreeNode *Root = RootPair.first;
43 unsigned RootLevel = RootPair.second;
45 // Walk all dominator tree children of Root, inspecting their CFG edges with
46 // targets elsewhere on the dominator tree. Only targets whose level is at
47 // most Root's level are added to the iterated dominance frontier of the
51 Worklist.push_back(Root);
52 VisitedWorklist.insert(Root);
54 while (!Worklist.empty()) {
55 DomTreeNode *Node = Worklist.pop_back_val();
56 BasicBlock *BB = Node->getBlock();
57 // Succ is the successor in the direction we are calculating IDF, so it is
58 // successor for IDF, and predecessor for Reverse IDF.
59 for (auto *Succ : children<NodeTy>(BB)) {
60 DomTreeNode *SuccNode = DT.getNode(Succ);
62 // Quickly skip all CFG edges that are also dominator tree edges instead
63 // of catching them below.
64 if (SuccNode->getIDom() == Node)
67 const unsigned SuccLevel = SuccNode->getLevel();
68 if (SuccLevel > RootLevel)
71 if (!VisitedPQ.insert(SuccNode).second)
74 BasicBlock *SuccBB = SuccNode->getBlock();
75 if (useLiveIn && !LiveInBlocks->count(SuccBB))
78 PHIBlocks.emplace_back(SuccBB);
79 if (!DefBlocks->count(SuccBB))
80 PQ.push(std::make_pair(SuccNode, SuccLevel));
83 for (auto DomChild : *Node) {
84 if (VisitedWorklist.insert(DomChild).second)
85 Worklist.push_back(DomChild);
91 template class IDFCalculator<BasicBlock *, false>;
92 template class IDFCalculator<Inverse<BasicBlock *>, true>;