MemoryDependenceAnalysis.h revision c765a5acad26ae3d86832d4153e6569d1043a9ca 
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
23namespace llvm {
24  class Function;
25  class FunctionPass;
26  class Instruction;
27  class CallSite;
28  class AliasAnalysis;
29  class TargetData;
30  class MemoryDependenceAnalysis;
31
32  /// MemDepResult - A memory dependence query can return one of three different
33  /// answers, described below.
34  class MemDepResult {
35    enum DepType {
36      /// Invalid - Clients of MemDep never see this.
37      Invalid = 0,
38
39      /// Clobber - This is a dependence on the specified instruction which
40      /// clobbers the desired value.  The pointer member of the MemDepResult
41      /// pair holds the instruction that clobbers the memory.  For example,
42      /// this occurs when we see a may-aliased store to the memory location we
43      /// care about.
44      Clobber,
45
46      /// Def - This is a dependence on the specified instruction which
47      /// defines/produces the desired memory location.  The pointer member of
48      /// the MemDepResult pair holds the instruction that defines the memory.
49      /// Cases of interest:
50      ///   1. This could be a load or store for dependence queries on
51      ///      load/store.  The value loaded or stored is the produced value.
52      ///      Note that the pointer operand may be different than that of the
53      ///      queried pointer due to must aliases and phi translation.  Note
54      ///      that the def may not be the same type as the query, the pointers
55      ///      may just be must aliases.
56      ///   2. For loads and stores, this could be an allocation instruction. In
57      ///      this case, the load is loading an undef value or a store is the
58      ///      first store to (that part of) the allocation.
59      ///   3. Dependence queries on calls return Def only when they are
60      ///      readonly calls with identical callees and no intervening
61      ///      clobbers.  No validation is done that the operands to the calls
62      ///      are the same.
63      Def,
64
65      /// NonLocal - This marker indicates that the query has no dependency in
66      /// the specified block.  To find out more, the client should query other
67      /// predecessor blocks.
68      NonLocal
69    };
70    typedef PointerIntPair<Instruction*, 2, DepType> PairTy;
71    PairTy Value;
72    explicit MemDepResult(PairTy V) : Value(V) {}
73  public:
74    MemDepResult() : Value(0, Invalid) {}
75
76    /// get methods: These are static ctor methods for creating various
77    /// MemDepResult kinds.
78    static MemDepResult getDef(Instruction *Inst) {
79      return MemDepResult(PairTy(Inst, Def));
80    }
81    static MemDepResult getClobber(Instruction *Inst) {
82      return MemDepResult(PairTy(Inst, Clobber));
83    }
84    static MemDepResult getNonLocal() {
85      return MemDepResult(PairTy(0, NonLocal));
86    }
87
88    /// isClobber - Return true if this MemDepResult represents a query that is
89    /// a instruction clobber dependency.
90    bool isClobber() const { return Value.getInt() == Clobber; }
91
92    /// isDef - Return true if this MemDepResult represents a query that is
93    /// a instruction definition dependency.
94    bool isDef() const { return Value.getInt() == Def; }
95
96    /// isNonLocal - Return true if this MemDepResult represents an query that
97    /// is transparent to the start of the block, but where a non-local hasn't
98    /// been done.
99    bool isNonLocal() const { return Value.getInt() == NonLocal; }
100
101    /// getInst() - If this is a normal dependency, return the instruction that
102    /// is depended on.  Otherwise, return null.
103    Instruction *getInst() const { return Value.getPointer(); }
104
105    bool operator==(const MemDepResult &M) const { return M.Value == Value; }
106    bool operator!=(const MemDepResult &M) const { return M.Value != Value; }
107    bool operator<(const MemDepResult &M) const { return M.Value < Value; }
108    bool operator>(const MemDepResult &M) const { return M.Value > Value; }
109  private:
110    friend class MemoryDependenceAnalysis;
111    /// Dirty - Entries with this marker occur in a LocalDeps map or
112    /// NonLocalDeps map when the instruction they previously referenced was
113    /// removed from MemDep.  In either case, the entry may include an
114    /// instruction pointer.  If so, the pointer is an instruction in the
115    /// block where scanning can start from, saving some work.
116    ///
117    /// In a default-constructed MemDepResult object, the type will be Dirty
118    /// and the instruction pointer will be null.
119    ///
120
121    /// isDirty - Return true if this is a MemDepResult in its dirty/invalid.
122    /// state.
123    bool isDirty() const { return Value.getInt() == Invalid; }
124
125    static MemDepResult getDirty(Instruction *Inst) {
126      return MemDepResult(PairTy(Inst, Invalid));
127    }
128  };
129
130  /// MemoryDependenceAnalysis - This is an analysis that determines, for a
131  /// given memory operation, what preceding memory operations it depends on.
132  /// It builds on alias analysis information, and tries to provide a lazy,
133  /// caching interface to a common kind of alias information query.
134  ///
135  /// The dependency information returned is somewhat unusual, but is pragmatic.
136  /// If queried about a store or call that might modify memory, the analysis
137  /// will return the instruction[s] that may either load from that memory or
138  /// store to it.  If queried with a load or call that can never modify memory,
139  /// the analysis will return calls and stores that might modify the pointer,
140  /// but generally does not return loads unless a) they are volatile, or
141  /// b) they load from *must-aliased* pointers.  Returning a dependence on
142  /// must-alias'd pointers instead of all pointers interacts well with the
143  /// internal caching mechanism.
144  ///
145  class MemoryDependenceAnalysis : public FunctionPass {
146    // A map from instructions to their dependency.
147    typedef DenseMap<Instruction*, MemDepResult> LocalDepMapType;
148    LocalDepMapType LocalDeps;
149
150  public:
151    typedef std::pair<BasicBlock*, MemDepResult> NonLocalDepEntry;
152    typedef std::vector<NonLocalDepEntry> NonLocalDepInfo;
153  private:
154    /// ValueIsLoadPair - This is a pair<Value*, bool> where the bool is true if
155    /// the dependence is a read only dependence, false if read/write.
156    typedef PointerIntPair<Value*, 1, bool> ValueIsLoadPair;
157
158    /// CachedNonLocalPointerInfo - This map stores the cached results of doing
159    /// a pointer lookup at the bottom of a block.  The key of this map is the
160    /// pointer+isload bit, the value is a list of <bb->result> mappings.
161    typedef DenseMap<ValueIsLoadPair, NonLocalDepInfo>CachedNonLocalPointerInfo;
162    CachedNonLocalPointerInfo NonLocalPointerDeps;
163
164    // A map from instructions to their non-local pointer dependencies.
165    // The elements of the SmallPtrSet are ValueIsLoadPair's.
166    typedef DenseMap<Instruction*,
167                     SmallPtrSet<void*, 4> > ReverseNonLocalPtrDepTy;
168    ReverseNonLocalPtrDepTy ReverseNonLocalPtrDeps;
169
170
171
172
173    /// PerInstNLInfo - This is the instruction we keep for each cached access
174    /// that we have for an instruction.  The pointer is an owning pointer and
175    /// the bool indicates whether we have any dirty bits in the set.
176    typedef std::pair<NonLocalDepInfo, bool> PerInstNLInfo;
177
178    // A map from instructions to their non-local dependencies.
179    typedef DenseMap<Instruction*, PerInstNLInfo> NonLocalDepMapType;
180
181    NonLocalDepMapType NonLocalDeps;
182
183    // A reverse mapping from dependencies to the dependees.  This is
184    // used when removing instructions to keep the cache coherent.
185    typedef DenseMap<Instruction*,
186                     SmallPtrSet<Instruction*, 4> > ReverseDepMapType;
187    ReverseDepMapType ReverseLocalDeps;
188
189    // A reverse mapping form dependencies to the non-local dependees.
190    ReverseDepMapType ReverseNonLocalDeps;
191
192    /// Current AA implementation, just a cache.
193    AliasAnalysis *AA;
194    TargetData *TD;
195  public:
196    MemoryDependenceAnalysis() : FunctionPass(&ID) {}
197    static char ID;
198
199    /// Pass Implementation stuff.  This doesn't do any analysis eagerly.
200    bool runOnFunction(Function &);
201
202    /// Clean up memory in between runs
203    void releaseMemory() {
204      LocalDeps.clear();
205      NonLocalDeps.clear();
206      NonLocalPointerDeps.clear();
207      ReverseLocalDeps.clear();
208      ReverseNonLocalDeps.clear();
209      ReverseNonLocalPtrDeps.clear();
210    }
211
212    /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
213    /// and Alias Analysis.
214    ///
215    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
216
217    /// getDependency - Return the instruction on which a memory operation
218    /// depends.  See the class comment for more details.  It is illegal to call
219    /// this on non-memory instructions.
220    MemDepResult getDependency(Instruction *QueryInst);
221
222    /// getNonLocalDependency - Perform a full dependency query for the
223    /// specified instruction, returning the set of blocks that the value is
224    /// potentially live across.  The returned set of results will include a
225    /// "NonLocal" result for all blocks where the value is live across.
226    ///
227    /// This method assumes the instruction returns a "NonLocal" dependency
228    /// within its own block.
229    ///
230    /// This returns a reference to an internal data structure that may be
231    /// invalidated on the next non-local query or when an instruction is
232    /// removed.  Clients must copy this data if they want it around longer than
233    /// that.
234    const NonLocalDepInfo &getNonLocalDependency(Instruction *QueryInst);
235
236
237    /// getNonLocalPointerDependency - Perform a full dependency query for an
238    /// access to the specified (non-volatile) memory location, returning the
239    /// set of instructions that either define or clobber the value.
240    ///
241    /// This method assumes the pointer has a "NonLocal" dependency within BB.
242    void getNonLocalPointerDependency(Value *Pointer, bool isLoad,
243                                      BasicBlock *BB,
244                                     SmallVectorImpl<NonLocalDepEntry> &Result);
245
246    /// removeInstruction - Remove an instruction from the dependence analysis,
247    /// updating the dependence of instructions that previously depended on it.
248    void removeInstruction(Instruction *InstToRemove);
249
250  private:
251    MemDepResult getPointerDependencyFrom(Value *Pointer, uint64_t MemSize,
252                                          bool isLoad,
253                                          BasicBlock::iterator ScanIt,
254                                          BasicBlock *BB);
255    MemDepResult getCallSiteDependencyFrom(CallSite C,
256                                           BasicBlock::iterator ScanIt,
257                                           BasicBlock *BB);
258    void getNonLocalPointerDepInternal(Value *Pointer, uint64_t Size,
259                                       bool isLoad, BasicBlock *BB,
260                                      SmallVectorImpl<NonLocalDepEntry> &Result,
261                                       SmallPtrSet<BasicBlock*, 64> &Visited);
262    void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P);
263
264    /// verifyRemoved - Verify that the specified instruction does not occur
265    /// in our internal data structures.
266    void verifyRemoved(Instruction *Inst) const;
267
268  };
269
270} // End llvm namespace
271
272#endif
273