1 //===- SSAUpdaterImpl.h - SSA Updater Implementation ------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file provides a template that implements the core algorithm for the
10 // SSAUpdater and MachineSSAUpdater.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
15 #define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
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"
23 #define DEBUG_TYPE "ssaupdater"
27 template<typename T
> class SSAUpdaterTraits
;
29 template<typename UpdaterT
>
30 class SSAUpdaterImpl
{
34 using Traits
= SSAUpdaterTraits
<UpdaterT
>;
35 using BlkT
= typename
Traits::BlkT
;
36 using ValT
= typename
Traits::ValT
;
37 using PhiT
= typename
Traits::PhiT
;
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.
44 // Back-pointer to the corresponding block.
47 // Value to use in this block.
50 // Block that defines the available value.
56 // Immediate dominator.
57 BBInfo
*IDom
= nullptr;
59 // Number of predecessor blocks.
60 unsigned NumPreds
= 0;
62 // Array[NumPreds] of predecessor blocks.
63 BBInfo
**Preds
= nullptr;
65 // Marker for existing PHIs that match.
66 PhiT
*PHITag
= nullptr;
68 BBInfo(BlkT
*ThisBB
, ValT V
)
69 : BB(ThisBB
), AvailableVal(V
), DefBB(V
? this : nullptr) {}
72 using AvailableValsTy
= DenseMap
<BlkT
*, ValT
>;
74 AvailableValsTy
*AvailableVals
;
76 SmallVectorImpl
<PhiT
*> *InsertedPHIs
;
78 using BlockListTy
= SmallVectorImpl
<BBInfo
*>;
79 using BBMapTy
= DenseMap
<BlkT
*, BBInfo
*>;
82 BumpPtrAllocator Allocator
;
85 explicit SSAUpdaterImpl(UpdaterT
*U
, AvailableValsTy
*A
,
86 SmallVectorImpl
<PhiT
*> *Ins
) :
87 Updater(U
), AvailableVals(A
), InsertedPHIs(Ins
) {}
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
93 ValT
GetValue(BlkT
*BB
) {
94 SmallVector
<BBInfo
*, 100> BlockList
;
95 BBInfo
*PseudoEntry
= BuildBlockList(BB
, &BlockList
);
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
;
104 FindDominators(&BlockList
, PseudoEntry
);
105 FindPHIPlacement(&BlockList
);
106 FindAvailableVals(&BlockList
);
108 return BBMap
[BB
]->DefBB
->AvailableVal
;
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
115 BBInfo
*BuildBlockList(BlkT
*BB
, BlockListTy
*BlockList
) {
116 SmallVector
<BBInfo
*, 10> RootList
;
117 SmallVector
<BBInfo
*, 64> WorkList
;
119 BBInfo
*Info
= new (Allocator
) BBInfo(BB
, 0);
121 WorkList
.push_back(Info
);
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();
130 Traits::FindPredecessorBlocks(Info
->BB
, &Preds
);
131 Info
->NumPreds
= Preds
.size();
132 if (Info
->NumPreds
== 0)
133 Info
->Preds
= nullptr;
135 Info
->Preds
= static_cast<BBInfo
**>(Allocator
.Allocate(
136 Info
->NumPreds
* sizeof(BBInfo
*), alignof(BBInfo
*)));
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
;
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
;
154 if (PredInfo
->AvailableVal
) {
155 RootList
.push_back(PredInfo
);
158 WorkList
.push_back(PredInfo
);
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
165 BBInfo
*PseudoEntry
= new (Allocator
) BBInfo(nullptr, 0);
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
;
173 WorkList
.push_back(Info
);
176 while (!WorkList
.empty()) {
177 Info
= WorkList
.back();
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
);
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
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
)
202 SuccInfo
->BlkNum
= -1;
203 WorkList
.push_back(SuccInfo
);
206 PseudoEntry
->BlkNum
= BlkNum
;
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
) {
221 while (Blk2
->BlkNum
< Blk1
->BlkNum
) {
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
) {
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
) {
248 BBInfo
*NewIDom
= nullptr;
250 // Iterate through the block's predecessors.
251 for (unsigned p
= 0; p
!= Info
->NumPreds
; ++p
) {
252 BBInfo
*Pred
= Info
->Preds
[p
];
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
;
259 Pred
->BlkNum
= PseudoEntry
->BlkNum
;
260 PseudoEntry
->BlkNum
++;
266 NewIDom
= IntersectDominators(NewIDom
, Pred
);
269 // Check if the IDom value has changed.
270 if (NewIDom
&& NewIDom
!= Info
->IDom
) {
271 Info
->IDom
= NewIDom
;
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
)
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
) {
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
) {
303 // If this block already needs a PHI, there is nothing to do here.
304 if (Info
->DefBB
== Info
)
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(Info
->Preds
[p
], Info
->IDom
)) {
317 // Check if anything changed.
318 if (NewDefBB
!= Info
->DefBB
) {
319 Info
->DefBB
= NewDefBB
;
326 /// FindAvailableVal - If this block requires a PHI, first check if an
327 /// existing PHI matches the PHI placement and reaching definitions computed
328 /// earlier, and if not, create a new PHI. Visit all the block's
329 /// predecessors to calculate the available value for each one and fill in
330 /// the incoming values for a new PHI.
331 void FindAvailableVals(BlockListTy
*BlockList
) {
332 // Go through the worklist in forward order (i.e., backward through the CFG)
333 // and check if existing PHIs can be used. If not, create empty PHIs where
335 for (typename
BlockListTy::iterator I
= BlockList
->begin(),
336 E
= BlockList
->end(); I
!= E
; ++I
) {
338 // Check if there needs to be a PHI in BB.
339 if (Info
->DefBB
!= Info
)
342 // Look for an existing PHI.
343 FindExistingPHI(Info
->BB
, BlockList
);
344 if (Info
->AvailableVal
)
347 ValT PHI
= Traits::CreateEmptyPHI(Info
->BB
, Info
->NumPreds
, Updater
);
348 Info
->AvailableVal
= PHI
;
349 (*AvailableVals
)[Info
->BB
] = PHI
;
352 // Now go back through the worklist in reverse order to fill in the
353 // arguments for any new PHIs added in the forward traversal.
354 for (typename
BlockListTy::reverse_iterator I
= BlockList
->rbegin(),
355 E
= BlockList
->rend(); I
!= E
; ++I
) {
358 if (Info
->DefBB
!= Info
) {
359 // Record the available value to speed up subsequent uses of this
360 // SSAUpdater for the same value.
361 (*AvailableVals
)[Info
->BB
] = Info
->DefBB
->AvailableVal
;
365 // Check if this block contains a newly added PHI.
366 PhiT
*PHI
= Traits::ValueIsNewPHI(Info
->AvailableVal
, Updater
);
370 // Iterate through the block's predecessors.
371 for (unsigned p
= 0; p
!= Info
->NumPreds
; ++p
) {
372 BBInfo
*PredInfo
= Info
->Preds
[p
];
373 BlkT
*Pred
= PredInfo
->BB
;
374 // Skip to the nearest preceding definition.
375 if (PredInfo
->DefBB
!= PredInfo
)
376 PredInfo
= PredInfo
->DefBB
;
377 Traits::AddPHIOperand(PHI
, PredInfo
->AvailableVal
, Pred
);
380 LLVM_DEBUG(dbgs() << " Inserted PHI: " << *PHI
<< "\n");
382 // If the client wants to know about all new instructions, tell it.
383 if (InsertedPHIs
) InsertedPHIs
->push_back(PHI
);
387 /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
388 /// them match what is needed.
389 void FindExistingPHI(BlkT
*BB
, BlockListTy
*BlockList
) {
390 for (auto &SomePHI
: BB
->phis()) {
391 if (CheckIfPHIMatches(&SomePHI
)) {
392 RecordMatchingPHIs(BlockList
);
395 // Match failed: clear all the PHITag values.
396 for (typename
BlockListTy::iterator I
= BlockList
->begin(),
397 E
= BlockList
->end(); I
!= E
; ++I
)
398 (*I
)->PHITag
= nullptr;
402 /// CheckIfPHIMatches - Check if a PHI node matches the placement and values
404 bool CheckIfPHIMatches(PhiT
*PHI
) {
405 SmallVector
<PhiT
*, 20> WorkList
;
406 WorkList
.push_back(PHI
);
408 // Mark that the block containing this PHI has been visited.
409 BBMap
[PHI
->getParent()]->PHITag
= PHI
;
411 while (!WorkList
.empty()) {
412 PHI
= WorkList
.pop_back_val();
414 // Iterate through the PHI's incoming values.
415 for (typename
Traits::PHI_iterator I
= Traits::PHI_begin(PHI
),
416 E
= Traits::PHI_end(PHI
); I
!= E
; ++I
) {
417 ValT IncomingVal
= I
.getIncomingValue();
418 BBInfo
*PredInfo
= BBMap
[I
.getIncomingBlock()];
419 // Skip to the nearest preceding definition.
420 if (PredInfo
->DefBB
!= PredInfo
)
421 PredInfo
= PredInfo
->DefBB
;
423 // Check if it matches the expected value.
424 if (PredInfo
->AvailableVal
) {
425 if (IncomingVal
== PredInfo
->AvailableVal
)
430 // Check if the value is a PHI in the correct block.
431 PhiT
*IncomingPHIVal
= Traits::ValueIsPHI(IncomingVal
, Updater
);
432 if (!IncomingPHIVal
|| IncomingPHIVal
->getParent() != PredInfo
->BB
)
435 // If this block has already been visited, check if this PHI matches.
436 if (PredInfo
->PHITag
) {
437 if (IncomingPHIVal
== PredInfo
->PHITag
)
441 PredInfo
->PHITag
= IncomingPHIVal
;
443 WorkList
.push_back(IncomingPHIVal
);
449 /// RecordMatchingPHIs - For each PHI node that matches, record it in both
450 /// the BBMap and the AvailableVals mapping.
451 void RecordMatchingPHIs(BlockListTy
*BlockList
) {
452 for (typename
BlockListTy::iterator I
= BlockList
->begin(),
453 E
= BlockList
->end(); I
!= E
; ++I
)
454 if (PhiT
*PHI
= (*I
)->PHITag
) {
455 BlkT
*BB
= PHI
->getParent();
456 ValT PHIVal
= Traits::GetPHIValue(PHI
);
457 (*AvailableVals
)[BB
] = PHIVal
;
458 BBMap
[BB
]->AvailableVal
= PHIVal
;
463 } // end namespace llvm
465 #undef DEBUG_TYPE // "ssaupdater"
467 #endif // LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H