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/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   const SmallVectorImpl<BlockT *> &getRoots() const { return Roots; }
  62
  63   BlockT *getRoot() const {
  64     assert(Roots.size() == 1 && "Should always have entry node!");
  65     return Roots[0];
  66   }
  67
  68   /// isPostDominator - Returns true if analysis based of postdoms
  69   bool isPostDominator() const {
  70     return IsPostDominators;
  71   }
  72
  73   void releaseMemory() {
  74     Frontiers.clear();
  75   }
  76
  77   // Accessor interface:
  78   using iterator = typename DomSetMapType::iterator;
  79   using const_iterator = typename DomSetMapType::const_iterator;
  80
  81   iterator begin() { return Frontiers.begin(); }
  82   const_iterator begin() const { return Frontiers.begin(); }
  83   iterator end() { return Frontiers.end(); }
  84   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
  88   iterator addBasicBlock(BlockT *BB, const DomSetType &frontier) {
  89     assert(find(BB) == end() && "Block already in DominanceFrontier!");
  90     return Frontiers.insert(std::make_pair(BB, frontier)).first;
  91   }
  92
  93   /// removeBlock - Remove basic block BB's frontier.
  94   void removeBlock(BlockT *BB);
  95
  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   /// return true;
 102   bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const;
 103
 104   /// compare - Return true if the other dominance frontier base matches
 105   /// this dominance frontier base. Otherwise return false.
 106   bool compare(DominanceFrontierBase &Other) const;
 107
 108   /// print - Convert to human readable form
 109   ///
 110   void print(raw_ostream &OS) const;
 111
 112   /// dump - Dump the dominance frontier to dbgs().
 113 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 114   void dump() const;
 115 #endif
 116 };
 117
 118 //===-------------------------------------
 119 /// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
 120 /// used to compute a forward dominator frontiers.
 121 ///
 122 template <class BlockT>
 123 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   void analyze(DomTreeT &DT) {
 134     assert(DT.getRoots().size() == 1 &&
 135            "Only one entry block for forward domfronts!");
 136     this->Roots = {DT.getRoot()};
 137     calculate(DT, DT[this->Roots[0]]);
 138   }
 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   static char ID; // Pass ID, replacement for typeid
 162
 163   DominanceFrontierWrapperPass();
 164
 165   DominanceFrontier &getDominanceFrontier() { return DF; }
 166   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