path: root/lib/Analysis/BasicAliasAnalysis.cpp

//===- BasicAliasAnalysis.cpp - Local Alias Analysis Impl -----------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the default implementation of the Alias Analysis interface
// that simply implements a few identities (two different globals cannot alias,
// etc), but otherwise does no analysis.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Passes.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
#include "llvm/ParameterAttributes.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Instructions.h"
#include "llvm/Intrinsics.h"
#include "llvm/Pass.h"
#include "llvm/Target/TargetData.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringMap.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/ManagedStatic.h"
#include <algorithm>
using namespace llvm;

namespace {
  /// NoAA - This class implements the -no-aa pass, which always returns "I
  /// don't know" for alias queries.  NoAA is unlike other alias analysis
  /// implementations, in that it does not chain to a previous analysis.  As
  /// such it doesn't follow many of the rules that other alias analyses must.
  ///
  struct VISIBILITY_HIDDEN NoAA : public ImmutablePass, public AliasAnalysis {
    static char ID; // Class identification, replacement for typeinfo
    NoAA() : ImmutablePass((intptr_t)&ID) {}
    explicit NoAA(intptr_t PID) : ImmutablePass(PID) { }

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.addRequired<TargetData>();
    }

    virtual void initializePass() {
      TD = &getAnalysis<TargetData>();
    }

    virtual AliasResult alias(const Value *V1, unsigned V1Size,
                              const Value *V2, unsigned V2Size) {
      return MayAlias;
    }

    virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
                                         std::vector<PointerAccessInfo> *Info) {
      return UnknownModRefBehavior;
    }

    virtual void getArgumentAccesses(Function *F, CallSite CS,
                                     std::vector<PointerAccessInfo> &Info) {
      assert(0 && "This method may not be called on this function!");
    }

    virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals) { }
    virtual bool pointsToConstantMemory(const Value *P) { return false; }
    virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size) {
      return ModRef;
    }
    virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
      return ModRef;
    }
    virtual bool hasNoModRefInfoForCalls() const { return true; }

    virtual void deleteValue(Value *V) {}
    virtual void copyValue(Value *From, Value *To) {}
  };

  // Register this pass...
  char NoAA::ID = 0;
  RegisterPass<NoAA>
  U("no-aa", "No Alias Analysis (always returns 'may' alias)");

  // Declare that we implement the AliasAnalysis interface
  RegisterAnalysisGroup<AliasAnalysis> V(U);
}  // End of anonymous namespace

ImmutablePass *llvm::createNoAAPass() { return new NoAA(); }

namespace {
  /// BasicAliasAnalysis - This is the default alias analysis implementation.
  /// Because it doesn't chain to a previous alias analysis (like -no-aa), it
  /// derives from the NoAA class.
  struct VISIBILITY_HIDDEN BasicAliasAnalysis : public NoAA {
    static char ID; // Class identification, replacement for typeinfo
    BasicAliasAnalysis() : NoAA((intptr_t)&ID) { }
    AliasResult alias(const Value *V1, unsigned V1Size,
                      const Value *V2, unsigned V2Size);

    ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
    ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
      return NoAA::getModRefInfo(CS1,CS2);
    }

    /// hasNoModRefInfoForCalls - We can provide mod/ref information against
    /// non-escaping allocations.
    virtual bool hasNoModRefInfoForCalls() const { return false; }

    /// pointsToConstantMemory - Chase pointers until we find a (constant
    /// global) or not.
    bool pointsToConstantMemory(const Value *P);

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

  private:
    // CheckGEPInstructions - Check two GEP instructions with known
    // must-aliasing base pointers.  This checks to see if the index expressions
    // preclude the pointers from aliasing...
    AliasResult
    CheckGEPInstructions(const Type* BasePtr1Ty,
                         Value **GEP1Ops, unsigned NumGEP1Ops, unsigned G1Size,