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/DenseMap.h"
21 #include "llvm/ADT/GraphTraits.h"
22 #include "llvm/ADT/SetVector.h"
23 #include "llvm/Config/llvm-config.h"
24 #include "llvm/IR/PassManager.h"
25 #include "llvm/Pass.h"
26 #include "llvm/Support/GenericDomTree.h"
27 #include <cassert>
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   // Dom set for a bb. Use SetVector to make iterating dom frontiers of a bb
43   // deterministic.
44   using DomSetType = SetVector<BlockT *>;
45   using DomSetMapType = DenseMap<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).
getRoots()61   const SmallVectorImpl<BlockT *> &getRoots() const { return Roots; }
62 
getRoot()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
isPostDominator()69   bool isPostDominator() const {
70     return IsPostDominators;
71   }
72 
releaseMemory()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 
begin()81   iterator begin() { return Frontiers.begin(); }
begin()82   const_iterator begin() const { return Frontiers.begin(); }
end()83   iterator end() { return Frontiers.end(); }
end()84   const_iterator end() const { return Frontiers.end(); }
find(BlockT * B)85   iterator find(BlockT *B) { return Frontiers.find(B); }
find(BlockT * B)86   const_iterator find(BlockT *B) const { return Frontiers.find(B); }
87 
addBasicBlock(BlockT * BB,const DomSetType & frontier)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 false if the other dominance frontier base matches
105   /// this dominance frontier base. Otherwise return true.
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 
analyze(DomTreeT & DT)133   void analyze(DomTreeT &DT) {
134     assert(DT.root_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 
getDominanceFrontier()165   DominanceFrontier &getDominanceFrontier() { return DF; }
getDominanceFrontier()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 
isRequired()208   static bool isRequired() { return true; }
209 };
210 
211 } // end namespace llvm
212 
213 #endif // LLVM_ANALYSIS_DOMINANCEFRONTIER_H
214