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