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