#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/DepthFirstIterator.h"
-#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/DominatorInternals.h"
+#include "llvm/Assembly/Writer.h"
#include "llvm/Instructions.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/CommandLine.h"
//===----------------------------------------------------------------------===//
//
// Provide public access to DominatorTree information. Implementation details
-// can be found in DominatorCalculation.h.
+// can be found in DominatorInternals.h.
//
//===----------------------------------------------------------------------===//
DominatorTree OtherDT;
OtherDT.getBase().recalculate(F);
- assert(!compare(OtherDT) && "Invalid DominatorTree info!");
+ if (compare(OtherDT)) {
+ errs() << "DominatorTree is not up to date!\nComputed:\n";
+ print(errs());
+ errs() << "\nActual:\n";
+ OtherDT.print(errs());
+ abort();
+ }
}
void DominatorTree::print(raw_ostream &OS, const Module *) const {
return &*I == A;
}
-
-
-
-//===----------------------------------------------------------------------===//
-// DominanceFrontier Implementation
-//===----------------------------------------------------------------------===//
-
-char DominanceFrontier::ID = 0;
-INITIALIZE_PASS_BEGIN(DominanceFrontier, "domfrontier",
- "Dominance Frontier Construction", true, true)
-INITIALIZE_PASS_DEPENDENCY(DominatorTree)
-INITIALIZE_PASS_END(DominanceFrontier, "domfrontier",
- "Dominance Frontier Construction", true, true)
-
-void DominanceFrontier::verifyAnalysis() const {
- if (!VerifyDomInfo) return;
-
- DominatorTree &DT = getAnalysis<DominatorTree>();
-
- DominanceFrontier OtherDF;
- const std::vector<BasicBlock*> &DTRoots = DT.getRoots();
- OtherDF.calculate(DT, DT.getNode(DTRoots[0]));
- assert(!compare(OtherDF) && "Invalid DominanceFrontier info!");
-}
-
-// NewBB is split and now it has one successor. Update dominance frontier to
-// reflect this change.
-void DominanceFrontier::splitBlock(BasicBlock *NewBB) {
- assert(NewBB->getTerminator()->getNumSuccessors() == 1 &&
- "NewBB should have a single successor!");
- BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0);
-
- // NewBBSucc inherits original NewBB frontier.
- DominanceFrontier::iterator NewBBI = find(NewBB);
- if (NewBBI != end())
- addBasicBlock(NewBBSucc, NewBBI->second);
-
- // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the
- // DF(NewBBSucc) without the stuff that the new block does not dominate
- // a predecessor of.
- DominatorTree &DT = getAnalysis<DominatorTree>();
- DomTreeNode *NewBBNode = DT.getNode(NewBB);
- DomTreeNode *NewBBSuccNode = DT.getNode(NewBBSucc);
- if (DT.dominates(NewBBNode, NewBBSuccNode)) {
- DominanceFrontier::iterator DFI = find(NewBBSucc);
- if (DFI != end()) {
- DominanceFrontier::DomSetType Set = DFI->second;
- // Filter out stuff in Set that we do not dominate a predecessor of.
- for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(),
- E = Set.end(); SetI != E;) {
- bool DominatesPred = false;
- for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI);
- PI != E; ++PI)
- if (DT.dominates(NewBBNode, DT.getNode(*PI))) {
- DominatesPred = true;
- break;
- }
- if (!DominatesPred)
- Set.erase(SetI++);
- else
- ++SetI;
- }
-
- if (NewBBI != end()) {
- for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(),
- E = Set.end(); SetI != E; ++SetI) {
- BasicBlock *SB = *SetI;
- addToFrontier(NewBBI, SB);
- }
- } else
- addBasicBlock(NewBB, Set);
- }
-
- } else {
- // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate
- // NewBBSucc, but it does dominate itself (and there is an edge (NewBB ->
- // NewBBSucc)). NewBBSucc is the single successor of NewBB.
- DominanceFrontier::DomSetType NewDFSet;
- NewDFSet.insert(NewBBSucc);
- addBasicBlock(NewBB, NewDFSet);
- }
-
- // Now update dominance frontiers which either used to contain NewBBSucc
- // or which now need to include NewBB.
-
- // Collect the set of blocks which dominate a predecessor of NewBB or
- // NewSuccBB and which don't dominate both. This is an initial
- // approximation of the blocks whose dominance frontiers will need updates.
- SmallVector<DomTreeNode *, 16> AllPredDoms;
-
- // Compute the block which dominates both NewBBSucc and NewBB. This is
- // the immediate dominator of NewBBSucc unless NewBB dominates NewBBSucc.
- // The code below which climbs dominator trees will stop at this point,
- // because from this point up, dominance frontiers are unaffected.
- DomTreeNode *DominatesBoth = 0;
- if (NewBBSuccNode) {
- DominatesBoth = NewBBSuccNode->getIDom();
- if (DominatesBoth == NewBBNode)
- DominatesBoth = NewBBNode->getIDom();
- }
-
- // Collect the set of all blocks which dominate a predecessor of NewBB.
- SmallPtrSet<DomTreeNode *, 8> NewBBPredDoms;
- for (pred_iterator PI = pred_begin(NewBB), E = pred_end(NewBB); PI != E; ++PI)
- for (DomTreeNode *DTN = DT.getNode(*PI); DTN; DTN = DTN->getIDom()) {
- if (DTN == DominatesBoth)
- break;
- if (!NewBBPredDoms.insert(DTN))
- break;
- AllPredDoms.push_back(DTN);
- }
-
- // Collect the set of all blocks which dominate a predecessor of NewSuccBB.
- SmallPtrSet<DomTreeNode *, 8> NewBBSuccPredDoms;
- for (pred_iterator PI = pred_begin(NewBBSucc),
- E = pred_end(NewBBSucc); PI != E; ++PI)
- for (DomTreeNode *DTN = DT.getNode(*PI); DTN; DTN = DTN->getIDom()) {
- if (DTN == DominatesBoth)
- break;
- if (!NewBBSuccPredDoms.insert(DTN))
- break;
- if (!NewBBPredDoms.count(DTN))
- AllPredDoms.push_back(DTN);
- }
-
- // Visit all relevant dominance frontiers and make any needed updates.
- for (SmallVectorImpl<DomTreeNode *>::const_iterator I = AllPredDoms.begin(),
- E = AllPredDoms.end(); I != E; ++I) {
- DomTreeNode *DTN = *I;
- iterator DFI = find((*I)->getBlock());
-
- // Only consider nodes that have NewBBSucc in their dominator frontier.
- if (DFI == end() || !DFI->second.count(NewBBSucc)) continue;
-
- // If the block dominates a predecessor of NewBB but does not properly
- // dominate NewBB itself, add NewBB to its dominance frontier.
- if (NewBBPredDoms.count(DTN) &&
- !DT.properlyDominates(DTN, NewBBNode))
- addToFrontier(DFI, NewBB);
-
- // If the block does not dominate a predecessor of NewBBSucc or
- // properly dominates NewBBSucc itself, remove NewBBSucc from its
- // dominance frontier.
- if (!NewBBSuccPredDoms.count(DTN) ||
- DT.properlyDominates(DTN, NewBBSuccNode))
- removeFromFrontier(DFI, NewBBSucc);
- }
-}
-
-namespace {
- class DFCalculateWorkObject {
- public:
- DFCalculateWorkObject(BasicBlock *B, BasicBlock *P,
- const DomTreeNode *N,
- const DomTreeNode *PN)
- : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
- BasicBlock *currentBB;
- BasicBlock *parentBB;
- const DomTreeNode *Node;
- const DomTreeNode *parentNode;
- };
-}
-
-const DominanceFrontier::DomSetType &
-DominanceFrontier::calculate(const DominatorTree &DT,
- const DomTreeNode *Node) {
- BasicBlock *BB = Node->getBlock();
- DomSetType *Result = NULL;
-
- std::vector<DFCalculateWorkObject> workList;
- SmallPtrSet<BasicBlock *, 32> visited;
-
- workList.push_back(DFCalculateWorkObject(BB, NULL, Node, NULL));
- do {
- DFCalculateWorkObject *currentW = &workList.back();
- assert (currentW && "Missing work object.");
-
- BasicBlock *currentBB = currentW->currentBB;
- BasicBlock *parentBB = currentW->parentBB;
- const DomTreeNode *currentNode = currentW->Node;
- const DomTreeNode *parentNode = currentW->parentNode;
- assert (currentBB && "Invalid work object. Missing current Basic Block");
- assert (currentNode && "Invalid work object. Missing current Node");
- DomSetType &S = Frontiers[currentBB];
-
- // Visit each block only once.
- if (visited.count(currentBB) == 0) {
- visited.insert(currentBB);
-
- // Loop over CFG successors to calculate DFlocal[currentNode]
- for (succ_iterator SI = succ_begin(currentBB), SE = succ_end(currentBB);
- SI != SE; ++SI) {
- // Does Node immediately dominate this successor?
- if (DT[*SI]->getIDom() != currentNode)
- S.insert(*SI);
- }
- }
-
- // At this point, S is DFlocal. Now we union in DFup's of our children...
- // Loop through and visit the nodes that Node immediately dominates (Node's
- // children in the IDomTree)
- bool visitChild = false;
- for (DomTreeNode::const_iterator NI = currentNode->begin(),
- NE = currentNode->end(); NI != NE; ++NI) {
- DomTreeNode *IDominee = *NI;
- BasicBlock *childBB = IDominee->getBlock();
- if (visited.count(childBB) == 0) {
- workList.push_back(DFCalculateWorkObject(childBB, currentBB,
- IDominee, currentNode));
- visitChild = true;
- }
- }
-
- // If all children are visited or there is any child then pop this block
- // from the workList.
- if (!visitChild) {
-
- if (!parentBB) {
- Result = &S;
- break;
- }
-
- DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
- DomSetType &parentSet = Frontiers[parentBB];
- for (; CDFI != CDFE; ++CDFI) {
- if (!DT.properlyDominates(parentNode, DT[*CDFI]))
- parentSet.insert(*CDFI);
- }
- workList.pop_back();
- }
-
- } while (!workList.empty());
-
- return *Result;
-}
-
-void DominanceFrontierBase::print(raw_ostream &OS, const Module* ) const {
- for (const_iterator I = begin(), E = end(); I != E; ++I) {
- OS << " DomFrontier for BB ";
- if (I->first)
- WriteAsOperand(OS, I->first, false);
- else
- OS << " <<exit node>>";
- OS << " is:\t";
-
- const std::set<BasicBlock*> &BBs = I->second;
-
- for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
- I != E; ++I) {
- OS << ' ';
- if (*I)
- WriteAsOperand(OS, *I, false);
- else
- OS << "<<exit node>>";
- }
- OS << "\n";
- }
-}
-
-void DominanceFrontierBase::dump() const {
- print(dbgs());
-}
-
projects / oota-llvm.git / blobdiff