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// CAUTION: For SSA-construction-like problems there are more efficient ways to
13// do that, take a look at GenericIteratedDominanceFrontier.h/SSAUpdater.h. Also
14// note that that this analysis computes dominance frontiers for *every* block
15// which inherently increases complexity. Unless you do need *all* of them and
16// *without* any modifications to the DomTree/CFG in between queries there
17// should be better alternatives.
18//
19//===----------------------------------------------------------------------===//
20
21#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H
22#define LLVM_ANALYSIS_DOMINANCEFRONTIER_H
23
24#include "llvm/ADT/DenseMap.h"
25#include "llvm/ADT/GraphTraits.h"
26#include "llvm/ADT/SetVector.h"
27#include "llvm/IR/PassManager.h"
28#include "llvm/Pass.h"
29#include "llvm/Support/GenericDomTree.h"
30#include <cassert>
31
32namespace llvm {
33
34class BasicBlock;
35class Function;
36class raw_ostream;
37
38//===----------------------------------------------------------------------===//
39/// DominanceFrontierBase - Common base class for computing forward and inverse
40/// dominance frontiers for a function.
41///
42template <class BlockT, bool IsPostDom>
43class DominanceFrontierBase {
44public:
45 // Dom set for a bb. Use SetVector to make iterating dom frontiers of a bb
46 // deterministic.
47 using DomSetType = SetVector<BlockT *>;
48 using DomSetMapType = DenseMap<BlockT *, DomSetType>; // Dom set map
49 using DomTreeT = DominatorTreeBase<BlockT, IsPostDom>;
50 using DomTreeNodeT = DomTreeNodeBase<BlockT>;
51
52protected:
53 using GraphTy = std::conditional_t<IsPostDom, Inverse<BlockT *>, BlockT *>;
54 using BlockTraits = GraphTraits<GraphTy>;
55
56 DomSetMapType Frontiers;
57 // Postdominators can have multiple roots.
58 SmallVector<BlockT *, IsPostDom ? 4 : 1> Roots;
59 static constexpr bool IsPostDominators = IsPostDom;
60
61public:
62 DominanceFrontierBase() = default;
63
64 /// getRoots - Return the root blocks of the current CFG. This may include
65 /// multiple blocks if we are computing post dominators. For forward
66 /// dominators, this will always be a single block (the entry node).
67 const SmallVectorImpl<BlockT *> &getRoots() const { return Roots; }
68
69 BlockT *getRoot() const {
70 assert(Roots.size() == 1 && "Should always have entry node!");
71 return Roots[0];
72 }
73
74 /// isPostDominator - Returns true if analysis based of postdoms
75 bool isPostDominator() const {
76 return IsPostDominators;
77 }
78
79 void releaseMemory() {
80 Frontiers.clear();
81 }
82
83 // Accessor interface:
84 using iterator = typename DomSetMapType::iterator;
85 using const_iterator = typename DomSetMapType::const_iterator;
86
87 iterator begin() { return Frontiers.begin(); }
88 const_iterator begin() const { return Frontiers.begin(); }
89 iterator end() { return Frontiers.end(); }
90 const_iterator end() const { return Frontiers.end(); }
91 iterator find(BlockT *B) { return Frontiers.find(B); }
92 const_iterator find(BlockT *B) const { return Frontiers.find(B); }
93
94 /// print - Convert to human readable form
95 ///
96 void print(raw_ostream &OS) const;
97
98 /// dump - Dump the dominance frontier to dbgs().
99#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
100 void dump() const;
101#endif
102
103 void analyze(DomTreeT &DT) {
104 assert((IsPostDom || DT.root_size() == 1) &&
105 "Only one entry block for forward domfronts!");
106 assert(DT.root_size() == 1 &&
107 "Support for post-dom frontiers with multiple roots hasn't been "
108 "implemented yet!");
109 this->Roots = {DT.getRoot()};
110 calculate(DT, Node: DT[this->Roots[0]]);
111 }
112
113 void calculate(const DomTreeT &DT, const DomTreeNodeT *Node);
114};
115
116class DominanceFrontier : public DominanceFrontierBase<BasicBlock, false> {
117public:
118 using DomTreeT = DomTreeBase<BasicBlock>;
119 using DomTreeNodeT = DomTreeNodeBase<BasicBlock>;
120 using DomSetType = DominanceFrontier::DomSetType;
121 using iterator = DominanceFrontier::iterator;
122 using const_iterator = DominanceFrontier::const_iterator;
123
124 /// Handle invalidation explicitly.
125 bool invalidate(Function &F, const PreservedAnalyses &PA,
126 FunctionAnalysisManager::Invalidator &);
127};
128
129class DominanceFrontierWrapperPass : public FunctionPass {
130 DominanceFrontier DF;
131
132public:
133 static char ID; // Pass ID, replacement for typeid
134
135 DominanceFrontierWrapperPass();
136
137 DominanceFrontier &getDominanceFrontier() { return DF; }
138 const DominanceFrontier &getDominanceFrontier() const { return DF; }
139
140 void releaseMemory() override;
141
142 bool runOnFunction(Function &) override;
143
144 void getAnalysisUsage(AnalysisUsage &AU) const override;
145
146 void print(raw_ostream &OS, const Module * = nullptr) const override;
147
148 void dump() const;
149};
150
151extern template class DominanceFrontierBase<BasicBlock, false>;
152extern template class DominanceFrontierBase<BasicBlock, true>;
153
154/// Analysis pass which computes a \c DominanceFrontier.
155class DominanceFrontierAnalysis
156 : public AnalysisInfoMixin<DominanceFrontierAnalysis> {
157 friend AnalysisInfoMixin<DominanceFrontierAnalysis>;
158
159 static AnalysisKey Key;
160
161public:
162 /// Provide the result type for this analysis pass.
163 using Result = DominanceFrontier;
164
165 /// Run the analysis pass over a function and produce a dominator tree.
166 DominanceFrontier run(Function &F, FunctionAnalysisManager &AM);
167};
168
169/// Printer pass for the \c DominanceFrontier.
170class DominanceFrontierPrinterPass
171 : public PassInfoMixin<DominanceFrontierPrinterPass> {
172 raw_ostream &OS;
173
174public:
175 explicit DominanceFrontierPrinterPass(raw_ostream &OS);
176
177 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
178
179 static bool isRequired() { return true; }
180};
181
182} // end namespace llvm
183
184#endif // LLVM_ANALYSIS_DOMINANCEFRONTIER_H
185