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 18b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Transforms/Scalar.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SetVector.h" 21d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 22a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson#include "llvm/Analysis/AliasAnalysis.h" 234d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky#include "llvm/Analysis/CaptureTracking.h" 24f006b183e2d2bebcf6968d1dd7350397c95b0325Victor Hernandez#include "llvm/Analysis/MemoryBuiltins.h" 25b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Analysis/MemoryDependenceAnalysis.h" 26a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner#include "llvm/Analysis/ValueTracking.h" 270b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 280b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 2936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 300b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 310b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/GlobalVariable.h" 320b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 330b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 34d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Pass.h" 35d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/Debug.h" 363dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky#include "llvm/Target/TargetLibraryInfo.h" 37b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Transforms/Utils/Local.h" 38b77c457cc87aeeb166995aed793a516e9e431703Owen Andersonusing namespace llvm; 39b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 40dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "dse" 41dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 42b77c457cc87aeeb166995aed793a516e9e431703Owen AndersonSTATISTIC(NumFastStores, "Number of stores deleted"); 43b77c457cc87aeeb166995aed793a516e9e431703Owen AndersonSTATISTIC(NumFastOther , "Number of other instrs removed"); 44b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 45b77c457cc87aeeb166995aed793a516e9e431703Owen Andersonnamespace { 463e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct DSE : public FunctionPass { 47e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AliasAnalysis *AA; 48e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MemoryDependenceAnalysis *MD; 49336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky DominatorTree *DT; 5097a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky const TargetLibraryInfo *TLI; 51e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 52b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson static char ID; // Pass identification, replacement for typeid 53dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DSE() : FunctionPass(ID), AA(nullptr), MD(nullptr), DT(nullptr) { 54081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeDSEPass(*PassRegistry::getPassRegistry()); 55081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 56b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 5736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override { 5836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (skipOptnoneFunction(F)) 5936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 6036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 61e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AA = &getAnalysis<AliasAnalysis>(); 62e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MD = &getAnalysis<MemoryDependenceAnalysis>(); 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 6497a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky TLI = AA->getTargetLibraryInfo(); 6581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 66e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner bool Changed = false; 67b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 6898df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner // Only check non-dead blocks. Dead blocks may have strange pointer 6998df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner // cycles that will confuse alias analysis. 70336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (DT->isReachableFromEntry(I)) 7198df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner Changed |= runOnBasicBlock(*I); 7281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 73dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AA = nullptr; MD = nullptr; DT = nullptr; 74b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return Changed; 75b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 7681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 77b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool runOnBasicBlock(BasicBlock &BB); 781ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner bool HandleFree(CallInst *F); 79925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner bool handleEndBlock(BasicBlock &BB); 80d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner void RemoveAccessedObjects(const AliasAnalysis::Location &LoadedLoc, 816e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng SmallSetVector<Value*, 16> &DeadStackObjects); 82b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 8336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 84b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.setPreservesCFG(); 8536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addRequired<DominatorTreeWrapperPass>(); 86a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addRequired<AliasAnalysis>(); 87b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addRequired<MemoryDependenceAnalysis>(); 88e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AU.addPreserved<AliasAnalysis>(); 8936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addPreserved<DominatorTreeWrapperPass>(); 90b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addPreserved<MemoryDependenceAnalysis>(); 91b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 92b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson }; 93b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 94b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 95844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar DSE::ID = 0; 962ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false) 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 982ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) 992ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 1002ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(DSE, "dse", "Dead Store Elimination", false, false) 101844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 102f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen AndersonFunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } 103b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 1047c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner//===----------------------------------------------------------------------===// 1057c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner// Helper functions 1067c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner//===----------------------------------------------------------------------===// 1077c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 1087c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// DeleteDeadInstruction - Delete this instruction. Before we do, go through 1097c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// and zero out all the operands of this instruction. If any of them become 1107c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// dead, delete them and the computation tree that feeds them. 1117c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// 1127c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// If ValueSet is non-null, remove any deleted instructions from it as well. 1137c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// 1147c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattnerstatic void DeleteDeadInstruction(Instruction *I, 115dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MemoryDependenceAnalysis &MD, 116dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const TargetLibraryInfo *TLI, 117dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SmallSetVector<Value*, 16> *ValueSet = nullptr) { 1187c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner SmallVector<Instruction*, 32> NowDeadInsts; 11981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1207c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner NowDeadInsts.push_back(I); 1217c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner --NumFastOther; 12281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1237c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // Before we touch this instruction, remove it from memdep! 1247c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner do { 1257c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner Instruction *DeadInst = NowDeadInsts.pop_back_val(); 1267c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner ++NumFastOther; 12781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1287c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // This instruction is dead, zap it, in stages. Start by removing it from 1297c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // MemDep, which needs to know the operands and needs it to be in the 1307c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // function. 1317c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner MD.removeInstruction(DeadInst); 13281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1337c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) { 1347c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner Value *Op = DeadInst->getOperand(op); 135dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DeadInst->setOperand(op, nullptr); 13681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1377c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // If this operand just became dead, add it to the NowDeadInsts list. 1387c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner if (!Op->use_empty()) continue; 13981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1407c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner if (Instruction *OpI = dyn_cast<Instruction>(Op)) 1418e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (isInstructionTriviallyDead(OpI, TLI)) 1427c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner NowDeadInsts.push_back(OpI); 1437c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner } 14481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1457c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner DeadInst->eraseFromParent(); 14681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1476e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng if (ValueSet) ValueSet->remove(DeadInst); 1487c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner } while (!NowDeadInsts.empty()); 1497c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner} 1507c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 1517c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 15272987a274223e64482d8697b948e1c13a448198dChris Lattner/// hasMemoryWrite - Does this instruction write some memory? This only returns 15372987a274223e64482d8697b948e1c13a448198dChris Lattner/// true for things that we can analyze with other helpers below. 1543dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewyckystatic bool hasMemoryWrite(Instruction *I, const TargetLibraryInfo *TLI) { 15558571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (isa<StoreInst>(I)) 15658571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky return true; 15758571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 15858571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky switch (II->getIntrinsicID()) { 15965a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner default: 16065a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner return false; 16165a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::memset: 16265a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::memmove: 16365a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::memcpy: 16465a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::init_trampoline: 16565a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::lifetime_end: 16665a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner return true; 16758571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky } 16858571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky } 1693dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (CallSite CS = I) { 1703dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (Function *F = CS.getCalledFunction()) { 1713dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (TLI && TLI->has(LibFunc::strcpy) && 1723dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky F->getName() == TLI->getName(LibFunc::strcpy)) { 1733dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return true; 1743dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 1753dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (TLI && TLI->has(LibFunc::strncpy) && 1763dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky F->getName() == TLI->getName(LibFunc::strncpy)) { 1773dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return true; 1783dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 1793dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (TLI && TLI->has(LibFunc::strcat) && 1803dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky F->getName() == TLI->getName(LibFunc::strcat)) { 1813dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return true; 1823dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 1833dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (TLI && TLI->has(LibFunc::strncat) && 1843dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky F->getName() == TLI->getName(LibFunc::strncat)) { 1853dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return true; 1863dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 1873dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 1883dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 18958571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky return false; 19058571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky} 19158571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky 192cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner/// getLocForWrite - Return a Location stored to by the specified instruction. 1931582e7f1e255c19595f82cb447e52869196dec58Eli Friedman/// If isRemovable returns true, this function and getLocForRead completely 1941582e7f1e255c19595f82cb447e52869196dec58Eli Friedman/// describe the memory operations for this instruction. 195cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattnerstatic AliasAnalysis::Location 196cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris LattnergetLocForWrite(Instruction *Inst, AliasAnalysis &AA) { 19736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DataLayout *DL = AA.getDataLayout(); 198cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) 199cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AA.getLocation(SI); 20081856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 201cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Inst)) { 202cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // memcpy/memmove/memset. 203cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner AliasAnalysis::Location Loc = AA.getLocationForDest(MI); 204cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we don't have target data around, an unknown size in Location means 205cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // that we should use the size of the pointee type. This isn't valid for 206cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // memset/memcpy, which writes more than an i8. 207dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Loc.Size == AliasAnalysis::UnknownSize && DL == nullptr) 208cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AliasAnalysis::Location(); 209cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return Loc; 210cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 21181856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 212cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst); 213dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!II) return AliasAnalysis::Location(); 21481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 215cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner switch (II->getIntrinsicID()) { 216cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner default: return AliasAnalysis::Location(); // Unhandled intrinsic. 217cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner case Intrinsic::init_trampoline: 218cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we don't have target data around, an unknown size in Location means 219cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // that we should use the size of the pointee type. This isn't valid for 220cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // init.trampoline, which writes more than an i8. 221dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!DL) return AliasAnalysis::Location(); 22281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 223cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // FIXME: We don't know the size of the trampoline, so we can't really 224cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // handle it here. 225cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AliasAnalysis::Location(II->getArgOperand(0)); 226cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner case Intrinsic::lifetime_end: { 227cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); 228cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AliasAnalysis::Location(II->getArgOperand(1), Len); 229cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 230cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 231cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner} 232cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 233cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// getLocForRead - Return the location read by the specified "hasMemoryWrite" 234cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// instruction if any. 23581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Andersonstatic AliasAnalysis::Location 236cc10244d7725f191bdc91cd62befff0c97257c7bChris LattnergetLocForRead(Instruction *Inst, AliasAnalysis &AA) { 2373dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky assert(hasMemoryWrite(Inst, AA.getTargetLibraryInfo()) && 2383dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky "Unknown instruction case"); 23981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 240cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // The only instructions that both read and write are the mem transfer 241cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // instructions (memcpy/memmove). 242cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(Inst)) 243cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner return AA.getLocationForSource(MTI); 244cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner return AliasAnalysis::Location(); 245cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner} 246cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 247cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 248bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattner/// isRemovable - If the value of this instruction and the memory it writes to 249bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattner/// is unused, may we delete this instruction? 250bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattnerstatic bool isRemovable(Instruction *I) { 25156efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman // Don't remove volatile/atomic stores. 25258571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (StoreInst *SI = dyn_cast<StoreInst>(I)) 25356efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman return SI->isUnordered(); 25481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 2553dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 2563dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky switch (II->getIntrinsicID()) { 2573dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky default: llvm_unreachable("doesn't pass 'hasMemoryWrite' predicate"); 2583dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky case Intrinsic::lifetime_end: 2593dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky // Never remove dead lifetime_end's, e.g. because it is followed by a 2603dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky // free. 2613dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return false; 2623dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky case Intrinsic::init_trampoline: 2633dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky // Always safe to remove init_trampoline. 2643dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return true; 26581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 2663dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky case Intrinsic::memset: 2673dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky case Intrinsic::memmove: 2683dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky case Intrinsic::memcpy: 2693dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky // Don't remove volatile memory intrinsics. 2703dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return !cast<MemIntrinsic>(II)->isVolatile(); 2713dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 27255ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner } 2733dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky 27424ab21c691fb98040318b9521cd1247c3e0b79ccNick Lewycky if (CallSite CS = I) 27524ab21c691fb98040318b9521cd1247c3e0b79ccNick Lewycky return CS.getInstruction()->use_empty(); 2763dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky 2773dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return false; 27858571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky} 27958571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky 2805ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper 2815ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper/// isShortenable - Returns true if this instruction can be safely shortened in 2825ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper/// length. 2835ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooperstatic bool isShortenable(Instruction *I) { 2845ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // Don't shorten stores for now 2855ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (isa<StoreInst>(I)) 2865ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return false; 287a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 2883dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 2893dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky switch (II->getIntrinsicID()) { 2903dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky default: return false; 2913dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky case Intrinsic::memset: 2923dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky case Intrinsic::memcpy: 2933dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky // Do shorten memory intrinsics. 2943dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return true; 2953dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 2965ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper } 2973dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky 2983dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky // Don't shorten libcalls calls for now. 2993dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky 3003dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return false; 3015ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper} 3025ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper 3037c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// getStoredPointerOperand - Return the pointer that is being written to. 3047c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattnerstatic Value *getStoredPointerOperand(Instruction *I) { 30558571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (StoreInst *SI = dyn_cast<StoreInst>(I)) 30658571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky return SI->getPointerOperand(); 30758571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) 3087c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner return MI->getDest(); 3093ccbb22eaf3f0deebc15ff7be992f090a6f0ba0bGabor Greif 3103dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 3113dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky switch (II->getIntrinsicID()) { 3123dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky default: llvm_unreachable("Unexpected intrinsic!"); 3133dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky case Intrinsic::init_trampoline: 3143dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return II->getArgOperand(0); 3153dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 316710c37c494229334f59b9be328366807db2a7d01Duncan Sands } 3173dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky 3181afd6bb93998d85582d85a0258bb9976061d86ddNick Lewycky CallSite CS = I; 3193dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky // All the supported functions so far happen to have dest as their first 3203dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky // argument. 3213dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return CS.getArgument(0); 32258571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky} 32358571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky 324ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewyckystatic uint64_t getPointerSize(const Value *V, AliasAnalysis &AA) { 3259e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes uint64_t Size; 3263574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow if (getObjectSize(V, Size, AA.getDataLayout(), AA.getTargetLibraryInfo())) 3279e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return Size; 328ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewycky return AliasAnalysis::UnknownSize; 3293161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner} 330e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 3315ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Coopernamespace { 3325ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper enum OverwriteResult 3335ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper { 3345ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper OverwriteComplete, 3355ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper OverwriteEnd, 3365ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper OverwriteUnknown 3375ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper }; 3385ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper} 3395ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper 3405ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper/// isOverwrite - Return 'OverwriteComplete' if a store to the 'Later' location 341cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner/// completely overwrites a store to the 'Earlier' location. 342a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem/// 'OverwriteEnd' if the end of the 'Earlier' location is completely 3439e1154cf5b268b1036ad7611cd249647a76efb49Pete Cooper/// overwritten by 'Later', or 'OverwriteUnknown' if nothing can be determined 3445ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooperstatic OverwriteResult isOverwrite(const AliasAnalysis::Location &Later, 3455ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper const AliasAnalysis::Location &Earlier, 3465ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper AliasAnalysis &AA, 347ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewycky int64_t &EarlierOff, 348ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewycky int64_t &LaterOff) { 34936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DataLayout *DL = AA.getDataLayout(); 350a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner const Value *P1 = Earlier.Ptr->stripPointerCasts(); 351a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner const Value *P2 = Later.Ptr->stripPointerCasts(); 35281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 353a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // If the start pointers are the same, we just have to compare sizes to see if 354a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // the later store was larger than the earlier store. 355a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner if (P1 == P2) { 356a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // If we don't know the sizes of either access, then we can't do a 357a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // comparison. 358a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner if (Later.Size == AliasAnalysis::UnknownSize || 359a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner Earlier.Size == AliasAnalysis::UnknownSize) { 3603574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow // If we have no DataLayout information around, then the size of the store 361a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // is inferrable from the pointee type. If they are the same type, then 362a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // we know that the store is safe. 363dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (DL == nullptr && Later.Ptr->getType() == Earlier.Ptr->getType()) 3645ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteComplete; 365a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 3665ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteUnknown; 367a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner } 36881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 369a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // Make sure that the Later size is >= the Earlier size. 3705ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (Later.Size >= Earlier.Size) 3715ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteComplete; 372a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner } 37381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 374a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // Otherwise, we have to have size information, and the later store has to be 375a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // larger than the earlier one. 37698016511932510bd5ec5dad1319922d9daf18991Chris Lattner if (Later.Size == AliasAnalysis::UnknownSize || 377dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Earlier.Size == AliasAnalysis::UnknownSize || DL == nullptr) 3785ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteUnknown; 37981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 3803161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // Check to see if the later store is to the entire object (either a global, 38136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // an alloca, or a byval/inalloca argument). If so, then it clearly 38236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // overwrites any other store to the same object. 38336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const Value *UO1 = GetUnderlyingObject(P1, DL), 38436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines *UO2 = GetUnderlyingObject(P2, DL); 38581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 3863161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // If we can't resolve the same pointers to the same object, then we can't 3873161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // analyze them at all. 3883161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner if (UO1 != UO2) 3895ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteUnknown; 39081856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 3913161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // If the "Later" store is to a recognizable object, get its size. 392ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewycky uint64_t ObjectSize = getPointerSize(UO2, AA); 393ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewycky if (ObjectSize != AliasAnalysis::UnknownSize) 394c7e5a6a2c69ee2552242da2a70775acd7d8819aePete Cooper if (ObjectSize == Later.Size && ObjectSize >= Earlier.Size) 3955ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteComplete; 39681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 397a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // Okay, we have stores to two completely different pointers. Try to 398a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // decompose the pointer into a "base + constant_offset" form. If the base 399a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // pointers are equal, then we can reason about the two stores. 4005ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper EarlierOff = 0; 4015ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper LaterOff = 0; 40236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, DL); 40336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, DL); 40481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 405a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // If the base pointers still differ, we have two completely different stores. 406a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner if (BP1 != BP2) 4075ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteUnknown; 408e420449e80191051d6d1636883f2400cb0a8ace5Bill Wendling 409150c4a1a89478f36af776f9146288afd528b33daBill Wendling // The later store completely overlaps the earlier store if: 41081856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson // 411150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 1. Both start at the same offset and the later one's size is greater than 412150c4a1a89478f36af776f9146288afd528b33daBill Wendling // or equal to the earlier one's, or 413150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 414150c4a1a89478f36af776f9146288afd528b33daBill Wendling // |--earlier--| 415150c4a1a89478f36af776f9146288afd528b33daBill Wendling // |-- later --| 41681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson // 417150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 2. The earlier store has an offset greater than the later offset, but which 418150c4a1a89478f36af776f9146288afd528b33daBill Wendling // still lies completely within the later store. 419150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 420150c4a1a89478f36af776f9146288afd528b33daBill Wendling // |--earlier--| 421150c4a1a89478f36af776f9146288afd528b33daBill Wendling // |----- later ------| 42231d244ead52171632cc4649623b426dbea27040aBill Wendling // 42331d244ead52171632cc4649623b426dbea27040aBill Wendling // We have to be careful here as *Off is signed while *.Size is unsigned. 4241a4d58af0923123b655a6c0c553c62a266e1ebbcBill Wendling if (EarlierOff >= LaterOff && 425750d7616c6d9ed5a40de1ac8f74fb40afd82ebc6Craig Topper Later.Size >= Earlier.Size && 42631d244ead52171632cc4649623b426dbea27040aBill Wendling uint64_t(EarlierOff - LaterOff) + Earlier.Size <= Later.Size) 4275ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteComplete; 428a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 4295ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // The other interesting case is if the later store overwrites the end of 4305ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // the earlier store 4315ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // 4325ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // |--earlier--| 4335ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // |-- later --| 4345ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // 4355ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // In this case we may want to trim the size of earlier to avoid generating 4365ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // writes to addresses which will definitely be overwritten later 4375ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (LaterOff > EarlierOff && 4385ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper LaterOff < int64_t(EarlierOff + Earlier.Size) && 439de2e27cc52a9e47e0261dda6dfb54a32eefa90a0Pete Cooper int64_t(LaterOff + Later.Size) >= int64_t(EarlierOff + Earlier.Size)) 4405ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteEnd; 441150c4a1a89478f36af776f9146288afd528b33daBill Wendling 442150c4a1a89478f36af776f9146288afd528b33daBill Wendling // Otherwise, they don't completely overlap. 4435ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteUnknown; 44440dd12e7080c5df253fd70b468368e3144a43c0cChris Lattner} 44540dd12e7080c5df253fd70b468368e3144a43c0cChris Lattner 446cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// isPossibleSelfRead - If 'Inst' might be a self read (i.e. a noop copy of a 447cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// memory region into an identical pointer) then it doesn't actually make its 44881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson/// input dead in the traditional sense. Consider this case: 449cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// 450cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// memcpy(A <- B) 451cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// memcpy(A <- A) 452cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// 453cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// In this case, the second store to A does not make the first store to A dead. 454cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// The usual situation isn't an explicit A<-A store like this (which can be 455cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// trivially removed) but a case where two pointers may alias. 456cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// 457cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// This function detects when it is unsafe to remove a dependent instruction 458cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// because the DSE inducing instruction may be a self-read. 459cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattnerstatic bool isPossibleSelfRead(Instruction *Inst, 460cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner const AliasAnalysis::Location &InstStoreLoc, 461cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner Instruction *DepWrite, AliasAnalysis &AA) { 462cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // Self reads can only happen for instructions that read memory. Get the 463cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // location read. 464cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner AliasAnalysis::Location InstReadLoc = getLocForRead(Inst, AA); 465dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!InstReadLoc.Ptr) return false; // Not a reading instruction. 46681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 467cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // If the read and written loc obviously don't alias, it isn't a read. 468cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (AA.isNoAlias(InstReadLoc, InstStoreLoc)) return false; 46981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 470cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // Okay, 'Inst' may copy over itself. However, we can still remove a the 471cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // DepWrite instruction if we can prove that it reads from the same location 472cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // as Inst. This handles useful cases like: 473cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // memcpy(A <- B) 474cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // memcpy(A <- B) 475cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // Here we don't know if A/B may alias, but we do know that B/B are must 476cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // aliases, so removing the first memcpy is safe (assuming it writes <= # 477cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // bytes as the second one. 478cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner AliasAnalysis::Location DepReadLoc = getLocForRead(DepWrite, AA); 47981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 480cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (DepReadLoc.Ptr && AA.isMustAlias(InstReadLoc.Ptr, DepReadLoc.Ptr)) 481cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner return false; 48281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 483cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // If DepWrite doesn't read memory or if we can't prove it is a must alias, 484cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // then it can't be considered dead. 485cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner return true; 486cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner} 487cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 4887c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 4897c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner//===----------------------------------------------------------------------===// 4907c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner// DSE Pass 4917c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner//===----------------------------------------------------------------------===// 4927c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 493f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Andersonbool DSE::runOnBasicBlock(BasicBlock &BB) { 494b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool MadeChange = false; 49581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 49640ef630a4626365faeef8696f611e18d1a69f63aChris Lattner // Do a top-down walk on the BB. 497565f96b196325e83f41a83c97bdc751e731de608Chris Lattner for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) { 498565f96b196325e83f41a83c97bdc751e731de608Chris Lattner Instruction *Inst = BBI++; 49981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 5001ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner // Handle 'free' calls specially. 50197a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky if (CallInst *F = isFreeCall(Inst, TLI)) { 5021ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner MadeChange |= HandleFree(F); 5031ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner continue; 5041ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner } 50581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 50672987a274223e64482d8697b948e1c13a448198dChris Lattner // If we find something that writes memory, get its memory dependence. 5073dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (!hasMemoryWrite(Inst, TLI)) 5086ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson continue; 5090f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner 510e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MemDepResult InstDep = MD->getDependency(Inst); 51181856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 512a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman // Ignore any store where we can't find a local dependence. 5135e600e67b11c55c204b3eec00798badc96ed720bChris Lattner // FIXME: cross-block DSE would be fun. :) 514b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman if (!InstDep.isDef() && !InstDep.isClobber()) 515cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner continue; 51681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 5170f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // If we're storing the same value back to a pointer that we just 5180f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // loaded from, then the store can be removed. 5190f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 5200f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) { 5210f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (SI->getPointerOperand() == DepLoad->getPointerOperand() && 52256efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman SI->getOperand(0) == DepLoad && isRemovable(SI)) { 523a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n " 524a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner << "LOAD: " << *DepLoad << "\n STORE: " << *SI << '\n'); 52581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 5260f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // DeleteDeadInstruction can delete the current instruction. Save BBI 5270f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // in case we need it. 5280f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner WeakVH NextInst(BBI); 52981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 53097a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky DeleteDeadInstruction(SI, *MD, TLI); 53181856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 532dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!NextInst) // Next instruction deleted. 5330f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner BBI = BB.begin(); 5340f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner else if (BBI != BB.begin()) // Revisit this instruction if possible. 5350f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner --BBI; 5360f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner ++NumFastStores; 5370f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner MadeChange = true; 5380f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner continue; 5390f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner } 5400f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner } 5410f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner } 54281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 543cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Figure out what location is being stored to. 544e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AliasAnalysis::Location Loc = getLocForWrite(Inst, *AA); 545cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 546cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we didn't get a useful location, fail. 547dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Loc.Ptr) 548cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner continue; 54981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 550b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman while (InstDep.isDef() || InstDep.isClobber()) { 551cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Get the memory clobbered by the instruction we depend on. MemDep will 552cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // skip any instructions that 'Loc' clearly doesn't interact with. If we 553cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // end up depending on a may- or must-aliased load, then we can't optimize 554cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // away the store and we bail out. However, if we depend on on something 555cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // that overwrites the memory location we *can* potentially optimize it. 556cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // 5577a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // Find out what memory location the dependent instruction stores. 558cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner Instruction *DepWrite = InstDep.getInst(); 559e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AliasAnalysis::Location DepLoc = getLocForWrite(DepWrite, *AA); 560cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we didn't get a useful location, or if it isn't a size, bail out. 561dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!DepLoc.Ptr) 562cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner break; 563cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 564cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // If we find a write that is a) removable (i.e., non-volatile), b) is 565cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // completely obliterated by the store to 'Loc', and c) which we know that 566cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // 'Inst' doesn't load from, then we can remove it. 567a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem if (isRemovable(DepWrite) && 568cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner !isPossibleSelfRead(Inst, Loc, DepWrite, *AA)) { 569a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem int64_t InstWriteOffset, DepWriteOffset; 570a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem OverwriteResult OR = isOverwrite(Loc, DepLoc, *AA, 571a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem DepWriteOffset, InstWriteOffset); 5725ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (OR == OverwriteComplete) { 5735ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " 5745ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper << *DepWrite << "\n KILLER: " << *Inst << '\n'); 5755ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper 5765ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // Delete the store and now-dead instructions that feed it. 57797a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky DeleteDeadInstruction(DepWrite, *MD, TLI); 5785ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper ++NumFastStores; 5795ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper MadeChange = true; 580a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 5815ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // DeleteDeadInstruction can delete the current instruction in loop 5825ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // cases, reset BBI. 5835ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper BBI = Inst; 5845ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (BBI != BB.begin()) 5855ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper --BBI; 5865ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper break; 5875ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper } else if (OR == OverwriteEnd && isShortenable(DepWrite)) { 5885ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // TODO: base this on the target vector size so that if the earlier 5895ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // store was too small to get vector writes anyway then its likely 5905ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // a good idea to shorten it 5915ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // Power of 2 vector writes are probably always a bad idea to optimize 5925ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // as any store/memset/memcpy is likely using vector instructions so 5935ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // shortening it to not vector size is likely to be slower 5945ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper MemIntrinsic* DepIntrinsic = cast<MemIntrinsic>(DepWrite); 5955ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper unsigned DepWriteAlign = DepIntrinsic->getAlignment(); 5965ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (llvm::isPowerOf2_64(InstWriteOffset) || 5975ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper ((DepWriteAlign != 0) && InstWriteOffset % DepWriteAlign == 0)) { 598a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 5995ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper DEBUG(dbgs() << "DSE: Remove Dead Store:\n OW END: " 600a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem << *DepWrite << "\n KILLER (offset " 601a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem << InstWriteOffset << ", " 6025ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper << DepLoc.Size << ")" 6035ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper << *Inst << '\n'); 604a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 6055ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper Value* DepWriteLength = DepIntrinsic->getLength(); 6065ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper Value* TrimmedLength = ConstantInt::get(DepWriteLength->getType(), 607a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem InstWriteOffset - 6085ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper DepWriteOffset); 6095ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper DepIntrinsic->setLength(TrimmedLength); 6105ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper MadeChange = true; 6115ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper } 6125ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper } 613cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 61481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 615f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // If this is a may-aliased store that is clobbering the store value, we 616f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // can keep searching past it for another must-aliased pointer that stores 617f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // to the same location. For example, in: 618f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // store -> P 619f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // store -> Q 620f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // store -> P 621f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // we can remove the first store to P even though we don't know if P and Q 622f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // alias. 623cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (DepWrite == &BB.front()) break; 62481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 625cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Can't look past this instruction if it might read 'Loc'. 626e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (AA->getModRefInfo(DepWrite, Loc) & AliasAnalysis::Ref) 627cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner break; 62881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 629e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner InstDep = MD->getPointerDependencyFrom(Loc, false, DepWrite, &BB); 63058571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky } 631b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 63281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 633565f96b196325e83f41a83c97bdc751e731de608Chris Lattner // If this block ends in a return, unwind, or unreachable, all allocas are 634565f96b196325e83f41a83c97bdc751e731de608Chris Lattner // dead at its end, which means stores to them are also dead. 63543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (BB.getTerminator()->getNumSuccessors() == 0) 636925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner MadeChange |= handleEndBlock(BB); 63781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 638b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return MadeChange; 639b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 640b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 641336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky/// Find all blocks that will unconditionally lead to the block BB and append 642336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky/// them to F. 643336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewyckystatic void FindUnconditionalPreds(SmallVectorImpl<BasicBlock *> &Blocks, 644336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky BasicBlock *BB, DominatorTree *DT) { 645336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 646336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky BasicBlock *Pred = *I; 647c9b98ad7a7c3f2c098657a077a995912dce033e3Nick Lewycky if (Pred == BB) continue; 648336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky TerminatorInst *PredTI = Pred->getTerminator(); 649336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (PredTI->getNumSuccessors() != 1) 650336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky continue; 651336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky 652336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (DT->isReachableFromEntry(Pred)) 653336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Blocks.push_back(Pred); 654336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky } 655336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky} 656336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky 6571ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner/// HandleFree - Handle frees of entire structures whose dependency is a store 6581ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner/// to a field of that structure. 6591ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattnerbool DSE::HandleFree(CallInst *F) { 660a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman bool MadeChange = false; 661a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman 662336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky AliasAnalysis::Location Loc = AliasAnalysis::Location(F->getOperand(0)); 663336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky SmallVector<BasicBlock *, 16> Blocks; 664336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Blocks.push_back(F->getParent()); 665a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman 666336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky while (!Blocks.empty()) { 667336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky BasicBlock *BB = Blocks.pop_back_val(); 668336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Instruction *InstPt = BB->getTerminator(); 669336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (BB == F->getParent()) InstPt = F; 67081856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 671336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky MemDepResult Dep = MD->getPointerDependencyFrom(Loc, false, InstPt, BB); 672336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky while (Dep.isDef() || Dep.isClobber()) { 673336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Instruction *Dependency = Dep.getInst(); 6743dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (!hasMemoryWrite(Dependency, TLI) || !isRemovable(Dependency)) 675336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky break; 67602ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 677336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Value *DepPointer = 678336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky GetUnderlyingObject(getStoredPointerOperand(Dependency)); 67981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 680336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // Check for aliasing. 681336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (!AA->isMustAlias(F->getArgOperand(0), DepPointer)) 682336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky break; 683720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman 68436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *Next = std::next(BasicBlock::iterator(Dependency)); 685336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky 686336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // DCE instructions only used to calculate that store 68797a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky DeleteDeadInstruction(Dependency, *MD, TLI); 688336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky ++NumFastStores; 689336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky MadeChange = true; 690336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky 691336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // Inst's old Dependency is now deleted. Compute the next dependency, 692336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // which may also be dead, as in 693336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // s[0] = 0; 694336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // s[1] = 0; // This has just been deleted. 695336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // free(s); 696336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Dep = MD->getPointerDependencyFrom(Loc, false, Next, BB); 697336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky } 698336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky 699336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (Dep.isNonLocal()) 700336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky FindUnconditionalPreds(Blocks, BB, DT); 701336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky } 70281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 703a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman return MadeChange; 704a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson} 705a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 706666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson/// handleEndBlock - Remove dead stores to stack-allocated locations in the 707bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// function end block. Ex: 708bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// %A = alloca i32 709bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ... 710bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// store i32 1, i32* %A 711bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ret void 712925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattnerbool DSE::handleEndBlock(BasicBlock &BB) { 71343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool MadeChange = false; 71481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 7155fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // Keep track of all of the stack objects that are dead at the end of the 7165fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // function. 7176e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng SmallSetVector<Value*, 16> DeadStackObjects; 71881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 719925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // Find all of the alloca'd pointers in the entry block. 72043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BasicBlock *Entry = BB.getParent()->begin(); 7214d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) { 7229e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (isa<AllocaInst>(I)) 7239e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DeadStackObjects.insert(I); 72481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 7254d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky // Okay, so these are dead heap objects, but if the pointer never escapes 7264d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky // then it's leaked by this function anyways. 72797a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky else if (isAllocLikeFn(I, TLI) && !PointerMayBeCaptured(I, true, true)) 7289e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DeadStackObjects.insert(I); 7294d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky } 7304d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky 73136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Treat byval or inalloca arguments the same, stores to them are dead at the 73236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // end of the function. 733a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (Function::arg_iterator AI = BB.getParent()->arg_begin(), 734a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson AE = BB.getParent()->arg_end(); AI != AE; ++AI) 73536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (AI->hasByValOrInAllocaAttr()) 7365fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner DeadStackObjects.insert(AI); 73781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 73843b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Scan the basic block backwards 73943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ 74043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson --BBI; 74181856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 74283d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // If we find a store, check to see if it points into a dead stack value. 7433dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (hasMemoryWrite(BBI, TLI) && isRemovable(BBI)) { 74483d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // See through pointer-to-pointer bitcasts 745b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman SmallVector<Value *, 4> Pointers; 746b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman GetUnderlyingObjects(getStoredPointerOperand(BBI), Pointers); 74783d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner 7487c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // Stores to stack values are valid candidates for removal. 749b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman bool AllDead = true; 750b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(), 751b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman E = Pointers.end(); I != E; ++I) 752b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman if (!DeadStackObjects.count(*I)) { 753b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman AllDead = false; 754b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman break; 755b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman } 756b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman 757b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman if (AllDead) { 75883d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner Instruction *Dead = BBI++; 75981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 760a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner DEBUG(dbgs() << "DSE: Dead Store at End of Block:\n DEAD: " 761b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman << *Dead << "\n Objects: "; 762b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(), 763b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman E = Pointers.end(); I != E; ++I) { 764b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman dbgs() << **I; 76536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (std::next(I) != E) 766b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman dbgs() << ", "; 767b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman } 768b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman dbgs() << '\n'); 76981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 770a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner // DCE instructions only used to calculate that store. 77197a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky DeleteDeadInstruction(Dead, *MD, TLI, &DeadStackObjects); 77283d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner ++NumFastStores; 77383d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner MadeChange = true; 77454c4735db3f973a85bc73e0a231f00ab18762c54Owen Anderson continue; 77583d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } 77683d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } 77781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 77883d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // Remove any dead non-memory-mutating instructions. 77997a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky if (isInstructionTriviallyDead(BBI, TLI)) { 78083d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner Instruction *Inst = BBI++; 78197a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky DeleteDeadInstruction(Inst, *MD, TLI, &DeadStackObjects); 78283d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner ++NumFastOther; 78383d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner MadeChange = true; 78483d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner continue; 78583d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } 78681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 7871b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman if (isa<AllocaInst>(BBI)) { 7881b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman // Remove allocas from the list of dead stack objects; there can't be 7891b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman // any references before the definition. 7909e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DeadStackObjects.remove(BBI); 791e54874471cf565bbacdca69c95ae7287badc578fNuno Lopes continue; 792e54874471cf565bbacdca69c95ae7287badc578fNuno Lopes } 793e54874471cf565bbacdca69c95ae7287badc578fNuno Lopes 79486dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner if (CallSite CS = cast<Value>(BBI)) { 7951b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman // Remove allocation function calls from the list of dead stack objects; 7961b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman // there can't be any references before the definition. 79797a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky if (isAllocLikeFn(BBI, TLI)) 7981b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman DeadStackObjects.remove(BBI); 7991b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman 80083d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // If this call does not access memory, it can't be loading any of our 80183d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // pointers. 802e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (AA->doesNotAccessMemory(CS)) 803df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson continue; 80481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 80586dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // If the call might load from any of our allocas, then any store above 80686dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // the call is live. 80736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DeadStackObjects.remove_if([&](Value *I) { 80836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // See if the call site touches the value. 80936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AliasAnalysis::ModRefResult A = 81036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AA->getModRefInfo(CS, I, getPointerSize(I, *AA)); 81136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 81236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref; 81336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines }); 81481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 81586dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // If all of the allocas were clobbered by the call then we're not going 81686dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // to find anything else to process. 8170d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer if (DeadStackObjects.empty()) 8181b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman break; 81981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 82043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 82186dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner } 8228a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman 823d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner AliasAnalysis::Location LoadedLoc; 82481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 82586dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // If we encounter a use of the pointer, it is no longer considered dead 82686dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner if (LoadInst *L = dyn_cast<LoadInst>(BBI)) { 82756efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman if (!L->isUnordered()) // Be conservative with atomic/volatile load 82856efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman break; 829d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner LoadedLoc = AA->getLocation(L); 83086dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) { 831d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner LoadedLoc = AA->getLocation(V); 83286dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(BBI)) { 833d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner LoadedLoc = AA->getLocationForSource(MTI); 83481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson } else if (!BBI->mayReadFromMemory()) { 83581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson // Instruction doesn't read memory. Note that stores that weren't removed 83681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson // above will hit this case. 837925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner continue; 8388a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman } else { 8398a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman // Unknown inst; assume it clobbers everything. 8408a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman break; 84143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 8425d0392c6b370758750b397e254a6c6f028479969Duncan Sands 8435fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // Remove any allocas from the DeadPointer set that are loaded, as this 8445fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // makes any stores above the access live. 845d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner RemoveAccessedObjects(LoadedLoc, DeadStackObjects); 8465d0392c6b370758750b397e254a6c6f028479969Duncan Sands 8475fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // If all of the allocas were clobbered by the access then we're not going 8485fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // to find anything else to process. 8495fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner if (DeadStackObjects.empty()) 8505fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner break; 85143b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 85281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 85343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson return MadeChange; 85443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 85543b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 8565fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner/// RemoveAccessedObjects - Check to see if the specified location may alias any 8575fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner/// of the stack objects in the DeadStackObjects set. If so, they become live 8585fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner/// because the location is being loaded. 859d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattnervoid DSE::RemoveAccessedObjects(const AliasAnalysis::Location &LoadedLoc, 8606e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng SmallSetVector<Value*, 16> &DeadStackObjects) { 8615034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman const Value *UnderlyingPointer = GetUnderlyingObject(LoadedLoc.Ptr); 8625fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner 8635fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // A constant can't be in the dead pointer set. 8645fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner if (isa<Constant>(UnderlyingPointer)) 86542cb684f8d8440ffd79415280dcb7676d0b5f29aChris Lattner return; 86681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 8675fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // If the kill pointer can be easily reduced to an alloca, don't bother doing 8685fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // extraneous AA queries. 86942cb684f8d8440ffd79415280dcb7676d0b5f29aChris Lattner if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) { 8706e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng DeadStackObjects.remove(const_cast<Value*>(UnderlyingPointer)); 87142cb684f8d8440ffd79415280dcb7676d0b5f29aChris Lattner return; 8725fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner } 87381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 8740d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer // Remove objects that could alias LoadedLoc. 87536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DeadStackObjects.remove_if([&](Value *I) { 87636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // See if the loaded location could alias the stack location. 87736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AliasAnalysis::Location StackLoc(I, getPointerSize(I, *AA)); 87836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return !AA->isNoAlias(StackLoc, LoadedLoc); 87936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines }); 88043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 881