LLVM API Documentation

MemoryDependenceAnalysis.h

Go to the documentation of this file.
00001 //===- llvm/Analysis/MemoryDependenceAnalysis.h - Memory Deps  --*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the MemoryDependenceAnalysis analysis pass.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #ifndef LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
00015 #define LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
00016 
00017 #include "llvm/BasicBlock.h"
00018 #include "llvm/Pass.h"
00019 #include "llvm/ADT/DenseMap.h"
00020 #include "llvm/ADT/SmallPtrSet.h"
00021 #include "llvm/ADT/OwningPtr.h"
00022 #include "llvm/ADT/PointerIntPair.h"
00023 
00024 namespace llvm {
00025   class Function;
00026   class FunctionPass;
00027   class Instruction;
00028   class CallSite;
00029   class AliasAnalysis;
00030   class TargetData;
00031   class MemoryDependenceAnalysis;
00032   class PredIteratorCache;
00033   
00034   /// MemDepResult - A memory dependence query can return one of three different
00035   /// answers, described below.
00036   class MemDepResult {
00037     enum DepType {
00038       /// Invalid - Clients of MemDep never see this.
00039       Invalid = 0,
00040       
00041       /// Clobber - This is a dependence on the specified instruction which
00042       /// clobbers the desired value.  The pointer member of the MemDepResult
00043       /// pair holds the instruction that clobbers the memory.  For example,
00044       /// this occurs when we see a may-aliased store to the memory location we
00045       /// care about.
00046       Clobber,
00047 
00048       /// Def - This is a dependence on the specified instruction which
00049       /// defines/produces the desired memory location.  The pointer member of
00050       /// the MemDepResult pair holds the instruction that defines the memory.
00051       /// Cases of interest:
00052       ///   1. This could be a load or store for dependence queries on
00053       ///      load/store.  The value loaded or stored is the produced value.
00054       ///      Note that the pointer operand may be different than that of the
00055       ///      queried pointer due to must aliases and phi translation.  Note
00056       ///      that the def may not be the same type as the query, the pointers
00057       ///      may just be must aliases.
00058       ///   2. For loads and stores, this could be an allocation instruction. In
00059       ///      this case, the load is loading an undef value or a store is the
00060       ///      first store to (that part of) the allocation.
00061       ///   3. Dependence queries on calls return Def only when they are
00062       ///      readonly calls with identical callees and no intervening
00063       ///      clobbers.  No validation is done that the operands to the calls
00064       ///      are the same.
00065       Def,
00066       
00067       /// NonLocal - This marker indicates that the query has no dependency in
00068       /// the specified block.  To find out more, the client should query other
00069       /// predecessor blocks.
00070       NonLocal
00071     };
00072     typedef PointerIntPair<Instruction*, 2, DepType> PairTy;
00073     PairTy Value;
00074     explicit MemDepResult(PairTy V) : Value(V) {}
00075   public:
00076     MemDepResult() : Value(0, Invalid) {}
00077     
00078     /// get methods: These are static ctor methods for creating various
00079     /// MemDepResult kinds.
00080     static MemDepResult getDef(Instruction *Inst) {
00081       return MemDepResult(PairTy(Inst, Def));
00082     }
00083     static MemDepResult getClobber(Instruction *Inst) {
00084       return MemDepResult(PairTy(Inst, Clobber));
00085     }
00086     static MemDepResult getNonLocal() {
00087       return MemDepResult(PairTy(0, NonLocal));
00088     }
00089 
00090     /// isClobber - Return true if this MemDepResult represents a query that is
00091     /// a instruction clobber dependency.
00092     bool isClobber() const { return Value.getInt() == Clobber; }
00093 
00094     /// isDef - Return true if this MemDepResult represents a query that is
00095     /// a instruction definition dependency.
00096     bool isDef() const { return Value.getInt() == Def; }
00097     
00098     /// isNonLocal - Return true if this MemDepResult represents a query that
00099     /// is transparent to the start of the block, but where a non-local hasn't
00100     /// been done.
00101     bool isNonLocal() const { return Value.getInt() == NonLocal; }
00102     
00103     /// getInst() - If this is a normal dependency, return the instruction that
00104     /// is depended on.  Otherwise, return null.
00105     Instruction *getInst() const { return Value.getPointer(); }
00106     
00107     bool operator==(const MemDepResult &M) const { return Value == M.Value; }
00108     bool operator!=(const MemDepResult &M) const { return Value != M.Value; }
00109     bool operator<(const MemDepResult &M) const { return Value < M.Value; }
00110     bool operator>(const MemDepResult &M) const { return Value > M.Value; }
00111   private:
00112     friend class MemoryDependenceAnalysis;
00113     /// Dirty - Entries with this marker occur in a LocalDeps map or
00114     /// NonLocalDeps map when the instruction they previously referenced was
00115     /// removed from MemDep.  In either case, the entry may include an
00116     /// instruction pointer.  If so, the pointer is an instruction in the
00117     /// block where scanning can start from, saving some work.
00118     ///
00119     /// In a default-constructed MemDepResult object, the type will be Dirty
00120     /// and the instruction pointer will be null.
00121     ///
00122          
00123     /// isDirty - Return true if this is a MemDepResult in its dirty/invalid.
00124     /// state.
00125     bool isDirty() const { return Value.getInt() == Invalid; }
00126     
00127     static MemDepResult getDirty(Instruction *Inst) {
00128       return MemDepResult(PairTy(Inst, Invalid));
00129     }
00130   };
00131 
00132   /// MemoryDependenceAnalysis - This is an analysis that determines, for a
00133   /// given memory operation, what preceding memory operations it depends on.
00134   /// It builds on alias analysis information, and tries to provide a lazy,
00135   /// caching interface to a common kind of alias information query.
00136   ///
00137   /// The dependency information returned is somewhat unusual, but is pragmatic.
00138   /// If queried about a store or call that might modify memory, the analysis
00139   /// will return the instruction[s] that may either load from that memory or
00140   /// store to it.  If queried with a load or call that can never modify memory,
00141   /// the analysis will return calls and stores that might modify the pointer,
00142   /// but generally does not return loads unless a) they are volatile, or
00143   /// b) they load from *must-aliased* pointers.  Returning a dependence on
00144   /// must-alias'd pointers instead of all pointers interacts well with the
00145   /// internal caching mechanism.
00146   ///
00147   class MemoryDependenceAnalysis : public FunctionPass {
00148     // A map from instructions to their dependency.
00149     typedef DenseMap<Instruction*, MemDepResult> LocalDepMapType;
00150     LocalDepMapType LocalDeps;
00151 
00152   public:
00153     typedef std::pair<BasicBlock*, MemDepResult> NonLocalDepEntry;
00154     typedef std::vector<NonLocalDepEntry> NonLocalDepInfo;
00155   private:
00156     /// ValueIsLoadPair - This is a pair<Value*, bool> where the bool is true if
00157     /// the dependence is a read only dependence, false if read/write.
00158     typedef PointerIntPair<Value*, 1, bool> ValueIsLoadPair;
00159 
00160     /// BBSkipFirstBlockPair - This pair is used when caching information for a
00161     /// block.  If the pointer is null, the cache value is not a full query that
00162     /// starts at the specified block.  If non-null, the bool indicates whether
00163     /// or not the contents of the block was skipped.
00164     typedef PointerIntPair<BasicBlock*, 1, bool> BBSkipFirstBlockPair;
00165 
00166     /// CachedNonLocalPointerInfo - This map stores the cached results of doing
00167     /// a pointer lookup at the bottom of a block.  The key of this map is the
00168     /// pointer+isload bit, the value is a list of <bb->result> mappings.
00169     typedef DenseMap<ValueIsLoadPair, std::pair<BBSkipFirstBlockPair, 
00170                   NonLocalDepInfo> > CachedNonLocalPointerInfo;
00171     CachedNonLocalPointerInfo NonLocalPointerDeps;
00172 
00173     // A map from instructions to their non-local pointer dependencies.
00174     typedef DenseMap<Instruction*, 
00175                      SmallPtrSet<ValueIsLoadPair, 4> > ReverseNonLocalPtrDepTy;
00176     ReverseNonLocalPtrDepTy ReverseNonLocalPtrDeps;
00177 
00178     
00179     /// PerInstNLInfo - This is the instruction we keep for each cached access
00180     /// that we have for an instruction.  The pointer is an owning pointer and
00181     /// the bool indicates whether we have any dirty bits in the set.
00182     typedef std::pair<NonLocalDepInfo, bool> PerInstNLInfo;
00183     
00184     // A map from instructions to their non-local dependencies.
00185     typedef DenseMap<Instruction*, PerInstNLInfo> NonLocalDepMapType;
00186       
00187     NonLocalDepMapType NonLocalDeps;
00188     
00189     // A reverse mapping from dependencies to the dependees.  This is
00190     // used when removing instructions to keep the cache coherent.
00191     typedef DenseMap<Instruction*,
00192                      SmallPtrSet<Instruction*, 4> > ReverseDepMapType;
00193     ReverseDepMapType ReverseLocalDeps;
00194     
00195     // A reverse mapping form dependencies to the non-local dependees.
00196     ReverseDepMapType ReverseNonLocalDeps;
00197     
00198     /// Current AA implementation, just a cache.
00199     AliasAnalysis *AA;
00200     TargetData *TD;
00201     OwningPtr<PredIteratorCache> PredCache;
00202   public:
00203     MemoryDependenceAnalysis();
00204     ~MemoryDependenceAnalysis();
00205     static char ID;
00206 
00207     /// Pass Implementation stuff.  This doesn't do any analysis eagerly.
00208     bool runOnFunction(Function &);
00209     
00210     /// Clean up memory in between runs
00211     void releaseMemory();
00212     
00213     /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
00214     /// and Alias Analysis.
00215     ///
00216     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
00217     
00218     /// getDependency - Return the instruction on which a memory operation
00219     /// depends.  See the class comment for more details.  It is illegal to call
00220     /// this on non-memory instructions.
00221     MemDepResult getDependency(Instruction *QueryInst);
00222 
00223     /// getNonLocalCallDependency - Perform a full dependency query for the
00224     /// specified call, returning the set of blocks that the value is
00225     /// potentially live across.  The returned set of results will include a
00226     /// "NonLocal" result for all blocks where the value is live across.
00227     ///
00228     /// This method assumes the instruction returns a "NonLocal" dependency
00229     /// within its own block.
00230     ///
00231     /// This returns a reference to an internal data structure that may be
00232     /// invalidated on the next non-local query or when an instruction is
00233     /// removed.  Clients must copy this data if they want it around longer than
00234     /// that.
00235     const NonLocalDepInfo &getNonLocalCallDependency(CallSite QueryCS);
00236     
00237     
00238     /// getNonLocalPointerDependency - Perform a full dependency query for an
00239     /// access to the specified (non-volatile) memory location, returning the
00240     /// set of instructions that either define or clobber the value.
00241     ///
00242     /// This method assumes the pointer has a "NonLocal" dependency within BB.
00243     void getNonLocalPointerDependency(Value *Pointer, bool isLoad,
00244                                       BasicBlock *BB,
00245                                      SmallVectorImpl<NonLocalDepEntry> &Result);
00246     
00247     /// removeInstruction - Remove an instruction from the dependence analysis,
00248     /// updating the dependence of instructions that previously depended on it.
00249     void removeInstruction(Instruction *InstToRemove);
00250     
00251     /// invalidateCachedPointerInfo - This method is used to invalidate cached
00252     /// information about the specified pointer, because it may be too
00253     /// conservative in memdep.  This is an optional call that can be used when
00254     /// the client detects an equivalence between the pointer and some other
00255     /// value and replaces the other value with ptr. This can make Ptr available
00256     /// in more places that cached info does not necessarily keep.
00257     void invalidateCachedPointerInfo(Value *Ptr);
00258     
00259   private:
00260     MemDepResult getPointerDependencyFrom(Value *Pointer, uint64_t MemSize,
00261                                           bool isLoad, 
00262                                           BasicBlock::iterator ScanIt,
00263                                           BasicBlock *BB);
00264     MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall,
00265                                            BasicBlock::iterator ScanIt,
00266                                            BasicBlock *BB);
00267     bool getNonLocalPointerDepFromBB(Value *Pointer, uint64_t Size,
00268                                      bool isLoad, BasicBlock *BB,
00269                                      SmallVectorImpl<NonLocalDepEntry> &Result,
00270                                      DenseMap<BasicBlock*, Value*> &Visited,
00271                                      bool SkipFirstBlock = false);
00272     MemDepResult GetNonLocalInfoForBlock(Value *Pointer, uint64_t PointeeSize,
00273                                          bool isLoad, BasicBlock *BB,
00274                                          NonLocalDepInfo *Cache,
00275                                          unsigned NumSortedEntries);
00276 
00277     void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P);
00278     
00279     /// verifyRemoved - Verify that the specified instruction does not occur
00280     /// in our internal data structures.
00281     void verifyRemoved(Instruction *Inst) const;
00282     
00283   };
00284 
00285 } // End llvm namespace
00286 
00287 #endif