1 //===-- LoopSink.cpp - Loop Sink Pass ------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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:
16 // * It only handles sinking of instructions from the loop's preheader to the
18 // * It uses alias set tracker to get more accurate alias info
19 // * It uses block frequency info to find the optimal sinking locations
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 //===----------------------------------------------------------------------===//
33 #include "llvm/ADT/Statistic.h"
34 #include "llvm/Analysis/AliasAnalysis.h"
35 #include "llvm/Analysis/AliasSetTracker.h"
36 #include "llvm/Analysis/BasicAliasAnalysis.h"
37 #include "llvm/Analysis/BlockFrequencyInfo.h"
38 #include "llvm/Analysis/Loads.h"
39 #include "llvm/Analysis/LoopInfo.h"
40 #include "llvm/Analysis/LoopPass.h"
41 #include "llvm/Analysis/LoopPassManager.h"
42 #include "llvm/Analysis/ScalarEvolution.h"
43 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
44 #include "llvm/IR/Dominators.h"
45 #include "llvm/IR/Instructions.h"
46 #include "llvm/IR/LLVMContext.h"
47 #include "llvm/IR/Metadata.h"
48 #include "llvm/Support/CommandLine.h"
49 #include "llvm/Transforms/Scalar.h"
50 #include "llvm/Transforms/Utils/Local.h"
51 #include "llvm/Transforms/Utils/LoopUtils.h"
54 #define DEBUG_TYPE "loopsink"
56 STATISTIC(NumLoopSunk, "Number of instructions sunk into loop");
57 STATISTIC(NumLoopSunkCloned, "Number of cloned instructions sunk into loop");
59 static cl::opt<unsigned> SinkFrequencyPercentThreshold(
60 "sink-freq-percent-threshold", cl::Hidden, cl::init(90),
61 cl::desc("Do not sink instructions that require cloning unless they "
62 "execute less than this percent of the time."));
64 static cl::opt<unsigned> MaxNumberOfUseBBsForSinking(
65 "max-uses-for-sinking", cl::Hidden, cl::init(30),
66 cl::desc("Do not sink instructions that have too many uses."));
68 /// Return adjusted total frequency of \p BBs.
70 /// * If there is only one BB, sinking instruction will not introduce code
71 /// size increase. Thus there is no need to adjust the frequency.
72 /// * If there are more than one BB, sinking would lead to code size increase.
73 /// In this case, we add some "tax" to the total frequency to make it harder
75 /// Freq(Preheader) = 100
76 /// Freq(BBs) = sum(50, 49) = 99
77 /// Even if Freq(BBs) < Freq(Preheader), we will not sink from Preheade to
78 /// BBs as the difference is too small to justify the code size increase.
79 /// To model this, The adjusted Freq(BBs) will be:
80 /// AdjustedFreq(BBs) = 99 / SinkFrequencyPercentThreshold%
81 static BlockFrequency adjustedSumFreq(SmallPtrSetImpl<BasicBlock *> &BBs,
82 BlockFrequencyInfo &BFI) {
84 for (BasicBlock *B : BBs)
85 T += BFI.getBlockFreq(B);
87 T /= BranchProbability(SinkFrequencyPercentThreshold, 100);
91 /// Return a set of basic blocks to insert sinked instructions.
93 /// The returned set of basic blocks (BBsToSinkInto) should satisfy:
95 /// * Inside the loop \p L
96 /// * For each UseBB in \p UseBBs, there is at least one BB in BBsToSinkInto
97 /// that domintates the UseBB
98 /// * Has minimum total frequency that is no greater than preheader frequency
100 /// The purpose of the function is to find the optimal sinking points to
101 /// minimize execution cost, which is defined as "sum of frequency of
103 /// As a result, the returned BBsToSinkInto needs to have minimum total
105 /// Additionally, if the total frequency of BBsToSinkInto exceeds preheader
106 /// frequency, the optimal solution is not sinking (return empty set).
108 /// \p ColdLoopBBs is used to help find the optimal sinking locations.
109 /// It stores a list of BBs that is:
111 /// * Inside the loop \p L
112 /// * Has a frequency no larger than the loop's preheader
113 /// * Sorted by BB frequency
115 /// The complexity of the function is O(UseBBs.size() * ColdLoopBBs.size()).
116 /// To avoid expensive computation, we cap the maximum UseBBs.size() in its
118 static SmallPtrSet<BasicBlock *, 2>
119 findBBsToSinkInto(const Loop &L, const SmallPtrSetImpl<BasicBlock *> &UseBBs,
120 const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
121 DominatorTree &DT, BlockFrequencyInfo &BFI) {
122 SmallPtrSet<BasicBlock *, 2> BBsToSinkInto;
123 if (UseBBs.size() == 0)
124 return BBsToSinkInto;
126 BBsToSinkInto.insert(UseBBs.begin(), UseBBs.end());
127 SmallPtrSet<BasicBlock *, 2> BBsDominatedByColdestBB;
129 // For every iteration:
130 // * Pick the ColdestBB from ColdLoopBBs
131 // * Find the set BBsDominatedByColdestBB that satisfy:
132 // - BBsDominatedByColdestBB is a subset of BBsToSinkInto
133 // - Every BB in BBsDominatedByColdestBB is dominated by ColdestBB
134 // * If Freq(ColdestBB) < Freq(BBsDominatedByColdestBB), remove
135 // BBsDominatedByColdestBB from BBsToSinkInto, add ColdestBB to
137 for (BasicBlock *ColdestBB : ColdLoopBBs) {
138 BBsDominatedByColdestBB.clear();
139 for (BasicBlock *SinkedBB : BBsToSinkInto)
140 if (DT.dominates(ColdestBB, SinkedBB))
141 BBsDominatedByColdestBB.insert(SinkedBB);
142 if (BBsDominatedByColdestBB.size() == 0)
144 if (adjustedSumFreq(BBsDominatedByColdestBB, BFI) >
145 BFI.getBlockFreq(ColdestBB)) {
146 for (BasicBlock *DominatedBB : BBsDominatedByColdestBB) {
147 BBsToSinkInto.erase(DominatedBB);
149 BBsToSinkInto.insert(ColdestBB);
153 // If the total frequency of BBsToSinkInto is larger than preheader frequency,
155 if (adjustedSumFreq(BBsToSinkInto, BFI) >
156 BFI.getBlockFreq(L.getLoopPreheader()))
157 BBsToSinkInto.clear();
158 return BBsToSinkInto;
161 // Sinks \p I from the loop \p L's preheader to its uses. Returns true if
162 // sinking is successful.
163 // \p LoopBlockNumber is used to sort the insertion blocks to ensure
165 static bool sinkInstruction(Loop &L, Instruction &I,
166 const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
167 const SmallDenseMap<BasicBlock *, int, 16> &LoopBlockNumber,
168 LoopInfo &LI, DominatorTree &DT,
169 BlockFrequencyInfo &BFI) {
170 // Compute the set of blocks in loop L which contain a use of I.
171 SmallPtrSet<BasicBlock *, 2> BBs;
172 for (auto &U : I.uses()) {
173 Instruction *UI = cast<Instruction>(U.getUser());
174 // We cannot sink I to PHI-uses.
175 if (dyn_cast<PHINode>(UI))
177 // We cannot sink I if it has uses outside of the loop.
178 if (!L.contains(LI.getLoopFor(UI->getParent())))
180 BBs.insert(UI->getParent());
183 // findBBsToSinkInto is O(BBs.size() * ColdLoopBBs.size()). We cap the max
184 // BBs.size() to avoid expensive computation.
185 // FIXME: Handle code size growth for min_size and opt_size.
186 if (BBs.size() > MaxNumberOfUseBBsForSinking)
189 // Find the set of BBs that we should insert a copy of I.
190 SmallPtrSet<BasicBlock *, 2> BBsToSinkInto =
191 findBBsToSinkInto(L, BBs, ColdLoopBBs, DT, BFI);
192 if (BBsToSinkInto.empty())
195 // Copy the final BBs into a vector and sort them using the total ordering
196 // of the loop block numbers as iterating the set doesn't give a useful
197 // order. No need to stable sort as the block numbers are a total ordering.
198 SmallVector<BasicBlock *, 2> SortedBBsToSinkInto;
199 SortedBBsToSinkInto.insert(SortedBBsToSinkInto.begin(), BBsToSinkInto.begin(),
200 BBsToSinkInto.end());
201 std::sort(SortedBBsToSinkInto.begin(), SortedBBsToSinkInto.end(),
202 [&](BasicBlock *A, BasicBlock *B) {
203 return *LoopBlockNumber.find(A) < *LoopBlockNumber.find(B);
206 BasicBlock *MoveBB = *SortedBBsToSinkInto.begin();
207 // FIXME: Optimize the efficiency for cloned value replacement. The current
208 // implementation is O(SortedBBsToSinkInto.size() * I.num_uses()).
209 for (BasicBlock *N : SortedBBsToSinkInto) {
212 // Clone I and replace its uses.
213 Instruction *IC = I.clone();
214 IC->setName(I.getName());
215 IC->insertBefore(&*N->getFirstInsertionPt());
216 // Replaces uses of I with IC in N
217 for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE;) {
219 auto *I = cast<Instruction>(U.getUser());
220 if (I->getParent() == N)
223 // Replaces uses of I with IC in blocks dominated by N
224 replaceDominatedUsesWith(&I, IC, DT, N);
225 DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName()
229 DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n');
231 I.moveBefore(&*MoveBB->getFirstInsertionPt());
236 /// Sinks instructions from loop's preheader to the loop body if the
237 /// sum frequency of inserted copy is smaller than preheader's frequency.
238 static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI,
240 BlockFrequencyInfo &BFI,
241 ScalarEvolution *SE) {
242 BasicBlock *Preheader = L.getLoopPreheader();
246 // Enable LoopSink only when runtime profile is available.
247 // With static profile, the sinking decision may be sub-optimal.
248 if (!Preheader->getParent()->getEntryCount())
251 const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader);
252 // If there are no basic blocks with lower frequency than the preheader then
253 // we can avoid the detailed analysis as we will never find profitable sinking
255 if (all_of(L.blocks(), [&](const BasicBlock *BB) {
256 return BFI.getBlockFreq(BB) > PreheaderFreq;
260 bool Changed = false;
261 AliasSetTracker CurAST(AA);
263 // Compute alias set.
264 for (BasicBlock *BB : L.blocks())
267 // Sort loop's basic blocks by frequency
268 SmallVector<BasicBlock *, 10> ColdLoopBBs;
269 SmallDenseMap<BasicBlock *, int, 16> LoopBlockNumber;
271 for (BasicBlock *B : L.blocks())
272 if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) {
273 ColdLoopBBs.push_back(B);
274 LoopBlockNumber[B] = ++i;
276 std::stable_sort(ColdLoopBBs.begin(), ColdLoopBBs.end(),
277 [&](BasicBlock *A, BasicBlock *B) {
278 return BFI.getBlockFreq(A) < BFI.getBlockFreq(B);
281 // Traverse preheader's instructions in reverse order becaue if A depends
282 // on B (A appears after B), A needs to be sinked first before B can be
284 for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) {
285 Instruction *I = &*II++;
286 if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr))
288 if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI))
293 SE->forgetLoopDispositions(&L);
298 struct LegacyLoopSinkPass : public LoopPass {
300 LegacyLoopSinkPass() : LoopPass(ID) {
301 initializeLegacyLoopSinkPassPass(*PassRegistry::getPassRegistry());
304 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
308 auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
309 return sinkLoopInvariantInstructions(
310 *L, getAnalysis<AAResultsWrapperPass>().getAAResults(),
311 getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
312 getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
313 getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(),
314 SE ? &SE->getSE() : nullptr);
317 void getAnalysisUsage(AnalysisUsage &AU) const override {
318 AU.setPreservesCFG();
319 AU.addRequired<BlockFrequencyInfoWrapperPass>();
320 getLoopAnalysisUsage(AU);
325 char LegacyLoopSinkPass::ID = 0;
326 INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false,
328 INITIALIZE_PASS_DEPENDENCY(LoopPass)
329 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
330 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false)
332 Pass *llvm::createLoopSinkPass() { return new LegacyLoopSinkPass(); }