//
//===----------------------------------------------------------------------===//
//
-// This file defines the following classes:
-// 1. DominatorTree: Represent dominators as an explicit tree structure.
-// 2. DominanceFrontier: Calculate and hold the dominance frontier for a
-// function.
-//
-// These data structures are listed in increasing order of complexity. It
-// takes longer to calculate the dominator frontier, for example, than the
-// DominatorTree mapping.
+// This file defines the DominatorTree class, which provides fast and efficient
+// dominance queries.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_DOMINATORS_H
#define LLVM_ANALYSIS_DOMINATORS_H
-#include "llvm/Pass.h"
-#include "llvm/Function.h"
-#include "llvm/Instructions.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
-#include "llvm/Assembly/Writer.h"
+#include "llvm/Function.h"
+#include "llvm/Pass.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
-#include <map>
-#include <set>
namespace llvm {
EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>);
template<class NodeT>
-static raw_ostream &operator<<(raw_ostream &o,
+inline raw_ostream &operator<<(raw_ostream &o,
const DomTreeNodeBase<NodeT> *Node) {
if (Node->getBlock())
WriteAsOperand(o, Node->getBlock(), false);
}
template<class NodeT>
-static void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o,
+inline void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o,
unsigned Lev) {
o.indent(2*Lev) << "[" << Lev << "] " << N;
for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
template<class NodeT>
class DominatorTreeBase : public DominatorBase<NodeT> {
+ bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
+ const DomTreeNodeBase<NodeT> *B) const {
+ assert(A != B);
+ assert(isReachableFromEntry(B));
+ assert(isReachableFromEntry(A));
+
+ const DomTreeNodeBase<NodeT> *IDom;
+ while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B)
+ B = IDom; // Walk up the tree
+ return IDom != 0;
+ }
+
protected:
typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> DomTreeNodeMapType;
DomTreeNodeMapType DomTreeNodes;
// Information record used during immediate dominators computation.
struct InfoRec {
unsigned DFSNum;
+ unsigned Parent;
unsigned Semi;
- unsigned Size;
- NodeT *Label, *Child;
- unsigned Parent, Ancestor;
+ NodeT *Label;
- std::vector<NodeT*> Bucket;
-
- InfoRec() : DFSNum(0), Semi(0), Size(0), Label(0), Child(0), Parent(0),
- Ancestor(0) {}
+ InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(0) {}
};
DenseMap<NodeT*, NodeT*> IDoms;
: DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {}
virtual ~DominatorTreeBase() { reset(); }
- // FIXME: Should remove this
- virtual bool runOnFunction(Function &F) { return false; }
-
/// compare - Return false if the other dominator tree base matches this
/// dominator tree base. Otherwise return true.
bool compare(DominatorTreeBase &Other) const {
/// block. This is the same as using operator[] on this class.
///
inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
- typename DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB);
- return I != DomTreeNodes.end() ? I->second : 0;
+ return DomTreeNodes.lookup(BB);
}
/// getRootNode - This returns the entry node for the CFG of the function. If
DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
- /// properlyDominates - Returns true iff this dominates N and this != N.
+ /// properlyDominates - Returns true iff A dominates B and A != B.
/// Note that this is not a constant time operation!
///
bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
- const DomTreeNodeBase<NodeT> *B) const {
- if (A == 0 || B == 0) return false;
- return dominatedBySlowTreeWalk(A, B);
- }
-
- inline bool properlyDominates(NodeT *A, NodeT *B) {
- return properlyDominates(getNode(A), getNode(B));
- }
-
- bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
- const DomTreeNodeBase<NodeT> *B) const {
- const DomTreeNodeBase<NodeT> *IDom;
- if (A == 0 || B == 0) return false;
- while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B)
- B = IDom; // Walk up the tree
- return IDom != 0;
+ const DomTreeNodeBase<NodeT> *B) {
+ if (A == 0 || B == 0)
+ return false;
+ if (A == B)
+ return false;
+ return dominates(A, B);
}
+ bool properlyDominates(const NodeT *A, const NodeT *B);
/// isReachableFromEntry - Return true if A is dominated by the entry
/// block of the function containing it.
- bool isReachableFromEntry(NodeT* A) {
+ bool isReachableFromEntry(const NodeT* A) const {
assert(!this->isPostDominator() &&
"This is not implemented for post dominators");
- return dominates(&A->getParent()->front(), A);
+ return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
+ }
+
+ inline bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const {
+ return A;
}
/// dominates - Returns true iff A dominates B. Note that this is not a
///
inline bool dominates(const DomTreeNodeBase<NodeT> *A,
const DomTreeNodeBase<NodeT> *B) {
+ // A node trivially dominates itself.
if (B == A)
- return true; // A node trivially dominates itself.
+ return true;
- if (A == 0 || B == 0)
+ // An unreachable node is dominated by anything.
+ if (!isReachableFromEntry(B))
+ return true;
+
+ // And dominates nothing.
+ if (!isReachableFromEntry(A))
return false;
// Compare the result of the tree walk and the dfs numbers, if expensive
return dominatedBySlowTreeWalk(A, B);
}
- inline bool dominates(const NodeT *A, const NodeT *B) {
- if (A == B)
- return true;
-
- // Cast away the const qualifiers here. This is ok since
- // this function doesn't actually return the values returned
- // from getNode.
- return dominates(getNode(const_cast<NodeT *>(A)),
- getNode(const_cast<NodeT *>(B)));
- }
+ bool dominates(const NodeT *A, const NodeT *B);
NodeT *getRoot() const {
assert(this->Roots.size() == 1 && "Should always have entry node!");
return NULL;
}
+ const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) {
+ // Cast away the const qualifiers here. This is ok since
+ // const is re-introduced on the return type.
+ return findNearestCommonDominator(const_cast<NodeT *>(A),
+ const_cast<NodeT *>(B));
+ }
+
//===--------------------------------------------------------------------===//
// API to update (Post)DominatorTree information based on modifications to
// the CFG...
}
/// eraseNode - Removes a node from the dominator tree. Block must not
- /// domiante any other blocks. Removes node from its immediate dominator's
+ /// dominate any other blocks. Removes node from its immediate dominator's
/// children list. Deletes dominator node associated with basic block BB.
void eraseNode(NodeT *BB) {
DomTreeNodeBase<NodeT> *Node = getNode(BB);
o << "Inorder PostDominator Tree: ";
else
o << "Inorder Dominator Tree: ";
- if (this->DFSInfoValid)
+ if (!this->DFSInfoValid)
o << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
o << "\n";
}
protected:
- template<class GraphT>
- friend void Compress(DominatorTreeBase<typename GraphT::NodeType>& DT,
- typename GraphT::NodeType* VIn);
-
template<class GraphT>
friend typename GraphT::NodeType* Eval(
DominatorTreeBase<typename GraphT::NodeType>& DT,
- typename GraphT::NodeType* V);
-
- template<class GraphT>
- friend void Link(DominatorTreeBase<typename GraphT::NodeType>& DT,
- unsigned DFSNumV, typename GraphT::NodeType* W,
- typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo);
+ typename GraphT::NodeType* V,
+ unsigned LastLinked);
template<class GraphT>
friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
}
DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
- typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.find(BB);
- if (I != this->DomTreeNodes.end() && I->second)
- return I->second;
+ if (DomTreeNodeBase<NodeT> *Node = getNode(BB))
+ return Node;
// Haven't calculated this node yet? Get or calculate the node for the
// immediate dominator.
}
inline NodeT *getIDom(NodeT *BB) const {
- typename DenseMap<NodeT*, NodeT*>::const_iterator I = IDoms.find(BB);
- return I != IDoms.end() ? I->second : 0;
+ return IDoms.lookup(BB);
}
inline void addRoot(NodeT* BB) {
/// recalculate - compute a dominator tree for the given function
template<class FT>
void recalculate(FT& F) {
+ typedef GraphTraits<FT*> TraitsTy;
reset();
this->Vertex.push_back(0);
if (!this->IsPostDominators) {
// Initialize root
- this->Roots.push_back(&F.front());
- this->IDoms[&F.front()] = 0;
- this->DomTreeNodes[&F.front()] = 0;
+ NodeT *entry = TraitsTy::getEntryNode(&F);
+ this->Roots.push_back(entry);
+ this->IDoms[entry] = 0;
+ this->DomTreeNodes[entry] = 0;
Calculate<FT, NodeT*>(*this, F);
} else {
// Initialize the roots list
- for (typename FT::iterator I = F.begin(), E = F.end(); I != E; ++I) {
- if (std::distance(GraphTraits<FT*>::child_begin(I),
- GraphTraits<FT*>::child_end(I)) == 0)
+ for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F),
+ E = TraitsTy::nodes_end(&F); I != E; ++I) {
+ if (std::distance(TraitsTy::child_begin(I),
+ TraitsTy::child_end(I)) == 0)
addRoot(I);
// Prepopulate maps so that we don't get iterator invalidation issues later.
}
};
+// These two functions are declared out of line as a workaround for building
+// with old (< r147295) versions of clang because of pr11642.
+template<class NodeT>
+bool DominatorTreeBase<NodeT>::dominates(const NodeT *A, const NodeT *B) {
+ if (A == B)
+ return true;
+
+ // Cast away the const qualifiers here. This is ok since
+ // this function doesn't actually return the values returned
+ // from getNode.
+ return dominates(getNode(const_cast<NodeT *>(A)),
+ getNode(const_cast<NodeT *>(B)));
+}
+template<class NodeT>
+bool
+DominatorTreeBase<NodeT>::properlyDominates(const NodeT *A, const NodeT *B) {
+ if (A == B)
+ return false;
+
+ // Cast away the const qualifiers here. This is ok since
+ // this function doesn't actually return the values returned
+ // from getNode.
+ return dominates(getNode(const_cast<NodeT *>(A)),
+ getNode(const_cast<NodeT *>(B)));
+}
+
EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
+class BasicBlockEdge {
+ const BasicBlock *Start;
+ const BasicBlock *End;
+public:
+ BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :
+ Start(Start_), End(End_) { }
+ const BasicBlock *getStart() const {
+ return Start;
+ }
+ const BasicBlock *getEnd() const {
+ return End;
+ }
+ bool isSingleEdge() const;
+};
+
//===-------------------------------------
/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
/// compute a normal dominator tree.
static char ID; // Pass ID, replacement for typeid
DominatorTreeBase<BasicBlock>* DT;
- DominatorTree() : FunctionPass(&ID) {
+ DominatorTree() : FunctionPass(ID) {
+ initializeDominatorTreePass(*PassRegistry::getPassRegistry());
DT = new DominatorTreeBase<BasicBlock>(false);
}
AU.setPreservesAll();
}
- inline bool dominates(DomTreeNode* A, DomTreeNode* B) const {
+ inline bool dominates(const DomTreeNode* A, const DomTreeNode* B) const {
return DT->dominates(A, B);
}
return DT->dominates(A, B);
}
- // dominates - Return true if A dominates B. This performs the
- // special checks necessary if A and B are in the same basic block.
- bool dominates(const Instruction *A, const Instruction *B) const;
+ // dominates - Return true if Def dominates a use in User. This performs
+ // the special checks necessary if Def and User are in the same basic block.
+ // Note that Def doesn't dominate a use in Def itself!
+ bool dominates(const Instruction *Def, const Use &U) const;
+ bool dominates(const Instruction *Def, const Instruction *User) const;
+ bool dominates(const Instruction *Def, const BasicBlock *BB) const;
+ bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
+ bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
bool properlyDominates(const DomTreeNode *A, const DomTreeNode *B) const {
return DT->properlyDominates(A, B);
}
- bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
+ bool properlyDominates(const BasicBlock *A, const BasicBlock *B) const {
return DT->properlyDominates(A, B);
}
return DT->findNearestCommonDominator(A, B);
}
+ inline const BasicBlock *findNearestCommonDominator(const BasicBlock *A,
+ const BasicBlock *B) {
+ return DT->findNearestCommonDominator(A, B);
+ }
+
inline DomTreeNode *operator[](BasicBlock *BB) const {
return DT->getNode(BB);
}
}
/// eraseNode - Removes a node from the dominator tree. Block must not
- /// domiante any other blocks. Removes node from its immediate dominator's
+ /// dominate any other blocks. Removes node from its immediate dominator's
/// children list. Deletes dominator node associated with basic block BB.
inline void eraseNode(BasicBlock *BB) {
DT->eraseNode(BB);
DT->splitBlock(NewBB);
}
- bool isReachableFromEntry(BasicBlock* A) {
+ bool isReachableFromEntry(const BasicBlock* A) const {
return DT->isReachableFromEntry(A);
}
+ bool isReachableFromEntry(const Use &U) const;
+
virtual void releaseMemory() {
DT->releaseMemory();
};
-//===----------------------------------------------------------------------===//
-/// DominanceFrontierBase - Common base class for computing forward and inverse
-/// dominance frontiers for a function.
-///
-class DominanceFrontierBase : public FunctionPass {
-public:
- typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb
- typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
-protected:
- DomSetMapType Frontiers;
- std::vector<BasicBlock*> Roots;
- const bool IsPostDominators;
-
-public:
- DominanceFrontierBase(void *ID, bool isPostDom)
- : FunctionPass(ID), IsPostDominators(isPostDom) {}
-
- /// getRoots - Return the root blocks of the current CFG. This may include
- /// multiple blocks if we are computing post dominators. For forward
- /// dominators, this will always be a single block (the entry node).
- ///
- inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
-
- /// isPostDominator - Returns true if analysis based of postdoms
- ///
- bool isPostDominator() const { return IsPostDominators; }
-
- virtual void releaseMemory() { Frontiers.clear(); }
-
- // Accessor interface:
- typedef DomSetMapType::iterator iterator;
- typedef DomSetMapType::const_iterator const_iterator;
- iterator begin() { return Frontiers.begin(); }
- const_iterator begin() const { return Frontiers.begin(); }
- iterator end() { return Frontiers.end(); }
- const_iterator end() const { return Frontiers.end(); }
- iterator find(BasicBlock *B) { return Frontiers.find(B); }
- const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
-
- iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
- assert(find(BB) == end() && "Block already in DominanceFrontier!");
- return Frontiers.insert(std::make_pair(BB, frontier)).first;
- }
-
- /// removeBlock - Remove basic block BB's frontier.
- void removeBlock(BasicBlock *BB) {
- assert(find(BB) != end() && "Block is not in DominanceFrontier!");
- for (iterator I = begin(), E = end(); I != E; ++I)
- I->second.erase(BB);
- Frontiers.erase(BB);
- }
-
- void addToFrontier(iterator I, BasicBlock *Node) {
- assert(I != end() && "BB is not in DominanceFrontier!");
- I->second.insert(Node);
- }
-
- void removeFromFrontier(iterator I, BasicBlock *Node) {
- assert(I != end() && "BB is not in DominanceFrontier!");
- assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
- I->second.erase(Node);
- }
-
- /// compareDomSet - Return false if two domsets match. Otherwise
- /// return true;
- bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const {
- std::set<BasicBlock *> tmpSet;
- for (DomSetType::const_iterator I = DS2.begin(),
- E = DS2.end(); I != E; ++I)
- tmpSet.insert(*I);
-
- for (DomSetType::const_iterator I = DS1.begin(),
- E = DS1.end(); I != E; ) {
- BasicBlock *Node = *I++;
-
- if (tmpSet.erase(Node) == 0)
- // Node is in DS1 but not in DS2.
- return true;
- }
-
- if (!tmpSet.empty())
- // There are nodes that are in DS2 but not in DS1.
- return true;
-
- // DS1 and DS2 matches.
- return false;
- }
-
- /// compare - Return true if the other dominance frontier base matches
- /// this dominance frontier base. Otherwise return false.
- bool compare(DominanceFrontierBase &Other) const {
- DomSetMapType tmpFrontiers;
- for (DomSetMapType::const_iterator I = Other.begin(),
- E = Other.end(); I != E; ++I)
- tmpFrontiers.insert(std::make_pair(I->first, I->second));
-
- for (DomSetMapType::iterator I = tmpFrontiers.begin(),
- E = tmpFrontiers.end(); I != E; ) {
- BasicBlock *Node = I->first;
- const_iterator DFI = find(Node);
- if (DFI == end())
- return true;
-
- if (compareDomSet(I->second, DFI->second))
- return true;
-
- ++I;
- tmpFrontiers.erase(Node);
- }
-
- if (!tmpFrontiers.empty())
- return true;
-
- return false;
- }
-
- /// print - Convert to human readable form
- ///
- virtual void print(raw_ostream &OS, const Module* = 0) const;
-
- /// dump - Dump the dominance frontier to dbgs().
- void dump() const;
-};
-
-
-//===-------------------------------------
-/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
-/// used to compute a forward dominator frontiers.
-///
-class DominanceFrontier : public DominanceFrontierBase {
-public:
- static char ID; // Pass ID, replacement for typeid
- DominanceFrontier() :
- DominanceFrontierBase(&ID, false) {}
-
- BasicBlock *getRoot() const {
- assert(Roots.size() == 1 && "Should always have entry node!");
- return Roots[0];
- }
-
- virtual bool runOnFunction(Function &) {
- Frontiers.clear();
- DominatorTree &DT = getAnalysis<DominatorTree>();
- Roots = DT.getRoots();
- assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
- calculate(DT, DT[Roots[0]]);
- return false;
- }
-
- virtual void verifyAnalysis() const;
-
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.setPreservesAll();
- AU.addRequired<DominatorTree>();
- }
-
- /// splitBlock - BB is split and now it has one successor. Update dominance
- /// frontier to reflect this change.
- void splitBlock(BasicBlock *BB);
-
- /// BasicBlock BB's new dominator is NewBB. Update BB's dominance frontier
- /// to reflect this change.
- void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB,
- DominatorTree *DT) {
- // NewBB is now dominating BB. Which means BB's dominance
- // frontier is now part of NewBB's dominance frontier. However, BB
- // itself is not member of NewBB's dominance frontier.
- DominanceFrontier::iterator NewDFI = find(NewBB);
- DominanceFrontier::iterator DFI = find(BB);
- // If BB was an entry block then its frontier is empty.
- if (DFI == end())
- return;
- DominanceFrontier::DomSetType BBSet = DFI->second;
- for (DominanceFrontier::DomSetType::iterator BBSetI = BBSet.begin(),
- BBSetE = BBSet.end(); BBSetI != BBSetE; ++BBSetI) {
- BasicBlock *DFMember = *BBSetI;
- // Insert only if NewBB dominates DFMember.
- if (!DT->dominates(NewBB, DFMember))
- NewDFI->second.insert(DFMember);
- }
- NewDFI->second.erase(BB);
- }
-
- const DomSetType &calculate(const DominatorTree &DT,
- const DomTreeNode *Node);
-};
-
-
} // End llvm namespace
#endif
projects / oota-llvm.git / blobdiff