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