path: root/lib/Analysis/MemoryDependenceAnalysis.cpp

//===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation  --*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements an analysis that determines, for a given memory
// operation, what preceding memory operations it depends on.  It builds on 
// alias analysis information, and tries to provide a lazy, caching interface to
// a common kind of alias information query.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "memdep"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/Function.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Target/TargetData.h"
using namespace llvm;

STATISTIC(NumCacheNonLocal, "Number of cached non-local responses");
STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses");

char MemoryDependenceAnalysis::ID = 0;
  
// Register this pass...
static RegisterPass<MemoryDependenceAnalysis> X("memdep",
                                     "Memory Dependence Analysis", false, true);

/// getAnalysisUsage - Does not modify anything.  It uses Alias Analysis.
///
void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.setPreservesAll();
  AU.addRequiredTransitive<AliasAnalysis>();
  AU.addRequiredTransitive<TargetData>();
}

/// getCallSiteDependency - Private helper for finding the local dependencies
/// of a call site.
MemoryDependenceAnalysis::DepResultTy MemoryDependenceAnalysis::
getCallSiteDependency(CallSite C, BasicBlock::iterator ScanIt,
                      BasicBlock *BB) {
  AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
  TargetData &TD = getAnalysis<TargetData>();
  
  // Walk backwards through the block, looking for dependencies
  while (ScanIt != BB->begin()) {
    Instruction *Inst = --ScanIt;
    
    // If this inst is a memory op, get the pointer it accessed
    Value *Pointer = 0;
    uint64_t PointerSize = 0;
    if (StoreInst *S = dyn_cast<StoreInst>(Inst)) {
      Pointer = S->getPointerOperand();
      PointerSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
    } else if (VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
      Pointer = V->getOperand(0);
      PointerSize = TD.getTypeStoreSize(V->getType());
    } else if (FreeInst *F = dyn_cast<FreeInst>(Inst)) {
      Pointer = F->getPointerOperand();
      
      // FreeInsts erase the entire structure
      PointerSize = ~0UL;
    } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) {
      if (AA.getModRefBehavior(CallSite::get(Inst)) ==
            AliasAnalysis::DoesNotAccessMemory)
        continue;
      return DepResultTy(Inst, Normal);
    } else {
      // Non-memory instruction.
      continue;
    }
    
    if (AA.getModRefInfo(C, Pointer, PointerSize) != AliasAnalysis::NoModRef)
      return DepResultTy(Inst, Normal);
  }
  
  // No dependence found.
  return DepResultTy(0, NonLocal);
}

/// getDependency - Return the instruction on which a memory operation
/// depends.  The local parameter indicates if the query should only
/// evaluate dependencies within the same basic block.
MemoryDependenceAnalysis::DepResultTy MemoryDependenceAnalysis::
getDependencyFromInternal(Instruction *QueryInst, BasicBlock::iterator ScanIt, 
                          BasicBlock *BB) {
  AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
  TargetData &TD = getAnalysis<TargetData>();
  
  // Get the pointer value for which dependence will be determined
  Value *MemPtr = 0;
  uint64_t MemSize = 0;
  bool MemVolatile = false;
  
  if (StoreInst* S = dyn_cast<StoreInst>(QueryInst)) {
    MemPtr = S->getPointerOperand();
    MemSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
    MemVolatile = S->isVolatile();
  } else if (LoadInst* L = dyn_cast<LoadInst>(QueryInst)) {
    MemPtr = L->getPointerOperand();
    MemSize = TD.getTypeStoreSize(L->getType());
    MemVolatile = L->isVolatile();
  } else if (VAArgInst* V = dyn_cast<VAArgInst>(QueryInst)) {
    MemPtr = V->getOperand(0);
    MemSize = TD.getTypeStoreSize(V->getType());
  } else if (FreeInst* F = dyn_cast<FreeInst>(QueryInst)) {
    MemPtr = F->getPointerOperand();
    // FreeInsts erase the entire structure, not just a field.
    MemSize = ~0UL;
  } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst))
    return getCallSiteDependency(CallSite::get(QueryInst), ScanIt, BB);
  else  // Non-memory instructions depend on nothing.
    return DepResultTy(0, None);
  
  // Walk backwards through the basic block, looking for dependencies
  while (ScanIt != BB->begin()) {
    Instruction *Inst = --ScanIt;

    // If the access is volatile and this is a volatile load/store, return a
    // dependence.
    if (MemVolatile &&
        ((isa<LoadInst>(Inst) && cast<LoadInst>(Inst)->isVolatile()) ||
         (isa<StoreInst>(Inst) && cast<StoreInst>(Inst)->isVolatile())))
      return DepResultTy(Inst, Normal);

    // Values depend on loads if the pointers are must aliased.  This means that
    // a load depends on another must aliased load from the same value.
    if (LoadInst *L = dyn_cast<LoadInst>(Inst)) {
      Value *Pointer = L->getPointerOperand();
      uint64_t PointerSize = TD.getTypeStoreSize(L->getType());
      
      // If we found a pointer, check if it could be the same as our pointer
      AliasAnalysis::AliasResult R =
        AA.alias(Pointer, PointerSize, MemPtr, MemSize);
      
      if (R == AliasAnalysis::NoAlias)
        continue;
      
      // May-alias loads don't depend on each other without a dependence.
      if (isa<LoadInst>(QueryInst) && R == AliasAnalysis::MayAlias)
        continue;
      return DepResultTy(Inst, Normal);
    }

    // If this is an allocation, and if we know that the accessed pointer is to
    // the allocation, return None.  This means that there is no dependence and
    // the access can be optimized based on that.  For example, a load could
    // turn into undef.
    if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) {
      Value *AccessPtr = MemPtr->getUnderlyingObject();
      
      if (AccessPtr == AI ||
          AA.alias(AI, 1, AccessPtr, 1) == AliasAnalysis::MustAlias)
        return DepResultTy(0, None);
      continue;
    }
    
    // See if this instruction mod/ref's the pointer.
    AliasAnalysis::ModRefResult MRR = AA.getModRefInfo(Inst, MemPtr, MemSize);

    if (MRR == AliasAnalysis::NoModRef)
      continue;
    
    // Loads don't depend on read-only instructions.
    if (isa<LoadInst>(QueryInst) && MRR == AliasAnalysis::Ref)
      continue;
    
    // Otherwise, there is a dependence.
    return DepResultTy(Inst, Normal);
  }
  
  // If we found nothing, return the non-local flag.
  return DepResultTy(0, NonLocal);
}

/// getDependency - Return the instruction on which a memory operation
/// depends.
MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
  Instruction *ScanPos = QueryInst;
  
  // Check for a cached result
  DepResultTy &LocalCache = LocalDeps[QueryInst];
  
  // If the cached entry is non-dirty, just return it.  Note that this depends
  // on DepResultTy's default constructing to 'dirty'.
  if (LocalCache.getInt() != Dirty)
    return ConvToResult(LocalCache);
    
  // Otherwise, if we have a dirty entry, we know we can start the scan at that
  // instruction, which may save us some work.
  if (Instruction *Inst = LocalCache.getPointer())
    ScanPos = Inst;
  
  // Do the scan.
  LocalCache = get