128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman//===-- Sink.cpp - Code Sinking -------------------------------------------===// 228a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman// 328a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman// The LLVM Compiler Infrastructure 428a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman// 528a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman// This file is distributed under the University of Illinois Open Source 628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman// License. See LICENSE.TXT for details. 728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman// 828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman//===----------------------------------------------------------------------===// 928a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman// 1028a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman// This pass moves instructions into successor blocks, when possible, so that 1128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman// they aren't executed on paths where their results aren't needed. 1228a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman// 1328a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman//===----------------------------------------------------------------------===// 1428a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 1528a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman#define DEBUG_TYPE "sink" 1628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman#include "llvm/Transforms/Scalar.h" 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/AliasAnalysis.h" 1928a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman#include "llvm/Analysis/Dominators.h" 2028a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman#include "llvm/Analysis/LoopInfo.h" 21f0426601977c3e386d2d26c72a2cca691dc42072Dan Gohman#include "llvm/Analysis/ValueTracking.h" 2228a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman#include "llvm/Assembly/Writer.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 2428a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman#include "llvm/Support/CFG.h" 2528a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman#include "llvm/Support/Debug.h" 2628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman#include "llvm/Support/raw_ostream.h" 2728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohmanusing namespace llvm; 2828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 2928a193ed8b4b37593afb76f9130eacf393ea9383Dan GohmanSTATISTIC(NumSunk, "Number of instructions sunk"); 3053b4177df78401da23468f49ad0bc056e9acb627Duncan SandsSTATISTIC(NumSinkIter, "Number of sinking iterations"); 3128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 3228a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohmannamespace { 3328a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman class Sinking : public FunctionPass { 3428a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman DominatorTree *DT; 3528a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman LoopInfo *LI; 3628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman AliasAnalysis *AA; 3728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 3828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman public: 3928a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman static char ID; // Pass identification 40081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson Sinking() : FunctionPass(ID) { 41081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeSinkingPass(*PassRegistry::getPassRegistry()); 42081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 43a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 4428a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman virtual bool runOnFunction(Function &F); 45a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 4628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman virtual void getAnalysisUsage(AnalysisUsage &AU) const { 4728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman AU.setPreservesCFG(); 4828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman FunctionPass::getAnalysisUsage(AU); 4928a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman AU.addRequired<AliasAnalysis>(); 5028a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman AU.addRequired<DominatorTree>(); 5128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman AU.addRequired<LoopInfo>(); 5228a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman AU.addPreserved<DominatorTree>(); 5328a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman AU.addPreserved<LoopInfo>(); 5428a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman } 5528a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman private: 5628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman bool ProcessBlock(BasicBlock &BB); 5728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman bool SinkInstruction(Instruction *I, SmallPtrSet<Instruction *, 8> &Stores); 5828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman bool AllUsesDominatedByBlock(Instruction *Inst, BasicBlock *BB) const; 5953b4177df78401da23468f49ad0bc056e9acb627Duncan Sands bool IsAcceptableTarget(Instruction *Inst, BasicBlock *SuccToSinkTo) const; 6028a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman }; 6128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman} // end anonymous namespace 62a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 6328a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohmanchar Sinking::ID = 0; 642ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(Sinking, "sink", "Code sinking", false, false) 652ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LoopInfo) 662ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 672ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 682ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(Sinking, "sink", "Code sinking", false, false) 6928a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 7028a193ed8b4b37593afb76f9130eacf393ea9383Dan GohmanFunctionPass *llvm::createSinkingPass() { return new Sinking(); } 7128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 7228a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman/// AllUsesDominatedByBlock - Return true if all uses of the specified value 7328a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman/// occur in blocks dominated by the specified block. 74a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotembool Sinking::AllUsesDominatedByBlock(Instruction *Inst, 7528a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman BasicBlock *BB) const { 7628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // Ignoring debug uses is necessary so debug info doesn't affect the code. 7728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // This may leave a referencing dbg_value in the original block, before 7828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // the definition of the vreg. Dwarf generator handles this although the 7928a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // user might not get the right info at runtime. 8028a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman for (Value::use_iterator I = Inst->use_begin(), 8128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman E = Inst->use_end(); I != E; ++I) { 8228a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // Determine the block of the use. 8328a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman Instruction *UseInst = cast<Instruction>(*I); 8428a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman BasicBlock *UseBlock = UseInst->getParent(); 8528a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman if (PHINode *PN = dyn_cast<PHINode>(UseInst)) { 8628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // PHI nodes use the operand in the predecessor block, not the block with 8728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // the PHI. 8828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman unsigned Num = PHINode::getIncomingValueNumForOperand(I.getOperandNo()); 8928a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman UseBlock = PN->getIncomingBlock(Num); 9028a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman } 9128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // Check that it dominates. 9228a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman if (!DT->dominates(BB, UseBlock)) 9328a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman return false; 9428a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman } 9528a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman return true; 9628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman} 9728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 9828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohmanbool Sinking::runOnFunction(Function &F) { 9928a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman DT = &getAnalysis<DominatorTree>(); 10028a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman LI = &getAnalysis<LoopInfo>(); 10128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman AA = &getAnalysis<AliasAnalysis>(); 10228a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 10353b4177df78401da23468f49ad0bc056e9acb627Duncan Sands bool MadeChange, EverMadeChange = false; 104a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 10553b4177df78401da23468f49ad0bc056e9acb627Duncan Sands do { 10653b4177df78401da23468f49ad0bc056e9acb627Duncan Sands MadeChange = false; 10753b4177df78401da23468f49ad0bc056e9acb627Duncan Sands DEBUG(dbgs() << "Sinking iteration " << NumSinkIter << "\n"); 10828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // Process all basic blocks. 109a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem for (Function::iterator I = F.begin(), E = F.end(); 11028a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman I != E; ++I) 11128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman MadeChange |= ProcessBlock(*I); 11253b4177df78401da23468f49ad0bc056e9acb627Duncan Sands EverMadeChange |= MadeChange; 11353b4177df78401da23468f49ad0bc056e9acb627Duncan Sands NumSinkIter++; 11453b4177df78401da23468f49ad0bc056e9acb627Duncan Sands } while (MadeChange); 115a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 11628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman return EverMadeChange; 11728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman} 11828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 11928a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohmanbool Sinking::ProcessBlock(BasicBlock &BB) { 12028a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // Can't sink anything out of a block that has less than two successors. 12128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman if (BB.getTerminator()->getNumSuccessors() <= 1 || BB.empty()) return false; 12228a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 12328a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // Don't bother sinking code out of unreachable blocks. In addition to being 124a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem // unprofitable, it can also lead to infinite looping, because in an 125a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem // unreachable loop there may be nowhere to stop. 12628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman if (!DT->isReachableFromEntry(&BB)) return false; 12728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 12828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman bool MadeChange = false; 12928a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 13028a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // Walk the basic block bottom-up. Remember if we saw a store. 13128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman BasicBlock::iterator I = BB.end(); 13228a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman --I; 13328a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman bool ProcessedBegin = false; 13428a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman SmallPtrSet<Instruction *, 8> Stores; 13528a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman do { 13628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman Instruction *Inst = I; // The instruction to sink. 137a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 13828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // Predecrement I (if it's not begin) so that it isn't invalidated by 13928a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // sinking. 14028a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman ProcessedBegin = I == BB.begin(); 14128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman if (!ProcessedBegin) 14228a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman --I; 14328a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 14428a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman if (isa<DbgInfoIntrinsic>(Inst)) 14528a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman continue; 14628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 14728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman if (SinkInstruction(Inst, Stores)) 14828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman ++NumSunk, MadeChange = true; 149a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 15028a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // If we just processed the first instruction in the block, we're done. 15128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman } while (!ProcessedBegin); 152a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 15328a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman return MadeChange; 15428a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman} 15528a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 15628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohmanstatic bool isSafeToMove(Instruction *Inst, AliasAnalysis *AA, 15728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman SmallPtrSet<Instruction *, 8> &Stores) { 15828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 15986b5db8c011d96e7b7af0299cc99c942b790499eEli Friedman if (Inst->mayWriteToMemory()) { 16086b5db8c011d96e7b7af0299cc99c942b790499eEli Friedman Stores.insert(Inst); 16186b5db8c011d96e7b7af0299cc99c942b790499eEli Friedman return false; 16286b5db8c011d96e7b7af0299cc99c942b790499eEli Friedman } 16386b5db8c011d96e7b7af0299cc99c942b790499eEli Friedman 16486b5db8c011d96e7b7af0299cc99c942b790499eEli Friedman if (LoadInst *L = dyn_cast<LoadInst>(Inst)) { 1656d8eb156e6be727570b300bac7712f745a318c7dDan Gohman AliasAnalysis::Location Loc = AA->getLocation(L); 16628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman for (SmallPtrSet<Instruction *, 8>::iterator I = Stores.begin(), 16728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman E = Stores.end(); I != E; ++I) 1685aae3dcb53b89344d598eee7e1021dce7ec6345cDan Gohman if (AA->getModRefInfo(*I, Loc) & AliasAnalysis::Mod) 16928a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman return false; 17028a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman } 17128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 1722c71f18ff7f5e1504ffeff85f643314e84e6e5d9Dan Gohman if (isa<TerminatorInst>(Inst) || isa<PHINode>(Inst)) 1732c71f18ff7f5e1504ffeff85f643314e84e6e5d9Dan Gohman return false; 1742c71f18ff7f5e1504ffeff85f643314e84e6e5d9Dan Gohman 1752c71f18ff7f5e1504ffeff85f643314e84e6e5d9Dan Gohman return true; 17628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman} 17728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman 17853b4177df78401da23468f49ad0bc056e9acb627Duncan Sands/// IsAcceptableTarget - Return true if it is possible to sink the instruction 17953b4177df78401da23468f49ad0bc056e9acb627Duncan Sands/// in the specified basic block. 180a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotembool Sinking::IsAcceptableTarget(Instruction *Inst, 181a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem BasicBlock *SuccToSinkTo) const { 18253b4177df78401da23468f49ad0bc056e9acb627Duncan Sands assert(Inst && "Instruction to be sunk is null"); 18353b4177df78401da23468f49ad0bc056e9acb627Duncan Sands assert(SuccToSinkTo && "Candidate sink target is null"); 184a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 18553b4177df78401da23468f49ad0bc056e9acb627Duncan Sands // It is not possible to sink an instruction into its own block. This can 18653b4177df78401da23468f49ad0bc056e9acb627Duncan Sands // happen with loops. 18753b4177df78401da23468f49ad0bc056e9acb627Duncan Sands if (Inst->getParent() == SuccToSinkTo) 18853b4177df78401da23468f49ad0bc056e9acb627Duncan Sands return false; 189a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 190a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem // If the block has multiple predecessors, this would introduce computation 19153b4177df78401da23468f49ad0bc056e9acb627Duncan Sands // on different code paths. We could split the critical edge, but for now we 19253b4177df78401da23468f49ad0bc056e9acb627Duncan Sands // just punt. 19353b4177df78401da23468f49ad0bc056e9acb627Duncan Sands // FIXME: Split critical edges if not backedges. 19453b4177df78401da23468f49ad0bc056e9acb627Duncan Sands if (SuccToSinkTo->getUniquePredecessor() != Inst->getParent()) { 19553b4177df78401da23468f49ad0bc056e9acb627Duncan Sands // We cannot sink a load across a critical edge - there may be stores in 19653b4177df78401da23468f49ad0bc056e9acb627Duncan Sands // other code paths. 19753b4177df78401da23468f49ad0bc056e9acb627Duncan Sands if (!isSafeToSpeculativelyExecute(Inst)) 19853b4177df78401da23468f49ad0bc056e9acb627Duncan Sands return false; 199a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 20053b4177df78401da23468f49ad0bc056e9acb627Duncan Sands // We don't want to sink across a critical edge if we don't dominate the 20153b4177df78401da23468f49ad0bc056e9acb627Duncan Sands // successor. We could be introducing calculations to new code paths. 20253b4177df78401da23468f49ad0bc056e9acb627Duncan Sands if (!DT->dominates(Inst->getParent(), SuccToSinkTo)) 20353b4177df78401da23468f49ad0bc056e9acb627Duncan Sands return false; 204a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 20553b4177df78401da23468f49ad0bc056e9acb627Duncan Sands // Don't sink instructions into a loop. 206a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem Loop *succ = LI->getLoopFor(SuccToSinkTo); 207a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem Loop *cur = LI->getLoopFor(Inst->getParent()); 20853b4177df78401da23468f49ad0bc056e9acb627Duncan Sands if (succ != 0 && succ != cur) 20953b4177df78401da23468f49ad0bc056e9acb627Duncan Sands return false; 21053b4177df78401da23468f49ad0bc056e9acb627Duncan Sands } 211a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 21253b4177df78401da23468f49ad0bc056e9acb627Duncan Sands // Finally, check that all the uses of the instruction are actually 21353b4177df78401da23468f49ad0bc056e9acb627Duncan Sands // dominated by the candidate 21453b4177df78401da23468f49ad0bc056e9acb627Duncan Sands return AllUsesDominatedByBlock(Inst, SuccToSinkTo); 21553b4177df78401da23468f49ad0bc056e9acb627Duncan Sands} 21653b4177df78401da23468f49ad0bc056e9acb627Duncan Sands 21728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman/// SinkInstruction - Determine whether it is safe to sink the specified machine 21828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman/// instruction out of its current block into a successor. 21928a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohmanbool Sinking::SinkInstruction(Instruction *Inst, 22028a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman SmallPtrSet<Instruction *, 8> &Stores) { 22128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // Check if it's safe to move the instruction. 22228a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman if (!isSafeToMove(Inst, AA, Stores)) 22328a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman return false; 224a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 22528a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // FIXME: This should include support for sinking instructions within the 22628a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // block they are currently in to shorten the live ranges. We often get 22728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // instructions sunk into the top of a large block, but it would be better to 22828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // also sink them down before their first use in the block. This xform has to 22928a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // be careful not to *increase* register pressure though, e.g. sinking 23028a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // "x = y + z" down if it kills y and z would increase the live ranges of y 23128a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // and z and only shrink the live range of x. 232a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 23328a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // SuccToSinkTo - This is the successor to sink this instruction to, once we 23428a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // decide. 23528a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman BasicBlock *SuccToSinkTo = 0; 236a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 23728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // Instructions can only be sunk if all their uses are in blocks 23828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // dominated by one of the successors. 23953b4177df78401da23468f49ad0bc056e9acb627Duncan Sands // Look at all the postdominators and see if we can sink it in one. 24053b4177df78401da23468f49ad0bc056e9acb627Duncan Sands DomTreeNode *DTN = DT->getNode(Inst->getParent()); 241a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem for (DomTreeNode::iterator I = DTN->begin(), E = DTN->end(); 24253b4177df78401da23468f49ad0bc056e9acb627Duncan Sands I != E && SuccToSinkTo == 0; ++I) { 24353b4177df78401da23468f49ad0bc056e9acb627Duncan Sands BasicBlock *Candidate = (*I)->getBlock(); 244a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem if ((*I)->getIDom()->getBlock() == Inst->getParent() && 24553b4177df78401da23468f49ad0bc056e9acb627Duncan Sands IsAcceptableTarget(Inst, Candidate)) 24653b4177df78401da23468f49ad0bc056e9acb627Duncan Sands SuccToSinkTo = Candidate; 24753b4177df78401da23468f49ad0bc056e9acb627Duncan Sands } 24853b4177df78401da23468f49ad0bc056e9acb627Duncan Sands 249a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem // If no suitable postdominator was found, look at all the successors and 25053b4177df78401da23468f49ad0bc056e9acb627Duncan Sands // decide which one we should sink to, if any. 251a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem for (succ_iterator I = succ_begin(Inst->getParent()), 25253b4177df78401da23468f49ad0bc056e9acb627Duncan Sands E = succ_end(Inst->getParent()); I != E && SuccToSinkTo == 0; ++I) { 25353b4177df78401da23468f49ad0bc056e9acb627Duncan Sands if (IsAcceptableTarget(Inst, *I)) 25453b4177df78401da23468f49ad0bc056e9acb627Duncan Sands SuccToSinkTo = *I; 25528a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman } 256a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 25728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // If we couldn't find a block to sink to, ignore this instruction. 25828a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman if (SuccToSinkTo == 0) 25928a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman return false; 260a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 26153b4177df78401da23468f49ad0bc056e9acb627Duncan Sands DEBUG(dbgs() << "Sink" << *Inst << " ("; 262a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem WriteAsOperand(dbgs(), Inst->getParent(), false); 26353b4177df78401da23468f49ad0bc056e9acb627Duncan Sands dbgs() << " -> "; 264a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem WriteAsOperand(dbgs(), SuccToSinkTo, false); 26553b4177df78401da23468f49ad0bc056e9acb627Duncan Sands dbgs() << ")\n"); 266a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 26728a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman // Move the instruction. 26853b4177df78401da23468f49ad0bc056e9acb627Duncan Sands Inst->moveBefore(SuccToSinkTo->getFirstInsertionPt()); 26928a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman return true; 27028a193ed8b4b37593afb76f9130eacf393ea9383Dan Gohman} 271