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"
24#include "llvm/Support/GenericDomTree.h"
25#include <cassert>
26#include <map>
27#include <set>
28#include <utility>
29#include <vector>
30
31namespace llvm {
32
33class Function;
34class raw_ostream;
35
36//===----------------------------------------------------------------------===//
37/// DominanceFrontierBase - Common base class for computing forward and inverse
38/// dominance frontiers for a function.
39///
40template <class BlockT, bool IsPostDom>
41class DominanceFrontierBase {
42public:
43  using DomSetType = std::set<BlockT *>;                // Dom set for a bb
44  using DomSetMapType = std::map<BlockT *, DomSetType>; // Dom set map
45
46protected:
47  using BlockTraits = GraphTraits<BlockT *>;
48
49  DomSetMapType Frontiers;
50  // Postdominators can have multiple roots.
51  SmallVector<BlockT *, IsPostDom ? 4 : 1> Roots;
52  static constexpr bool IsPostDominators = IsPostDom;
53
54public:
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///
121template <class BlockT>
122class ForwardDominanceFrontierBase
123    : public DominanceFrontierBase<BlockT, false> {
124private:
125  using BlockTraits = GraphTraits<BlockT *>;
126
127public:
128  using DomTreeT = DomTreeBase<BlockT>;
129  using DomTreeNodeT = DomTreeNodeBase<BlockT>;
130  using DomSetType = typename DominanceFrontierBase<BlockT, false>::DomSetType;
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
142class DominanceFrontier : public ForwardDominanceFrontierBase<BasicBlock> {
143public:
144  using DomTreeT = DomTreeBase<BasicBlock>;
145  using DomTreeNodeT = DomTreeNodeBase<BasicBlock>;
146  using DomSetType = DominanceFrontierBase<BasicBlock, false>::DomSetType;
147  using iterator = DominanceFrontierBase<BasicBlock, false>::iterator;
148  using const_iterator =
149      DominanceFrontierBase<BasicBlock, false>::const_iterator;
150
151  /// Handle invalidation explicitly.
152  bool invalidate(Function &F, const PreservedAnalyses &PA,
153                  FunctionAnalysisManager::Invalidator &);
154};
155
156class DominanceFrontierWrapperPass : public FunctionPass {
157  DominanceFrontier DF;
158
159public:
160  static char ID; // Pass ID, replacement for typeid
161
162  DominanceFrontierWrapperPass();
163
164  DominanceFrontier &getDominanceFrontier() { return DF; }
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
178extern template class DominanceFrontierBase<BasicBlock, false>;
179extern template class DominanceFrontierBase<BasicBlock, true>;
180extern template class ForwardDominanceFrontierBase<BasicBlock>;
181
182/// \brief Analysis pass which computes a \c DominanceFrontier.
183class DominanceFrontierAnalysis
184    : public AnalysisInfoMixin<DominanceFrontierAnalysis> {
185  friend AnalysisInfoMixin<DominanceFrontierAnalysis>;
186
187  static AnalysisKey Key;
188
189public:
190  /// \brief Provide the result type for this analysis pass.
191  using Result = DominanceFrontier;
192
193  /// \brief Run the analysis pass over a function and produce a dominator tree.
194  DominanceFrontier run(Function &F, FunctionAnalysisManager &AM);
195};
196
197/// \brief Printer pass for the \c DominanceFrontier.
198class DominanceFrontierPrinterPass
199    : public PassInfoMixin<DominanceFrontierPrinterPass> {
200  raw_ostream &OS;
201
202public:
203  explicit DominanceFrontierPrinterPass(raw_ostream &OS);
204
205  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
206};
207
208} // end namespace llvm
209
210#endif // LLVM_ANALYSIS_DOMINANCEFRONTIER_H
211