From 9cb7f49ee9d8c77f5ae82e36befde2b3094fdd02 Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Wed, 3 Oct 2007 21:25:45 +0000 Subject: [PATCH] Completely merge the implementation details of DomTree and PostDomTree. Also, add a FIXME for a bug in PostDomTree calculation I noticed while writing this, git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42593 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/DominatorInternals.h | 87 +++++++++++++++++ include/llvm/Analysis/Dominators.h | 6 +- include/llvm/Analysis/PostDominators.h | 2 - lib/Analysis/PostDominatorCalculation.h | 99 ------------------- lib/Analysis/PostDominators.cpp | 4 +- lib/VMCore/DominatorCalculation.h | 106 --------------------- lib/VMCore/Dominators.cpp | 7 +- 7 files changed, 97 insertions(+), 214 deletions(-) delete mode 100644 lib/Analysis/PostDominatorCalculation.h delete mode 100644 lib/VMCore/DominatorCalculation.h diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h index 972a6d80462..5d5714a5c78 100644 --- a/include/llvm/Analysis/DominatorInternals.h +++ b/include/llvm/Analysis/DominatorInternals.h @@ -208,6 +208,93 @@ void Link(DominatorTreeBase& DT, typename GraphT::NodeType* V, #endif } +template +void Calculate(DominatorTreeBase& DT, Function& F) { + // Step #1: Number blocks in depth-first order and initialize variables used + // in later stages of the algorithm. + unsigned N = 0; + for (unsigned i = 0, e = DT.Roots.size(); i != e; ++i) + N = DFSPass >(DT, DT.Roots[i], N); + + for (unsigned i = N; i >= 2; --i) { + typename GraphTraits::NodeType* W = DT.Vertex[i]; + DominatorTree::InfoRec &WInfo = DT.Info[W]; + + // Step #2: Calculate the semidominators of all vertices + for (typename GraphTraits >::ChildIteratorType CI = + GraphTraits >::child_begin(W), + E = GraphTraits >::child_end(W); CI != E; ++CI) + if (DT.Info.count(*CI)) { // Only if this predecessor is reachable! + unsigned SemiU = DT.Info[Eval >(DT, *CI)].Semi; + if (SemiU < WInfo.Semi) + WInfo.Semi = SemiU; + } + + DT.Info[DT.Vertex[WInfo.Semi]].Bucket.push_back(W); + + typename GraphTraits::NodeType* WParent = WInfo.Parent; + Link >(DT, WParent, W, WInfo); + + // Step #3: Implicitly define the immediate dominator of vertices + std::vector::NodeType*> &WParentBucket = + DT.Info[WParent].Bucket; + while (!WParentBucket.empty()) { + typename GraphTraits::NodeType* V = WParentBucket.back(); + WParentBucket.pop_back(); + typename GraphTraits::NodeType* U = + Eval >(DT, V); + DT.IDoms[V] = DT.Info[U].Semi < DT.Info[V].Semi ? U : WParent; + } + } + + // Step #4: Explicitly define the immediate dominator of each vertex + for (unsigned i = 2; i <= N; ++i) { + typename GraphTraits::NodeType* W = DT.Vertex[i]; + typename GraphTraits::NodeType*& WIDom = DT.IDoms[W]; + if (WIDom != DT.Vertex[DT.Info[W].Semi]) + WIDom = DT.IDoms[WIDom]; + } + + if (DT.Roots.empty()) return; + + // Add a node for the root. This node might be the actual root, if there is + // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0) + // which postdominates all real exits if there are multiple exit blocks. + typename GraphTraits::NodeType* Root = DT.Roots.size() == 1 ? DT.Roots[0] + : 0; + DT.DomTreeNodes[Root] = DT.RootNode = new DomTreeNode(Root, 0); + + // Loop over all of the reachable blocks in the function... + for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) + if (typename GraphTraits::NodeType* ImmDom = DT.getIDom(I)) { + // Reachable block. + DomTreeNode *BBNode = DT.DomTreeNodes[I]; + if (BBNode) continue; // Haven't calculated this node yet? + + // Get or calculate the node for the immediate dominator + DomTreeNode *IDomNode = DT.getNodeForBlock(ImmDom); + + // Add a new tree node for this BasicBlock, and link it as a child of + // IDomNode + DomTreeNode *C = new DomTreeNode(I, IDomNode); + DT.DomTreeNodes[I] = IDomNode->addChild(C); + } + + // Free temporary memory used to construct idom's + DT.IDoms.clear(); + DT.Info.clear(); + std::vector::NodeType*>().swap(DT.Vertex); + + // FIXME: This does not work on PostDomTrees. It seems likely that this is + // due to an error in the algorithm for post-dominators. This really should + // be investigated and fixed at some point. + // DT.updateDFSNumbers(); + + // Start out with the DFS numbers being invalid. Let them be computed if + // demanded. + DT.DFSInfoValid = false; +} + } #endif diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index f16d16874f7..abff3998cec 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -289,6 +289,9 @@ protected: typename GraphT::NodeType* V, unsigned N); + template friend void Calculate(DominatorTreeBase& DT, + Function& F); + /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking /// dominator tree in dfs order. void updateDFSNumbers(); @@ -325,9 +328,6 @@ public: /// BB is split and now it has one successor. Update dominator tree to /// reflect this change. void splitBlock(BasicBlock *BB); - -private: - friend void DTcalculate(DominatorTree& DT, Function& F); }; //===------------------------------------- diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h index 098339a0c5f..50fe984cc3c 100644 --- a/include/llvm/Analysis/PostDominators.h +++ b/include/llvm/Analysis/PostDominators.h @@ -32,8 +32,6 @@ struct PostDominatorTree : public DominatorTreeBase { virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); } -private: - friend void PDTcalculate(PostDominatorTree& PDT, Function &F); }; diff --git a/lib/Analysis/PostDominatorCalculation.h b/lib/Analysis/PostDominatorCalculation.h deleted file mode 100644 index 724ff795fd1..00000000000 --- a/lib/Analysis/PostDominatorCalculation.h +++ /dev/null @@ -1,99 +0,0 @@ -//==- PostDominatorCalculation.h - Post-Dominator Calculation ----*- C++ -*-==// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by Owen Anderson and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// PostDominatorTree calculation implementation. -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_POST_DOMINATOR_CALCULATION_H -#define LLVM_ANALYSIS_POST_DOMINATOR_CALCULATION_H - -#include "llvm/Analysis/PostDominators.h" -#include "llvm/Analysis/DominatorInternals.h" - -namespace llvm { - -void PDTcalculate(PostDominatorTree& PDT, Function &F) { - // Step #1: Number blocks in depth-first order and initialize variables used - // in later stages of the algorithm. - unsigned N = 0; - for (unsigned i = 0, e = PDT.Roots.size(); i != e; ++i) - N = DFSPass > >(PDT, PDT.Roots[i], N); - - for (unsigned i = N; i >= 2; --i) { - BasicBlock *W = PDT.Vertex[i]; - PostDominatorTree::InfoRec &WInfo = PDT.Info[W]; - - // Step #2: Calculate the semidominators of all vertices - for (succ_iterator SI = succ_begin(W), SE = succ_end(W); SI != SE; ++SI) - if (PDT.Info.count(*SI)) { // Only if this predecessor is reachable! - unsigned SemiU = - PDT.Info[Eval > >(PDT, *SI)].Semi; - if (SemiU < WInfo.Semi) - WInfo.Semi = SemiU; - } - - PDT.Info[PDT.Vertex[WInfo.Semi]].Bucket.push_back(W); - - BasicBlock *WParent = WInfo.Parent; - Link > >(PDT, WParent, W, WInfo); - - // Step #3: Implicitly define the immediate dominator of vertices - std::vector &WParentBucket = PDT.Info[WParent].Bucket; - while (!WParentBucket.empty()) { - BasicBlock *V = WParentBucket.back(); - WParentBucket.pop_back(); - BasicBlock *U = Eval > >(PDT, V); - PDT.IDoms[V] = PDT.Info[U].Semi < PDT.Info[V].Semi ? U : WParent; - } - } - - // Step #4: Explicitly define the immediate dominator of each vertex - for (unsigned i = 2; i <= N; ++i) { - BasicBlock *W = PDT.Vertex[i]; - BasicBlock *&WIDom = PDT.IDoms[W]; - if (WIDom != PDT.Vertex[PDT.Info[W].Semi]) - WIDom = PDT.IDoms[WIDom]; - } - - if (PDT.Roots.empty()) return; - - // Add a node for the root. This node might be the actual root, if there is - // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0) - // which postdominates all real exits if there are multiple exit blocks. - BasicBlock *Root = PDT.Roots.size() == 1 ? PDT.Roots[0] : 0; - PDT.DomTreeNodes[Root] = PDT.RootNode = new DomTreeNode(Root, 0); - - // Loop over all of the reachable blocks in the function... - for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) - if (BasicBlock *ImmPostDom = PDT.getIDom(I)) { // Reachable block. - DomTreeNode *&BBNode = PDT.DomTreeNodes[I]; - if (!BBNode) { // Haven't calculated this node yet? - // Get or calculate the node for the immediate dominator - DomTreeNode *IPDomNode = PDT.getNodeForBlock(ImmPostDom); - - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - DomTreeNode *C = new DomTreeNode(I, IPDomNode); - PDT.DomTreeNodes[I] = C; - BBNode = IPDomNode->addChild(C); - } - } - - // Free temporary memory used to construct idom's - PDT.IDoms.clear(); - PDT.Info.clear(); - std::vector().swap(PDT.Vertex); - - // Start out with the DFS numbers being invalid. Let them be computed if - // demanded. - PDT.DFSInfoValid = false; -} - -} -#endif diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp index 0ca73882312..f066f7ae525 100644 --- a/lib/Analysis/PostDominators.cpp +++ b/lib/Analysis/PostDominators.cpp @@ -16,7 +16,7 @@ #include "llvm/Support/CFG.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SetOperations.h" -#include "PostDominatorCalculation.h" +#include "llvm/Analysis/DominatorInternals.h" using namespace llvm; //===----------------------------------------------------------------------===// @@ -47,7 +47,7 @@ bool PostDominatorTree::runOnFunction(Function &F) { Vertex.push_back(0); - PDTcalculate(*this, F); + Calculate >(*this, F); return false; } diff --git a/lib/VMCore/DominatorCalculation.h b/lib/VMCore/DominatorCalculation.h deleted file mode 100644 index 1d245d474f5..00000000000 --- a/lib/VMCore/DominatorCalculation.h +++ /dev/null @@ -1,106 +0,0 @@ -//==- DominatorCalculation.h - Dominator Calculation -------------*- C++ -*-==// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by Owen Anderson and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_VMCORE_DOMINATOR_CALCULATION_H -#define LLVM_VMCORE_DOMINATOR_CALCULATION_H - -#include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/DominatorInternals.h" - -//===----------------------------------------------------------------------===// -// -// DominatorTree construction - This pass constructs immediate dominator -// information for a flow-graph based on the algorithm described in this -// document: -// -// A Fast Algorithm for Finding Dominators in a Flowgraph -// T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. -// -// This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and -// LINK, but it turns out that the theoretically slower O(n*log(n)) -// implementation is actually faster than the "efficient" algorithm (even for -// large CFGs) because the constant overheads are substantially smaller. The -// lower-complexity version can be enabled with the following #define: -// -#define BALANCE_IDOM_TREE 0 -// -//===----------------------------------------------------------------------===// - -namespace llvm { - -void DTcalculate(DominatorTree& DT, Function &F) { - BasicBlock* Root = DT.Roots[0]; - - // Add a node for the root... - DT.DomTreeNodes[Root] = DT.RootNode = new DomTreeNode(Root, 0); - - // Step #1: Number blocks in depth-first order and initialize variables used - // in later stages of the algorithm. - unsigned N = DFSPass >(DT, Root, 0); - - for (unsigned i = N; i >= 2; --i) { - BasicBlock *W = DT.Vertex[i]; - DominatorTree::InfoRec &WInfo = DT.Info[W]; - - // Step #2: Calculate the semidominators of all vertices - for (pred_iterator PI = pred_begin(W), E = pred_end(W); PI != E; ++PI) - if (DT.Info.count(*PI)) { // Only if this predecessor is reachable! - unsigned SemiU = DT.Info[Eval >(DT, *PI)].Semi; - if (SemiU < WInfo.Semi) - WInfo.Semi = SemiU; - } - - DT.Info[DT.Vertex[WInfo.Semi]].Bucket.push_back(W); - - BasicBlock *WParent = WInfo.Parent; - Link >(DT, WParent, W, WInfo); - - // Step #3: Implicitly define the immediate dominator of vertices - std::vector &WParentBucket = DT.Info[WParent].Bucket; - while (!WParentBucket.empty()) { - BasicBlock *V = WParentBucket.back(); - WParentBucket.pop_back(); - BasicBlock *U = Eval >(DT, V); - DT.IDoms[V] = DT.Info[U].Semi < DT.Info[V].Semi ? U : WParent; - } - } - - // Step #4: Explicitly define the immediate dominator of each vertex - for (unsigned i = 2; i <= N; ++i) { - BasicBlock *W = DT.Vertex[i]; - BasicBlock *&WIDom = DT.IDoms[W]; - if (WIDom != DT.Vertex[DT.Info[W].Semi]) - WIDom = DT.IDoms[WIDom]; - } - - // Loop over all of the reachable blocks in the function... - for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) - if (BasicBlock *ImmDom = DT.getIDom(I)) { // Reachable block. - DomTreeNode *BBNode = DT.DomTreeNodes[I]; - if (BBNode) continue; // Haven't calculated this node yet? - - // Get or calculate the node for the immediate dominator - DomTreeNode *IDomNode = DT.getNodeForBlock(ImmDom); - - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - DomTreeNode *C = new DomTreeNode(I, IDomNode); - DT.DomTreeNodes[I] = IDomNode->addChild(C); - } - - // Free temporary memory used to construct idom's - DT.Info.clear(); - DT.IDoms.clear(); - std::vector().swap(DT.Vertex); - - DT.updateDFSNumbers(); -} - -} -#endif diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 57cf6702868..164fb64d0ec 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -21,9 +21,9 @@ #include "llvm/ADT/SetOperations.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/Analysis/DominatorInternals.h" #include "llvm/Instructions.h" #include "llvm/Support/Streams.h" -#include "DominatorCalculation.h" #include using namespace llvm; @@ -357,7 +357,10 @@ bool DominatorTree::runOnFunction(Function &F) { DomTreeNodes[&F.getEntryBlock()] = 0; Vertex.push_back(0); - DTcalculate(*this, F); + Calculate(*this, F); + + updateDFSNumbers(); + return false; } -- 2.34.1