AliasAnalysis.h

//===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the generic AliasAnalysis interface, which is used as the
// common interface used by all clients of alias analysis information, and
// implemented by all alias analysis implementations.  Mod/Ref information is
// also captured by this interface.
//
// Implementations of this interface must implement the various virtual methods,
// which automatically provides functionality for the entire suite of client
// APIs.
//
// This API represents memory as a (Pointer, Size) pair.  The Pointer component
// specifies the base memory address of the region, the Size specifies how large
// of an area is being queried.  If Size is 0, two pointers only alias if they
// are exactly equal.  If size is greater than zero, but small, the two pointers
// alias if the areas pointed to overlap.  If the size is very large (ie, ~0U),
// then the two pointers alias if they may be pointing to components of the same
// memory object.  Pointers that point to two completely different objects in
// memory never alias, regardless of the value of the Size component.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_ALIAS_ANALYSIS_H
#define LLVM_ANALYSIS_ALIAS_ANALYSIS_H

#include "llvm/Support/CallSite.h"
#include "llvm/System/IncludeFile.h"
#include <vector>

namespace llvm {

class LoadInst;
class StoreInst;
class VAArgInst;
class TargetData;
class Pass;
class AnalysisUsage;

class AliasAnalysis {
protected:
  const TargetData *TD;
  AliasAnalysis *AA;       // Previous Alias Analysis to chain to.

  void InitializeAliasAnalysis(Pass *P);

  virtual void getAnalysisUsage(AnalysisUsage &AU) const;

public:
  static char ID; // Class identification, replacement for typeinfo
  AliasAnalysis() : TD(0), AA(0) {}
  virtual ~AliasAnalysis();  // We want to be subclassed

  const TargetData *getTargetData() const { return TD; }

  unsigned getTypeStoreSize(const Type *Ty);

  //===--------------------------------------------------------------------===//

  enum AliasResult { NoAlias = 0, MayAlias = 1, MustAlias = 2 };

  virtual AliasResult alias(const Value *V1, unsigned V1Size,
                            const Value *V2, unsigned V2Size);

  bool isNoAlias(const Value *V1, unsigned V1Size,
                 const Value *V2, unsigned V2Size) {
    return alias(V1, V1Size, V2, V2Size) == NoAlias;
  }

  virtual bool pointsToConstantMemory(const Value *P);

  //===--------------------------------------------------------------------===//

  enum ModRefResult { NoModRef = 0, Ref = 1, Mod = 2, ModRef = 3 };


  enum ModRefBehavior {
    // DoesNotAccessMemory - This function does not perform any non-local loads
    // or stores to memory.
    //
    // This property corresponds to the GCC 'const' attribute.
    DoesNotAccessMemory,

    // AccessesArguments - This function accesses function arguments in well
    // known (possibly volatile) ways, but does not access any other memory.
    //
    // Clients may use the Info parameter of getModRefBehavior to get specific
    // information about how pointer arguments are used.
    AccessesArguments,

    // AccessesArgumentsAndGlobals - This function has accesses function
    // arguments and global variables well known (possibly volatile) ways, but
    // does not access any other memory.
    //
    // Clients may use the Info parameter of getModRefBehavior to get specific
    // information about how pointer arguments are used.
    AccessesArgumentsAndGlobals,

    // OnlyReadsMemory - This function does not perform any non-local stores or
    // volatile loads, but may read from any memory location.
    //
    // This property corresponds to the GCC 'pure' attribute.
    OnlyReadsMemory,

    // UnknownModRefBehavior - This indicates that the function could not be
    // classified into one of the behaviors above.
    UnknownModRefBehavior
  };

  struct PointerAccessInfo {
    Value *V;

    ModRefResult ModRefInfo;

    enum AccessType {
      ScalarAccess,

      ArrayAccess,


      CallsThrough
    };
  };

  virtual ModRefBehavior getModRefBehavior(CallSite CS,
                                   std::vector<PointerAccessInfo> *Info = 0);

  virtual ModRefBehavior getModRefBehavior(Function *F,
                                   std::vector<PointerAccessInfo> *Info = 0);

  static ModRefBehavior getModRefBehavior(unsigned iid);

  bool doesNotAccessMemory(CallSite CS) {
    return getModRefBehavior(CS) == DoesNotAccessMemory;
  }

  bool doesNotAccessMemory(Function *F) {
    return getModRefBehavior(F) == DoesNotAccessMemory;
  }

  bool onlyReadsMemory(CallSite CS) {
    ModRefBehavior MRB = getModRefBehavior(CS);
    return MRB == DoesNotAccessMemory || MRB == OnlyReadsMemory;
  }

  bool onlyReadsMemory(Function *F) {
    ModRefBehavior MRB = getModRefBehavior(F);
    return MRB == DoesNotAccessMemory || MRB == OnlyReadsMemory;
  }



  virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);

  virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2);

public:
  ModRefResult getModRefInfo(LoadInst *L, Value *P, unsigned Size);
  ModRefResult getModRefInfo(StoreInst *S, Value *P, unsigned Size);
  ModRefResult getModRefInfo(CallInst *C, Value *P, unsigned Size) {
    return getModRefInfo(CallSite(C), P, Size);
  }
  ModRefResult getModRefInfo(InvokeInst *I, Value *P, unsigned Size) {
    return getModRefInfo(CallSite(I), P, Size);
  }
  ModRefResult getModRefInfo(VAArgInst* I, Value* P, unsigned Size) {
    return AliasAnalysis::ModRef;
  }
  ModRefResult getModRefInfo(Instruction *I, Value *P, unsigned Size) {
    switch (I->getOpcode()) {
    case Instruction::VAArg:  return getModRefInfo((VAArgInst*)I, P, Size);
    case Instruction::Load:   return getModRefInfo((LoadInst*)I, P, Size);
    case Instruction::Store:  return getModRefInfo((StoreInst*)I, P, Size);
    case Instruction::Call:   return getModRefInfo((CallInst*)I, P, Size);
    case Instruction::Invoke: return getModRefInfo((InvokeInst*)I, P, Size);
    default:                  return NoModRef;
    }
  }

  //===--------------------------------------------------------------------===//

  bool canBasicBlockModify(const BasicBlock &BB, const Value *P, unsigned Size);

  bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2,
                                 const Value *Ptr, unsigned Size);

  //===--------------------------------------------------------------------===//

  virtual void deleteValue(Value *V);

  virtual void copyValue(Value *From, Value *To);

  void replaceWithNewValue(Value *Old, Value *New) {
    copyValue(Old, New);
    deleteValue(Old);
  }
};

bool isNoAliasCall(const Value *V);

bool isIdentifiedObject(const Value *V);

} // End llvm namespace

// Because of the way .a files work, we must force the BasicAA implementation to
// be pulled in if the AliasAnalysis header is included.  Otherwise we run
// the risk of AliasAnalysis being used, but the default implementation not
// being linked into the tool that uses it.
FORCE_DEFINING_FILE_TO_BE_LINKED(AliasAnalysis)
FORCE_DEFINING_FILE_TO_BE_LINKED(BasicAliasAnalysis)

#endif

---