1208599Srdivacky//===-- Sink.cpp - Code Sinking -------------------------------------------===// 2208599Srdivacky// 3208599Srdivacky// The LLVM Compiler Infrastructure 4208599Srdivacky// 5208599Srdivacky// This file is distributed under the University of Illinois Open Source 6208599Srdivacky// License. See LICENSE.TXT for details. 7208599Srdivacky// 8208599Srdivacky//===----------------------------------------------------------------------===// 9208599Srdivacky// 10208599Srdivacky// This pass moves instructions into successor blocks, when possible, so that 11208599Srdivacky// they aren't executed on paths where their results aren't needed. 12208599Srdivacky// 13208599Srdivacky//===----------------------------------------------------------------------===// 14208599Srdivacky 15208599Srdivacky#define DEBUG_TYPE "sink" 16208599Srdivacky#include "llvm/Transforms/Scalar.h" 17249423Sdim#include "llvm/ADT/Statistic.h" 18249423Sdim#include "llvm/Analysis/AliasAnalysis.h" 19208599Srdivacky#include "llvm/Analysis/Dominators.h" 20208599Srdivacky#include "llvm/Analysis/LoopInfo.h" 21234353Sdim#include "llvm/Analysis/ValueTracking.h" 22208599Srdivacky#include "llvm/Assembly/Writer.h" 23249423Sdim#include "llvm/IR/IntrinsicInst.h" 24208599Srdivacky#include "llvm/Support/CFG.h" 25208599Srdivacky#include "llvm/Support/Debug.h" 26208599Srdivacky#include "llvm/Support/raw_ostream.h" 27208599Srdivackyusing namespace llvm; 28208599Srdivacky 29208599SrdivackySTATISTIC(NumSunk, "Number of instructions sunk"); 30239462SdimSTATISTIC(NumSinkIter, "Number of sinking iterations"); 31208599Srdivacky 32208599Srdivackynamespace { 33208599Srdivacky class Sinking : public FunctionPass { 34208599Srdivacky DominatorTree *DT; 35208599Srdivacky LoopInfo *LI; 36208599Srdivacky AliasAnalysis *AA; 37208599Srdivacky 38208599Srdivacky public: 39208599Srdivacky static char ID; // Pass identification 40218893Sdim Sinking() : FunctionPass(ID) { 41218893Sdim initializeSinkingPass(*PassRegistry::getPassRegistry()); 42218893Sdim } 43239462Sdim 44208599Srdivacky virtual bool runOnFunction(Function &F); 45239462Sdim 46208599Srdivacky virtual void getAnalysisUsage(AnalysisUsage &AU) const { 47208599Srdivacky AU.setPreservesCFG(); 48208599Srdivacky FunctionPass::getAnalysisUsage(AU); 49208599Srdivacky AU.addRequired<AliasAnalysis>(); 50208599Srdivacky AU.addRequired<DominatorTree>(); 51208599Srdivacky AU.addRequired<LoopInfo>(); 52208599Srdivacky AU.addPreserved<DominatorTree>(); 53208599Srdivacky AU.addPreserved<LoopInfo>(); 54208599Srdivacky } 55208599Srdivacky private: 56208599Srdivacky bool ProcessBlock(BasicBlock &BB); 57208599Srdivacky bool SinkInstruction(Instruction *I, SmallPtrSet<Instruction *, 8> &Stores); 58208599Srdivacky bool AllUsesDominatedByBlock(Instruction *Inst, BasicBlock *BB) const; 59239462Sdim bool IsAcceptableTarget(Instruction *Inst, BasicBlock *SuccToSinkTo) const; 60208599Srdivacky }; 61208599Srdivacky} // end anonymous namespace 62239462Sdim 63208599Srdivackychar Sinking::ID = 0; 64218893SdimINITIALIZE_PASS_BEGIN(Sinking, "sink", "Code sinking", false, false) 65218893SdimINITIALIZE_PASS_DEPENDENCY(LoopInfo) 66218893SdimINITIALIZE_PASS_DEPENDENCY(DominatorTree) 67218893SdimINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 68218893SdimINITIALIZE_PASS_END(Sinking, "sink", "Code sinking", false, false) 69208599Srdivacky 70208599SrdivackyFunctionPass *llvm::createSinkingPass() { return new Sinking(); } 71208599Srdivacky 72208599Srdivacky/// AllUsesDominatedByBlock - Return true if all uses of the specified value 73208599Srdivacky/// occur in blocks dominated by the specified block. 74239462Sdimbool Sinking::AllUsesDominatedByBlock(Instruction *Inst, 75208599Srdivacky BasicBlock *BB) const { 76208599Srdivacky // Ignoring debug uses is necessary so debug info doesn't affect the code. 77208599Srdivacky // This may leave a referencing dbg_value in the original block, before 78208599Srdivacky // the definition of the vreg. Dwarf generator handles this although the 79208599Srdivacky // user might not get the right info at runtime. 80208599Srdivacky for (Value::use_iterator I = Inst->use_begin(), 81208599Srdivacky E = Inst->use_end(); I != E; ++I) { 82208599Srdivacky // Determine the block of the use. 83208599Srdivacky Instruction *UseInst = cast<Instruction>(*I); 84208599Srdivacky BasicBlock *UseBlock = UseInst->getParent(); 85208599Srdivacky if (PHINode *PN = dyn_cast<PHINode>(UseInst)) { 86208599Srdivacky // PHI nodes use the operand in the predecessor block, not the block with 87208599Srdivacky // the PHI. 88208599Srdivacky unsigned Num = PHINode::getIncomingValueNumForOperand(I.getOperandNo()); 89208599Srdivacky UseBlock = PN->getIncomingBlock(Num); 90208599Srdivacky } 91208599Srdivacky // Check that it dominates. 92208599Srdivacky if (!DT->dominates(BB, UseBlock)) 93208599Srdivacky return false; 94208599Srdivacky } 95208599Srdivacky return true; 96208599Srdivacky} 97208599Srdivacky 98208599Srdivackybool Sinking::runOnFunction(Function &F) { 99208599Srdivacky DT = &getAnalysis<DominatorTree>(); 100208599Srdivacky LI = &getAnalysis<LoopInfo>(); 101208599Srdivacky AA = &getAnalysis<AliasAnalysis>(); 102208599Srdivacky 103239462Sdim bool MadeChange, EverMadeChange = false; 104208599Srdivacky 105239462Sdim do { 106239462Sdim MadeChange = false; 107239462Sdim DEBUG(dbgs() << "Sinking iteration " << NumSinkIter << "\n"); 108208599Srdivacky // Process all basic blocks. 109239462Sdim for (Function::iterator I = F.begin(), E = F.end(); 110208599Srdivacky I != E; ++I) 111208599Srdivacky MadeChange |= ProcessBlock(*I); 112239462Sdim EverMadeChange |= MadeChange; 113239462Sdim NumSinkIter++; 114239462Sdim } while (MadeChange); 115239462Sdim 116208599Srdivacky return EverMadeChange; 117208599Srdivacky} 118208599Srdivacky 119208599Srdivackybool Sinking::ProcessBlock(BasicBlock &BB) { 120208599Srdivacky // Can't sink anything out of a block that has less than two successors. 121208599Srdivacky if (BB.getTerminator()->getNumSuccessors() <= 1 || BB.empty()) return false; 122208599Srdivacky 123208599Srdivacky // Don't bother sinking code out of unreachable blocks. In addition to being 124239462Sdim // unprofitable, it can also lead to infinite looping, because in an 125239462Sdim // unreachable loop there may be nowhere to stop. 126208599Srdivacky if (!DT->isReachableFromEntry(&BB)) return false; 127208599Srdivacky 128208599Srdivacky bool MadeChange = false; 129208599Srdivacky 130208599Srdivacky // Walk the basic block bottom-up. Remember if we saw a store. 131208599Srdivacky BasicBlock::iterator I = BB.end(); 132208599Srdivacky --I; 133208599Srdivacky bool ProcessedBegin = false; 134208599Srdivacky SmallPtrSet<Instruction *, 8> Stores; 135208599Srdivacky do { 136208599Srdivacky Instruction *Inst = I; // The instruction to sink. 137239462Sdim 138208599Srdivacky // Predecrement I (if it's not begin) so that it isn't invalidated by 139208599Srdivacky // sinking. 140208599Srdivacky ProcessedBegin = I == BB.begin(); 141208599Srdivacky if (!ProcessedBegin) 142208599Srdivacky --I; 143208599Srdivacky 144208599Srdivacky if (isa<DbgInfoIntrinsic>(Inst)) 145208599Srdivacky continue; 146208599Srdivacky 147208599Srdivacky if (SinkInstruction(Inst, Stores)) 148208599Srdivacky ++NumSunk, MadeChange = true; 149239462Sdim 150208599Srdivacky // If we just processed the first instruction in the block, we're done. 151208599Srdivacky } while (!ProcessedBegin); 152239462Sdim 153208599Srdivacky return MadeChange; 154208599Srdivacky} 155208599Srdivacky 156208599Srdivackystatic bool isSafeToMove(Instruction *Inst, AliasAnalysis *AA, 157208599Srdivacky SmallPtrSet<Instruction *, 8> &Stores) { 158226633Sdim 159226633Sdim if (Inst->mayWriteToMemory()) { 160226633Sdim Stores.insert(Inst); 161226633Sdim return false; 162226633Sdim } 163226633Sdim 164208599Srdivacky if (LoadInst *L = dyn_cast<LoadInst>(Inst)) { 165218893Sdim AliasAnalysis::Location Loc = AA->getLocation(L); 166208599Srdivacky for (SmallPtrSet<Instruction *, 8>::iterator I = Stores.begin(), 167208599Srdivacky E = Stores.end(); I != E; ++I) 168218893Sdim if (AA->getModRefInfo(*I, Loc) & AliasAnalysis::Mod) 169208599Srdivacky return false; 170208599Srdivacky } 171208599Srdivacky 172218893Sdim if (isa<TerminatorInst>(Inst) || isa<PHINode>(Inst)) 173218893Sdim return false; 174218893Sdim 175218893Sdim return true; 176208599Srdivacky} 177208599Srdivacky 178239462Sdim/// IsAcceptableTarget - Return true if it is possible to sink the instruction 179239462Sdim/// in the specified basic block. 180239462Sdimbool Sinking::IsAcceptableTarget(Instruction *Inst, 181239462Sdim BasicBlock *SuccToSinkTo) const { 182239462Sdim assert(Inst && "Instruction to be sunk is null"); 183239462Sdim assert(SuccToSinkTo && "Candidate sink target is null"); 184239462Sdim 185239462Sdim // It is not possible to sink an instruction into its own block. This can 186239462Sdim // happen with loops. 187239462Sdim if (Inst->getParent() == SuccToSinkTo) 188239462Sdim return false; 189239462Sdim 190239462Sdim // If the block has multiple predecessors, this would introduce computation 191239462Sdim // on different code paths. We could split the critical edge, but for now we 192239462Sdim // just punt. 193239462Sdim // FIXME: Split critical edges if not backedges. 194239462Sdim if (SuccToSinkTo->getUniquePredecessor() != Inst->getParent()) { 195239462Sdim // We cannot sink a load across a critical edge - there may be stores in 196239462Sdim // other code paths. 197239462Sdim if (!isSafeToSpeculativelyExecute(Inst)) 198239462Sdim return false; 199239462Sdim 200239462Sdim // We don't want to sink across a critical edge if we don't dominate the 201239462Sdim // successor. We could be introducing calculations to new code paths. 202239462Sdim if (!DT->dominates(Inst->getParent(), SuccToSinkTo)) 203239462Sdim return false; 204239462Sdim 205239462Sdim // Don't sink instructions into a loop. 206239462Sdim Loop *succ = LI->getLoopFor(SuccToSinkTo); 207239462Sdim Loop *cur = LI->getLoopFor(Inst->getParent()); 208239462Sdim if (succ != 0 && succ != cur) 209239462Sdim return false; 210239462Sdim } 211239462Sdim 212239462Sdim // Finally, check that all the uses of the instruction are actually 213239462Sdim // dominated by the candidate 214239462Sdim return AllUsesDominatedByBlock(Inst, SuccToSinkTo); 215239462Sdim} 216239462Sdim 217208599Srdivacky/// SinkInstruction - Determine whether it is safe to sink the specified machine 218208599Srdivacky/// instruction out of its current block into a successor. 219208599Srdivackybool Sinking::SinkInstruction(Instruction *Inst, 220208599Srdivacky SmallPtrSet<Instruction *, 8> &Stores) { 221208599Srdivacky // Check if it's safe to move the instruction. 222208599Srdivacky if (!isSafeToMove(Inst, AA, Stores)) 223208599Srdivacky return false; 224239462Sdim 225208599Srdivacky // FIXME: This should include support for sinking instructions within the 226208599Srdivacky // block they are currently in to shorten the live ranges. We often get 227208599Srdivacky // instructions sunk into the top of a large block, but it would be better to 228208599Srdivacky // also sink them down before their first use in the block. This xform has to 229208599Srdivacky // be careful not to *increase* register pressure though, e.g. sinking 230208599Srdivacky // "x = y + z" down if it kills y and z would increase the live ranges of y 231208599Srdivacky // and z and only shrink the live range of x. 232239462Sdim 233208599Srdivacky // SuccToSinkTo - This is the successor to sink this instruction to, once we 234208599Srdivacky // decide. 235208599Srdivacky BasicBlock *SuccToSinkTo = 0; 236239462Sdim 237208599Srdivacky // Instructions can only be sunk if all their uses are in blocks 238208599Srdivacky // dominated by one of the successors. 239239462Sdim // Look at all the postdominators and see if we can sink it in one. 240239462Sdim DomTreeNode *DTN = DT->getNode(Inst->getParent()); 241239462Sdim for (DomTreeNode::iterator I = DTN->begin(), E = DTN->end(); 242239462Sdim I != E && SuccToSinkTo == 0; ++I) { 243239462Sdim BasicBlock *Candidate = (*I)->getBlock(); 244239462Sdim if ((*I)->getIDom()->getBlock() == Inst->getParent() && 245239462Sdim IsAcceptableTarget(Inst, Candidate)) 246239462Sdim SuccToSinkTo = Candidate; 247208599Srdivacky } 248239462Sdim 249239462Sdim // If no suitable postdominator was found, look at all the successors and 250239462Sdim // decide which one we should sink to, if any. 251239462Sdim for (succ_iterator I = succ_begin(Inst->getParent()), 252239462Sdim E = succ_end(Inst->getParent()); I != E && SuccToSinkTo == 0; ++I) { 253239462Sdim if (IsAcceptableTarget(Inst, *I)) 254239462Sdim SuccToSinkTo = *I; 255239462Sdim } 256239462Sdim 257208599Srdivacky // If we couldn't find a block to sink to, ignore this instruction. 258208599Srdivacky if (SuccToSinkTo == 0) 259208599Srdivacky return false; 260208599Srdivacky 261239462Sdim DEBUG(dbgs() << "Sink" << *Inst << " ("; 262239462Sdim WriteAsOperand(dbgs(), Inst->getParent(), false); 263239462Sdim dbgs() << " -> "; 264239462Sdim WriteAsOperand(dbgs(), SuccToSinkTo, false); 265239462Sdim dbgs() << ")\n"); 266208599Srdivacky 267208599Srdivacky // Move the instruction. 268239462Sdim Inst->moveBefore(SuccToSinkTo->getFirstInsertionPt()); 269208599Srdivacky return true; 270208599Srdivacky} 271