#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/CFG.h"
#include "llvm/IR/Instructions.h"
-#include "llvm/Support/CFG.h"
+#include "llvm/IR/PassManager.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
//
//===----------------------------------------------------------------------===//
-TEMPLATE_INSTANTIATION(class llvm::DomTreeNodeBase<BasicBlock>);
-TEMPLATE_INSTANTIATION(class llvm::DominatorTreeBase<BasicBlock>);
+template class llvm::DomTreeNodeBase<BasicBlock>;
+template class llvm::DominatorTreeBase<BasicBlock>;
-#define LLVM_COMMA ,
-TEMPLATE_INSTANTIATION(void llvm::Calculate<Function LLVM_COMMA BasicBlock *>(
- DominatorTreeBase<typename GraphTraits<BasicBlock *>::NodeType> &DT
- LLVM_COMMA Function &F));
-TEMPLATE_INSTANTIATION(void llvm::Calculate<
- Function LLVM_COMMA Inverse<BasicBlock *> >(DominatorTreeBase<
- typename GraphTraits<Inverse<BasicBlock *> >::NodeType> &DT LLVM_COMMA
- Function &F));
-#undef LLVM_COMMA
+template void llvm::Calculate<Function, BasicBlock *>(
+ DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT, Function &F);
+template void llvm::Calculate<Function, Inverse<BasicBlock *>>(
+ DominatorTreeBase<GraphTraits<Inverse<BasicBlock *>>::NodeType> &DT,
+ Function &F);
// 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.
if (Def == User)
return false;
- // The value defined by an invoke dominates an instruction only if
+ // The value defined by an invoke/catchpad dominates an instruction only if
// it dominates every instruction in UseBB.
// A PHI is dominated only if the instruction dominates every possible use
// in the UseBB.
- if (isa<InvokeInst>(Def) || isa<PHINode>(User))
+ if (isa<InvokeInst>(Def) || isa<CatchPadInst>(Def) || isa<PHINode>(User))
return dominates(Def, UseBB);
if (DefBB != UseBB)
if (DefBB == UseBB)
return false;
- const InvokeInst *II = dyn_cast<InvokeInst>(Def);
- if (!II)
- return dominates(DefBB, UseBB);
+ // Invoke/CatchPad results are only usable in the normal destination, not in
+ // the exceptional destination.
+ if (const auto *II = dyn_cast<InvokeInst>(Def)) {
+ BasicBlock *NormalDest = II->getNormalDest();
+ BasicBlockEdge E(DefBB, NormalDest);
+ return dominates(E, UseBB);
+ }
+ if (const auto *CPI = dyn_cast<CatchPadInst>(Def)) {
+ BasicBlock *NormalDest = CPI->getNormalDest();
+ BasicBlockEdge E(DefBB, NormalDest);
+ return dominates(E, UseBB);
+ }
- // Invoke results are only usable in the normal destination, not in the
- // exceptional destination.
- BasicBlock *NormalDest = II->getNormalDest();
- BasicBlockEdge E(DefBB, NormalDest);
- return dominates(E, UseBB);
+ return dominates(DefBB, UseBB);
}
bool DominatorTree::dominates(const BasicBlockEdge &BBE,
// 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());
+ 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.
// 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());
+ 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.
if (!isReachableFromEntry(DefBB))
return false;
- // Invoke instructions define their return values on the edges
+ // Invoke/CatchPad instructions define their return values on the edges
// to their normal successors, so we have to handle them specially.
// Among other things, this means they don't dominate anything in
// their own block, except possibly a phi, so we don't need to
BasicBlockEdge E(DefBB, NormalDest);
return dominates(E, U);
}
+ if (const auto *CPI = dyn_cast<CatchPadInst>(Def)) {
+ BasicBlock *NormalDest = CPI->getNormalDest();
+ BasicBlockEdge E(DefBB, NormalDest);
+ return dominates(E, U);
+ }
// If the def and use are in different blocks, do a simple CFG dominator
// tree query.
}
void DominatorTree::verifyDomTree() const {
- if (!VerifyDomInfo)
- return;
-
Function &F = *getRoot()->getParent();
DominatorTree OtherDT;
}
}
+//===----------------------------------------------------------------------===//
+// DominatorTreeAnalysis and related pass implementations
+//===----------------------------------------------------------------------===//
+//
+// This implements the DominatorTreeAnalysis which is used with the new pass
+// manager. It also implements some methods from utility passes.
+//
+//===----------------------------------------------------------------------===//
+
+DominatorTree DominatorTreeAnalysis::run(Function &F) {
+ DominatorTree DT;
+ DT.recalculate(F);
+ return DT;
+}
+
+char DominatorTreeAnalysis::PassID;
+
+DominatorTreePrinterPass::DominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {}
+
+PreservedAnalyses DominatorTreePrinterPass::run(Function &F,
+ FunctionAnalysisManager *AM) {
+ OS << "DominatorTree for function: " << F.getName() << "\n";
+ AM->getResult<DominatorTreeAnalysis>(F).print(OS);
+
+ return PreservedAnalyses::all();
+}
+
+PreservedAnalyses DominatorTreeVerifierPass::run(Function &F,
+ FunctionAnalysisManager *AM) {
+ AM->getResult<DominatorTreeAnalysis>(F).verifyDomTree();
+
+ return PreservedAnalyses::all();
+}
+
//===----------------------------------------------------------------------===//
// DominatorTreeWrapperPass Implementation
//===----------------------------------------------------------------------===//
//
-// The implementation details of the wrapper pass that holds a DominatorTree.
+// The implementation details of the wrapper pass that holds a DominatorTree
+// suitable for use with the legacy pass manager.
//
//===----------------------------------------------------------------------===//
return false;
}
-void DominatorTreeWrapperPass::verifyAnalysis() const { DT.verifyDomTree(); }
+void DominatorTreeWrapperPass::verifyAnalysis() const {
+ if (VerifyDomInfo)
+ DT.verifyDomTree();
+}
void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
DT.print(OS);