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-05-20 00:06:23 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      447822 :   BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :
      80      447822 :     Start(Start_), End(End_) {}
      81             : 
      82             :   BasicBlockEdge(const std::pair<BasicBlock *, BasicBlock *> &Pair)
      83          28 :       : 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        2796 :   static unsigned getHashValue(const BasicBlockEdge &Edge) {
     114        8388 :     return hash_combine(BBInfo::getHashValue(Edge.getStart()),
     115       11184 :                         BBInfo::getHashValue(Edge.getEnd()));
     116             :   }
     117             : 
     118             :   static bool isEqual(const BasicBlockEdge &LHS, const BasicBlockEdge &RHS) {
     119       32385 :     return BBInfo::isEqual(LHS.getStart(), RHS.getStart()) &&
     120       14648 :            BBInfo::isEqual(LHS.getEnd(), RHS.getEnd());
     121             :   }
     122             : };
     123             : 
     124             : /// 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      355034 : class DominatorTree : public DominatorTreeBase<BasicBlock, false> {
     143             :  public:
     144             :   using Base = DominatorTreeBase<BasicBlock, false>;
     145             : 
     146             :   DominatorTree() = default;
     147        1036 :   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             :   /// 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             :   /// Provide an overload for a Use.
     175             :   bool isReachableFromEntry(const Use &U) const;
     176             : 
     177             :   // Pop up a GraphViz/gv window with the Dominator Tree rendered using `dot`.
     178             :   void viewGraph(const Twine &Name, const Twine &Title);
     179             :   void viewGraph();
     180             : };
     181             : 
     182             : //===-------------------------------------
     183             : // DominatorTree GraphTraits specializations so the DominatorTree can be
     184             : // iterable by generic graph iterators.
     185             : 
     186             : template <class Node, class ChildIterator> struct DomTreeGraphTraitsBase {
     187             :   using NodeRef = Node *;
     188             :   using ChildIteratorType = ChildIterator;
     189             :   using nodes_iterator = df_iterator<Node *, df_iterator_default_set<Node*>>;
     190             : 
     191             :   static NodeRef getEntryNode(NodeRef N) { return N; }
     192             :   static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
     193             :   static ChildIteratorType child_end(NodeRef N) { return N->end(); }
     194             : 
     195             :   static nodes_iterator nodes_begin(NodeRef N) {
     196             :     return df_begin(getEntryNode(N));
     197             :   }
     198             : 
     199             :   static nodes_iterator nodes_end(NodeRef N) { return df_end(getEntryNode(N)); }
     200             : };
     201             : 
     202             : template <>
     203             : struct GraphTraits<DomTreeNode *>
     204             :     : public DomTreeGraphTraitsBase<DomTreeNode, DomTreeNode::iterator> {};
     205             : 
     206             : template <>
     207             : struct GraphTraits<const DomTreeNode *>
     208             :     : public DomTreeGraphTraitsBase<const DomTreeNode,
     209             :                                     DomTreeNode::const_iterator> {};
     210             : 
     211             : template <> struct GraphTraits<DominatorTree*>
     212             :   : public GraphTraits<DomTreeNode*> {
     213       69630 :   static NodeRef getEntryNode(DominatorTree *DT) { return DT->getRootNode(); }
     214             : 
     215             :   static nodes_iterator nodes_begin(DominatorTree *N) {
     216             :     return df_begin(getEntryNode(N));
     217             :   }
     218             : 
     219             :   static nodes_iterator nodes_end(DominatorTree *N) {
     220             :     return df_end(getEntryNode(N));
     221             :   }
     222             : };
     223             : 
     224             : /// Analysis pass which computes a \c DominatorTree.
     225             : class DominatorTreeAnalysis : public AnalysisInfoMixin<DominatorTreeAnalysis> {
     226             :   friend AnalysisInfoMixin<DominatorTreeAnalysis>;
     227             :   static AnalysisKey Key;
     228             : 
     229             : public:
     230             :   /// Provide the result typedef for this analysis pass.
     231             :   using Result = DominatorTree;
     232             : 
     233             :   /// Run the analysis pass over a function and produce a dominator tree.
     234             :   DominatorTree run(Function &F, FunctionAnalysisManager &);
     235             : };
     236             : 
     237             : /// Printer pass for the \c DominatorTree.
     238             : class DominatorTreePrinterPass
     239             :     : public PassInfoMixin<DominatorTreePrinterPass> {
     240             :   raw_ostream &OS;
     241             : 
     242             : public:
     243             :   explicit DominatorTreePrinterPass(raw_ostream &OS);
     244             : 
     245             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     246             : };
     247             : 
     248             : /// Verifier pass for the \c DominatorTree.
     249             : struct DominatorTreeVerifierPass : PassInfoMixin<DominatorTreeVerifierPass> {
     250             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     251             : };
     252             : 
     253             : /// Legacy analysis pass which computes a \c DominatorTree.
     254      300378 : class DominatorTreeWrapperPass : public FunctionPass {
     255             :   DominatorTree DT;
     256             : 
     257             : public:
     258             :   static char ID;
     259             : 
     260      301664 :   DominatorTreeWrapperPass() : FunctionPass(ID) {
     261      150832 :     initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
     262      150832 :   }
     263             : 
     264     3969809 :   DominatorTree &getDomTree() { return DT; }
     265             :   const DominatorTree &getDomTree() const { return DT; }
     266             : 
     267             :   bool runOnFunction(Function &F) override;
     268             : 
     269             :   void verifyAnalysis() const override;
     270             : 
     271      146577 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
     272             :     AU.setPreservesAll();
     273      146577 :   }
     274             : 
     275     3240328 :   void releaseMemory() override { DT.releaseMemory(); }
     276             : 
     277             :   void print(raw_ostream &OS, const Module *M = nullptr) const override;
     278             : };
     279             : 
     280             : //===-------------------------------------
     281             : /// Class to defer updates to a DominatorTree.
     282             : ///
     283             : /// Definition: Applying updates to every edge insertion and deletion is
     284             : /// expensive and not necessary. When one needs the DominatorTree for analysis
     285             : /// they can request a flush() to perform a larger batch update. This has the
     286             : /// advantage of the DominatorTree inspecting the set of updates to find
     287             : /// duplicates or unnecessary subtree updates.
     288             : ///
     289             : /// The scope of DeferredDominance operates at a Function level.
     290             : ///
     291             : /// It is not necessary for the user to scrub the updates for duplicates or
     292             : /// updates that point to the same block (Delete, BB_A, BB_A). Performance
     293             : /// can be gained if the caller attempts to batch updates before submitting
     294             : /// to applyUpdates(ArrayRef) in cases where duplicate edge requests will
     295             : /// occur.
     296             : ///
     297             : /// It is required for the state of the LLVM IR to be applied *before*
     298             : /// submitting updates. The update routines must analyze the current state
     299             : /// between a pair of (From, To) basic blocks to determine if the update
     300             : /// needs to be queued.
     301             : /// Example (good):
     302             : ///     TerminatorInstructionBB->removeFromParent();
     303             : ///     DDT->deleteEdge(BB, Successor);
     304             : /// Example (bad):
     305             : ///     DDT->deleteEdge(BB, Successor);
     306             : ///     TerminatorInstructionBB->removeFromParent();
     307      138666 : class DeferredDominance {
     308             : public:
     309       69333 :   DeferredDominance(DominatorTree &DT_) : DT(DT_) {}
     310             : 
     311             :   /// Queues multiple updates and discards duplicates.
     312             :   void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates);
     313             : 
     314             :   /// Helper method for a single edge insertion. It's almost always
     315             :   /// better to batch updates and call applyUpdates to quickly remove duplicate
     316             :   /// edges. This is best used when there is only a single insertion needed to
     317             :   /// update Dominators.
     318             :   void insertEdge(BasicBlock *From, BasicBlock *To);
     319             : 
     320             :   /// Helper method for a single edge deletion. It's almost always better
     321             :   /// to batch updates and call applyUpdates to quickly remove duplicate edges.
     322             :   /// This is best used when there is only a single deletion needed to update
     323             :   /// Dominators.
     324             :   void deleteEdge(BasicBlock *From, BasicBlock *To);
     325             : 
     326             :   /// Delays the deletion of a basic block until a flush() event.
     327             :   void deleteBB(BasicBlock *DelBB);
     328             : 
     329             :   /// Returns true if DelBB is awaiting deletion at a flush() event.
     330             :   bool pendingDeletedBB(BasicBlock *DelBB);
     331             : 
     332             :   /// Returns true if pending DT updates are queued for a flush() event.
     333             :   bool pending();
     334             : 
     335             :   /// Flushes all pending updates and block deletions. Returns a
     336             :   /// correct DominatorTree reference to be used by the caller for analysis.
     337             :   DominatorTree &flush();
     338             : 
     339             :   /// Drops all internal state and forces a (slow) recalculation of the
     340             :   /// DominatorTree based on the current state of the LLVM IR in F. This should
     341             :   /// only be used in corner cases such as the Entry block of F being deleted.
     342             :   void recalculate(Function &F);
     343             : 
     344             :   /// Debug method to help view the state of pending updates.
     345             :   LLVM_DUMP_METHOD void dump() const;
     346             : 
     347             : private:
     348             :   DominatorTree &DT;
     349             :   SmallVector<DominatorTree::UpdateType, 16> PendUpdates;
     350             :   SmallPtrSet<BasicBlock *, 8> DeletedBBs;
     351             : 
     352             :   /// Apply an update (Kind, From, To) to the internal queued updates. The
     353             :   /// update is only added when determined to be necessary. Checks for
     354             :   /// self-domination, unnecessary updates, duplicate requests, and balanced
     355             :   /// pairs of requests are all performed. Returns true if the update is
     356             :   /// queued and false if it is discarded.
     357             :   bool applyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From,
     358             :                    BasicBlock *To);
     359             : 
     360             :   /// Performs all pending basic block deletions. We have to defer the deletion
     361             :   /// of these blocks until after the DominatorTree updates are applied. The
     362             :   /// internal workings of the DominatorTree code expect every update's From
     363             :   /// and To blocks to exist and to be a member of the same Function.
     364             :   bool flushDelBB();
     365             : };
     366             : 
     367             : } // end namespace llvm
     368             : 
     369             : #endif // LLVM_IR_DOMINATORS_H

Generated by: LCOV version 1.13