aboutsummaryrefslogtreecommitdiffstats
path: root/include
diff options
context:
space:
mode:
authorNate Begeman <natebegeman@mac.com>2006-03-11 02:20:46 +0000
committerNate Begeman <natebegeman@mac.com>2006-03-11 02:20:46 +0000
commit442b32b5c5f690bc9b49d67b3ec76008879bc4d9 (patch)
treefe3e71fffa0ec5fb7290b29d95eb510178c63579 /include
parent78167faa18e66e95be3d73028b2db99bf3fbdcb3 (diff)
downloadexternal_llvm-442b32b5c5f690bc9b49d67b3ec76008879bc4d9.zip
external_llvm-442b32b5c5f690bc9b49d67b3ec76008879bc4d9.tar.gz
external_llvm-442b32b5c5f690bc9b49d67b3ec76008879bc4d9.tar.bz2
Fix PR681 by using the standard Lengauer and Tarjan algorithm for dominator
set construction, rather than intersecting various std::sets. This reduces the memory usage for the testcase in PR681 from 496 to 26MB of ram on my darwin system, and reduces the runtime from 32.8 to 0.8 seconds on a 2.5GHz G5. This also enables future code sharing between Dom and PostDom now that they share near-identical implementations. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@26707 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include')
-rw-r--r--include/llvm/Analysis/PostDominators.h81
1 files changed, 49 insertions, 32 deletions
diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h
index 754d436..39b26d7 100644
--- a/include/llvm/Analysis/PostDominators.h
+++ b/include/llvm/Analysis/PostDominators.h
@@ -18,6 +18,42 @@
namespace llvm {
+//===-------------------------------------
+/// ImmediatePostDominators Class - Concrete subclass of ImmediateDominatorsBase
+/// that is used to compute a normal immediate dominator set.
+///
+struct ImmediatePostDominators : public ImmediateDominatorsBase {
+ ImmediatePostDominators() : ImmediateDominatorsBase(false) {}
+
+ virtual bool runOnFunction(Function &F);
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ }
+
+private:
+ struct InfoRec {
+ unsigned Semi;
+ unsigned Size;
+ BasicBlock *Label, *Parent, *Child, *Ancestor;
+
+ std::vector<BasicBlock*> Bucket;
+
+ InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){}
+ };
+
+ // Vertex - Map the DFS number to the BasicBlock*
+ std::vector<BasicBlock*> Vertex;
+
+ // Info - Collection of information used during the computation of idoms.
+ std::map<BasicBlock*, InfoRec> Info;
+
+ unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
+ void Compress(BasicBlock *V, InfoRec &VInfo);
+ BasicBlock *Eval(BasicBlock *v);
+ void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
+};
+
/// 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
@@ -27,40 +63,20 @@ namespace llvm {
///
struct PostDominatorSet : public DominatorSetBase {
PostDominatorSet() : DominatorSetBase(true) {}
-
+
virtual bool runOnFunction(Function &F);
-
- /// getAnalysisUsage - This pass does not modify the function at all.
+
+ /// getAnalysisUsage - This simply provides a dominator set
///
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<ImmediatePostDominators>();
AU.setPreservesAll();
}
+
+ // stub - dummy function, just ignore it
+ static void stub();
};
-
-/// ImmediatePostDominators Class - Concrete subclass of ImmediateDominatorsBase
-/// that is used to compute the immediate post-dominators.
-///
-struct ImmediatePostDominators : public ImmediateDominatorsBase {
- ImmediatePostDominators() : ImmediateDominatorsBase(true) {}
-
- virtual bool runOnFunction(Function &F) {
- IDoms.clear(); // Reset from the last time we were run...
- PostDominatorSet &DS = getAnalysis<PostDominatorSet>();
- Roots = DS.getRoots();
- calcIDoms(DS);
- return false;
- }
-
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.setPreservesAll();
- AU.addRequired<PostDominatorSet>();
- }
-private:
- void calcIDoms(const DominatorSetBase &DS);
-};
-
-
/// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
/// compute the a post-dominator tree.
///
@@ -69,18 +85,19 @@ struct PostDominatorTree : public DominatorTreeBase {
virtual bool runOnFunction(Function &F) {
reset(); // Reset from the last time we were run...
- PostDominatorSet &DS = getAnalysis<PostDominatorSet>();
- Roots = DS.getRoots();
- calculate(DS);
+ ImmediatePostDominators &IPD = getAnalysis<ImmediatePostDominators>();
+ Roots = IPD.getRoots();
+ calculate(IPD);
return false;
}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
- AU.addRequired<PostDominatorSet>();
+ AU.addRequired<ImmediatePostDominators>();
}
private:
- void calculate(const PostDominatorSet &DS);
+ void calculate(const ImmediatePostDominators &IPD);
+ Node *getNodeForBlock(BasicBlock *BB);
};