#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>;
-char DominatorTree::ID = 0;
-INITIALIZE_PASS(DominatorTree, "domtree",
- "Dominator Tree Construction", true, true)
-
-bool DominatorTree::runOnFunction(Function &F) {
- DT->recalculate(F);
- return false;
-}
-
-void DominatorTree::verifyAnalysis() const {
- if (!VerifyDomInfo) return;
-
- Function &F = *getRoot()->getParent();
-
- DominatorTree OtherDT;
- OtherDT.getBase().recalculate(F);
- 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 {
- DT->print(OS);
-}
+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.
return true;
}
-bool DominatorTree::dominates(const BasicBlockEdge &BBE,
- const Use &U) const {
+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());
+ 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.
return dominates(BBE, UseBB);
}
-bool DominatorTree::dominates(const Instruction *Def,
- const Use &U) const {
+bool DominatorTree::dominates(const Instruction *Def, const Use &U) const {
Instruction *UserInst = cast<Instruction>(U.getUser());
const BasicBlock *DefBB = Def->getParent();
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.
// Everything else uses their operands in their own block.
return isReachableFromEntry(I->getParent());
}
+
+void DominatorTree::verifyDomTree() const {
+ Function &F = *getRoot()->getParent();
+
+ DominatorTree OtherDT;
+ OtherDT.recalculate(F);
+ if (compare(OtherDT)) {
+ errs() << "DominatorTree is not up to date!\nComputed:\n";
+ print(errs());
+ errs() << "\nActual:\n";
+ OtherDT.print(errs());
+ abort();
+ }
+}
+
+//===----------------------------------------------------------------------===//
+// 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
+// suitable for use with the legacy pass manager.
+//
+//===----------------------------------------------------------------------===//
+
+char DominatorTreeWrapperPass::ID = 0;
+INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree",
+ "Dominator Tree Construction", true, true)
+
+bool DominatorTreeWrapperPass::runOnFunction(Function &F) {
+ DT.recalculate(F);
+ return false;
+}
+
+void DominatorTreeWrapperPass::verifyAnalysis() const {
+ if (VerifyDomInfo)
+ DT.verifyDomTree();
+}
+
+void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
+ DT.print(OS);
+}
+
projects / oota-llvm.git / blobdiff