1
//===- llvm/Analysis/Dominators.h - Dominator Info Calculation --*- C++ -*-===//
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 defines the following classes:
11
// 1. DominatorTree: Represent dominators as an explicit tree structure.
12
// 2. DominanceFrontier: Calculate and hold the dominance frontier for a
15
// These data structures are listed in increasing order of complexity. It
16
// takes longer to calculate the dominator frontier, for example, than the
17
// DominatorTree mapping.
19
//===----------------------------------------------------------------------===//
21
#ifndef LLVM_ANALYSIS_DOMINATORS_H
22
#define LLVM_ANALYSIS_DOMINATORS_H
24
#include "llvm/Pass.h"
25
#include "llvm/Function.h"
26
#include "llvm/Instructions.h"
27
#include "llvm/ADT/DenseMap.h"
28
#include "llvm/ADT/DepthFirstIterator.h"
29
#include "llvm/ADT/GraphTraits.h"
30
#include "llvm/ADT/SmallPtrSet.h"
31
#include "llvm/ADT/SmallVector.h"
32
#include "llvm/Assembly/Writer.h"
33
#include "llvm/Support/CFG.h"
34
#include "llvm/Support/Compiler.h"
35
#include "llvm/Support/raw_ostream.h"
42
//===----------------------------------------------------------------------===//
43
/// DominatorBase - Base class that other, more interesting dominator analyses
46
template <class NodeT>
49
std::vector<NodeT*> Roots;
50
const bool IsPostDominators;
51
inline explicit DominatorBase(bool isPostDom) :
52
Roots(), IsPostDominators(isPostDom) {}
55
/// getRoots - Return the root blocks of the current CFG. This may include
56
/// multiple blocks if we are computing post dominators. For forward
57
/// dominators, this will always be a single block (the entry node).
59
inline const std::vector<NodeT*> &getRoots() const { return Roots; }
61
/// isPostDominator - Returns true if analysis based of postdoms
63
bool isPostDominator() const { return IsPostDominators; }
67
//===----------------------------------------------------------------------===//
68
// DomTreeNode - Dominator Tree Node
69
template<class NodeT> class DominatorTreeBase;
70
struct PostDominatorTree;
71
class MachineBasicBlock;
73
template <class NodeT>
74
class DomTreeNodeBase {
76
DomTreeNodeBase<NodeT> *IDom;
77
std::vector<DomTreeNodeBase<NodeT> *> Children;
78
int DFSNumIn, DFSNumOut;
80
template<class N> friend class DominatorTreeBase;
81
friend struct PostDominatorTree;
83
typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator;
84
typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator
87
iterator begin() { return Children.begin(); }
88
iterator end() { return Children.end(); }
89
const_iterator begin() const { return Children.begin(); }
90
const_iterator end() const { return Children.end(); }
92
NodeT *getBlock() const { return TheBB; }
93
DomTreeNodeBase<NodeT> *getIDom() const { return IDom; }
94
const std::vector<DomTreeNodeBase<NodeT>*> &getChildren() const {
98
DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom)
99
: TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { }
101
DomTreeNodeBase<NodeT> *addChild(DomTreeNodeBase<NodeT> *C) {
102
Children.push_back(C);
106
size_t getNumChildren() const {
107
return Children.size();
110
void clearAllChildren() {
114
bool compare(DomTreeNodeBase<NodeT> *Other) {
115
if (getNumChildren() != Other->getNumChildren())
118
SmallPtrSet<NodeT *, 4> OtherChildren;
119
for (iterator I = Other->begin(), E = Other->end(); I != E; ++I) {
120
NodeT *Nd = (*I)->getBlock();
121
OtherChildren.insert(Nd);
124
for (iterator I = begin(), E = end(); I != E; ++I) {
125
NodeT *N = (*I)->getBlock();
126
if (OtherChildren.count(N) == 0)
132
void setIDom(DomTreeNodeBase<NodeT> *NewIDom) {
133
assert(IDom && "No immediate dominator?");
134
if (IDom != NewIDom) {
135
typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I =
136
std::find(IDom->Children.begin(), IDom->Children.end(), this);
137
assert(I != IDom->Children.end() &&
138
"Not in immediate dominator children set!");
139
// I am no longer your child...
140
IDom->Children.erase(I);
142
// Switch to new dominator
144
IDom->Children.push_back(this);
148
/// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do
150
unsigned getDFSNumIn() const { return DFSNumIn; }
151
unsigned getDFSNumOut() const { return DFSNumOut; }
153
// Return true if this node is dominated by other. Use this only if DFS info
155
bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const {
156
return this->DFSNumIn >= other->DFSNumIn &&
157
this->DFSNumOut <= other->DFSNumOut;
161
EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>);
162
EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>);
164
template<class NodeT>
165
static raw_ostream &operator<<(raw_ostream &o,
166
const DomTreeNodeBase<NodeT> *Node) {
167
if (Node->getBlock())
168
WriteAsOperand(o, Node->getBlock(), false);
170
o << " <<exit node>>";
172
o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}";
177
template<class NodeT>
178
static void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o,
180
o.indent(2*Lev) << "[" << Lev << "] " << N;
181
for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
182
E = N->end(); I != E; ++I)
183
PrintDomTree<NodeT>(*I, o, Lev+1);
186
typedef DomTreeNodeBase<BasicBlock> DomTreeNode;
188
//===----------------------------------------------------------------------===//
189
/// DominatorTree - Calculate the immediate dominator tree for a function.
192
template<class FuncT, class N>
193
void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT,
196
template<class NodeT>
197
class DominatorTreeBase : public DominatorBase<NodeT> {
199
typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> DomTreeNodeMapType;
200
DomTreeNodeMapType DomTreeNodes;
201
DomTreeNodeBase<NodeT> *RootNode;
204
unsigned int SlowQueries;
205
// Information record used during immediate dominators computation.
210
NodeT *Label, *Child;
211
unsigned Parent, Ancestor;
213
std::vector<NodeT*> Bucket;
215
InfoRec() : DFSNum(0), Semi(0), Size(0), Label(0), Child(0), Parent(0),
219
DenseMap<NodeT*, NodeT*> IDoms;
221
// Vertex - Map the DFS number to the BasicBlock*
222
std::vector<NodeT*> Vertex;
224
// Info - Collection of information used during the computation of idoms.
225
DenseMap<NodeT*, InfoRec> Info;
228
for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(),
229
E = DomTreeNodes.end(); I != E; ++I)
231
DomTreeNodes.clear();
238
// NewBB is split and now it has one successor. Update dominator tree to
239
// reflect this change.
240
template<class N, class GraphT>
241
void Split(DominatorTreeBase<typename GraphT::NodeType>& DT,
242
typename GraphT::NodeType* NewBB) {
243
assert(std::distance(GraphT::child_begin(NewBB),
244
GraphT::child_end(NewBB)) == 1 &&
245
"NewBB should have a single successor!");
246
typename GraphT::NodeType* NewBBSucc = *GraphT::child_begin(NewBB);
248
std::vector<typename GraphT::NodeType*> PredBlocks;
249
typedef GraphTraits<Inverse<N> > InvTraits;
250
for (typename InvTraits::ChildIteratorType PI =
251
InvTraits::child_begin(NewBB),
252
PE = InvTraits::child_end(NewBB); PI != PE; ++PI)
253
PredBlocks.push_back(*PI);
255
assert(!PredBlocks.empty() && "No predblocks?");
257
bool NewBBDominatesNewBBSucc = true;
258
for (typename InvTraits::ChildIteratorType PI =
259
InvTraits::child_begin(NewBBSucc),
260
E = InvTraits::child_end(NewBBSucc); PI != E; ++PI) {
261
typename InvTraits::NodeType *ND = *PI;
262
if (ND != NewBB && !DT.dominates(NewBBSucc, ND) &&
263
DT.isReachableFromEntry(ND)) {
264
NewBBDominatesNewBBSucc = false;
269
// Find NewBB's immediate dominator and create new dominator tree node for
271
NodeT *NewBBIDom = 0;
273
for (i = 0; i < PredBlocks.size(); ++i)
274
if (DT.isReachableFromEntry(PredBlocks[i])) {
275
NewBBIDom = PredBlocks[i];
279
// It's possible that none of the predecessors of NewBB are reachable;
280
// in that case, NewBB itself is unreachable, so nothing needs to be
285
for (i = i + 1; i < PredBlocks.size(); ++i) {
286
if (DT.isReachableFromEntry(PredBlocks[i]))
287
NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
290
// Create the new dominator tree node... and set the idom of NewBB.
291
DomTreeNodeBase<NodeT> *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom);
293
// If NewBB strictly dominates other blocks, then it is now the immediate
294
// dominator of NewBBSucc. Update the dominator tree as appropriate.
295
if (NewBBDominatesNewBBSucc) {
296
DomTreeNodeBase<NodeT> *NewBBSuccNode = DT.getNode(NewBBSucc);
297
DT.changeImmediateDominator(NewBBSuccNode, NewBBNode);
302
explicit DominatorTreeBase(bool isPostDom)
303
: DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {}
304
virtual ~DominatorTreeBase() { reset(); }
306
// FIXME: Should remove this
307
virtual bool runOnFunction(Function &F) { return false; }
309
/// compare - Return false if the other dominator tree base matches this
310
/// dominator tree base. Otherwise return true.
311
bool compare(DominatorTreeBase &Other) const {
313
const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
314
if (DomTreeNodes.size() != OtherDomTreeNodes.size())
317
for (typename DomTreeNodeMapType::const_iterator
318
I = this->DomTreeNodes.begin(),
319
E = this->DomTreeNodes.end(); I != E; ++I) {
320
NodeT *BB = I->first;
321
typename DomTreeNodeMapType::const_iterator OI = OtherDomTreeNodes.find(BB);
322
if (OI == OtherDomTreeNodes.end())
325
DomTreeNodeBase<NodeT>* MyNd = I->second;
326
DomTreeNodeBase<NodeT>* OtherNd = OI->second;
328
if (MyNd->compare(OtherNd))
335
virtual void releaseMemory() { reset(); }
337
/// getNode - return the (Post)DominatorTree node for the specified basic
338
/// block. This is the same as using operator[] on this class.
340
inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
341
typename DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB);
342
return I != DomTreeNodes.end() ? I->second : 0;
345
/// getRootNode - This returns the entry node for the CFG of the function. If
346
/// this tree represents the post-dominance relations for a function, however,
347
/// this root may be a node with the block == NULL. This is the case when
348
/// there are multiple exit nodes from a particular function. Consumers of
349
/// post-dominance information must be capable of dealing with this
352
DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
353
const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
355
/// properlyDominates - Returns true iff this dominates N and this != N.
356
/// Note that this is not a constant time operation!
358
bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
359
const DomTreeNodeBase<NodeT> *B) const {
360
if (A == 0 || B == 0) return false;
361
return dominatedBySlowTreeWalk(A, B);
364
inline bool properlyDominates(NodeT *A, NodeT *B) {
365
return properlyDominates(getNode(A), getNode(B));
368
bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
369
const DomTreeNodeBase<NodeT> *B) const {
370
const DomTreeNodeBase<NodeT> *IDom;
371
if (A == 0 || B == 0) return false;
372
while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B)
373
B = IDom; // Walk up the tree
378
/// isReachableFromEntry - Return true if A is dominated by the entry
379
/// block of the function containing it.
380
bool isReachableFromEntry(NodeT* A) {
381
assert(!this->isPostDominator() &&
382
"This is not implemented for post dominators");
383
return dominates(&A->getParent()->front(), A);
386
/// dominates - Returns true iff A dominates B. Note that this is not a
387
/// constant time operation!
389
inline bool dominates(const DomTreeNodeBase<NodeT> *A,
390
const DomTreeNodeBase<NodeT> *B) {
392
return true; // A node trivially dominates itself.
394
if (A == 0 || B == 0)
397
// Compare the result of the tree walk and the dfs numbers, if expensive
398
// checks are enabled.
400
assert((!DFSInfoValid ||
401
(dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
402
"Tree walk disagrees with dfs numbers!");
406
return B->DominatedBy(A);
408
// If we end up with too many slow queries, just update the
409
// DFS numbers on the theory that we are going to keep querying.
411
if (SlowQueries > 32) {
413
return B->DominatedBy(A);
416
return dominatedBySlowTreeWalk(A, B);
419
inline bool dominates(const NodeT *A, const NodeT *B) {
423
// Cast away the const qualifiers here. This is ok since
424
// this function doesn't actually return the values returned
426
return dominates(getNode(const_cast<NodeT *>(A)),
427
getNode(const_cast<NodeT *>(B)));
430
NodeT *getRoot() const {
431
assert(this->Roots.size() == 1 && "Should always have entry node!");
432
return this->Roots[0];
435
/// findNearestCommonDominator - Find nearest common dominator basic block
436
/// for basic block A and B. If there is no such block then return NULL.
437
NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) {
438
assert(A->getParent() == B->getParent() &&
439
"Two blocks are not in same function");
441
// If either A or B is a entry block then it is nearest common dominator
442
// (for forward-dominators).
443
if (!this->isPostDominator()) {
444
NodeT &Entry = A->getParent()->front();
445
if (A == &Entry || B == &Entry)
449
// If B dominates A then B is nearest common dominator.
453
// If A dominates B then A is nearest common dominator.
457
DomTreeNodeBase<NodeT> *NodeA = getNode(A);
458
DomTreeNodeBase<NodeT> *NodeB = getNode(B);
460
// Collect NodeA dominators set.
461
SmallPtrSet<DomTreeNodeBase<NodeT>*, 16> NodeADoms;
462
NodeADoms.insert(NodeA);
463
DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom();
465
NodeADoms.insert(IDomA);
466
IDomA = IDomA->getIDom();
469
// Walk NodeB immediate dominators chain and find common dominator node.
470
DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom();
472
if (NodeADoms.count(IDomB) != 0)
473
return IDomB->getBlock();
475
IDomB = IDomB->getIDom();
481
//===--------------------------------------------------------------------===//
482
// API to update (Post)DominatorTree information based on modifications to
485
/// addNewBlock - Add a new node to the dominator tree information. This
486
/// creates a new node as a child of DomBB dominator node,linking it into
487
/// the children list of the immediate dominator.
488
DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
489
assert(getNode(BB) == 0 && "Block already in dominator tree!");
490
DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
491
assert(IDomNode && "Not immediate dominator specified for block!");
492
DFSInfoValid = false;
493
return DomTreeNodes[BB] =
494
IDomNode->addChild(new DomTreeNodeBase<NodeT>(BB, IDomNode));
497
/// changeImmediateDominator - This method is used to update the dominator
498
/// tree information when a node's immediate dominator changes.
500
void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
501
DomTreeNodeBase<NodeT> *NewIDom) {
502
assert(N && NewIDom && "Cannot change null node pointers!");
503
DFSInfoValid = false;
507
void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
508
changeImmediateDominator(getNode(BB), getNode(NewBB));
511
/// eraseNode - Removes a node from the dominator tree. Block must not
512
/// domiante any other blocks. Removes node from its immediate dominator's
513
/// children list. Deletes dominator node associated with basic block BB.
514
void eraseNode(NodeT *BB) {
515
DomTreeNodeBase<NodeT> *Node = getNode(BB);
516
assert(Node && "Removing node that isn't in dominator tree.");
517
assert(Node->getChildren().empty() && "Node is not a leaf node.");
519
// Remove node from immediate dominator's children list.
520
DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
522
typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I =
523
std::find(IDom->Children.begin(), IDom->Children.end(), Node);
524
assert(I != IDom->Children.end() &&
525
"Not in immediate dominator children set!");
526
// I am no longer your child...
527
IDom->Children.erase(I);
530
DomTreeNodes.erase(BB);
534
/// removeNode - Removes a node from the dominator tree. Block must not
535
/// dominate any other blocks. Invalidates any node pointing to removed
537
void removeNode(NodeT *BB) {
538
assert(getNode(BB) && "Removing node that isn't in dominator tree.");
539
DomTreeNodes.erase(BB);
542
/// splitBlock - BB is split and now it has one successor. Update dominator
543
/// tree to reflect this change.
544
void splitBlock(NodeT* NewBB) {
545
if (this->IsPostDominators)
546
this->Split<Inverse<NodeT*>, GraphTraits<Inverse<NodeT*> > >(*this, NewBB);
548
this->Split<NodeT*, GraphTraits<NodeT*> >(*this, NewBB);
551
/// print - Convert to human readable form
553
void print(raw_ostream &o) const {
554
o << "=============================--------------------------------\n";
555
if (this->isPostDominator())
556
o << "Inorder PostDominator Tree: ";
558
o << "Inorder Dominator Tree: ";
559
if (this->DFSInfoValid)
560
o << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
563
// The postdom tree can have a null root if there are no returns.
565
PrintDomTree<NodeT>(getRootNode(), o, 1);
569
template<class GraphT>
570
friend void Compress(DominatorTreeBase<typename GraphT::NodeType>& DT,
571
typename GraphT::NodeType* VIn);
573
template<class GraphT>
574
friend typename GraphT::NodeType* Eval(
575
DominatorTreeBase<typename GraphT::NodeType>& DT,
576
typename GraphT::NodeType* V);
578
template<class GraphT>
579
friend void Link(DominatorTreeBase<typename GraphT::NodeType>& DT,
580
unsigned DFSNumV, typename GraphT::NodeType* W,
581
typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo);
583
template<class GraphT>
584
friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
585
typename GraphT::NodeType* V,
588
template<class FuncT, class N>
589
friend void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT,
592
/// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
593
/// dominator tree in dfs order.
594
void updateDFSNumbers() {
597
SmallVector<std::pair<DomTreeNodeBase<NodeT>*,
598
typename DomTreeNodeBase<NodeT>::iterator>, 32> WorkStack;
600
DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
605
// Even in the case of multiple exits that form the post dominator root
606
// nodes, do not iterate over all exits, but start from the virtual root
607
// node. Otherwise bbs, that are not post dominated by any exit but by the
608
// virtual root node, will never be assigned a DFS number.
609
WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin()));
610
ThisRoot->DFSNumIn = DFSNum++;
612
while (!WorkStack.empty()) {
613
DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
614
typename DomTreeNodeBase<NodeT>::iterator ChildIt =
615
WorkStack.back().second;
617
// If we visited all of the children of this node, "recurse" back up the
618
// stack setting the DFOutNum.
619
if (ChildIt == Node->end()) {
620
Node->DFSNumOut = DFSNum++;
621
WorkStack.pop_back();
623
// Otherwise, recursively visit this child.
624
DomTreeNodeBase<NodeT> *Child = *ChildIt;
625
++WorkStack.back().second;
627
WorkStack.push_back(std::make_pair(Child, Child->begin()));
628
Child->DFSNumIn = DFSNum++;
636
DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
637
typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.find(BB);
638
if (I != this->DomTreeNodes.end() && I->second)
641
// Haven't calculated this node yet? Get or calculate the node for the
642
// immediate dominator.
643
NodeT *IDom = getIDom(BB);
645
assert(IDom || this->DomTreeNodes[NULL]);
646
DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom);
648
// Add a new tree node for this BasicBlock, and link it as a child of
650
DomTreeNodeBase<NodeT> *C = new DomTreeNodeBase<NodeT>(BB, IDomNode);
651
return this->DomTreeNodes[BB] = IDomNode->addChild(C);
654
inline NodeT *getIDom(NodeT *BB) const {
655
typename DenseMap<NodeT*, NodeT*>::const_iterator I = IDoms.find(BB);
656
return I != IDoms.end() ? I->second : 0;
659
inline void addRoot(NodeT* BB) {
660
this->Roots.push_back(BB);
664
/// recalculate - compute a dominator tree for the given function
666
void recalculate(FT& F) {
668
this->Vertex.push_back(0);
670
if (!this->IsPostDominators) {
672
this->Roots.push_back(&F.front());
673
this->IDoms[&F.front()] = 0;
674
this->DomTreeNodes[&F.front()] = 0;
676
Calculate<FT, NodeT*>(*this, F);
678
// Initialize the roots list
679
for (typename FT::iterator I = F.begin(), E = F.end(); I != E; ++I) {
680
if (std::distance(GraphTraits<FT*>::child_begin(I),
681
GraphTraits<FT*>::child_end(I)) == 0)
684
// Prepopulate maps so that we don't get iterator invalidation issues later.
686
this->DomTreeNodes[I] = 0;
689
Calculate<FT, Inverse<NodeT*> >(*this, F);
694
EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
696
//===-------------------------------------
697
/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
698
/// compute a normal dominator tree.
700
class DominatorTree : public FunctionPass {
702
static char ID; // Pass ID, replacement for typeid
703
DominatorTreeBase<BasicBlock>* DT;
705
DominatorTree() : FunctionPass(ID) {
706
DT = new DominatorTreeBase<BasicBlock>(false);
713
DominatorTreeBase<BasicBlock>& getBase() { return *DT; }
715
/// getRoots - Return the root blocks of the current CFG. This may include
716
/// multiple blocks if we are computing post dominators. For forward
717
/// dominators, this will always be a single block (the entry node).
719
inline const std::vector<BasicBlock*> &getRoots() const {
720
return DT->getRoots();
723
inline BasicBlock *getRoot() const {
724
return DT->getRoot();
727
inline DomTreeNode *getRootNode() const {
728
return DT->getRootNode();
731
/// compare - Return false if the other dominator tree matches this
732
/// dominator tree. Otherwise return true.
733
inline bool compare(DominatorTree &Other) const {
734
DomTreeNode *R = getRootNode();
735
DomTreeNode *OtherR = Other.getRootNode();
737
if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
740
if (DT->compare(Other.getBase()))
746
virtual bool runOnFunction(Function &F);
748
virtual void verifyAnalysis() const;
750
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
751
AU.setPreservesAll();
754
inline bool dominates(DomTreeNode* A, DomTreeNode* B) const {
755
return DT->dominates(A, B);
758
inline bool dominates(const BasicBlock* A, const BasicBlock* B) const {
759
return DT->dominates(A, B);
762
// dominates - Return true if A dominates B. This performs the
763
// special checks necessary if A and B are in the same basic block.
764
bool dominates(const Instruction *A, const Instruction *B) const;
766
bool properlyDominates(const DomTreeNode *A, const DomTreeNode *B) const {
767
return DT->properlyDominates(A, B);
770
bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
771
return DT->properlyDominates(A, B);
774
/// findNearestCommonDominator - Find nearest common dominator basic block
775
/// for basic block A and B. If there is no such block then return NULL.
776
inline BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B) {
777
return DT->findNearestCommonDominator(A, B);
780
inline DomTreeNode *operator[](BasicBlock *BB) const {
781
return DT->getNode(BB);
784
/// getNode - return the (Post)DominatorTree node for the specified basic
785
/// block. This is the same as using operator[] on this class.
787
inline DomTreeNode *getNode(BasicBlock *BB) const {
788
return DT->getNode(BB);
791
/// addNewBlock - Add a new node to the dominator tree information. This
792
/// creates a new node as a child of DomBB dominator node,linking it into
793
/// the children list of the immediate dominator.
794
inline DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) {
795
return DT->addNewBlock(BB, DomBB);
798
/// changeImmediateDominator - This method is used to update the dominator
799
/// tree information when a node's immediate dominator changes.
801
inline void changeImmediateDominator(BasicBlock *N, BasicBlock* NewIDom) {
802
DT->changeImmediateDominator(N, NewIDom);
805
inline void changeImmediateDominator(DomTreeNode *N, DomTreeNode* NewIDom) {
806
DT->changeImmediateDominator(N, NewIDom);
809
/// eraseNode - Removes a node from the dominator tree. Block must not
810
/// domiante any other blocks. Removes node from its immediate dominator's
811
/// children list. Deletes dominator node associated with basic block BB.
812
inline void eraseNode(BasicBlock *BB) {
816
/// splitBlock - BB is split and now it has one successor. Update dominator
817
/// tree to reflect this change.
818
inline void splitBlock(BasicBlock* NewBB) {
819
DT->splitBlock(NewBB);
822
bool isReachableFromEntry(BasicBlock* A) {
823
return DT->isReachableFromEntry(A);
827
virtual void releaseMemory() {
831
virtual void print(raw_ostream &OS, const Module* M= 0) const;
834
//===-------------------------------------
835
/// DominatorTree GraphTraits specialization so the DominatorTree can be
836
/// iterable by generic graph iterators.
838
template <> struct GraphTraits<DomTreeNode*> {
839
typedef DomTreeNode NodeType;
840
typedef NodeType::iterator ChildIteratorType;
842
static NodeType *getEntryNode(NodeType *N) {
845
static inline ChildIteratorType child_begin(NodeType *N) {
848
static inline ChildIteratorType child_end(NodeType *N) {
852
typedef df_iterator<DomTreeNode*> nodes_iterator;
854
static nodes_iterator nodes_begin(DomTreeNode *N) {
855
return df_begin(getEntryNode(N));
858
static nodes_iterator nodes_end(DomTreeNode *N) {
859
return df_end(getEntryNode(N));
863
template <> struct GraphTraits<DominatorTree*>
864
: public GraphTraits<DomTreeNode*> {
865
static NodeType *getEntryNode(DominatorTree *DT) {
866
return DT->getRootNode();
869
static nodes_iterator nodes_begin(DominatorTree *N) {
870
return df_begin(getEntryNode(N));
873
static nodes_iterator nodes_end(DominatorTree *N) {
874
return df_end(getEntryNode(N));
879
//===----------------------------------------------------------------------===//
880
/// DominanceFrontierBase - Common base class for computing forward and inverse
881
/// dominance frontiers for a function.
883
class DominanceFrontierBase : public FunctionPass {
885
typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
886
typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
888
DomSetMapType Frontiers;
889
std::vector<BasicBlock*> Roots;
890
const bool IsPostDominators;
893
DominanceFrontierBase(char &ID, bool isPostDom)
894
: FunctionPass(ID), IsPostDominators(isPostDom) {}
896
/// getRoots - Return the root blocks of the current CFG. This may include
897
/// multiple blocks if we are computing post dominators. For forward
898
/// dominators, this will always be a single block (the entry node).
900
inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
902
/// isPostDominator - Returns true if analysis based of postdoms
904
bool isPostDominator() const { return IsPostDominators; }
906
virtual void releaseMemory() { Frontiers.clear(); }
908
// Accessor interface:
909
typedef DomSetMapType::iterator iterator;
910
typedef DomSetMapType::const_iterator const_iterator;
911
iterator begin() { return Frontiers.begin(); }
912
const_iterator begin() const { return Frontiers.begin(); }
913
iterator end() { return Frontiers.end(); }
914
const_iterator end() const { return Frontiers.end(); }
915
iterator find(BasicBlock *B) { return Frontiers.find(B); }
916
const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
918
iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
919
assert(find(BB) == end() && "Block already in DominanceFrontier!");
920
return Frontiers.insert(std::make_pair(BB, frontier)).first;
923
/// removeBlock - Remove basic block BB's frontier.
924
void removeBlock(BasicBlock *BB) {
925
assert(find(BB) != end() && "Block is not in DominanceFrontier!");
926
for (iterator I = begin(), E = end(); I != E; ++I)
931
void addToFrontier(iterator I, BasicBlock *Node) {
932
assert(I != end() && "BB is not in DominanceFrontier!");
933
I->second.insert(Node);
936
void removeFromFrontier(iterator I, BasicBlock *Node) {
937
assert(I != end() && "BB is not in DominanceFrontier!");
938
assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
939
I->second.erase(Node);
942
/// compareDomSet - Return false if two domsets match. Otherwise
944
bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const {
945
std::set<BasicBlock *> tmpSet;
946
for (DomSetType::const_iterator I = DS2.begin(),
947
E = DS2.end(); I != E; ++I)
950
for (DomSetType::const_iterator I = DS1.begin(),
951
E = DS1.end(); I != E; ) {
952
BasicBlock *Node = *I++;
954
if (tmpSet.erase(Node) == 0)
955
// Node is in DS1 but not in DS2.
960
// There are nodes that are in DS2 but not in DS1.
963
// DS1 and DS2 matches.
967
/// compare - Return true if the other dominance frontier base matches
968
/// this dominance frontier base. Otherwise return false.
969
bool compare(DominanceFrontierBase &Other) const {
970
DomSetMapType tmpFrontiers;
971
for (DomSetMapType::const_iterator I = Other.begin(),
972
E = Other.end(); I != E; ++I)
973
tmpFrontiers.insert(std::make_pair(I->first, I->second));
975
for (DomSetMapType::iterator I = tmpFrontiers.begin(),
976
E = tmpFrontiers.end(); I != E; ) {
977
BasicBlock *Node = I->first;
978
const_iterator DFI = find(Node);
982
if (compareDomSet(I->second, DFI->second))
986
tmpFrontiers.erase(Node);
989
if (!tmpFrontiers.empty())
995
/// print - Convert to human readable form
997
virtual void print(raw_ostream &OS, const Module* = 0) const;
999
/// dump - Dump the dominance frontier to dbgs().
1004
//===-------------------------------------
1005
/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
1006
/// used to compute a forward dominator frontiers.
1008
class DominanceFrontier : public DominanceFrontierBase {
1010
static char ID; // Pass ID, replacement for typeid
1011
DominanceFrontier() :
1012
DominanceFrontierBase(ID, false) {}
1014
BasicBlock *getRoot() const {
1015
assert(Roots.size() == 1 && "Should always have entry node!");
1019
virtual bool runOnFunction(Function &) {
1021
DominatorTree &DT = getAnalysis<DominatorTree>();
1022
Roots = DT.getRoots();
1023
assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
1024
calculate(DT, DT[Roots[0]]);
1028
virtual void verifyAnalysis() const;
1030
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1031
AU.setPreservesAll();
1032
AU.addRequired<DominatorTree>();
1035
/// splitBlock - BB is split and now it has one successor. Update dominance
1036
/// frontier to reflect this change.
1037
void splitBlock(BasicBlock *BB);
1039
/// BasicBlock BB's new dominator is NewBB. Update BB's dominance frontier
1040
/// to reflect this change.
1041
void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB,
1042
DominatorTree *DT) {
1043
// NewBB is now dominating BB. Which means BB's dominance
1044
// frontier is now part of NewBB's dominance frontier. However, BB
1045
// itself is not member of NewBB's dominance frontier.
1046
DominanceFrontier::iterator NewDFI = find(NewBB);
1047
DominanceFrontier::iterator DFI = find(BB);
1048
// If BB was an entry block then its frontier is empty.
1051
DominanceFrontier::DomSetType BBSet = DFI->second;
1052
for (DominanceFrontier::DomSetType::iterator BBSetI = BBSet.begin(),
1053
BBSetE = BBSet.end(); BBSetI != BBSetE; ++BBSetI) {
1054
BasicBlock *DFMember = *BBSetI;
1055
// Insert only if NewBB dominates DFMember.
1056
if (!DT->dominates(NewBB, DFMember))
1057
NewDFI->second.insert(DFMember);
1059
NewDFI->second.erase(BB);
1062
const DomSetType &calculate(const DominatorTree &DT,
1063
const DomTreeNode *Node);
1067
} // End llvm namespace
added
removed
libclamav/c++/llvm/include/llvm/Analysis/Dominators.h
