Line data Source code
1 : //===- SSAUpdaterImpl.h - SSA Updater Implementation ------------*- 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 file provides a template that implements the core algorithm for the
11 : // SSAUpdater and MachineSSAUpdater.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
16 : #define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
17 :
18 : #include "llvm/ADT/DenseMap.h"
19 : #include "llvm/ADT/SmallVector.h"
20 : #include "llvm/Support/Allocator.h"
21 : #include "llvm/Support/Debug.h"
22 : #include "llvm/Support/raw_ostream.h"
23 :
24 : #define DEBUG_TYPE "ssaupdater"
25 :
26 : namespace llvm {
27 :
28 : template<typename T> class SSAUpdaterTraits;
29 :
30 : template<typename UpdaterT>
31 25607 : class SSAUpdaterImpl {
32 : private:
33 : UpdaterT *Updater;
34 :
35 : using Traits = SSAUpdaterTraits<UpdaterT>;
36 : using BlkT = typename Traits::BlkT;
37 : using ValT = typename Traits::ValT;
38 : using PhiT = typename Traits::PhiT;
39 :
40 : /// BBInfo - Per-basic block information used internally by SSAUpdaterImpl.
41 : /// The predecessors of each block are cached here since pred_iterator is
42 : /// slow and we need to iterate over the blocks at least a few times.
43 : class BBInfo {
44 : public:
45 : // Back-pointer to the corresponding block.
46 : BlkT *BB;
47 :
48 : // Value to use in this block.
49 : ValT AvailableVal;
50 :
51 : // Block that defines the available value.
52 : BBInfo *DefBB;
53 :
54 : // Postorder number.
55 : int BlkNum = 0;
56 :
57 : // Immediate dominator.
58 : BBInfo *IDom = nullptr;
59 :
60 : // Number of predecessor blocks.
61 : unsigned NumPreds = 0;
62 :
63 : // Array[NumPreds] of predecessor blocks.
64 : BBInfo **Preds = nullptr;
65 :
66 : // Marker for existing PHIs that match.
67 : PhiT *PHITag = nullptr;
68 :
69 179370 : BBInfo(BlkT *ThisBB, ValT V)
70 25607 : : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr) {}
71 : };
72 :
73 : using AvailableValsTy = DenseMap<BlkT *, ValT>;
74 :
75 : AvailableValsTy *AvailableVals;
76 :
77 : SmallVectorImpl<PhiT *> *InsertedPHIs;
78 :
79 : using BlockListTy = SmallVectorImpl<BBInfo *>;
80 : using BBMapTy = DenseMap<BlkT *, BBInfo *>;
81 :
82 : BBMapTy BBMap;
83 : BumpPtrAllocator Allocator;
84 :
85 : public:
86 25607 : explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A,
87 : SmallVectorImpl<PhiT *> *Ins) :
88 25607 : Updater(U), AvailableVals(A), InsertedPHIs(Ins) {}
89 :
90 : /// GetValue - Check to see if AvailableVals has an entry for the specified
91 : /// BB and if so, return it. If not, construct SSA form by first
92 : /// calculating the required placement of PHIs and then inserting new PHIs
93 : /// where needed.
94 25607 : ValT GetValue(BlkT *BB) {
95 : SmallVector<BBInfo *, 100> BlockList;
96 25607 : BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList);
97 :
98 : // Special case: bail out if BB is unreachable.
99 25607 : if (BlockList.size() == 0) {
100 6 : ValT V = Traits::GetUndefVal(BB, Updater);
101 6 : (*AvailableVals)[BB] = V;
102 6 : return V;
103 : }
104 :
105 25601 : FindDominators(&BlockList, PseudoEntry);
106 25601 : FindPHIPlacement(&BlockList);
107 25601 : FindAvailableVals(&BlockList);
108 :
109 25601 : return BBMap[BB]->DefBB->AvailableVal;
110 : }
111 :
112 : /// BuildBlockList - Starting from the specified basic block, traverse back
113 : /// through its predecessors until reaching blocks with known values.
114 : /// Create BBInfo structures for the blocks and append them to the block
115 : /// list.
116 25607 : BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) {
117 : SmallVector<BBInfo *, 10> RootList;
118 : SmallVector<BBInfo *, 64> WorkList;
119 :
120 25607 : BBInfo *Info = new (Allocator) BBInfo(BB, 0);
121 25607 : BBMap[BB] = Info;
122 25607 : WorkList.push_back(Info);
123 :
124 : // Search backward from BB, creating BBInfos along the way and stopping
125 : // when reaching blocks that define the value. Record those defining
126 : // blocks on the RootList.
127 : SmallVector<BlkT *, 10> Preds;
128 130585 : while (!WorkList.empty()) {
129 104978 : Info = WorkList.pop_back_val();
130 : Preds.clear();
131 104978 : Traits::FindPredecessorBlocks(Info->BB, &Preds);
132 104978 : Info->NumPreds = Preds.size();
133 104978 : if (Info->NumPreds == 0)
134 13 : Info->Preds = nullptr;
135 : else
136 104965 : Info->Preds = static_cast<BBInfo **>(Allocator.Allocate(
137 : Info->NumPreds * sizeof(BBInfo *), alignof(BBInfo *)));
138 :
139 261312 : for (unsigned p = 0; p != Info->NumPreds; ++p) {
140 156334 : BlkT *Pred = Preds[p];
141 : // Check if BBMap already has a BBInfo for the predecessor block.
142 156334 : typename BBMapTy::value_type &BBMapBucket =
143 : BBMap.FindAndConstruct(Pred);
144 156334 : if (BBMapBucket.second) {
145 28178 : Info->Preds[p] = BBMapBucket.second;
146 76963 : continue;
147 : }
148 :
149 : // Create a new BBInfo for the predecessor.
150 256312 : ValT PredVal = AvailableVals->lookup(Pred);
151 128156 : BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal);
152 128156 : BBMapBucket.second = PredInfo;
153 128156 : Info->Preds[p] = PredInfo;
154 :
155 128156 : if (PredInfo->AvailableVal) {
156 48785 : RootList.push_back(PredInfo);
157 48785 : continue;
158 : }
159 79371 : WorkList.push_back(PredInfo);
160 : }
161 : }
162 :
163 : // Now that we know what blocks are backwards-reachable from the starting
164 : // block, do a forward depth-first traversal to assign postorder numbers
165 : // to those blocks.
166 : BBInfo *PseudoEntry = new (Allocator) BBInfo(nullptr, 0);
167 : unsigned BlkNum = 1;
168 :
169 : // Initialize the worklist with the roots from the backward traversal.
170 74392 : while (!RootList.empty()) {
171 48785 : Info = RootList.pop_back_val();
172 48785 : Info->IDom = PseudoEntry;
173 48785 : Info->BlkNum = -1;
174 48785 : WorkList.push_back(Info);
175 : }
176 :
177 333107 : while (!WorkList.empty()) {
178 307500 : Info = WorkList.back();
179 :
180 307500 : if (Info->BlkNum == -2) {
181 : // All the successors have been handled; assign the postorder number.
182 153750 : Info->BlkNum = BlkNum++;
183 : // If not a root, put it on the BlockList.
184 153750 : if (!Info->AvailableVal)
185 104965 : BlockList->push_back(Info);
186 : WorkList.pop_back();
187 153750 : continue;
188 : }
189 :
190 : // Leave this entry on the worklist, but set its BlkNum to mark that its
191 : // successors have been put on the worklist. When it returns to the top
192 : // the list, after handling its successors, it will be assigned a
193 : // number.
194 153750 : Info->BlkNum = -2;
195 :
196 : // Add unvisited successors to the work list.
197 : for (typename Traits::BlkSucc_iterator SI =
198 153750 : Traits::BlkSucc_begin(Info->BB),
199 390360 : E = Traits::BlkSucc_end(Info->BB); SI != E; ++SI) {
200 236610 : BBInfo *SuccInfo = BBMap[*SI];
201 236610 : if (!SuccInfo || SuccInfo->BlkNum)
202 131645 : continue;
203 104965 : SuccInfo->BlkNum = -1;
204 104965 : WorkList.push_back(SuccInfo);
205 : }
206 : }
207 25607 : PseudoEntry->BlkNum = BlkNum;
208 25607 : return PseudoEntry;
209 : }
210 :
211 : /// IntersectDominators - This is the dataflow lattice "meet" operation for
212 : /// finding dominators. Given two basic blocks, it walks up the dominator
213 : /// tree until it finds a common dominator of both. It uses the postorder
214 : /// number of the blocks to determine how to do that.
215 0 : BBInfo *IntersectDominators(BBInfo *Blk1, BBInfo *Blk2) {
216 212389 : while (Blk1 != Blk2) {
217 223447 : while (Blk1->BlkNum < Blk2->BlkNum) {
218 109982 : Blk1 = Blk1->IDom;
219 109982 : if (!Blk1)
220 0 : return Blk2;
221 : }
222 220992 : while (Blk2->BlkNum < Blk1->BlkNum) {
223 111988 : Blk2 = Blk2->IDom;
224 111988 : if (!Blk2)
225 0 : return Blk1;
226 : }
227 : }
228 : return Blk1;
229 : }
230 :
231 : /// FindDominators - Calculate the dominator tree for the subset of the CFG
232 : /// corresponding to the basic blocks on the BlockList. This uses the
233 : /// algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper, Harvey
234 : /// and Kennedy, published in Software--Practice and Experience, 2001,
235 : /// 4:1-10. Because the CFG subset does not include any edges leading into
236 : /// blocks that define the value, the results are not the usual dominator
237 : /// tree. The CFG subset has a single pseudo-entry node with edges to a set
238 : /// of root nodes for blocks that define the value. The dominators for this
239 : /// subset CFG are not the standard dominators but they are adequate for
240 : /// placing PHIs within the subset CFG.
241 25601 : void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) {
242 : bool Changed;
243 51399 : do {
244 : Changed = false;
245 : // Iterate over the list in reverse order, i.e., forward on CFG edges.
246 : for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
247 262416 : E = BlockList->rend(); I != E; ++I) {
248 211017 : BBInfo *Info = *I;
249 : BBInfo *NewIDom = nullptr;
250 :
251 : // Iterate through the block's predecessors.
252 525419 : for (unsigned p = 0; p != Info->NumPreds; ++p) {
253 314402 : BBInfo *Pred = Info->Preds[p];
254 :
255 : // Treat an unreachable predecessor as a definition with 'undef'.
256 314402 : if (Pred->BlkNum == 0) {
257 7 : Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater);
258 7 : (*AvailableVals)[Pred->BB] = Pred->AvailableVal;
259 7 : Pred->DefBB = Pred;
260 7 : Pred->BlkNum = PseudoEntry->BlkNum;
261 7 : PseudoEntry->BlkNum++;
262 : }
263 :
264 314402 : if (!NewIDom)
265 : NewIDom = Pred;
266 : else
267 : NewIDom = IntersectDominators(NewIDom, Pred);
268 : }
269 :
270 : // Check if the IDom value has changed.
271 211017 : if (NewIDom && NewIDom != Info->IDom) {
272 105178 : Info->IDom = NewIDom;
273 : Changed = true;
274 : }
275 : }
276 : } while (Changed);
277 25601 : }
278 :
279 : /// IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for
280 : /// any blocks containing definitions of the value. If one is found, then
281 : /// the successor of Pred is in the dominance frontier for the definition,
282 : /// and this function returns true.
283 0 : bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom) {
284 374793 : for (; Pred != IDom; Pred = Pred->IDom) {
285 156994 : if (Pred->DefBB == Pred)
286 0 : return true;
287 : }
288 : return false;
289 : }
290 :
291 : /// FindPHIPlacement - PHIs are needed in the iterated dominance frontiers
292 : /// of the known definitions. Iteratively add PHIs in the dom frontiers
293 : /// until nothing changes. Along the way, keep track of the nearest
294 : /// dominating definitions for non-PHI blocks.
295 25601 : void FindPHIPlacement(BlockListTy *BlockList) {
296 : bool Changed;
297 51202 : do {
298 : Changed = false;
299 : // Iterate over the list in reverse order, i.e., forward on CFG edges.
300 : for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
301 261132 : E = BlockList->rend(); I != E; ++I) {
302 209930 : BBInfo *Info = *I;
303 :
304 : // If this block already needs a PHI, there is nothing to do here.
305 209930 : if (Info->DefBB == Info)
306 : continue;
307 :
308 : // Default to use the same def as the immediate dominator.
309 187421 : BBInfo *NewDefBB = Info->IDom->DefBB;
310 405220 : for (unsigned p = 0; p != Info->NumPreds; ++p) {
311 480616 : if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) {
312 : // Need a PHI here.
313 : NewDefBB = Info;
314 : break;
315 : }
316 : }
317 :
318 : // Check if anything changed.
319 187421 : if (NewDefBB != Info->DefBB) {
320 104965 : Info->DefBB = NewDefBB;
321 : Changed = true;
322 : }
323 : }
324 : } while (Changed);
325 25601 : }
326 :
327 : /// FindAvailableVal - If this block requires a PHI, first check if an
328 : /// existing PHI matches the PHI placement and reaching definitions computed
329 : /// earlier, and if not, create a new PHI. Visit all the block's
330 : /// predecessors to calculate the available value for each one and fill in
331 : /// the incoming values for a new PHI.
332 25601 : void FindAvailableVals(BlockListTy *BlockList) {
333 : // Go through the worklist in forward order (i.e., backward through the CFG)
334 : // and check if existing PHIs can be used. If not, create empty PHIs where
335 : // they are needed.
336 104965 : for (typename BlockListTy::iterator I = BlockList->begin(),
337 130566 : E = BlockList->end(); I != E; ++I) {
338 104965 : BBInfo *Info = *I;
339 : // Check if there needs to be a PHI in BB.
340 104965 : if (Info->DefBB != Info)
341 : continue;
342 :
343 : // Look for an existing PHI.
344 22509 : FindExistingPHI(Info->BB, BlockList);
345 22509 : if (Info->AvailableVal)
346 : continue;
347 :
348 22118 : ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater);
349 22118 : Info->AvailableVal = PHI;
350 22118 : (*AvailableVals)[Info->BB] = PHI;
351 : }
352 :
353 : // Now go back through the worklist in reverse order to fill in the
354 : // arguments for any new PHIs added in the forward traversal.
355 : for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
356 130566 : E = BlockList->rend(); I != E; ++I) {
357 104965 : BBInfo *Info = *I;
358 :
359 104965 : if (Info->DefBB != Info) {
360 : // Record the available value to speed up subsequent uses of this
361 : // SSAUpdater for the same value.
362 82456 : (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal;
363 82847 : continue;
364 : }
365 :
366 : // Check if this block contains a newly added PHI.
367 22509 : PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater);
368 22509 : if (!PHI)
369 : continue;
370 :
371 : // Iterate through the block's predecessors.
372 68664 : for (unsigned p = 0; p != Info->NumPreds; ++p) {
373 46546 : BBInfo *PredInfo = Info->Preds[p];
374 46546 : BlkT *Pred = PredInfo->BB;
375 : // Skip to the nearest preceding definition.
376 46546 : if (PredInfo->DefBB != PredInfo)
377 : PredInfo = PredInfo->DefBB;
378 46546 : Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred);
379 : }
380 :
381 : LLVM_DEBUG(dbgs() << " Inserted PHI: " << *PHI << "\n");
382 :
383 : // If the client wants to know about all new instructions, tell it.
384 22118 : if (InsertedPHIs) InsertedPHIs->push_back(PHI);
385 : }
386 25601 : }
387 :
388 : /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
389 : /// them match what is needed.
390 22509 : void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) {
391 173190 : for (auto &SomePHI : BB->phis()) {
392 128606 : if (CheckIfPHIMatches(&SomePHI)) {
393 391 : RecordMatchingPHIs(BlockList);
394 391 : break;
395 : }
396 : // Match failed: clear all the PHITag values.
397 1011981 : for (typename BlockListTy::iterator I = BlockList->begin(),
398 1140196 : E = BlockList->end(); I != E; ++I)
399 1011981 : (*I)->PHITag = nullptr;
400 : }
401 22509 : }
402 :
403 : /// CheckIfPHIMatches - Check if a PHI node matches the placement and values
404 : /// in the BBMap.
405 128606 : bool CheckIfPHIMatches(PhiT *PHI) {
406 : SmallVector<PhiT *, 20> WorkList;
407 128606 : WorkList.push_back(PHI);
408 :
409 : // Mark that the block containing this PHI has been visited.
410 128606 : BBMap[PHI->getParent()]->PHITag = PHI;
411 :
412 130473 : while (!WorkList.empty()) {
413 130082 : PHI = WorkList.pop_back_val();
414 :
415 : // Iterate through the PHI's incoming values.
416 : for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),
417 149259 : E = Traits::PHI_end(PHI); I != E; ++I) {
418 : ValT IncomingVal = I.getIncomingValue();
419 147392 : BBInfo *PredInfo = BBMap[I.getIncomingBlock()];
420 : // Skip to the nearest preceding definition.
421 147392 : if (PredInfo->DefBB != PredInfo)
422 : PredInfo = PredInfo->DefBB;
423 :
424 : // Check if it matches the expected value.
425 147392 : if (PredInfo->AvailableVal) {
426 124480 : if (IncomingVal == PredInfo->AvailableVal)
427 1517 : continue;
428 128215 : return false;
429 : }
430 :
431 : // Check if the value is a PHI in the correct block.
432 22912 : PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);
433 22912 : if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB)
434 : return false;
435 :
436 : // If this block has already been visited, check if this PHI matches.
437 17708 : if (PredInfo->PHITag) {
438 48 : if (IncomingPHIVal == PredInfo->PHITag)
439 : continue;
440 : return false;
441 : }
442 17660 : PredInfo->PHITag = IncomingPHIVal;
443 :
444 17660 : WorkList.push_back(IncomingPHIVal);
445 : }
446 : }
447 : return true;
448 : }
449 :
450 : /// RecordMatchingPHIs - For each PHI node that matches, record it in both
451 : /// the BBMap and the AvailableVals mapping.
452 391 : void RecordMatchingPHIs(BlockListTy *BlockList) {
453 2510 : for (typename BlockListTy::iterator I = BlockList->begin(),
454 2901 : E = BlockList->end(); I != E; ++I)
455 2510 : if (PhiT *PHI = (*I)->PHITag) {
456 560 : BlkT *BB = PHI->getParent();
457 : ValT PHIVal = Traits::GetPHIValue(PHI);
458 560 : (*AvailableVals)[BB] = PHIVal;
459 560 : BBMap[BB]->AvailableVal = PHIVal;
460 : }
461 391 : }
462 : };
463 :
464 : } // end namespace llvm
465 :
466 : #undef DEBUG_TYPE // "ssaupdater"
467 :
468 : #endif // LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
|
