diff options
Diffstat (limited to 'include/llvm/Analysis/MemoryDependenceAnalysis.h')
| -rw-r--r-- | include/llvm/Analysis/MemoryDependenceAnalysis.h | 109 |
1 files changed, 69 insertions, 40 deletions
diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index f6aab03690ff..4d5dd1987f28 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -17,6 +17,7 @@ #include "llvm/BasicBlock.h" #include "llvm/Pass.h" #include "llvm/Support/ValueHandle.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/OwningPtr.h" @@ -46,6 +47,9 @@ namespace llvm { /// pair holds the instruction that clobbers the memory. For example, /// this occurs when we see a may-aliased store to the memory location we /// care about. + /// + /// A dependence query on the first instruction of the entry block will + /// return a clobber(self) result. Clobber, /// Def - This is a dependence on the specified instruction which @@ -132,26 +136,49 @@ namespace llvm { } }; + /// NonLocalDepEntry - This is an entry in the NonLocalDepInfo cache. For + /// each BasicBlock (the BB entry) it keeps a MemDepResult. + class NonLocalDepEntry { + BasicBlock *BB; + MemDepResult Result; + public: + NonLocalDepEntry(BasicBlock *bb, MemDepResult result) + : BB(bb), Result(result) {} + + // This is used for searches. + NonLocalDepEntry(BasicBlock *bb) : BB(bb) {} + + // BB is the sort key, it can't be changed. + BasicBlock *getBB() const { return BB; } + + void setResult(const MemDepResult &R) { Result = R; } + + const MemDepResult &getResult() const { return Result; } + + bool operator<(const NonLocalDepEntry &RHS) const { + return BB < RHS.BB; + } + }; + /// NonLocalDepResult - This is a result from a NonLocal dependence query. /// For each BasicBlock (the BB entry) it keeps a MemDepResult and the /// (potentially phi translated) address that was live in the block. class NonLocalDepResult { - BasicBlock *BB; - MemDepResult Result; + NonLocalDepEntry Entry; Value *Address; public: NonLocalDepResult(BasicBlock *bb, MemDepResult result, Value *address) - : BB(bb), Result(result), Address(address) {} + : Entry(bb, result), Address(address) {} // BB is the sort key, it can't be changed. - BasicBlock *getBB() const { return BB; } + BasicBlock *getBB() const { return Entry.getBB(); } void setResult(const MemDepResult &R, Value *Addr) { - Result = R; + Entry.setResult(R); Address = Addr; } - const MemDepResult &getResult() const { return Result; } + const MemDepResult &getResult() const { return Entry.getResult(); } /// getAddress - Return the address of this pointer in this block. This can /// be different than the address queried for the non-local result because @@ -163,30 +190,6 @@ namespace llvm { Value *getAddress() const { return Address; } }; - /// NonLocalDepEntry - This is an entry in the NonLocalDepInfo cache. For - /// each BasicBlock (the BB entry) it keeps a MemDepResult. - class NonLocalDepEntry { - BasicBlock *BB; - MemDepResult Result; - public: - NonLocalDepEntry(BasicBlock *bb, MemDepResult result) - : BB(bb), Result(result) {} - - // This is used for searches. - NonLocalDepEntry(BasicBlock *bb) : BB(bb) {} - - // BB is the sort key, it can't be changed. - BasicBlock *getBB() const { return BB; } - - void setResult(const MemDepResult &R) { Result = R; } - - const MemDepResult &getResult() const { return Result; } - - bool operator<(const NonLocalDepEntry &RHS) const { - return BB < RHS.BB; - } - }; - /// MemoryDependenceAnalysis - This is an analysis that determines, for a /// given memory operation, what preceding memory operations it depends on. /// It builds on alias analysis information, and tries to provide a lazy, @@ -212,7 +215,7 @@ namespace llvm { private: /// ValueIsLoadPair - This is a pair<Value*, bool> where the bool is true if /// the dependence is a read only dependence, false if read/write. - typedef PointerIntPair<Value*, 1, bool> ValueIsLoadPair; + typedef PointerIntPair<const Value*, 1, bool> ValueIsLoadPair; /// BBSkipFirstBlockPair - This pair is used when caching information for a /// block. If the pointer is null, the cache value is not a full query that @@ -220,11 +223,28 @@ namespace llvm { /// or not the contents of the block was skipped. typedef PointerIntPair<BasicBlock*, 1, bool> BBSkipFirstBlockPair; + /// NonLocalPointerInfo - This record is the information kept for each + /// (value, is load) pair. + struct NonLocalPointerInfo { + /// Pair - The pair of the block and the skip-first-block flag. + BBSkipFirstBlockPair Pair; + /// NonLocalDeps - The results of the query for each relevant block. + NonLocalDepInfo NonLocalDeps; + /// Size - The maximum size of the dereferences of the + /// pointer. May be UnknownSize if the sizes are unknown. + uint64_t Size; + /// TBAATag - The TBAA tag associated with dereferences of the + /// pointer. May be null if there are no tags or conflicting tags. + const MDNode *TBAATag; + + NonLocalPointerInfo() : Size(AliasAnalysis::UnknownSize), TBAATag(0) {} + }; + /// CachedNonLocalPointerInfo - This map stores the cached results of doing /// a pointer lookup at the bottom of a block. The key of this map is the /// pointer+isload bit, the value is a list of <bb->result> mappings. - typedef DenseMap<ValueIsLoadPair, std::pair<BBSkipFirstBlockPair, - NonLocalDepInfo> > CachedNonLocalPointerInfo; + typedef DenseMap<ValueIsLoadPair, + NonLocalPointerInfo> CachedNonLocalPointerInfo; CachedNonLocalPointerInfo NonLocalPointerDeps; // A map from instructions to their non-local pointer dependencies. @@ -297,10 +317,10 @@ namespace llvm { /// set of instructions that either define or clobber the value. /// /// This method assumes the pointer has a "NonLocal" dependency within BB. - void getNonLocalPointerDependency(Value *Pointer, bool isLoad, - BasicBlock *BB, + void getNonLocalPointerDependency(const AliasAnalysis::Location &Loc, + bool isLoad, BasicBlock *BB, SmallVectorImpl<NonLocalDepResult> &Result); - + /// removeInstruction - Remove an instruction from the dependence analysis, /// updating the dependence of instructions that previously depended on it. void removeInstruction(Instruction *InstToRemove); @@ -318,20 +338,29 @@ namespace llvm { /// critical edges. void invalidateCachedPredecessors(); - private: - MemDepResult getPointerDependencyFrom(Value *Pointer, uint64_t MemSize, + /// getPointerDependencyFrom - Return the instruction on which a memory + /// location depends. If isLoad is true, this routine ignores may-aliases + /// with read-only operations. If isLoad is false, this routine ignores + /// may-aliases with reads from read-only locations. + /// + /// Note that this is an uncached query, and thus may be inefficient. + /// + MemDepResult getPointerDependencyFrom(const AliasAnalysis::Location &Loc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB); + + private: MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall, BasicBlock::iterator ScanIt, BasicBlock *BB); - bool getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, uint64_t Size, + bool getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, + const AliasAnalysis::Location &Loc, bool isLoad, BasicBlock *BB, SmallVectorImpl<NonLocalDepResult> &Result, DenseMap<BasicBlock*, Value*> &Visited, bool SkipFirstBlock = false); - MemDepResult GetNonLocalInfoForBlock(Value *Pointer, uint64_t PointeeSize, + MemDepResult GetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc, bool isLoad, BasicBlock *BB, NonLocalDepInfo *Cache, unsigned NumSortedEntries); |