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