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