#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFG.h"
#include "llvm/IR/Function.h"
#include "llvm/Pass.h"
-#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
+#include "llvm/Support/GenericDomTree.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
namespace llvm {
-//===----------------------------------------------------------------------===//
-/// DominatorBase - Base class that other, more interesting dominator analyses
-/// inherit from.
-///
-template <class NodeT>
-class DominatorBase {
-protected:
- std::vector<NodeT*> Roots;
- const bool IsPostDominators;
- inline explicit DominatorBase(bool isPostDom) :
- Roots(), IsPostDominators(isPostDom) {}
-public:
-
- /// 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<NodeT*> &getRoots() const { return Roots; }
-
- /// isPostDominator - Returns true if analysis based of postdoms
- ///
- bool isPostDominator() const { return IsPostDominators; }
-};
-
-
-//===----------------------------------------------------------------------===//
-// DomTreeNode - Dominator Tree Node
-template<class NodeT> class DominatorTreeBase;
-struct PostDominatorTree;
-class MachineBasicBlock;
-
-template <class NodeT>
-class DomTreeNodeBase {
- NodeT *TheBB;
- DomTreeNodeBase<NodeT> *IDom;
- std::vector<DomTreeNodeBase<NodeT> *> Children;
- int DFSNumIn, DFSNumOut;
-
- template<class N> friend class DominatorTreeBase;
- friend struct PostDominatorTree;
-public:
- typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator;
- typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator
- const_iterator;
-
- iterator begin() { return Children.begin(); }
- iterator end() { return Children.end(); }
- const_iterator begin() const { return Children.begin(); }
- const_iterator end() const { return Children.end(); }
-
- NodeT *getBlock() const { return TheBB; }
- DomTreeNodeBase<NodeT> *getIDom() const { return IDom; }
- const std::vector<DomTreeNodeBase<NodeT>*> &getChildren() const {
- return Children;
- }
-
- DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom)
- : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { }
-
- DomTreeNodeBase<NodeT> *addChild(DomTreeNodeBase<NodeT> *C) {
- Children.push_back(C);
- return C;
- }
-
- size_t getNumChildren() const {
- return Children.size();
- }
-
- void clearAllChildren() {
- Children.clear();
- }
-
- bool compare(const DomTreeNodeBase<NodeT> *Other) const {
- if (getNumChildren() != Other->getNumChildren())
- return true;
-
- SmallPtrSet<const NodeT *, 4> OtherChildren;
- for (const_iterator I = Other->begin(), E = Other->end(); I != E; ++I) {
- const NodeT *Nd = (*I)->getBlock();
- OtherChildren.insert(Nd);
- }
-
- for (const_iterator I = begin(), E = end(); I != E; ++I) {
- const NodeT *N = (*I)->getBlock();
- if (OtherChildren.count(N) == 0)
- return true;
- }
- return false;
- }
-
- void setIDom(DomTreeNodeBase<NodeT> *NewIDom) {
- assert(IDom && "No immediate dominator?");
- if (IDom != NewIDom) {
- typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I =
- std::find(IDom->Children.begin(), IDom->Children.end(), this);
- assert(I != IDom->Children.end() &&
- "Not in immediate dominator children set!");
- // I am no longer your child...
- IDom->Children.erase(I);
-
- // Switch to new dominator
- IDom = NewIDom;
- IDom->Children.push_back(this);
- }
- }
-
- /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do
- /// not call them.
- unsigned getDFSNumIn() const { return DFSNumIn; }
- unsigned getDFSNumOut() const { return DFSNumOut; }
-private:
- // Return true if this node is dominated by other. Use this only if DFS info
- // is valid.
- bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const {
- return this->DFSNumIn >= other->DFSNumIn &&
- this->DFSNumOut <= other->DFSNumOut;
- }
-};
+// FIXME: Replace this brittle forward declaration with the include of the new
+// PassManager.h when doing so doesn't break the PassManagerBuilder.
+template <typename IRUnitT> class AnalysisManager;
+class PreservedAnalyses;
EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>);
-EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>);
-
-template<class NodeT>
-inline raw_ostream &operator<<(raw_ostream &o,
- const DomTreeNodeBase<NodeT> *Node) {
- if (Node->getBlock())
- Node->getBlock()->printAsOperand(o, false);
- else
- o << " <<exit node>>";
-
- o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}";
-
- return o << "\n";
-}
-
-template<class NodeT>
-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(),
- E = N->end(); I != E; ++I)
- PrintDomTree<NodeT>(*I, o, Lev+1);
-}
-
-typedef DomTreeNodeBase<BasicBlock> DomTreeNode;
-
-//===----------------------------------------------------------------------===//
-/// DominatorTree - Calculate the immediate dominator tree for a function.
-///
-
-template<class FuncT, class N>
-void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT,
- FuncT& F);
-
-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;
- DomTreeNodeBase<NodeT> *RootNode;
-
- bool DFSInfoValid;
- unsigned int SlowQueries;
- // Information record used during immediate dominators computation.
- struct InfoRec {
- unsigned DFSNum;
- unsigned Parent;
- unsigned Semi;
- NodeT *Label;
-
- InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(0) {}
- };
-
- DenseMap<NodeT*, NodeT*> IDoms;
-
- // Vertex - Map the DFS number to the BasicBlock*
- std::vector<NodeT*> Vertex;
-
- // Info - Collection of information used during the computation of idoms.
- DenseMap<NodeT*, InfoRec> Info;
-
- void reset() {
- for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(),
- E = DomTreeNodes.end(); I != E; ++I)
- delete I->second;
- DomTreeNodes.clear();
- IDoms.clear();
- this->Roots.clear();
- Vertex.clear();
- RootNode = 0;
- }
-
- // NewBB is split and now it has one successor. Update dominator tree to
- // reflect this change.
- template<class N, class GraphT>
- void Split(DominatorTreeBase<typename GraphT::NodeType>& DT,
- typename GraphT::NodeType* NewBB) {
- assert(std::distance(GraphT::child_begin(NewBB),
- GraphT::child_end(NewBB)) == 1 &&
- "NewBB should have a single successor!");
- typename GraphT::NodeType* NewBBSucc = *GraphT::child_begin(NewBB);
-
- std::vector<typename GraphT::NodeType*> PredBlocks;
- typedef GraphTraits<Inverse<N> > InvTraits;
- for (typename InvTraits::ChildIteratorType PI =
- InvTraits::child_begin(NewBB),
- PE = InvTraits::child_end(NewBB); PI != PE; ++PI)
- PredBlocks.push_back(*PI);
-
- assert(!PredBlocks.empty() && "No predblocks?");
-
- bool NewBBDominatesNewBBSucc = true;
- for (typename InvTraits::ChildIteratorType PI =
- InvTraits::child_begin(NewBBSucc),
- E = InvTraits::child_end(NewBBSucc); PI != E; ++PI) {
- typename InvTraits::NodeType *ND = *PI;
- if (ND != NewBB && !DT.dominates(NewBBSucc, ND) &&
- DT.isReachableFromEntry(ND)) {
- NewBBDominatesNewBBSucc = false;
- break;
- }
- }
-
- // Find NewBB's immediate dominator and create new dominator tree node for
- // NewBB.
- NodeT *NewBBIDom = 0;
- unsigned i = 0;
- for (i = 0; i < PredBlocks.size(); ++i)
- if (DT.isReachableFromEntry(PredBlocks[i])) {
- NewBBIDom = PredBlocks[i];
- break;
- }
-
- // It's possible that none of the predecessors of NewBB are reachable;
- // in that case, NewBB itself is unreachable, so nothing needs to be
- // changed.
- if (!NewBBIDom)
- return;
-
- for (i = i + 1; i < PredBlocks.size(); ++i) {
- if (DT.isReachableFromEntry(PredBlocks[i]))
- NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
- }
-
- // Create the new dominator tree node... and set the idom of NewBB.
- DomTreeNodeBase<NodeT> *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom);
-
- // If NewBB strictly dominates other blocks, then it is now the immediate
- // dominator of NewBBSucc. Update the dominator tree as appropriate.
- if (NewBBDominatesNewBBSucc) {
- DomTreeNodeBase<NodeT> *NewBBSuccNode = DT.getNode(NewBBSucc);
- DT.changeImmediateDominator(NewBBSuccNode, NewBBNode);
- }
- }
-
-public:
- explicit DominatorTreeBase(bool isPostDom)
- : DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {}
- virtual ~DominatorTreeBase() { reset(); }
-
- /// compare - Return false if the other dominator tree base matches this
- /// dominator tree base. Otherwise return true.
- bool compare(DominatorTreeBase &Other) const {
-
- const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
- if (DomTreeNodes.size() != OtherDomTreeNodes.size())
- return true;
-
- for (typename DomTreeNodeMapType::const_iterator
- I = this->DomTreeNodes.begin(),
- E = this->DomTreeNodes.end(); I != E; ++I) {
- NodeT *BB = I->first;
- typename DomTreeNodeMapType::const_iterator OI = OtherDomTreeNodes.find(BB);
- if (OI == OtherDomTreeNodes.end())
- return true;
-
- DomTreeNodeBase<NodeT>* MyNd = I->second;
- DomTreeNodeBase<NodeT>* OtherNd = OI->second;
-
- if (MyNd->compare(OtherNd))
- return true;
- }
-
- return false;
- }
-
- virtual void releaseMemory() { reset(); }
-
- /// getNode - return the (Post)DominatorTree node for the specified basic
- /// block. This is the same as using operator[] on this class.
- ///
- inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
- return DomTreeNodes.lookup(BB);
- }
-
- /// getRootNode - This returns the entry node for the CFG of the function. If
- /// this tree represents the post-dominance relations for a function, however,
- /// this root may be a node with the block == NULL. This is the case when
- /// there are multiple exit nodes from a particular function. Consumers of
- /// post-dominance information must be capable of dealing with this
- /// possibility.
- ///
- DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
- const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
-
- /// Get all nodes dominated by R, including R itself.
- void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
- Result.clear();
- const DomTreeNodeBase<NodeT> *RN = getNode(R);
- if (RN == NULL)
- return; // If R is unreachable, it will not be present in the DOM tree.
- SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
- WL.push_back(RN);
-
- while (!WL.empty()) {
- const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
- Result.push_back(N->getBlock());
- WL.append(N->begin(), N->end());
- }
- }
-
- /// 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) {
- 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(const NodeT* A) const {
- assert(!this->isPostDominator() &&
- "This is not implemented for post dominators");
- 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
- /// constant time operation!
- ///
- inline bool dominates(const DomTreeNodeBase<NodeT> *A,
- const DomTreeNodeBase<NodeT> *B) {
- // A node trivially dominates itself.
- if (B == A)
- return true;
-
- // 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
- // checks are enabled.
-#ifdef XDEBUG
- assert((!DFSInfoValid ||
- (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
- "Tree walk disagrees with dfs numbers!");
-#endif
-
- if (DFSInfoValid)
- return B->DominatedBy(A);
-
- // If we end up with too many slow queries, just update the
- // DFS numbers on the theory that we are going to keep querying.
- SlowQueries++;
- if (SlowQueries > 32) {
- updateDFSNumbers();
- return B->DominatedBy(A);
- }
-
- return dominatedBySlowTreeWalk(A, B);
- }
-
- bool dominates(const NodeT *A, const NodeT *B);
-
- NodeT *getRoot() const {
- assert(this->Roots.size() == 1 && "Should always have entry node!");
- return this->Roots[0];
- }
-
- /// findNearestCommonDominator - Find nearest common dominator basic block
- /// for basic block A and B. If there is no such block then return NULL.
- NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) {
- assert(A->getParent() == B->getParent() &&
- "Two blocks are not in same function");
-
- // If either A or B is a entry block then it is nearest common dominator
- // (for forward-dominators).
- if (!this->isPostDominator()) {
- NodeT &Entry = A->getParent()->front();
- if (A == &Entry || B == &Entry)
- return &Entry;
- }
-
- // If B dominates A then B is nearest common dominator.
- if (dominates(B, A))
- return B;
-
- // If A dominates B then A is nearest common dominator.
- if (dominates(A, B))
- return A;
-
- DomTreeNodeBase<NodeT> *NodeA = getNode(A);
- DomTreeNodeBase<NodeT> *NodeB = getNode(B);
-
- // Collect NodeA dominators set.
- SmallPtrSet<DomTreeNodeBase<NodeT>*, 16> NodeADoms;
- NodeADoms.insert(NodeA);
- DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom();
- while (IDomA) {
- NodeADoms.insert(IDomA);
- IDomA = IDomA->getIDom();
- }
-
- // Walk NodeB immediate dominators chain and find common dominator node.
- DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom();
- while (IDomB) {
- if (NodeADoms.count(IDomB) != 0)
- return IDomB->getBlock();
-
- IDomB = IDomB->getIDom();
- }
-
- 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...
-
- /// addNewBlock - Add a new node to the dominator tree information. This
- /// creates a new node as a child of DomBB dominator node,linking it into
- /// the children list of the immediate dominator.
- DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
- assert(getNode(BB) == 0 && "Block already in dominator tree!");
- DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
- assert(IDomNode && "Not immediate dominator specified for block!");
- DFSInfoValid = false;
- return DomTreeNodes[BB] =
- IDomNode->addChild(new DomTreeNodeBase<NodeT>(BB, IDomNode));
- }
-
- /// changeImmediateDominator - This method is used to update the dominator
- /// tree information when a node's immediate dominator changes.
- ///
- void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
- DomTreeNodeBase<NodeT> *NewIDom) {
- assert(N && NewIDom && "Cannot change null node pointers!");
- DFSInfoValid = false;
- N->setIDom(NewIDom);
- }
-
- void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
- changeImmediateDominator(getNode(BB), getNode(NewBB));
- }
-
- /// eraseNode - Removes a node from the dominator tree. Block must not
- /// 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);
- assert(Node && "Removing node that isn't in dominator tree.");
- assert(Node->getChildren().empty() && "Node is not a leaf node.");
-
- // Remove node from immediate dominator's children list.
- DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
- if (IDom) {
- typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I =
- std::find(IDom->Children.begin(), IDom->Children.end(), Node);
- assert(I != IDom->Children.end() &&
- "Not in immediate dominator children set!");
- // I am no longer your child...
- IDom->Children.erase(I);
- }
-
- DomTreeNodes.erase(BB);
- delete Node;
- }
-
- /// removeNode - Removes a node from the dominator tree. Block must not
- /// dominate any other blocks. Invalidates any node pointing to removed
- /// block.
- void removeNode(NodeT *BB) {
- assert(getNode(BB) && "Removing node that isn't in dominator tree.");
- DomTreeNodes.erase(BB);
- }
-
- /// splitBlock - BB is split and now it has one successor. Update dominator
- /// tree to reflect this change.
- void splitBlock(NodeT* NewBB) {
- if (this->IsPostDominators)
- this->Split<Inverse<NodeT*>, GraphTraits<Inverse<NodeT*> > >(*this, NewBB);
- else
- this->Split<NodeT*, GraphTraits<NodeT*> >(*this, NewBB);
- }
-
- /// print - Convert to human readable form
- ///
- void print(raw_ostream &o) const {
- o << "=============================--------------------------------\n";
- if (this->isPostDominator())
- o << "Inorder PostDominator Tree: ";
- else
- o << "Inorder Dominator Tree: ";
- if (!this->DFSInfoValid)
- o << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
- o << "\n";
-
- // The postdom tree can have a null root if there are no returns.
- if (getRootNode())
- PrintDomTree<NodeT>(getRootNode(), o, 1);
- }
-
-protected:
- template<class GraphT>
- friend typename GraphT::NodeType* Eval(
- DominatorTreeBase<typename GraphT::NodeType>& DT,
- typename GraphT::NodeType* V,
- unsigned LastLinked);
-
- template<class GraphT>
- friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
- typename GraphT::NodeType* V,
- unsigned N);
-
- template<class FuncT, class N>
- friend void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT,
- FuncT& F);
-
- /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
- /// dominator tree in dfs order.
- void updateDFSNumbers() {
- unsigned DFSNum = 0;
-
- SmallVector<std::pair<DomTreeNodeBase<NodeT>*,
- typename DomTreeNodeBase<NodeT>::iterator>, 32> WorkStack;
-
- DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
-
- if (!ThisRoot)
- return;
-
- // Even in the case of multiple exits that form the post dominator root
- // nodes, do not iterate over all exits, but start from the virtual root
- // node. Otherwise bbs, that are not post dominated by any exit but by the
- // virtual root node, will never be assigned a DFS number.
- WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin()));
- ThisRoot->DFSNumIn = DFSNum++;
-
- while (!WorkStack.empty()) {
- DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
- typename DomTreeNodeBase<NodeT>::iterator ChildIt =
- WorkStack.back().second;
-
- // If we visited all of the children of this node, "recurse" back up the
- // stack setting the DFOutNum.
- if (ChildIt == Node->end()) {
- Node->DFSNumOut = DFSNum++;
- WorkStack.pop_back();
- } else {
- // Otherwise, recursively visit this child.
- DomTreeNodeBase<NodeT> *Child = *ChildIt;
- ++WorkStack.back().second;
-
- WorkStack.push_back(std::make_pair(Child, Child->begin()));
- Child->DFSNumIn = DFSNum++;
- }
- }
-
- SlowQueries = 0;
- DFSInfoValid = true;
- }
-
- DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
- if (DomTreeNodeBase<NodeT> *Node = getNode(BB))
- return Node;
-
- // Haven't calculated this node yet? Get or calculate the node for the
- // immediate dominator.
- NodeT *IDom = getIDom(BB);
-
- assert(IDom || this->DomTreeNodes[NULL]);
- DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom);
-
- // Add a new tree node for this BasicBlock, and link it as a child of
- // IDomNode
- DomTreeNodeBase<NodeT> *C = new DomTreeNodeBase<NodeT>(BB, IDomNode);
- return this->DomTreeNodes[BB] = IDomNode->addChild(C);
- }
-
- inline NodeT *getIDom(NodeT *BB) const {
- return IDoms.lookup(BB);
- }
-
- inline void addRoot(NodeT* BB) {
- this->Roots.push_back(BB);
- }
-
-public:
- /// 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
- 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 TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F),
- E = TraitsTy::nodes_end(&F); I != E; ++I) {
- if (TraitsTy::child_begin(I) == TraitsTy::child_end(I))
- addRoot(I);
-
- // Prepopulate maps so that we don't get iterator invalidation issues later.
- this->IDoms[I] = 0;
- this->DomTreeNodes[I] = 0;
- }
-
- Calculate<FT, Inverse<NodeT*> >(*this, F);
- }
- }
-};
-
-// 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;
+EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
- // 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)));
-}
+#define LLVM_COMMA ,
+EXTERN_TEMPLATE_INSTANTIATION(void Calculate<Function LLVM_COMMA BasicBlock *>(
+ DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT LLVM_COMMA
+ Function &F));
+EXTERN_TEMPLATE_INSTANTIATION(
+ void Calculate<Function LLVM_COMMA Inverse<BasicBlock *> >(
+ DominatorTreeBase<GraphTraits<Inverse<BasicBlock *> >::NodeType> &DT
+ LLVM_COMMA Function &F));
+#undef LLVM_COMMA
-EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
+typedef DomTreeNodeBase<BasicBlock> DomTreeNode;
class BasicBlockEdge {
const BasicBlock *Start;
bool isSingleEdge() const;
};
-//===-------------------------------------
-/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
-/// compute a normal dominator tree.
-///
-class DominatorTree : public FunctionPass {
+/// \brief Concrete subclass of DominatorTreeBase that is used to compute a
+/// normal dominator tree.
+class DominatorTree : public DominatorTreeBase<BasicBlock> {
public:
- static char ID; // Pass ID, replacement for typeid
- DominatorTreeBase<BasicBlock>* DT;
-
- DominatorTree() : FunctionPass(ID) {
- initializeDominatorTreePass(*PassRegistry::getPassRegistry());
- DT = new DominatorTreeBase<BasicBlock>(false);
- }
-
- ~DominatorTree() {
- delete DT;
- }
-
- DominatorTreeBase<BasicBlock>& getBase() { return *DT; }
+ typedef DominatorTreeBase<BasicBlock> Base;
- /// 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 DT->getRoots();
- }
-
- inline BasicBlock *getRoot() const {
- return DT->getRoot();
- }
-
- inline DomTreeNode *getRootNode() const {
- return DT->getRootNode();
- }
+ DominatorTree() : DominatorTreeBase<BasicBlock>(false) {}
- /// Get all nodes dominated by R, including R itself.
- void getDescendants(BasicBlock *R,
- SmallVectorImpl<BasicBlock *> &Result) const {
- DT->getDescendants(R, Result);
+ DominatorTree(DominatorTree &&Arg)
+ : Base(std::move(static_cast<Base &>(Arg))) {}
+ DominatorTree &operator=(DominatorTree &&RHS) {
+ Base::operator=(std::move(static_cast<Base &>(RHS)));
+ return *this;
}
- /// compare - Return false if the other dominator tree matches this
- /// dominator tree. Otherwise return true.
- inline bool compare(DominatorTree &Other) const {
- DomTreeNode *R = getRootNode();
- DomTreeNode *OtherR = Other.getRootNode();
+ /// \brief Returns *false* if the other dominator tree matches this dominator
+ /// tree.
+ inline bool compare(const DominatorTree &Other) const {
+ const DomTreeNode *R = getRootNode();
+ const DomTreeNode *OtherR = Other.getRootNode();
if (!R || !OtherR || R->getBlock() != OtherR->getBlock())
return true;
- if (DT->compare(Other.getBase()))
+ if (Base::compare(Other))
return true;
return false;
}
- virtual bool runOnFunction(Function &F);
-
- virtual void verifyAnalysis() const;
-
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.setPreservesAll();
- }
-
- inline bool dominates(const DomTreeNode* A, const DomTreeNode* B) const {
- return DT->dominates(A, B);
- }
+ // Ensure base-class overloads are visible.
+ using Base::dominates;
- inline bool dominates(const BasicBlock* A, const BasicBlock* B) const {
- return DT->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!
+ /// \brief 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(const BasicBlock *A, const BasicBlock *B) const {
- return DT->properlyDominates(A, B);
- }
-
- /// findNearestCommonDominator - Find nearest common dominator basic block
- /// for basic block A and B. If there is no such block then return NULL.
- inline BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *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);
- }
-
- /// getNode - return the (Post)DominatorTree node for the specified basic
- /// block. This is the same as using operator[] on this class.
- ///
- inline DomTreeNode *getNode(BasicBlock *BB) const {
- return DT->getNode(BB);
- }
-
- /// addNewBlock - Add a new node to the dominator tree information. This
- /// creates a new node as a child of DomBB dominator node,linking it into
- /// the children list of the immediate dominator.
- inline DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) {
- return DT->addNewBlock(BB, DomBB);
- }
-
- /// changeImmediateDominator - This method is used to update the dominator
- /// tree information when a node's immediate dominator changes.
- ///
- inline void changeImmediateDominator(BasicBlock *N, BasicBlock* NewIDom) {
- DT->changeImmediateDominator(N, NewIDom);
- }
-
- inline void changeImmediateDominator(DomTreeNode *N, DomTreeNode* NewIDom) {
- DT->changeImmediateDominator(N, NewIDom);
- }
-
- /// eraseNode - Removes a node from the dominator tree. Block must not
- /// 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);
- }
-
- /// splitBlock - BB is split and now it has one successor. Update dominator
- /// tree to reflect this change.
- inline void splitBlock(BasicBlock* NewBB) {
- DT->splitBlock(NewBB);
- }
-
- bool isReachableFromEntry(const BasicBlock* A) const {
- return DT->isReachableFromEntry(A);
- }
+ // Ensure base class overloads are visible.
+ using Base::isReachableFromEntry;
+ /// \brief Provide an overload for a Use.
bool isReachableFromEntry(const Use &U) const;
-
- virtual void releaseMemory() {
- DT->releaseMemory();
- }
-
- virtual void print(raw_ostream &OS, const Module* M= 0) const;
+ /// \brief Verify the correctness of the domtree by re-computing it.
+ ///
+ /// This should only be used for debugging as it aborts the program if the
+ /// verification fails.
+ void verifyDomTree() const;
};
//===-------------------------------------
-/// DominatorTree GraphTraits specialization so the DominatorTree can be
-/// iterable by generic graph iterators.
-///
+// DominatorTree GraphTraits specializations so the DominatorTree can be
+// iterable by generic graph iterators.
+
template <> struct GraphTraits<DomTreeNode*> {
typedef DomTreeNode NodeType;
typedef NodeType::iterator ChildIteratorType;
}
};
+/// \brief Analysis pass which computes a \c DominatorTree.
+class DominatorTreeAnalysis {
+public:
+ /// \brief Provide the result typedef for this analysis pass.
+ typedef DominatorTree Result;
+
+ /// \brief Opaque, unique identifier for this analysis pass.
+ static void *ID() { return (void *)&PassID; }
+
+ /// \brief Run the analysis pass over a function and produce a dominator tree.
+ DominatorTree run(Function &F);
+
+ /// \brief Provide access to a name for this pass for debugging purposes.
+ static StringRef name() { return "DominatorTreeAnalysis"; }
+
+private:
+ static char PassID;
+};
+
+/// \brief Printer pass for the \c DominatorTree.
+class DominatorTreePrinterPass {
+ raw_ostream &OS;
+
+public:
+ explicit DominatorTreePrinterPass(raw_ostream &OS);
+ PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM);
+
+ static StringRef name() { return "DominatorTreePrinterPass"; }
+};
+
+/// \brief Verifier pass for the \c DominatorTree.
+struct DominatorTreeVerifierPass {
+ PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM);
+
+ static StringRef name() { return "DominatorTreeVerifierPass"; }
+};
+
+/// \brief Legacy analysis pass which computes a \c DominatorTree.
+class DominatorTreeWrapperPass : public FunctionPass {
+ DominatorTree DT;
+
+public:
+ static char ID;
+
+ DominatorTreeWrapperPass() : FunctionPass(ID) {
+ initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
+ }
+
+ DominatorTree &getDomTree() { return DT; }
+ const DominatorTree &getDomTree() const { return DT; }
+
+ bool runOnFunction(Function &F) override;
+
+ void verifyAnalysis() const override;
+
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
+ AU.setPreservesAll();
+ }
+
+ void releaseMemory() override { DT.releaseMemory(); }
+
+ void print(raw_ostream &OS, const Module *M = nullptr) const override;
+};
} // End llvm namespace
projects / oota-llvm.git / blobdiff