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" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 21d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SetVector.h" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 23a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson#include "llvm/Analysis/AliasAnalysis.h" 244d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky#include "llvm/Analysis/CaptureTracking.h" 258aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson#include "llvm/Analysis/Dominators.h" 26f006b183e2d2bebcf6968d1dd7350397c95b0325Victor Hernandez#include "llvm/Analysis/MemoryBuiltins.h" 27b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Analysis/MemoryDependenceAnalysis.h" 28a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner#include "llvm/Analysis/ValueTracking.h" 290b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 300b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 310b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 320b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/GlobalVariable.h" 330b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 340b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 35d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Pass.h" 36d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/Debug.h" 373dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky#include "llvm/Target/TargetLibraryInfo.h" 38b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson#include "llvm/Transforms/Utils/Local.h" 39b77c457cc87aeeb166995aed793a516e9e431703Owen Andersonusing namespace llvm; 40b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 41b77c457cc87aeeb166995aed793a516e9e431703Owen AndersonSTATISTIC(NumFastStores, "Number of stores deleted"); 42b77c457cc87aeeb166995aed793a516e9e431703Owen AndersonSTATISTIC(NumFastOther , "Number of other instrs removed"); 43b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 44b77c457cc87aeeb166995aed793a516e9e431703Owen Andersonnamespace { 453e8b6631e67e01e4960a7ba4668a50c596607473Chris Lattner struct DSE : public FunctionPass { 46e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AliasAnalysis *AA; 47e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MemoryDependenceAnalysis *MD; 48336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky DominatorTree *DT; 4997a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky const TargetLibraryInfo *TLI; 50e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 51b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson static char ID; // Pass identification, replacement for typeid 52336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky DSE() : FunctionPass(ID), AA(0), MD(0), DT(0) { 53081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeDSEPass(*PassRegistry::getPassRegistry()); 54081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 55b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 56b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson virtual bool runOnFunction(Function &F) { 57e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AA = &getAnalysis<AliasAnalysis>(); 58e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MD = &getAnalysis<MemoryDependenceAnalysis>(); 59336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky DT = &getAnalysis<DominatorTree>(); 6097a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky TLI = AA->getTargetLibraryInfo(); 6181856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 62e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner bool Changed = false; 63b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 6498df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner // Only check non-dead blocks. Dead blocks may have strange pointer 6598df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner // cycles that will confuse alias analysis. 66336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (DT->isReachableFromEntry(I)) 6798df4f9cf2dea81af1cc2e68f23b285d22cebc6aChris Lattner Changed |= runOnBasicBlock(*I); 6881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 69336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky AA = 0; MD = 0; DT = 0; 70b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return Changed; 71b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 7281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 73b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool runOnBasicBlock(BasicBlock &BB); 741ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner bool HandleFree(CallInst *F); 75925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner bool handleEndBlock(BasicBlock &BB); 76d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner void RemoveAccessedObjects(const AliasAnalysis::Location &LoadedLoc, 776e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng SmallSetVector<Value*, 16> &DeadStackObjects); 78b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 79b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const { 80b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.setPreservesCFG(); 818aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson AU.addRequired<DominatorTree>(); 82a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson AU.addRequired<AliasAnalysis>(); 83b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addRequired<MemoryDependenceAnalysis>(); 84e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AU.addPreserved<AliasAnalysis>(); 858aa895b19a64796a4c1f7cd0cb0750ad34263ea0Owen Anderson AU.addPreserved<DominatorTree>(); 86b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson AU.addPreserved<MemoryDependenceAnalysis>(); 87b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 88b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson }; 89b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 90b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 91844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar DSE::ID = 0; 922ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false) 932ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(DominatorTree) 942ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) 952ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 962ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(DSE, "dse", "Dead Store Elimination", false, false) 97844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 98f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen AndersonFunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } 99b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 1007c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner//===----------------------------------------------------------------------===// 1017c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner// Helper functions 1027c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner//===----------------------------------------------------------------------===// 1037c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 1047c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// DeleteDeadInstruction - Delete this instruction. Before we do, go through 1057c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// and zero out all the operands of this instruction. If any of them become 1067c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// dead, delete them and the computation tree that feeds them. 1077c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// 1087c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// If ValueSet is non-null, remove any deleted instructions from it as well. 1097c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// 1107c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattnerstatic void DeleteDeadInstruction(Instruction *I, 1117c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner MemoryDependenceAnalysis &MD, 1128e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer const TargetLibraryInfo *TLI, 1136e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng SmallSetVector<Value*, 16> *ValueSet = 0) { 1147c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner SmallVector<Instruction*, 32> NowDeadInsts; 11581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1167c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner NowDeadInsts.push_back(I); 1177c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner --NumFastOther; 11881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1197c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // Before we touch this instruction, remove it from memdep! 1207c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner do { 1217c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner Instruction *DeadInst = NowDeadInsts.pop_back_val(); 1227c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner ++NumFastOther; 12381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1247c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // This instruction is dead, zap it, in stages. Start by removing it from 1257c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // MemDep, which needs to know the operands and needs it to be in the 1267c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // function. 1277c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner MD.removeInstruction(DeadInst); 12881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1297c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) { 1307c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner Value *Op = DeadInst->getOperand(op); 1317c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner DeadInst->setOperand(op, 0); 13281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1337c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // If this operand just became dead, add it to the NowDeadInsts list. 1347c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner if (!Op->use_empty()) continue; 13581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1367c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner if (Instruction *OpI = dyn_cast<Instruction>(Op)) 1378e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (isInstructionTriviallyDead(OpI, TLI)) 1387c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner NowDeadInsts.push_back(OpI); 1397c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner } 14081856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1417c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner DeadInst->eraseFromParent(); 14281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 1436e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng if (ValueSet) ValueSet->remove(DeadInst); 1447c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner } while (!NowDeadInsts.empty()); 1457c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner} 1467c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 1477c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 14872987a274223e64482d8697b948e1c13a448198dChris Lattner/// hasMemoryWrite - Does this instruction write some memory? This only returns 14972987a274223e64482d8697b948e1c13a448198dChris Lattner/// true for things that we can analyze with other helpers below. 1503dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewyckystatic bool hasMemoryWrite(Instruction *I, const TargetLibraryInfo *TLI) { 15158571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (isa<StoreInst>(I)) 15258571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky return true; 15358571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 15458571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky switch (II->getIntrinsicID()) { 15565a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner default: 15665a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner return false; 15765a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::memset: 15865a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::memmove: 15965a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::memcpy: 16065a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::init_trampoline: 16165a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner case Intrinsic::lifetime_end: 16265a9ab4f8f75216f92a06ac2fe84d16ed7f0ccaeChris Lattner return true; 16358571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky } 16458571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky } 1653dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (CallSite CS = I) { 1663dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (Function *F = CS.getCalledFunction()) { 1673dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (TLI && TLI->has(LibFunc::strcpy) && 1683dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky F->getName() == TLI->getName(LibFunc::strcpy)) { 1693dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return true; 1703dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 1713dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (TLI && TLI->has(LibFunc::strncpy) && 1723dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky F->getName() == TLI->getName(LibFunc::strncpy)) { 1733dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return true; 1743dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 1753dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (TLI && TLI->has(LibFunc::strcat) && 1763dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky F->getName() == TLI->getName(LibFunc::strcat)) { 1773dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return true; 1783dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 1793dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (TLI && TLI->has(LibFunc::strncat) && 1803dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky F->getName() == TLI->getName(LibFunc::strncat)) { 1813dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return true; 1823dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 1833dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 1843dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 18558571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky return false; 18658571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky} 18758571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky 188cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner/// getLocForWrite - Return a Location stored to by the specified instruction. 1891582e7f1e255c19595f82cb447e52869196dec58Eli Friedman/// If isRemovable returns true, this function and getLocForRead completely 1901582e7f1e255c19595f82cb447e52869196dec58Eli Friedman/// describe the memory operations for this instruction. 191cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattnerstatic AliasAnalysis::Location 192cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris LattnergetLocForWrite(Instruction *Inst, AliasAnalysis &AA) { 193cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) 194cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AA.getLocation(SI); 19581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 196cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Inst)) { 197cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // memcpy/memmove/memset. 198cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner AliasAnalysis::Location Loc = AA.getLocationForDest(MI); 199cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we don't have target data around, an unknown size in Location means 200cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // that we should use the size of the pointee type. This isn't valid for 201cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // memset/memcpy, which writes more than an i8. 2023574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow if (Loc.Size == AliasAnalysis::UnknownSize && AA.getDataLayout() == 0) 203cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AliasAnalysis::Location(); 204cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return Loc; 205cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 20681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 207cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst); 208cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (II == 0) return AliasAnalysis::Location(); 20981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 210cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner switch (II->getIntrinsicID()) { 211cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner default: return AliasAnalysis::Location(); // Unhandled intrinsic. 212cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner case Intrinsic::init_trampoline: 213cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we don't have target data around, an unknown size in Location means 214cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // that we should use the size of the pointee type. This isn't valid for 215cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // init.trampoline, which writes more than an i8. 2163574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow if (AA.getDataLayout() == 0) return AliasAnalysis::Location(); 21781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 218cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // FIXME: We don't know the size of the trampoline, so we can't really 219cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // handle it here. 220cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AliasAnalysis::Location(II->getArgOperand(0)); 221cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner case Intrinsic::lifetime_end: { 222cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); 223cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner return AliasAnalysis::Location(II->getArgOperand(1), Len); 224cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 225cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 226cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner} 227cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 228cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// getLocForRead - Return the location read by the specified "hasMemoryWrite" 229cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// instruction if any. 23081856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Andersonstatic AliasAnalysis::Location 231cc10244d7725f191bdc91cd62befff0c97257c7bChris LattnergetLocForRead(Instruction *Inst, AliasAnalysis &AA) { 2323dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky assert(hasMemoryWrite(Inst, AA.getTargetLibraryInfo()) && 2333dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky "Unknown instruction case"); 23481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 235cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // The only instructions that both read and write are the mem transfer 236cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // instructions (memcpy/memmove). 237cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(Inst)) 238cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner return AA.getLocationForSource(MTI); 239cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner return AliasAnalysis::Location(); 240cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner} 241cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 242cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 243bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattner/// isRemovable - If the value of this instruction and the memory it writes to 244bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattner/// is unused, may we delete this instruction? 245bbdc3703a37c2be32ed23d4bb1b1e2bb14780643Chris Lattnerstatic bool isRemovable(Instruction *I) { 24656efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman // Don't remove volatile/atomic stores. 24758571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (StoreInst *SI = dyn_cast<StoreInst>(I)) 24856efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman return SI->isUnordered(); 24981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 2503dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 2513dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky switch (II->getIntrinsicID()) { 2523dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky default: llvm_unreachable("doesn't pass 'hasMemoryWrite' predicate"); 2533dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky case Intrinsic::lifetime_end: 2543dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky // Never remove dead lifetime_end's, e.g. because it is followed by a 2553dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky // free. 2563dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return false; 2573dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky case Intrinsic::init_trampoline: 2583dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky // Always safe to remove init_trampoline. 2593dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return true; 26081856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 2613dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky case Intrinsic::memset: 2623dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky case Intrinsic::memmove: 2633dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky case Intrinsic::memcpy: 2643dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky // Don't remove volatile memory intrinsics. 2653dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return !cast<MemIntrinsic>(II)->isVolatile(); 2663dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 26755ee75d57114c17460d364121a2ec3a5cf40e1d2Chris Lattner } 2683dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky 26924ab21c691fb98040318b9521cd1247c3e0b79ccNick Lewycky if (CallSite CS = I) 27024ab21c691fb98040318b9521cd1247c3e0b79ccNick Lewycky return CS.getInstruction()->use_empty(); 2713dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky 2723dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return false; 27358571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky} 27458571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky 2755ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper 2765ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper/// isShortenable - Returns true if this instruction can be safely shortened in 2775ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper/// length. 2785ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooperstatic bool isShortenable(Instruction *I) { 2795ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // Don't shorten stores for now 2805ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (isa<StoreInst>(I)) 2815ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return false; 282a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 2833dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 2843dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky switch (II->getIntrinsicID()) { 2853dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky default: return false; 2863dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky case Intrinsic::memset: 2873dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky case Intrinsic::memcpy: 2883dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky // Do shorten memory intrinsics. 2893dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return true; 2903dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 2915ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper } 2923dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky 2933dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky // Don't shorten libcalls calls for now. 2943dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky 2953dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return false; 2965ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper} 2975ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper 2987c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner/// getStoredPointerOperand - Return the pointer that is being written to. 2997c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattnerstatic Value *getStoredPointerOperand(Instruction *I) { 30058571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (StoreInst *SI = dyn_cast<StoreInst>(I)) 30158571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky return SI->getPointerOperand(); 30258571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) 3037c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner return MI->getDest(); 3043ccbb22eaf3f0deebc15ff7be992f090a6f0ba0bGabor Greif 3053dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 3063dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky switch (II->getIntrinsicID()) { 3073dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky default: llvm_unreachable("Unexpected intrinsic!"); 3083dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky case Intrinsic::init_trampoline: 3093dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return II->getArgOperand(0); 3103dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky } 311710c37c494229334f59b9be328366807db2a7d01Duncan Sands } 3123dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky 3131afd6bb93998d85582d85a0258bb9976061d86ddNick Lewycky CallSite CS = I; 3143dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky // All the supported functions so far happen to have dest as their first 3153dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky // argument. 3163dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky return CS.getArgument(0); 31758571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky} 31858571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky 319ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewyckystatic uint64_t getPointerSize(const Value *V, AliasAnalysis &AA) { 3209e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes uint64_t Size; 3213574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow if (getObjectSize(V, Size, AA.getDataLayout(), AA.getTargetLibraryInfo())) 3229e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes return Size; 323ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewycky return AliasAnalysis::UnknownSize; 3243161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner} 325e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner 3265ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Coopernamespace { 3275ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper enum OverwriteResult 3285ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper { 3295ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper OverwriteComplete, 3305ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper OverwriteEnd, 3315ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper OverwriteUnknown 3325ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper }; 3335ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper} 3345ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper 3355ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper/// isOverwrite - Return 'OverwriteComplete' if a store to the 'Later' location 336cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner/// completely overwrites a store to the 'Earlier' location. 337a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem/// 'OverwriteEnd' if the end of the 'Earlier' location is completely 3389e1154cf5b268b1036ad7611cd249647a76efb49Pete Cooper/// overwritten by 'Later', or 'OverwriteUnknown' if nothing can be determined 3395ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooperstatic OverwriteResult isOverwrite(const AliasAnalysis::Location &Later, 3405ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper const AliasAnalysis::Location &Earlier, 3415ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper AliasAnalysis &AA, 342ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewycky int64_t &EarlierOff, 343ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewycky int64_t &LaterOff) { 344a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner const Value *P1 = Earlier.Ptr->stripPointerCasts(); 345a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner const Value *P2 = Later.Ptr->stripPointerCasts(); 34681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 347a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // If the start pointers are the same, we just have to compare sizes to see if 348a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // the later store was larger than the earlier store. 349a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner if (P1 == P2) { 350a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // If we don't know the sizes of either access, then we can't do a 351a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // comparison. 352a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner if (Later.Size == AliasAnalysis::UnknownSize || 353a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner Earlier.Size == AliasAnalysis::UnknownSize) { 3543574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow // If we have no DataLayout information around, then the size of the store 355a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // is inferrable from the pointee type. If they are the same type, then 356a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // we know that the store is safe. 3573574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow if (AA.getDataLayout() == 0 && 3585ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper Later.Ptr->getType() == Earlier.Ptr->getType()) 3595ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteComplete; 360a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 3615ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteUnknown; 362a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner } 36381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 364a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // Make sure that the Later size is >= the Earlier size. 3655ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (Later.Size >= Earlier.Size) 3665ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteComplete; 367a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner } 36881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 369a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // Otherwise, we have to have size information, and the later store has to be 370a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // larger than the earlier one. 37198016511932510bd5ec5dad1319922d9daf18991Chris Lattner if (Later.Size == AliasAnalysis::UnknownSize || 372a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner Earlier.Size == AliasAnalysis::UnknownSize || 3733574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow AA.getDataLayout() == 0) 3745ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteUnknown; 37581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 3763161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // Check to see if the later store is to the entire object (either a global, 3773161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // an alloca, or a byval argument). If so, then it clearly overwrites any 3783161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // other store to the same object. 379a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman const DataLayout *TD = AA.getDataLayout(); 38081856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 381a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman const Value *UO1 = GetUnderlyingObject(P1, TD), 382a070d2a0355c4993240b5206ebc1d517c151331dDan Gohman *UO2 = GetUnderlyingObject(P2, TD); 38381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 3843161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // If we can't resolve the same pointers to the same object, then we can't 3853161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // analyze them at all. 3863161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner if (UO1 != UO2) 3875ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteUnknown; 38881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 3893161ae18670e2b66aa4a7bf4805b32ca6aff1757Chris Lattner // If the "Later" store is to a recognizable object, get its size. 390ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewycky uint64_t ObjectSize = getPointerSize(UO2, AA); 391ae10dd2859a3729e3518f043cf252dc8676ed165Nick Lewycky if (ObjectSize != AliasAnalysis::UnknownSize) 392c7e5a6a2c69ee2552242da2a70775acd7d8819aePete Cooper if (ObjectSize == Later.Size && ObjectSize >= Earlier.Size) 3935ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteComplete; 39481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 395a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // Okay, we have stores to two completely different pointers. Try to 396a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // decompose the pointer into a "base + constant_offset" form. If the base 397a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // pointers are equal, then we can reason about the two stores. 3985ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper EarlierOff = 0; 3995ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper LaterOff = 0; 400150c4a1a89478f36af776f9146288afd528b33daBill Wendling const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, TD); 401150c4a1a89478f36af776f9146288afd528b33daBill Wendling const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, TD); 40281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 403a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner // If the base pointers still differ, we have two completely different stores. 404a04096580a65b6cfbe12dabf6d695f7303750c0dChris Lattner if (BP1 != BP2) 4055ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteUnknown; 406e420449e80191051d6d1636883f2400cb0a8ace5Bill Wendling 407150c4a1a89478f36af776f9146288afd528b33daBill Wendling // The later store completely overlaps the earlier store if: 40881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson // 409150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 1. Both start at the same offset and the later one's size is greater than 410150c4a1a89478f36af776f9146288afd528b33daBill Wendling // or equal to the earlier one's, or 411150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 412150c4a1a89478f36af776f9146288afd528b33daBill Wendling // |--earlier--| 413150c4a1a89478f36af776f9146288afd528b33daBill Wendling // |-- later --| 41481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson // 415150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 2. The earlier store has an offset greater than the later offset, but which 416150c4a1a89478f36af776f9146288afd528b33daBill Wendling // still lies completely within the later store. 417150c4a1a89478f36af776f9146288afd528b33daBill Wendling // 418150c4a1a89478f36af776f9146288afd528b33daBill Wendling // |--earlier--| 419150c4a1a89478f36af776f9146288afd528b33daBill Wendling // |----- later ------| 42031d244ead52171632cc4649623b426dbea27040aBill Wendling // 42131d244ead52171632cc4649623b426dbea27040aBill Wendling // We have to be careful here as *Off is signed while *.Size is unsigned. 4221a4d58af0923123b655a6c0c553c62a266e1ebbcBill Wendling if (EarlierOff >= LaterOff && 423750d7616c6d9ed5a40de1ac8f74fb40afd82ebc6Craig Topper Later.Size >= Earlier.Size && 42431d244ead52171632cc4649623b426dbea27040aBill Wendling uint64_t(EarlierOff - LaterOff) + Earlier.Size <= Later.Size) 4255ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteComplete; 426a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 4275ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // The other interesting case is if the later store overwrites the end of 4285ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // the earlier store 4295ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // 4305ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // |--earlier--| 4315ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // |-- later --| 4325ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // 4335ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // In this case we may want to trim the size of earlier to avoid generating 4345ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // writes to addresses which will definitely be overwritten later 4355ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (LaterOff > EarlierOff && 4365ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper LaterOff < int64_t(EarlierOff + Earlier.Size) && 437de2e27cc52a9e47e0261dda6dfb54a32eefa90a0Pete Cooper int64_t(LaterOff + Later.Size) >= int64_t(EarlierOff + Earlier.Size)) 4385ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteEnd; 439150c4a1a89478f36af776f9146288afd528b33daBill Wendling 440150c4a1a89478f36af776f9146288afd528b33daBill Wendling // Otherwise, they don't completely overlap. 4415ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper return OverwriteUnknown; 44240dd12e7080c5df253fd70b468368e3144a43c0cChris Lattner} 44340dd12e7080c5df253fd70b468368e3144a43c0cChris Lattner 444cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// isPossibleSelfRead - If 'Inst' might be a self read (i.e. a noop copy of a 445cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// memory region into an identical pointer) then it doesn't actually make its 44681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson/// input dead in the traditional sense. Consider this case: 447cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// 448cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// memcpy(A <- B) 449cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// memcpy(A <- A) 450cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// 451cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// In this case, the second store to A does not make the first store to A dead. 452cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// The usual situation isn't an explicit A<-A store like this (which can be 453cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// trivially removed) but a case where two pointers may alias. 454cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// 455cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// This function detects when it is unsafe to remove a dependent instruction 456cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner/// because the DSE inducing instruction may be a self-read. 457cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattnerstatic bool isPossibleSelfRead(Instruction *Inst, 458cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner const AliasAnalysis::Location &InstStoreLoc, 459cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner Instruction *DepWrite, AliasAnalysis &AA) { 460cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // Self reads can only happen for instructions that read memory. Get the 461cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // location read. 462cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner AliasAnalysis::Location InstReadLoc = getLocForRead(Inst, AA); 463cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (InstReadLoc.Ptr == 0) return false; // Not a reading instruction. 46481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 465cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // If the read and written loc obviously don't alias, it isn't a read. 466cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (AA.isNoAlias(InstReadLoc, InstStoreLoc)) return false; 46781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 468cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // Okay, 'Inst' may copy over itself. However, we can still remove a the 469cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // DepWrite instruction if we can prove that it reads from the same location 470cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // as Inst. This handles useful cases like: 471cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // memcpy(A <- B) 472cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // memcpy(A <- B) 473cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // Here we don't know if A/B may alias, but we do know that B/B are must 474cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // aliases, so removing the first memcpy is safe (assuming it writes <= # 475cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // bytes as the second one. 476cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner AliasAnalysis::Location DepReadLoc = getLocForRead(DepWrite, AA); 47781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 478cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner if (DepReadLoc.Ptr && AA.isMustAlias(InstReadLoc.Ptr, DepReadLoc.Ptr)) 479cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner return false; 48081856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 481cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // If DepWrite doesn't read memory or if we can't prove it is a must alias, 482cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // then it can't be considered dead. 483cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner return true; 484cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner} 485cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner 4867c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 4877c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner//===----------------------------------------------------------------------===// 4887c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner// DSE Pass 4897c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner//===----------------------------------------------------------------------===// 4907c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner 491f6a05f949f39d94d846dff9bf5093a838c6ebc4bOwen Andersonbool DSE::runOnBasicBlock(BasicBlock &BB) { 492b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson bool MadeChange = false; 49381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 49440ef630a4626365faeef8696f611e18d1a69f63aChris Lattner // Do a top-down walk on the BB. 495565f96b196325e83f41a83c97bdc751e731de608Chris Lattner for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) { 496565f96b196325e83f41a83c97bdc751e731de608Chris Lattner Instruction *Inst = BBI++; 49781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 4981ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner // Handle 'free' calls specially. 49997a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky if (CallInst *F = isFreeCall(Inst, TLI)) { 5001ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner MadeChange |= HandleFree(F); 5011ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner continue; 5021ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner } 50381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 50472987a274223e64482d8697b948e1c13a448198dChris Lattner // If we find something that writes memory, get its memory dependence. 5053dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (!hasMemoryWrite(Inst, TLI)) 5066ca4cb37553fc8ab568d1695d2afc99cf100d777Owen Anderson continue; 5070f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner 508e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner MemDepResult InstDep = MD->getDependency(Inst); 50981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 510a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman // Ignore any store where we can't find a local dependence. 5115e600e67b11c55c204b3eec00798badc96ed720bChris Lattner // FIXME: cross-block DSE would be fun. :) 512b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman if (!InstDep.isDef() && !InstDep.isClobber()) 513cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner continue; 51481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 5150f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // If we're storing the same value back to a pointer that we just 5160f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // loaded from, then the store can be removed. 5170f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 5180f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) { 5190f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (SI->getPointerOperand() == DepLoad->getPointerOperand() && 52056efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman SI->getOperand(0) == DepLoad && isRemovable(SI)) { 521a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n " 522a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner << "LOAD: " << *DepLoad << "\n STORE: " << *SI << '\n'); 52381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 5240f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // DeleteDeadInstruction can delete the current instruction. Save BBI 5250f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner // in case we need it. 5260f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner WeakVH NextInst(BBI); 52781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 52897a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky DeleteDeadInstruction(SI, *MD, TLI); 52981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 5300f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner if (NextInst == 0) // Next instruction deleted. 5310f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner BBI = BB.begin(); 5320f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner else if (BBI != BB.begin()) // Revisit this instruction if possible. 5330f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner --BBI; 5340f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner ++NumFastStores; 5350f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner MadeChange = true; 5360f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner continue; 5370f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner } 5380f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner } 5390f53f592ad8b81bb5e28e0d0e8b9461ddfa3ae01Chris Lattner } 54081856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 541cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Figure out what location is being stored to. 542e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AliasAnalysis::Location Loc = getLocForWrite(Inst, *AA); 543cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 544cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we didn't get a useful location, fail. 545cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (Loc.Ptr == 0) 546cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner continue; 54781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 548b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman while (InstDep.isDef() || InstDep.isClobber()) { 549cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Get the memory clobbered by the instruction we depend on. MemDep will 550cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // skip any instructions that 'Loc' clearly doesn't interact with. If we 551cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // end up depending on a may- or must-aliased load, then we can't optimize 552cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // away the store and we bail out. However, if we depend on on something 553cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // that overwrites the memory location we *can* potentially optimize it. 554cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // 5557a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // Find out what memory location the dependent instruction stores. 556cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner Instruction *DepWrite = InstDep.getInst(); 557e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner AliasAnalysis::Location DepLoc = getLocForWrite(DepWrite, *AA); 558cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // If we didn't get a useful location, or if it isn't a size, bail out. 559cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (DepLoc.Ptr == 0) 560cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner break; 561cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner 562cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // If we find a write that is a) removable (i.e., non-volatile), b) is 563cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // completely obliterated by the store to 'Loc', and c) which we know that 564cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner // 'Inst' doesn't load from, then we can remove it. 565a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem if (isRemovable(DepWrite) && 566cc10244d7725f191bdc91cd62befff0c97257c7bChris Lattner !isPossibleSelfRead(Inst, Loc, DepWrite, *AA)) { 567a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem int64_t InstWriteOffset, DepWriteOffset; 568a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem OverwriteResult OR = isOverwrite(Loc, DepLoc, *AA, 569a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem DepWriteOffset, InstWriteOffset); 5705ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (OR == OverwriteComplete) { 5715ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " 5725ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper << *DepWrite << "\n KILLER: " << *Inst << '\n'); 5735ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper 5745ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // Delete the store and now-dead instructions that feed it. 57597a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky DeleteDeadInstruction(DepWrite, *MD, TLI); 5765ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper ++NumFastStores; 5775ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper MadeChange = true; 578a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 5795ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // DeleteDeadInstruction can delete the current instruction in loop 5805ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // cases, reset BBI. 5815ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper BBI = Inst; 5825ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (BBI != BB.begin()) 5835ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper --BBI; 5845ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper break; 5855ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper } else if (OR == OverwriteEnd && isShortenable(DepWrite)) { 5865ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // TODO: base this on the target vector size so that if the earlier 5875ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // store was too small to get vector writes anyway then its likely 5885ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // a good idea to shorten it 5895ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // Power of 2 vector writes are probably always a bad idea to optimize 5905ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // as any store/memset/memcpy is likely using vector instructions so 5915ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper // shortening it to not vector size is likely to be slower 5925ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper MemIntrinsic* DepIntrinsic = cast<MemIntrinsic>(DepWrite); 5935ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper unsigned DepWriteAlign = DepIntrinsic->getAlignment(); 5945ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper if (llvm::isPowerOf2_64(InstWriteOffset) || 5955ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper ((DepWriteAlign != 0) && InstWriteOffset % DepWriteAlign == 0)) { 596a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 5975ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper DEBUG(dbgs() << "DSE: Remove Dead Store:\n OW END: " 598a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem << *DepWrite << "\n KILLER (offset " 599a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem << InstWriteOffset << ", " 6005ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper << DepLoc.Size << ")" 6015ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper << *Inst << '\n'); 602a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 6035ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper Value* DepWriteLength = DepIntrinsic->getLength(); 6045ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper Value* TrimmedLength = ConstantInt::get(DepWriteLength->getType(), 605a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem InstWriteOffset - 6065ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper DepWriteOffset); 6075ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper DepIntrinsic->setLength(TrimmedLength); 6085ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper MadeChange = true; 6095ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper } 6105ccb0825ed1bdf6271ef451b8239e86d4ff635b1Pete Cooper } 611cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner } 61281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 613f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // If this is a may-aliased store that is clobbering the store value, we 614f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // can keep searching past it for another must-aliased pointer that stores 615f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // to the same location. For example, in: 616f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // store -> P 617f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // store -> Q 618f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // store -> P 619f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // we can remove the first store to P even though we don't know if P and Q 620f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner // alias. 621cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner if (DepWrite == &BB.front()) break; 62281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 623cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner // Can't look past this instruction if it might read 'Loc'. 624e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (AA->getModRefInfo(DepWrite, Loc) & AliasAnalysis::Ref) 625cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner break; 62681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 627e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner InstDep = MD->getPointerDependencyFrom(Loc, false, DepWrite, &BB); 62858571d663c8c7d57fae1054d21686d8c8a7c8a7aNick Lewycky } 629b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson } 63081856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 631565f96b196325e83f41a83c97bdc751e731de608Chris Lattner // If this block ends in a return, unwind, or unreachable, all allocas are 632565f96b196325e83f41a83c97bdc751e731de608Chris Lattner // dead at its end, which means stores to them are also dead. 63343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson if (BB.getTerminator()->getNumSuccessors() == 0) 634925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner MadeChange |= handleEndBlock(BB); 63581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 636b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson return MadeChange; 637b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson} 638b77c457cc87aeeb166995aed793a516e9e431703Owen Anderson 639336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky/// Find all blocks that will unconditionally lead to the block BB and append 640336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky/// them to F. 641336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewyckystatic void FindUnconditionalPreds(SmallVectorImpl<BasicBlock *> &Blocks, 642336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky BasicBlock *BB, DominatorTree *DT) { 643336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 644336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky BasicBlock *Pred = *I; 645c9b98ad7a7c3f2c098657a077a995912dce033e3Nick Lewycky if (Pred == BB) continue; 646336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky TerminatorInst *PredTI = Pred->getTerminator(); 647336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (PredTI->getNumSuccessors() != 1) 648336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky continue; 649336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky 650336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (DT->isReachableFromEntry(Pred)) 651336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Blocks.push_back(Pred); 652336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky } 653336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky} 654336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky 6551ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner/// HandleFree - Handle frees of entire structures whose dependency is a store 6561ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattner/// to a field of that structure. 6571ab4285b721a412692e96a493ef4f2b9223902f9Chris Lattnerbool DSE::HandleFree(CallInst *F) { 658a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman bool MadeChange = false; 659a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman 660336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky AliasAnalysis::Location Loc = AliasAnalysis::Location(F->getOperand(0)); 661336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky SmallVector<BasicBlock *, 16> Blocks; 662336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Blocks.push_back(F->getParent()); 663a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman 664336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky while (!Blocks.empty()) { 665336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky BasicBlock *BB = Blocks.pop_back_val(); 666336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Instruction *InstPt = BB->getTerminator(); 667336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (BB == F->getParent()) InstPt = F; 66881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 669336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky MemDepResult Dep = MD->getPointerDependencyFrom(Loc, false, InstPt, BB); 670336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky while (Dep.isDef() || Dep.isClobber()) { 671336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Instruction *Dependency = Dep.getInst(); 6723dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (!hasMemoryWrite(Dependency, TLI) || !isRemovable(Dependency)) 673336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky break; 67402ec6e51edf361e1030b71494a71de0a7a9931e7Duncan Sands 675336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Value *DepPointer = 676336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky GetUnderlyingObject(getStoredPointerOperand(Dependency)); 67781856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 678336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // Check for aliasing. 679336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (!AA->isMustAlias(F->getArgOperand(0), DepPointer)) 680336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky break; 681720a2ed6d99d5665cc1601426353c84cc76fffbbDan Gohman 682336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Instruction *Next = llvm::next(BasicBlock::iterator(Dependency)); 683336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky 684336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // DCE instructions only used to calculate that store 68597a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky DeleteDeadInstruction(Dependency, *MD, TLI); 686336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky ++NumFastStores; 687336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky MadeChange = true; 688336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky 689336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // Inst's old Dependency is now deleted. Compute the next dependency, 690336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // which may also be dead, as in 691336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // s[0] = 0; 692336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // s[1] = 0; // This has just been deleted. 693336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky // free(s); 694336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky Dep = MD->getPointerDependencyFrom(Loc, false, Next, BB); 695336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky } 696336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky 697336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky if (Dep.isNonLocal()) 698336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky FindUnconditionalPreds(Blocks, BB, DT); 699336b88dac8054d6ed6cda6d6198b7d4bb026b3e1Nick Lewycky } 70081856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 701a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman return MadeChange; 702a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson} 703a96c1f665af2d8bc8539e7d202b058cb0853c2b7Owen Anderson 7040d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramernamespace { 7050d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer struct CouldRef { 7060d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer typedef Value *argument_type; 7070d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer const CallSite CS; 7080d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer AliasAnalysis *AA; 7090d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer 7100d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer bool operator()(Value *I) { 7110d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer // See if the call site touches the value. 7120d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer AliasAnalysis::ModRefResult A = 7130d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer AA->getModRefInfo(CS, I, getPointerSize(I, *AA)); 7140d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer 7150d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer return A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref; 7160d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer } 7170d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer }; 7180d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer} 7190d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer 720666f6fe0ce93b8ac2f810ec2c171710834ac7185Owen Anderson/// handleEndBlock - Remove dead stores to stack-allocated locations in the 721bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// function end block. Ex: 722bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// %A = alloca i32 723bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ... 724bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// store i32 1, i32* %A 725bb3abf41a868357e95b639b34baebf802199e190Owen Anderson/// ret void 726925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattnerbool DSE::handleEndBlock(BasicBlock &BB) { 72743b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson bool MadeChange = false; 72881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 7295fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // Keep track of all of the stack objects that are dead at the end of the 7305fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // function. 7316e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng SmallSetVector<Value*, 16> DeadStackObjects; 73281856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 733925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // Find all of the alloca'd pointers in the entry block. 73443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson BasicBlock *Entry = BB.getParent()->begin(); 7354d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) { 7369e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes if (isa<AllocaInst>(I)) 7379e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DeadStackObjects.insert(I); 73881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 7394d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky // Okay, so these are dead heap objects, but if the pointer never escapes 7404d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky // then it's leaked by this function anyways. 74197a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky else if (isAllocLikeFn(I, TLI) && !PointerMayBeCaptured(I, true, true)) 7429e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DeadStackObjects.insert(I); 7434d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky } 7444d882aae2acc5194b47385c7cb2e0e9ddd202927Nick Lewycky 745925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // Treat byval arguments the same, stores to them are dead at the end of the 746925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner // function. 747a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson for (Function::arg_iterator AI = BB.getParent()->arg_begin(), 748a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson AE = BB.getParent()->arg_end(); AI != AE; ++AI) 749a34d8a0d83bb39f4058e5dea4558e69cc4eda37cOwen Anderson if (AI->hasByValAttr()) 7505fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner DeadStackObjects.insert(AI); 75181856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 75243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson // Scan the basic block backwards 75343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ 75443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson --BBI; 75581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 75683d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // If we find a store, check to see if it points into a dead stack value. 7573dbefbd9bb9801db3b8fda8e15d03f2659393135Nick Lewycky if (hasMemoryWrite(BBI, TLI) && isRemovable(BBI)) { 75883d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // See through pointer-to-pointer bitcasts 759b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman SmallVector<Value *, 4> Pointers; 760b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman GetUnderlyingObjects(getStoredPointerOperand(BBI), Pointers); 76183d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner 7627c80c15a8bc5ac24b1c7651344a22d62e4308c14Chris Lattner // Stores to stack values are valid candidates for removal. 763b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman bool AllDead = true; 764b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(), 765b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman E = Pointers.end(); I != E; ++I) 766b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman if (!DeadStackObjects.count(*I)) { 767b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman AllDead = false; 768b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman break; 769b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman } 770b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman 771b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman if (AllDead) { 77283d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner Instruction *Dead = BBI++; 77381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 774a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner DEBUG(dbgs() << "DSE: Dead Store at End of Block:\n DEAD: " 775b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman << *Dead << "\n Objects: "; 776b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(), 777b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman E = Pointers.end(); I != E; ++I) { 778b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman dbgs() << **I; 779b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman if (llvm::next(I) != E) 780b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman dbgs() << ", "; 781b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman } 782b401e3bd16c3d648464606d5e5b496dd61d12afcDan Gohman dbgs() << '\n'); 78381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 784a9d4da85d6136d42648884de45d3dbda4725ee84Chris Lattner // DCE instructions only used to calculate that store. 78597a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky DeleteDeadInstruction(Dead, *MD, TLI, &DeadStackObjects); 78683d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner ++NumFastStores; 78783d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner MadeChange = true; 78854c4735db3f973a85bc73e0a231f00ab18762c54Owen Anderson continue; 78983d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } 79083d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } 79181856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 79283d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // Remove any dead non-memory-mutating instructions. 79397a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky if (isInstructionTriviallyDead(BBI, TLI)) { 79483d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner Instruction *Inst = BBI++; 79597a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky DeleteDeadInstruction(Inst, *MD, TLI, &DeadStackObjects); 79683d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner ++NumFastOther; 79783d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner MadeChange = true; 79883d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner continue; 79983d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner } 80081856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 8011b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman if (isa<AllocaInst>(BBI)) { 8021b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman // Remove allocas from the list of dead stack objects; there can't be 8031b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman // any references before the definition. 8049e72a79ef4a9fcda482ce0b0e1f0bd6a4f16cffdNuno Lopes DeadStackObjects.remove(BBI); 805e54874471cf565bbacdca69c95ae7287badc578fNuno Lopes continue; 806e54874471cf565bbacdca69c95ae7287badc578fNuno Lopes } 807e54874471cf565bbacdca69c95ae7287badc578fNuno Lopes 80886dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner if (CallSite CS = cast<Value>(BBI)) { 8091b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman // Remove allocation function calls from the list of dead stack objects; 8101b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman // there can't be any references before the definition. 81197a1a6144721c2eec2323ff85a80f77b36b58c96Nick Lewycky if (isAllocLikeFn(BBI, TLI)) 8121b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman DeadStackObjects.remove(BBI); 8131b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman 81483d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // If this call does not access memory, it can't be loading any of our 81583d675940309b2df3ab16efd50f7e90ce4ead8e7Chris Lattner // pointers. 816e3c611085ecb4bc1f30f445e6b1eb736cf29fee1Chris Lattner if (AA->doesNotAccessMemory(CS)) 817df359c264eb717ea69ca8dbda91992d707928af0Owen Anderson continue; 81881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 81986dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // If the call might load from any of our allocas, then any store above 82086dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // the call is live. 8210d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer CouldRef Pred = { CS, AA }; 8220d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer DeadStackObjects.remove_if(Pred); 82381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 82486dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // If all of the allocas were clobbered by the call then we're not going 82586dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // to find anything else to process. 8260d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer if (DeadStackObjects.empty()) 8271b88fc012240d10af5a80571aa8def36796f7b18Eli Friedman break; 82881856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 82943b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson continue; 83086dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner } 8318a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman 832d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner AliasAnalysis::Location LoadedLoc; 83381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 83486dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner // If we encounter a use of the pointer, it is no longer considered dead 83586dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner if (LoadInst *L = dyn_cast<LoadInst>(BBI)) { 83656efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman if (!L->isUnordered()) // Be conservative with atomic/volatile load 83756efe24431b045be120d1fd5f6b0aa43a6b01c48Eli Friedman break; 838d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner LoadedLoc = AA->getLocation(L); 83986dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) { 840d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner LoadedLoc = AA->getLocation(V); 84186dc6c08cf72668b433ad207cf42cdd9a8fe822aChris Lattner } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(BBI)) { 842d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner LoadedLoc = AA->getLocationForSource(MTI); 84381856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson } else if (!BBI->mayReadFromMemory()) { 84481856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson // Instruction doesn't read memory. Note that stores that weren't removed 84581856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson // above will hit this case. 846925451e020781bf43b4711b2ab1122f54c68ae0bChris Lattner continue; 8478a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman } else { 8488a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman // Unknown inst; assume it clobbers everything. 8498a552bb85a5e9a6c250c0a899941fbd3ae7b5006Eli Friedman break; 85043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 8515d0392c6b370758750b397e254a6c6f028479969Duncan Sands 8525fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // Remove any allocas from the DeadPointer set that are loaded, as this 8535fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // makes any stores above the access live. 854d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattner RemoveAccessedObjects(LoadedLoc, DeadStackObjects); 8555d0392c6b370758750b397e254a6c6f028479969Duncan Sands 8565fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // If all of the allocas were clobbered by the access then we're not going 8575fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // to find anything else to process. 8585fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner if (DeadStackObjects.empty()) 8595fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner break; 86043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson } 86181856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 86243b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson return MadeChange; 86343b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 86443b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson 8650d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramernamespace { 8660d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer struct CouldAlias { 8670d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer typedef Value *argument_type; 8680d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer const AliasAnalysis::Location &LoadedLoc; 8690d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer AliasAnalysis *AA; 8700d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer 8710d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer bool operator()(Value *I) { 8720d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer // See if the loaded location could alias the stack location. 8730d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer AliasAnalysis::Location StackLoc(I, getPointerSize(I, *AA)); 8740d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer return !AA->isNoAlias(StackLoc, LoadedLoc); 8750d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer } 8760d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer }; 8770d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer} 8780d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer 8795fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner/// RemoveAccessedObjects - Check to see if the specified location may alias any 8805fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner/// of the stack objects in the DeadStackObjects set. If so, they become live 8815fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner/// because the location is being loaded. 882d8d35316dee5e642c976ff0984ce316cbe57cc4cChris Lattnervoid DSE::RemoveAccessedObjects(const AliasAnalysis::Location &LoadedLoc, 8836e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng SmallSetVector<Value*, 16> &DeadStackObjects) { 8845034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman const Value *UnderlyingPointer = GetUnderlyingObject(LoadedLoc.Ptr); 8855fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner 8865fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // A constant can't be in the dead pointer set. 8875fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner if (isa<Constant>(UnderlyingPointer)) 88842cb684f8d8440ffd79415280dcb7676d0b5f29aChris Lattner return; 88981856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 8905fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // If the kill pointer can be easily reduced to an alloca, don't bother doing 8915fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner // extraneous AA queries. 89242cb684f8d8440ffd79415280dcb7676d0b5f29aChris Lattner if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) { 8936e406d8f11307474bbfb8bd464f7b1a71876f9a3Evan Cheng DeadStackObjects.remove(const_cast<Value*>(UnderlyingPointer)); 89442cb684f8d8440ffd79415280dcb7676d0b5f29aChris Lattner return; 8955fb0fb397caeb711bbaf387e5d46f96856c14b5bChris Lattner } 89681856f7313cb8cd64e0c3746ebcc3337ade9e5eeOwen Anderson 8970d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer // Remove objects that could alias LoadedLoc. 8980d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer CouldAlias Pred = { LoadedLoc, AA }; 8990d05acf592565c0f64661e0b5307f51f31d6cbc1Benjamin Kramer DeadStackObjects.remove_if(Pred); 90043b2676cc22c1f337e015f46aacbd699d039cad9Owen Anderson} 901