#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"
class TargetData;
class MemoryDependenceAnalysis;
class PredIteratorCache;
+ class DominatorTree;
+ class PHITransAddr;
/// MemDepResult - A memory dependence query can return one of three different
/// answers, described below.
/// this case, the load is loading an undef value or a store is the
/// first store to (that part of) the allocation.
/// 3. Dependence queries on calls return Def only when they are
- /// readonly calls with identical callees and no intervening
- /// clobbers. No validation is done that the operands to the calls
- /// are the same.
+ /// readonly calls or memory use intrinsics with identical callees
+ /// and no intervening clobbers. No validation is done that the
+ /// operands to the calls are the same.
Def,
/// NonLocal - This marker indicates that the query has no dependency in
}
};
+ /// 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;
+ Value *Address;
+ public:
+ NonLocalDepResult(BasicBlock *bb, MemDepResult result, Value *address)
+ : BB(bb), Result(result), Address(address) {}
+
+ // BB is the sort key, it can't be changed.
+ BasicBlock *getBB() const { return BB; }
+
+ void setResult(const MemDepResult &R, Value *Addr) {
+ Result = R;
+ Address = Addr;
+ }
+
+ const MemDepResult &getResult() const { return Result; }
+
+ /// getAddress - Return the address of this pointer in this block. This can
+ /// be different than the address queried for the non-local result because
+ /// of phi translation. This returns null if the address was not available
+ /// in a block (i.e. because phi translation failed) or if this is a cached
+ /// result and that address was deleted.
+ ///
+ /// The address is always null for a non-local 'call' dependence.
+ 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,
LocalDepMapType LocalDeps;
public:
- typedef std::pair<BasicBlock*, MemDepResult> NonLocalDepEntry;
typedef std::vector<NonLocalDepEntry> NonLocalDepInfo;
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
/// 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;
+ /// TBAATag - The TBAA tag associated with dereferences of the
+ /// pointer. May be null if there are no tags or conflicting tags.
+ MDNode *TBAATag;
+
+ NonLocalPointerInfo() : 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.
SmallPtrSet<Instruction*, 4> > ReverseDepMapType;
ReverseDepMapType ReverseLocalDeps;
- // A reverse mapping form dependencies to the non-local dependees.
+ // A reverse mapping from dependencies to the non-local dependees.
ReverseDepMapType ReverseNonLocalDeps;
/// Current AA implementation, just a cache.
/// set of instructions that either define or clobber the value.
///
/// This method assumes the pointer has a "NonLocal" dependency within BB.
+ void getNonLocalPointerDependency(const AliasAnalysis::Location &Loc,
+ bool isLoad, BasicBlock *BB,
+ SmallVectorImpl<NonLocalDepResult> &Result);
+
+ /// getNonLocalPointerDependence - A convenience wrapper.
void getNonLocalPointerDependency(Value *Pointer, bool isLoad,
BasicBlock *BB,
- SmallVectorImpl<NonLocalDepEntry> &Result);
+ SmallVectorImpl<NonLocalDepResult> &Result){
+ return getNonLocalPointerDependency(AliasAnalysis::Location(Pointer),
+ isLoad, BB, Result);
+ }
/// removeInstruction - Remove an instruction from the dependence analysis,
/// updating the dependence of instructions that previously depended on it.
/// value and replaces the other value with ptr. This can make Ptr available
/// in more places that cached info does not necessarily keep.
void invalidateCachedPointerInfo(Value *Ptr);
+
+ /// invalidateCachedPredecessors - Clear the PredIteratorCache info.
+ /// This needs to be done when the CFG changes, e.g., due to splitting
+ /// critical edges.
+ void invalidateCachedPredecessors();
private:
- MemDepResult getPointerDependencyFrom(Value *Pointer, uint64_t MemSize,
+ MemDepResult getPointerDependencyFrom(const AliasAnalysis::Location &Loc,
bool isLoad,
BasicBlock::iterator ScanIt,
BasicBlock *BB);
MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall,
BasicBlock::iterator ScanIt,
BasicBlock *BB);
- bool getNonLocalPointerDepFromBB(Value *Pointer, uint64_t Size,
+ bool getNonLocalPointerDepFromBB(const PHITransAddr &Pointer,
+ const AliasAnalysis::Location &Loc,
bool isLoad, BasicBlock *BB,
- SmallVectorImpl<NonLocalDepEntry> &Result,
+ 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);