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 the MemoryDependenceAnalysis analysis pass.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
15 #define LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
17 #include "llvm/Pass.h"
18 #include "llvm/Support/CallSite.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/SmallPtrSet.h"
27 /// MemoryDependenceAnalysis - This is an analysis that determines, for a
28 /// given memory operation, what preceding memory operations it depends on.
29 /// It builds on alias analysis information, and tries to provide a lazy,
30 /// caching interface to a common kind of alias information query.
31 class MemoryDependenceAnalysis : public FunctionPass {
33 // A map from instructions to their dependency, with a boolean
34 // flags for whether this mapping is confirmed or not
35 typedef DenseMap<Instruction*, std::pair<Instruction*, bool> >
37 depMapType depGraphLocal;
39 // A map from instructions to their non-local dependencies.
40 typedef DenseMap<Instruction*, DenseMap<BasicBlock*, Value*> >
42 nonLocalDepMapType depGraphNonLocal;
44 // A reverse mapping form dependencies to the dependees. This is
45 // used when removing instructions to keep the cache coherent.
46 typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> >
48 reverseDepMapType reverseDep;
50 // A reverse mapping form dependencies to the non-local dependees.
51 reverseDepMapType reverseDepNonLocal;
54 // Special marker indicating that the query has no dependency
55 // in the specified block.
56 static Instruction* const NonLocal;
58 // Special marker indicating that the query has no dependency at all
59 static Instruction* const None;
61 // Special marker indicating a dirty cache entry
62 static Instruction* const Dirty;
64 static char ID; // Class identification, replacement for typeinfo
65 MemoryDependenceAnalysis() : FunctionPass(&ID) {}
67 /// Pass Implementation stuff. This doesn't do any analysis.
69 bool runOnFunction(Function &) {return false; }
71 /// Clean up memory in between runs
72 void releaseMemory() {
73 depGraphLocal.clear();
74 depGraphNonLocal.clear();
76 reverseDepNonLocal.clear();
79 /// getAnalysisUsage - Does not modify anything. It uses Value Numbering
80 /// and Alias Analysis.
82 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
84 /// getDependency - Return the instruction on which a memory operation
85 /// depends, starting with start.
86 Instruction* getDependency(Instruction* query, Instruction* start = 0,
87 BasicBlock* block = 0);
89 /// getNonLocalDependency - Fills the passed-in map with the non-local
90 /// dependencies of the queries. The map will contain NonLocal for
91 /// blocks between the query and its dependencies.
92 void getNonLocalDependency(Instruction* query,
93 DenseMap<BasicBlock*, Value*>& resp);
95 /// removeInstruction - Remove an instruction from the dependence analysis,
96 /// updating the dependence of instructions that previously depended on it.
97 void removeInstruction(Instruction* rem);
99 /// dropInstruction - Remove an instruction from the analysis, making
100 /// absolutely conservative assumptions when updating the cache. This is
101 /// useful, for example when an instruction is changed rather than removed.
102 void dropInstruction(Instruction* drop);
105 /// verifyRemoved - Verify that the specified instruction does not occur
106 /// in our internal data structures.
107 void verifyRemoved(Instruction *Inst) const;
109 Instruction* getCallSiteDependency(CallSite C, Instruction* start,
111 void nonLocalHelper(Instruction* query, BasicBlock* block,
112 DenseMap<BasicBlock*, Value*>& resp);
115 } // End llvm namespace