contrib/llvm/include/llvm/Analysis/DominanceFrontier.h

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