DeadStoreElimination.cpp revision 54c4735db3f973a85bc73e0a231f00ab18762c54
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" 223161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner#include "llvm/GlobalVariable.h" 23b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Instructions.h" 24a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson#include "llvm/IntrinsicInst.h" 25b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Pass.h" 26a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson#include "llvm/Analysis/AliasAnalysis.h" 278aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson#include "llvm/Analysis/Dominators.h" 28f006b183e2d2bebcf6968d1dd7350397c95b0325Victor Hernandez#include "llvm/Analysis/MemoryBuiltins.h" 29b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Analysis/MemoryDependenceAnalysis.h" 30a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner#include "llvm/Analysis/ValueTracking.h" 31a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson#include "llvm/Target/TargetData.h" 32b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Transforms/Utils/Local.h" 33a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner#include "llvm/Support/Debug.h" 34a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner#include "llvm/ADT/SmallPtrSet.h" 35a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner#include "llvm/ADT/Statistic.h" 36b77c457cc87aeeb166995aed793a516e9e431703Owen Andersonusing namespace llvm; 37b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 38b77c457cc87aeeb166995aed793a516e9e431703Owen AndersonSTATISTIC(NumFastStores, "Number of stores deleted"); 39b77c457cc87aeeb166995aed793a516e9e431703Owen AndersonSTATISTIC(NumFastOther , "Number of other instrs removed"); 40b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 41b77c457cc87aeeb166995aed793a516e9e431703Owen Andersonnamespace { 423e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct DSE : public FunctionPass { 43e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AliasAnalysis *AA; 44e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MemoryDependenceAnalysis *MD; 45e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 46b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson static char ID; // Pass identification, replacement for typeid 47e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner DSE() : FunctionPass(ID), AA(0), MD(0) { 48081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeDSEPass(*PassRegistry::getPassRegistry()); 49081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 50b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 51b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson virtual bool runOnFunction(Function &F) { 52e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AA = &getAnalysis<AliasAnalysis>(); 53e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MD = &getAnalysis<MemoryDependenceAnalysis>(); 5498df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner DominatorTree &DT = getAnalysis<DominatorTree>(); 5598df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner 56e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner bool Changed = false; 57b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 5898df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner // Only check non-dead blocks. Dead blocks may have strange pointer 5998df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner // cycles that will confuse alias analysis. 6098df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner if (DT.isReachableFromEntry(I)) 6198df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner Changed |= runOnBasicBlock(*I); 62e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 63e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AA = 0; MD = 0; 64b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return Changed; 65b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 6639f372e23e49cecb8db2eb7120eb331173e50c74Chris Lattner 67b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool runOnBasicBlock(BasicBlock &BB); 681ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner bool HandleFree(CallInst *F); 69925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner bool handleEndBlock(BasicBlock &BB); 70d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner void RemoveAccessedObjects(const AliasAnalysis::Location &LoadedLoc, 71d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner SmallPtrSet<Value*, 16> &DeadStackObjects); 72b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 73b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const { 74b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.setPreservesCFG(); 758aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson AU.addRequired<DominatorTree>(); 76a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addRequired<AliasAnalysis>(); 77b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addRequired<MemoryDependenceAnalysis>(); 78e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AU.addPreserved<AliasAnalysis>(); 798aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson AU.addPreserved<DominatorTree>(); 80b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addPreserved<MemoryDependenceAnalysis>(); 81b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 82b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson }; 83b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 84b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 85844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar DSE::ID = 0; 862ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false) 872ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 882ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) 892ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 902ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(DSE, "dse", "Dead Store Elimination", false, false) 91844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 92f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen AndersonFunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } 93b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 947c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner//===----------------------------------------------------------------------===// 957c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner// Helper functions 967c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner//===----------------------------------------------------------------------===// 977c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 987c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// DeleteDeadInstruction - Delete this instruction. Before we do, go through 997c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// and zero out all the operands of this instruction. If any of them become 1007c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// dead, delete them and the computation tree that feeds them. 1017c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// 1027c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// If ValueSet is non-null, remove any deleted instructions from it as well. 1037c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// 1047c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattnerstatic void DeleteDeadInstruction(Instruction *I, 1057c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner MemoryDependenceAnalysis &MD, 1067c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner SmallPtrSet<Value*, 16> *ValueSet = 0) { 1077c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner SmallVector<Instruction*, 32> NowDeadInsts; 1087c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 1097c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner NowDeadInsts.push_back(I); 1107c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner --NumFastOther; 1117c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 1127c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // Before we touch this instruction, remove it from memdep! 1137c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner do { 1147c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner Instruction *DeadInst = NowDeadInsts.pop_back_val(); 1157c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner ++NumFastOther; 1167c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 1177c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // This instruction is dead, zap it, in stages. Start by removing it from 1187c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // MemDep, which needs to know the operands and needs it to be in the 1197c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // function. 1207c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner MD.removeInstruction(DeadInst); 1217c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 1227c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) { 1237c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner Value *Op = DeadInst->getOperand(op); 1247c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner DeadInst->setOperand(op, 0); 1257c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 1267c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // If this operand just became dead, add it to the NowDeadInsts list. 1277c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner if (!Op->use_empty()) continue; 1287c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 1297c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner if (Instruction *OpI = dyn_cast<Instruction>(Op)) 1307c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner if (isInstructionTriviallyDead(OpI)) 1317c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner NowDeadInsts.push_back(OpI); 1327c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner } 1337c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 1347c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner DeadInst->eraseFromParent(); 1357c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 1367c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner if (ValueSet) ValueSet->erase(DeadInst); 1377c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner } while (!NowDeadInsts.empty()); 1387c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner} 1397c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 1407c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 14172987a274223e64482d8697b948e1c13a448198dChris Lattner/// hasMemoryWrite - Does this instruction write some memory? This only returns 14272987a274223e64482d8697b948e1c13a448198dChris Lattner/// true for things that we can analyze with other helpers below. 14372987a274223e64482d8697b948e1c13a448198dChris Lattnerstatic bool hasMemoryWrite(Instruction *I) { 14458571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (isa<StoreInst>(I)) 14558571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky return true; 14658571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 14758571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky switch (II->getIntrinsicID()) { 14865a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner default: 14965a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner return false; 15065a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::memset: 15165a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::memmove: 15265a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::memcpy: 15365a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::init_trampoline: 15465a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::lifetime_end: 15565a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner return true; 15658571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky } 15758571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky } 15858571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky return false; 15958571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky} 16058571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky 161cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner/// getLocForWrite - Return a Location stored to by the specified instruction. 162cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattnerstatic AliasAnalysis::Location 163cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris LattnergetLocForWrite(Instruction *Inst, AliasAnalysis &AA) { 164cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) 165cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AA.getLocation(SI); 166cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 167cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Inst)) { 168cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // memcpy/memmove/memset. 169cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner AliasAnalysis::Location Loc = AA.getLocationForDest(MI); 170cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we don't have target data around, an unknown size in Location means 171cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // that we should use the size of the pointee type. This isn't valid for 172cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // memset/memcpy, which writes more than an i8. 173cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (Loc.Size == AliasAnalysis::UnknownSize && AA.getTargetData() == 0) 174cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AliasAnalysis::Location(); 175cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return Loc; 176cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 177cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 178cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst); 179cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (II == 0) return AliasAnalysis::Location(); 180cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 181cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner switch (II->getIntrinsicID()) { 182cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner default: return AliasAnalysis::Location(); // Unhandled intrinsic. 183cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner case Intrinsic::init_trampoline: 184cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we don't have target data around, an unknown size in Location means 185cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // that we should use the size of the pointee type. This isn't valid for 186cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // init.trampoline, which writes more than an i8. 187cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (AA.getTargetData() == 0) return AliasAnalysis::Location(); 188cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 189cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // FIXME: We don't know the size of the trampoline, so we can't really 190cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // handle it here. 191cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AliasAnalysis::Location(II->getArgOperand(0)); 192cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner case Intrinsic::lifetime_end: { 193cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); 194cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AliasAnalysis::Location(II->getArgOperand(1), Len); 195cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 196cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 197cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner} 198cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 199cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// getLocForRead - Return the location read by the specified "hasMemoryWrite" 200cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// instruction if any. 201cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattnerstatic AliasAnalysis::Location 202cc10244d7725f191bdc91cd62befff0c97257c7bChris LattnergetLocForRead(Instruction *Inst, AliasAnalysis &AA) { 203cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner assert(hasMemoryWrite(Inst) && "Unknown instruction case"); 204cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 205cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // The only instructions that both read and write are the mem transfer 206cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // instructions (memcpy/memmove). 207cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(Inst)) 208cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner return AA.getLocationForSource(MTI); 209cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner return AliasAnalysis::Location(); 210cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner} 211cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 212cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 213bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattner/// isRemovable - If the value of this instruction and the memory it writes to 214bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattner/// is unused, may we delete this instruction? 215bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattnerstatic bool isRemovable(Instruction *I) { 21656efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman // Don't remove volatile/atomic stores. 21758571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (StoreInst *SI = dyn_cast<StoreInst>(I)) 21856efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman return SI->isUnordered(); 21955ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner 22055ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner IntrinsicInst *II = cast<IntrinsicInst>(I); 22155ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner switch (II->getIntrinsicID()) { 22255ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner default: assert(0 && "doesn't pass 'hasMemoryWrite' predicate"); 22355ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner case Intrinsic::lifetime_end: 22455ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner // Never remove dead lifetime_end's, e.g. because it is followed by a 22555ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner // free. 22655ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner return false; 22755ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner case Intrinsic::init_trampoline: 22855ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner // Always safe to remove init_trampoline. 22955ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner return true; 23055ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner 23155ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner case Intrinsic::memset: 23255ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner case Intrinsic::memmove: 23355ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner case Intrinsic::memcpy: 23455ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner // Don't remove volatile memory intrinsics. 23555ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner return !cast<MemIntrinsic>(II)->isVolatile(); 23655ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner } 23758571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky} 23858571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky 2397c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// getStoredPointerOperand - Return the pointer that is being written to. 2407c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattnerstatic Value *getStoredPointerOperand(Instruction *I) { 24158571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (StoreInst *SI = dyn_cast<StoreInst>(I)) 24258571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky return SI->getPointerOperand(); 24358571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) 2447c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner return MI->getDest(); 2453ccbb22eaf3f0deebc15ff7be992f090a6f0ba0bGabor Greif 2463ccbb22eaf3f0deebc15ff7be992f090a6f0ba0bGabor Greif IntrinsicInst *II = cast<IntrinsicInst>(I); 2473ccbb22eaf3f0deebc15ff7be992f090a6f0ba0bGabor Greif switch (II->getIntrinsicID()) { 24865a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner default: assert(false && "Unexpected intrinsic!"); 24965a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::init_trampoline: 2503ccbb22eaf3f0deebc15ff7be992f090a6f0ba0bGabor Greif return II->getArgOperand(0); 251710c37c494229334f59b9be328366807db2a7d01Duncan Sands } 25258571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky} 25358571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky 254e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattnerstatic uint64_t getPointerSize(Value *V, AliasAnalysis &AA) { 255e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner const TargetData *TD = AA.getTargetData(); 256e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (TD == 0) 257e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner return AliasAnalysis::UnknownSize; 258e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 259e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (AllocaInst *A = dyn_cast<AllocaInst>(V)) { 260e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner // Get size information for the alloca 261e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(A->getArraySize())) 262e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner return C->getZExtValue() * TD->getTypeAllocSize(A->getAllocatedType()); 263e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner return AliasAnalysis::UnknownSize; 264e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner } 265e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 266e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner assert(isa<Argument>(V) && "Expected AllocaInst or Argument!"); 267db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner PointerType *PT = cast<PointerType>(V->getType()); 268e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner return TD->getTypeAllocSize(PT->getElementType()); 269e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner} 270e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 2713161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner/// isObjectPointerWithTrustworthySize - Return true if the specified Value* is 2723161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner/// pointing to an object with a pointer size we can trust. 2733161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattnerstatic bool isObjectPointerWithTrustworthySize(const Value *V) { 2743161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) 2753161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner return !AI->isArrayAllocation(); 2763161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 27729d8d6b039fff0d7bed81f72b8432f9e9bd5df33Chris Lattner return !GV->mayBeOverridden(); 2783161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner if (const Argument *A = dyn_cast<Argument>(V)) 2793161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner return A->hasByValAttr(); 2803161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner return false; 2813161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner} 282e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 283cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner/// isCompleteOverwrite - Return true if a store to the 'Later' location 284cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner/// completely overwrites a store to the 'Earlier' location. 285cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattnerstatic bool isCompleteOverwrite(const AliasAnalysis::Location &Later, 286cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner const AliasAnalysis::Location &Earlier, 28798016511932510bd5ec5dad1319922d9daf18991Chris Lattner AliasAnalysis &AA) { 288a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner const Value *P1 = Earlier.Ptr->stripPointerCasts(); 289a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner const Value *P2 = Later.Ptr->stripPointerCasts(); 290cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 291a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // If the start pointers are the same, we just have to compare sizes to see if 292a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // the later store was larger than the earlier store. 293a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner if (P1 == P2) { 294a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // If we don't know the sizes of either access, then we can't do a 295a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // comparison. 296a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner if (Later.Size == AliasAnalysis::UnknownSize || 297a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner Earlier.Size == AliasAnalysis::UnknownSize) { 298a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // If we have no TargetData information around, then the size of the store 299a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // is inferrable from the pointee type. If they are the same type, then 300a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // we know that the store is safe. 301a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner if (AA.getTargetData() == 0) 302a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner return Later.Ptr->getType() == Earlier.Ptr->getType(); 303a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner return false; 304a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner } 305a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner 306a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // Make sure that the Later size is >= the Earlier size. 307a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner if (Later.Size < Earlier.Size) 308a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner return false; 309a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner return true; 310a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner } 311a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner 312a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // Otherwise, we have to have size information, and the later store has to be 313a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // larger than the earlier one. 31498016511932510bd5ec5dad1319922d9daf18991Chris Lattner if (Later.Size == AliasAnalysis::UnknownSize || 315a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner Earlier.Size == AliasAnalysis::UnknownSize || 3163161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner Later.Size <= Earlier.Size || AA.getTargetData() == 0) 31798016511932510bd5ec5dad1319922d9daf18991Chris Lattner return false; 31840dd12e7080c5df253fd70b468368e3144a43c0cChris Lattner 3193161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // Check to see if the later store is to the entire object (either a global, 3203161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // an alloca, or a byval argument). If so, then it clearly overwrites any 3213161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // other store to the same object. 322a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner const TargetData &TD = *AA.getTargetData(); 323a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner 324bd1801b5553c8be3960255a92738464e0010b6f6Dan Gohman const Value *UO1 = GetUnderlyingObject(P1, &TD), 325bd1801b5553c8be3960255a92738464e0010b6f6Dan Gohman *UO2 = GetUnderlyingObject(P2, &TD); 3263161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner 3273161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // If we can't resolve the same pointers to the same object, then we can't 3283161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // analyze them at all. 3293161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner if (UO1 != UO2) 3303161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner return false; 3313161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner 3323161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // If the "Later" store is to a recognizable object, get its size. 3333161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner if (isObjectPointerWithTrustworthySize(UO2)) { 3343161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner uint64_t ObjectSize = 3353161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner TD.getTypeAllocSize(cast<PointerType>(UO2->getType())->getElementType()); 3363161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner if (ObjectSize == Later.Size) 3373161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner return true; 3383161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner } 3393161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner 340a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // Okay, we have stores to two completely different pointers. Try to 341a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // decompose the pointer into a "base + constant_offset" form. If the base 342a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // pointers are equal, then we can reason about the two stores. 343150c4a1a89478f36af776f9146288afd528b33daBill Wendling int64_t EarlierOff = 0, LaterOff = 0; 344150c4a1a89478f36af776f9146288afd528b33daBill Wendling const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, TD); 345150c4a1a89478f36af776f9146288afd528b33daBill Wendling const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, TD); 346a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner 347a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // If the base pointers still differ, we have two completely different stores. 348a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner if (BP1 != BP2) 349cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return false; 350e420449e80191051d6d1636883f2400cb0a8ace5Bill Wendling 351150c4a1a89478f36af776f9146288afd528b33daBill Wendling // The later store completely overlaps the earlier store if: 352150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 353150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 1. Both start at the same offset and the later one's size is greater than 354150c4a1a89478f36af776f9146288afd528b33daBill Wendling // or equal to the earlier one's, or 355150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 356150c4a1a89478f36af776f9146288afd528b33daBill Wendling // |--earlier--| 357150c4a1a89478f36af776f9146288afd528b33daBill Wendling // |-- later --| 358150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 359150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 2. The earlier store has an offset greater than the later offset, but which 360150c4a1a89478f36af776f9146288afd528b33daBill Wendling // still lies completely within the later store. 361150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 362150c4a1a89478f36af776f9146288afd528b33daBill Wendling // |--earlier--| 363150c4a1a89478f36af776f9146288afd528b33daBill Wendling // |----- later ------| 36431d244ead52171632cc4649623b426dbea27040aBill Wendling // 36531d244ead52171632cc4649623b426dbea27040aBill Wendling // We have to be careful here as *Off is signed while *.Size is unsigned. 3661a4d58af0923123b655a6c0c553c62a266e1ebbcBill Wendling if (EarlierOff >= LaterOff && 36731d244ead52171632cc4649623b426dbea27040aBill Wendling uint64_t(EarlierOff - LaterOff) + Earlier.Size <= Later.Size) 368150c4a1a89478f36af776f9146288afd528b33daBill Wendling return true; 369150c4a1a89478f36af776f9146288afd528b33daBill Wendling 370150c4a1a89478f36af776f9146288afd528b33daBill Wendling // Otherwise, they don't completely overlap. 371150c4a1a89478f36af776f9146288afd528b33daBill Wendling return false; 37240dd12e7080c5df253fd70b468368e3144a43c0cChris Lattner} 37340dd12e7080c5df253fd70b468368e3144a43c0cChris Lattner 374cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// isPossibleSelfRead - If 'Inst' might be a self read (i.e. a noop copy of a 375cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// memory region into an identical pointer) then it doesn't actually make its 376cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// input dead in the traditional sense. Consider this case: 377cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// 378cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// memcpy(A <- B) 379cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// memcpy(A <- A) 380cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// 381cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// In this case, the second store to A does not make the first store to A dead. 382cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// The usual situation isn't an explicit A<-A store like this (which can be 383cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// trivially removed) but a case where two pointers may alias. 384cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// 385cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// This function detects when it is unsafe to remove a dependent instruction 386cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// because the DSE inducing instruction may be a self-read. 387cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattnerstatic bool isPossibleSelfRead(Instruction *Inst, 388cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner const AliasAnalysis::Location &InstStoreLoc, 389cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner Instruction *DepWrite, AliasAnalysis &AA) { 390cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // Self reads can only happen for instructions that read memory. Get the 391cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // location read. 392cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner AliasAnalysis::Location InstReadLoc = getLocForRead(Inst, AA); 393cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (InstReadLoc.Ptr == 0) return false; // Not a reading instruction. 394cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 395cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // If the read and written loc obviously don't alias, it isn't a read. 396cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (AA.isNoAlias(InstReadLoc, InstStoreLoc)) return false; 397cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 398cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // Okay, 'Inst' may copy over itself. However, we can still remove a the 399cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // DepWrite instruction if we can prove that it reads from the same location 400cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // as Inst. This handles useful cases like: 401cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // memcpy(A <- B) 402cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // memcpy(A <- B) 403cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // Here we don't know if A/B may alias, but we do know that B/B are must 404cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // aliases, so removing the first memcpy is safe (assuming it writes <= # 405cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // bytes as the second one. 406cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner AliasAnalysis::Location DepReadLoc = getLocForRead(DepWrite, AA); 407cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 408cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (DepReadLoc.Ptr && AA.isMustAlias(InstReadLoc.Ptr, DepReadLoc.Ptr)) 409cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner return false; 410cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 411cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // If DepWrite doesn't read memory or if we can't prove it is a must alias, 412cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // then it can't be considered dead. 413cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner return true; 414cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner} 415cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 4167c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 4177c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner//===----------------------------------------------------------------------===// 4187c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner// DSE Pass 4197c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner//===----------------------------------------------------------------------===// 4207c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 421f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Andersonbool DSE::runOnBasicBlock(BasicBlock &BB) { 422b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool MadeChange = false; 423b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 42440ef630a4626365faeef8696f611e18d1a69f63aChris Lattner // Do a top-down walk on the BB. 425565f96b196325e83f41a83c97bdc751e731de608Chris Lattner for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) { 426565f96b196325e83f41a83c97bdc751e731de608Chris Lattner Instruction *Inst = BBI++; 427565f96b196325e83f41a83c97bdc751e731de608Chris Lattner 4281ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner // Handle 'free' calls specially. 4291ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner if (CallInst *F = isFreeCall(Inst)) { 4301ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner MadeChange |= HandleFree(F); 4311ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner continue; 4321ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner } 4331ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner 43472987a274223e64482d8697b948e1c13a448198dChris Lattner // If we find something that writes memory, get its memory dependence. 43572987a274223e64482d8697b948e1c13a448198dChris Lattner if (!hasMemoryWrite(Inst)) 4366ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson continue; 4370f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner 438e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MemDepResult InstDep = MD->getDependency(Inst); 4395e600e67b11c55c204b3eec00798badc96ed720bChris Lattner 440a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman // Ignore any store where we can't find a local dependence. 4415e600e67b11c55c204b3eec00798badc96ed720bChris Lattner // FIXME: cross-block DSE would be fun. :) 442a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman if (InstDep.isNonLocal() || InstDep.isUnknown()) 443cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner continue; 4441ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner 4450f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // If we're storing the same value back to a pointer that we just 4460f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // loaded from, then the store can be removed. 4470f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 4480f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) { 4490f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (SI->getPointerOperand() == DepLoad->getPointerOperand() && 45056efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman SI->getOperand(0) == DepLoad && isRemovable(SI)) { 451a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n " 452a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner << "LOAD: " << *DepLoad << "\n STORE: " << *SI << '\n'); 453a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner 4540f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // DeleteDeadInstruction can delete the current instruction. Save BBI 4550f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // in case we need it. 4560f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner WeakVH NextInst(BBI); 4570f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner 4587c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner DeleteDeadInstruction(SI, *MD); 4590f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner 4600f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (NextInst == 0) // Next instruction deleted. 4610f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner BBI = BB.begin(); 4620f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner else if (BBI != BB.begin()) // Revisit this instruction if possible. 4630f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner --BBI; 4640f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner ++NumFastStores; 4650f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner MadeChange = true; 4660f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner continue; 4670f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner } 4680f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner } 4690f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner } 470bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattner 471cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Figure out what location is being stored to. 472e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AliasAnalysis::Location Loc = getLocForWrite(Inst, *AA); 473cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 474cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we didn't get a useful location, fail. 475cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (Loc.Ptr == 0) 476cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner continue; 477cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 478a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman while (!InstDep.isNonLocal() && !InstDep.isUnknown()) { 479cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Get the memory clobbered by the instruction we depend on. MemDep will 480cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // skip any instructions that 'Loc' clearly doesn't interact with. If we 481cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // end up depending on a may- or must-aliased load, then we can't optimize 482cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // away the store and we bail out. However, if we depend on on something 483cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // that overwrites the memory location we *can* potentially optimize it. 484cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // 4857a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // Find out what memory location the dependent instruction stores. 486cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner Instruction *DepWrite = InstDep.getInst(); 487e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AliasAnalysis::Location DepLoc = getLocForWrite(DepWrite, *AA); 488cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we didn't get a useful location, or if it isn't a size, bail out. 489cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (DepLoc.Ptr == 0) 490cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner break; 491cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 492cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // If we find a write that is a) removable (i.e., non-volatile), b) is 493cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // completely obliterated by the store to 'Loc', and c) which we know that 494cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // 'Inst' doesn't load from, then we can remove it. 495cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (isRemovable(DepWrite) && isCompleteOverwrite(Loc, DepLoc, *AA) && 496cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner !isPossibleSelfRead(Inst, Loc, DepWrite, *AA)) { 497a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " 498a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner << *DepWrite << "\n KILLER: " << *Inst << '\n'); 499a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner 500cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Delete the store and now-dead instructions that feed it. 5017c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner DeleteDeadInstruction(DepWrite, *MD); 502cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner ++NumFastStores; 503cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner MadeChange = true; 504cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 505cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // DeleteDeadInstruction can delete the current instruction in loop 506cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // cases, reset BBI. 507cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner BBI = Inst; 508cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (BBI != BB.begin()) 509cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner --BBI; 510cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner break; 511cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 512cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 513f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // If this is a may-aliased store that is clobbering the store value, we 514f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // can keep searching past it for another must-aliased pointer that stores 515f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // to the same location. For example, in: 516f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // store -> P 517f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // store -> Q 518f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // store -> P 519f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // we can remove the first store to P even though we don't know if P and Q 520f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // alias. 521cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (DepWrite == &BB.front()) break; 522cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 523cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Can't look past this instruction if it might read 'Loc'. 524e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (AA->getModRefInfo(DepWrite, Loc) & AliasAnalysis::Ref) 525cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner break; 526bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattner 527e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner InstDep = MD->getPointerDependencyFrom(Loc, false, DepWrite, &BB); 52858571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky } 529b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 530b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 531565f96b196325e83f41a83c97bdc751e731de608Chris Lattner // If this block ends in a return, unwind, or unreachable, all allocas are 532565f96b196325e83f41a83c97bdc751e731de608Chris Lattner // dead at its end, which means stores to them are also dead. 53343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (BB.getTerminator()->getNumSuccessors() == 0) 534925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner MadeChange |= handleEndBlock(BB); 535b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 536b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return MadeChange; 537b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 538b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 5391ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner/// HandleFree - Handle frees of entire structures whose dependency is a store 5401ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner/// to a field of that structure. 5411ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattnerbool DSE::HandleFree(CallInst *F) { 542a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman bool MadeChange = false; 543a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman 544e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MemDepResult Dep = MD->getDependency(F); 545a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman 546a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman while (!Dep.isNonLocal() && !Dep.isUnknown()) { 547720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman Instruction *Dependency = Dep.getInst(); 548bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattner if (!hasMemoryWrite(Dependency) || !isRemovable(Dependency)) 549a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman return MadeChange; 550dd61c2b25c1ea3f0ee2f3d4283b6814ab2c7891cOwen Anderson 5517c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner Value *DepPointer = 5525034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman GetUnderlyingObject(getStoredPointerOperand(Dependency)); 55302ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 554720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman // Check for aliasing. 555cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (!AA->isMustAlias(F->getArgOperand(0), DepPointer)) 556a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman return MadeChange; 557a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 558720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman // DCE instructions only used to calculate that store 5597c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner DeleteDeadInstruction(Dependency, *MD); 560720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman ++NumFastStores; 561a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman MadeChange = true; 562720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman 563720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman // Inst's old Dependency is now deleted. Compute the next dependency, 564720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman // which may also be dead, as in 565720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman // s[0] = 0; 566720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman // s[1] = 0; // This has just been deleted. 567720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman // free(s); 568e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner Dep = MD->getDependency(F); 569a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman }; 5701ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner 571a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman return MadeChange; 572a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson} 573a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 574666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson/// handleEndBlock - Remove dead stores to stack-allocated locations in the 575bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// function end block. Ex: 576bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// %A = alloca i32 577bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ... 578bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// store i32 1, i32* %A 579bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ret void 580925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattnerbool DSE::handleEndBlock(BasicBlock &BB) { 58143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool MadeChange = false; 58243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 5835fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // Keep track of all of the stack objects that are dead at the end of the 5845fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // function. 5855fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner SmallPtrSet<Value*, 16> DeadStackObjects; 58643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 587925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // Find all of the alloca'd pointers in the entry block. 58843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BasicBlock *Entry = BB.getParent()->begin(); 58943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) 59043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 5915fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner DeadStackObjects.insert(AI); 592925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 593925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // Treat byval arguments the same, stores to them are dead at the end of the 594925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // function. 595a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (Function::arg_iterator AI = BB.getParent()->arg_begin(), 596a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson AE = BB.getParent()->arg_end(); AI != AE; ++AI) 597a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (AI->hasByValAttr()) 5985fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner DeadStackObjects.insert(AI); 59943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 60043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Scan the basic block backwards 60143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ 60243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson --BBI; 60343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 60483d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // If we find a store, check to see if it points into a dead stack value. 60583d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner if (hasMemoryWrite(BBI) && isRemovable(BBI)) { 60683d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // See through pointer-to-pointer bitcasts 6075034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman Value *Pointer = GetUnderlyingObject(getStoredPointerOperand(BBI)); 60883d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner 6097c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // Stores to stack values are valid candidates for removal. 6105fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner if (DeadStackObjects.count(Pointer)) { 61183d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner Instruction *Dead = BBI++; 612a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner 613a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner DEBUG(dbgs() << "DSE: Dead Store at End of Block:\n DEAD: " 614a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner << *Dead << "\n Object: " << *Pointer << '\n'); 615a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner 616a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner // DCE instructions only used to calculate that store. 6177c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner DeleteDeadInstruction(Dead, *MD, &DeadStackObjects); 61883d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner ++NumFastStores; 61983d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner MadeChange = true; 62054c4735db3f973a85bc73e0a231f00ab18762c54Owen Anderson continue; 62183d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } 62283d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } 62383d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner 62483d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // Remove any dead non-memory-mutating instructions. 62583d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner if (isInstructionTriviallyDead(BBI)) { 62683d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner Instruction *Inst = BBI++; 6277c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner DeleteDeadInstruction(Inst, *MD, &DeadStackObjects); 62883d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner ++NumFastOther; 62983d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner MadeChange = true; 63083d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner continue; 63183d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } 63283d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner 63383d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner if (AllocaInst *A = dyn_cast<AllocaInst>(BBI)) { 6345fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner DeadStackObjects.erase(A); 63583d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner continue; 636bb3abf41a868357e95b639b34baebf802199e190Owen Anderson } 637bb3abf41a868357e95b639b34baebf802199e190Owen Anderson 63886dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner if (CallSite CS = cast<Value>(BBI)) { 63983d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // If this call does not access memory, it can't be loading any of our 64083d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // pointers. 641e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (AA->doesNotAccessMemory(CS)) 642df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson continue; 643df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson 64486dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // If the call might load from any of our allocas, then any store above 64586dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // the call is live. 64686dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner SmallVector<Value*, 8> LiveAllocas; 6475fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner for (SmallPtrSet<Value*, 16>::iterator I = DeadStackObjects.begin(), 6485fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner E = DeadStackObjects.end(); I != E; ++I) { 64986dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // See if the call site touches it. 65098016511932510bd5ec5dad1319922d9daf18991Chris Lattner AliasAnalysis::ModRefResult A = 651e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AA->getModRefInfo(CS, *I, getPointerSize(*I, *AA)); 652362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 6533e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) 65486dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner LiveAllocas.push_back(*I); 65543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 65686dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner 65786dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner for (SmallVector<Value*, 8>::iterator I = LiveAllocas.begin(), 65886dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner E = LiveAllocas.end(); I != E; ++I) 6595fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner DeadStackObjects.erase(*I); 66043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 66186dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // If all of the allocas were clobbered by the call then we're not going 66286dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // to find anything else to process. 6635fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner if (DeadStackObjects.empty()) 66486dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner return MadeChange; 66586dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner 66643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 66786dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner } 6688a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman 669d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner AliasAnalysis::Location LoadedLoc; 67086dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner 67186dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // If we encounter a use of the pointer, it is no longer considered dead 67286dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner if (LoadInst *L = dyn_cast<LoadInst>(BBI)) { 67356efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman if (!L->isUnordered()) // Be conservative with atomic/volatile load 67456efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman break; 675d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner LoadedLoc = AA->getLocation(L); 67686dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) { 677d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner LoadedLoc = AA->getLocation(V); 67886dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(BBI)) { 679d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner LoadedLoc = AA->getLocationForSource(MTI); 6808a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman } else if (!BBI->mayReadOrWriteMemory()) { 6818a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman // Instruction doesn't touch memory. 682925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner continue; 6838a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman } else { 6848a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman // Unknown inst; assume it clobbers everything. 6858a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman break; 68643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 6875d0392c6b370758750b397e254a6c6f028479969Duncan Sands 6885fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // Remove any allocas from the DeadPointer set that are loaded, as this 6895fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // makes any stores above the access live. 690d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner RemoveAccessedObjects(LoadedLoc, DeadStackObjects); 6915d0392c6b370758750b397e254a6c6f028479969Duncan Sands 6925fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // If all of the allocas were clobbered by the access then we're not going 6935fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // to find anything else to process. 6945fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner if (DeadStackObjects.empty()) 6955fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner break; 69643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 69743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 69843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson return MadeChange; 69943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 70043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 7015fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner/// RemoveAccessedObjects - Check to see if the specified location may alias any 7025fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner/// of the stack objects in the DeadStackObjects set. If so, they become live 7035fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner/// because the location is being loaded. 704d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattnervoid DSE::RemoveAccessedObjects(const AliasAnalysis::Location &LoadedLoc, 7055fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner SmallPtrSet<Value*, 16> &DeadStackObjects) { 7065034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman const Value *UnderlyingPointer = GetUnderlyingObject(LoadedLoc.Ptr); 7075fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner 7085fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // A constant can't be in the dead pointer set. 7095fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner if (isa<Constant>(UnderlyingPointer)) 71042cb684f8d8440ffd79415280dcb7676d0b5f29aChris Lattner return; 711362bb521087649c1a473ec97d6ec03c6eab9e662Owen Anderson 7125fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // If the kill pointer can be easily reduced to an alloca, don't bother doing 7135fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // extraneous AA queries. 71442cb684f8d8440ffd79415280dcb7676d0b5f29aChris Lattner if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) { 715d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner DeadStackObjects.erase(const_cast<Value*>(UnderlyingPointer)); 71642cb684f8d8440ffd79415280dcb7676d0b5f29aChris Lattner return; 7175fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner } 718925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner 7195fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner SmallVector<Value*, 16> NowLive; 7205fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner for (SmallPtrSet<Value*, 16>::iterator I = DeadStackObjects.begin(), 7215fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner E = DeadStackObjects.end(); I != E; ++I) { 722d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner // See if the loaded location could alias the stack location. 723d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner AliasAnalysis::Location StackLoc(*I, getPointerSize(*I, *AA)); 724d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner if (!AA->isNoAlias(StackLoc, LoadedLoc)) 7255fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner NowLive.push_back(*I); 72643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 72743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 7285fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner for (SmallVector<Value*, 16>::iterator I = NowLive.begin(), E = NowLive.end(); 72943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson I != E; ++I) 7305fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner DeadStackObjects.erase(*I); 73143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 73243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 733