diff options
author | Chris Lattner <sabre@nondot.org> | 2003-09-10 20:36:51 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2003-09-10 20:36:51 +0000 |
commit | 420a8bf2b2276acdb4d7004ae251a2460999c0e4 (patch) | |
tree | 346223450312bbf15c09a9f9a105a0f1956ca39f /include | |
parent | 1df2998451793ba5afae6972af242c4c36ac133d (diff) | |
download | llvm-420a8bf2b2276acdb4d7004ae251a2460999c0e4.tar.gz llvm-420a8bf2b2276acdb4d7004ae251a2460999c0e4.tar.bz2 llvm-420a8bf2b2276acdb4d7004ae251a2460999c0e4.tar.xz |
Rework dominator and post dominator information so that we do not have to
unify all exit nodes of a function to compute post-dominance information.
This does not work with functions that have both unwind and return nodes,
because we cannot unify these blocks. The new implementation is better
anyway. :)
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8459 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include')
-rw-r--r-- | include/llvm/Analysis/Dominators.h | 55 | ||||
-rw-r--r-- | include/llvm/Analysis/PostDominators.h | 26 |
2 files changed, 61 insertions, 20 deletions
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index a6df556051..17b5efa52a 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -32,12 +32,15 @@ template <typename GraphType> struct GraphTraits; // class DominatorBase : public FunctionPass { protected: - BasicBlock *Root; + std::vector<BasicBlock*> Roots; const bool IsPostDominators; - inline DominatorBase(bool isPostDom) : Root(0), IsPostDominators(isPostDom) {} + inline DominatorBase(bool isPostDom) : Roots(), IsPostDominators(isPostDom) {} public: - inline BasicBlock *getRoot() const { return Root; } + // 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; } // Returns true if analysis based of postdoms bool isPostDominator() const { return IsPostDominators; } @@ -144,6 +147,11 @@ struct DominatorSet : public DominatorSetBase { /// obviously really slow, so it should be avoided if at all possible. void recalculate(); + BasicBlock *getRoot() const { + assert(Roots.size() == 1 && "Should always have entry node!"); + return Roots[0]; + } + // getAnalysisUsage - This simply provides a dominator set virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); @@ -219,10 +227,15 @@ public: struct ImmediateDominators : public ImmediateDominatorsBase { ImmediateDominators() : ImmediateDominatorsBase(false) {} + BasicBlock *getRoot() const { + assert(Roots.size() == 1 && "Should always have entry node!"); + return Roots[0]; + } + virtual bool runOnFunction(Function &F) { IDoms.clear(); // Reset from the last time we were run... DominatorSet &DS = getAnalysis<DominatorSet>(); - Root = DS.getRoot(); + Roots = DS.getRoots(); calcIDoms(DS); return false; } @@ -247,6 +260,8 @@ protected: std::map<BasicBlock*, Node*> Nodes; void reset(); typedef std::map<BasicBlock*, Node*> NodeMapType; + + Node *RootNode; public: class Node2 { friend class DominatorTree; @@ -303,7 +318,18 @@ public: return getNode(BB); } - //===--------------------------------------------------------------------===// // API to update (Post)DominatorTree information based on modifications to + // 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. + // + Node *getRootNode() { return RootNode; } + const Node *getRootNode() const { return RootNode; } + + //===--------------------------------------------------------------------===// + // API to update (Post)DominatorTree information based on modifications to // the CFG... /// createNewNode - Add a new node to the dominator tree information. This @@ -336,10 +362,15 @@ public: struct DominatorTree : public DominatorTreeBase { DominatorTree() : DominatorTreeBase(false) {} + BasicBlock *getRoot() const { + assert(Roots.size() == 1 && "Should always have entry node!"); + return Roots[0]; + } + virtual bool runOnFunction(Function &F) { reset(); // Reset from the last time we were run... DominatorSet &DS = getAnalysis<DominatorSet>(); - Root = DS.getRoot(); + Roots = DS.getRoots(); calculate(DS); return false; } @@ -374,7 +405,7 @@ template <> struct GraphTraits<DominatorTree::Node*> { template <> struct GraphTraits<DominatorTree*> : public GraphTraits<DominatorTree::Node*> { static NodeType *getEntryNode(DominatorTree *DT) { - return DT->getNode(DT->getRoot()); + return DT->getRootNode(); } }; @@ -431,11 +462,17 @@ public: struct DominanceFrontier : public DominanceFrontierBase { DominanceFrontier() : DominanceFrontierBase(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>(); - Root = DT.getRoot(); - calculate(DT, DT[Root]); + Roots = DT.getRoots(); + assert(Roots.size() == 1 && "Only one entry block for forward domfronts!"); + calculate(DT, DT[Roots[0]]); return false; } diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h index 3a4ac7f92c..f7131f2a45 100644 --- a/include/llvm/Analysis/PostDominators.h +++ b/include/llvm/Analysis/PostDominators.h @@ -10,19 +10,23 @@ #include "llvm/Analysis/Dominators.h" -//===------------------------------------- -// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to -// compute the post-dominator set. -// +/// PostDominatorSet Class - Concrete subclass of DominatorSetBase that is used +/// to compute the post-dominator set. Because there can be multiple exit nodes +/// in an LLVM function, we calculate post dominators with a special null block +/// which is the virtual exit node that the real exit nodes all virtually branch +/// to. Clients should be prepared to see an entry in the dominator sets with a +/// null BasicBlock*. +/// struct PostDominatorSet : public DominatorSetBase { PostDominatorSet() : DominatorSetBase(true) {} virtual bool runOnFunction(Function &F); - // getAnalysisUsage - This obviously provides a dominator set, but it also - // uses the UnifyFunctionExitNode pass if building post-dominators + // getAnalysisUsage - This pass does not modify the function at all. // - virtual void getAnalysisUsage(AnalysisUsage &AU) const; + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + } }; @@ -37,7 +41,7 @@ struct ImmediatePostDominators : public ImmediateDominatorsBase { virtual bool runOnFunction(Function &F) { IDoms.clear(); // Reset from the last time we were run... PostDominatorSet &DS = getAnalysis<PostDominatorSet>(); - Root = DS.getRoot(); + Roots = DS.getRoots(); calcIDoms(DS); return false; } @@ -59,7 +63,7 @@ struct PostDominatorTree : public DominatorTreeBase { virtual bool runOnFunction(Function &F) { reset(); // Reset from the last time we were run... PostDominatorSet &DS = getAnalysis<PostDominatorSet>(); - Root = DS.getRoot(); + Roots = DS.getRoots(); calculate(DS); return false; } @@ -83,8 +87,8 @@ struct PostDominanceFrontier : public DominanceFrontierBase { virtual bool runOnFunction(Function &) { Frontiers.clear(); PostDominatorTree &DT = getAnalysis<PostDominatorTree>(); - Root = DT.getRoot(); - calculate(DT, DT[Root]); + Roots = DT.getRoots(); + calculate(DT, DT.getRootNode()); return false; } |