1 //===- llvm/Analysis/MemoryDependenceAnalysis.h - Memory Deps --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines an analysis that determines, for a given memory operation,
11 // what preceding memory operations it depends on. It builds on alias analysis
12 // information, and tries to provide a lazy, caching interface to a common kind
13 // of alias information query.
15 //===----------------------------------------------------------------------===//
17 #ifndef LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
18 #define LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
20 #include "llvm/Pass.h"
21 #include "llvm/Support/CallSite.h"
22 #include "llvm/ADT/DenseMap.h"
23 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/Support/Compiler.h"
32 class MemoryDependenceAnalysis : public FunctionPass {
34 // A map from instructions to their dependency, with a boolean
35 // flags for whether this mapping is confirmed or not
36 typedef DenseMap<Instruction*, std::pair<Instruction*, bool> >
38 depMapType depGraphLocal;
40 // A map from instructions to their non-local dependencies.
41 typedef DenseMap<Instruction*, DenseMap<BasicBlock*, Value*> >
43 nonLocalDepMapType depGraphNonLocal;
45 // A reverse mapping form dependencies to the dependees. This is
46 // used when removing instructions to keep the cache coherent.
47 typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> >
49 reverseDepMapType reverseDep;
51 // A reverse mapping form dependencies to the non-local dependees.
52 reverseDepMapType reverseDepNonLocal;
55 void ping(Instruction* D);
57 // Special marker indicating that the query has no dependency
58 // in the specified block.
59 static Instruction* const NonLocal;
61 // Special marker indicating that the query has no dependency at all
62 static Instruction* const None;
65 // Special marker indicating a dirty cache entry
66 static Instruction* const Dirty;
68 static char ID; // Class identification, replacement for typeinfo
69 MemoryDependenceAnalysis() : FunctionPass((intptr_t)&ID) {}
71 /// Pass Implementation stuff. This doesn't do any analysis.
73 bool runOnFunction(Function &) {return false; }
75 /// Clean up memory in between runs
76 void releaseMemory() {
77 depGraphLocal.clear();
78 depGraphNonLocal.clear();
80 reverseDepNonLocal.clear();
83 /// getAnalysisUsage - Does not modify anything. It uses Value Numbering
84 /// and Alias Analysis.
86 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
88 /// getDependency - Return the instruction on which a memory operation
89 /// depends, starting with start.
90 Instruction* getDependency(Instruction* query, Instruction* start = 0,
91 BasicBlock* block = 0);
93 /// getNonLocalDependency - Fills the passed-in map with the non-local
94 /// dependencies of the queries. The map will contain NonLocal for
95 /// blocks between the query and its dependencies.
96 void getNonLocalDependency(Instruction* query,
97 DenseMap<BasicBlock*, Value*>& resp);
99 /// removeInstruction - Remove an instruction from the dependence analysis,
100 /// updating the dependence of instructions that previously depended on it.
101 void removeInstruction(Instruction* rem);
103 /// dropInstruction - Remove an instruction from the analysis, making
104 /// absolutely conservative assumptions when updating the cache. This is
105 /// useful, for example when an instruction is changed rather than removed.
106 void dropInstruction(Instruction* drop);
109 Instruction* getCallSiteDependency(CallSite C, Instruction* start,
111 void nonLocalHelper(Instruction* query, BasicBlock* block,
112 DenseMap<BasicBlock*, Value*>& resp);
115 } // End llvm namespace