DeadStoreElimination.cpp revision 83d675940309b2df3ab16efd50f7e90ce4ead8e7
1666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson//===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===// 2b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson// 3b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson// The LLVM Compiler Infrastructure 4b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson// 8b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson//===----------------------------------------------------------------------===// 9b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson// 10b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson// This file implements a trivial dead store elimination that only considers 11b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson// basic-block local redundant stores. 12b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson// 13b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson// FIXME: This should eventually be extended to be a post-dominator tree 14b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson// traversal. Doing so would be pretty trivial. 15b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson// 16b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson//===----------------------------------------------------------------------===// 17b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 18f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Anderson#define DEBUG_TYPE "dse" 19b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Transforms/Scalar.h" 2043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson#include "llvm/Constants.h" 21b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Function.h" 22b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Instructions.h" 23a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson#include "llvm/IntrinsicInst.h" 24b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Pass.h" 25b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/ADT/SmallPtrSet.h" 26b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/ADT/Statistic.h" 27a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson#include "llvm/Analysis/AliasAnalysis.h" 288aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson#include "llvm/Analysis/Dominators.h" 29f006b183e2d2bebcf6968d1dd7350397c95b0325Victor Hernandez#include "llvm/Analysis/MemoryBuiltins.h" 30b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Analysis/MemoryDependenceAnalysis.h" 31a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson#include "llvm/Target/TargetData.h" 32b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Transforms/Utils/Local.h" 33b77c457cc87aeeb166995aed793a516e9e431703Owen Andersonusing namespace llvm; 34b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 35b77c457cc87aeeb166995aed793a516e9e431703Owen AndersonSTATISTIC(NumFastStores, "Number of stores deleted"); 36b77c457cc87aeeb166995aed793a516e9e431703Owen AndersonSTATISTIC(NumFastOther , "Number of other instrs removed"); 37b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 38b77c457cc87aeeb166995aed793a516e9e431703Owen Andersonnamespace { 393e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct DSE : public FunctionPass { 40e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AliasAnalysis *AA; 41e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MemoryDependenceAnalysis *MD; 42e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 43b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson static char ID; // Pass identification, replacement for typeid 44e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner DSE() : FunctionPass(ID), AA(0), MD(0) { 45081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeDSEPass(*PassRegistry::getPassRegistry()); 46081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 47b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 48b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson virtual bool runOnFunction(Function &F) { 49e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AA = &getAnalysis<AliasAnalysis>(); 50e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MD = &getAnalysis<MemoryDependenceAnalysis>(); 5198df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner DominatorTree &DT = getAnalysis<DominatorTree>(); 5298df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner 53e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner bool Changed = false; 54b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 5598df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner // Only check non-dead blocks. Dead blocks may have strange pointer 5698df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner // cycles that will confuse alias analysis. 5798df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner if (DT.isReachableFromEntry(I)) 5898df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner Changed |= runOnBasicBlock(*I); 59e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 60e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AA = 0; MD = 0; 61b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return Changed; 62b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 6339f372e23e49cecb8db2eb7120eb331173e50c74Chris Lattner 64b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool runOnBasicBlock(BasicBlock &BB); 651ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner bool HandleFree(CallInst *F); 66925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner bool handleEndBlock(BasicBlock &BB); 673da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohman bool RemoveUndeadPointers(Value *Ptr, uint64_t killPointerSize, 68cccbe7e4156884c6483b548997eea02bcf8b748eNick Lewycky BasicBlock::iterator &BBI, 69cccbe7e4156884c6483b548997eea02bcf8b748eNick Lewycky SmallPtrSet<Value*, 64> &deadPointers); 70925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner void DeleteDeadInstruction(Instruction *I, 71925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner SmallPtrSet<Value*, 64> *deadPointers = 0); 72925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 73b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 74b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // getAnalysisUsage - We require post dominance frontiers (aka Control 75b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Dependence Graph) 76b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const { 77b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.setPreservesCFG(); 788aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson AU.addRequired<DominatorTree>(); 79a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addRequired<AliasAnalysis>(); 80b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addRequired<MemoryDependenceAnalysis>(); 81e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AU.addPreserved<AliasAnalysis>(); 828aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson AU.addPreserved<DominatorTree>(); 83b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addPreserved<MemoryDependenceAnalysis>(); 84b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 85b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson }; 86b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 87b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 88844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar DSE::ID = 0; 892ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false) 902ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 912ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) 922ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 932ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(DSE, "dse", "Dead Store Elimination", false, false) 94844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 95f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen AndersonFunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } 96b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 9772987a274223e64482d8697b948e1c13a448198dChris Lattner/// hasMemoryWrite - Does this instruction write some memory? This only returns 9872987a274223e64482d8697b948e1c13a448198dChris Lattner/// true for things that we can analyze with other helpers below. 9972987a274223e64482d8697b948e1c13a448198dChris Lattnerstatic bool hasMemoryWrite(Instruction *I) { 10058571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (isa<StoreInst>(I)) 10158571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky return true; 10258571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 10358571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky switch (II->getIntrinsicID()) { 10465a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner default: 10565a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner return false; 10665a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::memset: 10765a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::memmove: 10865a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::memcpy: 10965a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::init_trampoline: 11065a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::lifetime_end: 11165a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner return true; 11258571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky } 11358571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky } 11458571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky return false; 11558571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky} 11658571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky 117cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner/// getLocForWrite - Return a Location stored to by the specified instruction. 118cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattnerstatic AliasAnalysis::Location 119cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris LattnergetLocForWrite(Instruction *Inst, AliasAnalysis &AA) { 120cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) 121cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AA.getLocation(SI); 122cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 123cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Inst)) { 124cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // memcpy/memmove/memset. 125cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner AliasAnalysis::Location Loc = AA.getLocationForDest(MI); 126cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we don't have target data around, an unknown size in Location means 127cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // that we should use the size of the pointee type. This isn't valid for 128cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // memset/memcpy, which writes more than an i8. 129cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (Loc.Size == AliasAnalysis::UnknownSize && AA.getTargetData() == 0) 130cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AliasAnalysis::Location(); 131cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return Loc; 132cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 133cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 134cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst); 135cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (II == 0) return AliasAnalysis::Location(); 136cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 137cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner switch (II->getIntrinsicID()) { 138cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner default: return AliasAnalysis::Location(); // Unhandled intrinsic. 139cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner case Intrinsic::init_trampoline: 140cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we don't have target data around, an unknown size in Location means 141cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // that we should use the size of the pointee type. This isn't valid for 142cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // init.trampoline, which writes more than an i8. 143cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (AA.getTargetData() == 0) return AliasAnalysis::Location(); 144cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 145cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // FIXME: We don't know the size of the trampoline, so we can't really 146cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // handle it here. 147cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AliasAnalysis::Location(II->getArgOperand(0)); 148cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner case Intrinsic::lifetime_end: { 149cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); 150cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AliasAnalysis::Location(II->getArgOperand(1), Len); 151cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 152cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 153cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner} 154cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 155bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattner/// isRemovable - If the value of this instruction and the memory it writes to 156bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattner/// is unused, may we delete this instruction? 157bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattnerstatic bool isRemovable(Instruction *I) { 15855ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner // Don't remove volatile stores. 15958571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (StoreInst *SI = dyn_cast<StoreInst>(I)) 16058571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky return !SI->isVolatile(); 16155ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner 16255ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner IntrinsicInst *II = cast<IntrinsicInst>(I); 16355ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner switch (II->getIntrinsicID()) { 16455ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner default: assert(0 && "doesn't pass 'hasMemoryWrite' predicate"); 16555ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner case Intrinsic::lifetime_end: 16655ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner // Never remove dead lifetime_end's, e.g. because it is followed by a 16755ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner // free. 16855ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner return false; 16955ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner case Intrinsic::init_trampoline: 17055ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner // Always safe to remove init_trampoline. 17155ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner return true; 17255ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner 17355ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner case Intrinsic::memset: 17455ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner case Intrinsic::memmove: 17555ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner case Intrinsic::memcpy: 17655ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner // Don't remove volatile memory intrinsics. 17755ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner return !cast<MemIntrinsic>(II)->isVolatile(); 17855ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner } 17958571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky} 18058571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky 1811ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner/// getPointerOperand - Return the pointer that is being written to. 18258571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewyckystatic Value *getPointerOperand(Instruction *I) { 18372987a274223e64482d8697b948e1c13a448198dChris Lattner assert(hasMemoryWrite(I)); 18458571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (StoreInst *SI = dyn_cast<StoreInst>(I)) 18558571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky return SI->getPointerOperand(); 18658571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) 1873ccbb22eaf3f0deebc15ff7be992f090a6f0ba0bGabor Greif return MI->getArgOperand(0); 1883ccbb22eaf3f0deebc15ff7be992f090a6f0ba0bGabor Greif 1893ccbb22eaf3f0deebc15ff7be992f090a6f0ba0bGabor Greif IntrinsicInst *II = cast<IntrinsicInst>(I); 1903ccbb22eaf3f0deebc15ff7be992f090a6f0ba0bGabor Greif switch (II->getIntrinsicID()) { 19165a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner default: assert(false && "Unexpected intrinsic!"); 19265a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::init_trampoline: 1933ccbb22eaf3f0deebc15ff7be992f090a6f0ba0bGabor Greif return II->getArgOperand(0); 194551754c4958086cc6910da7c950f2875e212f5cfEric Christopher case Intrinsic::lifetime_end: 1953ccbb22eaf3f0deebc15ff7be992f090a6f0ba0bGabor Greif return II->getArgOperand(1); 196710c37c494229334f59b9be328366807db2a7d01Duncan Sands } 19758571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky} 19858571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky 199e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattnerstatic uint64_t getPointerSize(Value *V, AliasAnalysis &AA) { 200e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner const TargetData *TD = AA.getTargetData(); 201e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (TD == 0) 202e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner return AliasAnalysis::UnknownSize; 203e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 204e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (AllocaInst *A = dyn_cast<AllocaInst>(V)) { 205e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner // Get size information for the alloca 206e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(A->getArraySize())) 207e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner return C->getZExtValue() * TD->getTypeAllocSize(A->getAllocatedType()); 208e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner return AliasAnalysis::UnknownSize; 209e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner } 210e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 211e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner assert(isa<Argument>(V) && "Expected AllocaInst or Argument!"); 212e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner const PointerType *PT = cast<PointerType>(V->getType()); 213e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner return TD->getTypeAllocSize(PT->getElementType()); 214e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner} 215e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 216e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 217cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner/// isCompleteOverwrite - Return true if a store to the 'Later' location 218cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner/// completely overwrites a store to the 'Earlier' location. 219cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattnerstatic bool isCompleteOverwrite(const AliasAnalysis::Location &Later, 220cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner const AliasAnalysis::Location &Earlier, 22198016511932510bd5ec5dad1319922d9daf18991Chris Lattner AliasAnalysis &AA) { 222cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner const Value *P1 = Later.Ptr->stripPointerCasts(); 223cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner const Value *P2 = Earlier.Ptr->stripPointerCasts(); 224cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 225cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Make sure that the start pointers are the same. 226cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (P1 != P2) 227cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return false; 22858571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky 22998016511932510bd5ec5dad1319922d9daf18991Chris Lattner // If we don't know the sizes of either access, then we can't do a comparison. 23098016511932510bd5ec5dad1319922d9daf18991Chris Lattner if (Later.Size == AliasAnalysis::UnknownSize || 23198016511932510bd5ec5dad1319922d9daf18991Chris Lattner Earlier.Size == AliasAnalysis::UnknownSize) { 23298016511932510bd5ec5dad1319922d9daf18991Chris Lattner // If we have no TargetData information around, then the size of the store 23398016511932510bd5ec5dad1319922d9daf18991Chris Lattner // is inferrable from the pointee type. If they are the same type, then we 23498016511932510bd5ec5dad1319922d9daf18991Chris Lattner // know that the store is safe. 23598016511932510bd5ec5dad1319922d9daf18991Chris Lattner if (AA.getTargetData() == 0) 23698016511932510bd5ec5dad1319922d9daf18991Chris Lattner return Later.Ptr->getType() == Earlier.Ptr->getType(); 23798016511932510bd5ec5dad1319922d9daf18991Chris Lattner return false; 23898016511932510bd5ec5dad1319922d9daf18991Chris Lattner } 23940dd12e7080c5df253fd70b468368e3144a43c0cChris Lattner 240cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Make sure that the Later size is >= the Earlier size. 241cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (Later.Size < Earlier.Size) 242cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return false; 24340dd12e7080c5df253fd70b468368e3144a43c0cChris Lattner 244cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return true; 24540dd12e7080c5df253fd70b468368e3144a43c0cChris Lattner} 24640dd12e7080c5df253fd70b468368e3144a43c0cChris Lattner 247f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Andersonbool DSE::runOnBasicBlock(BasicBlock &BB) { 248b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool MadeChange = false; 249b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 25040ef630a4626365faeef8696f611e18d1a69f63aChris Lattner // Do a top-down walk on the BB. 251565f96b196325e83f41a83c97bdc751e731de608Chris Lattner for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) { 252565f96b196325e83f41a83c97bdc751e731de608Chris Lattner Instruction *Inst = BBI++; 253565f96b196325e83f41a83c97bdc751e731de608Chris Lattner 2541ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner // Handle 'free' calls specially. 2551ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner if (CallInst *F = isFreeCall(Inst)) { 2561ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner MadeChange |= HandleFree(F); 2571ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner continue; 2581ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner } 2591ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner 26072987a274223e64482d8697b948e1c13a448198dChris Lattner // If we find something that writes memory, get its memory dependence. 26172987a274223e64482d8697b948e1c13a448198dChris Lattner if (!hasMemoryWrite(Inst)) 2626ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson continue; 2630f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner 264e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MemDepResult InstDep = MD->getDependency(Inst); 2655e600e67b11c55c204b3eec00798badc96ed720bChris Lattner 2660f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // Ignore non-local store liveness. 2675e600e67b11c55c204b3eec00798badc96ed720bChris Lattner // FIXME: cross-block DSE would be fun. :) 268cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (InstDep.isNonLocal() || 269cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Ignore self dependence, which happens in the entry block of the 270cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // function. 271cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner InstDep.getInst() == Inst) 272cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner continue; 2731ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner 2740f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // If we're storing the same value back to a pointer that we just 2750f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // loaded from, then the store can be removed. 2760f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 2770f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) { 2780f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (SI->getPointerOperand() == DepLoad->getPointerOperand() && 279184d1ba73866b688cef5f78a214e3fb964b6d833Chris Lattner SI->getOperand(0) == DepLoad && !SI->isVolatile()) { 2800f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // DeleteDeadInstruction can delete the current instruction. Save BBI 2810f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // in case we need it. 2820f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner WeakVH NextInst(BBI); 2830f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner 2840f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner DeleteDeadInstruction(SI); 2850f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner 2860f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (NextInst == 0) // Next instruction deleted. 2870f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner BBI = BB.begin(); 2880f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner else if (BBI != BB.begin()) // Revisit this instruction if possible. 2890f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner --BBI; 2900f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner ++NumFastStores; 2910f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner MadeChange = true; 2920f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner continue; 2930f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner } 2940f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner } 2950f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner } 296bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattner 297cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Figure out what location is being stored to. 298e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AliasAnalysis::Location Loc = getLocForWrite(Inst, *AA); 299cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 300cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we didn't get a useful location, fail. 301cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (Loc.Ptr == 0) 302cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner continue; 303cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 304cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner while (!InstDep.isNonLocal()) { 305cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Get the memory clobbered by the instruction we depend on. MemDep will 306cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // skip any instructions that 'Loc' clearly doesn't interact with. If we 307cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // end up depending on a may- or must-aliased load, then we can't optimize 308cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // away the store and we bail out. However, if we depend on on something 309cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // that overwrites the memory location we *can* potentially optimize it. 310cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // 311cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Find out what memory location the dependant instruction stores. 312cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner Instruction *DepWrite = InstDep.getInst(); 313e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AliasAnalysis::Location DepLoc = getLocForWrite(DepWrite, *AA); 314cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we didn't get a useful location, or if it isn't a size, bail out. 315cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (DepLoc.Ptr == 0) 316cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner break; 317cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 318cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we find a removable write that is completely obliterated by the 319cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // store to 'Loc' then we can remove it. 320e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (isRemovable(DepWrite) && isCompleteOverwrite(Loc, DepLoc, *AA)) { 321cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Delete the store and now-dead instructions that feed it. 322cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner DeleteDeadInstruction(DepWrite); 323cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner ++NumFastStores; 324cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner MadeChange = true; 325cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 326cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // DeleteDeadInstruction can delete the current instruction in loop 327cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // cases, reset BBI. 328cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner BBI = Inst; 329cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (BBI != BB.begin()) 330cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner --BBI; 331cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner break; 332cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 333cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 334f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // If this is a may-aliased store that is clobbering the store value, we 335f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // can keep searching past it for another must-aliased pointer that stores 336f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // to the same location. For example, in: 337f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // store -> P 338f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // store -> Q 339f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // store -> P 340f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // we can remove the first store to P even though we don't know if P and Q 341f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // alias. 342cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (DepWrite == &BB.front()) break; 343cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 344cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Can't look past this instruction if it might read 'Loc'. 345e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (AA->getModRefInfo(DepWrite, Loc) & AliasAnalysis::Ref) 346cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner break; 347bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattner 348e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner InstDep = MD->getPointerDependencyFrom(Loc, false, DepWrite, &BB); 34958571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky } 350b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 351b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 352565f96b196325e83f41a83c97bdc751e731de608Chris Lattner // If this block ends in a return, unwind, or unreachable, all allocas are 353565f96b196325e83f41a83c97bdc751e731de608Chris Lattner // dead at its end, which means stores to them are also dead. 35443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (BB.getTerminator()->getNumSuccessors() == 0) 355925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner MadeChange |= handleEndBlock(BB); 356b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 357b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return MadeChange; 358b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 359b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 3601ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner/// HandleFree - Handle frees of entire structures whose dependency is a store 3611ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner/// to a field of that structure. 3621ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattnerbool DSE::HandleFree(CallInst *F) { 363e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MemDepResult Dep = MD->getDependency(F); 364720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman do { 3651ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner if (Dep.isNonLocal()) return false; 3661ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner 367720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman Instruction *Dependency = Dep.getInst(); 368bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattner if (!hasMemoryWrite(Dependency) || !isRemovable(Dependency)) 369720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman return false; 370dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson 371720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman Value *DepPointer = getPointerOperand(Dependency)->getUnderlyingObject(); 37202ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 373720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman // Check for aliasing. 374e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (AA->alias(F->getArgOperand(0), 1, DepPointer, 1) != 3751ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner AliasAnalysis::MustAlias) 376720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman return false; 377a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 378720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman // DCE instructions only used to calculate that store 379720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman DeleteDeadInstruction(Dependency); 380720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman ++NumFastStores; 381720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman 382720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman // Inst's old Dependency is now deleted. Compute the next dependency, 383720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman // which may also be dead, as in 384720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman // s[0] = 0; 385720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman // s[1] = 0; // This has just been deleted. 386720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman // free(s); 387e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner Dep = MD->getDependency(F); 388720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman } while (!Dep.isNonLocal()); 3891ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner 390925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner return true; 391a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson} 392a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 393666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson/// handleEndBlock - Remove dead stores to stack-allocated locations in the 394bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// function end block. Ex: 395bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// %A = alloca i32 396bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ... 397bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// store i32 1, i32* %A 398bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ret void 399925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattnerbool DSE::handleEndBlock(BasicBlock &BB) { 40043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool MadeChange = false; 40143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 40243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Pointers alloca'd in this function are dead in the end block 40383d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner SmallPtrSet<Value*, 64> DeadPointers; 40443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 405925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // Find all of the alloca'd pointers in the entry block. 40643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BasicBlock *Entry = BB.getParent()->begin(); 40743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) 40843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 40983d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner DeadPointers.insert(AI); 410925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 411925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // Treat byval arguments the same, stores to them are dead at the end of the 412925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // function. 413a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (Function::arg_iterator AI = BB.getParent()->arg_begin(), 414a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson AE = BB.getParent()->arg_end(); AI != AE; ++AI) 415a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (AI->hasByValAttr()) 41683d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner DeadPointers.insert(AI); 41743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 41843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Scan the basic block backwards 41943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ 42043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson --BBI; 42143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 42283d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // If we find a store, check to see if it points into a dead stack value. 42383d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner if (hasMemoryWrite(BBI) && isRemovable(BBI)) { 42483d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // See through pointer-to-pointer bitcasts 42583d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner Value *Pointer = getPointerOperand(BBI)->getUnderlyingObject(); 42683d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner 42783d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // Alloca'd pointers or byval arguments (which are functionally like 42883d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // alloca's) are valid candidates for removal. 42983d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner if (DeadPointers.count(Pointer)) { 43083d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // DCE instructions only used to calculate that store. 43183d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner Instruction *Dead = BBI++; 43283d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner DeleteDeadInstruction(Dead, &DeadPointers); 43383d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner ++NumFastStores; 43483d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner MadeChange = true; 435a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson continue; 43683d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } 43783d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } 43883d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner 43983d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // Remove any dead non-memory-mutating instructions. 44083d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner if (isInstructionTriviallyDead(BBI)) { 44183d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner Instruction *Inst = BBI++; 44283d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner DeleteDeadInstruction(Inst, &DeadPointers); 44383d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner ++NumFastOther; 44483d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner MadeChange = true; 44583d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner continue; 44683d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } 44783d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner 44883d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner if (AllocaInst *A = dyn_cast<AllocaInst>(BBI)) { 44983d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner DeadPointers.erase(A); 45083d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner continue; 451bb3abf41a868357e95b639b34baebf802199e190Owen Anderson } 452bb3abf41a868357e95b639b34baebf802199e190Owen Anderson 45383d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner 45483d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner Value *KillPointer = 0; 45583d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner uint64_t KillPointerSize = AliasAnalysis::UnknownSize; 45643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 45743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // If we encounter a use of the pointer, it is no longer considered dead 458925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner if (LoadInst *L = dyn_cast<LoadInst>(BBI)) { 45983d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner KillPointer = L->getPointerOperand(); 460cccbe7e4156884c6483b548997eea02bcf8b748eNick Lewycky } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) { 46183d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner KillPointer = V->getOperand(0); 46283d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(BBI)) { 46383d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner KillPointer = cast<MemTransferInst>(BBI)->getSource(); 46483d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner if (ConstantInt *Len = dyn_cast<ConstantInt>(MTI->getLength())) 46583d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner KillPointerSize = Len->getZExtValue(); 466d09475c2269ca822620e2e561af62d0a8aec7b1eGabor Greif } else if (CallSite CS = cast<Value>(BBI)) { 46783d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // If this call does not access memory, it can't be loading any of our 46883d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // pointers. 469e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (AA->doesNotAccessMemory(CS)) 470df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson continue; 471df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson 47283d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner unsigned NumModRef = 0; 47383d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner unsigned NumOther = 0; 474362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 47543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Remove any pointers made undead by the call from the dead set 476a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson std::vector<Value*> dead; 47783d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner for (SmallPtrSet<Value*, 64>::iterator I = DeadPointers.begin(), 47883d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner E = DeadPointers.end(); I != E; ++I) { 479362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // HACK: if we detect that our AA is imprecise, it's not 480362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // worth it to scan the rest of the deadPointers set. Just 481362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // assume that the AA will return ModRef for everything, and 482362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // go ahead and bail. 48383d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner if (NumModRef >= 16 && NumOther == 0) { 48483d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner DeadPointers.clear(); 485362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson return MadeChange; 486362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson } 487cccbe7e4156884c6483b548997eea02bcf8b748eNick Lewycky 48843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // See if the call site touches it 48998016511932510bd5ec5dad1319922d9daf18991Chris Lattner AliasAnalysis::ModRefResult A = 490e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AA->getModRefInfo(CS, *I, getPointerSize(*I, *AA)); 491362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 492362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson if (A == AliasAnalysis::ModRef) 49383d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner ++NumModRef; 494362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson else 49583d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner ++NumOther; 496362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 4973e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) 49843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson dead.push_back(*I); 49943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 50043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 501a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end(); 50243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson I != E; ++I) 50383d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner DeadPointers.erase(*I); 50443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 50543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 50683d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } else { 50783d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // Not a loading instruction. 508925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner continue; 50943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 5105d0392c6b370758750b397e254a6c6f028479969Duncan Sands 51183d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner KillPointer = KillPointer->getUnderlyingObject(); 5125d0392c6b370758750b397e254a6c6f028479969Duncan Sands 51343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Deal with undead pointers 51483d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner MadeChange |= RemoveUndeadPointers(KillPointer, KillPointerSize, BBI, 51583d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner DeadPointers); 51643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 51743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 51843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson return MadeChange; 51943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 52043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 521362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson/// RemoveUndeadPointers - check for uses of a pointer that make it 522362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson/// undead when scanning for dead stores to alloca's. 5233da848bbda62b25c12335998aaa44ab361f0bf15Dan Gohmanbool DSE::RemoveUndeadPointers(Value *killPointer, uint64_t killPointerSize, 524925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner BasicBlock::iterator &BBI, 52583d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner SmallPtrSet<Value*, 64> &DeadPointers) { 526362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // If the kill pointer can be easily reduced to an alloca, 527925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // don't bother doing extraneous AA queries. 52883d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner if (DeadPointers.count(killPointer)) { 52983d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner DeadPointers.erase(killPointer); 530362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson return false; 531362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson } 532362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 533925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // A global can't be in the dead pointer set. 534925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner if (isa<GlobalValue>(killPointer)) 535925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner return false; 536925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 53743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool MadeChange = false; 53843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 539925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner SmallVector<Value*, 16> undead; 540cccbe7e4156884c6483b548997eea02bcf8b748eNick Lewycky 54183d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner for (SmallPtrSet<Value*, 64>::iterator I = DeadPointers.begin(), 54283d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner E = DeadPointers.end(); I != E; ++I) { 54343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // See if this pointer could alias it 544e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AliasAnalysis::AliasResult A = AA->alias(*I, getPointerSize(*I, *AA), 545e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner killPointer, killPointerSize); 54643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 54743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // If it must-alias and a store, we can delete it 54843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) { 549cccbe7e4156884c6483b548997eea02bcf8b748eNick Lewycky StoreInst *S = cast<StoreInst>(BBI); 55043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 55143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Remove it! 552cccbe7e4156884c6483b548997eea02bcf8b748eNick Lewycky ++BBI; 55383d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner DeleteDeadInstruction(S, &DeadPointers); 554fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumFastStores; 55543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MadeChange = true; 55643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 55743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 55843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 55943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Otherwise, it is undead 560925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner } else if (A != AliasAnalysis::NoAlias) 561925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner undead.push_back(*I); 56243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 56343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 564925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner for (SmallVector<Value*, 16>::iterator I = undead.begin(), E = undead.end(); 56543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson I != E; ++I) 56683d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner DeadPointers.erase(*I); 56743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 56843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson return MadeChange; 56943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 57043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 571925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner/// DeleteDeadInstruction - Delete this instruction. Before we do, go through 572925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner/// and zero out all the operands of this instruction. If any of them become 573925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner/// dead, delete them and the computation tree that feeds them. 574925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner/// 575925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner/// If ValueSet is non-null, remove any deleted instructions from it as well. 576925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner/// 577925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattnervoid DSE::DeleteDeadInstruction(Instruction *I, 578925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner SmallPtrSet<Value*, 64> *ValueSet) { 579925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner SmallVector<Instruction*, 32> NowDeadInsts; 580925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 581925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner NowDeadInsts.push_back(I); 582925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner --NumFastOther; 583925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 584925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // Before we touch this instruction, remove it from memdep! 585321a813c536e2f1f2f05bbe78a7fbf64046f0557Dan Gohman do { 586321a813c536e2f1f2f05bbe78a7fbf64046f0557Dan Gohman Instruction *DeadInst = NowDeadInsts.pop_back_val(); 587925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 588925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner ++NumFastOther; 589925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 590925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // This instruction is dead, zap it, in stages. Start by removing it from 591925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // MemDep, which needs to know the operands and needs it to be in the 592925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // function. 593e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MD->removeInstruction(DeadInst); 594bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson 595925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) { 596925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner Value *Op = DeadInst->getOperand(op); 597925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner DeadInst->setOperand(op, 0); 598925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 599925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // If this operand just became dead, add it to the NowDeadInsts list. 600925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner if (!Op->use_empty()) continue; 601925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 602925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner if (Instruction *OpI = dyn_cast<Instruction>(Op)) 603925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner if (isInstructionTriviallyDead(OpI)) 604925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner NowDeadInsts.push_back(OpI); 605925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner } 606925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 607925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner DeadInst->eraseFromParent(); 608925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 609925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner if (ValueSet) ValueSet->erase(DeadInst); 610321a813c536e2f1f2f05bbe78a7fbf64046f0557Dan Gohman } while (!NowDeadInsts.empty()); 611b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 612cccbe7e4156884c6483b548997eea02bcf8b748eNick Lewycky 613