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