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