*** empty log message ***
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@3105 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
index caff1f1..777b3c4 100644
--- a/lib/Analysis/PostDominators.cpp
+++ b/lib/Analysis/PostDominators.cpp
@@ -19,22 +19,12 @@
//===----------------------------------------------------------------------===//
AnalysisID DominatorSet::ID(AnalysisID::create<DominatorSet>(), true);
-AnalysisID DominatorSet::PostDomID(AnalysisID::create<DominatorSet>(), true);
-
-bool DominatorSet::runOnFunction(Function &F) {
- Doms.clear(); // Reset from the last time we were run...
-
- if (isPostDominator())
- calcPostDominatorSet(F);
- else
- calcForwardDominatorSet(F);
- return false;
-}
+AnalysisID PostDominatorSet::ID(AnalysisID::create<PostDominatorSet>(), true);
// dominates - Return true if A dominates B. This performs the special checks
// neccesary if A and B are in the same basic block.
//
-bool DominatorSet::dominates(Instruction *A, Instruction *B) const {
+bool DominatorSetBase::dominates(Instruction *A, Instruction *B) const {
BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
if (BBA != BBB) return dominates(BBA, BBB);
@@ -46,10 +36,11 @@
return &*I == A;
}
-// calcForwardDominatorSet - This method calculates the forward dominator sets
-// for the specified function.
+// runOnFunction - This method calculates the forward dominator sets for the
+// specified function.
//
-void DominatorSet::calcForwardDominatorSet(Function &F) {
+bool DominatorSet::runOnFunction(Function &F) {
+ Doms.clear(); // Reset from the last time we were run...
Root = &F.getEntryNode();
assert(pred_begin(Root) == pred_end(Root) &&
"Root node has predecessors in function!");
@@ -87,13 +78,16 @@
WorkingSet.clear(); // Clear out the set for next iteration
}
} while (Changed);
+ return false;
}
-// Postdominator set constructor. This ctor converts the specified function to
-// only have a single exit node (return stmt), then calculates the post
-// dominance sets for the function.
+
+// Postdominator set construction. This converts the specified function to only
+// have a single exit node (return stmt), then calculates the post dominance
+// sets for the function.
//
-void DominatorSet::calcPostDominatorSet(Function &F) {
+bool PostDominatorSet::runOnFunction(Function &F) {
+ Doms.clear(); // Reset from the last time we were run...
// Since we require that the unify all exit nodes pass has been run, we know
// that there can be at most one return instruction in the function left.
// Get it.
@@ -103,7 +97,7 @@
if (Root == 0) { // No exit node for the function? Postdomsets are all empty
for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
Doms[FI] = DomSetType();
- return;
+ return false;
}
bool Changed;
@@ -140,19 +134,16 @@
WorkingSet.clear(); // Clear out the set for next iteration
}
} while (Changed);
+ return false;
}
-// getAnalysisUsage - This obviously provides a dominator set, but it also
-// uses the UnifyFunctionExitNodes pass if building post-dominators
+// getAnalysisUsage - This obviously provides a post-dominator set, but it also
+// requires the UnifyFunctionExitNodes pass.
//
-void DominatorSet::getAnalysisUsage(AnalysisUsage &AU) const {
+void PostDominatorSet::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
- if (isPostDominator()) {
- AU.addProvided(PostDomID);
- AU.addRequired(UnifyFunctionExitNodes::ID);
- } else {
- AU.addProvided(ID);
- }
+ AU.addProvided(ID);
+ AU.addRequired(UnifyFunctionExitNodes::ID);
}
@@ -161,11 +152,11 @@
//===----------------------------------------------------------------------===//
AnalysisID ImmediateDominators::ID(AnalysisID::create<ImmediateDominators>(), true);
-AnalysisID ImmediateDominators::PostDomID(AnalysisID::create<ImmediateDominators>(), true);
+AnalysisID ImmediatePostDominators::ID(AnalysisID::create<ImmediatePostDominators>(), true);
// calcIDoms - Calculate the immediate dominator mapping, given a set of
// dominators for every basic block.
-void ImmediateDominators::calcIDoms(const DominatorSet &DS) {
+void ImmediateDominatorsBase::calcIDoms(const DominatorSetBase &DS) {
// Loop over all of the nodes that have dominators... figuring out the IDOM
// for each node...
//
@@ -205,89 +196,67 @@
//===----------------------------------------------------------------------===//
AnalysisID DominatorTree::ID(AnalysisID::create<DominatorTree>(), true);
-AnalysisID DominatorTree::PostDomID(AnalysisID::create<DominatorTree>(), true);
+AnalysisID PostDominatorTree::ID(AnalysisID::create<PostDominatorTree>(), true);
-// DominatorTree::reset - Free all of the tree node memory.
+// DominatorTreeBase::reset - Free all of the tree node memory.
//
-void DominatorTree::reset() {
+void DominatorTreeBase::reset() {
for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
delete I->second;
Nodes.clear();
}
-#if 0
-// Given immediate dominators, we can also calculate the dominator tree
-DominatorTree::DominatorTree(const ImmediateDominators &IDoms)
- : DominatorBase(IDoms.getRoot()) {
- const Function *M = Root->getParent();
-
- Nodes[Root] = new Node(Root, 0); // Add a node for the root...
-
- // Iterate over all nodes in depth first order...
- for (df_iterator<const Function*> I = df_begin(M), E = df_end(M); I!=E; ++I) {
- const BasicBlock *BB = *I, *IDom = IDoms[*I];
-
- if (IDom != 0) { // Ignore the root node and other nasty nodes
- // We know that the immediate dominator should already have a node,
- // because we are traversing the CFG in depth first order!
- //
- assert(Nodes[IDom] && "No node for IDOM?");
- Node *IDomNode = Nodes[IDom];
-
- // Add a new tree node for this BasicBlock, and link it as a child of
- // IDomNode
- Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
- }
- }
-}
-#endif
-
void DominatorTree::calculate(const DominatorSet &DS) {
Nodes[Root] = new Node(Root, 0); // Add a node for the root...
- if (!isPostDominator()) {
- // Iterate over all nodes in depth first order...
- for (df_iterator<BasicBlock*> I = df_begin(Root), E = df_end(Root);
- I != E; ++I) {
- BasicBlock *BB = *I;
- const DominatorSet::DomSetType &Dominators = DS.getDominators(BB);
- unsigned DomSetSize = Dominators.size();
- if (DomSetSize == 1) continue; // Root node... IDom = null
+ // Iterate over all nodes in depth first order...
+ for (df_iterator<BasicBlock*> I = df_begin(Root), E = df_end(Root);
+ I != E; ++I) {
+ BasicBlock *BB = *I;
+ const DominatorSet::DomSetType &Dominators = DS.getDominators(BB);
+ unsigned DomSetSize = Dominators.size();
+ if (DomSetSize == 1) continue; // Root node... IDom = null
- // Loop over all dominators of this node. This corresponds to looping over
- // nodes in the dominator chain, looking for a node whose dominator set is
- // equal to the current nodes, except that the current node does not exist
- // in it. This means that it is one level higher in the dom chain than the
- // current node, and it is our idom! We know that we have already added
- // a DominatorTree node for our idom, because the idom must be a
- // predecessor in the depth first order that we are iterating through the
- // function.
+ // Loop over all dominators of this node. This corresponds to looping over
+ // nodes in the dominator chain, looking for a node whose dominator set is
+ // equal to the current nodes, except that the current node does not exist
+ // in it. This means that it is one level higher in the dom chain than the
+ // current node, and it is our idom! We know that we have already added
+ // a DominatorTree node for our idom, because the idom must be a
+ // predecessor in the depth first order that we are iterating through the
+ // function.
+ //
+ DominatorSet::DomSetType::const_iterator I = Dominators.begin();
+ DominatorSet::DomSetType::const_iterator End = Dominators.end();
+ for (; I != End; ++I) { // Iterate over dominators...
+ // All of our dominators should form a chain, where the number of
+ // elements in the dominator set indicates what level the node is at in
+ // the chain. We want the node immediately above us, so it will have
+ // an identical dominator set, except that BB will not dominate it...
+ // therefore it's dominator set size will be one less than BB's...
//
- DominatorSet::DomSetType::const_iterator I = Dominators.begin();
- DominatorSet::DomSetType::const_iterator End = Dominators.end();
- for (; I != End; ++I) { // Iterate over dominators...
- // All of our dominators should form a chain, where the number of
- // elements in the dominator set indicates what level the node is at in
- // the chain. We want the node immediately above us, so it will have
- // an identical dominator set, except that BB will not dominate it...
- // therefore it's dominator set size will be one less than BB's...
- //
- if (DS.getDominators(*I).size() == DomSetSize - 1) {
- // We know that the immediate dominator should already have a node,
- // because we are traversing the CFG in depth first order!
- //
- Node *IDomNode = Nodes[*I];
- assert(IDomNode && "No node for IDOM?");
-
- // Add a new tree node for this BasicBlock, and link it as a child of
- // IDomNode
- Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
- break;
- }
+ if (DS.getDominators(*I).size() == DomSetSize - 1) {
+ // We know that the immediate dominator should already have a node,
+ // because we are traversing the CFG in depth first order!
+ //
+ Node *IDomNode = Nodes[*I];
+ assert(IDomNode && "No node for IDOM?");
+
+ // Add a new tree node for this BasicBlock, and link it as a child of
+ // IDomNode
+ Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
+ break;
}
}
- } else if (Root) {
+ }
+}
+
+
+void PostDominatorTree::calculate(const PostDominatorSet &DS) {
+ Nodes[Root] = new Node(Root, 0); // Add a node for the root...
+
+ if (Root) {
// Iterate over all nodes in depth first order...
for (idf_iterator<BasicBlock*> I = idf_begin(Root), E = idf_end(Root);
I != E; ++I) {
@@ -339,11 +308,11 @@
//===----------------------------------------------------------------------===//
AnalysisID DominanceFrontier::ID(AnalysisID::create<DominanceFrontier>(), true);
-AnalysisID DominanceFrontier::PostDomID(AnalysisID::create<DominanceFrontier>(), true);
+AnalysisID PostDominanceFrontier::ID(AnalysisID::create<PostDominanceFrontier>(), true);
const DominanceFrontier::DomSetType &
-DominanceFrontier::calcDomFrontier(const DominatorTree &DT,
- const DominatorTree::Node *Node) {
+DominanceFrontier::calculate(const DominatorTree &DT,
+ const DominatorTree::Node *Node) {
// Loop over CFG successors to calculate DFlocal[Node]
BasicBlock *BB = Node->getNode();
DomSetType &S = Frontiers[BB]; // The new set to fill in...
@@ -362,7 +331,7 @@
for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end();
NI != NE; ++NI) {
DominatorTree::Node *IDominee = *NI;
- const DomSetType &ChildDF = calcDomFrontier(DT, IDominee);
+ const DomSetType &ChildDF = calculate(DT, IDominee);
DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
for (; CDFI != CDFE; ++CDFI) {
@@ -375,8 +344,8 @@
}
const DominanceFrontier::DomSetType &
-DominanceFrontier::calcPostDomFrontier(const DominatorTree &DT,
- const DominatorTree::Node *Node) {
+PostDominanceFrontier::calculate(const PostDominatorTree &DT,
+ const DominatorTree::Node *Node) {
// Loop over CFG successors to calculate DFlocal[Node]
BasicBlock *BB = Node->getNode();
DomSetType &S = Frontiers[BB]; // The new set to fill in...
@@ -393,10 +362,10 @@
// Loop through and visit the nodes that Node immediately dominates (Node's
// children in the IDomTree)
//
- for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end();
- NI != NE; ++NI) {
+ for (PostDominatorTree::Node::const_iterator
+ NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) {
DominatorTree::Node *IDominee = *NI;
- const DomSetType &ChildDF = calcPostDomFrontier(DT, IDominee);
+ const DomSetType &ChildDF = calculate(DT, IDominee);
DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
for (; CDFI != CDFE; ++CDFI) {
diff --git a/lib/Analysis/Writer.cpp b/lib/Analysis/Writer.cpp
index e7eaf44..80a8f91 100644
--- a/lib/Analysis/Writer.cpp
+++ b/lib/Analysis/Writer.cpp
@@ -62,8 +62,9 @@
return o;
}
-void WriteToOutput(const DominatorSet &DS, ostream &o) {
- for (DominatorSet::const_iterator I = DS.begin(), E = DS.end(); I != E; ++I) {
+void WriteToOutput(const DominatorSetBase &DS, ostream &o) {
+ for (DominatorSetBase::const_iterator I = DS.begin(), E = DS.end();
+ I != E; ++I) {
o << "=============================--------------------------------\n"
<< "\nDominator Set For Basic Block\n" << I->first
<< "-------------------------------\n" << I->second << "\n";
@@ -71,8 +72,8 @@
}
-void WriteToOutput(const ImmediateDominators &ID, ostream &o) {
- for (ImmediateDominators::const_iterator I = ID.begin(), E = ID.end();
+void WriteToOutput(const ImmediateDominatorsBase &ID, ostream &o) {
+ for (ImmediateDominatorsBase::const_iterator I = ID.begin(), E = ID.end();
I != E; ++I) {
o << "=============================--------------------------------\n"
<< "\nImmediate Dominator For Basic Block\n" << *I->first
@@ -81,28 +82,28 @@
}
-static ostream &operator<<(ostream &o, const DominatorTree::Node *Node) {
+static ostream &operator<<(ostream &o, const DominatorTreeBase::Node *Node) {
return o << Node->getNode() << "\n------------------------------------------\n";
}
-static void PrintDomTree(const DominatorTree::Node *N, ostream &o,
+static void PrintDomTree(const DominatorTreeBase::Node *N, ostream &o,
unsigned Lev) {
o << "Level #" << Lev << ": " << N;
- for (DominatorTree::Node::const_iterator I = N->begin(), E = N->end();
+ for (DominatorTreeBase::Node::const_iterator I = N->begin(), E = N->end();
I != E; ++I) {
PrintDomTree(*I, o, Lev+1);
}
}
-void WriteToOutput(const DominatorTree &DT, ostream &o) {
+void WriteToOutput(const DominatorTreeBase &DT, ostream &o) {
o << "=============================--------------------------------\n"
<< "Inorder Dominator Tree:\n";
PrintDomTree(DT[DT.getRoot()], o, 1);
}
-void WriteToOutput(const DominanceFrontier &DF, ostream &o) {
- for (DominanceFrontier::const_iterator I = DF.begin(), E = DF.end();
+void WriteToOutput(const DominanceFrontierBase &DF, ostream &o) {
+ for (DominanceFrontierBase::const_iterator I = DF.begin(), E = DF.end();
I != E; ++I) {
o << "=============================--------------------------------\n"
<< "\nDominance Frontier For Basic Block\n";
diff --git a/lib/Bytecode/Writer/InstructionWriter.cpp b/lib/Bytecode/Writer/InstructionWriter.cpp
index 36414be..fdc5c5c 100644
--- a/lib/Bytecode/Writer/InstructionWriter.cpp
+++ b/lib/Bytecode/Writer/InstructionWriter.cpp
@@ -16,8 +16,14 @@
#include "llvm/DerivedTypes.h"
#include "llvm/iOther.h"
#include "llvm/iTerminators.h"
+#include "Support/StatisticReporter.h"
#include <algorithm>
+static Statistic<>
+NumOversized("bytecodewriter\t- Number of oversized instructions");
+static Statistic<>
+NumNormal("bytecodewriter\t- Number of normal instructions");
+
typedef unsigned char uchar;
// outputInstructionFormat0 - Output those wierd instructions that have a large
@@ -48,6 +54,7 @@
}
align32(Out); // We must maintain correct alignment!
+ ++NumOversized;
}
@@ -97,6 +104,7 @@
output_vbr((unsigned)Slot, Out);
}
align32(Out); // We must maintain correct alignment!
+ ++NumOversized;
}
@@ -118,6 +126,7 @@
unsigned Bits = 1 | (Opcode << 2) | (Type << 8) | (Slots[0] << 20);
// cerr << "1 " << IType << " " << Type << " " << Slots[0] << endl;
output(Bits, Out);
+ ++NumNormal;
}
@@ -142,6 +151,7 @@
// cerr << "2 " << IType << " " << Type << " " << Slots[0] << " "
// << Slots[1] << endl;
output(Bits, Out);
+ ++NumNormal;
}
@@ -167,6 +177,7 @@
//cerr << "3 " << IType << " " << Type << " " << Slots[0] << " "
// << Slots[1] << " " << Slots[2] << endl;
output(Bits, Out);
+ ++NumNormal;
}
void BytecodeWriter::processInstruction(const Instruction &I) {
diff --git a/lib/Bytecode/Writer/Writer.cpp b/lib/Bytecode/Writer/Writer.cpp
index f7219ea..4eade88 100644
--- a/lib/Bytecode/Writer/Writer.cpp
+++ b/lib/Bytecode/Writer/Writer.cpp
@@ -25,11 +25,14 @@
#include "llvm/SymbolTable.h"
#include "llvm/DerivedTypes.h"
#include "Support/STLExtras.h"
+#include "Support/StatisticReporter.h"
#include <string.h>
#include <algorithm>
static RegisterPass<WriteBytecodePass> X("emitbytecode", "Bytecode Writer");
+static Statistic<>
+BytesWritten("bytecodewriter\t- Number of bytecode bytes written");
BytecodeWriter::BytecodeWriter(std::deque<unsigned char> &o, const Module *M)
@@ -234,6 +237,9 @@
// This object populates buffer for us...
BytecodeWriter BCW(Buffer, C);
+ // Keep track of how much we've written...
+ BytesWritten += Buffer.size();
+
// Okay, write the deque out to the ostream now... the deque is not
// sequential in memory, however, so write out as much as possible in big
// chunks, until we're done.
diff --git a/lib/Transforms/Scalar/ADCE.cpp b/lib/Transforms/Scalar/ADCE.cpp
index d70980e..058ef1b 100644
--- a/lib/Transforms/Scalar/ADCE.cpp
+++ b/lib/Transforms/Scalar/ADCE.cpp
@@ -55,8 +55,8 @@
// getAnalysisUsage - We require post dominance frontiers (aka Control
// Dependence Graph)
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.addRequired(DominatorTree::PostDomID);
- AU.addRequired(DominanceFrontier::PostDomID);
+ AU.addRequired(PostDominatorTree::ID);
+ AU.addRequired(PostDominanceFrontier::ID);
}
@@ -93,13 +93,12 @@
// Mark the basic block as being newly ALIVE... and mark all branches that
// this block is control dependant on as being alive also...
//
- DominanceFrontier &CDG =
- getAnalysis<DominanceFrontier>(DominanceFrontier::PostDomID);
+ PostDominanceFrontier &CDG = getAnalysis<PostDominanceFrontier>();
- DominanceFrontier::const_iterator It = CDG.find(BB);
+ PostDominanceFrontier::const_iterator It = CDG.find(BB);
if (It != CDG.end()) {
// Get the blocks that this node is control dependant on...
- const DominanceFrontier::DomSetType &CDB = It->second;
+ const PostDominanceFrontier::DomSetType &CDB = It->second;
for_each(CDB.begin(), CDB.end(), // Mark all their terminators as live
bind_obj(this, &ADCE::markTerminatorLive));
}
@@ -191,7 +190,7 @@
// Find the first postdominator of the entry node that is alive. Make it the
// new entry node...
//
- DominatorTree &DT = getAnalysis<DominatorTree>(DominatorTree::PostDomID);
+ PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
// If there are some blocks dead...
if (AliveBlocks.size() != Func->size()) {
@@ -218,8 +217,8 @@
// postdominator that is alive, and the last postdominator that is
// dead...
//
- DominatorTree::Node *LastNode = DT[TI->getSuccessor(i)];
- DominatorTree::Node *NextNode = LastNode->getIDom();
+ PostDominatorTree::Node *LastNode = DT[TI->getSuccessor(i)];
+ PostDominatorTree::Node *NextNode = LastNode->getIDom();
while (!AliveBlocks.count(NextNode->getNode())) {
LastNode = NextNode;
NextNode = NextNode->getIDom();
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index caff1f1..777b3c4 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -19,22 +19,12 @@
//===----------------------------------------------------------------------===//
AnalysisID DominatorSet::ID(AnalysisID::create<DominatorSet>(), true);
-AnalysisID DominatorSet::PostDomID(AnalysisID::create<DominatorSet>(), true);
-
-bool DominatorSet::runOnFunction(Function &F) {
- Doms.clear(); // Reset from the last time we were run...
-
- if (isPostDominator())
- calcPostDominatorSet(F);
- else
- calcForwardDominatorSet(F);
- return false;
-}
+AnalysisID PostDominatorSet::ID(AnalysisID::create<PostDominatorSet>(), true);
// dominates - Return true if A dominates B. This performs the special checks
// neccesary if A and B are in the same basic block.
//
-bool DominatorSet::dominates(Instruction *A, Instruction *B) const {
+bool DominatorSetBase::dominates(Instruction *A, Instruction *B) const {
BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
if (BBA != BBB) return dominates(BBA, BBB);
@@ -46,10 +36,11 @@
return &*I == A;
}
-// calcForwardDominatorSet - This method calculates the forward dominator sets
-// for the specified function.
+// runOnFunction - This method calculates the forward dominator sets for the
+// specified function.
//
-void DominatorSet::calcForwardDominatorSet(Function &F) {
+bool DominatorSet::runOnFunction(Function &F) {
+ Doms.clear(); // Reset from the last time we were run...
Root = &F.getEntryNode();
assert(pred_begin(Root) == pred_end(Root) &&
"Root node has predecessors in function!");
@@ -87,13 +78,16 @@
WorkingSet.clear(); // Clear out the set for next iteration
}
} while (Changed);
+ return false;
}
-// Postdominator set constructor. This ctor converts the specified function to
-// only have a single exit node (return stmt), then calculates the post
-// dominance sets for the function.
+
+// Postdominator set construction. This converts the specified function to only
+// have a single exit node (return stmt), then calculates the post dominance
+// sets for the function.
//
-void DominatorSet::calcPostDominatorSet(Function &F) {
+bool PostDominatorSet::runOnFunction(Function &F) {
+ Doms.clear(); // Reset from the last time we were run...
// Since we require that the unify all exit nodes pass has been run, we know
// that there can be at most one return instruction in the function left.
// Get it.
@@ -103,7 +97,7 @@
if (Root == 0) { // No exit node for the function? Postdomsets are all empty
for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
Doms[FI] = DomSetType();
- return;
+ return false;
}
bool Changed;
@@ -140,19 +134,16 @@
WorkingSet.clear(); // Clear out the set for next iteration
}
} while (Changed);
+ return false;
}
-// getAnalysisUsage - This obviously provides a dominator set, but it also
-// uses the UnifyFunctionExitNodes pass if building post-dominators
+// getAnalysisUsage - This obviously provides a post-dominator set, but it also
+// requires the UnifyFunctionExitNodes pass.
//
-void DominatorSet::getAnalysisUsage(AnalysisUsage &AU) const {
+void PostDominatorSet::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
- if (isPostDominator()) {
- AU.addProvided(PostDomID);
- AU.addRequired(UnifyFunctionExitNodes::ID);
- } else {
- AU.addProvided(ID);
- }
+ AU.addProvided(ID);
+ AU.addRequired(UnifyFunctionExitNodes::ID);
}
@@ -161,11 +152,11 @@
//===----------------------------------------------------------------------===//
AnalysisID ImmediateDominators::ID(AnalysisID::create<ImmediateDominators>(), true);
-AnalysisID ImmediateDominators::PostDomID(AnalysisID::create<ImmediateDominators>(), true);
+AnalysisID ImmediatePostDominators::ID(AnalysisID::create<ImmediatePostDominators>(), true);
// calcIDoms - Calculate the immediate dominator mapping, given a set of
// dominators for every basic block.
-void ImmediateDominators::calcIDoms(const DominatorSet &DS) {
+void ImmediateDominatorsBase::calcIDoms(const DominatorSetBase &DS) {
// Loop over all of the nodes that have dominators... figuring out the IDOM
// for each node...
//
@@ -205,89 +196,67 @@
//===----------------------------------------------------------------------===//
AnalysisID DominatorTree::ID(AnalysisID::create<DominatorTree>(), true);
-AnalysisID DominatorTree::PostDomID(AnalysisID::create<DominatorTree>(), true);
+AnalysisID PostDominatorTree::ID(AnalysisID::create<PostDominatorTree>(), true);
-// DominatorTree::reset - Free all of the tree node memory.
+// DominatorTreeBase::reset - Free all of the tree node memory.
//
-void DominatorTree::reset() {
+void DominatorTreeBase::reset() {
for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
delete I->second;
Nodes.clear();
}
-#if 0
-// Given immediate dominators, we can also calculate the dominator tree
-DominatorTree::DominatorTree(const ImmediateDominators &IDoms)
- : DominatorBase(IDoms.getRoot()) {
- const Function *M = Root->getParent();
-
- Nodes[Root] = new Node(Root, 0); // Add a node for the root...
-
- // Iterate over all nodes in depth first order...
- for (df_iterator<const Function*> I = df_begin(M), E = df_end(M); I!=E; ++I) {
- const BasicBlock *BB = *I, *IDom = IDoms[*I];
-
- if (IDom != 0) { // Ignore the root node and other nasty nodes
- // We know that the immediate dominator should already have a node,
- // because we are traversing the CFG in depth first order!
- //
- assert(Nodes[IDom] && "No node for IDOM?");
- Node *IDomNode = Nodes[IDom];
-
- // Add a new tree node for this BasicBlock, and link it as a child of
- // IDomNode
- Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
- }
- }
-}
-#endif
-
void DominatorTree::calculate(const DominatorSet &DS) {
Nodes[Root] = new Node(Root, 0); // Add a node for the root...
- if (!isPostDominator()) {
- // Iterate over all nodes in depth first order...
- for (df_iterator<BasicBlock*> I = df_begin(Root), E = df_end(Root);
- I != E; ++I) {
- BasicBlock *BB = *I;
- const DominatorSet::DomSetType &Dominators = DS.getDominators(BB);
- unsigned DomSetSize = Dominators.size();
- if (DomSetSize == 1) continue; // Root node... IDom = null
+ // Iterate over all nodes in depth first order...
+ for (df_iterator<BasicBlock*> I = df_begin(Root), E = df_end(Root);
+ I != E; ++I) {
+ BasicBlock *BB = *I;
+ const DominatorSet::DomSetType &Dominators = DS.getDominators(BB);
+ unsigned DomSetSize = Dominators.size();
+ if (DomSetSize == 1) continue; // Root node... IDom = null
- // Loop over all dominators of this node. This corresponds to looping over
- // nodes in the dominator chain, looking for a node whose dominator set is
- // equal to the current nodes, except that the current node does not exist
- // in it. This means that it is one level higher in the dom chain than the
- // current node, and it is our idom! We know that we have already added
- // a DominatorTree node for our idom, because the idom must be a
- // predecessor in the depth first order that we are iterating through the
- // function.
+ // Loop over all dominators of this node. This corresponds to looping over
+ // nodes in the dominator chain, looking for a node whose dominator set is
+ // equal to the current nodes, except that the current node does not exist
+ // in it. This means that it is one level higher in the dom chain than the
+ // current node, and it is our idom! We know that we have already added
+ // a DominatorTree node for our idom, because the idom must be a
+ // predecessor in the depth first order that we are iterating through the
+ // function.
+ //
+ DominatorSet::DomSetType::const_iterator I = Dominators.begin();
+ DominatorSet::DomSetType::const_iterator End = Dominators.end();
+ for (; I != End; ++I) { // Iterate over dominators...
+ // All of our dominators should form a chain, where the number of
+ // elements in the dominator set indicates what level the node is at in
+ // the chain. We want the node immediately above us, so it will have
+ // an identical dominator set, except that BB will not dominate it...
+ // therefore it's dominator set size will be one less than BB's...
//
- DominatorSet::DomSetType::const_iterator I = Dominators.begin();
- DominatorSet::DomSetType::const_iterator End = Dominators.end();
- for (; I != End; ++I) { // Iterate over dominators...
- // All of our dominators should form a chain, where the number of
- // elements in the dominator set indicates what level the node is at in
- // the chain. We want the node immediately above us, so it will have
- // an identical dominator set, except that BB will not dominate it...
- // therefore it's dominator set size will be one less than BB's...
- //
- if (DS.getDominators(*I).size() == DomSetSize - 1) {
- // We know that the immediate dominator should already have a node,
- // because we are traversing the CFG in depth first order!
- //
- Node *IDomNode = Nodes[*I];
- assert(IDomNode && "No node for IDOM?");
-
- // Add a new tree node for this BasicBlock, and link it as a child of
- // IDomNode
- Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
- break;
- }
+ if (DS.getDominators(*I).size() == DomSetSize - 1) {
+ // We know that the immediate dominator should already have a node,
+ // because we are traversing the CFG in depth first order!
+ //
+ Node *IDomNode = Nodes[*I];
+ assert(IDomNode && "No node for IDOM?");
+
+ // Add a new tree node for this BasicBlock, and link it as a child of
+ // IDomNode
+ Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
+ break;
}
}
- } else if (Root) {
+ }
+}
+
+
+void PostDominatorTree::calculate(const PostDominatorSet &DS) {
+ Nodes[Root] = new Node(Root, 0); // Add a node for the root...
+
+ if (Root) {
// Iterate over all nodes in depth first order...
for (idf_iterator<BasicBlock*> I = idf_begin(Root), E = idf_end(Root);
I != E; ++I) {
@@ -339,11 +308,11 @@
//===----------------------------------------------------------------------===//
AnalysisID DominanceFrontier::ID(AnalysisID::create<DominanceFrontier>(), true);
-AnalysisID DominanceFrontier::PostDomID(AnalysisID::create<DominanceFrontier>(), true);
+AnalysisID PostDominanceFrontier::ID(AnalysisID::create<PostDominanceFrontier>(), true);
const DominanceFrontier::DomSetType &
-DominanceFrontier::calcDomFrontier(const DominatorTree &DT,
- const DominatorTree::Node *Node) {
+DominanceFrontier::calculate(const DominatorTree &DT,
+ const DominatorTree::Node *Node) {
// Loop over CFG successors to calculate DFlocal[Node]
BasicBlock *BB = Node->getNode();
DomSetType &S = Frontiers[BB]; // The new set to fill in...
@@ -362,7 +331,7 @@
for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end();
NI != NE; ++NI) {
DominatorTree::Node *IDominee = *NI;
- const DomSetType &ChildDF = calcDomFrontier(DT, IDominee);
+ const DomSetType &ChildDF = calculate(DT, IDominee);
DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
for (; CDFI != CDFE; ++CDFI) {
@@ -375,8 +344,8 @@
}
const DominanceFrontier::DomSetType &
-DominanceFrontier::calcPostDomFrontier(const DominatorTree &DT,
- const DominatorTree::Node *Node) {
+PostDominanceFrontier::calculate(const PostDominatorTree &DT,
+ const DominatorTree::Node *Node) {
// Loop over CFG successors to calculate DFlocal[Node]
BasicBlock *BB = Node->getNode();
DomSetType &S = Frontiers[BB]; // The new set to fill in...
@@ -393,10 +362,10 @@
// Loop through and visit the nodes that Node immediately dominates (Node's
// children in the IDomTree)
//
- for (DominatorTree::Node::const_iterator NI = Node->begin(), NE = Node->end();
- NI != NE; ++NI) {
+ for (PostDominatorTree::Node::const_iterator
+ NI = Node->begin(), NE = Node->end(); NI != NE; ++NI) {
DominatorTree::Node *IDominee = *NI;
- const DomSetType &ChildDF = calcPostDomFrontier(DT, IDominee);
+ const DomSetType &ChildDF = calculate(DT, IDominee);
DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
for (; CDFI != CDFE; ++CDFI) {
diff --git a/tools/analyze/analyze.cpp b/tools/analyze/analyze.cpp
index 7373741..7a8c36a 100644
--- a/tools/analyze/analyze.cpp
+++ b/tools/analyze/analyze.cpp
@@ -116,10 +116,6 @@
-template <class PassType, class PassName, AnalysisID &ID>
-Pass *New() {
- return new PassPrinter<PassType, PassName>(ID);
-}
template <class PassType, class PassName>
Pass *New() {
return new PassPrinter<PassType, PassName>(PassName::ID);
@@ -295,10 +291,10 @@
{ domtree , New<FunctionPass, DominatorTree> },
{ domfrontier , New<FunctionPass, DominanceFrontier> },
- { postdomset , New<FunctionPass, DominatorSet, DominatorSet::PostDomID> },
- { postidom , New<FunctionPass, ImmediateDominators, ImmediateDominators::PostDomID> },
- { postdomtree , New<FunctionPass, DominatorTree, DominatorTree::PostDomID> },
- { postdomfrontier , New<FunctionPass, DominanceFrontier, DominanceFrontier::PostDomID> },
+ { postdomset , New<FunctionPass, PostDominatorSet> },
+ { postidom , New<FunctionPass, ImmediatePostDominators> },
+ { postdomtree , New<FunctionPass, PostDominatorTree> },
+ { postdomfrontier , New<FunctionPass, PostDominanceFrontier> },
};
int main(int argc, char **argv) {