• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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%
adjustedSumFreq(SmallPtrSetImpl<BasicBlock * > & BBs,BlockFrequencyInfo & BFI)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>
findBBsToSinkInto(const Loop & L,const SmallPtrSetImpl<BasicBlock * > & UseBBs,const SmallVectorImpl<BasicBlock * > & ColdLoopBBs,DominatorTree & DT,BlockFrequencyInfo & BFI)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.
sinkInstruction(Loop & L,Instruction & I,const SmallVectorImpl<BasicBlock * > & ColdLoopBBs,const SmallDenseMap<BasicBlock *,int,16> & LoopBlockNumber,LoopInfo & LI,DominatorTree & DT,BlockFrequencyInfo & BFI)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.
sinkLoopInvariantInstructions(Loop & L,AAResults & AA,LoopInfo & LI,DominatorTree & DT,BlockFrequencyInfo & BFI,ScalarEvolution * SE)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 
run(Function & F,FunctionAnalysisManager & FAM)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;
LegacyLoopSinkPass__anoncebf8f450411::LegacyLoopSinkPass351   LegacyLoopSinkPass() : LoopPass(ID) {
352     initializeLegacyLoopSinkPassPass(*PassRegistry::getPassRegistry());
353   }
354 
runOnLoop__anoncebf8f450411::LegacyLoopSinkPass355   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 
getAnalysisUsage__anoncebf8f450411::LegacyLoopSinkPass368   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)
INITIALIZE_PASS_DEPENDENCY(LoopPass)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