LLVM API Documentation

AliasAnalysis.h

Go to the documentation of this file.
00001 //===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the generic AliasAnalysis interface, which is used as the
00011 // common interface used by all clients of alias analysis information, and
00012 // implemented by all alias analysis implementations.  Mod/Ref information is
00013 // also captured by this interface.
00014 //
00015 // Implementations of this interface must implement the various virtual methods,
00016 // which automatically provides functionality for the entire suite of client
00017 // APIs.
00018 //
00019 // This API represents memory as a (Pointer, Size) pair.  The Pointer component
00020 // specifies the base memory address of the region, the Size specifies how large
00021 // of an area is being queried.  If Size is 0, two pointers only alias if they
00022 // are exactly equal.  If size is greater than zero, but small, the two pointers
00023 // alias if the areas pointed to overlap.  If the size is very large (ie, ~0U),
00024 // then the two pointers alias if they may be pointing to components of the same
00025 // memory object.  Pointers that point to two completely different objects in
00026 // memory never alias, regardless of the value of the Size component.
00027 //
00028 //===----------------------------------------------------------------------===//
00029 
00030 #ifndef LLVM_ANALYSIS_ALIAS_ANALYSIS_H
00031 #define LLVM_ANALYSIS_ALIAS_ANALYSIS_H
00032 
00033 #include "llvm/Support/CallSite.h"
00034 #include "llvm/Pass.h"    // Need this for IncludeFile
00035 
00036 namespace llvm {
00037 
00038 class LoadInst;
00039 class StoreInst;
00040 class VAArgInst;
00041 class TargetData;
00042 
00043 class AliasAnalysis {
00044 protected:
00045   const TargetData *TD;
00046   AliasAnalysis *AA;       // Previous Alias Analysis to chain to.
00047 
00048   /// InitializeAliasAnalysis - Subclasses must call this method to initialize
00049   /// the AliasAnalysis interface before any other methods are called.  This is
00050   /// typically called by the run* methods of these subclasses.  This may be
00051   /// called multiple times.
00052   ///
00053   void InitializeAliasAnalysis(Pass *P);
00054 
00055   // getAnalysisUsage - All alias analysis implementations should invoke this
00056   // directly (using AliasAnalysis::getAnalysisUsage(AU)) to make sure that
00057   // TargetData is required by the pass.
00058   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
00059 
00060 public:
00061   AliasAnalysis() : TD(0), AA(0) {}
00062   virtual ~AliasAnalysis();  // We want to be subclassed
00063 
00064   /// getTargetData - Every alias analysis implementation depends on the size of
00065   /// data items in the current Target.  This provides a uniform way to handle
00066   /// it.
00067   ///
00068   const TargetData &getTargetData() const { return *TD; }
00069 
00070   //===--------------------------------------------------------------------===//
00071   /// Alias Queries...
00072   ///
00073 
00074   /// Alias analysis result - Either we know for sure that it does not alias, we
00075   /// know for sure it must alias, or we don't know anything: The two pointers
00076   /// _might_ alias.  This enum is designed so you can do things like:
00077   ///     if (AA.alias(P1, P2)) { ... }
00078   /// to check to see if two pointers might alias.
00079   ///
00080   enum AliasResult { NoAlias = 0, MayAlias = 1, MustAlias = 2 };
00081 
00082   /// alias - The main low level interface to the alias analysis implementation.
00083   /// Returns a Result indicating whether the two pointers are aliased to each
00084   /// other.  This is the interface that must be implemented by specific alias
00085   /// analysis implementations.
00086   ///
00087   virtual AliasResult alias(const Value *V1, unsigned V1Size,
00088                             const Value *V2, unsigned V2Size);
00089 
00090   /// getMustAliases - If there are any pointers known that must alias this
00091   /// pointer, return them now.  This allows alias-set based alias analyses to
00092   /// perform a form a value numbering (which is exposed by load-vn).  If an
00093   /// alias analysis supports this, it should ADD any must aliased pointers to
00094   /// the specified vector.
00095   ///
00096   virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals);
00097 
00098   /// pointsToConstantMemory - If the specified pointer is known to point into
00099   /// constant global memory, return true.  This allows disambiguation of store
00100   /// instructions from constant pointers.
00101   ///
00102   virtual bool pointsToConstantMemory(const Value *P);
00103 
00104   //===--------------------------------------------------------------------===//
00105   /// Simple mod/ref information...
00106   ///
00107 
00108   /// ModRefResult - Represent the result of a mod/ref query.  Mod and Ref are
00109   /// bits which may be or'd together.
00110   ///
00111   enum ModRefResult { NoModRef = 0, Ref = 1, Mod = 2, ModRef = 3 };
00112 
00113 
00114   /// ModRefBehavior - Summary of how a function affects memory in the program.
00115   /// Loads from constant globals are not considered memory accesses for this
00116   /// interface.  Also, functions may freely modify stack space local to their
00117   /// invocation without having to report it through these interfaces.
00118   enum ModRefBehavior {
00119     // DoesNotAccessMemory - This function does not perform any non-local loads
00120     // or stores to memory.
00121     //
00122     // This property corresponds to the GCC 'const' attribute.
00123     DoesNotAccessMemory,
00124 
00125     // AccessesArguments - This function accesses function arguments in
00126     // non-volatile and well known ways, but does not access any other memory.
00127     //
00128     // Clients may call getArgumentAccesses to get specific information about
00129     // how pointer arguments are used.
00130     AccessesArguments,
00131 
00132     // AccessesArgumentsAndGlobals - This function has accesses function
00133     // arguments and global variables in non-volatile and well-known ways, but
00134     // does not access any other memory.
00135     //
00136     // Clients may call getArgumentAccesses to get specific information about
00137     // how pointer arguments and globals are used.
00138     AccessesArgumentsAndGlobals,
00139 
00140     // OnlyReadsMemory - This function does not perform any non-local stores or
00141     // volatile loads, but may read from any memory location.
00142     //
00143     // This property corresponds to the GCC 'pure' attribute.
00144     OnlyReadsMemory,
00145 
00146     // UnknownModRefBehavior - This indicates that the function could not be
00147     // classified into one of the behaviors above.
00148     UnknownModRefBehavior
00149   };
00150 
00151   /// PointerAccessInfo - This struct is used to return results for pointers,
00152   /// globals, and the return value of a function.
00153   struct PointerAccessInfo {
00154     /// V - The value this record corresponds to.  This may be an Argument for
00155     /// the function, a GlobalVariable, or null, corresponding to the return
00156     /// value for the function.
00157     Value *V;
00158 
00159     /// ModRefInfo - Whether the pointer is loaded or stored to/from.
00160     ///
00161     ModRefResult ModRefInfo;
00162 
00163     /// AccessType - Specific fine-grained access information for the argument.
00164     /// If none of these classifications is general enough, the
00165     /// getModRefBehavior method should not return AccessesArguments*.  If a
00166     /// record is not returned for a particular argument, the argument is never
00167     /// dead and never dereferenced.
00168     enum AccessType {
00169       /// ScalarAccess - The pointer is dereferenced.
00170       ///
00171       ScalarAccess,
00172 
00173       /// ArrayAccess - The pointer is indexed through as an array of elements.
00174       ///
00175       ArrayAccess,
00176 
00177       /// ElementAccess ?? P->F only?
00178 
00179       /// CallsThrough - Indirect calls are made through the specified function
00180       /// pointer.
00181       CallsThrough
00182     };
00183   };
00184 
00185   /// getModRefBehavior - Return the behavior of the specified function if
00186   /// called from the specified call site.  The call site may be null in which
00187   /// case the most generic behavior of this function should be returned.
00188   virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
00189                                      std::vector<PointerAccessInfo> *Info = 0);
00190 
00191   /// doesNotAccessMemory - If the specified function is known to never read or
00192   /// write memory, return true.  If the function only reads from known-constant
00193   /// memory, it is also legal to return true.  Functions that unwind the stack
00194   /// are not legal for this predicate.
00195   ///
00196   /// Many optimizations (such as CSE and LICM) can be performed on calls to it,
00197   /// without worrying about aliasing properties, and many functions have this
00198   /// property (e.g. 'sin' and 'cos').
00199   ///
00200   /// This property corresponds to the GCC 'const' attribute.
00201   ///
00202   bool doesNotAccessMemory(Function *F) {
00203     return getModRefBehavior(F, CallSite()) == DoesNotAccessMemory;
00204   }
00205 
00206   /// onlyReadsMemory - If the specified function is known to only read from
00207   /// non-volatile memory (or not access memory at all), return true.  Functions
00208   /// that unwind the stack are not legal for this predicate.
00209   ///
00210   /// This property allows many common optimizations to be performed in the
00211   /// absence of interfering store instructions, such as CSE of strlen calls.
00212   ///
00213   /// This property corresponds to the GCC 'pure' attribute.
00214   ///
00215   bool onlyReadsMemory(Function *F) {
00216     /// FIXME: If the analysis returns more precise info, we can reduce it to
00217     /// this.
00218     ModRefBehavior MRB = getModRefBehavior(F, CallSite());
00219     return MRB == DoesNotAccessMemory || MRB == OnlyReadsMemory;
00220   }
00221 
00222 
00223   /// getModRefInfo - Return information about whether or not an instruction may
00224   /// read or write memory specified by the pointer operand.  An instruction
00225   /// that doesn't read or write memory may be trivially LICM'd for example.
00226 
00227   /// getModRefInfo (for call sites) - Return whether information about whether
00228   /// a particular call site modifies or reads the memory specified by the
00229   /// pointer.
00230   ///
00231   virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
00232 
00233   /// getModRefInfo - Return information about whether two call sites may refer
00234   /// to the same set of memory locations.  This function returns NoModRef if
00235   /// the two calls refer to disjoint memory locations, Ref if CS1 reads memory
00236   /// written by CS2, Mod if CS1 writes to memory read or written by CS2, or
00237   /// ModRef if CS1 might read or write memory accessed by CS2.
00238   ///
00239   virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2);
00240 
00241   /// hasNoModRefInfoForCalls - Return true if the analysis has no mod/ref
00242   /// information for pairs of function calls (other than "pure" and "const"
00243   /// functions).  This can be used by clients to avoid many pointless queries.
00244   /// Remember that if you override this and chain to another analysis, you must
00245   /// make sure that it doesn't have mod/ref info either.
00246   ///
00247   virtual bool hasNoModRefInfoForCalls() const;
00248 
00249   /// Convenience functions...
00250   ModRefResult getModRefInfo(LoadInst *L, Value *P, unsigned Size);
00251   ModRefResult getModRefInfo(StoreInst *S, Value *P, unsigned Size);
00252   ModRefResult getModRefInfo(CallInst *C, Value *P, unsigned Size) {
00253     return getModRefInfo(CallSite(C), P, Size);
00254   }
00255   ModRefResult getModRefInfo(InvokeInst *I, Value *P, unsigned Size) {
00256     return getModRefInfo(CallSite(I), P, Size);
00257   }
00258   ModRefResult getModRefInfo(VAArgInst* I, Value* P, unsigned Size) {
00259     return AliasAnalysis::Mod;
00260   }
00261   ModRefResult getModRefInfo(Instruction *I, Value *P, unsigned Size) {
00262     switch (I->getOpcode()) {
00263     case Instruction::VAArg:  return getModRefInfo((VAArgInst*)I, P, Size);
00264     case Instruction::Load:   return getModRefInfo((LoadInst*)I, P, Size);
00265     case Instruction::Store:  return getModRefInfo((StoreInst*)I, P, Size);
00266     case Instruction::Call:   return getModRefInfo((CallInst*)I, P, Size);
00267     case Instruction::Invoke: return getModRefInfo((InvokeInst*)I, P, Size);
00268     default:                  return NoModRef;
00269     }
00270   }
00271 
00272   //===--------------------------------------------------------------------===//
00273   /// Higher level methods for querying mod/ref information.
00274   ///
00275 
00276   /// canBasicBlockModify - Return true if it is possible for execution of the
00277   /// specified basic block to modify the value pointed to by Ptr.
00278   ///
00279   bool canBasicBlockModify(const BasicBlock &BB, const Value *P, unsigned Size);
00280 
00281   /// canInstructionRangeModify - Return true if it is possible for the
00282   /// execution of the specified instructions to modify the value pointed to by
00283   /// Ptr.  The instructions to consider are all of the instructions in the
00284   /// range of [I1,I2] INCLUSIVE.  I1 and I2 must be in the same basic block.
00285   ///
00286   bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2,
00287                                  const Value *Ptr, unsigned Size);
00288 
00289   //===--------------------------------------------------------------------===//
00290   /// Methods that clients should call when they transform the program to allow
00291   /// alias analyses to update their internal data structures.  Note that these
00292   /// methods may be called on any instruction, regardless of whether or not
00293   /// they have pointer-analysis implications.
00294   ///
00295 
00296   /// deleteValue - This method should be called whenever an LLVM Value is
00297   /// deleted from the program, for example when an instruction is found to be
00298   /// redundant and is eliminated.
00299   ///
00300   virtual void deleteValue(Value *V);
00301 
00302   /// copyValue - This method should be used whenever a preexisting value in the
00303   /// program is copied or cloned, introducing a new value.  Note that analysis
00304   /// implementations should tolerate clients that use this method to introduce
00305   /// the same value multiple times: if the analysis already knows about a
00306   /// value, it should ignore the request.
00307   ///
00308   virtual void copyValue(Value *From, Value *To);
00309 
00310   /// replaceWithNewValue - This method is the obvious combination of the two
00311   /// above, and it provided as a helper to simplify client code.
00312   ///
00313   void replaceWithNewValue(Value *Old, Value *New) {
00314     copyValue(Old, New);
00315     deleteValue(Old);
00316   }
00317 };
00318 
00319 // Because of the way .a files work, we must force the BasicAA implementation to
00320 // be pulled in if the AliasAnalysis header is included.  Otherwise we run
00321 // the risk of AliasAnalysis being used, but the default implementation not
00322 // being linked into the tool that uses it.
00323 //
00324 extern void BasicAAStub();
00325 static IncludeFile HDR_INCLUDE_BASICAA_CPP((void*)&BasicAAStub);
00326 
00327 } // End llvm namespace
00328 
00329 #endif