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). |
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.root_size() == 1 && |
135 | "Only one entry block for forward domfronts!" ); |
136 | this->Roots = {DT.getRoot()}; |
137 | calculate(DT, Node: 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 | static bool isRequired() { return true; } |
209 | }; |
210 | |
211 | } // end namespace llvm |
212 | |
213 | #endif // LLVM_ANALYSIS_DOMINANCEFRONTIER_H |
214 | |