MemoryDependenceAnalysis.h revision 20d6f0982ad33818cfa141f80157ac13e36d5550
178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson//===- llvm/Analysis/MemoryDependenceAnalysis.h - Memory Deps --*- C++ -*-===// 278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// The LLVM Compiler Infrastructure 478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson//===----------------------------------------------------------------------===// 978e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 10e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner// This file defines the MemoryDependenceAnalysis analysis pass. 1178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson// 1278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson//===----------------------------------------------------------------------===// 1378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 1478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#ifndef LLVM_ANALYSIS_MEMORY_DEPENDENCE_H 1578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#define LLVM_ANALYSIS_MEMORY_DEPENDENCE_H 1678e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 175391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner#include "llvm/BasicBlock.h" 1878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#include "llvm/Pass.h" 1978e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#include "llvm/ADT/DenseMap.h" 204beedbd0063a8ba6f97db02c3c94707d8ab45b50Owen Anderson#include "llvm/ADT/SmallPtrSet.h" 214012fdda13710d21b415a79475adc2bbb6628527Chris Lattner#include "llvm/ADT/OwningPtr.h" 2239f372e23e49cecb8db2eb7120eb331173e50c74Chris Lattner#include "llvm/ADT/PointerIntPair.h" 2378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 2478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Andersonnamespace llvm { 25e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner class Function; 26e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner class FunctionPass; 27e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner class Instruction; 28b390b1728e6c36f1f28d75d6f8f27cb91f8a8c56Chris Lattner class CallSite; 29d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner class AliasAnalysis; 30d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner class TargetData; 31fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner class MemoryDependenceAnalysis; 324012fdda13710d21b415a79475adc2bbb6628527Chris Lattner class PredIteratorCache; 334c724006256032e827177afeae04ea62436796e7Chris Lattner 344c724006256032e827177afeae04ea62436796e7Chris Lattner /// MemDepResult - A memory dependence query can return one of three different 35fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// answers, described below. 364c724006256032e827177afeae04ea62436796e7Chris Lattner class MemDepResult { 374c724006256032e827177afeae04ea62436796e7Chris Lattner enum DepType { 38fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// Invalid - Clients of MemDep never see this. 39fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner Invalid = 0, 400f41ad3bc9a295332a8e6d025b42cebc9b9e8125Chris Lattner 41b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// Clobber - This is a dependence on the specified instruction which 42b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// clobbers the desired value. The pointer member of the MemDepResult 43b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// pair holds the instruction that clobbers the memory. For example, 44b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// this occurs when we see a may-aliased store to the memory location we 45b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// care about. 46b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner Clobber, 47fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner 48b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// Def - This is a dependence on the specified instruction which 49b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// defines/produces the desired memory location. The pointer member of 50b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// the MemDepResult pair holds the instruction that defines the memory. 51b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// Cases of interest: 52b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// 1. This could be a load or store for dependence queries on 53b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// load/store. The value loaded or stored is the produced value. 54b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// Note that the pointer operand may be different than that of the 55b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// queried pointer due to must aliases and phi translation. Note 56b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// that the def may not be the same type as the query, the pointers 57b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// may just be must aliases. 58b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// 2. For loads and stores, this could be an allocation instruction. In 59b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// this case, the load is loading an undef value or a store is the 60b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// first store to (that part of) the allocation. 61b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// 3. Dependence queries on calls return Def only when they are 62b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// readonly calls with identical callees and no intervening 63b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// clobbers. No validation is done that the operands to the calls 64b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// are the same. 65b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner Def, 66b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner 67fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// NonLocal - This marker indicates that the query has no dependency in 68fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// the specified block. To find out more, the client should query other 69fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// predecessor blocks. 70b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner NonLocal 714c724006256032e827177afeae04ea62436796e7Chris Lattner }; 724c724006256032e827177afeae04ea62436796e7Chris Lattner typedef PointerIntPair<Instruction*, 2, DepType> PairTy; 734c724006256032e827177afeae04ea62436796e7Chris Lattner PairTy Value; 744c724006256032e827177afeae04ea62436796e7Chris Lattner explicit MemDepResult(PairTy V) : Value(V) {} 754c724006256032e827177afeae04ea62436796e7Chris Lattner public: 764c724006256032e827177afeae04ea62436796e7Chris Lattner MemDepResult() : Value(0, Invalid) {} 774c724006256032e827177afeae04ea62436796e7Chris Lattner 784c724006256032e827177afeae04ea62436796e7Chris Lattner /// get methods: These are static ctor methods for creating various 794c724006256032e827177afeae04ea62436796e7Chris Lattner /// MemDepResult kinds. 80b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner static MemDepResult getDef(Instruction *Inst) { 81b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner return MemDepResult(PairTy(Inst, Def)); 82b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner } 83b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner static MemDepResult getClobber(Instruction *Inst) { 84b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner return MemDepResult(PairTy(Inst, Clobber)); 854c724006256032e827177afeae04ea62436796e7Chris Lattner } 864c724006256032e827177afeae04ea62436796e7Chris Lattner static MemDepResult getNonLocal() { 874c724006256032e827177afeae04ea62436796e7Chris Lattner return MemDepResult(PairTy(0, NonLocal)); 884c724006256032e827177afeae04ea62436796e7Chris Lattner } 894c724006256032e827177afeae04ea62436796e7Chris Lattner 90b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// isClobber - Return true if this MemDepResult represents a query that is 91b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// a instruction clobber dependency. 92b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner bool isClobber() const { return Value.getInt() == Clobber; } 93b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner 94b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// isDef - Return true if this MemDepResult represents a query that is 95b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// a instruction definition dependency. 96b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner bool isDef() const { return Value.getInt() == Def; } 974c724006256032e827177afeae04ea62436796e7Chris Lattner 984c724006256032e827177afeae04ea62436796e7Chris Lattner /// isNonLocal - Return true if this MemDepResult represents an query that 994c724006256032e827177afeae04ea62436796e7Chris Lattner /// is transparent to the start of the block, but where a non-local hasn't 1004c724006256032e827177afeae04ea62436796e7Chris Lattner /// been done. 10186b29ef64a36c8779ef7855b3c4b95744eb2f08bChris Lattner bool isNonLocal() const { return Value.getInt() == NonLocal; } 1024c724006256032e827177afeae04ea62436796e7Chris Lattner 1034c724006256032e827177afeae04ea62436796e7Chris Lattner /// getInst() - If this is a normal dependency, return the instruction that 1044c724006256032e827177afeae04ea62436796e7Chris Lattner /// is depended on. Otherwise, return null. 105fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner Instruction *getInst() const { return Value.getPointer(); } 1064c724006256032e827177afeae04ea62436796e7Chris Lattner 107bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner bool operator==(const MemDepResult &M) const { return M.Value == Value; } 108bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner bool operator!=(const MemDepResult &M) const { return M.Value != Value; } 109bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner bool operator<(const MemDepResult &M) const { return M.Value < Value; } 110bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner bool operator>(const MemDepResult &M) const { return M.Value > Value; } 111fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner private: 112fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner friend class MemoryDependenceAnalysis; 113fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// Dirty - Entries with this marker occur in a LocalDeps map or 114fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// NonLocalDeps map when the instruction they previously referenced was 115fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// removed from MemDep. In either case, the entry may include an 116fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// instruction pointer. If so, the pointer is an instruction in the 117fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// block where scanning can start from, saving some work. 118fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// 119bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner /// In a default-constructed MemDepResult object, the type will be Dirty 120fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// and the instruction pointer will be null. 121fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// 122bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner 123fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// isDirty - Return true if this is a MemDepResult in its dirty/invalid. 124fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// state. 125fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner bool isDirty() const { return Value.getInt() == Invalid; } 126bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner 127fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner static MemDepResult getDirty(Instruction *Inst) { 128fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner return MemDepResult(PairTy(Inst, Invalid)); 129fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner } 1304c724006256032e827177afeae04ea62436796e7Chris Lattner }; 13178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 132e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner /// MemoryDependenceAnalysis - This is an analysis that determines, for a 133e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner /// given memory operation, what preceding memory operations it depends on. 134e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner /// It builds on alias analysis information, and tries to provide a lazy, 135e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner /// caching interface to a common kind of alias information query. 1360e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// 1370e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// The dependency information returned is somewhat unusual, but is pragmatic. 1380e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// If queried about a store or call that might modify memory, the analysis 1390e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// will return the instruction[s] that may either load from that memory or 1400e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// store to it. If queried with a load or call that can never modify memory, 1410e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// the analysis will return calls and stores that might modify the pointer, 1420e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// but generally does not return loads unless a) they are volatile, or 1430e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// b) they load from *must-aliased* pointers. Returning a dependence on 1440e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// must-alias'd pointers instead of all pointers interacts well with the 1450e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// internal caching mechanism. 1460e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// 147e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner class MemoryDependenceAnalysis : public FunctionPass { 1487f52422a3c821c1deb7171808ffcf83386970791Chris Lattner // A map from instructions to their dependency. 149fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner typedef DenseMap<Instruction*, MemDepResult> LocalDepMapType; 15039f372e23e49cecb8db2eb7120eb331173e50c74Chris Lattner LocalDepMapType LocalDeps; 151df464195fe049d5ea921e2e37f4f833c2ea4e3ecDavid Greene 152bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner public: 153bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner typedef std::pair<BasicBlock*, MemDepResult> NonLocalDepEntry; 154bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner typedef std::vector<NonLocalDepEntry> NonLocalDepInfo; 155bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner private: 1566290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner /// ValueIsLoadPair - This is a pair<Value*, bool> where the bool is true if 1576290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner /// the dependence is a read only dependence, false if read/write. 158c765a5acad26ae3d86832d4153e6569d1043a9caDan Gohman typedef PointerIntPair<Value*, 1, bool> ValueIsLoadPair; 1596290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner 1606290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner /// CachedNonLocalPointerInfo - This map stores the cached results of doing 161e91a4881e17127686345f62df08da6370b14d51fChris Lattner /// a pointer lookup at the bottom of a block. The key of this map is the 1626290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner /// pointer+isload bit, the value is a list of <bb->result> mappings. 16311dcd8d38de031c34380fd6ab7a0daacdefb263aChris Lattner typedef DenseMap<ValueIsLoadPair, 16411dcd8d38de031c34380fd6ab7a0daacdefb263aChris Lattner std::pair<BasicBlock*, NonLocalDepInfo> > CachedNonLocalPointerInfo; 1656290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner CachedNonLocalPointerInfo NonLocalPointerDeps; 1666290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner 1676290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // A map from instructions to their non-local pointer dependencies. 1686290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // The elements of the SmallPtrSet are ValueIsLoadPair's. 1696290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner typedef DenseMap<Instruction*, 1706290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner SmallPtrSet<void*, 4> > ReverseNonLocalPtrDepTy; 1716290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner ReverseNonLocalPtrDepTy ReverseNonLocalPtrDeps; 1726290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner 1736290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner 1744a69bade2385022ca776edc22150f3b750cdf23cChris Lattner /// PerInstNLInfo - This is the instruction we keep for each cached access 1754a69bade2385022ca776edc22150f3b750cdf23cChris Lattner /// that we have for an instruction. The pointer is an owning pointer and 1764a69bade2385022ca776edc22150f3b750cdf23cChris Lattner /// the bool indicates whether we have any dirty bits in the set. 177bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner typedef std::pair<NonLocalDepInfo, bool> PerInstNLInfo; 17825f4b2b7a3f1f2bbaf954257e7834ba29a6ede7cChris Lattner 1794d13de4e3bfc5121207efd01e1b31caa6bb4e40bOwen Anderson // A map from instructions to their non-local dependencies. 1804a69bade2385022ca776edc22150f3b750cdf23cChris Lattner typedef DenseMap<Instruction*, PerInstNLInfo> NonLocalDepMapType; 1814a69bade2385022ca776edc22150f3b750cdf23cChris Lattner 1828c4652790e04515f34cf920b0783d6ec4161a313Chris Lattner NonLocalDepMapType NonLocalDeps; 1834d13de4e3bfc5121207efd01e1b31caa6bb4e40bOwen Anderson 184956033a4f5de491fcc07bc3ef0700ad22fd836a0Chris Lattner // A reverse mapping from dependencies to the dependees. This is 185179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson // used when removing instructions to keep the cache coherent. 1867f52422a3c821c1deb7171808ffcf83386970791Chris Lattner typedef DenseMap<Instruction*, 1878c4652790e04515f34cf920b0783d6ec4161a313Chris Lattner SmallPtrSet<Instruction*, 4> > ReverseDepMapType; 1888c4652790e04515f34cf920b0783d6ec4161a313Chris Lattner ReverseDepMapType ReverseLocalDeps; 18978e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 1904d13de4e3bfc5121207efd01e1b31caa6bb4e40bOwen Anderson // A reverse mapping form dependencies to the non-local dependees. 1918c4652790e04515f34cf920b0783d6ec4161a313Chris Lattner ReverseDepMapType ReverseNonLocalDeps; 1924d13de4e3bfc5121207efd01e1b31caa6bb4e40bOwen Anderson 193d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner /// Current AA implementation, just a cache. 194d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner AliasAnalysis *AA; 195d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner TargetData *TD; 1964012fdda13710d21b415a79475adc2bbb6628527Chris Lattner OwningPtr<PredIteratorCache> PredCache; 197179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson public: 1984012fdda13710d21b415a79475adc2bbb6628527Chris Lattner MemoryDependenceAnalysis(); 1994012fdda13710d21b415a79475adc2bbb6628527Chris Lattner ~MemoryDependenceAnalysis(); 20039f372e23e49cecb8db2eb7120eb331173e50c74Chris Lattner static char ID; 2011cee94f04111cfd7114979d6dfddce2669c9380dDevang Patel 202d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner /// Pass Implementation stuff. This doesn't do any analysis eagerly. 203d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner bool runOnFunction(Function &); 2046b278fc7860c1e0e5cf72340e43f78a87159be4cOwen Anderson 2056b278fc7860c1e0e5cf72340e43f78a87159be4cOwen Anderson /// Clean up memory in between runs 2064012fdda13710d21b415a79475adc2bbb6628527Chris Lattner void releaseMemory(); 2074012fdda13710d21b415a79475adc2bbb6628527Chris Lattner 20878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// getAnalysisUsage - Does not modify anything. It uses Value Numbering 20978e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// and Alias Analysis. 21078e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// 21178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const; 21278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 21378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// getDependency - Return the instruction on which a memory operation 2146951381995f24dc9c7bbcacefd5a1315784f66f3Chris Lattner /// depends. See the class comment for more details. It is illegal to call 2156951381995f24dc9c7bbcacefd5a1315784f66f3Chris Lattner /// this on non-memory instructions. 2165391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner MemDepResult getDependency(Instruction *QueryInst); 2175391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner 2181559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner /// getNonLocalCallDependency - Perform a full dependency query for the 2191559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner /// specified call, returning the set of blocks that the value is 22086b29ef64a36c8779ef7855b3c4b95744eb2f08bChris Lattner /// potentially live across. The returned set of results will include a 22186b29ef64a36c8779ef7855b3c4b95744eb2f08bChris Lattner /// "NonLocal" result for all blocks where the value is live across. 22286b29ef64a36c8779ef7855b3c4b95744eb2f08bChris Lattner /// 223bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner /// This method assumes the instruction returns a "NonLocal" dependency 22486b29ef64a36c8779ef7855b3c4b95744eb2f08bChris Lattner /// within its own block. 225bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner /// 226bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner /// This returns a reference to an internal data structure that may be 227bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner /// invalidated on the next non-local query or when an instruction is 228bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner /// removed. Clients must copy this data if they want it around longer than 229bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner /// that. 2301559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner const NonLocalDepInfo &getNonLocalCallDependency(CallSite QueryCS); 23178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 2327ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner 2337ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner /// getNonLocalPointerDependency - Perform a full dependency query for an 2347ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner /// access to the specified (non-volatile) memory location, returning the 2357ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner /// set of instructions that either define or clobber the value. 2367ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner /// 2379a193fd8ae630478123938e12b56f84c5b2227b9Chris Lattner /// This method assumes the pointer has a "NonLocal" dependency within BB. 2387ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner void getNonLocalPointerDependency(Value *Pointer, bool isLoad, 2397ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner BasicBlock *BB, 2407ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner SmallVectorImpl<NonLocalDepEntry> &Result); 2417ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner 24278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// removeInstruction - Remove an instruction from the dependence analysis, 24378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// updating the dependence of instructions that previously depended on it. 24439f372e23e49cecb8db2eb7120eb331173e50c74Chris Lattner void removeInstruction(Instruction *InstToRemove); 245179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson 246179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson private: 247e79be944c8ced0a0cb80ede8cb9f97e4fdc6778fChris Lattner MemDepResult getPointerDependencyFrom(Value *Pointer, uint64_t MemSize, 248e79be944c8ced0a0cb80ede8cb9f97e4fdc6778fChris Lattner bool isLoad, 249e79be944c8ced0a0cb80ede8cb9f97e4fdc6778fChris Lattner BasicBlock::iterator ScanIt, 250e79be944c8ced0a0cb80ede8cb9f97e4fdc6778fChris Lattner BasicBlock *BB); 25120d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall, 2528ef57c5faf77890828ac439482420646b2a0beb8Chris Lattner BasicBlock::iterator ScanIt, 2538ef57c5faf77890828ac439482420646b2a0beb8Chris Lattner BasicBlock *BB); 2549863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner void getNonLocalPointerDepFromBB(Value *Pointer, uint64_t Size, 2559863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner bool isLoad, BasicBlock *BB, 2569863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner SmallVectorImpl<NonLocalDepEntry> &Result, 2579863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner SmallPtrSet<BasicBlock*, 64> &Visited); 2589863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner MemDepResult GetNonLocalInfoForBlock(Value *Pointer, uint64_t PointeeSize, 2599863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner bool isLoad, BasicBlock *BB, 2609863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner NonLocalDepInfo *Cache, 2619863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner unsigned NumSortedEntries); 2629863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner 2639863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner 2646290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P); 2659a193fd8ae630478123938e12b56f84c5b2227b9Chris Lattner 2668b589fa135d873e683b29ed0918638a79272f5d2Chris Lattner /// verifyRemoved - Verify that the specified instruction does not occur 2678b589fa135d873e683b29ed0918638a79272f5d2Chris Lattner /// in our internal data structures. 2688b589fa135d873e683b29ed0918638a79272f5d2Chris Lattner void verifyRemoved(Instruction *Inst) const; 2698b589fa135d873e683b29ed0918638a79272f5d2Chris Lattner 27078e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson }; 27178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 27278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson} // End llvm namespace 27378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 27478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#endif 275