LCOV - code coverage report
Current view: top level - include/llvm/Analysis - DominanceFrontier.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 15 26 57.7 %
Date: 2017-09-14 15:23:50 Functions: 6 51 11.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- 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 DominanceFrontier class, which calculate and holds the
      11             : // dominance frontier for a function.
      12             : //
      13             : // This should be considered deprecated, don't add any more uses of this data
      14             : // structure.
      15             : //
      16             : //===----------------------------------------------------------------------===//
      17             : 
      18             : #ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H
      19             : #define LLVM_ANALYSIS_DOMINANCEFRONTIER_H
      20             : 
      21             : #include "llvm/ADT/GraphTraits.h"
      22             : #include "llvm/IR/PassManager.h"
      23             : #include "llvm/Pass.h"
      24             : #include "llvm/Support/GenericDomTree.h"
      25             : #include <cassert>
      26             : #include <map>
      27             : #include <set>
      28             : #include <utility>
      29             : #include <vector>
      30             : 
      31             : namespace llvm {
      32             : 
      33             : class Function;
      34             : class raw_ostream;
      35             : 
      36             : //===----------------------------------------------------------------------===//
      37             : /// DominanceFrontierBase - Common base class for computing forward and inverse
      38             : /// dominance frontiers for a function.
      39             : ///
      40             : template <class BlockT, bool IsPostDom>
      41       14868 : class DominanceFrontierBase {
      42             : public:
      43             :   using DomSetType = std::set<BlockT *>;                // Dom set for a bb
      44             :   using DomSetMapType = std::map<BlockT *, DomSetType>; // Dom set map
      45             : 
      46             : protected:
      47             :   using BlockTraits = GraphTraits<BlockT *>;
      48             : 
      49             :   DomSetMapType Frontiers;
      50             :   // Postdominators can have multiple roots.
      51             :   SmallVector<BlockT *, IsPostDom ? 4 : 1> Roots;
      52             :   static constexpr bool IsPostDominators = IsPostDom;
      53             : 
      54             : public:
      55       14955 :   DominanceFrontierBase() = default;
      56             : 
      57             :   /// getRoots - Return the root blocks of the current CFG.  This may include
      58             :   /// multiple blocks if we are computing post dominators.  For forward
      59             :   /// dominators, this will always be a single block (the entry node).
      60           0 :   const SmallVectorImpl<BlockT *> &getRoots() const { return Roots; }
      61             : 
      62           0 :   BlockT *getRoot() const {
      63             :     assert(Roots.size() == 1 && "Should always have entry node!");
      64           0 :     return Roots[0];
      65             :   }
      66             : 
      67             :   /// isPostDominator - Returns true if analysis based of postdoms
      68           0 :   bool isPostDominator() const {
      69           0 :     return IsPostDominators;
      70             :   }
      71             : 
      72           0 :   void releaseMemory() {
      73       84720 :     Frontiers.clear();
      74           0 :   }
      75             : 
      76             :   // Accessor interface:
      77             :   using iterator = typename DomSetMapType::iterator;
      78             :   using const_iterator = typename DomSetMapType::const_iterator;
      79             : 
      80           0 :   iterator begin() { return Frontiers.begin(); }
      81           4 :   const_iterator begin() const { return Frontiers.begin(); }
      82           0 :   iterator end() { return Frontiers.end(); }
      83       19070 :   const_iterator end() const { return Frontiers.end(); }
      84       81914 :   iterator find(BlockT *B) { return Frontiers.find(B); }
      85       19066 :   const_iterator find(BlockT *B) const { return Frontiers.find(B); }
      86             : 
      87           0 :   iterator addBasicBlock(BlockT *BB, const DomSetType &frontier) {
      88             :     assert(find(BB) == end() && "Block already in DominanceFrontier!");
      89           0 :     return Frontiers.insert(std::make_pair(BB, frontier)).first;
      90             :   }
      91             : 
      92             :   /// removeBlock - Remove basic block BB's frontier.
      93             :   void removeBlock(BlockT *BB);
      94             : 
      95             :   void addToFrontier(iterator I, BlockT *Node);
      96             : 
      97             :   void removeFromFrontier(iterator I, BlockT *Node);
      98             : 
      99             :   /// compareDomSet - Return false if two domsets match. Otherwise
     100             :   /// return true;
     101             :   bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const;
     102             : 
     103             :   /// compare - Return true if the other dominance frontier base matches
     104             :   /// this dominance frontier base. Otherwise return false.
     105             :   bool compare(DominanceFrontierBase &Other) const;
     106             : 
     107             :   /// print - Convert to human readable form
     108             :   ///
     109             :   void print(raw_ostream &OS) const;
     110             : 
     111             :   /// dump - Dump the dominance frontier to dbgs().
     112             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     113             :   void dump() const;
     114             : #endif
     115             : };
     116             : 
     117             : //===-------------------------------------
     118             : /// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
     119             : /// used to compute a forward dominator frontiers.
     120             : ///
     121             : template <class BlockT>
     122       14926 : class ForwardDominanceFrontierBase
     123             :     : public DominanceFrontierBase<BlockT, false> {
     124             : private:
     125             :   using BlockTraits = GraphTraits<BlockT *>;
     126             : 
     127             : public:
     128             :   using DomTreeT = DomTreeBase<BlockT>;
     129             :   using DomTreeNodeT = DomTreeNodeBase<BlockT>;
     130             :   using DomSetType = typename DominanceFrontierBase<BlockT, false>::DomSetType;
     131             : 
     132       21208 :   void analyze(DomTreeT &DT) {
     133             :     assert(DT.getRoots().size() == 1 &&
     134             :            "Only one entry block for forward domfronts!");
     135       42416 :     this->Roots = {DT.getRoot()};
     136       63624 :     calculate(DT, DT[this->Roots[0]]);
     137       21208 :   }
     138             : 
     139             :   const DomSetType &calculate(const DomTreeT &DT, const DomTreeNodeT *Node);
     140             : };
     141             : 
     142       16678 : class DominanceFrontier : public ForwardDominanceFrontierBase<BasicBlock> {
     143             : public:
     144             :   using DomTreeT = DomTreeBase<BasicBlock>;
     145             :   using DomTreeNodeT = DomTreeNodeBase<BasicBlock>;
     146             :   using DomSetType = DominanceFrontierBase<BasicBlock, false>::DomSetType;
     147             :   using iterator = DominanceFrontierBase<BasicBlock, false>::iterator;
     148             :   using const_iterator =
     149             :       DominanceFrontierBase<BasicBlock, false>::const_iterator;
     150             : 
     151             :   /// Handle invalidation explicitly.
     152             :   bool invalidate(Function &F, const PreservedAnalyses &PA,
     153             :                   FunctionAnalysisManager::Invalidator &);
     154             : };
     155             : 
     156       12375 : class DominanceFrontierWrapperPass : public FunctionPass {
     157             :   DominanceFrontier DF;
     158             : 
     159             : public:
     160             :   static char ID; // Pass ID, replacement for typeid
     161             : 
     162             :   DominanceFrontierWrapperPass();
     163             : 
     164       19483 :   DominanceFrontier &getDominanceFrontier() { return DF; }
     165             :   const DominanceFrontier &getDominanceFrontier() const { return DF;  }
     166             : 
     167             :   void releaseMemory() override;
     168             : 
     169             :   bool runOnFunction(Function &) override;
     170             : 
     171             :   void getAnalysisUsage(AnalysisUsage &AU) const override;
     172             : 
     173             :   void print(raw_ostream &OS, const Module * = nullptr) const override;
     174             : 
     175             :   void dump() const;
     176             : };
     177             : 
     178             : extern template class DominanceFrontierBase<BasicBlock, false>;
     179             : extern template class DominanceFrontierBase<BasicBlock, true>;
     180             : extern template class ForwardDominanceFrontierBase<BasicBlock>;
     181             : 
     182             : /// \brief Analysis pass which computes a \c DominanceFrontier.
     183             : class DominanceFrontierAnalysis
     184             :     : public AnalysisInfoMixin<DominanceFrontierAnalysis> {
     185             :   friend AnalysisInfoMixin<DominanceFrontierAnalysis>;
     186             : 
     187             :   static AnalysisKey Key;
     188             : 
     189             : public:
     190             :   /// \brief Provide the result type for this analysis pass.
     191             :   using Result = DominanceFrontier;
     192             : 
     193             :   /// \brief Run the analysis pass over a function and produce a dominator tree.
     194             :   DominanceFrontier run(Function &F, FunctionAnalysisManager &AM);
     195             : };
     196             : 
     197             : /// \brief Printer pass for the \c DominanceFrontier.
     198             : class DominanceFrontierPrinterPass
     199             :     : public PassInfoMixin<DominanceFrontierPrinterPass> {
     200             :   raw_ostream &OS;
     201             : 
     202             : public:
     203             :   explicit DominanceFrontierPrinterPass(raw_ostream &OS);
     204             : 
     205             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     206             : };
     207             : 
     208             : } // end namespace llvm
     209             : 
     210             : #endif // LLVM_ANALYSIS_DOMINANCEFRONTIER_H

Generated by: LCOV version 1.13