DeadStoreElimination.cpp revision 8aa895b19a64796a4c1f7cd0cb0750ad34263ea0
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" 298aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson#include "llvm/Analysis/Dominators.h" 30b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Analysis/MemoryDependenceAnalysis.h" 31a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson#include "llvm/Target/TargetData.h" 32b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Transforms/Utils/Local.h" 33b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Support/Compiler.h" 34b77c457cc87aeeb166995aed793a516e9e431703Owen Andersonusing namespace llvm; 35b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 36b77c457cc87aeeb166995aed793a516e9e431703Owen AndersonSTATISTIC(NumFastStores, "Number of stores deleted"); 37b77c457cc87aeeb166995aed793a516e9e431703Owen AndersonSTATISTIC(NumFastOther , "Number of other instrs removed"); 38b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 39b77c457cc87aeeb166995aed793a516e9e431703Owen Andersonnamespace { 40f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Anderson struct VISIBILITY_HIDDEN DSE : public FunctionPass { 41b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson static char ID; // Pass identification, replacement for typeid 42f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Anderson DSE() : FunctionPass((intptr_t)&ID) {} 43b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 44b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson virtual bool runOnFunction(Function &F) { 45b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool Changed = false; 46b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 47b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson Changed |= runOnBasicBlock(*I); 48b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return Changed; 49b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 50b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 51b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool runOnBasicBlock(BasicBlock &BB); 52666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson bool handleFreeWithNonTrivialDependency(FreeInst* F, 53666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson Instruction* dependency, 54666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson SetVector<Instruction*>& possiblyDead); 5543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool handleEndBlock(BasicBlock& BB, SetVector<Instruction*>& possiblyDead); 56c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson bool RemoveUndeadPointers(Value* pointer, uint64_t killPointerSize, 5743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BasicBlock::iterator& BBI, 58a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson SmallPtrSet<Value*, 64>& deadPointers, 5943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson SetVector<Instruction*>& possiblyDead); 60b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson void DeleteDeadInstructionChains(Instruction *I, 61b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson SetVector<Instruction*> &DeadInsts); 626ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson 63c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson /// Find the base pointer that a pointer came from 64c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson /// Because this is used to find pointers that originate 65c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson /// from allocas, it is safe to ignore GEP indices, since 66c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson /// either the store will be in the alloca, and thus dead, 67c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson /// or beyond the end of the alloca, and thus undefined. 687ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson void TranslatePointerBitCasts(Value*& v, bool zeroGepsOnly = false) { 69666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson assert(isa<PointerType>(v->getType()) && 70666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson "Translating a non-pointer type?"); 716ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson while (true) { 72ce17b1c1f8761f5fabb4b0531b7127254cdc89deOwen Anderson if (BitCastInst* C = dyn_cast<BitCastInst>(v)) 73ce17b1c1f8761f5fabb4b0531b7127254cdc89deOwen Anderson v = C->getOperand(0); 74ce17b1c1f8761f5fabb4b0531b7127254cdc89deOwen Anderson else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(v)) 757ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson if (!zeroGepsOnly || G->hasAllZeroIndices()) { 767ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson v = G->getOperand(0); 777ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson } else { 787ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson break; 797ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson } 806ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson else 816ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson break; 826ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson } 833e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson } 84b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 85b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // getAnalysisUsage - We require post dominance frontiers (aka Control 86b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Dependence Graph) 87b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const { 88b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.setPreservesCFG(); 898aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson AU.addRequired<DominatorTree>(); 90a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addRequired<TargetData>(); 91a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addRequired<AliasAnalysis>(); 92b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addRequired<MemoryDependenceAnalysis>(); 938aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson AU.addPreserved<DominatorTree>(); 94a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addPreserved<AliasAnalysis>(); 95b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addPreserved<MemoryDependenceAnalysis>(); 96b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 97b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson }; 98b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 99b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 100844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar DSE::ID = 0; 101844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<DSE> X("dse", "Dead Store Elimination"); 102844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 103f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen AndersonFunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } 104b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 105f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Andersonbool DSE::runOnBasicBlock(BasicBlock &BB) { 106b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 1077ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson TargetData &TD = getAnalysis<TargetData>(); 1087ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson 109bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson // Record the last-seen store to this pointer 110b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson DenseMap<Value*, StoreInst*> lastStore; 111bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson // Record instructions possibly made dead by deleting a store 112b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson SetVector<Instruction*> possiblyDead; 113b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 114b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool MadeChange = false; 115b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 116b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Do a top-down walk on the BB 117666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); 118666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson BBI != BBE; ++BBI) { 1196f46d65104ab08a75acb3d24056d19bdc2b054c3Owen Anderson // If we find a store or a free... 1206ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (!isa<StoreInst>(BBI) && !isa<FreeInst>(BBI)) 1216ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson continue; 1226ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson 1236ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson Value* pointer = 0; 1245dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson if (StoreInst* S = dyn_cast<StoreInst>(BBI)) { 1255dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson if (!S->isVolatile()) 1265dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson pointer = S->getPointerOperand(); 1275dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson else 1285dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson continue; 1295dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson } else 130c182f17aed0b9d4fa8a87bdbea56fcd3a3e121dcOwen Anderson pointer = cast<FreeInst>(BBI)->getPointerOperand(); 1312655adb3b26b845193be9802f6f938d836c4a939Owen Anderson 1327ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson TranslatePointerBitCasts(pointer, true); 1336ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson StoreInst*& last = lastStore[pointer]; 1346ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson bool deletedStore = false; 135b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 1366ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // ... to a pointer that has been stored to before... 1376ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (last) { 1389528f11481e6840a10442733f1dc45c04b79d596Owen Anderson Instruction* dep = MD.getDependency(BBI); 139b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 1406ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // ... and no other memory dependencies are between them.... 1416ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson while (dep != MemoryDependenceAnalysis::None && 1426ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson dep != MemoryDependenceAnalysis::NonLocal && 1436ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson isa<StoreInst>(dep)) { 1447ebba512c3417f0eb52ab68b39831e3a85105d66Owen Anderson if (dep != last || 145514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands TD.getTypeStoreSize(last->getOperand(0)->getType()) > 146514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands TD.getTypeStoreSize(BBI->getOperand(0)->getType())) { 1479528f11481e6840a10442733f1dc45c04b79d596Owen Anderson dep = MD.getDependency(BBI, dep); 1486ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson continue; 1496ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson } 150faac518ce0ae88a19f26b9aa9d34f6bf86ecb8c4Owen Anderson 1516ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // Remove it! 1526ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson MD.removeInstruction(last); 153b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 1546ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // DCE instructions only used to calculate that store 1556ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (Instruction* D = dyn_cast<Instruction>(last->getOperand(0))) 1566ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson possiblyDead.insert(D); 1576ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (Instruction* D = dyn_cast<Instruction>(last->getOperand(1))) 1586ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson possiblyDead.insert(D); 159772601a8850808a66270372164941e373074493dOwen Anderson 1606ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson last->eraseFromParent(); 1616ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson NumFastStores++; 1626ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson deletedStore = true; 1636ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson MadeChange = true; 1646ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson 1656ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson break; 166b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 1676ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson } 1686ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson 1696ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // Handle frees whose dependencies are non-trivial. 1706ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (FreeInst* F = dyn_cast<FreeInst>(BBI)) { 1716ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson if (!deletedStore) 1726ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson MadeChange |= handleFreeWithNonTrivialDependency(F, 1739528f11481e6840a10442733f1dc45c04b79d596Owen Anderson MD.getDependency(F), 1746ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson possiblyDead); 1756ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson // No known stores after the free 1766ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson last = 0; 1776ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson } else { 1788aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson StoreInst* S = cast<StoreInst>(BBI); 1798aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson 1808aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson // If we're storing the same value back to a pointer that we just 1818aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson // loaded from, then the store can be removed; 1828aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson if (LoadInst* L = dyn_cast<LoadInst>(S->getOperand(0))) { 1838aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson Instruction* dep = MD.getDependency(S); 1848aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson DominatorTree& DT = getAnalysis<DominatorTree>(); 1858aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson 1868aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson if (S->getParent() == L->getParent() && 1878aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson S->getPointerOperand() == L->getPointerOperand() && 1888aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson ( dep == MemoryDependenceAnalysis::None || 1898aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson dep == MemoryDependenceAnalysis::NonLocal || 1908aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson DT.dominates(dep, L))) { 1918aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0))) 1928aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson possiblyDead.insert(D); 1938aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1))) 1948aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson possiblyDead.insert(D); 1958aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson 1968aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson // Avoid iterator invalidation. 1978aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson BBI--; 1988aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson 1998aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson MD.removeInstruction(S); 2008aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson S->eraseFromParent(); 2018aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson NumFastStores++; 2028aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson MadeChange = true; 2038aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson } else 2048aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson // Update our most-recent-store map. 2058aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson last = S; 2068aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson } else 2078aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson // Update our most-recent-store map. 2088aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson last = S; 209b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 210b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 211b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 21243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // If this block ends in a return, unwind, unreachable, and eventually 21343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // tailcall, then all allocas are dead at its end. 21443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (BB.getTerminator()->getNumSuccessors() == 0) 21543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MadeChange |= handleEndBlock(BB, possiblyDead); 21643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 217b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Do a trivial DCE 218b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson while (!possiblyDead.empty()) { 219b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson Instruction *I = possiblyDead.back(); 220b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson possiblyDead.pop_back(); 221b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson DeleteDeadInstructionChains(I, possiblyDead); 222b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 223b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 224b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return MadeChange; 225b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 226b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 227a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson/// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose 228a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson/// dependency is a store to a field of that structure 229f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Andersonbool DSE::handleFreeWithNonTrivialDependency(FreeInst* F, Instruction* dep, 230666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson SetVector<Instruction*>& possiblyDead) { 231a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson TargetData &TD = getAnalysis<TargetData>(); 232a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 233a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 234a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 235dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson if (dep == MemoryDependenceAnalysis::None || 236dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson dep == MemoryDependenceAnalysis::NonLocal) 237dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson return false; 238dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson 239dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson StoreInst* dependency = dyn_cast<StoreInst>(dep); 240dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson if (!dependency) 241dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson return false; 2425dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson else if (dependency->isVolatile()) 2435dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson return false; 244dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson 245a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson Value* depPointer = dependency->getPointerOperand(); 246666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson const Type* depType = dependency->getOperand(0)->getType(); 247514ab348fddcdffa8367685dc608b2f8d5de986dDuncan Sands unsigned depPointerSize = TD.getTypeStoreSize(depType); 24802ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 249a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson // Check for aliasing 25002ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands AliasAnalysis::AliasResult A = AA.alias(F->getPointerOperand(), ~0U, 251a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson depPointer, depPointerSize); 25202ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 253a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson if (A == AliasAnalysis::MustAlias) { 254a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson // Remove it! 255a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson MD.removeInstruction(dependency); 256a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 257a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson // DCE instructions only used to calculate that store 258a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson if (Instruction* D = dyn_cast<Instruction>(dependency->getOperand(0))) 259a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson possiblyDead.insert(D); 2603e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson if (Instruction* D = dyn_cast<Instruction>(dependency->getOperand(1))) 2613e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson possiblyDead.insert(D); 262a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 263a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson dependency->eraseFromParent(); 264a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson NumFastStores++; 265a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson return true; 266a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson } 267a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 268a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson return false; 269a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson} 270a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 271666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson/// handleEndBlock - Remove dead stores to stack-allocated locations in the 272bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// function end block. Ex: 273bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// %A = alloca i32 274bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ... 275bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// store i32 1, i32* %A 276bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ret void 277666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Andersonbool DSE::handleEndBlock(BasicBlock& BB, 278666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson SetVector<Instruction*>& possiblyDead) { 27943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson TargetData &TD = getAnalysis<TargetData>(); 28043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 28143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 28243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 28343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool MadeChange = false; 28443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 28543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Pointers alloca'd in this function are dead in the end block 286a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson SmallPtrSet<Value*, 64> deadPointers; 28743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 28843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Find all of the alloca'd pointers in the entry block 28943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BasicBlock *Entry = BB.getParent()->begin(); 29043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) 29143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 29243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson deadPointers.insert(AI); 293a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (Function::arg_iterator AI = BB.getParent()->arg_begin(), 294a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson AE = BB.getParent()->arg_end(); AI != AE; ++AI) 295a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (AI->hasByValAttr()) 296a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson deadPointers.insert(AI); 29743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 29843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Scan the basic block backwards 29943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ 30043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson --BBI; 30143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 30243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // If we find a store whose pointer is dead... 30343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (StoreInst* S = dyn_cast<StoreInst>(BBI)) { 3045dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson if (!S->isVolatile()) { 3055dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson Value* pointerOperand = S->getPointerOperand(); 3065dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson // See through pointer-to-pointer bitcasts 3075dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson TranslatePointerBitCasts(pointerOperand); 3083e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson 309e3c36f67580f0963abdf696a26690facb0791ce0Owen Anderson // Alloca'd pointers or byval arguments (which are functionally like 310e3c36f67580f0963abdf696a26690facb0791ce0Owen Anderson // alloca's) are valid candidates for removal. 311a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (deadPointers.count(pointerOperand)) { 3125dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson // Remove it! 3135dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson MD.removeInstruction(S); 31443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 3155dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson // DCE instructions only used to calculate that store 3165dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0))) 3175dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson possiblyDead.insert(D); 3185dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1))) 3195dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson possiblyDead.insert(D); 32043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 3215dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson BBI++; 3228aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson MD.removeInstruction(S); 3235dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson S->eraseFromParent(); 3245dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson NumFastStores++; 3255dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson MadeChange = true; 3265dfcf4318ab10da62a86cdce94f90c0a0cd42ad1Owen Anderson } 32743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 328bb3abf41a868357e95b639b34baebf802199e190Owen Anderson 329bb3abf41a868357e95b639b34baebf802199e190Owen Anderson continue; 330a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson 331a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson // We can also remove memcpy's to local variables at the end of a function 332a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } else if (MemCpyInst* M = dyn_cast<MemCpyInst>(BBI)) { 333a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson Value* dest = M->getDest(); 334a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson TranslatePointerBitCasts(dest); 335a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson 336a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (deadPointers.count(dest)) { 337a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson MD.removeInstruction(M); 338a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson 339a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson // DCE instructions only used to calculate that memcpy 340772601a8850808a66270372164941e373074493dOwen Anderson if (Instruction* D = dyn_cast<Instruction>(M->getRawSource())) 341a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson possiblyDead.insert(D); 342a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (Instruction* D = dyn_cast<Instruction>(M->getLength())) 343a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson possiblyDead.insert(D); 344a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (Instruction* D = dyn_cast<Instruction>(M->getRawDest())) 345a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson possiblyDead.insert(D); 346a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson 347a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson BBI++; 348a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson M->eraseFromParent(); 349a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson NumFastOther++; 350a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson MadeChange = true; 351a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson 352a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson continue; 353a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } 354a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson 355a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson // Because a memcpy is also a load, we can't skip it if we didn't remove it 356bb3abf41a868357e95b639b34baebf802199e190Owen Anderson } 357bb3abf41a868357e95b639b34baebf802199e190Owen Anderson 358bb3abf41a868357e95b639b34baebf802199e190Owen Anderson Value* killPointer = 0; 359c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson uint64_t killPointerSize = ~0UL; 36043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 36143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // If we encounter a use of the pointer, it is no longer considered dead 362bb3abf41a868357e95b639b34baebf802199e190Owen Anderson if (LoadInst* L = dyn_cast<LoadInst>(BBI)) { 363a72acf938902ea8ae2776cad7327257e88a63a54Nate Begeman // However, if this load is unused and not volatile, we can go ahead and 364a72acf938902ea8ae2776cad7327257e88a63a54Nate Begeman // remove it, and not have to worry about it making our pointer undead! 36500acf97feb2cba053a07505dfad9116ad09aae7aDan Gohman if (L->use_empty() && !L->isVolatile()) { 366772601a8850808a66270372164941e373074493dOwen Anderson MD.removeInstruction(L); 367772601a8850808a66270372164941e373074493dOwen Anderson 368772601a8850808a66270372164941e373074493dOwen Anderson // DCE instructions only used to calculate that load 369772601a8850808a66270372164941e373074493dOwen Anderson if (Instruction* D = dyn_cast<Instruction>(L->getPointerOperand())) 370772601a8850808a66270372164941e373074493dOwen Anderson possiblyDead.insert(D); 371772601a8850808a66270372164941e373074493dOwen Anderson 372772601a8850808a66270372164941e373074493dOwen Anderson BBI++; 373772601a8850808a66270372164941e373074493dOwen Anderson L->eraseFromParent(); 374772601a8850808a66270372164941e373074493dOwen Anderson NumFastOther++; 375772601a8850808a66270372164941e373074493dOwen Anderson MadeChange = true; 376772601a8850808a66270372164941e373074493dOwen Anderson possiblyDead.remove(L); 377772601a8850808a66270372164941e373074493dOwen Anderson 378772601a8850808a66270372164941e373074493dOwen Anderson continue; 379772601a8850808a66270372164941e373074493dOwen Anderson } 380772601a8850808a66270372164941e373074493dOwen Anderson 38143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson killPointer = L->getPointerOperand(); 38243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } else if (VAArgInst* V = dyn_cast<VAArgInst>(BBI)) { 38343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson killPointer = V->getOperand(0); 384c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson } else if (isa<MemCpyInst>(BBI) && 385c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson isa<ConstantInt>(cast<MemCpyInst>(BBI)->getLength())) { 386c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson killPointer = cast<MemCpyInst>(BBI)->getSource(); 387c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson killPointerSize = cast<ConstantInt>( 388c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson cast<MemCpyInst>(BBI)->getLength())->getZExtValue(); 38943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } else if (AllocaInst* A = dyn_cast<AllocaInst>(BBI)) { 39043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson deadPointers.erase(A); 391772601a8850808a66270372164941e373074493dOwen Anderson 392772601a8850808a66270372164941e373074493dOwen Anderson // Dead alloca's can be DCE'd when we reach them 393b4b04172206810623845a7f11dd3a65b0b3b10d5Nick Lewycky if (A->use_empty()) { 394772601a8850808a66270372164941e373074493dOwen Anderson MD.removeInstruction(A); 395772601a8850808a66270372164941e373074493dOwen Anderson 396772601a8850808a66270372164941e373074493dOwen Anderson // DCE instructions only used to calculate that load 397772601a8850808a66270372164941e373074493dOwen Anderson if (Instruction* D = dyn_cast<Instruction>(A->getArraySize())) 398772601a8850808a66270372164941e373074493dOwen Anderson possiblyDead.insert(D); 399772601a8850808a66270372164941e373074493dOwen Anderson 400772601a8850808a66270372164941e373074493dOwen Anderson BBI++; 401772601a8850808a66270372164941e373074493dOwen Anderson A->eraseFromParent(); 402772601a8850808a66270372164941e373074493dOwen Anderson NumFastOther++; 403772601a8850808a66270372164941e373074493dOwen Anderson MadeChange = true; 404772601a8850808a66270372164941e373074493dOwen Anderson possiblyDead.remove(A); 405772601a8850808a66270372164941e373074493dOwen Anderson } 406772601a8850808a66270372164941e373074493dOwen Anderson 40743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 40843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } else if (CallSite::get(BBI).getInstruction() != 0) { 409df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson // If this call does not access memory, it can't 410df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson // be undeadifying any of our pointers. 411df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson CallSite CS = CallSite::get(BBI); 412dff6710717b159f089c76a07eda074eb6347eb92Duncan Sands if (AA.doesNotAccessMemory(CS)) 413df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson continue; 414df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson 415362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson unsigned modRef = 0; 416362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson unsigned other = 0; 417362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 41843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Remove any pointers made undead by the call from the dead set 419a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson std::vector<Value*> dead; 420a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 42143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson E = deadPointers.end(); I != E; ++I) { 422362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // HACK: if we detect that our AA is imprecise, it's not 423362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // worth it to scan the rest of the deadPointers set. Just 424362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // assume that the AA will return ModRef for everything, and 425362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // go ahead and bail. 426362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson if (modRef >= 16 && other == 0) { 427362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson deadPointers.clear(); 428362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson return MadeChange; 429362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson } 43002ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 43143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Get size information for the alloca 43202ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands unsigned pointerSize = ~0U; 433a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) { 434a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize())) 435a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson pointerSize = C->getZExtValue() * \ 436a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson TD.getABITypeSize(A->getAllocatedType()); 437a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } else { 438a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson const PointerType* PT = cast<PointerType>( 439a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson cast<Argument>(*I)->getType()); 440a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson pointerSize = TD.getABITypeSize(PT->getElementType()); 441a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } 44202ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 44343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // See if the call site touches it 444df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, pointerSize); 445362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 446362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson if (A == AliasAnalysis::ModRef) 447362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson modRef++; 448362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson else 449362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson other++; 450362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 4513e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) 45243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson dead.push_back(*I); 45343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 45443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 455a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end(); 45643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson I != E; ++I) 457a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson deadPointers.erase(*I); 45843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 45943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 460772601a8850808a66270372164941e373074493dOwen Anderson } else { 461772601a8850808a66270372164941e373074493dOwen Anderson // For any non-memory-affecting non-terminators, DCE them as we reach them 462772601a8850808a66270372164941e373074493dOwen Anderson Instruction *CI = BBI; 463c7444498eebb654ea089df8ec52dba5f84f9a108Nick Lewycky if (!CI->isTerminator() && CI->use_empty() && !isa<FreeInst>(CI)) { 464772601a8850808a66270372164941e373074493dOwen Anderson 465772601a8850808a66270372164941e373074493dOwen Anderson // DCE instructions only used to calculate that load 466772601a8850808a66270372164941e373074493dOwen Anderson for (Instruction::op_iterator OI = CI->op_begin(), OE = CI->op_end(); 467772601a8850808a66270372164941e373074493dOwen Anderson OI != OE; ++OI) 468772601a8850808a66270372164941e373074493dOwen Anderson if (Instruction* D = dyn_cast<Instruction>(OI)) 469772601a8850808a66270372164941e373074493dOwen Anderson possiblyDead.insert(D); 470772601a8850808a66270372164941e373074493dOwen Anderson 471772601a8850808a66270372164941e373074493dOwen Anderson BBI++; 472772601a8850808a66270372164941e373074493dOwen Anderson CI->eraseFromParent(); 473772601a8850808a66270372164941e373074493dOwen Anderson NumFastOther++; 474772601a8850808a66270372164941e373074493dOwen Anderson MadeChange = true; 475772601a8850808a66270372164941e373074493dOwen Anderson possiblyDead.remove(CI); 476772601a8850808a66270372164941e373074493dOwen Anderson 477772601a8850808a66270372164941e373074493dOwen Anderson continue; 478772601a8850808a66270372164941e373074493dOwen Anderson } 47943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 48043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 48143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (!killPointer) 48243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 48343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 484362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson TranslatePointerBitCasts(killPointer); 485362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 48643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Deal with undead pointers 487c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson MadeChange |= RemoveUndeadPointers(killPointer, killPointerSize, BBI, 48843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson deadPointers, possiblyDead); 48943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 49043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 49143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson return MadeChange; 49243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 49343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 494362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson/// RemoveUndeadPointers - check for uses of a pointer that make it 495362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson/// undead when scanning for dead stores to alloca's. 496c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Andersonbool DSE::RemoveUndeadPointers(Value* killPointer, uint64_t killPointerSize, 49743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BasicBlock::iterator& BBI, 498a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson SmallPtrSet<Value*, 64>& deadPointers, 49943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson SetVector<Instruction*>& possiblyDead) { 50043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson TargetData &TD = getAnalysis<TargetData>(); 50143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 50243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 50343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 504362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // If the kill pointer can be easily reduced to an alloca, 505362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson // don't bother doing extraneous AA queries 506a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (deadPointers.count(killPointer)) { 507a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson deadPointers.erase(killPointer); 508362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson return false; 509838014ee5bda6c1b99ad8d74664aa5ea19fb501bOwen Anderson } else if (isa<GlobalValue>(killPointer)) { 510838014ee5bda6c1b99ad8d74664aa5ea19fb501bOwen Anderson // A global can't be in the dead pointer set 511838014ee5bda6c1b99ad8d74664aa5ea19fb501bOwen Anderson return false; 512362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson } 513362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 51443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool MadeChange = false; 51543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 516a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson std::vector<Value*> undead; 51743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 518a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 51943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson E = deadPointers.end(); I != E; ++I) { 52043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Get size information for the alloca 52102ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands unsigned pointerSize = ~0U; 522a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) { 523a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize())) 524a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson pointerSize = C->getZExtValue() * \ 525a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson TD.getABITypeSize(A->getAllocatedType()); 526a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } else { 527a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson const PointerType* PT = cast<PointerType>( 528a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson cast<Argument>(*I)->getType()); 529a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson pointerSize = TD.getABITypeSize(PT->getElementType()); 530a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson } 53102ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 53243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // See if this pointer could alias it 533666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson AliasAnalysis::AliasResult A = AA.alias(*I, pointerSize, 534c69ace3a64aee6f97bd82f0d811b89f49a3b38ceOwen Anderson killPointer, killPointerSize); 53543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 53643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // If it must-alias and a store, we can delete it 53743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) { 53843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson StoreInst* S = cast<StoreInst>(BBI); 53943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 54043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Remove it! 54143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MD.removeInstruction(S); 54243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 54343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // DCE instructions only used to calculate that store 54443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0))) 54543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson possiblyDead.insert(D); 5463e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1))) 5473e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson possiblyDead.insert(D); 54843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 54943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BBI++; 55043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson S->eraseFromParent(); 55143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson NumFastStores++; 55243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson MadeChange = true; 55343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 55443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 55543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 55643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Otherwise, it is undead 55743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } else if (A != AliasAnalysis::NoAlias) 55843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson undead.push_back(*I); 55943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 56043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 561a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (std::vector<Value*>::iterator I = undead.begin(), E = undead.end(); 56243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson I != E; ++I) 563a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson deadPointers.erase(*I); 56443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 56543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson return MadeChange; 56643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 56743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 568bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// DeleteDeadInstructionChains - takes an instruction and a setvector of 569bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// dead instructions. If I is dead, it is erased, and its operands are 570bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// checked for deadness. If they are dead, they are added to the dead 571bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// setvector. 572f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Andersonvoid DSE::DeleteDeadInstructionChains(Instruction *I, 573b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson SetVector<Instruction*> &DeadInsts) { 574b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Instruction must be dead. 575b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson if (!I->use_empty() || !isInstructionTriviallyDead(I)) return; 576b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 577b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // Let the memory dependence know 578b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson getAnalysis<MemoryDependenceAnalysis>().removeInstruction(I); 579b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 580b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // See if this made any operands dead. We do it this way in case the 581b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // instruction uses the same operand twice. We don't want to delete a 582b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson // value then reference it. 583b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 584bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson if (I->getOperand(i)->hasOneUse()) 585bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson if (Instruction* Op = dyn_cast<Instruction>(I->getOperand(i))) 586bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson DeadInsts.insert(Op); // Attempt to nuke it later. 587bfbfb3c464e2e89653bc0a76c67cf807ecd0fd6aOwen Anderson 588b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson I->setOperand(i, 0); // Drop from the operand list. 589b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 590b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 591b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson I->eraseFromParent(); 592b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson ++NumFastOther; 593b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 594