xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/Scalar/LoopSink.cpp (revision 6966ac055c3b7a39266fb982493330df7a097997)
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