145dec48dc3725a8e5ca5cfdeeed941eea2e456f1Nick Lewycky//===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation -------------===// 278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// The LLVM Compiler Infrastructure 478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson//===----------------------------------------------------------------------===// 978e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 1078e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// This file implements an analysis that determines, for a given memory 116178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak// operation, what preceding memory operations it depends on. It builds on 1280b1f09693dd849620330da76b445fa0b3873dd1Owen Anderson// alias analysis information, and tries to provide a lazy, caching interface to 1378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// a common kind of alias information query. 1478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 1578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson//===----------------------------------------------------------------------===// 1678e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 1778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#include "llvm/Analysis/MemoryDependenceAnalysis.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 2078e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#include "llvm/Analysis/AliasAnalysis.h" 21e19e4baf3b4f145fad122de7e6a02ed3a68bc082Chris Lattner#include "llvm/Analysis/InstructionSimplify.h" 22f006b183e2d2bebcf6968d1dd7350397c95b0325Victor Hernandez#include "llvm/Analysis/MemoryBuiltins.h" 2305e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner#include "llvm/Analysis/PHITransAddr.h" 245034dd318a9dfa0dc45a3ac01e58e60f2aa2498dDan Gohman#include "llvm/Analysis/ValueTracking.h" 250b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 270b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 280b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 290b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 300b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 3136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/PredIteratorCache.h" 32d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/Debug.h" 3378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Andersonusing namespace llvm; 3478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 35dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "memdep" 36dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 37bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris LattnerSTATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses"); 38bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris LattnerSTATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses"); 390ec48ddef20deaa061152d86645972122beef605Chris LattnerSTATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses"); 406290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner 416290f5cac23399201f8785e5ca8b305e42a1342cChris LattnerSTATISTIC(NumCacheNonLocalPtr, 426290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner "Number of fully cached non-local ptr responses"); 436290f5cac23399201f8785e5ca8b305e42a1342cChris LattnerSTATISTIC(NumCacheDirtyNonLocalPtr, 446290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner "Number of cached, but dirty, non-local ptr responses"); 456290f5cac23399201f8785e5ca8b305e42a1342cChris LattnerSTATISTIC(NumUncacheNonLocalPtr, 466290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner "Number of uncached non-local ptr responses"); 4711dcd8d38de031c34380fd6ab7a0daacdefb263aChris LattnerSTATISTIC(NumCacheCompleteNonLocalPtr, 4811dcd8d38de031c34380fd6ab7a0daacdefb263aChris Lattner "Number of block queries that were completely cached"); 496290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner 50992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman// Limit for the number of instructions to scan in a block. 51d58b50b99b04bcb8199c2b0273618b6a37d61015Bill Wendlingstatic const int BlockScanLimit = 100; 52992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman 5378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Andersonchar MemoryDependenceAnalysis::ID = 0; 546178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 5578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// Register this pass... 562ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(MemoryDependenceAnalysis, "memdep", 57ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Memory Dependence Analysis", false, true) 582ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 592ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep", 602ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Memory Dependence Analysis", false, true) 6178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 624012fdda13710d21b415a79475adc2bbb6628527Chris LattnerMemoryDependenceAnalysis::MemoryDependenceAnalysis() 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines : FunctionPass(ID), PredCache() { 64081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry()); 654012fdda13710d21b415a79475adc2bbb6628527Chris Lattner} 664012fdda13710d21b415a79475adc2bbb6628527Chris LattnerMemoryDependenceAnalysis::~MemoryDependenceAnalysis() { 674012fdda13710d21b415a79475adc2bbb6628527Chris Lattner} 684012fdda13710d21b415a79475adc2bbb6628527Chris Lattner 694012fdda13710d21b415a79475adc2bbb6628527Chris Lattner/// Clean up memory in between runs 704012fdda13710d21b415a79475adc2bbb6628527Chris Lattnervoid MemoryDependenceAnalysis::releaseMemory() { 714012fdda13710d21b415a79475adc2bbb6628527Chris Lattner LocalDeps.clear(); 724012fdda13710d21b415a79475adc2bbb6628527Chris Lattner NonLocalDeps.clear(); 734012fdda13710d21b415a79475adc2bbb6628527Chris Lattner NonLocalPointerDeps.clear(); 744012fdda13710d21b415a79475adc2bbb6628527Chris Lattner ReverseLocalDeps.clear(); 754012fdda13710d21b415a79475adc2bbb6628527Chris Lattner ReverseNonLocalDeps.clear(); 764012fdda13710d21b415a79475adc2bbb6628527Chris Lattner ReverseNonLocalPtrDeps.clear(); 774012fdda13710d21b415a79475adc2bbb6628527Chris Lattner PredCache->clear(); 784012fdda13710d21b415a79475adc2bbb6628527Chris Lattner} 794012fdda13710d21b415a79475adc2bbb6628527Chris Lattner 804012fdda13710d21b415a79475adc2bbb6628527Chris Lattner 814012fdda13710d21b415a79475adc2bbb6628527Chris Lattner 8278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson/// getAnalysisUsage - Does not modify anything. It uses Alias Analysis. 8378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson/// 8478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Andersonvoid MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 8578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson AU.setPreservesAll(); 8678e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson AU.addRequiredTransitive<AliasAnalysis>(); 8778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson} 8878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 89d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattnerbool MemoryDependenceAnalysis::runOnFunction(Function &) { 90d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner AA = &getAnalysis<AliasAnalysis>(); 9136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); 92dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DL = DLP ? &DLP->getDataLayout() : nullptr; 9336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTreeWrapperPass *DTWP = 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 95dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DT = DTWP ? &DTWP->getDomTree() : nullptr; 96453f4f01302f00651aae2fc7658f6e23a2beadb0David Blaikie if (!PredCache) 974012fdda13710d21b415a79475adc2bbb6628527Chris Lattner PredCache.reset(new PredIteratorCache()); 98d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner return false; 99d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner} 100d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner 101d44745d24175079f0675c6199ab9929d19edd1aaChris Lattner/// RemoveFromReverseMap - This is a helper function that removes Val from 102d44745d24175079f0675c6199ab9929d19edd1aaChris Lattner/// 'Inst's set in ReverseMap. If the set becomes empty, remove Inst's entry. 103d44745d24175079f0675c6199ab9929d19edd1aaChris Lattnertemplate <typename KeyTy> 1046178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszakstatic void RemoveFromReverseMap(DenseMap<Instruction*, 1056a0dcc10778468b1556474aa43d4a86a14ab15d7Chris Lattner SmallPtrSet<KeyTy, 4> > &ReverseMap, 1066a0dcc10778468b1556474aa43d4a86a14ab15d7Chris Lattner Instruction *Inst, KeyTy Val) { 1076a0dcc10778468b1556474aa43d4a86a14ab15d7Chris Lattner typename DenseMap<Instruction*, SmallPtrSet<KeyTy, 4> >::iterator 108d44745d24175079f0675c6199ab9929d19edd1aaChris Lattner InstIt = ReverseMap.find(Inst); 109d44745d24175079f0675c6199ab9929d19edd1aaChris Lattner assert(InstIt != ReverseMap.end() && "Reverse map out of sync?"); 110d44745d24175079f0675c6199ab9929d19edd1aaChris Lattner bool Found = InstIt->second.erase(Val); 1118e68c3873549ca31533e2e3e40dda3a43cb79566Jeffrey Yasskin assert(Found && "Invalid reverse map!"); (void)Found; 112d44745d24175079f0675c6199ab9929d19edd1aaChris Lattner if (InstIt->second.empty()) 113d44745d24175079f0675c6199ab9929d19edd1aaChris Lattner ReverseMap.erase(InstIt); 114d44745d24175079f0675c6199ab9929d19edd1aaChris Lattner} 115d44745d24175079f0675c6199ab9929d19edd1aaChris Lattner 116533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman/// GetLocation - If the given instruction references a specific memory 117533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman/// location, fill in Loc with the details, otherwise set Loc.Ptr to null. 118533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman/// Return a ModRefInfo value describing the general behavior of the 119533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman/// instruction. 120533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohmanstatic 121533c2ad360eaaab2a0a25dab5a99255256b84814Dan GohmanAliasAnalysis::ModRefResult GetLocation(const Instruction *Inst, 122533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman AliasAnalysis::Location &Loc, 123533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman AliasAnalysis *AA) { 124533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 125667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman if (LI->isUnordered()) { 126667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman Loc = AA->getLocation(LI); 127667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman return AliasAnalysis::Ref; 1287f19e5db5f4f730f72c248282b7c00e6cdaf6782Jakub Staszak } 1297f19e5db5f4f730f72c248282b7c00e6cdaf6782Jakub Staszak if (LI->getOrdering() == Monotonic) { 130667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman Loc = AA->getLocation(LI); 131533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman return AliasAnalysis::ModRef; 132533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman } 133667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman Loc = AliasAnalysis::Location(); 134667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman return AliasAnalysis::ModRef; 135533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman } 136533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman 137533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 138667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman if (SI->isUnordered()) { 139667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman Loc = AA->getLocation(SI); 140667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman return AliasAnalysis::Mod; 1417f19e5db5f4f730f72c248282b7c00e6cdaf6782Jakub Staszak } 1427f19e5db5f4f730f72c248282b7c00e6cdaf6782Jakub Staszak if (SI->getOrdering() == Monotonic) { 143667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman Loc = AA->getLocation(SI); 144533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman return AliasAnalysis::ModRef; 145533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman } 146667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman Loc = AliasAnalysis::Location(); 147667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman return AliasAnalysis::ModRef; 148533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman } 149533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman 150533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman if (const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) { 1516d8eb156e6be727570b300bac7712f745a318c7dDan Gohman Loc = AA->getLocation(V); 152533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman return AliasAnalysis::ModRef; 153533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman } 154533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman 1558e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (const CallInst *CI = isFreeCall(Inst, AA->getTargetLibraryInfo())) { 156533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman // calls to free() deallocate the entire structure 157533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman Loc = AliasAnalysis::Location(CI->getArgOperand(0)); 158533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman return AliasAnalysis::Mod; 159533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman } 160533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman 161533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) 162533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman switch (II->getIntrinsicID()) { 163533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman case Intrinsic::lifetime_start: 164533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman case Intrinsic::lifetime_end: 165533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman case Intrinsic::invariant_start: 166533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman Loc = AliasAnalysis::Location(II->getArgOperand(1), 167533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman cast<ConstantInt>(II->getArgOperand(0)) 168533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman ->getZExtValue(), 169533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman II->getMetadata(LLVMContext::MD_tbaa)); 170533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman // These intrinsics don't really modify the memory, but returning Mod 171533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman // will allow them to be handled conservatively. 172533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman return AliasAnalysis::Mod; 173533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman case Intrinsic::invariant_end: 174533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman Loc = AliasAnalysis::Location(II->getArgOperand(2), 175533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman cast<ConstantInt>(II->getArgOperand(1)) 176533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman ->getZExtValue(), 177533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman II->getMetadata(LLVMContext::MD_tbaa)); 178533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman // These intrinsics don't really modify the memory, but returning Mod 179533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman // will allow them to be handled conservatively. 180533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman return AliasAnalysis::Mod; 181533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman default: 182533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman break; 183533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman } 184533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman 185533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman // Otherwise, just do the coarse-grained thing that always works. 186533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman if (Inst->mayWriteToMemory()) 187533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman return AliasAnalysis::ModRef; 188533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman if (Inst->mayReadFromMemory()) 189533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman return AliasAnalysis::Ref; 190533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman return AliasAnalysis::NoModRef; 191533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman} 192bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner 1938ef57c5faf77890828ac439482420646b2a0beb8Chris Lattner/// getCallSiteDependencyFrom - Private helper for finding the local 1948ef57c5faf77890828ac439482420646b2a0beb8Chris Lattner/// dependencies of a call site. 195fd3dcbea06f934572a3ba02821b1485eb7a073aaChris LattnerMemDepResult MemoryDependenceAnalysis:: 19620d6f0982ad33818cfa141f80157ac13e36d5550Chris LattnergetCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, 19720d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner BasicBlock::iterator ScanIt, BasicBlock *BB) { 198992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman unsigned Limit = BlockScanLimit; 199992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman 200642a9e3436dfe2afcaee6fb734d02c006d32ba3aOwen Anderson // Walk backwards through the block, looking for dependencies 2015391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner while (ScanIt != BB->begin()) { 202992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman // Limit the amount of scanning we do so we don't end up with quadratic 2036178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak // running time on extreme testcases. 204992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman --Limit; 205992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman if (!Limit) 206992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman return MemDepResult::getUnknown(); 207992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman 2085391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner Instruction *Inst = --ScanIt; 2096178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 2105f323207971da23e2f78dd61d383e9d506fd9d6cOwen Anderson // If this inst is a memory op, get the pointer it accessed 211c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman AliasAnalysis::Location Loc; 212533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman AliasAnalysis::ModRefResult MR = GetLocation(Inst, Loc, AA); 213533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman if (Loc.Ptr) { 214533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman // A simple instruction. 215533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman if (AA->getModRefInfo(CS, Loc) != AliasAnalysis::NoModRef) 216533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman return MemDepResult::getClobber(Inst); 217533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman continue; 218533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman } 219533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman 220533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman if (CallSite InstCS = cast<Value>(Inst)) { 221f6cec85a4b40094fc8fd5182d88cd01e92f12444Owen Anderson // Debug intrinsics don't cause dependences. 222497cb6fd4c9505f49842edd3f754f967b5fd9401Dale Johannesen if (isa<DbgInfoIntrinsic>(Inst)) continue; 223b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner // If these two calls do not interfere, look past it. 22420d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner switch (AA->getModRefInfo(CS, InstCS)) { 22520d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner case AliasAnalysis::NoModRef: 2265fa417c7904f7394d4e6dcb86e366c86867bcb5aDan Gohman // If the two calls are the same, return InstCS as a Def, so that 2275fa417c7904f7394d4e6dcb86e366c86867bcb5aDan Gohman // CS can be found redundant and eliminated. 228533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman if (isReadOnlyCall && !(MR & AliasAnalysis::Mod) && 2295fa417c7904f7394d4e6dcb86e366c86867bcb5aDan Gohman CS.getInstruction()->isIdenticalToWhenDefined(Inst)) 2305fa417c7904f7394d4e6dcb86e366c86867bcb5aDan Gohman return MemDepResult::getDef(Inst); 2315fa417c7904f7394d4e6dcb86e366c86867bcb5aDan Gohman 2325fa417c7904f7394d4e6dcb86e366c86867bcb5aDan Gohman // Otherwise if the two calls don't interact (e.g. InstCS is readnone) 2335fa417c7904f7394d4e6dcb86e366c86867bcb5aDan Gohman // keep scanning. 2348dff60e96a0b3044628511b0e43a59788de56b9dNadav Rotem continue; 23520d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner default: 236b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner return MemDepResult::getClobber(Inst); 23720d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner } 238cfbb634225007b2eddfbfcbf2adff2291b9c03bdChris Lattner } 2398dff60e96a0b3044628511b0e43a59788de56b9dNadav Rotem 2408dff60e96a0b3044628511b0e43a59788de56b9dNadav Rotem // If we could not obtain a pointer for the instruction and the instruction 2418dff60e96a0b3044628511b0e43a59788de56b9dNadav Rotem // touches memory then assume that this is a dependency. 2428dff60e96a0b3044628511b0e43a59788de56b9dNadav Rotem if (MR != AliasAnalysis::NoModRef) 2438dff60e96a0b3044628511b0e43a59788de56b9dNadav Rotem return MemDepResult::getClobber(Inst); 2445f323207971da23e2f78dd61d383e9d506fd9d6cOwen Anderson } 2458dff60e96a0b3044628511b0e43a59788de56b9dNadav Rotem 246a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman // No dependence found. If this is the entry block of the function, it is 247a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman // unknown, otherwise it is non-local. 2487ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner if (BB != &BB->getParent()->getEntryBlock()) 2497ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner return MemDepResult::getNonLocal(); 250b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman return MemDepResult::getNonFuncLocal(); 2515f323207971da23e2f78dd61d383e9d506fd9d6cOwen Anderson} 2525f323207971da23e2f78dd61d383e9d506fd9d6cOwen Anderson 253cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner/// isLoadLoadClobberIfExtendedToFullWidth - Return true if LI is a load that 254cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner/// would fully overlap MemLoc if done as a wider legal integer load. 255cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner/// 256cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner/// MemLocBase, MemLocOffset are lazily computed here the first time the 257cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner/// base/offs of memloc is needed. 2586178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszakstatic bool 259cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris LattnerisLoadLoadClobberIfExtendedToFullWidth(const AliasAnalysis::Location &MemLoc, 260cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner const Value *&MemLocBase, 261cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner int64_t &MemLocOffs, 2624034e14985af013f71f7884fa275415a3be27778Chris Lattner const LoadInst *LI, 26336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DataLayout *DL) { 264cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // If we have no target data, we can't do this. 265dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!DL) return false; 266cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner 267cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // If we haven't already computed the base/offset of MemLoc, do so now. 268dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!MemLocBase) 26936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MemLocBase = GetPointerBaseWithConstantOffset(MemLoc.Ptr, MemLocOffs, DL); 270cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner 2714034e14985af013f71f7884fa275415a3be27778Chris Lattner unsigned Size = MemoryDependenceAnalysis:: 2724034e14985af013f71f7884fa275415a3be27778Chris Lattner getLoadLoadClobberFullWidthSize(MemLocBase, MemLocOffs, MemLoc.Size, 27336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LI, *DL); 2744034e14985af013f71f7884fa275415a3be27778Chris Lattner return Size != 0; 2754034e14985af013f71f7884fa275415a3be27778Chris Lattner} 2764034e14985af013f71f7884fa275415a3be27778Chris Lattner 2774034e14985af013f71f7884fa275415a3be27778Chris Lattner/// getLoadLoadClobberFullWidthSize - This is a little bit of analysis that 2784034e14985af013f71f7884fa275415a3be27778Chris Lattner/// looks at a memory location for a load (specified by MemLocBase, Offs, 2794034e14985af013f71f7884fa275415a3be27778Chris Lattner/// and Size) and compares it against a load. If the specified load could 2804034e14985af013f71f7884fa275415a3be27778Chris Lattner/// be safely widened to a larger integer load that is 1) still efficient, 2814034e14985af013f71f7884fa275415a3be27778Chris Lattner/// 2) safe for the target, and 3) would provide the specified memory 2824034e14985af013f71f7884fa275415a3be27778Chris Lattner/// location value, then this function returns the size in bytes of the 2834034e14985af013f71f7884fa275415a3be27778Chris Lattner/// load width to use. If not, this returns zero. 2844034e14985af013f71f7884fa275415a3be27778Chris Lattnerunsigned MemoryDependenceAnalysis:: 2854034e14985af013f71f7884fa275415a3be27778Chris LattnergetLoadLoadClobberFullWidthSize(const Value *MemLocBase, int64_t MemLocOffs, 2864034e14985af013f71f7884fa275415a3be27778Chris Lattner unsigned MemLocSize, const LoadInst *LI, 28736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const DataLayout &DL) { 288667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman // We can only extend simple integer loads. 289667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman if (!isa<IntegerType>(LI->getType()) || !LI->isSimple()) return 0; 2907bce462c15356229e13d78d14560feaac30a0f5fKostya Serebryany 2917bce462c15356229e13d78d14560feaac30a0f5fKostya Serebryany // Load widening is hostile to ThreadSanitizer: it may cause false positives 2927bce462c15356229e13d78d14560feaac30a0f5fKostya Serebryany // or make the reports more cryptic (access sizes are wrong). 2937bce462c15356229e13d78d14560feaac30a0f5fKostya Serebryany if (LI->getParent()->getParent()->getAttributes(). 2948eec41fc778e99d42172a7f6de76faa43a6d8847Kostya Serebryany hasAttribute(AttributeSet::FunctionIndex, Attribute::SanitizeThread)) 2957bce462c15356229e13d78d14560feaac30a0f5fKostya Serebryany return 0; 2966178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 297cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // Get the base of this load. 298cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner int64_t LIOffs = 0; 2996178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak const Value *LIBase = 30036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines GetPointerBaseWithConstantOffset(LI->getPointerOperand(), LIOffs, &DL); 3016178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 302cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // If the two pointers are not based on the same pointer, we can't tell that 303cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // they are related. 3044034e14985af013f71f7884fa275415a3be27778Chris Lattner if (LIBase != MemLocBase) return 0; 3056178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 306cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // Okay, the two values are based on the same pointer, but returned as 307cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // no-alias. This happens when we have things like two byte loads at "P+1" 308cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // and "P+3". Check to see if increasing the size of the "LI" load up to its 309cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // alignment (or the largest native integer type) will allow us to load all 310cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // the bits required by MemLoc. 3116178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 312cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // If MemLoc is before LI, then no widening of LI will help us out. 3134034e14985af013f71f7884fa275415a3be27778Chris Lattner if (MemLocOffs < LIOffs) return 0; 3146178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 315cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // Get the alignment of the load in bytes. We assume that it is safe to load 316cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // any legal integer up to this size without a problem. For example, if we're 317cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // looking at an i8 load on x86-32 that is known 1024 byte aligned, we can 318cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // widen it up to an i32 load. If it is known 2-byte aligned, we can widen it 319cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // to i16. 320cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner unsigned LoadAlign = LI->getAlignment(); 321cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner 3224034e14985af013f71f7884fa275415a3be27778Chris Lattner int64_t MemLocEnd = MemLocOffs+MemLocSize; 3236178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 324cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // If no amount of rounding up will let MemLoc fit into LI, then bail out. 3254034e14985af013f71f7884fa275415a3be27778Chris Lattner if (LIOffs+LoadAlign < MemLocEnd) return 0; 3266178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 327cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // This is the size of the load to try. Start with the next larger power of 328cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // two. 329cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner unsigned NewLoadByteSize = LI->getType()->getPrimitiveSizeInBits()/8U; 330cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner NewLoadByteSize = NextPowerOf2(NewLoadByteSize); 3316178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 332cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner while (1) { 333cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // If this load size is bigger than our known alignment or would not fit 334cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // into a native integer register, then we fail. 335cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner if (NewLoadByteSize > LoadAlign || 33636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines !DL.fitsInLegalInteger(NewLoadByteSize*8)) 3374034e14985af013f71f7884fa275415a3be27778Chris Lattner return 0; 338cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner 3390ca032b03dc3a862670461651b3a950d1f14991bKostya Serebryany if (LIOffs+NewLoadByteSize > MemLocEnd && 340831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling LI->getParent()->getParent()->getAttributes(). 3418eec41fc778e99d42172a7f6de76faa43a6d8847Kostya Serebryany hasAttribute(AttributeSet::FunctionIndex, Attribute::SanitizeAddress)) 3420ca032b03dc3a862670461651b3a950d1f14991bKostya Serebryany // We will be reading past the location accessed by the original program. 3430ca032b03dc3a862670461651b3a950d1f14991bKostya Serebryany // While this is safe in a regular build, Address Safety analysis tools 3440ca032b03dc3a862670461651b3a950d1f14991bKostya Serebryany // may start reporting false warnings. So, don't do widening. 3450ca032b03dc3a862670461651b3a950d1f14991bKostya Serebryany return 0; 3460ca032b03dc3a862670461651b3a950d1f14991bKostya Serebryany 347cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // If a load of this width would include all of MemLoc, then we succeed. 348cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner if (LIOffs+NewLoadByteSize >= MemLocEnd) 3494034e14985af013f71f7884fa275415a3be27778Chris Lattner return NewLoadByteSize; 3506178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 351cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner NewLoadByteSize <<= 1; 352cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner } 353cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner} 354cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner 355e79be944c8ced0a0cb80ede8cb9f97e4fdc6778fChris Lattner/// getPointerDependencyFrom - Return the instruction on which a memory 356cd5c123a1d8723dbd5d493210c0a56890bffe409Dan Gohman/// location depends. If isLoad is true, this routine ignores may-aliases with 357cd5c123a1d8723dbd5d493210c0a56890bffe409Dan Gohman/// read-only operations. If isLoad is false, this routine ignores may-aliases 358985dac65791b9f6f631bdd51c18fe66592a67469Shuxin Yang/// with reads from read-only locations. If possible, pass the query 359985dac65791b9f6f631bdd51c18fe66592a67469Shuxin Yang/// instruction as well; this function may take advantage of the metadata 360985dac65791b9f6f631bdd51c18fe66592a67469Shuxin Yang/// annotated to the query instruction to refine the result. 361fd3dcbea06f934572a3ba02821b1485eb7a073aaChris LattnerMemDepResult MemoryDependenceAnalysis:: 3626178e5f50c0c8be26913cd93238a5035a39cdf37Jakub StaszakgetPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, 363985dac65791b9f6f631bdd51c18fe66592a67469Shuxin Yang BasicBlock::iterator ScanIt, BasicBlock *BB, 364985dac65791b9f6f631bdd51c18fe66592a67469Shuxin Yang Instruction *QueryInst) { 3657ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner 366dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const Value *MemLocBase = nullptr; 367cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner int64_t MemLocOffset = 0; 368992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman unsigned Limit = BlockScanLimit; 369985dac65791b9f6f631bdd51c18fe66592a67469Shuxin Yang bool isInvariantLoad = false; 370985dac65791b9f6f631bdd51c18fe66592a67469Shuxin Yang if (isLoad && QueryInst) { 371985dac65791b9f6f631bdd51c18fe66592a67469Shuxin Yang LoadInst *LI = dyn_cast<LoadInst>(QueryInst); 372dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (LI && LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr) 373985dac65791b9f6f631bdd51c18fe66592a67469Shuxin Yang isInvariantLoad = true; 374985dac65791b9f6f631bdd51c18fe66592a67469Shuxin Yang } 375992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman 3766290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // Walk backwards through the basic block, looking for dependencies. 3775391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner while (ScanIt != BB->begin()) { 3782999b2f2ccc3a48c834dffe19bb39c67641a3afdYunzhong Gao Instruction *Inst = --ScanIt; 3792999b2f2ccc3a48c834dffe19bb39c67641a3afdYunzhong Gao 3802999b2f2ccc3a48c834dffe19bb39c67641a3afdYunzhong Gao if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) 3812999b2f2ccc3a48c834dffe19bb39c67641a3afdYunzhong Gao // Debug intrinsics don't (and can't) cause dependencies. 3822999b2f2ccc3a48c834dffe19bb39c67641a3afdYunzhong Gao if (isa<DbgInfoIntrinsic>(II)) continue; 3832999b2f2ccc3a48c834dffe19bb39c67641a3afdYunzhong Gao 384992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman // Limit the amount of scanning we do so we don't end up with quadratic 385992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman // running time on extreme testcases. 386992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman --Limit; 387992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman if (!Limit) 388992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman return MemDepResult::getUnknown(); 389992205ac71e214562beffd1e84716f0f7ccb3bd9Eli Friedman 3901ffb70f21d109c01f81e34feb5e134ea1bcaf551Chris Lattner if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) { 391b62f792e78df12a43029352eb4c7cde9d456c67eOwen Anderson // If we reach a lifetime begin or end marker, then the query ends here 392b62f792e78df12a43029352eb4c7cde9d456c67eOwen Anderson // because the value is undefined. 39309981982f13085d5e7fd5fb8f87b4a626d770c5fChris Lattner if (II->getIntrinsicID() == Intrinsic::lifetime_start) { 3949ff5a23186f8761d9e5b4b5adf6fae9ce7d63860Owen Anderson // FIXME: This only considers queries directly on the invariant-tagged 3959ff5a23186f8761d9e5b4b5adf6fae9ce7d63860Owen Anderson // pointer, not on query pointers that are indexed off of them. It'd 396cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // be nice to handle that at some point (the right approach is to use 397cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // GetPointerBaseWithConstantOffset). 398d5c7f7cb5e15a7382cd163cb191db898510226c8Chris Lattner if (AA->isMustAlias(AliasAnalysis::Location(II->getArgOperand(1)), 399d5c7f7cb5e15a7382cd163cb191db898510226c8Chris Lattner MemLoc)) 400b62f792e78df12a43029352eb4c7cde9d456c67eOwen Anderson return MemDepResult::getDef(II); 40109981982f13085d5e7fd5fb8f87b4a626d770c5fChris Lattner continue; 4024bc737c5ef120e27834b92a86939331f370ba49cOwen Anderson } 4034bc737c5ef120e27834b92a86939331f370ba49cOwen Anderson } 4044bc737c5ef120e27834b92a86939331f370ba49cOwen Anderson 405cfbb634225007b2eddfbfcbf2adff2291b9c03bdChris Lattner // Values depend on loads if the pointers are must aliased. This means that 406cfbb634225007b2eddfbfcbf2adff2291b9c03bdChris Lattner // a load depends on another must aliased load from the same value. 407b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 408667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman // Atomic loads have complications involved. 409667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman // FIXME: This is overly conservative. 410667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman if (!LI->isUnordered()) 411667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman return MemDepResult::getClobber(LI); 412667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman 4136d8eb156e6be727570b300bac7712f745a318c7dDan Gohman AliasAnalysis::Location LoadLoc = AA->getLocation(LI); 4146178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 415b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner // If we found a pointer, check if it could be the same as our pointer. 416cd5c123a1d8723dbd5d493210c0a56890bffe409Dan Gohman AliasAnalysis::AliasResult R = AA->alias(LoadLoc, MemLoc); 4176178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 4181f821512fc1441480b3355305e0da5267073fe1cChris Lattner if (isLoad) { 419cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner if (R == AliasAnalysis::NoAlias) { 420cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // If this is an over-aligned integer load (for example, 421cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // "load i8* %P, align 4") see if it would obviously overlap with the 422cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // queried location if widened to a larger load (e.g. if the queried 423cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // location is 1 byte at P+1). If so, return it as a load/load 424cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // clobber result, allowing the client to decide to widen the load if 425cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // it wants to. 426db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner if (IntegerType *ITy = dyn_cast<IntegerType>(LI->getType())) 427cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner if (LI->getAlignment()*8 > ITy->getPrimitiveSizeInBits() && 428cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner isLoadLoadClobberIfExtendedToFullWidth(MemLoc, MemLocBase, 42936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MemLocOffset, LI, DL)) 430cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner return MemDepResult::getClobber(Inst); 4316178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 432cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner continue; 433cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner } 4346178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 4351f821512fc1441480b3355305e0da5267073fe1cChris Lattner // Must aliased loads are defs of each other. 4361f821512fc1441480b3355305e0da5267073fe1cChris Lattner if (R == AliasAnalysis::MustAlias) 4371f821512fc1441480b3355305e0da5267073fe1cChris Lattner return MemDepResult::getDef(Inst); 4381f821512fc1441480b3355305e0da5267073fe1cChris Lattner 439a3351a0e5db0b5b2c53920f2f15d3e862fecfad3Dan Gohman#if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting loads 440a3351a0e5db0b5b2c53920f2f15d3e862fecfad3Dan Gohman // in terms of clobbering loads, but since it does this by looking 441a3351a0e5db0b5b2c53920f2f15d3e862fecfad3Dan Gohman // at the clobbering load directly, it doesn't know about any 442a3351a0e5db0b5b2c53920f2f15d3e862fecfad3Dan Gohman // phi translation that may have happened along the way. 443a3351a0e5db0b5b2c53920f2f15d3e862fecfad3Dan Gohman 4441f821512fc1441480b3355305e0da5267073fe1cChris Lattner // If we have a partial alias, then return this as a clobber for the 4451f821512fc1441480b3355305e0da5267073fe1cChris Lattner // client to handle. 4461f821512fc1441480b3355305e0da5267073fe1cChris Lattner if (R == AliasAnalysis::PartialAlias) 4471f821512fc1441480b3355305e0da5267073fe1cChris Lattner return MemDepResult::getClobber(Inst); 448a3351a0e5db0b5b2c53920f2f15d3e862fecfad3Dan Gohman#endif 4496178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 4501f821512fc1441480b3355305e0da5267073fe1cChris Lattner // Random may-alias loads don't depend on each other without a 4511f821512fc1441480b3355305e0da5267073fe1cChris Lattner // dependence. 452a161ab06d9e194bbc048b04998e64a8f8a14e49cChris Lattner continue; 4531f821512fc1441480b3355305e0da5267073fe1cChris Lattner } 454cd5c123a1d8723dbd5d493210c0a56890bffe409Dan Gohman 455cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner // Stores don't depend on other no-aliased accesses. 456cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner if (R == AliasAnalysis::NoAlias) 457cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner continue; 458cb5fd743a95898ddefd75b6d104f5e91c0d50b23Chris Lattner 459cd5c123a1d8723dbd5d493210c0a56890bffe409Dan Gohman // Stores don't alias loads from read-only memory. 4601f821512fc1441480b3355305e0da5267073fe1cChris Lattner if (AA->pointsToConstantMemory(LoadLoc)) 461cd5c123a1d8723dbd5d493210c0a56890bffe409Dan Gohman continue; 462cd5c123a1d8723dbd5d493210c0a56890bffe409Dan Gohman 4631f821512fc1441480b3355305e0da5267073fe1cChris Lattner // Stores depend on may/must aliased loads. 464b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner return MemDepResult::getDef(Inst); 465b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner } 4666178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 467b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 468667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman // Atomic stores have complications involved. 469667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman // FIXME: This is overly conservative. 470667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman if (!SI->isUnordered()) 471667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman return MemDepResult::getClobber(SI); 472667ccf231b57857ea9e36f1d93bd895242d58284Eli Friedman 473ab9cf1282baf559771183304ffc9959882e17ebbChris Lattner // If alias analysis can tell that this store is guaranteed to not modify 474ab9cf1282baf559771183304ffc9959882e17ebbChris Lattner // the query pointer, ignore it. Use getModRefInfo to handle cases where 475ab9cf1282baf559771183304ffc9959882e17ebbChris Lattner // the query pointer points to constant memory etc. 476c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman if (AA->getModRefInfo(SI, MemLoc) == AliasAnalysis::NoModRef) 477ab9cf1282baf559771183304ffc9959882e17ebbChris Lattner continue; 478ab9cf1282baf559771183304ffc9959882e17ebbChris Lattner 479ab9cf1282baf559771183304ffc9959882e17ebbChris Lattner // Ok, this store might clobber the query pointer. Check to see if it is 480ab9cf1282baf559771183304ffc9959882e17ebbChris Lattner // a must alias: in this case, we want to return this as a def. 4816d8eb156e6be727570b300bac7712f745a318c7dDan Gohman AliasAnalysis::Location StoreLoc = AA->getLocation(SI); 4826178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 483b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner // If we found a pointer, check if it could be the same as our pointer. 4846d8eb156e6be727570b300bac7712f745a318c7dDan Gohman AliasAnalysis::AliasResult R = AA->alias(StoreLoc, MemLoc); 4856178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 486b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner if (R == AliasAnalysis::NoAlias) 487b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner continue; 4882cd195291722ad0153125a6c032c96e361d8c48eDan Gohman if (R == AliasAnalysis::MustAlias) 4892cd195291722ad0153125a6c032c96e361d8c48eDan Gohman return MemDepResult::getDef(Inst); 490985dac65791b9f6f631bdd51c18fe66592a67469Shuxin Yang if (isInvariantLoad) 491985dac65791b9f6f631bdd51c18fe66592a67469Shuxin Yang continue; 4922cd195291722ad0153125a6c032c96e361d8c48eDan Gohman return MemDepResult::getClobber(Inst); 493a161ab06d9e194bbc048b04998e64a8f8a14e49cChris Lattner } 494237a8287454389a5b940e18c1efb2201fc443208Chris Lattner 495237a8287454389a5b940e18c1efb2201fc443208Chris Lattner // If this is an allocation, and if we know that the accessed pointer is to 496b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner // the allocation, return Def. This means that there is no dependence and 497237a8287454389a5b940e18c1efb2201fc443208Chris Lattner // the access can be optimized based on that. For example, a load could 498237a8287454389a5b940e18c1efb2201fc443208Chris Lattner // turn into undef. 4995c78736f85579aa6de38cba2742ea13ff9f79e70Victor Hernandez // Note: Only determine this to be a malloc if Inst is the malloc call, not 5005c78736f85579aa6de38cba2742ea13ff9f79e70Victor Hernandez // a subsequent bitcast of the malloc call result. There can be stores to 5015c78736f85579aa6de38cba2742ea13ff9f79e70Victor Hernandez // the malloced memory between the malloc call and its bitcast uses, and we 5025c78736f85579aa6de38cba2742ea13ff9f79e70Victor Hernandez // need to continue scanning until the malloc call. 50384451a110da981adfff2792c3aee5df322864da6Bob Wilson const TargetLibraryInfo *TLI = AA->getTargetLibraryInfo(); 50484451a110da981adfff2792c3aee5df322864da6Bob Wilson if (isa<AllocaInst>(Inst) || isNoAliasFn(Inst, TLI)) { 50536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, DL); 5066178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 507d5c7f7cb5e15a7382cd163cb191db898510226c8Chris Lattner if (AccessPtr == Inst || AA->isMustAlias(Inst, AccessPtr)) 50846e8312fb733338e9af4db3757a1a8beddeae15aVictor Hernandez return MemDepResult::getDef(Inst); 5092d5c28da0d14883cd0cd6fcf38d7e28040b634c0Bob Wilson // Be conservative if the accessed pointer may alias the allocation. 5102d5c28da0d14883cd0cd6fcf38d7e28040b634c0Bob Wilson if (AA->alias(Inst, AccessPtr) != AliasAnalysis::NoAlias) 5112d5c28da0d14883cd0cd6fcf38d7e28040b634c0Bob Wilson return MemDepResult::getClobber(Inst); 51284451a110da981adfff2792c3aee5df322864da6Bob Wilson // If the allocation is not aliased and does not read memory (like 51384451a110da981adfff2792c3aee5df322864da6Bob Wilson // strdup), it is safe to ignore. 51484451a110da981adfff2792c3aee5df322864da6Bob Wilson if (isa<AllocaInst>(Inst) || 51584451a110da981adfff2792c3aee5df322864da6Bob Wilson isMallocLikeFn(Inst, TLI) || isCallocLikeFn(Inst, TLI)) 51684451a110da981adfff2792c3aee5df322864da6Bob Wilson continue; 51746e8312fb733338e9af4db3757a1a8beddeae15aVictor Hernandez } 51846e8312fb733338e9af4db3757a1a8beddeae15aVictor Hernandez 519b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer. 5203a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier AliasAnalysis::ModRefResult MR = AA->getModRefInfo(Inst, MemLoc); 5213a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier // If necessary, perform additional analysis. 5223a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier if (MR == AliasAnalysis::ModRef) 5233a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier MR = AA->callCapturesBefore(Inst, MemLoc, DT); 5243a884f5c17ac32e34e7e62b4602a0d73eeda1ce8Chad Rosier switch (MR) { 5253579e44bf33ed34f8b498834bfb40e407082bf31Chris Lattner case AliasAnalysis::NoModRef: 5263579e44bf33ed34f8b498834bfb40e407082bf31Chris Lattner // If the call has no effect on the queried pointer, just ignore it. 52725a081439f2c48a384c69ba8ad5e9ae005f4cf10Chris Lattner continue; 528a85a66423d966bf6210daf9587dba7ec1ff8d64eOwen Anderson case AliasAnalysis::Mod: 529a85a66423d966bf6210daf9587dba7ec1ff8d64eOwen Anderson return MemDepResult::getClobber(Inst); 5303579e44bf33ed34f8b498834bfb40e407082bf31Chris Lattner case AliasAnalysis::Ref: 5313579e44bf33ed34f8b498834bfb40e407082bf31Chris Lattner // If the call is known to never store to the pointer, and if this is a 5323579e44bf33ed34f8b498834bfb40e407082bf31Chris Lattner // load query, we can safely ignore it (scan past it). 5333579e44bf33ed34f8b498834bfb40e407082bf31Chris Lattner if (isLoad) 5343579e44bf33ed34f8b498834bfb40e407082bf31Chris Lattner continue; 5353579e44bf33ed34f8b498834bfb40e407082bf31Chris Lattner default: 5363579e44bf33ed34f8b498834bfb40e407082bf31Chris Lattner // Otherwise, there is a potential dependence. Return a clobber. 5373579e44bf33ed34f8b498834bfb40e407082bf31Chris Lattner return MemDepResult::getClobber(Inst); 5383579e44bf33ed34f8b498834bfb40e407082bf31Chris Lattner } 53978e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson } 5406178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 541a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman // No dependence found. If this is the entry block of the function, it is 542a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman // unknown, otherwise it is non-local. 5437ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner if (BB != &BB->getParent()->getEntryBlock()) 5447ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner return MemDepResult::getNonLocal(); 545b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman return MemDepResult::getNonFuncLocal(); 54678e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson} 54778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 5485391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner/// getDependency - Return the instruction on which a memory operation 5495391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner/// depends. 5505391a1d8046396fb4dd005b1910973789f5427f4Chris LattnerMemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { 5515391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner Instruction *ScanPos = QueryInst; 5526178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 5535391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner // Check for a cached result 554fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner MemDepResult &LocalCache = LocalDeps[QueryInst]; 5556178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 5560ec48ddef20deaa061152d86645972122beef605Chris Lattner // If the cached entry is non-dirty, just return it. Note that this depends 557fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner // on MemDepResult's default constructing to 'dirty'. 558fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner if (!LocalCache.isDirty()) 559fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner return LocalCache; 5606178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 5615391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner // Otherwise, if we have a dirty entry, we know we can start the scan at that 5625391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner // instruction, which may save us some work. 563fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner if (Instruction *Inst = LocalCache.getInst()) { 5645391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner ScanPos = Inst; 5656178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 566d44745d24175079f0675c6199ab9929d19edd1aaChris Lattner RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst); 5674a69bade2385022ca776edc22150f3b750cdf23cChris Lattner } 5686178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 569e79be944c8ced0a0cb80ede8cb9f97e4fdc6778fChris Lattner BasicBlock *QueryParent = QueryInst->getParent(); 5706178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 5715391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner // Do the scan. 572e79be944c8ced0a0cb80ede8cb9f97e4fdc6778fChris Lattner if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) { 573a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman // No dependence found. If this is the entry block of the function, it is 574a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman // unknown, otherwise it is non-local. 5757ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner if (QueryParent != &QueryParent->getParent()->getEntryBlock()) 5767ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner LocalCache = MemDepResult::getNonLocal(); 5777ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner else 578b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman LocalCache = MemDepResult::getNonFuncLocal(); 579533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman } else { 580533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman AliasAnalysis::Location MemLoc; 581533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman AliasAnalysis::ModRefResult MR = GetLocation(QueryInst, MemLoc, AA); 582533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman if (MemLoc.Ptr) { 583533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman // If we can do a pointer scan, make it happen. 584533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman bool isLoad = !(MR & AliasAnalysis::Mod); 58512bf43bc4f86602a5677d5e1662cb4e40562351bChris Lattner if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(QueryInst)) 586e1edb17bc3c606dd2e9c4e1b55da8e13817e5e09Owen Anderson isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start; 587f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner 588533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman LocalCache = getPointerDependencyFrom(MemLoc, isLoad, ScanPos, 589985dac65791b9f6f631bdd51c18fe66592a67469Shuxin Yang QueryParent, QueryInst); 590533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) { 591622b7cf147f9231a1d6e3aac81a2dd1b6047b26cGabor Greif CallSite QueryCS(QueryInst); 59293d3311d1f0169c456b6176a69b45d79533c75e2Nick Lewycky bool isReadOnly = AA->onlyReadsMemory(QueryCS); 59393d3311d1f0169c456b6176a69b45d79533c75e2Nick Lewycky LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos, 59493d3311d1f0169c456b6176a69b45d79533c75e2Nick Lewycky QueryParent); 595533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman } else 596533c2ad360eaaab2a0a25dab5a99255256b84814Dan Gohman // Non-memory instruction. 597a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman LocalCache = MemDepResult::getUnknown(); 598d801c10de6cd1760f0994452c0e78156782d9fcaNick Lewycky } 5996178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 6005391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner // Remember the result! 601fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner if (Instruction *I = LocalCache.getInst()) 6028c4652790e04515f34cf920b0783d6ec4161a313Chris Lattner ReverseLocalDeps[I].insert(QueryInst); 6036178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 604fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner return LocalCache; 6055391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner} 6065391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner 60712a7db383090dd21b1f8488be330a274cffaff3cChris Lattner#ifndef NDEBUG 60812a7db383090dd21b1f8488be330a274cffaff3cChris Lattner/// AssertSorted - This method is used when -debug is specified to verify that 60912a7db383090dd21b1f8488be330a274cffaff3cChris Lattner/// cache arrays are properly kept sorted. 61012a7db383090dd21b1f8488be330a274cffaff3cChris Lattnerstatic void AssertSorted(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, 61112a7db383090dd21b1f8488be330a274cffaff3cChris Lattner int Count = -1) { 61212a7db383090dd21b1f8488be330a274cffaff3cChris Lattner if (Count == -1) Count = Cache.size(); 61312a7db383090dd21b1f8488be330a274cffaff3cChris Lattner if (Count == 0) return; 61412a7db383090dd21b1f8488be330a274cffaff3cChris Lattner 61512a7db383090dd21b1f8488be330a274cffaff3cChris Lattner for (unsigned i = 1; i != unsigned(Count); ++i) 616e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner assert(!(Cache[i] < Cache[i-1]) && "Cache isn't sorted!"); 61712a7db383090dd21b1f8488be330a274cffaff3cChris Lattner} 61812a7db383090dd21b1f8488be330a274cffaff3cChris Lattner#endif 61912a7db383090dd21b1f8488be330a274cffaff3cChris Lattner 6201559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner/// getNonLocalCallDependency - Perform a full dependency query for the 6211559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner/// specified call, returning the set of blocks that the value is 62237d041c25f6cac462efef0d614a67ef657aad11aChris Lattner/// potentially live across. The returned set of results will include a 62337d041c25f6cac462efef0d614a67ef657aad11aChris Lattner/// "NonLocal" result for all blocks where the value is live across. 62437d041c25f6cac462efef0d614a67ef657aad11aChris Lattner/// 6251559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner/// This method assumes the instruction returns a "NonLocal" dependency 62637d041c25f6cac462efef0d614a67ef657aad11aChris Lattner/// within its own block. 62737d041c25f6cac462efef0d614a67ef657aad11aChris Lattner/// 6281559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner/// This returns a reference to an internal data structure that may be 6291559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner/// invalidated on the next non-local query or when an instruction is 6301559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner/// removed. Clients must copy this data if they want it around longer than 6311559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner/// that. 632bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattnerconst MemoryDependenceAnalysis::NonLocalDepInfo & 6331559b3625be7b80bee6b066af4b91b9d10dfb5faChris LattnerMemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { 6341559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner assert(getDependency(QueryCS.getInstruction()).isNonLocal() && 6351559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner "getNonLocalCallDependency should only be used on calls with non-local deps!"); 6361559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner PerInstNLInfo &CacheP = NonLocalDeps[QueryCS.getInstruction()]; 637bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner NonLocalDepInfo &Cache = CacheP.first; 63837d041c25f6cac462efef0d614a67ef657aad11aChris Lattner 63937d041c25f6cac462efef0d614a67ef657aad11aChris Lattner /// DirtyBlocks - This is the set of blocks that need to be recomputed. In 64037d041c25f6cac462efef0d614a67ef657aad11aChris Lattner /// the cached case, this can happen due to instructions being deleted etc. In 64137d041c25f6cac462efef0d614a67ef657aad11aChris Lattner /// the uncached case, this starts out as the set of predecessors we care 64237d041c25f6cac462efef0d614a67ef657aad11aChris Lattner /// about. 64337d041c25f6cac462efef0d614a67ef657aad11aChris Lattner SmallVector<BasicBlock*, 32> DirtyBlocks; 6446178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 64537d041c25f6cac462efef0d614a67ef657aad11aChris Lattner if (!Cache.empty()) { 646bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner // Okay, we have a cache entry. If we know it is not dirty, just return it 647bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner // with no computation. 648bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner if (!CacheP.second) { 649fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumCacheNonLocal; 650bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner return Cache; 651bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner } 6526178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 65337d041c25f6cac462efef0d614a67ef657aad11aChris Lattner // If we already have a partially computed set of results, scan them to 654bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner // determine what is dirty, seeding our initial DirtyBlocks worklist. 655bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner for (NonLocalDepInfo::iterator I = Cache.begin(), E = Cache.end(); 656bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner I != E; ++I) 657e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner if (I->getResult().isDirty()) 658e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner DirtyBlocks.push_back(I->getBB()); 6596178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 660bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner // Sort the cache so that we can do fast binary search lookups below. 661bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner std::sort(Cache.begin(), Cache.end()); 6626178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 663bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner ++NumCacheDirtyNonLocal; 66437d041c25f6cac462efef0d614a67ef657aad11aChris Lattner //cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: " 66537d041c25f6cac462efef0d614a67ef657aad11aChris Lattner // << Cache.size() << " cached: " << *QueryInst; 66637d041c25f6cac462efef0d614a67ef657aad11aChris Lattner } else { 66737d041c25f6cac462efef0d614a67ef657aad11aChris Lattner // Seed DirtyBlocks with each of the preds of QueryInst's block. 6681559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner BasicBlock *QueryBB = QueryCS.getInstruction()->getParent(); 669511b36c00f3fbe80770e0bbbfe8ed2f266148d65Chris Lattner for (BasicBlock **PI = PredCache->GetPreds(QueryBB); *PI; ++PI) 670511b36c00f3fbe80770e0bbbfe8ed2f266148d65Chris Lattner DirtyBlocks.push_back(*PI); 671fe60104ac97f3a8736dcfbfdf9547c7b7cc7b951Dan Gohman ++NumUncacheNonLocal; 67237d041c25f6cac462efef0d614a67ef657aad11aChris Lattner } 6736178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 67420d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner // isReadonlyCall - If this is a read-only call, we can be more aggressive. 67520d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner bool isReadonlyCall = AA->onlyReadsMemory(QueryCS); 6769e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner 677bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner SmallPtrSet<BasicBlock*, 64> Visited; 6786178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 679bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner unsigned NumSortedEntries = Cache.size(); 68012a7db383090dd21b1f8488be330a274cffaff3cChris Lattner DEBUG(AssertSorted(Cache)); 6816178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 68237d041c25f6cac462efef0d614a67ef657aad11aChris Lattner // Iterate while we still have blocks to update. 68337d041c25f6cac462efef0d614a67ef657aad11aChris Lattner while (!DirtyBlocks.empty()) { 68437d041c25f6cac462efef0d614a67ef657aad11aChris Lattner BasicBlock *DirtyBB = DirtyBlocks.back(); 68537d041c25f6cac462efef0d614a67ef657aad11aChris Lattner DirtyBlocks.pop_back(); 6866178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 687bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner // Already processed this block? 688bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner if (!Visited.insert(DirtyBB)) 689bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner continue; 6906178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 691bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner // Do a binary search to see if we already have an entry for this block in 692bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner // the cache set. If so, find it. 69312a7db383090dd21b1f8488be330a274cffaff3cChris Lattner DEBUG(AssertSorted(Cache, NumSortedEntries)); 6946178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak NonLocalDepInfo::iterator Entry = 695bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner std::upper_bound(Cache.begin(), Cache.begin()+NumSortedEntries, 696dad451cb7c6b94b3af40f59271e24357616a05a9Chris Lattner NonLocalDepEntry(DirtyBB)); 69736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Entry != Cache.begin() && std::prev(Entry)->getBB() == DirtyBB) 698bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner --Entry; 6996178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 700dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NonLocalDepEntry *ExistingResult = nullptr; 7016178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak if (Entry != Cache.begin()+NumSortedEntries && 702e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner Entry->getBB() == DirtyBB) { 703bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner // If we already have an entry, and if it isn't already dirty, the block 704bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner // is done. 705e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner if (!Entry->getResult().isDirty()) 706bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner continue; 7076178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 708bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner // Otherwise, remember this slot so we can update the value. 709e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner ExistingResult = &*Entry; 710bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner } 7116178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 71237d041c25f6cac462efef0d614a67ef657aad11aChris Lattner // If the dirty entry has a pointer, start scanning from it so we don't have 71337d041c25f6cac462efef0d614a67ef657aad11aChris Lattner // to rescan the entire block. 71437d041c25f6cac462efef0d614a67ef657aad11aChris Lattner BasicBlock::iterator ScanPos = DirtyBB->end(); 715bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner if (ExistingResult) { 716e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner if (Instruction *Inst = ExistingResult->getResult().getInst()) { 717bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner ScanPos = Inst; 718bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner // We're removing QueryInst's use of Inst. 7191559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner RemoveFromReverseMap(ReverseNonLocalDeps, Inst, 7201559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner QueryCS.getInstruction()); 721bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner } 722f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner } 7236178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 72473ec3cdd7140aee6d2b9ac32bc2298254ff48c97Chris Lattner // Find out if this block has a local dependency for QueryInst. 725d8dd934d16d1190881d45b065daec4a1ba82133fChris Lattner MemDepResult Dep; 7266178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 7271559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner if (ScanPos != DirtyBB->begin()) { 72820d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner Dep = getCallSiteDependencyFrom(QueryCS, isReadonlyCall,ScanPos, DirtyBB); 7291559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner } else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) { 7301559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner // No dependence found. If this is the entry block of the function, it is 731a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman // a clobber, otherwise it is unknown. 7321559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner Dep = MemDepResult::getNonLocal(); 733e79be944c8ced0a0cb80ede8cb9f97e4fdc6778fChris Lattner } else { 734b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman Dep = MemDepResult::getNonFuncLocal(); 735e79be944c8ced0a0cb80ede8cb9f97e4fdc6778fChris Lattner } 7366178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 737bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner // If we had a dirty entry for the block, update it. Otherwise, just add 738bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner // a new entry. 739bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner if (ExistingResult) 7400ee443d169786017d151034b8bd34225bc144c98Chris Lattner ExistingResult->setResult(Dep); 741bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner else 7420ee443d169786017d151034b8bd34225bc144c98Chris Lattner Cache.push_back(NonLocalDepEntry(DirtyBB, Dep)); 7436178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 74437d041c25f6cac462efef0d614a67ef657aad11aChris Lattner // If the block has a dependency (i.e. it isn't completely transparent to 745bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner // the value), remember the association! 746bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner if (!Dep.isNonLocal()) { 74737d041c25f6cac462efef0d614a67ef657aad11aChris Lattner // Keep the ReverseNonLocalDeps map up to date so we can efficiently 74837d041c25f6cac462efef0d614a67ef657aad11aChris Lattner // update this when we remove instructions. 749bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner if (Instruction *Inst = Dep.getInst()) 7501559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner ReverseNonLocalDeps[Inst].insert(QueryCS.getInstruction()); 751bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner } else { 7526178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 753bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner // If the block *is* completely transparent to the load, we need to check 754bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner // the predecessors of this block. Add them to our worklist. 755511b36c00f3fbe80770e0bbbfe8ed2f266148d65Chris Lattner for (BasicBlock **PI = PredCache->GetPreds(DirtyBB); *PI; ++PI) 756511b36c00f3fbe80770e0bbbfe8ed2f266148d65Chris Lattner DirtyBlocks.push_back(*PI); 757bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner } 75837d041c25f6cac462efef0d614a67ef657aad11aChris Lattner } 7596178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 760bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner return Cache; 76137d041c25f6cac462efef0d614a67ef657aad11aChris Lattner} 76237d041c25f6cac462efef0d614a67ef657aad11aChris Lattner 7637ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner/// getNonLocalPointerDependency - Perform a full dependency query for an 7647ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner/// access to the specified (non-volatile) memory location, returning the 7657ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner/// set of instructions that either define or clobber the value. 7667ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner/// 7677ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner/// This method assumes the pointer has a "NonLocal" dependency within its 7687ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner/// own block. 7697ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner/// 7707ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattnervoid MemoryDependenceAnalysis:: 771c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan GohmangetNonLocalPointerDependency(const AliasAnalysis::Location &Loc, bool isLoad, 772c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman BasicBlock *FromBB, 7730ee443d169786017d151034b8bd34225bc144c98Chris Lattner SmallVectorImpl<NonLocalDepResult> &Result) { 774c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman assert(Loc.Ptr->getType()->isPointerTy() && 7753f7eb5b795f933aecf0e0f1fea646c516f6dc1c5Chris Lattner "Can't get pointer deps of a non-pointer!"); 7769a193fd8ae630478123938e12b56f84c5b2227b9Chris Lattner Result.clear(); 7776178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 77836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PHITransAddr Address(const_cast<Value *>(Loc.Ptr), DL); 7796178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 7809e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // This is the set of blocks we've inspected, and the pointer we consider in 7819e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // each block. Because of critical edges, we currently bail out if querying 7829e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // a block with multiple different pointers. This can happen during PHI 7839e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // translation. 7849e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner DenseMap<BasicBlock*, Value*> Visited; 785c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman if (!getNonLocalPointerDepFromBB(Address, Loc, isLoad, FromBB, 7869e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner Result, Visited, true)) 7879e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner return; 7883af23f8aba9ac28fe5a8646f57c2c307a35c1e4dChris Lattner Result.clear(); 7890ee443d169786017d151034b8bd34225bc144c98Chris Lattner Result.push_back(NonLocalDepResult(FromBB, 790a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman MemDepResult::getUnknown(), 791c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman const_cast<Value *>(Loc.Ptr))); 7929a193fd8ae630478123938e12b56f84c5b2227b9Chris Lattner} 7939a193fd8ae630478123938e12b56f84c5b2227b9Chris Lattner 7949863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner/// GetNonLocalInfoForBlock - Compute the memdep value for BB with 7959863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner/// Pointer/PointeeSize using either cached information in Cache or by doing a 7969863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner/// lookup (which may use dirty cache info if available). If we do a lookup, 7979863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner/// add the result to the cache. 7989863c3f507913f17de0fd707e27fde9dc35f6ca6Chris LattnerMemDepResult MemoryDependenceAnalysis:: 799c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan GohmanGetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc, 8009863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner bool isLoad, BasicBlock *BB, 8019863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner NonLocalDepInfo *Cache, unsigned NumSortedEntries) { 8026178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 8039863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // Do a binary search to see if we already have an entry for this block in 8049863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // the cache set. If so, find it. 8059863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner NonLocalDepInfo::iterator Entry = 8069863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries, 807dad451cb7c6b94b3af40f59271e24357616a05a9Chris Lattner NonLocalDepEntry(BB)); 808e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner if (Entry != Cache->begin() && (Entry-1)->getBB() == BB) 8099863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner --Entry; 8106178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 811dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NonLocalDepEntry *ExistingResult = nullptr; 812e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner if (Entry != Cache->begin()+NumSortedEntries && Entry->getBB() == BB) 813e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner ExistingResult = &*Entry; 8146178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 8159863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // If we have a cached entry, and it is non-dirty, use it as the value for 8169863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // this dependency. 817e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner if (ExistingResult && !ExistingResult->getResult().isDirty()) { 8189863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner ++NumCacheNonLocalPtr; 819e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner return ExistingResult->getResult(); 8206178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak } 8216178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 8229863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // Otherwise, we have to scan for the value. If we have a dirty cache 8239863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // entry, start scanning from its position, otherwise we scan from the end 8249863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // of the block. 8259863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner BasicBlock::iterator ScanPos = BB->end(); 826e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner if (ExistingResult && ExistingResult->getResult().getInst()) { 827e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner assert(ExistingResult->getResult().getInst()->getParent() == BB && 8289863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner "Instruction invalidated?"); 8299863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner ++NumCacheDirtyNonLocalPtr; 830e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner ScanPos = ExistingResult->getResult().getInst(); 8316178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 8329863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // Eliminating the dirty entry from 'Cache', so update the reverse info. 833c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman ValueIsLoadPair CacheKey(Loc.Ptr, isLoad); 8346a0dcc10778468b1556474aa43d4a86a14ab15d7Chris Lattner RemoveFromReverseMap(ReverseNonLocalPtrDeps, ScanPos, CacheKey); 8359863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner } else { 8369863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner ++NumUncacheNonLocalPtr; 8379863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner } 8386178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 8399863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // Scan the block for the dependency. 840c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman MemDepResult Dep = getPointerDependencyFrom(Loc, isLoad, ScanPos, BB); 8416178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 8429863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // If we had a dirty entry for the block, update it. Otherwise, just add 8439863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // a new entry. 8449863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner if (ExistingResult) 8450ee443d169786017d151034b8bd34225bc144c98Chris Lattner ExistingResult->setResult(Dep); 8469863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner else 8470ee443d169786017d151034b8bd34225bc144c98Chris Lattner Cache->push_back(NonLocalDepEntry(BB, Dep)); 8486178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 8499863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // If the block has a dependency (i.e. it isn't completely transparent to 8509863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // the value), remember the reverse association because we just added it 8519863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // to Cache! 852b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman if (!Dep.isDef() && !Dep.isClobber()) 8539863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner return Dep; 8546178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 8559863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently 8569863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // update MemDep when we remove instructions. 8579863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner Instruction *Inst = Dep.getInst(); 8589863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner assert(Inst && "Didn't depend on anything?"); 859c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman ValueIsLoadPair CacheKey(Loc.Ptr, isLoad); 8606a0dcc10778468b1556474aa43d4a86a14ab15d7Chris Lattner ReverseNonLocalPtrDeps[Inst].insert(CacheKey); 8619863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner return Dep; 8629863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner} 8639863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner 864a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner/// SortNonLocalDepInfoCache - Sort the a NonLocalDepInfo cache, given a certain 865a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner/// number of elements in the array that are already properly ordered. This is 866a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner/// optimized for the case when only a few entries are added. 8676178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszakstatic void 868a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris LattnerSortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, 869a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner unsigned NumSortedEntries) { 870a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner switch (Cache.size() - NumSortedEntries) { 871a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner case 0: 872a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner // done, no new entries. 873a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner break; 874a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner case 2: { 875a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner // Two new entries, insert the last one into place. 876e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner NonLocalDepEntry Val = Cache.back(); 877a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner Cache.pop_back(); 878a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry = 879a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner std::upper_bound(Cache.begin(), Cache.end()-1, Val); 880a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner Cache.insert(Entry, Val); 881a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner // FALL THROUGH. 882a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner } 883a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner case 1: 884a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner // One new entry, Just insert the new value at the appropriate position. 885a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner if (Cache.size() != 1) { 886e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner NonLocalDepEntry Val = Cache.back(); 887a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner Cache.pop_back(); 888a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry = 889a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner std::upper_bound(Cache.begin(), Cache.end(), Val); 890a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner Cache.insert(Entry, Val); 891a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner } 892a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner break; 893a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner default: 894a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner // Added many values, do a full scale sort. 895a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner std::sort(Cache.begin(), Cache.end()); 896a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner break; 897a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner } 898a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner} 899a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner 9009e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner/// getNonLocalPointerDepFromBB - Perform a dependency query based on 9019e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner/// pointer/pointeesize starting at the end of StartBB. Add any clobber/def 9029e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner/// results to the results vector and keep track of which blocks are visited in 9039e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner/// 'Visited'. 9049e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner/// 9059e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner/// This has special behavior for the first block queries (when SkipFirstBlock 9069e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner/// is true). In this special case, it ignores the contents of the specified 9079e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner/// block and starts returning dependence info for its predecessors. 9089e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner/// 9099e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner/// This function returns false on success, or true to indicate that it could 9109e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner/// not compute dependence information for some reason. This should be treated 9119e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner/// as a clobber dependence on the first instruction in the predecessor block. 9129e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattnerbool MemoryDependenceAnalysis:: 913c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan GohmangetNonLocalPointerDepFromBB(const PHITransAddr &Pointer, 914c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman const AliasAnalysis::Location &Loc, 9159863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner bool isLoad, BasicBlock *StartBB, 9160ee443d169786017d151034b8bd34225bc144c98Chris Lattner SmallVectorImpl<NonLocalDepResult> &Result, 9179e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner DenseMap<BasicBlock*, Value*> &Visited, 9189e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner bool SkipFirstBlock) { 9196290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // Look up the cached info for Pointer. 92005e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad); 921c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman 922075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman // Set up a temporary NLPI value. If the map doesn't yet have an entry for 923075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman // CacheKey, this value will be inserted as the associated value. Otherwise, 924075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman // it'll be ignored, and we'll have to check to see if the cached size and 925075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman // tbaa tag are consistent with the current query. 926075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman NonLocalPointerInfo InitialNLPI; 927075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman InitialNLPI.Size = Loc.Size; 928075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman InitialNLPI.TBAATag = Loc.TBAATag; 929075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman 930075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman // Get the NLPI for CacheKey, inserting one into the map if it doesn't 931075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman // already have one. 9326178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair = 933075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI)); 934075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman NonLocalPointerInfo *CacheInfo = &Pair.first->second; 935075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman 936733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman // If we already have a cache entry for this CacheKey, we may need to do some 937733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman // work to reconcile the cache entry and the current query. 938075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman if (!Pair.second) { 939733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman if (CacheInfo->Size < Loc.Size) { 940733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman // The query's Size is greater than the cached one. Throw out the 941d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer // cached data and proceed with the query at the greater size. 942733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman CacheInfo->Pair = BBSkipFirstBlockPair(); 943733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman CacheInfo->Size = Loc.Size; 9442365f08c7dfd039ef325d8cb4621b40fc5bd605fDan Gohman for (NonLocalDepInfo::iterator DI = CacheInfo->NonLocalDeps.begin(), 9452365f08c7dfd039ef325d8cb4621b40fc5bd605fDan Gohman DE = CacheInfo->NonLocalDeps.end(); DI != DE; ++DI) 9462365f08c7dfd039ef325d8cb4621b40fc5bd605fDan Gohman if (Instruction *Inst = DI->getResult().getInst()) 9472365f08c7dfd039ef325d8cb4621b40fc5bd605fDan Gohman RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey); 948733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman CacheInfo->NonLocalDeps.clear(); 949733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman } else if (CacheInfo->Size > Loc.Size) { 950733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman // This query's Size is less than the cached one. Conservatively restart 951733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman // the query using the greater size. 952075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman return getNonLocalPointerDepFromBB(Pointer, 953075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman Loc.getWithNewSize(CacheInfo->Size), 954075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman isLoad, StartBB, Result, Visited, 955075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman SkipFirstBlock); 956075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman } 957075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman 958733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman // If the query's TBAATag is inconsistent with the cached one, 959733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman // conservatively throw out the cached data and restart the query with 960733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman // no tag if needed. 961075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman if (CacheInfo->TBAATag != Loc.TBAATag) { 962733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman if (CacheInfo->TBAATag) { 963733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman CacheInfo->Pair = BBSkipFirstBlockPair(); 964dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CacheInfo->TBAATag = nullptr; 9652365f08c7dfd039ef325d8cb4621b40fc5bd605fDan Gohman for (NonLocalDepInfo::iterator DI = CacheInfo->NonLocalDeps.begin(), 9662365f08c7dfd039ef325d8cb4621b40fc5bd605fDan Gohman DE = CacheInfo->NonLocalDeps.end(); DI != DE; ++DI) 9672365f08c7dfd039ef325d8cb4621b40fc5bd605fDan Gohman if (Instruction *Inst = DI->getResult().getInst()) 9682365f08c7dfd039ef325d8cb4621b40fc5bd605fDan Gohman RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey); 969733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman CacheInfo->NonLocalDeps.clear(); 970733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman } 971733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman if (Loc.TBAATag) 972733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman return getNonLocalPointerDepFromBB(Pointer, Loc.getWithoutTBAATag(), 973733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman isLoad, StartBB, Result, Visited, 974733c54da1e5432d9d64f88ea960121fa7a16076aDan Gohman SkipFirstBlock); 975075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman } 976c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman } 977c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman 978c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman NonLocalDepInfo *Cache = &CacheInfo->NonLocalDeps; 97911dcd8d38de031c34380fd6ab7a0daacdefb263aChris Lattner 98011dcd8d38de031c34380fd6ab7a0daacdefb263aChris Lattner // If we have valid cached information for exactly the block we are 98111dcd8d38de031c34380fd6ab7a0daacdefb263aChris Lattner // investigating, just return it with no recomputation. 982c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman if (CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) { 983f478951b0eeed2f8a9e39254f65458c9325dab91Chris Lattner // We have a fully cached result for this query then we can just return the 984f478951b0eeed2f8a9e39254f65458c9325dab91Chris Lattner // cached results and populate the visited set. However, we have to verify 985f478951b0eeed2f8a9e39254f65458c9325dab91Chris Lattner // that we don't already have conflicting results for these blocks. Check 986f478951b0eeed2f8a9e39254f65458c9325dab91Chris Lattner // to ensure that if a block in the results set is in the visited set that 987f478951b0eeed2f8a9e39254f65458c9325dab91Chris Lattner // it was for the same pointer query. 988f478951b0eeed2f8a9e39254f65458c9325dab91Chris Lattner if (!Visited.empty()) { 989f478951b0eeed2f8a9e39254f65458c9325dab91Chris Lattner for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end(); 990f478951b0eeed2f8a9e39254f65458c9325dab91Chris Lattner I != E; ++I) { 991e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner DenseMap<BasicBlock*, Value*>::iterator VI = Visited.find(I->getBB()); 99205e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner if (VI == Visited.end() || VI->second == Pointer.getAddr()) 99305e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner continue; 9946178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 995f478951b0eeed2f8a9e39254f65458c9325dab91Chris Lattner // We have a pointer mismatch in a block. Just return clobber, saying 996f478951b0eeed2f8a9e39254f65458c9325dab91Chris Lattner // that something was clobbered in this result. We could also do a 997f478951b0eeed2f8a9e39254f65458c9325dab91Chris Lattner // non-fully cached query, but there is little point in doing this. 998f478951b0eeed2f8a9e39254f65458c9325dab91Chris Lattner return true; 999f478951b0eeed2f8a9e39254f65458c9325dab91Chris Lattner } 1000f478951b0eeed2f8a9e39254f65458c9325dab91Chris Lattner } 10016178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 10020ee443d169786017d151034b8bd34225bc144c98Chris Lattner Value *Addr = Pointer.getAddr(); 100311dcd8d38de031c34380fd6ab7a0daacdefb263aChris Lattner for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end(); 1004f478951b0eeed2f8a9e39254f65458c9325dab91Chris Lattner I != E; ++I) { 10050ee443d169786017d151034b8bd34225bc144c98Chris Lattner Visited.insert(std::make_pair(I->getBB(), Addr)); 10068b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault if (I->getResult().isNonLocal()) { 10078b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault continue; 10088b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault } 10098b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault 10108b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault if (!DT) { 10118b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault Result.push_back(NonLocalDepResult(I->getBB(), 10128b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault MemDepResult::getUnknown(), 10138b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault Addr)); 10148b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault } else if (DT->isReachableFromEntry(I->getBB())) { 10150ee443d169786017d151034b8bd34225bc144c98Chris Lattner Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), Addr)); 10168b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault } 1017f478951b0eeed2f8a9e39254f65458c9325dab91Chris Lattner } 101811dcd8d38de031c34380fd6ab7a0daacdefb263aChris Lattner ++NumCacheCompleteNonLocalPtr; 10199e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner return false; 102011dcd8d38de031c34380fd6ab7a0daacdefb263aChris Lattner } 10216178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 102211dcd8d38de031c34380fd6ab7a0daacdefb263aChris Lattner // Otherwise, either this is a new block, a block with an invalid cache 102311dcd8d38de031c34380fd6ab7a0daacdefb263aChris Lattner // pointer or one that we're about to invalidate by putting more info into it 102411dcd8d38de031c34380fd6ab7a0daacdefb263aChris Lattner // than its valid cache info. If empty, the result will be valid cache info, 102511dcd8d38de031c34380fd6ab7a0daacdefb263aChris Lattner // otherwise it isn't. 10269e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner if (Cache->empty()) 1027c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock); 10288a66a202f6c110273a7570b77e0b8bcb660fd92fDan Gohman else 1029c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman CacheInfo->Pair = BBSkipFirstBlockPair(); 10306178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 103111dcd8d38de031c34380fd6ab7a0daacdefb263aChris Lattner SmallVector<BasicBlock*, 32> Worklist; 103211dcd8d38de031c34380fd6ab7a0daacdefb263aChris Lattner Worklist.push_back(StartBB); 10336178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1034fc09797426894602355d248edb174676ec7fd560Eli Friedman // PredList used inside loop. 1035fc09797426894602355d248edb174676ec7fd560Eli Friedman SmallVector<std::pair<BasicBlock*, PHITransAddr>, 16> PredList; 1036fc09797426894602355d248edb174676ec7fd560Eli Friedman 10376290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // Keep track of the entries that we know are sorted. Previously cached 10386290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // entries will all be sorted. The entries we add we only sort on demand (we 10396290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // don't insert every element into its sorted position). We know that we 10406290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // won't get any reuse from currently inserted values, because we don't 10416290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // revisit blocks after we insert info for them. 10426290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner unsigned NumSortedEntries = Cache->size(); 104312a7db383090dd21b1f8488be330a274cffaff3cChris Lattner DEBUG(AssertSorted(*Cache)); 10446178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 10457ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner while (!Worklist.empty()) { 10469a193fd8ae630478123938e12b56f84c5b2227b9Chris Lattner BasicBlock *BB = Worklist.pop_back_val(); 10476178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 10486563371bad878cb9737970fea6162044a0370df8Chris Lattner // Skip the first block if we have it. 10499e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner if (!SkipFirstBlock) { 10506563371bad878cb9737970fea6162044a0370df8Chris Lattner // Analyze the dependency of *Pointer in FromBB. See if we already have 10516563371bad878cb9737970fea6162044a0370df8Chris Lattner // been here. 10529e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner assert(Visited.count(BB) && "Should check 'visited' before adding to WL"); 10536290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner 10546563371bad878cb9737970fea6162044a0370df8Chris Lattner // Get the dependency info for Pointer in BB. If we have cached 10556563371bad878cb9737970fea6162044a0370df8Chris Lattner // information, we will use it, otherwise we compute it. 105612a7db383090dd21b1f8488be330a274cffaff3cChris Lattner DEBUG(AssertSorted(*Cache, NumSortedEntries)); 1057c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman MemDepResult Dep = GetNonLocalInfoForBlock(Loc, isLoad, BB, Cache, 105805e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner NumSortedEntries); 10596178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 10606563371bad878cb9737970fea6162044a0370df8Chris Lattner // If we got a Def or Clobber, add this to the list of results. 10618b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault if (!Dep.isNonLocal()) { 10628b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault if (!DT) { 10638b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault Result.push_back(NonLocalDepResult(BB, 10648b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault MemDepResult::getUnknown(), 10658b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault Pointer.getAddr())); 10668b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault continue; 10678b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault } else if (DT->isReachableFromEntry(BB)) { 10688b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr())); 10698b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault continue; 10708b9dc21d6f12a0251cdb6116c2297c13d77073d5Matt Arsenault } 10716563371bad878cb9737970fea6162044a0370df8Chris Lattner } 10727ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner } 10736178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 10749e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // If 'Pointer' is an instruction defined in this block, then we need to do 10759e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // phi translation to change it into a value live in the predecessor block. 107605e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner // If not, we just add the predecessors to the worklist and scan them with 107705e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner // the same Pointer. 107805e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner if (!Pointer.NeedsPHITranslationFromBlock(BB)) { 10799e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner SkipFirstBlock = false; 1080fc09797426894602355d248edb174676ec7fd560Eli Friedman SmallVector<BasicBlock*, 16> NewBlocks; 10819e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) { 10829e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // Verify that we haven't looked at this block yet. 10839e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool> 108405e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner InsertRes = Visited.insert(std::make_pair(*PI, Pointer.getAddr())); 10859e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner if (InsertRes.second) { 10869e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // First time we've looked at *PI. 1087fc09797426894602355d248edb174676ec7fd560Eli Friedman NewBlocks.push_back(*PI); 10889e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner continue; 10899e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner } 10906178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 10919e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // If we have seen this block before, but it was with a different 10929e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // pointer then we have a phi translation failure and we have to treat 10939e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // this as a clobber. 1094fc09797426894602355d248edb174676ec7fd560Eli Friedman if (InsertRes.first->second != Pointer.getAddr()) { 1095fc09797426894602355d248edb174676ec7fd560Eli Friedman // Make sure to clean up the Visited map before continuing on to 1096fc09797426894602355d248edb174676ec7fd560Eli Friedman // PredTranslationFailure. 1097fc09797426894602355d248edb174676ec7fd560Eli Friedman for (unsigned i = 0; i < NewBlocks.size(); i++) 1098fc09797426894602355d248edb174676ec7fd560Eli Friedman Visited.erase(NewBlocks[i]); 10999e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner goto PredTranslationFailure; 1100fc09797426894602355d248edb174676ec7fd560Eli Friedman } 11019e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner } 1102fc09797426894602355d248edb174676ec7fd560Eli Friedman Worklist.append(NewBlocks.begin(), NewBlocks.end()); 11039e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner continue; 11049e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner } 11056178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 110605e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner // We do need to do phi translation, if we know ahead of time we can't phi 110705e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner // translate this value, don't even try. 110805e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner if (!Pointer.IsPotentiallyPHITranslatable()) 110905e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner goto PredTranslationFailure; 11106178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 11116fbc1969e94cb00c82ab84e1dfe243e7388d3b1bChris Lattner // We may have added values to the cache list before this PHI translation. 11126fbc1969e94cb00c82ab84e1dfe243e7388d3b1bChris Lattner // If so, we haven't done anything to ensure that the cache remains sorted. 11136fbc1969e94cb00c82ab84e1dfe243e7388d3b1bChris Lattner // Sort it now (if needed) so that recursive invocations of 11146fbc1969e94cb00c82ab84e1dfe243e7388d3b1bChris Lattner // getNonLocalPointerDepFromBB and other routines that could reuse the cache 11156fbc1969e94cb00c82ab84e1dfe243e7388d3b1bChris Lattner // value will only see properly sorted cache arrays. 11166fbc1969e94cb00c82ab84e1dfe243e7388d3b1bChris Lattner if (Cache && NumSortedEntries != Cache->size()) { 1117a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner SortNonLocalDepInfoCache(*Cache, NumSortedEntries); 11186fbc1969e94cb00c82ab84e1dfe243e7388d3b1bChris Lattner NumSortedEntries = Cache->size(); 11196fbc1969e94cb00c82ab84e1dfe243e7388d3b1bChris Lattner } 1120dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Cache = nullptr; 1121fc09797426894602355d248edb174676ec7fd560Eli Friedman 1122fc09797426894602355d248edb174676ec7fd560Eli Friedman PredList.clear(); 1123e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) { 1124e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner BasicBlock *Pred = *PI; 1125fc09797426894602355d248edb174676ec7fd560Eli Friedman PredList.push_back(std::make_pair(Pred, Pointer)); 1126fc09797426894602355d248edb174676ec7fd560Eli Friedman 112705e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner // Get the PHI translated pointer in this predecessor. This can fail if 112805e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner // not translatable, in which case the getAddr() returns null. 1129fc09797426894602355d248edb174676ec7fd560Eli Friedman PHITransAddr &PredPointer = PredList.back().second; 1130dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PredPointer.PHITranslateValue(BB, Pred, nullptr); 113105e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner 113205e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner Value *PredPtrVal = PredPointer.getAddr(); 11336178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1134e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner // Check to see if we have already visited this pred block with another 1135e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner // pointer. If so, we can't do this lookup. This failure can occur 1136e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner // with PHI translation when a critical edge exists and the PHI node in 1137e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner // the successor translates to a pointer value different than the 1138e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner // pointer the block was first analyzed with. 1139e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool> 114005e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner InsertRes = Visited.insert(std::make_pair(Pred, PredPtrVal)); 114112a7db383090dd21b1f8488be330a274cffaff3cChris Lattner 1142e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner if (!InsertRes.second) { 1143fc09797426894602355d248edb174676ec7fd560Eli Friedman // We found the pred; take it off the list of preds to visit. 1144fc09797426894602355d248edb174676ec7fd560Eli Friedman PredList.pop_back(); 1145fc09797426894602355d248edb174676ec7fd560Eli Friedman 1146e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner // If the predecessor was visited with PredPtr, then we already did 1147e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner // the analysis and can ignore it. 114805e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner if (InsertRes.first->second == PredPtrVal) 1149e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner continue; 11506178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1151e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner // Otherwise, the block was previously analyzed with a different 1152e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner // pointer. We can't represent the result of this case, so we just 1153e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner // treat this as a phi translation failure. 1154fc09797426894602355d248edb174676ec7fd560Eli Friedman 1155fc09797426894602355d248edb174676ec7fd560Eli Friedman // Make sure to clean up the Visited map before continuing on to 1156fc09797426894602355d248edb174676ec7fd560Eli Friedman // PredTranslationFailure. 11577d4ff60b55772c731688cd27f9252e31ae964f84Matt Arsenault for (unsigned i = 0, n = PredList.size(); i < n; ++i) 1158fc09797426894602355d248edb174676ec7fd560Eli Friedman Visited.erase(PredList[i].first); 1159fc09797426894602355d248edb174676ec7fd560Eli Friedman 1160e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner goto PredTranslationFailure; 11619e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner } 1162fc09797426894602355d248edb174676ec7fd560Eli Friedman } 1163fc09797426894602355d248edb174676ec7fd560Eli Friedman 1164fc09797426894602355d248edb174676ec7fd560Eli Friedman // Actually process results here; this need to be a separate loop to avoid 1165fc09797426894602355d248edb174676ec7fd560Eli Friedman // calling getNonLocalPointerDepFromBB for blocks we don't want to return 11666178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak // any results for. (getNonLocalPointerDepFromBB will modify our 1167fc09797426894602355d248edb174676ec7fd560Eli Friedman // datastructures in ways the code after the PredTranslationFailure label 1168fc09797426894602355d248edb174676ec7fd560Eli Friedman // doesn't expect.) 11697d4ff60b55772c731688cd27f9252e31ae964f84Matt Arsenault for (unsigned i = 0, n = PredList.size(); i < n; ++i) { 1170fc09797426894602355d248edb174676ec7fd560Eli Friedman BasicBlock *Pred = PredList[i].first; 1171fc09797426894602355d248edb174676ec7fd560Eli Friedman PHITransAddr &PredPointer = PredList[i].second; 1172fc09797426894602355d248edb174676ec7fd560Eli Friedman Value *PredPtrVal = PredPointer.getAddr(); 1173fc09797426894602355d248edb174676ec7fd560Eli Friedman 1174fc09797426894602355d248edb174676ec7fd560Eli Friedman bool CanTranslate = true; 11756f7b210b2577fbc9247a9fc5223655390008ae89Chris Lattner // If PHI translation was unable to find an available pointer in this 11766f7b210b2577fbc9247a9fc5223655390008ae89Chris Lattner // predecessor, then we have to assume that the pointer is clobbered in 11776f7b210b2577fbc9247a9fc5223655390008ae89Chris Lattner // that predecessor. We can still do PRE of the load, which would insert 11786f7b210b2577fbc9247a9fc5223655390008ae89Chris Lattner // a computation of the pointer in this predecessor. 1179dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!PredPtrVal) 1180fc09797426894602355d248edb174676ec7fd560Eli Friedman CanTranslate = false; 1181fc09797426894602355d248edb174676ec7fd560Eli Friedman 1182fc09797426894602355d248edb174676ec7fd560Eli Friedman // FIXME: it is entirely possible that PHI translating will end up with 1183fc09797426894602355d248edb174676ec7fd560Eli Friedman // the same value. Consider PHI translating something like: 1184fc09797426894602355d248edb174676ec7fd560Eli Friedman // X = phi [x, bb1], [y, bb2]. PHI translating for bb1 doesn't *need* 1185fc09797426894602355d248edb174676ec7fd560Eli Friedman // to recurse here, pedantically speaking. 1186fc09797426894602355d248edb174676ec7fd560Eli Friedman 1187fc09797426894602355d248edb174676ec7fd560Eli Friedman // If getNonLocalPointerDepFromBB fails here, that means the cached 1188fc09797426894602355d248edb174676ec7fd560Eli Friedman // result conflicted with the Visited list; we have to conservatively 1189a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman // assume it is unknown, but this also does not block PRE of the load. 1190fc09797426894602355d248edb174676ec7fd560Eli Friedman if (!CanTranslate || 1191fc09797426894602355d248edb174676ec7fd560Eli Friedman getNonLocalPointerDepFromBB(PredPointer, 1192fc09797426894602355d248edb174676ec7fd560Eli Friedman Loc.getWithNewPtr(PredPtrVal), 1193fc09797426894602355d248edb174676ec7fd560Eli Friedman isLoad, Pred, 1194fc09797426894602355d248edb174676ec7fd560Eli Friedman Result, Visited)) { 1195855d9da596062b5742a27d9d96c38528120f391bChris Lattner // Add the entry to the Result list. 1196a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman NonLocalDepResult Entry(Pred, MemDepResult::getUnknown(), PredPtrVal); 1197855d9da596062b5742a27d9d96c38528120f391bChris Lattner Result.push_back(Entry); 1198855d9da596062b5742a27d9d96c38528120f391bChris Lattner 1199f648125be9385a0d4abfd5e77ea3dd40694c4c07Chris Lattner // Since we had a phi translation failure, the cache for CacheKey won't 1200f648125be9385a0d4abfd5e77ea3dd40694c4c07Chris Lattner // include all of the entries that we need to immediately satisfy future 1201f648125be9385a0d4abfd5e77ea3dd40694c4c07Chris Lattner // queries. Mark this in NonLocalPointerDeps by setting the 1202f648125be9385a0d4abfd5e77ea3dd40694c4c07Chris Lattner // BBSkipFirstBlockPair pointer to null. This requires reuse of the 1203f648125be9385a0d4abfd5e77ea3dd40694c4c07Chris Lattner // cached value to do more work but not miss the phi trans failure. 1204c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey]; 1205c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman NLPI.Pair = BBSkipFirstBlockPair(); 12066f7b210b2577fbc9247a9fc5223655390008ae89Chris Lattner continue; 12076f7b210b2577fbc9247a9fc5223655390008ae89Chris Lattner } 12089e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner } 12096178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1210e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner // Refresh the CacheInfo/Cache pointer so that it isn't invalidated. 1211e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner CacheInfo = &NonLocalPointerDeps[CacheKey]; 1212c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman Cache = &CacheInfo->NonLocalDeps; 1213e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner NumSortedEntries = Cache->size(); 12146178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1215e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner // Since we did phi translation, the "Cache" set won't contain all of the 1216e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner // results for the query. This is ok (we can still use it to accelerate 1217e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner // specific block queries) but we can't do the fastpath "return all 1218e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner // results from the set" Clear out the indicator for this. 1219c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman CacheInfo->Pair = BBSkipFirstBlockPair(); 1220e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner SkipFirstBlock = false; 1221e95035aea481f70a6ea9183a7e133f8e9a98e073Chris Lattner continue; 1222dc59311c5c1fef7788f58096c6f417df2b5b72dfChris Lattner 12239e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner PredTranslationFailure: 1224fc09797426894602355d248edb174676ec7fd560Eli Friedman // The following code is "failure"; we can't produce a sane translation 1225fc09797426894602355d248edb174676ec7fd560Eli Friedman // for the given block. It assumes that we haven't modified any of 1226fc09797426894602355d248edb174676ec7fd560Eli Friedman // our datastructures while processing the current block. 12276178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1228dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Cache) { 122995900f2dda0d573b927a54910386130b779a48ffChris Lattner // Refresh the CacheInfo/Cache pointer if it got invalidated. 123095900f2dda0d573b927a54910386130b779a48ffChris Lattner CacheInfo = &NonLocalPointerDeps[CacheKey]; 1231c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman Cache = &CacheInfo->NonLocalDeps; 123295900f2dda0d573b927a54910386130b779a48ffChris Lattner NumSortedEntries = Cache->size(); 123395900f2dda0d573b927a54910386130b779a48ffChris Lattner } 12346178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1235f648125be9385a0d4abfd5e77ea3dd40694c4c07Chris Lattner // Since we failed phi translation, the "Cache" set won't contain all of the 12369e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // results for the query. This is ok (we can still use it to accelerate 12379e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // specific block queries) but we can't do the fastpath "return all 1238f648125be9385a0d4abfd5e77ea3dd40694c4c07Chris Lattner // results from the set". Clear out the indicator for this. 1239c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman CacheInfo->Pair = BBSkipFirstBlockPair(); 12406178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1241a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman // If *nothing* works, mark the pointer as unknown. 12429e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // 12439e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // If this is the magic first block, return this as a clobber of the whole 12449e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // incoming value. Since we can't phi translate to one of the predecessors, 12459e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner // we have to bail out. 12469e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner if (SkipFirstBlock) 12479e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner return true; 12486178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 12499e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner for (NonLocalDepInfo::reverse_iterator I = Cache->rbegin(); ; ++I) { 12509e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner assert(I != Cache->rend() && "Didn't find current block??"); 1251e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner if (I->getBB() != BB) 12529e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner continue; 12536178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1254e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner assert(I->getResult().isNonLocal() && 12559e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner "Should only be here with transparent block"); 1256a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman I->setResult(MemDepResult::getUnknown()); 12570ee443d169786017d151034b8bd34225bc144c98Chris Lattner Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), 12580ee443d169786017d151034b8bd34225bc144c98Chris Lattner Pointer.getAddr())); 12599e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner break; 12609a193fd8ae630478123938e12b56f84c5b2227b9Chris Lattner } 12617ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner } 126295900f2dda0d573b927a54910386130b779a48ffChris Lattner 12639863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner // Okay, we're done now. If we added new values to the cache, re-sort it. 1264a2f55dd388e1fb33b553a5862bca0fe4bd4b781eChris Lattner SortNonLocalDepInfoCache(*Cache, NumSortedEntries); 126512a7db383090dd21b1f8488be330a274cffaff3cChris Lattner DEBUG(AssertSorted(*Cache)); 12669e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner return false; 12676290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner} 12686290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner 12696290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner/// RemoveCachedNonLocalPointerDependencies - If P exists in 12706290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner/// CachedNonLocalPointerInfo, remove it. 12716290f5cac23399201f8785e5ca8b305e42a1342cChris Lattnervoid MemoryDependenceAnalysis:: 12726290f5cac23399201f8785e5ca8b305e42a1342cChris LattnerRemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P) { 12736178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak CachedNonLocalPointerInfo::iterator It = 12746290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner NonLocalPointerDeps.find(P); 12756290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner if (It == NonLocalPointerDeps.end()) return; 12766178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 12776290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // Remove all of the entries in the BB->val map. This involves removing 12786290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // instructions from the reverse map. 1279c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman NonLocalDepInfo &PInfo = It->second.NonLocalDeps; 12806178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 12816290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner for (unsigned i = 0, e = PInfo.size(); i != e; ++i) { 1282e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner Instruction *Target = PInfo[i].getResult().getInst(); 1283dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Target) continue; // Ignore non-local dep results. 1284e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner assert(Target->getParent() == PInfo[i].getBB()); 12856178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 12866290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // Eliminating the dirty entry from 'Cache', so update the reverse info. 12876a0dcc10778468b1556474aa43d4a86a14ab15d7Chris Lattner RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P); 12886290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner } 12896178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 12906290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo). 12916290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner NonLocalPointerDeps.erase(It); 12927ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner} 12937ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner 12947ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner 1295bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner/// invalidateCachedPointerInfo - This method is used to invalidate cached 1296bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner/// information about the specified pointer, because it may be too 1297bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner/// conservative in memdep. This is an optional call that can be used when 1298bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner/// the client detects an equivalence between the pointer and some other 1299bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner/// value and replaces the other value with ptr. This can make Ptr available 1300bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner/// in more places that cached info does not necessarily keep. 1301bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattnervoid MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) { 1302bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner // If Ptr isn't really a pointer, just ignore it. 13031df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (!Ptr->getType()->isPointerTy()) return; 1304bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner // Flush store info for the pointer. 1305bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, false)); 1306bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner // Flush load info for the pointer. 1307bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true)); 1308bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner} 1309bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner 1310484d4a30c055eef3101d01a7a468db3413dd20d3Bob Wilson/// invalidateCachedPredecessors - Clear the PredIteratorCache info. 1311484d4a30c055eef3101d01a7a468db3413dd20d3Bob Wilson/// This needs to be done when the CFG changes, e.g., due to splitting 1312484d4a30c055eef3101d01a7a468db3413dd20d3Bob Wilson/// critical edges. 1313484d4a30c055eef3101d01a7a468db3413dd20d3Bob Wilsonvoid MemoryDependenceAnalysis::invalidateCachedPredecessors() { 1314484d4a30c055eef3101d01a7a468db3413dd20d3Bob Wilson PredCache->clear(); 1315484d4a30c055eef3101d01a7a468db3413dd20d3Bob Wilson} 1316484d4a30c055eef3101d01a7a468db3413dd20d3Bob Wilson 131778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson/// removeInstruction - Remove an instruction from the dependence analysis, 131878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson/// updating the dependence of instructions that previously depended on it. 1319642a9e3436dfe2afcaee6fb734d02c006d32ba3aOwen Anderson/// This method attempts to keep the cache coherent using the reverse map. 13205f589dc77f459d169495ab1e0e03de3740a3b290Chris Lattnervoid MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { 13215f589dc77f459d169495ab1e0e03de3740a3b290Chris Lattner // Walk through the Non-local dependencies, removing this one as the value 13225f589dc77f459d169495ab1e0e03de3740a3b290Chris Lattner // for any cached queries. 1323f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst); 1324f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner if (NLDI != NonLocalDeps.end()) { 1325bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner NonLocalDepInfo &BlockMap = NLDI->second.first; 132625f4b2b7a3f1f2bbaf954257e7834ba29a6ede7cChris Lattner for (NonLocalDepInfo::iterator DI = BlockMap.begin(), DE = BlockMap.end(); 132725f4b2b7a3f1f2bbaf954257e7834ba29a6ede7cChris Lattner DI != DE; ++DI) 1328e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner if (Instruction *Inst = DI->getResult().getInst()) 1329d44745d24175079f0675c6199ab9929d19edd1aaChris Lattner RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst); 1330f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner NonLocalDeps.erase(NLDI); 1331f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner } 1332df464195fe049d5ea921e2e37f4f833c2ea4e3ecDavid Greene 13335f589dc77f459d169495ab1e0e03de3740a3b290Chris Lattner // If we have a cached local dependence query for this instruction, remove it. 1334baad8881f1d87b50053edc862248dc6cb15af81bChris Lattner // 133539f372e23e49cecb8db2eb7120eb331173e50c74Chris Lattner LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst); 133639f372e23e49cecb8db2eb7120eb331173e50c74Chris Lattner if (LocalDepEntry != LocalDeps.end()) { 1337baad8881f1d87b50053edc862248dc6cb15af81bChris Lattner // Remove us from DepInst's reverse set now that the local dep info is gone. 1338d44745d24175079f0675c6199ab9929d19edd1aaChris Lattner if (Instruction *Inst = LocalDepEntry->second.getInst()) 1339d44745d24175079f0675c6199ab9929d19edd1aaChris Lattner RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst); 1340125ce362693350ebe713b58c92a9c0ced26680eaChris Lattner 1341125ce362693350ebe713b58c92a9c0ced26680eaChris Lattner // Remove this local dependency info. 1342125ce362693350ebe713b58c92a9c0ced26680eaChris Lattner LocalDeps.erase(LocalDepEntry); 13436290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner } 13446178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 13456290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // If we have any cached pointer dependencies on this instruction, remove 13466290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // them. If the instruction has non-pointer type, then it can't be a pointer 13476290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // base. 13486178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 13496290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // Remove it from both the load info and the store info. The instruction 13506290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // can't be in either of these maps if it is non-pointer. 13511df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (RemInst->getType()->isPointerTy()) { 13526290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false)); 13536290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true)); 13546290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner } 13556178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1356d3d12ecadd1eb859c4b30b6582e31901a45d6626Chris Lattner // Loop over all of the things that depend on the instruction we're removing. 13576178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak // 13584f8c18c7c757875cfa45383e7cf33d65d2c4d564Chris Lattner SmallVector<std::pair<Instruction*, Instruction*>, 8> ReverseDepsToAdd; 13590655f73ef7e423a7802f2056b473a1f1caa3996dChris Lattner 13600655f73ef7e423a7802f2056b473a1f1caa3996dChris Lattner // If we find RemInst as a clobber or Def in any of the maps for other values, 13610655f73ef7e423a7802f2056b473a1f1caa3996dChris Lattner // we need to replace its entry with a dirty version of the instruction after 13620655f73ef7e423a7802f2056b473a1f1caa3996dChris Lattner // it. If RemInst is a terminator, we use a null dirty value. 13630655f73ef7e423a7802f2056b473a1f1caa3996dChris Lattner // 13640655f73ef7e423a7802f2056b473a1f1caa3996dChris Lattner // Using a dirty version of the instruction after RemInst saves having to scan 13650655f73ef7e423a7802f2056b473a1f1caa3996dChris Lattner // the entire block to get to this point. 13660655f73ef7e423a7802f2056b473a1f1caa3996dChris Lattner MemDepResult NewDirtyVal; 13670655f73ef7e423a7802f2056b473a1f1caa3996dChris Lattner if (!RemInst->isTerminator()) 13680655f73ef7e423a7802f2056b473a1f1caa3996dChris Lattner NewDirtyVal = MemDepResult::getDirty(++BasicBlock::iterator(RemInst)); 13696178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 13708c4652790e04515f34cf920b0783d6ec4161a313Chris Lattner ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst); 13718c4652790e04515f34cf920b0783d6ec4161a313Chris Lattner if (ReverseDepIt != ReverseLocalDeps.end()) { 1372d3d12ecadd1eb859c4b30b6582e31901a45d6626Chris Lattner SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second; 13736290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // RemInst can't be the terminator if it has local stuff depending on it. 1374125ce362693350ebe713b58c92a9c0ced26680eaChris Lattner assert(!ReverseDeps.empty() && !isa<TerminatorInst>(RemInst) && 1375125ce362693350ebe713b58c92a9c0ced26680eaChris Lattner "Nothing can locally depend on a terminator"); 13766178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1377d3d12ecadd1eb859c4b30b6582e31901a45d6626Chris Lattner for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(), 1378d3d12ecadd1eb859c4b30b6582e31901a45d6626Chris Lattner E = ReverseDeps.end(); I != E; ++I) { 1379d3d12ecadd1eb859c4b30b6582e31901a45d6626Chris Lattner Instruction *InstDependingOnRemInst = *I; 1380f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner assert(InstDependingOnRemInst != RemInst && 1381f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner "Already removed our local dep info"); 13826178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 13830655f73ef7e423a7802f2056b473a1f1caa3996dChris Lattner LocalDeps[InstDependingOnRemInst] = NewDirtyVal; 13846178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1385125ce362693350ebe713b58c92a9c0ced26680eaChris Lattner // Make sure to remember that new things depend on NewDepInst. 13860655f73ef7e423a7802f2056b473a1f1caa3996dChris Lattner assert(NewDirtyVal.getInst() && "There is no way something else can have " 13870655f73ef7e423a7802f2056b473a1f1caa3996dChris Lattner "a local dep on this if it is a terminator!"); 13886178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak ReverseDepsToAdd.push_back(std::make_pair(NewDirtyVal.getInst(), 1389125ce362693350ebe713b58c92a9c0ced26680eaChris Lattner InstDependingOnRemInst)); 13904f8c18c7c757875cfa45383e7cf33d65d2c4d564Chris Lattner } 13916178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 13924f8c18c7c757875cfa45383e7cf33d65d2c4d564Chris Lattner ReverseLocalDeps.erase(ReverseDepIt); 13934f8c18c7c757875cfa45383e7cf33d65d2c4d564Chris Lattner 13944f8c18c7c757875cfa45383e7cf33d65d2c4d564Chris Lattner // Add new reverse deps after scanning the set, to avoid invalidating the 13954f8c18c7c757875cfa45383e7cf33d65d2c4d564Chris Lattner // 'ReverseDeps' reference. 13964f8c18c7c757875cfa45383e7cf33d65d2c4d564Chris Lattner while (!ReverseDepsToAdd.empty()) { 13974f8c18c7c757875cfa45383e7cf33d65d2c4d564Chris Lattner ReverseLocalDeps[ReverseDepsToAdd.back().first] 13984f8c18c7c757875cfa45383e7cf33d65d2c4d564Chris Lattner .insert(ReverseDepsToAdd.back().second); 13994f8c18c7c757875cfa45383e7cf33d65d2c4d564Chris Lattner ReverseDepsToAdd.pop_back(); 1400d3d12ecadd1eb859c4b30b6582e31901a45d6626Chris Lattner } 140178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson } 14026178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 14038c4652790e04515f34cf920b0783d6ec4161a313Chris Lattner ReverseDepIt = ReverseNonLocalDeps.find(RemInst); 14048c4652790e04515f34cf920b0783d6ec4161a313Chris Lattner if (ReverseDepIt != ReverseNonLocalDeps.end()) { 14056290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner SmallPtrSet<Instruction*, 4> &Set = ReverseDepIt->second; 14066290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner for (SmallPtrSet<Instruction*, 4>::iterator I = Set.begin(), E = Set.end(); 1407f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner I != E; ++I) { 1408f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner assert(*I != RemInst && "Already removed NonLocalDep info for RemInst"); 14096178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 14104a69bade2385022ca776edc22150f3b750cdf23cChris Lattner PerInstNLInfo &INLD = NonLocalDeps[*I]; 14114a69bade2385022ca776edc22150f3b750cdf23cChris Lattner // The information is now dirty! 1412bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner INLD.second = true; 14136178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 14146178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak for (NonLocalDepInfo::iterator DI = INLD.first.begin(), 1415bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner DE = INLD.first.end(); DI != DE; ++DI) { 1416e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner if (DI->getResult().getInst() != RemInst) continue; 14176178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1418f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner // Convert to a dirty entry for the subsequent instruction. 14190ee443d169786017d151034b8bd34225bc144c98Chris Lattner DI->setResult(NewDirtyVal); 14206178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 14210655f73ef7e423a7802f2056b473a1f1caa3996dChris Lattner if (Instruction *NextI = NewDirtyVal.getInst()) 1422f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner ReverseDepsToAdd.push_back(std::make_pair(NextI, *I)); 1423f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner } 1424f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner } 14254f8c18c7c757875cfa45383e7cf33d65d2c4d564Chris Lattner 14264f8c18c7c757875cfa45383e7cf33d65d2c4d564Chris Lattner ReverseNonLocalDeps.erase(ReverseDepIt); 14274f8c18c7c757875cfa45383e7cf33d65d2c4d564Chris Lattner 14280ec48ddef20deaa061152d86645972122beef605Chris Lattner // Add new reverse deps after scanning the set, to avoid invalidating 'Set' 14290ec48ddef20deaa061152d86645972122beef605Chris Lattner while (!ReverseDepsToAdd.empty()) { 14300ec48ddef20deaa061152d86645972122beef605Chris Lattner ReverseNonLocalDeps[ReverseDepsToAdd.back().first] 14310ec48ddef20deaa061152d86645972122beef605Chris Lattner .insert(ReverseDepsToAdd.back().second); 14320ec48ddef20deaa061152d86645972122beef605Chris Lattner ReverseDepsToAdd.pop_back(); 14330ec48ddef20deaa061152d86645972122beef605Chris Lattner } 14344d13de4e3bfc5121207efd01e1b31caa6bb4e40bOwen Anderson } 14356178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 14366290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // If the instruction is in ReverseNonLocalPtrDeps then it appears as a 14376290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // value in the NonLocalPointerDeps info. 14386290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt = 14396290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner ReverseNonLocalPtrDeps.find(RemInst); 14406290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) { 14416a0dcc10778468b1556474aa43d4a86a14ab15d7Chris Lattner SmallPtrSet<ValueIsLoadPair, 4> &Set = ReversePtrDepIt->second; 14426290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner SmallVector<std::pair<Instruction*, ValueIsLoadPair>,8> ReversePtrDepsToAdd; 14436178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 14446a0dcc10778468b1556474aa43d4a86a14ab15d7Chris Lattner for (SmallPtrSet<ValueIsLoadPair, 4>::iterator I = Set.begin(), 14456a0dcc10778468b1556474aa43d4a86a14ab15d7Chris Lattner E = Set.end(); I != E; ++I) { 14466a0dcc10778468b1556474aa43d4a86a14ab15d7Chris Lattner ValueIsLoadPair P = *I; 14476290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner assert(P.getPointer() != RemInst && 14486290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner "Already removed NonLocalPointerDeps info for RemInst"); 14496178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1450c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].NonLocalDeps; 14516178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 145211dcd8d38de031c34380fd6ab7a0daacdefb263aChris Lattner // The cache is not valid for any specific block anymore. 1453c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman NonLocalPointerDeps[P].Pair = BBSkipFirstBlockPair(); 14546178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 14556290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // Update any entries for RemInst to use the instruction after it. 14566290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end(); 14576290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner DI != DE; ++DI) { 1458e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner if (DI->getResult().getInst() != RemInst) continue; 14596178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 14606290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // Convert to a dirty entry for the subsequent instruction. 14610ee443d169786017d151034b8bd34225bc144c98Chris Lattner DI->setResult(NewDirtyVal); 14626178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 14636290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner if (Instruction *NewDirtyInst = NewDirtyVal.getInst()) 14646290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P)); 14656290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner } 14666178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 146795900f2dda0d573b927a54910386130b779a48ffChris Lattner // Re-sort the NonLocalDepInfo. Changing the dirty entry to its 146895900f2dda0d573b927a54910386130b779a48ffChris Lattner // subsequent value may invalidate the sortedness. 146995900f2dda0d573b927a54910386130b779a48ffChris Lattner std::sort(NLPDI.begin(), NLPDI.end()); 14706290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner } 14716178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 14726290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner ReverseNonLocalPtrDeps.erase(ReversePtrDepIt); 14736178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 14746290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner while (!ReversePtrDepsToAdd.empty()) { 14756290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first] 14766a0dcc10778468b1556474aa43d4a86a14ab15d7Chris Lattner .insert(ReversePtrDepsToAdd.back().second); 14776290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner ReversePtrDepsToAdd.pop_back(); 14786290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner } 14796290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner } 14806178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 14816178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1482f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?"); 1483d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner AA->deleteValue(RemInst); 1484f7624bc6dd57d5b4deea7c336c3e3aec67f38c9bJakob Stoklund Olesen DEBUG(verifyRemoved(RemInst)); 148578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson} 1486729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner/// verifyRemoved - Verify that the specified instruction does not occur 1487729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner/// in our internal data structures. 1488729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattnervoid MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const { 1489729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner for (LocalDepMapType::const_iterator I = LocalDeps.begin(), 1490729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner E = LocalDeps.end(); I != E; ++I) { 1491729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner assert(I->first != D && "Inst occurs in data structures"); 1492fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner assert(I->second.getInst() != D && 1493729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner "Inst occurs in data structures"); 1494729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner } 14956178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 14966290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner for (CachedNonLocalPointerInfo::const_iterator I =NonLocalPointerDeps.begin(), 14976290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner E = NonLocalPointerDeps.end(); I != E; ++I) { 14986290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner assert(I->first.getPointer() != D && "Inst occurs in NLPD map key"); 1499c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman const NonLocalDepInfo &Val = I->second.NonLocalDeps; 15006290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner for (NonLocalDepInfo::const_iterator II = Val.begin(), E = Val.end(); 15016290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner II != E; ++II) 1502e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner assert(II->getResult().getInst() != D && "Inst occurs as NLPD value"); 15036290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner } 15046178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1505729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(), 1506729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner E = NonLocalDeps.end(); I != E; ++I) { 1507729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner assert(I->first != D && "Inst occurs in data structures"); 15084a69bade2385022ca776edc22150f3b750cdf23cChris Lattner const PerInstNLInfo &INLD = I->second; 1509bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner for (NonLocalDepInfo::const_iterator II = INLD.first.begin(), 1510bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner EE = INLD.first.end(); II != EE; ++II) 1511e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner assert(II->getResult().getInst() != D && "Inst occurs in data structures"); 1512729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner } 15136178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1514729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(), 1515f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner E = ReverseLocalDeps.end(); I != E; ++I) { 1516f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner assert(I->first != D && "Inst occurs in data structures"); 1517729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(), 1518729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner EE = I->second.end(); II != EE; ++II) 1519729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner assert(*II != D && "Inst occurs in data structures"); 1520f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner } 15216178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1522729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(), 1523729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner E = ReverseNonLocalDeps.end(); 1524f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner I != E; ++I) { 1525f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner assert(I->first != D && "Inst occurs in data structures"); 1526729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(), 1527729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner EE = I->second.end(); II != EE; ++II) 1528729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner assert(*II != D && "Inst occurs in data structures"); 1529f68f310386c8e1772a3e6eba01f09590678a8f96Chris Lattner } 15306178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 15316290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner for (ReverseNonLocalPtrDepTy::const_iterator 15326290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner I = ReverseNonLocalPtrDeps.begin(), 15336290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner E = ReverseNonLocalPtrDeps.end(); I != E; ++I) { 15346290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner assert(I->first != D && "Inst occurs in rev NLPD map"); 15356178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 15366a0dcc10778468b1556474aa43d4a86a14ab15d7Chris Lattner for (SmallPtrSet<ValueIsLoadPair, 4>::const_iterator II = I->second.begin(), 15376290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner E = I->second.end(); II != E; ++II) 15386a0dcc10778468b1556474aa43d4a86a14ab15d7Chris Lattner assert(*II != ValueIsLoadPair(D, false) && 15396a0dcc10778468b1556474aa43d4a86a14ab15d7Chris Lattner *II != ValueIsLoadPair(D, true) && 15406290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner "Inst occurs in ReverseNonLocalPtrDeps map"); 15416290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner } 15426178e5f50c0c8be26913cd93238a5035a39cdf37Jakub Staszak 1543729b23758ab990a7bd07ceb5ac6af04c32f40a76Chris Lattner} 1544