diff options
Diffstat (limited to 'contrib/llvm/lib/IR/Dominators.cpp')
| -rw-r--r-- | contrib/llvm/lib/IR/Dominators.cpp | 75 |
1 files changed, 49 insertions, 26 deletions
diff --git a/contrib/llvm/lib/IR/Dominators.cpp b/contrib/llvm/lib/IR/Dominators.cpp index 1880807..4d7e304 100644 --- a/contrib/llvm/lib/IR/Dominators.cpp +++ b/contrib/llvm/lib/IR/Dominators.cpp @@ -29,9 +29,9 @@ using namespace llvm; // Always verify dominfo if expensive checking is enabled. #ifdef EXPENSIVE_CHECKS -static bool VerifyDomInfo = true; +bool llvm::VerifyDomInfo = true; #else -static bool VerifyDomInfo = false; +bool llvm::VerifyDomInfo = false; #endif static cl::opt<bool,true> VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), @@ -61,17 +61,39 @@ bool BasicBlockEdge::isSingleEdge() const { //===----------------------------------------------------------------------===// template class llvm::DomTreeNodeBase<BasicBlock>; -template class llvm::DominatorTreeBase<BasicBlock>; - -template void llvm::Calculate<Function, BasicBlock *>( - DominatorTreeBase< - typename std::remove_pointer<GraphTraits<BasicBlock *>::NodeRef>::type> - &DT, - Function &F); -template void llvm::Calculate<Function, Inverse<BasicBlock *>>( - DominatorTreeBase<typename std::remove_pointer< - GraphTraits<Inverse<BasicBlock *>>::NodeRef>::type> &DT, - Function &F); +template class llvm::DominatorTreeBase<BasicBlock, false>; // DomTreeBase +template class llvm::DominatorTreeBase<BasicBlock, true>; // PostDomTreeBase + +template void +llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBDomTree, Function>( + DomTreeBuilder::BBDomTree &DT, Function &F); +template void +llvm::DomTreeBuilder::Calculate<DomTreeBuilder::BBPostDomTree, Function>( + DomTreeBuilder::BBPostDomTree &DT, Function &F); + +template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBDomTree>( + DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To); +template void llvm::DomTreeBuilder::InsertEdge<DomTreeBuilder::BBPostDomTree>( + DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To); + +template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBDomTree>( + DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To); +template void llvm::DomTreeBuilder::DeleteEdge<DomTreeBuilder::BBPostDomTree>( + DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To); + +template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBDomTree>( + const DomTreeBuilder::BBDomTree &DT); +template bool llvm::DomTreeBuilder::Verify<DomTreeBuilder::BBPostDomTree>( + const DomTreeBuilder::BBPostDomTree &DT); + +bool DominatorTree::invalidate(Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &) { + // Check whether the analysis, all analyses on functions, or the function's + // CFG have been preserved. + auto PAC = PA.getChecker<DominatorTreeAnalysis>(); + return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() || + PAC.preservedSet<CFGAnalyses>()); +} // dominates - Return true if Def dominates a use in User. This performs // the special checks necessary if Def and User are in the same basic block. @@ -141,12 +163,6 @@ bool DominatorTree::dominates(const Instruction *Def, bool DominatorTree::dominates(const BasicBlockEdge &BBE, const BasicBlock *UseBB) const { - // Assert that we have a single edge. We could handle them by simply - // returning false, but since isSingleEdge is linear on the number of - // edges, the callers can normally handle them more efficiently. - assert(BBE.isSingleEdge() && - "This function is not efficient in handling multiple edges"); - // If the BB the edge ends in doesn't dominate the use BB, then the // edge also doesn't. const BasicBlock *Start = BBE.getStart(); @@ -179,11 +195,17 @@ bool DominatorTree::dominates(const BasicBlockEdge &BBE, // trivially dominates itself, so we only have to find if it dominates the // other predecessors. Since the only way out of X is via NormalDest, X can // only properly dominate a node if NormalDest dominates that node too. + int IsDuplicateEdge = 0; for (const_pred_iterator PI = pred_begin(End), E = pred_end(End); PI != E; ++PI) { const BasicBlock *BB = *PI; - if (BB == Start) + if (BB == Start) { + // If there are multiple edges between Start and End, by definition they + // can't dominate anything. + if (IsDuplicateEdge++) + return false; continue; + } if (!dominates(End, BB)) return false; @@ -192,12 +214,6 @@ bool DominatorTree::dominates(const BasicBlockEdge &BBE, } bool DominatorTree::dominates(const BasicBlockEdge &BBE, const Use &U) const { - // Assert that we have a single edge. We could handle them by simply - // returning false, but since isSingleEdge is linear on the number of - // edges, the callers can normally handle them more efficiently. - assert(BBE.isSingleEdge() && - "This function is not efficient in handling multiple edges"); - Instruction *UserInst = cast<Instruction>(U.getUser()); // A PHI in the end of the edge is dominated by it. PHINode *PN = dyn_cast<PHINode>(UserInst); @@ -282,6 +298,13 @@ bool DominatorTree::isReachableFromEntry(const Use &U) const { } void DominatorTree::verifyDomTree() const { + // Perform the expensive checks only when VerifyDomInfo is set. + if (VerifyDomInfo && !verify()) { + errs() << "\n~~~~~~~~~~~\n\t\tDomTree verification failed!\n~~~~~~~~~~~\n"; + print(errs()); + abort(); + } + Function &F = *getRoot()->getParent(); DominatorTree OtherDT; |
