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
31namespace llvm {
32
33template <class BlockT>
34class DFCalculateWorkObject {
35public:
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
48template <class BlockT, bool IsPostDom>
49void 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
56template <class BlockT, bool IsPostDom>
57void 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
63template <class BlockT, bool IsPostDom>
64void 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
71template <class BlockT, bool IsPostDom>
72bool 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
96template <class BlockT, bool IsPostDom>
97bool 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(DS1&: I->second, DS2: 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
126template <class BlockT, bool IsPostDom>
127void 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)
150template <class BlockT, bool IsPostDom>
151void DominanceFrontierBase<BlockT, IsPostDom>::dump() const {
152 print(dbgs());
153}
154#endif
155
156template <class BlockT>
157const typename ForwardDominanceFrontierBase<BlockT>::DomSetType &
158ForwardDominanceFrontierBase<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