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