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