DeadStoreElimination.cpp revision 565f96b196325e83f41a83c97bdc751e731de608
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" 29b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Analysis/MemoryDependenceAnalysis.h" 30a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson#include "llvm/Target/TargetData.h" 31b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Transforms/Utils/Local.h" 32b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Support/Compiler.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 { 39f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Anderson struct VISIBILITY_HIDDEN DSE : public FunctionPass { 40b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson static char ID; // Pass identification, replacement for typeid 41ae73dc1448d25b02cabc7c64c86c64371453dda8Dan Gohman DSE() : FunctionPass(&ID) {} 42b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 43b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson virtual bool runOnFunction(Function &F) { 44b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool Changed = false; 45b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 46b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson Changed |= runOnBasicBlock(*I); 47b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return Changed; 48b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 49b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 50b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool runOnBasicBlock(BasicBlock &BB); 51925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner bool handleFreeWithNonTrivialDependency(FreeInst *F, Instruction *Dep); 52925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner bool handleEndBlock(BasicBlock &BB); 53c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson bool RemoveUndeadPointers(Value* pointer, uint64_t killPointerSize, 5443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BasicBlock::iterator& BBI, 55925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner SmallPtrSet<Value*, 64>& deadPointers); 56925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner void DeleteDeadInstruction(Instruction *I, 57925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner SmallPtrSet<Value*, 64> *deadPointers = 0); 58925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 59b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 60b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // getAnalysisUsage - We require post dominance frontiers (aka Control 61b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Dependence Graph) 62b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const { 63b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.setPreservesCFG(); 648aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson AU.addRequired<DominatorTree>(); 65a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addRequired<TargetData>(); 66a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addRequired<AliasAnalysis>(); 67b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addRequired<MemoryDependenceAnalysis>(); 688aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson AU.addPreserved<DominatorTree>(); 69a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addPreserved<AliasAnalysis>(); 70b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addPreserved<MemoryDependenceAnalysis>(); 71b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 72b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson }; 73b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 74b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 75844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar DSE::ID = 0; 76844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<DSE> X("dse", "Dead Store Elimination"); 77844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 78f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen AndersonFunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } 79b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 80f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Andersonbool DSE::runOnBasicBlock(BasicBlock &BB) { 81b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 827ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson TargetData &TD = getAnalysis<TargetData>(); 837ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson 84bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson // Record the last-seen store to this pointer 85b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson DenseMap<Value*, StoreInst*> lastStore; 86b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 87b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool MadeChange = false; 88b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 89b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Do a top-down walk on the BB 90565f96b196325e83f41a83c97bdc751e731de608Chris Lattner for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) { 91565f96b196325e83f41a83c97bdc751e731de608Chris Lattner Instruction *Inst = BBI++; 92565f96b196325e83f41a83c97bdc751e731de608Chris Lattner 936f46d65104ab08a75acb3d24056d19bdc2b054c3Owen Anderson // If we find a store or a free... 94565f96b196325e83f41a83c97bdc751e731de608Chris Lattner if (!isa<StoreInst>(Inst) && !isa<FreeInst>(Inst)) 956ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson continue; 965d0392c6b370758750b397e254a6c6f028479969Duncan Sands 976ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson Value* pointer = 0; 98565f96b196325e83f41a83c97bdc751e731de608Chris Lattner if (StoreInst* S = dyn_cast<StoreInst>(Inst)) { 995d0392c6b370758750b397e254a6c6f028479969Duncan Sands if (S->isVolatile()) 1005dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson continue; 1015d0392c6b370758750b397e254a6c6f028479969Duncan Sands pointer = S->getPointerOperand(); 1025d0392c6b370758750b397e254a6c6f028479969Duncan Sands } else { 103565f96b196325e83f41a83c97bdc751e731de608Chris Lattner pointer = cast<FreeInst>(Inst)->getPointerOperand(); 1045d0392c6b370758750b397e254a6c6f028479969Duncan Sands } 1055d0392c6b370758750b397e254a6c6f028479969Duncan Sands 1065d0392c6b370758750b397e254a6c6f028479969Duncan Sands pointer = pointer->stripPointerCasts(); 107565f96b196325e83f41a83c97bdc751e731de608Chris Lattner StoreInst *&last = lastStore[pointer]; 108565f96b196325e83f41a83c97bdc751e731de608Chris Lattner 1096ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // ... to a pointer that has been stored to before... 1106ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (last) { 111565f96b196325e83f41a83c97bdc751e731de608Chris Lattner Instruction* dep = MD.getDependency(Inst); 112565f96b196325e83f41a83c97bdc751e731de608Chris Lattner bool deletedStore = false; 113565f96b196325e83f41a83c97bdc751e731de608Chris Lattner 1146ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // ... and no other memory dependencies are between them.... 1156ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson while (dep != MemoryDependenceAnalysis::None && 1166ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson dep != MemoryDependenceAnalysis::NonLocal && 1176ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson isa<StoreInst>(dep)) { 1187ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson if (dep != last || 119514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands TD.getTypeStoreSize(last->getOperand(0)->getType()) > 120565f96b196325e83f41a83c97bdc751e731de608Chris Lattner TD.getTypeStoreSize(Inst->getOperand(0)->getType())) { 121565f96b196325e83f41a83c97bdc751e731de608Chris Lattner dep = MD.getDependency(Inst, dep); 1226ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson continue; 1236ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson } 124faac518ce0ae88a19f26b9aa9d34f6bf86ecb8c4Owen Anderson 125925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // Delete the store and now-dead instructions that feed it. 126925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner DeleteDeadInstruction(last); 1276ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson NumFastStores++; 1286ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson deletedStore = true; 1296ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson MadeChange = true; 1306ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson break; 131b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 132565f96b196325e83f41a83c97bdc751e731de608Chris Lattner 133565f96b196325e83f41a83c97bdc751e731de608Chris Lattner // If we deleted a store, reinvestigate this instruction. 134565f96b196325e83f41a83c97bdc751e731de608Chris Lattner if (deletedStore) { 135565f96b196325e83f41a83c97bdc751e731de608Chris Lattner --BBI; 136565f96b196325e83f41a83c97bdc751e731de608Chris Lattner continue; 137565f96b196325e83f41a83c97bdc751e731de608Chris Lattner } 1386ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson } 1396ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson 1406ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // Handle frees whose dependencies are non-trivial. 141565f96b196325e83f41a83c97bdc751e731de608Chris Lattner if (FreeInst* F = dyn_cast<FreeInst>(Inst)) { 142565f96b196325e83f41a83c97bdc751e731de608Chris Lattner MadeChange |= handleFreeWithNonTrivialDependency(F, MD.getDependency(F)); 143925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 144565f96b196325e83f41a83c97bdc751e731de608Chris Lattner // No known stores after the free. 1456ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson last = 0; 1466ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson } else { 147565f96b196325e83f41a83c97bdc751e731de608Chris Lattner StoreInst* S = cast<StoreInst>(Inst); 1488aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson 1498aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson // If we're storing the same value back to a pointer that we just 1508aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson // loaded from, then the store can be removed; 1518aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson if (LoadInst* L = dyn_cast<LoadInst>(S->getOperand(0))) { 152565f96b196325e83f41a83c97bdc751e731de608Chris Lattner // FIXME: Don't do dep query if Parents don't match and other stuff! 1538aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson Instruction* dep = MD.getDependency(S); 1548aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson DominatorTree& DT = getAnalysis<DominatorTree>(); 1558aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson 15680e051dfdede65678ac66f1552278338bc1a1b33Owen Anderson if (!S->isVolatile() && S->getParent() == L->getParent() && 1578aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson S->getPointerOperand() == L->getPointerOperand() && 158925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner (dep == MemoryDependenceAnalysis::None || 159925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner dep == MemoryDependenceAnalysis::NonLocal || 160925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner DT.dominates(dep, L))) { 1618aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson 162925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner DeleteDeadInstruction(S); 163565f96b196325e83f41a83c97bdc751e731de608Chris Lattner --BBI; 1648aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson NumFastStores++; 1658aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson MadeChange = true; 1668aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson } else 1678aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson // Update our most-recent-store map. 1688aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson last = S; 1698aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson } else 1708aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson // Update our most-recent-store map. 1718aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson last = S; 172b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 173b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 174b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 175565f96b196325e83f41a83c97bdc751e731de608Chris Lattner // If this block ends in a return, unwind, or unreachable, all allocas are 176565f96b196325e83f41a83c97bdc751e731de608Chris Lattner // dead at its end, which means stores to them are also dead. 17743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (BB.getTerminator()->getNumSuccessors() == 0) 178925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner MadeChange |= handleEndBlock(BB); 179b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 180b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return MadeChange; 181b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 182b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 183a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson/// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose 184925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner/// dependency is a store to a field of that structure. 185925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattnerbool DSE::handleFreeWithNonTrivialDependency(FreeInst* F, Instruction* dep) { 186a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson TargetData &TD = getAnalysis<TargetData>(); 187a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 188a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 189dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson if (dep == MemoryDependenceAnalysis::None || 190dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson dep == MemoryDependenceAnalysis::NonLocal) 191dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson return false; 192dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson 193dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson StoreInst* dependency = dyn_cast<StoreInst>(dep); 194dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson if (!dependency) 195dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson return false; 1965dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson else if (dependency->isVolatile()) 1975dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson return false; 198dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson 199a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson Value* depPointer = dependency->getPointerOperand(); 200666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson const Type* depType = dependency->getOperand(0)->getType(); 201514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands unsigned depPointerSize = TD.getTypeStoreSize(depType); 20202ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 203a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson // Check for aliasing 20402ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands AliasAnalysis::AliasResult A = AA.alias(F->getPointerOperand(), ~0U, 205a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson depPointer, depPointerSize); 20602ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 207925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner if (A != AliasAnalysis::MustAlias) 208925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner return false; 209a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 210925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // DCE instructions only used to calculate that store 211925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner DeleteDeadInstruction(dependency); 212925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner NumFastStores++; 213925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner return true; 214a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson} 215a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 216666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson/// handleEndBlock - Remove dead stores to stack-allocated locations in the 217bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// function end block. Ex: 218bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// %A = alloca i32 219bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ... 220bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// store i32 1, i32* %A 221bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ret void 222925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattnerbool DSE::handleEndBlock(BasicBlock &BB) { 22343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson TargetData &TD = getAnalysis<TargetData>(); 22443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 22543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 22643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool MadeChange = false; 22743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 22843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Pointers alloca'd in this function are dead in the end block 229a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson SmallPtrSet<Value*, 64> deadPointers; 23043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 231925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // Find all of the alloca'd pointers in the entry block. 23243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BasicBlock *Entry = BB.getParent()->begin(); 23343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) 23443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 23543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson deadPointers.insert(AI); 236925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 237925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // Treat byval arguments the same, stores to them are dead at the end of the 238925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // function. 239a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (Function::arg_iterator AI = BB.getParent()->arg_begin(), 240a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson AE = BB.getParent()->arg_end(); AI != AE; ++AI) 241a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (AI->hasByValAttr()) 242a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson deadPointers.insert(AI); 24343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 24443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Scan the basic block backwards 24543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ 24643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson --BBI; 24743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 248925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // If we find a store whose pointer is dead. 24943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (StoreInst* S = dyn_cast<StoreInst>(BBI)) { 2505dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson if (!S->isVolatile()) { 2515dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson // See through pointer-to-pointer bitcasts 2525d0392c6b370758750b397e254a6c6f028479969Duncan Sands Value* pointerOperand = S->getPointerOperand()->getUnderlyingObject(); 2535d0392c6b370758750b397e254a6c6f028479969Duncan Sands 254e3c36f67580f0963abdf696a26690facb0791ce0Owen Anderson // Alloca'd pointers or byval arguments (which are functionally like 255e3c36f67580f0963abdf696a26690facb0791ce0Owen Anderson // alloca's) are valid candidates for removal. 256a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (deadPointers.count(pointerOperand)) { 257925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // DCE instructions only used to calculate that store. 2585dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson BBI++; 259925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner DeleteDeadInstruction(S, &deadPointers); 2605dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson NumFastStores++; 2615dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson MadeChange = true; 2625dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson } 26343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 264bb3abf41a868357e95b639b34baebf802199e190Owen Anderson 265bb3abf41a868357e95b639b34baebf802199e190Owen Anderson continue; 266925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner } 267a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson 268925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // We can also remove memcpy's to local variables at the end of a function. 269925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner if (MemCpyInst *M = dyn_cast<MemCpyInst>(BBI)) { 270925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner Value *dest = M->getDest()->getUnderlyingObject(); 2715d0392c6b370758750b397e254a6c6f028479969Duncan Sands 272a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (deadPointers.count(dest)) { 273a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson BBI++; 274925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner DeleteDeadInstruction(M, &deadPointers); 275a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson NumFastOther++; 276a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson MadeChange = true; 277a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson continue; 278a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } 279a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson 280925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // Because a memcpy is also a load, we can't skip it if we didn't remove 281925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // it. 282bb3abf41a868357e95b639b34baebf802199e190Owen Anderson } 283bb3abf41a868357e95b639b34baebf802199e190Owen Anderson 284bb3abf41a868357e95b639b34baebf802199e190Owen Anderson Value* killPointer = 0; 285c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson uint64_t killPointerSize = ~0UL; 28643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 28743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // If we encounter a use of the pointer, it is no longer considered dead 288925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner if (LoadInst *L = dyn_cast<LoadInst>(BBI)) { 289a72acf938902ea8ae2776cad7327257e88a63a54Nate Begeman // However, if this load is unused and not volatile, we can go ahead and 290a72acf938902ea8ae2776cad7327257e88a63a54Nate Begeman // remove it, and not have to worry about it making our pointer undead! 29100acf97feb2cba053a07505dfad9116ad09aae7aDan Gohman if (L->use_empty() && !L->isVolatile()) { 292772601a8850808a66270372164941e373074493dOwen Anderson BBI++; 293925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner DeleteDeadInstruction(L, &deadPointers); 294772601a8850808a66270372164941e373074493dOwen Anderson NumFastOther++; 295772601a8850808a66270372164941e373074493dOwen Anderson MadeChange = true; 296772601a8850808a66270372164941e373074493dOwen Anderson continue; 297772601a8850808a66270372164941e373074493dOwen Anderson } 298772601a8850808a66270372164941e373074493dOwen Anderson 29943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson killPointer = L->getPointerOperand(); 30043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } else if (VAArgInst* V = dyn_cast<VAArgInst>(BBI)) { 30143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson killPointer = V->getOperand(0); 302c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson } else if (isa<MemCpyInst>(BBI) && 303c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson isa<ConstantInt>(cast<MemCpyInst>(BBI)->getLength())) { 304c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson killPointer = cast<MemCpyInst>(BBI)->getSource(); 305c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson killPointerSize = cast<ConstantInt>( 306c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson cast<MemCpyInst>(BBI)->getLength())->getZExtValue(); 30743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } else if (AllocaInst* A = dyn_cast<AllocaInst>(BBI)) { 30843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson deadPointers.erase(A); 309772601a8850808a66270372164941e373074493dOwen Anderson 310772601a8850808a66270372164941e373074493dOwen Anderson // Dead alloca's can be DCE'd when we reach them 311b4b04172206810623845a7f11dd3a65b0b3b10d5Nick Lewycky if (A->use_empty()) { 312772601a8850808a66270372164941e373074493dOwen Anderson BBI++; 313925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner DeleteDeadInstruction(A, &deadPointers); 314772601a8850808a66270372164941e373074493dOwen Anderson NumFastOther++; 315772601a8850808a66270372164941e373074493dOwen Anderson MadeChange = true; 316772601a8850808a66270372164941e373074493dOwen Anderson } 317772601a8850808a66270372164941e373074493dOwen Anderson 31843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 31943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } else if (CallSite::get(BBI).getInstruction() != 0) { 320df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson // If this call does not access memory, it can't 321df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson // be undeadifying any of our pointers. 322df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson CallSite CS = CallSite::get(BBI); 323dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands if (AA.doesNotAccessMemory(CS)) 324df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson continue; 325df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson 326362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson unsigned modRef = 0; 327362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson unsigned other = 0; 328362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 32943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Remove any pointers made undead by the call from the dead set 330a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson std::vector<Value*> dead; 331a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 33243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson E = deadPointers.end(); I != E; ++I) { 333362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // HACK: if we detect that our AA is imprecise, it's not 334362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // worth it to scan the rest of the deadPointers set. Just 335362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // assume that the AA will return ModRef for everything, and 336362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // go ahead and bail. 337362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson if (modRef >= 16 && other == 0) { 338362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson deadPointers.clear(); 339362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson return MadeChange; 340362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson } 34102ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 34243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Get size information for the alloca 34302ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands unsigned pointerSize = ~0U; 344a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) { 345a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize())) 346565f96b196325e83f41a83c97bdc751e731de608Chris Lattner pointerSize = C->getZExtValue() * 347a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson TD.getABITypeSize(A->getAllocatedType()); 348a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } else { 349a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson const PointerType* PT = cast<PointerType>( 350a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson cast<Argument>(*I)->getType()); 351a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson pointerSize = TD.getABITypeSize(PT->getElementType()); 352a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } 35302ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 35443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // See if the call site touches it 355df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, pointerSize); 356362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 357362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson if (A == AliasAnalysis::ModRef) 358362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson modRef++; 359362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson else 360362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson other++; 361362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 3623e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) 36343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson dead.push_back(*I); 36443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 36543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 366a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end(); 36743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson I != E; ++I) 368a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson deadPointers.erase(*I); 36943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 37043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 371925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner } else if (isInstructionTriviallyDead(BBI)) { 372772601a8850808a66270372164941e373074493dOwen Anderson // For any non-memory-affecting non-terminators, DCE them as we reach them 373925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner Instruction *Inst = BBI; 374925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner BBI++; 375925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner DeleteDeadInstruction(Inst, &deadPointers); 376925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner NumFastOther++; 377925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner MadeChange = true; 378925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner continue; 37943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 38043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 38143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (!killPointer) 38243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 3835d0392c6b370758750b397e254a6c6f028479969Duncan Sands 3845d0392c6b370758750b397e254a6c6f028479969Duncan Sands killPointer = killPointer->getUnderlyingObject(); 3855d0392c6b370758750b397e254a6c6f028479969Duncan Sands 38643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Deal with undead pointers 387c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson MadeChange |= RemoveUndeadPointers(killPointer, killPointerSize, BBI, 388925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner deadPointers); 38943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 39043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 39143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson return MadeChange; 39243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 39343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 394362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson/// RemoveUndeadPointers - check for uses of a pointer that make it 395362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson/// undead when scanning for dead stores to alloca's. 396c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Andersonbool DSE::RemoveUndeadPointers(Value* killPointer, uint64_t killPointerSize, 397925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner BasicBlock::iterator &BBI, 398925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner SmallPtrSet<Value*, 64>& deadPointers) { 39943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson TargetData &TD = getAnalysis<TargetData>(); 40043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 40143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 402362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // If the kill pointer can be easily reduced to an alloca, 403925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // don't bother doing extraneous AA queries. 404a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (deadPointers.count(killPointer)) { 405a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson deadPointers.erase(killPointer); 406362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson return false; 407362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson } 408362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 409925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // A global can't be in the dead pointer set. 410925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner if (isa<GlobalValue>(killPointer)) 411925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner return false; 412925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 41343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool MadeChange = false; 41443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 415925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner SmallVector<Value*, 16> undead; 41643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 417a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 41843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson E = deadPointers.end(); I != E; ++I) { 419925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // Get size information for the alloca. 42002ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands unsigned pointerSize = ~0U; 421a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) { 422a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize())) 423925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner pointerSize = C->getZExtValue() * 424a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson TD.getABITypeSize(A->getAllocatedType()); 425a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } else { 426925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner const PointerType* PT = cast<PointerType>(cast<Argument>(*I)->getType()); 427a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson pointerSize = TD.getABITypeSize(PT->getElementType()); 428a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } 42902ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 43043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // See if this pointer could alias it 431666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson AliasAnalysis::AliasResult A = AA.alias(*I, pointerSize, 432c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson killPointer, killPointerSize); 43343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 43443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // If it must-alias and a store, we can delete it 43543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) { 43643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson StoreInst* S = cast<StoreInst>(BBI); 43743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 43843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Remove it! 43943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BBI++; 440925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner DeleteDeadInstruction(S, &deadPointers); 44143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson NumFastStores++; 44243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MadeChange = true; 44343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 44443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 44543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 44643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Otherwise, it is undead 447925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner } else if (A != AliasAnalysis::NoAlias) 448925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner undead.push_back(*I); 44943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 45043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 451925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner for (SmallVector<Value*, 16>::iterator I = undead.begin(), E = undead.end(); 45243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson I != E; ++I) 453a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson deadPointers.erase(*I); 45443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 45543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson return MadeChange; 45643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 45743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 458925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner/// DeleteDeadInstruction - Delete this instruction. Before we do, go through 459925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner/// and zero out all the operands of this instruction. If any of them become 460925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner/// dead, delete them and the computation tree that feeds them. 461925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner/// 462925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner/// If ValueSet is non-null, remove any deleted instructions from it as well. 463925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner/// 464925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattnervoid DSE::DeleteDeadInstruction(Instruction *I, 465925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner SmallPtrSet<Value*, 64> *ValueSet) { 466925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner SmallVector<Instruction*, 32> NowDeadInsts; 467925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 468925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner NowDeadInsts.push_back(I); 469925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner --NumFastOther; 470925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 471925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // Before we touch this instruction, remove it from memdep! 472925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>(); 473925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner while (!NowDeadInsts.empty()) { 474925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner Instruction *DeadInst = NowDeadInsts.back(); 475925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner NowDeadInsts.pop_back(); 476925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 477925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner ++NumFastOther; 478925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 479925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // This instruction is dead, zap it, in stages. Start by removing it from 480925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // MemDep, which needs to know the operands and needs it to be in the 481925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // function. 482925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner MDA.removeInstruction(DeadInst); 483bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson 484925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) { 485925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner Value *Op = DeadInst->getOperand(op); 486925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner DeadInst->setOperand(op, 0); 487925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 488925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // If this operand just became dead, add it to the NowDeadInsts list. 489925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner if (!Op->use_empty()) continue; 490925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 491925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner if (Instruction *OpI = dyn_cast<Instruction>(Op)) 492925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner if (isInstructionTriviallyDead(OpI)) 493925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner NowDeadInsts.push_back(OpI); 494925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner } 495925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 496925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner DeadInst->eraseFromParent(); 497925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 498925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner if (ValueSet) ValueSet->erase(DeadInst); 499b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 500b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 501