1
//===- Dominators.cpp - Dominator Calculation -----------------------------===//
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
// 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/Support/Debug.h"
21
#include "llvm/ADT/DepthFirstIterator.h"
22
#include "llvm/ADT/SetOperations.h"
23
#include "llvm/ADT/SmallPtrSet.h"
24
#include "llvm/ADT/SmallVector.h"
25
#include "llvm/Analysis/DominatorInternals.h"
26
#include "llvm/Instructions.h"
27
#include "llvm/Support/raw_ostream.h"
28
#include "llvm/Support/CommandLine.h"
32
// Always verify dominfo if expensive checking is enabled.
34
static bool VerifyDomInfo = true;
36
static bool VerifyDomInfo = false;
38
static cl::opt<bool,true>
39
VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo),
40
cl::desc("Verify dominator info (time consuming)"));
42
//===----------------------------------------------------------------------===//
43
// DominatorTree Implementation
44
//===----------------------------------------------------------------------===//
46
// Provide public access to DominatorTree information. Implementation details
47
// can be found in DominatorCalculation.h.
49
//===----------------------------------------------------------------------===//
51
TEMPLATE_INSTANTIATION(class llvm::DomTreeNodeBase<BasicBlock>);
52
TEMPLATE_INSTANTIATION(class llvm::DominatorTreeBase<BasicBlock>);
54
char DominatorTree::ID = 0;
55
INITIALIZE_PASS(DominatorTree, "domtree",
56
"Dominator Tree Construction", true, true);
58
bool DominatorTree::runOnFunction(Function &F) {
63
void DominatorTree::verifyAnalysis() const {
64
if (!VerifyDomInfo) return;
66
Function &F = *getRoot()->getParent();
68
DominatorTree OtherDT;
69
OtherDT.getBase().recalculate(F);
70
assert(!compare(OtherDT) && "Invalid DominatorTree info!");
73
void DominatorTree::print(raw_ostream &OS, const Module *) const {
77
// dominates - Return true if A dominates a use in B. This performs the
78
// special checks necessary if A and B are in the same basic block.
79
bool DominatorTree::dominates(const Instruction *A, const Instruction *B) const{
80
const BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
82
// If A is an invoke instruction, its value is only available in this normal
84
if (const InvokeInst *II = dyn_cast<InvokeInst>(A))
85
BBA = II->getNormalDest();
87
if (BBA != BBB) return dominates(BBA, BBB);
89
// It is not possible to determine dominance between two PHI nodes
90
// based on their ordering.
91
if (isa<PHINode>(A) && isa<PHINode>(B))
94
// Loop through the basic block until we find A or B.
95
BasicBlock::const_iterator I = BBA->begin();
96
for (; &*I != A && &*I != B; ++I)
104
//===----------------------------------------------------------------------===//
105
// DominanceFrontier Implementation
106
//===----------------------------------------------------------------------===//
108
char DominanceFrontier::ID = 0;
109
INITIALIZE_PASS(DominanceFrontier, "domfrontier",
110
"Dominance Frontier Construction", true, true);
112
void DominanceFrontier::verifyAnalysis() const {
113
if (!VerifyDomInfo) return;
115
DominatorTree &DT = getAnalysis<DominatorTree>();
117
DominanceFrontier OtherDF;
118
const std::vector<BasicBlock*> &DTRoots = DT.getRoots();
119
OtherDF.calculate(DT, DT.getNode(DTRoots[0]));
120
assert(!compare(OtherDF) && "Invalid DominanceFrontier info!");
123
// NewBB is split and now it has one successor. Update dominance frontier to
124
// reflect this change.
125
void DominanceFrontier::splitBlock(BasicBlock *NewBB) {
126
assert(NewBB->getTerminator()->getNumSuccessors() == 1 &&
127
"NewBB should have a single successor!");
128
BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0);
130
// NewBBSucc inherits original NewBB frontier.
131
DominanceFrontier::iterator NewBBI = find(NewBB);
133
addBasicBlock(NewBBSucc, NewBBI->second);
135
// If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the
136
// DF(NewBBSucc) without the stuff that the new block does not dominate
138
DominatorTree &DT = getAnalysis<DominatorTree>();
139
DomTreeNode *NewBBNode = DT.getNode(NewBB);
140
DomTreeNode *NewBBSuccNode = DT.getNode(NewBBSucc);
141
if (DT.dominates(NewBBNode, NewBBSuccNode)) {
142
DominanceFrontier::iterator DFI = find(NewBBSucc);
144
DominanceFrontier::DomSetType Set = DFI->second;
145
// Filter out stuff in Set that we do not dominate a predecessor of.
146
for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(),
147
E = Set.end(); SetI != E;) {
148
bool DominatesPred = false;
149
for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI);
151
if (DT.dominates(NewBBNode, DT.getNode(*PI))) {
152
DominatesPred = true;
161
if (NewBBI != end()) {
162
for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(),
163
E = Set.end(); SetI != E; ++SetI) {
164
BasicBlock *SB = *SetI;
165
addToFrontier(NewBBI, SB);
168
addBasicBlock(NewBB, Set);
172
// DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate
173
// NewBBSucc, but it does dominate itself (and there is an edge (NewBB ->
174
// NewBBSucc)). NewBBSucc is the single successor of NewBB.
175
DominanceFrontier::DomSetType NewDFSet;
176
NewDFSet.insert(NewBBSucc);
177
addBasicBlock(NewBB, NewDFSet);
180
// Now update dominance frontiers which either used to contain NewBBSucc
181
// or which now need to include NewBB.
183
// Collect the set of blocks which dominate a predecessor of NewBB or
184
// NewSuccBB and which don't dominate both. This is an initial
185
// approximation of the blocks whose dominance frontiers will need updates.
186
SmallVector<DomTreeNode *, 16> AllPredDoms;
188
// Compute the block which dominates both NewBBSucc and NewBB. This is
189
// the immediate dominator of NewBBSucc unless NewBB dominates NewBBSucc.
190
// The code below which climbs dominator trees will stop at this point,
191
// because from this point up, dominance frontiers are unaffected.
192
DomTreeNode *DominatesBoth = 0;
194
DominatesBoth = NewBBSuccNode->getIDom();
195
if (DominatesBoth == NewBBNode)
196
DominatesBoth = NewBBNode->getIDom();
199
// Collect the set of all blocks which dominate a predecessor of NewBB.
200
SmallPtrSet<DomTreeNode *, 8> NewBBPredDoms;
201
for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB); PI != E; ++PI)
202
for (DomTreeNode *DTN = DT.getNode(*PI); DTN; DTN = DTN->getIDom()) {
203
if (DTN == DominatesBoth)
205
if (!NewBBPredDoms.insert(DTN))
207
AllPredDoms.push_back(DTN);
210
// Collect the set of all blocks which dominate a predecessor of NewSuccBB.
211
SmallPtrSet<DomTreeNode *, 8> NewBBSuccPredDoms;
212
for (pred_iterator PI = pred_begin(NewBBSucc),
213
E = pred_end(NewBBSucc); PI != E; ++PI)
214
for (DomTreeNode *DTN = DT.getNode(*PI); DTN; DTN = DTN->getIDom()) {
215
if (DTN == DominatesBoth)
217
if (!NewBBSuccPredDoms.insert(DTN))
219
if (!NewBBPredDoms.count(DTN))
220
AllPredDoms.push_back(DTN);
223
// Visit all relevant dominance frontiers and make any needed updates.
224
for (SmallVectorImpl<DomTreeNode *>::const_iterator I = AllPredDoms.begin(),
225
E = AllPredDoms.end(); I != E; ++I) {
226
DomTreeNode *DTN = *I;
227
iterator DFI = find((*I)->getBlock());
229
// Only consider nodes that have NewBBSucc in their dominator frontier.
230
if (DFI == end() || !DFI->second.count(NewBBSucc)) continue;
232
// If the block dominates a predecessor of NewBB but does not properly
233
// dominate NewBB itself, add NewBB to its dominance frontier.
234
if (NewBBPredDoms.count(DTN) &&
235
!DT.properlyDominates(DTN, NewBBNode))
236
addToFrontier(DFI, NewBB);
238
// If the block does not dominate a predecessor of NewBBSucc or
239
// properly dominates NewBBSucc itself, remove NewBBSucc from its
240
// dominance frontier.
241
if (!NewBBSuccPredDoms.count(DTN) ||
242
DT.properlyDominates(DTN, NewBBSuccNode))
243
removeFromFrontier(DFI, NewBBSucc);
248
class DFCalculateWorkObject {
250
DFCalculateWorkObject(BasicBlock *B, BasicBlock *P,
251
const DomTreeNode *N,
252
const DomTreeNode *PN)
253
: currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
254
BasicBlock *currentBB;
255
BasicBlock *parentBB;
256
const DomTreeNode *Node;
257
const DomTreeNode *parentNode;
261
const DominanceFrontier::DomSetType &
262
DominanceFrontier::calculate(const DominatorTree &DT,
263
const DomTreeNode *Node) {
264
BasicBlock *BB = Node->getBlock();
265
DomSetType *Result = NULL;
267
std::vector<DFCalculateWorkObject> workList;
268
SmallPtrSet<BasicBlock *, 32> visited;
270
workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL));
272
DFCalculateWorkObject *currentW = &workList.back();
273
assert (currentW && "Missing work object.");
275
BasicBlock *currentBB = currentW->currentBB;
276
BasicBlock *parentBB = currentW->parentBB;
277
const DomTreeNode *currentNode = currentW->Node;
278
const DomTreeNode *parentNode = currentW->parentNode;
279
assert (currentBB && "Invalid work object. Missing current Basic Block");
280
assert (currentNode && "Invalid work object. Missing current Node");
281
DomSetType &S = Frontiers[currentBB];
283
// Visit each block only once.
284
if (visited.count(currentBB) == 0) {
285
visited.insert(currentBB);
287
// Loop over CFG successors to calculate DFlocal[currentNode]
288
for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB);
290
// Does Node immediately dominate this successor?
291
if (DT[*SI]->getIDom() != currentNode)
296
// At this point, S is DFlocal. Now we union in DFup's of our children...
297
// Loop through and visit the nodes that Node immediately dominates (Node's
298
// children in the IDomTree)
299
bool visitChild = false;
300
for (DomTreeNode::const_iterator NI = currentNode->begin(),
301
NE = currentNode->end(); NI != NE; ++NI) {
302
DomTreeNode *IDominee = *NI;
303
BasicBlock *childBB = IDominee->getBlock();
304
if (visited.count(childBB) == 0) {
305
workList.push_back(DFCalculateWorkObject(childBB, currentBB,
306
IDominee, currentNode));
311
// If all children are visited or there is any child then pop this block
312
// from the workList.
320
DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
321
DomSetType &parentSet = Frontiers[parentBB];
322
for (; CDFI != CDFE; ++CDFI) {
323
if (!DT.properlyDominates(parentNode, DT[*CDFI]))
324
parentSet.insert(*CDFI);
329
} while (!workList.empty());
334
void DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const {
335
for (const_iterator I = begin(), E = end(); I != E; ++I) {
336
OS << " DomFrontier for BB ";
338
WriteAsOperand(OS, I->first, false);
340
OS << " <<exit node>>";
343
const std::set<BasicBlock*> &BBs = I->second;
345
for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
349
WriteAsOperand(OS, *I, false);
351
OS << "<<exit node>>";
357
void DominanceFrontierBase::dump() const {