#ifndef LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
#define LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
-#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"
#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/ValueHandle.h"
namespace llvm {
class Function;
class Instruction;
class CallSite;
class AliasAnalysis;
- class TargetData;
+ class DataLayout;
class MemoryDependenceAnalysis;
class PredIteratorCache;
class DominatorTree;
/// 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.
+ ///
+ /// There are several cases that may be interesting here:
+ /// 1. Loads are clobbered by may-alias stores.
+ /// 2. Loads are considered clobbered by partially-aliased loads. The
+ /// client may choose to analyze deeper into these cases.
Clobber,
/// Def - This is a dependence on the specified instruction which
/// operands to the calls are the same.
Def,
+ /// Other - This marker indicates that the query has no known dependency
+ /// in the specified block. More detailed state info is encoded in the
+ /// upper part of the pair (i.e. the Instruction*)
+ Other
+ };
+ /// If DepType is "Other", the upper part of the pair
+ /// (i.e. the Instruction* part) is instead used to encode more detailed
+ /// type information as follows
+ enum OtherType {
/// NonLocal - This marker indicates that the query has no dependency in
/// the specified block. To find out more, the client should query other
/// predecessor blocks.
- NonLocal
+ NonLocal = 0x4,
+ /// NonFuncLocal - This marker indicates that the query has no
+ /// dependency in the specified function.
+ NonFuncLocal = 0x8,
+ /// Unknown - This marker indicates that the query dependency
+ /// is unknown.
+ Unknown = 0xc
};
+
typedef PointerIntPair<Instruction*, 2, DepType> PairTy;
PairTy Value;
explicit MemDepResult(PairTy V) : Value(V) {}
/// get methods: These are static ctor methods for creating various
/// MemDepResult kinds.
static MemDepResult getDef(Instruction *Inst) {
+ assert(Inst && "Def requires inst");
return MemDepResult(PairTy(Inst, Def));
}
static MemDepResult getClobber(Instruction *Inst) {
+ assert(Inst && "Clobber requires inst");
return MemDepResult(PairTy(Inst, Clobber));
}
static MemDepResult getNonLocal() {
- return MemDepResult(PairTy(0, NonLocal));
+ return MemDepResult(
+ PairTy(reinterpret_cast<Instruction*>(NonLocal), Other));
+ }
+ static MemDepResult getNonFuncLocal() {
+ return MemDepResult(
+ PairTy(reinterpret_cast<Instruction*>(NonFuncLocal), Other));
+ }
+ static MemDepResult getUnknown() {
+ return MemDepResult(
+ PairTy(reinterpret_cast<Instruction*>(Unknown), Other));
}
/// isClobber - Return true if this MemDepResult represents a query that is
- /// a instruction clobber dependency.
+ /// an instruction clobber dependency.
bool isClobber() const { return Value.getInt() == Clobber; }
/// isDef - Return true if this MemDepResult represents a query that is
- /// a instruction definition dependency.
+ /// an instruction definition dependency.
bool isDef() const { return Value.getInt() == Def; }
/// isNonLocal - Return true if this MemDepResult represents a query that
/// is transparent to the start of the block, but where a non-local hasn't
/// been done.
- bool isNonLocal() const { return Value.getInt() == NonLocal; }
+ bool isNonLocal() const {
+ return Value.getInt() == Other
+ && Value.getPointer() == reinterpret_cast<Instruction*>(NonLocal);
+ }
+
+ /// isNonFuncLocal - Return true if this MemDepResult represents a query
+ /// that is transparent to the start of the function.
+ bool isNonFuncLocal() const {
+ return Value.getInt() == Other
+ && Value.getPointer() == reinterpret_cast<Instruction*>(NonFuncLocal);
+ }
+ /// isUnknown - Return true if this MemDepResult represents a query which
+ /// cannot and/or will not be computed.
+ bool isUnknown() const {
+ return Value.getInt() == Other
+ && Value.getPointer() == reinterpret_cast<Instruction*>(Unknown);
+ }
+
/// getInst() - If this is a normal dependency, return the instruction that
/// is depended on. Otherwise, return null.
- Instruction *getInst() const { return Value.getPointer(); }
+ Instruction *getInst() const {
+ if (Value.getInt() == Other) return NULL;
+ return Value.getPointer();
+ }
bool operator==(const MemDepResult &M) const { return Value == M.Value; }
bool operator!=(const MemDepResult &M) const { return Value != M.Value; }
}
};
+ /// 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
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,
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.
- MDNode *TBAATag;
+ const MDNode *TBAATag;
+
+ NonLocalPointerInfo() : Size(AliasAnalysis::UnknownSize), TBAATag(0) {}
};
/// CachedNonLocalPointerInfo - This map stores the cached results of doing
/// Current AA implementation, just a cache.
AliasAnalysis *AA;
- TargetData *TD;
+ DataLayout *TD;
+ DominatorTree *DT;
OwningPtr<PredIteratorCache> PredCache;
public:
MemoryDependenceAnalysis();
bool isLoad, BasicBlock *BB,
SmallVectorImpl<NonLocalDepResult> &Result);
- /// getNonLocalPointerDependence - A convenience wrapper.
- void getNonLocalPointerDependency(Value *Pointer, bool isLoad,
- BasicBlock *BB,
- 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.
void removeInstruction(Instruction *InstToRemove);
/// critical edges.
void invalidateCachedPredecessors();
- private:
+ /// 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);
+
+
+ /// getLoadLoadClobberFullWidthSize - This is a little bit of analysis that
+ /// looks at a memory location for a load (specified by MemLocBase, Offs,
+ /// and Size) and compares it against a load. If the specified load could
+ /// be safely widened to a larger integer load that is 1) still efficient,
+ /// 2) safe for the target, and 3) would provide the specified memory
+ /// location value, then this function returns the size in bytes of the
+ /// load width to use. If not, this returns zero.
+ static unsigned getLoadLoadClobberFullWidthSize(const Value *MemLocBase,
+ int64_t MemLocOffs,
+ unsigned MemLocSize,
+ const LoadInst *LI,
+ const DataLayout &TD);
+
+ private:
MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall,
BasicBlock::iterator ScanIt,
BasicBlock *BB);
projects / oota-llvm.git / blobdiff