lib/Transforms/Scalar/Sink.cpp

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