5bd6a82d01399289e4e9dd391af63d64827b3fc2
[oota-llvm.git] / include / llvm / Analysis / MemoryDependenceAnalysis.h
1 //===- llvm/Analysis/MemoryDependenceAnalysis.h - Memory Deps  --*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the MemoryDependenceAnalysis analysis pass.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #ifndef LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
15 #define LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
16
17 #include "llvm/BasicBlock.h"
18 #include "llvm/Pass.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/PointerIntPair.h"
22
23 namespace llvm {
24   class Function;
25   class FunctionPass;
26   class Instruction;
27   class CallSite;
28   
29   /// MemDepResult - A memory dependence query can return one of three different
30   /// answers:
31   ///   Normal  : The query is dependent on a specific instruction.
32   ///   NonLocal: The query does not depend on anything inside this block, but
33   ///             we haven't scanned beyond the block to find out what.
34   ///   None    : The query does not depend on anything: we found the entry
35   ///             block or the allocation site of the memory.
36   class MemDepResult {
37     enum DepType {
38       Invalid = 0, Normal, NonLocal, None
39     };
40     typedef PointerIntPair<Instruction*, 2, DepType> PairTy;
41     PairTy Value;
42     explicit MemDepResult(PairTy V) : Value(V) {}
43   public:
44     MemDepResult() : Value(0, Invalid) {}
45     
46     /// get methods: These are static ctor methods for creating various
47     /// MemDepResult kinds.
48     static MemDepResult get(Instruction *Inst) {
49       return MemDepResult(PairTy(Inst, Normal));
50     }
51     static MemDepResult getNonLocal() {
52       return MemDepResult(PairTy(0, NonLocal));
53     }
54     static MemDepResult getNone() {
55       return MemDepResult(PairTy(0, None));
56     }
57
58     /// isNormal - Return true if this MemDepResult represents a query that is
59     /// a normal instruction dependency.
60     bool isNormal() const { return Value.getInt() == Normal; }
61     
62     /// isNonLocal - Return true if this MemDepResult represents an query that
63     /// is transparent to the start of the block, but where a non-local hasn't
64     /// been done.
65     bool isNonLocal() const { return Value.getInt() == NonLocal; }
66     
67     /// isNone - Return true if this MemDepResult represents a query that
68     /// doesn't depend on any instruction.
69     bool isNone() const { return Value.getInt() == None; }
70
71     /// getInst() - If this is a normal dependency, return the instruction that
72     /// is depended on.  Otherwise, return null.
73     Instruction *getInst() const { return isNormal() ? Value.getPointer() : 0; }
74     
75     bool operator==(const MemDepResult &M) { return M.Value == Value; }
76     bool operator!=(const MemDepResult &M) { return M.Value != Value; }
77   };
78
79   /// MemoryDependenceAnalysis - This is an analysis that determines, for a
80   /// given memory operation, what preceding memory operations it depends on.
81   /// It builds on alias analysis information, and tries to provide a lazy,
82   /// caching interface to a common kind of alias information query.
83   class MemoryDependenceAnalysis : public FunctionPass {
84     /// DepType - This enum is used to indicate what flavor of dependence this
85     /// is.  If the type is Normal, there is an associated instruction pointer.
86     enum DepType {
87       /// Dirty - Entries with this marker occur in a LocalDeps map or
88       /// NonLocalDeps map when the instruction they previously referenced was
89       /// removed from MemDep.  In either case, the entry may include an
90       /// instruction pointer.  If so, the pointer is an instruction in the
91       /// block where scanning can start from, saving some work.
92       ///
93       /// In a default-constructed DepResultTy object, the type will be Dirty
94       /// and the instruction pointer will be null.
95       ///
96       Dirty = 0,
97       
98       /// Normal - This is a normal instruction dependence.  The pointer member
99       /// of the DepResultTy pair holds the instruction.
100       Normal,
101
102       /// None - This dependence type indicates that the query does not depend
103       /// on any instructions, either because it scanned to the start of the
104       /// function or it scanned to the definition of the memory
105       /// (alloca/malloc).
106       None,
107       
108       /// NonLocal - This marker indicates that the query has no dependency in
109       /// the specified block.  To find out more, the client should query other
110       /// predecessor blocks.
111       NonLocal
112     };
113     typedef PointerIntPair<Instruction*, 2, DepType> DepResultTy;
114
115     // A map from instructions to their dependency.
116     typedef DenseMap<Instruction*, DepResultTy> LocalDepMapType;
117     LocalDepMapType LocalDeps;
118
119     // A map from instructions to their non-local dependencies.
120     // FIXME: DENSEMAP of DENSEMAP not a great idea.
121     typedef DenseMap<Instruction*,
122                      DenseMap<BasicBlock*, DepResultTy> > NonLocalDepMapType;
123     NonLocalDepMapType NonLocalDeps;
124     
125     // A reverse mapping from dependencies to the dependees.  This is
126     // used when removing instructions to keep the cache coherent.
127     typedef DenseMap<Instruction*,
128                      SmallPtrSet<Instruction*, 4> > ReverseDepMapType;
129     ReverseDepMapType ReverseLocalDeps;
130     
131     // A reverse mapping form dependencies to the non-local dependees.
132     ReverseDepMapType ReverseNonLocalDeps;
133     
134   public:
135     MemoryDependenceAnalysis() : FunctionPass(&ID) {}
136     static char ID;
137
138     /// Pass Implementation stuff.  This doesn't do any analysis.
139     ///
140     bool runOnFunction(Function &) {return false; }
141     
142     /// Clean up memory in between runs
143     void releaseMemory() {
144       LocalDeps.clear();
145       NonLocalDeps.clear();
146       ReverseLocalDeps.clear();
147       ReverseNonLocalDeps.clear();
148     }
149
150     /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
151     /// and Alias Analysis.
152     ///
153     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
154     
155     /// getDependency - Return the instruction on which a memory operation
156     /// depends.
157     MemDepResult getDependency(Instruction *QueryInst);
158
159     /// getDependencyFrom - Return the instruction on which the memory operation
160     /// 'QueryInst' depends.  This starts scanning from the instruction before
161     /// the position indicated by ScanIt.
162     MemDepResult getDependencyFrom(Instruction *QueryInst,
163                                    BasicBlock::iterator ScanIt, BasicBlock *BB);
164
165     
166     /// getNonLocalDependency - Perform a full dependency query for the
167     /// specified instruction, returning the set of blocks that the value is
168     /// potentially live across.  The returned set of results will include a
169     /// "NonLocal" result for all blocks where the value is live across.
170     ///
171     /// This method assumes the instruction returns a "nonlocal" dependency
172     /// within its own block.
173     void getNonLocalDependency(Instruction *QueryInst,
174                                SmallVectorImpl<std::pair<BasicBlock*, 
175                                                        MemDepResult> > &Result);
176     
177     /// removeInstruction - Remove an instruction from the dependence analysis,
178     /// updating the dependence of instructions that previously depended on it.
179     void removeInstruction(Instruction *InstToRemove);
180     
181     /// dropInstruction - Remove an instruction from the analysis, making 
182     /// absolutely conservative assumptions when updating the cache.  This is
183     /// useful, for example when an instruction is changed rather than removed.
184     void dropInstruction(Instruction *InstToDrop);
185     
186   private:
187     DepResultTy ConvFromResult(MemDepResult R) {
188       if (Instruction *I = R.getInst())
189         return DepResultTy(I, Normal);
190       if (R.isNonLocal())
191         return DepResultTy(0, NonLocal);
192       assert(R.isNone() && "Unknown MemDepResult!");
193       return DepResultTy(0, None);
194     }
195     
196     MemDepResult ConvToResult(DepResultTy R) {
197       if (R.getInt() == Normal)
198         return MemDepResult::get(R.getPointer());
199       if (R.getInt() == NonLocal)
200         return MemDepResult::getNonLocal();
201       assert(R.getInt() == None && "Unknown MemDepResult!");
202       return MemDepResult::getNone();
203     }
204     
205     /// verifyRemoved - Verify that the specified instruction does not occur
206     /// in our internal data structures.
207     void verifyRemoved(Instruction *Inst) const;
208     
209     MemDepResult getCallSiteDependency(CallSite C, BasicBlock::iterator ScanIt,
210                                        BasicBlock *BB);
211   };
212
213 } // End llvm namespace
214
215 #endif