1 //===- Dominators.cpp - Dominator Calculation -----------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements simple dominator construction algorithms for finding
11 // forward dominators. Postdominators are available in libanalysis, but are not
12 // included in libvmcore, because it's not needed. Forward dominators are
13 // needed to support the Verifier pass.
15 //===----------------------------------------------------------------------===//
17 #include "llvm/Analysis/Dominators.h"
18 #include "llvm/Support/CFG.h"
19 #include "llvm/Support/Compiler.h"
20 #include "llvm/ADT/DepthFirstIterator.h"
21 #include "llvm/ADT/SetOperations.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/Analysis/DominatorInternals.h"
25 #include "llvm/Instructions.h"
26 #include "llvm/Support/Streams.h"
31 static std::ostream &operator<<(std::ostream &o,
32 const std::set<BasicBlock*> &BBs) {
33 for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
36 WriteAsOperand(o, *I, false);
38 o << " <<exit node>>";
43 //===----------------------------------------------------------------------===//
44 // DominatorTree Implementation
45 //===----------------------------------------------------------------------===//
47 // Provide public access to DominatorTree information. Implementation details
48 // can be found in DominatorCalculation.h.
50 //===----------------------------------------------------------------------===//
52 TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>);
53 TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
55 char DominatorTree::ID = 0;
56 static RegisterPass<DominatorTree>
57 E("domtree", "Dominator Tree Construction", true);
59 bool DominatorTree::runOnFunction(Function &F) {
65 //===----------------------------------------------------------------------===//
66 // DominanceFrontier Implementation
67 //===----------------------------------------------------------------------===//
69 char DominanceFrontier::ID = 0;
70 static RegisterPass<DominanceFrontier>
71 G("domfrontier", "Dominance Frontier Construction", true);
73 // NewBB is split and now it has one successor. Update dominace frontier to
74 // reflect this change.
75 void DominanceFrontier::splitBlock(BasicBlock *NewBB) {
76 assert(NewBB->getTerminator()->getNumSuccessors() == 1
77 && "NewBB should have a single successor!");
78 BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0);
80 std::vector<BasicBlock*> PredBlocks;
81 for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB);
83 PredBlocks.push_back(*PI);
85 if (PredBlocks.empty())
86 // If NewBB does not have any predecessors then it is a entry block.
87 // In this case, NewBB and its successor NewBBSucc dominates all
91 // NewBBSucc inherits original NewBB frontier.
92 DominanceFrontier::iterator NewBBI = find(NewBB);
93 if (NewBBI != end()) {
94 DominanceFrontier::DomSetType NewBBSet = NewBBI->second;
95 DominanceFrontier::DomSetType NewBBSuccSet;
96 NewBBSuccSet.insert(NewBBSet.begin(), NewBBSet.end());
97 addBasicBlock(NewBBSucc, NewBBSuccSet);
100 // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the
101 // DF(PredBlocks[0]) without the stuff that the new block does not dominate
103 DominatorTree &DT = getAnalysis<DominatorTree>();
104 if (DT.dominates(NewBB, NewBBSucc)) {
105 DominanceFrontier::iterator DFI = find(PredBlocks[0]);
107 DominanceFrontier::DomSetType Set = DFI->second;
108 // Filter out stuff in Set that we do not dominate a predecessor of.
109 for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(),
110 E = Set.end(); SetI != E;) {
111 bool DominatesPred = false;
112 for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI);
114 if (DT.dominates(NewBB, *PI))
115 DominatesPred = true;
122 if (NewBBI != end()) {
123 for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(),
124 E = Set.end(); SetI != E; ++SetI) {
125 BasicBlock *SB = *SetI;
126 addToFrontier(NewBBI, SB);
129 addBasicBlock(NewBB, Set);
133 // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate
134 // NewBBSucc, but it does dominate itself (and there is an edge (NewBB ->
135 // NewBBSucc)). NewBBSucc is the single successor of NewBB.
136 DominanceFrontier::DomSetType NewDFSet;
137 NewDFSet.insert(NewBBSucc);
138 addBasicBlock(NewBB, NewDFSet);
141 // Now we must loop over all of the dominance frontiers in the function,
142 // replacing occurrences of NewBBSucc with NewBB in some cases. All
143 // blocks that dominate a block in PredBlocks and contained NewBBSucc in
144 // their dominance frontier must be updated to contain NewBB instead.
146 for (Function::iterator FI = NewBB->getParent()->begin(),
147 FE = NewBB->getParent()->end(); FI != FE; ++FI) {
148 DominanceFrontier::iterator DFI = find(FI);
149 if (DFI == end()) continue; // unreachable block.
151 // Only consider nodes that have NewBBSucc in their dominator frontier.
152 if (!DFI->second.count(NewBBSucc)) continue;
154 // Verify whether this block dominates a block in predblocks. If not, do
156 bool BlockDominatesAny = false;
157 for (std::vector<BasicBlock*>::const_iterator BI = PredBlocks.begin(),
158 BE = PredBlocks.end(); BI != BE; ++BI) {
159 if (DT.dominates(FI, *BI)) {
160 BlockDominatesAny = true;
165 if (!BlockDominatesAny)
168 // If NewBBSucc should not stay in our dominator frontier, remove it.
169 // We remove it unless there is a predecessor of NewBBSucc that we
170 // dominate, but we don't strictly dominate NewBBSucc.
171 bool ShouldRemove = true;
172 if ((BasicBlock*)FI == NewBBSucc || !DT.dominates(FI, NewBBSucc)) {
173 // Okay, we know that PredDom does not strictly dominate NewBBSucc.
174 // Check to see if it dominates any predecessors of NewBBSucc.
175 for (pred_iterator PI = pred_begin(NewBBSucc),
176 E = pred_end(NewBBSucc); PI != E; ++PI)
177 if (DT.dominates(FI, *PI)) {
178 ShouldRemove = false;
184 removeFromFrontier(DFI, NewBBSucc);
185 addToFrontier(DFI, NewBB);
190 class DFCalculateWorkObject {
192 DFCalculateWorkObject(BasicBlock *B, BasicBlock *P,
193 const DomTreeNode *N,
194 const DomTreeNode *PN)
195 : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
196 BasicBlock *currentBB;
197 BasicBlock *parentBB;
198 const DomTreeNode *Node;
199 const DomTreeNode *parentNode;
203 const DominanceFrontier::DomSetType &
204 DominanceFrontier::calculate(const DominatorTree &DT,
205 const DomTreeNode *Node) {
206 BasicBlock *BB = Node->getBlock();
207 DomSetType *Result = NULL;
209 std::vector<DFCalculateWorkObject> workList;
210 SmallPtrSet<BasicBlock *, 32> visited;
212 workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL));
214 DFCalculateWorkObject *currentW = &workList.back();
215 assert (currentW && "Missing work object.");
217 BasicBlock *currentBB = currentW->currentBB;
218 BasicBlock *parentBB = currentW->parentBB;
219 const DomTreeNode *currentNode = currentW->Node;
220 const DomTreeNode *parentNode = currentW->parentNode;
221 assert (currentBB && "Invalid work object. Missing current Basic Block");
222 assert (currentNode && "Invalid work object. Missing current Node");
223 DomSetType &S = Frontiers[currentBB];
225 // Visit each block only once.
226 if (visited.count(currentBB) == 0) {
227 visited.insert(currentBB);
229 // Loop over CFG successors to calculate DFlocal[currentNode]
230 for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB);
232 // Does Node immediately dominate this successor?
233 if (DT[*SI]->getIDom() != currentNode)
238 // At this point, S is DFlocal. Now we union in DFup's of our children...
239 // Loop through and visit the nodes that Node immediately dominates (Node's
240 // children in the IDomTree)
241 bool visitChild = false;
242 for (DomTreeNode::const_iterator NI = currentNode->begin(),
243 NE = currentNode->end(); NI != NE; ++NI) {
244 DomTreeNode *IDominee = *NI;
245 BasicBlock *childBB = IDominee->getBlock();
246 if (visited.count(childBB) == 0) {
247 workList.push_back(DFCalculateWorkObject(childBB, currentBB,
248 IDominee, currentNode));
253 // If all children are visited or there is any child then pop this block
254 // from the workList.
262 DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
263 DomSetType &parentSet = Frontiers[parentBB];
264 for (; CDFI != CDFE; ++CDFI) {
265 if (!DT.properlyDominates(parentNode, DT[*CDFI]))
266 parentSet.insert(*CDFI);
271 } while (!workList.empty());
276 void DominanceFrontierBase::print(std::ostream &o, const Module* ) const {
277 for (const_iterator I = begin(), E = end(); I != E; ++I) {
278 o << " DomFrontier for BB";
280 WriteAsOperand(o, I->first, false);
282 o << " <<exit node>>";
283 o << " is:\t" << I->second << "\n";
287 void DominanceFrontierBase::dump() {