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