<commit_before>//===- 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/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Function.h"
#include "llvm/LLVMContext.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/PHITransAddr.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/PredIteratorCache.h"
#include "llvm/Support/Debug.h"
using namespace llvm;

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

STATISTIC(NumCacheNonLocalPtr,
          "Number of fully cached non-local ptr responses");
STATISTIC(NumCacheDirtyNonLocalPtr,
          "Number of cached, but dirty, non-local ptr responses");
STATISTIC(NumUncacheNonLocalPtr,
          "Number of uncached non-local ptr responses");
STATISTIC(NumCacheCompleteNonLocalPtr,
          "Number of block queries that were completely cached");

char MemoryDependenceAnalysis::ID = 0;
  
// Register this pass...
INITIALIZE_PASS_BEGIN(MemoryDependenceAnalysis, "memdep",
                "Memory Dependence Analysis", false, true)
INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
INITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep",
                      "Memory Dependence Analysis", false, true)

MemoryDependenceAnalysis::MemoryDependenceAnalysis()
: FunctionPass(ID), PredCache(0) {
  initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry());
}
MemoryDependenceAnalysis::~MemoryDependenceAnalysis() {
}

/// Clean up memory in between runs
void MemoryDependenceAnalysis::releaseMemory() {
  LocalDeps.clear();
  NonLocalDeps.clear();
  NonLocalPointerDeps.clear();
  ReverseLocalDeps.clear();
  ReverseNonLocalDeps.clear();
  ReverseNonLocalPtrDeps.clear();
  PredCache->clear();
}



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

bool MemoryDependenceAnalysis::runOnFunction(Function &) {
  AA = &getAnalysis<AliasAnalysis>();
  if (PredCache == 0)
    PredCache.reset(new PredIteratorCache());
  return false;
}

/// RemoveFromReverseMap - This is a helper function that removes Val from
/// 'Inst's set in ReverseMap.  If the set becomes empty, remove Inst's entry.
template <typename KeyTy>
static void RemoveFromReverseMap(DenseMap<Instruction*, 
                                 SmallPtrSet<KeyTy, 4> > &ReverseMap,
                                 Instruction *Inst, KeyTy Val) {
  typename DenseMap<Instruction*, SmallPtrSet<KeyTy, 4> >::iterator
  InstIt = ReverseMap.find(Inst);
  assert(InstIt != ReverseMap.end() && "Reverse map out of sync?");
  bool Found = InstIt->second.erase(Val);
  assert(Found && "Invalid reverse map!"); Found=Found;
  if (InstIt->second.empty())
    ReverseMap.erase(InstIt);
}


/// getCallSiteDependencyFrom - Private helper for finding the local
/// dependencies of a call site.
MemDepResult MemoryDependenceAnalysis::
getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall,
                          BasicBlock::iterator ScanIt, BasicBlock *BB) {
  // 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
    AliasAnalysis::Location Loc;
    if (StoreInst *S = dyn_cast<StoreInst>(Inst)) {
      Loc = AliasAnalysis::Location(S->getPointerOperand(),
                                    AA->getTypeStoreSize(S->getValueOperand()
                                                           ->getType()),
                                    S->getMetadata(LLVMContext::MD_tbaa));
    } else if (VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
      Loc = AliasAnalysis::Location(V->getPointerOperand(),
                                    AA->getTypeStoreSize(V->getType()),
                                    V->getMetadata(LLVMContext::MD_tbaa));
    } else if (const CallInst *CI = isFreeCall(Inst)) {
      // calls to free() erase the entire structure
      Loc = AliasAnalysis::Location(CI->getArgOperand(0));
    } else if (CallSite InstCS = cast<Value>(Inst)) {
      // Debug intrinsics don't cause dependences.
      if (isa<DbgInfoIntrinsic>(Inst)) continue;
      // If these two calls do not interfere, look past it.
      switch (AA->getModRefInfo(CS, InstCS)) {
      case AliasAnalysis::NoModRef:
        // If the two calls are the same, return InstCS as a Def, so that
        // CS can be found redundant and eliminated.
        if (isReadOnlyCall && InstCS.onlyReadsMemory() &&
            CS.getInstruction()->isIdenticalToWhenDefined(Inst))
          return MemDepResult::getDef(Inst);

        // Otherwise if the two calls don't interact (e.g. InstCS is readnone)
        // keep scanning.
        continue;
      default:
        return MemDepResult::getClobber(Inst);
      }
    } else {
      // Non-memory instruction.
      continue;
    }
    
    if (AA->getModRefInfo(CS, Loc) != AliasAnalysis::NoModRef)
      return MemDepResult::getClobber(Inst);
  }
  
  // No dependence found.  If this is the entry block of the function, it is a
  // clobber, otherwise it is non-local.
  if (BB != &BB->getParent()->getEntryBlock())
    return MemDepResult::getNonLocal();
  return MemDepResult::getClobber(ScanIt);
}

/// getPointerDependencyFrom - Return the instruction on which a memory
/// location depends.  If isLoad is true, this routine ignores may-aliases with
/// read-only operations.  If isLoad is false, this routine ignores may-aliases
/// with reads from read-only locations.
MemDepResult MemoryDependenceAnalysis::
getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, 
                         BasicBlock::iterator ScanIt, BasicBlock *BB) {

  Value *InvariantTag = 0;

  // Walk backwards through the basic block, looking for dependencies.
  while (ScanIt != BB->begin()) {
    Instruction *Inst = --ScanIt;

    // If we're in an invariant region, no dependencies can be found before
    // we pass an invariant-begin marker.
    if (InvariantTag == Inst) {
      InvariantTag = 0;
      continue;
    }
    
    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
      // Debug intrinsics don't (and can't) cause dependences.
      if (isa<DbgInfoIntrinsic>(II)) continue;
      
      // If we pass an invariant-end marker, then we've just entered an
      // invariant region and can start ignoring dependencies.
      if (II->getIntrinsicID() == Intrinsic::invariant_end) {
        // FIXME: This only considers queries directly on the invariant-tagged
        // pointer, not on query pointers that are indexed off of them.  It'd
        // be nice to handle that at some point.
        AliasAnalysis::AliasResult R =
          AA->alias(AliasAnalysis::Location(II->getArgOperand(2)), MemLoc);
        if (R == AliasAnalysis::MustAlias)
          InvariantTag = II->getArgOperand(0);

        continue;
      }

      // If we reach a lifetime begin or end marker, then the query ends here
      // because the value is undefined.
      if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
        // FIXME: This only considers queries directly on the invariant-tagged
        // pointer, not on query pointers that are indexed off of them.  It'd
        // be nice to handle that at some point.
        AliasAnalysis::AliasResult R =
          AA->alias(AliasAnalysis::Location(II->getArgOperand(1)), MemLoc);
        if (R == AliasAnalysis::MustAlias)
          return MemDepResult::getDef(II);
        continue;
      }
    }

    // If we're querying on a load and we're in an invariant region, we're done
    // at this point. Nothing a load depends on can live in an invariant region.
    //
    // FIXME: this will prevent us from returning load/load must-aliases, so GVN
    // won't remove redundant loads.
    if (isLoad && InvariantTag) continue;

    // 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 *LI = dyn_cast<LoadInst>(Inst)) {
      Value *Pointer = LI->getPointerOperand();
      uint64_t PointerSize = AA->getTypeStoreSize(LI->getType());
      MDNode *TBAATag = LI->getMetadata(LLVMContext::MD_tbaa);
      AliasAnalysis::Location LoadLoc(Pointer, PointerSize, TBAATag);
      
      // If we found a pointer, check if it could be the same as our pointer.
      AliasAnalysis::AliasResult R = AA->alias(LoadLoc, MemLoc);
      if (R == AliasAnalysis::NoAlias)
        continue;
      
      // May-alias loads don't depend on each other without a dependence.
      if (isLoad && R == AliasAnalysis::MayAlias)
        continue;

      // Stores don't alias loads from read-only memory.
      if (!isLoad && AA->pointsToConstantMemory(LoadLoc))
        continue;

      // Stores depend on may and must aliased loads, loads depend on must-alias
      // loads.
      return MemDepResult::getDef(Inst);
    }
    
    if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
      // There can't be stores to the value we care about inside an 
      // invariant region.
      if (InvariantTag) continue;
      
      // If alias analysis can tell that this store is guaranteed to not modify
      // the query pointer, ignore it.  Use getModRefInfo to handle cases where
      // the query pointer points to constant memory etc.
      if (AA->getModRefInfo(SI, MemLoc) == AliasAnalysis::NoModRef)
        continue;

      // Ok, this store might clobber the query pointer.  Check to see if it is
      // a must alias: in this case, we want to return this as a def.
      Value *Pointer = SI->getPointerOperand();
      uint64_t PointerSize = AA->getTypeStoreSize(SI->getOperand(0)->getType());
      MDNode *TBAATag = SI->getMetadata(LLVMContext::MD_tbaa);
      
      // If we found a pointer, check if it could be the same as our pointer.
      AliasAnalysis::AliasResult R =
        AA->alias(AliasAnalysis::Location(Pointer, PointerSize, TBAATag),
                  MemLoc);
      
      if (R == AliasAnalysis::NoAlias)
        continue;
      if (R == AliasAnalysis::MayAlias)
        return MemDepResult::getClobber(Inst);
      return MemDepResult::getDef(Inst);
    }

    // If this is an allocation, and if we know that the accessed pointer is to
    // the allocation, return Def.  This means that there is no dependence and
    // the access can be optimized based on that.  For example, a load could
    // turn into undef.
    // Note: Only determine this to be a malloc if Inst is the malloc call, not
    // a subsequent bitcast of the malloc call result.  There can be stores to
    // the malloced memory between the malloc call and its bitcast uses, and we
    // need to continue scanning until the malloc call.
    if (isa<AllocaInst>(Inst) ||
        (isa<CallInst>(Inst) && extractMallocCall(Inst))) {
      const Value *AccessPtr = MemLoc.Ptr->getUnderlyingObject();
      
      if (AccessPtr == Inst ||
          AA->alias(Inst, 1, AccessPtr, 1) == AliasAnalysis::MustAlias)
        return MemDepResult::getDef(Inst);
      continue;
    }

    // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
    switch (AA->getModRefInfo(Inst, MemLoc)) {
    case AliasAnalysis::NoModRef:
      // If the call has no effect on the queried pointer, just ignore it.
      continue;
    case AliasAnalysis::Mod:
      // If we're in an invariant region, we can ignore calls that ONLY
      // modify the pointer.
      if (InvariantTag) continue;
      return MemDepResult::getClobber(Inst);
    case AliasAnalysis::Ref:
      // If the call is known to never store to the pointer, and if this is a
      // load query, we can safely ignore it (scan past it).
      if (isLoad)
        continue;
    default:
      // Otherwise, there is a potential dependence.  Return a clobber.
      return MemDepResult::getClobber(Inst);
    }
  }
  
  // No dependence found.  If this is the entry block of the function, it is a
  // clobber, otherwise it is non-local.
  if (BB != &BB->getParent()->getEntryBlock())
    return MemDepResult::getNonLocal();
  return MemDepResult::getClobber(ScanIt);
}

/// getDependency - Return the instruction on which a memory operation
/// depends.
MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
  Instruction *ScanPos = QueryInst;
  
  // Check for a cached result
  MemDepResult &LocalCache = LocalDeps[QueryInst];
  
  // If the cached entry is non-dirty, just return it.  Note that this depends
  // on MemDepResult's default constructing to 'dirty'.
  if (!LocalCache.isDirty())
    return 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.getInst()) {
    ScanPos = Inst;
   
    RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst);
  }
  
  BasicBlock *QueryParent = QueryInst->getParent();
  
  AliasAnalysis::Location MemLoc;
  
  // Do the scan.
  if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
    // No dependence found.  If this is the entry block of the function, it is a
    // clobber, otherwise it is non-local.
    if (QueryParent != &QueryParent->getParent()->getEntryBlock())
      LocalCache = MemDepResult::getNonLocal();
    else
      LocalCache = MemDepResult::getClobber(QueryInst);
  } else if (StoreInst *SI = dyn_cast<StoreInst>(QueryInst)) {
    // If this is a volatile store, don't mess around with it.  Just return the
    // previous instruction as a clobber.
    if (SI->isVolatile())
      LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
    else
      MemLoc = AliasAnalysis::Location(SI->getPointerOperand(),
                                       AA->getTypeStoreSize(SI->getOperand(0)
                                                              ->getType()),
                                       SI->getMetadata(LLVMContext::MD_tbaa));
  } else if (LoadInst *LI = dyn_cast<LoadInst>(QueryInst)) {
    // If this is a volatile load, don't mess around with it.  Just return the
    // previous instruction as a clobber.
    if (LI->isVolatile())
      LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
    else
      MemLoc = AliasAnalysis::Location(LI->getPointerOperand(),
                                       AA->getTypeStoreSize(LI->getType()),
                                       LI->getMetadata(LLVMContext::MD_tbaa));
  } else if (const CallInst *CI = isFreeCall(QueryInst)) {
    // calls to free() erase the entire structure, not just a field.
    MemLoc = AliasAnalysis::Location(CI->getArgOperand(0));
  } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) {
    int IntrinsicID = 0;  // Intrinsic IDs start at 1.
    IntrinsicInst *II = dyn_cast<IntrinsicInst>(QueryInst);
    if (II)
      IntrinsicID = II->getIntrinsicID();

    switch (IntrinsicID) {
    case Intrinsic::lifetime_start:
    case Intrinsic::lifetime_end:
    case Intrinsic::invariant_start:
      MemLoc = AliasAnalysis::Location(II->getArgOperand(1),
                                       cast<ConstantInt>(II->getArgOperand(0))
                                         ->getZExtValue(),
                                       II->getMetadata(LLVMContext::MD_tbaa));
      break;
    case Intrinsic::invariant_end:
      MemLoc = AliasAnalysis::Location(II->getArgOperand(2),
                                       cast<ConstantInt>(II->getArgOperand(1))
                                         ->getZExtValue(),
                                       II->getMetadata(LLVMContext::MD_tbaa));
      break;
    default:
      CallSite QueryCS(QueryInst);
      bool isReadOnly = AA->onlyReadsMemory(QueryCS);
      LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos,
                                             QueryParent);
      break;
    }
  } else {
    // Non-memory instruction.
    LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
  }
  
  // If we need to do a pointer scan, make it happen.
  if (MemLoc.Ptr) {
    bool isLoad = !QueryInst->mayWriteToMemory();
    if (IntrinsicInst *II = dyn_cast<MemoryUseIntrinsic>(QueryInst)) {
      isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_end;
    }
    LocalCache = getPointerDependencyFrom(MemLoc, isLoad, ScanPos,
                                          QueryParent);<commit_msg>Factor out the code for computing an AliasAnalysis::Location for a given instruction into a helper function.<commit_after>//===- 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/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Function.h"
#include "llvm/LLVMContext.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/PHITransAddr.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/PredIteratorCache.h"
#include "llvm/Support/Debug.h"
using namespace llvm;

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

STATISTIC(NumCacheNonLocalPtr,
          "Number of fully cached non-local ptr responses");
STATISTIC(NumCacheDirtyNonLocalPtr,
          "Number of cached, but dirty, non-local ptr responses");
STATISTIC(NumUncacheNonLocalPtr,
          "Number of uncached non-local ptr responses");
STATISTIC(NumCacheCompleteNonLocalPtr,
          "Number of block queries that were completely cached");

char MemoryDependenceAnalysis::ID = 0;
  
// Register this pass...
INITIALIZE_PASS_BEGIN(MemoryDependenceAnalysis, "memdep",
                "Memory Dependence Analysis", false, true)
INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
INITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep",
                      "Memory Dependence Analysis", false, true)

MemoryDependenceAnalysis::MemoryDependenceAnalysis()
: FunctionPass(ID), PredCache(0) {
  initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry());
}
MemoryDependenceAnalysis::~MemoryDependenceAnalysis() {
}

/// Clean up memory in between runs
void MemoryDependenceAnalysis::releaseMemory() {
  LocalDeps.clear();
  NonLocalDeps.clear();
  NonLocalPointerDeps.clear();
  ReverseLocalDeps.clear();
  ReverseNonLocalDeps.clear();
  ReverseNonLocalPtrDeps.clear();
  PredCache->clear();
}



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

bool MemoryDependenceAnalysis::runOnFunction(Function &) {
  AA = &getAnalysis<AliasAnalysis>();
  if (PredCache == 0)
    PredCache.reset(new PredIteratorCache());
  return false;
}

/// RemoveFromReverseMap - This is a helper function that removes Val from
/// 'Inst's set in ReverseMap.  If the set becomes empty, remove Inst's entry.
template <typename KeyTy>
static void RemoveFromReverseMap(DenseMap<Instruction*, 
                                 SmallPtrSet<KeyTy, 4> > &ReverseMap,
                                 Instruction *Inst, KeyTy Val) {
  typename DenseMap<Instruction*, SmallPtrSet<KeyTy, 4> >::iterator
  InstIt = ReverseMap.find(Inst);
  assert(InstIt != ReverseMap.end() && "Reverse map out of sync?");
  bool Found = InstIt->second.erase(Val);
  assert(Found && "Invalid reverse map!"); Found=Found;
  if (InstIt->second.empty())
    ReverseMap.erase(InstIt);
}

/// GetLocation - If the given instruction references a specific memory
/// location, fill in Loc with the details, otherwise set Loc.Ptr to null.
/// Return a ModRefInfo value describing the general behavior of the
/// instruction.
static
AliasAnalysis::ModRefResult GetLocation(const Instruction *Inst,
                                        AliasAnalysis::Location &Loc,
                                        AliasAnalysis *AA) {
  if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
    if (LI->isVolatile()) {
      Loc = AliasAnalysis::Location();
      return AliasAnalysis::ModRef;
    }
    Loc = AliasAnalysis::Location(LI->getPointerOperand(),
                                  AA->getTypeStoreSize(LI->getType()),
                                  LI->getMetadata(LLVMContext::MD_tbaa));
    return AliasAnalysis::Ref;
  }

  if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
    if (SI->isVolatile()) {
      Loc = AliasAnalysis::Location();
      return AliasAnalysis::ModRef;
    }
    Loc = AliasAnalysis::Location(SI->getPointerOperand(),
                                  AA->getTypeStoreSize(SI->getValueOperand()
                                                         ->getType()),
                                  SI->getMetadata(LLVMContext::MD_tbaa));
    return AliasAnalysis::Mod;
  }

  if (const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
    Loc = AliasAnalysis::Location(V->getPointerOperand(),
                                  AA->getTypeStoreSize(V->getType()),
                                  V->getMetadata(LLVMContext::MD_tbaa));
    return AliasAnalysis::ModRef;
  }

  if (const CallInst *CI = isFreeCall(Inst)) {
    // calls to free() deallocate the entire structure
    Loc = AliasAnalysis::Location(CI->getArgOperand(0));
    return AliasAnalysis::Mod;
  }

  if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
    switch (II->getIntrinsicID()) {
    case Intrinsic::lifetime_start:
    case Intrinsic::lifetime_end:
    case Intrinsic::invariant_start:
      Loc = AliasAnalysis::Location(II->getArgOperand(1),
                                    cast<ConstantInt>(II->getArgOperand(0))
                                      ->getZExtValue(),
                                    II->getMetadata(LLVMContext::MD_tbaa));
      // These intrinsics don't really modify the memory, but returning Mod
      // will allow them to be handled conservatively.
      return AliasAnalysis::Mod;
    case Intrinsic::invariant_end:
      Loc = AliasAnalysis::Location(II->getArgOperand(2),
                                    cast<ConstantInt>(II->getArgOperand(1))
                                      ->getZExtValue(),
                                    II->getMetadata(LLVMContext::MD_tbaa));
      // These intrinsics don't really modify the memory, but returning Mod
      // will allow them to be handled conservatively.
      return AliasAnalysis::Mod;
    default:
      break;
    }

  // Otherwise, just do the coarse-grained thing that always works.
  if (Inst->mayWriteToMemory())
    return AliasAnalysis::ModRef;
  if (Inst->mayReadFromMemory())
    return AliasAnalysis::Ref;
  return AliasAnalysis::NoModRef;
}

/// getCallSiteDependencyFrom - Private helper for finding the local
/// dependencies of a call site.
MemDepResult MemoryDependenceAnalysis::
getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall,
                          BasicBlock::iterator ScanIt, BasicBlock *BB) {
  // 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
    AliasAnalysis::Location Loc;
    AliasAnalysis::ModRefResult MR = GetLocation(Inst, Loc, AA);
    if (Loc.Ptr) {
      // A simple instruction.
      if (AA->getModRefInfo(CS, Loc) != AliasAnalysis::NoModRef)
        return MemDepResult::getClobber(Inst);
      continue;
    }

    if (CallSite InstCS = cast<Value>(Inst)) {
      // Debug intrinsics don't cause dependences.
      if (isa<DbgInfoIntrinsic>(Inst)) continue;
      // If these two calls do not interfere, look past it.
      switch (AA->getModRefInfo(CS, InstCS)) {
      case AliasAnalysis::NoModRef:
        // If the two calls are the same, return InstCS as a Def, so that
        // CS can be found redundant and eliminated.
        if (isReadOnlyCall && !(MR & AliasAnalysis::Mod) &&
            CS.getInstruction()->isIdenticalToWhenDefined(Inst))
          return MemDepResult::getDef(Inst);

        // Otherwise if the two calls don't interact (e.g. InstCS is readnone)
        // keep scanning.
        break;
      default:
        return MemDepResult::getClobber(Inst);
      }
    }
  }
  
  // No dependence found.  If this is the entry block of the function, it is a
  // clobber, otherwise it is non-local.
  if (BB != &BB->getParent()->getEntryBlock())
    return MemDepResult::getNonLocal();
  return MemDepResult::getClobber(ScanIt);
}

/// getPointerDependencyFrom - Return the instruction on which a memory
/// location depends.  If isLoad is true, this routine ignores may-aliases with
/// read-only operations.  If isLoad is false, this routine ignores may-aliases
/// with reads from read-only locations.
MemDepResult MemoryDependenceAnalysis::
getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, 
                         BasicBlock::iterator ScanIt, BasicBlock *BB) {

  Value *InvariantTag = 0;

  // Walk backwards through the basic block, looking for dependencies.
  while (ScanIt != BB->begin()) {
    Instruction *Inst = --ScanIt;

    // If we're in an invariant region, no dependencies can be found before
    // we pass an invariant-begin marker.
    if (InvariantTag == Inst) {
      InvariantTag = 0;
      continue;
    }
    
    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
      // Debug intrinsics don't (and can't) cause dependences.
      if (isa<DbgInfoIntrinsic>(II)) continue;
      
      // If we pass an invariant-end marker, then we've just entered an
      // invariant region and can start ignoring dependencies.
      if (II->getIntrinsicID() == Intrinsic::invariant_end) {
        // FIXME: This only considers queries directly on the invariant-tagged
        // pointer, not on query pointers that are indexed off of them.  It'd
        // be nice to handle that at some point.
        AliasAnalysis::AliasResult R =
          AA->alias(AliasAnalysis::Location(II->getArgOperand(2)), MemLoc);
        if (R == AliasAnalysis::MustAlias)
          InvariantTag = II->getArgOperand(0);

        continue;
      }

      // If we reach a lifetime begin or end marker, then the query ends here
      // because the value is undefined.
      if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
        // FIXME: This only considers queries directly on the invariant-tagged
        // pointer, not on query pointers that are indexed off of them.  It'd
        // be nice to handle that at some point.
        AliasAnalysis::AliasResult R =
          AA->alias(AliasAnalysis::Location(II->getArgOperand(1)), MemLoc);
        if (R == AliasAnalysis::MustAlias)
          return MemDepResult::getDef(II);
        continue;
      }
    }

    // If we're querying on a load and we're in an invariant region, we're done
    // at this point. Nothing a load depends on can live in an invariant region.
    //
    // FIXME: this will prevent us from returning load/load must-aliases, so GVN
    // won't remove redundant loads.
    if (isLoad && InvariantTag) continue;

    // 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 *LI = dyn_cast<LoadInst>(Inst)) {
      Value *Pointer = LI->getPointerOperand();
      uint64_t PointerSize = AA->getTypeStoreSize(LI->getType());
      MDNode *TBAATag = LI->getMetadata(LLVMContext::MD_tbaa);
      AliasAnalysis::Location LoadLoc(Pointer, PointerSize, TBAATag);
      
      // If we found a pointer, check if it could be the same as our pointer.
      AliasAnalysis::AliasResult R = AA->alias(LoadLoc, MemLoc);
      if (R == AliasAnalysis::NoAlias)
        continue;
      
      // May-alias loads don't depend on each other without a dependence.
      if (isLoad && R == AliasAnalysis::MayAlias)
        continue;

      // Stores don't alias loads from read-only memory.
      if (!isLoad && AA->pointsToConstantMemory(LoadLoc))
        continue;

      // Stores depend on may and must aliased loads, loads depend on must-alias
      // loads.
      return MemDepResult::getDef(Inst);
    }
    
    if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
      // There can't be stores to the value we care about inside an 
      // invariant region.
      if (InvariantTag) continue;
      
      // If alias analysis can tell that this store is guaranteed to not modify
      // the query pointer, ignore it.  Use getModRefInfo to handle cases where
      // the query pointer points to constant memory etc.
      if (AA->getModRefInfo(SI, MemLoc) == AliasAnalysis::NoModRef)
        continue;

      // Ok, this store might clobber the query pointer.  Check to see if it is
      // a must alias: in this case, we want to return this as a def.
      Value *Pointer = SI->getPointerOperand();
      uint64_t PointerSize = AA->getTypeStoreSize(SI->getOperand(0)->getType());
      MDNode *TBAATag = SI->getMetadata(LLVMContext::MD_tbaa);
      
      // If we found a pointer, check if it could be the same as our pointer.
      AliasAnalysis::AliasResult R =
        AA->alias(AliasAnalysis::Location(Pointer, PointerSize, TBAATag),
                  MemLoc);
      
      if (R == AliasAnalysis::NoAlias)
        continue;
      if (R == AliasAnalysis::MayAlias)
        return MemDepResult::getClobber(Inst);
      return MemDepResult::getDef(Inst);
    }

    // If this is an allocation, and if we know that the accessed pointer is to
    // the allocation, return Def.  This means that there is no dependence and
    // the access can be optimized based on that.  For example, a load could
    // turn into undef.
    // Note: Only determine this to be a malloc if Inst is the malloc call, not
    // a subsequent bitcast of the malloc call result.  There can be stores to
    // the malloced memory between the malloc call and its bitcast uses, and we
    // need to continue scanning until the malloc call.
    if (isa<AllocaInst>(Inst) ||
        (isa<CallInst>(Inst) && extractMallocCall(Inst))) {
      const Value *AccessPtr = MemLoc.Ptr->getUnderlyingObject();
      
      if (AccessPtr == Inst ||
          AA->alias(Inst, 1, AccessPtr, 1) == AliasAnalysis::MustAlias)
        return MemDepResult::getDef(Inst);
      continue;
    }

    // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
    switch (AA->getModRefInfo(Inst, MemLoc)) {
    case AliasAnalysis::NoModRef:
      // If the call has no effect on the queried pointer, just ignore it.
      continue;
    case AliasAnalysis::Mod:
      // If we're in an invariant region, we can ignore calls that ONLY
      // modify the pointer.
      if (InvariantTag) continue;
      return MemDepResult::getClobber(Inst);
    case AliasAnalysis::Ref:
      // If the call is known to never store to the pointer, and if this is a
      // load query, we can safely ignore it (scan past it).
      if (isLoad)
        continue;
    default:
      // Otherwise, there is a potential dependence.  Return a clobber.
      return MemDepResult::getClobber(Inst);
    }
  }
  
  // No dependence found.  If this is the entry block of the function, it is a
  // clobber, otherwise it is non-local.
  if (BB != &BB->getParent()->getEntryBlock())
    return MemDepResult::getNonLocal();
  return MemDepResult::getClobber(ScanIt);
}

/// getDependency - Return the instruction on which a memory operation
/// depends.
MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
  Instruction *ScanPos = QueryInst;
  
  // Check for a cached result
  MemDepResult &LocalCache = LocalDeps[QueryInst];
  
  // If the cached entry is non-dirty, just return it.  Note that this depends
  // on MemDepResult's default constructing to 'dirty'.
  if (!LocalCache.isDirty())
    return 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.getInst()) {
    ScanPos = Inst;
   
    RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst);
  }
  
  BasicBlock *QueryParent = QueryInst->getParent();
  
  // Do the scan.
  if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
    // No dependence found.  If this is the entry block of the function, it is a
    // clobber, otherwise it is non-local.
    if (QueryParent != &QueryParent->getParent()->getEntryBlock())
      LocalCache = MemDepResult::getNonLocal();
    else
      LocalCache = MemDepResult::getClobber(QueryInst);
  } else {
    AliasAnalysis::Location MemLoc;
    AliasAnalysis::ModRefResult MR = GetLocation(QueryInst, MemLoc, AA);
    if (MemLoc.Ptr) {
      // If we can do a pointer scan, make it happen.
      bool isLoad = !(MR & AliasAnalysis::Mod);
      if (IntrinsicInst *II = dyn_cast<MemoryUseIntrinsic>(QueryInst)) {
        isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_end;
      }
      LocalCache = getPointerDependencyFrom(MemLoc, isLoad, ScanPos,
                                            QueryParent);
    } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) {
      CallSite QueryCS(QueryInst);
      bool isReadOnly = AA->onlyReadsMemory(QueryCS);
      LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos,
                                             QueryParent);
    } else
      // Non-memory instruction.
      LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
{'fraction_non_alphanumeric': 0.11258892669347355, 'fraction_numerical': 0.001349717402918764, 'mean_word_length': 2.687681459975114, 'pattern_counts': {'":': 0, '<': 52, '<?xml version=': 0, '>': 193, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 48, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5924672', 'n_tokens_mistral': 10008, 'n_tokens_neox': 9746, 'n_words': 3052}