include/llvm/Analysis/DominanceFrontier.h

   1 //===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines the DominanceFrontier class, which calculate and holds the
  10 // dominance frontier for a function.
  11 //
  12 // This should be considered deprecated, don't add any more uses of this data
  13 // structure.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H
  18 #define LLVM_ANALYSIS_DOMINANCEFRONTIER_H
  19
  20 #include "llvm/ADT/GraphTraits.h"
  21 #include "llvm/Config/llvm-config.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 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   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   const SmallVectorImpl<BlockT *> &getRoots() const { return Roots; }
  61
  62   BlockT *getRoot() const {
  63     assert(Roots.size() == 1 && "Should always have entry node!");
  64     return Roots[0];
  65   }
  66
  67   /// isPostDominator - Returns true if analysis based of postdoms
  68   bool isPostDominator() const {
  69     return IsPostDominators;
  70   }
  71
  72   void releaseMemory() {
  73     Frontiers.clear();
  74   }
  75
  76   // Accessor interface:
  77   using iterator = typename DomSetMapType::iterator;
  78   using const_iterator = typename DomSetMapType::const_iterator;
  79
  80   iterator begin() { return Frontiers.begin(); }
  81   const_iterator begin() const { return Frontiers.begin(); }
  82   iterator end() { return Frontiers.end(); }
  83   const_iterator end() const { return Frontiers.end(); }
  84   iterator find(BlockT *B) { return Frontiers.find(B); }
  85   const_iterator find(BlockT *B) const { return Frontiers.find(B); }
  86
  87   iterator addBasicBlock(BlockT *BB, const DomSetType &frontier) {
  88     assert(find(BB) == end() && "Block already in DominanceFrontier!");
  89     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 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   void analyze(DomTreeT &DT) {
 133     assert(DT.getRoots().size() == 1 &&
 134            "Only one entry block for forward domfronts!");
 135     this->Roots = {DT.getRoot()};
 136     calculate(DT, DT[this->Roots[0]]);
 137   }
 138
 139   const DomSetType &calculate(const DomTreeT &DT, const DomTreeNodeT *Node);
 140 };
 141
 142 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 class DominanceFrontierWrapperPass : public FunctionPass {
 157   DominanceFrontier DF;
 158
 159 public:
 160   static char ID; // Pass ID, replacement for typeid
 161
 162   DominanceFrontierWrapperPass();
 163
 164   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 /// 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   /// Provide the result type for this analysis pass.
 191   using Result = DominanceFrontier;
 192
 193   /// Run the analysis pass over a function and produce a dominator tree.
 194   DominanceFrontier run(Function &F, FunctionAnalysisManager &AM);
 195 };
 196
 197 /// 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