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