aboutsummaryrefslogtreecommitdiffstats
path: root/include/llvm/Analysis/DominatorInternals.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/Analysis/DominatorInternals.h')
-rw-r--r--include/llvm/Analysis/DominatorInternals.h68
1 files changed, 38 insertions, 30 deletions
diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h
index 5d5714a..3486b77 100644
--- a/include/llvm/Analysis/DominatorInternals.h
+++ b/include/llvm/Analysis/DominatorInternals.h
@@ -35,8 +35,8 @@
namespace llvm {
template<class GraphT>
-unsigned DFSPass(DominatorTreeBase& DT, typename GraphT::NodeType* V,
- unsigned N) {
+unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
+ typename GraphT::NodeType* V, unsigned N) {
// This is more understandable as a recursive algorithm, but we can't use the
// recursive algorithm due to stack depth issues. Keep it here for
// documentation purposes.
@@ -67,7 +67,8 @@ unsigned DFSPass(DominatorTreeBase& DT, typename GraphT::NodeType* V,
// First time we visited this BB?
if (NextSucc == GraphT::child_begin(BB)) {
- DominatorTree::InfoRec &BBInfo = DT.Info[BB];
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &BBInfo =
+ DT.Info[BB];
BBInfo.Semi = ++N;
BBInfo.Label = BB;
@@ -89,7 +90,8 @@ unsigned DFSPass(DominatorTreeBase& DT, typename GraphT::NodeType* V,
// Visit the successor next, if it isn't already visited.
typename GraphT::NodeType* Succ = *NextSucc;
- DominatorTree::InfoRec &SuccVInfo = DT.Info[Succ];
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &SuccVInfo =
+ DT.Info[Succ];
if (SuccVInfo.Semi == 0) {
SuccVInfo.Parent = BB;
Worklist.push_back(std::make_pair(Succ, GraphT::child_begin(Succ)));
@@ -100,20 +102,24 @@ unsigned DFSPass(DominatorTreeBase& DT, typename GraphT::NodeType* V,
}
template<class GraphT>
-void Compress(DominatorTreeBase& DT, typename GraphT::NodeType *VIn) {
+void Compress(DominatorTreeBase<typename GraphT::NodeType>& DT,
+ typename GraphT::NodeType *VIn) {
std::vector<typename GraphT::NodeType*> Work;
SmallPtrSet<typename GraphT::NodeType*, 32> Visited;
typename GraphT::NodeType* VInAncestor = DT.Info[VIn].Ancestor;
- DominatorTreeBase::InfoRec &VInVAInfo = DT.Info[VInAncestor];
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInVAInfo =
+ DT.Info[VInAncestor];
if (VInVAInfo.Ancestor != 0)
Work.push_back(VIn);
while (!Work.empty()) {
typename GraphT::NodeType* V = Work.back();
- DominatorTree::InfoRec &VInfo = DT.Info[V];
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInfo =
+ DT.Info[V];
typename GraphT::NodeType* VAncestor = VInfo.Ancestor;
- DominatorTreeBase::InfoRec &VAInfo = DT.Info[VAncestor];
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VAInfo =
+ DT.Info[VAncestor];
// Process Ancestor first
if (Visited.insert(VAncestor) &&
@@ -135,9 +141,10 @@ void Compress(DominatorTreeBase& DT, typename GraphT::NodeType *VIn) {
}
template<class GraphT>
-typename GraphT::NodeType* Eval(DominatorTreeBase& DT,
+typename GraphT::NodeType* Eval(DominatorTreeBase<typename GraphT::NodeType>& DT,
typename GraphT::NodeType *V) {
- DominatorTreeBase::InfoRec &VInfo = DT.Info[V];
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInfo =
+ DT.Info[V];
#if !BALANCE_IDOM_TREE
// Higher-complexity but faster implementation
if (VInfo.Ancestor == 0)
@@ -160,8 +167,9 @@ typename GraphT::NodeType* Eval(DominatorTreeBase& DT,
}
template<class GraphT>
-void Link(DominatorTreeBase& DT, typename GraphT::NodeType* V,
- typename GraphT::NodeType* W, DominatorTreeBase::InfoRec &WInfo) {
+void Link(DominatorTreeBase<typename GraphT::NodeType>& DT,
+ typename GraphT::NodeType* V, typename GraphT::NodeType* W,
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo) {
#if !BALANCE_IDOM_TREE
// Higher-complexity but faster implementation
WInfo.Ancestor = V;
@@ -208,49 +216,49 @@ void Link(DominatorTreeBase& DT, typename GraphT::NodeType* V,
#endif
}
-template<class NodeT>
-void Calculate(DominatorTreeBase& DT, Function& F) {
+template<class NodeT, class GraphT>
+void Calculate(DominatorTreeBase<typename GraphT::NodeType>& 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<GraphTraits<NodeT> >(DT, DT.Roots[i], N);
+ N = DFSPass<GraphT>(DT, DT.Roots[i], N);
for (unsigned i = N; i >= 2; --i) {
- typename GraphTraits<NodeT>::NodeType* W = DT.Vertex[i];
- DominatorTree::InfoRec &WInfo = DT.Info[W];
+ typename GraphT::NodeType* W = DT.Vertex[i];
+ typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo =
+ DT.Info[W];
// Step #2: Calculate the semidominators of all vertices
for (typename GraphTraits<Inverse<NodeT> >::ChildIteratorType CI =
GraphTraits<Inverse<NodeT> >::child_begin(W),
E = GraphTraits<Inverse<NodeT> >::child_end(W); CI != E; ++CI)
if (DT.Info.count(*CI)) { // Only if this predecessor is reachable!
- unsigned SemiU = DT.Info[Eval<GraphTraits<NodeT> >(DT, *CI)].Semi;
+ unsigned SemiU = DT.Info[Eval<GraphT>(DT, *CI)].Semi;
if (SemiU < WInfo.Semi)
WInfo.Semi = SemiU;
}
DT.Info[DT.Vertex[WInfo.Semi]].Bucket.push_back(W);
- typename GraphTraits<NodeT>::NodeType* WParent = WInfo.Parent;
- Link<GraphTraits<NodeT> >(DT, WParent, W, WInfo);
+ typename GraphT::NodeType* WParent = WInfo.Parent;
+ Link<GraphT>(DT, WParent, W, WInfo);
// Step #3: Implicitly define the immediate dominator of vertices
- std::vector<typename GraphTraits<NodeT>::NodeType*> &WParentBucket =
+ std::vector<typename GraphT::NodeType*> &WParentBucket =
DT.Info[WParent].Bucket;
while (!WParentBucket.empty()) {
- typename GraphTraits<NodeT>::NodeType* V = WParentBucket.back();
+ typename GraphT::NodeType* V = WParentBucket.back();
WParentBucket.pop_back();
- typename GraphTraits<NodeT>::NodeType* U =
- Eval<GraphTraits<NodeT> >(DT, V);
+ typename GraphT::NodeType* U = Eval<GraphT>(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<NodeT>::NodeType* W = DT.Vertex[i];
- typename GraphTraits<NodeT>::NodeType*& WIDom = DT.IDoms[W];
+ typename GraphT::NodeType* W = DT.Vertex[i];
+ typename GraphT::NodeType*& WIDom = DT.IDoms[W];
if (WIDom != DT.Vertex[DT.Info[W].Semi])
WIDom = DT.IDoms[WIDom];
}
@@ -260,13 +268,13 @@ void Calculate(DominatorTreeBase& DT, Function& F) {
// 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<NodeT>::NodeType* Root = DT.Roots.size() == 1 ? DT.Roots[0]
- : 0;
+ typename GraphT::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<NodeT>::NodeType* ImmDom = DT.getIDom(I)) {
+ if (typename GraphT::NodeType* ImmDom = DT.getIDom(I)) {
// Reachable block.
DomTreeNode *BBNode = DT.DomTreeNodes[I];
if (BBNode) continue; // Haven't calculated this node yet?
@@ -283,7 +291,7 @@ void Calculate(DominatorTreeBase& DT, Function& F) {
// Free temporary memory used to construct idom's
DT.IDoms.clear();
DT.Info.clear();
- std::vector<typename GraphTraits<NodeT>::NodeType*>().swap(DT.Vertex);
+ std::vector<typename GraphT::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
generated by cgit v1.1 at 2025-11-28 19:24:55 +0000