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) {
60 reset(); // Reset from the last time we were run...
63 Roots.push_back(&F.getEntryBlock());
64 IDoms[&F.getEntryBlock()] = 0;
65 DomTreeNodes[&F.getEntryBlock()] = 0;
68 Calculate<BasicBlock*, GraphTraits<BasicBlock*> >(*this, F);
75 //===----------------------------------------------------------------------===//
76 // DominanceFrontier Implementation
77 //===----------------------------------------------------------------------===//
79 char DominanceFrontier::ID = 0;
80 static RegisterPass<DominanceFrontier>
81 G("domfrontier", "Dominance Frontier Construction", true);
83 // NewBB is split and now it has one successor. Update dominace frontier to
84 // reflect this change.
85 void DominanceFrontier::splitBlock(BasicBlock *NewBB) {
86 assert(NewBB->getTerminator()->getNumSuccessors() == 1
87 && "NewBB should have a single successor!");
88 BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0);
90 std::vector<BasicBlock*> PredBlocks;
91 for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB);
93 PredBlocks.push_back(*PI);
95 if (PredBlocks.empty())
96 // If NewBB does not have any predecessors then it is a entry block.
97 // In this case, NewBB and its successor NewBBSucc dominates all
101 // NewBBSucc inherits original NewBB frontier.
102 DominanceFrontier::iterator NewBBI = find(NewBB);
103 if (NewBBI != end()) {
104 DominanceFrontier::DomSetType NewBBSet = NewBBI->second;
105 DominanceFrontier::DomSetType NewBBSuccSet;
106 NewBBSuccSet.insert(NewBBSet.begin(), NewBBSet.end());
107 addBasicBlock(NewBBSucc, NewBBSuccSet);
110 // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the
111 // DF(PredBlocks[0]) without the stuff that the new block does not dominate
113 DominatorTree &DT = getAnalysis<DominatorTree>();
114 if (DT.dominates(NewBB, NewBBSucc)) {
115 DominanceFrontier::iterator DFI = find(PredBlocks[0]);
117 DominanceFrontier::DomSetType Set = DFI->second;
118 // Filter out stuff in Set that we do not dominate a predecessor of.
119 for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(),
120 E = Set.end(); SetI != E;) {
121 bool DominatesPred = false;
122 for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI);
124 if (DT.dominates(NewBB, *PI))
125 DominatesPred = true;
132 if (NewBBI != end()) {
133 for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(),
134 E = Set.end(); SetI != E; ++SetI) {
135 BasicBlock *SB = *SetI;
136 addToFrontier(NewBBI, SB);
139 addBasicBlock(NewBB, Set);
143 // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate
144 // NewBBSucc, but it does dominate itself (and there is an edge (NewBB ->
145 // NewBBSucc)). NewBBSucc is the single successor of NewBB.
146 DominanceFrontier::DomSetType NewDFSet;
147 NewDFSet.insert(NewBBSucc);
148 addBasicBlock(NewBB, NewDFSet);
151 // Now we must loop over all of the dominance frontiers in the function,
152 // replacing occurrences of NewBBSucc with NewBB in some cases. All
153 // blocks that dominate a block in PredBlocks and contained NewBBSucc in
154 // their dominance frontier must be updated to contain NewBB instead.
156 for (Function::iterator FI = NewBB->getParent()->begin(),
157 FE = NewBB->getParent()->end(); FI != FE; ++FI) {
158 DominanceFrontier::iterator DFI = find(FI);
159 if (DFI == end()) continue; // unreachable block.
161 // Only consider nodes that have NewBBSucc in their dominator frontier.
162 if (!DFI->second.count(NewBBSucc)) continue;
164 // Verify whether this block dominates a block in predblocks. If not, do
166 bool BlockDominatesAny = false;
167 for (std::vector<BasicBlock*>::const_iterator BI = PredBlocks.begin(),
168 BE = PredBlocks.end(); BI != BE; ++BI) {
169 if (DT.dominates(FI, *BI)) {
170 BlockDominatesAny = true;
175 if (!BlockDominatesAny)
178 // If NewBBSucc should not stay in our dominator frontier, remove it.
179 // We remove it unless there is a predecessor of NewBBSucc that we
180 // dominate, but we don't strictly dominate NewBBSucc.
181 bool ShouldRemove = true;
182 if ((BasicBlock*)FI == NewBBSucc || !DT.dominates(FI, NewBBSucc)) {
183 // Okay, we know that PredDom does not strictly dominate NewBBSucc.
184 // Check to see if it dominates any predecessors of NewBBSucc.
185 for (pred_iterator PI = pred_begin(NewBBSucc),
186 E = pred_end(NewBBSucc); PI != E; ++PI)
187 if (DT.dominates(FI, *PI)) {
188 ShouldRemove = false;
194 removeFromFrontier(DFI, NewBBSucc);
195 addToFrontier(DFI, NewBB);
200 class DFCalculateWorkObject {
202 DFCalculateWorkObject(BasicBlock *B, BasicBlock *P,
203 const DomTreeNode *N,
204 const DomTreeNode *PN)
205 : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
206 BasicBlock *currentBB;
207 BasicBlock *parentBB;
208 const DomTreeNode *Node;
209 const DomTreeNode *parentNode;
213 const DominanceFrontier::DomSetType &
214 DominanceFrontier::calculate(const DominatorTree &DT,
215 const DomTreeNode *Node) {
216 BasicBlock *BB = Node->getBlock();
217 DomSetType *Result = NULL;
219 std::vector<DFCalculateWorkObject> workList;
220 SmallPtrSet<BasicBlock *, 32> visited;
222 workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL));
224 DFCalculateWorkObject *currentW = &workList.back();
225 assert (currentW && "Missing work object.");
227 BasicBlock *currentBB = currentW->currentBB;
228 BasicBlock *parentBB = currentW->parentBB;
229 const DomTreeNode *currentNode = currentW->Node;
230 const DomTreeNode *parentNode = currentW->parentNode;
231 assert (currentBB && "Invalid work object. Missing current Basic Block");
232 assert (currentNode && "Invalid work object. Missing current Node");
233 DomSetType &S = Frontiers[currentBB];
235 // Visit each block only once.
236 if (visited.count(currentBB) == 0) {
237 visited.insert(currentBB);
239 // Loop over CFG successors to calculate DFlocal[currentNode]
240 for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB);
242 // Does Node immediately dominate this successor?
243 if (DT[*SI]->getIDom() != currentNode)
248 // At this point, S is DFlocal. Now we union in DFup's of our children...
249 // Loop through and visit the nodes that Node immediately dominates (Node's
250 // children in the IDomTree)
251 bool visitChild = false;
252 for (DomTreeNode::const_iterator NI = currentNode->begin(),
253 NE = currentNode->end(); NI != NE; ++NI) {
254 DomTreeNode *IDominee = *NI;
255 BasicBlock *childBB = IDominee->getBlock();
256 if (visited.count(childBB) == 0) {
257 workList.push_back(DFCalculateWorkObject(childBB, currentBB,
258 IDominee, currentNode));
263 // If all children are visited or there is any child then pop this block
264 // from the workList.
272 DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
273 DomSetType &parentSet = Frontiers[parentBB];
274 for (; CDFI != CDFE; ++CDFI) {
275 if (!DT.properlyDominates(parentNode, DT[*CDFI]))
276 parentSet.insert(*CDFI);
281 } while (!workList.empty());
286 void DominanceFrontierBase::print(std::ostream &o, const Module* ) const {
287 for (const_iterator I = begin(), E = end(); I != E; ++I) {
288 o << " DomFrontier for BB";
290 WriteAsOperand(o, I->first, false);
292 o << " <<exit node>>";
293 o << " is:\t" << I->second << "\n";
297 void DominanceFrontierBase::dump() {