llvm/lib/Transforms/Scalar/Sink.cpp

   1 //===-- Sink.cpp - Code Sinking -------------------------------------------===//
   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 moves instructions into successor blocks, when possible, so that
  10 // they aren't executed on paths where their results aren't needed.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Transforms/Scalar/Sink.h"
  15 #include "llvm/ADT/Statistic.h"
  16 #include "llvm/Analysis/AliasAnalysis.h"
  17 #include "llvm/Analysis/LoopInfo.h"
  18 #include "llvm/IR/Dominators.h"
  19 #include "llvm/InitializePasses.h"
  20 #include "llvm/Support/Debug.h"
  21 #include "llvm/Support/raw_ostream.h"
  22 #include "llvm/Transforms/Scalar.h"
  23 using namespace llvm;
  24
  25 #define DEBUG_TYPE "sink"
  26
  27 STATISTIC(NumSunk, "Number of instructions sunk");
  28 STATISTIC(NumSinkIter, "Number of sinking iterations");
  29
  30 static bool isSafeToMove(Instruction *Inst, AliasAnalysis &AA,
  31                          SmallPtrSetImpl<Instruction *> &Stores) {
  32
  33   if (Inst->mayWriteToMemory()) {
  34     Stores.insert(Inst);
  35     return false;
  36   }
  37
  38   if (LoadInst *L = dyn_cast<LoadInst>(Inst)) {
  39     MemoryLocation Loc = MemoryLocation::get(L);
  40     for (Instruction *S : Stores)
  41       if (isModSet(AA.getModRefInfo(S, Loc)))
  42         return false;
  43   }
  44
  45   if (Inst->isTerminator() || isa<PHINode>(Inst) || Inst->isEHPad() ||
  46       Inst->mayThrow() || !Inst->willReturn())
  47     return false;
  48
  49   if (auto *Call = dyn_cast<CallBase>(Inst)) {
  50     // Convergent operations cannot be made control-dependent on additional
  51     // values.
  52     if (Call->isConvergent())
  53       return false;
  54
  55     for (Instruction *S : Stores)
  56       if (isModSet(AA.getModRefInfo(S, Call)))
  57         return false;
  58   }
  59
  60   return true;
  61 }
  62
  63 /// IsAcceptableTarget - Return true if it is possible to sink the instruction
  64 /// in the specified basic block.
  65 static bool IsAcceptableTarget(Instruction *Inst, BasicBlock *SuccToSinkTo,
  66                                DominatorTree &DT, LoopInfo &LI) {
  67   assert(Inst && "Instruction to be sunk is null");
  68   assert(SuccToSinkTo && "Candidate sink target is null");
  69
  70   // It's never legal to sink an instruction into an EH-pad block.
  71   if (SuccToSinkTo->isEHPad())
  72     return false;
  73
  74   // If the block has multiple predecessors, this would introduce computation
  75   // on different code paths.  We could split the critical edge, but for now we
  76   // just punt.
  77   // FIXME: Split critical edges if not backedges.
  78   if (SuccToSinkTo->getUniquePredecessor() != Inst->getParent()) {
  79     // We cannot sink a load across a critical edge - there may be stores in
  80     // other code paths.
  81     if (Inst->mayReadFromMemory() &&
  82         !Inst->hasMetadata(LLVMContext::MD_invariant_load))
  83       return false;
  84
  85     // We don't want to sink across a critical edge if we don't dominate the
  86     // successor. We could be introducing calculations to new code paths.
  87     if (!DT.dominates(Inst->getParent(), SuccToSinkTo))
  88       return false;
  89
  90     // Don't sink instructions into a loop.
  91     Loop *succ = LI.getLoopFor(SuccToSinkTo);
  92     Loop *cur = LI.getLoopFor(Inst->getParent());
  93     if (succ != nullptr && succ != cur)
  94       return false;
  95   }
  96
  97   return true;
  98 }
  99
 100 /// SinkInstruction - Determine whether it is safe to sink the specified machine
 101 /// instruction out of its current block into a successor.
 102 static bool SinkInstruction(Instruction *Inst,
 103                             SmallPtrSetImpl<Instruction *> &Stores,
 104                             DominatorTree &DT, LoopInfo &LI, AAResults &AA) {
 105
 106   // Don't sink static alloca instructions.  CodeGen assumes allocas outside the
 107   // entry block are dynamically sized stack objects.
 108   if (AllocaInst *AI = dyn_cast<AllocaInst>(Inst))
 109     if (AI->isStaticAlloca())
 110       return false;
 111
 112   // Check if it's safe to move the instruction.
 113   if (!isSafeToMove(Inst, AA, Stores))
 114     return false;
 115
 116   // FIXME: This should include support for sinking instructions within the
 117   // block they are currently in to shorten the live ranges.  We often get
 118   // instructions sunk into the top of a large block, but it would be better to
 119   // also sink them down before their first use in the block.  This xform has to
 120   // be careful not to *increase* register pressure though, e.g. sinking
 121   // "x = y + z" down if it kills y and z would increase the live ranges of y
 122   // and z and only shrink the live range of x.
 123
 124   // SuccToSinkTo - This is the successor to sink this instruction to, once we
 125   // decide.
 126   BasicBlock *SuccToSinkTo = nullptr;
 127
 128   // Find the nearest common dominator of all users as the candidate.
 129   BasicBlock *BB = Inst->getParent();
 130   for (Use &U : Inst->uses()) {
 131     Instruction *UseInst = cast<Instruction>(U.getUser());
 132     BasicBlock *UseBlock = UseInst->getParent();
 133     if (PHINode *PN = dyn_cast<PHINode>(UseInst)) {
 134       // PHI nodes use the operand in the predecessor block, not the block with
 135       // the PHI.
 136       unsigned Num = PHINode::getIncomingValueNumForOperand(U.getOperandNo());
 137       UseBlock = PN->getIncomingBlock(Num);
 138     }
 139     // Don't worry about dead users.
 140     if (!DT.isReachableFromEntry(UseBlock))
 141       continue;
 142
 143     if (SuccToSinkTo)
 144       SuccToSinkTo = DT.findNearestCommonDominator(SuccToSinkTo, UseBlock);
 145     else
 146       SuccToSinkTo = UseBlock;
 147     // The current basic block needs to dominate the candidate.
 148     if (!DT.dominates(BB, SuccToSinkTo))
 149       return false;
 150   }
 151
 152   if (SuccToSinkTo) {
 153     // The nearest common dominator may be in a parent loop of BB, which may not
 154     // be beneficial. Find an ancestor.
 155     while (SuccToSinkTo != BB &&
 156            !IsAcceptableTarget(Inst, SuccToSinkTo, DT, LI))
 157       SuccToSinkTo = DT.getNode(SuccToSinkTo)->getIDom()->getBlock();
 158     if (SuccToSinkTo == BB)
 159       SuccToSinkTo = nullptr;
 160   }
 161
 162   // If we couldn't find a block to sink to, ignore this instruction.
 163   if (!SuccToSinkTo)
 164     return false;
 165
 166   LLVM_DEBUG(dbgs() << "Sink" << *Inst << " (";
 167              Inst->getParent()->printAsOperand(dbgs(), false); dbgs() << " -> ";
 168              SuccToSinkTo->printAsOperand(dbgs(), false); dbgs() << ")\n");
 169
 170   // Move the instruction.
 171   Inst->moveBefore(&*SuccToSinkTo->getFirstInsertionPt());
 172   return true;
 173 }
 174
 175 static bool ProcessBlock(BasicBlock &BB, DominatorTree &DT, LoopInfo &LI,
 176                          AAResults &AA) {
 177   // Don't bother sinking code out of unreachable blocks. In addition to being
 178   // unprofitable, it can also lead to infinite looping, because in an
 179   // unreachable loop there may be nowhere to stop.
 180   if (!DT.isReachableFromEntry(&BB)) return false;
 181
 182   bool MadeChange = false;
 183
 184   // Walk the basic block bottom-up.  Remember if we saw a store.
 185   BasicBlock::iterator I = BB.end();
 186   --I;
 187   bool ProcessedBegin = false;
 188   SmallPtrSet<Instruction *, 8> Stores;
 189   do {
 190     Instruction *Inst = &*I; // The instruction to sink.
 191
 192     // Predecrement I (if it's not begin) so that it isn't invalidated by
 193     // sinking.
 194     ProcessedBegin = I == BB.begin();
 195     if (!ProcessedBegin)
 196       --I;
 197
 198     if (Inst->isDebugOrPseudoInst())
 199       continue;
 200
 201     if (SinkInstruction(Inst, Stores, DT, LI, AA)) {
 202       ++NumSunk;
 203       MadeChange = true;
 204     }
 205
 206     // If we just processed the first instruction in the block, we're done.
 207   } while (!ProcessedBegin);
 208
 209   return MadeChange;
 210 }
 211
 212 static bool iterativelySinkInstructions(Function &F, DominatorTree &DT,
 213                                         LoopInfo &LI, AAResults &AA) {
 214   bool MadeChange, EverMadeChange = false;
 215
 216   do {
 217     MadeChange = false;
 218     LLVM_DEBUG(dbgs() << "Sinking iteration " << NumSinkIter << "\n");
 219     // Process all basic blocks.
 220     for (BasicBlock &I : F)
 221       MadeChange |= ProcessBlock(I, DT, LI, AA);
 222     EverMadeChange |= MadeChange;
 223     NumSinkIter++;
 224   } while (MadeChange);
 225
 226   return EverMadeChange;
 227 }
 228
 229 PreservedAnalyses SinkingPass::run(Function &F, FunctionAnalysisManager &AM) {
 230   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 231   auto &LI = AM.getResult<LoopAnalysis>(F);
 232   auto &AA = AM.getResult<AAManager>(F);
 233
 234   if (!iterativelySinkInstructions(F, DT, LI, AA))
 235     return PreservedAnalyses::all();
 236
 237   PreservedAnalyses PA;
 238   PA.preserveSet<CFGAnalyses>();
 239   return PA;
 240 }
 241
 242 namespace {
 243   class SinkingLegacyPass : public FunctionPass {
 244   public:
 245     static char ID; // Pass identification
 246     SinkingLegacyPass() : FunctionPass(ID) {
 247       initializeSinkingLegacyPassPass(*PassRegistry::getPassRegistry());
 248     }
 249
 250     bool runOnFunction(Function &F) override {
 251       auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 252       auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 253       auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
 254
 255       return iterativelySinkInstructions(F, DT, LI, AA);
 256     }
 257
 258     void getAnalysisUsage(AnalysisUsage &AU) const override {
 259       AU.setPreservesCFG();
 260       FunctionPass::getAnalysisUsage(AU);
 261       AU.addRequired<AAResultsWrapperPass>();
 262       AU.addRequired<DominatorTreeWrapperPass>();
 263       AU.addRequired<LoopInfoWrapperPass>();
 264       AU.addPreserved<DominatorTreeWrapperPass>();
 265       AU.addPreserved<LoopInfoWrapperPass>();
 266     }
 267   };
 268 } // end anonymous namespace
 269
 270 char SinkingLegacyPass::ID = 0;
 271 INITIALIZE_PASS_BEGIN(SinkingLegacyPass, "sink", "Code sinking", false, false)
 272 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 273 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 274 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 275 INITIALIZE_PASS_END(SinkingLegacyPass, "sink", "Code sinking", false, false)
 276
 277 FunctionPass *llvm::createSinkingPass() { return new SinkingLegacyPass(); }