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 is the generic implementation of the DominanceFrontier class, which
10 // calculate and holds the dominance frontier for a function for.
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_DOMINANCEFRONTIERIMPL_H
18 #define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
19 
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/Analysis/DominanceFrontier.h"
22 #include "llvm/Config/llvm-config.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/GenericDomTree.h"
25 #include "llvm/Support/raw_ostream.h"
26 #include <cassert>
27 #include <set>
28 #include <utility>
29 #include <vector>
30 
31 namespace llvm {
32 
33 template <class BlockT>
34 class DFCalculateWorkObject {
35 public:
36   using DomTreeNodeT = DomTreeNodeBase<BlockT>;
37 
38   DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N,
39                         const DomTreeNodeT *PN)
40       : currentBB(B), parentBB(P), Node(N), parentNode(PN) {}
41 
42   BlockT *currentBB;
43   BlockT *parentBB;
44   const DomTreeNodeT *Node;
45   const DomTreeNodeT *parentNode;
46 };
47 
48 template <class BlockT, bool IsPostDom>
49 void DominanceFrontierBase<BlockT, IsPostDom>::removeBlock(BlockT *BB) {
50   assert(find(BB) != end() && "Block is not in DominanceFrontier!");
51   for (iterator I = begin(), E = end(); I != E; ++I)
52     I->second.erase(BB);
53   Frontiers.erase(BB);
54 }
55 
56 template <class BlockT, bool IsPostDom>
57 void DominanceFrontierBase<BlockT, IsPostDom>::addToFrontier(iterator I,
58                                                              BlockT *Node) {
59   assert(I != end() && "BB is not in DominanceFrontier!");
60   assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
61   I->second.erase(Node);
62 }
63 
64 template <class BlockT, bool IsPostDom>
65 void DominanceFrontierBase<BlockT, IsPostDom>::removeFromFrontier(
66     iterator I, BlockT *Node) {
67   assert(I != end() && "BB is not in DominanceFrontier!");
68   assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
69   I->second.erase(Node);
70 }
71 
72 template <class BlockT, bool IsPostDom>
73 bool DominanceFrontierBase<BlockT, IsPostDom>::compareDomSet(
74     DomSetType &DS1, const DomSetType &DS2) const {
75   std::set<BlockT *> tmpSet;
76   for (BlockT *BB : DS2)
77     tmpSet.insert(BB);
78 
79   for (typename DomSetType::const_iterator I = DS1.begin(), E = DS1.end();
80        I != E;) {
81     BlockT *Node = *I++;
82 
83     if (tmpSet.erase(Node) == 0)
84       // Node is in DS1 but tnot in DS2.
85       return true;
86   }
87 
88   if (!tmpSet.empty()) {
89     // There are nodes that are in DS2 but not in DS1.
90     return true;
91   }
92 
93   // DS1 and DS2 matches.
94   return false;
95 }
96 
97 template <class BlockT, bool IsPostDom>
98 bool DominanceFrontierBase<BlockT, IsPostDom>::compare(
99     DominanceFrontierBase<BlockT, IsPostDom> &Other) const {
100   DomSetMapType tmpFrontiers;
101   for (typename DomSetMapType::const_iterator I = Other.begin(),
102                                               E = Other.end();
103        I != E; ++I)
104     tmpFrontiers.insert(std::make_pair(I->first, I->second));
105 
106   for (typename DomSetMapType::iterator I = tmpFrontiers.begin(),
107                                         E = tmpFrontiers.end();
108        I != E;) {
109     BlockT *Node = I->first;
110     const_iterator DFI = find(Node);
111     if (DFI == end())
112       return true;
113 
114     if (compareDomSet(I->second, DFI->second))
115       return true;
116 
117     ++I;
118     tmpFrontiers.erase(Node);
119   }
120 
121   if (!tmpFrontiers.empty())
122     return true;
123 
124   return false;
125 }
126 
127 template <class BlockT, bool IsPostDom>
128 void DominanceFrontierBase<BlockT, IsPostDom>::print(raw_ostream &OS) const {
129   for (const_iterator I = begin(), E = end(); I != E; ++I) {
130     OS << "  DomFrontier for BB ";
131     if (I->first)
132       I->first->printAsOperand(OS, false);
133     else
134       OS << " <<exit node>>";
135     OS << " is:\t";
136 
137     const std::set<BlockT *> &BBs = I->second;
138 
139     for (const BlockT *BB : BBs) {
140       OS << ' ';
141       if (BB)
142         BB->printAsOperand(OS, false);
143       else
144         OS << "<<exit node>>";
145     }
146     OS << '\n';
147   }
148 }
149 
150 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
151 template <class BlockT, bool IsPostDom>
152 void DominanceFrontierBase<BlockT, IsPostDom>::dump() const {
153   print(dbgs());
154 }
155 #endif
156 
157 template <class BlockT>
158 const typename ForwardDominanceFrontierBase<BlockT>::DomSetType &
159 ForwardDominanceFrontierBase<BlockT>::calculate(const DomTreeT &DT,
160                                                 const DomTreeNodeT *Node) {
161   BlockT *BB = Node->getBlock();
162   DomSetType *Result = nullptr;
163 
164   std::vector<DFCalculateWorkObject<BlockT>> workList;
165   SmallPtrSet<BlockT *, 32> visited;
166 
167   workList.push_back(DFCalculateWorkObject<BlockT>(BB, nullptr, Node, nullptr));
168   do {
169     DFCalculateWorkObject<BlockT> *currentW = &workList.back();
170     assert(currentW && "Missing work object.");
171 
172     BlockT *currentBB = currentW->currentBB;
173     BlockT *parentBB = currentW->parentBB;
174     const DomTreeNodeT *currentNode = currentW->Node;
175     const DomTreeNodeT *parentNode = currentW->parentNode;
176     assert(currentBB && "Invalid work object. Missing current Basic Block");
177     assert(currentNode && "Invalid work object. Missing current Node");
178     DomSetType &S = this->Frontiers[currentBB];
179 
180     // Visit each block only once.
181     if (visited.insert(currentBB).second) {
182       // Loop over CFG successors to calculate DFlocal[currentNode]
183       for (const auto Succ : children<BlockT *>(currentBB)) {
184         // Does Node immediately dominate this successor?
185         if (DT[Succ]->getIDom() != currentNode)
186           S.insert(Succ);
187       }
188     }
189 
190     // At this point, S is DFlocal.  Now we union in DFup's of our children...
191     // Loop through and visit the nodes that Node immediately dominates (Node's
192     // children in the IDomTree)
193     bool visitChild = false;
194     for (typename DomTreeNodeT::const_iterator NI = currentNode->begin(),
195                                                NE = currentNode->end();
196          NI != NE; ++NI) {
197       DomTreeNodeT *IDominee = *NI;
198       BlockT *childBB = IDominee->getBlock();
199       if (visited.count(childBB) == 0) {
200         workList.push_back(DFCalculateWorkObject<BlockT>(
201             childBB, currentBB, IDominee, currentNode));
202         visitChild = true;
203       }
204     }
205 
206     // If all children are visited or there is any child then pop this block
207     // from the workList.
208     if (!visitChild) {
209       if (!parentBB) {
210         Result = &S;
211         break;
212       }
213 
214       typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
215       DomSetType &parentSet = this->Frontiers[parentBB];
216       for (; CDFI != CDFE; ++CDFI) {
217         if (!DT.properlyDominates(parentNode, DT[*CDFI]))
218           parentSet.insert(*CDFI);
219       }
220       workList.pop_back();
221     }
222 
223   } while (!workList.empty());
224 
225   return *Result;
226 }
227 
228 } // end namespace llvm
229 
230 #endif // LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
231