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" 274d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky#include "llvm/Analysis/CaptureTracking.h" 288aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson#include "llvm/Analysis/Dominators.h" 29f006b183e2d2bebcf6968d1dd7350397c95b0325Victor Hernandez#include "llvm/Analysis/MemoryBuiltins.h" 30b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Analysis/MemoryDependenceAnalysis.h" 31a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner#include "llvm/Analysis/ValueTracking.h" 32a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson#include "llvm/Target/TargetData.h" 33b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Transforms/Utils/Local.h" 34a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner#include "llvm/Support/Debug.h" 356e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng#include "llvm/ADT/SetVector.h" 36a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner#include "llvm/ADT/Statistic.h" 37336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky#include "llvm/ADT/STLExtras.h" 38b77c457cc87aeeb166995aed793a516e9e431703Owen Andersonusing namespace llvm; 39b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 40b77c457cc87aeeb166995aed793a516e9e431703Owen AndersonSTATISTIC(NumFastStores, "Number of stores deleted"); 41b77c457cc87aeeb166995aed793a516e9e431703Owen AndersonSTATISTIC(NumFastOther , "Number of other instrs removed"); 42b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 43b77c457cc87aeeb166995aed793a516e9e431703Owen Andersonnamespace { 443e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct DSE : public FunctionPass { 45e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AliasAnalysis *AA; 46e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MemoryDependenceAnalysis *MD; 47336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky DominatorTree *DT; 48e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 49b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson static char ID; // Pass identification, replacement for typeid 50336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky DSE() : FunctionPass(ID), AA(0), MD(0), DT(0) { 51081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeDSEPass(*PassRegistry::getPassRegistry()); 52081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 53b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 54b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson virtual bool runOnFunction(Function &F) { 55e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AA = &getAnalysis<AliasAnalysis>(); 56e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MD = &getAnalysis<MemoryDependenceAnalysis>(); 57336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky DT = &getAnalysis<DominatorTree>(); 5881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 59e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner bool Changed = false; 60b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 6198df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner // Only check non-dead blocks. Dead blocks may have strange pointer 6298df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner // cycles that will confuse alias analysis. 63336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (DT->isReachableFromEntry(I)) 6498df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner Changed |= runOnBasicBlock(*I); 6581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 66336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky AA = 0; MD = 0; DT = 0; 67b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return Changed; 68b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 6981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 70b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool runOnBasicBlock(BasicBlock &BB); 711ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner bool HandleFree(CallInst *F); 72925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner bool handleEndBlock(BasicBlock &BB); 73d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner void RemoveAccessedObjects(const AliasAnalysis::Location &LoadedLoc, 746e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng SmallSetVector<Value*, 16> &DeadStackObjects); 75b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 76b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const { 77b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.setPreservesCFG(); 788aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson AU.addRequired<DominatorTree>(); 79a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addRequired<AliasAnalysis>(); 80b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addRequired<MemoryDependenceAnalysis>(); 81e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AU.addPreserved<AliasAnalysis>(); 828aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson AU.addPreserved<DominatorTree>(); 83b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addPreserved<MemoryDependenceAnalysis>(); 84b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 85b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson }; 86b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 87b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 88844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar DSE::ID = 0; 892ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false) 902ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 912ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) 922ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 932ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(DSE, "dse", "Dead Store Elimination", false, false) 94844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 95f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen AndersonFunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } 96b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 977c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner//===----------------------------------------------------------------------===// 987c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner// Helper functions 997c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner//===----------------------------------------------------------------------===// 1007c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 1017c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// DeleteDeadInstruction - Delete this instruction. Before we do, go through 1027c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// and zero out all the operands of this instruction. If any of them become 1037c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// dead, delete them and the computation tree that feeds them. 1047c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// 1057c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// If ValueSet is non-null, remove any deleted instructions from it as well. 1067c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// 1077c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattnerstatic void DeleteDeadInstruction(Instruction *I, 1087c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner MemoryDependenceAnalysis &MD, 1098e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI, 1106e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng SmallSetVector<Value*, 16> *ValueSet = 0) { 1117c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner SmallVector<Instruction*, 32> NowDeadInsts; 11281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1137c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner NowDeadInsts.push_back(I); 1147c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner --NumFastOther; 11581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1167c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // Before we touch this instruction, remove it from memdep! 1177c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner do { 1187c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner Instruction *DeadInst = NowDeadInsts.pop_back_val(); 1197c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner ++NumFastOther; 12081856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1217c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // This instruction is dead, zap it, in stages. Start by removing it from 1227c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // MemDep, which needs to know the operands and needs it to be in the 1237c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // function. 1247c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner MD.removeInstruction(DeadInst); 12581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1267c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) { 1277c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner Value *Op = DeadInst->getOperand(op); 1287c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner DeadInst->setOperand(op, 0); 12981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1307c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // If this operand just became dead, add it to the NowDeadInsts list. 1317c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner if (!Op->use_empty()) continue; 13281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1337c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner if (Instruction *OpI = dyn_cast<Instruction>(Op)) 1348e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (isInstructionTriviallyDead(OpI, TLI)) 1357c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner NowDeadInsts.push_back(OpI); 1367c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner } 13781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1387c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner DeadInst->eraseFromParent(); 13981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1406e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng if (ValueSet) ValueSet->remove(DeadInst); 1417c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner } while (!NowDeadInsts.empty()); 1427c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner} 1437c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 1447c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 14572987a274223e64482d8697b948e1c13a448198dChris Lattner/// hasMemoryWrite - Does this instruction write some memory? This only returns 14672987a274223e64482d8697b948e1c13a448198dChris Lattner/// true for things that we can analyze with other helpers below. 14772987a274223e64482d8697b948e1c13a448198dChris Lattnerstatic bool hasMemoryWrite(Instruction *I) { 14858571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (isa<StoreInst>(I)) 14958571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky return true; 15058571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 15158571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky switch (II->getIntrinsicID()) { 15265a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner default: 15365a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner return false; 15465a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::memset: 15565a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::memmove: 15665a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::memcpy: 15765a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::init_trampoline: 15865a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::lifetime_end: 15965a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner return true; 16058571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky } 16158571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky } 16258571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky return false; 16358571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky} 16458571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky 165cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner/// getLocForWrite - Return a Location stored to by the specified instruction. 1661582e7f1e255c19595f82cb447e52869196dec58Eli Friedman/// If isRemovable returns true, this function and getLocForRead completely 1671582e7f1e255c19595f82cb447e52869196dec58Eli Friedman/// describe the memory operations for this instruction. 168cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattnerstatic AliasAnalysis::Location 169cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris LattnergetLocForWrite(Instruction *Inst, AliasAnalysis &AA) { 170cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) 171cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AA.getLocation(SI); 17281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 173cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Inst)) { 174cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // memcpy/memmove/memset. 175cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner AliasAnalysis::Location Loc = AA.getLocationForDest(MI); 176cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we don't have target data around, an unknown size in Location means 177cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // that we should use the size of the pointee type. This isn't valid for 178cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // memset/memcpy, which writes more than an i8. 179cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (Loc.Size == AliasAnalysis::UnknownSize && AA.getTargetData() == 0) 180cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AliasAnalysis::Location(); 181cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return Loc; 182cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 18381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 184cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst); 185cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (II == 0) return AliasAnalysis::Location(); 18681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 187cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner switch (II->getIntrinsicID()) { 188cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner default: return AliasAnalysis::Location(); // Unhandled intrinsic. 189cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner case Intrinsic::init_trampoline: 190cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we don't have target data around, an unknown size in Location means 191cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // that we should use the size of the pointee type. This isn't valid for 192cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // init.trampoline, which writes more than an i8. 193cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (AA.getTargetData() == 0) return AliasAnalysis::Location(); 19481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 195cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // FIXME: We don't know the size of the trampoline, so we can't really 196cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // handle it here. 197cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AliasAnalysis::Location(II->getArgOperand(0)); 198cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner case Intrinsic::lifetime_end: { 199cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); 200cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AliasAnalysis::Location(II->getArgOperand(1), Len); 201cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 202cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 203cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner} 204cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 205cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// getLocForRead - Return the location read by the specified "hasMemoryWrite" 206cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// instruction if any. 20781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Andersonstatic AliasAnalysis::Location 208cc10244d7725f191bdc91cd62befff0c97257c7bChris LattnergetLocForRead(Instruction *Inst, AliasAnalysis &AA) { 209cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner assert(hasMemoryWrite(Inst) && "Unknown instruction case"); 21081856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 211cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // The only instructions that both read and write are the mem transfer 212cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // instructions (memcpy/memmove). 213cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(Inst)) 214cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner return AA.getLocationForSource(MTI); 215cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner return AliasAnalysis::Location(); 216cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner} 217cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 218cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 219bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattner/// isRemovable - If the value of this instruction and the memory it writes to 220bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattner/// is unused, may we delete this instruction? 221bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattnerstatic bool isRemovable(Instruction *I) { 22256efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman // Don't remove volatile/atomic stores. 22358571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (StoreInst *SI = dyn_cast<StoreInst>(I)) 22456efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman return SI->isUnordered(); 22581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 22655ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner IntrinsicInst *II = cast<IntrinsicInst>(I); 22755ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner switch (II->getIntrinsicID()) { 228858143816d43e58b17bfd11cb1b57afbd7f0f893Craig Topper default: llvm_unreachable("doesn't pass 'hasMemoryWrite' predicate"); 22955ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner case Intrinsic::lifetime_end: 23055ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner // Never remove dead lifetime_end's, e.g. because it is followed by a 23155ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner // free. 23255ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner return false; 23355ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner case Intrinsic::init_trampoline: 23455ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner // Always safe to remove init_trampoline. 23555ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner return true; 23681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 23755ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner case Intrinsic::memset: 23855ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner case Intrinsic::memmove: 23955ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner case Intrinsic::memcpy: 24055ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner // Don't remove volatile memory intrinsics. 24155ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner return !cast<MemIntrinsic>(II)->isVolatile(); 24255ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner } 24358571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky} 24458571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky 2455ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper 2465ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper/// isShortenable - Returns true if this instruction can be safely shortened in 2475ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper/// length. 2485ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooperstatic bool isShortenable(Instruction *I) { 2495ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // Don't shorten stores for now 2505ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (isa<StoreInst>(I)) 2515ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return false; 252a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 2535ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper IntrinsicInst *II = cast<IntrinsicInst>(I); 2545ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper switch (II->getIntrinsicID()) { 2555ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper default: return false; 2565ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper case Intrinsic::memset: 2575ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper case Intrinsic::memcpy: 2585ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // Do shorten memory intrinsics. 2595ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return true; 2605ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper } 2615ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper} 2625ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper 2637c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// getStoredPointerOperand - Return the pointer that is being written to. 2647c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattnerstatic Value *getStoredPointerOperand(Instruction *I) { 26558571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (StoreInst *SI = dyn_cast<StoreInst>(I)) 26658571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky return SI->getPointerOperand(); 26758571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) 2687c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner return MI->getDest(); 2693ccbb22eaf3f0deebc15ff7be992f090a6f0ba0bGabor Greif 2703ccbb22eaf3f0deebc15ff7be992f090a6f0ba0bGabor Greif IntrinsicInst *II = cast<IntrinsicInst>(I); 2713ccbb22eaf3f0deebc15ff7be992f090a6f0ba0bGabor Greif switch (II->getIntrinsicID()) { 272858143816d43e58b17bfd11cb1b57afbd7f0f893Craig Topper default: llvm_unreachable("Unexpected intrinsic!"); 27365a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::init_trampoline: 2743ccbb22eaf3f0deebc15ff7be992f090a6f0ba0bGabor Greif return II->getArgOperand(0); 275710c37c494229334f59b9be328366807db2a7d01Duncan Sands } 27658571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky} 27758571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky 278ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewyckystatic uint64_t getPointerSize(const Value *V, AliasAnalysis &AA) { 2799e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes uint64_t Size; 2808e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (getObjectSize(V, Size, AA.getTargetData(), AA.getTargetLibraryInfo())) 2819e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return Size; 282ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewycky return AliasAnalysis::UnknownSize; 2833161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner} 284e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 2855ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Coopernamespace { 2865ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper enum OverwriteResult 2875ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper { 2885ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper OverwriteComplete, 2895ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper OverwriteEnd, 2905ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper OverwriteUnknown 2915ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper }; 2925ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper} 2935ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper 2945ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper/// isOverwrite - Return 'OverwriteComplete' if a store to the 'Later' location 295cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner/// completely overwrites a store to the 'Earlier' location. 296a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem/// 'OverwriteEnd' if the end of the 'Earlier' location is completely 2979e1154cf5b268b1036ad7611cd249647a76efb49Pete Cooper/// overwritten by 'Later', or 'OverwriteUnknown' if nothing can be determined 2985ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooperstatic OverwriteResult isOverwrite(const AliasAnalysis::Location &Later, 2995ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper const AliasAnalysis::Location &Earlier, 3005ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper AliasAnalysis &AA, 301ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewycky int64_t &EarlierOff, 302ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewycky int64_t &LaterOff) { 303a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner const Value *P1 = Earlier.Ptr->stripPointerCasts(); 304a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner const Value *P2 = Later.Ptr->stripPointerCasts(); 30581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 306a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // If the start pointers are the same, we just have to compare sizes to see if 307a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // the later store was larger than the earlier store. 308a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner if (P1 == P2) { 309a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // If we don't know the sizes of either access, then we can't do a 310a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // comparison. 311a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner if (Later.Size == AliasAnalysis::UnknownSize || 312a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner Earlier.Size == AliasAnalysis::UnknownSize) { 313a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // If we have no TargetData information around, then the size of the store 314a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // is inferrable from the pointee type. If they are the same type, then 315a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // we know that the store is safe. 3165ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (AA.getTargetData() == 0 && 3175ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper Later.Ptr->getType() == Earlier.Ptr->getType()) 3185ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteComplete; 319a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 3205ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteUnknown; 321a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner } 32281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 323a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // Make sure that the Later size is >= the Earlier size. 3245ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (Later.Size >= Earlier.Size) 3255ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteComplete; 326a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner } 32781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 328a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // Otherwise, we have to have size information, and the later store has to be 329a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // larger than the earlier one. 33098016511932510bd5ec5dad1319922d9daf18991Chris Lattner if (Later.Size == AliasAnalysis::UnknownSize || 331a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner Earlier.Size == AliasAnalysis::UnknownSize || 3325ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper AA.getTargetData() == 0) 3335ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteUnknown; 33481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 3353161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // Check to see if the later store is to the entire object (either a global, 3363161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // an alloca, or a byval argument). If so, then it clearly overwrites any 3373161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // other store to the same object. 338a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner const TargetData &TD = *AA.getTargetData(); 33981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 340bd1801b5553c8be3960255a92738464e0010b6f6Dan Gohman const Value *UO1 = GetUnderlyingObject(P1, &TD), 341bd1801b5553c8be3960255a92738464e0010b6f6Dan Gohman *UO2 = GetUnderlyingObject(P2, &TD); 34281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 3433161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // If we can't resolve the same pointers to the same object, then we can't 3443161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // analyze them at all. 3453161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner if (UO1 != UO2) 3465ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteUnknown; 34781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 3483161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // If the "Later" store is to a recognizable object, get its size. 349ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewycky uint64_t ObjectSize = getPointerSize(UO2, AA); 350ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewycky if (ObjectSize != AliasAnalysis::UnknownSize) 351c7e5a6a2c69ee2552242da2a70775acd7d8819aePete Cooper if (ObjectSize == Later.Size && ObjectSize >= Earlier.Size) 3525ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteComplete; 35381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 354a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // Okay, we have stores to two completely different pointers. Try to 355a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // decompose the pointer into a "base + constant_offset" form. If the base 356a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // pointers are equal, then we can reason about the two stores. 3575ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper EarlierOff = 0; 3585ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper LaterOff = 0; 359150c4a1a89478f36af776f9146288afd528b33daBill Wendling const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, TD); 360150c4a1a89478f36af776f9146288afd528b33daBill Wendling const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, TD); 36181856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 362a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // If the base pointers still differ, we have two completely different stores. 363a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner if (BP1 != BP2) 3645ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteUnknown; 365e420449e80191051d6d1636883f2400cb0a8ace5Bill Wendling 366150c4a1a89478f36af776f9146288afd528b33daBill Wendling // The later store completely overlaps the earlier store if: 36781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson // 368150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 1. Both start at the same offset and the later one's size is greater than 369150c4a1a89478f36af776f9146288afd528b33daBill Wendling // or equal to the earlier one's, or 370150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 371150c4a1a89478f36af776f9146288afd528b33daBill Wendling // |--earlier--| 372150c4a1a89478f36af776f9146288afd528b33daBill Wendling // |-- later --| 37381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson // 374150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 2. The earlier store has an offset greater than the later offset, but which 375150c4a1a89478f36af776f9146288afd528b33daBill Wendling // still lies completely within the later store. 376150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 377150c4a1a89478f36af776f9146288afd528b33daBill Wendling // |--earlier--| 378150c4a1a89478f36af776f9146288afd528b33daBill Wendling // |----- later ------| 37931d244ead52171632cc4649623b426dbea27040aBill Wendling // 38031d244ead52171632cc4649623b426dbea27040aBill Wendling // We have to be careful here as *Off is signed while *.Size is unsigned. 3811a4d58af0923123b655a6c0c553c62a266e1ebbcBill Wendling if (EarlierOff >= LaterOff && 382750d7616c6d9ed5a40de1ac8f74fb40afd82ebc6Craig Topper Later.Size >= Earlier.Size && 38331d244ead52171632cc4649623b426dbea27040aBill Wendling uint64_t(EarlierOff - LaterOff) + Earlier.Size <= Later.Size) 3845ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteComplete; 385a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 3865ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // The other interesting case is if the later store overwrites the end of 3875ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // the earlier store 3885ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // 3895ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // |--earlier--| 3905ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // |-- later --| 3915ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // 3925ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // In this case we may want to trim the size of earlier to avoid generating 3935ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // writes to addresses which will definitely be overwritten later 3945ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (LaterOff > EarlierOff && 3955ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper LaterOff < int64_t(EarlierOff + Earlier.Size) && 396de2e27cc52a9e47e0261dda6dfb54a32eefa90a0Pete Cooper int64_t(LaterOff + Later.Size) >= int64_t(EarlierOff + Earlier.Size)) 3975ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteEnd; 398150c4a1a89478f36af776f9146288afd528b33daBill Wendling 399150c4a1a89478f36af776f9146288afd528b33daBill Wendling // Otherwise, they don't completely overlap. 4005ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteUnknown; 40140dd12e7080c5df253fd70b468368e3144a43c0cChris Lattner} 40240dd12e7080c5df253fd70b468368e3144a43c0cChris Lattner 403cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// isPossibleSelfRead - If 'Inst' might be a self read (i.e. a noop copy of a 404cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// memory region into an identical pointer) then it doesn't actually make its 40581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson/// input dead in the traditional sense. Consider this case: 406cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// 407cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// memcpy(A <- B) 408cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// memcpy(A <- A) 409cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// 410cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// In this case, the second store to A does not make the first store to A dead. 411cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// The usual situation isn't an explicit A<-A store like this (which can be 412cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// trivially removed) but a case where two pointers may alias. 413cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// 414cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// This function detects when it is unsafe to remove a dependent instruction 415cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// because the DSE inducing instruction may be a self-read. 416cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattnerstatic bool isPossibleSelfRead(Instruction *Inst, 417cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner const AliasAnalysis::Location &InstStoreLoc, 418cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner Instruction *DepWrite, AliasAnalysis &AA) { 419cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // Self reads can only happen for instructions that read memory. Get the 420cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // location read. 421cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner AliasAnalysis::Location InstReadLoc = getLocForRead(Inst, AA); 422cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (InstReadLoc.Ptr == 0) return false; // Not a reading instruction. 42381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 424cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // If the read and written loc obviously don't alias, it isn't a read. 425cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (AA.isNoAlias(InstReadLoc, InstStoreLoc)) return false; 42681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 427cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // Okay, 'Inst' may copy over itself. However, we can still remove a the 428cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // DepWrite instruction if we can prove that it reads from the same location 429cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // as Inst. This handles useful cases like: 430cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // memcpy(A <- B) 431cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // memcpy(A <- B) 432cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // Here we don't know if A/B may alias, but we do know that B/B are must 433cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // aliases, so removing the first memcpy is safe (assuming it writes <= # 434cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // bytes as the second one. 435cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner AliasAnalysis::Location DepReadLoc = getLocForRead(DepWrite, AA); 43681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 437cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (DepReadLoc.Ptr && AA.isMustAlias(InstReadLoc.Ptr, DepReadLoc.Ptr)) 438cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner return false; 43981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 440cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // If DepWrite doesn't read memory or if we can't prove it is a must alias, 441cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // then it can't be considered dead. 442cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner return true; 443cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner} 444cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 4457c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 4467c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner//===----------------------------------------------------------------------===// 4477c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner// DSE Pass 4487c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner//===----------------------------------------------------------------------===// 4497c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 450f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Andersonbool DSE::runOnBasicBlock(BasicBlock &BB) { 451b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool MadeChange = false; 45281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 45340ef630a4626365faeef8696f611e18d1a69f63aChris Lattner // Do a top-down walk on the BB. 454565f96b196325e83f41a83c97bdc751e731de608Chris Lattner for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) { 455565f96b196325e83f41a83c97bdc751e731de608Chris Lattner Instruction *Inst = BBI++; 45681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 4571ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner // Handle 'free' calls specially. 4588e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (CallInst *F = isFreeCall(Inst, AA->getTargetLibraryInfo())) { 4591ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner MadeChange |= HandleFree(F); 4601ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner continue; 4611ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner } 46281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 46372987a274223e64482d8697b948e1c13a448198dChris Lattner // If we find something that writes memory, get its memory dependence. 46472987a274223e64482d8697b948e1c13a448198dChris Lattner if (!hasMemoryWrite(Inst)) 4656ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson continue; 4660f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner 467e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MemDepResult InstDep = MD->getDependency(Inst); 46881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 469a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman // Ignore any store where we can't find a local dependence. 4705e600e67b11c55c204b3eec00798badc96ed720bChris Lattner // FIXME: cross-block DSE would be fun. :) 471b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman if (!InstDep.isDef() && !InstDep.isClobber()) 472cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner continue; 47381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 4740f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // If we're storing the same value back to a pointer that we just 4750f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // loaded from, then the store can be removed. 4760f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 4770f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) { 4780f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (SI->getPointerOperand() == DepLoad->getPointerOperand() && 47956efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman SI->getOperand(0) == DepLoad && isRemovable(SI)) { 480a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n " 481a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner << "LOAD: " << *DepLoad << "\n STORE: " << *SI << '\n'); 48281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 4830f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // DeleteDeadInstruction can delete the current instruction. Save BBI 4840f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // in case we need it. 4850f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner WeakVH NextInst(BBI); 48681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 4878e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer DeleteDeadInstruction(SI, *MD, AA->getTargetLibraryInfo()); 48881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 4890f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (NextInst == 0) // Next instruction deleted. 4900f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner BBI = BB.begin(); 4910f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner else if (BBI != BB.begin()) // Revisit this instruction if possible. 4920f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner --BBI; 4930f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner ++NumFastStores; 4940f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner MadeChange = true; 4950f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner continue; 4960f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner } 4970f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner } 4980f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner } 49981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 500cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Figure out what location is being stored to. 501e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AliasAnalysis::Location Loc = getLocForWrite(Inst, *AA); 502cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 503cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we didn't get a useful location, fail. 504cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (Loc.Ptr == 0) 505cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner continue; 50681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 507b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman while (InstDep.isDef() || InstDep.isClobber()) { 508cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Get the memory clobbered by the instruction we depend on. MemDep will 509cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // skip any instructions that 'Loc' clearly doesn't interact with. If we 510cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // end up depending on a may- or must-aliased load, then we can't optimize 511cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // away the store and we bail out. However, if we depend on on something 512cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // that overwrites the memory location we *can* potentially optimize it. 513cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // 5147a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // Find out what memory location the dependent instruction stores. 515cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner Instruction *DepWrite = InstDep.getInst(); 516e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AliasAnalysis::Location DepLoc = getLocForWrite(DepWrite, *AA); 517cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we didn't get a useful location, or if it isn't a size, bail out. 518cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (DepLoc.Ptr == 0) 519cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner break; 520cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 521cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // If we find a write that is a) removable (i.e., non-volatile), b) is 522cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // completely obliterated by the store to 'Loc', and c) which we know that 523cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // 'Inst' doesn't load from, then we can remove it. 524a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem if (isRemovable(DepWrite) && 525cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner !isPossibleSelfRead(Inst, Loc, DepWrite, *AA)) { 526a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem int64_t InstWriteOffset, DepWriteOffset; 527a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem OverwriteResult OR = isOverwrite(Loc, DepLoc, *AA, 528a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem DepWriteOffset, InstWriteOffset); 5295ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (OR == OverwriteComplete) { 5305ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " 5315ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper << *DepWrite << "\n KILLER: " << *Inst << '\n'); 5325ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper 5335ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // Delete the store and now-dead instructions that feed it. 5348e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer DeleteDeadInstruction(DepWrite, *MD, AA->getTargetLibraryInfo()); 5355ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper ++NumFastStores; 5365ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper MadeChange = true; 537a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 5385ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // DeleteDeadInstruction can delete the current instruction in loop 5395ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // cases, reset BBI. 5405ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper BBI = Inst; 5415ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (BBI != BB.begin()) 5425ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper --BBI; 5435ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper break; 5445ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper } else if (OR == OverwriteEnd && isShortenable(DepWrite)) { 5455ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // TODO: base this on the target vector size so that if the earlier 5465ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // store was too small to get vector writes anyway then its likely 5475ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // a good idea to shorten it 5485ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // Power of 2 vector writes are probably always a bad idea to optimize 5495ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // as any store/memset/memcpy is likely using vector instructions so 5505ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // shortening it to not vector size is likely to be slower 5515ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper MemIntrinsic* DepIntrinsic = cast<MemIntrinsic>(DepWrite); 5525ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper unsigned DepWriteAlign = DepIntrinsic->getAlignment(); 5535ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (llvm::isPowerOf2_64(InstWriteOffset) || 5545ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper ((DepWriteAlign != 0) && InstWriteOffset % DepWriteAlign == 0)) { 555a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 5565ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper DEBUG(dbgs() << "DSE: Remove Dead Store:\n OW END: " 557a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem << *DepWrite << "\n KILLER (offset " 558a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem << InstWriteOffset << ", " 5595ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper << DepLoc.Size << ")" 5605ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper << *Inst << '\n'); 561a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 5625ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper Value* DepWriteLength = DepIntrinsic->getLength(); 5635ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper Value* TrimmedLength = ConstantInt::get(DepWriteLength->getType(), 564a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem InstWriteOffset - 5655ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper DepWriteOffset); 5665ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper DepIntrinsic->setLength(TrimmedLength); 5675ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper MadeChange = true; 5685ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper } 5695ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper } 570cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 57181856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 572f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // If this is a may-aliased store that is clobbering the store value, we 573f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // can keep searching past it for another must-aliased pointer that stores 574f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // to the same location. For example, in: 575f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // store -> P 576f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // store -> Q 577f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // store -> P 578f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // we can remove the first store to P even though we don't know if P and Q 579f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // alias. 580cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (DepWrite == &BB.front()) break; 58181856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 582cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Can't look past this instruction if it might read 'Loc'. 583e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (AA->getModRefInfo(DepWrite, Loc) & AliasAnalysis::Ref) 584cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner break; 58581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 586e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner InstDep = MD->getPointerDependencyFrom(Loc, false, DepWrite, &BB); 58758571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky } 588b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 58981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 590565f96b196325e83f41a83c97bdc751e731de608Chris Lattner // If this block ends in a return, unwind, or unreachable, all allocas are 591565f96b196325e83f41a83c97bdc751e731de608Chris Lattner // dead at its end, which means stores to them are also dead. 59243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (BB.getTerminator()->getNumSuccessors() == 0) 593925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner MadeChange |= handleEndBlock(BB); 59481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 595b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return MadeChange; 596b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 597b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 598336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky/// Find all blocks that will unconditionally lead to the block BB and append 599336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky/// them to F. 600336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewyckystatic void FindUnconditionalPreds(SmallVectorImpl<BasicBlock *> &Blocks, 601336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky BasicBlock *BB, DominatorTree *DT) { 602336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 603336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky BasicBlock *Pred = *I; 604c9b98ad7a7c3f2c098657a077a995912dce033e3Nick Lewycky if (Pred == BB) continue; 605336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky TerminatorInst *PredTI = Pred->getTerminator(); 606336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (PredTI->getNumSuccessors() != 1) 607336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky continue; 608336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky 609336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (DT->isReachableFromEntry(Pred)) 610336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Blocks.push_back(Pred); 611336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky } 612336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky} 613336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky 6141ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner/// HandleFree - Handle frees of entire structures whose dependency is a store 6151ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner/// to a field of that structure. 6161ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattnerbool DSE::HandleFree(CallInst *F) { 617a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman bool MadeChange = false; 618a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman 619336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky AliasAnalysis::Location Loc = AliasAnalysis::Location(F->getOperand(0)); 620336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky SmallVector<BasicBlock *, 16> Blocks; 621336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Blocks.push_back(F->getParent()); 622a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman 623336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky while (!Blocks.empty()) { 624336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky BasicBlock *BB = Blocks.pop_back_val(); 625336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Instruction *InstPt = BB->getTerminator(); 626336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (BB == F->getParent()) InstPt = F; 62781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 628336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky MemDepResult Dep = MD->getPointerDependencyFrom(Loc, false, InstPt, BB); 629336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky while (Dep.isDef() || Dep.isClobber()) { 630336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Instruction *Dependency = Dep.getInst(); 631336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (!hasMemoryWrite(Dependency) || !isRemovable(Dependency)) 632336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky break; 63302ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 634336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Value *DepPointer = 635336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky GetUnderlyingObject(getStoredPointerOperand(Dependency)); 63681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 637336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // Check for aliasing. 638336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (!AA->isMustAlias(F->getArgOperand(0), DepPointer)) 639336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky break; 640720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman 641336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Instruction *Next = llvm::next(BasicBlock::iterator(Dependency)); 642336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky 643336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // DCE instructions only used to calculate that store 6448e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer DeleteDeadInstruction(Dependency, *MD, AA->getTargetLibraryInfo()); 645336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky ++NumFastStores; 646336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky MadeChange = true; 647336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky 648336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // Inst's old Dependency is now deleted. Compute the next dependency, 649336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // which may also be dead, as in 650336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // s[0] = 0; 651336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // s[1] = 0; // This has just been deleted. 652336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // free(s); 653336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Dep = MD->getPointerDependencyFrom(Loc, false, Next, BB); 654336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky } 655336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky 656336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (Dep.isNonLocal()) 657336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky FindUnconditionalPreds(Blocks, BB, DT); 658336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky } 65981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 660a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman return MadeChange; 661a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson} 662a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 663666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson/// handleEndBlock - Remove dead stores to stack-allocated locations in the 664bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// function end block. Ex: 665bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// %A = alloca i32 666bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ... 667bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// store i32 1, i32* %A 668bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ret void 669925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattnerbool DSE::handleEndBlock(BasicBlock &BB) { 67043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool MadeChange = false; 67181856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 6725fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // Keep track of all of the stack objects that are dead at the end of the 6735fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // function. 6746e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng SmallSetVector<Value*, 16> DeadStackObjects; 67581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 676925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // Find all of the alloca'd pointers in the entry block. 67743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BasicBlock *Entry = BB.getParent()->begin(); 6784d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) { 6799e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (isa<AllocaInst>(I)) 6809e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DeadStackObjects.insert(I); 68181856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 6824d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky // Okay, so these are dead heap objects, but if the pointer never escapes 6834d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky // then it's leaked by this function anyways. 6848e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer else if (isAllocLikeFn(I, AA->getTargetLibraryInfo()) && 6858e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer !PointerMayBeCaptured(I, true, true)) 6869e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DeadStackObjects.insert(I); 6874d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky } 6884d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky 689925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // Treat byval arguments the same, stores to them are dead at the end of the 690925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // function. 691a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (Function::arg_iterator AI = BB.getParent()->arg_begin(), 692a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson AE = BB.getParent()->arg_end(); AI != AE; ++AI) 693a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (AI->hasByValAttr()) 6945fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner DeadStackObjects.insert(AI); 69581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 69643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Scan the basic block backwards 69743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ 69843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson --BBI; 69981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 70083d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // If we find a store, check to see if it points into a dead stack value. 70183d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner if (hasMemoryWrite(BBI) && isRemovable(BBI)) { 70283d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // See through pointer-to-pointer bitcasts 703b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman SmallVector<Value *, 4> Pointers; 704b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman GetUnderlyingObjects(getStoredPointerOperand(BBI), Pointers); 70583d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner 7067c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // Stores to stack values are valid candidates for removal. 707b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman bool AllDead = true; 708b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(), 709b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman E = Pointers.end(); I != E; ++I) 710b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman if (!DeadStackObjects.count(*I)) { 711b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman AllDead = false; 712b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman break; 713b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman } 714b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman 715b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman if (AllDead) { 71683d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner Instruction *Dead = BBI++; 71781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 718a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner DEBUG(dbgs() << "DSE: Dead Store at End of Block:\n DEAD: " 719b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman << *Dead << "\n Objects: "; 720b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(), 721b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman E = Pointers.end(); I != E; ++I) { 722b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman dbgs() << **I; 723b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman if (llvm::next(I) != E) 724b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman dbgs() << ", "; 725b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman } 726b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman dbgs() << '\n'); 72781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 728a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner // DCE instructions only used to calculate that store. 7298e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer DeleteDeadInstruction(Dead, *MD, AA->getTargetLibraryInfo(), 7308e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer &DeadStackObjects); 73183d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner ++NumFastStores; 73283d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner MadeChange = true; 73354c4735db3f973a85bc73e0a231f00ab18762c54Owen Anderson continue; 73483d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } 73583d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } 73681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 73783d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // Remove any dead non-memory-mutating instructions. 7388e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (isInstructionTriviallyDead(BBI, AA->getTargetLibraryInfo())) { 73983d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner Instruction *Inst = BBI++; 7408e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer DeleteDeadInstruction(Inst, *MD, AA->getTargetLibraryInfo(), 7418e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer &DeadStackObjects); 74283d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner ++NumFastOther; 74383d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner MadeChange = true; 74483d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner continue; 74583d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } 74681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 7471b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman if (isa<AllocaInst>(BBI)) { 7481b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman // Remove allocas from the list of dead stack objects; there can't be 7491b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman // any references before the definition. 7509e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DeadStackObjects.remove(BBI); 751e54874471cf565bbacdca69c95ae7287badc578fNuno Lopes continue; 752e54874471cf565bbacdca69c95ae7287badc578fNuno Lopes } 753e54874471cf565bbacdca69c95ae7287badc578fNuno Lopes 75486dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner if (CallSite CS = cast<Value>(BBI)) { 7551b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman // Remove allocation function calls from the list of dead stack objects; 7561b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman // there can't be any references before the definition. 7578e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (isAllocLikeFn(BBI, AA->getTargetLibraryInfo())) 7581b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman DeadStackObjects.remove(BBI); 7591b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman 76083d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // If this call does not access memory, it can't be loading any of our 76183d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // pointers. 762e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (AA->doesNotAccessMemory(CS)) 763df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson continue; 76481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 76586dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // If the call might load from any of our allocas, then any store above 76686dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // the call is live. 76786dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner SmallVector<Value*, 8> LiveAllocas; 7686e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng for (SmallSetVector<Value*, 16>::iterator I = DeadStackObjects.begin(), 7695fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner E = DeadStackObjects.end(); I != E; ++I) { 77086dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // See if the call site touches it. 77181856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson AliasAnalysis::ModRefResult A = 772e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AA->getModRefInfo(CS, *I, getPointerSize(*I, *AA)); 77381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 7743e8d0017996aeb08c5190b6b6d83f0a717526ab5Owen Anderson if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) 77586dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner LiveAllocas.push_back(*I); 77643b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 77781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 77886dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // If all of the allocas were clobbered by the call then we're not going 77986dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // to find anything else to process. 7803be7584f40cc822252e613af0c42dcb17e6a5d05Benjamin Kramer if (DeadStackObjects.size() == LiveAllocas.size()) 7811b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman break; 78281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 7833be7584f40cc822252e613af0c42dcb17e6a5d05Benjamin Kramer for (SmallVector<Value*, 8>::iterator I = LiveAllocas.begin(), 7843be7584f40cc822252e613af0c42dcb17e6a5d05Benjamin Kramer E = LiveAllocas.end(); I != E; ++I) 7853be7584f40cc822252e613af0c42dcb17e6a5d05Benjamin Kramer DeadStackObjects.remove(*I); 7863be7584f40cc822252e613af0c42dcb17e6a5d05Benjamin Kramer 78743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 78886dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner } 7898a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman 790d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner AliasAnalysis::Location LoadedLoc; 79181856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 79286dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // If we encounter a use of the pointer, it is no longer considered dead 79386dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner if (LoadInst *L = dyn_cast<LoadInst>(BBI)) { 79456efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman if (!L->isUnordered()) // Be conservative with atomic/volatile load 79556efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman break; 796d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner LoadedLoc = AA->getLocation(L); 79786dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) { 798d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner LoadedLoc = AA->getLocation(V); 79986dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(BBI)) { 800d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner LoadedLoc = AA->getLocationForSource(MTI); 80181856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson } else if (!BBI->mayReadFromMemory()) { 80281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson // Instruction doesn't read memory. Note that stores that weren't removed 80381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson // above will hit this case. 804925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner continue; 8058a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman } else { 8068a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman // Unknown inst; assume it clobbers everything. 8078a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman break; 80843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 8095d0392c6b370758750b397e254a6c6f028479969Duncan Sands 8105fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // Remove any allocas from the DeadPointer set that are loaded, as this 8115fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // makes any stores above the access live. 812d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner RemoveAccessedObjects(LoadedLoc, DeadStackObjects); 8135d0392c6b370758750b397e254a6c6f028479969Duncan Sands 8145fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // If all of the allocas were clobbered by the access then we're not going 8155fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // to find anything else to process. 8165fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner if (DeadStackObjects.empty()) 8175fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner break; 81843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 81981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 82043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson return MadeChange; 82143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 82243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 8235fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner/// RemoveAccessedObjects - Check to see if the specified location may alias any 8245fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner/// of the stack objects in the DeadStackObjects set. If so, they become live 8255fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner/// because the location is being loaded. 826d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattnervoid DSE::RemoveAccessedObjects(const AliasAnalysis::Location &LoadedLoc, 8276e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng SmallSetVector<Value*, 16> &DeadStackObjects) { 8285034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman const Value *UnderlyingPointer = GetUnderlyingObject(LoadedLoc.Ptr); 8295fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner 8305fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // A constant can't be in the dead pointer set. 8315fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner if (isa<Constant>(UnderlyingPointer)) 83242cb684f8d8440ffd79415280dcb7676d0b5f29aChris Lattner return; 83381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 8345fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // If the kill pointer can be easily reduced to an alloca, don't bother doing 8355fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // extraneous AA queries. 83642cb684f8d8440ffd79415280dcb7676d0b5f29aChris Lattner if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) { 8376e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng DeadStackObjects.remove(const_cast<Value*>(UnderlyingPointer)); 83842cb684f8d8440ffd79415280dcb7676d0b5f29aChris Lattner return; 8395fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner } 84081856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 8415fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner SmallVector<Value*, 16> NowLive; 8426e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng for (SmallSetVector<Value*, 16>::iterator I = DeadStackObjects.begin(), 8435fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner E = DeadStackObjects.end(); I != E; ++I) { 844d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner // See if the loaded location could alias the stack location. 845d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner AliasAnalysis::Location StackLoc(*I, getPointerSize(*I, *AA)); 846d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner if (!AA->isNoAlias(StackLoc, LoadedLoc)) 8475fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner NowLive.push_back(*I); 84843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 84943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 8505fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner for (SmallVector<Value*, 16>::iterator I = NowLive.begin(), E = NowLive.end(); 85143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson I != E; ++I) 8526e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng DeadStackObjects.remove(*I); 85343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 854