A("domset", "Dominator Set Construction", true);
// dominates - Return true if A dominates B. This performs the special checks
-// neccesary if A and B are in the same basic block.
+// necessary if A and B are in the same basic block.
//
bool DominatorSetBase::dominates(Instruction *A, Instruction *B) const {
BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
BasicBlock *BB = *It;
pred_iterator PI = pred_begin(BB), PEnd = pred_end(BB);
if (PI != PEnd) { // Is there SOME predecessor?
- // Loop until we get to a predecessor that has had it's dom set filled
+ // Loop until we get to a predecessor that has had its dom set filled
// in at least once. We are guaranteed to have this because we are
// traversing the graph in DFO and have handled start nodes specially,
// except when there are unreachable blocks.
if (PredSet.size())
set_intersect(WorkingSet, PredSet);
}
- } else {
- // Otherwise this block is unreachable. it doesn't really matter what
- // we use for the dominator set for the node...
- //
- WorkingSet = Doms[Root];
}
- } else if (BB != Root) {
- // If this isn't the root basic block and it has no predecessors, it
- // must be an unreachable block. Fib a bit by saying that the root node
- // dominates this unreachable node. This isn't exactly true, because
- // there is no path from the entry node to this node, but it is sorta
- // true because any paths to this node would have to go through the
- // entry node.
- //
- // This allows for dominator properties to be built for unreachable code
- // in a reasonable manner.
- //
- WorkingSet = Doms[Root];
+ } else {
+ assert(Roots.size() == 1 && BB == Roots[0] &&
+ "We got into unreachable code somehow!");
}
WorkingSet.insert(BB); // A block always dominates itself
DomSetType &BBSet = Doms[BB];
if (BBSet != WorkingSet) {
+ //assert(WorkingSet.size() > BBSet.size() && "Must only grow sets!");
BBSet.swap(WorkingSet); // Constant time operation!
Changed = true; // The sets changed.
}
// specified function.
//
bool DominatorSet::runOnFunction(Function &F) {
- Root = &F.getEntryNode();
+ BasicBlock *Root = &F.getEntryBlock();
+ Roots.clear();
+ Roots.push_back(Root);
assert(pred_begin(Root) == pred_end(Root) &&
"Root node has predecessors in function!");
recalculate();
}
void DominatorSet::recalculate() {
+ assert(Roots.size() == 1 && "DominatorSet should have single root block!");
Doms.clear(); // Reset from the last time we were run...
// Calculate dominator sets for the reachable basic blocks...
- calculateDominatorsFromBlock(Root);
+ calculateDominatorsFromBlock(Roots[0]);
- // Every basic block in the function should at least dominate themselves, and
- // thus every basic block should have an entry in Doms. The one case where we
- // miss this is when a basic block is unreachable. To get these we now do an
- // extra pass over the function, calculating dominator information for
+
+ // Loop through the function, ensuring that every basic block has at least an
+ // empty set of nodes. This is important for the case when there is
// unreachable blocks.
- //
- Function *F = Root->getParent();
- for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
- if (Doms[I].count(I) == 0)
- calculateDominatorsFromBlock(I);
+ Function *F = Roots[0]->getParent();
+ for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) Doms[I];
}
static std::ostream &operator<<(std::ostream &o,
const std::set<BasicBlock*> &BBs) {
for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
- I != E; ++I) {
- o << " ";
- WriteAsOperand(o, *I, false);
- o << "\n";
- }
+ I != E; ++I)
+ if (*I)
+ WriteAsOperand(o, *I, false);
+ else
+ o << " <<exit node>>";
return o;
}
void DominatorSetBase::print(std::ostream &o) const {
for (const_iterator I = begin(), E = end(); I != E; ++I) {
- o << "=============================--------------------------------\n"
- << "\nDominator Set For Basic Block: ";
- WriteAsOperand(o, I->first, false);
- o << "\n-------------------------------\n" << I->second << "\n";
+ o << " DomSet For BB: ";
+ if (I->first)
+ WriteAsOperand(o, I->first, false);
+ else
+ o << " <<exit node>>";
+ o << " is:\t" << I->second << "\n";
}
}
void ImmediateDominatorsBase::print(std::ostream &o) const {
for (const_iterator I = begin(), E = end(); I != E; ++I) {
- o << "=============================--------------------------------\n"
- << "\nImmediate Dominator For Basic Block:";
- WriteAsOperand(o, I->first, false);
+ o << " Immediate Dominator For Basic Block:";
+ if (I->first)
+ WriteAsOperand(o, I->first, false);
+ else
+ o << " <<exit node>>";
o << " is:";
- WriteAsOperand(o, I->second, false);
+ if (I->second)
+ WriteAsOperand(o, I->second, false);
+ else
+ o << " <<exit node>>";
o << "\n";
}
+ o << "\n";
}
for (NodeMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I)
delete I->second;
Nodes.clear();
+ RootNode = 0;
}
-void DominatorTreeBase::Node2::setIDom(Node2 *NewIDom) {
+void DominatorTreeBase::Node::setIDom(Node *NewIDom) {
assert(IDom && "No immediate dominator?");
if (IDom != NewIDom) {
std::vector<Node*>::iterator I =
void DominatorTree::calculate(const DominatorSet &DS) {
- Nodes[Root] = new Node(Root, 0); // Add a node for the root...
+ assert(Roots.size() == 1 && "DominatorTree should have 1 root block!");
+ BasicBlock *Root = Roots[0];
+ Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root...
// Iterate over all nodes in depth first order...
for (df_iterator<BasicBlock*> I = df_begin(Root), E = df_end(Root);
static std::ostream &operator<<(std::ostream &o,
const DominatorTreeBase::Node *Node) {
- return o << Node->getNode()
- << "\n------------------------------------------\n";
+ if (Node->getBlock())
+ WriteAsOperand(o, Node->getBlock(), false);
+ else
+ o << " <<exit node>>";
+ return o << "\n";
}
static void PrintDomTree(const DominatorTreeBase::Node *N, std::ostream &o,
unsigned Lev) {
- o << "Level #" << Lev << ": " << N;
+ o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N;
for (DominatorTreeBase::Node::const_iterator I = N->begin(), E = N->end();
- I != E; ++I) {
+ I != E; ++I)
PrintDomTree(*I, o, Lev+1);
- }
}
void DominatorTreeBase::print(std::ostream &o) const {
o << "=============================--------------------------------\n"
<< "Inorder Dominator Tree:\n";
- PrintDomTree(Nodes.find(getRoot())->second, o, 1);
+ PrintDomTree(getRootNode(), o, 1);
}
DominanceFrontier::calculate(const DominatorTree &DT,
const DominatorTree::Node *Node) {
// Loop over CFG successors to calculate DFlocal[Node]
- BasicBlock *BB = Node->getNode();
+ BasicBlock *BB = Node->getBlock();
DomSetType &S = Frontiers[BB]; // The new set to fill in...
for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB);
void DominanceFrontierBase::print(std::ostream &o) const {
for (const_iterator I = begin(), E = end(); I != E; ++I) {
- o << "=============================--------------------------------\n"
- << "\nDominance Frontier For Basic Block\n";
- WriteAsOperand(o, I->first, false);
- o << " is: \n" << I->second << "\n";
+ o << " DomFrontier for BB";
+ if (I->first)
+ WriteAsOperand(o, I->first, false);
+ else
+ o << " <<exit node>>";
+ o << " is:\t" << I->second << "\n";
}
}
projects / oota-llvm.git / blobdiff