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 bool invalidate(Function &F, const PreservedAnalyses &PA,
104 FunctionAnalysisManager::Invalidator &);
105};
106
107class 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 DominanceFrontierBase<BasicBlock, false>;
130extern template class DominanceFrontierBase<BasicBlock, true>;
131
132/// Analysis pass which computes a \c DominanceFrontier.
133class DominanceFrontierAnalysis
134 : public AnalysisInfoMixin<DominanceFrontierAnalysis> {
135 friend AnalysisInfoMixin<DominanceFrontierAnalysis>;
136
137 static AnalysisKey Key;
138
139public:
140 /// Provide the result type for this analysis pass.
141 using Result = DominanceFrontier;
142
143 /// Run the analysis pass over a function and produce a dominator tree.
144 DominanceFrontier run(Function &F, FunctionAnalysisManager &AM);
145};
146
147/// Printer pass for the \c DominanceFrontier.
148class DominanceFrontierPrinterPass
149 : public PassInfoMixin<DominanceFrontierPrinterPass> {
150 raw_ostream &OS;
151
152public:
153 explicit DominanceFrontierPrinterPass(raw_ostream &OS);
154
155 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
156
157 static bool isRequired() { return true; }
158};
159
160} // end namespace llvm
161
162#endif // LLVM_ANALYSIS_DOMINANCEFRONTIER_H
163