SSAUpdater.cpp revision a0c6057061be055faa542d05b2213f2bd779e160
1//===- SSAUpdater.cpp - Unstructured SSA Update Tool ----------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the SSAUpdater class. 11// 12//===----------------------------------------------------------------------===// 13 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" 22using namespace llvm; 23 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. 27class SSAUpdater::BBInfo { 28public: 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. 35 36 BBInfo(BasicBlock *BB, Value *V, BumpPtrAllocator *Allocator); 37}; 38typedef DenseMap<BasicBlock*, SSAUpdater::BBInfo*> BBMapTy; 39 40SSAUpdater::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. 44 if (V) { 45 DefBB = BB; 46 return; 47 } 48 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); 59 return; 60 } 61 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); 67 ++NumPreds; 68 } 69 Preds = static_cast<BasicBlock**> 70 (Allocator->Allocate(NumPreds * sizeof(BasicBlock*), 71 AlignOf<BasicBlock*>::Alignment)); 72 memcpy(Preds, TmpPreds.data(), NumPreds * sizeof(BasicBlock*)); 73} 74 75typedef DenseMap<BasicBlock*, Value*> AvailableValsTy; 76static AvailableValsTy &getAvailableVals(void *AV) { 77 return *static_cast<AvailableValsTy*>(AV); 78} 79 80static BBMapTy *getBBMap(void *BM) { 81 return static_cast<BBMapTy*>(BM); 82} 83 84static BumpPtrAllocator *getAllocator(void *BPA) { 85 return static_cast<BumpPtrAllocator*>(BPA); 86} 87 88SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI) 89 : AV(0), PrototypeValue(0), BM(0), BPA(0), InsertedPHIs(NewPHI) {} 90 91SSAUpdater::~SSAUpdater() { 92 delete &getAvailableVals(AV); 93} 94 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. 97void SSAUpdater::Initialize(Value *ProtoValue) { 98 if (AV == 0) 99 AV = new AvailableValsTy(); 100 else 101 getAvailableVals(AV).clear(); 102 PrototypeValue = ProtoValue; 103} 104 105/// HasValueForBlock - Return true if the SSAUpdater already has a value for 106/// the specified block. 107bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const { 108 return getAvailableVals(AV).count(BB); 109} 110 111/// AddAvailableValue - Indicate that a rewritten value is available in the 112/// specified block with the specified value. 113void 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; 118} 119 120/// IsEquivalentPHI - Check if PHI has the same incoming value as specified 121/// in ValueMapping for each predecessor block. 122static bool IsEquivalentPHI(PHINode *PHI, 123 DenseMap<BasicBlock*, Value*> &ValueMapping) { 124 unsigned PHINumValues = PHI->getNumIncomingValues(); 125 if (PHINumValues != ValueMapping.size()) 126 return false; 127 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)) { 132 return false; 133 } 134 135 return true; 136} 137 138/// GetExistingPHI - Check if BB already contains a phi node that is equivalent 139/// to the specified mapping from predecessor blocks to incoming values. 140static Value *GetExistingPHI(BasicBlock *BB, 141 DenseMap<BasicBlock*, Value*> &ValueMapping) { 142 PHINode *SomePHI; 143 for (BasicBlock::iterator It = BB->begin(); 144 (SomePHI = dyn_cast<PHINode>(It)); ++It) { 145 if (IsEquivalentPHI(SomePHI, ValueMapping)) 146 return SomePHI; 147 } 148 return 0; 149} 150 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. 154template<typename InputIt> 155static Value *GetExistingPHI(BasicBlock *BB, const InputIt &I, 156 const InputIt &E) { 157 // Avoid create the mapping if BB has no phi nodes at all. 158 if (!isa<PHINode>(BB->begin())) 159 return 0; 160 DenseMap<BasicBlock*, Value*> ValueMapping(I, E); 161 return GetExistingPHI(BB, ValueMapping); 162} 163 164/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is 165/// live at the end of the specified block. 166Value *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"); 170 return Res; 171} 172 173/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that 174/// is live in the middle of the specified block. 175/// 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: 179/// 180/// X1 = ... 181/// SomeBB: 182/// use(X) 183/// X2 = ... 184/// br Cond, SomeBB, OutBB 185/// 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. 191/// 192Value *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); 197 198 // Otherwise, we have the hard case. Get the live-in values for each 199 // predecessor. 200 SmallVector<std::pair<BasicBlock*, Value*>, 8> PredValues; 201 Value *SingularValue = 0; 202 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)); 211 212 // Compute SingularValue. 213 if (i == 0) 214 SingularValue = PredVal; 215 else if (PredVal != SingularValue) 216 SingularValue = 0; 217 } 218 } else { 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)); 224 225 // Compute SingularValue. 226 if (isFirstPred) { 227 SingularValue = PredVal; 228 isFirstPred = false; 229 } else if (PredVal != SingularValue) 230 SingularValue = 0; 231 } 232 } 233 234 // If there are no predecessors, just return undef. 235 if (PredValues.empty()) 236 return UndefValue::get(PrototypeValue->getType()); 237 238 // Otherwise, if all the merged values are the same, just use it. 239 if (SingularValue != 0) 240 return SingularValue; 241 242 // Otherwise, we do need a PHI. 243 if (Value *ExistingPHI = GetExistingPHI(BB, PredValues.begin(), 244 PredValues.end())) 245 return ExistingPHI; 246 247 // Ok, we have no way out, insert a new one now. 248 PHINode *InsertedPHI = PHINode::Create(PrototypeValue->getType(), 249 PrototypeValue->getName(), 250 &BB->front()); 251 InsertedPHI->reserveOperandSpace(PredValues.size()); 252 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); 256 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(); 261 return ConstVal; 262 } 263 264 // If the client wants to know about all new instructions, tell it. 265 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 266 267 DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); 268 return InsertedPHI; 269} 270 271/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, 272/// which use their value in the corresponding predecessor. 273void SSAUpdater::RewriteUse(Use &U) { 274 Instruction *User = cast<Instruction>(U.getUser()); 275 276 Value *V; 277 if (PHINode *UserPN = dyn_cast<PHINode>(User)) 278 V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U)); 279 else 280 V = GetValueInMiddleOfBlock(User->getParent()); 281 282 U.set(V); 283} 284 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. 289Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) { 290 AvailableValsTy &AvailableVals = getAvailableVals(AV); 291 if (Value *V = AvailableVals[BB]) 292 return V; 293 294 // Pool allocation used internally by GetValueAtEndOfBlock. 295 BumpPtrAllocator AllocatorObj; 296 BBMapTy BBMapObj; 297 BPA = &AllocatorObj; 298 BM = &BBMapObj; 299 300 BBInfo *Info = new (AllocatorObj) BBInfo(BB, 0, &AllocatorObj); 301 BBMapObj[BB] = Info; 302 303 bool Changed; 304 unsigned Counter = 1; 305 do { 306 Changed = false; 307 FindPHIPlacement(BB, Info, Changed, Counter); 308 ++Counter; 309 } while (Changed); 310 311 FindAvailableVal(BB, Info, Counter); 312 313 BPA = 0; 314 BM = 0; 315 return Info->AvailableVal; 316} 317 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. 321void SSAUpdater::FindPHIPlacement(BasicBlock *BB, BBInfo *Info, bool &Changed, 322 unsigned Counter) { 323 AvailableValsTy &AvailableVals = getAvailableVals(AV); 324 BBMapTy *BBMap = getBBMap(BM); 325 BumpPtrAllocator *Allocator = getAllocator(BPA); 326 bool BBNeedsPHI = false; 327 BasicBlock *SamePredDefBB = 0; 328 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()); 333 Info->DefBB = BB; 334 return; 335 } 336 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); 344 } 345 BBInfo *PredInfo = BBMapBucket.second; 346 BasicBlock *DefBB = 0; 347 if (!PredInfo->AvailableVal) { 348 if (PredInfo->Counter != Counter) 349 FindPHIPlacement(Pred, PredInfo, Changed, Counter); 350 351 // Ignore back edges where the value is not yet known. 352 if (!PredInfo->DefBB) 353 continue; 354 } 355 DefBB = PredInfo->DefBB; 356 357 if (!SamePredDefBB) 358 SamePredDefBB = DefBB; 359 else if (DefBB != SamePredDefBB) 360 BBNeedsPHI = true; 361 } 362 363 BasicBlock *NewDefBB = (BBNeedsPHI ? BB : SamePredDefBB); 364 if (Info->DefBB != NewDefBB) { 365 Changed = true; 366 Info->DefBB = NewDefBB; 367 } 368} 369 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 374/// for a new PHI. 375void SSAUpdater::FindAvailableVal(BasicBlock *BB, BBInfo *Info, 376 unsigned Counter) { 377 if (Info->AvailableVal || Info->Counter == Counter) 378 return; 379 380 AvailableValsTy &AvailableVals = getAvailableVals(AV); 381 BBMapTy *BBMap = getBBMap(BM); 382 383 // Check if there needs to be a PHI in BB. 384 PHINode *NewPHI = 0; 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; 394 } 395 } 396 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); 403 if (NewPHI) { 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; 410 } 411 412 if (NewPHI) { 413 DEBUG(dbgs() << " Inserted PHI: " << *NewPHI << "\n"); 414 415 // If the client wants to know about all new instructions, tell it. 416 if (InsertedPHIs) InsertedPHIs->push_back(NewPHI); 417 } 418} 419 420/// FindExistingPHI - Look through the PHI nodes in a block to see if any of 421/// them match what is needed. 422void SSAUpdater::FindExistingPHI(BasicBlock *BB, BBInfo *Info) { 423 PHINode *SomePHI; 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); 428 break; 429 } 430 ClearPHITags(BB, Info, SomePHI); 431 } 432} 433 434/// CheckIfPHIMatches - Check if Val is a PHI node in block BB that matches 435/// the placement and values in the BBMap. 436bool SSAUpdater::CheckIfPHIMatches(BasicBlock *BB, BBInfo *Info, Value *Val) { 437 if (Info->AvailableVal) 438 return Val == Info->AvailableVal; 439 440 // Check if Val is a PHI in this block. 441 PHINode *PHI = dyn_cast<PHINode>(Val); 442 if (!PHI || PHI->getParent() != BB) 443 return false; 444 445 // If this block has already been visited, check if this PHI matches. 446 if (Info->PHITag) 447 return PHI == Info->PHITag; 448 Info->PHITag = PHI; 449 bool IsMatch = true; 450 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]; 461 } 462 if (!CheckIfPHIMatches(Pred, PredInfo, IncomingVal)) { 463 IsMatch = false; 464 break; 465 } 466 } 467 return IsMatch; 468} 469 470/// RecordMatchingPHI - For a PHI node that matches, record it in both the 471/// BBMap and the AvailableVals mapping. Recursively record its input PHIs 472/// as well. 473void SSAUpdater::RecordMatchingPHI(BasicBlock *BB, BBInfo *Info, PHINode *PHI) { 474 if (!Info || Info->AvailableVal) 475 return; 476 477 // Record the PHI. 478 AvailableValsTy &AvailableVals = getAvailableVals(AV); 479 AvailableVals[BB] = PHI; 480 Info->AvailableVal = PHI; 481 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); 489 } 490} 491 492/// ClearPHITags - When one of the existing PHI nodes fails to match, clear 493/// the PHITag values stored in the BBMap while checking to see if it matched. 494void SSAUpdater::ClearPHITags(BasicBlock *BB, BBInfo *Info, PHINode *PHI) { 495 if (!Info || Info->AvailableVal || !Info->PHITag) 496 return; 497 498 // Clear the tag. 499 Info->PHITag = 0; 500 501 // Iterate through the predecessors. 502 BBMapTy *BBMap = getBBMap(BM); 503 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) { 504 PHINode *PHIVal = dyn_cast<PHINode>(PHI->getIncomingValue(i)); 505 if (!PHIVal) continue; 506 BasicBlock *Pred = PHIVal->getParent(); 507 ClearPHITags(Pred, (*BBMap)[Pred], PHIVal); 508 } 509} 510