LCOV - code coverage report
Current view: top level - include/llvm/IR - Dominators.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 32 32 100.0 %
Date: 2017-09-14 15:23:50 Functions: 7 8 87.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- Dominators.h - Dominator Info Calculation ----------------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file defines the DominatorTree class, which provides fast and efficient
      11             : // dominance queries.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #ifndef LLVM_IR_DOMINATORS_H
      16             : #define LLVM_IR_DOMINATORS_H
      17             : 
      18             : #include "llvm/ADT/DenseMapInfo.h"
      19             : #include "llvm/ADT/DepthFirstIterator.h"
      20             : #include "llvm/ADT/GraphTraits.h"
      21             : #include "llvm/ADT/Hashing.h"
      22             : #include "llvm/IR/BasicBlock.h"
      23             : #include "llvm/IR/CFG.h"
      24             : #include "llvm/IR/PassManager.h"
      25             : #include "llvm/Pass.h"
      26             : #include "llvm/Support/GenericDomTree.h"
      27             : #include <utility>
      28             : 
      29             : namespace llvm {
      30             : 
      31             : class Function;
      32             : class Instruction;
      33             : class Module;
      34             : class raw_ostream;
      35             : 
      36             : extern template class DomTreeNodeBase<BasicBlock>;
      37             : extern template class DominatorTreeBase<BasicBlock, false>; // DomTree
      38             : extern template class DominatorTreeBase<BasicBlock, true>; // PostDomTree
      39             : 
      40             : namespace DomTreeBuilder {
      41             : using BBDomTree = DomTreeBase<BasicBlock>;
      42             : using BBPostDomTree = PostDomTreeBase<BasicBlock>;
      43             : 
      44             : extern template struct Update<BasicBlock *>;
      45             : 
      46             : using BBUpdates = ArrayRef<Update<BasicBlock *>>;
      47             : 
      48             : extern template void Calculate<BBDomTree>(BBDomTree &DT);
      49             : extern template void Calculate<BBPostDomTree>(BBPostDomTree &DT);
      50             : 
      51             : extern template void InsertEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
      52             :                                            BasicBlock *To);
      53             : extern template void InsertEdge<BBPostDomTree>(BBPostDomTree &DT,
      54             :                                                BasicBlock *From,
      55             :                                                BasicBlock *To);
      56             : 
      57             : extern template void DeleteEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
      58             :                                            BasicBlock *To);
      59             : extern template void DeleteEdge<BBPostDomTree>(BBPostDomTree &DT,
      60             :                                                BasicBlock *From,
      61             :                                                BasicBlock *To);
      62             : 
      63             : extern template void ApplyUpdates<BBDomTree>(BBDomTree &DT, BBUpdates);
      64             : extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT, BBUpdates);
      65             : 
      66             : extern template bool Verify<BBDomTree>(const BBDomTree &DT);
      67             : extern template bool Verify<BBPostDomTree>(const BBPostDomTree &DT);
      68             : }  // namespace DomTreeBuilder
      69             : 
      70             : using DomTreeNode = DomTreeNodeBase<BasicBlock>;
      71             : 
      72             : class BasicBlockEdge {
      73             :   const BasicBlock *Start;
      74             :   const BasicBlock *End;
      75             : 
      76             : public:
      77      411140 :   BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :
      78      411140 :     Start(Start_), End(End_) {}
      79             : 
      80             :   BasicBlockEdge(const std::pair<BasicBlock *, BasicBlock *> &Pair)
      81          27 :       : Start(Pair.first), End(Pair.second) {}
      82             : 
      83             :   BasicBlockEdge(const std::pair<const BasicBlock *, const BasicBlock *> &Pair)
      84             :       : Start(Pair.first), End(Pair.second) {}
      85             : 
      86             :   const BasicBlock *getStart() const {
      87             :     return Start;
      88             :   }
      89             : 
      90             :   const BasicBlock *getEnd() const {
      91             :     return End;
      92             :   }
      93             : 
      94             :   /// Check if this is the only edge between Start and End.
      95             :   bool isSingleEdge() const;
      96             : };
      97             : 
      98             : template <> struct DenseMapInfo<BasicBlockEdge> {
      99             :   using BBInfo = DenseMapInfo<const BasicBlock *>;
     100             : 
     101             :   static unsigned getHashValue(const BasicBlockEdge *V);
     102             : 
     103             :   static inline BasicBlockEdge getEmptyKey() {
     104        4903 :     return BasicBlockEdge(BBInfo::getEmptyKey(), BBInfo::getEmptyKey());
     105             :   }
     106             : 
     107             :   static inline BasicBlockEdge getTombstoneKey() {
     108        3741 :     return BasicBlockEdge(BBInfo::getTombstoneKey(), BBInfo::getTombstoneKey());
     109             :   }
     110             : 
     111        2579 :   static unsigned getHashValue(const BasicBlockEdge &Edge) {
     112        7737 :     return hash_combine(BBInfo::getHashValue(Edge.getStart()),
     113       10316 :                         BBInfo::getHashValue(Edge.getEnd()));
     114             :   }
     115             : 
     116             :   static bool isEqual(const BasicBlockEdge &LHS, const BasicBlockEdge &RHS) {
     117       31866 :     return BBInfo::isEqual(LHS.getStart(), RHS.getStart()) &&
     118       13922 :            BBInfo::isEqual(LHS.getEnd(), RHS.getEnd());
     119             :   }
     120             : };
     121             : 
     122             : /// \brief Concrete subclass of DominatorTreeBase that is used to compute a
     123             : /// normal dominator tree.
     124             : ///
     125             : /// Definition: A block is said to be forward statically reachable if there is
     126             : /// a path from the entry of the function to the block.  A statically reachable
     127             : /// block may become statically unreachable during optimization.
     128             : ///
     129             : /// A forward unreachable block may appear in the dominator tree, or it may
     130             : /// not.  If it does, dominance queries will return results as if all reachable
     131             : /// blocks dominate it.  When asking for a Node corresponding to a potentially
     132             : /// unreachable block, calling code must handle the case where the block was
     133             : /// unreachable and the result of getNode() is nullptr.
     134             : ///
     135             : /// Generally, a block known to be unreachable when the dominator tree is
     136             : /// constructed will not be in the tree.  One which becomes unreachable after
     137             : /// the dominator tree is initially constructed may still exist in the tree,
     138             : /// even if the tree is properly updated. Calling code should not rely on the
     139             : /// preceding statements; this is stated only to assist human understanding.
     140      295386 : class DominatorTree : public DominatorTreeBase<BasicBlock, false> {
     141             :  public:
     142             :   using Base = DominatorTreeBase<BasicBlock, false>;
     143             : 
     144      575146 :   DominatorTree() = default;
     145        1347 :   explicit DominatorTree(Function &F) { recalculate(F); }
     146             : 
     147             :   /// Handle invalidation explicitly.
     148             :   bool invalidate(Function &F, const PreservedAnalyses &PA,
     149             :                   FunctionAnalysisManager::Invalidator &);
     150             : 
     151             :   /// \brief Returns *false* if the other dominator tree matches this dominator
     152             :   /// tree.
     153          47 :   inline bool compare(const DominatorTree &Other) const {
     154          91 :     const DomTreeNode *R = getRootNode();
     155          91 :     const DomTreeNode *OtherR = Other.getRootNode();
     156         182 :     return !R || !OtherR || R->getBlock() != OtherR->getBlock() ||
     157          94 :            Base::compare(Other);
     158             :   }
     159             : 
     160             :   // Ensure base-class overloads are visible.
     161             :   using Base::dominates;
     162             : 
     163             :   /// \brief Return true if Def dominates a use in User.
     164             :   ///
     165             :   /// This performs the special checks necessary if Def and User are in the same
     166             :   /// basic block. Note that Def doesn't dominate a use in Def itself!
     167             :   bool dominates(const Instruction *Def, const Use &U) const;
     168             :   bool dominates(const Instruction *Def, const Instruction *User) const;
     169             :   bool dominates(const Instruction *Def, const BasicBlock *BB) const;
     170             : 
     171             :   /// Return true if an edge dominates a use.
     172             :   ///
     173             :   /// If BBE is not a unique edge between start and end of the edge, it can
     174             :   /// never dominate the use.
     175             :   bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
     176             :   bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
     177             : 
     178             :   // Ensure base class overloads are visible.
     179             :   using Base::isReachableFromEntry;
     180             : 
     181             :   /// \brief Provide an overload for a Use.
     182             :   bool isReachableFromEntry(const Use &U) const;
     183             : 
     184             :   /// \brief Verify the correctness of the domtree by re-computing it.
     185             :   ///
     186             :   /// This should only be used for debugging as it aborts the program if the
     187             :   /// verification fails.
     188             :   void verifyDomTree() const;
     189             : 
     190             :   // Pop up a GraphViz/gv window with the Dominator Tree rendered using `dot`.
     191             :   void viewGraph(const Twine &Name, const Twine &Title);
     192             :   void viewGraph();
     193             : };
     194             : 
     195             : //===-------------------------------------
     196             : // DominatorTree GraphTraits specializations so the DominatorTree can be
     197             : // iterable by generic graph iterators.
     198             : 
     199             : template <class Node, class ChildIterator> struct DomTreeGraphTraitsBase {
     200             :   using NodeRef = Node *;
     201             :   using ChildIteratorType = ChildIterator;
     202             :   using nodes_iterator = df_iterator<Node *, df_iterator_default_set<Node*>>;
     203             : 
     204             :   static NodeRef getEntryNode(NodeRef N) { return N; }
     205     3544049 :   static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
     206     5904704 :   static ChildIteratorType child_end(NodeRef N) { return N->end(); }
     207             : 
     208             :   static nodes_iterator nodes_begin(NodeRef N) {
     209             :     return df_begin(getEntryNode(N));
     210             :   }
     211             : 
     212             :   static nodes_iterator nodes_end(NodeRef N) { return df_end(getEntryNode(N)); }
     213             : };
     214             : 
     215             : template <>
     216             : struct GraphTraits<DomTreeNode *>
     217             :     : public DomTreeGraphTraitsBase<DomTreeNode, DomTreeNode::iterator> {};
     218             : 
     219             : template <>
     220             : struct GraphTraits<const DomTreeNode *>
     221             :     : public DomTreeGraphTraitsBase<const DomTreeNode,
     222             :                                     DomTreeNode::const_iterator> {};
     223             : 
     224             : template <> struct GraphTraits<DominatorTree*>
     225             :   : public GraphTraits<DomTreeNode*> {
     226       59903 :   static NodeRef getEntryNode(DominatorTree *DT) { return DT->getRootNode(); }
     227             : 
     228             :   static nodes_iterator nodes_begin(DominatorTree *N) {
     229         307 :     return df_begin(getEntryNode(N));
     230             :   }
     231             : 
     232             :   static nodes_iterator nodes_end(DominatorTree *N) {
     233         307 :     return df_end(getEntryNode(N));
     234             :   }
     235             : };
     236             : 
     237             : /// \brief Analysis pass which computes a \c DominatorTree.
     238             : class DominatorTreeAnalysis : public AnalysisInfoMixin<DominatorTreeAnalysis> {
     239             :   friend AnalysisInfoMixin<DominatorTreeAnalysis>;
     240             :   static AnalysisKey Key;
     241             : 
     242             : public:
     243             :   /// \brief Provide the result typedef for this analysis pass.
     244             :   using Result = DominatorTree;
     245             : 
     246             :   /// \brief Run the analysis pass over a function and produce a dominator tree.
     247             :   DominatorTree run(Function &F, FunctionAnalysisManager &);
     248             : };
     249             : 
     250             : /// \brief Printer pass for the \c DominatorTree.
     251             : class DominatorTreePrinterPass
     252             :     : public PassInfoMixin<DominatorTreePrinterPass> {
     253             :   raw_ostream &OS;
     254             : 
     255             : public:
     256             :   explicit DominatorTreePrinterPass(raw_ostream &OS);
     257             : 
     258             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     259             : };
     260             : 
     261             : /// \brief Verifier pass for the \c DominatorTree.
     262             : struct DominatorTreeVerifierPass : PassInfoMixin<DominatorTreeVerifierPass> {
     263             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     264             : };
     265             : 
     266             : /// \brief Legacy analysis pass which computes a \c DominatorTree.
     267      346814 : class DominatorTreeWrapperPass : public FunctionPass {
     268             :   DominatorTree DT;
     269             : 
     270             : public:
     271             :   static char ID;
     272             : 
     273      348639 :   DominatorTreeWrapperPass() : FunctionPass(ID) {
     274      116213 :     initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
     275      116213 :   }
     276             : 
     277     3610047 :   DominatorTree &getDomTree() { return DT; }
     278             :   const DominatorTree &getDomTree() const { return DT; }
     279             : 
     280             :   bool runOnFunction(Function &F) override;
     281             : 
     282             :   void verifyAnalysis() const override;
     283             : 
     284      113582 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
     285      113582 :     AU.setPreservesAll();
     286      113582 :   }
     287             : 
     288     2504964 :   void releaseMemory() override { DT.releaseMemory(); }
     289             : 
     290             :   void print(raw_ostream &OS, const Module *M = nullptr) const override;
     291             : };
     292             : 
     293             : } // end namespace llvm
     294             : 
     295             : #endif // LLVM_IR_DOMINATORS_H

Generated by: LCOV version 1.13