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 static constexpr bool IsPostDominators = IsPostDom;
58
59public:
60 DominanceFrontierBase() = default;
61
62 /// isPostDominator - Returns true if analysis based of postdoms
63 bool isPostDominator() const {
64 return IsPostDominators;
65 }
66
67 void releaseMemory() {
68 Frontiers.clear();
69 }
70
71 // Accessor interface:
72 using iterator = typename DomSetMapType::iterator;
73 using const_iterator = typename DomSetMapType::const_iterator;
74
75 iterator begin() { return Frontiers.begin(); }
76 const_iterator begin() const { return Frontiers.begin(); }
77 iterator end() { return Frontiers.end(); }
78 const_iterator end() const { return Frontiers.end(); }
79 iterator find(BlockT *B) { return Frontiers.find(B); }
80 const_iterator find(BlockT *B) const { return Frontiers.find(B); }
81
82 /// print - Convert to human readable form
83 ///
84 void print(raw_ostream &OS) const;
85
86 /// dump - Dump the dominance frontier to dbgs().
87#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
88 void dump() const;
89#endif
90
91 void analyze(const DomTreeT &DT);
92};
93
94class DominanceFrontier : public DominanceFrontierBase<BasicBlock, false> {
95public:
96 using DomTreeT = DomTreeBase<BasicBlock>;
97 using DomTreeNodeT = DomTreeNodeBase<BasicBlock>;
98 using DomSetType = DominanceFrontier::DomSetType;
99 using iterator = DominanceFrontier::iterator;
100 using const_iterator = DominanceFrontier::const_iterator;
101
102 /// Handle invalidation explicitly.
103 LLVM_ABI bool invalidate(Function &F, const PreservedAnalyses &PA,
104 FunctionAnalysisManager::Invalidator &);
105};
106
107class LLVM_ABI DominanceFrontierWrapperPass : public FunctionPass {
108 DominanceFrontier DF;
109
110public:
111 static char ID; // Pass ID, replacement for typeid
112
113 DominanceFrontierWrapperPass();
114
115 DominanceFrontier &getDominanceFrontier() { return DF; }
116 const DominanceFrontier &getDominanceFrontier() const { return DF; }
117
118 void releaseMemory() override;
119
120 bool runOnFunction(Function &) override;
121
122 void getAnalysisUsage(AnalysisUsage &AU) const override;
123
124 void print(raw_ostream &OS, const Module * = nullptr) const override;
125
126 void dump() const;
127};
128
129extern template class LLVM_TEMPLATE_ABI
130 DominanceFrontierBase<BasicBlock, false>;
131extern template class LLVM_TEMPLATE_ABI DominanceFrontierBase<BasicBlock, true>;
132
133/// Analysis pass which computes a \c DominanceFrontier.
134class DominanceFrontierAnalysis
135 : public AnalysisInfoMixin<DominanceFrontierAnalysis> {
136 friend AnalysisInfoMixin<DominanceFrontierAnalysis>;
137
138 static AnalysisKey Key;
139
140public:
141 /// Provide the result type for this analysis pass.
142 using Result = DominanceFrontier;
143
144 /// Run the analysis pass over a function and produce a dominator tree.
145 LLVM_ABI DominanceFrontier run(Function &F, FunctionAnalysisManager &AM);
146};
147
148/// Printer pass for the \c DominanceFrontier.
149class DominanceFrontierPrinterPass
150 : public RequiredPassInfoMixin<DominanceFrontierPrinterPass> {
151 raw_ostream &OS;
152
153public:
154 LLVM_ABI explicit DominanceFrontierPrinterPass(raw_ostream &OS);
155
156 LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
157};
158
159} // end namespace llvm
160
161#endif // LLVM_ANALYSIS_DOMINANCEFRONTIER_H
162