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/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 (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) {
 327     Instruction *I = &*II++;
 328     // No need to check for instruction's operands are loop invariant.
 329     assert(L.hasLoopInvariantOperands(I) &&
 330            "Insts in a loop's preheader should have loop invariant operands!");
 331     if (!canSinkOrHoistInst(*I, &AA, &DT, &L, CurAST, MSSAU.get(), false,
 332                             LICMFlags.get()))
 333       continue;
 334     if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI,
 335                         MSSAU.get()))
 336       Changed = true;
 337   }
 338
 339   if (Changed && SE)
 340     SE->forgetLoopDispositions(&L);
 341   return Changed;
 342 }
 343
 344 static void computeAliasSet(Loop &L, BasicBlock &Preheader,
 345                             AliasSetTracker &CurAST) {
 346   for (BasicBlock *BB : L.blocks())
 347     CurAST.add(*BB);
 348   CurAST.add(Preheader);
 349 }
 350
 351 PreservedAnalyses LoopSinkPass::run(Function &F, FunctionAnalysisManager &FAM) {
 352   LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);
 353   // Nothing to do if there are no loops.
 354   if (LI.empty())
 355     return PreservedAnalyses::all();
 356
 357   AAResults &AA = FAM.getResult<AAManager>(F);
 358   DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);
 359   BlockFrequencyInfo &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
 360
 361   MemorySSA *MSSA = EnableMSSAInLoopSink
 362                         ? &FAM.getResult<MemorySSAAnalysis>(F).getMSSA()
 363                         : nullptr;
 364
 365   // We want to do a postorder walk over the loops. Since loops are a tree this
 366   // is equivalent to a reversed preorder walk and preorder is easy to compute
 367   // without recursion. Since we reverse the preorder, we will visit siblings
 368   // in reverse program order. This isn't expected to matter at all but is more
 369   // consistent with sinking algorithms which generally work bottom-up.
 370   SmallVector<Loop *, 4> PreorderLoops = LI.getLoopsInPreorder();
 371
 372   bool Changed = false;
 373   do {
 374     Loop &L = *PreorderLoops.pop_back_val();
 375
 376     BasicBlock *Preheader = L.getLoopPreheader();
 377     if (!Preheader)
 378       continue;
 379
 380     // Enable LoopSink only when runtime profile is available.
 381     // With static profile, the sinking decision may be sub-optimal.
 382     if (!Preheader->getParent()->hasProfileData())
 383       continue;
 384
 385     std::unique_ptr<AliasSetTracker> CurAST;
 386     if (!EnableMSSAInLoopSink) {
 387       CurAST = std::make_unique<AliasSetTracker>(AA);
 388       computeAliasSet(L, *Preheader, *CurAST.get());
 389     }
 390
 391     // Note that we don't pass SCEV here because it is only used to invalidate
 392     // loops in SCEV and we don't preserve (or request) SCEV at all making that
 393     // unnecessary.
 394     Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI,
 395                                              /*ScalarEvolution*/ nullptr,
 396                                              CurAST.get(), MSSA);
 397   } while (!PreorderLoops.empty());
 398
 399   if (!Changed)
 400     return PreservedAnalyses::all();
 401
 402   PreservedAnalyses PA;
 403   PA.preserveSet<CFGAnalyses>();
 404
 405   if (MSSA) {
 406     PA.preserve<MemorySSAAnalysis>();
 407
 408     if (VerifyMemorySSA)
 409       MSSA->verifyMemorySSA();
 410   }
 411
 412   return PA;
 413 }
 414
 415 namespace {
 416 struct LegacyLoopSinkPass : public LoopPass {
 417   static char ID;
 418   LegacyLoopSinkPass() : LoopPass(ID) {
 419     initializeLegacyLoopSinkPassPass(*PassRegistry::getPassRegistry());
 420   }
 421
 422   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
 423     if (skipLoop(L))
 424       return false;
 425
 426     BasicBlock *Preheader = L->getLoopPreheader();
 427     if (!Preheader)
 428       return false;
 429
 430     // Enable LoopSink only when runtime profile is available.
 431     // With static profile, the sinking decision may be sub-optimal.
 432     if (!Preheader->getParent()->hasProfileData())
 433       return false;
 434
 435     AAResults &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
 436     auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
 437     std::unique_ptr<AliasSetTracker> CurAST;
 438     MemorySSA *MSSA = nullptr;
 439     if (EnableMSSAInLegacyLoopSink)
 440       MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
 441     else {
 442       CurAST = std::make_unique<AliasSetTracker>(AA);
 443       computeAliasSet(*L, *Preheader, *CurAST.get());
 444     }
 445
 446     bool Changed = sinkLoopInvariantInstructions(
 447         *L, AA, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
 448         getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
 449         getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(),
 450         SE ? &SE->getSE() : nullptr, CurAST.get(), MSSA);
 451
 452     if (MSSA && VerifyMemorySSA)
 453       MSSA->verifyMemorySSA();
 454
 455     return Changed;
 456   }
 457
 458   void getAnalysisUsage(AnalysisUsage &AU) const override {
 459     AU.setPreservesCFG();
 460     AU.addRequired<BlockFrequencyInfoWrapperPass>();
 461     getLoopAnalysisUsage(AU);
 462     if (EnableMSSAInLegacyLoopSink) {
 463       AU.addRequired<MemorySSAWrapperPass>();
 464       AU.addPreserved<MemorySSAWrapperPass>();
 465     }
 466   }
 467 };
 468 }
 469
 470 char LegacyLoopSinkPass::ID = 0;
 471 INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false,
 472                       false)
 473 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 474 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
 475 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 476 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false)
 477
 478 Pass *llvm::createLoopSinkPass() { return new LegacyLoopSinkPass(); }