<commit_before>//===- LoopAccessAnalysis.cpp - Loop Access Analysis Implementation --------==//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// The implementation for the loop memory dependence that was originally
// developed for the loop vectorizer.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Analysis/VectorUtils.h"
using namespace llvm;

#define DEBUG_TYPE "loop-accesses"

static cl::opt<unsigned, true>
VectorizationFactor("force-vector-width", cl::Hidden,
                    cl::desc("Sets the SIMD width. Zero is autoselect."),
                    cl::location(VectorizerParams::VectorizationFactor));
unsigned VectorizerParams::VectorizationFactor;

static cl::opt<unsigned, true>
VectorizationInterleave("force-vector-interleave", cl::Hidden,
                        cl::desc("Sets the vectorization interleave count. "
                                 "Zero is autoselect."),
                        cl::location(
                            VectorizerParams::VectorizationInterleave));
unsigned VectorizerParams::VectorizationInterleave;

static cl::opt<unsigned, true> RuntimeMemoryCheckThreshold(
    "runtime-memory-check-threshold", cl::Hidden,
    cl::desc("When performing memory disambiguation checks at runtime do not "
             "generate more than this number of comparisons (default = 8)."),
    cl::location(VectorizerParams::RuntimeMemoryCheckThreshold), cl::init(8));
unsigned VectorizerParams::RuntimeMemoryCheckThreshold;

/// \brief The maximum iterations used to merge memory checks
static cl::opt<unsigned> MemoryCheckMergeThreshold(
    "memory-check-merge-threshold", cl::Hidden,
    cl::desc("Maximum number of comparisons done when trying to merge "
             "runtime memory checks. (default = 100)"),
    cl::init(100));

/// Maximum SIMD width.
const unsigned VectorizerParams::MaxVectorWidth = 64;

/// \brief We collect interesting dependences up to this threshold.
static cl::opt<unsigned> MaxInterestingDependence(
    "max-interesting-dependences", cl::Hidden,
    cl::desc("Maximum number of interesting dependences collected by "
             "loop-access analysis (default = 100)"),
    cl::init(100));

bool VectorizerParams::isInterleaveForced() {
  return ::VectorizationInterleave.getNumOccurrences() > 0;
}

void LoopAccessReport::emitAnalysis(const LoopAccessReport &Message,
                                    const Function *TheFunction,
                                    const Loop *TheLoop,
                                    const char *PassName) {
  DebugLoc DL = TheLoop->getStartLoc();
  if (const Instruction *I = Message.getInstr())
    DL = I->getDebugLoc();
  emitOptimizationRemarkAnalysis(TheFunction->getContext(), PassName,
                                 *TheFunction, DL, Message.str());
}

Value *llvm::stripIntegerCast(Value *V) {
  if (CastInst *CI = dyn_cast<CastInst>(V))
    if (CI->getOperand(0)->getType()->isIntegerTy())
      return CI->getOperand(0);
  return V;
}

const SCEV *llvm::replaceSymbolicStrideSCEV(ScalarEvolution *SE,
                                            const ValueToValueMap &PtrToStride,
                                            Value *Ptr, Value *OrigPtr) {

  const SCEV *OrigSCEV = SE->getSCEV(Ptr);

  // If there is an entry in the map return the SCEV of the pointer with the
  // symbolic stride replaced by one.
  ValueToValueMap::const_iterator SI =
      PtrToStride.find(OrigPtr ? OrigPtr : Ptr);
  if (SI != PtrToStride.end()) {
    Value *StrideVal = SI->second;

    // Strip casts.
    StrideVal = stripIntegerCast(StrideVal);

    // Replace symbolic stride by one.
    Value *One = ConstantInt::get(StrideVal->getType(), 1);
    ValueToValueMap RewriteMap;
    RewriteMap[StrideVal] = One;

    const SCEV *ByOne =
        SCEVParameterRewriter::rewrite(OrigSCEV, *SE, RewriteMap, true);
    DEBUG(dbgs() << "LAA: Replacing SCEV: " << *OrigSCEV << " by: " << *ByOne
                 << "\n");
    return ByOne;
  }

  // Otherwise, just return the SCEV of the original pointer.
  return SE->getSCEV(Ptr);
}

void LoopAccessInfo::RuntimePointerCheck::insert(
    Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId, unsigned ASId,
    const ValueToValueMap &Strides) {
  // Get the stride replaced scev.
  const SCEV *Sc = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
  assert(AR && "Invalid addrec expression");
  const SCEV *Ex = SE->getBackedgeTakenCount(Lp);
  const SCEV *ScEnd = AR->evaluateAtIteration(Ex, *SE);
  Pointers.push_back(Ptr);
  Starts.push_back(AR->getStart());
  Ends.push_back(ScEnd);
  IsWritePtr.push_back(WritePtr);
  DependencySetId.push_back(DepSetId);
  AliasSetId.push_back(ASId);
  Exprs.push_back(Sc);
}

bool LoopAccessInfo::RuntimePointerCheck::needsChecking(
    const CheckingPtrGroup &M, const CheckingPtrGroup &N,
    const SmallVectorImpl<int> *PtrPartition) const {
  for (unsigned I = 0, EI = M.Members.size(); EI != I; ++I)
    for (unsigned J = 0, EJ = N.Members.size(); EJ != J; ++J)
      if (needsChecking(M.Members[I], N.Members[J], PtrPartition))
        return true;
  return false;
}

/// Compare \p I and \p J and return the minimum.
/// Return nullptr in case we couldn't find an answer.
static const SCEV *getMinFromExprs(const SCEV *I, const SCEV *J,
                                   ScalarEvolution *SE) {
  const SCEV *Diff = SE->getMinusSCEV(J, I);
  const SCEVConstant *C = dyn_cast<const SCEVConstant>(Diff);

  if (!C)
    return nullptr;
  if (C->getValue()->isNegative())
    return J;
  return I;
}

bool LoopAccessInfo::RuntimePointerCheck::CheckingPtrGroup::addPointer(
    unsigned Index) {
  // Compare the starts and ends with the known minimum and maximum
  // of this set. We need to know how we compare against the min/max
  // of the set in order to be able to emit memchecks.
  const SCEV *Min0 = getMinFromExprs(RtCheck.Starts[Index], Low, RtCheck.SE);
  if (!Min0)
    return false;

  const SCEV *Min1 = getMinFromExprs(RtCheck.Ends[Index], High, RtCheck.SE);
  if (!Min1)
    return false;

  // Update the low bound  expression if we've found a new min value.
  if (Min0 == RtCheck.Starts[Index])
    Low = RtCheck.Starts[Index];

  // Update the high bound expression if we've found a new max value.
  if (Min1 != RtCheck.Ends[Index])
    High = RtCheck.Ends[Index];

  Members.push_back(Index);
  return true;
}

void LoopAccessInfo::RuntimePointerCheck::groupChecks(
    MemoryDepChecker::DepCandidates &DepCands,
    bool UseDependencies) {
  // We build the groups from dependency candidates equivalence classes
  // because:
  //    - We know that pointers in the same equivalence class share
  //      the same underlying object and therefore there is a chance
  //      that we can compare pointers
  //    - We wouldn't be able to merge two pointers for which we need
  //      to emit a memcheck. The classes in DepCands are already
  //      conveniently built such that no two pointers in the same
  //      class need checking against each other.

  // We use the following (greedy) algorithm to construct the groups
  // For every pointer in the equivalence class:
  //   For each existing group:
  //   - if the difference between this pointer and the min/max bounds
  //     of the group is a constant, then make the pointer part of the
  //     group and update the min/max bounds of that group as required.

  CheckingGroups.clear();

  // If we don't have the dependency partitions, construct a new
  // checking pointer group for each pointer.
  if (!UseDependencies) {
    for (unsigned I = 0; I < Pointers.size(); ++I)
      CheckingGroups.push_back(CheckingPtrGroup(I, *this));
    return;
  }

  unsigned TotalComparisons = 0;

  DenseMap<Value *, unsigned> PositionMap;
  for (unsigned Pointer = 0; Pointer < Pointers.size(); ++Pointer)
    PositionMap[Pointers[Pointer]] = Pointer;

  // Go through all equivalence classes, get the the "pointer check groups"
  // and add them to the overall solution.
  for (auto DI = DepCands.begin(), DE = DepCands.end(); DI != DE; ++DI) {
    if (!DI->isLeader())
      continue;

    SmallVector<CheckingPtrGroup, 2> Groups;

    for (auto MI = DepCands.member_begin(DI), ME = DepCands.member_end();
         MI != ME; ++MI) {
      unsigned Pointer = PositionMap[MI->getPointer()];
      bool Merged = false;

      // Go through all the existing sets and see if we can find one
      // which can include this pointer.
      for (CheckingPtrGroup &Group : Groups) {
        // Don't perform more than a certain amount of comparisons.
        // This should limit the cost of grouping the pointers to something
        // reasonable.  If we do end up hitting this threshold, the algorithm
        // will create separate groups for all remaining pointers.
        if (TotalComparisons > MemoryCheckMergeThreshold)
          break;

        TotalComparisons++;

        if (Group.addPointer(Pointer)) {
          Merged = true;
          break;
        }
      }

      if (!Merged)
        // We couldn't add this pointer to any existing set or the threshold
        // for the number of comparisons has been reached. Create a new group
        // to hold the current pointer.
        Groups.push_back(CheckingPtrGroup(Pointer, *this));
    }

    // We've computed the grouped checks for this partition.
    // Save the results and continue with the next one.
    std::copy(Groups.begin(), Groups.end(), std::back_inserter(CheckingGroups));
  }
}

bool LoopAccessInfo::RuntimePointerCheck::needsChecking(
    unsigned I, unsigned J, const SmallVectorImpl<int> *PtrPartition) const {
  // No need to check if two readonly pointers intersect.
  if (!IsWritePtr[I] && !IsWritePtr[J])
    return false;

  // Only need to check pointers between two different dependency sets.
  if (DependencySetId[I] == DependencySetId[J])
    return false;

  // Only need to check pointers in the same alias set.
  if (AliasSetId[I] != AliasSetId[J])
    return false;

  // If PtrPartition is set omit checks between pointers of the same partition.
  // Partition number -1 means that the pointer is used in multiple partitions.
  // In this case we can't omit the check.
  if (PtrPartition && (*PtrPartition)[I] != -1 &&
      (*PtrPartition)[I] == (*PtrPartition)[J])
    return false;

  return true;
}

void LoopAccessInfo::RuntimePointerCheck::print(
    raw_ostream &OS, unsigned Depth,
    const SmallVectorImpl<int> *PtrPartition) const {

  OS.indent(Depth) << "Run-time memory checks:\n";

  unsigned N = 0;
  for (unsigned I = 0; I < CheckingGroups.size(); ++I)
    for (unsigned J = I + 1; J < CheckingGroups.size(); ++J)
      if (needsChecking(CheckingGroups[I], CheckingGroups[J], PtrPartition)) {
        OS.indent(Depth) << "Check " << N++ << ":\n";
        OS.indent(Depth + 2) << "Comparing group " << I << ":\n";

        for (unsigned K = 0; K < CheckingGroups[I].Members.size(); ++K) {
          OS.indent(Depth + 2) << *Pointers[CheckingGroups[I].Members[K]]
                               << "\n";
          if (PtrPartition)
            OS << " (Partition: "
               << (*PtrPartition)[CheckingGroups[I].Members[K]] << ")"
               << "\n";
        }

        OS.indent(Depth + 2) << "Against group " << J << ":\n";

        for (unsigned K = 0; K < CheckingGroups[J].Members.size(); ++K) {
          OS.indent(Depth + 2) << *Pointers[CheckingGroups[J].Members[K]]
                               << "\n";
          if (PtrPartition)
            OS << " (Partition: "
               << (*PtrPartition)[CheckingGroups[J].Members[K]] << ")"
               << "\n";
        }
      }

  OS.indent(Depth) << "Grouped accesses:\n";
  for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
    OS.indent(Depth + 2) << "Group " << I << ":\n";
    OS.indent(Depth + 4) << "(Low: " << *CheckingGroups[I].Low
                         << " High: " << *CheckingGroups[I].High << ")\n";
    for (unsigned J = 0; J < CheckingGroups[I].Members.size(); ++J) {
      OS.indent(Depth + 6) << "Member: " << *Exprs[CheckingGroups[I].Members[J]]
                           << "\n";
    }
  }
}

unsigned LoopAccessInfo::RuntimePointerCheck::getNumberOfChecks(
    const SmallVectorImpl<int> *PtrPartition) const {

  unsigned NumPartitions = CheckingGroups.size();
  unsigned CheckCount = 0;

  for (unsigned I = 0; I < NumPartitions; ++I)
    for (unsigned J = I + 1; J < NumPartitions; ++J)
      if (needsChecking(CheckingGroups[I], CheckingGroups[J], PtrPartition))
        CheckCount++;
  return CheckCount;
}

bool LoopAccessInfo::RuntimePointerCheck::needsAnyChecking(
    const SmallVectorImpl<int> *PtrPartition) const {
  unsigned NumPointers = Pointers.size();

  for (unsigned I = 0; I < NumPointers; ++I)
    for (unsigned J = I + 1; J < NumPointers; ++J)
      if (needsChecking(I, J, PtrPartition))
        return true;
  return false;
}

namespace {
/// \brief Analyses memory accesses in a loop.
///
/// Checks whether run time pointer checks are needed and builds sets for data
/// dependence checking.
class AccessAnalysis {
public:
  /// \brief Read or write access location.
  typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
  typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet;

  AccessAnalysis(const DataLayout &Dl, AliasAnalysis *AA, LoopInfo *LI,
                 MemoryDepChecker::DepCandidates &DA)
      : DL(Dl), AST(*AA), LI(LI), DepCands(DA), IsRTCheckNeeded(false) {}

  /// \brief Register a load  and whether it is only read from.
  void addLoad(MemoryLocation &Loc, bool IsReadOnly) {
    Value *Ptr = const_cast<Value*>(Loc.Ptr);
    AST.add(Ptr, MemoryLocation::UnknownSize, Loc.AATags);
    Accesses.insert(MemAccessInfo(Ptr, false));
    if (IsReadOnly)
      ReadOnlyPtr.insert(Ptr);
  }

  /// \brief Register a store.
  void addStore(MemoryLocation &Loc) {
    Value *Ptr = const_cast<Value*>(Loc.Ptr);
    AST.add(Ptr, MemoryLocation::UnknownSize, Loc.AATags);
    Accesses.insert(MemAccessInfo(Ptr, true));
  }

  /// \brief Check whether we can check the pointers at runtime for
  /// non-intersection. Returns true when we have 0 pointers
  /// (a check on 0 pointers for non-intersection will always return true).
  bool canCheckPtrAtRT(LoopAccessInfo::RuntimePointerCheck &RtCheck,
                       bool &NeedRTCheck, ScalarEvolution *SE, Loop *TheLoop,
                       const ValueToValueMap &Strides,
                       bool ShouldCheckStride = false);

  /// \brief Goes over all memory accesses, checks whether a RT check is needed
  /// and builds sets of dependent accesses.
  void buildDependenceSets() {
    processMemAccesses();
  }

  bool isRTCheckNeeded() { return IsRTCheckNeeded; }

  bool isDependencyCheckNeeded() { return !CheckDeps.empty(); }

  /// We decided that no dependence analysis would be used.  Reset the state.
  void resetDepChecks(MemoryDepChecker &DepChecker) {
    CheckDeps.clear();
    DepChecker.clearInterestingDependences();
  }

  MemAccessInfoSet &getDependenciesToCheck() { return CheckDeps; }

private:
  typedef SetVector<MemAccessInfo> PtrAccessSet;

  /// \brief Go over all memory access and check whether runtime pointer checks
  /// are needed /// and build sets of dependency check candidates.
  void processMemAccesses();

  /// Set of all accesses.
  PtrAccessSet Accesses;

  const DataLayout &DL;

  /// Set of accesses that need a further dependence check.
  MemAccessInfoSet CheckDeps;

  /// Set of pointers that are read only.
  SmallPtrSet<Value*, 16> ReadOnlyPtr;

  /// An alias set tracker to partition the access set by underlying object and
  //intrinsic property (such as TBAA metadata).
  AliasSetTracker AST;

  LoopInfo *LI;

  /// Sets of potentially dependent accesses - members of one set share an
  /// underlying pointer. The set "CheckDeps" identfies which sets really need a
  /// dependence check.
  MemoryDepChecker::DepCandidates &DepCands;

  bool IsRTCheckNeeded;
};

} // end anonymous namespace

/// \brief Check whether a pointer can participate in a runtime bounds check.
static bool hasComputableBounds(ScalarEvolution *SE,
                                const ValueToValueMap &Strides, Value *Ptr) {
  const SCEV *PtrScev = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
  if (!AR)
    return false;

  return AR->isAffine();
}

bool AccessAnalysis::canCheckPtrAtRT(
    LoopAccessInfo::RuntimePointerCheck &RtCheck, bool &NeedRTCheck,
    ScalarEvolution *SE, Loop *TheLoop, const ValueToValueMap &StridesMap,
    bool ShouldCheckStride) {
  // Find pointers with computable bounds. We are going to use this information
  // to place a runtime bound check.
  bool CanDoRT = true;

  NeedRTCheck = false;
  if (!IsRTCheckNeeded) return true;

  bool IsDepCheckNeeded = isDependencyCheckNeeded();

  // We assign a consecutive id to access from different alias sets.
  // Accesses between different groups doesn't need to be checked.
  unsigned ASId = 1;
  for (auto &AS : AST) {
    int NumReadPtrChecks = 0;
    int NumWritePtrChecks = 0;

    // We assign consecutive id to access from different dependence sets.
    // Accesses within the same set don't need a runtime check.
    unsigned RunningDepId = 1;
    DenseMap<Value *, unsigned> DepSetId;

    for (auto A : AS) {
      Value *Ptr = A.getValue();
      bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true));
      MemAccessInfo Access(Ptr, IsWrite);

      if (IsWrite)
        ++NumWritePtrChecks;
      else
        ++NumReadPtrChecks;

      if (hasComputableBounds(SE, StridesMap, Ptr) &&
          // When we run after a failing dependency check we have to make sure
          // we don't have wrapping pointers.
          (!ShouldCheckStride ||
           isStridedPtr(SE, Ptr, TheLoop, StridesMap) == 1)) {
        // The id of the dependence set.
        unsigned DepId;

        if (IsDepCheckNeeded) {
          Value *Leader = DepCands.getLeaderValue(Access).getPointer();
          unsigned &LeaderId = DepSetId[Leader];
          if (!LeaderId)
            LeaderId = RunningDepId++;
          DepId = LeaderId;
        } else
          // Each access has its own dependence set.
          DepId = RunningDepId++;

        RtCheck.insert(TheLoop, Ptr, IsWrite, DepId, ASId, StridesMap);

        DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
      } else {
        DEBUG(dbgs() << "LAA: Can't find bounds for ptr:" << *Ptr << '\n');
        CanDoRT = false;
      }
    }

    // If we have at least two writes or one write and a read then we need to
    // check them.  But there is no need to checks if there is only one
    // dependence set for this alias set.
    //
    // Note that this function computes CanDoRT and NeedRTCheck independently.
    // For example CanDoRT=false, NeedRTCheck=false means that we have a pointer
    // for which we couldn't find the bounds but we don't actually need to emit
    // any checks so it does not matter.
    if (!(IsDepCheckNeeded && CanDoRT && RunningDepId == 2))
      NeedRTCheck |= (NumWritePtrChecks >= 2 || (NumReadPtrChecks >= 1 &&
                                                 NumWritePtrChecks >= 1));

    ++ASId;
  }

  // If the pointers that we would use for the bounds comparison have different
  // address spaces, assume the values aren't directly comparable, so we can't
  // use them for the runtime check. We also have to assume they could
  // overlap. In the future there should be metadata for whether address spaces
  // are disjoint.
  unsigned NumPointers = RtCheck.Pointers.size();
  for (unsigned i = 0; i < NumPointers; ++i) {
    for (unsigned j = i + 1; j < NumPointers; ++j) {
      // Only need to check pointers between two different dependency sets.
      if (RtCheck.DependencySetId[i] == RtCheck.DependencySetId[j])
       continue;
      // Only need to check pointers in the same alias set.
      if (RtCheck.AliasSetId[i] != RtCheck.AliasSetId[j])
        continue;

      Value *PtrI = RtCheck.Pointers[i];
      Value *PtrJ = RtCheck.Pointers[j];

      unsigned ASi = PtrI->getType()->getPointerAddressSpace();
      unsigned ASj = PtrJ->getType()->getPointerAddressSpace();
      if (ASi != ASj) {
        DEBUG(dbgs() << "LAA: Runtime check would require comparison between"
                       " different address spaces\n");
        return false;
      }
    }
  }

  if (NeedRTCheck && CanDoRT)
    RtCheck.groupChecks(DepCands, IsDepCheckNeeded);

  return CanDoRT;
}

void AccessAnalysis::processMemAccesses() {
  // We process the set twice: first we process read-write pointers, last we
  // process read-only pointers. This allows us to skip dependence tests for
  // read-only pointers.

  DEBUG(dbgs() << "LAA: Processing memory accesses...\n");
  DEBUG(dbgs() << "  AST: "; AST.dump());
  DEBUG(dbgs() << "LAA:   Accesses(" << Accesses.size() << "):\n");
  DEBUG({
    for (auto A : Accesses)
      dbgs() << "\t" << *A.getPointer() << " (" <<
                (A.getInt() ? "write" : (ReadOnlyPtr.count(A.getPointer()) ?
                                         "read-only" : "read")) << ")\n";
  });

  // The AliasSetTracker has nicely partitioned our pointers by metadata
  // compatibility and potential for underlying-object overlap. As a result, we
  // only need to check for potential pointer dependencies within each alias
  // set.
  for (auto &AS : AST) {
    // Note that both the alias-set tracker and the alias sets themselves used
    // linked lists internally and so the iteration order here is deterministic
    // (matching the original instruction order within each set).

    bool SetHasWrite = false;

    // Map of pointers to last access encountered.
    typedef DenseMap<Value*, MemAccessInfo> UnderlyingObjToAccessMap;
    UnderlyingObjToAccessMap ObjToLastAccess;

    // Set of access to check after all writes have been processed.
    PtrAccessSet DeferredAccesses;

    // Iterate over each alias set twice, once to process read/write pointers,
    // and then to process read-only pointers.
    for (int SetIteration = 0; SetIteration < 2; ++SetIteration) {
      bool UseDeferred = SetIteration > 0;
      PtrAccessSet &S = UseDeferred ? DeferredAccesses : Accesses;

      for (auto AV : AS) {
        Value *Ptr = AV.getValue();

        // For a single memory access in AliasSetTracker, Accesses may contain
        // both read and write, and they both need to be handled for CheckDeps.
        for (auto AC : S) {
          if (AC.getPointer() != Ptr)
            continue;

          bool IsWrite = AC.getInt();

          // If we're using the deferred access set, then it contains only
          // reads.
          bool IsReadOnlyPtr = ReadOnlyPtr.count(Ptr) && !IsWrite;
          if (UseDeferred && !IsReadOnlyPtr)
            continue;
          // Otherwise, the pointer must be in the PtrAccessSet, either as a
          // read or a write.
          assert(((IsReadOnlyPtr && UseDeferred) || IsWrite ||
                  S.count(MemAccessInfo(Ptr, false))) &&
                 "Alias-set pointer not in the access set?");

          MemAccessInfo Access(Ptr, IsWrite);
          DepCands.insert(Access);

          // Memorize read-only pointers for later processing and skip them in
          // the first round (they need to be checked after we have seen all
          // write pointers). Note: we also mark pointer that are not
          // consecutive as "read-only" pointers (so that we check
          // "a[b[i]] +="). Hence, we need the second check for "!IsWrite".
          if (!UseDeferred && IsReadOnlyPtr) {
            DeferredAccesses.insert(Access);
            continue;
          }

          // If this is a write - check other reads and writes for conflicts. If
          // this is a read only check other writes for conflicts (but only if
          // there is no other write to the ptr - this is an optimization to
          // catch "a[i] = a[i] + " without having to do a dependence check).
          if ((IsWrite || IsReadOnlyPtr) && SetHasWrite) {
            CheckDeps.insert(Access);
            IsRTCheckNeeded = true;
          }

          if (IsWrite)
            SetHasWrite = true;

          // Create sets of pointers connected by a shared alias set and
          // underlying object.
          typedef SmallVector<Value *, 16> ValueVector;
          ValueVector TempObjects;

          GetUnderlyingObjects(Ptr, TempObjects, DL, LI);
          DEBUG(dbgs() << "Underlying objects for pointer " << *Ptr << "\n");
          for (Value *UnderlyingObj : TempObjects) {
            UnderlyingObjToAccessMap::iterator Prev =
                ObjToLastAccess.find(UnderlyingObj);<commit_msg>[LAA] Rename IsRTNeeded to IsRTCheckAnalysisNeeded<commit_after>//===- LoopAccessAnalysis.cpp - Loop Access Analysis Implementation --------==//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// The implementation for the loop memory dependence that was originally
// developed for the loop vectorizer.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Analysis/VectorUtils.h"
using namespace llvm;

#define DEBUG_TYPE "loop-accesses"

static cl::opt<unsigned, true>
VectorizationFactor("force-vector-width", cl::Hidden,
                    cl::desc("Sets the SIMD width. Zero is autoselect."),
                    cl::location(VectorizerParams::VectorizationFactor));
unsigned VectorizerParams::VectorizationFactor;

static cl::opt<unsigned, true>
VectorizationInterleave("force-vector-interleave", cl::Hidden,
                        cl::desc("Sets the vectorization interleave count. "
                                 "Zero is autoselect."),
                        cl::location(
                            VectorizerParams::VectorizationInterleave));
unsigned VectorizerParams::VectorizationInterleave;

static cl::opt<unsigned, true> RuntimeMemoryCheckThreshold(
    "runtime-memory-check-threshold", cl::Hidden,
    cl::desc("When performing memory disambiguation checks at runtime do not "
             "generate more than this number of comparisons (default = 8)."),
    cl::location(VectorizerParams::RuntimeMemoryCheckThreshold), cl::init(8));
unsigned VectorizerParams::RuntimeMemoryCheckThreshold;

/// \brief The maximum iterations used to merge memory checks
static cl::opt<unsigned> MemoryCheckMergeThreshold(
    "memory-check-merge-threshold", cl::Hidden,
    cl::desc("Maximum number of comparisons done when trying to merge "
             "runtime memory checks. (default = 100)"),
    cl::init(100));

/// Maximum SIMD width.
const unsigned VectorizerParams::MaxVectorWidth = 64;

/// \brief We collect interesting dependences up to this threshold.
static cl::opt<unsigned> MaxInterestingDependence(
    "max-interesting-dependences", cl::Hidden,
    cl::desc("Maximum number of interesting dependences collected by "
             "loop-access analysis (default = 100)"),
    cl::init(100));

bool VectorizerParams::isInterleaveForced() {
  return ::VectorizationInterleave.getNumOccurrences() > 0;
}

void LoopAccessReport::emitAnalysis(const LoopAccessReport &Message,
                                    const Function *TheFunction,
                                    const Loop *TheLoop,
                                    const char *PassName) {
  DebugLoc DL = TheLoop->getStartLoc();
  if (const Instruction *I = Message.getInstr())
    DL = I->getDebugLoc();
  emitOptimizationRemarkAnalysis(TheFunction->getContext(), PassName,
                                 *TheFunction, DL, Message.str());
}

Value *llvm::stripIntegerCast(Value *V) {
  if (CastInst *CI = dyn_cast<CastInst>(V))
    if (CI->getOperand(0)->getType()->isIntegerTy())
      return CI->getOperand(0);
  return V;
}

const SCEV *llvm::replaceSymbolicStrideSCEV(ScalarEvolution *SE,
                                            const ValueToValueMap &PtrToStride,
                                            Value *Ptr, Value *OrigPtr) {

  const SCEV *OrigSCEV = SE->getSCEV(Ptr);

  // If there is an entry in the map return the SCEV of the pointer with the
  // symbolic stride replaced by one.
  ValueToValueMap::const_iterator SI =
      PtrToStride.find(OrigPtr ? OrigPtr : Ptr);
  if (SI != PtrToStride.end()) {
    Value *StrideVal = SI->second;

    // Strip casts.
    StrideVal = stripIntegerCast(StrideVal);

    // Replace symbolic stride by one.
    Value *One = ConstantInt::get(StrideVal->getType(), 1);
    ValueToValueMap RewriteMap;
    RewriteMap[StrideVal] = One;

    const SCEV *ByOne =
        SCEVParameterRewriter::rewrite(OrigSCEV, *SE, RewriteMap, true);
    DEBUG(dbgs() << "LAA: Replacing SCEV: " << *OrigSCEV << " by: " << *ByOne
                 << "\n");
    return ByOne;
  }

  // Otherwise, just return the SCEV of the original pointer.
  return SE->getSCEV(Ptr);
}

void LoopAccessInfo::RuntimePointerCheck::insert(
    Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId, unsigned ASId,
    const ValueToValueMap &Strides) {
  // Get the stride replaced scev.
  const SCEV *Sc = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
  assert(AR && "Invalid addrec expression");
  const SCEV *Ex = SE->getBackedgeTakenCount(Lp);
  const SCEV *ScEnd = AR->evaluateAtIteration(Ex, *SE);
  Pointers.push_back(Ptr);
  Starts.push_back(AR->getStart());
  Ends.push_back(ScEnd);
  IsWritePtr.push_back(WritePtr);
  DependencySetId.push_back(DepSetId);
  AliasSetId.push_back(ASId);
  Exprs.push_back(Sc);
}

bool LoopAccessInfo::RuntimePointerCheck::needsChecking(
    const CheckingPtrGroup &M, const CheckingPtrGroup &N,
    const SmallVectorImpl<int> *PtrPartition) const {
  for (unsigned I = 0, EI = M.Members.size(); EI != I; ++I)
    for (unsigned J = 0, EJ = N.Members.size(); EJ != J; ++J)
      if (needsChecking(M.Members[I], N.Members[J], PtrPartition))
        return true;
  return false;
}

/// Compare \p I and \p J and return the minimum.
/// Return nullptr in case we couldn't find an answer.
static const SCEV *getMinFromExprs(const SCEV *I, const SCEV *J,
                                   ScalarEvolution *SE) {
  const SCEV *Diff = SE->getMinusSCEV(J, I);
  const SCEVConstant *C = dyn_cast<const SCEVConstant>(Diff);

  if (!C)
    return nullptr;
  if (C->getValue()->isNegative())
    return J;
  return I;
}

bool LoopAccessInfo::RuntimePointerCheck::CheckingPtrGroup::addPointer(
    unsigned Index) {
  // Compare the starts and ends with the known minimum and maximum
  // of this set. We need to know how we compare against the min/max
  // of the set in order to be able to emit memchecks.
  const SCEV *Min0 = getMinFromExprs(RtCheck.Starts[Index], Low, RtCheck.SE);
  if (!Min0)
    return false;

  const SCEV *Min1 = getMinFromExprs(RtCheck.Ends[Index], High, RtCheck.SE);
  if (!Min1)
    return false;

  // Update the low bound  expression if we've found a new min value.
  if (Min0 == RtCheck.Starts[Index])
    Low = RtCheck.Starts[Index];

  // Update the high bound expression if we've found a new max value.
  if (Min1 != RtCheck.Ends[Index])
    High = RtCheck.Ends[Index];

  Members.push_back(Index);
  return true;
}

void LoopAccessInfo::RuntimePointerCheck::groupChecks(
    MemoryDepChecker::DepCandidates &DepCands,
    bool UseDependencies) {
  // We build the groups from dependency candidates equivalence classes
  // because:
  //    - We know that pointers in the same equivalence class share
  //      the same underlying object and therefore there is a chance
  //      that we can compare pointers
  //    - We wouldn't be able to merge two pointers for which we need
  //      to emit a memcheck. The classes in DepCands are already
  //      conveniently built such that no two pointers in the same
  //      class need checking against each other.

  // We use the following (greedy) algorithm to construct the groups
  // For every pointer in the equivalence class:
  //   For each existing group:
  //   - if the difference between this pointer and the min/max bounds
  //     of the group is a constant, then make the pointer part of the
  //     group and update the min/max bounds of that group as required.

  CheckingGroups.clear();

  // If we don't have the dependency partitions, construct a new
  // checking pointer group for each pointer.
  if (!UseDependencies) {
    for (unsigned I = 0; I < Pointers.size(); ++I)
      CheckingGroups.push_back(CheckingPtrGroup(I, *this));
    return;
  }

  unsigned TotalComparisons = 0;

  DenseMap<Value *, unsigned> PositionMap;
  for (unsigned Pointer = 0; Pointer < Pointers.size(); ++Pointer)
    PositionMap[Pointers[Pointer]] = Pointer;

  // Go through all equivalence classes, get the the "pointer check groups"
  // and add them to the overall solution.
  for (auto DI = DepCands.begin(), DE = DepCands.end(); DI != DE; ++DI) {
    if (!DI->isLeader())
      continue;

    SmallVector<CheckingPtrGroup, 2> Groups;

    for (auto MI = DepCands.member_begin(DI), ME = DepCands.member_end();
         MI != ME; ++MI) {
      unsigned Pointer = PositionMap[MI->getPointer()];
      bool Merged = false;

      // Go through all the existing sets and see if we can find one
      // which can include this pointer.
      for (CheckingPtrGroup &Group : Groups) {
        // Don't perform more than a certain amount of comparisons.
        // This should limit the cost of grouping the pointers to something
        // reasonable.  If we do end up hitting this threshold, the algorithm
        // will create separate groups for all remaining pointers.
        if (TotalComparisons > MemoryCheckMergeThreshold)
          break;

        TotalComparisons++;

        if (Group.addPointer(Pointer)) {
          Merged = true;
          break;
        }
      }

      if (!Merged)
        // We couldn't add this pointer to any existing set or the threshold
        // for the number of comparisons has been reached. Create a new group
        // to hold the current pointer.
        Groups.push_back(CheckingPtrGroup(Pointer, *this));
    }

    // We've computed the grouped checks for this partition.
    // Save the results and continue with the next one.
    std::copy(Groups.begin(), Groups.end(), std::back_inserter(CheckingGroups));
  }
}

bool LoopAccessInfo::RuntimePointerCheck::needsChecking(
    unsigned I, unsigned J, const SmallVectorImpl<int> *PtrPartition) const {
  // No need to check if two readonly pointers intersect.
  if (!IsWritePtr[I] && !IsWritePtr[J])
    return false;

  // Only need to check pointers between two different dependency sets.
  if (DependencySetId[I] == DependencySetId[J])
    return false;

  // Only need to check pointers in the same alias set.
  if (AliasSetId[I] != AliasSetId[J])
    return false;

  // If PtrPartition is set omit checks between pointers of the same partition.
  // Partition number -1 means that the pointer is used in multiple partitions.
  // In this case we can't omit the check.
  if (PtrPartition && (*PtrPartition)[I] != -1 &&
      (*PtrPartition)[I] == (*PtrPartition)[J])
    return false;

  return true;
}

void LoopAccessInfo::RuntimePointerCheck::print(
    raw_ostream &OS, unsigned Depth,
    const SmallVectorImpl<int> *PtrPartition) const {

  OS.indent(Depth) << "Run-time memory checks:\n";

  unsigned N = 0;
  for (unsigned I = 0; I < CheckingGroups.size(); ++I)
    for (unsigned J = I + 1; J < CheckingGroups.size(); ++J)
      if (needsChecking(CheckingGroups[I], CheckingGroups[J], PtrPartition)) {
        OS.indent(Depth) << "Check " << N++ << ":\n";
        OS.indent(Depth + 2) << "Comparing group " << I << ":\n";

        for (unsigned K = 0; K < CheckingGroups[I].Members.size(); ++K) {
          OS.indent(Depth + 2) << *Pointers[CheckingGroups[I].Members[K]]
                               << "\n";
          if (PtrPartition)
            OS << " (Partition: "
               << (*PtrPartition)[CheckingGroups[I].Members[K]] << ")"
               << "\n";
        }

        OS.indent(Depth + 2) << "Against group " << J << ":\n";

        for (unsigned K = 0; K < CheckingGroups[J].Members.size(); ++K) {
          OS.indent(Depth + 2) << *Pointers[CheckingGroups[J].Members[K]]
                               << "\n";
          if (PtrPartition)
            OS << " (Partition: "
               << (*PtrPartition)[CheckingGroups[J].Members[K]] << ")"
               << "\n";
        }
      }

  OS.indent(Depth) << "Grouped accesses:\n";
  for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
    OS.indent(Depth + 2) << "Group " << I << ":\n";
    OS.indent(Depth + 4) << "(Low: " << *CheckingGroups[I].Low
                         << " High: " << *CheckingGroups[I].High << ")\n";
    for (unsigned J = 0; J < CheckingGroups[I].Members.size(); ++J) {
      OS.indent(Depth + 6) << "Member: " << *Exprs[CheckingGroups[I].Members[J]]
                           << "\n";
    }
  }
}

unsigned LoopAccessInfo::RuntimePointerCheck::getNumberOfChecks(
    const SmallVectorImpl<int> *PtrPartition) const {

  unsigned NumPartitions = CheckingGroups.size();
  unsigned CheckCount = 0;

  for (unsigned I = 0; I < NumPartitions; ++I)
    for (unsigned J = I + 1; J < NumPartitions; ++J)
      if (needsChecking(CheckingGroups[I], CheckingGroups[J], PtrPartition))
        CheckCount++;
  return CheckCount;
}

bool LoopAccessInfo::RuntimePointerCheck::needsAnyChecking(
    const SmallVectorImpl<int> *PtrPartition) const {
  unsigned NumPointers = Pointers.size();

  for (unsigned I = 0; I < NumPointers; ++I)
    for (unsigned J = I + 1; J < NumPointers; ++J)
      if (needsChecking(I, J, PtrPartition))
        return true;
  return false;
}

namespace {
/// \brief Analyses memory accesses in a loop.
///
/// Checks whether run time pointer checks are needed and builds sets for data
/// dependence checking.
class AccessAnalysis {
public:
  /// \brief Read or write access location.
  typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
  typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet;

  AccessAnalysis(const DataLayout &Dl, AliasAnalysis *AA, LoopInfo *LI,
                 MemoryDepChecker::DepCandidates &DA)
      : DL(Dl), AST(*AA), LI(LI), DepCands(DA),
        IsRTCheckAnalysisNeeded(false) {}

  /// \brief Register a load  and whether it is only read from.
  void addLoad(MemoryLocation &Loc, bool IsReadOnly) {
    Value *Ptr = const_cast<Value*>(Loc.Ptr);
    AST.add(Ptr, MemoryLocation::UnknownSize, Loc.AATags);
    Accesses.insert(MemAccessInfo(Ptr, false));
    if (IsReadOnly)
      ReadOnlyPtr.insert(Ptr);
  }

  /// \brief Register a store.
  void addStore(MemoryLocation &Loc) {
    Value *Ptr = const_cast<Value*>(Loc.Ptr);
    AST.add(Ptr, MemoryLocation::UnknownSize, Loc.AATags);
    Accesses.insert(MemAccessInfo(Ptr, true));
  }

  /// \brief Check whether we can check the pointers at runtime for
  /// non-intersection. Returns true when we have 0 pointers
  /// (a check on 0 pointers for non-intersection will always return true).
  bool canCheckPtrAtRT(LoopAccessInfo::RuntimePointerCheck &RtCheck,
                       bool &NeedRTCheck, ScalarEvolution *SE, Loop *TheLoop,
                       const ValueToValueMap &Strides,
                       bool ShouldCheckStride = false);

  /// \brief Goes over all memory accesses, checks whether a RT check is needed
  /// and builds sets of dependent accesses.
  void buildDependenceSets() {
    processMemAccesses();
  }

  /// \brief Initial processing of memory accesses determined that we need to
  /// perform dependency checking.
  ///
  /// Note that this can later be cleared if we retry memcheck analysis without
  /// dependency checking (i.e. ShouldRetryWithRuntimeCheck).
  bool isDependencyCheckNeeded() { return !CheckDeps.empty(); }

  /// We decided that no dependence analysis would be used.  Reset the state.
  void resetDepChecks(MemoryDepChecker &DepChecker) {
    CheckDeps.clear();
    DepChecker.clearInterestingDependences();
  }

  MemAccessInfoSet &getDependenciesToCheck() { return CheckDeps; }

private:
  typedef SetVector<MemAccessInfo> PtrAccessSet;

  /// \brief Go over all memory access and check whether runtime pointer checks
  /// are needed /// and build sets of dependency check candidates.
  void processMemAccesses();

  /// Set of all accesses.
  PtrAccessSet Accesses;

  const DataLayout &DL;

  /// Set of accesses that need a further dependence check.
  MemAccessInfoSet CheckDeps;

  /// Set of pointers that are read only.
  SmallPtrSet<Value*, 16> ReadOnlyPtr;

  /// An alias set tracker to partition the access set by underlying object and
  //intrinsic property (such as TBAA metadata).
  AliasSetTracker AST;

  LoopInfo *LI;

  /// Sets of potentially dependent accesses - members of one set share an
  /// underlying pointer. The set "CheckDeps" identfies which sets really need a
  /// dependence check.
  MemoryDepChecker::DepCandidates &DepCands;

  /// \brief Initial processing of memory accesses determined that we may need
  /// to add memchecks.  Perform the analysis to determine the necessary checks.
  ///
  /// Note that, this is different from isDependencyCheckNeeded.  When we retry
  /// memcheck analysis without dependency checking
  /// (i.e. ShouldRetryWithRuntimeCheck), isDependencyCheckNeeded is cleared
  /// while this remains set if we have potentially dependent accesses.
  bool IsRTCheckAnalysisNeeded;
};

} // end anonymous namespace

/// \brief Check whether a pointer can participate in a runtime bounds check.
static bool hasComputableBounds(ScalarEvolution *SE,
                                const ValueToValueMap &Strides, Value *Ptr) {
  const SCEV *PtrScev = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
  if (!AR)
    return false;

  return AR->isAffine();
}

bool AccessAnalysis::canCheckPtrAtRT(
    LoopAccessInfo::RuntimePointerCheck &RtCheck, bool &NeedRTCheck,
    ScalarEvolution *SE, Loop *TheLoop, const ValueToValueMap &StridesMap,
    bool ShouldCheckStride) {
  // Find pointers with computable bounds. We are going to use this information
  // to place a runtime bound check.
  bool CanDoRT = true;

  NeedRTCheck = false;
  if (!IsRTCheckAnalysisNeeded) return true;

  bool IsDepCheckNeeded = isDependencyCheckNeeded();

  // We assign a consecutive id to access from different alias sets.
  // Accesses between different groups doesn't need to be checked.
  unsigned ASId = 1;
  for (auto &AS : AST) {
    int NumReadPtrChecks = 0;
    int NumWritePtrChecks = 0;

    // We assign consecutive id to access from different dependence sets.
    // Accesses within the same set don't need a runtime check.
    unsigned RunningDepId = 1;
    DenseMap<Value *, unsigned> DepSetId;

    for (auto A : AS) {
      Value *Ptr = A.getValue();
      bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true));
      MemAccessInfo Access(Ptr, IsWrite);

      if (IsWrite)
        ++NumWritePtrChecks;
      else
        ++NumReadPtrChecks;

      if (hasComputableBounds(SE, StridesMap, Ptr) &&
          // When we run after a failing dependency check we have to make sure
          // we don't have wrapping pointers.
          (!ShouldCheckStride ||
           isStridedPtr(SE, Ptr, TheLoop, StridesMap) == 1)) {
        // The id of the dependence set.
        unsigned DepId;

        if (IsDepCheckNeeded) {
          Value *Leader = DepCands.getLeaderValue(Access).getPointer();
          unsigned &LeaderId = DepSetId[Leader];
          if (!LeaderId)
            LeaderId = RunningDepId++;
          DepId = LeaderId;
        } else
          // Each access has its own dependence set.
          DepId = RunningDepId++;

        RtCheck.insert(TheLoop, Ptr, IsWrite, DepId, ASId, StridesMap);

        DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
      } else {
        DEBUG(dbgs() << "LAA: Can't find bounds for ptr:" << *Ptr << '\n');
        CanDoRT = false;
      }
    }

    // If we have at least two writes or one write and a read then we need to
    // check them.  But there is no need to checks if there is only one
    // dependence set for this alias set.
    //
    // Note that this function computes CanDoRT and NeedRTCheck independently.
    // For example CanDoRT=false, NeedRTCheck=false means that we have a pointer
    // for which we couldn't find the bounds but we don't actually need to emit
    // any checks so it does not matter.
    if (!(IsDepCheckNeeded && CanDoRT && RunningDepId == 2))
      NeedRTCheck |= (NumWritePtrChecks >= 2 || (NumReadPtrChecks >= 1 &&
                                                 NumWritePtrChecks >= 1));

    ++ASId;
  }

  // If the pointers that we would use for the bounds comparison have different
  // address spaces, assume the values aren't directly comparable, so we can't
  // use them for the runtime check. We also have to assume they could
  // overlap. In the future there should be metadata for whether address spaces
  // are disjoint.
  unsigned NumPointers = RtCheck.Pointers.size();
  for (unsigned i = 0; i < NumPointers; ++i) {
    for (unsigned j = i + 1; j < NumPointers; ++j) {
      // Only need to check pointers between two different dependency sets.
      if (RtCheck.DependencySetId[i] == RtCheck.DependencySetId[j])
       continue;
      // Only need to check pointers in the same alias set.
      if (RtCheck.AliasSetId[i] != RtCheck.AliasSetId[j])
        continue;

      Value *PtrI = RtCheck.Pointers[i];
      Value *PtrJ = RtCheck.Pointers[j];

      unsigned ASi = PtrI->getType()->getPointerAddressSpace();
      unsigned ASj = PtrJ->getType()->getPointerAddressSpace();
      if (ASi != ASj) {
        DEBUG(dbgs() << "LAA: Runtime check would require comparison between"
                       " different address spaces\n");
        return false;
      }
    }
  }

  if (NeedRTCheck && CanDoRT)
    RtCheck.groupChecks(DepCands, IsDepCheckNeeded);

  return CanDoRT;
}

void AccessAnalysis::processMemAccesses() {
  // We process the set twice: first we process read-write pointers, last we
  // process read-only pointers. This allows us to skip dependence tests for
  // read-only pointers.

  DEBUG(dbgs() << "LAA: Processing memory accesses...\n");
  DEBUG(dbgs() << "  AST: "; AST.dump());
  DEBUG(dbgs() << "LAA:   Accesses(" << Accesses.size() << "):\n");
  DEBUG({
    for (auto A : Accesses)
      dbgs() << "\t" << *A.getPointer() << " (" <<
                (A.getInt() ? "write" : (ReadOnlyPtr.count(A.getPointer()) ?
                                         "read-only" : "read")) << ")\n";
  });

  // The AliasSetTracker has nicely partitioned our pointers by metadata
  // compatibility and potential for underlying-object overlap. As a result, we
  // only need to check for potential pointer dependencies within each alias
  // set.
  for (auto &AS : AST) {
    // Note that both the alias-set tracker and the alias sets themselves used
    // linked lists internally and so the iteration order here is deterministic
    // (matching the original instruction order within each set).

    bool SetHasWrite = false;

    // Map of pointers to last access encountered.
    typedef DenseMap<Value*, MemAccessInfo> UnderlyingObjToAccessMap;
    UnderlyingObjToAccessMap ObjToLastAccess;

    // Set of access to check after all writes have been processed.
    PtrAccessSet DeferredAccesses;

    // Iterate over each alias set twice, once to process read/write pointers,
    // and then to process read-only pointers.
    for (int SetIteration = 0; SetIteration < 2; ++SetIteration) {
      bool UseDeferred = SetIteration > 0;
      PtrAccessSet &S = UseDeferred ? DeferredAccesses : Accesses;

      for (auto AV : AS) {
        Value *Ptr = AV.getValue();

        // For a single memory access in AliasSetTracker, Accesses may contain
        // both read and write, and they both need to be handled for CheckDeps.
        for (auto AC : S) {
          if (AC.getPointer() != Ptr)
            continue;

          bool IsWrite = AC.getInt();

          // If we're using the deferred access set, then it contains only
          // reads.
          bool IsReadOnlyPtr = ReadOnlyPtr.count(Ptr) && !IsWrite;
          if (UseDeferred && !IsReadOnlyPtr)
            continue;
          // Otherwise, the pointer must be in the PtrAccessSet, either as a
          // read or a write.
          assert(((IsReadOnlyPtr && UseDeferred) || IsWrite ||
                  S.count(MemAccessInfo(Ptr, false))) &&
                 "Alias-set pointer not in the access set?");

          MemAccessInfo Access(Ptr, IsWrite);
          DepCands.insert(Access);

          // Memorize read-only pointers for later processing and skip them in
          // the first round (they need to be checked after we have seen all
          // write pointers). Note: we also mark pointer that are not
          // consecutive as "read-only" pointers (so that we check
          // "a[b[i]] +="). Hence, we need the second check for "!IsWrite".
          if (!UseDeferred && IsReadOnlyPtr) {
            DeferredAccesses.insert(Access);
            continue;
          }

          // If this is a write - check other reads and writes for conflicts. If
          // this is a read only check other writes for conflicts (but only if
          // there is no other write to the ptr - this is an optimization to
          // catch "a[i] = a[i] + " without having to do a dependence check).
          if ((IsWrite || IsReadOnlyPtr) && SetHasWrite) {
            CheckDeps.insert(Access);
            IsRTCheckAnalysisNeeded = true;
          }

          if (IsWrite)
            SetHasWrite = true;

          // Create sets of pointers connected by a shared alias set and
          // underlying object.
          typedef SmallVector<Value *, 16> ValueVector;
          ValueVector TempObjects;

          GetUnderlyingObjects(Ptr, TempObjects, DL, LI);
          DEBUG(dbgs() << "Underlying objects for pointer " << *Ptr << "\n");
          for (Value *UnderlyingObj : TempObjects) {
            UnderlyingObjToAccessMap::iterator Prev =
                ObjToLastAccess.find(UnderlyingObj);
{'fraction_non_alphanumeric': 0.11587932874187604, 'fraction_numerical': 0.0029100785721214474, 'mean_word_length': 2.7038154774735936, 'pattern_counts': {'":': 8, '<': 319, '<?xml version=': 0, '>': 113, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 32, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3205202', 'n_tokens_mistral': 15233, 'n_tokens_neox': 14567, 'n_words': 4870}