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/IR/Dominators.h"
22#include "llvm/IR/PassManager.h"
23#include <map>
24#include <set>
25
26namespace llvm {
27
28//===----------------------------------------------------------------------===//
29/// DominanceFrontierBase - Common base class for computing forward and inverse
30/// dominance frontiers for a function.
31///
32template <class BlockT>
33class DominanceFrontierBase {
34public:
35  typedef std::set<BlockT *> DomSetType;                // Dom set for a bb
36  typedef std::map<BlockT *, DomSetType> DomSetMapType; // Dom set map
37
38protected:
39  typedef GraphTraits<BlockT *> BlockTraits;
40
41  DomSetMapType Frontiers;
42  std::vector<BlockT *> Roots;
43  const bool IsPostDominators;
44
45public:
46  DominanceFrontierBase(bool isPostDom) : IsPostDominators(isPostDom) {}
47
48  /// getRoots - Return the root blocks of the current CFG.  This may include
49  /// multiple blocks if we are computing post dominators.  For forward
50  /// dominators, this will always be a single block (the entry node).
51  ///
52  inline const std::vector<BlockT *> &getRoots() const {
53    return Roots;
54  }
55
56  BlockT *getRoot() const {
57    assert(Roots.size() == 1 && "Should always have entry node!");
58    return Roots[0];
59  }
60
61  /// isPostDominator - Returns true if analysis based of postdoms
62  ///
63  bool isPostDominator() const {
64    return IsPostDominators;
65  }
66
67  void releaseMemory() {
68    Frontiers.clear();
69  }
70
71  // Accessor interface:
72  typedef typename DomSetMapType::iterator iterator;
73  typedef typename DomSetMapType::const_iterator const_iterator;
74  iterator begin() { return Frontiers.begin(); }
75  const_iterator begin() const { return Frontiers.begin(); }
76  iterator end() { return Frontiers.end(); }
77  const_iterator end() const { return Frontiers.end(); }
78  iterator find(BlockT *B) { return Frontiers.find(B); }
79  const_iterator find(BlockT *B) const { return Frontiers.find(B); }
80
81  iterator addBasicBlock(BlockT *BB, const DomSetType &frontier) {
82    assert(find(BB) == end() && "Block already in DominanceFrontier!");
83    return Frontiers.insert(std::make_pair(BB, frontier)).first;
84  }
85
86  /// removeBlock - Remove basic block BB's frontier.
87  void removeBlock(BlockT *BB);
88
89  void addToFrontier(iterator I, BlockT *Node);
90
91  void removeFromFrontier(iterator I, BlockT *Node);
92
93  /// compareDomSet - Return false if two domsets match. Otherwise
94  /// return true;
95  bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const;
96
97  /// compare - Return true if the other dominance frontier base matches
98  /// this dominance frontier base. Otherwise return false.
99  bool compare(DominanceFrontierBase<BlockT> &Other) const;
100
101  /// print - Convert to human readable form
102  ///
103  void print(raw_ostream &OS) const;
104
105  /// dump - Dump the dominance frontier to dbgs().
106#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
107  void dump() const;
108#endif
109};
110
111//===-------------------------------------
112/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
113/// used to compute a forward dominator frontiers.
114///
115template <class BlockT>
116class ForwardDominanceFrontierBase : public DominanceFrontierBase<BlockT> {
117private:
118  typedef GraphTraits<BlockT *> BlockTraits;
119
120public:
121  typedef DominatorTreeBase<BlockT> DomTreeT;
122  typedef DomTreeNodeBase<BlockT> DomTreeNodeT;
123  typedef typename DominanceFrontierBase<BlockT>::DomSetType DomSetType;
124
125  ForwardDominanceFrontierBase() : DominanceFrontierBase<BlockT>(false) {}
126
127  void analyze(DomTreeT &DT) {
128    this->Roots = DT.getRoots();
129    assert(this->Roots.size() == 1 &&
130           "Only one entry block for forward domfronts!");
131    calculate(DT, DT[this->Roots[0]]);
132  }
133
134  const DomSetType &calculate(const DomTreeT &DT, const DomTreeNodeT *Node);
135};
136
137class DominanceFrontier : public ForwardDominanceFrontierBase<BasicBlock> {
138public:
139  typedef DominatorTreeBase<BasicBlock> DomTreeT;
140  typedef DomTreeNodeBase<BasicBlock> DomTreeNodeT;
141  typedef DominanceFrontierBase<BasicBlock>::DomSetType DomSetType;
142  typedef DominanceFrontierBase<BasicBlock>::iterator iterator;
143  typedef DominanceFrontierBase<BasicBlock>::const_iterator const_iterator;
144};
145
146class DominanceFrontierWrapperPass : public FunctionPass {
147  DominanceFrontier DF;
148public:
149  static char ID; // Pass ID, replacement for typeid
150
151  DominanceFrontierWrapperPass();
152
153  DominanceFrontier &getDominanceFrontier() { return DF; }
154  const DominanceFrontier &getDominanceFrontier() const { return DF;  }
155
156  void releaseMemory() override;
157
158  bool runOnFunction(Function &) override;
159
160  void getAnalysisUsage(AnalysisUsage &AU) const override;
161
162  void print(raw_ostream &OS, const Module * = nullptr) const override;
163
164  void dump() const;
165};
166
167extern template class DominanceFrontierBase<BasicBlock>;
168extern template class ForwardDominanceFrontierBase<BasicBlock>;
169
170/// \brief Analysis pass which computes a \c DominanceFrontier.
171class DominanceFrontierAnalysis
172    : public AnalysisInfoMixin<DominanceFrontierAnalysis> {
173  friend AnalysisInfoMixin<DominanceFrontierAnalysis>;
174  static char PassID;
175
176public:
177  /// \brief Provide the result typedef for this analysis pass.
178  typedef DominanceFrontier Result;
179
180  /// \brief Run the analysis pass over a function and produce a dominator tree.
181  DominanceFrontier run(Function &F, AnalysisManager<Function> &AM);
182};
183
184/// \brief Printer pass for the \c DominanceFrontier.
185class DominanceFrontierPrinterPass
186    : public PassInfoMixin<DominanceFrontierPrinterPass> {
187  raw_ostream &OS;
188
189public:
190  explicit DominanceFrontierPrinterPass(raw_ostream &OS);
191  PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM);
192};
193
194} // End llvm namespace
195
196#endif
197