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
DFCalculateWorkObject(BlockT * B,BlockT * P,const DomTreeNodeT * N,const DomTreeNodeT * PN)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>
removeBlock(BlockT * BB)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>
addToFrontier(iterator I,BlockT * Node)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>
removeFromFrontier(iterator I,BlockT * Node)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>
compareDomSet(DomSetType & DS1,const DomSetType & DS2)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>
compare(DominanceFrontierBase<BlockT,IsPostDom> & Other)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>
print(raw_ostream & OS)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>
dump()152 void DominanceFrontierBase<BlockT, IsPostDom>::dump() const {
153 print(dbgs());
154 }
155 #endif
156
157 template <class BlockT>
158 const typename ForwardDominanceFrontierBase<BlockT>::DomSetType &
calculate(const DomTreeT & DT,const DomTreeNodeT * Node)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