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/IR/PassManager.h"
24#include "llvm/Pass.h"
25#include "llvm/Support/GenericDomTree.h"
26#include <cassert>
27
28namespace llvm {
29
30class BasicBlock;
31class Function;
32class raw_ostream;
33
34//===----------------------------------------------------------------------===//
35/// DominanceFrontierBase - Common base class for computing forward and inverse
36/// dominance frontiers for a function.
37///
38template <class BlockT, bool IsPostDom>
39class DominanceFrontierBase {
40public:
41 // Dom set for a bb. Use SetVector to make iterating dom frontiers of a bb
42 // deterministic.
43 using DomSetType = SetVector<BlockT *>;
44 using DomSetMapType = DenseMap<BlockT *, DomSetType>; // Dom set map
45
46protected:
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
54public:
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 /// print - Convert to human readable form
88 ///
89 void print(raw_ostream &OS) const;
90
91 /// dump - Dump the dominance frontier to dbgs().
92#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
93 void dump() const;
94#endif
95};
96
97//===-------------------------------------
98/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
99/// used to compute a forward dominator frontiers.
100///
101template <class BlockT>
102class ForwardDominanceFrontierBase
103 : public DominanceFrontierBase<BlockT, false> {
104private:
105 using BlockTraits = GraphTraits<BlockT *>;
106
107public:
108 using DomTreeT = DomTreeBase<BlockT>;
109 using DomTreeNodeT = DomTreeNodeBase<BlockT>;
110 using DomSetType = typename DominanceFrontierBase<BlockT, false>::DomSetType;
111
112 void analyze(DomTreeT &DT) {
113 assert(DT.root_size() == 1 &&
114 "Only one entry block for forward domfronts!");
115 this->Roots = {DT.getRoot()};
116 calculate(DT, Node: DT[this->Roots[0]]);
117 }
118
119 void calculate(const DomTreeT &DT, const DomTreeNodeT *Node);
120};
121
122class DominanceFrontier : public ForwardDominanceFrontierBase<BasicBlock> {
123public:
124 using DomTreeT = DomTreeBase<BasicBlock>;
125 using DomTreeNodeT = DomTreeNodeBase<BasicBlock>;
126 using DomSetType = DominanceFrontierBase<BasicBlock, false>::DomSetType;
127 using iterator = DominanceFrontierBase<BasicBlock, false>::iterator;
128 using const_iterator =
129 DominanceFrontierBase<BasicBlock, false>::const_iterator;
130
131 /// Handle invalidation explicitly.
132 bool invalidate(Function &F, const PreservedAnalyses &PA,
133 FunctionAnalysisManager::Invalidator &);
134};
135
136class DominanceFrontierWrapperPass : public FunctionPass {
137 DominanceFrontier DF;
138
139public:
140 static char ID; // Pass ID, replacement for typeid
141
142 DominanceFrontierWrapperPass();
143
144 DominanceFrontier &getDominanceFrontier() { return DF; }
145 const DominanceFrontier &getDominanceFrontier() const { return DF; }
146
147 void releaseMemory() override;
148
149 bool runOnFunction(Function &) override;
150
151 void getAnalysisUsage(AnalysisUsage &AU) const override;
152
153 void print(raw_ostream &OS, const Module * = nullptr) const override;
154
155 void dump() const;
156};
157
158extern template class DominanceFrontierBase<BasicBlock, false>;
159extern template class DominanceFrontierBase<BasicBlock, true>;
160extern template class ForwardDominanceFrontierBase<BasicBlock>;
161
162/// Analysis pass which computes a \c DominanceFrontier.
163class DominanceFrontierAnalysis
164 : public AnalysisInfoMixin<DominanceFrontierAnalysis> {
165 friend AnalysisInfoMixin<DominanceFrontierAnalysis>;
166
167 static AnalysisKey Key;
168
169public:
170 /// Provide the result type for this analysis pass.
171 using Result = DominanceFrontier;
172
173 /// Run the analysis pass over a function and produce a dominator tree.
174 DominanceFrontier run(Function &F, FunctionAnalysisManager &AM);
175};
176
177/// Printer pass for the \c DominanceFrontier.
178class DominanceFrontierPrinterPass
179 : public PassInfoMixin<DominanceFrontierPrinterPass> {
180 raw_ostream &OS;
181
182public:
183 explicit DominanceFrontierPrinterPass(raw_ostream &OS);
184
185 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
186
187 static bool isRequired() { return true; }
188};
189
190} // end namespace llvm
191
192#endif // LLVM_ANALYSIS_DOMINANCEFRONTIER_H
193