1 //===-- LoopSink.cpp - Loop Sink Pass -------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This pass does the inverse transformation of what LICM does. 10 // It traverses all of the instructions in the loop's preheader and sinks 11 // them to the loop body where frequency is lower than the loop's preheader. 12 // This pass is a reverse-transformation of LICM. It differs from the Sink 13 // pass in the following ways: 14 // 15 // * It only handles sinking of instructions from the loop's preheader to the 16 // loop's body 17 // * It uses alias set tracker to get more accurate alias info 18 // * It uses block frequency info to find the optimal sinking locations 19 // 20 // Overall algorithm: 21 // 22 // For I in Preheader: 23 // InsertBBs = BBs that uses I 24 // For BB in sorted(LoopBBs): 25 // DomBBs = BBs in InsertBBs that are dominated by BB 26 // if freq(DomBBs) > freq(BB) 27 // InsertBBs = UseBBs - DomBBs + BB 28 // For BB in InsertBBs: 29 // Insert I at BB's beginning 30 // 31 //===----------------------------------------------------------------------===// 32 33 #include "llvm/Transforms/Scalar/LoopSink.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/BlockFrequencyInfo.h" 39 #include "llvm/Analysis/Loads.h" 40 #include "llvm/Analysis/LoopInfo.h" 41 #include "llvm/Analysis/LoopPass.h" 42 #include "llvm/Analysis/MemorySSA.h" 43 #include "llvm/Analysis/MemorySSAUpdater.h" 44 #include "llvm/Analysis/ScalarEvolution.h" 45 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" 46 #include "llvm/IR/Dominators.h" 47 #include "llvm/IR/Instructions.h" 48 #include "llvm/IR/LLVMContext.h" 49 #include "llvm/IR/Metadata.h" 50 #include "llvm/InitializePasses.h" 51 #include "llvm/Support/CommandLine.h" 52 #include "llvm/Transforms/Scalar.h" 53 #include "llvm/Transforms/Scalar/LoopPassManager.h" 54 #include "llvm/Transforms/Utils/Local.h" 55 #include "llvm/Transforms/Utils/LoopUtils.h" 56 using namespace llvm; 57 58 #define DEBUG_TYPE "loopsink" 59 60 STATISTIC(NumLoopSunk, "Number of instructions sunk into loop"); 61 STATISTIC(NumLoopSunkCloned, "Number of cloned instructions sunk into loop"); 62 63 static cl::opt<unsigned> SinkFrequencyPercentThreshold( 64 "sink-freq-percent-threshold", cl::Hidden, cl::init(90), 65 cl::desc("Do not sink instructions that require cloning unless they " 66 "execute less than this percent of the time.")); 67 68 static cl::opt<unsigned> MaxNumberOfUseBBsForSinking( 69 "max-uses-for-sinking", cl::Hidden, cl::init(30), 70 cl::desc("Do not sink instructions that have too many uses.")); 71 72 static cl::opt<bool> EnableMSSAInLoopSink( 73 "enable-mssa-in-loop-sink", cl::Hidden, cl::init(false), 74 cl::desc("Enable MemorySSA for LoopSink in new pass manager")); 75 76 static cl::opt<bool> EnableMSSAInLegacyLoopSink( 77 "enable-mssa-in-legacy-loop-sink", cl::Hidden, cl::init(false), 78 cl::desc("Enable MemorySSA for LoopSink in legacy pass manager")); 79 80 /// Return adjusted total frequency of \p BBs. 81 /// 82 /// * If there is only one BB, sinking instruction will not introduce code 83 /// size increase. Thus there is no need to adjust the frequency. 84 /// * If there are more than one BB, sinking would lead to code size increase. 85 /// In this case, we add some "tax" to the total frequency to make it harder 86 /// to sink. E.g. 87 /// Freq(Preheader) = 100 88 /// Freq(BBs) = sum(50, 49) = 99 89 /// Even if Freq(BBs) < Freq(Preheader), we will not sink from Preheade to 90 /// BBs as the difference is too small to justify the code size increase. 91 /// To model this, The adjusted Freq(BBs) will be: 92 /// AdjustedFreq(BBs) = 99 / SinkFrequencyPercentThreshold% 93 static BlockFrequency adjustedSumFreq(SmallPtrSetImpl<BasicBlock *> &BBs, 94 BlockFrequencyInfo &BFI) { 95 BlockFrequency T = 0; 96 for (BasicBlock *B : BBs) 97 T += BFI.getBlockFreq(B); 98 if (BBs.size() > 1) 99 T /= BranchProbability(SinkFrequencyPercentThreshold, 100); 100 return T; 101 } 102 103 /// Return a set of basic blocks to insert sinked instructions. 104 /// 105 /// The returned set of basic blocks (BBsToSinkInto) should satisfy: 106 /// 107 /// * Inside the loop \p L 108 /// * For each UseBB in \p UseBBs, there is at least one BB in BBsToSinkInto 109 /// that domintates the UseBB 110 /// * Has minimum total frequency that is no greater than preheader frequency 111 /// 112 /// The purpose of the function is to find the optimal sinking points to 113 /// minimize execution cost, which is defined as "sum of frequency of 114 /// BBsToSinkInto". 115 /// As a result, the returned BBsToSinkInto needs to have minimum total 116 /// frequency. 117 /// Additionally, if the total frequency of BBsToSinkInto exceeds preheader 118 /// frequency, the optimal solution is not sinking (return empty set). 119 /// 120 /// \p ColdLoopBBs is used to help find the optimal sinking locations. 121 /// It stores a list of BBs that is: 122 /// 123 /// * Inside the loop \p L 124 /// * Has a frequency no larger than the loop's preheader 125 /// * Sorted by BB frequency 126 /// 127 /// The complexity of the function is O(UseBBs.size() * ColdLoopBBs.size()). 128 /// To avoid expensive computation, we cap the maximum UseBBs.size() in its 129 /// caller. 130 static SmallPtrSet<BasicBlock *, 2> 131 findBBsToSinkInto(const Loop &L, const SmallPtrSetImpl<BasicBlock *> &UseBBs, 132 const SmallVectorImpl<BasicBlock *> &ColdLoopBBs, 133 DominatorTree &DT, BlockFrequencyInfo &BFI) { 134 SmallPtrSet<BasicBlock *, 2> BBsToSinkInto; 135 if (UseBBs.size() == 0) 136 return BBsToSinkInto; 137 138 BBsToSinkInto.insert(UseBBs.begin(), UseBBs.end()); 139 SmallPtrSet<BasicBlock *, 2> BBsDominatedByColdestBB; 140 141 // For every iteration: 142 // * Pick the ColdestBB from ColdLoopBBs 143 // * Find the set BBsDominatedByColdestBB that satisfy: 144 // - BBsDominatedByColdestBB is a subset of BBsToSinkInto 145 // - Every BB in BBsDominatedByColdestBB is dominated by ColdestBB 146 // * If Freq(ColdestBB) < Freq(BBsDominatedByColdestBB), remove 147 // BBsDominatedByColdestBB from BBsToSinkInto, add ColdestBB to 148 // BBsToSinkInto 149 for (BasicBlock *ColdestBB : ColdLoopBBs) { 150 BBsDominatedByColdestBB.clear(); 151 for (BasicBlock *SinkedBB : BBsToSinkInto) 152 if (DT.dominates(ColdestBB, SinkedBB)) 153 BBsDominatedByColdestBB.insert(SinkedBB); 154 if (BBsDominatedByColdestBB.size() == 0) 155 continue; 156 if (adjustedSumFreq(BBsDominatedByColdestBB, BFI) > 157 BFI.getBlockFreq(ColdestBB)) { 158 for (BasicBlock *DominatedBB : BBsDominatedByColdestBB) { 159 BBsToSinkInto.erase(DominatedBB); 160 } 161 BBsToSinkInto.insert(ColdestBB); 162 } 163 } 164 165 // Can't sink into blocks that have no valid insertion point. 166 for (BasicBlock *BB : BBsToSinkInto) { 167 if (BB->getFirstInsertionPt() == BB->end()) { 168 BBsToSinkInto.clear(); 169 break; 170 } 171 } 172 173 // If the total frequency of BBsToSinkInto is larger than preheader frequency, 174 // do not sink. 175 if (adjustedSumFreq(BBsToSinkInto, BFI) > 176 BFI.getBlockFreq(L.getLoopPreheader())) 177 BBsToSinkInto.clear(); 178 return BBsToSinkInto; 179 } 180 181 // Sinks \p I from the loop \p L's preheader to its uses. Returns true if 182 // sinking is successful. 183 // \p LoopBlockNumber is used to sort the insertion blocks to ensure 184 // determinism. 185 static bool sinkInstruction( 186 Loop &L, Instruction &I, const SmallVectorImpl<BasicBlock *> &ColdLoopBBs, 187 const SmallDenseMap<BasicBlock *, int, 16> &LoopBlockNumber, LoopInfo &LI, 188 DominatorTree &DT, BlockFrequencyInfo &BFI, MemorySSAUpdater *MSSAU) { 189 // Compute the set of blocks in loop L which contain a use of I. 190 SmallPtrSet<BasicBlock *, 2> BBs; 191 for (auto &U : I.uses()) { 192 Instruction *UI = cast<Instruction>(U.getUser()); 193 // We cannot sink I to PHI-uses. 194 if (dyn_cast<PHINode>(UI)) 195 return false; 196 // We cannot sink I if it has uses outside of the loop. 197 if (!L.contains(LI.getLoopFor(UI->getParent()))) 198 return false; 199 BBs.insert(UI->getParent()); 200 } 201 202 // findBBsToSinkInto is O(BBs.size() * ColdLoopBBs.size()). We cap the max 203 // BBs.size() to avoid expensive computation. 204 // FIXME: Handle code size growth for min_size and opt_size. 205 if (BBs.size() > MaxNumberOfUseBBsForSinking) 206 return false; 207 208 // Find the set of BBs that we should insert a copy of I. 209 SmallPtrSet<BasicBlock *, 2> BBsToSinkInto = 210 findBBsToSinkInto(L, BBs, ColdLoopBBs, DT, BFI); 211 if (BBsToSinkInto.empty()) 212 return false; 213 214 // Return if any of the candidate blocks to sink into is non-cold. 215 if (BBsToSinkInto.size() > 1) { 216 for (auto *BB : BBsToSinkInto) 217 if (!LoopBlockNumber.count(BB)) 218 return false; 219 } 220 221 // Copy the final BBs into a vector and sort them using the total ordering 222 // of the loop block numbers as iterating the set doesn't give a useful 223 // order. No need to stable sort as the block numbers are a total ordering. 224 SmallVector<BasicBlock *, 2> SortedBBsToSinkInto; 225 SortedBBsToSinkInto.insert(SortedBBsToSinkInto.begin(), BBsToSinkInto.begin(), 226 BBsToSinkInto.end()); 227 llvm::sort(SortedBBsToSinkInto, [&](BasicBlock *A, BasicBlock *B) { 228 return LoopBlockNumber.find(A)->second < LoopBlockNumber.find(B)->second; 229 }); 230 231 BasicBlock *MoveBB = *SortedBBsToSinkInto.begin(); 232 // FIXME: Optimize the efficiency for cloned value replacement. The current 233 // implementation is O(SortedBBsToSinkInto.size() * I.num_uses()). 234 for (BasicBlock *N : makeArrayRef(SortedBBsToSinkInto).drop_front(1)) { 235 assert(LoopBlockNumber.find(N)->second > 236 LoopBlockNumber.find(MoveBB)->second && 237 "BBs not sorted!"); 238 // Clone I and replace its uses. 239 Instruction *IC = I.clone(); 240 IC->setName(I.getName()); 241 IC->insertBefore(&*N->getFirstInsertionPt()); 242 243 if (MSSAU && MSSAU->getMemorySSA()->getMemoryAccess(&I)) { 244 // Create a new MemoryAccess and let MemorySSA set its defining access. 245 MemoryAccess *NewMemAcc = 246 MSSAU->createMemoryAccessInBB(IC, nullptr, N, MemorySSA::Beginning); 247 if (NewMemAcc) { 248 if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc)) 249 MSSAU->insertDef(MemDef, /*RenameUses=*/true); 250 else { 251 auto *MemUse = cast<MemoryUse>(NewMemAcc); 252 MSSAU->insertUse(MemUse, /*RenameUses=*/true); 253 } 254 } 255 } 256 257 // Replaces uses of I with IC in N 258 I.replaceUsesWithIf(IC, [N](Use &U) { 259 return cast<Instruction>(U.getUser())->getParent() == N; 260 }); 261 // Replaces uses of I with IC in blocks dominated by N 262 replaceDominatedUsesWith(&I, IC, DT, N); 263 LLVM_DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName() 264 << '\n'); 265 NumLoopSunkCloned++; 266 } 267 LLVM_DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n'); 268 NumLoopSunk++; 269 I.moveBefore(&*MoveBB->getFirstInsertionPt()); 270 271 if (MSSAU) 272 if (MemoryUseOrDef *OldMemAcc = cast_or_null<MemoryUseOrDef>( 273 MSSAU->getMemorySSA()->getMemoryAccess(&I))) 274 MSSAU->moveToPlace(OldMemAcc, MoveBB, MemorySSA::Beginning); 275 276 return true; 277 } 278 279 /// Sinks instructions from loop's preheader to the loop body if the 280 /// sum frequency of inserted copy is smaller than preheader's frequency. 281 static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI, 282 DominatorTree &DT, 283 BlockFrequencyInfo &BFI, 284 ScalarEvolution *SE, 285 AliasSetTracker *CurAST, 286 MemorySSA *MSSA) { 287 BasicBlock *Preheader = L.getLoopPreheader(); 288 assert(Preheader && "Expected loop to have preheader"); 289 290 assert(Preheader->getParent()->hasProfileData() && 291 "Unexpected call when profile data unavailable."); 292 293 const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader); 294 // If there are no basic blocks with lower frequency than the preheader then 295 // we can avoid the detailed analysis as we will never find profitable sinking 296 // opportunities. 297 if (all_of(L.blocks(), [&](const BasicBlock *BB) { 298 return BFI.getBlockFreq(BB) > PreheaderFreq; 299 })) 300 return false; 301 302 std::unique_ptr<MemorySSAUpdater> MSSAU; 303 std::unique_ptr<SinkAndHoistLICMFlags> LICMFlags; 304 if (MSSA) { 305 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA); 306 LICMFlags = 307 std::make_unique<SinkAndHoistLICMFlags>(/*IsSink=*/true, &L, MSSA); 308 } 309 310 bool Changed = false; 311 312 // Sort loop's basic blocks by frequency 313 SmallVector<BasicBlock *, 10> ColdLoopBBs; 314 SmallDenseMap<BasicBlock *, int, 16> LoopBlockNumber; 315 int i = 0; 316 for (BasicBlock *B : L.blocks()) 317 if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) { 318 ColdLoopBBs.push_back(B); 319 LoopBlockNumber[B] = ++i; 320 } 321 llvm::stable_sort(ColdLoopBBs, [&](BasicBlock *A, BasicBlock *B) { 322 return BFI.getBlockFreq(A) < BFI.getBlockFreq(B); 323 }); 324 325 // Traverse preheader's instructions in reverse order becaue if A depends 326 // on B (A appears after B), A needs to be sinked first before B can be 327 // sinked. 328 for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) { 329 Instruction *I = &*II++; 330 // No need to check for instruction's operands are loop invariant. 331 assert(L.hasLoopInvariantOperands(I) && 332 "Insts in a loop's preheader should have loop invariant operands!"); 333 if (!canSinkOrHoistInst(*I, &AA, &DT, &L, CurAST, MSSAU.get(), false, 334 LICMFlags.get())) 335 continue; 336 if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI, 337 MSSAU.get())) 338 Changed = true; 339 } 340 341 if (Changed && SE) 342 SE->forgetLoopDispositions(&L); 343 return Changed; 344 } 345 346 static void computeAliasSet(Loop &L, BasicBlock &Preheader, 347 AliasSetTracker &CurAST) { 348 for (BasicBlock *BB : L.blocks()) 349 CurAST.add(*BB); 350 CurAST.add(Preheader); 351 } 352 353 PreservedAnalyses LoopSinkPass::run(Function &F, FunctionAnalysisManager &FAM) { 354 LoopInfo &LI = FAM.getResult<LoopAnalysis>(F); 355 // Nothing to do if there are no loops. 356 if (LI.empty()) 357 return PreservedAnalyses::all(); 358 359 AAResults &AA = FAM.getResult<AAManager>(F); 360 DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F); 361 BlockFrequencyInfo &BFI = FAM.getResult<BlockFrequencyAnalysis>(F); 362 363 MemorySSA *MSSA = EnableMSSAInLoopSink 364 ? &FAM.getResult<MemorySSAAnalysis>(F).getMSSA() 365 : nullptr; 366 367 // We want to do a postorder walk over the loops. Since loops are a tree this 368 // is equivalent to a reversed preorder walk and preorder is easy to compute 369 // without recursion. Since we reverse the preorder, we will visit siblings 370 // in reverse program order. This isn't expected to matter at all but is more 371 // consistent with sinking algorithms which generally work bottom-up. 372 SmallVector<Loop *, 4> PreorderLoops = LI.getLoopsInPreorder(); 373 374 bool Changed = false; 375 do { 376 Loop &L = *PreorderLoops.pop_back_val(); 377 378 BasicBlock *Preheader = L.getLoopPreheader(); 379 if (!Preheader) 380 continue; 381 382 // Enable LoopSink only when runtime profile is available. 383 // With static profile, the sinking decision may be sub-optimal. 384 if (!Preheader->getParent()->hasProfileData()) 385 continue; 386 387 std::unique_ptr<AliasSetTracker> CurAST; 388 if (!EnableMSSAInLoopSink) { 389 CurAST = std::make_unique<AliasSetTracker>(AA); 390 computeAliasSet(L, *Preheader, *CurAST.get()); 391 } 392 393 // Note that we don't pass SCEV here because it is only used to invalidate 394 // loops in SCEV and we don't preserve (or request) SCEV at all making that 395 // unnecessary. 396 Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI, 397 /*ScalarEvolution*/ nullptr, 398 CurAST.get(), MSSA); 399 } while (!PreorderLoops.empty()); 400 401 if (!Changed) 402 return PreservedAnalyses::all(); 403 404 PreservedAnalyses PA; 405 PA.preserveSet<CFGAnalyses>(); 406 407 if (MSSA) { 408 PA.preserve<MemorySSAAnalysis>(); 409 410 if (VerifyMemorySSA) 411 MSSA->verifyMemorySSA(); 412 } 413 414 return PA; 415 } 416 417 namespace { 418 struct LegacyLoopSinkPass : public LoopPass { 419 static char ID; 420 LegacyLoopSinkPass() : LoopPass(ID) { 421 initializeLegacyLoopSinkPassPass(*PassRegistry::getPassRegistry()); 422 } 423 424 bool runOnLoop(Loop *L, LPPassManager &LPM) override { 425 if (skipLoop(L)) 426 return false; 427 428 BasicBlock *Preheader = L->getLoopPreheader(); 429 if (!Preheader) 430 return false; 431 432 // Enable LoopSink only when runtime profile is available. 433 // With static profile, the sinking decision may be sub-optimal. 434 if (!Preheader->getParent()->hasProfileData()) 435 return false; 436 437 AAResults &AA = getAnalysis<AAResultsWrapperPass>().getAAResults(); 438 auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>(); 439 std::unique_ptr<AliasSetTracker> CurAST; 440 MemorySSA *MSSA = nullptr; 441 if (EnableMSSAInLegacyLoopSink) 442 MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA(); 443 else { 444 CurAST = std::make_unique<AliasSetTracker>(AA); 445 computeAliasSet(*L, *Preheader, *CurAST.get()); 446 } 447 448 bool Changed = sinkLoopInvariantInstructions( 449 *L, AA, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), 450 getAnalysis<DominatorTreeWrapperPass>().getDomTree(), 451 getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(), 452 SE ? &SE->getSE() : nullptr, CurAST.get(), MSSA); 453 454 if (MSSA && VerifyMemorySSA) 455 MSSA->verifyMemorySSA(); 456 457 return Changed; 458 } 459 460 void getAnalysisUsage(AnalysisUsage &AU) const override { 461 AU.setPreservesCFG(); 462 AU.addRequired<BlockFrequencyInfoWrapperPass>(); 463 getLoopAnalysisUsage(AU); 464 if (EnableMSSAInLegacyLoopSink) { 465 AU.addRequired<MemorySSAWrapperPass>(); 466 AU.addPreserved<MemorySSAWrapperPass>(); 467 } 468 } 469 }; 470 } 471 472 char LegacyLoopSinkPass::ID = 0; 473 INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, 474 false) 475 INITIALIZE_PASS_DEPENDENCY(LoopPass) 476 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) 477 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass) 478 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false) 479 480 Pass *llvm::createLoopSinkPass() { return new LegacyLoopSinkPass(); } 481