aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/DominatorInternals.h89
-rw-r--r--include/llvm/Analysis/Dominators.h3
-rw-r--r--lib/VMCore/DominatorCalculation.h5
-rw-r--r--lib/VMCore/DominatorInternals.cpp4
-rw-r--r--lib/VMCore/Dominators.cpp62
5 files changed, 96 insertions, 67 deletions
diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h
new file mode 100644
index 0000000..66ac2b7
--- /dev/null
+++ b/include/llvm/Analysis/DominatorInternals.h
@@ -0,0 +1,89 @@
+//=== llvm/Analysis/DominatorInternals.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.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines shared implementation details of dominator and
+// postdominator calculation. This file SHOULD NOT BE INCLUDED outside
+// of the dominator and postdominator implementation files.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_DOMINATOR_INTERNALS_H
+#define LLVM_ANALYSIS_DOMINATOR_INTERNALS_H
+
+#include "llvm/Analysis/Dominators.h"
+
+namespace llvm {
+
+template<class GraphT>
+unsigned DFSPass(DominatorTree& 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.
+#if 0
+ InfoRec &VInfo = DT.Info[DT.Roots[i]];
+ VInfo.Semi = ++N;
+ VInfo.Label = V;
+
+ Vertex.push_back(V); // Vertex[n] = V;
+ //Info[V].Ancestor = 0; // Ancestor[n] = 0
+ //Info[V].Child = 0; // Child[v] = 0
+ VInfo.Size = 1; // Size[v] = 1
+
+ for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) {
+ InfoRec &SuccVInfo = DT.Info[*SI];
+ if (SuccVInfo.Semi == 0) {
+ SuccVInfo.Parent = V;
+ N = DTDFSPass(DT, *SI, N);
+ }
+ }
+#else
+ std::vector<std::pair<typename GraphT::NodeType*,
+ typename GraphT::ChildIteratorType> > Worklist;
+ Worklist.push_back(std::make_pair(V, GraphT::child_begin(V)));
+ while (!Worklist.empty()) {
+ typename GraphT::NodeType* BB = Worklist.back().first;
+ typename GraphT::ChildIteratorType NextSucc = Worklist.back().second;
+
+ // First time we visited this BB?
+ if (NextSucc == GraphT::child_begin(BB)) {
+ DominatorTree::InfoRec &BBInfo = DT.Info[BB];
+ BBInfo.Semi = ++N;
+ BBInfo.Label = BB;
+
+ DT.Vertex.push_back(BB); // Vertex[n] = V;
+ //BBInfo[V].Ancestor = 0; // Ancestor[n] = 0
+ //BBInfo[V].Child = 0; // Child[v] = 0
+ BBInfo.Size = 1; // Size[v] = 1
+ }
+
+ // If we are done with this block, remove it from the worklist.
+ if (NextSucc == GraphT::child_end(BB)) {
+ Worklist.pop_back();
+ continue;
+ }
+
+ // Increment the successor number for the next time we get to it.
+ ++Worklist.back().second;
+
+ // Visit the successor next, if it isn't already visited.
+ typename GraphT::NodeType* Succ = *NextSucc;
+
+ DominatorTree::InfoRec &SuccVInfo = DT.Info[Succ];
+ if (SuccVInfo.Semi == 0) {
+ SuccVInfo.Parent = BB;
+ Worklist.push_back(std::make_pair(Succ, GraphT::child_begin(Succ)));
+ }
+ }
+#endif
+ return N;
+}
+
+}
+
+#endif \ No newline at end of file
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index b9c85b5..e8ed92c 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -320,7 +320,8 @@ public:
private:
friend void DTcalculate(DominatorTree& DT, Function& F);
- unsigned DFSPass(BasicBlock *V, unsigned N);
+ template<class GraphT> friend
+ unsigned DFSPass(DominatorTree& DT, typename GraphT::NodeType* V, unsigned N);
};
//===-------------------------------------
diff --git a/lib/VMCore/DominatorCalculation.h b/lib/VMCore/DominatorCalculation.h
index 0ad4bc0..bf90a97 100644
--- a/lib/VMCore/DominatorCalculation.h
+++ b/lib/VMCore/DominatorCalculation.h
@@ -11,6 +11,7 @@
#define LLVM_VMCORE_DOMINATOR_CALCULATION_H
#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/DominatorInternals.h"
//===----------------------------------------------------------------------===//
//
@@ -32,7 +33,7 @@
//===----------------------------------------------------------------------===//
namespace llvm {
-
+
void DTcalculate(DominatorTree& DT, Function &F) {
BasicBlock* Root = DT.Roots[0];
@@ -43,7 +44,7 @@ void DTcalculate(DominatorTree& DT, Function &F) {
// Step #1: Number blocks in depth-first order and initialize variables used
// in later stages of the algorithm.
- unsigned N = DT.DFSPass(Root, 0);
+ unsigned N = DFSPass<GraphTraits<BasicBlock*> >(DT, Root, 0);
for (unsigned i = N; i >= 2; --i) {
BasicBlock *W = DT.Vertex[i];
diff --git a/lib/VMCore/DominatorInternals.cpp b/lib/VMCore/DominatorInternals.cpp
index b40e2d9..fbbac9f 100644
--- a/lib/VMCore/DominatorInternals.cpp
+++ b/lib/VMCore/DominatorInternals.cpp
@@ -7,8 +7,8 @@
//
//===----------------------------------------------------------------------===//
-#ifndef LLVM_ANALYSIS_DOMINATOR_INTERNALS_H
-#define LLVM_ANALYSIS_DOMINATOR_INTERNALS_H
+#ifndef LIB_LLVM_ANALYSIS_DOMINATOR_INTERNALS_H
+#define LIB_LLVM_ANALYSIS_DOMINATOR_INTERNALS_H
#include "llvm/Analysis/Dominators.h"
#include "llvm/ADT/DenseMap.h"
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 0fc024b..a1eaf4a 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -53,68 +53,6 @@ char DominatorTree::ID = 0;
static RegisterPass<DominatorTree>
E("domtree", "Dominator Tree Construction", true);
-unsigned DominatorTree::DFSPass(BasicBlock *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.
-#if 0
- InfoRec &VInfo = Info[Roots[i]];
- VInfo.Semi = ++N;
- VInfo.Label = V;
-
- Vertex.push_back(V); // Vertex[n] = V;
- //Info[V].Ancestor = 0; // Ancestor[n] = 0
- //Info[V].Child = 0; // Child[v] = 0
- VInfo.Size = 1; // Size[v] = 1
-
- for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) {
- InfoRec &SuccVInfo = Info[*SI];
- if (SuccVInfo.Semi == 0) {
- SuccVInfo.Parent = V;
- N = DFSPass(*SI, N);
- }
- }
-#else
- std::vector<std::pair<BasicBlock*, unsigned> > Worklist;
- Worklist.push_back(std::make_pair(V, 0U));
- while (!Worklist.empty()) {
- BasicBlock *BB = Worklist.back().first;
- unsigned NextSucc = Worklist.back().second;
-
- // First time we visited this BB?
- if (NextSucc == 0) {
- InfoRec &BBInfo = Info[BB];
- BBInfo.Semi = ++N;
- BBInfo.Label = BB;
-
- Vertex.push_back(BB); // Vertex[n] = V;
- //BBInfo[V].Ancestor = 0; // Ancestor[n] = 0
- //BBInfo[V].Child = 0; // Child[v] = 0
- BBInfo.Size = 1; // Size[v] = 1
- }
-
- // If we are done with this block, remove it from the worklist.
- if (NextSucc == BB->getTerminator()->getNumSuccessors()) {
- Worklist.pop_back();
- continue;
- }
-
- // Otherwise, increment the successor number for the next time we get to it.
- ++Worklist.back().second;
-
- // Visit the successor next, if it isn't already visited.
- BasicBlock *Succ = BB->getTerminator()->getSuccessor(NextSucc);
-
- InfoRec &SuccVInfo = Info[Succ];
- if (SuccVInfo.Semi == 0) {
- SuccVInfo.Parent = BB;
- Worklist.push_back(std::make_pair(Succ, 0U));
- }
- }
-#endif
- return N;
-}
-
// NewBB is split and now it has one successor. Update dominator tree to
// reflect this change.
void DominatorTree::splitBlock(BasicBlock *NewBB) {
generated by cgit v1.1 at 2024-07-07 14:07:19 +0000