namespace llvm {
-EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>);
-EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
-
-#define LLVM_COMMA ,
-EXTERN_TEMPLATE_INSTANTIATION(void Calculate<Function LLVM_COMMA BasicBlock *>(
- DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT LLVM_COMMA
- Function &F));
-EXTERN_TEMPLATE_INSTANTIATION(
- void Calculate<Function LLVM_COMMA Inverse<BasicBlock *> >(
- DominatorTreeBase<GraphTraits<Inverse<BasicBlock *> >::NodeType> &DT
- LLVM_COMMA Function &F));
-#undef LLVM_COMMA
+// FIXME: Replace this brittle forward declaration with the include of the new
+// PassManager.h when doing so doesn't break the PassManagerBuilder.
+template <typename IRUnitT> class AnalysisManager;
+class PreservedAnalyses;
+
+extern template class DomTreeNodeBase<BasicBlock>;
+extern template class DominatorTreeBase<BasicBlock>;
+
+extern template void Calculate<Function, BasicBlock *>(
+ DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT, Function &F);
+extern template void Calculate<Function, Inverse<BasicBlock *>>(
+ DominatorTreeBase<GraphTraits<Inverse<BasicBlock *>>::NodeType> &DT,
+ Function &F);
typedef DomTreeNodeBase<BasicBlock> DomTreeNode;
/// \brief Concrete subclass of DominatorTreeBase that is used to compute a
/// normal dominator tree.
+///
+/// Definition: A block is said to be forward statically reachable if there is
+/// a path from the entry of the function to the block. A statically reachable
+/// block may become statically unreachable during optimization.
+///
+/// A forward unreachable block may appear in the dominator tree, or it may
+/// not. If it does, dominance queries will return results as if all reachable
+/// blocks dominate it. When asking for a Node corresponding to a potentially
+/// unreachable block, calling code must handle the case where the block was
+/// unreachable and the result of getNode() is nullptr.
+///
+/// Generally, a block known to be unreachable when the dominator tree is
+/// constructed will not be in the tree. One which becomes unreachable after
+/// the dominator tree is initially constructed may still exist in the tree,
+/// even if the tree is properly updated. Calling code should not rely on the
+/// preceding statements; this is stated only to assist human understanding.
class DominatorTree : public DominatorTreeBase<BasicBlock> {
public:
typedef DominatorTreeBase<BasicBlock> Base;
DominatorTree() : DominatorTreeBase<BasicBlock>(false) {}
+ explicit DominatorTree(Function &F) : DominatorTreeBase<BasicBlock>(false) {
+ recalculate(F);
+ }
+
+ DominatorTree(DominatorTree &&Arg)
+ : Base(std::move(static_cast<Base &>(Arg))) {}
+ DominatorTree &operator=(DominatorTree &&RHS) {
+ Base::operator=(std::move(static_cast<Base &>(RHS)));
+ return *this;
+ }
/// \brief Returns *false* if the other dominator tree matches this dominator
/// tree.
bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
- inline DomTreeNode *operator[](BasicBlock *BB) const {
- return getNode(BB);
- }
-
// Ensure base class overloads are visible.
using Base::isReachableFromEntry;
// DominatorTree GraphTraits specializations so the DominatorTree can be
// iterable by generic graph iterators.
-template <> struct GraphTraits<DomTreeNode*> {
- typedef DomTreeNode NodeType;
- typedef NodeType::iterator ChildIteratorType;
+template <class Node, class ChildIterator> struct DomTreeGraphTraitsBase {
+ typedef Node NodeType;
+ typedef ChildIterator ChildIteratorType;
+ typedef df_iterator<Node *, SmallPtrSet<NodeType *, 8>> nodes_iterator;
- static NodeType *getEntryNode(NodeType *N) {
- return N;
- }
+ static NodeType *getEntryNode(NodeType *N) { return N; }
static inline ChildIteratorType child_begin(NodeType *N) {
return N->begin();
}
- static inline ChildIteratorType child_end(NodeType *N) {
- return N->end();
- }
+ static inline ChildIteratorType child_end(NodeType *N) { return N->end(); }
- typedef df_iterator<DomTreeNode*> nodes_iterator;
-
- static nodes_iterator nodes_begin(DomTreeNode *N) {
+ static nodes_iterator nodes_begin(NodeType *N) {
return df_begin(getEntryNode(N));
}
- static nodes_iterator nodes_end(DomTreeNode *N) {
+ static nodes_iterator nodes_end(NodeType *N) {
return df_end(getEntryNode(N));
}
};
+template <>
+struct GraphTraits<DomTreeNode *>
+ : public DomTreeGraphTraitsBase<DomTreeNode, DomTreeNode::iterator> {};
+
+template <>
+struct GraphTraits<const DomTreeNode *>
+ : public DomTreeGraphTraitsBase<const DomTreeNode,
+ DomTreeNode::const_iterator> {};
+
template <> struct GraphTraits<DominatorTree*>
: public GraphTraits<DomTreeNode*> {
static NodeType *getEntryNode(DominatorTree *DT) {
};
/// \brief Analysis pass which computes a \c DominatorTree.
+class DominatorTreeAnalysis {
+public:
+ /// \brief Provide the result typedef for this analysis pass.
+ typedef DominatorTree Result;
+
+ /// \brief Opaque, unique identifier for this analysis pass.
+ static void *ID() { return (void *)&PassID; }
+
+ /// \brief Run the analysis pass over a function and produce a dominator tree.
+ DominatorTree run(Function &F);
+
+ /// \brief Provide access to a name for this pass for debugging purposes.
+ static StringRef name() { return "DominatorTreeAnalysis"; }
+
+private:
+ static char PassID;
+};
+
+/// \brief Printer pass for the \c DominatorTree.
+class DominatorTreePrinterPass {
+ raw_ostream &OS;
+
+public:
+ explicit DominatorTreePrinterPass(raw_ostream &OS);
+ PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM);
+
+ static StringRef name() { return "DominatorTreePrinterPass"; }
+};
+
+/// \brief Verifier pass for the \c DominatorTree.
+struct DominatorTreeVerifierPass {
+ PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM);
+
+ static StringRef name() { return "DominatorTreeVerifierPass"; }
+};
+
+/// \brief Legacy analysis pass which computes a \c DominatorTree.
class DominatorTreeWrapperPass : public FunctionPass {
DominatorTree DT;
void releaseMemory() override { DT.releaseMemory(); }
- void print(raw_ostream &OS, const Module *M = 0) const override;
+ void print(raw_ostream &OS, const Module *M = nullptr) const override;
};
} // End llvm namespace
projects / oota-llvm.git / blobdiff