PromoteMemoryToRegister.cpp revision 321a813c536e2f1f2f05bbe78a7fbf64046f0557
1//===- PromoteMemoryToRegister.cpp - Convert allocas to registers ---------===// 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 promotes memory references to be register references. It promotes 11// alloca instructions which only have loads and stores as uses. An alloca is 12// transformed by using dominator frontiers to place PHI nodes, then traversing 13// the function in depth-first order to rewrite loads and stores as appropriate. 14// This is just the standard SSA construction algorithm to construct "pruned" 15// SSA form. 16// 17//===----------------------------------------------------------------------===// 18 19#define DEBUG_TYPE "mem2reg" 20#include "llvm/Transforms/Utils/PromoteMemToReg.h" 21#include "llvm/Constants.h" 22#include "llvm/DerivedTypes.h" 23#include "llvm/Function.h" 24#include "llvm/Instructions.h" 25#include "llvm/IntrinsicInst.h" 26#include "llvm/Analysis/Dominators.h" 27#include "llvm/Analysis/AliasSetTracker.h" 28#include "llvm/ADT/DenseMap.h" 29#include "llvm/ADT/SmallPtrSet.h" 30#include "llvm/ADT/SmallVector.h" 31#include "llvm/ADT/Statistic.h" 32#include "llvm/ADT/STLExtras.h" 33#include "llvm/Support/CFG.h" 34#include <algorithm> 35using namespace llvm; 36 37STATISTIC(NumLocalPromoted, "Number of alloca's promoted within one block"); 38STATISTIC(NumSingleStore, "Number of alloca's promoted with a single store"); 39STATISTIC(NumDeadAlloca, "Number of dead alloca's removed"); 40STATISTIC(NumPHIInsert, "Number of PHI nodes inserted"); 41 42namespace llvm { 43template<> 44struct DenseMapInfo<std::pair<BasicBlock*, unsigned> > { 45 typedef std::pair<BasicBlock*, unsigned> EltTy; 46 static inline EltTy getEmptyKey() { 47 return EltTy(reinterpret_cast<BasicBlock*>(-1), ~0U); 48 } 49 static inline EltTy getTombstoneKey() { 50 return EltTy(reinterpret_cast<BasicBlock*>(-2), 0U); 51 } 52 static unsigned getHashValue(const std::pair<BasicBlock*, unsigned> &Val) { 53 return DenseMapInfo<void*>::getHashValue(Val.first) + Val.second*2; 54 } 55 static bool isEqual(const EltTy &LHS, const EltTy &RHS) { 56 return LHS == RHS; 57 } 58}; 59} 60 61/// isAllocaPromotable - Return true if this alloca is legal for promotion. 62/// This is true if there are only loads and stores to the alloca. 63/// 64bool llvm::isAllocaPromotable(const AllocaInst *AI) { 65 // FIXME: If the memory unit is of pointer or integer type, we can permit 66 // assignments to subsections of the memory unit. 67 68 // Only allow direct and non-volatile loads and stores... 69 for (Value::use_const_iterator UI = AI->use_begin(), UE = AI->use_end(); 70 UI != UE; ++UI) // Loop over all of the uses of the alloca 71 if (const LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 72 if (LI->isVolatile()) 73 return false; 74 } else if (const StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 75 if (SI->getOperand(0) == AI) 76 return false; // Don't allow a store OF the AI, only INTO the AI. 77 if (SI->isVolatile()) 78 return false; 79 } else if (const BitCastInst *BC = dyn_cast<BitCastInst>(*UI)) { 80 // A bitcast that does not feed into debug info inhibits promotion. 81 if (!BC->hasOneUse() || !isa<DbgInfoIntrinsic>(*BC->use_begin())) 82 return false; 83 // If the only use is by debug info, this alloca will not exist in 84 // non-debug code, so don't try to promote; this ensures the same 85 // codegen with debug info. Otherwise, debug info should not 86 // inhibit promotion (but we must examine other uses). 87 if (AI->hasOneUse()) 88 return false; 89 } else { 90 return false; 91 } 92 93 return true; 94} 95 96namespace { 97 struct AllocaInfo; 98 99 // Data package used by RenamePass() 100 class RenamePassData { 101 public: 102 typedef std::vector<Value *> ValVector; 103 104 RenamePassData() : BB(NULL), Pred(NULL), Values() {} 105 RenamePassData(BasicBlock *B, BasicBlock *P, 106 const ValVector &V) : BB(B), Pred(P), Values(V) {} 107 BasicBlock *BB; 108 BasicBlock *Pred; 109 ValVector Values; 110 111 void swap(RenamePassData &RHS) { 112 std::swap(BB, RHS.BB); 113 std::swap(Pred, RHS.Pred); 114 Values.swap(RHS.Values); 115 } 116 }; 117 118 /// LargeBlockInfo - This assigns and keeps a per-bb relative ordering of 119 /// load/store instructions in the block that directly load or store an alloca. 120 /// 121 /// This functionality is important because it avoids scanning large basic 122 /// blocks multiple times when promoting many allocas in the same block. 123 class LargeBlockInfo { 124 /// InstNumbers - For each instruction that we track, keep the index of the 125 /// instruction. The index starts out as the number of the instruction from 126 /// the start of the block. 127 DenseMap<const Instruction *, unsigned> InstNumbers; 128 public: 129 130 /// isInterestingInstruction - This code only looks at accesses to allocas. 131 static bool isInterestingInstruction(const Instruction *I) { 132 return (isa<LoadInst>(I) && isa<AllocaInst>(I->getOperand(0))) || 133 (isa<StoreInst>(I) && isa<AllocaInst>(I->getOperand(1))); 134 } 135 136 /// getInstructionIndex - Get or calculate the index of the specified 137 /// instruction. 138 unsigned getInstructionIndex(const Instruction *I) { 139 assert(isInterestingInstruction(I) && 140 "Not a load/store to/from an alloca?"); 141 142 // If we already have this instruction number, return it. 143 DenseMap<const Instruction *, unsigned>::iterator It = InstNumbers.find(I); 144 if (It != InstNumbers.end()) return It->second; 145 146 // Scan the whole block to get the instruction. This accumulates 147 // information for every interesting instruction in the block, in order to 148 // avoid gratuitus rescans. 149 const BasicBlock *BB = I->getParent(); 150 unsigned InstNo = 0; 151 for (BasicBlock::const_iterator BBI = BB->begin(), E = BB->end(); 152 BBI != E; ++BBI) 153 if (isInterestingInstruction(BBI)) 154 InstNumbers[BBI] = InstNo++; 155 It = InstNumbers.find(I); 156 157 assert(It != InstNumbers.end() && "Didn't insert instruction?"); 158 return It->second; 159 } 160 161 void deleteValue(const Instruction *I) { 162 InstNumbers.erase(I); 163 } 164 165 void clear() { 166 InstNumbers.clear(); 167 } 168 }; 169 170 struct PromoteMem2Reg { 171 /// Allocas - The alloca instructions being promoted. 172 /// 173 std::vector<AllocaInst*> Allocas; 174 DominatorTree &DT; 175 DominanceFrontier &DF; 176 177 /// AST - An AliasSetTracker object to update. If null, don't update it. 178 /// 179 AliasSetTracker *AST; 180 181 /// AllocaLookup - Reverse mapping of Allocas. 182 /// 183 std::map<AllocaInst*, unsigned> AllocaLookup; 184 185 /// NewPhiNodes - The PhiNodes we're adding. 186 /// 187 DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*> NewPhiNodes; 188 189 /// PhiToAllocaMap - For each PHI node, keep track of which entry in Allocas 190 /// it corresponds to. 191 DenseMap<PHINode*, unsigned> PhiToAllocaMap; 192 193 /// PointerAllocaValues - If we are updating an AliasSetTracker, then for 194 /// each alloca that is of pointer type, we keep track of what to copyValue 195 /// to the inserted PHI nodes here. 196 /// 197 std::vector<Value*> PointerAllocaValues; 198 199 /// Visited - The set of basic blocks the renamer has already visited. 200 /// 201 SmallPtrSet<BasicBlock*, 16> Visited; 202 203 /// BBNumbers - Contains a stable numbering of basic blocks to avoid 204 /// non-determinstic behavior. 205 DenseMap<BasicBlock*, unsigned> BBNumbers; 206 207 /// BBNumPreds - Lazily compute the number of predecessors a block has. 208 DenseMap<const BasicBlock*, unsigned> BBNumPreds; 209 public: 210 PromoteMem2Reg(const std::vector<AllocaInst*> &A, DominatorTree &dt, 211 DominanceFrontier &df, AliasSetTracker *ast) 212 : Allocas(A), DT(dt), DF(df), AST(ast) {} 213 214 void run(); 215 216 /// properlyDominates - Return true if I1 properly dominates I2. 217 /// 218 bool properlyDominates(Instruction *I1, Instruction *I2) const { 219 if (InvokeInst *II = dyn_cast<InvokeInst>(I1)) 220 I1 = II->getNormalDest()->begin(); 221 return DT.properlyDominates(I1->getParent(), I2->getParent()); 222 } 223 224 /// dominates - Return true if BB1 dominates BB2 using the DominatorTree. 225 /// 226 bool dominates(BasicBlock *BB1, BasicBlock *BB2) const { 227 return DT.dominates(BB1, BB2); 228 } 229 230 private: 231 void RemoveFromAllocasList(unsigned &AllocaIdx) { 232 Allocas[AllocaIdx] = Allocas.back(); 233 Allocas.pop_back(); 234 --AllocaIdx; 235 } 236 237 unsigned getNumPreds(const BasicBlock *BB) { 238 unsigned &NP = BBNumPreds[BB]; 239 if (NP == 0) 240 NP = std::distance(pred_begin(BB), pred_end(BB))+1; 241 return NP-1; 242 } 243 244 void DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum, 245 AllocaInfo &Info); 246 void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info, 247 const SmallPtrSet<BasicBlock*, 32> &DefBlocks, 248 SmallPtrSet<BasicBlock*, 32> &LiveInBlocks); 249 250 void RewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info, 251 LargeBlockInfo &LBI); 252 void PromoteSingleBlockAlloca(AllocaInst *AI, AllocaInfo &Info, 253 LargeBlockInfo &LBI); 254 255 256 void RenamePass(BasicBlock *BB, BasicBlock *Pred, 257 RenamePassData::ValVector &IncVals, 258 std::vector<RenamePassData> &Worklist); 259 bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version, 260 SmallPtrSet<PHINode*, 16> &InsertedPHINodes); 261 }; 262 263 struct AllocaInfo { 264 std::vector<BasicBlock*> DefiningBlocks; 265 std::vector<BasicBlock*> UsingBlocks; 266 267 StoreInst *OnlyStore; 268 BasicBlock *OnlyBlock; 269 bool OnlyUsedInOneBlock; 270 271 Value *AllocaPointerVal; 272 273 void clear() { 274 DefiningBlocks.clear(); 275 UsingBlocks.clear(); 276 OnlyStore = 0; 277 OnlyBlock = 0; 278 OnlyUsedInOneBlock = true; 279 AllocaPointerVal = 0; 280 } 281 282 /// AnalyzeAlloca - Scan the uses of the specified alloca, filling in our 283 /// ivars. 284 void AnalyzeAlloca(AllocaInst *AI) { 285 clear(); 286 287 // As we scan the uses of the alloca instruction, keep track of stores, 288 // and decide whether all of the loads and stores to the alloca are within 289 // the same basic block. 290 for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 291 UI != E;) { 292 Instruction *User = cast<Instruction>(*UI++); 293 if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) { 294 // Remove any uses of this alloca in DbgInfoInstrinsics. 295 assert(BC->hasOneUse() && "Unexpected alloca uses!"); 296 DbgInfoIntrinsic *DI = cast<DbgInfoIntrinsic>(*BC->use_begin()); 297 DI->eraseFromParent(); 298 BC->eraseFromParent(); 299 continue; 300 } 301 302 if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 303 // Remember the basic blocks which define new values for the alloca 304 DefiningBlocks.push_back(SI->getParent()); 305 AllocaPointerVal = SI->getOperand(0); 306 OnlyStore = SI; 307 } else { 308 LoadInst *LI = cast<LoadInst>(User); 309 // Otherwise it must be a load instruction, keep track of variable 310 // reads. 311 UsingBlocks.push_back(LI->getParent()); 312 AllocaPointerVal = LI; 313 } 314 315 if (OnlyUsedInOneBlock) { 316 if (OnlyBlock == 0) 317 OnlyBlock = User->getParent(); 318 else if (OnlyBlock != User->getParent()) 319 OnlyUsedInOneBlock = false; 320 } 321 } 322 } 323 }; 324} // end of anonymous namespace 325 326 327void PromoteMem2Reg::run() { 328 Function &F = *DF.getRoot()->getParent(); 329 330 if (AST) PointerAllocaValues.resize(Allocas.size()); 331 332 AllocaInfo Info; 333 LargeBlockInfo LBI; 334 335 for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) { 336 AllocaInst *AI = Allocas[AllocaNum]; 337 338 assert(isAllocaPromotable(AI) && 339 "Cannot promote non-promotable alloca!"); 340 assert(AI->getParent()->getParent() == &F && 341 "All allocas should be in the same function, which is same as DF!"); 342 343 if (AI->use_empty()) { 344 // If there are no uses of the alloca, just delete it now. 345 if (AST) AST->deleteValue(AI); 346 AI->eraseFromParent(); 347 348 // Remove the alloca from the Allocas list, since it has been processed 349 RemoveFromAllocasList(AllocaNum); 350 ++NumDeadAlloca; 351 continue; 352 } 353 354 // Calculate the set of read and write-locations for each alloca. This is 355 // analogous to finding the 'uses' and 'definitions' of each variable. 356 Info.AnalyzeAlloca(AI); 357 358 // If there is only a single store to this value, replace any loads of 359 // it that are directly dominated by the definition with the value stored. 360 if (Info.DefiningBlocks.size() == 1) { 361 RewriteSingleStoreAlloca(AI, Info, LBI); 362 363 // Finally, after the scan, check to see if the store is all that is left. 364 if (Info.UsingBlocks.empty()) { 365 // Remove the (now dead) store and alloca. 366 Info.OnlyStore->eraseFromParent(); 367 LBI.deleteValue(Info.OnlyStore); 368 369 if (AST) AST->deleteValue(AI); 370 AI->eraseFromParent(); 371 LBI.deleteValue(AI); 372 373 // The alloca has been processed, move on. 374 RemoveFromAllocasList(AllocaNum); 375 376 ++NumSingleStore; 377 continue; 378 } 379 } 380 381 // If the alloca is only read and written in one basic block, just perform a 382 // linear sweep over the block to eliminate it. 383 if (Info.OnlyUsedInOneBlock) { 384 PromoteSingleBlockAlloca(AI, Info, LBI); 385 386 // Finally, after the scan, check to see if the stores are all that is 387 // left. 388 if (Info.UsingBlocks.empty()) { 389 390 // Remove the (now dead) stores and alloca. 391 while (!AI->use_empty()) { 392 StoreInst *SI = cast<StoreInst>(AI->use_back()); 393 SI->eraseFromParent(); 394 LBI.deleteValue(SI); 395 } 396 397 if (AST) AST->deleteValue(AI); 398 AI->eraseFromParent(); 399 LBI.deleteValue(AI); 400 401 // The alloca has been processed, move on. 402 RemoveFromAllocasList(AllocaNum); 403 404 ++NumLocalPromoted; 405 continue; 406 } 407 } 408 409 // If we haven't computed a numbering for the BB's in the function, do so 410 // now. 411 if (BBNumbers.empty()) { 412 unsigned ID = 0; 413 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 414 BBNumbers[I] = ID++; 415 } 416 417 // If we have an AST to keep updated, remember some pointer value that is 418 // stored into the alloca. 419 if (AST) 420 PointerAllocaValues[AllocaNum] = Info.AllocaPointerVal; 421 422 // Keep the reverse mapping of the 'Allocas' array for the rename pass. 423 AllocaLookup[Allocas[AllocaNum]] = AllocaNum; 424 425 // At this point, we're committed to promoting the alloca using IDF's, and 426 // the standard SSA construction algorithm. Determine which blocks need PHI 427 // nodes and see if we can optimize out some work by avoiding insertion of 428 // dead phi nodes. 429 DetermineInsertionPoint(AI, AllocaNum, Info); 430 } 431 432 if (Allocas.empty()) 433 return; // All of the allocas must have been trivial! 434 435 LBI.clear(); 436 437 438 // Set the incoming values for the basic block to be null values for all of 439 // the alloca's. We do this in case there is a load of a value that has not 440 // been stored yet. In this case, it will get this null value. 441 // 442 RenamePassData::ValVector Values(Allocas.size()); 443 for (unsigned i = 0, e = Allocas.size(); i != e; ++i) 444 Values[i] = UndefValue::get(Allocas[i]->getAllocatedType()); 445 446 // Walks all basic blocks in the function performing the SSA rename algorithm 447 // and inserting the phi nodes we marked as necessary 448 // 449 std::vector<RenamePassData> RenamePassWorkList; 450 RenamePassWorkList.push_back(RenamePassData(F.begin(), 0, Values)); 451 do { 452 RenamePassData RPD; 453 RPD.swap(RenamePassWorkList.back()); 454 RenamePassWorkList.pop_back(); 455 // RenamePass may add new worklist entries. 456 RenamePass(RPD.BB, RPD.Pred, RPD.Values, RenamePassWorkList); 457 } while (!RenamePassWorkList.empty()); 458 459 // The renamer uses the Visited set to avoid infinite loops. Clear it now. 460 Visited.clear(); 461 462 // Remove the allocas themselves from the function. 463 for (unsigned i = 0, e = Allocas.size(); i != e; ++i) { 464 Instruction *A = Allocas[i]; 465 466 // If there are any uses of the alloca instructions left, they must be in 467 // sections of dead code that were not processed on the dominance frontier. 468 // Just delete the users now. 469 // 470 if (!A->use_empty()) 471 A->replaceAllUsesWith(UndefValue::get(A->getType())); 472 if (AST) AST->deleteValue(A); 473 A->eraseFromParent(); 474 } 475 476 477 // Loop over all of the PHI nodes and see if there are any that we can get 478 // rid of because they merge all of the same incoming values. This can 479 // happen due to undef values coming into the PHI nodes. This process is 480 // iterative, because eliminating one PHI node can cause others to be removed. 481 bool EliminatedAPHI = true; 482 while (EliminatedAPHI) { 483 EliminatedAPHI = false; 484 485 for (DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*>::iterator I = 486 NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E;) { 487 PHINode *PN = I->second; 488 489 // If this PHI node merges one value and/or undefs, get the value. 490 if (Value *V = PN->hasConstantValue(&DT)) { 491 if (AST && isa<PointerType>(PN->getType())) 492 AST->deleteValue(PN); 493 PN->replaceAllUsesWith(V); 494 PN->eraseFromParent(); 495 NewPhiNodes.erase(I++); 496 EliminatedAPHI = true; 497 continue; 498 } 499 ++I; 500 } 501 } 502 503 // At this point, the renamer has added entries to PHI nodes for all reachable 504 // code. Unfortunately, there may be unreachable blocks which the renamer 505 // hasn't traversed. If this is the case, the PHI nodes may not 506 // have incoming values for all predecessors. Loop over all PHI nodes we have 507 // created, inserting undef values if they are missing any incoming values. 508 // 509 for (DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*>::iterator I = 510 NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) { 511 // We want to do this once per basic block. As such, only process a block 512 // when we find the PHI that is the first entry in the block. 513 PHINode *SomePHI = I->second; 514 BasicBlock *BB = SomePHI->getParent(); 515 if (&BB->front() != SomePHI) 516 continue; 517 518 // Only do work here if there the PHI nodes are missing incoming values. We 519 // know that all PHI nodes that were inserted in a block will have the same 520 // number of incoming values, so we can just check any of them. 521 if (SomePHI->getNumIncomingValues() == getNumPreds(BB)) 522 continue; 523 524 // Get the preds for BB. 525 SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB)); 526 527 // Ok, now we know that all of the PHI nodes are missing entries for some 528 // basic blocks. Start by sorting the incoming predecessors for efficient 529 // access. 530 std::sort(Preds.begin(), Preds.end()); 531 532 // Now we loop through all BB's which have entries in SomePHI and remove 533 // them from the Preds list. 534 for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) { 535 // Do a log(n) search of the Preds list for the entry we want. 536 SmallVector<BasicBlock*, 16>::iterator EntIt = 537 std::lower_bound(Preds.begin(), Preds.end(), 538 SomePHI->getIncomingBlock(i)); 539 assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i)&& 540 "PHI node has entry for a block which is not a predecessor!"); 541 542 // Remove the entry 543 Preds.erase(EntIt); 544 } 545 546 // At this point, the blocks left in the preds list must have dummy 547 // entries inserted into every PHI nodes for the block. Update all the phi 548 // nodes in this block that we are inserting (there could be phis before 549 // mem2reg runs). 550 unsigned NumBadPreds = SomePHI->getNumIncomingValues(); 551 BasicBlock::iterator BBI = BB->begin(); 552 while ((SomePHI = dyn_cast<PHINode>(BBI++)) && 553 SomePHI->getNumIncomingValues() == NumBadPreds) { 554 Value *UndefVal = UndefValue::get(SomePHI->getType()); 555 for (unsigned pred = 0, e = Preds.size(); pred != e; ++pred) 556 SomePHI->addIncoming(UndefVal, Preds[pred]); 557 } 558 } 559 560 NewPhiNodes.clear(); 561} 562 563 564/// ComputeLiveInBlocks - Determine which blocks the value is live in. These 565/// are blocks which lead to uses. Knowing this allows us to avoid inserting 566/// PHI nodes into blocks which don't lead to uses (thus, the inserted phi nodes 567/// would be dead). 568void PromoteMem2Reg:: 569ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info, 570 const SmallPtrSet<BasicBlock*, 32> &DefBlocks, 571 SmallPtrSet<BasicBlock*, 32> &LiveInBlocks) { 572 573 // To determine liveness, we must iterate through the predecessors of blocks 574 // where the def is live. Blocks are added to the worklist if we need to 575 // check their predecessors. Start with all the using blocks. 576 SmallVector<BasicBlock*, 64> LiveInBlockWorklist; 577 LiveInBlockWorklist.insert(LiveInBlockWorklist.end(), 578 Info.UsingBlocks.begin(), Info.UsingBlocks.end()); 579 580 // If any of the using blocks is also a definition block, check to see if the 581 // definition occurs before or after the use. If it happens before the use, 582 // the value isn't really live-in. 583 for (unsigned i = 0, e = LiveInBlockWorklist.size(); i != e; ++i) { 584 BasicBlock *BB = LiveInBlockWorklist[i]; 585 if (!DefBlocks.count(BB)) continue; 586 587 // Okay, this is a block that both uses and defines the value. If the first 588 // reference to the alloca is a def (store), then we know it isn't live-in. 589 for (BasicBlock::iterator I = BB->begin(); ; ++I) { 590 if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 591 if (SI->getOperand(1) != AI) continue; 592 593 // We found a store to the alloca before a load. The alloca is not 594 // actually live-in here. 595 LiveInBlockWorklist[i] = LiveInBlockWorklist.back(); 596 LiveInBlockWorklist.pop_back(); 597 --i, --e; 598 break; 599 } 600 601 if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 602 if (LI->getOperand(0) != AI) continue; 603 604 // Okay, we found a load before a store to the alloca. It is actually 605 // live into this block. 606 break; 607 } 608 } 609 } 610 611 // Now that we have a set of blocks where the phi is live-in, recursively add 612 // their predecessors until we find the full region the value is live. 613 while (!LiveInBlockWorklist.empty()) { 614 BasicBlock *BB = LiveInBlockWorklist.pop_back_val(); 615 616 // The block really is live in here, insert it into the set. If already in 617 // the set, then it has already been processed. 618 if (!LiveInBlocks.insert(BB)) 619 continue; 620 621 // Since the value is live into BB, it is either defined in a predecessor or 622 // live into it to. Add the preds to the worklist unless they are a 623 // defining block. 624 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 625 BasicBlock *P = *PI; 626 627 // The value is not live into a predecessor if it defines the value. 628 if (DefBlocks.count(P)) 629 continue; 630 631 // Otherwise it is, add to the worklist. 632 LiveInBlockWorklist.push_back(P); 633 } 634 } 635} 636 637/// DetermineInsertionPoint - At this point, we're committed to promoting the 638/// alloca using IDF's, and the standard SSA construction algorithm. Determine 639/// which blocks need phi nodes and see if we can optimize out some work by 640/// avoiding insertion of dead phi nodes. 641void PromoteMem2Reg::DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum, 642 AllocaInfo &Info) { 643 644 // Unique the set of defining blocks for efficient lookup. 645 SmallPtrSet<BasicBlock*, 32> DefBlocks; 646 DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end()); 647 648 // Determine which blocks the value is live in. These are blocks which lead 649 // to uses. 650 SmallPtrSet<BasicBlock*, 32> LiveInBlocks; 651 ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks); 652 653 // Compute the locations where PhiNodes need to be inserted. Look at the 654 // dominance frontier of EACH basic-block we have a write in. 655 unsigned CurrentVersion = 0; 656 SmallPtrSet<PHINode*, 16> InsertedPHINodes; 657 std::vector<std::pair<unsigned, BasicBlock*> > DFBlocks; 658 while (!Info.DefiningBlocks.empty()) { 659 BasicBlock *BB = Info.DefiningBlocks.back(); 660 Info.DefiningBlocks.pop_back(); 661 662 // Look up the DF for this write, add it to defining blocks. 663 DominanceFrontier::const_iterator it = DF.find(BB); 664 if (it == DF.end()) continue; 665 666 const DominanceFrontier::DomSetType &S = it->second; 667 668 // In theory we don't need the indirection through the DFBlocks vector. 669 // In practice, the order of calling QueuePhiNode would depend on the 670 // (unspecified) ordering of basic blocks in the dominance frontier, 671 // which would give PHI nodes non-determinstic subscripts. Fix this by 672 // processing blocks in order of the occurance in the function. 673 for (DominanceFrontier::DomSetType::const_iterator P = S.begin(), 674 PE = S.end(); P != PE; ++P) { 675 // If the frontier block is not in the live-in set for the alloca, don't 676 // bother processing it. 677 if (!LiveInBlocks.count(*P)) 678 continue; 679 680 DFBlocks.push_back(std::make_pair(BBNumbers[*P], *P)); 681 } 682 683 // Sort by which the block ordering in the function. 684 if (DFBlocks.size() > 1) 685 std::sort(DFBlocks.begin(), DFBlocks.end()); 686 687 for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i) { 688 BasicBlock *BB = DFBlocks[i].second; 689 if (QueuePhiNode(BB, AllocaNum, CurrentVersion, InsertedPHINodes)) 690 Info.DefiningBlocks.push_back(BB); 691 } 692 DFBlocks.clear(); 693 } 694} 695 696/// RewriteSingleStoreAlloca - If there is only a single store to this value, 697/// replace any loads of it that are directly dominated by the definition with 698/// the value stored. 699void PromoteMem2Reg::RewriteSingleStoreAlloca(AllocaInst *AI, 700 AllocaInfo &Info, 701 LargeBlockInfo &LBI) { 702 StoreInst *OnlyStore = Info.OnlyStore; 703 bool StoringGlobalVal = !isa<Instruction>(OnlyStore->getOperand(0)); 704 BasicBlock *StoreBB = OnlyStore->getParent(); 705 int StoreIndex = -1; 706 707 // Clear out UsingBlocks. We will reconstruct it here if needed. 708 Info.UsingBlocks.clear(); 709 710 for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E; ) { 711 Instruction *UserInst = cast<Instruction>(*UI++); 712 if (!isa<LoadInst>(UserInst)) { 713 assert(UserInst == OnlyStore && "Should only have load/stores"); 714 continue; 715 } 716 LoadInst *LI = cast<LoadInst>(UserInst); 717 718 // Okay, if we have a load from the alloca, we want to replace it with the 719 // only value stored to the alloca. We can do this if the value is 720 // dominated by the store. If not, we use the rest of the mem2reg machinery 721 // to insert the phi nodes as needed. 722 if (!StoringGlobalVal) { // Non-instructions are always dominated. 723 if (LI->getParent() == StoreBB) { 724 // If we have a use that is in the same block as the store, compare the 725 // indices of the two instructions to see which one came first. If the 726 // load came before the store, we can't handle it. 727 if (StoreIndex == -1) 728 StoreIndex = LBI.getInstructionIndex(OnlyStore); 729 730 if (unsigned(StoreIndex) > LBI.getInstructionIndex(LI)) { 731 // Can't handle this load, bail out. 732 Info.UsingBlocks.push_back(StoreBB); 733 continue; 734 } 735 736 } else if (LI->getParent() != StoreBB && 737 !dominates(StoreBB, LI->getParent())) { 738 // If the load and store are in different blocks, use BB dominance to 739 // check their relationships. If the store doesn't dom the use, bail 740 // out. 741 Info.UsingBlocks.push_back(LI->getParent()); 742 continue; 743 } 744 } 745 746 // Otherwise, we *can* safely rewrite this load. 747 Value *ReplVal = OnlyStore->getOperand(0); 748 // If the replacement value is the load, this must occur in unreachable 749 // code. 750 if (ReplVal == LI) 751 ReplVal = UndefValue::get(LI->getType()); 752 LI->replaceAllUsesWith(ReplVal); 753 if (AST && isa<PointerType>(LI->getType())) 754 AST->deleteValue(LI); 755 LI->eraseFromParent(); 756 LBI.deleteValue(LI); 757 } 758} 759 760namespace { 761 762/// StoreIndexSearchPredicate - This is a helper predicate used to search by the 763/// first element of a pair. 764struct StoreIndexSearchPredicate { 765 bool operator()(const std::pair<unsigned, StoreInst*> &LHS, 766 const std::pair<unsigned, StoreInst*> &RHS) { 767 return LHS.first < RHS.first; 768 } 769}; 770 771} 772 773/// PromoteSingleBlockAlloca - Many allocas are only used within a single basic 774/// block. If this is the case, avoid traversing the CFG and inserting a lot of 775/// potentially useless PHI nodes by just performing a single linear pass over 776/// the basic block using the Alloca. 777/// 778/// If we cannot promote this alloca (because it is read before it is written), 779/// return true. This is necessary in cases where, due to control flow, the 780/// alloca is potentially undefined on some control flow paths. e.g. code like 781/// this is potentially correct: 782/// 783/// for (...) { if (c) { A = undef; undef = B; } } 784/// 785/// ... so long as A is not used before undef is set. 786/// 787void PromoteMem2Reg::PromoteSingleBlockAlloca(AllocaInst *AI, AllocaInfo &Info, 788 LargeBlockInfo &LBI) { 789 // The trickiest case to handle is when we have large blocks. Because of this, 790 // this code is optimized assuming that large blocks happen. This does not 791 // significantly pessimize the small block case. This uses LargeBlockInfo to 792 // make it efficient to get the index of various operations in the block. 793 794 // Clear out UsingBlocks. We will reconstruct it here if needed. 795 Info.UsingBlocks.clear(); 796 797 // Walk the use-def list of the alloca, getting the locations of all stores. 798 typedef SmallVector<std::pair<unsigned, StoreInst*>, 64> StoresByIndexTy; 799 StoresByIndexTy StoresByIndex; 800 801 for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 802 UI != E; ++UI) 803 if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) 804 StoresByIndex.push_back(std::make_pair(LBI.getInstructionIndex(SI), SI)); 805 806 // If there are no stores to the alloca, just replace any loads with undef. 807 if (StoresByIndex.empty()) { 808 for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;) 809 if (LoadInst *LI = dyn_cast<LoadInst>(*UI++)) { 810 LI->replaceAllUsesWith(UndefValue::get(LI->getType())); 811 if (AST && isa<PointerType>(LI->getType())) 812 AST->deleteValue(LI); 813 LBI.deleteValue(LI); 814 LI->eraseFromParent(); 815 } 816 return; 817 } 818 819 // Sort the stores by their index, making it efficient to do a lookup with a 820 // binary search. 821 std::sort(StoresByIndex.begin(), StoresByIndex.end()); 822 823 // Walk all of the loads from this alloca, replacing them with the nearest 824 // store above them, if any. 825 for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;) { 826 LoadInst *LI = dyn_cast<LoadInst>(*UI++); 827 if (!LI) continue; 828 829 unsigned LoadIdx = LBI.getInstructionIndex(LI); 830 831 // Find the nearest store that has a lower than this load. 832 StoresByIndexTy::iterator I = 833 std::lower_bound(StoresByIndex.begin(), StoresByIndex.end(), 834 std::pair<unsigned, StoreInst*>(LoadIdx, 0), 835 StoreIndexSearchPredicate()); 836 837 // If there is no store before this load, then we can't promote this load. 838 if (I == StoresByIndex.begin()) { 839 // Can't handle this load, bail out. 840 Info.UsingBlocks.push_back(LI->getParent()); 841 continue; 842 } 843 844 // Otherwise, there was a store before this load, the load takes its value. 845 --I; 846 LI->replaceAllUsesWith(I->second->getOperand(0)); 847 if (AST && isa<PointerType>(LI->getType())) 848 AST->deleteValue(LI); 849 LI->eraseFromParent(); 850 LBI.deleteValue(LI); 851 } 852} 853 854 855// QueuePhiNode - queues a phi-node to be added to a basic-block for a specific 856// Alloca returns true if there wasn't already a phi-node for that variable 857// 858bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo, 859 unsigned &Version, 860 SmallPtrSet<PHINode*, 16> &InsertedPHINodes) { 861 // Look up the basic-block in question. 862 PHINode *&PN = NewPhiNodes[std::make_pair(BB, AllocaNo)]; 863 864 // If the BB already has a phi node added for the i'th alloca then we're done! 865 if (PN) return false; 866 867 // Create a PhiNode using the dereferenced type... and add the phi-node to the 868 // BasicBlock. 869 PN = PHINode::Create(Allocas[AllocaNo]->getAllocatedType(), 870 Allocas[AllocaNo]->getName() + "." + Twine(Version++), 871 BB->begin()); 872 ++NumPHIInsert; 873 PhiToAllocaMap[PN] = AllocaNo; 874 PN->reserveOperandSpace(getNumPreds(BB)); 875 876 InsertedPHINodes.insert(PN); 877 878 if (AST && isa<PointerType>(PN->getType())) 879 AST->copyValue(PointerAllocaValues[AllocaNo], PN); 880 881 return true; 882} 883 884// RenamePass - Recursively traverse the CFG of the function, renaming loads and 885// stores to the allocas which we are promoting. IncomingVals indicates what 886// value each Alloca contains on exit from the predecessor block Pred. 887// 888void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred, 889 RenamePassData::ValVector &IncomingVals, 890 std::vector<RenamePassData> &Worklist) { 891NextIteration: 892 // If we are inserting any phi nodes into this BB, they will already be in the 893 // block. 894 if (PHINode *APN = dyn_cast<PHINode>(BB->begin())) { 895 // If we have PHI nodes to update, compute the number of edges from Pred to 896 // BB. 897 if (PhiToAllocaMap.count(APN)) { 898 // We want to be able to distinguish between PHI nodes being inserted by 899 // this invocation of mem2reg from those phi nodes that already existed in 900 // the IR before mem2reg was run. We determine that APN is being inserted 901 // because it is missing incoming edges. All other PHI nodes being 902 // inserted by this pass of mem2reg will have the same number of incoming 903 // operands so far. Remember this count. 904 unsigned NewPHINumOperands = APN->getNumOperands(); 905 906 unsigned NumEdges = 0; 907 for (succ_iterator I = succ_begin(Pred), E = succ_end(Pred); I != E; ++I) 908 if (*I == BB) 909 ++NumEdges; 910 assert(NumEdges && "Must be at least one edge from Pred to BB!"); 911 912 // Add entries for all the phis. 913 BasicBlock::iterator PNI = BB->begin(); 914 do { 915 unsigned AllocaNo = PhiToAllocaMap[APN]; 916 917 // Add N incoming values to the PHI node. 918 for (unsigned i = 0; i != NumEdges; ++i) 919 APN->addIncoming(IncomingVals[AllocaNo], Pred); 920 921 // The currently active variable for this block is now the PHI. 922 IncomingVals[AllocaNo] = APN; 923 924 // Get the next phi node. 925 ++PNI; 926 APN = dyn_cast<PHINode>(PNI); 927 if (APN == 0) break; 928 929 // Verify that it is missing entries. If not, it is not being inserted 930 // by this mem2reg invocation so we want to ignore it. 931 } while (APN->getNumOperands() == NewPHINumOperands); 932 } 933 } 934 935 // Don't revisit blocks. 936 if (!Visited.insert(BB)) return; 937 938 for (BasicBlock::iterator II = BB->begin(); !isa<TerminatorInst>(II); ) { 939 Instruction *I = II++; // get the instruction, increment iterator 940 941 if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 942 AllocaInst *Src = dyn_cast<AllocaInst>(LI->getPointerOperand()); 943 if (!Src) continue; 944 945 std::map<AllocaInst*, unsigned>::iterator AI = AllocaLookup.find(Src); 946 if (AI == AllocaLookup.end()) continue; 947 948 Value *V = IncomingVals[AI->second]; 949 950 // Anything using the load now uses the current value. 951 LI->replaceAllUsesWith(V); 952 if (AST && isa<PointerType>(LI->getType())) 953 AST->deleteValue(LI); 954 BB->getInstList().erase(LI); 955 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 956 // Delete this instruction and mark the name as the current holder of the 957 // value 958 AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand()); 959 if (!Dest) continue; 960 961 std::map<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Dest); 962 if (ai == AllocaLookup.end()) 963 continue; 964 965 // what value were we writing? 966 IncomingVals[ai->second] = SI->getOperand(0); 967 BB->getInstList().erase(SI); 968 } 969 } 970 971 // 'Recurse' to our successors. 972 succ_iterator I = succ_begin(BB), E = succ_end(BB); 973 if (I == E) return; 974 975 // Keep track of the successors so we don't visit the same successor twice 976 SmallPtrSet<BasicBlock*, 8> VisitedSuccs; 977 978 // Handle the first successor without using the worklist. 979 VisitedSuccs.insert(*I); 980 Pred = BB; 981 BB = *I; 982 ++I; 983 984 for (; I != E; ++I) 985 if (VisitedSuccs.insert(*I)) 986 Worklist.push_back(RenamePassData(*I, Pred, IncomingVals)); 987 988 goto NextIteration; 989} 990 991/// PromoteMemToReg - Promote the specified list of alloca instructions into 992/// scalar registers, inserting PHI nodes as appropriate. This function makes 993/// use of DominanceFrontier information. This function does not modify the CFG 994/// of the function at all. All allocas must be from the same function. 995/// 996/// If AST is specified, the specified tracker is updated to reflect changes 997/// made to the IR. 998/// 999void llvm::PromoteMemToReg(const std::vector<AllocaInst*> &Allocas, 1000 DominatorTree &DT, DominanceFrontier &DF, 1001 AliasSetTracker *AST) { 1002 // If there is nothing to do, bail out... 1003 if (Allocas.empty()) return; 1004 1005 PromoteMem2Reg(Allocas, DT, DF, AST).run(); 1006} 1007