LCOV - code coverage report
Current view: top level - include/llvm/IR - Dominators.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 17 27 63.0 %
Date: 2018-10-20 13:21:21 Functions: 5 9 55.6 %
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             : extern template class cfg::Update<BasicBlock *>;
      41             : 
      42             : namespace DomTreeBuilder {
      43             : using BBDomTree = DomTreeBase<BasicBlock>;
      44             : using BBPostDomTree = PostDomTreeBase<BasicBlock>;
      45             : 
      46             : using BBUpdates = ArrayRef<llvm::cfg::Update<BasicBlock *>>;
      47             : 
      48             : extern template void Calculate<BBDomTree>(BBDomTree &DT);
      49             : extern template void CalculateWithUpdates<BBDomTree>(BBDomTree &DT,
      50             :                                                      BBUpdates U);
      51             : 
      52             : extern template void Calculate<BBPostDomTree>(BBPostDomTree &DT);
      53             : 
      54             : extern template void InsertEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
      55             :                                            BasicBlock *To);
      56             : extern template void InsertEdge<BBPostDomTree>(BBPostDomTree &DT,
      57             :                                                BasicBlock *From,
      58             :                                                BasicBlock *To);
      59             : 
      60             : extern template void DeleteEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
      61             :                                            BasicBlock *To);
      62             : extern template void DeleteEdge<BBPostDomTree>(BBPostDomTree &DT,
      63             :                                                BasicBlock *From,
      64             :                                                BasicBlock *To);
      65             : 
      66             : extern template void ApplyUpdates<BBDomTree>(BBDomTree &DT, BBUpdates);
      67             : extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT, BBUpdates);
      68             : 
      69             : extern template bool Verify<BBDomTree>(const BBDomTree &DT,
      70             :                                        BBDomTree::VerificationLevel VL);
      71             : extern template bool Verify<BBPostDomTree>(const BBPostDomTree &DT,
      72             :                                            BBPostDomTree::VerificationLevel VL);
      73             : }  // namespace DomTreeBuilder
      74             : 
      75             : using DomTreeNode = DomTreeNodeBase<BasicBlock>;
      76             : 
      77             : class BasicBlockEdge {
      78             :   const BasicBlock *Start;
      79             :   const BasicBlock *End;
      80             : 
      81             : public:
      82     1068892 :   BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :
      83     1061308 :     Start(Start_), End(End_) {}
      84             : 
      85             :   BasicBlockEdge(const std::pair<BasicBlock *, BasicBlock *> &Pair)
      86         760 :       : Start(Pair.first), End(Pair.second) {}
      87             : 
      88             :   BasicBlockEdge(const std::pair<const BasicBlock *, const BasicBlock *> &Pair)
      89             :       : Start(Pair.first), End(Pair.second) {}
      90             : 
      91           0 :   const BasicBlock *getStart() const {
      92           0 :     return Start;
      93             :   }
      94             : 
      95           0 :   const BasicBlock *getEnd() const {
      96           0 :     return End;
      97             :   }
      98             : 
      99             :   /// Check if this is the only edge between Start and End.
     100             :   bool isSingleEdge() const;
     101             : };
     102             : 
     103             : template <> struct DenseMapInfo<BasicBlockEdge> {
     104             :   using BBInfo = DenseMapInfo<const BasicBlock *>;
     105             : 
     106             :   static unsigned getHashValue(const BasicBlockEdge *V);
     107             : 
     108             :   static inline BasicBlockEdge getEmptyKey() {
     109             :     return BasicBlockEdge(BBInfo::getEmptyKey(), BBInfo::getEmptyKey());
     110             :   }
     111             : 
     112             :   static inline BasicBlockEdge getTombstoneKey() {
     113             :     return BasicBlockEdge(BBInfo::getTombstoneKey(), BBInfo::getTombstoneKey());
     114             :   }
     115             : 
     116        2888 :   static unsigned getHashValue(const BasicBlockEdge &Edge) {
     117        8664 :     return hash_combine(BBInfo::getHashValue(Edge.getStart()),
     118        8664 :                         BBInfo::getHashValue(Edge.getEnd()));
     119             :   }
     120             : 
     121             :   static bool isEqual(const BasicBlockEdge &LHS, const BasicBlockEdge &RHS) {
     122       19011 :     return BBInfo::isEqual(LHS.getStart(), RHS.getStart()) &&
     123       15768 :            BBInfo::isEqual(LHS.getEnd(), RHS.getEnd());
     124             :   }
     125             : };
     126             : 
     127             : /// Concrete subclass of DominatorTreeBase that is used to compute a
     128             : /// normal dominator tree.
     129             : ///
     130             : /// Definition: A block is said to be forward statically reachable if there is
     131             : /// a path from the entry of the function to the block.  A statically reachable
     132             : /// block may become statically unreachable during optimization.
     133             : ///
     134             : /// A forward unreachable block may appear in the dominator tree, or it may
     135             : /// not.  If it does, dominance queries will return results as if all reachable
     136             : /// blocks dominate it.  When asking for a Node corresponding to a potentially
     137             : /// unreachable block, calling code must handle the case where the block was
     138             : /// unreachable and the result of getNode() is nullptr.
     139             : ///
     140             : /// Generally, a block known to be unreachable when the dominator tree is
     141             : /// constructed will not be in the tree.  One which becomes unreachable after
     142             : /// the dominator tree is initially constructed may still exist in the tree,
     143             : /// even if the tree is properly updated. Calling code should not rely on the
     144             : /// preceding statements; this is stated only to assist human understanding.
     145       25008 : class DominatorTree : public DominatorTreeBase<BasicBlock, false> {
     146             :  public:
     147             :   using Base = DominatorTreeBase<BasicBlock, false>;
     148             : 
     149             :   DominatorTree() = default;
     150        1270 :   explicit DominatorTree(Function &F) { recalculate(F); }
     151           0 :   explicit DominatorTree(DominatorTree &DT, DomTreeBuilder::BBUpdates U) {
     152           0 :     recalculate(*DT.Parent, U);
     153           0 :   }
     154             : 
     155             :   /// Handle invalidation explicitly.
     156             :   bool invalidate(Function &F, const PreservedAnalyses &PA,
     157             :                   FunctionAnalysisManager::Invalidator &);
     158             : 
     159             :   // Ensure base-class overloads are visible.
     160             :   using Base::dominates;
     161             : 
     162             :   /// Return true if Def dominates a use in User.
     163             :   ///
     164             :   /// This performs the special checks necessary if Def and User are in the same
     165             :   /// basic block. Note that Def doesn't dominate a use in Def itself!
     166             :   bool dominates(const Instruction *Def, const Use &U) const;
     167             :   bool dominates(const Instruction *Def, const Instruction *User) const;
     168             :   bool dominates(const Instruction *Def, const BasicBlock *BB) const;
     169             : 
     170             :   /// Return true if an edge dominates a use.
     171             :   ///
     172             :   /// If BBE is not a unique edge between start and end of the edge, it can
     173             :   /// never dominate the use.
     174             :   bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
     175             :   bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
     176             : 
     177             :   // Ensure base class overloads are visible.
     178             :   using Base::isReachableFromEntry;
     179             : 
     180             :   /// Provide an overload for a Use.
     181             :   bool isReachableFromEntry(const Use &U) const;
     182             : 
     183             :   // Pop up a GraphViz/gv window with the Dominator Tree rendered using `dot`.
     184             :   void viewGraph(const Twine &Name, const Twine &Title);
     185             :   void viewGraph();
     186             : };
     187             : 
     188             : //===-------------------------------------
     189             : // DominatorTree GraphTraits specializations so the DominatorTree can be
     190             : // iterable by generic graph iterators.
     191             : 
     192             : template <class Node, class ChildIterator> struct DomTreeGraphTraitsBase {
     193             :   using NodeRef = Node *;
     194             :   using ChildIteratorType = ChildIterator;
     195             :   using nodes_iterator = df_iterator<Node *, df_iterator_default_set<Node*>>;
     196             : 
     197             :   static NodeRef getEntryNode(NodeRef N) { return N; }
     198             :   static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
     199             :   static ChildIteratorType child_end(NodeRef N) { return N->end(); }
     200             : 
     201             :   static nodes_iterator nodes_begin(NodeRef N) {
     202             :     return df_begin(getEntryNode(N));
     203             :   }
     204             : 
     205             :   static nodes_iterator nodes_end(NodeRef N) { return df_end(getEntryNode(N)); }
     206             : };
     207             : 
     208             : template <>
     209             : struct GraphTraits<DomTreeNode *>
     210             :     : public DomTreeGraphTraitsBase<DomTreeNode, DomTreeNode::iterator> {};
     211             : 
     212             : template <>
     213             : struct GraphTraits<const DomTreeNode *>
     214             :     : public DomTreeGraphTraitsBase<const DomTreeNode,
     215             :                                     DomTreeNode::const_iterator> {};
     216             : 
     217             : template <> struct GraphTraits<DominatorTree*>
     218             :   : public GraphTraits<DomTreeNode*> {
     219           0 :   static NodeRef getEntryNode(DominatorTree *DT) { return DT->getRootNode(); }
     220             : 
     221             :   static nodes_iterator nodes_begin(DominatorTree *N) {
     222             :     return df_begin(getEntryNode(N));
     223             :   }
     224             : 
     225           0 :   static nodes_iterator nodes_end(DominatorTree *N) {
     226           0 :     return df_end(getEntryNode(N));
     227             :   }
     228             : };
     229             : 
     230             : /// Analysis pass which computes a \c DominatorTree.
     231             : class DominatorTreeAnalysis : public AnalysisInfoMixin<DominatorTreeAnalysis> {
     232             :   friend AnalysisInfoMixin<DominatorTreeAnalysis>;
     233             :   static AnalysisKey Key;
     234             : 
     235             : public:
     236             :   /// Provide the result typedef for this analysis pass.
     237             :   using Result = DominatorTree;
     238             : 
     239             :   /// Run the analysis pass over a function and produce a dominator tree.
     240             :   DominatorTree run(Function &F, FunctionAnalysisManager &);
     241             : };
     242             : 
     243             : /// Printer pass for the \c DominatorTree.
     244             : class DominatorTreePrinterPass
     245             :     : public PassInfoMixin<DominatorTreePrinterPass> {
     246             :   raw_ostream &OS;
     247             : 
     248             : public:
     249             :   explicit DominatorTreePrinterPass(raw_ostream &OS);
     250             : 
     251             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     252             : };
     253             : 
     254             : /// Verifier pass for the \c DominatorTree.
     255             : struct DominatorTreeVerifierPass : PassInfoMixin<DominatorTreeVerifierPass> {
     256             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     257             : };
     258             : 
     259             : /// Legacy analysis pass which computes a \c DominatorTree.
     260             : class DominatorTreeWrapperPass : public FunctionPass {
     261             :   DominatorTree DT;
     262             : 
     263             : public:
     264             :   static char ID;
     265             : 
     266      354114 :   DominatorTreeWrapperPass() : FunctionPass(ID) {
     267      177057 :     initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
     268      177057 :   }
     269             : 
     270     5677213 :   DominatorTree &getDomTree() { return DT; }
     271             :   const DominatorTree &getDomTree() const { return DT; }
     272             : 
     273             :   bool runOnFunction(Function &F) override;
     274             : 
     275             :   void verifyAnalysis() const override;
     276             : 
     277      169554 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
     278             :     AU.setPreservesAll();
     279      169554 :   }
     280             : 
     281     2123032 :   void releaseMemory() override { DT.releaseMemory(); }
     282             : 
     283             :   void print(raw_ostream &OS, const Module *M = nullptr) const override;
     284             : };
     285             : } // end namespace llvm
     286             : 
     287             : #endif // LLVM_IR_DOMINATORS_H

Generated by: LCOV version 1.13