1 //===- SSAUpdater.cpp - Unstructured SSA Update Tool ----------------------===//
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 implements the SSAUpdater class.
12 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "ssaupdater"
15 #include "llvm/Transforms/Utils/SSAUpdater.h"
16 #include "llvm/Instructions.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/Support/AlignOf.h"
19 #include "llvm/Support/Allocator.h"
20 #include "llvm/Support/CFG.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/raw_ostream.h"
25 /// BBInfo - Per-basic block information used internally by SSAUpdater.
26 /// The predecessors of each block are cached here since pred_iterator is
27 /// slow and we need to iterate over the blocks at least a few times.
28 class SSAUpdater::BBInfo {
30 BasicBlock *BB; // Back-pointer to the corresponding block.
31 Value *AvailableVal; // Value to use in this block.
32 BBInfo *DefBB; // Block that defines the available value.
33 int BlkNum; // Postorder number.
34 BBInfo *IDom; // Immediate dominator.
35 unsigned NumPreds; // Number of predecessor blocks.
36 BBInfo **Preds; // Array[NumPreds] of predecessor blocks.
37 PHINode *PHITag; // Marker for existing PHIs that match.
39 BBInfo(BasicBlock *ThisBB, Value *V)
40 : BB(ThisBB), AvailableVal(V), DefBB(V ? this : 0), BlkNum(0), IDom(0),
41 NumPreds(0), Preds(0), PHITag(0) { }
44 typedef DenseMap<BasicBlock*, SSAUpdater::BBInfo*> BBMapTy;
46 typedef DenseMap<BasicBlock*, Value*> AvailableValsTy;
47 static AvailableValsTy &getAvailableVals(void *AV) {
48 return *static_cast<AvailableValsTy*>(AV);
51 static BBMapTy *getBBMap(void *BM) {
52 return static_cast<BBMapTy*>(BM);
55 SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI)
56 : AV(0), PrototypeValue(0), BM(0), InsertedPHIs(NewPHI) {}
58 SSAUpdater::~SSAUpdater() {
59 delete &getAvailableVals(AV);
62 /// Initialize - Reset this object to get ready for a new set of SSA
63 /// updates. ProtoValue is the value used to name PHI nodes.
64 void SSAUpdater::Initialize(Value *ProtoValue) {
66 AV = new AvailableValsTy();
68 getAvailableVals(AV).clear();
69 PrototypeValue = ProtoValue;
72 /// HasValueForBlock - Return true if the SSAUpdater already has a value for
73 /// the specified block.
74 bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const {
75 return getAvailableVals(AV).count(BB);
78 /// AddAvailableValue - Indicate that a rewritten value is available in the
79 /// specified block with the specified value.
80 void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) {
81 assert(PrototypeValue != 0 && "Need to initialize SSAUpdater");
82 assert(PrototypeValue->getType() == V->getType() &&
83 "All rewritten values must have the same type");
84 getAvailableVals(AV)[BB] = V;
87 /// IsEquivalentPHI - Check if PHI has the same incoming value as specified
88 /// in ValueMapping for each predecessor block.
89 static bool IsEquivalentPHI(PHINode *PHI,
90 DenseMap<BasicBlock*, Value*> &ValueMapping) {
91 unsigned PHINumValues = PHI->getNumIncomingValues();
92 if (PHINumValues != ValueMapping.size())
95 // Scan the phi to see if it matches.
96 for (unsigned i = 0, e = PHINumValues; i != e; ++i)
97 if (ValueMapping[PHI->getIncomingBlock(i)] !=
98 PHI->getIncomingValue(i)) {
105 /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is
106 /// live at the end of the specified block.
107 Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) {
108 assert(BM == 0 && "Unexpected Internal State");
109 Value *Res = GetValueAtEndOfBlockInternal(BB);
110 assert(BM == 0 && "Unexpected Internal State");
114 /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that
115 /// is live in the middle of the specified block.
117 /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one
118 /// important case: if there is a definition of the rewritten value after the
119 /// 'use' in BB. Consider code like this:
125 /// br Cond, SomeBB, OutBB
127 /// In this case, there are two values (X1 and X2) added to the AvailableVals
128 /// set by the client of the rewriter, and those values are both live out of
129 /// their respective blocks. However, the use of X happens in the *middle* of
130 /// a block. Because of this, we need to insert a new PHI node in SomeBB to
131 /// merge the appropriate values, and this value isn't live out of the block.
133 Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) {
134 // If there is no definition of the renamed variable in this block, just use
135 // GetValueAtEndOfBlock to do our work.
136 if (!HasValueForBlock(BB))
137 return GetValueAtEndOfBlock(BB);
139 // Otherwise, we have the hard case. Get the live-in values for each
141 SmallVector<std::pair<BasicBlock*, Value*>, 8> PredValues;
142 Value *SingularValue = 0;
144 // We can get our predecessor info by walking the pred_iterator list, but it
145 // is relatively slow. If we already have PHI nodes in this block, walk one
146 // of them to get the predecessor list instead.
147 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
148 for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) {
149 BasicBlock *PredBB = SomePhi->getIncomingBlock(i);
150 Value *PredVal = GetValueAtEndOfBlock(PredBB);
151 PredValues.push_back(std::make_pair(PredBB, PredVal));
153 // Compute SingularValue.
155 SingularValue = PredVal;
156 else if (PredVal != SingularValue)
160 bool isFirstPred = true;
161 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
162 BasicBlock *PredBB = *PI;
163 Value *PredVal = GetValueAtEndOfBlock(PredBB);
164 PredValues.push_back(std::make_pair(PredBB, PredVal));
166 // Compute SingularValue.
168 SingularValue = PredVal;
170 } else if (PredVal != SingularValue)
175 // If there are no predecessors, just return undef.
176 if (PredValues.empty())
177 return UndefValue::get(PrototypeValue->getType());
179 // Otherwise, if all the merged values are the same, just use it.
180 if (SingularValue != 0)
181 return SingularValue;
183 // Otherwise, we do need a PHI: check to see if we already have one available
184 // in this block that produces the right value.
185 if (isa<PHINode>(BB->begin())) {
186 DenseMap<BasicBlock*, Value*> ValueMapping(PredValues.begin(),
189 for (BasicBlock::iterator It = BB->begin();
190 (SomePHI = dyn_cast<PHINode>(It)); ++It) {
191 if (IsEquivalentPHI(SomePHI, ValueMapping))
196 // Ok, we have no way out, insert a new one now.
197 PHINode *InsertedPHI = PHINode::Create(PrototypeValue->getType(),
198 PrototypeValue->getName(),
200 InsertedPHI->reserveOperandSpace(PredValues.size());
202 // Fill in all the predecessors of the PHI.
203 for (unsigned i = 0, e = PredValues.size(); i != e; ++i)
204 InsertedPHI->addIncoming(PredValues[i].second, PredValues[i].first);
206 // See if the PHI node can be merged to a single value. This can happen in
207 // loop cases when we get a PHI of itself and one other value.
208 if (Value *ConstVal = InsertedPHI->hasConstantValue()) {
209 InsertedPHI->eraseFromParent();
213 // If the client wants to know about all new instructions, tell it.
214 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
216 DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");
220 /// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes,
221 /// which use their value in the corresponding predecessor.
222 void SSAUpdater::RewriteUse(Use &U) {
223 Instruction *User = cast<Instruction>(U.getUser());
226 if (PHINode *UserPN = dyn_cast<PHINode>(User))
227 V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
229 V = GetValueInMiddleOfBlock(User->getParent());
234 /// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry
235 /// for the specified BB and if so, return it. If not, construct SSA form by
236 /// first calculating the required placement of PHIs and then inserting new
237 /// PHIs where needed.
238 Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {
239 AvailableValsTy &AvailableVals = getAvailableVals(AV);
240 if (Value *V = AvailableVals[BB])
243 // Pool allocation used internally by GetValueAtEndOfBlock.
244 BumpPtrAllocator Allocator;
248 SmallVector<BBInfo*, 100> BlockList;
249 BuildBlockList(BB, &BlockList, &Allocator);
251 // Special case: bail out if BB is unreachable.
252 if (BlockList.size() == 0) {
254 return UndefValue::get(PrototypeValue->getType());
257 FindDominators(&BlockList);
258 FindPHIPlacement(&BlockList);
259 FindAvailableVals(&BlockList);
262 return BBMapObj[BB]->DefBB->AvailableVal;
265 /// FindPredecessorBlocks - Put the predecessors of Info->BB into the Preds
266 /// vector, set Info->NumPreds, and allocate space in Info->Preds.
267 static void FindPredecessorBlocks(SSAUpdater::BBInfo *Info,
268 SmallVectorImpl<BasicBlock*> *Preds,
269 BumpPtrAllocator *Allocator) {
270 // We can get our predecessor info by walking the pred_iterator list,
271 // but it is relatively slow. If we already have PHI nodes in this
272 // block, walk one of them to get the predecessor list instead.
273 BasicBlock *BB = Info->BB;
274 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
275 for (unsigned PI = 0, E = SomePhi->getNumIncomingValues(); PI != E; ++PI)
276 Preds->push_back(SomePhi->getIncomingBlock(PI));
278 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
279 Preds->push_back(*PI);
282 Info->NumPreds = Preds->size();
283 Info->Preds = static_cast<SSAUpdater::BBInfo**>
284 (Allocator->Allocate(Info->NumPreds * sizeof(SSAUpdater::BBInfo*),
285 AlignOf<SSAUpdater::BBInfo*>::Alignment));
288 /// BuildBlockList - Starting from the specified basic block, traverse back
289 /// through its predecessors until reaching blocks with known values. Create
290 /// BBInfo structures for the blocks and append them to the block list.
291 void SSAUpdater::BuildBlockList(BasicBlock *BB, BlockListTy *BlockList,
292 BumpPtrAllocator *Allocator) {
293 AvailableValsTy &AvailableVals = getAvailableVals(AV);
294 BBMapTy *BBMap = getBBMap(BM);
295 SmallVector<BBInfo*, 10> RootList;
296 SmallVector<BBInfo*, 64> WorkList;
298 BBInfo *Info = new (*Allocator) BBInfo(BB, 0);
300 WorkList.push_back(Info);
302 // Search backward from BB, creating BBInfos along the way and stopping when
303 // reaching blocks that define the value. Record those defining blocks on
305 SmallVector<BasicBlock*, 10> Preds;
306 while (!WorkList.empty()) {
307 Info = WorkList.pop_back_val();
309 FindPredecessorBlocks(Info, &Preds, Allocator);
311 // Treat an unreachable predecessor as a definition with 'undef'.
312 if (Info->NumPreds == 0) {
313 Info->AvailableVal = UndefValue::get(PrototypeValue->getType());
315 RootList.push_back(Info);
319 for (unsigned p = 0; p != Info->NumPreds; ++p) {
320 BasicBlock *Pred = Preds[p];
321 // Check if BBMap already has a BBInfo for the predecessor block.
322 BBMapTy::value_type &BBMapBucket = BBMap->FindAndConstruct(Pred);
323 if (BBMapBucket.second) {
324 Info->Preds[p] = BBMapBucket.second;
328 // Create a new BBInfo for the predecessor.
329 Value *PredVal = AvailableVals.lookup(Pred);
330 BBInfo *PredInfo = new (*Allocator) BBInfo(Pred, PredVal);
331 BBMapBucket.second = PredInfo;
332 Info->Preds[p] = PredInfo;
334 if (PredInfo->AvailableVal) {
335 RootList.push_back(PredInfo);
338 WorkList.push_back(PredInfo);
342 // Now that we know what blocks are backwards-reachable from the starting
343 // block, do a forward depth-first traversal to assign postorder numbers
345 BBInfo *PseudoEntry = new (*Allocator) BBInfo(0, 0);
348 // Initialize the worklist with the roots from the backward traversal.
349 while (!RootList.empty()) {
350 Info = RootList.pop_back_val();
351 Info->IDom = PseudoEntry;
353 WorkList.push_back(Info);
356 while (!WorkList.empty()) {
357 Info = WorkList.back();
359 if (Info->BlkNum == -2) {
360 // All the successors have been handled; assign the postorder number.
361 Info->BlkNum = BlkNum++;
362 // If not a root, put it on the BlockList.
363 if (!Info->AvailableVal)
364 BlockList->push_back(Info);
369 // Leave this entry on the worklist, but set its BlkNum to mark that its
370 // successors have been put on the worklist. When it returns to the top
371 // the list, after handling its successors, it will be assigned a number.
374 // Add unvisited successors to the work list.
375 for (succ_iterator SI = succ_begin(Info->BB), E = succ_end(Info->BB);
377 BBInfo *SuccInfo = (*BBMap)[*SI];
378 if (!SuccInfo || SuccInfo->BlkNum)
380 SuccInfo->BlkNum = -1;
381 WorkList.push_back(SuccInfo);
384 PseudoEntry->BlkNum = BlkNum;
387 /// IntersectDominators - This is the dataflow lattice "meet" operation for
388 /// finding dominators. Given two basic blocks, it walks up the dominator
389 /// tree until it finds a common dominator of both. It uses the postorder
390 /// number of the blocks to determine how to do that.
391 static SSAUpdater::BBInfo *IntersectDominators(SSAUpdater::BBInfo *Blk1,
392 SSAUpdater::BBInfo *Blk2) {
393 while (Blk1 != Blk2) {
394 while (Blk1->BlkNum < Blk2->BlkNum) {
399 while (Blk2->BlkNum < Blk1->BlkNum) {
408 /// FindDominators - Calculate the dominator tree for the subset of the CFG
409 /// corresponding to the basic blocks on the BlockList. This uses the
410 /// algorithm from: "A Simple, Fast Dominance Algorithm" by Cooper, Harvey and
411 /// Kennedy, published in Software--Practice and Experience, 2001, 4:1-10.
412 /// Because the CFG subset does not include any edges leading into blocks that
413 /// define the value, the results are not the usual dominator tree. The CFG
414 /// subset has a single pseudo-entry node with edges to a set of root nodes
415 /// for blocks that define the value. The dominators for this subset CFG are
416 /// not the standard dominators but they are adequate for placing PHIs within
418 void SSAUpdater::FindDominators(BlockListTy *BlockList) {
422 // Iterate over the list in reverse order, i.e., forward on CFG edges.
423 for (BlockListTy::reverse_iterator I = BlockList->rbegin(),
424 E = BlockList->rend(); I != E; ++I) {
427 // Start with the first predecessor.
428 assert(Info->NumPreds > 0 && "unreachable block");
429 BBInfo *NewIDom = Info->Preds[0];
431 // Iterate through the block's other predecessors.
432 for (unsigned p = 1; p != Info->NumPreds; ++p) {
433 BBInfo *Pred = Info->Preds[p];
434 NewIDom = IntersectDominators(NewIDom, Pred);
437 // Check if the IDom value has changed.
438 if (NewIDom != Info->IDom) {
439 Info->IDom = NewIDom;
446 /// IsDefInDomFrontier - Search up the dominator tree from Pred to IDom for
447 /// any blocks containing definitions of the value. If one is found, then the
448 /// successor of Pred is in the dominance frontier for the definition, and
449 /// this function returns true.
450 static bool IsDefInDomFrontier(const SSAUpdater::BBInfo *Pred,
451 const SSAUpdater::BBInfo *IDom) {
452 for (; Pred != IDom; Pred = Pred->IDom) {
453 if (Pred->DefBB == Pred)
459 /// FindPHIPlacement - PHIs are needed in the iterated dominance frontiers of
460 /// the known definitions. Iteratively add PHIs in the dom frontiers until
461 /// nothing changes. Along the way, keep track of the nearest dominating
462 /// definitions for non-PHI blocks.
463 void SSAUpdater::FindPHIPlacement(BlockListTy *BlockList) {
467 // Iterate over the list in reverse order, i.e., forward on CFG edges.
468 for (BlockListTy::reverse_iterator I = BlockList->rbegin(),
469 E = BlockList->rend(); I != E; ++I) {
472 // If this block already needs a PHI, there is nothing to do here.
473 if (Info->DefBB == Info)
476 // Default to use the same def as the immediate dominator.
477 BBInfo *NewDefBB = Info->IDom->DefBB;
478 for (unsigned p = 0; p != Info->NumPreds; ++p) {
479 if (IsDefInDomFrontier(Info->Preds[p], Info->IDom)) {
486 // Check if anything changed.
487 if (NewDefBB != Info->DefBB) {
488 Info->DefBB = NewDefBB;
495 /// FindAvailableVal - If this block requires a PHI, first check if an existing
496 /// PHI matches the PHI placement and reaching definitions computed earlier,
497 /// and if not, create a new PHI. Visit all the block's predecessors to
498 /// calculate the available value for each one and fill in the incoming values
500 void SSAUpdater::FindAvailableVals(BlockListTy *BlockList) {
501 AvailableValsTy &AvailableVals = getAvailableVals(AV);
503 // Go through the worklist in forward order (i.e., backward through the CFG)
504 // and check if existing PHIs can be used. If not, create empty PHIs where
506 for (BlockListTy::iterator I = BlockList->begin(), E = BlockList->end();
509 // Check if there needs to be a PHI in BB.
510 if (Info->DefBB != Info)
513 // Look for an existing PHI.
514 FindExistingPHI(Info->BB, BlockList);
515 if (Info->AvailableVal)
518 PHINode *PHI = PHINode::Create(PrototypeValue->getType(),
519 PrototypeValue->getName(),
521 PHI->reserveOperandSpace(Info->NumPreds);
522 Info->AvailableVal = PHI;
523 AvailableVals[Info->BB] = PHI;
526 // Now go back through the worklist in reverse order to fill in the arguments
527 // for any new PHIs added in the forward traversal.
528 for (BlockListTy::reverse_iterator I = BlockList->rbegin(),
529 E = BlockList->rend(); I != E; ++I) {
532 if (Info->DefBB != Info) {
533 // Record the available value at join nodes to speed up subsequent
534 // uses of this SSAUpdater for the same value.
535 if (Info->NumPreds > 1)
536 AvailableVals[Info->BB] = Info->DefBB->AvailableVal;
540 // Check if this block contains a newly added PHI.
541 PHINode *PHI = dyn_cast<PHINode>(Info->AvailableVal);
542 if (!PHI || PHI->getNumIncomingValues() == Info->NumPreds)
545 // Iterate through the block's predecessors.
546 for (unsigned p = 0; p != Info->NumPreds; ++p) {
547 BBInfo *PredInfo = Info->Preds[p];
548 BasicBlock *Pred = PredInfo->BB;
549 // Skip to the nearest preceding definition.
550 if (PredInfo->DefBB != PredInfo)
551 PredInfo = PredInfo->DefBB;
552 PHI->addIncoming(PredInfo->AvailableVal, Pred);
555 DEBUG(dbgs() << " Inserted PHI: " << *PHI << "\n");
557 // If the client wants to know about all new instructions, tell it.
558 if (InsertedPHIs) InsertedPHIs->push_back(PHI);
562 /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
563 /// them match what is needed.
564 void SSAUpdater::FindExistingPHI(BasicBlock *BB, BlockListTy *BlockList) {
566 for (BasicBlock::iterator It = BB->begin();
567 (SomePHI = dyn_cast<PHINode>(It)); ++It) {
568 if (CheckIfPHIMatches(SomePHI)) {
569 RecordMatchingPHI(SomePHI);
572 // Match failed: clear all the PHITag values.
573 for (BlockListTy::iterator I = BlockList->begin(), E = BlockList->end();
579 /// CheckIfPHIMatches - Check if a PHI node matches the placement and values
581 bool SSAUpdater::CheckIfPHIMatches(PHINode *PHI) {
582 BBMapTy *BBMap = getBBMap(BM);
583 SmallVector<PHINode*, 20> WorkList;
584 WorkList.push_back(PHI);
586 // Mark that the block containing this PHI has been visited.
587 (*BBMap)[PHI->getParent()]->PHITag = PHI;
589 while (!WorkList.empty()) {
590 PHI = WorkList.pop_back_val();
592 // Iterate through the PHI's incoming values.
593 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
594 Value *IncomingVal = PHI->getIncomingValue(i);
595 BBInfo *PredInfo = (*BBMap)[PHI->getIncomingBlock(i)];
596 // Skip to the nearest preceding definition.
597 if (PredInfo->DefBB != PredInfo)
598 PredInfo = PredInfo->DefBB;
600 // Check if it matches the expected value.
601 if (PredInfo->AvailableVal) {
602 if (IncomingVal == PredInfo->AvailableVal)
607 // Check if the value is a PHI in the correct block.
608 PHINode *IncomingPHIVal = dyn_cast<PHINode>(IncomingVal);
609 if (!IncomingPHIVal || IncomingPHIVal->getParent() != PredInfo->BB)
612 // If this block has already been visited, check if this PHI matches.
613 if (PredInfo->PHITag) {
614 if (IncomingPHIVal == PredInfo->PHITag)
618 PredInfo->PHITag = IncomingPHIVal;
620 WorkList.push_back(IncomingPHIVal);
626 /// RecordMatchingPHI - For a PHI node that matches, record it and its input
627 /// PHIs in both the BBMap and the AvailableVals mapping.
628 void SSAUpdater::RecordMatchingPHI(PHINode *PHI) {
629 BBMapTy *BBMap = getBBMap(BM);
630 AvailableValsTy &AvailableVals = getAvailableVals(AV);
631 SmallVector<PHINode*, 20> WorkList;
632 WorkList.push_back(PHI);
635 BasicBlock *BB = PHI->getParent();
636 AvailableVals[BB] = PHI;
637 (*BBMap)[BB]->AvailableVal = PHI;
639 while (!WorkList.empty()) {
640 PHI = WorkList.pop_back_val();
642 // Iterate through the PHI's incoming values.
643 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
644 PHINode *IncomingPHIVal = dyn_cast<PHINode>(PHI->getIncomingValue(i));
645 if (!IncomingPHIVal) continue;
646 BB = IncomingPHIVal->getParent();
647 BBInfo *Info = (*BBMap)[BB];
648 if (!Info || Info->AvailableVal)
651 // Record the PHI and add it to the worklist.
652 AvailableVals[BB] = IncomingPHIVal;
653 Info->AvailableVal = IncomingPHIVal;
654 WorkList.push_back(IncomingPHIVal);