SSAUpdater.cpp revision 4cc3c26834892dd7541a09759da4d31052f8a9f3
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#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" 23using namespace llvm; 24 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. 28class SSAUpdater::BBInfo { 29public: 30 Value *AvailableVal; // Value to use in this block. 31 BasicBlock *DefBB; // Block that defines the available value. 32 unsigned NumPreds; // Number of predecessor blocks. 33 BasicBlock **Preds; // Array[NumPreds] of predecessor blocks. 34 unsigned Counter; // Marker to identify blocks already visited. 35 PHINode *PHITag; // Marker for existing PHIs that match. 36 37 BBInfo(BasicBlock *BB, Value *V, BumpPtrAllocator *Allocator); 38}; 39typedef DenseMap<BasicBlock*, SSAUpdater::BBInfo*> BBMapTy; 40 41SSAUpdater::BBInfo::BBInfo(BasicBlock *BB, Value *V, 42 BumpPtrAllocator *Allocator) 43 : AvailableVal(V), DefBB(0), NumPreds(0), Preds(0), Counter(0), PHITag(0) { 44 // If this block has a known value, don't bother finding its predecessors. 45 if (V) { 46 DefBB = BB; 47 return; 48 } 49 50 // We can get our predecessor info by walking the pred_iterator list, but it 51 // is relatively slow. If we already have PHI nodes in this block, walk one 52 // of them to get the predecessor list instead. 53 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 54 NumPreds = SomePhi->getNumIncomingValues(); 55 Preds = static_cast<BasicBlock**> 56 (Allocator->Allocate(NumPreds * sizeof(BasicBlock*), 57 AlignOf<BasicBlock*>::Alignment)); 58 for (unsigned pi = 0; pi != NumPreds; ++pi) 59 Preds[pi] = SomePhi->getIncomingBlock(pi); 60 return; 61 } 62 63 // Stash the predecessors in a temporary vector until we know how much space 64 // to allocate for them. 65 SmallVector<BasicBlock*, 10> TmpPreds; 66 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 67 TmpPreds.push_back(*PI); 68 ++NumPreds; 69 } 70 Preds = static_cast<BasicBlock**> 71 (Allocator->Allocate(NumPreds * sizeof(BasicBlock*), 72 AlignOf<BasicBlock*>::Alignment)); 73 memcpy(Preds, TmpPreds.data(), NumPreds * sizeof(BasicBlock*)); 74} 75 76typedef DenseMap<BasicBlock*, Value*> AvailableValsTy; 77static AvailableValsTy &getAvailableVals(void *AV) { 78 return *static_cast<AvailableValsTy*>(AV); 79} 80 81static BBMapTy *getBBMap(void *BM) { 82 return static_cast<BBMapTy*>(BM); 83} 84 85static BumpPtrAllocator *getAllocator(void *BPA) { 86 return static_cast<BumpPtrAllocator*>(BPA); 87} 88 89SSAUpdater::SSAUpdater(SmallVectorImpl<PHINode*> *NewPHI) 90 : AV(0), PrototypeValue(0), BM(0), BPA(0), InsertedPHIs(NewPHI) {} 91 92SSAUpdater::~SSAUpdater() { 93 delete &getAvailableVals(AV); 94} 95 96/// Initialize - Reset this object to get ready for a new set of SSA 97/// updates. ProtoValue is the value used to name PHI nodes. 98void SSAUpdater::Initialize(Value *ProtoValue) { 99 if (AV == 0) 100 AV = new AvailableValsTy(); 101 else 102 getAvailableVals(AV).clear(); 103 PrototypeValue = ProtoValue; 104} 105 106/// HasValueForBlock - Return true if the SSAUpdater already has a value for 107/// the specified block. 108bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const { 109 return getAvailableVals(AV).count(BB); 110} 111 112/// AddAvailableValue - Indicate that a rewritten value is available in the 113/// specified block with the specified value. 114void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) { 115 assert(PrototypeValue != 0 && "Need to initialize SSAUpdater"); 116 assert(PrototypeValue->getType() == V->getType() && 117 "All rewritten values must have the same type"); 118 getAvailableVals(AV)[BB] = V; 119} 120 121/// IsEquivalentPHI - Check if PHI has the same incoming value as specified 122/// in ValueMapping for each predecessor block. 123static bool IsEquivalentPHI(PHINode *PHI, 124 DenseMap<BasicBlock*, Value*> &ValueMapping) { 125 unsigned PHINumValues = PHI->getNumIncomingValues(); 126 if (PHINumValues != ValueMapping.size()) 127 return false; 128 129 // Scan the phi to see if it matches. 130 for (unsigned i = 0, e = PHINumValues; i != e; ++i) 131 if (ValueMapping[PHI->getIncomingBlock(i)] != 132 PHI->getIncomingValue(i)) { 133 return false; 134 } 135 136 return true; 137} 138 139/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is 140/// live at the end of the specified block. 141Value *SSAUpdater::GetValueAtEndOfBlock(BasicBlock *BB) { 142 assert(BM == 0 && BPA == 0 && "Unexpected Internal State"); 143 Value *Res = GetValueAtEndOfBlockInternal(BB); 144 assert(BM == 0 && BPA == 0 && "Unexpected Internal State"); 145 return Res; 146} 147 148/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that 149/// is live in the middle of the specified block. 150/// 151/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one 152/// important case: if there is a definition of the rewritten value after the 153/// 'use' in BB. Consider code like this: 154/// 155/// X1 = ... 156/// SomeBB: 157/// use(X) 158/// X2 = ... 159/// br Cond, SomeBB, OutBB 160/// 161/// In this case, there are two values (X1 and X2) added to the AvailableVals 162/// set by the client of the rewriter, and those values are both live out of 163/// their respective blocks. However, the use of X happens in the *middle* of 164/// a block. Because of this, we need to insert a new PHI node in SomeBB to 165/// merge the appropriate values, and this value isn't live out of the block. 166/// 167Value *SSAUpdater::GetValueInMiddleOfBlock(BasicBlock *BB) { 168 // If there is no definition of the renamed variable in this block, just use 169 // GetValueAtEndOfBlock to do our work. 170 if (!HasValueForBlock(BB)) 171 return GetValueAtEndOfBlock(BB); 172 173 // Otherwise, we have the hard case. Get the live-in values for each 174 // predecessor. 175 SmallVector<std::pair<BasicBlock*, Value*>, 8> PredValues; 176 Value *SingularValue = 0; 177 178 // We can get our predecessor info by walking the pred_iterator list, but it 179 // is relatively slow. If we already have PHI nodes in this block, walk one 180 // of them to get the predecessor list instead. 181 if (PHINode *SomePhi = dyn_cast<PHINode>(BB->begin())) { 182 for (unsigned i = 0, e = SomePhi->getNumIncomingValues(); i != e; ++i) { 183 BasicBlock *PredBB = SomePhi->getIncomingBlock(i); 184 Value *PredVal = GetValueAtEndOfBlock(PredBB); 185 PredValues.push_back(std::make_pair(PredBB, PredVal)); 186 187 // Compute SingularValue. 188 if (i == 0) 189 SingularValue = PredVal; 190 else if (PredVal != SingularValue) 191 SingularValue = 0; 192 } 193 } else { 194 bool isFirstPred = true; 195 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 196 BasicBlock *PredBB = *PI; 197 Value *PredVal = GetValueAtEndOfBlock(PredBB); 198 PredValues.push_back(std::make_pair(PredBB, PredVal)); 199 200 // Compute SingularValue. 201 if (isFirstPred) { 202 SingularValue = PredVal; 203 isFirstPred = false; 204 } else if (PredVal != SingularValue) 205 SingularValue = 0; 206 } 207 } 208 209 // If there are no predecessors, just return undef. 210 if (PredValues.empty()) 211 return UndefValue::get(PrototypeValue->getType()); 212 213 // Otherwise, if all the merged values are the same, just use it. 214 if (SingularValue != 0) 215 return SingularValue; 216 217 // Otherwise, we do need a PHI: check to see if we already have one available 218 // in this block that produces the right value. 219 if (isa<PHINode>(BB->begin())) { 220 DenseMap<BasicBlock*, Value*> ValueMapping(PredValues.begin(), 221 PredValues.end()); 222 PHINode *SomePHI; 223 for (BasicBlock::iterator It = BB->begin(); 224 (SomePHI = dyn_cast<PHINode>(It)); ++It) { 225 if (IsEquivalentPHI(SomePHI, ValueMapping)) 226 return SomePHI; 227 } 228 } 229 230 // Ok, we have no way out, insert a new one now. 231 PHINode *InsertedPHI = PHINode::Create(PrototypeValue->getType(), 232 PrototypeValue->getName(), 233 &BB->front()); 234 InsertedPHI->reserveOperandSpace(PredValues.size()); 235 236 // Fill in all the predecessors of the PHI. 237 for (unsigned i = 0, e = PredValues.size(); i != e; ++i) 238 InsertedPHI->addIncoming(PredValues[i].second, PredValues[i].first); 239 240 // See if the PHI node can be merged to a single value. This can happen in 241 // loop cases when we get a PHI of itself and one other value. 242 if (Value *ConstVal = InsertedPHI->hasConstantValue()) { 243 InsertedPHI->eraseFromParent(); 244 return ConstVal; 245 } 246 247 // If the client wants to know about all new instructions, tell it. 248 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); 249 250 DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); 251 return InsertedPHI; 252} 253 254/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, 255/// which use their value in the corresponding predecessor. 256void SSAUpdater::RewriteUse(Use &U) { 257 Instruction *User = cast<Instruction>(U.getUser()); 258 259 Value *V; 260 if (PHINode *UserPN = dyn_cast<PHINode>(User)) 261 V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U)); 262 else 263 V = GetValueInMiddleOfBlock(User->getParent()); 264 265 U.set(V); 266} 267 268/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry 269/// for the specified BB and if so, return it. If not, construct SSA form by 270/// first calculating the required placement of PHIs and then inserting new 271/// PHIs where needed. 272Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) { 273 AvailableValsTy &AvailableVals = getAvailableVals(AV); 274 if (Value *V = AvailableVals[BB]) 275 return V; 276 277 // Pool allocation used internally by GetValueAtEndOfBlock. 278 BumpPtrAllocator AllocatorObj; 279 BBMapTy BBMapObj; 280 BPA = &AllocatorObj; 281 BM = &BBMapObj; 282 283 BBInfo *Info = new (AllocatorObj) BBInfo(BB, 0, &AllocatorObj); 284 BBMapObj[BB] = Info; 285 286 bool Changed; 287 unsigned Counter = 1; 288 do { 289 Changed = false; 290 FindPHIPlacement(BB, Info, Changed, Counter); 291 ++Counter; 292 } while (Changed); 293 294 FindAvailableVal(BB, Info, Counter); 295 296 BPA = 0; 297 BM = 0; 298 return Info->AvailableVal; 299} 300 301/// FindPHIPlacement - Recursively visit the predecessors of a block to find 302/// the reaching definition for each predecessor and then determine whether 303/// a PHI is needed in this block. 304void SSAUpdater::FindPHIPlacement(BasicBlock *BB, BBInfo *Info, bool &Changed, 305 unsigned Counter) { 306 AvailableValsTy &AvailableVals = getAvailableVals(AV); 307 BBMapTy *BBMap = getBBMap(BM); 308 BumpPtrAllocator *Allocator = getAllocator(BPA); 309 bool BBNeedsPHI = false; 310 BasicBlock *SamePredDefBB = 0; 311 312 // If there are no predecessors, then we must have found an unreachable 313 // block. Treat it as a definition with 'undef'. 314 if (Info->NumPreds == 0) { 315 Info->AvailableVal = UndefValue::get(PrototypeValue->getType()); 316 Info->DefBB = BB; 317 return; 318 } 319 320 Info->Counter = Counter; 321 for (unsigned pi = 0; pi != Info->NumPreds; ++pi) { 322 BasicBlock *Pred = Info->Preds[pi]; 323 BBMapTy::value_type &BBMapBucket = BBMap->FindAndConstruct(Pred); 324 if (!BBMapBucket.second) { 325 Value *PredVal = AvailableVals.lookup(Pred); 326 BBMapBucket.second = new (*Allocator) BBInfo(Pred, PredVal, Allocator); 327 } 328 BBInfo *PredInfo = BBMapBucket.second; 329 BasicBlock *DefBB = 0; 330 if (!PredInfo->AvailableVal) { 331 if (PredInfo->Counter != Counter) 332 FindPHIPlacement(Pred, PredInfo, Changed, Counter); 333 334 // Ignore back edges where the value is not yet known. 335 if (!PredInfo->DefBB) 336 continue; 337 } 338 DefBB = PredInfo->DefBB; 339 340 if (!SamePredDefBB) 341 SamePredDefBB = DefBB; 342 else if (DefBB != SamePredDefBB) 343 BBNeedsPHI = true; 344 } 345 346 BasicBlock *NewDefBB = (BBNeedsPHI ? BB : SamePredDefBB); 347 if (Info->DefBB != NewDefBB) { 348 Changed = true; 349 Info->DefBB = NewDefBB; 350 } 351} 352 353/// FindAvailableVal - If this block requires a PHI, first check if an existing 354/// PHI matches the PHI placement and reaching definitions computed earlier, 355/// and if not, create a new PHI. Visit all the block's predecessors to 356/// calculate the available value for each one and fill in the incoming values 357/// for a new PHI. 358void SSAUpdater::FindAvailableVal(BasicBlock *BB, BBInfo *Info, 359 unsigned Counter) { 360 if (Info->AvailableVal || Info->Counter == Counter) 361 return; 362 363 AvailableValsTy &AvailableVals = getAvailableVals(AV); 364 BBMapTy *BBMap = getBBMap(BM); 365 366 // Check if there needs to be a PHI in BB. 367 PHINode *NewPHI = 0; 368 if (Info->DefBB == BB) { 369 // Look for an existing PHI. 370 FindExistingPHI(BB); 371 if (!Info->AvailableVal) { 372 NewPHI = PHINode::Create(PrototypeValue->getType(), 373 PrototypeValue->getName(), &BB->front()); 374 NewPHI->reserveOperandSpace(Info->NumPreds); 375 Info->AvailableVal = NewPHI; 376 AvailableVals[BB] = NewPHI; 377 } 378 } 379 380 // Iterate through the block's predecessors. 381 Info->Counter = Counter; 382 for (unsigned pi = 0; pi != Info->NumPreds; ++pi) { 383 BasicBlock *Pred = Info->Preds[pi]; 384 BBInfo *PredInfo = (*BBMap)[Pred]; 385 FindAvailableVal(Pred, PredInfo, Counter); 386 if (NewPHI) { 387 // Skip to the nearest preceding definition. 388 if (PredInfo->DefBB != Pred) 389 PredInfo = (*BBMap)[PredInfo->DefBB]; 390 NewPHI->addIncoming(PredInfo->AvailableVal, Pred); 391 } else if (!Info->AvailableVal) 392 Info->AvailableVal = PredInfo->AvailableVal; 393 } 394 395 if (NewPHI) { 396 DEBUG(dbgs() << " Inserted PHI: " << *NewPHI << "\n"); 397 398 // If the client wants to know about all new instructions, tell it. 399 if (InsertedPHIs) InsertedPHIs->push_back(NewPHI); 400 } 401} 402 403/// FindExistingPHI - Look through the PHI nodes in a block to see if any of 404/// them match what is needed. 405void SSAUpdater::FindExistingPHI(BasicBlock *BB) { 406 PHINode *SomePHI; 407 for (BasicBlock::iterator It = BB->begin(); 408 (SomePHI = dyn_cast<PHINode>(It)); ++It) { 409 if (CheckIfPHIMatches(SomePHI)) { 410 RecordMatchingPHI(SomePHI); 411 break; 412 } 413 ClearPHITags(SomePHI); 414 } 415} 416 417/// CheckIfPHIMatches - Check if a PHI node matches the placement and values 418/// in the BBMap. 419bool SSAUpdater::CheckIfPHIMatches(PHINode *PHI) { 420 BBMapTy *BBMap = getBBMap(BM); 421 SmallVector<PHINode*, 20> WorkList; 422 WorkList.push_back(PHI); 423 424 // Mark that the block containing this PHI has been visited. 425 (*BBMap)[PHI->getParent()]->PHITag = PHI; 426 427 while (!WorkList.empty()) { 428 PHI = WorkList.pop_back_val(); 429 430 // Iterate through the PHI's incoming values. 431 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) { 432 Value *IncomingVal = PHI->getIncomingValue(i); 433 BasicBlock *Pred = PHI->getIncomingBlock(i); 434 BBInfo *PredInfo = (*BBMap)[Pred]; 435 // Skip to the nearest preceding definition. 436 if (PredInfo->DefBB != Pred) { 437 Pred = PredInfo->DefBB; 438 PredInfo = (*BBMap)[Pred]; 439 } 440 441 // Check if it matches the expected value. 442 if (PredInfo->AvailableVal) { 443 if (IncomingVal == PredInfo->AvailableVal) 444 continue; 445 return false; 446 } 447 448 // Check if the value is a PHI in the correct block. 449 PHINode *IncomingPHIVal = dyn_cast<PHINode>(IncomingVal); 450 if (!IncomingPHIVal || IncomingPHIVal->getParent() != Pred) 451 return false; 452 453 // If this block has already been visited, check if this PHI matches. 454 if (PredInfo->PHITag) { 455 if (IncomingPHIVal == PredInfo->PHITag) 456 continue; 457 return false; 458 } 459 PredInfo->PHITag = IncomingPHIVal; 460 461 WorkList.push_back(IncomingPHIVal); 462 } 463 } 464 return true; 465} 466 467/// RecordMatchingPHI - For a PHI node that matches, record it and its input 468/// PHIs in both the BBMap and the AvailableVals mapping. 469void SSAUpdater::RecordMatchingPHI(PHINode *PHI) { 470 BBMapTy *BBMap = getBBMap(BM); 471 AvailableValsTy &AvailableVals = getAvailableVals(AV); 472 SmallVector<PHINode*, 20> WorkList; 473 WorkList.push_back(PHI); 474 475 // Record this PHI. 476 BasicBlock *BB = PHI->getParent(); 477 AvailableVals[BB] = PHI; 478 (*BBMap)[BB]->AvailableVal = PHI; 479 480 while (!WorkList.empty()) { 481 PHI = WorkList.pop_back_val(); 482 483 // Iterate through the PHI's incoming values. 484 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) { 485 PHINode *IncomingPHIVal = dyn_cast<PHINode>(PHI->getIncomingValue(i)); 486 if (!IncomingPHIVal) continue; 487 BB = IncomingPHIVal->getParent(); 488 BBInfo *Info = (*BBMap)[BB]; 489 if (!Info || Info->AvailableVal) 490 continue; 491 492 // Record the PHI and add it to the worklist. 493 AvailableVals[BB] = IncomingPHIVal; 494 Info->AvailableVal = IncomingPHIVal; 495 WorkList.push_back(IncomingPHIVal); 496 } 497 } 498} 499 500/// ClearPHITags - When one of the existing PHI nodes fails to match, clear 501/// the PHITag values that were stored in the BBMap when checking to see if 502/// it matched. 503void SSAUpdater::ClearPHITags(PHINode *PHI) { 504 BBMapTy *BBMap = getBBMap(BM); 505 SmallVector<PHINode*, 20> WorkList; 506 WorkList.push_back(PHI); 507 508 // Clear the tag for this PHI. 509 (*BBMap)[PHI->getParent()]->PHITag = 0; 510 511 while (!WorkList.empty()) { 512 PHI = WorkList.pop_back_val(); 513 514 // Iterate through the PHI's incoming values. 515 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) { 516 PHINode *IncomingPHIVal = dyn_cast<PHINode>(PHI->getIncomingValue(i)); 517 if (!IncomingPHIVal) continue; 518 BasicBlock *BB = IncomingPHIVal->getParent(); 519 BBInfo *Info = (*BBMap)[BB]; 520 if (!Info || Info->AvailableVal || !Info->PHITag) 521 continue; 522 523 // Clear the tag and add the PHI to the worklist. 524 Info->PHITag = 0; 525 WorkList.push_back(IncomingPHIVal); 526 } 527 } 528} 529