Changes in directory llvm/include/llvm/Analysis:
PostDominators.h updated: 1.10 -> 1.11 --- Log message: Fix PR681: http://llvm.cs.uiuc.edu/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: http://llvm.cs.uiuc.edu/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. --- Diffs of the changes: (+49 -32) PostDominators.h | 81 +++++++++++++++++++++++++++++++++---------------------- 1 files changed, 49 insertions(+), 32 deletions(-) Index: llvm/include/llvm/Analysis/PostDominators.h diff -u llvm/include/llvm/Analysis/PostDominators.h:1.10 llvm/include/llvm/Analysis/PostDominators.h:1.11 --- llvm/include/llvm/Analysis/PostDominators.h:1.10 Sun Jan 8 02:19:58 2006 +++ llvm/include/llvm/Analysis/PostDominators.h Fri Mar 10 20:20:46 2006 @@ -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 @@ /// 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 @@ 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); }; _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
