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