contrib/llvm-project/llvm/lib/Transforms/Scalar/LoopSink.cpp

   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/IR/Dominators.h"
  45 #include "llvm/IR/Instructions.h"
  46 #include "llvm/IR/LLVMContext.h"
  47 #include "llvm/IR/Metadata.h"
  48 #include "llvm/InitializePasses.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/Local.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   // Return if any of the candidate blocks to sink into is non-cold.
 206   if (BBsToSinkInto.size() > 1) {
 207     for (auto *BB : BBsToSinkInto)
 208       if (!LoopBlockNumber.count(BB))
 209         return false;
 210   }
 211
 212   // Copy the final BBs into a vector and sort them using the total ordering
 213   // of the loop block numbers as iterating the set doesn't give a useful
 214   // order. No need to stable sort as the block numbers are a total ordering.
 215   SmallVector<BasicBlock *, 2> SortedBBsToSinkInto;
 216   SortedBBsToSinkInto.insert(SortedBBsToSinkInto.begin(), BBsToSinkInto.begin(),
 217                              BBsToSinkInto.end());
 218   llvm::sort(SortedBBsToSinkInto, [&](BasicBlock *A, BasicBlock *B) {
 219     return LoopBlockNumber.find(A)->second < LoopBlockNumber.find(B)->second;
 220   });
 221
 222   BasicBlock *MoveBB = *SortedBBsToSinkInto.begin();
 223   // FIXME: Optimize the efficiency for cloned value replacement. The current
 224   //        implementation is O(SortedBBsToSinkInto.size() * I.num_uses()).
 225   for (BasicBlock *N : makeArrayRef(SortedBBsToSinkInto).drop_front(1)) {
 226     assert(LoopBlockNumber.find(N)->second >
 227                LoopBlockNumber.find(MoveBB)->second &&
 228            "BBs not sorted!");
 229     // Clone I and replace its uses.
 230     Instruction *IC = I.clone();
 231     IC->setName(I.getName());
 232     IC->insertBefore(&*N->getFirstInsertionPt());
 233     // Replaces uses of I with IC in N
 234     I.replaceUsesWithIf(IC, [N](Use &U) {
 235       return cast<Instruction>(U.getUser())->getParent() == N;
 236     });
 237     // Replaces uses of I with IC in blocks dominated by N
 238     replaceDominatedUsesWith(&I, IC, DT, N);
 239     LLVM_DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName()
 240                       << '\n');
 241     NumLoopSunkCloned++;
 242   }
 243   LLVM_DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n');
 244   NumLoopSunk++;
 245   I.moveBefore(&*MoveBB->getFirstInsertionPt());
 246
 247   return true;
 248 }
 249
 250 /// Sinks instructions from loop's preheader to the loop body if the
 251 /// sum frequency of inserted copy is smaller than preheader's frequency.
 252 static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI,
 253                                           DominatorTree &DT,
 254                                           BlockFrequencyInfo &BFI,
 255                                           ScalarEvolution *SE) {
 256   BasicBlock *Preheader = L.getLoopPreheader();
 257   if (!Preheader)
 258     return false;
 259
 260   // Enable LoopSink only when runtime profile is available.
 261   // With static profile, the sinking decision may be sub-optimal.
 262   if (!Preheader->getParent()->hasProfileData())
 263     return false;
 264
 265   const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader);
 266   // If there are no basic blocks with lower frequency than the preheader then
 267   // we can avoid the detailed analysis as we will never find profitable sinking
 268   // opportunities.
 269   if (all_of(L.blocks(), [&](const BasicBlock *BB) {
 270         return BFI.getBlockFreq(BB) > PreheaderFreq;
 271       }))
 272     return false;
 273
 274   bool Changed = false;
 275   AliasSetTracker CurAST(AA);
 276
 277   // Compute alias set.
 278   for (BasicBlock *BB : L.blocks())
 279     CurAST.add(*BB);
 280   CurAST.add(*Preheader);
 281
 282   // Sort loop's basic blocks by frequency
 283   SmallVector<BasicBlock *, 10> ColdLoopBBs;
 284   SmallDenseMap<BasicBlock *, int, 16> LoopBlockNumber;
 285   int i = 0;
 286   for (BasicBlock *B : L.blocks())
 287     if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) {
 288       ColdLoopBBs.push_back(B);
 289       LoopBlockNumber[B] = ++i;
 290     }
 291   llvm::stable_sort(ColdLoopBBs, [&](BasicBlock *A, BasicBlock *B) {
 292     return BFI.getBlockFreq(A) < BFI.getBlockFreq(B);
 293   });
 294
 295   // Traverse preheader's instructions in reverse order becaue if A depends
 296   // on B (A appears after B), A needs to be sinked first before B can be
 297   // sinked.
 298   for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) {
 299     Instruction *I = &*II++;
 300     // No need to check for instruction's operands are loop invariant.
 301     assert(L.hasLoopInvariantOperands(I) &&
 302            "Insts in a loop's preheader should have loop invariant operands!");
 303     if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr, false))
 304       continue;
 305     if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI))
 306       Changed = true;
 307   }
 308
 309   if (Changed && SE)
 310     SE->forgetLoopDispositions(&L);
 311   return Changed;
 312 }
 313
 314 PreservedAnalyses LoopSinkPass::run(Function &F, FunctionAnalysisManager &FAM) {
 315   LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);
 316   // Nothing to do if there are no loops.
 317   if (LI.empty())
 318     return PreservedAnalyses::all();
 319
 320   AAResults &AA = FAM.getResult<AAManager>(F);
 321   DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);
 322   BlockFrequencyInfo &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
 323
 324   // We want to do a postorder walk over the loops. Since loops are a tree this
 325   // is equivalent to a reversed preorder walk and preorder is easy to compute
 326   // without recursion. Since we reverse the preorder, we will visit siblings
 327   // in reverse program order. This isn't expected to matter at all but is more
 328   // consistent with sinking algorithms which generally work bottom-up.
 329   SmallVector<Loop *, 4> PreorderLoops = LI.getLoopsInPreorder();
 330
 331   bool Changed = false;
 332   do {
 333     Loop &L = *PreorderLoops.pop_back_val();
 334
 335     // Note that we don't pass SCEV here because it is only used to invalidate
 336     // loops in SCEV and we don't preserve (or request) SCEV at all making that
 337     // unnecessary.
 338     Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI,
 339                                              /*ScalarEvolution*/ nullptr);
 340   } while (!PreorderLoops.empty());
 341
 342   if (!Changed)
 343     return PreservedAnalyses::all();
 344
 345   PreservedAnalyses PA;
 346   PA.preserveSet<CFGAnalyses>();
 347   return PA;
 348 }
 349
 350 namespace {
 351 struct LegacyLoopSinkPass : public LoopPass {
 352   static char ID;
 353   LegacyLoopSinkPass() : LoopPass(ID) {
 354     initializeLegacyLoopSinkPassPass(*PassRegistry::getPassRegistry());
 355   }
 356
 357   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
 358     if (skipLoop(L))
 359       return false;
 360
 361     auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
 362     return sinkLoopInvariantInstructions(
 363         *L, getAnalysis<AAResultsWrapperPass>().getAAResults(),
 364         getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
 365         getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
 366         getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(),
 367         SE ? &SE->getSE() : nullptr);
 368   }
 369
 370   void getAnalysisUsage(AnalysisUsage &AU) const override {
 371     AU.setPreservesCFG();
 372     AU.addRequired<BlockFrequencyInfoWrapperPass>();
 373     getLoopAnalysisUsage(AU);
 374   }
 375 };
 376 }
 377
 378 char LegacyLoopSinkPass::ID = 0;
 379 INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false,
 380                       false)
 381 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 382 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
 383 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false)
 384
 385 Pass *llvm::createLoopSinkPass() { return new LegacyLoopSinkPass(); }