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 #include "llvm/Transforms/Scalar.h" 34 #include "llvm/ADT/Statistic.h" 35 #include "llvm/Analysis/AliasAnalysis.h" 36 #include "llvm/Analysis/AliasSetTracker.h" 37 #include "llvm/Analysis/ConstantFolding.h" 38 #include "llvm/Analysis/LoopInfo.h" 39 #include "llvm/Analysis/LoopPass.h" 40 #include "llvm/Analysis/ScalarEvolution.h" 41 #include "llvm/Analysis/ValueTracking.h" 42 #include "llvm/IR/CFG.h" 43 #include "llvm/IR/Constants.h" 44 #include "llvm/IR/DataLayout.h" 45 #include "llvm/IR/DerivedTypes.h" 46 #include "llvm/IR/Dominators.h" 47 #include "llvm/IR/Instructions.h" 48 #include "llvm/IR/IntrinsicInst.h" 49 #include "llvm/IR/LLVMContext.h" 50 #include "llvm/IR/Metadata.h" 51 #include "llvm/IR/PredIteratorCache.h" 52 #include "llvm/Support/CommandLine.h" 53 #include "llvm/Support/Debug.h" 54 #include "llvm/Support/raw_ostream.h" 55 #include "llvm/Target/TargetLibraryInfo.h" 56 #include "llvm/Transforms/Utils/Local.h" 57 #include "llvm/Transforms/Utils/LoopUtils.h" 58 #include "llvm/Transforms/Utils/SSAUpdater.h" 59 #include <algorithm> 60 using namespace llvm; 61 62 #define DEBUG_TYPE "licm" 63 64 STATISTIC(NumSunk , "Number of instructions sunk out of loop"); 65 STATISTIC(NumHoisted , "Number of instructions hoisted out of loop"); 66 STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk"); 67 STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk"); 68 STATISTIC(NumPromoted , "Number of memory locations promoted to registers"); 69 70 static cl::opt<bool> 71 DisablePromotion("disable-licm-promotion", cl::Hidden, 72 cl::desc("Disable memory promotion in LICM pass")); 73 74 namespace { 75 struct LICM : public LoopPass { 76 static char ID; // Pass identification, replacement for typeid 77 LICM() : LoopPass(ID) { 78 initializeLICMPass(*PassRegistry::getPassRegistry()); 79 } 80 81 bool runOnLoop(Loop *L, LPPassManager &LPM) override; 82 83 /// This transformation requires natural loop information & requires that 84 /// loop preheaders be inserted into the CFG... 85 /// 86 void getAnalysisUsage(AnalysisUsage &AU) const override { 87 AU.setPreservesCFG(); 88 AU.addRequired<DominatorTreeWrapperPass>(); 89 AU.addRequired<LoopInfo>(); 90 AU.addRequiredID(LoopSimplifyID); 91 AU.addPreservedID(LoopSimplifyID); 92 AU.addRequiredID(LCSSAID); 93 AU.addPreservedID(LCSSAID); 94 AU.addRequired<AliasAnalysis>(); 95 AU.addPreserved<AliasAnalysis>(); 96 AU.addPreserved<ScalarEvolution>(); 97 AU.addRequired<TargetLibraryInfo>(); 98 } 99 100 using llvm::Pass::doFinalization; 101 102 bool doFinalization() override { 103 assert(LoopToAliasSetMap.empty() && "Didn't free loop alias sets"); 104 return false; 105 } 106 107 private: 108 AliasAnalysis *AA; // Current AliasAnalysis information 109 LoopInfo *LI; // Current LoopInfo 110 DominatorTree *DT; // Dominator Tree for the current Loop. 111 112 const DataLayout *DL; // DataLayout for constant folding. 113 TargetLibraryInfo *TLI; // TargetLibraryInfo for constant folding. 114 115 // State that is updated as we process loops. 116 bool Changed; // Set to true when we change anything. 117 BasicBlock *Preheader; // The preheader block of the current loop... 118 Loop *CurLoop; // The current loop we are working on... 119 AliasSetTracker *CurAST; // AliasSet information for the current loop... 120 bool MayThrow; // The current loop contains an instruction which 121 // may throw, thus preventing code motion of 122 // instructions with side effects. 123 DenseMap<Loop*, AliasSetTracker*> LoopToAliasSetMap; 124 125 /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. 126 void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, 127 Loop *L) override; 128 129 /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias 130 /// set. 131 void deleteAnalysisValue(Value *V, Loop *L) override; 132 133 /// SinkRegion - Walk the specified region of the CFG (defined by all blocks 134 /// dominated by the specified block, and that are in the current loop) in 135 /// reverse depth first order w.r.t the DominatorTree. This allows us to 136 /// visit uses before definitions, allowing us to sink a loop body in one 137 /// pass without iteration. 138 /// 139 void SinkRegion(DomTreeNode *N); 140 141 /// HoistRegion - Walk the specified region of the CFG (defined by all 142 /// blocks dominated by the specified block, and that are in the current 143 /// loop) in depth first order w.r.t the DominatorTree. This allows us to 144 /// visit definitions before uses, allowing us to hoist a loop body in one 145 /// pass without iteration. 146 /// 147 void HoistRegion(DomTreeNode *N); 148 149 /// inSubLoop - Little predicate that returns true if the specified basic 150 /// block is in a subloop of the current one, not the current one itself. 151 /// 152 bool inSubLoop(BasicBlock *BB) { 153 assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop"); 154 return LI->getLoopFor(BB) != CurLoop; 155 } 156 157 /// sink - When an instruction is found to only be used outside of the loop, 158 /// this function moves it to the exit blocks and patches up SSA form as 159 /// needed. 160 /// 161 void sink(Instruction &I); 162 163 /// hoist - When an instruction is found to only use loop invariant operands 164 /// that is safe to hoist, this instruction is called to do the dirty work. 165 /// 166 void hoist(Instruction &I); 167 168 /// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it 169 /// is not a trapping instruction or if it is a trapping instruction and is 170 /// guaranteed to execute. 171 /// 172 bool isSafeToExecuteUnconditionally(Instruction &I); 173 174 /// isGuaranteedToExecute - Check that the instruction is guaranteed to 175 /// execute. 176 /// 177 bool isGuaranteedToExecute(Instruction &I); 178 179 /// pointerInvalidatedByLoop - Return true if the body of this loop may 180 /// store into the memory location pointed to by V. 181 /// 182 bool pointerInvalidatedByLoop(Value *V, uint64_t Size, 183 const MDNode *TBAAInfo) { 184 // Check to see if any of the basic blocks in CurLoop invalidate *V. 185 return CurAST->getAliasSetForPointer(V, Size, TBAAInfo).isMod(); 186 } 187 188 bool canSinkOrHoistInst(Instruction &I); 189 bool isNotUsedInLoop(Instruction &I); 190 191 void PromoteAliasSet(AliasSet &AS, 192 SmallVectorImpl<BasicBlock*> &ExitBlocks, 193 SmallVectorImpl<Instruction*> &InsertPts, 194 PredIteratorCache &PIC); 195 196 /// \brief Create a copy of the instruction in the exit block and patch up 197 /// SSA. 198 /// PN is a user of I in ExitBlock that can be used to get the number and 199 /// list of predecessors fast. 200 Instruction *CloneInstructionInExitBlock(Instruction &I, 201 BasicBlock &ExitBlock, 202 PHINode &PN); 203 }; 204 } 205 206 char LICM::ID = 0; 207 INITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false) 208 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 209 INITIALIZE_PASS_DEPENDENCY(LoopInfo) 210 INITIALIZE_PASS_DEPENDENCY(LoopSimplify) 211 INITIALIZE_PASS_DEPENDENCY(LCSSA) 212 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 213 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 214 INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 215 INITIALIZE_PASS_END(LICM, "licm", "Loop Invariant Code Motion", false, false) 216 217 Pass *llvm::createLICMPass() { return new LICM(); } 218 219 /// Hoist expressions out of the specified loop. Note, alias info for inner 220 /// loop is not preserved so it is not a good idea to run LICM multiple 221 /// times on one loop. 222 /// 223 bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) { 224 if (skipOptnoneFunction(L)) 225 return false; 226 227 Changed = false; 228 229 // Get our Loop and Alias Analysis information... 230 LI = &getAnalysis<LoopInfo>(); 231 AA = &getAnalysis<AliasAnalysis>(); 232 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 233 234 DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); 235 DL = DLP ? &DLP->getDataLayout() : nullptr; 236 TLI = &getAnalysis<TargetLibraryInfo>(); 237 238 assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form."); 239 240 CurAST = new AliasSetTracker(*AA); 241 // Collect Alias info from subloops. 242 for (Loop::iterator LoopItr = L->begin(), LoopItrE = L->end(); 243 LoopItr != LoopItrE; ++LoopItr) { 244 Loop *InnerL = *LoopItr; 245 AliasSetTracker *InnerAST = LoopToAliasSetMap[InnerL]; 246 assert(InnerAST && "Where is my AST?"); 247 248 // What if InnerLoop was modified by other passes ? 249 CurAST->add(*InnerAST); 250 251 // Once we've incorporated the inner loop's AST into ours, we don't need the 252 // subloop's anymore. 253 delete InnerAST; 254 LoopToAliasSetMap.erase(InnerL); 255 } 256 257 CurLoop = L; 258 259 // Get the preheader block to move instructions into... 260 Preheader = L->getLoopPreheader(); 261 262 // Loop over the body of this loop, looking for calls, invokes, and stores. 263 // Because subloops have already been incorporated into AST, we skip blocks in 264 // subloops. 265 // 266 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 267 I != E; ++I) { 268 BasicBlock *BB = *I; 269 if (LI->getLoopFor(BB) == L) // Ignore blocks in subloops. 270 CurAST->add(*BB); // Incorporate the specified basic block 271 } 272 273 MayThrow = false; 274 // TODO: We've already searched for instructions which may throw in subloops. 275 // We may want to reuse this information. 276 for (Loop::block_iterator BB = L->block_begin(), BBE = L->block_end(); 277 (BB != BBE) && !MayThrow ; ++BB) 278 for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); 279 (I != E) && !MayThrow; ++I) 280 MayThrow |= I->mayThrow(); 281 282 // We want to visit all of the instructions in this loop... that are not parts 283 // of our subloops (they have already had their invariants hoisted out of 284 // their loop, into this loop, so there is no need to process the BODIES of 285 // the subloops). 286 // 287 // Traverse the body of the loop in depth first order on the dominator tree so 288 // that we are guaranteed to see definitions before we see uses. This allows 289 // us to sink instructions in one pass, without iteration. After sinking 290 // instructions, we perform another pass to hoist them out of the loop. 291 // 292 if (L->hasDedicatedExits()) 293 SinkRegion(DT->getNode(L->getHeader())); 294 if (Preheader) 295 HoistRegion(DT->getNode(L->getHeader())); 296 297 // Now that all loop invariants have been removed from the loop, promote any 298 // memory references to scalars that we can. 299 if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) { 300 SmallVector<BasicBlock *, 8> ExitBlocks; 301 SmallVector<Instruction *, 8> InsertPts; 302 PredIteratorCache PIC; 303 304 // Loop over all of the alias sets in the tracker object. 305 for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); 306 I != E; ++I) 307 PromoteAliasSet(*I, ExitBlocks, InsertPts, PIC); 308 309 // Once we have promoted values across the loop body we have to recursively 310 // reform LCSSA as any nested loop may now have values defined within the 311 // loop used in the outer loop. 312 // FIXME: This is really heavy handed. It would be a bit better to use an 313 // SSAUpdater strategy during promotion that was LCSSA aware and reformed 314 // it as it went. 315 if (Changed) 316 formLCSSARecursively(*L, *DT, getAnalysisIfAvailable<ScalarEvolution>()); 317 } 318 319 // Check that neither this loop nor its parent have had LCSSA broken. LICM is 320 // specifically moving instructions across the loop boundary and so it is 321 // especially in need of sanity checking here. 322 assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!"); 323 assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) && 324 "Parent loop not left in LCSSA form after LICM!"); 325 326 // Clear out loops state information for the next iteration 327 CurLoop = nullptr; 328 Preheader = nullptr; 329 330 // If this loop is nested inside of another one, save the alias information 331 // for when we process the outer loop. 332 if (L->getParentLoop()) 333 LoopToAliasSetMap[L] = CurAST; 334 else 335 delete CurAST; 336 return Changed; 337 } 338 339 /// SinkRegion - Walk the specified region of the CFG (defined by all blocks 340 /// dominated by the specified block, and that are in the current loop) in 341 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit 342 /// uses before definitions, allowing us to sink a loop body in one pass without 343 /// iteration. 344 /// 345 void LICM::SinkRegion(DomTreeNode *N) { 346 assert(N != nullptr && "Null dominator tree node?"); 347 BasicBlock *BB = N->getBlock(); 348 349 // If this subregion is not in the top level loop at all, exit. 350 if (!CurLoop->contains(BB)) return; 351 352 // We are processing blocks in reverse dfo, so process children first. 353 const std::vector<DomTreeNode*> &Children = N->getChildren(); 354 for (unsigned i = 0, e = Children.size(); i != e; ++i) 355 SinkRegion(Children[i]); 356 357 // Only need to process the contents of this block if it is not part of a 358 // subloop (which would already have been processed). 359 if (inSubLoop(BB)) return; 360 361 for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) { 362 Instruction &I = *--II; 363 364 // If the instruction is dead, we would try to sink it because it isn't used 365 // in the loop, instead, just delete it. 366 if (isInstructionTriviallyDead(&I, TLI)) { 367 DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n'); 368 ++II; 369 CurAST->deleteValue(&I); 370 I.eraseFromParent(); 371 Changed = true; 372 continue; 373 } 374 375 // Check to see if we can sink this instruction to the exit blocks 376 // of the loop. We can do this if the all users of the instruction are 377 // outside of the loop. In this case, it doesn't even matter if the 378 // operands of the instruction are loop invariant. 379 // 380 if (isNotUsedInLoop(I) && canSinkOrHoistInst(I)) { 381 ++II; 382 sink(I); 383 } 384 } 385 } 386 387 /// HoistRegion - Walk the specified region of the CFG (defined by all blocks 388 /// dominated by the specified block, and that are in the current loop) in depth 389 /// first order w.r.t the DominatorTree. This allows us to visit definitions 390 /// before uses, allowing us to hoist a loop body in one pass without iteration. 391 /// 392 void LICM::HoistRegion(DomTreeNode *N) { 393 assert(N != nullptr && "Null dominator tree node?"); 394 BasicBlock *BB = N->getBlock(); 395 396 // If this subregion is not in the top level loop at all, exit. 397 if (!CurLoop->contains(BB)) return; 398 399 // Only need to process the contents of this block if it is not part of a 400 // subloop (which would already have been processed). 401 if (!inSubLoop(BB)) 402 for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) { 403 Instruction &I = *II++; 404 405 // Try constant folding this instruction. If all the operands are 406 // constants, it is technically hoistable, but it would be better to just 407 // fold it. 408 if (Constant *C = ConstantFoldInstruction(&I, DL, TLI)) { 409 DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C << '\n'); 410 CurAST->copyValue(&I, C); 411 CurAST->deleteValue(&I); 412 I.replaceAllUsesWith(C); 413 I.eraseFromParent(); 414 continue; 415 } 416 417 // Try hoisting the instruction out to the preheader. We can only do this 418 // if all of the operands of the instruction are loop invariant and if it 419 // is safe to hoist the instruction. 420 // 421 if (CurLoop->hasLoopInvariantOperands(&I) && canSinkOrHoistInst(I) && 422 isSafeToExecuteUnconditionally(I)) 423 hoist(I); 424 } 425 426 const std::vector<DomTreeNode*> &Children = N->getChildren(); 427 for (unsigned i = 0, e = Children.size(); i != e; ++i) 428 HoistRegion(Children[i]); 429 } 430 431 /// canSinkOrHoistInst - Return true if the hoister and sinker can handle this 432 /// instruction. 433 /// 434 bool LICM::canSinkOrHoistInst(Instruction &I) { 435 // Loads have extra constraints we have to verify before we can hoist them. 436 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) { 437 if (!LI->isUnordered()) 438 return false; // Don't hoist volatile/atomic loads! 439 440 // Loads from constant memory are always safe to move, even if they end up 441 // in the same alias set as something that ends up being modified. 442 if (AA->pointsToConstantMemory(LI->getOperand(0))) 443 return true; 444 if (LI->getMetadata("invariant.load")) 445 return true; 446 447 // Don't hoist loads which have may-aliased stores in loop. 448 uint64_t Size = 0; 449 if (LI->getType()->isSized()) 450 Size = AA->getTypeStoreSize(LI->getType()); 451 return !pointerInvalidatedByLoop(LI->getOperand(0), Size, 452 LI->getMetadata(LLVMContext::MD_tbaa)); 453 } else if (CallInst *CI = dyn_cast<CallInst>(&I)) { 454 // Don't sink or hoist dbg info; it's legal, but not useful. 455 if (isa<DbgInfoIntrinsic>(I)) 456 return false; 457 458 // Handle simple cases by querying alias analysis. 459 AliasAnalysis::ModRefBehavior Behavior = AA->getModRefBehavior(CI); 460 if (Behavior == AliasAnalysis::DoesNotAccessMemory) 461 return true; 462 if (AliasAnalysis::onlyReadsMemory(Behavior)) { 463 // If this call only reads from memory and there are no writes to memory 464 // in the loop, we can hoist or sink the call as appropriate. 465 bool FoundMod = false; 466 for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); 467 I != E; ++I) { 468 AliasSet &AS = *I; 469 if (!AS.isForwardingAliasSet() && AS.isMod()) { 470 FoundMod = true; 471 break; 472 } 473 } 474 if (!FoundMod) return true; 475 } 476 477 // FIXME: This should use mod/ref information to see if we can hoist or 478 // sink the call. 479 480 return false; 481 } 482 483 // Only these instructions are hoistable/sinkable. 484 if (!isa<BinaryOperator>(I) && !isa<CastInst>(I) && !isa<SelectInst>(I) && 485 !isa<GetElementPtrInst>(I) && !isa<CmpInst>(I) && 486 !isa<InsertElementInst>(I) && !isa<ExtractElementInst>(I) && 487 !isa<ShuffleVectorInst>(I) && !isa<ExtractValueInst>(I) && 488 !isa<InsertValueInst>(I)) 489 return false; 490 491 return isSafeToExecuteUnconditionally(I); 492 } 493 494 /// \brief Returns true if a PHINode is a trivially replaceable with an 495 /// Instruction. 496 /// 497 /// This is true when all incoming values are that instruction. This pattern 498 /// occurs most often with LCSSA PHI nodes. 499 static bool isTriviallyReplacablePHI(PHINode &PN, Instruction &I) { 500 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) 501 if (PN.getIncomingValue(i) != &I) 502 return false; 503 504 return true; 505 } 506 507 /// isNotUsedInLoop - Return true if the only users of this instruction are 508 /// outside of the loop. If this is true, we can sink the instruction to the 509 /// exit blocks of the loop. 510 /// 511 bool LICM::isNotUsedInLoop(Instruction &I) { 512 for (User *U : I.users()) { 513 Instruction *UI = cast<Instruction>(U); 514 if (PHINode *PN = dyn_cast<PHINode>(UI)) { 515 // A PHI node where all of the incoming values are this instruction are 516 // special -- they can just be RAUW'ed with the instruction and thus 517 // don't require a use in the predecessor. This is a particular important 518 // special case because it is the pattern found in LCSSA form. 519 if (isTriviallyReplacablePHI(*PN, I)) { 520 if (CurLoop->contains(PN)) 521 return false; 522 else 523 continue; 524 } 525 526 // Otherwise, PHI node uses occur in predecessor blocks if the incoming 527 // values. Check for such a use being inside the loop. 528 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 529 if (PN->getIncomingValue(i) == &I) 530 if (CurLoop->contains(PN->getIncomingBlock(i))) 531 return false; 532 533 continue; 534 } 535 536 if (CurLoop->contains(UI)) 537 return false; 538 } 539 return true; 540 } 541 542 Instruction *LICM::CloneInstructionInExitBlock(Instruction &I, 543 BasicBlock &ExitBlock, 544 PHINode &PN) { 545 Instruction *New = I.clone(); 546 ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New); 547 if (!I.getName().empty()) New->setName(I.getName() + ".le"); 548 549 // Build LCSSA PHI nodes for any in-loop operands. Note that this is 550 // particularly cheap because we can rip off the PHI node that we're 551 // replacing for the number and blocks of the predecessors. 552 // OPT: If this shows up in a profile, we can instead finish sinking all 553 // invariant instructions, and then walk their operands to re-establish 554 // LCSSA. That will eliminate creating PHI nodes just to nuke them when 555 // sinking bottom-up. 556 for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE; 557 ++OI) 558 if (Instruction *OInst = dyn_cast<Instruction>(*OI)) 559 if (Loop *OLoop = LI->getLoopFor(OInst->getParent())) 560 if (!OLoop->contains(&PN)) { 561 PHINode *OpPN = 562 PHINode::Create(OInst->getType(), PN.getNumIncomingValues(), 563 OInst->getName() + ".lcssa", ExitBlock.begin()); 564 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) 565 OpPN->addIncoming(OInst, PN.getIncomingBlock(i)); 566 *OI = OpPN; 567 } 568 return New; 569 } 570 571 /// sink - When an instruction is found to only be used outside of the loop, 572 /// this function moves it to the exit blocks and patches up SSA form as needed. 573 /// This method is guaranteed to remove the original instruction from its 574 /// position, and may either delete it or move it to outside of the loop. 575 /// 576 void LICM::sink(Instruction &I) { 577 DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n"); 578 579 if (isa<LoadInst>(I)) ++NumMovedLoads; 580 else if (isa<CallInst>(I)) ++NumMovedCalls; 581 ++NumSunk; 582 Changed = true; 583 584 #ifndef NDEBUG 585 SmallVector<BasicBlock *, 32> ExitBlocks; 586 CurLoop->getUniqueExitBlocks(ExitBlocks); 587 SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); 588 #endif 589 590 // Clones of this instruction. Don't create more than one per exit block! 591 SmallDenseMap<BasicBlock *, Instruction *, 32> SunkCopies; 592 593 // If this instruction is only used outside of the loop, then all users are 594 // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of 595 // the instruction. 596 while (!I.use_empty()) { 597 // The user must be a PHI node. 598 PHINode *PN = cast<PHINode>(I.user_back()); 599 600 BasicBlock *ExitBlock = PN->getParent(); 601 assert(ExitBlockSet.count(ExitBlock) && 602 "The LCSSA PHI is not in an exit block!"); 603 604 Instruction *New; 605 auto It = SunkCopies.find(ExitBlock); 606 if (It != SunkCopies.end()) 607 New = It->second; 608 else 609 New = SunkCopies[ExitBlock] = 610 CloneInstructionInExitBlock(I, *ExitBlock, *PN); 611 612 PN->replaceAllUsesWith(New); 613 PN->eraseFromParent(); 614 } 615 616 CurAST->deleteValue(&I); 617 I.eraseFromParent(); 618 } 619 620 /// hoist - When an instruction is found to only use loop invariant operands 621 /// that is safe to hoist, this instruction is called to do the dirty work. 622 /// 623 void LICM::hoist(Instruction &I) { 624 DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " 625 << I << "\n"); 626 627 // Move the new node to the Preheader, before its terminator. 628 I.moveBefore(Preheader->getTerminator()); 629 630 if (isa<LoadInst>(I)) ++NumMovedLoads; 631 else if (isa<CallInst>(I)) ++NumMovedCalls; 632 ++NumHoisted; 633 Changed = true; 634 } 635 636 /// isSafeToExecuteUnconditionally - Only sink or hoist an instruction if it is 637 /// not a trapping instruction or if it is a trapping instruction and is 638 /// guaranteed to execute. 639 /// 640 bool LICM::isSafeToExecuteUnconditionally(Instruction &Inst) { 641 // If it is not a trapping instruction, it is always safe to hoist. 642 if (isSafeToSpeculativelyExecute(&Inst, DL)) 643 return true; 644 645 return isGuaranteedToExecute(Inst); 646 } 647 648 bool LICM::isGuaranteedToExecute(Instruction &Inst) { 649 650 // Somewhere in this loop there is an instruction which may throw and make us 651 // exit the loop. 652 if (MayThrow) 653 return false; 654 655 // Otherwise we have to check to make sure that the instruction dominates all 656 // of the exit blocks. If it doesn't, then there is a path out of the loop 657 // which does not execute this instruction, so we can't hoist it. 658 659 // If the instruction is in the header block for the loop (which is very 660 // common), it is always guaranteed to dominate the exit blocks. Since this 661 // is a common case, and can save some work, check it now. 662 if (Inst.getParent() == CurLoop->getHeader()) 663 return true; 664 665 // Get the exit blocks for the current loop. 666 SmallVector<BasicBlock*, 8> ExitBlocks; 667 CurLoop->getExitBlocks(ExitBlocks); 668 669 // Verify that the block dominates each of the exit blocks of the loop. 670 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 671 if (!DT->dominates(Inst.getParent(), ExitBlocks[i])) 672 return false; 673 674 // As a degenerate case, if the loop is statically infinite then we haven't 675 // proven anything since there are no exit blocks. 676 if (ExitBlocks.empty()) 677 return false; 678 679 return true; 680 } 681 682 namespace { 683 class LoopPromoter : public LoadAndStorePromoter { 684 Value *SomePtr; // Designated pointer to store to. 685 SmallPtrSet<Value*, 4> &PointerMustAliases; 686 SmallVectorImpl<BasicBlock*> &LoopExitBlocks; 687 SmallVectorImpl<Instruction*> &LoopInsertPts; 688 PredIteratorCache &PredCache; 689 AliasSetTracker &AST; 690 LoopInfo &LI; 691 DebugLoc DL; 692 int Alignment; 693 MDNode *TBAATag; 694 695 Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const { 696 if (Instruction *I = dyn_cast<Instruction>(V)) 697 if (Loop *L = LI.getLoopFor(I->getParent())) 698 if (!L->contains(BB)) { 699 // We need to create an LCSSA PHI node for the incoming value and 700 // store that. 701 PHINode *PN = PHINode::Create( 702 I->getType(), PredCache.GetNumPreds(BB), 703 I->getName() + ".lcssa", BB->begin()); 704 for (BasicBlock **PI = PredCache.GetPreds(BB); *PI; ++PI) 705 PN->addIncoming(I, *PI); 706 return PN; 707 } 708 return V; 709 } 710 711 public: 712 LoopPromoter(Value *SP, const SmallVectorImpl<Instruction *> &Insts, 713 SSAUpdater &S, SmallPtrSet<Value *, 4> &PMA, 714 SmallVectorImpl<BasicBlock *> &LEB, 715 SmallVectorImpl<Instruction *> &LIP, PredIteratorCache &PIC, 716 AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment, 717 MDNode *TBAATag) 718 : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA), 719 LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast), 720 LI(li), DL(dl), Alignment(alignment), TBAATag(TBAATag) {} 721 722 bool isInstInList(Instruction *I, 723 const SmallVectorImpl<Instruction*> &) const override { 724 Value *Ptr; 725 if (LoadInst *LI = dyn_cast<LoadInst>(I)) 726 Ptr = LI->getOperand(0); 727 else 728 Ptr = cast<StoreInst>(I)->getPointerOperand(); 729 return PointerMustAliases.count(Ptr); 730 } 731 732 void doExtraRewritesBeforeFinalDeletion() const override { 733 // Insert stores after in the loop exit blocks. Each exit block gets a 734 // store of the live-out values that feed them. Since we've already told 735 // the SSA updater about the defs in the loop and the preheader 736 // definition, it is all set and we can start using it. 737 for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) { 738 BasicBlock *ExitBlock = LoopExitBlocks[i]; 739 Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock); 740 LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock); 741 Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock); 742 Instruction *InsertPos = LoopInsertPts[i]; 743 StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos); 744 NewSI->setAlignment(Alignment); 745 NewSI->setDebugLoc(DL); 746 if (TBAATag) NewSI->setMetadata(LLVMContext::MD_tbaa, TBAATag); 747 } 748 } 749 750 void replaceLoadWithValue(LoadInst *LI, Value *V) const override { 751 // Update alias analysis. 752 AST.copyValue(LI, V); 753 } 754 void instructionDeleted(Instruction *I) const override { 755 AST.deleteValue(I); 756 } 757 }; 758 } // end anon namespace 759 760 /// PromoteAliasSet - Try to promote memory values to scalars by sinking 761 /// stores out of the loop and moving loads to before the loop. We do this by 762 /// looping over the stores in the loop, looking for stores to Must pointers 763 /// which are loop invariant. 764 /// 765 void LICM::PromoteAliasSet(AliasSet &AS, 766 SmallVectorImpl<BasicBlock*> &ExitBlocks, 767 SmallVectorImpl<Instruction*> &InsertPts, 768 PredIteratorCache &PIC) { 769 // We can promote this alias set if it has a store, if it is a "Must" alias 770 // set, if the pointer is loop invariant, and if we are not eliminating any 771 // volatile loads or stores. 772 if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() || 773 AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue())) 774 return; 775 776 assert(!AS.empty() && 777 "Must alias set should have at least one pointer element in it!"); 778 Value *SomePtr = AS.begin()->getValue(); 779 780 // It isn't safe to promote a load/store from the loop if the load/store is 781 // conditional. For example, turning: 782 // 783 // for () { if (c) *P += 1; } 784 // 785 // into: 786 // 787 // tmp = *P; for () { if (c) tmp +=1; } *P = tmp; 788 // 789 // is not safe, because *P may only be valid to access if 'c' is true. 790 // 791 // It is safe to promote P if all uses are direct load/stores and if at 792 // least one is guaranteed to be executed. 793 bool GuaranteedToExecute = false; 794 795 SmallVector<Instruction*, 64> LoopUses; 796 SmallPtrSet<Value*, 4> PointerMustAliases; 797 798 // We start with an alignment of one and try to find instructions that allow 799 // us to prove better alignment. 800 unsigned Alignment = 1; 801 MDNode *TBAATag = nullptr; 802 803 // Check that all of the pointers in the alias set have the same type. We 804 // cannot (yet) promote a memory location that is loaded and stored in 805 // different sizes. While we are at it, collect alignment and TBAA info. 806 for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) { 807 Value *ASIV = ASI->getValue(); 808 PointerMustAliases.insert(ASIV); 809 810 // Check that all of the pointers in the alias set have the same type. We 811 // cannot (yet) promote a memory location that is loaded and stored in 812 // different sizes. 813 if (SomePtr->getType() != ASIV->getType()) 814 return; 815 816 for (User *U : ASIV->users()) { 817 // Ignore instructions that are outside the loop. 818 Instruction *UI = dyn_cast<Instruction>(U); 819 if (!UI || !CurLoop->contains(UI)) 820 continue; 821 822 // If there is an non-load/store instruction in the loop, we can't promote 823 // it. 824 if (LoadInst *load = dyn_cast<LoadInst>(UI)) { 825 assert(!load->isVolatile() && "AST broken"); 826 if (!load->isSimple()) 827 return; 828 } else if (StoreInst *store = dyn_cast<StoreInst>(UI)) { 829 // Stores *of* the pointer are not interesting, only stores *to* the 830 // pointer. 831 if (UI->getOperand(1) != ASIV) 832 continue; 833 assert(!store->isVolatile() && "AST broken"); 834 if (!store->isSimple()) 835 return; 836 837 // Note that we only check GuaranteedToExecute inside the store case 838 // so that we do not introduce stores where they did not exist before 839 // (which would break the LLVM concurrency model). 840 841 // If the alignment of this instruction allows us to specify a more 842 // restrictive (and performant) alignment and if we are sure this 843 // instruction will be executed, update the alignment. 844 // Larger is better, with the exception of 0 being the best alignment. 845 unsigned InstAlignment = store->getAlignment(); 846 if ((InstAlignment > Alignment || InstAlignment == 0) && Alignment != 0) 847 if (isGuaranteedToExecute(*UI)) { 848 GuaranteedToExecute = true; 849 Alignment = InstAlignment; 850 } 851 852 if (!GuaranteedToExecute) 853 GuaranteedToExecute = isGuaranteedToExecute(*UI); 854 855 } else 856 return; // Not a load or store. 857 858 // Merge the TBAA tags. 859 if (LoopUses.empty()) { 860 // On the first load/store, just take its TBAA tag. 861 TBAATag = UI->getMetadata(LLVMContext::MD_tbaa); 862 } else if (TBAATag) { 863 TBAATag = MDNode::getMostGenericTBAA(TBAATag, 864 UI->getMetadata(LLVMContext::MD_tbaa)); 865 } 866 867 LoopUses.push_back(UI); 868 } 869 } 870 871 // If there isn't a guaranteed-to-execute instruction, we can't promote. 872 if (!GuaranteedToExecute) 873 return; 874 875 // Otherwise, this is safe to promote, lets do it! 876 DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " <<*SomePtr<<'\n'); 877 Changed = true; 878 ++NumPromoted; 879 880 // Grab a debug location for the inserted loads/stores; given that the 881 // inserted loads/stores have little relation to the original loads/stores, 882 // this code just arbitrarily picks a location from one, since any debug 883 // location is better than none. 884 DebugLoc DL = LoopUses[0]->getDebugLoc(); 885 886 // Figure out the loop exits and their insertion points, if this is the 887 // first promotion. 888 if (ExitBlocks.empty()) { 889 CurLoop->getUniqueExitBlocks(ExitBlocks); 890 InsertPts.resize(ExitBlocks.size()); 891 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 892 InsertPts[i] = ExitBlocks[i]->getFirstInsertionPt(); 893 } 894 895 // We use the SSAUpdater interface to insert phi nodes as required. 896 SmallVector<PHINode*, 16> NewPHIs; 897 SSAUpdater SSA(&NewPHIs); 898 LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks, 899 InsertPts, PIC, *CurAST, *LI, DL, Alignment, TBAATag); 900 901 // Set up the preheader to have a definition of the value. It is the live-out 902 // value from the preheader that uses in the loop will use. 903 LoadInst *PreheaderLoad = 904 new LoadInst(SomePtr, SomePtr->getName()+".promoted", 905 Preheader->getTerminator()); 906 PreheaderLoad->setAlignment(Alignment); 907 PreheaderLoad->setDebugLoc(DL); 908 if (TBAATag) PreheaderLoad->setMetadata(LLVMContext::MD_tbaa, TBAATag); 909 SSA.AddAvailableValue(Preheader, PreheaderLoad); 910 911 // Rewrite all the loads in the loop and remember all the definitions from 912 // stores in the loop. 913 Promoter.run(LoopUses); 914 915 // If the SSAUpdater didn't use the load in the preheader, just zap it now. 916 if (PreheaderLoad->use_empty()) 917 PreheaderLoad->eraseFromParent(); 918 } 919 920 921 /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. 922 void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) { 923 AliasSetTracker *AST = LoopToAliasSetMap.lookup(L); 924 if (!AST) 925 return; 926 927 AST->copyValue(From, To); 928 } 929 930 /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias 931 /// set. 932 void LICM::deleteAnalysisValue(Value *V, Loop *L) { 933 AliasSetTracker *AST = LoopToAliasSetMap.lookup(L); 934 if (!AST) 935 return; 936 937 AST->deleteValue(V); 938 } 939