DeadStoreElimination.cpp revision a72acf938902ea8ae2776cad7327257e88a63a54
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/SetVector.h" 26b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/ADT/SmallPtrSet.h" 27b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/ADT/Statistic.h" 28a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson#include "llvm/Analysis/AliasAnalysis.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 41f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Anderson DSE() : FunctionPass((intptr_t)&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); 51666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson bool handleFreeWithNonTrivialDependency(FreeInst* F, 52666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson Instruction* dependency, 53666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson SetVector<Instruction*>& possiblyDead); 5443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool handleEndBlock(BasicBlock& BB, SetVector<Instruction*>& possiblyDead); 55c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson bool RemoveUndeadPointers(Value* pointer, uint64_t killPointerSize, 5643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BasicBlock::iterator& BBI, 57a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson SmallPtrSet<Value*, 64>& deadPointers, 5843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson SetVector<Instruction*>& possiblyDead); 59b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson void DeleteDeadInstructionChains(Instruction *I, 60b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson SetVector<Instruction*> &DeadInsts); 616ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson 62c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson /// Find the base pointer that a pointer came from 63c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson /// Because this is used to find pointers that originate 64c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson /// from allocas, it is safe to ignore GEP indices, since 65c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson /// either the store will be in the alloca, and thus dead, 66c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson /// or beyond the end of the alloca, and thus undefined. 677ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson void TranslatePointerBitCasts(Value*& v, bool zeroGepsOnly = false) { 68666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson assert(isa<PointerType>(v->getType()) && 69666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson "Translating a non-pointer type?"); 706ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson while (true) { 71ce17b1c1f8761f5fabb4b0531b7127254cdc89deOwen Anderson if (BitCastInst* C = dyn_cast<BitCastInst>(v)) 72ce17b1c1f8761f5fabb4b0531b7127254cdc89deOwen Anderson v = C->getOperand(0); 73ce17b1c1f8761f5fabb4b0531b7127254cdc89deOwen Anderson else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(v)) 747ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson if (!zeroGepsOnly || G->hasAllZeroIndices()) { 757ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson v = G->getOperand(0); 767ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson } else { 777ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson break; 787ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson } 796ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson else 806ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson break; 816ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson } 823e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson } 83b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 84b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // getAnalysisUsage - We require post dominance frontiers (aka Control 85b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Dependence Graph) 86b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const { 87b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.setPreservesCFG(); 88a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addRequired<TargetData>(); 89a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addRequired<AliasAnalysis>(); 90b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addRequired<MemoryDependenceAnalysis>(); 91a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addPreserved<AliasAnalysis>(); 92b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addPreserved<MemoryDependenceAnalysis>(); 93b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 94b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson }; 95b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 96b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 97844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar DSE::ID = 0; 98844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<DSE> X("dse", "Dead Store Elimination"); 99844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 100f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen AndersonFunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } 101b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 102f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Andersonbool DSE::runOnBasicBlock(BasicBlock &BB) { 103b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1047ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson TargetData &TD = getAnalysis<TargetData>(); 1057ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson 106bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson // Record the last-seen store to this pointer 107b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson DenseMap<Value*, StoreInst*> lastStore; 108bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson // Record instructions possibly made dead by deleting a store 109b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson SetVector<Instruction*> possiblyDead; 110b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 111b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool MadeChange = false; 112b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 113b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Do a top-down walk on the BB 114666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); 115666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson BBI != BBE; ++BBI) { 1166f46d65104ab08a75acb3d24056d19bdc2b054c3Owen Anderson // If we find a store or a free... 1176ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (!isa<StoreInst>(BBI) && !isa<FreeInst>(BBI)) 1186ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson continue; 1196ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson 1206ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson Value* pointer = 0; 1215dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson if (StoreInst* S = dyn_cast<StoreInst>(BBI)) { 1225dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson if (!S->isVolatile()) 1235dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson pointer = S->getPointerOperand(); 1245dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson else 1255dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson continue; 1265dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson } else 127c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson pointer = cast<FreeInst>(BBI)->getPointerOperand(); 1282655adb3b26b845193be9802f6f938d836c4a939Owen Anderson 1297ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson TranslatePointerBitCasts(pointer, true); 1306ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson StoreInst*& last = lastStore[pointer]; 1316ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson bool deletedStore = false; 132b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 1336ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // ... to a pointer that has been stored to before... 1346ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (last) { 1359528f11481e6840a10442733f1dc45c04b79d596Owen Anderson Instruction* dep = MD.getDependency(BBI); 136b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 1376ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // ... and no other memory dependencies are between them.... 1386ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson while (dep != MemoryDependenceAnalysis::None && 1396ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson dep != MemoryDependenceAnalysis::NonLocal && 1406ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson isa<StoreInst>(dep)) { 1417ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson if (dep != last || 142514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands TD.getTypeStoreSize(last->getOperand(0)->getType()) > 143514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands TD.getTypeStoreSize(BBI->getOperand(0)->getType())) { 1449528f11481e6840a10442733f1dc45c04b79d596Owen Anderson dep = MD.getDependency(BBI, dep); 1456ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson continue; 1466ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson } 147faac518ce0ae88a19f26b9aa9d34f6bf86ecb8c4Owen Anderson 1486ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // Remove it! 1496ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson MD.removeInstruction(last); 150b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 1516ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // DCE instructions only used to calculate that store 1526ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (Instruction* D = dyn_cast<Instruction>(last->getOperand(0))) 1536ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson possiblyDead.insert(D); 1546ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (Instruction* D = dyn_cast<Instruction>(last->getOperand(1))) 1556ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson possiblyDead.insert(D); 156772601a8850808a66270372164941e373074493dOwen Anderson 1576ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson last->eraseFromParent(); 1586ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson NumFastStores++; 1596ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson deletedStore = true; 1606ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson MadeChange = true; 1616ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson 1626ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson break; 163b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 1646ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson } 1656ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson 1666ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // Handle frees whose dependencies are non-trivial. 1676ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (FreeInst* F = dyn_cast<FreeInst>(BBI)) { 1686ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (!deletedStore) 1696ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson MadeChange |= handleFreeWithNonTrivialDependency(F, 1709528f11481e6840a10442733f1dc45c04b79d596Owen Anderson MD.getDependency(F), 1716ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson possiblyDead); 1726ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // No known stores after the free 1736ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson last = 0; 1746ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson } else { 1756ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // Update our most-recent-store map. 1766ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson last = cast<StoreInst>(BBI); 177b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 178b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 179b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 18043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // If this block ends in a return, unwind, unreachable, and eventually 18143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // tailcall, then all allocas are dead at its end. 18243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (BB.getTerminator()->getNumSuccessors() == 0) 18343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MadeChange |= handleEndBlock(BB, possiblyDead); 18443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 185b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Do a trivial DCE 186b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson while (!possiblyDead.empty()) { 187b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson Instruction *I = possiblyDead.back(); 188b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson possiblyDead.pop_back(); 189b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson DeleteDeadInstructionChains(I, possiblyDead); 190b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 191b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 192b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return MadeChange; 193b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 194b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 195a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson/// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose 196a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson/// dependency is a store to a field of that structure 197f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Andersonbool DSE::handleFreeWithNonTrivialDependency(FreeInst* F, Instruction* dep, 198666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson SetVector<Instruction*>& possiblyDead) { 199a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson TargetData &TD = getAnalysis<TargetData>(); 200a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 201a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 202a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 203dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson if (dep == MemoryDependenceAnalysis::None || 204dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson dep == MemoryDependenceAnalysis::NonLocal) 205dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson return false; 206dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson 207dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson StoreInst* dependency = dyn_cast<StoreInst>(dep); 208dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson if (!dependency) 209dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson return false; 2105dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson else if (dependency->isVolatile()) 2115dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson return false; 212dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson 213a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson Value* depPointer = dependency->getPointerOperand(); 214666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson const Type* depType = dependency->getOperand(0)->getType(); 215514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands unsigned depPointerSize = TD.getTypeStoreSize(depType); 21602ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 217a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson // Check for aliasing 21802ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands AliasAnalysis::AliasResult A = AA.alias(F->getPointerOperand(), ~0U, 219a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson depPointer, depPointerSize); 22002ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 221a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson if (A == AliasAnalysis::MustAlias) { 222a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson // Remove it! 223a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson MD.removeInstruction(dependency); 224a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 225a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson // DCE instructions only used to calculate that store 226a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson if (Instruction* D = dyn_cast<Instruction>(dependency->getOperand(0))) 227a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson possiblyDead.insert(D); 2283e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson if (Instruction* D = dyn_cast<Instruction>(dependency->getOperand(1))) 2293e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson possiblyDead.insert(D); 230a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 231a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson dependency->eraseFromParent(); 232a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson NumFastStores++; 233a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson return true; 234a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson } 235a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 236a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson return false; 237a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson} 238a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 239666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson/// handleEndBlock - Remove dead stores to stack-allocated locations in the 240bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// function end block. Ex: 241bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// %A = alloca i32 242bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ... 243bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// store i32 1, i32* %A 244bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ret void 245666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Andersonbool DSE::handleEndBlock(BasicBlock& BB, 246666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson SetVector<Instruction*>& possiblyDead) { 24743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson TargetData &TD = getAnalysis<TargetData>(); 24843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 24943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 25043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 25143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool MadeChange = false; 25243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 25343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Pointers alloca'd in this function are dead in the end block 254a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson SmallPtrSet<Value*, 64> deadPointers; 25543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 25643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Find all of the alloca'd pointers in the entry block 25743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BasicBlock *Entry = BB.getParent()->begin(); 25843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) 25943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 26043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson deadPointers.insert(AI); 261a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (Function::arg_iterator AI = BB.getParent()->arg_begin(), 262a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson AE = BB.getParent()->arg_end(); AI != AE; ++AI) 263a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (AI->hasByValAttr()) 264a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson deadPointers.insert(AI); 26543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 26643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Scan the basic block backwards 26743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ 26843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson --BBI; 26943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 27043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // If we find a store whose pointer is dead... 27143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (StoreInst* S = dyn_cast<StoreInst>(BBI)) { 2725dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson if (!S->isVolatile()) { 2735dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson Value* pointerOperand = S->getPointerOperand(); 2745dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson // See through pointer-to-pointer bitcasts 2755dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson TranslatePointerBitCasts(pointerOperand); 2763e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson 277e3c36f67580f0963abdf696a26690facb0791ce0Owen Anderson // Alloca'd pointers or byval arguments (which are functionally like 278e3c36f67580f0963abdf696a26690facb0791ce0Owen Anderson // alloca's) are valid candidates for removal. 279a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (deadPointers.count(pointerOperand)) { 2805dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson // Remove it! 2815dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson MD.removeInstruction(S); 28243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 2835dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson // DCE instructions only used to calculate that store 2845dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0))) 2855dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson possiblyDead.insert(D); 2865dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1))) 2875dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson possiblyDead.insert(D); 28843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 2895dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson BBI++; 2905dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson S->eraseFromParent(); 2915dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson NumFastStores++; 2925dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson MadeChange = true; 2935dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson } 29443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 295bb3abf41a868357e95b639b34baebf802199e190Owen Anderson 296bb3abf41a868357e95b639b34baebf802199e190Owen Anderson continue; 297a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson 298a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson // We can also remove memcpy's to local variables at the end of a function 299a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } else if (MemCpyInst* M = dyn_cast<MemCpyInst>(BBI)) { 300a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson Value* dest = M->getDest(); 301a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson TranslatePointerBitCasts(dest); 302a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson 303a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (deadPointers.count(dest)) { 304a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson MD.removeInstruction(M); 305a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson 306a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson // DCE instructions only used to calculate that memcpy 307772601a8850808a66270372164941e373074493dOwen Anderson if (Instruction* D = dyn_cast<Instruction>(M->getRawSource())) 308a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson possiblyDead.insert(D); 309a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (Instruction* D = dyn_cast<Instruction>(M->getLength())) 310a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson possiblyDead.insert(D); 311a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (Instruction* D = dyn_cast<Instruction>(M->getRawDest())) 312a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson possiblyDead.insert(D); 313a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson 314a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson BBI++; 315a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson M->eraseFromParent(); 316a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson NumFastOther++; 317a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson MadeChange = true; 318a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson 319a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson continue; 320a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } 321a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson 322a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson // Because a memcpy is also a load, we can't skip it if we didn't remove it 323bb3abf41a868357e95b639b34baebf802199e190Owen Anderson } 324bb3abf41a868357e95b639b34baebf802199e190Owen Anderson 325bb3abf41a868357e95b639b34baebf802199e190Owen Anderson Value* killPointer = 0; 326c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson uint64_t killPointerSize = ~0UL; 32743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 32843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // If we encounter a use of the pointer, it is no longer considered dead 329bb3abf41a868357e95b639b34baebf802199e190Owen Anderson if (LoadInst* L = dyn_cast<LoadInst>(BBI)) { 330a72acf938902ea8ae2776cad7327257e88a63a54Nate Begeman // However, if this load is unused and not volatile, we can go ahead and 331a72acf938902ea8ae2776cad7327257e88a63a54Nate Begeman // remove it, and not have to worry about it making our pointer undead! 33200acf97feb2cba053a07505dfad9116ad09aae7aDan Gohman if (L->use_empty() && !L->isVolatile()) { 333772601a8850808a66270372164941e373074493dOwen Anderson MD.removeInstruction(L); 334772601a8850808a66270372164941e373074493dOwen Anderson 335772601a8850808a66270372164941e373074493dOwen Anderson // DCE instructions only used to calculate that load 336772601a8850808a66270372164941e373074493dOwen Anderson if (Instruction* D = dyn_cast<Instruction>(L->getPointerOperand())) 337772601a8850808a66270372164941e373074493dOwen Anderson possiblyDead.insert(D); 338772601a8850808a66270372164941e373074493dOwen Anderson 339772601a8850808a66270372164941e373074493dOwen Anderson BBI++; 340772601a8850808a66270372164941e373074493dOwen Anderson L->eraseFromParent(); 341772601a8850808a66270372164941e373074493dOwen Anderson NumFastOther++; 342772601a8850808a66270372164941e373074493dOwen Anderson MadeChange = true; 343772601a8850808a66270372164941e373074493dOwen Anderson possiblyDead.remove(L); 344772601a8850808a66270372164941e373074493dOwen Anderson 345772601a8850808a66270372164941e373074493dOwen Anderson continue; 346772601a8850808a66270372164941e373074493dOwen Anderson } 347772601a8850808a66270372164941e373074493dOwen Anderson 34843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson killPointer = L->getPointerOperand(); 34943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } else if (VAArgInst* V = dyn_cast<VAArgInst>(BBI)) { 35043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson killPointer = V->getOperand(0); 351c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson } else if (isa<MemCpyInst>(BBI) && 352c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson isa<ConstantInt>(cast<MemCpyInst>(BBI)->getLength())) { 353c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson killPointer = cast<MemCpyInst>(BBI)->getSource(); 354c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson killPointerSize = cast<ConstantInt>( 355c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson cast<MemCpyInst>(BBI)->getLength())->getZExtValue(); 35643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } else if (AllocaInst* A = dyn_cast<AllocaInst>(BBI)) { 35743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson deadPointers.erase(A); 358772601a8850808a66270372164941e373074493dOwen Anderson 359772601a8850808a66270372164941e373074493dOwen Anderson // Dead alloca's can be DCE'd when we reach them 360b4b04172206810623845a7f11dd3a65b0b3b10d5Nick Lewycky if (A->use_empty()) { 361772601a8850808a66270372164941e373074493dOwen Anderson MD.removeInstruction(A); 362772601a8850808a66270372164941e373074493dOwen Anderson 363772601a8850808a66270372164941e373074493dOwen Anderson // DCE instructions only used to calculate that load 364772601a8850808a66270372164941e373074493dOwen Anderson if (Instruction* D = dyn_cast<Instruction>(A->getArraySize())) 365772601a8850808a66270372164941e373074493dOwen Anderson possiblyDead.insert(D); 366772601a8850808a66270372164941e373074493dOwen Anderson 367772601a8850808a66270372164941e373074493dOwen Anderson BBI++; 368772601a8850808a66270372164941e373074493dOwen Anderson A->eraseFromParent(); 369772601a8850808a66270372164941e373074493dOwen Anderson NumFastOther++; 370772601a8850808a66270372164941e373074493dOwen Anderson MadeChange = true; 371772601a8850808a66270372164941e373074493dOwen Anderson possiblyDead.remove(A); 372772601a8850808a66270372164941e373074493dOwen Anderson } 373772601a8850808a66270372164941e373074493dOwen Anderson 37443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 37543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } else if (CallSite::get(BBI).getInstruction() != 0) { 376df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson // If this call does not access memory, it can't 377df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson // be undeadifying any of our pointers. 378df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson CallSite CS = CallSite::get(BBI); 379dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands if (AA.doesNotAccessMemory(CS)) 380df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson continue; 381df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson 382362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson unsigned modRef = 0; 383362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson unsigned other = 0; 384362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 38543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Remove any pointers made undead by the call from the dead set 386a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson std::vector<Value*> dead; 387a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 38843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson E = deadPointers.end(); I != E; ++I) { 389362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // HACK: if we detect that our AA is imprecise, it's not 390362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // worth it to scan the rest of the deadPointers set. Just 391362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // assume that the AA will return ModRef for everything, and 392362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // go ahead and bail. 393362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson if (modRef >= 16 && other == 0) { 394362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson deadPointers.clear(); 395362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson return MadeChange; 396362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson } 39702ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 39843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Get size information for the alloca 39902ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands unsigned pointerSize = ~0U; 400a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) { 401a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize())) 402a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson pointerSize = C->getZExtValue() * \ 403a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson TD.getABITypeSize(A->getAllocatedType()); 404a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } else { 405a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson const PointerType* PT = cast<PointerType>( 406a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson cast<Argument>(*I)->getType()); 407a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson pointerSize = TD.getABITypeSize(PT->getElementType()); 408a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } 40902ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 41043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // See if the call site touches it 411df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, pointerSize); 412362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 413362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson if (A == AliasAnalysis::ModRef) 414362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson modRef++; 415362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson else 416362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson other++; 417362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 4183e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) 41943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson dead.push_back(*I); 42043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 42143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 422a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end(); 42343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson I != E; ++I) 424a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson deadPointers.erase(*I); 42543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 42643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 427772601a8850808a66270372164941e373074493dOwen Anderson } else { 428772601a8850808a66270372164941e373074493dOwen Anderson // For any non-memory-affecting non-terminators, DCE them as we reach them 429772601a8850808a66270372164941e373074493dOwen Anderson Instruction *CI = BBI; 430c7444498eebb654ea089df8ec52dba5f84f9a108Nick Lewycky if (!CI->isTerminator() && CI->use_empty() && !isa<FreeInst>(CI)) { 431772601a8850808a66270372164941e373074493dOwen Anderson 432772601a8850808a66270372164941e373074493dOwen Anderson // DCE instructions only used to calculate that load 433772601a8850808a66270372164941e373074493dOwen Anderson for (Instruction::op_iterator OI = CI->op_begin(), OE = CI->op_end(); 434772601a8850808a66270372164941e373074493dOwen Anderson OI != OE; ++OI) 435772601a8850808a66270372164941e373074493dOwen Anderson if (Instruction* D = dyn_cast<Instruction>(OI)) 436772601a8850808a66270372164941e373074493dOwen Anderson possiblyDead.insert(D); 437772601a8850808a66270372164941e373074493dOwen Anderson 438772601a8850808a66270372164941e373074493dOwen Anderson BBI++; 439772601a8850808a66270372164941e373074493dOwen Anderson CI->eraseFromParent(); 440772601a8850808a66270372164941e373074493dOwen Anderson NumFastOther++; 441772601a8850808a66270372164941e373074493dOwen Anderson MadeChange = true; 442772601a8850808a66270372164941e373074493dOwen Anderson possiblyDead.remove(CI); 443772601a8850808a66270372164941e373074493dOwen Anderson 444772601a8850808a66270372164941e373074493dOwen Anderson continue; 445772601a8850808a66270372164941e373074493dOwen Anderson } 44643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 44743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 44843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (!killPointer) 44943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 45043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 451362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson TranslatePointerBitCasts(killPointer); 452362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 45343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Deal with undead pointers 454c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson MadeChange |= RemoveUndeadPointers(killPointer, killPointerSize, BBI, 45543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson deadPointers, possiblyDead); 45643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 45743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 45843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson return MadeChange; 45943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 46043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 461362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson/// RemoveUndeadPointers - check for uses of a pointer that make it 462362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson/// undead when scanning for dead stores to alloca's. 463c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Andersonbool DSE::RemoveUndeadPointers(Value* killPointer, uint64_t killPointerSize, 46443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BasicBlock::iterator& BBI, 465a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson SmallPtrSet<Value*, 64>& deadPointers, 46643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson SetVector<Instruction*>& possiblyDead) { 46743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson TargetData &TD = getAnalysis<TargetData>(); 46843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 46943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 47043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 471362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // If the kill pointer can be easily reduced to an alloca, 472362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // don't bother doing extraneous AA queries 473a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (deadPointers.count(killPointer)) { 474a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson deadPointers.erase(killPointer); 475362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson return false; 476838014ee5bda6c1b99ad8d74664aa5ea19fb501bOwen Anderson } else if (isa<GlobalValue>(killPointer)) { 477838014ee5bda6c1b99ad8d74664aa5ea19fb501bOwen Anderson // A global can't be in the dead pointer set 478838014ee5bda6c1b99ad8d74664aa5ea19fb501bOwen Anderson return false; 479362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson } 480362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 48143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool MadeChange = false; 48243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 483a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson std::vector<Value*> undead; 48443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 485a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 48643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson E = deadPointers.end(); I != E; ++I) { 48743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Get size information for the alloca 48802ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands unsigned pointerSize = ~0U; 489a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) { 490a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize())) 491a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson pointerSize = C->getZExtValue() * \ 492a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson TD.getABITypeSize(A->getAllocatedType()); 493a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } else { 494a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson const PointerType* PT = cast<PointerType>( 495a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson cast<Argument>(*I)->getType()); 496a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson pointerSize = TD.getABITypeSize(PT->getElementType()); 497a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } 49802ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 49943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // See if this pointer could alias it 500666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson AliasAnalysis::AliasResult A = AA.alias(*I, pointerSize, 501c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson killPointer, killPointerSize); 50243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 50343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // If it must-alias and a store, we can delete it 50443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) { 50543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson StoreInst* S = cast<StoreInst>(BBI); 50643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 50743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Remove it! 50843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MD.removeInstruction(S); 50943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 51043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // DCE instructions only used to calculate that store 51143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0))) 51243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson possiblyDead.insert(D); 5133e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1))) 5143e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson possiblyDead.insert(D); 51543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 51643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BBI++; 51743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson S->eraseFromParent(); 51843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson NumFastStores++; 51943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MadeChange = true; 52043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 52143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 52243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 52343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Otherwise, it is undead 52443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } else if (A != AliasAnalysis::NoAlias) 52543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson undead.push_back(*I); 52643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 52743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 528a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (std::vector<Value*>::iterator I = undead.begin(), E = undead.end(); 52943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson I != E; ++I) 530a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson deadPointers.erase(*I); 53143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 53243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson return MadeChange; 53343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 53443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 535bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// DeleteDeadInstructionChains - takes an instruction and a setvector of 536bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// dead instructions. If I is dead, it is erased, and its operands are 537bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// checked for deadness. If they are dead, they are added to the dead 538bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// setvector. 539f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Andersonvoid DSE::DeleteDeadInstructionChains(Instruction *I, 540b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson SetVector<Instruction*> &DeadInsts) { 541b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Instruction must be dead. 542b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson if (!I->use_empty() || !isInstructionTriviallyDead(I)) return; 543b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 544b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Let the memory dependence know 545b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson getAnalysis<MemoryDependenceAnalysis>().removeInstruction(I); 546b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 547b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // See if this made any operands dead. We do it this way in case the 548b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // instruction uses the same operand twice. We don't want to delete a 549b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // value then reference it. 550b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 551bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson if (I->getOperand(i)->hasOneUse()) 552bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson if (Instruction* Op = dyn_cast<Instruction>(I->getOperand(i))) 553bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson DeadInsts.insert(Op); // Attempt to nuke it later. 554bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson 555b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson I->setOperand(i, 0); // Drop from the operand list. 556b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 557b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 558b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson I->eraseFromParent(); 559b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson ++NumFastOther; 560b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 561