class MemoryDependenceAnalysis : public FunctionPass {
private:
-
+ // A map from instructions to their dependency, with a boolean
+ // flags for whether this mapping is confirmed or not
typedef DenseMap<Instruction*, std::pair<Instruction*, bool> >
- depMapType;
-
+ depMapType;
depMapType depGraphLocal;
- typedef DenseMap<Instruction*,
- SmallPtrSet<Instruction*, 4> > reverseDepMapType;
+ // A map from instructions to their non-local dependencies.
+ typedef DenseMap<Instruction*, DenseMap<BasicBlock*, Value*> >
+ nonLocalDepMapType;
+ nonLocalDepMapType depGraphNonLocal;
+
+ // A reverse mapping form dependencies to the dependees. This is
+ // used when removing instructions to keep the cache coherent.
+ typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> >
+ reverseDepMapType;
reverseDepMapType reverseDep;
-
- Instruction* getCallSiteDependency(CallSite C, Instruction* start,
- BasicBlock* block);
- void nonLocalHelper(Instruction* query, BasicBlock* block,
- DenseMap<BasicBlock*, Value*>& resp);
+
+ // A reverse mapping form dependencies to the non-local dependees.
+ reverseDepMapType reverseDepNonLocal;
+
public:
+ // Special marker indicating that the query has no dependency
+ // in the specified block.
+ static Instruction* const NonLocal;
- static Instruction* NonLocal;
- static Instruction* None;
+ // Special marker indicating that the query has no dependency at all
+ static Instruction* const None;
+
+
+ // Special marker indicating a dirty cache entry
+ static Instruction* const Dirty;
static char ID; // Class identification, replacement for typeinfo
MemoryDependenceAnalysis() : FunctionPass((intptr_t)&ID) {}
/// Clean up memory in between runs
void releaseMemory() {
depGraphLocal.clear();
+ depGraphNonLocal.clear();
reverseDep.clear();
+ reverseDepNonLocal.clear();
}
/// getAnalysisUsage - Does not modify anything. It uses Value Numbering
Instruction* getDependency(Instruction* query, Instruction* start = 0,
BasicBlock* block = 0);
+ /// getNonLocalDependency - Fills the passed-in map with the non-local
+ /// dependencies of the queries. The map will contain NonLocal for
+ /// blocks between the query and its dependencies.
void getNonLocalDependency(Instruction* query,
DenseMap<BasicBlock*, Value*>& resp);
/// removeInstruction - Remove an instruction from the dependence analysis,
/// updating the dependence of instructions that previously depended on it.
void removeInstruction(Instruction* rem);
+
+ private:
+ Instruction* getCallSiteDependency(CallSite C, Instruction* start,
+ BasicBlock* block);
+ void nonLocalHelper(Instruction* query, BasicBlock* block,
+ DenseMap<BasicBlock*, Value*>& resp);
};
} // End llvm namespace