DeadStoreElimination.cpp revision dff6710717b159f089c76a07eda074eb6347eb92
1666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson//===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===// 2b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson// 3b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson// The LLVM Compiler Infrastructure 4b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson// 5bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson// This file was developed by Owen Anderson and is distributed under 6b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson// the University of Illinois Open Source 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" 23b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Pass.h" 24b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/ADT/SetVector.h" 25b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/ADT/SmallPtrSet.h" 26b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/ADT/Statistic.h" 27a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson#include "llvm/Analysis/AliasAnalysis.h" 28b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Analysis/MemoryDependenceAnalysis.h" 29a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson#include "llvm/Target/TargetData.h" 30b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Transforms/Utils/Local.h" 31b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Support/Compiler.h" 32b77c457cc87aeeb166995aed793a516e9e431703Owen Andersonusing namespace llvm; 33b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 34b77c457cc87aeeb166995aed793a516e9e431703Owen AndersonSTATISTIC(NumFastStores, "Number of stores deleted"); 35b77c457cc87aeeb166995aed793a516e9e431703Owen AndersonSTATISTIC(NumFastOther , "Number of other instrs removed"); 36b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 37b77c457cc87aeeb166995aed793a516e9e431703Owen Andersonnamespace { 38f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Anderson struct VISIBILITY_HIDDEN DSE : public FunctionPass { 39b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson static char ID; // Pass identification, replacement for typeid 40f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Anderson DSE() : FunctionPass((intptr_t)&ID) {} 41b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 42b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson virtual bool runOnFunction(Function &F) { 43b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool Changed = false; 44b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 45b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson Changed |= runOnBasicBlock(*I); 46b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return Changed; 47b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 48b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 49b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool runOnBasicBlock(BasicBlock &BB); 50666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson bool handleFreeWithNonTrivialDependency(FreeInst* F, 51666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson Instruction* dependency, 52666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson SetVector<Instruction*>& possiblyDead); 5343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool handleEndBlock(BasicBlock& BB, SetVector<Instruction*>& possiblyDead); 54bb3abf41a868357e95b639b34baebf802199e190Owen Anderson bool RemoveUndeadPointers(Value* pointer, 5543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BasicBlock::iterator& BBI, 56bb3abf41a868357e95b639b34baebf802199e190Owen Anderson SmallPtrSet<AllocaInst*, 64>& deadPointers, 5743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson SetVector<Instruction*>& possiblyDead); 58b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson void DeleteDeadInstructionChains(Instruction *I, 59b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson SetVector<Instruction*> &DeadInsts); 606ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson 61c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson /// Find the base pointer that a pointer came from 62c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson /// Because this is used to find pointers that originate 63c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson /// from allocas, it is safe to ignore GEP indices, since 64c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson /// either the store will be in the alloca, and thus dead, 65c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson /// or beyond the end of the alloca, and thus undefined. 667ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson void TranslatePointerBitCasts(Value*& v, bool zeroGepsOnly = false) { 67666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson assert(isa<PointerType>(v->getType()) && 68666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson "Translating a non-pointer type?"); 696ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson while (true) { 70ce17b1c1f8761f5fabb4b0531b7127254cdc89deOwen Anderson if (BitCastInst* C = dyn_cast<BitCastInst>(v)) 71ce17b1c1f8761f5fabb4b0531b7127254cdc89deOwen Anderson v = C->getOperand(0); 72ce17b1c1f8761f5fabb4b0531b7127254cdc89deOwen Anderson else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(v)) 737ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson if (!zeroGepsOnly || G->hasAllZeroIndices()) { 747ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson v = G->getOperand(0); 757ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson } else { 767ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson break; 777ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson } 786ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson else 796ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson break; 806ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson } 813e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson } 82b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 83b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // getAnalysisUsage - We require post dominance frontiers (aka Control 84b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Dependence Graph) 85b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const { 86b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.setPreservesCFG(); 87a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addRequired<TargetData>(); 88a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addRequired<AliasAnalysis>(); 89b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addRequired<MemoryDependenceAnalysis>(); 90a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addPreserved<AliasAnalysis>(); 91b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addPreserved<MemoryDependenceAnalysis>(); 92b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 93b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson }; 94f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Anderson char DSE::ID = 0; 95f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Anderson RegisterPass<DSE> X("dse", "Dead Store Elimination"); 96b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 97b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 98f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen AndersonFunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } 99b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 100f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Andersonbool DSE::runOnBasicBlock(BasicBlock &BB) { 101b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1027ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson TargetData &TD = getAnalysis<TargetData>(); 1037ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson 104bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson // Record the last-seen store to this pointer 105b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson DenseMap<Value*, StoreInst*> lastStore; 106bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson // Record instructions possibly made dead by deleting a store 107b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson SetVector<Instruction*> possiblyDead; 108b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 109b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool MadeChange = false; 110b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 111b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Do a top-down walk on the BB 112666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); 113666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson BBI != BBE; ++BBI) { 1146f46d65104ab08a75acb3d24056d19bdc2b054c3Owen Anderson // If we find a store or a free... 1156ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (!isa<StoreInst>(BBI) && !isa<FreeInst>(BBI)) 1166ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson continue; 1176ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson 1186ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson Value* pointer = 0; 1195dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson if (StoreInst* S = dyn_cast<StoreInst>(BBI)) { 1205dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson if (!S->isVolatile()) 1215dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson pointer = S->getPointerOperand(); 1225dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson else 1235dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson continue; 1245dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson } else 125c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson pointer = cast<FreeInst>(BBI)->getPointerOperand(); 1262655adb3b26b845193be9802f6f938d836c4a939Owen Anderson 1277ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson TranslatePointerBitCasts(pointer, true); 1286ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson StoreInst*& last = lastStore[pointer]; 1296ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson bool deletedStore = false; 130b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 1316ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // ... to a pointer that has been stored to before... 1326ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (last) { 1339528f11481e6840a10442733f1dc45c04b79d596Owen Anderson Instruction* dep = MD.getDependency(BBI); 134b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 1356ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // ... and no other memory dependencies are between them.... 1366ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson while (dep != MemoryDependenceAnalysis::None && 1376ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson dep != MemoryDependenceAnalysis::NonLocal && 1386ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson isa<StoreInst>(dep)) { 1397ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson if (dep != last || 140514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands TD.getTypeStoreSize(last->getOperand(0)->getType()) > 141514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands TD.getTypeStoreSize(BBI->getOperand(0)->getType())) { 1429528f11481e6840a10442733f1dc45c04b79d596Owen Anderson dep = MD.getDependency(BBI, dep); 1436ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson continue; 1446ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson } 145faac518ce0ae88a19f26b9aa9d34f6bf86ecb8c4Owen Anderson 1466ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // Remove it! 1476ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson MD.removeInstruction(last); 148b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 1496ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // DCE instructions only used to calculate that store 1506ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (Instruction* D = dyn_cast<Instruction>(last->getOperand(0))) 1516ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson possiblyDead.insert(D); 1526ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (Instruction* D = dyn_cast<Instruction>(last->getOperand(1))) 1536ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson possiblyDead.insert(D); 154b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 1556ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson last->eraseFromParent(); 1566ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson NumFastStores++; 1576ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson deletedStore = true; 1586ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson MadeChange = true; 1596ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson 1606ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson break; 161b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 1626ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson } 1636ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson 1646ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // Handle frees whose dependencies are non-trivial. 1656ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (FreeInst* F = dyn_cast<FreeInst>(BBI)) { 1666ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (!deletedStore) 1676ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson MadeChange |= handleFreeWithNonTrivialDependency(F, 1689528f11481e6840a10442733f1dc45c04b79d596Owen Anderson MD.getDependency(F), 1696ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson possiblyDead); 1706ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // No known stores after the free 1716ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson last = 0; 1726ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson } else { 1736ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // Update our most-recent-store map. 1746ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson last = cast<StoreInst>(BBI); 175b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 176b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 177b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 17843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // If this block ends in a return, unwind, unreachable, and eventually 17943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // tailcall, then all allocas are dead at its end. 18043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (BB.getTerminator()->getNumSuccessors() == 0) 18143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MadeChange |= handleEndBlock(BB, possiblyDead); 18243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 183b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Do a trivial DCE 184b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson while (!possiblyDead.empty()) { 185b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson Instruction *I = possiblyDead.back(); 186b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson possiblyDead.pop_back(); 187b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson DeleteDeadInstructionChains(I, possiblyDead); 188b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 189b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 190b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return MadeChange; 191b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 192b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 193a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson/// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose 194a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson/// dependency is a store to a field of that structure 195f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Andersonbool DSE::handleFreeWithNonTrivialDependency(FreeInst* F, Instruction* dep, 196666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson SetVector<Instruction*>& possiblyDead) { 197a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson TargetData &TD = getAnalysis<TargetData>(); 198a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 199a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 200a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 201dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson if (dep == MemoryDependenceAnalysis::None || 202dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson dep == MemoryDependenceAnalysis::NonLocal) 203dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson return false; 204dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson 205dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson StoreInst* dependency = dyn_cast<StoreInst>(dep); 206dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson if (!dependency) 207dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson return false; 2085dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson else if (dependency->isVolatile()) 2095dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson return false; 210dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson 211a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson Value* depPointer = dependency->getPointerOperand(); 212666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson const Type* depType = dependency->getOperand(0)->getType(); 213514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands unsigned depPointerSize = TD.getTypeStoreSize(depType); 2143e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson 215a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson // Check for aliasing 216a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AliasAnalysis::AliasResult A = AA.alias(F->getPointerOperand(), ~0UL, 217a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson depPointer, depPointerSize); 218a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 219a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson if (A == AliasAnalysis::MustAlias) { 220a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson // Remove it! 221a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson MD.removeInstruction(dependency); 222a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 223a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson // DCE instructions only used to calculate that store 224a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson if (Instruction* D = dyn_cast<Instruction>(dependency->getOperand(0))) 225a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson possiblyDead.insert(D); 2263e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson if (Instruction* D = dyn_cast<Instruction>(dependency->getOperand(1))) 2273e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson possiblyDead.insert(D); 228a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 229a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson dependency->eraseFromParent(); 230a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson NumFastStores++; 231a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson return true; 232a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson } 233a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 234a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson return false; 235a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson} 236a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 237666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson/// handleEndBlock - Remove dead stores to stack-allocated locations in the 238bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// function end block. Ex: 239bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// %A = alloca i32 240bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ... 241bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// store i32 1, i32* %A 242bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ret void 243666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Andersonbool DSE::handleEndBlock(BasicBlock& BB, 244666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson SetVector<Instruction*>& possiblyDead) { 24543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson TargetData &TD = getAnalysis<TargetData>(); 24643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 24743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 24843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 24943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool MadeChange = false; 25043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 25143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Pointers alloca'd in this function are dead in the end block 252bb3abf41a868357e95b639b34baebf802199e190Owen Anderson SmallPtrSet<AllocaInst*, 64> deadPointers; 25343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 25443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Find all of the alloca'd pointers in the entry block 25543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BasicBlock *Entry = BB.getParent()->begin(); 25643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) 25743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 25843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson deadPointers.insert(AI); 25943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 26043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Scan the basic block backwards 26143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ 26243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson --BBI; 26343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 26443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (deadPointers.empty()) 26543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson break; 26643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 26743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // If we find a store whose pointer is dead... 26843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (StoreInst* S = dyn_cast<StoreInst>(BBI)) { 2695dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson if (!S->isVolatile()) { 2705dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson Value* pointerOperand = S->getPointerOperand(); 2715dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson // See through pointer-to-pointer bitcasts 2725dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson TranslatePointerBitCasts(pointerOperand); 2733e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson 2746390ae0a4ad9a5419b7a3c6f899de82c568807e8Chris Lattner if (isa<AllocaInst>(pointerOperand) && 2756390ae0a4ad9a5419b7a3c6f899de82c568807e8Chris Lattner deadPointers.count(cast<AllocaInst>(pointerOperand))) { 2765dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson // Remove it! 2775dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson MD.removeInstruction(S); 27843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 2795dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson // DCE instructions only used to calculate that store 2805dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0))) 2815dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson possiblyDead.insert(D); 2825dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1))) 2835dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson possiblyDead.insert(D); 28443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 2855dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson BBI++; 2865dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson S->eraseFromParent(); 2875dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson NumFastStores++; 2885dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson MadeChange = true; 2895dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson } 29043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 291bb3abf41a868357e95b639b34baebf802199e190Owen Anderson 292bb3abf41a868357e95b639b34baebf802199e190Owen Anderson continue; 293bb3abf41a868357e95b639b34baebf802199e190Owen Anderson } 294bb3abf41a868357e95b639b34baebf802199e190Owen Anderson 295bb3abf41a868357e95b639b34baebf802199e190Owen Anderson Value* killPointer = 0; 29643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 29743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // If we encounter a use of the pointer, it is no longer considered dead 298bb3abf41a868357e95b639b34baebf802199e190Owen Anderson if (LoadInst* L = dyn_cast<LoadInst>(BBI)) { 29943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson killPointer = L->getPointerOperand(); 30043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } else if (VAArgInst* V = dyn_cast<VAArgInst>(BBI)) { 30143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson killPointer = V->getOperand(0); 30243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } else if (AllocaInst* A = dyn_cast<AllocaInst>(BBI)) { 30343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson deadPointers.erase(A); 30443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 30543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } else if (CallSite::get(BBI).getInstruction() != 0) { 306df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson // If this call does not access memory, it can't 307df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson // be undeadifying any of our pointers. 308df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson CallSite CS = CallSite::get(BBI); 309dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands if (AA.doesNotAccessMemory(CS)) 310df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson continue; 311df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson 312362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson unsigned modRef = 0; 313362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson unsigned other = 0; 314362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 31543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Remove any pointers made undead by the call from the dead set 31643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson std::vector<Instruction*> dead; 317bb3abf41a868357e95b639b34baebf802199e190Owen Anderson for (SmallPtrSet<AllocaInst*, 64>::iterator I = deadPointers.begin(), 31843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson E = deadPointers.end(); I != E; ++I) { 319362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // HACK: if we detect that our AA is imprecise, it's not 320362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // worth it to scan the rest of the deadPointers set. Just 321362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // assume that the AA will return ModRef for everything, and 322362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // go ahead and bail. 323362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson if (modRef >= 16 && other == 0) { 324362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson deadPointers.clear(); 325362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson return MadeChange; 326362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson } 327362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 32843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Get size information for the alloca 32943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson unsigned pointerSize = ~0UL; 33043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (ConstantInt* C = dyn_cast<ConstantInt>((*I)->getArraySize())) 331666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson pointerSize = C->getZExtValue() * \ 332514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands TD.getABITypeSize((*I)->getAllocatedType()); 33343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 33443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // See if the call site touches it 335df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, pointerSize); 336362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 337362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson if (A == AliasAnalysis::ModRef) 338362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson modRef++; 339362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson else 340362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson other++; 341362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 3423e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) 34343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson dead.push_back(*I); 34443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 34543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 34643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (std::vector<Instruction*>::iterator I = dead.begin(), E = dead.end(); 34743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson I != E; ++I) 3486390ae0a4ad9a5419b7a3c6f899de82c568807e8Chris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(*I)) 3496390ae0a4ad9a5419b7a3c6f899de82c568807e8Chris Lattner deadPointers.erase(AI); 35043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 35143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 35243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 35343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 35443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (!killPointer) 35543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 35643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 357362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson TranslatePointerBitCasts(killPointer); 358362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 35943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Deal with undead pointers 360bb3abf41a868357e95b639b34baebf802199e190Owen Anderson MadeChange |= RemoveUndeadPointers(killPointer, BBI, 36143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson deadPointers, possiblyDead); 36243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 36343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 36443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson return MadeChange; 36543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 36643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 367362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson/// RemoveUndeadPointers - check for uses of a pointer that make it 368362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson/// undead when scanning for dead stores to alloca's. 369bb3abf41a868357e95b639b34baebf802199e190Owen Andersonbool DSE::RemoveUndeadPointers(Value* killPointer, 37043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BasicBlock::iterator& BBI, 371bb3abf41a868357e95b639b34baebf802199e190Owen Anderson SmallPtrSet<AllocaInst*, 64>& deadPointers, 37243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson SetVector<Instruction*>& possiblyDead) { 37343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson TargetData &TD = getAnalysis<TargetData>(); 37443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 37543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 37643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 377362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // If the kill pointer can be easily reduced to an alloca, 378362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // don't bother doing extraneous AA queries 379362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson if (AllocaInst* A = dyn_cast<AllocaInst>(killPointer)) { 380362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson if (deadPointers.count(A)) 381362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson deadPointers.erase(A); 382362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson return false; 383838014ee5bda6c1b99ad8d74664aa5ea19fb501bOwen Anderson } else if (isa<GlobalValue>(killPointer)) { 384838014ee5bda6c1b99ad8d74664aa5ea19fb501bOwen Anderson // A global can't be in the dead pointer set 385838014ee5bda6c1b99ad8d74664aa5ea19fb501bOwen Anderson return false; 386362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson } 387362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 38843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool MadeChange = false; 38943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 39043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson std::vector<Instruction*> undead; 39143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 392bb3abf41a868357e95b639b34baebf802199e190Owen Anderson for (SmallPtrSet<AllocaInst*, 64>::iterator I = deadPointers.begin(), 39343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson E = deadPointers.end(); I != E; ++I) { 39443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Get size information for the alloca 39543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson unsigned pointerSize = ~0UL; 39643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (ConstantInt* C = dyn_cast<ConstantInt>((*I)->getArraySize())) 397666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson pointerSize = C->getZExtValue() * \ 398514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands TD.getABITypeSize((*I)->getAllocatedType()); 39943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 40043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // See if this pointer could alias it 401666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson AliasAnalysis::AliasResult A = AA.alias(*I, pointerSize, 402bb3abf41a868357e95b639b34baebf802199e190Owen Anderson killPointer, ~0UL); 40343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 40443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // If it must-alias and a store, we can delete it 40543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) { 40643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson StoreInst* S = cast<StoreInst>(BBI); 40743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 40843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Remove it! 40943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MD.removeInstruction(S); 41043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 41143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // DCE instructions only used to calculate that store 41243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0))) 41343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson possiblyDead.insert(D); 4143e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1))) 4153e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson possiblyDead.insert(D); 41643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 41743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BBI++; 41843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson S->eraseFromParent(); 41943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson NumFastStores++; 42043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MadeChange = true; 42143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 42243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 42343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 42443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Otherwise, it is undead 42543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } else if (A != AliasAnalysis::NoAlias) 42643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson undead.push_back(*I); 42743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 42843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 42943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (std::vector<Instruction*>::iterator I = undead.begin(), E = undead.end(); 43043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson I != E; ++I) 4316390ae0a4ad9a5419b7a3c6f899de82c568807e8Chris Lattner if (AllocaInst *AI = dyn_cast<AllocaInst>(*I)) 4326390ae0a4ad9a5419b7a3c6f899de82c568807e8Chris Lattner deadPointers.erase(AI); 43343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 43443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson return MadeChange; 43543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 43643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 437bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// DeleteDeadInstructionChains - takes an instruction and a setvector of 438bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// dead instructions. If I is dead, it is erased, and its operands are 439bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// checked for deadness. If they are dead, they are added to the dead 440bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// setvector. 441f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Andersonvoid DSE::DeleteDeadInstructionChains(Instruction *I, 442b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson SetVector<Instruction*> &DeadInsts) { 443b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Instruction must be dead. 444b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson if (!I->use_empty() || !isInstructionTriviallyDead(I)) return; 445b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 446b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Let the memory dependence know 447b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson getAnalysis<MemoryDependenceAnalysis>().removeInstruction(I); 448b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 449b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // See if this made any operands dead. We do it this way in case the 450b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // instruction uses the same operand twice. We don't want to delete a 451b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // value then reference it. 452b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 453bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson if (I->getOperand(i)->hasOneUse()) 454bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson if (Instruction* Op = dyn_cast<Instruction>(I->getOperand(i))) 455bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson DeadInsts.insert(Op); // Attempt to nuke it later. 456bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson 457b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson I->setOperand(i, 0); // Drop from the operand list. 458b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 459b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 460b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson I->eraseFromParent(); 461b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson ++NumFastOther; 462b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 463