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;
- 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;
/// 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 if this dominates N and this != N.
/// 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(const NodeT *A, const NodeT *B) {
+ const DomTreeNodeBase<NodeT> *B) {
+ if (A == 0 || B == 0)
+ return false;
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 properlyDominates(getNode(const_cast<NodeT *>(A)),
- getNode(const_cast<NodeT *>(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;
+ 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(const 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
+ /// dominates - Returns true if A dominates B. Note that this is not a
/// constant time operation!
///
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!");
}
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.
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);
DT->splitBlock(NewBB);
}
- bool isReachableFromEntry(const BasicBlock* A) {
+ bool isReachableFromEntry(const BasicBlock* A) const {
return DT->isReachableFromEntry(A);
}
+ bool isReachableFromEntry(const Use &U) const;
+
virtual void releaseMemory() {
DT->releaseMemory();
projects / oota-llvm.git / blobdiff