LICM.cpp revision e488064922f12c4cf07f3aef9a4d2d3ffd15f9c0
1//===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===// 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 pass performs loop invariant code motion, attempting to remove as much 11// code from the body of a loop as possible. It does this by either hoisting 12// code into the preheader block, or by sinking code to the exit blocks if it is 13// safe. This pass also promotes must-aliased memory locations in the loop to 14// live in registers, thus hoisting and sinking "invariant" loads and stores. 15// 16// This pass uses alias analysis for two purposes: 17// 18// 1. Moving loop invariant loads and calls out of loops. If we can determine 19// that a load or call inside of a loop never aliases anything stored to, 20// we can hoist it or sink it like any other instruction. 21// 2. Scalar Promotion of Memory - If there is a store instruction inside of 22// the loop, we try to move the store to happen AFTER the loop instead of 23// inside of the loop. This can only happen if a few conditions are true: 24// A. The pointer stored through is loop invariant 25// B. There are no stores or loads in the loop which _may_ alias the 26// pointer. There are no calls in the loop which mod/ref the pointer. 27// If these conditions are true, we can promote the loads and stores in the 28// loop of the pointer to use a temporary alloca'd variable. We then use 29// the SSAUpdater to construct the appropriate SSA form for the value. 30// 31//===----------------------------------------------------------------------===// 32 33#define DEBUG_TYPE "licm" 34#include "llvm/Transforms/Scalar.h" 35#include "llvm/Constants.h" 36#include "llvm/DerivedTypes.h" 37#include "llvm/IntrinsicInst.h" 38#include "llvm/Instructions.h" 39#include "llvm/Target/TargetData.h" 40#include "llvm/Analysis/LoopInfo.h" 41#include "llvm/Analysis/LoopPass.h" 42#include "llvm/Analysis/AliasAnalysis.h" 43#include "llvm/Analysis/AliasSetTracker.h" 44#include "llvm/Analysis/Dominators.h" 45#include "llvm/Analysis/ScalarEvolution.h" 46#include "llvm/Transforms/Utils/SSAUpdater.h" 47#include "llvm/Support/CFG.h" 48#include "llvm/Support/CommandLine.h" 49#include "llvm/Support/raw_ostream.h" 50#include "llvm/Support/Debug.h" 51#include "llvm/ADT/Statistic.h" 52#include <algorithm> 53using namespace llvm; 54 55STATISTIC(NumSunk , "Number of instructions sunk out of loop"); 56STATISTIC(NumHoisted , "Number of instructions hoisted out of loop"); 57STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk"); 58STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk"); 59STATISTIC(NumPromoted , "Number of memory locations promoted to registers"); 60 61static cl::opt<bool> 62DisablePromotion("disable-licm-promotion", cl::Hidden, 63 cl::desc("Disable memory promotion in LICM pass")); 64 65namespace { 66 struct LICM : public LoopPass { 67 static char ID; // Pass identification, replacement for typeid 68 LICM() : LoopPass(ID) {} 69 70 virtual bool runOnLoop(Loop *L, LPPassManager &LPM); 71 72 /// This transformation requires natural loop information & requires that 73 /// loop preheaders be inserted into the CFG... 74 /// 75 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 76 AU.setPreservesCFG(); 77 AU.addRequired<DominatorTree>(); 78 AU.addRequired<DominanceFrontier>(); // For scalar promotion (mem2reg) 79 AU.addRequired<LoopInfo>(); 80 AU.addRequiredID(LoopSimplifyID); 81 AU.addRequired<AliasAnalysis>(); 82 AU.addPreserved<ScalarEvolution>(); 83 AU.addPreserved<DominanceFrontier>(); 84 AU.addPreservedID(LoopSimplifyID); 85 } 86 87 bool doFinalization() { 88 // Free the values stored in the map 89 for (std::map<Loop *, AliasSetTracker *>::iterator 90 I = LoopToAliasMap.begin(), E = LoopToAliasMap.end(); I != E; ++I) 91 delete I->second; 92 93 LoopToAliasMap.clear(); 94 return false; 95 } 96 97 private: 98 // Various analyses that we use... 99 AliasAnalysis *AA; // Current AliasAnalysis information 100 LoopInfo *LI; // Current LoopInfo 101 DominatorTree *DT; // Dominator Tree for the current Loop... 102 DominanceFrontier *DF; // Current Dominance Frontier 103 104 // State that is updated as we process loops 105 bool Changed; // Set to true when we change anything. 106 BasicBlock *Preheader; // The preheader block of the current loop... 107 Loop *CurLoop; // The current loop we are working on... 108 AliasSetTracker *CurAST; // AliasSet information for the current loop... 109 std::map<Loop *, AliasSetTracker *> LoopToAliasMap; 110 111 /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. 112 void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L); 113 114 /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias 115 /// set. 116 void deleteAnalysisValue(Value *V, Loop *L); 117 118 /// SinkRegion - Walk the specified region of the CFG (defined by all blocks 119 /// dominated by the specified block, and that are in the current loop) in 120 /// reverse depth first order w.r.t the DominatorTree. This allows us to 121 /// visit uses before definitions, allowing us to sink a loop body in one 122 /// pass without iteration. 123 /// 124 void SinkRegion(DomTreeNode *N); 125 126 /// HoistRegion - Walk the specified region of the CFG (defined by all 127 /// blocks dominated by the specified block, and that are in the current 128 /// loop) in depth first order w.r.t the DominatorTree. This allows us to 129 /// visit definitions before uses, allowing us to hoist a loop body in one 130 /// pass without iteration. 131 /// 132 void HoistRegion(DomTreeNode *N); 133 134 /// inSubLoop - Little predicate that returns true if the specified basic 135 /// block is in a subloop of the current one, not the current one itself. 136 /// 137 bool inSubLoop(BasicBlock *BB) { 138 assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop"); 139 for (Loop::iterator I = CurLoop->begin(), E = CurLoop->end(); I != E; ++I) 140 if ((*I)->contains(BB)) 141 return true; // A subloop actually contains this block! 142 return false; 143 } 144 145 /// isExitBlockDominatedByBlockInLoop - This method checks to see if the 146 /// specified exit block of the loop is dominated by the specified block 147 /// that is in the body of the loop. We use these constraints to 148 /// dramatically limit the amount of the dominator tree that needs to be 149 /// searched. 150 bool isExitBlockDominatedByBlockInLoop(BasicBlock *ExitBlock, 151 BasicBlock *BlockInLoop) const { 152 // If the block in the loop is the loop header, it must be dominated! 153 BasicBlock *LoopHeader = CurLoop->getHeader(); 154 if (BlockInLoop == LoopHeader) 155 return true; 156 157 DomTreeNode *BlockInLoopNode = DT->getNode(BlockInLoop); 158 DomTreeNode *IDom = DT->getNode(ExitBlock); 159 160 // Because the exit block is not in the loop, we know we have to get _at 161 // least_ its immediate dominator. 162 IDom = IDom->getIDom(); 163 164 while (IDom && IDom != BlockInLoopNode) { 165 // If we have got to the header of the loop, then the instructions block 166 // did not dominate the exit node, so we can't hoist it. 167 if (IDom->getBlock() == LoopHeader) 168 return false; 169 170 // Get next Immediate Dominator. 171 IDom = IDom->getIDom(); 172 }; 173 174 return true; 175 } 176 177 /// sink - When an instruction is found to only be used outside of the loop, 178 /// this function moves it to the exit blocks and patches up SSA form as 179 /// needed. 180 /// 181 void sink(Instruction &I); 182 183 /// hoist - When an instruction is found to only use loop invariant operands 184 /// that is safe to hoist, this instruction is called to do the dirty work. 185 /// 186 void hoist(Instruction &I); 187 188 /// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it 189 /// is not a trapping instruction or if it is a trapping instruction and is 190 /// guaranteed to execute. 191 /// 192 bool isSafeToExecuteUnconditionally(Instruction &I); 193 194 /// pointerInvalidatedByLoop - Return true if the body of this loop may 195 /// store into the memory location pointed to by V. 196 /// 197 bool pointerInvalidatedByLoop(Value *V, unsigned Size) { 198 // Check to see if any of the basic blocks in CurLoop invalidate *V. 199 return CurAST->getAliasSetForPointer(V, Size).isMod(); 200 } 201 202 bool canSinkOrHoistInst(Instruction &I); 203 bool isLoopInvariantInst(Instruction &I); 204 bool isNotUsedInLoop(Instruction &I); 205 206 void PromoteAliasSet(AliasSet &AS); 207 }; 208} 209 210char LICM::ID = 0; 211INITIALIZE_PASS(LICM, "licm", "Loop Invariant Code Motion", false, false); 212 213Pass *llvm::createLICMPass() { return new LICM(); } 214 215/// Hoist expressions out of the specified loop. Note, alias info for inner 216/// loop is not preserved so it is not a good idea to run LICM multiple 217/// times on one loop. 218/// 219bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) { 220 Changed = false; 221 222 // Get our Loop and Alias Analysis information... 223 LI = &getAnalysis<LoopInfo>(); 224 AA = &getAnalysis<AliasAnalysis>(); 225 DF = &getAnalysis<DominanceFrontier>(); 226 DT = &getAnalysis<DominatorTree>(); 227 228 CurAST = new AliasSetTracker(*AA); 229 // Collect Alias info from subloops 230 for (Loop::iterator LoopItr = L->begin(), LoopItrE = L->end(); 231 LoopItr != LoopItrE; ++LoopItr) { 232 Loop *InnerL = *LoopItr; 233 AliasSetTracker *InnerAST = LoopToAliasMap[InnerL]; 234 assert (InnerAST && "Where is my AST?"); 235 236 // What if InnerLoop was modified by other passes ? 237 CurAST->add(*InnerAST); 238 } 239 240 CurLoop = L; 241 242 // Get the preheader block to move instructions into... 243 Preheader = L->getLoopPreheader(); 244 245 // Loop over the body of this loop, looking for calls, invokes, and stores. 246 // Because subloops have already been incorporated into AST, we skip blocks in 247 // subloops. 248 // 249 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 250 I != E; ++I) { 251 BasicBlock *BB = *I; 252 if (LI->getLoopFor(BB) == L) // Ignore blocks in subloops... 253 CurAST->add(*BB); // Incorporate the specified basic block 254 } 255 256 // We want to visit all of the instructions in this loop... that are not parts 257 // of our subloops (they have already had their invariants hoisted out of 258 // their loop, into this loop, so there is no need to process the BODIES of 259 // the subloops). 260 // 261 // Traverse the body of the loop in depth first order on the dominator tree so 262 // that we are guaranteed to see definitions before we see uses. This allows 263 // us to sink instructions in one pass, without iteration. After sinking 264 // instructions, we perform another pass to hoist them out of the loop. 265 // 266 if (L->hasDedicatedExits()) 267 SinkRegion(DT->getNode(L->getHeader())); 268 if (Preheader) 269 HoistRegion(DT->getNode(L->getHeader())); 270 271 // Now that all loop invariants have been removed from the loop, promote any 272 // memory references to scalars that we can. 273 if (!DisablePromotion && Preheader && L->hasDedicatedExits()) { 274 // Loop over all of the alias sets in the tracker object. 275 for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); 276 I != E; ++I) 277 PromoteAliasSet(*I); 278 } 279 280 // Clear out loops state information for the next iteration 281 CurLoop = 0; 282 Preheader = 0; 283 284 LoopToAliasMap[L] = CurAST; 285 return Changed; 286} 287 288/// SinkRegion - Walk the specified region of the CFG (defined by all blocks 289/// dominated by the specified block, and that are in the current loop) in 290/// reverse depth first order w.r.t the DominatorTree. This allows us to visit 291/// uses before definitions, allowing us to sink a loop body in one pass without 292/// iteration. 293/// 294void LICM::SinkRegion(DomTreeNode *N) { 295 assert(N != 0 && "Null dominator tree node?"); 296 BasicBlock *BB = N->getBlock(); 297 298 // If this subregion is not in the top level loop at all, exit. 299 if (!CurLoop->contains(BB)) return; 300 301 // We are processing blocks in reverse dfo, so process children first... 302 const std::vector<DomTreeNode*> &Children = N->getChildren(); 303 for (unsigned i = 0, e = Children.size(); i != e; ++i) 304 SinkRegion(Children[i]); 305 306 // Only need to process the contents of this block if it is not part of a 307 // subloop (which would already have been processed). 308 if (inSubLoop(BB)) return; 309 310 for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) { 311 Instruction &I = *--II; 312 313 // Check to see if we can sink this instruction to the exit blocks 314 // of the loop. We can do this if the all users of the instruction are 315 // outside of the loop. In this case, it doesn't even matter if the 316 // operands of the instruction are loop invariant. 317 // 318 if (isNotUsedInLoop(I) && canSinkOrHoistInst(I)) { 319 ++II; 320 sink(I); 321 } 322 } 323} 324 325/// HoistRegion - Walk the specified region of the CFG (defined by all blocks 326/// dominated by the specified block, and that are in the current loop) in depth 327/// first order w.r.t the DominatorTree. This allows us to visit definitions 328/// before uses, allowing us to hoist a loop body in one pass without iteration. 329/// 330void LICM::HoistRegion(DomTreeNode *N) { 331 assert(N != 0 && "Null dominator tree node?"); 332 BasicBlock *BB = N->getBlock(); 333 334 // If this subregion is not in the top level loop at all, exit. 335 if (!CurLoop->contains(BB)) return; 336 337 // Only need to process the contents of this block if it is not part of a 338 // subloop (which would already have been processed). 339 if (!inSubLoop(BB)) 340 for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) { 341 Instruction &I = *II++; 342 343 // Try hoisting the instruction out to the preheader. We can only do this 344 // if all of the operands of the instruction are loop invariant and if it 345 // is safe to hoist the instruction. 346 // 347 if (isLoopInvariantInst(I) && canSinkOrHoistInst(I) && 348 isSafeToExecuteUnconditionally(I)) 349 hoist(I); 350 } 351 352 const std::vector<DomTreeNode*> &Children = N->getChildren(); 353 for (unsigned i = 0, e = Children.size(); i != e; ++i) 354 HoistRegion(Children[i]); 355} 356 357/// canSinkOrHoistInst - Return true if the hoister and sinker can handle this 358/// instruction. 359/// 360bool LICM::canSinkOrHoistInst(Instruction &I) { 361 // Loads have extra constraints we have to verify before we can hoist them. 362 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) { 363 if (LI->isVolatile()) 364 return false; // Don't hoist volatile loads! 365 366 // Loads from constant memory are always safe to move, even if they end up 367 // in the same alias set as something that ends up being modified. 368 if (AA->pointsToConstantMemory(LI->getOperand(0))) 369 return true; 370 371 // Don't hoist loads which have may-aliased stores in loop. 372 unsigned Size = 0; 373 if (LI->getType()->isSized()) 374 Size = AA->getTypeStoreSize(LI->getType()); 375 return !pointerInvalidatedByLoop(LI->getOperand(0), Size); 376 } else if (CallInst *CI = dyn_cast<CallInst>(&I)) { 377 // Handle obvious cases efficiently. 378 AliasAnalysis::ModRefBehavior Behavior = AA->getModRefBehavior(CI); 379 if (Behavior == AliasAnalysis::DoesNotAccessMemory) 380 return true; 381 else if (Behavior == AliasAnalysis::OnlyReadsMemory) { 382 // If this call only reads from memory and there are no writes to memory 383 // in the loop, we can hoist or sink the call as appropriate. 384 bool FoundMod = false; 385 for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); 386 I != E; ++I) { 387 AliasSet &AS = *I; 388 if (!AS.isForwardingAliasSet() && AS.isMod()) { 389 FoundMod = true; 390 break; 391 } 392 } 393 if (!FoundMod) return true; 394 } 395 396 // FIXME: This should use mod/ref information to see if we can hoist or sink 397 // the call. 398 399 return false; 400 } 401 402 // Otherwise these instructions are hoistable/sinkable 403 return isa<BinaryOperator>(I) || isa<CastInst>(I) || 404 isa<SelectInst>(I) || isa<GetElementPtrInst>(I) || isa<CmpInst>(I) || 405 isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) || 406 isa<ShuffleVectorInst>(I); 407} 408 409/// isNotUsedInLoop - Return true if the only users of this instruction are 410/// outside of the loop. If this is true, we can sink the instruction to the 411/// exit blocks of the loop. 412/// 413bool LICM::isNotUsedInLoop(Instruction &I) { 414 for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E; ++UI) { 415 Instruction *User = cast<Instruction>(*UI); 416 if (PHINode *PN = dyn_cast<PHINode>(User)) { 417 // PHI node uses occur in predecessor blocks! 418 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 419 if (PN->getIncomingValue(i) == &I) 420 if (CurLoop->contains(PN->getIncomingBlock(i))) 421 return false; 422 } else if (CurLoop->contains(User)) { 423 return false; 424 } 425 } 426 return true; 427} 428 429 430/// isLoopInvariantInst - Return true if all operands of this instruction are 431/// loop invariant. We also filter out non-hoistable instructions here just for 432/// efficiency. 433/// 434bool LICM::isLoopInvariantInst(Instruction &I) { 435 // The instruction is loop invariant if all of its operands are loop-invariant 436 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) 437 if (!CurLoop->isLoopInvariant(I.getOperand(i))) 438 return false; 439 440 // If we got this far, the instruction is loop invariant! 441 return true; 442} 443 444/// sink - When an instruction is found to only be used outside of the loop, 445/// this function moves it to the exit blocks and patches up SSA form as needed. 446/// This method is guaranteed to remove the original instruction from its 447/// position, and may either delete it or move it to outside of the loop. 448/// 449void LICM::sink(Instruction &I) { 450 DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n"); 451 452 SmallVector<BasicBlock*, 8> ExitBlocks; 453 CurLoop->getUniqueExitBlocks(ExitBlocks); 454 455 if (isa<LoadInst>(I)) ++NumMovedLoads; 456 else if (isa<CallInst>(I)) ++NumMovedCalls; 457 ++NumSunk; 458 Changed = true; 459 460 // The case where there is only a single exit node of this loop is common 461 // enough that we handle it as a special (more efficient) case. It is more 462 // efficient to handle because there are no PHI nodes that need to be placed. 463 if (ExitBlocks.size() == 1) { 464 if (!isExitBlockDominatedByBlockInLoop(ExitBlocks[0], I.getParent())) { 465 // Instruction is not used, just delete it. 466 CurAST->deleteValue(&I); 467 // If I has users in unreachable blocks, eliminate. 468 // If I is not void type then replaceAllUsesWith undef. 469 // This allows ValueHandlers and custom metadata to adjust itself. 470 if (!I.use_empty()) 471 I.replaceAllUsesWith(UndefValue::get(I.getType())); 472 I.eraseFromParent(); 473 } else { 474 // Move the instruction to the start of the exit block, after any PHI 475 // nodes in it. 476 I.removeFromParent(); 477 BasicBlock::iterator InsertPt = ExitBlocks[0]->getFirstNonPHI(); 478 ExitBlocks[0]->getInstList().insert(InsertPt, &I); 479 } 480 return; 481 } 482 483 if (ExitBlocks.empty()) { 484 // The instruction is actually dead if there ARE NO exit blocks. 485 CurAST->deleteValue(&I); 486 // If I has users in unreachable blocks, eliminate. 487 // If I is not void type then replaceAllUsesWith undef. 488 // This allows ValueHandlers and custom metadata to adjust itself. 489 if (!I.use_empty()) 490 I.replaceAllUsesWith(UndefValue::get(I.getType())); 491 I.eraseFromParent(); 492 return; 493 } 494 495 // Otherwise, if we have multiple exits, use the SSAUpdater to do all of the 496 // hard work of inserting PHI nodes as necessary. 497 SmallVector<PHINode*, 8> NewPHIs; 498 SSAUpdater SSA(&NewPHIs); 499 500 if (!I.use_empty()) 501 SSA.Initialize(&I); 502 503 // Insert a copy of the instruction in each exit block of the loop that is 504 // dominated by the instruction. Each exit block is known to only be in the 505 // ExitBlocks list once. 506 BasicBlock *InstOrigBB = I.getParent(); 507 unsigned NumInserted = 0; 508 509 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 510 BasicBlock *ExitBlock = ExitBlocks[i]; 511 512 if (!isExitBlockDominatedByBlockInLoop(ExitBlock, InstOrigBB)) 513 continue; 514 515 // Insert the code after the last PHI node. 516 BasicBlock::iterator InsertPt = ExitBlock->getFirstNonPHI(); 517 518 // If this is the first exit block processed, just move the original 519 // instruction, otherwise clone the original instruction and insert 520 // the copy. 521 Instruction *New; 522 if (NumInserted++ == 0) { 523 I.moveBefore(InsertPt); 524 New = &I; 525 } else { 526 New = I.clone(); 527 CurAST->copyValue(&I, New); 528 if (!I.getName().empty()) 529 New->setName(I.getName()+".le"); 530 ExitBlock->getInstList().insert(InsertPt, New); 531 } 532 533 // Now that we have inserted the instruction, inform SSAUpdater. 534 if (!I.use_empty()) 535 SSA.AddAvailableValue(ExitBlock, New); 536 } 537 538 // If the instruction doesn't dominate any exit blocks, it must be dead. 539 if (NumInserted == 0) { 540 CurAST->deleteValue(&I); 541 if (!I.use_empty()) 542 I.replaceAllUsesWith(UndefValue::get(I.getType())); 543 I.eraseFromParent(); 544 return; 545 } 546 547 // Next, rewrite uses of the instruction, inserting PHI nodes as needed. 548 for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE; ) { 549 // Grab the use before incrementing the iterator. 550 Use &U = UI.getUse(); 551 // Increment the iterator before removing the use from the list. 552 ++UI; 553 SSA.RewriteUseAfterInsertions(U); 554 } 555 556 // Update CurAST for NewPHIs if I had pointer type. 557 if (I.getType()->isPointerTy()) 558 for (unsigned i = 0, e = NewPHIs.size(); i != e; ++i) 559 CurAST->copyValue(NewPHIs[i], &I); 560} 561 562/// hoist - When an instruction is found to only use loop invariant operands 563/// that is safe to hoist, this instruction is called to do the dirty work. 564/// 565void LICM::hoist(Instruction &I) { 566 DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " 567 << I << "\n"); 568 569 // Remove the instruction from its current basic block... but don't delete the 570 // instruction. 571 I.removeFromParent(); 572 573 // Insert the new node in Preheader, before the terminator. 574 Preheader->getInstList().insert(Preheader->getTerminator(), &I); 575 576 if (isa<LoadInst>(I)) ++NumMovedLoads; 577 else if (isa<CallInst>(I)) ++NumMovedCalls; 578 ++NumHoisted; 579 Changed = true; 580} 581 582/// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it is 583/// not a trapping instruction or if it is a trapping instruction and is 584/// guaranteed to execute. 585/// 586bool LICM::isSafeToExecuteUnconditionally(Instruction &Inst) { 587 // If it is not a trapping instruction, it is always safe to hoist. 588 if (Inst.isSafeToSpeculativelyExecute()) 589 return true; 590 591 // Otherwise we have to check to make sure that the instruction dominates all 592 // of the exit blocks. If it doesn't, then there is a path out of the loop 593 // which does not execute this instruction, so we can't hoist it. 594 595 // If the instruction is in the header block for the loop (which is very 596 // common), it is always guaranteed to dominate the exit blocks. Since this 597 // is a common case, and can save some work, check it now. 598 if (Inst.getParent() == CurLoop->getHeader()) 599 return true; 600 601 // Get the exit blocks for the current loop. 602 SmallVector<BasicBlock*, 8> ExitBlocks; 603 CurLoop->getExitBlocks(ExitBlocks); 604 605 // For each exit block, get the DT node and walk up the DT until the 606 // instruction's basic block is found or we exit the loop. 607 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 608 if (!isExitBlockDominatedByBlockInLoop(ExitBlocks[i], Inst.getParent())) 609 return false; 610 611 return true; 612} 613 614/// PromoteAliasSet - Try to promote memory values to scalars by sinking 615/// stores out of the loop and moving loads to before the loop. We do this by 616/// looping over the stores in the loop, looking for stores to Must pointers 617/// which are loop invariant. 618/// 619void LICM::PromoteAliasSet(AliasSet &AS) { 620 // We can promote this alias set if it has a store, if it is a "Must" alias 621 // set, if the pointer is loop invariant, and if we are not eliminating any 622 // volatile loads or stores. 623 if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() || 624 AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue())) 625 return; 626 627 assert(!AS.empty() && 628 "Must alias set should have at least one pointer element in it!"); 629 Value *SomePtr = AS.begin()->getValue(); 630 631 // It isn't safe to promote a load/store from the loop if the load/store is 632 // conditional. For example, turning: 633 // 634 // for () { if (c) *P += 1; } 635 // 636 // into: 637 // 638 // tmp = *P; for () { if (c) tmp +=1; } *P = tmp; 639 // 640 // is not safe, because *P may only be valid to access if 'c' is true. 641 // 642 // It is safe to promote P if all uses are direct load/stores and if at 643 // least one is guaranteed to be executed. 644 bool GuaranteedToExecute = false; 645 646 SmallVector<Instruction*, 64> LoopUses; 647 SmallPtrSet<Value*, 4> PointerMustAliases; 648 649 // Check that all of the pointers in the alias set have the same type. We 650 // cannot (yet) promote a memory location that is loaded and stored in 651 // different sizes. 652 for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) { 653 Value *ASIV = ASI->getValue(); 654 PointerMustAliases.insert(ASIV); 655 656 // Check that all of the pointers in the alias set have the same type. We 657 // cannot (yet) promote a memory location that is loaded and stored in 658 // different sizes. 659 if (SomePtr->getType() != ASIV->getType()) 660 return; 661 662 for (Value::use_iterator UI = ASIV->use_begin(), UE = ASIV->use_end(); 663 UI != UE; ++UI) { 664 // Ignore instructions that are outside the loop. 665 Instruction *Use = dyn_cast<Instruction>(*UI); 666 if (!Use || !CurLoop->contains(Use)) 667 continue; 668 669 // If there is an non-load/store instruction in the loop, we can't promote 670 // it. 671 if (isa<LoadInst>(Use)) 672 assert(!cast<LoadInst>(Use)->isVolatile() && "AST broken"); 673 else if (isa<StoreInst>(Use)) 674 assert(!cast<StoreInst>(Use)->isVolatile() && 675 Use->getOperand(0) != ASIV && "AST broken"); 676 else 677 return; // Not a load or store. 678 679 if (!GuaranteedToExecute) 680 GuaranteedToExecute = isSafeToExecuteUnconditionally(*Use); 681 682 LoopUses.push_back(Use); 683 } 684 } 685 686 // If there isn't a guaranteed-to-execute instruction, we can't promote. 687 if (!GuaranteedToExecute) 688 return; 689 690 // Otherwise, this is safe to promote, lets do it! 691 DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " <<*SomePtr<<'\n'); 692 Changed = true; 693 ++NumPromoted; 694 695 // We use the SSAUpdater interface to insert phi nodes as required. 696 SmallVector<PHINode*, 16> NewPHIs; 697 SSAUpdater SSA(&NewPHIs); 698 699 // It wants to know some value of the same type as what we'll be inserting. 700 Value *SomeValue; 701 if (isa<LoadInst>(LoopUses[0])) 702 SomeValue = LoopUses[0]; 703 else 704 SomeValue = cast<StoreInst>(LoopUses[0])->getOperand(0); 705 SSA.Initialize(SomeValue); 706 707 // First step: bucket up uses of the pointers by the block they occur in. 708 // This is important because we have to handle multiple defs/uses in a block 709 // ourselves: SSAUpdater is purely for cross-block references. 710 // FIXME: Want a TinyVector<Instruction*> since there is usually 0/1 element. 711 DenseMap<BasicBlock*, std::vector<Instruction*> > UsesByBlock; 712 for (unsigned i = 0, e = LoopUses.size(); i != e; ++i) { 713 Instruction *User = LoopUses[i]; 714 UsesByBlock[User->getParent()].push_back(User); 715 } 716 717 // Okay, now we can iterate over all the blocks in the loop with uses, 718 // processing them. Keep track of which loads are loading a live-in value. 719 SmallVector<LoadInst*, 32> LiveInLoads; 720 721 for (unsigned LoopUse = 0, e = LoopUses.size(); LoopUse != e; ++LoopUse) { 722 Instruction *User = LoopUses[LoopUse]; 723 std::vector<Instruction*> &BlockUses = UsesByBlock[User->getParent()]; 724 725 // If this block has already been processed, ignore this repeat use. 726 if (BlockUses.empty()) continue; 727 728 // Okay, this is the first use in the block. If this block just has a 729 // single user in it, we can rewrite it trivially. 730 if (BlockUses.size() == 1) { 731 // If it is a store, it is a trivial def of the value in the block. 732 if (isa<StoreInst>(User)) { 733 SSA.AddAvailableValue(User->getParent(), 734 cast<StoreInst>(User)->getOperand(0)); 735 } else { 736 // Otherwise it is a load, queue it to rewrite as a live-in load. 737 LiveInLoads.push_back(cast<LoadInst>(User)); 738 } 739 BlockUses.clear(); 740 continue; 741 } 742 743 // Otherwise, check to see if this block is all loads. If so, we can queue 744 // them all as live in loads. 745 bool HasStore = false; 746 for (unsigned i = 0, e = BlockUses.size(); i != e; ++i) { 747 if (isa<StoreInst>(BlockUses[i])) { 748 HasStore = true; 749 break; 750 } 751 } 752 753 if (!HasStore) { 754 for (unsigned i = 0, e = BlockUses.size(); i != e; ++i) 755 LiveInLoads.push_back(cast<LoadInst>(BlockUses[i])); 756 BlockUses.clear(); 757 continue; 758 } 759 760 // Otherwise, we have mixed loads and stores (or just a bunch of stores). 761 // Since SSAUpdater is purely for cross-block values, we need to determine 762 // the order of these instructions in the block. If the first use in the 763 // block is a load, then it uses the live in value. The last store defines 764 // the live out value. We handle this by doing a linear scan of the block. 765 BasicBlock *BB = User->getParent(); 766 Value *StoredValue = 0; 767 for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ++II) { 768 if (LoadInst *L = dyn_cast<LoadInst>(II)) { 769 // If this is a load to an unrelated pointer, ignore it. 770 if (!PointerMustAliases.count(L->getOperand(0))) continue; 771 772 // If we haven't seen a store yet, this is a live in use, otherwise 773 // use the stored value. 774 if (StoredValue) 775 L->replaceAllUsesWith(StoredValue); 776 else 777 LiveInLoads.push_back(L); 778 continue; 779 } 780 781 if (StoreInst *S = dyn_cast<StoreInst>(II)) { 782 // If this is a load to an unrelated pointer, ignore it. 783 if (!PointerMustAliases.count(S->getOperand(1))) continue; 784 785 // Remember that this is the active value in the block. 786 StoredValue = S->getOperand(0); 787 } 788 } 789 790 // The last stored value that happened is the live-out for the block. 791 assert(StoredValue && "Already checked that there is a store in block"); 792 SSA.AddAvailableValue(BB, StoredValue); 793 BlockUses.clear(); 794 } 795 796 // Now that all the intra-loop values are classified, set up the preheader. 797 // It gets a load of the pointer we're promoting, and it is the live-out value 798 // from the preheader. 799 LoadInst *PreheaderLoad = new LoadInst(SomePtr,SomePtr->getName()+".promoted", 800 Preheader->getTerminator()); 801 SSA.AddAvailableValue(Preheader, PreheaderLoad); 802 803 // Now that the preheader is good to go, set up the exit blocks. Each exit 804 // block gets a store of the live-out values that feed them. Since we've 805 // already told the SSA updater about the defs in the loop and the preheader 806 // definition, it is all set and we can start using it. 807 SmallVector<BasicBlock*, 8> ExitBlocks; 808 CurLoop->getUniqueExitBlocks(ExitBlocks); 809 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 810 BasicBlock *ExitBlock = ExitBlocks[i]; 811 Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock); 812 Instruction *InsertPos = ExitBlock->getFirstNonPHI(); 813 new StoreInst(LiveInValue, SomePtr, InsertPos); 814 } 815 816 // Okay, now we rewrite all loads that use live-in values in the loop, 817 // inserting PHI nodes as necessary. 818 for (unsigned i = 0, e = LiveInLoads.size(); i != e; ++i) { 819 LoadInst *ALoad = LiveInLoads[i]; 820 ALoad->replaceAllUsesWith(SSA.GetValueInMiddleOfBlock(ALoad->getParent())); 821 } 822 823 // Now that everything is rewritten, delete the old instructions from the body 824 // of the loop. They should all be dead now. 825 for (unsigned i = 0, e = LoopUses.size(); i != e; ++i) { 826 Instruction *User = LoopUses[i]; 827 CurAST->deleteValue(User); 828 User->eraseFromParent(); 829 } 830 831 // If the preheader load is itself a pointer, we need to tell alias analysis 832 // about the new pointer we created in the preheader block and about any PHI 833 // nodes that just got inserted. 834 if (PreheaderLoad->getType()->isPointerTy()) { 835 // Copy any value stored to or loaded from a must-alias of the pointer. 836 CurAST->copyValue(SomeValue, PreheaderLoad); 837 838 for (unsigned i = 0, e = NewPHIs.size(); i != e; ++i) 839 CurAST->copyValue(SomeValue, NewPHIs[i]); 840 } 841 842 // fwew, we're done! 843} 844 845 846/// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. 847void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) { 848 AliasSetTracker *AST = LoopToAliasMap[L]; 849 if (!AST) 850 return; 851 852 AST->copyValue(From, To); 853} 854 855/// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias 856/// set. 857void LICM::deleteAnalysisValue(Value *V, Loop *L) { 858 AliasSetTracker *AST = LoopToAliasMap[L]; 859 if (!AST) 860 return; 861 862 AST->deleteValue(V); 863} 864