LLVM  14.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 
20 #include "llvm/ADT/GraphTraits.h"
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 
30 namespace llvm {
31 
32 class Function;
33 class raw_ostream;
34 
35 //===----------------------------------------------------------------------===//
36 /// DominanceFrontierBase - Common base class for computing forward and inverse
37 /// dominance frontiers for a function.
38 ///
39 template <class BlockT, bool IsPostDom>
41 public:
42  using DomSetType = std::set<BlockT *>; // Dom set for a bb
43  using DomSetMapType = std::map<BlockT *, DomSetType>; // Dom set map
44 
45 protected:
47 
49  // Postdominators can have multiple roots.
51  static constexpr bool IsPostDominators = IsPostDom;
52 
53 public:
54  DominanceFrontierBase() = default;
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 
71  void releaseMemory() {
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.
104  bool compare(DominanceFrontierBase &Other) const;
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 ///
120 template <class BlockT>
122  : public DominanceFrontierBase<BlockT, false> {
123 private:
125 
126 public:
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 
142 public:
147  using const_iterator =
149 
150  /// Handle invalidation explicitly.
151  bool invalidate(Function &F, const PreservedAnalyses &PA,
153 };
154 
157 
158 public:
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 
177 extern template class DominanceFrontierBase<BasicBlock, false>;
178 extern template class DominanceFrontierBase<BasicBlock, true>;
179 extern template class ForwardDominanceFrontierBase<BasicBlock>;
180 
181 /// Analysis pass which computes a \c DominanceFrontier.
185 
186  static AnalysisKey Key;
187 
188 public:
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.
199  raw_ostream &OS;
200 
201 public:
203 
205 };
206 
207 } // end namespace llvm
208 
209 #endif // LLVM_ANALYSIS_DOMINANCEFRONTIER_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::DominanceFrontierBase::Roots
SmallVector< BlockT *, IsPostDom ? 4 :1 > Roots
Definition: DominanceFrontier.h:50
llvm::DominanceFrontierBase::getRoot
BlockT * getRoot() const
Definition: DominanceFrontier.h:61
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::DominanceFrontierWrapperPass::runOnFunction
bool runOnFunction(Function &) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition: DominanceFrontier.cpp:48
llvm::PassInfoMixin< DominanceFrontierPrinterPass >
llvm::Function
Definition: Function.h:61
Pass.h
llvm::ForwardDominanceFrontierBase::DomSetType
typename DominanceFrontierBase< BlockT, false >::DomSetType DomSetType
Definition: DominanceFrontier.h:129
llvm::ForwardDominanceFrontierBase::DomTreeT
DomTreeBase< BlockT > DomTreeT
Definition: DominanceFrontier.h:127
llvm::SmallVector< BlockT *, IsPostDom ? 4 :1 >
llvm::DominanceFrontierWrapperPass::DominanceFrontierWrapperPass
DominanceFrontierWrapperPass()
Definition: DominanceFrontier.cpp:39
llvm::DominanceFrontierBase::dump
void dump() const
dump - Dump the dominance frontier to dbgs().
Definition: DominanceFrontierImpl.h:153
llvm::DominanceFrontierWrapperPass::dump
void dump() const
Definition: DominanceFrontier.cpp:64
llvm::DominatorTreeBase::root_size
size_t root_size() const
Definition: GenericDomTree.h:302
llvm::DominanceFrontierWrapperPass::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: DominanceFrontier.cpp:44
llvm::DominanceFrontierBase::compareDomSet
bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const
compareDomSet - Return false if two domsets match.
Definition: DominanceFrontierImpl.h:74
llvm::DominanceFrontierWrapperPass::getDominanceFrontier
const DominanceFrontier & getDominanceFrontier() const
Definition: DominanceFrontier.h:164
llvm::DominanceFrontier::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
Definition: DominanceFrontier.cpp:70
llvm::DominanceFrontierBase::IsPostDominators
static constexpr bool IsPostDominators
Definition: DominanceFrontier.h:51
F
#define F(x, y, z)
Definition: MD5.cpp:56
GraphTraits.h
llvm::DominanceFrontierBase::end
iterator end()
Definition: DominanceFrontier.h:81
llvm::DominanceFrontierPrinterPass
Printer pass for the DominanceFrontier.
Definition: DominanceFrontier.h:197
llvm::DominanceFrontierBase< BasicBlock, false >::iterator
typename DomSetMapType::iterator iterator
Definition: DominanceFrontier.h:76
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::DominanceFrontierWrapperPass::getDominanceFrontier
DominanceFrontier & getDominanceFrontier()
Definition: DominanceFrontier.h:163
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:481
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::DominanceFrontierBase::find
const_iterator find(BlockT *B) const
Definition: DominanceFrontier.h:84
llvm::DominanceFrontier::const_iterator
DominanceFrontierBase< BasicBlock, false >::const_iterator const_iterator
Definition: DominanceFrontier.h:148
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:672
llvm::DominatorTreeBase::getRoot
NodeT * getRoot() const
Definition: GenericDomTree.h:461
llvm::DominanceFrontierBase::releaseMemory
void releaseMemory()
Definition: DominanceFrontier.h:71
llvm::DominanceFrontier::DomSetType
DominanceFrontierBase< BasicBlock, false >::DomSetType DomSetType
Definition: DominanceFrontier.h:145
llvm::DominanceFrontierBase::addBasicBlock
iterator addBasicBlock(BlockT *BB, const DomSetType &frontier)
Definition: DominanceFrontier.h:86
llvm::DominanceFrontierWrapperPass::print
void print(raw_ostream &OS, const Module *=nullptr) const override
print - Print out the internal state of the pass.
Definition: DominanceFrontier.cpp:59
llvm::DominanceFrontier::iterator
DominanceFrontierBase< BasicBlock, false >::iterator iterator
Definition: DominanceFrontier.h:146
llvm::ForwardDominanceFrontierBase
DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is used to compute a forwar...
Definition: DominanceFrontier.h:121
llvm::DominanceFrontierWrapperPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: DominanceFrontier.cpp:54
llvm::DominanceFrontierBase::removeBlock
void removeBlock(BlockT *BB)
removeBlock - Remove basic block BB's frontier.
Definition: DominanceFrontierImpl.h:50
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
I
#define I(x, y, z)
Definition: MD5.cpp:59
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::DominanceFrontierBase< BasicBlock, false >::const_iterator
typename DomSetMapType::const_iterator const_iterator
Definition: DominanceFrontier.h:77
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::DominanceFrontierBase
DominanceFrontierBase - Common base class for computing forward and inverse dominance frontiers for a...
Definition: DominanceFrontier.h:40
llvm::AnalysisInfoMixin< DominanceFrontierAnalysis >
llvm::DominanceFrontierBase::print
void print(raw_ostream &OS) const
print - Convert to human readable form
Definition: DominanceFrontierImpl.h:129
llvm::ForwardDominanceFrontierBase::DomTreeNodeT
DomTreeNodeBase< BlockT > DomTreeNodeT
Definition: DominanceFrontier.h:128
llvm::DominanceFrontierBase::compare
bool compare(DominanceFrontierBase &Other) const
compare - Return true if the other dominance frontier base matches this dominance frontier base.
Definition: DominanceFrontierImpl.h:99
llvm::DominatorTreeBase
Core dominator tree base class.
Definition: LoopInfo.h:65
Node
Definition: ItaniumDemangle.h:234
llvm::DominanceFrontierAnalysis
Analysis pass which computes a DominanceFrontier.
Definition: DominanceFrontier.h:182
llvm::DomTreeNodeBase< BasicBlock >
llvm::DominanceFrontierBase::getRoots
const SmallVectorImpl< BlockT * > & getRoots() const
getRoots - Return the root blocks of the current CFG.
Definition: DominanceFrontier.h:59
GenericDomTree.h
llvm::DominanceFrontierBase< BasicBlock, false >::DomSetType
std::set< BasicBlock * > DomSetType
Definition: DominanceFrontier.h:42
PassManager.h
llvm::DominanceFrontierBase::end
const_iterator end() const
Definition: DominanceFrontier.h:82
llvm::DominanceFrontierWrapperPass::ID
static char ID
Definition: DominanceFrontier.h:159
llvm::GraphTraits< BasicBlock * >
Definition: CFG.h:301
llvm::DominanceFrontier
Definition: DominanceFrontier.h:141
llvm::ForwardDominanceFrontierBase::calculate
const DomSetType & calculate(const DomTreeT &DT, const DomTreeNodeT *Node)
Definition: DominanceFrontierImpl.h:160
llvm::DominanceFrontierBase::begin
const_iterator begin() const
Definition: DominanceFrontier.h:80
llvm::SmallVectorImpl< BlockT * >
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::DominanceFrontierBase::isPostDominator
bool isPostDominator() const
isPostDominator - Returns true if analysis based of postdoms
Definition: DominanceFrontier.h:67
llvm::ForwardDominanceFrontierBase::analyze
void analyze(DomTreeT &DT)
Definition: DominanceFrontier.h:131
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::DominanceFrontierBase::removeFromFrontier
void removeFromFrontier(iterator I, BlockT *Node)
Definition: DominanceFrontierImpl.h:66
llvm::DominanceFrontierBase::DominanceFrontierBase
DominanceFrontierBase()=default
llvm::DominanceFrontierWrapperPass
Definition: DominanceFrontier.h:155
llvm::GraphTraits
Definition: GraphTraits.h:35
llvm::DominanceFrontierBase::find
iterator find(BlockT *B)
Definition: DominanceFrontier.h:83
llvm::DominanceFrontierBase< BasicBlock, false >::DomSetMapType
std::map< BasicBlock *, DomSetType > DomSetMapType
Definition: DominanceFrontier.h:43
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::DominanceFrontierBase::Frontiers
DomSetMapType Frontiers
Definition: DominanceFrontier.h:48
llvm::DominanceFrontierBase::addToFrontier
void addToFrontier(iterator I, BlockT *Node)
Definition: DominanceFrontierImpl.h:58
llvm::DominanceFrontierBase::begin
iterator begin()
Definition: DominanceFrontier.h:79