#include "llvm/Assembly/Writer.h"
#include "Support/DepthFirstIterator.h"
#include "Support/SetOperations.h"
-using std::set;
//===----------------------------------------------------------------------===//
// DominatorSet Implementation
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.
+ // traversing the graph in DFO and have handled start nodes specially,
+ // except when there are unreachable blocks.
//
- while (Doms[*PI].empty()) ++PI;
- WorkingSet = Doms[*PI];
-
- for (++PI; PI != PEnd; ++PI) { // Intersect all of the predecessor sets
- DomSetType &PredSet = Doms[*PI];
- if (PredSet.size())
- set_intersect(WorkingSet, PredSet);
- }
+ while (PI != PEnd && Doms[*PI].empty()) ++PI;
+ if (PI != PEnd) { // Not unreachable code case?
+ WorkingSet = Doms[*PI];
+
+ // Intersect all of the predecessor sets
+ for (++PI; PI != PEnd; ++PI) {
+ DomSetType &PredSet = Doms[*PI];
+ if (PredSet.size())
+ set_intersect(WorkingSet, PredSet);
+ }
+ }
+ } else {
+ assert(BB == Root && "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) {
- 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!");
+ recalculate();
+ return false;
+}
+
+void DominatorSet::recalculate() {
+ Doms.clear(); // Reset from the last time we were run...
// Calculate dominator sets for the reachable basic blocks...
calculateDominatorsFromBlock(Root);
- // 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
- // unreachable blocks.
- //
- for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
- if (Doms[I].empty()) {
- calculateDominatorsFromBlock(I);
- }
- return false;
+ // 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) Doms[I];
}
-static std::ostream &operator<<(std::ostream &o, const set<BasicBlock*> &BBs) {
- for (set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
+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);
}
void DominatorSetBase::print(std::ostream &o) const {
- for (const_iterator I = begin(), E = end(); I != E; ++I)
+ for (const_iterator I = begin(), E = end(); I != E; ++I) {
o << "=============================--------------------------------\n"
- << "\nDominator Set For Basic Block\n" << I->first
- << "-------------------------------\n" << I->second << "\n";
+ << "\nDominator Set For Basic Block: ";
+ WriteAsOperand(o, I->first, false);
+ o << "\n-------------------------------\n" << I->second << "\n";
+ }
}
//===----------------------------------------------------------------------===//
}
void ImmediateDominatorsBase::print(std::ostream &o) const {
- for (const_iterator I = begin(), E = end(); I != E; ++I)
+ for (const_iterator I = begin(), E = end(); I != E; ++I) {
o << "=============================--------------------------------\n"
- << "\nImmediate Dominator For Basic Block\n" << *I->first
- << "is: \n" << *I->second << "\n";
+ << "\nImmediate Dominator For Basic Block:";
+ WriteAsOperand(o, I->first, false);
+ o << " is:";
+ WriteAsOperand(o, I->second, false);
+ o << "\n";
+ }
}
Nodes.clear();
}
+void DominatorTreeBase::Node2::setIDom(Node2 *NewIDom) {
+ assert(IDom && "No immediate dominator?");
+ if (IDom != NewIDom) {
+ std::vector<Node*>::iterator I =
+ std::find(IDom->Children.begin(), IDom->Children.end(), this);
+ assert(I != IDom->Children.end() &&
+ "Not in immediate dominator children set!");
+ // I am no longer your child...
+ IDom->Children.erase(I);
+
+ // Switch to new dominator
+ IDom = NewIDom;
+ IDom->Children.push_back(this);
+ }
+}
+
+
void DominatorTree::calculate(const DominatorSet &DS) {
Nodes[Root] = new Node(Root, 0); // Add a node for the root...
projects / oota-llvm.git / blobdiff