X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FVMCore%2FDominators.cpp;h=a1eaf4aa971f4737381235a5eb9996edc0cca6f6;hb=d070d1e56fbfdad752342838dda39e14582ccad5;hp=2fbb6e4bebe60a207f386f48929b9695e1db7cb9;hpb=d75405fe95660877f62064211e252c8c8c4c05ea;p=oota-llvm.git diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 2fbb6e4bebe..a1eaf4aa971 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -20,8 +20,10 @@ #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SetOperations.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/Instructions.h" #include "llvm/Support/Streams.h" +#include "DominatorCalculation.h" #include using namespace llvm; @@ -42,20 +44,8 @@ static std::ostream &operator<<(std::ostream &o, // DominatorTree Implementation //===----------------------------------------------------------------------===// // -// DominatorTree construction - This pass constructs immediate dominator -// information for a flow-graph based on the algorithm described in this -// document: -// -// A Fast Algorithm for Finding Dominators in a Flowgraph -// T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. -// -// This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and -// LINK, but it turns out that the theoretically slower O(n*log(n)) -// implementation is actually faster than the "efficient" algorithm (even for -// large CFGs) because the constant overheads are substantially smaller. The -// lower-complexity version can be enabled with the following #define: -// -#define BALANCE_IDOM_TREE 0 +// Provide public access to DominatorTree information. Implementation details +// can be found in DominatorCalculation.h. // //===----------------------------------------------------------------------===// @@ -63,261 +53,118 @@ char DominatorTree::ID = 0; static RegisterPass E("domtree", "Dominator Tree Construction", true); -unsigned DominatorTree::DFSPass(BasicBlock *V, InfoRec &VInfo, - 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 - 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, SuccVInfo, N); - } - } -#else - std::vector > 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 +// NewBB is split and now it has one successor. Update dominator tree to +// reflect this change. +void DominatorTree::splitBlock(BasicBlock *NewBB) { + assert(NewBB->getTerminator()->getNumSuccessors() == 1 + && "NewBB should have a single successor!"); + BasicBlock *NewBBSucc = NewBB->getTerminator()->getSuccessor(0); + + std::vector PredBlocks; + for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB); + PI != PE; ++PI) + PredBlocks.push_back(*PI); + + assert(!PredBlocks.empty() && "No predblocks??"); + + // The newly inserted basic block will dominate existing basic blocks iff the + // PredBlocks dominate all of the non-pred blocks. If all predblocks dominate + // the non-pred blocks, then they all must be the same block! + // + bool NewBBDominatesNewBBSucc = true; + { + BasicBlock *OnePred = PredBlocks[0]; + unsigned i = 1, e = PredBlocks.size(); + for (i = 1; !isReachableFromEntry(OnePred); ++i) { + assert(i != e && "Didn't find reachable pred?"); + OnePred = PredBlocks[i]; } - // 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; -} - -void DominatorTree::Compress(BasicBlock *VIn) { - - std::vector Work; - std::set Visited; - InfoRec &VInInfo = Info[VIn]; - BasicBlock *VInAncestor = VInInfo.Ancestor; - InfoRec &VInVAInfo = Info[VInAncestor]; - - if (VInVAInfo.Ancestor != 0) - Work.push_back(VIn); - - while (!Work.empty()) { - BasicBlock *V = Work.back(); - InfoRec &VInfo = Info[V]; - BasicBlock *VAncestor = VInfo.Ancestor; - InfoRec &VAInfo = Info[VAncestor]; - - // Process Ancestor first - if (Visited.count(VAncestor) == 0 && VAInfo.Ancestor != 0) { - Work.push_back(VAncestor); - Visited.insert(VAncestor); - continue; - } - Work.pop_back(); + for (; i != e; ++i) + if (PredBlocks[i] != OnePred && isReachableFromEntry(OnePred)) { + NewBBDominatesNewBBSucc = false; + break; + } - // Update VINfo based on Ancestor info - if (VAInfo.Ancestor == 0) - continue; - BasicBlock *VAncestorLabel = VAInfo.Label; - BasicBlock *VLabel = VInfo.Label; - if (Info[VAncestorLabel].Semi < Info[VLabel].Semi) - VInfo.Label = VAncestorLabel; - VInfo.Ancestor = VAInfo.Ancestor; + if (NewBBDominatesNewBBSucc) + for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); + PI != E; ++PI) + if (*PI != NewBB && !dominates(NewBBSucc, *PI)) { + NewBBDominatesNewBBSucc = false; + break; + } } -} -BasicBlock *DominatorTree::Eval(BasicBlock *V) { - InfoRec &VInfo = Info[V]; -#if !BALANCE_IDOM_TREE - // Higher-complexity but faster implementation - if (VInfo.Ancestor == 0) - return V; - Compress(V); - return VInfo.Label; -#else - // Lower-complexity but slower implementation - if (VInfo.Ancestor == 0) - return VInfo.Label; - Compress(V); - BasicBlock *VLabel = VInfo.Label; - - BasicBlock *VAncestorLabel = Info[VInfo.Ancestor].Label; - if (Info[VAncestorLabel].Semi >= Info[VLabel].Semi) - return VLabel; - else - return VAncestorLabel; -#endif -} + // The other scenario where the new block can dominate its successors are when + // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc + // already. + if (!NewBBDominatesNewBBSucc) { + NewBBDominatesNewBBSucc = true; + for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); + PI != E; ++PI) + if (*PI != NewBB && !dominates(NewBBSucc, *PI)) { + NewBBDominatesNewBBSucc = false; + break; + } + } -void DominatorTree::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){ -#if !BALANCE_IDOM_TREE - // Higher-complexity but faster implementation - WInfo.Ancestor = V; -#else - // Lower-complexity but slower implementation - BasicBlock *WLabel = WInfo.Label; - unsigned WLabelSemi = Info[WLabel].Semi; - BasicBlock *S = W; - InfoRec *SInfo = &Info[S]; - - BasicBlock *SChild = SInfo->Child; - InfoRec *SChildInfo = &Info[SChild]; - - while (WLabelSemi < Info[SChildInfo->Label].Semi) { - BasicBlock *SChildChild = SChildInfo->Child; - if (SInfo->Size+Info[SChildChild].Size >= 2*SChildInfo->Size) { - SChildInfo->Ancestor = S; - SInfo->Child = SChild = SChildChild; - SChildInfo = &Info[SChild]; - } else { - SChildInfo->Size = SInfo->Size; - S = SInfo->Ancestor = SChild; - SInfo = SChildInfo; - SChild = SChildChild; - SChildInfo = &Info[SChild]; + // Find NewBB's immediate dominator and create new dominator tree node for + // NewBB. + BasicBlock *NewBBIDom = 0; + unsigned i = 0; + for (i = 0; i < PredBlocks.size(); ++i) + if (isReachableFromEntry(PredBlocks[i])) { + NewBBIDom = PredBlocks[i]; + break; } + assert(i != PredBlocks.size() && "No reachable preds?"); + for (i = i + 1; i < PredBlocks.size(); ++i) { + if (isReachableFromEntry(PredBlocks[i])) + NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]); } - - InfoRec &VInfo = Info[V]; - SInfo->Label = WLabel; - - assert(V != W && "The optimization here will not work in this case!"); - unsigned WSize = WInfo.Size; - unsigned VSize = (VInfo.Size += WSize); - - if (VSize < 2*WSize) - std::swap(S, VInfo.Child); - - while (S) { - SInfo = &Info[S]; - SInfo->Ancestor = V; - S = SInfo->Child; + assert(NewBBIDom && "No immediate dominator found??"); + + // Create the new dominator tree node... and set the idom of NewBB. + DomTreeNode *NewBBNode = addNewBlock(NewBB, NewBBIDom); + + // If NewBB strictly dominates other blocks, then it is now the immediate + // dominator of NewBBSucc. Update the dominator tree as appropriate. + if (NewBBDominatesNewBBSucc) { + DomTreeNode *NewBBSuccNode = getNode(NewBBSucc); + changeImmediateDominator(NewBBSuccNode, NewBBNode); } -#endif } -void DominatorTree::calculate(Function& F) { - BasicBlock* Root = Roots[0]; - - // Add a node for the root... - DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0); - - Vertex.push_back(0); - - // Step #1: Number blocks in depth-first order and initialize variables used - // in later stages of the algorithm. - unsigned N = 0; - for (unsigned i = 0, e = Roots.size(); i != e; ++i) - N = DFSPass(Roots[i], Info[Roots[i]], 0); - - for (unsigned i = N; i >= 2; --i) { - BasicBlock *W = Vertex[i]; - InfoRec &WInfo = Info[W]; - - // Step #2: Calculate the semidominators of all vertices - for (pred_iterator PI = pred_begin(W), E = pred_end(W); PI != E; ++PI) - if (Info.count(*PI)) { // Only if this predecessor is reachable! - unsigned SemiU = Info[Eval(*PI)].Semi; - if (SemiU < WInfo.Semi) - WInfo.Semi = SemiU; - } - - Info[Vertex[WInfo.Semi]].Bucket.push_back(W); - - BasicBlock *WParent = WInfo.Parent; - Link(WParent, W, WInfo); +void DominatorTreeBase::updateDFSNumbers() { + unsigned DFSNum = 0; - // Step #3: Implicitly define the immediate dominator of vertices - std::vector &WParentBucket = Info[WParent].Bucket; - while (!WParentBucket.empty()) { - BasicBlock *V = WParentBucket.back(); - WParentBucket.pop_back(); - BasicBlock *U = Eval(V); - IDoms[V] = Info[U].Semi < Info[V].Semi ? U : WParent; - } - } - - // Step #4: Explicitly define the immediate dominator of each vertex - for (unsigned i = 2; i <= N; ++i) { - BasicBlock *W = Vertex[i]; - BasicBlock *&WIDom = IDoms[W]; - if (WIDom != Vertex[Info[W].Semi]) - WIDom = IDoms[WIDom]; - } - - // Loop over all of the reachable blocks in the function... - for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) - if (BasicBlock *ImmDom = getIDom(I)) { // Reachable block. - DomTreeNode *&BBNode = DomTreeNodes[I]; - if (!BBNode) { // Haven't calculated this node yet? - // Get or calculate the node for the immediate dominator - DomTreeNode *IDomNode = getNodeForBlock(ImmDom); - - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - DomTreeNode *C = new DomTreeNode(I, IDomNode); - DomTreeNodes[I] = C; - BBNode = IDomNode->addChild(C); + SmallVector, 32> WorkStack; + + for (unsigned i = 0, e = Roots.size(); i != e; ++i) { + DomTreeNode *ThisRoot = getNode(Roots[i]); + WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin())); + ThisRoot->DFSNumIn = DFSNum++; + + while (!WorkStack.empty()) { + DomTreeNode *Node = WorkStack.back().first; + DomTreeNode::iterator ChildIt = WorkStack.back().second; + + // If we visited all of the children of this node, "recurse" back up the + // stack setting the DFOutNum. + if (ChildIt == Node->end()) { + Node->DFSNumOut = DFSNum++; + WorkStack.pop_back(); + } else { + // Otherwise, recursively visit this child. + DomTreeNode *Child = *ChildIt; + ++WorkStack.back().second; + + WorkStack.push_back(std::make_pair(Child, Child->begin())); + Child->DFSNumIn = DFSNum++; } } - - // Free temporary memory used to construct idom's - Info.clear(); - IDoms.clear(); - std::vector().swap(Vertex); - - updateDFSNumbers(); -} - -void DominatorTreeBase::updateDFSNumbers() -{ - int dfsnum = 0; - // Iterate over all nodes in depth first order. - for (unsigned i = 0, e = Roots.size(); i != e; ++i) - for (df_iterator I = df_begin(Roots[i]), - E = df_end(Roots[i]); I != E; ++I) { - BasicBlock *BB = *I; - DomTreeNode *BBNode = getNode(BB); - if (BBNode) { - if (!BBNode->getIDom()) - BBNode->assignDFSNumber(dfsnum); - } } + SlowQueries = 0; DFSInfoValid = true; } @@ -367,6 +214,21 @@ void DominatorTreeBase::reset() { RootNode = 0; } +DomTreeNode *DominatorTreeBase::getNodeForBlock(BasicBlock *BB) { + if (DomTreeNode *BBNode = DomTreeNodes[BB]) + return BBNode; + + // Haven't calculated this node yet? Get or calculate the node for the + // immediate dominator. + BasicBlock *IDom = getIDom(BB); + DomTreeNode *IDomNode = getNodeForBlock(IDom); + + // Add a new tree node for this BasicBlock, and link it as a child of + // IDomNode + DomTreeNode *C = new DomTreeNode(BB, IDomNode); + return DomTreeNodes[BB] = IDomNode->addChild(C); +} + /// findNearestCommonDominator - Find nearest common dominator basic block /// for basic block A and B. If there is no such block then return NULL. BasicBlock *DominatorTreeBase::findNearestCommonDominator(BasicBlock *A, @@ -383,11 +245,11 @@ BasicBlock *DominatorTreeBase::findNearestCommonDominator(BasicBlock *A, return &Entry; // If B dominates A then B is nearest common dominator. - if (dominates(B,A)) + if (dominates(B, A)) return B; // If A dominates B then A is nearest common dominator. - if (dominates(A,B)) + if (dominates(A, B)) return A; DomTreeNode *NodeA = getNode(A); @@ -397,7 +259,7 @@ BasicBlock *DominatorTreeBase::findNearestCommonDominator(BasicBlock *A, SmallPtrSet NodeADoms; NodeADoms.insert(NodeA); DomTreeNode *IDomA = NodeA->getIDom(); - while(IDomA) { + while (IDomA) { NodeADoms.insert(IDomA); IDomA = IDomA->getIDom(); } @@ -414,38 +276,6 @@ BasicBlock *DominatorTreeBase::findNearestCommonDominator(BasicBlock *A, return NULL; } -/// assignDFSNumber - Assign In and Out numbers while walking dominator tree -/// in dfs order. -void DomTreeNode::assignDFSNumber(int num) { - std::vector workStack; - std::set visitedNodes; - - workStack.push_back(this); - visitedNodes.insert(this); - this->DFSNumIn = num++; - - while (!workStack.empty()) { - DomTreeNode *Node = workStack.back(); - - bool visitChild = false; - for (std::vector::iterator DI = Node->begin(), - E = Node->end(); DI != E && !visitChild; ++DI) { - DomTreeNode *Child = *DI; - if (visitedNodes.count(Child) == 0) { - visitChild = true; - Child->DFSNumIn = num++; - workStack.push_back(Child); - visitedNodes.insert(Child); - } - } - if (!visitChild) { - // If we reach here means all children are visited - Node->DFSNumOut = num++; - workStack.pop_back(); - } - } -} - void DomTreeNode::setIDom(DomTreeNode *NewIDom) { assert(IDom && "No immediate dominator?"); if (IDom != NewIDom) { @@ -462,28 +292,14 @@ void DomTreeNode::setIDom(DomTreeNode *NewIDom) { } } -DomTreeNode *DominatorTree::getNodeForBlock(BasicBlock *BB) { - DomTreeNode *&BBNode = DomTreeNodes[BB]; - if (BBNode) return BBNode; - - // Haven't calculated this node yet? Get or calculate the node for the - // immediate dominator. - BasicBlock *IDom = getIDom(BB); - DomTreeNode *IDomNode = getNodeForBlock(IDom); - - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - DomTreeNode *C = new DomTreeNode(BB, IDomNode); - DomTreeNodes[BB] = C; - return BBNode = IDomNode->addChild(C); -} - -static std::ostream &operator<<(std::ostream &o, - const DomTreeNode *Node) { +static std::ostream &operator<<(std::ostream &o, const DomTreeNode *Node) { if (Node->getBlock()) WriteAsOperand(o, Node->getBlock(), false); else o << " <>"; + + o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}"; + return o << "\n"; } @@ -495,20 +311,47 @@ static void PrintDomTree(const DomTreeNode *N, std::ostream &o, PrintDomTree(*I, o, Lev+1); } +/// eraseNode - Removes a node from the domiantor tree. Block must not +/// domiante any other blocks. Removes node from its immediate dominator's +/// children list. Deletes dominator node associated with basic block BB. +void DominatorTreeBase::eraseNode(BasicBlock *BB) { + DomTreeNode *Node = getNode(BB); + assert (Node && "Removing node that isn't in dominator tree."); + assert (Node->getChildren().empty() && "Node is not a leaf node."); + + // Remove node from immediate dominator's children list. + DomTreeNode *IDom = Node->getIDom(); + if (IDom) { + std::vector::iterator I = + std::find(IDom->Children.begin(), IDom->Children.end(), Node); + assert(I != IDom->Children.end() && + "Not in immediate dominator children set!"); + // I am no longer your child... + IDom->Children.erase(I); + } + + DomTreeNodes.erase(BB); + delete Node; +} + void DominatorTreeBase::print(std::ostream &o, const Module* ) const { - o << "=============================--------------------------------\n" - << "Inorder Dominator Tree:\n"; + o << "=============================--------------------------------\n"; + o << "Inorder Dominator Tree: "; + if (DFSInfoValid) + o << "DFSNumbers invalid: " << SlowQueries << " slow queries."; + o << "\n"; + PrintDomTree(getRootNode(), o, 1); } void DominatorTreeBase::dump() { - print (llvm::cerr); + print(llvm::cerr); } bool DominatorTree::runOnFunction(Function &F) { reset(); // Reset from the last time we were run... Roots.push_back(&F.getEntryBlock()); - calculate(F); + DTcalculate(*this, F); return false; } @@ -520,6 +363,119 @@ char DominanceFrontier::ID = 0; static RegisterPass G("domfrontier", "Dominance Frontier Construction", true); +// NewBB is split and now it has one successor. Update dominace 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); + + std::vector PredBlocks; + for (pred_iterator PI = pred_begin(NewBB), PE = pred_end(NewBB); + PI != PE; ++PI) + PredBlocks.push_back(*PI); + + if (PredBlocks.empty()) + // If NewBB does not have any predecessors then it is a entry block. + // In this case, NewBB and its successor NewBBSucc dominates all + // other blocks. + return; + + // NewBBSucc inherits original NewBB frontier. + DominanceFrontier::iterator NewBBI = find(NewBB); + if (NewBBI != end()) { + DominanceFrontier::DomSetType NewBBSet = NewBBI->second; + DominanceFrontier::DomSetType NewBBSuccSet; + NewBBSuccSet.insert(NewBBSet.begin(), NewBBSet.end()); + addBasicBlock(NewBBSucc, NewBBSuccSet); + } + + // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the + // DF(PredBlocks[0]) without the stuff that the new block does not dominate + // a predecessor of. + DominatorTree &DT = getAnalysis(); + if (DT.dominates(NewBB, NewBBSucc)) { + DominanceFrontier::iterator DFI = find(PredBlocks[0]); + 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(NewBB, *PI)) + DominatesPred = true; + if (!DominatesPred) + Set.erase(SetI++); + else + ++SetI; + } + + if (NewBBI != end()) { + DominanceFrontier::DomSetType NewBBSet = NewBBI->second; + NewBBSet.insert(Set.begin(), Set.end()); + } 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 we must loop over all of the dominance frontiers in the function, + // replacing occurrences of NewBBSucc with NewBB in some cases. All + // blocks that dominate a block in PredBlocks and contained NewBBSucc in + // their dominance frontier must be updated to contain NewBB instead. + // + for (Function::iterator FI = NewBB->getParent()->begin(), + FE = NewBB->getParent()->end(); FI != FE; ++FI) { + DominanceFrontier::iterator DFI = find(FI); + if (DFI == end()) continue; // unreachable block. + + // Only consider nodes that have NewBBSucc in their dominator frontier. + if (!DFI->second.count(NewBBSucc)) continue; + + // Verify whether this block dominates a block in predblocks. If not, do + // not update it. + bool BlockDominatesAny = false; + for (std::vector::const_iterator BI = PredBlocks.begin(), + BE = PredBlocks.end(); BI != BE; ++BI) { + if (DT.dominates(FI, *BI)) { + BlockDominatesAny = true; + break; + } + } + + if (!BlockDominatesAny) + continue; + + // If NewBBSucc should not stay in our dominator frontier, remove it. + // We remove it unless there is a predecessor of NewBBSucc that we + // dominate, but we don't strictly dominate NewBBSucc. + bool ShouldRemove = true; + if ((BasicBlock*)FI == NewBBSucc || !DT.dominates(FI, NewBBSucc)) { + // Okay, we know that PredDom does not strictly dominate NewBBSucc. + // Check to see if it dominates any predecessors of NewBBSucc. + for (pred_iterator PI = pred_begin(NewBBSucc), + E = pred_end(NewBBSucc); PI != E; ++PI) + if (DT.dominates(FI, *PI)) { + ShouldRemove = false; + break; + } + } + + if (ShouldRemove) + removeFromFrontier(DFI, NewBBSucc); + addToFrontier(DFI, NewBB); + } +} + namespace { class DFCalculateWorkObject { public: @@ -621,554 +577,3 @@ void DominanceFrontierBase::print(std::ostream &o, const Module* ) const { void DominanceFrontierBase::dump() { print (llvm::cerr); } - - -//===----------------------------------------------------------------------===// -// ETOccurrence Implementation -//===----------------------------------------------------------------------===// - -void ETOccurrence::Splay() { - ETOccurrence *father; - ETOccurrence *grandfather; - int occdepth; - int fatherdepth; - - while (Parent) { - occdepth = Depth; - - father = Parent; - fatherdepth = Parent->Depth; - grandfather = father->Parent; - - // If we have no grandparent, a single zig or zag will do. - if (!grandfather) { - setDepthAdd(fatherdepth); - MinOccurrence = father->MinOccurrence; - Min = father->Min; - - // See what we have to rotate - if (father->Left == this) { - // Zig - father->setLeft(Right); - setRight(father); - if (father->Left) - father->Left->setDepthAdd(occdepth); - } else { - // Zag - father->setRight(Left); - setLeft(father); - if (father->Right) - father->Right->setDepthAdd(occdepth); - } - father->setDepth(-occdepth); - Parent = NULL; - - father->recomputeMin(); - return; - } - - // If we have a grandfather, we need to do some - // combination of zig and zag. - int grandfatherdepth = grandfather->Depth; - - setDepthAdd(fatherdepth + grandfatherdepth); - MinOccurrence = grandfather->MinOccurrence; - Min = grandfather->Min; - - ETOccurrence *greatgrandfather = grandfather->Parent; - - if (grandfather->Left == father) { - if (father->Left == this) { - // Zig zig - grandfather->setLeft(father->Right); - father->setLeft(Right); - setRight(father); - father->setRight(grandfather); - - father->setDepth(-occdepth); - - if (father->Left) - father->Left->setDepthAdd(occdepth); - - grandfather->setDepth(-fatherdepth); - if (grandfather->Left) - grandfather->Left->setDepthAdd(fatherdepth); - } else { - // Zag zig - grandfather->setLeft(Right); - father->setRight(Left); - setLeft(father); - setRight(grandfather); - - father->setDepth(-occdepth); - if (father->Right) - father->Right->setDepthAdd(occdepth); - grandfather->setDepth(-occdepth - fatherdepth); - if (grandfather->Left) - grandfather->Left->setDepthAdd(occdepth + fatherdepth); - } - } else { - if (father->Left == this) { - // Zig zag - grandfather->setRight(Left); - father->setLeft(Right); - setLeft(grandfather); - setRight(father); - - father->setDepth(-occdepth); - if (father->Left) - father->Left->setDepthAdd(occdepth); - grandfather->setDepth(-occdepth - fatherdepth); - if (grandfather->Right) - grandfather->Right->setDepthAdd(occdepth + fatherdepth); - } else { // Zag Zag - grandfather->setRight(father->Left); - father->setRight(Left); - setLeft(father); - father->setLeft(grandfather); - - father->setDepth(-occdepth); - if (father->Right) - father->Right->setDepthAdd(occdepth); - grandfather->setDepth(-fatherdepth); - if (grandfather->Right) - grandfather->Right->setDepthAdd(fatherdepth); - } - } - - // Might need one more rotate depending on greatgrandfather. - setParent(greatgrandfather); - if (greatgrandfather) { - if (greatgrandfather->Left == grandfather) - greatgrandfather->Left = this; - else - greatgrandfather->Right = this; - - } - grandfather->recomputeMin(); - father->recomputeMin(); - } -} - -//===----------------------------------------------------------------------===// -// ETNode implementation -//===----------------------------------------------------------------------===// - -void ETNode::Split() { - ETOccurrence *right, *left; - ETOccurrence *rightmost = RightmostOcc; - ETOccurrence *parent; - - // Update the occurrence tree first. - RightmostOcc->Splay(); - - // Find the leftmost occurrence in the rightmost subtree, then splay - // around it. - for (right = rightmost->Right; right->Left; right = right->Left); - - right->Splay(); - - // Start splitting - right->Left->Parent = NULL; - parent = ParentOcc; - parent->Splay(); - ParentOcc = NULL; - - left = parent->Left; - parent->Right->Parent = NULL; - - right->setLeft(left); - - right->recomputeMin(); - - rightmost->Splay(); - rightmost->Depth = 0; - rightmost->Min = 0; - - delete parent; - - // Now update *our* tree - - if (Father->Son == this) - Father->Son = Right; - - if (Father->Son == this) - Father->Son = NULL; - else { - Left->Right = Right; - Right->Left = Left; - } - Left = Right = NULL; - Father = NULL; -} - -void ETNode::setFather(ETNode *NewFather) { - ETOccurrence *rightmost; - ETOccurrence *leftpart; - ETOccurrence *NewFatherOcc; - ETOccurrence *temp; - - // First update the path in the splay tree - NewFatherOcc = new ETOccurrence(NewFather); - - rightmost = NewFather->RightmostOcc; - rightmost->Splay(); - - leftpart = rightmost->Left; - - temp = RightmostOcc; - temp->Splay(); - - NewFatherOcc->setLeft(leftpart); - NewFatherOcc->setRight(temp); - - temp->Depth++; - temp->Min++; - NewFatherOcc->recomputeMin(); - - rightmost->setLeft(NewFatherOcc); - - if (NewFatherOcc->Min + rightmost->Depth < rightmost->Min) { - rightmost->Min = NewFatherOcc->Min + rightmost->Depth; - rightmost->MinOccurrence = NewFatherOcc->MinOccurrence; - } - - delete ParentOcc; - ParentOcc = NewFatherOcc; - - // Update *our* tree - ETNode *left; - ETNode *right; - - Father = NewFather; - right = Father->Son; - - if (right) - left = right->Left; - else - left = right = this; - - left->Right = this; - right->Left = this; - Left = left; - Right = right; - - Father->Son = this; -} - -bool ETNode::Below(ETNode *other) { - ETOccurrence *up = other->RightmostOcc; - ETOccurrence *down = RightmostOcc; - - if (this == other) - return true; - - up->Splay(); - - ETOccurrence *left, *right; - left = up->Left; - right = up->Right; - - if (!left) - return false; - - left->Parent = NULL; - - if (right) - right->Parent = NULL; - - down->Splay(); - - if (left == down || left->Parent != NULL) { - if (right) - right->Parent = up; - up->setLeft(down); - } else { - left->Parent = up; - - // If the two occurrences are in different trees, put things - // back the way they were. - if (right && right->Parent != NULL) - up->setRight(down); - else - up->setRight(right); - return false; - } - - if (down->Depth <= 0) - return false; - - return !down->Right || down->Right->Min + down->Depth >= 0; -} - -ETNode *ETNode::NCA(ETNode *other) { - ETOccurrence *occ1 = RightmostOcc; - ETOccurrence *occ2 = other->RightmostOcc; - - ETOccurrence *left, *right, *ret; - ETOccurrence *occmin; - int mindepth; - - if (this == other) - return this; - - occ1->Splay(); - left = occ1->Left; - right = occ1->Right; - - if (left) - left->Parent = NULL; - - if (right) - right->Parent = NULL; - occ2->Splay(); - - if (left == occ2 || (left && left->Parent != NULL)) { - ret = occ2->Right; - - occ1->setLeft(occ2); - if (right) - right->Parent = occ1; - } else { - ret = occ2->Left; - - occ1->setRight(occ2); - if (left) - left->Parent = occ1; - } - - if (occ2->Depth > 0) { - occmin = occ1; - mindepth = occ1->Depth; - } else { - occmin = occ2; - mindepth = occ2->Depth + occ1->Depth; - } - - if (ret && ret->Min + occ1->Depth + occ2->Depth < mindepth) - return ret->MinOccurrence->OccFor; - else - return occmin->OccFor; -} - -void ETNode::assignDFSNumber(int num) { - std::vector workStack; - std::set visitedNodes; - - workStack.push_back(this); - visitedNodes.insert(this); - this->DFSNumIn = num++; - - while (!workStack.empty()) { - ETNode *Node = workStack.back(); - - // If this is leaf node then set DFSNumOut and pop the stack - if (!Node->Son) { - Node->DFSNumOut = num++; - workStack.pop_back(); - continue; - } - - ETNode *son = Node->Son; - - // Visit Node->Son first - if (visitedNodes.count(son) == 0) { - son->DFSNumIn = num++; - workStack.push_back(son); - visitedNodes.insert(son); - continue; - } - - bool visitChild = false; - // Visit remaining children - for (ETNode *s = son->Right; s != son && !visitChild; s = s->Right) { - if (visitedNodes.count(s) == 0) { - visitChild = true; - s->DFSNumIn = num++; - workStack.push_back(s); - visitedNodes.insert(s); - } - } - - if (!visitChild) { - // If we reach here means all children are visited - Node->DFSNumOut = num++; - workStack.pop_back(); - } - } -} - -//===----------------------------------------------------------------------===// -// ETForest implementation -//===----------------------------------------------------------------------===// - -char ETForest::ID = 0; -static RegisterPass -D("etforest", "ET Forest Construction", true); - -void ETForestBase::reset() { - for (ETMapType::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) - delete I->second; - Nodes.clear(); -} - -void ETForestBase::updateDFSNumbers() -{ - int dfsnum = 0; - // Iterate over all nodes in depth first order. - for (unsigned i = 0, e = Roots.size(); i != e; ++i) - for (df_iterator I = df_begin(Roots[i]), - E = df_end(Roots[i]); I != E; ++I) { - BasicBlock *BB = *I; - ETNode *ETN = getNode(BB); - if (ETN && !ETN->hasFather()) - ETN->assignDFSNumber(dfsnum); - } - SlowQueries = 0; - DFSInfoValid = true; -} - -// dominates - Return true if A dominates B. THis performs the -// special checks necessary if A and B are in the same basic block. -bool ETForestBase::dominates(Instruction *A, Instruction *B) { - BasicBlock *BBA = A->getParent(), *BBB = B->getParent(); - if (BBA != BBB) return dominates(BBA, BBB); - - // It is not possible to determine dominance between two PHI nodes - // based on their ordering. - if (isa(A) && isa(B)) - return false; - - // Loop through the basic block until we find A or B. - BasicBlock::iterator I = BBA->begin(); - for (; &*I != A && &*I != B; ++I) /*empty*/; - - if(!IsPostDominators) { - // A dominates B if it is found first in the basic block. - return &*I == A; - } else { - // A post-dominates B if B is found first in the basic block. - return &*I == B; - } -} - -/// isReachableFromEntry - Return true if A is dominated by the entry -/// block of the function containing it. -const bool ETForestBase::isReachableFromEntry(BasicBlock* A) { - return dominates(&A->getParent()->getEntryBlock(), A); -} - -// FIXME : There is no need to make getNodeForBlock public. Fix -// predicate simplifier. -ETNode *ETForest::getNodeForBlock(BasicBlock *BB) { - ETNode *&BBNode = Nodes[BB]; - if (BBNode) return BBNode; - - // Haven't calculated this node yet? Get or calculate the node for the - // immediate dominator. - DomTreeNode *node= getAnalysis().getNode(BB); - - // If we are unreachable, we may not have an immediate dominator. - if (!node || !node->getIDom()) - return BBNode = new ETNode(BB); - else { - ETNode *IDomNode = getNodeForBlock(node->getIDom()->getBlock()); - - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - BBNode = new ETNode(BB); - BBNode->setFather(IDomNode); - return BBNode; - } -} - -void ETForest::calculate(const DominatorTree &DT) { - assert(Roots.size() == 1 && "ETForest should have 1 root block!"); - BasicBlock *Root = Roots[0]; - Nodes[Root] = new ETNode(Root); // Add a node for the root - - Function *F = Root->getParent(); - // Loop over all of the reachable blocks in the function... - for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { - DomTreeNode* node = DT.getNode(I); - if (node && node->getIDom()) { // Reachable block. - BasicBlock* ImmDom = node->getIDom()->getBlock(); - ETNode *&BBNode = Nodes[I]; - if (!BBNode) { // Haven't calculated this node yet? - // Get or calculate the node for the immediate dominator - ETNode *IDomNode = getNodeForBlock(ImmDom); - - // Add a new ETNode for this BasicBlock, and set it's parent - // to it's immediate dominator. - BBNode = new ETNode(I); - BBNode->setFather(IDomNode); - } - } - } - - // Make sure we've got nodes around for every block - for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { - ETNode *&BBNode = Nodes[I]; - if (!BBNode) - BBNode = new ETNode(I); - } - - updateDFSNumbers (); -} - -//===----------------------------------------------------------------------===// -// ETForestBase Implementation -//===----------------------------------------------------------------------===// - -void ETForestBase::addNewBlock(BasicBlock *BB, BasicBlock *IDom) { - ETNode *&BBNode = Nodes[BB]; - assert(!BBNode && "BasicBlock already in ET-Forest"); - - BBNode = new ETNode(BB); - BBNode->setFather(getNode(IDom)); - DFSInfoValid = false; -} - -void ETForestBase::setImmediateDominator(BasicBlock *BB, BasicBlock *newIDom) { - assert(getNode(BB) && "BasicBlock not in ET-Forest"); - assert(getNode(newIDom) && "IDom not in ET-Forest"); - - ETNode *Node = getNode(BB); - if (Node->hasFather()) { - if (Node->getFather()->getData() == newIDom) - return; - Node->Split(); - } - Node->setFather(getNode(newIDom)); - DFSInfoValid= false; -} - -void ETForestBase::print(std::ostream &o, const Module *) const { - o << "=============================--------------------------------\n"; - o << "ET Forest:\n"; - o << "DFS Info "; - if (DFSInfoValid) - o << "is"; - else - o << "is not"; - o << " up to date\n"; - - Function *F = getRoots()[0]->getParent(); - for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) { - o << " DFS Numbers For Basic Block:"; - WriteAsOperand(o, I, false); - o << " are:"; - if (ETNode *EN = getNode(I)) { - o << "In: " << EN->getDFSNumIn(); - o << " Out: " << EN->getDFSNumOut() << "\n"; - } else { - o << "No associated ETNode"; - } - o << "\n"; - } - o << "\n"; -} - -void ETForestBase::dump() { - print (llvm::cerr); -}