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 #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>
41 class DominanceFrontierBase {
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:
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 
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).
getRoots()60   const SmallVectorImpl<BlockT *> &getRoots() const { return Roots; }
61 
getRoot()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
isPostDominator()68   bool isPostDominator() const {
69     return IsPostDominators;
70   }
71 
releaseMemory()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 
begin()80   iterator begin() { return Frontiers.begin(); }
begin()81   const_iterator begin() const { return Frontiers.begin(); }
end()82   iterator end() { return Frontiers.end(); }
end()83   const_iterator end() const { return Frontiers.end(); }
find(BlockT * B)84   iterator find(BlockT *B) { return Frontiers.find(B); }
find(BlockT * B)85   const_iterator find(BlockT *B) const { return Frontiers.find(B); }
86 
addBasicBlock(BlockT * BB,const DomSetType & frontier)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>
122 class ForwardDominanceFrontierBase
123     : public DominanceFrontierBase<BlockT, false> {
124 private:
125   using BlockTraits = GraphTraits<BlockT *>;
126 
127 public:
128   using DomTreeT = DomTreeBase<BlockT>;
129   using DomTreeNodeT = DomTreeNodeBase<BlockT>;
130   using DomSetType = typename DominanceFrontierBase<BlockT, false>::DomSetType;
131 
analyze(DomTreeT & DT)132   void analyze(DomTreeT &DT) {
133     assert(DT.root_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 
142 class DominanceFrontier : public ForwardDominanceFrontierBase<BasicBlock> {
143 public:
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 
156 class DominanceFrontierWrapperPass : public FunctionPass {
157   DominanceFrontier DF;
158 
159 public:
160   static char ID; // Pass ID, replacement for typeid
161 
162   DominanceFrontierWrapperPass();
163 
getDominanceFrontier()164   DominanceFrontier &getDominanceFrontier() { return DF; }
getDominanceFrontier()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 /// Analysis pass which computes a \c DominanceFrontier.
183 class DominanceFrontierAnalysis
184     : public AnalysisInfoMixin<DominanceFrontierAnalysis> {
185   friend AnalysisInfoMixin<DominanceFrontierAnalysis>;
186 
187   static AnalysisKey Key;
188 
189 public:
190   /// Provide the result type for this analysis pass.
191   using Result = DominanceFrontier;
192 
193   /// Run the analysis pass over a function and produce a dominator tree.
194   DominanceFrontier run(Function &F, FunctionAnalysisManager &AM);
195 };
196 
197 /// Printer pass for the \c DominanceFrontier.
198 class DominanceFrontierPrinterPass
199     : public PassInfoMixin<DominanceFrontierPrinterPass> {
200   raw_ostream &OS;
201 
202 public:
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