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

   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 #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"
  52 using namespace llvm;
  53
  54 #define DEBUG_TYPE "loopsink"
  55
  56 STATISTIC(NumLoopSunk, "Number of instructions sunk into loop");
  57 STATISTIC(NumLoopSunkCloned, "Number of cloned instructions sunk into loop");
  58
  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."));
  63
  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."));
  67
  68 /// Return adjusted total frequency of \p BBs.
  69 ///
  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
  74 ///   to sink. E.g.
  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) {
  83   BlockFrequency T = 0;
  84   for (BasicBlock *B : BBs)
  85     T += BFI.getBlockFreq(B);
  86   if (BBs.size() > 1)
  87     T /= BranchProbability(SinkFrequencyPercentThreshold, 100);
  88   return T;
  89 }
  90
  91 /// Return a set of basic blocks to insert sinked instructions.
  92 ///
  93 /// The returned set of basic blocks (BBsToSinkInto) should satisfy:
  94 ///
  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
  99 ///
 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
 102 /// BBsToSinkInto".
 103 /// As a result, the returned BBsToSinkInto needs to have minimum total
 104 /// frequency.
 105 /// Additionally, if the total frequency of BBsToSinkInto exceeds preheader
 106 /// frequency, the optimal solution is not sinking (return empty set).
 107 ///
 108 /// \p ColdLoopBBs is used to help find the optimal sinking locations.
 109 /// It stores a list of BBs that is:
 110 ///
 111 /// * Inside the loop \p L
 112 /// * Has a frequency no larger than the loop's preheader
 113 /// * Sorted by BB frequency
 114 ///
 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
 117 /// caller.
 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;
 125
 126   BBsToSinkInto.insert(UseBBs.begin(), UseBBs.end());
 127   SmallPtrSet<BasicBlock *, 2> BBsDominatedByColdestBB;
 128
 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
 136   //     BBsToSinkInto
 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)
 143       continue;
 144     if (adjustedSumFreq(BBsDominatedByColdestBB, BFI) >
 145         BFI.getBlockFreq(ColdestBB)) {
 146       for (BasicBlock *DominatedBB : BBsDominatedByColdestBB) {
 147         BBsToSinkInto.erase(DominatedBB);
 148       }
 149       BBsToSinkInto.insert(ColdestBB);
 150     }
 151   }
 152
 153   // If the total frequency of BBsToSinkInto is larger than preheader frequency,
 154   // do not sink.
 155   if (adjustedSumFreq(BBsToSinkInto, BFI) >
 156       BFI.getBlockFreq(L.getLoopPreheader()))
 157     BBsToSinkInto.clear();
 158   return BBsToSinkInto;
 159 }
 160
 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
 164 // determinism.
 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))
 176       return false;
 177     // We cannot sink I if it has uses outside of the loop.
 178     if (!L.contains(LI.getLoopFor(UI->getParent())))
 179       return false;
 180     BBs.insert(UI->getParent());
 181   }
 182
 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)
 187     return false;
 188
 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())
 193     return false;
 194
 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);
 204             });
 205
 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) {
 210     if (N == MoveBB)
 211       continue;
 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;) {
 218       Use &U = *UI++;
 219       auto *I = cast<Instruction>(U.getUser());
 220       if (I->getParent() == N)
 221         U.set(IC);
 222     }
 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()
 226                  << '\n');
 227     NumLoopSunkCloned++;
 228   }
 229   DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n');
 230   NumLoopSunk++;
 231   I.moveBefore(&*MoveBB->getFirstInsertionPt());
 232
 233   return true;
 234 }
 235
 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,
 239                                           DominatorTree &DT,
 240                                           BlockFrequencyInfo &BFI,
 241                                           ScalarEvolution *SE) {
 242   BasicBlock *Preheader = L.getLoopPreheader();
 243   if (!Preheader)
 244     return false;
 245
 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())
 249     return false;
 250
 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
 254   // opportunities.
 255   if (all_of(L.blocks(), [&](const BasicBlock *BB) {
 256         return BFI.getBlockFreq(BB) > PreheaderFreq;
 257       }))
 258     return false;
 259
 260   bool Changed = false;
 261   AliasSetTracker CurAST(AA);
 262
 263   // Compute alias set.
 264   for (BasicBlock *BB : L.blocks())
 265     CurAST.add(*BB);
 266
 267   // Sort loop's basic blocks by frequency
 268   SmallVector<BasicBlock *, 10> ColdLoopBBs;
 269   SmallDenseMap<BasicBlock *, int, 16> LoopBlockNumber;
 270   int i = 0;
 271   for (BasicBlock *B : L.blocks())
 272     if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) {
 273       ColdLoopBBs.push_back(B);
 274       LoopBlockNumber[B] = ++i;
 275     }
 276   std::stable_sort(ColdLoopBBs.begin(), ColdLoopBBs.end(),
 277                    [&](BasicBlock *A, BasicBlock *B) {
 278                      return BFI.getBlockFreq(A) < BFI.getBlockFreq(B);
 279                    });
 280
 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
 283   // sinked.
 284   for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) {
 285     Instruction *I = &*II++;
 286     if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr))
 287       continue;
 288     if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI))
 289       Changed = true;
 290   }
 291
 292   if (Changed && SE)
 293     SE->forgetLoopDispositions(&L);
 294   return Changed;
 295 }
 296
 297 namespace {
 298 struct LegacyLoopSinkPass : public LoopPass {
 299   static char ID;
 300   LegacyLoopSinkPass() : LoopPass(ID) {
 301     initializeLegacyLoopSinkPassPass(*PassRegistry::getPassRegistry());
 302   }
 303
 304   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
 305     if (skipLoop(L))
 306       return false;
 307
 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);
 315   }
 316
 317   void getAnalysisUsage(AnalysisUsage &AU) const override {
 318     AU.setPreservesCFG();
 319     AU.addRequired<BlockFrequencyInfoWrapperPass>();
 320     getLoopAnalysisUsage(AU);
 321   }
 322 };
 323 }
 324
 325 char LegacyLoopSinkPass::ID = 0;
 326 INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false,
 327                       false)
 328 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 329 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
 330 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false)
 331
 332 Pass *llvm::createLoopSinkPass() { return new LegacyLoopSinkPass(); }