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 #include "llvm/Transforms/Utils/SSAUpdater.h"
15 #include "llvm/Instructions.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/Support/AlignOf.h"
18 #include "llvm/Support/Allocator.h"
19 #include "llvm/Support/CFG.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/raw_ostream.h"
24 /// BBInfo - Per-basic block information used internally by SSAUpdater.
25 /// The predecessors of each block are cached here since pred_iterator is
26 /// slow and we need to iterate over the blocks at least a few times.
27 class SSAUpdater::BBInfo {
29 Value *AvailableVal; // Value to use in this block.
30 BasicBlock *DefBB; // Block that defines the available value.
31 unsigned NumPreds; // Number of predecessor blocks.
32 BasicBlock **Preds; // Array[NumPreds] of predecessor blocks.
33 unsigned Counter; // Marker to identify blocks already visited.
34 PHINode *PHITag; // Marker for existing PHIs that match.
36 BBInfo(BasicBlock *BB, Value *V, BumpPtrAllocator *Allocator);
38 typedef DenseMap<BasicBlock*, SSAUpdater::BBInfo*> BBMapTy;
40 SSAUpdater::BBInfo::BBInfo(BasicBlock *BB, Value *V,
41 BumpPtrAllocator *Allocator)
42 : AvailableVal(V), DefBB(0), NumPreds(0), Preds(0), Counter(0), PHITag(0) {
43 // If this block has a known value, don't bother finding its predecessors.
49 // We can get our predecessor info by walking the pred_iterator list, but it
50 // is relatively slow. If we already have PHI nodes in this block, walk one
51 // of them to get the predecessor list instead.
52 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
53 NumPreds = SomePhi->getNumIncomingValues();
54 Preds = static_cast<BasicBlock**>
55 (Allocator->Allocate(NumPreds * sizeof(BasicBlock*),
56 AlignOf<BasicBlock*>::Alignment));
57 for (unsigned pi = 0; pi != NumPreds; ++pi)
58 Preds[pi] = SomePhi->getIncomingBlock(pi);
62 // Stash the predecessors in a temporary vector until we know how much space
63 // to allocate for them.
64 SmallVector<BasicBlock*, 10> TmpPreds;
65 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
66 TmpPreds.push_back(*PI);
69 Preds = static_cast<BasicBlock**>
70 (Allocator->Allocate(NumPreds * sizeof(BasicBlock*),
71 AlignOf<BasicBlock*>::Alignment));
72 memcpy(Preds, TmpPreds.data(), NumPreds * sizeof(BasicBlock*));
75 typedef DenseMap<BasicBlock*, Value*> AvailableValsTy;
76 static AvailableValsTy &getAvailableVals(void *AV) {
77 return *static_cast<AvailableValsTy*>(AV);
80 static BBMapTy *getBBMap(void *BM) {
81 return static_cast<BBMapTy*>(BM);
84 static BumpPtrAllocator *getAllocator(void *BPA) {
85 return static_cast<BumpPtrAllocator*>(BPA);
88 SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI)
89 : AV(0), PrototypeValue(0), BM(0), BPA(0), InsertedPHIs(NewPHI) {}
91 SSAUpdater::~SSAUpdater() {
92 delete &getAvailableVals(AV);
95 /// Initialize - Reset this object to get ready for a new set of SSA
96 /// updates. ProtoValue is the value used to name PHI nodes.
97 void SSAUpdater::Initialize(Value *ProtoValue) {
99 AV = new AvailableValsTy();
101 getAvailableVals(AV).clear();
102 PrototypeValue = ProtoValue;
105 /// HasValueForBlock - Return true if the SSAUpdater already has a value for
106 /// the specified block.
107 bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const {
108 return getAvailableVals(AV).count(BB);
111 /// AddAvailableValue - Indicate that a rewritten value is available in the
112 /// specified block with the specified value.
113 void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) {
114 assert(PrototypeValue != 0 && "Need to initialize SSAUpdater");
115 assert(PrototypeValue->getType() == V->getType() &&
116 "All rewritten values must have the same type");
117 getAvailableVals(AV)[BB] = V;
120 /// IsEquivalentPHI - Check if PHI has the same incoming value as specified
121 /// in ValueMapping for each predecessor block.
122 static bool IsEquivalentPHI(PHINode *PHI,
123 DenseMap<BasicBlock*, Value*> &ValueMapping) {
124 unsigned PHINumValues = PHI->getNumIncomingValues();
125 if (PHINumValues != ValueMapping.size())
128 // Scan the phi to see if it matches.
129 for (unsigned i = 0, e = PHINumValues; i != e; ++i)
130 if (ValueMapping[PHI->getIncomingBlock(i)] !=
131 PHI->getIncomingValue(i)) {
138 /// GetExistingPHI - Check if BB already contains a phi node that is equivalent
139 /// to the specified mapping from predecessor blocks to incoming values.
140 static Value *GetExistingPHI(BasicBlock *BB,
141 DenseMap<BasicBlock*, Value*> &ValueMapping) {
143 for (BasicBlock::iterator It = BB->begin();
144 (SomePHI = dyn_cast<PHINode>(It)); ++It) {
145 if (IsEquivalentPHI(SomePHI, ValueMapping))
151 /// GetExistingPHI - Check if BB already contains an equivalent phi node.
152 /// The InputIt type must be an iterator over std::pair<BasicBlock*, Value*>
153 /// objects that specify the mapping from predecessor blocks to incoming values.
154 template<typename InputIt>
155 static Value *GetExistingPHI(BasicBlock *BB, const InputIt &I,
157 // Avoid create the mapping if BB has no phi nodes at all.
158 if (!isa<PHINode>(BB->begin()))
160 DenseMap<BasicBlock*, Value*> ValueMapping(I, E);
161 return GetExistingPHI(BB, ValueMapping);
164 /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is
165 /// live at the end of the specified block.
166 Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) {
167 assert(BM == 0 && BPA == 0 && "Unexpected Internal State");
168 Value *Res = GetValueAtEndOfBlockInternal(BB);
169 assert(BM == 0 && BPA == 0 && "Unexpected Internal State");
173 /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that
174 /// is live in the middle of the specified block.
176 /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one
177 /// important case: if there is a definition of the rewritten value after the
178 /// 'use' in BB. Consider code like this:
184 /// br Cond, SomeBB, OutBB
186 /// In this case, there are two values (X1 and X2) added to the AvailableVals
187 /// set by the client of the rewriter, and those values are both live out of
188 /// their respective blocks. However, the use of X happens in the *middle* of
189 /// a block. Because of this, we need to insert a new PHI node in SomeBB to
190 /// merge the appropriate values, and this value isn't live out of the block.
192 Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) {
193 // If there is no definition of the renamed variable in this block, just use
194 // GetValueAtEndOfBlock to do our work.
195 if (!HasValueForBlock(BB))
196 return GetValueAtEndOfBlock(BB);
198 // Otherwise, we have the hard case. Get the live-in values for each
200 SmallVector<std::pair<BasicBlock*, Value*>, 8> PredValues;
201 Value *SingularValue = 0;
203 // We can get our predecessor info by walking the pred_iterator list, but it
204 // is relatively slow. If we already have PHI nodes in this block, walk one
205 // of them to get the predecessor list instead.
206 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) {
207 for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) {
208 BasicBlock *PredBB = SomePhi->getIncomingBlock(i);
209 Value *PredVal = GetValueAtEndOfBlock(PredBB);
210 PredValues.push_back(std::make_pair(PredBB, PredVal));
212 // Compute SingularValue.
214 SingularValue = PredVal;
215 else if (PredVal != SingularValue)
219 bool isFirstPred = true;
220 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
221 BasicBlock *PredBB = *PI;
222 Value *PredVal = GetValueAtEndOfBlock(PredBB);
223 PredValues.push_back(std::make_pair(PredBB, PredVal));
225 // Compute SingularValue.
227 SingularValue = PredVal;
229 } else if (PredVal != SingularValue)
234 // If there are no predecessors, just return undef.
235 if (PredValues.empty())
236 return UndefValue::get(PrototypeValue->getType());
238 // Otherwise, if all the merged values are the same, just use it.
239 if (SingularValue != 0)
240 return SingularValue;
242 // Otherwise, we do need a PHI.
243 if (Value *ExistingPHI = GetExistingPHI(BB, PredValues.begin(),
247 // Ok, we have no way out, insert a new one now.
248 PHINode *InsertedPHI = PHINode::Create(PrototypeValue->getType(),
249 PrototypeValue->getName(),
251 InsertedPHI->reserveOperandSpace(PredValues.size());
253 // Fill in all the predecessors of the PHI.
254 for (unsigned i = 0, e = PredValues.size(); i != e; ++i)
255 InsertedPHI->addIncoming(PredValues[i].second, PredValues[i].first);
257 // See if the PHI node can be merged to a single value. This can happen in
258 // loop cases when we get a PHI of itself and one other value.
259 if (Value *ConstVal = InsertedPHI->hasConstantValue()) {
260 InsertedPHI->eraseFromParent();
264 // If the client wants to know about all new instructions, tell it.
265 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
267 DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");
271 /// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes,
272 /// which use their value in the corresponding predecessor.
273 void SSAUpdater::RewriteUse(Use &U) {
274 Instruction *User = cast<Instruction>(U.getUser());
277 if (PHINode *UserPN = dyn_cast<PHINode>(User))
278 V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
280 V = GetValueInMiddleOfBlock(User->getParent());
285 /// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry
286 /// for the specified BB and if so, return it. If not, construct SSA form by
287 /// first calculating the required placement of PHIs and then inserting new
288 /// PHIs where needed.
289 Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {
290 AvailableValsTy &AvailableVals = getAvailableVals(AV);
291 if (Value *V = AvailableVals[BB])
294 // Pool allocation used internally by GetValueAtEndOfBlock.
295 BumpPtrAllocator AllocatorObj;
300 BBInfo *Info = new (AllocatorObj) BBInfo(BB, 0, &AllocatorObj);
304 unsigned Counter = 1;
307 FindPHIPlacement(BB, Info, Changed, Counter);
311 FindAvailableVal(BB, Info, Counter);
315 return Info->AvailableVal;
318 /// FindPHIPlacement - Recursively visit the predecessors of a block to find
319 /// the reaching definition for each predecessor and then determine whether
320 /// a PHI is needed in this block.
321 void SSAUpdater::FindPHIPlacement(BasicBlock *BB, BBInfo *Info, bool &Changed,
323 AvailableValsTy &AvailableVals = getAvailableVals(AV);
324 BBMapTy *BBMap = getBBMap(BM);
325 BumpPtrAllocator *Allocator = getAllocator(BPA);
326 bool BBNeedsPHI = false;
327 BasicBlock *SamePredDefBB = 0;
329 // If there are no predecessors, then we must have found an unreachable
330 // block. Treat it as a definition with 'undef'.
331 if (Info->NumPreds == 0) {
332 Info->AvailableVal = UndefValue::get(PrototypeValue->getType());
337 Info->Counter = Counter;
338 for (unsigned pi = 0; pi != Info->NumPreds; ++pi) {
339 BasicBlock *Pred = Info->Preds[pi];
340 BBMapTy::value_type &BBMapBucket = BBMap->FindAndConstruct(Pred);
341 if (!BBMapBucket.second) {
342 Value *PredVal = AvailableVals.lookup(Pred);
343 BBMapBucket.second = new (*Allocator) BBInfo(Pred, PredVal, Allocator);
345 BBInfo *PredInfo = BBMapBucket.second;
346 BasicBlock *DefBB = 0;
347 if (!PredInfo->AvailableVal) {
348 if (PredInfo->Counter != Counter)
349 FindPHIPlacement(Pred, PredInfo, Changed, Counter);
351 // Ignore back edges where the value is not yet known.
352 if (!PredInfo->DefBB)
355 DefBB = PredInfo->DefBB;
358 SamePredDefBB = DefBB;
359 else if (DefBB != SamePredDefBB)
363 BasicBlock *NewDefBB = (BBNeedsPHI ? BB : SamePredDefBB);
364 if (Info->DefBB != NewDefBB) {
366 Info->DefBB = NewDefBB;
370 /// FindAvailableVal - If this block requires a PHI, first check if an existing
371 /// PHI matches the PHI placement and reaching definitions computed earlier,
372 /// and if not, create a new PHI. Visit all the block's predecessors to
373 /// calculate the available value for each one and fill in the incoming values
375 void SSAUpdater::FindAvailableVal(BasicBlock *BB, BBInfo *Info,
377 if (Info->AvailableVal || Info->Counter == Counter)
380 AvailableValsTy &AvailableVals = getAvailableVals(AV);
381 BBMapTy *BBMap = getBBMap(BM);
383 // Check if there needs to be a PHI in BB.
385 if (Info->DefBB == BB) {
386 // Look for an existing PHI.
387 FindExistingPHI(BB, Info);
388 if (!Info->AvailableVal) {
389 NewPHI = PHINode::Create(PrototypeValue->getType(),
390 PrototypeValue->getName(), &BB->front());
391 NewPHI->reserveOperandSpace(Info->NumPreds);
392 Info->AvailableVal = NewPHI;
393 AvailableVals[BB] = NewPHI;
397 // Iterate through the block's predecessors.
398 Info->Counter = Counter;
399 for (unsigned pi = 0; pi != Info->NumPreds; ++pi) {
400 BasicBlock *Pred = Info->Preds[pi];
401 BBInfo *PredInfo = (*BBMap)[Pred];
402 FindAvailableVal(Pred, PredInfo, Counter);
404 // Skip to the nearest preceding definition.
405 if (PredInfo->DefBB != Pred)
406 PredInfo = (*BBMap)[PredInfo->DefBB];
407 NewPHI->addIncoming(PredInfo->AvailableVal, Pred);
408 } else if (!Info->AvailableVal)
409 Info->AvailableVal = PredInfo->AvailableVal;
413 DEBUG(dbgs() << " Inserted PHI: " << *NewPHI << "\n");
415 // If the client wants to know about all new instructions, tell it.
416 if (InsertedPHIs) InsertedPHIs->push_back(NewPHI);
420 /// FindExistingPHI - Look through the PHI nodes in a block to see if any of
421 /// them match what is needed.
422 void SSAUpdater::FindExistingPHI(BasicBlock *BB, BBInfo *Info) {
424 for (BasicBlock::iterator It = BB->begin();
425 (SomePHI = dyn_cast<PHINode>(It)); ++It) {
426 if (CheckIfPHIMatches(BB, Info, SomePHI)) {
427 RecordMatchingPHI(BB, Info, SomePHI);
430 ClearPHITags(SomePHI);
434 /// CheckIfPHIMatches - Check if Val is a PHI node in block BB that matches
435 /// the placement and values in the BBMap.
436 bool SSAUpdater::CheckIfPHIMatches(BasicBlock *BB, BBInfo *Info, Value *Val) {
437 if (Info->AvailableVal)
438 return Val == Info->AvailableVal;
440 // Check if Val is a PHI in this block.
441 PHINode *PHI = dyn_cast<PHINode>(Val);
442 if (!PHI || PHI->getParent() != BB)
445 // If this block has already been visited, check if this PHI matches.
447 return PHI == Info->PHITag;
451 // Iterate through the predecessors.
452 BBMapTy *BBMap = getBBMap(BM);
453 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
454 BasicBlock *Pred = PHI->getIncomingBlock(i);
455 Value *IncomingVal = PHI->getIncomingValue(i);
456 BBInfo *PredInfo = (*BBMap)[Pred];
457 // Skip to the nearest preceding definition.
458 if (PredInfo->DefBB != Pred) {
459 Pred = PredInfo->DefBB;
460 PredInfo = (*BBMap)[Pred];
462 if (!CheckIfPHIMatches(Pred, PredInfo, IncomingVal)) {
470 /// RecordMatchingPHI - For a PHI node that matches, record it in both the
471 /// BBMap and the AvailableVals mapping. Recursively record its input PHIs
473 void SSAUpdater::RecordMatchingPHI(BasicBlock *BB, BBInfo *Info, PHINode *PHI) {
474 if (!Info || Info->AvailableVal)
478 AvailableValsTy &AvailableVals = getAvailableVals(AV);
479 AvailableVals[BB] = PHI;
480 Info->AvailableVal = PHI;
482 // Iterate through the predecessors.
483 BBMapTy *BBMap = getBBMap(BM);
484 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
485 PHINode *PHIVal = dyn_cast<PHINode>(PHI->getIncomingValue(i));
486 if (!PHIVal) continue;
487 BasicBlock *Pred = PHIVal->getParent();
488 RecordMatchingPHI(Pred, (*BBMap)[Pred], PHIVal);
492 /// ClearPHITags - When one of the existing PHI nodes fails to match, clear
493 /// the PHITag values that were stored in the BBMap when checking to see if
495 void SSAUpdater::ClearPHITags(PHINode *PHI) {
496 BBMapTy *BBMap = getBBMap(BM);
497 SmallVector<PHINode*, 20> WorkList;
498 WorkList.push_back(PHI);
500 while (!WorkList.empty()) {
501 PHI = WorkList.pop_back_val();
502 BasicBlock *BB = PHI->getParent();
503 BBInfo *Info = (*BBMap)[BB];
504 if (!Info || Info->AvailableVal || !Info->PHITag)
510 // Iterate through the PHI's incoming values.
511 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
512 PHINode *IncomingVal = dyn_cast<PHINode>(PHI->getIncomingValue(i));
513 if (!IncomingVal) continue;
514 WorkList.push_back(IncomingVal);