LLVM 18.0.0git
DominanceFrontier.h
Go to the documentation of this file.
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
21#include "llvm/Config/llvm-config.h"
22#include "llvm/IR/PassManager.h"
23#include "llvm/Pass.h"
25#include <cassert>
26#include <map>
27#include <set>
28#include <utility>
29
30namespace llvm {
31
32class Function;
33class raw_ostream;
34
35//===----------------------------------------------------------------------===//
36/// DominanceFrontierBase - Common base class for computing forward and inverse
37/// dominance frontiers for a function.
38///
39template <class BlockT, bool IsPostDom>
41public:
42 using DomSetType = std::set<BlockT *>; // Dom set for a bb
43 using DomSetMapType = std::map<BlockT *, DomSetType>; // Dom set map
44
45protected:
47
49 // Postdominators can have multiple roots.
51 static constexpr bool IsPostDominators = IsPostDom;
52
53public:
55
56 /// getRoots - Return the root blocks of the current CFG. This may include
57 /// multiple blocks if we are computing post dominators. For forward
58 /// dominators, this will always be a single block (the entry node).
59 const SmallVectorImpl<BlockT *> &getRoots() const { return Roots; }
60
61 BlockT *getRoot() const {
62 assert(Roots.size() == 1 && "Should always have entry node!");
63 return Roots[0];
64 }
65
66 /// isPostDominator - Returns true if analysis based of postdoms
67 bool isPostDominator() const {
68 return IsPostDominators;
69 }
70
72 Frontiers.clear();
73 }
74
75 // Accessor interface:
76 using iterator = typename DomSetMapType::iterator;
77 using const_iterator = typename DomSetMapType::const_iterator;
78
79 iterator begin() { return Frontiers.begin(); }
80 const_iterator begin() const { return Frontiers.begin(); }
81 iterator end() { return Frontiers.end(); }
82 const_iterator end() const { return Frontiers.end(); }
83 iterator find(BlockT *B) { return Frontiers.find(B); }
84 const_iterator find(BlockT *B) const { return Frontiers.find(B); }
85
86 iterator addBasicBlock(BlockT *BB, const DomSetType &frontier) {
87 assert(find(BB) == end() && "Block already in DominanceFrontier!");
88 return Frontiers.insert(std::make_pair(BB, frontier)).first;
89 }
90
91 /// removeBlock - Remove basic block BB's frontier.
92 void removeBlock(BlockT *BB);
93
94 void addToFrontier(iterator I, BlockT *Node);
95
96 void removeFromFrontier(iterator I, BlockT *Node);
97
98 /// compareDomSet - Return false if two domsets match. Otherwise
99 /// return true;
100 bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const;
101
102 /// compare - Return true if the other dominance frontier base matches
103 /// this dominance frontier base. Otherwise return false.
105
106 /// print - Convert to human readable form
107 ///
108 void print(raw_ostream &OS) const;
109
110 /// dump - Dump the dominance frontier to dbgs().
111#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
112 void dump() const;
113#endif
114};
115
116//===-------------------------------------
117/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
118/// used to compute a forward dominator frontiers.
119///
120template <class BlockT>
122 : public DominanceFrontierBase<BlockT, false> {
123private:
125
126public:
130
131 void analyze(DomTreeT &DT) {
132 assert(DT.root_size() == 1 &&
133 "Only one entry block for forward domfronts!");
134 this->Roots = {DT.getRoot()};
135 calculate(DT, DT[this->Roots[0]]);
136 }
137
138 const DomSetType &calculate(const DomTreeT &DT, const DomTreeNodeT *Node);
139};
140
142public:
149
150 /// Handle invalidation explicitly.
151 bool invalidate(Function &F, const PreservedAnalyses &PA,
153};
154
157
158public:
159 static char ID; // Pass ID, replacement for typeid
160
162
164 const DominanceFrontier &getDominanceFrontier() const { return DF; }
165
166 void releaseMemory() override;
167
168 bool runOnFunction(Function &) override;
169
170 void getAnalysisUsage(AnalysisUsage &AU) const override;
171
172 void print(raw_ostream &OS, const Module * = nullptr) const override;
173
174 void dump() const;
175};
176
177extern template class DominanceFrontierBase<BasicBlock, false>;
178extern template class DominanceFrontierBase<BasicBlock, true>;
179extern template class ForwardDominanceFrontierBase<BasicBlock>;
180
181/// Analysis pass which computes a \c DominanceFrontier.
185
186 static AnalysisKey Key;
187
188public:
189 /// Provide the result type for this analysis pass.
191
192 /// Run the analysis pass over a function and produce a dominator tree.
194};
195
196/// Printer pass for the \c DominanceFrontier.
200
201public:
203
205};
206
207} // end namespace llvm
208
209#endif // LLVM_ANALYSIS_DOMINANCEFRONTIER_H
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file defines a set of templates that efficiently compute a dominator tree over a generic graph.
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
Represent the analysis usage information of a pass.
Base class for the actual dominator tree node.
Analysis pass which computes a DominanceFrontier.
DominanceFrontierBase - Common base class for computing forward and inverse dominance frontiers for a...
bool compare(DominanceFrontierBase &Other) const
compare - Return true if the other dominance frontier base matches this dominance frontier base.
void print(raw_ostream &OS) const
print - Convert to human readable form
iterator addBasicBlock(BlockT *BB, const DomSetType &frontier)
const_iterator find(BlockT *B) const
typename DomSetMapType::iterator iterator
bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const
compareDomSet - Return false if two domsets match.
std::set< BlockT * > DomSetType
SmallVector< BlockT *, IsPostDom ? 4 :1 > Roots
const_iterator end() const
const SmallVectorImpl< BlockT * > & getRoots() const
getRoots - Return the root blocks of the current CFG.
void removeFromFrontier(iterator I, BlockT *Node)
static constexpr bool IsPostDominators
void dump() const
dump - Dump the dominance frontier to dbgs().
bool isPostDominator() const
isPostDominator - Returns true if analysis based of postdoms
std::map< BlockT *, DomSetType > DomSetMapType
typename DomSetMapType::const_iterator const_iterator
void addToFrontier(iterator I, BlockT *Node)
const_iterator begin() const
void removeBlock(BlockT *BB)
removeBlock - Remove basic block BB's frontier.
Printer pass for the DominanceFrontier.
const DominanceFrontier & getDominanceFrontier() const
bool runOnFunction(Function &) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
DominanceFrontier & getDominanceFrontier()
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
DominanceFrontierBase< BasicBlock, false >::iterator iterator
DominanceFrontierBase< BasicBlock, false >::DomSetType DomSetType
DominanceFrontierBase< BasicBlock, false >::const_iterator const_iterator
Core dominator tree base class.
size_t root_size() const
NodeT * getRoot() const
DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is used to compute a forwar...
const DomSetType & calculate(const DomTreeT &DT, const DomTreeNodeT *Node)
typename DominanceFrontierBase< BlockT, false >::DomSetType DomSetType
DomTreeNodeBase< BlockT > DomTreeNodeT
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Other
Any other memory.
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371