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

Generated by: LCOV version 1.13