X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FDominators.h;h=c69b1edec7b30667d465efaaf9ab496aae56fe07;hb=b09c146b116359616f6cbd4c8b3328607e00ff42;hp=b539a788a2204a8b9e73c0e6e8f4b966d34a38e5;hpb=b5c26ef9da16052597d59a412eaae32098aa1be0;p=oota-llvm.git diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index b539a788a22..c69b1edec7b 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -15,13 +15,13 @@ #ifndef LLVM_ANALYSIS_DOMINATORS_H #define LLVM_ANALYSIS_DOMINATORS_H -#include "llvm/Pass.h" -#include "llvm/Function.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/Function.h" +#include "llvm/Pass.h" #include "llvm/Support/CFG.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/raw_ostream.h" @@ -152,7 +152,7 @@ EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase); EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase); template -static raw_ostream &operator<<(raw_ostream &o, +inline raw_ostream &operator<<(raw_ostream &o, const DomTreeNodeBase *Node) { if (Node->getBlock()) WriteAsOperand(o, Node->getBlock(), false); @@ -165,7 +165,7 @@ static raw_ostream &operator<<(raw_ostream &o, } template -static void PrintDomTree(const DomTreeNodeBase *N, raw_ostream &o, +inline void PrintDomTree(const DomTreeNodeBase *N, raw_ostream &o, unsigned Lev) { o.indent(2*Lev) << "[" << Lev << "] " << N; for (typename DomTreeNodeBase::const_iterator I = N->begin(), @@ -185,6 +185,18 @@ void Calculate(DominatorTreeBase::NodeType>& DT, template class DominatorTreeBase : public DominatorBase { + bool dominatedBySlowTreeWalk(const DomTreeNodeBase *A, + const DomTreeNodeBase *B) const { + assert(A != B); + assert(isReachableFromEntry(B)); + assert(isReachableFromEntry(A)); + + const DomTreeNodeBase *IDom; + while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B) + B = IDom; // Walk up the tree + return IDom != 0; + } + protected: typedef DenseMap*> DomTreeNodeMapType; DomTreeNodeMapType DomTreeNodes; @@ -334,42 +346,30 @@ public: DomTreeNodeBase *getRootNode() { return RootNode; } const DomTreeNodeBase *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 *A, - const DomTreeNodeBase *B) const { - if (A == 0 || B == 0) return false; - return dominatedBySlowTreeWalk(A, B); - } - - inline bool properlyDominates(const NodeT *A, const NodeT *B) { + const DomTreeNodeBase *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(A)), - getNode(const_cast(B))); - } - - bool dominatedBySlowTreeWalk(const DomTreeNodeBase *A, - const DomTreeNodeBase *B) const { - const DomTreeNodeBase *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(A))); + } + + inline bool isReachableFromEntry(const DomTreeNodeBase *A) const { + return A; } /// dominates - Returns true iff A dominates B. Note that this is not a @@ -377,10 +377,16 @@ public: /// inline bool dominates(const DomTreeNodeBase *A, const DomTreeNodeBase *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 @@ -405,16 +411,7 @@ public: 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(A)), - getNode(const_cast(B))); - } + bool dominates(const NodeT *A, const NodeT *B); NodeT *getRoot() const { assert(this->Roots.size() == 1 && "Should always have entry node!"); @@ -680,8 +677,49 @@ public: } }; +// These two functions are declared out of line as a workaround for building +// with old (< r147295) versions of clang because of pr11642. +template +bool DominatorTreeBase::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(A)), + getNode(const_cast(B))); +} +template +bool +DominatorTreeBase::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(A)), + getNode(const_cast(B))); +} + EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase); +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. @@ -749,15 +787,14 @@ public: 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; - - /// properlyDominates - Use this instead of dominates() to determine whether a - /// user of A can be hoisted above B. - bool properlyDominates(const Instruction *A, const Instruction *B) const { - return A != B && dominates(A, B); - } + // 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); @@ -820,10 +857,12 @@ public: 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();