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" 19dad451cb7c6b94b3af40f59271e24357616a05a9Chris Lattner#include "llvm/Support/ValueHandle.h" 20c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman#include "llvm/Analysis/AliasAnalysis.h" 2178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#include "llvm/ADT/DenseMap.h" 224beedbd0063a8ba6f97db02c3c94707d8ab45b50Owen Anderson#include "llvm/ADT/SmallPtrSet.h" 234012fdda13710d21b415a79475adc2bbb6628527Chris Lattner#include "llvm/ADT/OwningPtr.h" 2439f372e23e49cecb8db2eb7120eb331173e50c74Chris Lattner#include "llvm/ADT/PointerIntPair.h" 2578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 2678e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Andersonnamespace llvm { 27e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner class Function; 28e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner class FunctionPass; 29e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner class Instruction; 30b390b1728e6c36f1f28d75d6f8f27cb91f8a8c56Chris Lattner class CallSite; 31d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner class AliasAnalysis; 32d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner class TargetData; 33fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner class MemoryDependenceAnalysis; 344012fdda13710d21b415a79475adc2bbb6628527Chris Lattner class PredIteratorCache; 356f7b210b2577fbc9247a9fc5223655390008ae89Chris Lattner class DominatorTree; 3605e15f8897bd949f9d4bce073d53ed3256c71e2bChris Lattner class PHITransAddr; 374c724006256032e827177afeae04ea62436796e7Chris Lattner 384c724006256032e827177afeae04ea62436796e7Chris Lattner /// MemDepResult - A memory dependence query can return one of three different 39fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// answers, described below. 404c724006256032e827177afeae04ea62436796e7Chris Lattner class MemDepResult { 414c724006256032e827177afeae04ea62436796e7Chris Lattner enum DepType { 42fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// Invalid - Clients of MemDep never see this. 43fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner Invalid = 0, 440f41ad3bc9a295332a8e6d025b42cebc9b9e8125Chris Lattner 45b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// Clobber - This is a dependence on the specified instruction which 46b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// clobbers the desired value. The pointer member of the MemDepResult 47b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// pair holds the instruction that clobbers the memory. For example, 48b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// this occurs when we see a may-aliased store to the memory location we 49b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// care about. 50cf82dc376a11acb1b5d46d56c032bb0b9326c682Chris Lattner /// 511f821512fc1441480b3355305e0da5267073fe1cChris Lattner /// There are several cases that may be interesting here: 521f821512fc1441480b3355305e0da5267073fe1cChris Lattner /// 1. Loads are clobbered by may-alias stores. 531f821512fc1441480b3355305e0da5267073fe1cChris Lattner /// 2. Loads are considered clobbered by partially-aliased loads. The 541f821512fc1441480b3355305e0da5267073fe1cChris Lattner /// client may choose to analyze deeper into these cases. 55b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner Clobber, 56fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner 57b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// Def - This is a dependence on the specified instruction which 58b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// defines/produces the desired memory location. The pointer member of 59b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// the MemDepResult pair holds the instruction that defines the memory. 60b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// Cases of interest: 61b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// 1. This could be a load or store for dependence queries on 62b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// load/store. The value loaded or stored is the produced value. 63b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// Note that the pointer operand may be different than that of the 64b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// queried pointer due to must aliases and phi translation. Note 65b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// that the def may not be the same type as the query, the pointers 66b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// may just be must aliases. 67b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// 2. For loads and stores, this could be an allocation instruction. In 68b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// this case, the load is loading an undef value or a store is the 69b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// first store to (that part of) the allocation. 70b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// 3. Dependence queries on calls return Def only when they are 71750e0e0ad0e599fe701e5492eef5c2cab05f2e5cNick Lewycky /// readonly calls or memory use intrinsics with identical callees 72750e0e0ad0e599fe701e5492eef5c2cab05f2e5cNick Lewycky /// and no intervening clobbers. No validation is done that the 73750e0e0ad0e599fe701e5492eef5c2cab05f2e5cNick Lewycky /// operands to the calls are the same. 74b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner Def, 75b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner 76b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman /// Other - This marker indicates that the query has no known dependency 77b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman /// in the specified block. More detailed state info is encoded in the 78b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman /// upper part of the pair (i.e. the Instruction*) 79b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman Other 80b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman }; 81b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman /// If DepType is "Other", the upper part of the pair 82b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman /// (i.e. the Instruction* part) is instead used to encode more detailed 83b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman /// type information as follows 84b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman enum OtherType { 85fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// NonLocal - This marker indicates that the query has no dependency in 86fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// the specified block. To find out more, the client should query other 87fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// predecessor blocks. 88b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman NonLocal = 0x4, 89b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman /// NonFuncLocal - This marker indicates that the query has no 90b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman /// dependency in the specified function. 91b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman NonFuncLocal = 0x8, 92b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman /// Unknown - This marker indicates that the query dependency 93b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman /// is unknown. 94b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman Unknown = 0xc 954c724006256032e827177afeae04ea62436796e7Chris Lattner }; 96b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman 974c724006256032e827177afeae04ea62436796e7Chris Lattner typedef PointerIntPair<Instruction*, 2, DepType> PairTy; 984c724006256032e827177afeae04ea62436796e7Chris Lattner PairTy Value; 994c724006256032e827177afeae04ea62436796e7Chris Lattner explicit MemDepResult(PairTy V) : Value(V) {} 1004c724006256032e827177afeae04ea62436796e7Chris Lattner public: 1014c724006256032e827177afeae04ea62436796e7Chris Lattner MemDepResult() : Value(0, Invalid) {} 1024c724006256032e827177afeae04ea62436796e7Chris Lattner 1034c724006256032e827177afeae04ea62436796e7Chris Lattner /// get methods: These are static ctor methods for creating various 1044c724006256032e827177afeae04ea62436796e7Chris Lattner /// MemDepResult kinds. 105b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner static MemDepResult getDef(Instruction *Inst) { 106a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman assert(Inst && "Def requires inst"); 107b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner return MemDepResult(PairTy(Inst, Def)); 108b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner } 109b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner static MemDepResult getClobber(Instruction *Inst) { 110a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman assert(Inst && "Clobber requires inst"); 111b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner return MemDepResult(PairTy(Inst, Clobber)); 1124c724006256032e827177afeae04ea62436796e7Chris Lattner } 1134c724006256032e827177afeae04ea62436796e7Chris Lattner static MemDepResult getNonLocal() { 114b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman return MemDepResult( 115b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman PairTy(reinterpret_cast<Instruction*>(NonLocal), Other)); 116b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman } 117b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman static MemDepResult getNonFuncLocal() { 118b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman return MemDepResult( 119b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman PairTy(reinterpret_cast<Instruction*>(NonFuncLocal), Other)); 1204c724006256032e827177afeae04ea62436796e7Chris Lattner } 121a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman static MemDepResult getUnknown() { 122b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman return MemDepResult( 123b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman PairTy(reinterpret_cast<Instruction*>(Unknown), Other)); 124a990e071f2f29ba326b97a4288207a2c406c5b66Eli Friedman } 1254c724006256032e827177afeae04ea62436796e7Chris Lattner 126b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// isClobber - Return true if this MemDepResult represents a query that is 127a3a3219b3a972db6449548abf7e0c9112e8ce7b9Nadav Rotem /// an instruction clobber dependency. 128b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman bool isClobber() const { return Value.getInt() == Clobber; } 129b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner 130b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner /// isDef - Return true if this MemDepResult represents a query that is 131a3a3219b3a972db6449548abf7e0c9112e8ce7b9Nadav Rotem /// an instruction definition dependency. 132b51deb929ca95ce62e622b0475a05d83f26ab04dChris Lattner bool isDef() const { return Value.getInt() == Def; } 1334c724006256032e827177afeae04ea62436796e7Chris Lattner 13481acc554b9599bacf843e080dbf4c72fe88de0f7Dan Gohman /// isNonLocal - Return true if this MemDepResult represents a query that 1354c724006256032e827177afeae04ea62436796e7Chris Lattner /// is transparent to the start of the block, but where a non-local hasn't 1364c724006256032e827177afeae04ea62436796e7Chris Lattner /// been done. 137b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman bool isNonLocal() const { 138b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman return Value.getInt() == Other 139b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman && Value.getPointer() == reinterpret_cast<Instruction*>(NonLocal); 140b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman } 141b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman 142b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman /// isNonFuncLocal - Return true if this MemDepResult represents a query 143b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman /// that is transparent to the start of the function. 144b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman bool isNonFuncLocal() const { 145b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman return Value.getInt() == Other 146b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman && Value.getPointer() == reinterpret_cast<Instruction*>(NonFuncLocal); 147b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman } 1484c724006256032e827177afeae04ea62436796e7Chris Lattner 149b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman /// isUnknown - Return true if this MemDepResult represents a query which 150b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman /// cannot and/or will not be computed. 151b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman bool isUnknown() const { 152b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman return Value.getInt() == Other 153b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman && Value.getPointer() == reinterpret_cast<Instruction*>(Unknown); 154b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman } 155b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman 1564c724006256032e827177afeae04ea62436796e7Chris Lattner /// getInst() - If this is a normal dependency, return the instruction that 1574c724006256032e827177afeae04ea62436796e7Chris Lattner /// is depended on. Otherwise, return null. 158b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman Instruction *getInst() const { 159b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman if (Value.getInt() == Other) return NULL; 160b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman return Value.getPointer(); 161b414142036012dd9432c4e8c5fef09d4d49fcc22Eli Friedman } 1624c724006256032e827177afeae04ea62436796e7Chris Lattner 1639817b24e74532c13bad2c7350f17e17473b8c57aBill Wendling bool operator==(const MemDepResult &M) const { return Value == M.Value; } 1649817b24e74532c13bad2c7350f17e17473b8c57aBill Wendling bool operator!=(const MemDepResult &M) const { return Value != M.Value; } 1659817b24e74532c13bad2c7350f17e17473b8c57aBill Wendling bool operator<(const MemDepResult &M) const { return Value < M.Value; } 1669817b24e74532c13bad2c7350f17e17473b8c57aBill Wendling bool operator>(const MemDepResult &M) const { return Value > M.Value; } 167fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner private: 168fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner friend class MemoryDependenceAnalysis; 169fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// Dirty - Entries with this marker occur in a LocalDeps map or 170fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// NonLocalDeps map when the instruction they previously referenced was 171fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// removed from MemDep. In either case, the entry may include an 172fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// instruction pointer. If so, the pointer is an instruction in the 173fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// block where scanning can start from, saving some work. 174fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// 175bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner /// In a default-constructed MemDepResult object, the type will be Dirty 176fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// and the instruction pointer will be null. 177fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// 178bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner 179fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// isDirty - Return true if this is a MemDepResult in its dirty/invalid. 180fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner /// state. 181fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner bool isDirty() const { return Value.getInt() == Invalid; } 182bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner 183fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner static MemDepResult getDirty(Instruction *Inst) { 184fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner return MemDepResult(PairTy(Inst, Invalid)); 185fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner } 1864c724006256032e827177afeae04ea62436796e7Chris Lattner }; 18778e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 18850bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman /// NonLocalDepEntry - This is an entry in the NonLocalDepInfo cache. For 18950bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman /// each BasicBlock (the BB entry) it keeps a MemDepResult. 19050bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman class NonLocalDepEntry { 19150bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman BasicBlock *BB; 19250bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman MemDepResult Result; 19350bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman public: 19450bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman NonLocalDepEntry(BasicBlock *bb, MemDepResult result) 19550bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman : BB(bb), Result(result) {} 19650bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman 19750bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman // This is used for searches. 19850bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman NonLocalDepEntry(BasicBlock *bb) : BB(bb) {} 19950bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman 20050bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman // BB is the sort key, it can't be changed. 20150bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman BasicBlock *getBB() const { return BB; } 20250bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman 20350bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman void setResult(const MemDepResult &R) { Result = R; } 20450bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman 20550bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman const MemDepResult &getResult() const { return Result; } 20650bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman 20750bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman bool operator<(const NonLocalDepEntry &RHS) const { 20850bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman return BB < RHS.BB; 20950bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman } 21050bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman }; 21150bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman 2120ee443d169786017d151034b8bd34225bc144c98Chris Lattner /// NonLocalDepResult - This is a result from a NonLocal dependence query. 2130ee443d169786017d151034b8bd34225bc144c98Chris Lattner /// For each BasicBlock (the BB entry) it keeps a MemDepResult and the 2140ee443d169786017d151034b8bd34225bc144c98Chris Lattner /// (potentially phi translated) address that was live in the block. 2150ee443d169786017d151034b8bd34225bc144c98Chris Lattner class NonLocalDepResult { 21650bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman NonLocalDepEntry Entry; 2170ee443d169786017d151034b8bd34225bc144c98Chris Lattner Value *Address; 218e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner public: 2190ee443d169786017d151034b8bd34225bc144c98Chris Lattner NonLocalDepResult(BasicBlock *bb, MemDepResult result, Value *address) 22050bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman : Entry(bb, result), Address(address) {} 2210ee443d169786017d151034b8bd34225bc144c98Chris Lattner 222e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner // BB is the sort key, it can't be changed. 22350bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman BasicBlock *getBB() const { return Entry.getBB(); } 224e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner 225dad451cb7c6b94b3af40f59271e24357616a05a9Chris Lattner void setResult(const MemDepResult &R, Value *Addr) { 22650bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman Entry.setResult(R); 227dad451cb7c6b94b3af40f59271e24357616a05a9Chris Lattner Address = Addr; 228dad451cb7c6b94b3af40f59271e24357616a05a9Chris Lattner } 2290ee443d169786017d151034b8bd34225bc144c98Chris Lattner 23050bcaece670fea4c936c6730fab9f4d869d2ec67Dan Gohman const MemDepResult &getResult() const { return Entry.getResult(); } 231e18b97121c286eeff5efe89150b093bf1b7b7bfcChris Lattner 232dad451cb7c6b94b3af40f59271e24357616a05a9Chris Lattner /// getAddress - Return the address of this pointer in this block. This can 233dad451cb7c6b94b3af40f59271e24357616a05a9Chris Lattner /// be different than the address queried for the non-local result because 234dad451cb7c6b94b3af40f59271e24357616a05a9Chris Lattner /// of phi translation. This returns null if the address was not available 235dad451cb7c6b94b3af40f59271e24357616a05a9Chris Lattner /// in a block (i.e. because phi translation failed) or if this is a cached 236dad451cb7c6b94b3af40f59271e24357616a05a9Chris Lattner /// result and that address was deleted. 237dad451cb7c6b94b3af40f59271e24357616a05a9Chris Lattner /// 238dad451cb7c6b94b3af40f59271e24357616a05a9Chris Lattner /// The address is always null for a non-local 'call' dependence. 239dad451cb7c6b94b3af40f59271e24357616a05a9Chris Lattner Value *getAddress() const { return Address; } 2400ee443d169786017d151034b8bd34225bc144c98Chris Lattner }; 2410ee443d169786017d151034b8bd34225bc144c98Chris Lattner 242e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner /// MemoryDependenceAnalysis - This is an analysis that determines, for a 243e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner /// given memory operation, what preceding memory operations it depends on. 244e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner /// It builds on alias analysis information, and tries to provide a lazy, 245e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner /// caching interface to a common kind of alias information query. 2460e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// 2470e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// The dependency information returned is somewhat unusual, but is pragmatic. 2480e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// If queried about a store or call that might modify memory, the analysis 2490e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// will return the instruction[s] that may either load from that memory or 2500e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// store to it. If queried with a load or call that can never modify memory, 2510e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// the analysis will return calls and stores that might modify the pointer, 2520e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// but generally does not return loads unless a) they are volatile, or 2530e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// b) they load from *must-aliased* pointers. Returning a dependence on 2540e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// must-alias'd pointers instead of all pointers interacts well with the 2550e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// internal caching mechanism. 2560e0a5b690ca772a9002d8e8d21edac5f011bc7e8Chris Lattner /// 257e85866313a551fa3d4e2f118c3bf34e96af36763Chris Lattner class MemoryDependenceAnalysis : public FunctionPass { 2587f52422a3c821c1deb7171808ffcf83386970791Chris Lattner // A map from instructions to their dependency. 259fd3dcbea06f934572a3ba02821b1485eb7a073aaChris Lattner typedef DenseMap<Instruction*, MemDepResult> LocalDepMapType; 26039f372e23e49cecb8db2eb7120eb331173e50c74Chris Lattner LocalDepMapType LocalDeps; 261df464195fe049d5ea921e2e37f4f833c2ea4e3ecDavid Greene 262bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner public: 263bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner typedef std::vector<NonLocalDepEntry> NonLocalDepInfo; 264bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner private: 2656290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner /// ValueIsLoadPair - This is a pair<Value*, bool> where the bool is true if 2666290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner /// the dependence is a read only dependence, false if read/write. 267ba6ca6dd3bc4a7f30e07010c3b0b95cced719f76Dan Gohman typedef PointerIntPair<const Value*, 1, bool> ValueIsLoadPair; 2689e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner 2699e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner /// BBSkipFirstBlockPair - This pair is used when caching information for a 2709e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner /// block. If the pointer is null, the cache value is not a full query that 2719e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner /// starts at the specified block. If non-null, the bool indicates whether 2729e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner /// or not the contents of the block was skipped. 2739e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner typedef PointerIntPair<BasicBlock*, 1, bool> BBSkipFirstBlockPair; 2749e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner 275c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman /// NonLocalPointerInfo - This record is the information kept for each 276c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman /// (value, is load) pair. 277c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman struct NonLocalPointerInfo { 278c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman /// Pair - The pair of the block and the skip-first-block flag. 279c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman BBSkipFirstBlockPair Pair; 280c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman /// NonLocalDeps - The results of the query for each relevant block. 281c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman NonLocalDepInfo NonLocalDeps; 282075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman /// Size - The maximum size of the dereferences of the 283075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman /// pointer. May be UnknownSize if the sizes are unknown. 284075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman uint64_t Size; 285c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman /// TBAATag - The TBAA tag associated with dereferences of the 286c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman /// pointer. May be null if there are no tags or conflicting tags. 287075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2aDan Gohman const MDNode *TBAATag; 288bea77bb6e82e7f7feae71b2cafea4f6a9f6098c0Dan Gohman 289ec9b4ac914e91791c580148cf8068c82d4b2cb91Dan Gohman NonLocalPointerInfo() : Size(AliasAnalysis::UnknownSize), TBAATag(0) {} 290c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman }; 291c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman 2926290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner /// CachedNonLocalPointerInfo - This map stores the cached results of doing 293e91a4881e17127686345f62df08da6370b14d51fChris Lattner /// a pointer lookup at the bottom of a block. The key of this map is the 2946290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner /// pointer+isload bit, the value is a list of <bb->result> mappings. 295c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman typedef DenseMap<ValueIsLoadPair, 296c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman NonLocalPointerInfo> CachedNonLocalPointerInfo; 2976290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner CachedNonLocalPointerInfo NonLocalPointerDeps; 2986290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner 2996290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner // A map from instructions to their non-local pointer dependencies. 3006290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner typedef DenseMap<Instruction*, 3016a0dcc10778468b1556474aa43d4a86a14ab15d7Chris Lattner SmallPtrSet<ValueIsLoadPair, 4> > ReverseNonLocalPtrDepTy; 3026290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner ReverseNonLocalPtrDepTy ReverseNonLocalPtrDeps; 3036290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner 3046290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner 3054a69bade2385022ca776edc22150f3b750cdf23cChris Lattner /// PerInstNLInfo - This is the instruction we keep for each cached access 3064a69bade2385022ca776edc22150f3b750cdf23cChris Lattner /// that we have for an instruction. The pointer is an owning pointer and 3074a69bade2385022ca776edc22150f3b750cdf23cChris Lattner /// the bool indicates whether we have any dirty bits in the set. 308bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner typedef std::pair<NonLocalDepInfo, bool> PerInstNLInfo; 30925f4b2b7a3f1f2bbaf954257e7834ba29a6ede7cChris Lattner 3104d13de4e3bfc5121207efd01e1b31caa6bb4e40bOwen Anderson // A map from instructions to their non-local dependencies. 3114a69bade2385022ca776edc22150f3b750cdf23cChris Lattner typedef DenseMap<Instruction*, PerInstNLInfo> NonLocalDepMapType; 3124a69bade2385022ca776edc22150f3b750cdf23cChris Lattner 3138c4652790e04515f34cf920b0783d6ec4161a313Chris Lattner NonLocalDepMapType NonLocalDeps; 3144d13de4e3bfc5121207efd01e1b31caa6bb4e40bOwen Anderson 315956033a4f5de491fcc07bc3ef0700ad22fd836a0Chris Lattner // A reverse mapping from dependencies to the dependees. This is 316179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson // used when removing instructions to keep the cache coherent. 3177f52422a3c821c1deb7171808ffcf83386970791Chris Lattner typedef DenseMap<Instruction*, 3188c4652790e04515f34cf920b0783d6ec4161a313Chris Lattner SmallPtrSet<Instruction*, 4> > ReverseDepMapType; 3198c4652790e04515f34cf920b0783d6ec4161a313Chris Lattner ReverseDepMapType ReverseLocalDeps; 32078e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 321484d4a30c055eef3101d01a7a468db3413dd20d3Bob Wilson // A reverse mapping from dependencies to the non-local dependees. 3228c4652790e04515f34cf920b0783d6ec4161a313Chris Lattner ReverseDepMapType ReverseNonLocalDeps; 3234d13de4e3bfc5121207efd01e1b31caa6bb4e40bOwen Anderson 324d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner /// Current AA implementation, just a cache. 325d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner AliasAnalysis *AA; 326d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner TargetData *TD; 32788990248d3bfb2f265fcf27f8a032ac0eb14d09fNick Lewycky DominatorTree *DT; 3284012fdda13710d21b415a79475adc2bbb6628527Chris Lattner OwningPtr<PredIteratorCache> PredCache; 329179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson public: 3304012fdda13710d21b415a79475adc2bbb6628527Chris Lattner MemoryDependenceAnalysis(); 3314012fdda13710d21b415a79475adc2bbb6628527Chris Lattner ~MemoryDependenceAnalysis(); 33239f372e23e49cecb8db2eb7120eb331173e50c74Chris Lattner static char ID; 3331cee94f04111cfd7114979d6dfddce2669c9380dDevang Patel 334d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner /// Pass Implementation stuff. This doesn't do any analysis eagerly. 335d777d405cdda8d418ba8e8818e5c1272dfd999a0Chris Lattner bool runOnFunction(Function &); 3366b278fc7860c1e0e5cf72340e43f78a87159be4cOwen Anderson 3376b278fc7860c1e0e5cf72340e43f78a87159be4cOwen Anderson /// Clean up memory in between runs 3384012fdda13710d21b415a79475adc2bbb6628527Chris Lattner void releaseMemory(); 3394012fdda13710d21b415a79475adc2bbb6628527Chris Lattner 34078e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// getAnalysisUsage - Does not modify anything. It uses Value Numbering 34178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// and Alias Analysis. 34278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// 34378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const; 34478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 34578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// getDependency - Return the instruction on which a memory operation 3466951381995f24dc9c7bbcacefd5a1315784f66f3Chris Lattner /// depends. See the class comment for more details. It is illegal to call 3476951381995f24dc9c7bbcacefd5a1315784f66f3Chris Lattner /// this on non-memory instructions. 3485391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner MemDepResult getDependency(Instruction *QueryInst); 3495391a1d8046396fb4dd005b1910973789f5427f4Chris Lattner 3501559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner /// getNonLocalCallDependency - Perform a full dependency query for the 3511559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner /// specified call, returning the set of blocks that the value is 35286b29ef64a36c8779ef7855b3c4b95744eb2f08bChris Lattner /// potentially live across. The returned set of results will include a 35386b29ef64a36c8779ef7855b3c4b95744eb2f08bChris Lattner /// "NonLocal" result for all blocks where the value is live across. 35486b29ef64a36c8779ef7855b3c4b95744eb2f08bChris Lattner /// 355bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner /// This method assumes the instruction returns a "NonLocal" dependency 35686b29ef64a36c8779ef7855b3c4b95744eb2f08bChris Lattner /// within its own block. 357bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner /// 358bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner /// This returns a reference to an internal data structure that may be 359bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner /// invalidated on the next non-local query or when an instruction is 360bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner /// removed. Clients must copy this data if they want it around longer than 361bf145d6e2ba01f5099ccaa1b58ed3619406928a0Chris Lattner /// that. 3621559b3625be7b80bee6b066af4b91b9d10dfb5faChris Lattner const NonLocalDepInfo &getNonLocalCallDependency(CallSite QueryCS); 36378e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 3647ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner 3657ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner /// getNonLocalPointerDependency - Perform a full dependency query for an 3667ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner /// access to the specified (non-volatile) memory location, returning the 3677ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner /// set of instructions that either define or clobber the value. 3687ebcf0324668b7c6ba48832d5d8df95689a8d837Chris Lattner /// 3699a193fd8ae630478123938e12b56f84c5b2227b9Chris Lattner /// This method assumes the pointer has a "NonLocal" dependency within BB. 370c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman void getNonLocalPointerDependency(const AliasAnalysis::Location &Loc, 371c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman bool isLoad, BasicBlock *BB, 372c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman SmallVectorImpl<NonLocalDepResult> &Result); 373c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman 37478e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// removeInstruction - Remove an instruction from the dependence analysis, 37578e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson /// updating the dependence of instructions that previously depended on it. 37639f372e23e49cecb8db2eb7120eb331173e50c74Chris Lattner void removeInstruction(Instruction *InstToRemove); 377179463c0d4c20bfb2c6b1e697eed6f16305a201eOwen Anderson 378bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner /// invalidateCachedPointerInfo - This method is used to invalidate cached 379bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner /// information about the specified pointer, because it may be too 380bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner /// conservative in memdep. This is an optional call that can be used when 381bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner /// the client detects an equivalence between the pointer and some other 382bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner /// value and replaces the other value with ptr. This can make Ptr available 383bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner /// in more places that cached info does not necessarily keep. 384bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner void invalidateCachedPointerInfo(Value *Ptr); 385484d4a30c055eef3101d01a7a468db3413dd20d3Bob Wilson 386484d4a30c055eef3101d01a7a468db3413dd20d3Bob Wilson /// invalidateCachedPredecessors - Clear the PredIteratorCache info. 387484d4a30c055eef3101d01a7a468db3413dd20d3Bob Wilson /// This needs to be done when the CFG changes, e.g., due to splitting 388484d4a30c055eef3101d01a7a468db3413dd20d3Bob Wilson /// critical edges. 389484d4a30c055eef3101d01a7a468db3413dd20d3Bob Wilson void invalidateCachedPredecessors(); 390bc99be10b815e0bfc5102bd5746e9a80feebf6f4Chris Lattner 391f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner /// getPointerDependencyFrom - Return the instruction on which a memory 392f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner /// location depends. If isLoad is true, this routine ignores may-aliases 393f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner /// with read-only operations. If isLoad is false, this routine ignores 394f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner /// may-aliases with reads from read-only locations. 395f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner /// 396f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner /// Note that this is an uncached query, and thus may be inefficient. 397f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner /// 398c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman MemDepResult getPointerDependencyFrom(const AliasAnalysis::Location &Loc, 399e79be944c8ced0a0cb80ede8cb9f97e4fdc6778fChris Lattner bool isLoad, 400e79be944c8ced0a0cb80ede8cb9f97e4fdc6778fChris Lattner BasicBlock::iterator ScanIt, 401e79be944c8ced0a0cb80ede8cb9f97e4fdc6778fChris Lattner BasicBlock *BB); 402f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner 4034034e14985af013f71f7884fa275415a3be27778Chris Lattner 4044034e14985af013f71f7884fa275415a3be27778Chris Lattner /// getLoadLoadClobberFullWidthSize - This is a little bit of analysis that 4054034e14985af013f71f7884fa275415a3be27778Chris Lattner /// looks at a memory location for a load (specified by MemLocBase, Offs, 4064034e14985af013f71f7884fa275415a3be27778Chris Lattner /// and Size) and compares it against a load. If the specified load could 4074034e14985af013f71f7884fa275415a3be27778Chris Lattner /// be safely widened to a larger integer load that is 1) still efficient, 4084034e14985af013f71f7884fa275415a3be27778Chris Lattner /// 2) safe for the target, and 3) would provide the specified memory 4094034e14985af013f71f7884fa275415a3be27778Chris Lattner /// location value, then this function returns the size in bytes of the 4104034e14985af013f71f7884fa275415a3be27778Chris Lattner /// load width to use. If not, this returns zero. 4114034e14985af013f71f7884fa275415a3be27778Chris Lattner static unsigned getLoadLoadClobberFullWidthSize(const Value *MemLocBase, 4124034e14985af013f71f7884fa275415a3be27778Chris Lattner int64_t MemLocOffs, 4134034e14985af013f71f7884fa275415a3be27778Chris Lattner unsigned MemLocSize, 4144034e14985af013f71f7884fa275415a3be27778Chris Lattner const LoadInst *LI, 4154034e14985af013f71f7884fa275415a3be27778Chris Lattner const TargetData &TD); 4164034e14985af013f71f7884fa275415a3be27778Chris Lattner 417f6f1f062cc8029aa75ca7d0e99fbc1e0b453d07eChris Lattner private: 41820d6f0982ad33818cfa141f80157ac13e36d5550Chris Lattner MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall, 4198ef57c5faf77890828ac439482420646b2a0beb8Chris Lattner BasicBlock::iterator ScanIt, 4208ef57c5faf77890828ac439482420646b2a0beb8Chris Lattner BasicBlock *BB); 421c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman bool getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, 422c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman const AliasAnalysis::Location &Loc, 4239863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner bool isLoad, BasicBlock *BB, 4240ee443d169786017d151034b8bd34225bc144c98Chris Lattner SmallVectorImpl<NonLocalDepResult> &Result, 4259e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner DenseMap<BasicBlock*, Value*> &Visited, 4269e59c64c14cfe55e7cc9086c6bff8cfeecac361eChris Lattner bool SkipFirstBlock = false); 427c1ac0d7623f4f2047b4ab86bd5a60a9e19432b38Dan Gohman MemDepResult GetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc, 4289863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner bool isLoad, BasicBlock *BB, 4299863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner NonLocalDepInfo *Cache, 4309863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner unsigned NumSortedEntries); 4319863c3f507913f17de0fd707e27fde9dc35f6ca6Chris Lattner 4326290f5cac23399201f8785e5ca8b305e42a1342cChris Lattner void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P); 4339a193fd8ae630478123938e12b56f84c5b2227b9Chris Lattner 4348b589fa135d873e683b29ed0918638a79272f5d2Chris Lattner /// verifyRemoved - Verify that the specified instruction does not occur 4358b589fa135d873e683b29ed0918638a79272f5d2Chris Lattner /// in our internal data structures. 4368b589fa135d873e683b29ed0918638a79272f5d2Chris Lattner void verifyRemoved(Instruction *Inst) const; 4378b589fa135d873e683b29ed0918638a79272f5d2Chris Lattner 43878e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson }; 43978e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 44078e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson} // End llvm namespace 44178e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson 44278e02f78ce68274163e1e63be59abd17aaaf6cbfOwen Anderson#endif 443