1 //===-- SSAUpdaterImpl.h - SSA Updater Implementation -----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file provides a template that implements the core algorithm for the
11 // SSAUpdater and MachineSSAUpdater.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
16 #define LLVM_TRANSFORMS_UTILS_SSAUPDATERIMPL_H
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/IR/ValueHandle.h"
21 #include "llvm/Support/Allocator.h"
22 #include "llvm/Support/Debug.h"
26 #define DEBUG_TYPE "ssaupdater"
30 template<typename T> class SSAUpdaterTraits;
32 template<typename UpdaterT>
33 class SSAUpdaterImpl {
37 typedef SSAUpdaterTraits<UpdaterT> Traits;
38 typedef typename Traits::BlkT BlkT;
39 typedef typename Traits::ValT ValT;
40 typedef typename Traits::PhiT PhiT;
42 /// BBInfo - Per-basic block information used internally by SSAUpdaterImpl.
43 /// The predecessors of each block are cached here since pred_iterator is
44 /// slow and we need to iterate over the blocks at least a few times.
47 BlkT *BB; // Back-pointer to the corresponding block.
48 ValT AvailableVal; // Value to use in this block.
49 BBInfo *DefBB; // Block that defines the available value.
50 int BlkNum; // Postorder number.
51 BBInfo *IDom; // Immediate dominator.
52 unsigned NumPreds; // Number of predecessor blocks.
53 BBInfo **Preds; // Array[NumPreds] of predecessor blocks.
54 PhiT *PHITag; // Marker for existing PHIs that match.
56 BBInfo(BlkT *ThisBB, ValT V)
57 : BB(ThisBB), AvailableVal(V), DefBB(V ? this : nullptr), BlkNum(0),
58 IDom(nullptr), NumPreds(0), Preds(nullptr), PHITag(nullptr) {}
61 typedef DenseMap<BlkT*, ValT> AvailableValsTy;
62 AvailableValsTy *AvailableVals;
64 SmallVectorImpl<PhiT*> *InsertedPHIs;
66 typedef SmallVectorImpl<BBInfo*> BlockListTy;
67 typedef DenseMap<BlkT*, BBInfo*> BBMapTy;
69 BumpPtrAllocator Allocator;
72 explicit SSAUpdaterImpl(UpdaterT *U, AvailableValsTy *A,
73 SmallVectorImpl<PhiT*> *Ins) :
74 Updater(U), AvailableVals(A), InsertedPHIs(Ins) { }
76 /// GetValue - Check to see if AvailableVals has an entry for the specified
77 /// BB and if so, return it. If not, construct SSA form by first
78 /// calculating the required placement of PHIs and then inserting new PHIs
80 ValT GetValue(BlkT *BB) {
81 SmallVector<BBInfo*, 100> BlockList;
82 BBInfo *PseudoEntry = BuildBlockList(BB, &BlockList);
84 // Special case: bail out if BB is unreachable.
85 if (BlockList.size() == 0) {
86 ValT V = Traits::GetUndefVal(BB, Updater);
87 (*AvailableVals)[BB] = V;
91 FindDominators(&BlockList, PseudoEntry);
92 FindPHIPlacement(&BlockList);
93 FindAvailableVals(&BlockList);
95 return BBMap[BB]->DefBB->AvailableVal;
98 /// BuildBlockList - Starting from the specified basic block, traverse back
99 /// through its predecessors until reaching blocks with known values.
100 /// Create BBInfo structures for the blocks and append them to the block
102 BBInfo *BuildBlockList(BlkT *BB, BlockListTy *BlockList) {
103 SmallVector<BBInfo*, 10> RootList;
104 SmallVector<BBInfo*, 64> WorkList;
106 BBInfo *Info = new (Allocator) BBInfo(BB, 0);
108 WorkList.push_back(Info);
110 // Search backward from BB, creating BBInfos along the way and stopping
111 // when reaching blocks that define the value. Record those defining
112 // blocks on the RootList.
113 SmallVector<BlkT*, 10> Preds;
114 while (!WorkList.empty()) {
115 Info = WorkList.pop_back_val();
117 Traits::FindPredecessorBlocks(Info->BB, &Preds);
118 Info->NumPreds = Preds.size();
119 if (Info->NumPreds == 0)
120 Info->Preds = nullptr;
122 Info->Preds = static_cast<BBInfo**>
123 (Allocator.Allocate(Info->NumPreds * sizeof(BBInfo*),
124 AlignOf<BBInfo*>::Alignment));
126 for (unsigned p = 0; p != Info->NumPreds; ++p) {
127 BlkT *Pred = Preds[p];
128 // Check if BBMap already has a BBInfo for the predecessor block.
129 typename BBMapTy::value_type &BBMapBucket =
130 BBMap.FindAndConstruct(Pred);
131 if (BBMapBucket.second) {
132 Info->Preds[p] = BBMapBucket.second;
136 // Create a new BBInfo for the predecessor.
137 ValT PredVal = AvailableVals->lookup(Pred);
138 BBInfo *PredInfo = new (Allocator) BBInfo(Pred, PredVal);
139 BBMapBucket.second = PredInfo;
140 Info->Preds[p] = PredInfo;
142 if (PredInfo->AvailableVal) {
143 RootList.push_back(PredInfo);
146 WorkList.push_back(PredInfo);
150 // Now that we know what blocks are backwards-reachable from the starting
151 // block, do a forward depth-first traversal to assign postorder numbers
153 BBInfo *PseudoEntry = new (Allocator) BBInfo(nullptr, 0);
156 // Initialize the worklist with the roots from the backward traversal.
157 while (!RootList.empty()) {
158 Info = RootList.pop_back_val();
159 Info->IDom = PseudoEntry;
161 WorkList.push_back(Info);
164 while (!WorkList.empty()) {
165 Info = WorkList.back();
167 if (Info->BlkNum == -2) {
168 // All the successors have been handled; assign the postorder number.
169 Info->BlkNum = BlkNum++;
170 // If not a root, put it on the BlockList.
171 if (!Info->AvailableVal)
172 BlockList->push_back(Info);
177 // Leave this entry on the worklist, but set its BlkNum to mark that its
178 // successors have been put on the worklist. When it returns to the top
179 // the list, after handling its successors, it will be assigned a
183 // Add unvisited successors to the work list.
184 for (typename Traits::BlkSucc_iterator SI =
185 Traits::BlkSucc_begin(Info->BB),
186 E = Traits::BlkSucc_end(Info->BB); SI != E; ++SI) {
187 BBInfo *SuccInfo = BBMap[*SI];
188 if (!SuccInfo || SuccInfo->BlkNum)
190 SuccInfo->BlkNum = -1;
191 WorkList.push_back(SuccInfo);
194 PseudoEntry->BlkNum = BlkNum;
198 /// IntersectDominators - This is the dataflow lattice "meet" operation for
199 /// finding dominators. Given two basic blocks, it walks up the dominator
200 /// tree until it finds a common dominator of both. It uses the postorder
201 /// number of the blocks to determine how to do that.
202 BBInfo *IntersectDominators(BBInfo *Blk1, BBInfo *Blk2) {
203 while (Blk1 != Blk2) {
204 while (Blk1->BlkNum < Blk2->BlkNum) {
209 while (Blk2->BlkNum < Blk1->BlkNum) {
218 /// FindDominators - Calculate the dominator tree for the subset of the CFG
219 /// corresponding to the basic blocks on the BlockList. This uses the
220 /// algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper, Harvey
221 /// and Kennedy, published in Software--Practice and Experience, 2001,
222 /// 4:1-10. Because the CFG subset does not include any edges leading into
223 /// blocks that define the value, the results are not the usual dominator
224 /// tree. The CFG subset has a single pseudo-entry node with edges to a set
225 /// of root nodes for blocks that define the value. The dominators for this
226 /// subset CFG are not the standard dominators but they are adequate for
227 /// placing PHIs within the subset CFG.
228 void FindDominators(BlockListTy *BlockList, BBInfo *PseudoEntry) {
232 // Iterate over the list in reverse order, i.e., forward on CFG edges.
233 for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
234 E = BlockList->rend(); I != E; ++I) {
236 BBInfo *NewIDom = nullptr;
238 // Iterate through the block's predecessors.
239 for (unsigned p = 0; p != Info->NumPreds; ++p) {
240 BBInfo *Pred = Info->Preds[p];
242 // Treat an unreachable predecessor as a definition with 'undef'.
243 if (Pred->BlkNum == 0) {
244 Pred->AvailableVal = Traits::GetUndefVal(Pred->BB, Updater);
245 (*AvailableVals)[Pred->BB] = Pred->AvailableVal;
247 Pred->BlkNum = PseudoEntry->BlkNum;
248 PseudoEntry->BlkNum++;
254 NewIDom = IntersectDominators(NewIDom, Pred);
257 // Check if the IDom value has changed.
258 if (NewIDom && NewIDom != Info->IDom) {
259 Info->IDom = NewIDom;
266 /// IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for
267 /// any blocks containing definitions of the value. If one is found, then
268 /// the successor of Pred is in the dominance frontier for the definition,
269 /// and this function returns true.
270 bool IsDefInDomFrontier(const BBInfo *Pred, const BBInfo *IDom) {
271 for (; Pred != IDom; Pred = Pred->IDom) {
272 if (Pred->DefBB == Pred)
278 /// FindPHIPlacement - PHIs are needed in the iterated dominance frontiers
279 /// of the known definitions. Iteratively add PHIs in the dom frontiers
280 /// until nothing changes. Along the way, keep track of the nearest
281 /// dominating definitions for non-PHI blocks.
282 void FindPHIPlacement(BlockListTy *BlockList) {
286 // Iterate over the list in reverse order, i.e., forward on CFG edges.
287 for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
288 E = BlockList->rend(); I != E; ++I) {
291 // If this block already needs a PHI, there is nothing to do here.
292 if (Info->DefBB == Info)
295 // Default to use the same def as the immediate dominator.
296 BBInfo *NewDefBB = Info->IDom->DefBB;
297 for (unsigned p = 0; p != Info->NumPreds; ++p) {
298 if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) {
305 // Check if anything changed.
306 if (NewDefBB != Info->DefBB) {
307 Info->DefBB = NewDefBB;
314 /// FindAvailableVal - If this block requires a PHI, first check if an
315 /// existing PHI matches the PHI placement and reaching definitions computed
316 /// earlier, and if not, create a new PHI. Visit all the block's
317 /// predecessors to calculate the available value for each one and fill in
318 /// the incoming values for a new PHI.
319 void FindAvailableVals(BlockListTy *BlockList) {
320 // Go through the worklist in forward order (i.e., backward through the CFG)
321 // and check if existing PHIs can be used. If not, create empty PHIs where
323 for (typename BlockListTy::iterator I = BlockList->begin(),
324 E = BlockList->end(); I != E; ++I) {
326 // Check if there needs to be a PHI in BB.
327 if (Info->DefBB != Info)
330 // Look for an existing PHI.
331 FindExistingPHI(Info->BB, BlockList);
332 if (Info->AvailableVal)
335 ValT PHI = Traits::CreateEmptyPHI(Info->BB, Info->NumPreds, Updater);
336 Info->AvailableVal = PHI;
337 (*AvailableVals)[Info->BB] = PHI;
340 // Now go back through the worklist in reverse order to fill in the
341 // arguments for any new PHIs added in the forward traversal.
342 for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
343 E = BlockList->rend(); I != E; ++I) {
346 if (Info->DefBB != Info) {
347 // Record the available value at join nodes to speed up subsequent
348 // uses of this SSAUpdater for the same value.
349 if (Info->NumPreds > 1)
350 (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal;
354 // Check if this block contains a newly added PHI.
355 PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater);
359 // Iterate through the block's predecessors.
360 for (unsigned p = 0; p != Info->NumPreds; ++p) {
361 BBInfo *PredInfo = Info->Preds[p];
362 BlkT *Pred = PredInfo->BB;
363 // Skip to the nearest preceding definition.
364 if (PredInfo->DefBB != PredInfo)
365 PredInfo = PredInfo->DefBB;
366 Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred);
369 DEBUG(dbgs() << " Inserted PHI: " << *PHI << "\n");
371 // If the client wants to know about all new instructions, tell it.
372 if (InsertedPHIs) InsertedPHIs->push_back(PHI);
376 /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
377 /// them match what is needed.
378 void FindExistingPHI(BlkT *BB, BlockListTy *BlockList) {
379 for (typename BlkT::iterator BBI = BB->begin(), BBE = BB->end();
381 PhiT *SomePHI = Traits::InstrIsPHI(BBI);
384 if (CheckIfPHIMatches(SomePHI)) {
385 RecordMatchingPHIs(BlockList);
388 // Match failed: clear all the PHITag values.
389 for (typename BlockListTy::iterator I = BlockList->begin(),
390 E = BlockList->end(); I != E; ++I)
391 (*I)->PHITag = nullptr;
395 /// CheckIfPHIMatches - Check if a PHI node matches the placement and values
397 bool CheckIfPHIMatches(PhiT *PHI) {
398 SmallVector<PhiT*, 20> WorkList;
399 WorkList.push_back(PHI);
401 // Mark that the block containing this PHI has been visited.
402 BBMap[PHI->getParent()]->PHITag = PHI;
404 while (!WorkList.empty()) {
405 PHI = WorkList.pop_back_val();
407 // Iterate through the PHI's incoming values.
408 for (typename Traits::PHI_iterator I = Traits::PHI_begin(PHI),
409 E = Traits::PHI_end(PHI); I != E; ++I) {
410 ValT IncomingVal = I.getIncomingValue();
411 BBInfo *PredInfo = BBMap[I.getIncomingBlock()];
412 // Skip to the nearest preceding definition.
413 if (PredInfo->DefBB != PredInfo)
414 PredInfo = PredInfo->DefBB;
416 // Check if it matches the expected value.
417 if (PredInfo->AvailableVal) {
418 if (IncomingVal == PredInfo->AvailableVal)
423 // Check if the value is a PHI in the correct block.
424 PhiT *IncomingPHIVal = Traits::ValueIsPHI(IncomingVal, Updater);
425 if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB)
428 // If this block has already been visited, check if this PHI matches.
429 if (PredInfo->PHITag) {
430 if (IncomingPHIVal == PredInfo->PHITag)
434 PredInfo->PHITag = IncomingPHIVal;
436 WorkList.push_back(IncomingPHIVal);
442 /// RecordMatchingPHIs - For each PHI node that matches, record it in both
443 /// the BBMap and the AvailableVals mapping.
444 void RecordMatchingPHIs(BlockListTy *BlockList) {
445 for (typename BlockListTy::iterator I = BlockList->begin(),
446 E = BlockList->end(); I != E; ++I)
447 if (PhiT *PHI = (*I)->PHITag) {
448 BlkT *BB = PHI->getParent();
449 ValT PHIVal = Traits::GetPHIValue(PHI);
450 (*AvailableVals)[BB] = PHIVal;
451 BBMap[BB]->AvailableVal = PHIVal;
456 #undef DEBUG_TYPE // "ssaupdater"
458 } // End llvm namespace