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