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/ScalarEvolution.h" 43 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" 44 #include "llvm/Transforms/Utils/Local.h" 45 #include "llvm/IR/Dominators.h" 46 #include "llvm/IR/Instructions.h" 47 #include "llvm/IR/LLVMContext.h" 48 #include "llvm/IR/Metadata.h" 49 #include "llvm/Support/CommandLine.h" 50 #include "llvm/Transforms/Scalar.h" 51 #include "llvm/Transforms/Scalar/LoopPassManager.h" 52 #include "llvm/Transforms/Utils/LoopUtils.h" 53 using namespace llvm; 54 55 #define DEBUG_TYPE "loopsink" 56 57 STATISTIC(NumLoopSunk, "Number of instructions sunk into loop"); 58 STATISTIC(NumLoopSunkCloned, "Number of cloned instructions sunk into loop"); 59 60 static cl::opt<unsigned> SinkFrequencyPercentThreshold( 61 "sink-freq-percent-threshold", cl::Hidden, cl::init(90), 62 cl::desc("Do not sink instructions that require cloning unless they " 63 "execute less than this percent of the time.")); 64 65 static cl::opt<unsigned> MaxNumberOfUseBBsForSinking( 66 "max-uses-for-sinking", cl::Hidden, cl::init(30), 67 cl::desc("Do not sink instructions that have too many uses.")); 68 69 /// Return adjusted total frequency of \p BBs. 70 /// 71 /// * If there is only one BB, sinking instruction will not introduce code 72 /// size increase. Thus there is no need to adjust the frequency. 73 /// * If there are more than one BB, sinking would lead to code size increase. 74 /// In this case, we add some "tax" to the total frequency to make it harder 75 /// to sink. E.g. 76 /// Freq(Preheader) = 100 77 /// Freq(BBs) = sum(50, 49) = 99 78 /// Even if Freq(BBs) < Freq(Preheader), we will not sink from Preheade to 79 /// BBs as the difference is too small to justify the code size increase. 80 /// To model this, The adjusted Freq(BBs) will be: 81 /// AdjustedFreq(BBs) = 99 / SinkFrequencyPercentThreshold% 82 static BlockFrequency adjustedSumFreq(SmallPtrSetImpl<BasicBlock *> &BBs, 83 BlockFrequencyInfo &BFI) { 84 BlockFrequency T = 0; 85 for (BasicBlock *B : BBs) 86 T += BFI.getBlockFreq(B); 87 if (BBs.size() > 1) 88 T /= BranchProbability(SinkFrequencyPercentThreshold, 100); 89 return T; 90 } 91 92 /// Return a set of basic blocks to insert sinked instructions. 93 /// 94 /// The returned set of basic blocks (BBsToSinkInto) should satisfy: 95 /// 96 /// * Inside the loop \p L 97 /// * For each UseBB in \p UseBBs, there is at least one BB in BBsToSinkInto 98 /// that domintates the UseBB 99 /// * Has minimum total frequency that is no greater than preheader frequency 100 /// 101 /// The purpose of the function is to find the optimal sinking points to 102 /// minimize execution cost, which is defined as "sum of frequency of 103 /// BBsToSinkInto". 104 /// As a result, the returned BBsToSinkInto needs to have minimum total 105 /// frequency. 106 /// Additionally, if the total frequency of BBsToSinkInto exceeds preheader 107 /// frequency, the optimal solution is not sinking (return empty set). 108 /// 109 /// \p ColdLoopBBs is used to help find the optimal sinking locations. 110 /// It stores a list of BBs that is: 111 /// 112 /// * Inside the loop \p L 113 /// * Has a frequency no larger than the loop's preheader 114 /// * Sorted by BB frequency 115 /// 116 /// The complexity of the function is O(UseBBs.size() * ColdLoopBBs.size()). 117 /// To avoid expensive computation, we cap the maximum UseBBs.size() in its 118 /// caller. 119 static SmallPtrSet<BasicBlock *, 2> 120 findBBsToSinkInto(const Loop &L, const SmallPtrSetImpl<BasicBlock *> &UseBBs, 121 const SmallVectorImpl<BasicBlock *> &ColdLoopBBs, 122 DominatorTree &DT, BlockFrequencyInfo &BFI) { 123 SmallPtrSet<BasicBlock *, 2> BBsToSinkInto; 124 if (UseBBs.size() == 0) 125 return BBsToSinkInto; 126 127 BBsToSinkInto.insert(UseBBs.begin(), UseBBs.end()); 128 SmallPtrSet<BasicBlock *, 2> BBsDominatedByColdestBB; 129 130 // For every iteration: 131 // * Pick the ColdestBB from ColdLoopBBs 132 // * Find the set BBsDominatedByColdestBB that satisfy: 133 // - BBsDominatedByColdestBB is a subset of BBsToSinkInto 134 // - Every BB in BBsDominatedByColdestBB is dominated by ColdestBB 135 // * If Freq(ColdestBB) < Freq(BBsDominatedByColdestBB), remove 136 // BBsDominatedByColdestBB from BBsToSinkInto, add ColdestBB to 137 // BBsToSinkInto 138 for (BasicBlock *ColdestBB : ColdLoopBBs) { 139 BBsDominatedByColdestBB.clear(); 140 for (BasicBlock *SinkedBB : BBsToSinkInto) 141 if (DT.dominates(ColdestBB, SinkedBB)) 142 BBsDominatedByColdestBB.insert(SinkedBB); 143 if (BBsDominatedByColdestBB.size() == 0) 144 continue; 145 if (adjustedSumFreq(BBsDominatedByColdestBB, BFI) > 146 BFI.getBlockFreq(ColdestBB)) { 147 for (BasicBlock *DominatedBB : BBsDominatedByColdestBB) { 148 BBsToSinkInto.erase(DominatedBB); 149 } 150 BBsToSinkInto.insert(ColdestBB); 151 } 152 } 153 154 // Can't sink into blocks that have no valid insertion point. 155 for (BasicBlock *BB : BBsToSinkInto) { 156 if (BB->getFirstInsertionPt() == BB->end()) { 157 BBsToSinkInto.clear(); 158 break; 159 } 160 } 161 162 // If the total frequency of BBsToSinkInto is larger than preheader frequency, 163 // do not sink. 164 if (adjustedSumFreq(BBsToSinkInto, BFI) > 165 BFI.getBlockFreq(L.getLoopPreheader())) 166 BBsToSinkInto.clear(); 167 return BBsToSinkInto; 168 } 169 170 // Sinks \p I from the loop \p L's preheader to its uses. Returns true if 171 // sinking is successful. 172 // \p LoopBlockNumber is used to sort the insertion blocks to ensure 173 // determinism. 174 static bool sinkInstruction(Loop &L, Instruction &I, 175 const SmallVectorImpl<BasicBlock *> &ColdLoopBBs, 176 const SmallDenseMap<BasicBlock *, int, 16> &LoopBlockNumber, 177 LoopInfo &LI, DominatorTree &DT, 178 BlockFrequencyInfo &BFI) { 179 // Compute the set of blocks in loop L which contain a use of I. 180 SmallPtrSet<BasicBlock *, 2> BBs; 181 for (auto &U : I.uses()) { 182 Instruction *UI = cast<Instruction>(U.getUser()); 183 // We cannot sink I to PHI-uses. 184 if (dyn_cast<PHINode>(UI)) 185 return false; 186 // We cannot sink I if it has uses outside of the loop. 187 if (!L.contains(LI.getLoopFor(UI->getParent()))) 188 return false; 189 BBs.insert(UI->getParent()); 190 } 191 192 // findBBsToSinkInto is O(BBs.size() * ColdLoopBBs.size()). We cap the max 193 // BBs.size() to avoid expensive computation. 194 // FIXME: Handle code size growth for min_size and opt_size. 195 if (BBs.size() > MaxNumberOfUseBBsForSinking) 196 return false; 197 198 // Find the set of BBs that we should insert a copy of I. 199 SmallPtrSet<BasicBlock *, 2> BBsToSinkInto = 200 findBBsToSinkInto(L, BBs, ColdLoopBBs, DT, BFI); 201 if (BBsToSinkInto.empty()) 202 return false; 203 204 // Return if any of the candidate blocks to sink into is non-cold. 205 if (BBsToSinkInto.size() > 1) { 206 for (auto *BB : BBsToSinkInto) 207 if (!LoopBlockNumber.count(BB)) 208 return false; 209 } 210 211 // Copy the final BBs into a vector and sort them using the total ordering 212 // of the loop block numbers as iterating the set doesn't give a useful 213 // order. No need to stable sort as the block numbers are a total ordering. 214 SmallVector<BasicBlock *, 2> SortedBBsToSinkInto; 215 SortedBBsToSinkInto.insert(SortedBBsToSinkInto.begin(), BBsToSinkInto.begin(), 216 BBsToSinkInto.end()); 217 llvm::sort(SortedBBsToSinkInto, [&](BasicBlock *A, BasicBlock *B) { 218 return LoopBlockNumber.find(A)->second < LoopBlockNumber.find(B)->second; 219 }); 220 221 BasicBlock *MoveBB = *SortedBBsToSinkInto.begin(); 222 // FIXME: Optimize the efficiency for cloned value replacement. The current 223 // implementation is O(SortedBBsToSinkInto.size() * I.num_uses()). 224 for (BasicBlock *N : makeArrayRef(SortedBBsToSinkInto).drop_front(1)) { 225 assert(LoopBlockNumber.find(N)->second > 226 LoopBlockNumber.find(MoveBB)->second && 227 "BBs not sorted!"); 228 // Clone I and replace its uses. 229 Instruction *IC = I.clone(); 230 IC->setName(I.getName()); 231 IC->insertBefore(&*N->getFirstInsertionPt()); 232 // Replaces uses of I with IC in N 233 for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE;) { 234 Use &U = *UI++; 235 auto *I = cast<Instruction>(U.getUser()); 236 if (I->getParent() == N) 237 U.set(IC); 238 } 239 // Replaces uses of I with IC in blocks dominated by N 240 replaceDominatedUsesWith(&I, IC, DT, N); 241 LLVM_DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName() 242 << '\n'); 243 NumLoopSunkCloned++; 244 } 245 LLVM_DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n'); 246 NumLoopSunk++; 247 I.moveBefore(&*MoveBB->getFirstInsertionPt()); 248 249 return true; 250 } 251 252 /// Sinks instructions from loop's preheader to the loop body if the 253 /// sum frequency of inserted copy is smaller than preheader's frequency. 254 static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI, 255 DominatorTree &DT, 256 BlockFrequencyInfo &BFI, 257 ScalarEvolution *SE) { 258 BasicBlock *Preheader = L.getLoopPreheader(); 259 if (!Preheader) 260 return false; 261 262 // Enable LoopSink only when runtime profile is available. 263 // With static profile, the sinking decision may be sub-optimal. 264 if (!Preheader->getParent()->hasProfileData()) 265 return false; 266 267 const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader); 268 // If there are no basic blocks with lower frequency than the preheader then 269 // we can avoid the detailed analysis as we will never find profitable sinking 270 // opportunities. 271 if (all_of(L.blocks(), [&](const BasicBlock *BB) { 272 return BFI.getBlockFreq(BB) > PreheaderFreq; 273 })) 274 return false; 275 276 bool Changed = false; 277 AliasSetTracker CurAST(AA); 278 279 // Compute alias set. 280 for (BasicBlock *BB : L.blocks()) 281 CurAST.add(*BB); 282 CurAST.add(*Preheader); 283 284 // Sort loop's basic blocks by frequency 285 SmallVector<BasicBlock *, 10> ColdLoopBBs; 286 SmallDenseMap<BasicBlock *, int, 16> LoopBlockNumber; 287 int i = 0; 288 for (BasicBlock *B : L.blocks()) 289 if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) { 290 ColdLoopBBs.push_back(B); 291 LoopBlockNumber[B] = ++i; 292 } 293 llvm::stable_sort(ColdLoopBBs, [&](BasicBlock *A, BasicBlock *B) { 294 return BFI.getBlockFreq(A) < BFI.getBlockFreq(B); 295 }); 296 297 // Traverse preheader's instructions in reverse order becaue if A depends 298 // on B (A appears after B), A needs to be sinked first before B can be 299 // sinked. 300 for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) { 301 Instruction *I = &*II++; 302 // No need to check for instruction's operands are loop invariant. 303 assert(L.hasLoopInvariantOperands(I) && 304 "Insts in a loop's preheader should have loop invariant operands!"); 305 if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr, false)) 306 continue; 307 if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI)) 308 Changed = true; 309 } 310 311 if (Changed && SE) 312 SE->forgetLoopDispositions(&L); 313 return Changed; 314 } 315 316 PreservedAnalyses LoopSinkPass::run(Function &F, FunctionAnalysisManager &FAM) { 317 LoopInfo &LI = FAM.getResult<LoopAnalysis>(F); 318 // Nothing to do if there are no loops. 319 if (LI.empty()) 320 return PreservedAnalyses::all(); 321 322 AAResults &AA = FAM.getResult<AAManager>(F); 323 DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F); 324 BlockFrequencyInfo &BFI = FAM.getResult<BlockFrequencyAnalysis>(F); 325 326 // We want to do a postorder walk over the loops. Since loops are a tree this 327 // is equivalent to a reversed preorder walk and preorder is easy to compute 328 // without recursion. Since we reverse the preorder, we will visit siblings 329 // in reverse program order. This isn't expected to matter at all but is more 330 // consistent with sinking algorithms which generally work bottom-up. 331 SmallVector<Loop *, 4> PreorderLoops = LI.getLoopsInPreorder(); 332 333 bool Changed = false; 334 do { 335 Loop &L = *PreorderLoops.pop_back_val(); 336 337 // Note that we don't pass SCEV here because it is only used to invalidate 338 // loops in SCEV and we don't preserve (or request) SCEV at all making that 339 // unnecessary. 340 Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI, 341 /*ScalarEvolution*/ nullptr); 342 } while (!PreorderLoops.empty()); 343 344 if (!Changed) 345 return PreservedAnalyses::all(); 346 347 PreservedAnalyses PA; 348 PA.preserveSet<CFGAnalyses>(); 349 return PA; 350 } 351 352 namespace { 353 struct LegacyLoopSinkPass : public LoopPass { 354 static char ID; 355 LegacyLoopSinkPass() : LoopPass(ID) { 356 initializeLegacyLoopSinkPassPass(*PassRegistry::getPassRegistry()); 357 } 358 359 bool runOnLoop(Loop *L, LPPassManager &LPM) override { 360 if (skipLoop(L)) 361 return false; 362 363 auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>(); 364 return sinkLoopInvariantInstructions( 365 *L, getAnalysis<AAResultsWrapperPass>().getAAResults(), 366 getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), 367 getAnalysis<DominatorTreeWrapperPass>().getDomTree(), 368 getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(), 369 SE ? &SE->getSE() : nullptr); 370 } 371 372 void getAnalysisUsage(AnalysisUsage &AU) const override { 373 AU.setPreservesCFG(); 374 AU.addRequired<BlockFrequencyInfoWrapperPass>(); 375 getLoopAnalysisUsage(AU); 376 } 377 }; 378 } 379 380 char LegacyLoopSinkPass::ID = 0; 381 INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, 382 false) 383 INITIALIZE_PASS_DEPENDENCY(LoopPass) 384 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) 385 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false) 386 387 Pass *llvm::createLoopSinkPass() { return new LegacyLoopSinkPass(); } 388