LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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 TargetData;
00041 
00042 class AliasAnalysis {
00043 protected:
00044   const TargetData *TD;
00045   AliasAnalysis *AA;       // Previous Alias Analysis to chain to.
00046 
00047   /// InitializeAliasAnalysis - Subclasses must call this method to initialize
00048   /// the AliasAnalysis interface before any other methods are called.  This is
00049   /// typically called by the run* methods of these subclasses.  This may be
00050   /// called multiple times.
00051   ///
00052   void InitializeAliasAnalysis(Pass *P);
00053   
00054   // getAnalysisUsage - All alias analysis implementations should invoke this
00055   // directly (using AliasAnalysis::getAnalysisUsage(AU)) to make sure that
00056   // TargetData is required by the pass.
00057   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
00058 
00059 public:
00060   AliasAnalysis() : TD(0), AA(0) {}
00061   virtual ~AliasAnalysis();  // We want to be subclassed
00062 
00063   /// getTargetData - Every alias analysis implementation depends on the size of
00064   /// data items in the current Target.  This provides a uniform way to handle
00065   /// it.
00066   ///
00067   const TargetData &getTargetData() const { return *TD; }
00068 
00069   //===--------------------------------------------------------------------===//
00070   /// Alias Queries...
00071   ///
00072 
00073   /// Alias analysis result - Either we know for sure that it does not alias, we
00074   /// know for sure it must alias, or we don't know anything: The two pointers
00075   /// _might_ alias.  This enum is designed so you can do things like:
00076   ///     if (AA.alias(P1, P2)) { ... }
00077   /// to check to see if two pointers might alias.
00078   ///
00079   enum AliasResult { NoAlias = 0, MayAlias = 1, MustAlias = 2 };
00080 
00081   /// alias - The main low level interface to the alias analysis implementation.
00082   /// Returns a Result indicating whether the two pointers are aliased to each
00083   /// other.  This is the interface that must be implemented by specific alias
00084   /// analysis implementations.
00085   ///
00086   virtual AliasResult alias(const Value *V1, unsigned V1Size,
00087                             const Value *V2, unsigned V2Size);
00088 
00089   /// getMustAliases - If there are any pointers known that must alias this
00090   /// pointer, return them now.  This allows alias-set based alias analyses to
00091   /// perform a form a value numbering (which is exposed by load-vn).  If an
00092   /// alias analysis supports this, it should ADD any must aliased pointers to
00093   /// the specified vector.
00094   ///
00095   virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals);
00096 
00097   /// pointsToConstantMemory - If the specified pointer is known to point into
00098   /// constant global memory, return true.  This allows disambiguation of store
00099   /// instructions from constant pointers.
00100   ///
00101   virtual bool pointsToConstantMemory(const Value *P);
00102 
00103   /// doesNotAccessMemory - If the specified function is known to never read or
00104   /// write memory, return true.  If the function only reads from known-constant
00105   /// memory, it is also legal to return true.  Functions that unwind the stack
00106   /// are not legal for this predicate.
00107   ///
00108   /// Many optimizations (such as CSE and LICM) can be performed on calls to it,
00109   /// without worrying about aliasing properties, and many functions have this
00110   /// property (e.g. 'sin' and 'cos').
00111   ///
00112   /// This property corresponds to the GCC 'const' attribute.
00113   ///
00114   virtual bool doesNotAccessMemory(Function *F);
00115 
00116   /// onlyReadsMemory - If the specified function is known to only read from
00117   /// non-volatile memory (or not access memory at all), return true.  Functions
00118   /// that unwind the stack are not legal for this predicate.
00119   ///
00120   /// This property allows many common optimizations to be performed in the
00121   /// absence of interfering store instructions, such as CSE of strlen calls.
00122   ///
00123   /// This property corresponds to the GCC 'pure' attribute.
00124   ///
00125   virtual bool onlyReadsMemory(Function *F);
00126 
00127 
00128   //===--------------------------------------------------------------------===//
00129   /// Simple mod/ref information...
00130   ///
00131 
00132   /// ModRefResult - Represent the result of a mod/ref query.  Mod and Ref are
00133   /// bits which may be or'd together.
00134   ///
00135   enum ModRefResult { NoModRef = 0, Ref = 1, Mod = 2, ModRef = 3 };
00136 
00137   /// getModRefInfo - Return information about whether or not an instruction may
00138   /// read or write memory specified by the pointer operand.  An instruction
00139   /// that doesn't read or write memory may be trivially LICM'd for example.
00140 
00141   /// getModRefInfo (for call sites) - Return whether information about whether
00142   /// a particular call site modifies or reads the memory specified by the
00143   /// pointer.
00144   ///
00145   virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
00146 
00147   /// getModRefInfo - Return information about whether two call sites may refer
00148   /// to the same set of memory locations.  This function returns NoModRef if
00149   /// the two calls refer to disjoint memory locations, Ref if CS1 reads memory
00150   /// written by CS2, Mod if CS1 writes to memory read or written by CS2, or
00151   /// ModRef if CS1 might read or write memory accessed by CS2.
00152   ///
00153   virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2);
00154 
00155   /// hasNoModRefInfoForCalls - Return true if the analysis has no mod/ref
00156   /// information for pairs of function calls (other than "pure" and "const"
00157   /// functions).  This can be used by clients to avoid many pointless queries.
00158   /// Remember that if you override this and chain to another analysis, you must
00159   /// make sure that it doesn't have mod/ref info either.
00160   ///
00161   virtual bool hasNoModRefInfoForCalls() const;
00162 
00163   /// Convenience functions...
00164   ModRefResult getModRefInfo(LoadInst *L, Value *P, unsigned Size);
00165   ModRefResult getModRefInfo(StoreInst *S, Value *P, unsigned Size);
00166   ModRefResult getModRefInfo(CallInst *C, Value *P, unsigned Size) {
00167     return getModRefInfo(CallSite(C), P, Size);
00168   }
00169   ModRefResult getModRefInfo(InvokeInst *I, Value *P, unsigned Size) {
00170     return getModRefInfo(CallSite(I), P, Size);
00171   }
00172   ModRefResult getModRefInfo(Instruction *I, Value *P, unsigned Size) {
00173     switch (I->getOpcode()) {
00174     case Instruction::Load:   return getModRefInfo((LoadInst*)I, P, Size);
00175     case Instruction::Store:  return getModRefInfo((StoreInst*)I, P, Size);
00176     case Instruction::Call:   return getModRefInfo((CallInst*)I, P, Size);
00177     case Instruction::Invoke: return getModRefInfo((InvokeInst*)I, P, Size);
00178     default:                  return NoModRef;
00179     }
00180   }
00181 
00182   //===--------------------------------------------------------------------===//
00183   /// Higher level methods for querying mod/ref information.
00184   ///
00185 
00186   /// canBasicBlockModify - Return true if it is possible for execution of the
00187   /// specified basic block to modify the value pointed to by Ptr.
00188   ///
00189   bool canBasicBlockModify(const BasicBlock &BB, const Value *P, unsigned Size);
00190 
00191   /// canInstructionRangeModify - Return true if it is possible for the
00192   /// execution of the specified instructions to modify the value pointed to by
00193   /// Ptr.  The instructions to consider are all of the instructions in the
00194   /// range of [I1,I2] INCLUSIVE.  I1 and I2 must be in the same basic block.
00195   ///
00196   bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2,
00197                                  const Value *Ptr, unsigned Size);
00198 
00199   //===--------------------------------------------------------------------===//
00200   /// Methods that clients should call when they transform the program to allow
00201   /// alias analyses to update their internal data structures.  Note that these
00202   /// methods may be called on any instruction, regardless of whether or not
00203   /// they have pointer-analysis implications.
00204   ///
00205 
00206   /// deleteValue - This method should be called whenever an LLVM Value is
00207   /// deleted from the program, for example when an instruction is found to be
00208   /// redundant and is eliminated.
00209   ///
00210   virtual void deleteValue(Value *V);
00211 
00212   /// copyValue - This method should be used whenever a preexisting value in the
00213   /// program is copied or cloned, introducing a new value.  Note that analysis
00214   /// implementations should tolerate clients that use this method to introduce
00215   /// the same value multiple times: if the analysis already knows about a
00216   /// value, it should ignore the request.
00217   ///
00218   virtual void copyValue(Value *From, Value *To);
00219 
00220   /// replaceWithNewValue - This method is the obvious combination of the two
00221   /// above, and it provided as a helper to simplify client code.
00222   ///
00223   void replaceWithNewValue(Value *Old, Value *New) {
00224     copyValue(Old, New);
00225     deleteValue(Old);
00226   }
00227 };
00228 
00229 // Because of the way .a files work, we must force the BasicAA implementation to
00230 // be pulled in if the AliasAnalysis header is included.  Otherwise we run
00231 // the risk of AliasAnalysis being used, but the default implementation not
00232 // being linked into the tool that uses it.
00233 //
00234 extern void BasicAAStub();
00235 static IncludeFile HDR_INCLUDE_BASICAA_CPP((void*)&BasicAAStub);
00236 
00237 } // End llvm namespace
00238 
00239 #endif