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