LLVM  6.0.0svn
DominanceFrontier.h
Go to the documentation of this file.
1 //===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the DominanceFrontier class, which calculate and holds the
11 // dominance frontier for a function.
12 //
13 // This should be considered deprecated, don't add any more uses of this data
14 // structure.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H
19 #define LLVM_ANALYSIS_DOMINANCEFRONTIER_H
20 
21 #include "llvm/ADT/GraphTraits.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 #include <vector>
30 
31 namespace llvm {
32 
33 class Function;
34 class raw_ostream;
35 
36 //===----------------------------------------------------------------------===//
37 /// DominanceFrontierBase - Common base class for computing forward and inverse
38 /// dominance frontiers for a function.
39 ///
40 template <class BlockT, bool IsPostDom>
42 public:
43  using DomSetType = std::set<BlockT *>; // Dom set for a bb
44  using DomSetMapType = std::map<BlockT *, DomSetType>; // Dom set map
45 
46 protected:
48 
50  // Postdominators can have multiple roots.
52  static constexpr bool IsPostDominators = IsPostDom;
53 
54 public:
55  DominanceFrontierBase() = default;
56 
57  /// getRoots - Return the root blocks of the current CFG. This may include
58  /// multiple blocks if we are computing post dominators. For forward
59  /// dominators, this will always be a single block (the entry node).
60  const SmallVectorImpl<BlockT *> &getRoots() const { return Roots; }
61 
62  BlockT *getRoot() const {
63  assert(Roots.size() == 1 && "Should always have entry node!");
64  return Roots[0];
65  }
66 
67  /// isPostDominator - Returns true if analysis based of postdoms
68  bool isPostDominator() const {
69  return IsPostDominators;
70  }
71 
72  void releaseMemory() {
73  Frontiers.clear();
74  }
75 
76  // Accessor interface:
77  using iterator = typename DomSetMapType::iterator;
78  using const_iterator = typename DomSetMapType::const_iterator;
79 
80  iterator begin() { return Frontiers.begin(); }
81  const_iterator begin() const { return Frontiers.begin(); }
82  iterator end() { return Frontiers.end(); }
83  const_iterator end() const { return Frontiers.end(); }
84  iterator find(BlockT *B) { return Frontiers.find(B); }
85  const_iterator find(BlockT *B) const { return Frontiers.find(B); }
86 
87  iterator addBasicBlock(BlockT *BB, const DomSetType &frontier) {
88  assert(find(BB) == end() && "Block already in DominanceFrontier!");
89  return Frontiers.insert(std::make_pair(BB, frontier)).first;
90  }
91 
92  /// removeBlock - Remove basic block BB's frontier.
93  void removeBlock(BlockT *BB);
94 
95  void addToFrontier(iterator I, BlockT *Node);
96 
97  void removeFromFrontier(iterator I, BlockT *Node);
98 
99  /// compareDomSet - Return false if two domsets match. Otherwise
100  /// return true;
101  bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const;
102 
103  /// compare - Return true if the other dominance frontier base matches
104  /// this dominance frontier base. Otherwise return false.
105  bool compare(DominanceFrontierBase &Other) const;
106 
107  /// print - Convert to human readable form
108  ///
109  void print(raw_ostream &OS) const;
110 
111  /// dump - Dump the dominance frontier to dbgs().
112 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
113  void dump() const;
114 #endif
115 };
116 
117 //===-------------------------------------
118 /// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
119 /// used to compute a forward dominator frontiers.
120 ///
121 template <class BlockT>
123  : public DominanceFrontierBase<BlockT, false> {
124 private:
126 
127 public:
131 
132  void analyze(DomTreeT &DT) {
133  assert(DT.getRoots().size() == 1 &&
134  "Only one entry block for forward domfronts!");
135  this->Roots = {DT.getRoot()};
136  calculate(DT, DT[this->Roots[0]]);
137  }
138 
139  const DomSetType &calculate(const DomTreeT &DT, const DomTreeNodeT *Node);
140 };
141 
143 public:
148  using const_iterator =
150 
151  /// Handle invalidation explicitly.
152  bool invalidate(Function &F, const PreservedAnalyses &PA,
154 };
155 
158 
159 public:
160  static char ID; // Pass ID, replacement for typeid
161 
163 
165  const DominanceFrontier &getDominanceFrontier() const { return DF; }
166 
167  void releaseMemory() override;
168 
169  bool runOnFunction(Function &) override;
170 
171  void getAnalysisUsage(AnalysisUsage &AU) const override;
172 
173  void print(raw_ostream &OS, const Module * = nullptr) const override;
174 
175  void dump() const;
176 };
177 
178 extern template class DominanceFrontierBase<BasicBlock, false>;
179 extern template class DominanceFrontierBase<BasicBlock, true>;
180 extern template class ForwardDominanceFrontierBase<BasicBlock>;
181 
182 /// \brief Analysis pass which computes a \c DominanceFrontier.
186 
187  static AnalysisKey Key;
188 
189 public:
190  /// \brief Provide the result type for this analysis pass.
192 
193  /// \brief Run the analysis pass over a function and produce a dominator tree.
195 };
196 
197 /// \brief Printer pass for the \c DominanceFrontier.
200  raw_ostream &OS;
201 
202 public:
204 
206 };
207 
208 } // end namespace llvm
209 
210 #endif // LLVM_ANALYSIS_DOMINANCEFRONTIER_H
DominanceFrontierBase< BasicBlock, false >::const_iterator const_iterator
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
void addToFrontier(iterator I, BlockT *Node)
const_iterator find(BlockT *B) const
Printer pass for the DominanceFrontier.
DominanceFrontierBase - Common base class for computing forward and inverse dominance frontiers for a...
F(f)
bool isPostDominator() const
isPostDominator - Returns true if analysis based of postdoms
typename DomSetMapType::const_iterator const_iterator
void print(raw_ostream &OS) const
print - Convert to human readable form
std::map< BasicBlock *, DomSetType > DomSetMapType
Analysis pass which computes a DominanceFrontier.
void dump() const
dump - Dump the dominance frontier to dbgs().
DominanceFrontierBase< BasicBlock, false >::DomSetType DomSetType
static constexpr bool IsPostDominators
const SmallVectorImpl< NodeT * > & getRoots() const
getRoots - Return the root blocks of the current CFG.
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:736
Key
PAL metadata keys.
const SmallVectorImpl< BlockT * > & getRoots() const
getRoots - Return the root blocks of the current CFG.
DominanceFrontierBase< BasicBlock, false >::iterator iterator
void removeFromFrontier(iterator I, BlockT *Node)
Core dominator tree base class.
Definition: LoopInfo.h:61
static bool runOnFunction(Function &F, bool PostInlining)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
bool compare(DominanceFrontierBase &Other) const
compare - Return true if the other dominance frontier base matches this dominance frontier base...
iterator addBasicBlock(BlockT *BB, const DomSetType &frontier)
SmallVector< BlockT *, IsPostDom ? 4 :1 > Roots
DominanceFrontier & getDominanceFrontier()
const DominanceFrontier & getDominanceFrontier() const
#define I(x, y, z)
Definition: MD5.cpp:58
void removeBlock(BlockT *BB)
removeBlock - Remove basic block BB&#39;s frontier.
const_iterator end() const
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:559
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
NodeT * getRoot() const
This file defines a set of templates that efficiently compute a dominator tree over a generic graph...
A container for analyses that lazily runs them and caches their results.
This header defines various interfaces for pass management in LLVM.
bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const
compareDomSet - Return false if two domsets match.
const_iterator begin() const
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is used to compute a forwar...