LCOV - code coverage report
Current view: top level - include/llvm/IR - Dominators.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 21 21 100.0 %
Date: 2018-02-22 04:41:24 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             :                                        BBDomTree::VerificationLevel VL);
      68             : extern template bool Verify<BBPostDomTree>(const BBPostDomTree &DT,
      69             :                                            BBPostDomTree::VerificationLevel VL);
      70             : }  // namespace DomTreeBuilder
      71             : 
      72             : using DomTreeNode = DomTreeNodeBase<BasicBlock>;
      73             : 
      74             : class BasicBlockEdge {
      75             :   const BasicBlock *Start;
      76             :   const BasicBlock *End;
      77             : 
      78             : public:
      79      433319 :   BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :
      80      433319 :     Start(Start_), End(End_) {}
      81             : 
      82             :   BasicBlockEdge(const std::pair<BasicBlock *, BasicBlock *> &Pair)
      83          27 :       : Start(Pair.first), End(Pair.second) {}
      84             : 
      85             :   BasicBlockEdge(const std::pair<const BasicBlock *, const BasicBlock *> &Pair)
      86             :       : Start(Pair.first), End(Pair.second) {}
      87             : 
      88             :   const BasicBlock *getStart() const {
      89             :     return Start;
      90             :   }
      91             : 
      92             :   const BasicBlock *getEnd() const {
      93             :     return End;
      94             :   }
      95             : 
      96             :   /// Check if this is the only edge between Start and End.
      97             :   bool isSingleEdge() const;
      98             : };
      99             : 
     100             : template <> struct DenseMapInfo<BasicBlockEdge> {
     101             :   using BBInfo = DenseMapInfo<const BasicBlock *>;
     102             : 
     103             :   static unsigned getHashValue(const BasicBlockEdge *V);
     104             : 
     105             :   static inline BasicBlockEdge getEmptyKey() {
     106             :     return BasicBlockEdge(BBInfo::getEmptyKey(), BBInfo::getEmptyKey());
     107             :   }
     108             : 
     109             :   static inline BasicBlockEdge getTombstoneKey() {
     110             :     return BasicBlockEdge(BBInfo::getTombstoneKey(), BBInfo::getTombstoneKey());
     111             :   }
     112             : 
     113        2691 :   static unsigned getHashValue(const BasicBlockEdge &Edge) {
     114        8073 :     return hash_combine(BBInfo::getHashValue(Edge.getStart()),
     115       10764 :                         BBInfo::getHashValue(Edge.getEnd()));
     116             :   }
     117             : 
     118             :   static bool isEqual(const BasicBlockEdge &LHS, const BasicBlockEdge &RHS) {
     119       31725 :     return BBInfo::isEqual(LHS.getStart(), RHS.getStart()) &&
     120       14345 :            BBInfo::isEqual(LHS.getEnd(), RHS.getEnd());
     121             :   }
     122             : };
     123             : 
     124             : /// \brief Concrete subclass of DominatorTreeBase that is used to compute a
     125             : /// normal dominator tree.
     126             : ///
     127             : /// Definition: A block is said to be forward statically reachable if there is
     128             : /// a path from the entry of the function to the block.  A statically reachable
     129             : /// block may become statically unreachable during optimization.
     130             : ///
     131             : /// A forward unreachable block may appear in the dominator tree, or it may
     132             : /// not.  If it does, dominance queries will return results as if all reachable
     133             : /// blocks dominate it.  When asking for a Node corresponding to a potentially
     134             : /// unreachable block, calling code must handle the case where the block was
     135             : /// unreachable and the result of getNode() is nullptr.
     136             : ///
     137             : /// Generally, a block known to be unreachable when the dominator tree is
     138             : /// constructed will not be in the tree.  One which becomes unreachable after
     139             : /// the dominator tree is initially constructed may still exist in the tree,
     140             : /// even if the tree is properly updated. Calling code should not rely on the
     141             : /// preceding statements; this is stated only to assist human understanding.
     142      334207 : class DominatorTree : public DominatorTreeBase<BasicBlock, false> {
     143             :  public:
     144             :   using Base = DominatorTreeBase<BasicBlock, false>;
     145             : 
     146             :   DominatorTree() = default;
     147         986 :   explicit DominatorTree(Function &F) { recalculate(F); }
     148             : 
     149             :   /// Handle invalidation explicitly.
     150             :   bool invalidate(Function &F, const PreservedAnalyses &PA,
     151             :                   FunctionAnalysisManager::Invalidator &);
     152             : 
     153             :   // Ensure base-class overloads are visible.
     154             :   using Base::dominates;
     155             : 
     156             :   /// \brief Return true if Def dominates a use in User.
     157             :   ///
     158             :   /// This performs the special checks necessary if Def and User are in the same
     159             :   /// basic block. Note that Def doesn't dominate a use in Def itself!
     160             :   bool dominates(const Instruction *Def, const Use &U) const;
     161             :   bool dominates(const Instruction *Def, const Instruction *User) const;
     162             :   bool dominates(const Instruction *Def, const BasicBlock *BB) const;
     163             : 
     164             :   /// Return true if an edge dominates a use.
     165             :   ///
     166             :   /// If BBE is not a unique edge between start and end of the edge, it can
     167             :   /// never dominate the use.
     168             :   bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
     169             :   bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
     170             : 
     171             :   // Ensure base class overloads are visible.
     172             :   using Base::isReachableFromEntry;
     173             : 
     174             :   /// \brief Provide an overload for a Use.
     175             :   bool isReachableFromEntry(const Use &U) const;
     176             : 
     177             :   /// \brief Verify the correctness of the domtree by re-computing it.
     178             :   ///
     179             :   /// This should only be used for debugging as it aborts the program if the
     180             :   /// verification fails.
     181             :   void verifyDomTree() 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       66384 :   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             :   static nodes_iterator nodes_end(DominatorTree *N) {
     226             :     return df_end(getEntryNode(N));
     227             :   }
     228             : };
     229             : 
     230             : /// \brief 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             :   /// \brief Provide the result typedef for this analysis pass.
     237             :   using Result = DominatorTree;
     238             : 
     239             :   /// \brief Run the analysis pass over a function and produce a dominator tree.
     240             :   DominatorTree run(Function &F, FunctionAnalysisManager &);
     241             : };
     242             : 
     243             : /// \brief 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             : /// \brief Verifier pass for the \c DominatorTree.
     255             : struct DominatorTreeVerifierPass : PassInfoMixin<DominatorTreeVerifierPass> {
     256             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     257             : };
     258             : 
     259             : /// \brief Legacy analysis pass which computes a \c DominatorTree.
     260      275091 : class DominatorTreeWrapperPass : public FunctionPass {
     261             :   DominatorTree DT;
     262             : 
     263             : public:
     264             :   static char ID;
     265             : 
     266      276392 :   DominatorTreeWrapperPass() : FunctionPass(ID) {
     267      138196 :     initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
     268      138196 :   }
     269             : 
     270     3703469 :   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      134203 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
     278             :     AU.setPreservesAll();
     279      134203 :   }
     280             : 
     281     2947038 :   void releaseMemory() override { DT.releaseMemory(); }
     282             : 
     283             :   void print(raw_ostream &OS, const Module *M = nullptr) const override;
     284             : };
     285             : 
     286             : //===-------------------------------------
     287             : /// \brief Class to defer updates to a DominatorTree.
     288             : ///
     289             : /// Definition: Applying updates to every edge insertion and deletion is
     290             : /// expensive and not necessary. When one needs the DominatorTree for analysis
     291             : /// they can request a flush() to perform a larger batch update. This has the
     292             : /// advantage of the DominatorTree inspecting the set of updates to find
     293             : /// duplicates or unnecessary subtree updates.
     294             : ///
     295             : /// The scope of DeferredDominance operates at a Function level.
     296             : ///
     297             : /// It is not necessary for the user to scrub the updates for duplicates or
     298             : /// updates that point to the same block (Delete, BB_A, BB_A). Performance
     299             : /// can be gained if the caller attempts to batch updates before submitting
     300             : /// to applyUpdates(ArrayRef) in cases where duplicate edge requests will
     301             : /// occur.
     302             : ///
     303             : /// It is required for the state of the LLVM IR to be applied *before*
     304             : /// submitting updates. The update routines must analyze the current state
     305             : /// between a pair of (From, To) basic blocks to determine if the update
     306             : /// needs to be queued.
     307             : /// Example (good):
     308             : ///     TerminatorInstructionBB->removeFromParent();
     309             : ///     DDT->deleteEdge(BB, Successor);
     310             : /// Example (bad):
     311             : ///     DDT->deleteEdge(BB, Successor);
     312             : ///     TerminatorInstructionBB->removeFromParent();
     313      136314 : class DeferredDominance {
     314             : public:
     315       68157 :   DeferredDominance(DominatorTree &DT_) : DT(DT_) {}
     316             : 
     317             :   /// \brief Queues multiple updates and discards duplicates.
     318             :   void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates);
     319             : 
     320             :   /// \brief Helper method for a single edge insertion. It's almost always
     321             :   /// better to batch updates and call applyUpdates to quickly remove duplicate
     322             :   /// edges. This is best used when there is only a single insertion needed to
     323             :   /// update Dominators.
     324             :   void insertEdge(BasicBlock *From, BasicBlock *To);
     325             : 
     326             :   /// \brief Helper method for a single edge deletion. It's almost always better
     327             :   /// to batch updates and call applyUpdates to quickly remove duplicate edges.
     328             :   /// This is best used when there is only a single deletion needed to update
     329             :   /// Dominators.
     330             :   void deleteEdge(BasicBlock *From, BasicBlock *To);
     331             : 
     332             :   /// \brief Delays the deletion of a basic block until a flush() event.
     333             :   void deleteBB(BasicBlock *DelBB);
     334             : 
     335             :   /// \brief Returns true if DelBB is awaiting deletion at a flush() event.
     336             :   bool pendingDeletedBB(BasicBlock *DelBB);
     337             : 
     338             :   /// \brief Returns true if pending DT updates are queued for a flush() event.
     339             :   bool pending();
     340             : 
     341             :   /// \brief Flushes all pending updates and block deletions. Returns a
     342             :   /// correct DominatorTree reference to be used by the caller for analysis.
     343             :   DominatorTree &flush();
     344             : 
     345             :   /// \brief Drops all internal state and forces a (slow) recalculation of the
     346             :   /// DominatorTree based on the current state of the LLVM IR in F. This should
     347             :   /// only be used in corner cases such as the Entry block of F being deleted.
     348             :   void recalculate(Function &F);
     349             : 
     350             :   /// \brief Debug method to help view the state of pending updates.
     351             :   LLVM_DUMP_METHOD void dump() const;
     352             : 
     353             : private:
     354             :   DominatorTree &DT;
     355             :   SmallVector<DominatorTree::UpdateType, 16> PendUpdates;
     356             :   SmallPtrSet<BasicBlock *, 8> DeletedBBs;
     357             : 
     358             :   /// Apply an update (Kind, From, To) to the internal queued updates. The
     359             :   /// update is only added when determined to be necessary. Checks for
     360             :   /// self-domination, unnecessary updates, duplicate requests, and balanced
     361             :   /// pairs of requests are all performed. Returns true if the update is
     362             :   /// queued and false if it is discarded.
     363             :   bool applyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From,
     364             :                    BasicBlock *To);
     365             : 
     366             :   /// Performs all pending basic block deletions. We have to defer the deletion
     367             :   /// of these blocks until after the DominatorTree updates are applied. The
     368             :   /// internal workings of the DominatorTree code expect every update's From
     369             :   /// and To blocks to exist and to be a member of the same Function.
     370             :   bool flushDelBB();
     371             : };
     372             : 
     373             : } // end namespace llvm
     374             : 
     375             : #endif // LLVM_IR_DOMINATORS_H

Generated by: LCOV version 1.13