MemoryDependenceAnalysis.h revision d777d405cdda8d418ba8e8818e5c1272dfd999a0 
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
31  /// MemDepResult - A memory dependence query can return one of three different
32  /// answers:
33  ///   Normal  : The query is dependent on a specific instruction.
34  ///   NonLocal: The query does not depend on anything inside this block, but
35  ///             we haven't scanned beyond the block to find out what.
36  ///   None    : The query does not depend on anything: we found the entry
37  ///             block or the allocation site of the memory.
38  class MemDepResult {
39    enum DepType {
40      Invalid = 0, Normal, NonLocal, None
41    };
42    typedef PointerIntPair<Instruction*, 2, DepType> PairTy;
43    PairTy Value;
44    explicit MemDepResult(PairTy V) : Value(V) {}
45  public:
46    MemDepResult() : Value(0, Invalid) {}
47
48    /// get methods: These are static ctor methods for creating various
49    /// MemDepResult kinds.
50    static MemDepResult get(Instruction *Inst) {
51      return MemDepResult(PairTy(Inst, Normal));
52    }
53    static MemDepResult getNonLocal() {
54      return MemDepResult(PairTy(0, NonLocal));
55    }
56    static MemDepResult getNone() {
57      return MemDepResult(PairTy(0, None));
58    }
59
60    /// isNormal - Return true if this MemDepResult represents a query that is
61    /// a normal instruction dependency.
62    bool isNormal() const { return Value.getInt() == Normal; }
63
64    /// isNonLocal - Return true if this MemDepResult represents an query that
65    /// is transparent to the start of the block, but where a non-local hasn't
66    /// been done.
67    bool isNonLocal() const { return Value.getInt() == NonLocal; }
68
69    /// isNone - Return true if this MemDepResult represents a query that
70    /// doesn't depend on any instruction.
71    bool isNone() const { return Value.getInt() == None; }
72
73    /// getInst() - If this is a normal dependency, return the instruction that
74    /// is depended on.  Otherwise, return null.
75    Instruction *getInst() const { return isNormal() ? Value.getPointer() : 0; }
76
77    bool operator==(const MemDepResult &M) { return M.Value == Value; }
78    bool operator!=(const MemDepResult &M) { return M.Value != Value; }
79  };
80
81  /// MemoryDependenceAnalysis - This is an analysis that determines, for a
82  /// given memory operation, what preceding memory operations it depends on.
83  /// It builds on alias analysis information, and tries to provide a lazy,
84  /// caching interface to a common kind of alias information query.
85  ///
86  /// The dependency information returned is somewhat unusual, but is pragmatic.
87  /// If queried about a store or call that might modify memory, the analysis
88  /// will return the instruction[s] that may either load from that memory or
89  /// store to it.  If queried with a load or call that can never modify memory,
90  /// the analysis will return calls and stores that might modify the pointer,
91  /// but generally does not return loads unless a) they are volatile, or
92  /// b) they load from *must-aliased* pointers.  Returning a dependence on
93  /// must-alias'd pointers instead of all pointers interacts well with the
94  /// internal caching mechanism.
95  ///
96  class MemoryDependenceAnalysis : public FunctionPass {
97    /// DepType - This enum is used to indicate what flavor of dependence this
98    /// is.  If the type is Normal, there is an associated instruction pointer.
99    enum DepType {
100      /// Dirty - Entries with this marker occur in a LocalDeps map or
101      /// NonLocalDeps map when the instruction they previously referenced was
102      /// removed from MemDep.  In either case, the entry may include an
103      /// instruction pointer.  If so, the pointer is an instruction in the
104      /// block where scanning can start from, saving some work.
105      ///
106      /// In a default-constructed DepResultTy object, the type will be Dirty
107      /// and the instruction pointer will be null.
108      ///
109      Dirty = 0,
110
111      /// Normal - This is a normal instruction dependence.  The pointer member
112      /// of the DepResultTy pair holds the instruction.
113      Normal,
114
115      /// None - This dependence type indicates that the query does not depend
116      /// on any instructions, either because it is not a memory instruction or
117      /// because it scanned to the definition of the memory (alloca/malloc)
118      /// being accessed.
119      None,
120
121      /// NonLocal - This marker indicates that the query has no dependency in
122      /// the specified block.  To find out more, the client should query other
123      /// predecessor blocks.
124      NonLocal
125    };
126    typedef PointerIntPair<Instruction*, 2, DepType> DepResultTy;
127
128    // A map from instructions to their dependency.
129    typedef DenseMap<Instruction*, DepResultTy> LocalDepMapType;
130    LocalDepMapType LocalDeps;
131
132    typedef DenseMap<BasicBlock*, DepResultTy> NonLocalDepInfo;
133
134    /// PerInstNLInfo - This is the instruction we keep for each cached access
135    /// that we have for an instruction.  The pointer is an owning pointer and
136    /// the bool indicates whether we have any dirty bits in the set.
137    typedef PointerIntPair<NonLocalDepInfo*, 1, bool> PerInstNLInfo;
138
139    // A map from instructions to their non-local dependencies.
140    typedef DenseMap<Instruction*, PerInstNLInfo> NonLocalDepMapType;
141
142    NonLocalDepMapType NonLocalDeps;
143
144    // A reverse mapping from dependencies to the dependees.  This is
145    // used when removing instructions to keep the cache coherent.
146    typedef DenseMap<Instruction*,
147                     SmallPtrSet<Instruction*, 4> > ReverseDepMapType;
148    ReverseDepMapType ReverseLocalDeps;
149
150    // A reverse mapping form dependencies to the non-local dependees.
151    ReverseDepMapType ReverseNonLocalDeps;
152
153    /// Current AA implementation, just a cache.
154    AliasAnalysis *AA;
155    TargetData *TD;
156  public:
157    MemoryDependenceAnalysis() : FunctionPass(&ID) {}
158    static char ID;
159
160    /// Pass Implementation stuff.  This doesn't do any analysis eagerly.
161    bool runOnFunction(Function &);
162
163    /// Clean up memory in between runs
164    void releaseMemory() {
165      LocalDeps.clear();
166      for (NonLocalDepMapType::iterator I = NonLocalDeps.begin(),
167           E = NonLocalDeps.end(); I != E; ++I)
168        delete I->second.getPointer();
169      NonLocalDeps.clear();
170      ReverseLocalDeps.clear();
171      ReverseNonLocalDeps.clear();
172    }
173
174    /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
175    /// and Alias Analysis.
176    ///
177    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
178
179    /// getDependency - Return the instruction on which a memory operation
180    /// depends.  See the class comment for more details.
181    MemDepResult getDependency(Instruction *QueryInst);
182
183    /// getDependencyFrom - Return the instruction on which the memory operation
184    /// 'QueryInst' depends.  This starts scanning from the instruction before
185    /// the position indicated by ScanIt.
186    ///
187    /// Note that this method does no caching at all.  You should use
188    /// getDependency where possible.
189    MemDepResult getDependencyFrom(Instruction *QueryInst,
190                                   BasicBlock::iterator ScanIt, BasicBlock *BB){
191      return ConvToResult(getDependencyFromInternal(QueryInst, ScanIt, BB));
192    }
193
194
195    /// getNonLocalDependency - Perform a full dependency query for the
196    /// specified instruction, returning the set of blocks that the value is
197    /// potentially live across.  The returned set of results will include a
198    /// "NonLocal" result for all blocks where the value is live across.
199    ///
200    /// This method assumes the instruction returns a "nonlocal" dependency
201    /// within its own block.
202    void getNonLocalDependency(Instruction *QueryInst,
203                               SmallVectorImpl<std::pair<BasicBlock*,
204                                                       MemDepResult> > &Result);
205
206    /// removeInstruction - Remove an instruction from the dependence analysis,
207    /// updating the dependence of instructions that previously depended on it.
208    void removeInstruction(Instruction *InstToRemove);
209
210  private:
211    MemDepResult ConvToResult(DepResultTy R) {
212      if (R.getInt() == Normal)
213        return MemDepResult::get(R.getPointer());
214      if (R.getInt() == NonLocal)
215        return MemDepResult::getNonLocal();
216      assert(R.getInt() == None && "Unknown MemDepResult!");
217      return MemDepResult::getNone();
218    }
219
220    /// verifyRemoved - Verify that the specified instruction does not occur
221    /// in our internal data structures.
222    void verifyRemoved(Instruction *Inst) const;
223
224    /// getDependencyFromInternal - Return the instruction on which the memory
225    /// operation 'QueryInst' depends.  This starts scanning from the
226    /// instruction before the position indicated by ScanIt.
227    DepResultTy getDependencyFromInternal(Instruction *QueryInst,
228                                   BasicBlock::iterator ScanIt, BasicBlock *BB);
229    DepResultTy getCallSiteDependency(CallSite C, BasicBlock::iterator ScanIt,
230                                      BasicBlock *BB);
231  };
232
233} // End llvm namespace
234
235#endif
236