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