/build/llvm-toolchain-snapshot-14~++20220125101009+ceec4383681c/llvm/include/llvm/ADT/PointerIntPair.h

Bug Summary

File:	llvm/include/llvm/ADT/PointerIntPair.h
Warning:	line 189, column 52 The result of the left shift is undefined due to shifting '0' by '2', which is unrepresentable in the unsigned version of the return type 'intptr_t'

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name LoopAccessAnalysis.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20220125101009+ceec4383681c/build-llvm -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Analysis -I /build/llvm-toolchain-snapshot-14~++20220125101009+ceec4383681c/llvm/lib/Analysis -I include -I /build/llvm-toolchain-snapshot-14~++20220125101009+ceec4383681c/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220125101009+ceec4383681c/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220125101009+ceec4383681c/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220125101009+ceec4383681c/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220125101009+ceec4383681c/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20220125101009+ceec4383681c/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220125101009+ceec4383681c/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220125101009+ceec4383681c/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-01-25-232935-20746-1 -x c++ /build/llvm-toolchain-snapshot-14~++20220125101009+ceec4383681c/llvm/lib/Analysis/LoopAccessAnalysis.cpp

/build/llvm-toolchain-snapshot-14~++20220125101009+ceec4383681c/llvm/lib/Analysis/LoopAccessAnalysis.cpp

→

1//===- LoopAccessAnalysis.cpp - Loop Access Analysis Implementation --------==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// The implementation for the loop memory dependence that was originally
10// developed for the loop vectorizer.
11//
12//===----------------------------------------------------------------------===//

14#include "llvm/Analysis/LoopAccessAnalysis.h"
15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/DepthFirstIterator.h"
18#include "llvm/ADT/EquivalenceClasses.h"
19#include "llvm/ADT/PointerIntPair.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/SetVector.h"
22#include "llvm/ADT/SmallPtrSet.h"
23#include "llvm/ADT/SmallSet.h"
24#include "llvm/ADT/SmallVector.h"
25#include "llvm/ADT/iterator_range.h"
26#include "llvm/Analysis/AliasAnalysis.h"
27#include "llvm/Analysis/AliasSetTracker.h"
28#include "llvm/Analysis/LoopAnalysisManager.h"
29#include "llvm/Analysis/LoopInfo.h"
30#include "llvm/Analysis/MemoryLocation.h"
31#include "llvm/Analysis/OptimizationRemarkEmitter.h"
32#include "llvm/Analysis/ScalarEvolution.h"
33#include "llvm/Analysis/ScalarEvolutionExpressions.h"
34#include "llvm/Analysis/TargetLibraryInfo.h"
35#include "llvm/Analysis/ValueTracking.h"
36#include "llvm/Analysis/VectorUtils.h"
37#include "llvm/IR/BasicBlock.h"
38#include "llvm/IR/Constants.h"
39#include "llvm/IR/DataLayout.h"
40#include "llvm/IR/DebugLoc.h"
41#include "llvm/IR/DerivedTypes.h"
42#include "llvm/IR/DiagnosticInfo.h"
43#include "llvm/IR/Dominators.h"
44#include "llvm/IR/Function.h"
45#include "llvm/IR/InstrTypes.h"
46#include "llvm/IR/Instruction.h"
47#include "llvm/IR/Instructions.h"
48#include "llvm/IR/Operator.h"
49#include "llvm/IR/PassManager.h"
50#include "llvm/IR/Type.h"
51#include "llvm/IR/Value.h"
52#include "llvm/IR/ValueHandle.h"
53#include "llvm/InitializePasses.h"
54#include "llvm/Pass.h"
55#include "llvm/Support/Casting.h"
56#include "llvm/Support/CommandLine.h"
57#include "llvm/Support/Debug.h"
58#include "llvm/Support/ErrorHandling.h"
59#include "llvm/Support/raw_ostream.h"
60#include <algorithm>
61#include <cassert>
62#include <cstdint>
63#include <cstdlib>
64#include <iterator>
65#include <utility>
66#include <vector>

68using namespace llvm;

70#define DEBUG_TYPE"loop-accesses" "loop-accesses"

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

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

86static 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));
91unsigned VectorizerParams::RuntimeMemoryCheckThreshold;

93/// The maximum iterations used to merge memory checks
94static 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));

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

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

110/// This enables versioning on the strides of symbolically striding memory
111/// accesses in code like the following.
112///   for (i = 0; i < N; ++i)
113///     A[i * Stride1] += B[i * Stride2] ...
114///
115/// Will be roughly translated to
116///    if (Stride1 == 1 && Stride2 == 1) {
117///      for (i = 0; i < N; i+=4)
118///       A[i:i+3] += ...
119///    } else
120///      ...
121static cl::opt<bool> EnableMemAccessVersioning(
  "enable-mem-access-versioning", cl::init(true), cl::Hidden,
  cl::desc("Enable symbolic stride memory access versioning"));

125/// Enable store-to-load forwarding conflict detection. This option can
126/// be disabled for correctness testing.
127static cl::opt<bool> EnableForwardingConflictDetection(
  "store-to-load-forwarding-conflict-detection", cl::Hidden,
  cl::desc("Enable conflict detection in loop-access analysis"),
  cl::init(true));

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

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

143const SCEV *llvm::replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
                                          const ValueToValueMap &PtrToStride,
                                          Value *Ptr) {
const SCEV *OrigSCEV = PSE.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(Ptr);
if (SI == PtrToStride.end())
  // For a non-symbolic stride, just return the original expression.
  return OrigSCEV;

Value *StrideVal = stripIntegerCast(SI->second);

ScalarEvolution *SE = PSE.getSE();
const auto *U = cast<SCEVUnknown>(SE->getSCEV(StrideVal));
const auto *CT =
  static_cast<const SCEVConstant *>(SE->getOne(StrideVal->getType()));

PSE.addPredicate(*SE->getEqualPredicate(U, CT));
auto *Expr = PSE.getSCEV(Ptr);

LLVM_DEBUG(dbgs() << "LAA: Replacing SCEV: " << *OrigSCEVdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Replacing SCEV: " <<
 *OrigSCEV << " by: " << *Expr << "\n"; } }
 while (false)
    << " by: " << *Expr << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Replacing SCEV: " <<
 *OrigSCEV << " by: " << *Expr << "\n"; } }
 while (false);
return Expr;
168}

170RuntimeCheckingPtrGroup::RuntimeCheckingPtrGroup(
  unsigned Index, RuntimePointerChecking &RtCheck)
  : High(RtCheck.Pointers[Index].End), Low(RtCheck.Pointers[Index].Start),
    AddressSpace(RtCheck.Pointers[Index]
                     .PointerValue->getType()
                     ->getPointerAddressSpace()) {
Members.push_back(Index);
177}

179/// Calculate Start and End points of memory access.
180/// Let's assume A is the first access and B is a memory access on N-th loop
181/// iteration. Then B is calculated as:
182///   B = A + Step*N .
183/// Step value may be positive or negative.
184/// N is a calculated back-edge taken count:
185///     N = (TripCount > 0) ? RoundDown(TripCount -1 , VF) : 0
186/// Start and End points are calculated in the following way:
187/// Start = UMIN(A, B) ; End = UMAX(A, B) + SizeOfElt,
188/// where SizeOfElt is the size of single memory access in bytes.
189///
190/// There is no conflict when the intervals are disjoint:
191/// NoConflict = (P2.Start >= P1.End) || (P1.Start >= P2.End)
192void RuntimePointerChecking::insert(Loop *Lp, Value *Ptr, bool WritePtr,
                                  unsigned DepSetId, unsigned ASId,
                                  const ValueToValueMap &Strides,
                                  PredicatedScalarEvolution &PSE) {
// Get the stride replaced scev.
const SCEV *Sc = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);
ScalarEvolution *SE = PSE.getSE();

const SCEV *ScStart;
const SCEV *ScEnd;

if (SE->isLoopInvariant(Sc, Lp)) {
  ScStart = ScEnd = Sc;
} else {
  const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
  assert(AR && "Invalid addrec expression")(static_cast <bool> (AR && "Invalid addrec expression"
) ? void (0) : __assert_fail ("AR && \"Invalid addrec expression\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 207, __extension__
 __PRETTY_FUNCTION__));
  const SCEV *Ex = PSE.getBackedgeTakenCount();

  ScStart = AR->getStart();
  ScEnd = AR->evaluateAtIteration(Ex, *SE);
  const SCEV *Step = AR->getStepRecurrence(*SE);

  // For expressions with negative step, the upper bound is ScStart and the
  // lower bound is ScEnd.
  if (const auto *CStep = dyn_cast<SCEVConstant>(Step)) {
    if (CStep->getValue()->isNegative())
      std::swap(ScStart, ScEnd);
  } else {
    // Fallback case: the step is not constant, but we can still
    // get the upper and lower bounds of the interval by using min/max
    // expressions.
    ScStart = SE->getUMinExpr(ScStart, ScEnd);
    ScEnd = SE->getUMaxExpr(AR->getStart(), ScEnd);
  }
}
// Add the size of the pointed element to ScEnd.
auto &DL = Lp->getHeader()->getModule()->getDataLayout();
Type *IdxTy = DL.getIndexType(Ptr->getType());
const SCEV *EltSizeSCEV =
    SE->getStoreSizeOfExpr(IdxTy, Ptr->getType()->getPointerElementType());
ScEnd = SE->getAddExpr(ScEnd, EltSizeSCEV);

Pointers.emplace_back(Ptr, ScStart, ScEnd, WritePtr, DepSetId, ASId, Sc);
235}

237SmallVector<RuntimePointerCheck, 4>
238RuntimePointerChecking::generateChecks() const {
SmallVector<RuntimePointerCheck, 4> Checks;

for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
  for (unsigned J = I + 1; J < CheckingGroups.size(); ++J) {
    const RuntimeCheckingPtrGroup &CGI = CheckingGroups[I];
    const RuntimeCheckingPtrGroup &CGJ = CheckingGroups[J];

    if (needsChecking(CGI, CGJ))
      Checks.push_back(std::make_pair(&CGI, &CGJ));
  }
}
return Checks;
251}

253void RuntimePointerChecking::generateChecks(
  MemoryDepChecker::DepCandidates &DepCands, bool UseDependencies) {
assert(Checks.empty() && "Checks is not empty")(static_cast <bool> (Checks.empty() && "Checks is not empty"
) ? void (0) : __assert_fail ("Checks.empty() && \"Checks is not empty\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 255, __extension__
 __PRETTY_FUNCTION__));
groupChecks(DepCands, UseDependencies);
Checks = generateChecks();
258}

260bool RuntimePointerChecking::needsChecking(
  const RuntimeCheckingPtrGroup &M, const RuntimeCheckingPtrGroup &N) 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]))
      return true;
return false;
267}

269/// Compare \p I and \p J and return the minimum.
270/// Return nullptr in case we couldn't find an answer.
271static 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;
281}

283bool RuntimeCheckingPtrGroup::addPointer(unsigned Index,
                                       RuntimePointerChecking &RtCheck) {
return addPointer(
    Index, RtCheck.Pointers[Index].Start, RtCheck.Pointers[Index].End,
    RtCheck.Pointers[Index].PointerValue->getType()->getPointerAddressSpace(),
    *RtCheck.SE);
289}

291bool RuntimeCheckingPtrGroup::addPointer(unsigned Index, const SCEV *Start,
                                       const SCEV *End, unsigned AS,
                                       ScalarEvolution &SE) {
assert(AddressSpace == AS &&(static_cast <bool> (AddressSpace == AS && "all pointers in a checking group must be in the same address space"
) ? void (0) : __assert_fail ("AddressSpace == AS && \"all pointers in a checking group must be in the same address space\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 295, __extension__
 __PRETTY_FUNCTION__))
       "all pointers in a checking group must be in the same address space")(static_cast <bool> (AddressSpace == AS && "all pointers in a checking group must be in the same address space"
) ? void (0) : __assert_fail ("AddressSpace == AS && \"all pointers in a checking group must be in the same address space\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 295, __extension__
 __PRETTY_FUNCTION__));

// 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(Start, Low, &SE);
if (!Min0)
  return false;

const SCEV *Min1 = getMinFromExprs(End, High, &SE);
if (!Min1)
  return false;

// Update the low bound  expression if we've found a new min value.
if (Min0 == Start)
  Low = Start;

// Update the high bound expression if we've found a new max value.
if (Min1 != End)
  High = End;

Members.push_back(Index);
return true;
318}

320void RuntimePointerChecking::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 need to check two pointers to the same underlying object
// with a non-constant difference, we shouldn't perform any pointer
// grouping with those pointers. This is because we can easily get
// into cases where the resulting check would return false, even when
// the accesses are safe.
//
// The following example shows this:
// for (i = 0; i < 1000; ++i)
//   a[5000 + i * m] = a[i] + a[i + 9000]
//
// Here grouping gives a check of (5000, 5000 + 1000 * m) against
// (0, 10000) which is always false. However, if m is 1, there is no
// dependence. Not grouping the checks for a[i] and a[i + 9000] allows
// us to perform an accurate check in this case.
//
// The above case requires that we have an UnknownDependence between
// accesses to the same underlying object. This cannot happen unless
// FoundNonConstantDistanceDependence is set, and therefore UseDependencies
// is also false. In this case we will use the fallback path and create
// separate checking groups for all pointers.

// If we don't have the dependency partitions, construct a new
// checking pointer group for each pointer. This is also required
// for correctness, because in this case we can have checking between
// pointers to the same underlying object.
if (!UseDependencies) {
  for (unsigned I = 0; I < Pointers.size(); ++I)
    CheckingGroups.push_back(RuntimeCheckingPtrGroup(I, *this));
  return;
}

unsigned TotalComparisons = 0;

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

// We need to keep track of what pointers we've already seen so we
// don't process them twice.
SmallSet<unsigned, 2> Seen;

// Go through all equivalence classes, get the "pointer check groups"
// and add them to the overall solution. We use the order in which accesses
// appear in 'Pointers' to enforce determinism.
for (unsigned I = 0; I < Pointers.size(); ++I) {
  // We've seen this pointer before, and therefore already processed
  // its equivalence class.
  if (Seen.count(I))
    continue;

  MemoryDepChecker::MemAccessInfo Access(Pointers[I].PointerValue,
                                         Pointers[I].IsWritePtr);

  SmallVector<RuntimeCheckingPtrGroup, 2> Groups;
  auto LeaderI = DepCands.findValue(DepCands.getLeaderValue(Access));

  // Because DepCands is constructed by visiting accesses in the order in
  // which they appear in alias sets (which is deterministic) and the
  // iteration order within an equivalence class member is only dependent on
  // the order in which unions and insertions are performed on the
  // equivalence class, the iteration order is deterministic.
  for (auto MI = DepCands.member_begin(LeaderI), ME = DepCands.member_end();
       MI != ME; ++MI) {
    auto PointerI = PositionMap.find(MI->getPointer());
    assert(PointerI != PositionMap.end() &&(static_cast <bool> (PointerI != PositionMap.end() &&
 "pointer in equivalence class not found in PositionMap") ? void
 (0) : __assert_fail ("PointerI != PositionMap.end() && \"pointer in equivalence class not found in PositionMap\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 406, __extension__
 __PRETTY_FUNCTION__))
           "pointer in equivalence class not found in PositionMap")(static_cast <bool> (PointerI != PositionMap.end() &&
 "pointer in equivalence class not found in PositionMap") ? void
 (0) : __assert_fail ("PointerI != PositionMap.end() && \"pointer in equivalence class not found in PositionMap\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 406, __extension__
 __PRETTY_FUNCTION__));
    unsigned Pointer = PointerI->second;
    bool Merged = false;
    // Mark this pointer as seen.
    Seen.insert(Pointer);

    // Go through all the existing sets and see if we can find one
    // which can include this pointer.
    for (RuntimeCheckingPtrGroup &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, *this)) {
        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(RuntimeCheckingPtrGroup(Pointer, *this));
  }

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

443bool RuntimePointerChecking::arePointersInSamePartition(
  const SmallVectorImpl<int> &PtrToPartition, unsigned PtrIdx1,
  unsigned PtrIdx2) {
return (PtrToPartition[PtrIdx1] != -1 &&
        PtrToPartition[PtrIdx1] == PtrToPartition[PtrIdx2]);
448}

450bool RuntimePointerChecking::needsChecking(unsigned I, unsigned J) const {
const PointerInfo &PointerI = Pointers[I];
const PointerInfo &PointerJ = Pointers[J];

// No need to check if two readonly pointers intersect.
if (!PointerI.IsWritePtr && !PointerJ.IsWritePtr)
  return false;

// Only need to check pointers between two different dependency sets.
if (PointerI.DependencySetId == PointerJ.DependencySetId)
  return false;

// Only need to check pointers in the same alias set.
if (PointerI.AliasSetId != PointerJ.AliasSetId)
  return false;

return true;
467}

469void RuntimePointerChecking::printChecks(
  raw_ostream &OS, const SmallVectorImpl<RuntimePointerCheck> &Checks,
  unsigned Depth) const {
unsigned N = 0;
for (const auto &Check : Checks) {
  const auto &First = Check.first->Members, &Second = Check.second->Members;

  OS.indent(Depth) << "Check " << N++ << ":\n";

  OS.indent(Depth + 2) << "Comparing group (" << Check.first << "):\n";
  for (unsigned K = 0; K < First.size(); ++K)
    OS.indent(Depth + 2) << *Pointers[First[K]].PointerValue << "\n";

  OS.indent(Depth + 2) << "Against group (" << Check.second << "):\n";
  for (unsigned K = 0; K < Second.size(); ++K)
    OS.indent(Depth + 2) << *Pointers[Second[K]].PointerValue << "\n";
}
486}

488void RuntimePointerChecking::print(raw_ostream &OS, unsigned Depth) const {

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

OS.indent(Depth) << "Grouped accesses:\n";
for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
  const auto &CG = CheckingGroups[I];

  OS.indent(Depth + 2) << "Group " << &CG << ":\n";
  OS.indent(Depth + 4) << "(Low: " << *CG.Low << " High: " << *CG.High
                       << ")\n";
  for (unsigned J = 0; J < CG.Members.size(); ++J) {
    OS.indent(Depth + 6) << "Member: " << *Pointers[CG.Members[J]].Expr
                         << "\n";
  }
}
505}

507namespace {

509/// Analyses memory accesses in a loop.
510///
511/// Checks whether run time pointer checks are needed and builds sets for data
512/// dependence checking.
513class AccessAnalysis {
514public:
/// Read or write access location.
typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
typedef SmallVector<MemAccessInfo, 8> MemAccessInfoList;

AccessAnalysis(Loop *TheLoop, AAResults *AA, LoopInfo *LI,
               MemoryDepChecker::DepCandidates &DA,
               PredicatedScalarEvolution &PSE)
    : TheLoop(TheLoop), AST(*AA), LI(LI), DepCands(DA), PSE(PSE) {}

/// 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, LocationSize::beforeOrAfterPointer(), Loc.AATags);
  Accesses.insert(MemAccessInfo(Ptr, false));
  if (IsReadOnly)
    ReadOnlyPtr.insert(Ptr);
}

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

/// Check if we can emit a run-time no-alias check for \p Access.
///
/// Returns true if we can emit a run-time no alias check for \p Access.
/// If we can check this access, this also adds it to a dependence set and
/// adds a run-time to check for it to \p RtCheck. If \p Assume is true,
/// we will attempt to use additional run-time checks in order to get
/// the bounds of the pointer.
bool createCheckForAccess(RuntimePointerChecking &RtCheck,
                          MemAccessInfo Access,
                          const ValueToValueMap &Strides,
                          DenseMap<Value *, unsigned> &DepSetId,
                          Loop *TheLoop, unsigned &RunningDepId,
                          unsigned ASId, bool ShouldCheckStride,
                          bool Assume);

/// Check whether we can check the pointers at runtime for
/// non-intersection.
///
/// Returns true if we need no check or if we do and we can generate them
/// (i.e. the pointers have computable bounds).
bool canCheckPtrAtRT(RuntimePointerChecking &RtCheck, ScalarEvolution *SE,
                     Loop *TheLoop, const ValueToValueMap &Strides,
                     bool ShouldCheckWrap = false);

/// Goes over all memory accesses, checks whether a RT check is needed
/// and builds sets of dependent accesses.
void buildDependenceSets() {
  processMemAccesses();
11
←
Calling 'AccessAnalysis::processMemAccesses'→
}

/// 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. FoundNonConstantDistanceDependence).
bool isDependencyCheckNeeded() { return !CheckDeps.empty(); }

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

MemAccessInfoList &getDependenciesToCheck() { return CheckDeps; }

585private:
typedef SetVector<MemAccessInfo> PtrAccessSet;

/// 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;

/// The loop being checked.
const Loop *TheLoop;

/// List of accesses that need a further dependence check.
MemAccessInfoList 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;

/// 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. FoundNonConstantDistanceDependence), isDependencyCheckNeeded is
/// cleared while this remains set if we have potentially dependent accesses.
bool IsRTCheckAnalysisNeeded = false;

/// The SCEV predicate containing all the SCEV-related assumptions.
PredicatedScalarEvolution &PSE;
626};

628} // end anonymous namespace

630/// Check whether a pointer can participate in a runtime bounds check.
631/// If \p Assume, try harder to prove that we can compute the bounds of \p Ptr
632/// by adding run-time checks (overflow checks) if necessary.
633static bool hasComputableBounds(PredicatedScalarEvolution &PSE,
                              const ValueToValueMap &Strides, Value *Ptr,
                              Loop *L, bool Assume) {
const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);

// The bounds for loop-invariant pointer is trivial.
if (PSE.getSE()->isLoopInvariant(PtrScev, L))
  return true;

const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);

if (!AR && Assume)
  AR = PSE.getAsAddRec(Ptr);

if (!AR)
  return false;

return AR->isAffine();
651}

653/// Check whether a pointer address cannot wrap.
654static bool isNoWrap(PredicatedScalarEvolution &PSE,
                   const ValueToValueMap &Strides, Value *Ptr, Loop *L) {
const SCEV *PtrScev = PSE.getSCEV(Ptr);
if (PSE.getSE()->isLoopInvariant(PtrScev, L))
  return true;

Type *AccessTy = Ptr->getType()->getPointerElementType();
int64_t Stride = getPtrStride(PSE, AccessTy, Ptr, L, Strides);
if (Stride == 1 || PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW))
  return true;

return false;
666}

668static void visitPointers(Value *StartPtr, const Loop &InnermostLoop,
                        function_ref<void(Value *)> AddPointer) {
SmallPtrSet<Value *, 8> Visited;
SmallVector<Value *> WorkList;
WorkList.push_back(StartPtr);

while (!WorkList.empty()) {
  Value *Ptr = WorkList.pop_back_val();
  if (!Visited.insert(Ptr).second)
    continue;
  auto *PN = dyn_cast<PHINode>(Ptr);
  // SCEV does not look through non-header PHIs inside the loop. Such phis
  // can be analyzed by adding separate accesses for each incoming pointer
  // value.
  if (PN && InnermostLoop.contains(PN->getParent()) &&
      PN->getParent() != InnermostLoop.getHeader()) {
    for (const Use &Inc : PN->incoming_values())
      WorkList.push_back(Inc);
  } else
    AddPointer(Ptr);
}
689}

691bool AccessAnalysis::createCheckForAccess(RuntimePointerChecking &RtCheck,
                                        MemAccessInfo Access,
                                        const ValueToValueMap &StridesMap,
                                        DenseMap<Value *, unsigned> &DepSetId,
                                        Loop *TheLoop, unsigned &RunningDepId,
                                        unsigned ASId, bool ShouldCheckWrap,
                                        bool Assume) {
Value *Ptr = Access.getPointer();

if (!hasComputableBounds(PSE, StridesMap, Ptr, TheLoop, Assume))
  return false;

// When we run after a failing dependency check we have to make sure
// we don't have wrapping pointers.
if (ShouldCheckWrap && !isNoWrap(PSE, StridesMap, Ptr, TheLoop)) {
  auto *Expr = PSE.getSCEV(Ptr);
  if (!Assume || !isa<SCEVAddRecExpr>(Expr))
    return false;
  PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
}

// The id of the dependence set.
unsigned DepId;

if (isDependencyCheckNeeded()) {
  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++;

bool IsWrite = Access.getInt();
RtCheck.insert(TheLoop, Ptr, IsWrite, DepId, ASId, StridesMap, PSE);
LLVM_DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Found a runtime check ptr:"
 << *Ptr << '\n'; } } while (false);

return true;
}

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

bool MayNeedRTCheck = 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 = 0;
for (auto &AS : AST) {
  int NumReadPtrChecks = 0;
  int NumWritePtrChecks = 0;
  bool CanDoAliasSetRT = true;
  ++ASId;

  // 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;

  SmallVector<MemAccessInfo, 4> Retries;

  // First, count how many write and read accesses are in the alias set. Also
  // collect MemAccessInfos for later.
  SmallVector<MemAccessInfo, 4> AccessInfos;
  for (const auto &A : AS) {
    Value *Ptr = A.getValue();
    bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true));

    if (IsWrite)
      ++NumWritePtrChecks;
    else
      ++NumReadPtrChecks;
    AccessInfos.emplace_back(Ptr, IsWrite);
  }

  // We do not need runtime checks for this alias set, if there are no writes
  // or a single write and no reads.
  if (NumWritePtrChecks == 0 ||
      (NumWritePtrChecks == 1 && NumReadPtrChecks == 0)) {
    assert((AS.size() <= 1 ||(static_cast <bool> ((AS.size() <= 1 || all_of(AS, [
this](auto AC) { MemAccessInfo AccessWrite(AC.getValue(), true
); return DepCands.findValue(AccessWrite) == DepCands.end(); }
)) && "Can only skip updating CanDoRT below, if all entries in AS "
 "are reads or there is at most 1 entry") ? void (0) : __assert_fail
 ("(AS.size() <= 1 || all_of(AS, [this](auto AC) { MemAccessInfo AccessWrite(AC.getValue(), true); return DepCands.findValue(AccessWrite) == DepCands.end(); })) && \"Can only skip updating CanDoRT below, if all entries in AS \" \"are reads or there is at most 1 entry\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 786, __extension__
 __PRETTY_FUNCTION__))
            all_of(AS,(static_cast <bool> ((AS.size() <= 1 || all_of(AS, [
this](auto AC) { MemAccessInfo AccessWrite(AC.getValue(), true
); return DepCands.findValue(AccessWrite) == DepCands.end(); }
)) && "Can only skip updating CanDoRT below, if all entries in AS "
 "are reads or there is at most 1 entry") ? void (0) : __assert_fail
 ("(AS.size() <= 1 || all_of(AS, [this](auto AC) { MemAccessInfo AccessWrite(AC.getValue(), true); return DepCands.findValue(AccessWrite) == DepCands.end(); })) && \"Can only skip updating CanDoRT below, if all entries in AS \" \"are reads or there is at most 1 entry\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 786, __extension__
 __PRETTY_FUNCTION__))
                   [this](auto AC) {(static_cast <bool> ((AS.size() <= 1 || all_of(AS, [
this](auto AC) { MemAccessInfo AccessWrite(AC.getValue(), true
); return DepCands.findValue(AccessWrite) == DepCands.end(); }
)) && "Can only skip updating CanDoRT below, if all entries in AS "
 "are reads or there is at most 1 entry") ? void (0) : __assert_fail
 ("(AS.size() <= 1 || all_of(AS, [this](auto AC) { MemAccessInfo AccessWrite(AC.getValue(), true); return DepCands.findValue(AccessWrite) == DepCands.end(); })) && \"Can only skip updating CanDoRT below, if all entries in AS \" \"are reads or there is at most 1 entry\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 786, __extension__
 __PRETTY_FUNCTION__))
                     MemAccessInfo AccessWrite(AC.getValue(), true);(static_cast <bool> ((AS.size() <= 1 || all_of(AS, [
this](auto AC) { MemAccessInfo AccessWrite(AC.getValue(), true
); return DepCands.findValue(AccessWrite) == DepCands.end(); }
)) && "Can only skip updating CanDoRT below, if all entries in AS "
 "are reads or there is at most 1 entry") ? void (0) : __assert_fail
 ("(AS.size() <= 1 || all_of(AS, [this](auto AC) { MemAccessInfo AccessWrite(AC.getValue(), true); return DepCands.findValue(AccessWrite) == DepCands.end(); })) && \"Can only skip updating CanDoRT below, if all entries in AS \" \"are reads or there is at most 1 entry\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 786, __extension__
 __PRETTY_FUNCTION__))
                     return DepCands.findValue(AccessWrite) == DepCands.end();(static_cast <bool> ((AS.size() <= 1 || all_of(AS, [
this](auto AC) { MemAccessInfo AccessWrite(AC.getValue(), true
); return DepCands.findValue(AccessWrite) == DepCands.end(); }
)) && "Can only skip updating CanDoRT below, if all entries in AS "
 "are reads or there is at most 1 entry") ? void (0) : __assert_fail
 ("(AS.size() <= 1 || all_of(AS, [this](auto AC) { MemAccessInfo AccessWrite(AC.getValue(), true); return DepCands.findValue(AccessWrite) == DepCands.end(); })) && \"Can only skip updating CanDoRT below, if all entries in AS \" \"are reads or there is at most 1 entry\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 786, __extension__
 __PRETTY_FUNCTION__))
                   })) &&(static_cast <bool> ((AS.size() <= 1 || all_of(AS, [
this](auto AC) { MemAccessInfo AccessWrite(AC.getValue(), true
); return DepCands.findValue(AccessWrite) == DepCands.end(); }
)) && "Can only skip updating CanDoRT below, if all entries in AS "
 "are reads or there is at most 1 entry") ? void (0) : __assert_fail
 ("(AS.size() <= 1 || all_of(AS, [this](auto AC) { MemAccessInfo AccessWrite(AC.getValue(), true); return DepCands.findValue(AccessWrite) == DepCands.end(); })) && \"Can only skip updating CanDoRT below, if all entries in AS \" \"are reads or there is at most 1 entry\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 786, __extension__
 __PRETTY_FUNCTION__))
           "Can only skip updating CanDoRT below, if all entries in AS "(static_cast <bool> ((AS.size() <= 1 || all_of(AS, [
this](auto AC) { MemAccessInfo AccessWrite(AC.getValue(), true
); return DepCands.findValue(AccessWrite) == DepCands.end(); }
)) && "Can only skip updating CanDoRT below, if all entries in AS "
 "are reads or there is at most 1 entry") ? void (0) : __assert_fail
 ("(AS.size() <= 1 || all_of(AS, [this](auto AC) { MemAccessInfo AccessWrite(AC.getValue(), true); return DepCands.findValue(AccessWrite) == DepCands.end(); })) && \"Can only skip updating CanDoRT below, if all entries in AS \" \"are reads or there is at most 1 entry\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 786, __extension__
 __PRETTY_FUNCTION__))
           "are reads or there is at most 1 entry")(static_cast <bool> ((AS.size() <= 1 || all_of(AS, [
this](auto AC) { MemAccessInfo AccessWrite(AC.getValue(), true
); return DepCands.findValue(AccessWrite) == DepCands.end(); }
)) && "Can only skip updating CanDoRT below, if all entries in AS "
 "are reads or there is at most 1 entry") ? void (0) : __assert_fail
 ("(AS.size() <= 1 || all_of(AS, [this](auto AC) { MemAccessInfo AccessWrite(AC.getValue(), true); return DepCands.findValue(AccessWrite) == DepCands.end(); })) && \"Can only skip updating CanDoRT below, if all entries in AS \" \"are reads or there is at most 1 entry\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 786, __extension__
 __PRETTY_FUNCTION__));
    continue;
  }

  for (auto &Access : AccessInfos) {
    if (!createCheckForAccess(RtCheck, Access, StridesMap, DepSetId, TheLoop,
                              RunningDepId, ASId, ShouldCheckWrap, false)) {
      LLVM_DEBUG(dbgs() << "LAA: Can't find bounds for ptr:"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Can't find bounds for ptr:"
 << *Access.getPointer() << '\n'; } } while (false
)
                        << *Access.getPointer() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Can't find bounds for ptr:"
 << *Access.getPointer() << '\n'; } } while (false
);
      Retries.push_back(Access);
      CanDoAliasSetRT = false;
    }
  }

  // Note that this function computes CanDoRT and MayNeedRTCheck
  // independently. For example CanDoRT=false, MayNeedRTCheck=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.
  //
  // We need runtime checks for this alias set, if there are at least 2
  // dependence sets (in which case RunningDepId > 2) or if we need to re-try
  // any bound checks (because in that case the number of dependence sets is
  // incomplete).
  bool NeedsAliasSetRTCheck = RunningDepId > 2 || !Retries.empty();

  // We need to perform run-time alias checks, but some pointers had bounds
  // that couldn't be checked.
  if (NeedsAliasSetRTCheck && !CanDoAliasSetRT) {
    // Reset the CanDoSetRt flag and retry all accesses that have failed.
    // We know that we need these checks, so we can now be more aggressive
    // and add further checks if required (overflow checks).
    CanDoAliasSetRT = true;
    for (auto Access : Retries)
      if (!createCheckForAccess(RtCheck, Access, StridesMap, DepSetId,
                                TheLoop, RunningDepId, ASId,
                                ShouldCheckWrap, /*Assume=*/true)) {
        CanDoAliasSetRT = false;
        break;
      }
  }

  CanDoRT &= CanDoAliasSetRT;
  MayNeedRTCheck |= NeedsAliasSetRTCheck;
  ++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.Pointers[i].DependencySetId ==
        RtCheck.Pointers[j].DependencySetId)
     continue;
    // Only need to check pointers in the same alias set.
    if (RtCheck.Pointers[i].AliasSetId != RtCheck.Pointers[j].AliasSetId)
      continue;

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

    unsigned ASi = PtrI->getType()->getPointerAddressSpace();
    unsigned ASj = PtrJ->getType()->getPointerAddressSpace();
    if (ASi != ASj) {
      LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Runtime check would require comparison between"
 " different address spaces\n"; } } while (false)
          dbgs() << "LAA: Runtime check would require comparison between"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Runtime check would require comparison between"
 " different address spaces\n"; } } while (false)
                    " different address spaces\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Runtime check would require comparison between"
 " different address spaces\n"; } } while (false);
      return false;
    }
  }
}

if (MayNeedRTCheck && CanDoRT)
  RtCheck.generateChecks(DepCands, IsDepCheckNeeded);

LLVM_DEBUG(dbgs() << "LAA: We need to do " << RtCheck.getNumberOfChecks()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: We need to do " <<
 RtCheck.getNumberOfChecks() << " pointer comparisons.\n"
; } } while (false)
                  << " pointer comparisons.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: We need to do " <<
 RtCheck.getNumberOfChecks() << " pointer comparisons.\n"
; } } while (false);

// If we can do run-time checks, but there are no checks, no runtime checks
// are needed. This can happen when all pointers point to the same underlying
// object for example.
RtCheck.Need = CanDoRT ? RtCheck.getNumberOfChecks() != 0 : MayNeedRTCheck;

bool CanDoRTIfNeeded = !RtCheck.Need || CanDoRT;
if (!CanDoRTIfNeeded)
  RtCheck.reset();
return CanDoRTIfNeeded;
877}

879void 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.

LLVM_DEBUG(dbgs() << "LAA: Processing memory accesses...\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Processing memory accesses...\n"
; } } while (false);
12
←
Assuming 'DebugFlag' is false→
LLVM_DEBUG(dbgs() << "  AST: "; AST.dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "  AST: "; AST.dump(); }
 } while (false);
13
←
Loop condition is false.  Exiting loop→
LLVM_DEBUG(dbgs() << "LAA:   Accesses(" << Accesses.size() << "):\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA:   Accesses(" <<
 Accesses.size() << "):\n"; } } while (false);
14
←
Loop condition is false.  Exiting loop→
LLVM_DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { { for (auto A : Accesses) dbgs() <<
 "\t" << *A.getPointer() << " (" << (A.getInt
() ? "write" : (ReadOnlyPtr.count(A.getPointer()) ? "read-only"
 : "read")) << ")\n"; }; } } while (false)
15
←
Loop condition is false.  Exiting loop→
16
←
Loop condition is false.  Exiting loop→
  for (auto A : Accesses)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { { for (auto A : Accesses) dbgs() <<
 "\t" << *A.getPointer() << " (" << (A.getInt
() ? "write" : (ReadOnlyPtr.count(A.getPointer()) ? "read-only"
 : "read")) << ")\n"; }; } } while (false)
    dbgs() << "\t" << *A.getPointer() << " (" <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { { for (auto A : Accesses) dbgs() <<
 "\t" << *A.getPointer() << " (" << (A.getInt
() ? "write" : (ReadOnlyPtr.count(A.getPointer()) ? "read-only"
 : "read")) << ")\n"; }; } } while (false)
              (A.getInt() ? "write" : (ReadOnlyPtr.count(A.getPointer()) ?do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { { for (auto A : Accesses) dbgs() <<
 "\t" << *A.getPointer() << " (" << (A.getInt
() ? "write" : (ReadOnlyPtr.count(A.getPointer()) ? "read-only"
 : "read")) << ")\n"; }; } } while (false)
                                       "read-only" : "read")) << ")\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { { for (auto A : Accesses) dbgs() <<
 "\t" << *A.getPointer() << " (" << (A.getInt
() ? "write" : (ReadOnlyPtr.count(A.getPointer()) ? "read-only"
 : "read")) << ")\n"; }; } } while (false)
})do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { { for (auto A : Accesses) dbgs() <<
 "\t" << *A.getPointer() << " (" << (A.getInt
() ? "write" : (ReadOnlyPtr.count(A.getPointer()) ? "read-only"
 : "read")) << ")\n"; }; } } while (false);

// 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 (const 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<const 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) {
17
←
Loop condition is true.  Entering loop body→
    bool UseDeferred = SetIteration > 0;
    PtrAccessSet &S = UseDeferred17.1
'UseDeferred' is false
1
'UseDeferred' is false
 ? DeferredAccesses : Accesses;
18
←
'?' condition is false→

    for (const 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 (const auto &AC : S) {
        if (AC.getPointer() != Ptr)
19
←
Assuming the condition is false→
20
←
Taking false branch→
          continue;

        bool IsWrite = AC.getInt();
21
←
'IsWrite' initialized here→

        // If we're using the deferred access set, then it contains only
        // reads.
        bool IsReadOnlyPtr = ReadOnlyPtr.count(Ptr) && !IsWrite;
22
←
Assuming the condition is false→
        if (UseDeferred22.1
'UseDeferred' is false
1
'UseDeferred' is false
 && !IsReadOnlyPtr)
          continue;
        // Otherwise, the pointer must be in the PtrAccessSet, either as a
        // read or a write.
        assert(((IsReadOnlyPtr && UseDeferred) || IsWrite ||(static_cast <bool> (((IsReadOnlyPtr && UseDeferred
) || IsWrite || S.count(MemAccessInfo(Ptr, false))) &&
 "Alias-set pointer not in the access set?") ? void (0) : __assert_fail
 ("((IsReadOnlyPtr && UseDeferred) || IsWrite || S.count(MemAccessInfo(Ptr, false))) && \"Alias-set pointer not in the access set?\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 938, __extension__
 __PRETTY_FUNCTION__))
23
←
Assuming 'IsWrite' is false→
24
←
Assuming the condition is true→
25
←
'?' condition is true→
                S.count(MemAccessInfo(Ptr, false))) &&(static_cast <bool> (((IsReadOnlyPtr && UseDeferred
) || IsWrite || S.count(MemAccessInfo(Ptr, false))) &&
 "Alias-set pointer not in the access set?") ? void (0) : __assert_fail
 ("((IsReadOnlyPtr && UseDeferred) || IsWrite || S.count(MemAccessInfo(Ptr, false))) && \"Alias-set pointer not in the access set?\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 938, __extension__
 __PRETTY_FUNCTION__))
               "Alias-set pointer not in the access set?")(static_cast <bool> (((IsReadOnlyPtr && UseDeferred
) || IsWrite || S.count(MemAccessInfo(Ptr, false))) &&
 "Alias-set pointer not in the access set?") ? void (0) : __assert_fail
 ("((IsReadOnlyPtr && UseDeferred) || IsWrite || S.count(MemAccessInfo(Ptr, false))) && \"Alias-set pointer not in the access set?\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 938, __extension__
 __PRETTY_FUNCTION__));

        MemAccessInfo Access(Ptr, IsWrite);
26
←
Passing value via 2nd parameter 'IntVal'→
27
←
Calling constructor for 'PointerIntPair<llvm::Value *, 1U, bool, llvm::PointerLikeTypeTraits<llvm::Value *>, llvm::PointerIntPairInfo<llvm::Value *, 1, llvm::PointerLikeTypeTraits<llvm::Value *>>>'→
        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.push_back(Access);
          IsRTCheckAnalysisNeeded = true;
        }

        if (IsWrite)
          SetHasWrite = true;

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

        getUnderlyingObjects(Ptr, TempObjects, LI);
        LLVM_DEBUG(dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "Underlying objects for pointer "
 << *Ptr << "\n"; } } while (false)
                   << "Underlying objects for pointer " << *Ptr << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "Underlying objects for pointer "
 << *Ptr << "\n"; } } while (false);
        for (const Value *UnderlyingObj : TempObjects) {
          // nullptr never alias, don't join sets for pointer that have "null"
          // in their UnderlyingObjects list.
          if (isa<ConstantPointerNull>(UnderlyingObj) &&
              !NullPointerIsDefined(
                  TheLoop->getHeader()->getParent(),
                  UnderlyingObj->getType()->getPointerAddressSpace()))
            continue;

          UnderlyingObjToAccessMap::iterator Prev =
              ObjToLastAccess.find(UnderlyingObj);
          if (Prev != ObjToLastAccess.end())
            DepCands.unionSets(Access, Prev->second);

          ObjToLastAccess[UnderlyingObj] = Access;
          LLVM_DEBUG(dbgs() << "  " << *UnderlyingObj << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "  " << *UnderlyingObj
 << "\n"; } } while (false);
        }
      }
    }
  }
}
994}

996static bool isInBoundsGep(Value *Ptr) {
if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr))
  return GEP->isInBounds();
return false;
1000}

1002/// Return true if an AddRec pointer \p Ptr is unsigned non-wrapping,
1003/// i.e. monotonically increasing/decreasing.
1004static bool isNoWrapAddRec(Value *Ptr, const SCEVAddRecExpr *AR,
                         PredicatedScalarEvolution &PSE, const Loop *L) {
// FIXME: This should probably only return true for NUW.
if (AR->getNoWrapFlags(SCEV::NoWrapMask))
  return true;

// Scalar evolution does not propagate the non-wrapping flags to values that
// are derived from a non-wrapping induction variable because non-wrapping
// could be flow-sensitive.
//
// Look through the potentially overflowing instruction to try to prove
// non-wrapping for the *specific* value of Ptr.

// The arithmetic implied by an inbounds GEP can't overflow.
auto *GEP = dyn_cast<GetElementPtrInst>(Ptr);
if (!GEP || !GEP->isInBounds())
  return false;

// Make sure there is only one non-const index and analyze that.
Value *NonConstIndex = nullptr;
for (Value *Index : GEP->indices())
  if (!isa<ConstantInt>(Index)) {
    if (NonConstIndex)
      return false;
    NonConstIndex = Index;
  }
if (!NonConstIndex)
  // The recurrence is on the pointer, ignore for now.
  return false;

// The index in GEP is signed.  It is non-wrapping if it's derived from a NSW
// AddRec using a NSW operation.
if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(NonConstIndex))
  if (OBO->hasNoSignedWrap() &&
      // Assume constant for other the operand so that the AddRec can be
      // easily found.
      isa<ConstantInt>(OBO->getOperand(1))) {
    auto *OpScev = PSE.getSCEV(OBO->getOperand(0));

    if (auto *OpAR = dyn_cast<SCEVAddRecExpr>(OpScev))
      return OpAR->getLoop() == L && OpAR->getNoWrapFlags(SCEV::FlagNSW);
  }

return false;
1048}

1050/// Check whether the access through \p Ptr has a constant stride.
1051int64_t llvm::getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy,
                         Value *Ptr, const Loop *Lp,
                         const ValueToValueMap &StridesMap, bool Assume,
                         bool ShouldCheckWrap) {
Type *Ty = Ptr->getType();
assert(Ty->isPointerTy() && "Unexpected non-ptr")(static_cast <bool> (Ty->isPointerTy() && "Unexpected non-ptr"
) ? void (0) : __assert_fail ("Ty->isPointerTy() && \"Unexpected non-ptr\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 1056, __extension__
 __PRETTY_FUNCTION__));

if (isa<ScalableVectorType>(AccessTy)) {
  LLVM_DEBUG(dbgs() << "LAA: Bad stride - Scalable object: " << *AccessTydo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Bad stride - Scalable object: "
 << *AccessTy << "\n"; } } while (false)
                    << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Bad stride - Scalable object: "
 << *AccessTy << "\n"; } } while (false);
  return 0;
}

const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr);

const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
if (Assume && !AR)
  AR = PSE.getAsAddRec(Ptr);

if (!AR) {
  LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer " << *Ptrdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer "
 << *Ptr << " SCEV: " << *PtrScev << "\n"
; } } while (false)
                    << " SCEV: " << *PtrScev << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer "
 << *Ptr << " SCEV: " << *PtrScev << "\n"
; } } while (false);
  return 0;
}

// The access function must stride over the innermost loop.
if (Lp != AR->getLoop()) {
  LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not striding over innermost loop "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Bad stride - Not striding over innermost loop "
 << *Ptr << " SCEV: " << *AR << "\n";
 } } while (false)
                    << *Ptr << " SCEV: " << *AR << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Bad stride - Not striding over innermost loop "
 << *Ptr << " SCEV: " << *AR << "\n";
 } } while (false);
  return 0;
}

// The address calculation must not wrap. Otherwise, a dependence could be
// inverted.
// An inbounds getelementptr that is a AddRec with a unit stride
// cannot wrap per definition. The unit stride requirement is checked later.
// An getelementptr without an inbounds attribute and unit stride would have
// to access the pointer value "0" which is undefined behavior in address
// space 0, therefore we can also vectorize this case.
unsigned AddrSpace = Ty->getPointerAddressSpace();
bool IsInBoundsGEP = isInBoundsGep(Ptr);
bool IsNoWrapAddRec = !ShouldCheckWrap ||
  PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW) ||
  isNoWrapAddRec(Ptr, AR, PSE, Lp);
if (!IsNoWrapAddRec && !IsInBoundsGEP &&
    NullPointerIsDefined(Lp->getHeader()->getParent(), AddrSpace)) {
  if (Assume) {
    PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
    IsNoWrapAddRec = true;
    LLVM_DEBUG(dbgs() << "LAA: Pointer may wrap in the address space:\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Pointer may wrap in the address space:\n"
 << "LAA:   Pointer: " << *Ptr << "\n" <<
 "LAA:   SCEV: " << *AR << "\n" << "LAA:   Added an overflow assumption\n"
; } } while (false)
                      << "LAA:   Pointer: " << *Ptr << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Pointer may wrap in the address space:\n"
 << "LAA:   Pointer: " << *Ptr << "\n" <<
 "LAA:   SCEV: " << *AR << "\n" << "LAA:   Added an overflow assumption\n"
; } } while (false)
                      << "LAA:   SCEV: " << *AR << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Pointer may wrap in the address space:\n"
 << "LAA:   Pointer: " << *Ptr << "\n" <<
 "LAA:   SCEV: " << *AR << "\n" << "LAA:   Added an overflow assumption\n"
; } } while (false)
                      << "LAA:   Added an overflow assumption\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Pointer may wrap in the address space:\n"
 << "LAA:   Pointer: " << *Ptr << "\n" <<
 "LAA:   SCEV: " << *AR << "\n" << "LAA:   Added an overflow assumption\n"
; } } while (false);
  } else {
    LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Bad stride - Pointer may wrap in the address space "
 << *Ptr << " SCEV: " << *AR << "\n";
 } } while (false)
        dbgs() << "LAA: Bad stride - Pointer may wrap in the address space "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Bad stride - Pointer may wrap in the address space "
 << *Ptr << " SCEV: " << *AR << "\n";
 } } while (false)
               << *Ptr << " SCEV: " << *AR << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Bad stride - Pointer may wrap in the address space "
 << *Ptr << " SCEV: " << *AR << "\n";
 } } while (false);
    return 0;
  }
}

// Check the step is constant.
const SCEV *Step = AR->getStepRecurrence(*PSE.getSE());

// Calculate the pointer stride and check if it is constant.
const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
if (!C) {
  LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not a constant strided " << *Ptrdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Bad stride - Not a constant strided "
 << *Ptr << " SCEV: " << *AR << "\n";
 } } while (false)
                    << " SCEV: " << *AR << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Bad stride - Not a constant strided "
 << *Ptr << " SCEV: " << *AR << "\n";
 } } while (false);
  return 0;
}

auto &DL = Lp->getHeader()->getModule()->getDataLayout();
TypeSize AllocSize = DL.getTypeAllocSize(AccessTy);
int64_t Size = AllocSize.getFixedSize();
const APInt &APStepVal = C->getAPInt();

// Huge step value - give up.
if (APStepVal.getBitWidth() > 64)
  return 0;

int64_t StepVal = APStepVal.getSExtValue();

// Strided access.
int64_t Stride = StepVal / Size;
int64_t Rem = StepVal % Size;
if (Rem)
  return 0;

// If the SCEV could wrap but we have an inbounds gep with a unit stride we
// know we can't "wrap around the address space". In case of address space
// zero we know that this won't happen without triggering undefined behavior.
if (!IsNoWrapAddRec && Stride != 1 && Stride != -1 &&
    (IsInBoundsGEP || !NullPointerIsDefined(Lp->getHeader()->getParent(),
                                            AddrSpace))) {
  if (Assume) {
    // We can avoid this case by adding a run-time check.
    LLVM_DEBUG(dbgs() << "LAA: Non unit strided pointer which is not either "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Non unit strided pointer which is not either "
 << "inbounds or in address space 0 may wrap:\n" <<
 "LAA:   Pointer: " << *Ptr << "\n" << "LAA:   SCEV: "
 << *AR << "\n" << "LAA:   Added an overflow assumption\n"
; } } while (false)
                      << "inbounds or in address space 0 may wrap:\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Non unit strided pointer which is not either "
 << "inbounds or in address space 0 may wrap:\n" <<
 "LAA:   Pointer: " << *Ptr << "\n" << "LAA:   SCEV: "
 << *AR << "\n" << "LAA:   Added an overflow assumption\n"
; } } while (false)
                      << "LAA:   Pointer: " << *Ptr << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Non unit strided pointer which is not either "
 << "inbounds or in address space 0 may wrap:\n" <<
 "LAA:   Pointer: " << *Ptr << "\n" << "LAA:   SCEV: "
 << *AR << "\n" << "LAA:   Added an overflow assumption\n"
; } } while (false)
                      << "LAA:   SCEV: " << *AR << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Non unit strided pointer which is not either "
 << "inbounds or in address space 0 may wrap:\n" <<
 "LAA:   Pointer: " << *Ptr << "\n" << "LAA:   SCEV: "
 << *AR << "\n" << "LAA:   Added an overflow assumption\n"
; } } while (false)
                      << "LAA:   Added an overflow assumption\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Non unit strided pointer which is not either "
 << "inbounds or in address space 0 may wrap:\n" <<
 "LAA:   Pointer: " << *Ptr << "\n" << "LAA:   SCEV: "
 << *AR << "\n" << "LAA:   Added an overflow assumption\n"
; } } while (false);
    PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
  } else
    return 0;
}

return Stride;
1159}

1161Optional<int> llvm::getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB,
                                  Value *PtrB, const DataLayout &DL,
                                  ScalarEvolution &SE, bool StrictCheck,
                                  bool CheckType) {
assert(PtrA && PtrB && "Expected non-nullptr pointers.")(static_cast <bool> (PtrA && PtrB && "Expected non-nullptr pointers."
) ? void (0) : __assert_fail ("PtrA && PtrB && \"Expected non-nullptr pointers.\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 1165, __extension__
 __PRETTY_FUNCTION__));
assert(cast<PointerType>(PtrA->getType())(static_cast <bool> (cast<PointerType>(PtrA->getType
()) ->isOpaqueOrPointeeTypeMatches(ElemTyA) && "Wrong PtrA type"
) ? void (0) : __assert_fail ("cast<PointerType>(PtrA->getType()) ->isOpaqueOrPointeeTypeMatches(ElemTyA) && \"Wrong PtrA type\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 1167, __extension__
 __PRETTY_FUNCTION__))
           ->isOpaqueOrPointeeTypeMatches(ElemTyA) && "Wrong PtrA type")(static_cast <bool> (cast<PointerType>(PtrA->getType
()) ->isOpaqueOrPointeeTypeMatches(ElemTyA) && "Wrong PtrA type"
) ? void (0) : __assert_fail ("cast<PointerType>(PtrA->getType()) ->isOpaqueOrPointeeTypeMatches(ElemTyA) && \"Wrong PtrA type\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 1167, __extension__
 __PRETTY_FUNCTION__));
assert(cast<PointerType>(PtrB->getType())(static_cast <bool> (cast<PointerType>(PtrB->getType
()) ->isOpaqueOrPointeeTypeMatches(ElemTyB) && "Wrong PtrB type"
) ? void (0) : __assert_fail ("cast<PointerType>(PtrB->getType()) ->isOpaqueOrPointeeTypeMatches(ElemTyB) && \"Wrong PtrB type\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 1169, __extension__
 __PRETTY_FUNCTION__))
           ->isOpaqueOrPointeeTypeMatches(ElemTyB) && "Wrong PtrB type")(static_cast <bool> (cast<PointerType>(PtrB->getType
()) ->isOpaqueOrPointeeTypeMatches(ElemTyB) && "Wrong PtrB type"
) ? void (0) : __assert_fail ("cast<PointerType>(PtrB->getType()) ->isOpaqueOrPointeeTypeMatches(ElemTyB) && \"Wrong PtrB type\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 1169, __extension__
 __PRETTY_FUNCTION__));

// Make sure that A and B are different pointers.
if (PtrA == PtrB)
  return 0;

// Make sure that the element types are the same if required.
if (CheckType && ElemTyA != ElemTyB)
  return None;

unsigned ASA = PtrA->getType()->getPointerAddressSpace();
unsigned ASB = PtrB->getType()->getPointerAddressSpace();

// Check that the address spaces match.
if (ASA != ASB)
  return None;
unsigned IdxWidth = DL.getIndexSizeInBits(ASA);

APInt OffsetA(IdxWidth, 0), OffsetB(IdxWidth, 0);
Value *PtrA1 = PtrA->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetA);
Value *PtrB1 = PtrB->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetB);

int Val;
if (PtrA1 == PtrB1) {
  // Retrieve the address space again as pointer stripping now tracks through
  // `addrspacecast`.
  ASA = cast<PointerType>(PtrA1->getType())->getAddressSpace();
  ASB = cast<PointerType>(PtrB1->getType())->getAddressSpace();
  // Check that the address spaces match and that the pointers are valid.
  if (ASA != ASB)
    return None;

  IdxWidth = DL.getIndexSizeInBits(ASA);
  OffsetA = OffsetA.sextOrTrunc(IdxWidth);
  OffsetB = OffsetB.sextOrTrunc(IdxWidth);

  OffsetB -= OffsetA;
  Val = OffsetB.getSExtValue();
} else {
  // Otherwise compute the distance with SCEV between the base pointers.
  const SCEV *PtrSCEVA = SE.getSCEV(PtrA);
  const SCEV *PtrSCEVB = SE.getSCEV(PtrB);
  const auto *Diff =
      dyn_cast<SCEVConstant>(SE.getMinusSCEV(PtrSCEVB, PtrSCEVA));
  if (!Diff)
    return None;
  Val = Diff->getAPInt().getSExtValue();
}
int Size = DL.getTypeStoreSize(ElemTyA);
int Dist = Val / Size;

// Ensure that the calculated distance matches the type-based one after all
// the bitcasts removal in the provided pointers.
if (!StrictCheck || Dist * Size == Val)
  return Dist;
return None;
1225}

1227bool llvm::sortPtrAccesses(ArrayRef<Value *> VL, Type *ElemTy,
                         const DataLayout &DL, ScalarEvolution &SE,
                         SmallVectorImpl<unsigned> &SortedIndices) {
assert(llvm::all_of((static_cast <bool> (llvm::all_of( VL, [](const Value *
V) { return V->getType()->isPointerTy(); }) && "Expected list of pointer operands."
) ? void (0) : __assert_fail ("llvm::all_of( VL, [](const Value *V) { return V->getType()->isPointerTy(); }) && \"Expected list of pointer operands.\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 1232, __extension__
 __PRETTY_FUNCTION__))
           VL, [](const Value *V) { return V->getType()->isPointerTy(); }) &&(static_cast <bool> (llvm::all_of( VL, [](const Value *
V) { return V->getType()->isPointerTy(); }) && "Expected list of pointer operands."
) ? void (0) : __assert_fail ("llvm::all_of( VL, [](const Value *V) { return V->getType()->isPointerTy(); }) && \"Expected list of pointer operands.\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 1232, __extension__
 __PRETTY_FUNCTION__))
       "Expected list of pointer operands.")(static_cast <bool> (llvm::all_of( VL, [](const Value *
V) { return V->getType()->isPointerTy(); }) && "Expected list of pointer operands."
) ? void (0) : __assert_fail ("llvm::all_of( VL, [](const Value *V) { return V->getType()->isPointerTy(); }) && \"Expected list of pointer operands.\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 1232, __extension__
 __PRETTY_FUNCTION__));
// Walk over the pointers, and map each of them to an offset relative to
// first pointer in the array.
Value *Ptr0 = VL[0];

using DistOrdPair = std::pair<int64_t, int>;
auto Compare = [](const DistOrdPair &L, const DistOrdPair &R) {
  return L.first < R.first;
};
std::set<DistOrdPair, decltype(Compare)> Offsets(Compare);
Offsets.emplace(0, 0);
int Cnt = 1;
bool IsConsecutive = true;
for (auto *Ptr : VL.drop_front()) {
  Optional<int> Diff = getPointersDiff(ElemTy, Ptr0, ElemTy, Ptr, DL, SE,
                                       /*StrictCheck=*/true);
  if (!Diff)
    return false;

  // Check if the pointer with the same offset is found.
  int64_t Offset = *Diff;
  auto Res = Offsets.emplace(Offset, Cnt);
  if (!Res.second)
    return false;
  // Consecutive order if the inserted element is the last one.
  IsConsecutive = IsConsecutive && std::next(Res.first) == Offsets.end();
  ++Cnt;
}
SortedIndices.clear();
if (!IsConsecutive) {
  // Fill SortedIndices array only if it is non-consecutive.
  SortedIndices.resize(VL.size());
  Cnt = 0;
  for (const std::pair<int64_t, int> &Pair : Offsets) {
    SortedIndices[Cnt] = Pair.second;
    ++Cnt;
  }
}
return true;
1271}

1273/// Returns true if the memory operations \p A and \p B are consecutive.
1274bool llvm::isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
                             ScalarEvolution &SE, bool CheckType) {
Value *PtrA = getLoadStorePointerOperand(A);
Value *PtrB = getLoadStorePointerOperand(B);
if (!PtrA || !PtrB)
  return false;
Type *ElemTyA = getLoadStoreType(A);
Type *ElemTyB = getLoadStoreType(B);
Optional<int> Diff = getPointersDiff(ElemTyA, PtrA, ElemTyB, PtrB, DL, SE,
                                     /*StrictCheck=*/true, CheckType);
return Diff && *Diff == 1;
1285}

1287void MemoryDepChecker::addAccess(StoreInst *SI) {
visitPointers(SI->getPointerOperand(), *InnermostLoop,
              [this, SI](Value *Ptr) {
                Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
                InstMap.push_back(SI);
                ++AccessIdx;
              });
1294}

1296void MemoryDepChecker::addAccess(LoadInst *LI) {
visitPointers(LI->getPointerOperand(), *InnermostLoop,
              [this, LI](Value *Ptr) {
                Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx);
                InstMap.push_back(LI);
                ++AccessIdx;
              });
1303}

1305MemoryDepChecker::VectorizationSafetyStatus
1306MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) {
switch (Type) {
case NoDep:
case Forward:
case BackwardVectorizable:
  return VectorizationSafetyStatus::Safe;

case Unknown:
  return VectorizationSafetyStatus::PossiblySafeWithRtChecks;
case ForwardButPreventsForwarding:
case Backward:
case BackwardVectorizableButPreventsForwarding:
  return VectorizationSafetyStatus::Unsafe;
}
llvm_unreachable("unexpected DepType!")::llvm::llvm_unreachable_internal("unexpected DepType!", "llvm/lib/Analysis/LoopAccessAnalysis.cpp"
, 1320);
1321}

1323bool MemoryDepChecker::Dependence::isBackward() const {
switch (Type) {
case NoDep:
case Forward:
case ForwardButPreventsForwarding:
case Unknown:
  return false;

case BackwardVectorizable:
case Backward:
case BackwardVectorizableButPreventsForwarding:
  return true;
}
llvm_unreachable("unexpected DepType!")::llvm::llvm_unreachable_internal("unexpected DepType!", "llvm/lib/Analysis/LoopAccessAnalysis.cpp"
, 1336);
1337}

1339bool MemoryDepChecker::Dependence::isPossiblyBackward() const {
return isBackward() || Type == Unknown;
1341}

1343bool MemoryDepChecker::Dependence::isForward() const {
switch (Type) {
case Forward:
case ForwardButPreventsForwarding:
  return true;

case NoDep:
case Unknown:
case BackwardVectorizable:
case Backward:
case BackwardVectorizableButPreventsForwarding:
  return false;
}
llvm_unreachable("unexpected DepType!")::llvm::llvm_unreachable_internal("unexpected DepType!", "llvm/lib/Analysis/LoopAccessAnalysis.cpp"
, 1356);
1357}

1359bool MemoryDepChecker::couldPreventStoreLoadForward(uint64_t Distance,
                                                  uint64_t TypeByteSize) {
// If loads occur at a distance that is not a multiple of a feasible vector
// factor store-load forwarding does not take place.
// Positive dependences might cause troubles because vectorizing them might
// prevent store-load forwarding making vectorized code run a lot slower.
//   a[i] = a[i-3] ^ a[i-8];
//   The stores to a[i:i+1] don't align with the stores to a[i-3:i-2] and
//   hence on your typical architecture store-load forwarding does not take
//   place. Vectorizing in such cases does not make sense.
// Store-load forwarding distance.

// After this many iterations store-to-load forwarding conflicts should not
// cause any slowdowns.
const uint64_t NumItersForStoreLoadThroughMemory = 8 * TypeByteSize;
// Maximum vector factor.
uint64_t MaxVFWithoutSLForwardIssues = std::min(
    VectorizerParams::MaxVectorWidth * TypeByteSize, MaxSafeDepDistBytes);

// Compute the smallest VF at which the store and load would be misaligned.
for (uint64_t VF = 2 * TypeByteSize; VF <= MaxVFWithoutSLForwardIssues;
     VF *= 2) {
  // If the number of vector iteration between the store and the load are
  // small we could incur conflicts.
  if (Distance % VF && Distance / VF < NumItersForStoreLoadThroughMemory) {
    MaxVFWithoutSLForwardIssues = (VF >> 1);
    break;
  }
}

if (MaxVFWithoutSLForwardIssues < 2 * TypeByteSize) {
  LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Distance " <<
 Distance << " that could cause a store-load forwarding conflict\n"
; } } while (false)
      dbgs() << "LAA: Distance " << Distancedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Distance " <<
 Distance << " that could cause a store-load forwarding conflict\n"
; } } while (false)
             << " that could cause a store-load forwarding conflict\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Distance " <<
 Distance << " that could cause a store-load forwarding conflict\n"
; } } while (false);
  return true;
}

if (MaxVFWithoutSLForwardIssues < MaxSafeDepDistBytes &&
    MaxVFWithoutSLForwardIssues !=
        VectorizerParams::MaxVectorWidth * TypeByteSize)
  MaxSafeDepDistBytes = MaxVFWithoutSLForwardIssues;
return false;
1401}

1403void MemoryDepChecker::mergeInStatus(VectorizationSafetyStatus S) {
if (Status < S)
  Status = S;
1406}

1408/// Given a non-constant (unknown) dependence-distance \p Dist between two
1409/// memory accesses, that have the same stride whose absolute value is given
1410/// in \p Stride, and that have the same type size \p TypeByteSize,
1411/// in a loop whose takenCount is \p BackedgeTakenCount, check if it is
1412/// possible to prove statically that the dependence distance is larger
1413/// than the range that the accesses will travel through the execution of
1414/// the loop. If so, return true; false otherwise. This is useful for
1415/// example in loops such as the following (PR31098):
1416///     for (i = 0; i < D; ++i) {
1417///                = out[i];
1418///       out[i+D] =
1419///     }
1420static bool isSafeDependenceDistance(const DataLayout &DL, ScalarEvolution &SE,
                                   const SCEV &BackedgeTakenCount,
                                   const SCEV &Dist, uint64_t Stride,
                                   uint64_t TypeByteSize) {

// If we can prove that
//      (**) |Dist| > BackedgeTakenCount * Step
// where Step is the absolute stride of the memory accesses in bytes,
// then there is no dependence.
//
// Rationale:
// We basically want to check if the absolute distance (|Dist/Step|)
// is >= the loop iteration count (or > BackedgeTakenCount).
// This is equivalent to the Strong SIV Test (Practical Dependence Testing,
// Section 4.2.1); Note, that for vectorization it is sufficient to prove
// that the dependence distance is >= VF; This is checked elsewhere.
// But in some cases we can prune unknown dependence distances early, and
// even before selecting the VF, and without a runtime test, by comparing
// the distance against the loop iteration count. Since the vectorized code
// will be executed only if LoopCount >= VF, proving distance >= LoopCount
// also guarantees that distance >= VF.
//
const uint64_t ByteStride = Stride * TypeByteSize;
const SCEV *Step = SE.getConstant(BackedgeTakenCount.getType(), ByteStride);
const SCEV *Product = SE.getMulExpr(&BackedgeTakenCount, Step);

const SCEV *CastedDist = &Dist;
const SCEV *CastedProduct = Product;
uint64_t DistTypeSize = DL.getTypeAllocSize(Dist.getType());
uint64_t ProductTypeSize = DL.getTypeAllocSize(Product->getType());

// The dependence distance can be positive/negative, so we sign extend Dist;
// The multiplication of the absolute stride in bytes and the
// backedgeTakenCount is non-negative, so we zero extend Product.
if (DistTypeSize > ProductTypeSize)
  CastedProduct = SE.getZeroExtendExpr(Product, Dist.getType());
else
  CastedDist = SE.getNoopOrSignExtend(&Dist, Product->getType());

// Is  Dist - (BackedgeTakenCount * Step) > 0 ?
// (If so, then we have proven (**) because |Dist| >= Dist)
const SCEV *Minus = SE.getMinusSCEV(CastedDist, CastedProduct);
if (SE.isKnownPositive(Minus))
  return true;

// Second try: Is  -Dist - (BackedgeTakenCount * Step) > 0 ?
// (If so, then we have proven (**) because |Dist| >= -1*Dist)
const SCEV *NegDist = SE.getNegativeSCEV(CastedDist);
Minus = SE.getMinusSCEV(NegDist, CastedProduct);
if (SE.isKnownPositive(Minus))
  return true;

return false;
1473}

1475/// Check the dependence for two accesses with the same stride \p Stride.
1476/// \p Distance is the positive distance and \p TypeByteSize is type size in
1477/// bytes.
1478///
1479/// \returns true if they are independent.
1480static bool areStridedAccessesIndependent(uint64_t Distance, uint64_t Stride,
                                        uint64_t TypeByteSize) {
assert(Stride > 1 && "The stride must be greater than 1")(static_cast <bool> (Stride > 1 && "The stride must be greater than 1"
) ? void (0) : __assert_fail ("Stride > 1 && \"The stride must be greater than 1\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 1482, __extension__
 __PRETTY_FUNCTION__));
assert(TypeByteSize > 0 && "The type size in byte must be non-zero")(static_cast <bool> (TypeByteSize > 0 && "The type size in byte must be non-zero"
) ? void (0) : __assert_fail ("TypeByteSize > 0 && \"The type size in byte must be non-zero\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 1483, __extension__
 __PRETTY_FUNCTION__));
assert(Distance > 0 && "The distance must be non-zero")(static_cast <bool> (Distance > 0 && "The distance must be non-zero"
) ? void (0) : __assert_fail ("Distance > 0 && \"The distance must be non-zero\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 1484, __extension__
 __PRETTY_FUNCTION__));

// Skip if the distance is not multiple of type byte size.
if (Distance % TypeByteSize)
  return false;

uint64_t ScaledDist = Distance / TypeByteSize;

// No dependence if the scaled distance is not multiple of the stride.
// E.g.
//      for (i = 0; i < 1024 ; i += 4)
//        A[i+2] = A[i] + 1;
//
// Two accesses in memory (scaled distance is 2, stride is 4):
//     | A[0] |      |      |      | A[4] |      |      |      |
//     |      |      | A[2] |      |      |      | A[6] |      |
//
// E.g.
//      for (i = 0; i < 1024 ; i += 3)
//        A[i+4] = A[i] + 1;
//
// Two accesses in memory (scaled distance is 4, stride is 3):
//     | A[0] |      |      | A[3] |      |      | A[6] |      |      |
//     |      |      |      |      | A[4] |      |      | A[7] |      |
return ScaledDist % Stride;
1509}

1511MemoryDepChecker::Dependence::DepType
1512MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
                            const MemAccessInfo &B, unsigned BIdx,
                            const ValueToValueMap &Strides) {
assert (AIdx < BIdx && "Must pass arguments in program order")(static_cast <bool> (AIdx < BIdx && "Must pass arguments in program order"
) ? void (0) : __assert_fail ("AIdx < BIdx && \"Must pass arguments in program order\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 1515, __extension__
 __PRETTY_FUNCTION__));

Value *APtr = A.getPointer();
Value *BPtr = B.getPointer();
bool AIsWrite = A.getInt();
bool BIsWrite = B.getInt();
Type *ATy = APtr->getType()->getPointerElementType();
Type *BTy = BPtr->getType()->getPointerElementType();

// Two reads are independent.
if (!AIsWrite && !BIsWrite)
  return Dependence::NoDep;

// We cannot check pointers in different address spaces.
if (APtr->getType()->getPointerAddressSpace() !=
    BPtr->getType()->getPointerAddressSpace())
  return Dependence::Unknown;

int64_t StrideAPtr =
    getPtrStride(PSE, ATy, APtr, InnermostLoop, Strides, true);
int64_t StrideBPtr =
    getPtrStride(PSE, BTy, BPtr, InnermostLoop, Strides, true);

const SCEV *Src = PSE.getSCEV(APtr);
const SCEV *Sink = PSE.getSCEV(BPtr);

// If the induction step is negative we have to invert source and sink of the
// dependence.
if (StrideAPtr < 0) {
  std::swap(APtr, BPtr);
  std::swap(ATy, BTy);
  std::swap(Src, Sink);
  std::swap(AIsWrite, BIsWrite);
  std::swap(AIdx, BIdx);
  std::swap(StrideAPtr, StrideBPtr);
}

const SCEV *Dist = PSE.getSE()->getMinusSCEV(Sink, Src);

LLVM_DEBUG(dbgs() << "LAA: Src Scev: " << *Src << "Sink Scev: " << *Sinkdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Src Scev: " <<
 *Src << "Sink Scev: " << *Sink << "(Induction step: "
 << StrideAPtr << ")\n"; } } while (false)
                  << "(Induction step: " << StrideAPtr << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Src Scev: " <<
 *Src << "Sink Scev: " << *Sink << "(Induction step: "
 << StrideAPtr << ")\n"; } } while (false);
LLVM_DEBUG(dbgs() << "LAA: Distance for " << *InstMap[AIdx] << " to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Distance for " <<
 *InstMap[AIdx] << " to " << *InstMap[BIdx] <<
 ": " << *Dist << "\n"; } } while (false)
                  << *InstMap[BIdx] << ": " << *Dist << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Distance for " <<
 *InstMap[AIdx] << " to " << *InstMap[BIdx] <<
 ": " << *Dist << "\n"; } } while (false);

// Need accesses with constant stride. We don't want to vectorize
// "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in
// the address space.
if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){
  LLVM_DEBUG(dbgs() << "Pointer access with non-constant stride\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "Pointer access with non-constant stride\n"
; } } while (false);
  return Dependence::Unknown;
}

auto &DL = InnermostLoop->getHeader()->getModule()->getDataLayout();
uint64_t TypeByteSize = DL.getTypeAllocSize(ATy);
bool HasSameSize =
    DL.getTypeStoreSizeInBits(ATy) == DL.getTypeStoreSizeInBits(BTy);
uint64_t Stride = std::abs(StrideAPtr);
const SCEVConstant *C = dyn_cast<SCEVConstant>(Dist);
if (!C) {
  if (!isa<SCEVCouldNotCompute>(Dist) && HasSameSize &&
      isSafeDependenceDistance(DL, *(PSE.getSE()),
                               *(PSE.getBackedgeTakenCount()), *Dist, Stride,
                               TypeByteSize))
    return Dependence::NoDep;

  LLVM_DEBUG(dbgs() << "LAA: Dependence because of non-constant distance\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Dependence because of non-constant distance\n"
; } } while (false);
  FoundNonConstantDistanceDependence = true;
  return Dependence::Unknown;
}

const APInt &Val = C->getAPInt();
int64_t Distance = Val.getSExtValue();

// Attempt to prove strided accesses independent.
if (std::abs(Distance) > 0 && Stride > 1 && HasSameSize &&
    areStridedAccessesIndependent(std::abs(Distance), Stride, TypeByteSize)) {
  LLVM_DEBUG(dbgs() << "LAA: Strided accesses are independent\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Strided accesses are independent\n"
; } } while (false);
  return Dependence::NoDep;
}

// Negative distances are not plausible dependencies.
if (Val.isNegative()) {
  bool IsTrueDataDependence = (AIsWrite && !BIsWrite);
  if (IsTrueDataDependence && EnableForwardingConflictDetection &&
      (couldPreventStoreLoadForward(Val.abs().getZExtValue(), TypeByteSize) ||
       !HasSameSize)) {
    LLVM_DEBUG(dbgs() << "LAA: Forward but may prevent st->ld forwarding\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Forward but may prevent st->ld forwarding\n"
; } } while (false);
    return Dependence::ForwardButPreventsForwarding;
  }

  LLVM_DEBUG(dbgs() << "LAA: Dependence is negative\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Dependence is negative\n"
; } } while (false);
  return Dependence::Forward;
}

// Write to the same location with the same size.
if (Val == 0) {
  if (HasSameSize)
    return Dependence::Forward;
  LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Zero dependence difference but different type sizes\n"
; } } while (false)
      dbgs() << "LAA: Zero dependence difference but different type sizes\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Zero dependence difference but different type sizes\n"
; } } while (false);
  return Dependence::Unknown;
}

assert(Val.isStrictlyPositive() && "Expect a positive value")(static_cast <bool> (Val.isStrictlyPositive() &&
 "Expect a positive value") ? void (0) : __assert_fail ("Val.isStrictlyPositive() && \"Expect a positive value\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 1618, __extension__
 __PRETTY_FUNCTION__));

if (!HasSameSize) {
  LLVM_DEBUG(dbgs() << "LAA: ReadWrite-Write positive dependency with "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: ReadWrite-Write positive dependency with "
 "different type sizes\n"; } } while (false)
                       "different type sizes\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: ReadWrite-Write positive dependency with "
 "different type sizes\n"; } } while (false);
  return Dependence::Unknown;
}

// Bail out early if passed-in parameters make vectorization not feasible.
unsigned ForcedFactor = (VectorizerParams::VectorizationFactor ?
                         VectorizerParams::VectorizationFactor : 1);
unsigned ForcedUnroll = (VectorizerParams::VectorizationInterleave ?
                         VectorizerParams::VectorizationInterleave : 1);
// The minimum number of iterations for a vectorized/unrolled version.
unsigned MinNumIter = std::max(ForcedFactor * ForcedUnroll, 2U);

// It's not vectorizable if the distance is smaller than the minimum distance
// needed for a vectroized/unrolled version. Vectorizing one iteration in
// front needs TypeByteSize * Stride. Vectorizing the last iteration needs
// TypeByteSize (No need to plus the last gap distance).
//
// E.g. Assume one char is 1 byte in memory and one int is 4 bytes.
//      foo(int *A) {
//        int *B = (int *)((char *)A + 14);
//        for (i = 0 ; i < 1024 ; i += 2)
//          B[i] = A[i] + 1;
//      }
//
// Two accesses in memory (stride is 2):
//     | A[0] |      | A[2] |      | A[4] |      | A[6] |      |
//                              | B[0] |      | B[2] |      | B[4] |
//
// Distance needs for vectorizing iterations except the last iteration:
// 4 * 2 * (MinNumIter - 1). Distance needs for the last iteration: 4.
// So the minimum distance needed is: 4 * 2 * (MinNumIter - 1) + 4.
//
// If MinNumIter is 2, it is vectorizable as the minimum distance needed is
// 12, which is less than distance.
//
// If MinNumIter is 4 (Say if a user forces the vectorization factor to be 4),
// the minimum distance needed is 28, which is greater than distance. It is
// not safe to do vectorization.
uint64_t MinDistanceNeeded =
    TypeByteSize * Stride * (MinNumIter - 1) + TypeByteSize;
if (MinDistanceNeeded > static_cast<uint64_t>(Distance)) {
  LLVM_DEBUG(dbgs() << "LAA: Failure because of positive distance "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Failure because of positive distance "
 << Distance << '\n'; } } while (false)
                    << Distance << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Failure because of positive distance "
 << Distance << '\n'; } } while (false);
  return Dependence::Backward;
}

// Unsafe if the minimum distance needed is greater than max safe distance.
if (MinDistanceNeeded > MaxSafeDepDistBytes) {
  LLVM_DEBUG(dbgs() << "LAA: Failure because it needs at least "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Failure because it needs at least "
 << MinDistanceNeeded << " size in bytes"; } } while
 (false)
                    << MinDistanceNeeded << " size in bytes")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Failure because it needs at least "
 << MinDistanceNeeded << " size in bytes"; } } while
 (false);
  return Dependence::Backward;
}

// Positive distance bigger than max vectorization factor.
// FIXME: Should use max factor instead of max distance in bytes, which could
// not handle different types.
// E.g. Assume one char is 1 byte in memory and one int is 4 bytes.
//      void foo (int *A, char *B) {
//        for (unsigned i = 0; i < 1024; i++) {
//          A[i+2] = A[i] + 1;
//          B[i+2] = B[i] + 1;
//        }
//      }
//
// This case is currently unsafe according to the max safe distance. If we
// analyze the two accesses on array B, the max safe dependence distance
// is 2. Then we analyze the accesses on array A, the minimum distance needed
// is 8, which is less than 2 and forbidden vectorization, But actually
// both A and B could be vectorized by 2 iterations.
MaxSafeDepDistBytes =
    std::min(static_cast<uint64_t>(Distance), MaxSafeDepDistBytes);

bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
if (IsTrueDataDependence && EnableForwardingConflictDetection &&
    couldPreventStoreLoadForward(Distance, TypeByteSize))
  return Dependence::BackwardVectorizableButPreventsForwarding;

uint64_t MaxVF = MaxSafeDepDistBytes / (TypeByteSize * Stride);
LLVM_DEBUG(dbgs() << "LAA: Positive distance " << Val.getSExtValue()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Positive distance "
 << Val.getSExtValue() << " with max VF = " <<
 MaxVF << '\n'; } } while (false)
                  << " with max VF = " << MaxVF << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Positive distance "
 << Val.getSExtValue() << " with max VF = " <<
 MaxVF << '\n'; } } while (false);
uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8;
MaxSafeVectorWidthInBits = std::min(MaxSafeVectorWidthInBits, MaxVFInBits);
return Dependence::BackwardVectorizable;
1705}

1707bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
                                 MemAccessInfoList &CheckDeps,
                                 const ValueToValueMap &Strides) {

MaxSafeDepDistBytes = -1;
SmallPtrSet<MemAccessInfo, 8> Visited;
for (MemAccessInfo CurAccess : CheckDeps) {
  if (Visited.count(CurAccess))
    continue;

  // Get the relevant memory access set.
  EquivalenceClasses<MemAccessInfo>::iterator I =
    AccessSets.findValue(AccessSets.getLeaderValue(CurAccess));

  // Check accesses within this set.
  EquivalenceClasses<MemAccessInfo>::member_iterator AI =
      AccessSets.member_begin(I);
  EquivalenceClasses<MemAccessInfo>::member_iterator AE =
      AccessSets.member_end();

  // Check every access pair.
  while (AI != AE) {
    Visited.insert(*AI);
    bool AIIsWrite = AI->getInt();
    // Check loads only against next equivalent class, but stores also against
    // other stores in the same equivalence class - to the same address.
    EquivalenceClasses<MemAccessInfo>::member_iterator OI =
        (AIIsWrite ? AI : std::next(AI));
    while (OI != AE) {
      // Check every accessing instruction pair in program order.
      for (std::vector<unsigned>::iterator I1 = Accesses[*AI].begin(),
           I1E = Accesses[*AI].end(); I1 != I1E; ++I1)
        // Scan all accesses of another equivalence class, but only the next
        // accesses of the same equivalent class.
        for (std::vector<unsigned>::iterator
                 I2 = (OI == AI ? std::next(I1) : Accesses[*OI].begin()),
                 I2E = (OI == AI ? I1E : Accesses[*OI].end());
             I2 != I2E; ++I2) {
          auto A = std::make_pair(&*AI, *I1);
          auto B = std::make_pair(&*OI, *I2);

          assert(*I1 != *I2)(static_cast <bool> (*I1 != *I2) ? void (0) : __assert_fail
 ("*I1 != *I2", "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 1748
, __extension__ __PRETTY_FUNCTION__));
          if (*I1 > *I2)
            std::swap(A, B);

          Dependence::DepType Type =
              isDependent(*A.first, A.second, *B.first, B.second, Strides);
          mergeInStatus(Dependence::isSafeForVectorization(Type));

          // Gather dependences unless we accumulated MaxDependences
          // dependences.  In that case return as soon as we find the first
          // unsafe dependence.  This puts a limit on this quadratic
          // algorithm.
          if (RecordDependences) {
            if (Type != Dependence::NoDep)
              Dependences.push_back(Dependence(A.second, B.second, Type));

            if (Dependences.size() >= MaxDependences) {
              RecordDependences = false;
              Dependences.clear();
              LLVM_DEBUG(dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "Too many dependences, stopped recording\n"
; } } while (false)
                         << "Too many dependences, stopped recording\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "Too many dependences, stopped recording\n"
; } } while (false);
            }
          }
          if (!RecordDependences && !isSafeForVectorization())
            return false;
        }
      ++OI;
    }
    AI++;
  }
}

LLVM_DEBUG(dbgs() << "Total Dependences: " << Dependences.size() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "Total Dependences: " <<
 Dependences.size() << "\n"; } } while (false);
return isSafeForVectorization();
1782}

1784SmallVector<Instruction *, 4>
1785MemoryDepChecker::getInstructionsForAccess(Value *Ptr, bool isWrite) const {
MemAccessInfo Access(Ptr, isWrite);
auto &IndexVector = Accesses.find(Access)->second;

SmallVector<Instruction *, 4> Insts;
transform(IndexVector,
               std::back_inserter(Insts),
               [&](unsigned Idx) { return this->InstMap[Idx]; });
return Insts;
1794}

1796const char *MemoryDepChecker::Dependence::DepName[] = {
  "NoDep", "Unknown", "Forward", "ForwardButPreventsForwarding", "Backward",
  "BackwardVectorizable", "BackwardVectorizableButPreventsForwarding"};

1800void MemoryDepChecker::Dependence::print(
  raw_ostream &OS, unsigned Depth,
  const SmallVectorImpl<Instruction *> &Instrs) const {
OS.indent(Depth) << DepName[Type] << ":\n";
OS.indent(Depth + 2) << *Instrs[Source] << " -> \n";
OS.indent(Depth + 2) << *Instrs[Destination] << "\n";
1806}

1808bool LoopAccessInfo::canAnalyzeLoop() {
// We need to have a loop header.
LLVM_DEBUG(dbgs() << "LAA: Found a loop in "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Found a loop in " <<
 TheLoop->getHeader()->getParent()->getName() <<
 ": " << TheLoop->getHeader()->getName() <<
 '\n'; } } while (false)
                  << TheLoop->getHeader()->getParent()->getName() << ": "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Found a loop in " <<
 TheLoop->getHeader()->getParent()->getName() <<
 ": " << TheLoop->getHeader()->getName() <<
 '\n'; } } while (false)
                  << TheLoop->getHeader()->getName() << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Found a loop in " <<
 TheLoop->getHeader()->getParent()->getName() <<
 ": " << TheLoop->getHeader()->getName() <<
 '\n'; } } while (false);

// We can only analyze innermost loops.
if (!TheLoop->isInnermost()) {
  LLVM_DEBUG(dbgs() << "LAA: loop is not the innermost loop\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: loop is not the innermost loop\n"
; } } while (false);
  recordAnalysis("NotInnerMostLoop") << "loop is not the innermost loop";
  return false;
}

// We must have a single backedge.
if (TheLoop->getNumBackEdges() != 1) {
  LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: loop control flow is not understood by analyzer\n"
; } } while (false)
      dbgs() << "LAA: loop control flow is not understood by analyzer\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: loop control flow is not understood by analyzer\n"
; } } while (false);
  recordAnalysis("CFGNotUnderstood")
      << "loop control flow is not understood by analyzer";
  return false;
}

// ScalarEvolution needs to be able to find the exit count.
const SCEV *ExitCount = PSE->getBackedgeTakenCount();
if (isa<SCEVCouldNotCompute>(ExitCount)) {
  recordAnalysis("CantComputeNumberOfIterations")
      << "could not determine number of loop iterations";
  LLVM_DEBUG(dbgs() << "LAA: SCEV could not compute the loop exit count.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: SCEV could not compute the loop exit count.\n"
; } } while (false);
  return false;
}

return true;
1840}

1842void LoopAccessInfo::analyzeLoop(AAResults *AA, LoopInfo *LI,
                               const TargetLibraryInfo *TLI,
                               DominatorTree *DT) {
typedef SmallPtrSet<Value*, 16> ValueSet;

// Holds the Load and Store instructions.
SmallVector<LoadInst *, 16> Loads;
SmallVector<StoreInst *, 16> Stores;

// Holds all the different accesses in the loop.
unsigned NumReads = 0;
unsigned NumReadWrites = 0;

bool HasComplexMemInst = false;

// A runtime check is only legal to insert if there are no convergent calls.
HasConvergentOp = false;

PtrRtChecking->Pointers.clear();
PtrRtChecking->Need = false;

const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel();

const bool EnableMemAccessVersioningOfLoop =
    EnableMemAccessVersioning &&
1
Assuming the condition is false→
    !TheLoop->getHeader()->getParent()->hasOptSize();

// For each block.
for (BasicBlock *BB : TheLoop->blocks()) {
2
←
Assuming '__begin1' is equal to '__end1'→
  // Scan the BB and collect legal loads and stores. Also detect any
  // convergent instructions.
  for (Instruction &I : *BB) {
    if (auto *Call = dyn_cast<CallBase>(&I)) {
      if (Call->isConvergent())
        HasConvergentOp = true;
    }

    // With both a non-vectorizable memory instruction and a convergent
    // operation, found in this loop, no reason to continue the search.
    if (HasComplexMemInst && HasConvergentOp) {
      CanVecMem = false;
      return;
    }

    // Avoid hitting recordAnalysis multiple times.
    if (HasComplexMemInst)
      continue;

    // If this is a load, save it. If this instruction can read from memory
    // but is not a load, then we quit. Notice that we don't handle function
    // calls that read or write.
    if (I.mayReadFromMemory()) {
      // Many math library functions read the rounding mode. We will only
      // vectorize a loop if it contains known function calls that don't set
      // the flag. Therefore, it is safe to ignore this read from memory.
      auto *Call = dyn_cast<CallInst>(&I);
      if (Call && getVectorIntrinsicIDForCall(Call, TLI))
        continue;

      // If the function has an explicit vectorized counterpart, we can safely
      // assume that it can be vectorized.
      if (Call && !Call->isNoBuiltin() && Call->getCalledFunction() &&
          !VFDatabase::getMappings(*Call).empty())
        continue;

      auto *Ld = dyn_cast<LoadInst>(&I);
      if (!Ld) {
        recordAnalysis("CantVectorizeInstruction", Ld)
          << "instruction cannot be vectorized";
        HasComplexMemInst = true;
        continue;
      }
      if (!Ld->isSimple() && !IsAnnotatedParallel) {
        recordAnalysis("NonSimpleLoad", Ld)
            << "read with atomic ordering or volatile read";
        LLVM_DEBUG(dbgs() << "LAA: Found a non-simple load.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Found a non-simple load.\n"
; } } while (false);
        HasComplexMemInst = true;
        continue;
      }
      NumLoads++;
      Loads.push_back(Ld);
      DepChecker->addAccess(Ld);
      if (EnableMemAccessVersioningOfLoop)
        collectStridedAccess(Ld);
      continue;
    }

    // Save 'store' instructions. Abort if other instructions write to memory.
    if (I.mayWriteToMemory()) {
      auto *St = dyn_cast<StoreInst>(&I);
      if (!St) {
        recordAnalysis("CantVectorizeInstruction", St)
            << "instruction cannot be vectorized";
        HasComplexMemInst = true;
        continue;
      }
      if (!St->isSimple() && !IsAnnotatedParallel) {
        recordAnalysis("NonSimpleStore", St)
            << "write with atomic ordering or volatile write";
        LLVM_DEBUG(dbgs() << "LAA: Found a non-simple store.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Found a non-simple store.\n"
; } } while (false);
        HasComplexMemInst = true;
        continue;
      }
      NumStores++;
      Stores.push_back(St);
      DepChecker->addAccess(St);
      if (EnableMemAccessVersioningOfLoop)
        collectStridedAccess(St);
    }
  } // Next instr.
} // Next block.

if (HasComplexMemInst2.1
'HasComplexMemInst' is false
1
'HasComplexMemInst' is false
) {
3
←
Taking false branch→
  CanVecMem = false;
  return;
}

// Now we have two lists that hold the loads and the stores.
// Next, we find the pointers that they use.

// Check if we see any stores. If there are no stores, then we don't
// care if the pointers are *restrict*.
if (!Stores.size()) {
4
←
Assuming the condition is false→
5
←
Taking false branch→
  LLVM_DEBUG(dbgs() << "LAA: Found a read-only loop!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Found a read-only loop!\n"
; } } while (false);
  CanVecMem = true;
  return;
}

MemoryDepChecker::DepCandidates DependentAccesses;
AccessAnalysis Accesses(TheLoop, AA, LI, DependentAccesses, *PSE);

// Holds the analyzed pointers. We don't want to call getUnderlyingObjects
// multiple times on the same object. If the ptr is accessed twice, once
// for read and once for write, it will only appear once (on the write
// list). This is okay, since we are going to check for conflicts between
// writes and between reads and writes, but not between reads and reads.
ValueSet Seen;

// Record uniform store addresses to identify if we have multiple stores
// to the same address.
ValueSet UniformStores;

for (StoreInst *ST : Stores) {
6
←
Assuming '__begin1' is equal to '__end1'→
  Value *Ptr = ST->getPointerOperand();

  if (isUniform(Ptr))
    HasDependenceInvolvingLoopInvariantAddress |=
        !UniformStores.insert(Ptr).second;

  // If we did *not* see this pointer before, insert it to  the read-write
  // list. At this phase it is only a 'write' list.
  if (Seen.insert(Ptr).second) {
    ++NumReadWrites;

    MemoryLocation Loc = MemoryLocation::get(ST);
    // The TBAA metadata could have a control dependency on the predication
    // condition, so we cannot rely on it when determining whether or not we
    // need runtime pointer checks.
    if (blockNeedsPredication(ST->getParent(), TheLoop, DT))
      Loc.AATags.TBAA = nullptr;

    visitPointers(const_cast<Value *>(Loc.Ptr), *TheLoop,
                  [&Accesses, Loc](Value *Ptr) {
                    MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
                    Accesses.addStore(NewLoc);
                  });
  }
}

if (IsAnnotatedParallel) {
7
←
Assuming 'IsAnnotatedParallel' is false→
8
←
Taking false branch→
  LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: A loop annotated parallel, ignore memory dependency "
 << "checks.\n"; } } while (false)
      dbgs() << "LAA: A loop annotated parallel, ignore memory dependency "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: A loop annotated parallel, ignore memory dependency "
 << "checks.\n"; } } while (false)
             << "checks.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: A loop annotated parallel, ignore memory dependency "
 << "checks.\n"; } } while (false);
  CanVecMem = true;
  return;
}

for (LoadInst *LD : Loads) {
9
←
Assuming '__begin1' is equal to '__end1'→
  Value *Ptr = LD->getPointerOperand();
  // If we did *not* see this pointer before, insert it to the
  // read list. If we *did* see it before, then it is already in
  // the read-write list. This allows us to vectorize expressions
  // such as A[i] += x;  Because the address of A[i] is a read-write
  // pointer. This only works if the index of A[i] is consecutive.
  // If the address of i is unknown (for example A[B[i]]) then we may
  // read a few words, modify, and write a few words, and some of the
  // words may be written to the same address.
  bool IsReadOnlyPtr = false;
  if (Seen.insert(Ptr).second ||
      !getPtrStride(*PSE, LD->getType(), Ptr, TheLoop, SymbolicStrides)) {
    ++NumReads;
    IsReadOnlyPtr = true;
  }

  // See if there is an unsafe dependency between a load to a uniform address and
  // store to the same uniform address.
  if (UniformStores.count(Ptr)) {
    LLVM_DEBUG(dbgs() << "LAA: Found an unsafe dependency between a uniform "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Found an unsafe dependency between a uniform "
 "load and uniform store to the same address!\n"; } } while (
false)
                         "load and uniform store to the same address!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Found an unsafe dependency between a uniform "
 "load and uniform store to the same address!\n"; } } while (
false);
    HasDependenceInvolvingLoopInvariantAddress = true;
  }

  MemoryLocation Loc = MemoryLocation::get(LD);
  // The TBAA metadata could have a control dependency on the predication
  // condition, so we cannot rely on it when determining whether or not we
  // need runtime pointer checks.
  if (blockNeedsPredication(LD->getParent(), TheLoop, DT))
    Loc.AATags.TBAA = nullptr;

  visitPointers(const_cast<Value *>(Loc.Ptr), *TheLoop,
                [&Accesses, Loc, IsReadOnlyPtr](Value *Ptr) {
                  MemoryLocation NewLoc = Loc.getWithNewPtr(Ptr);
                  Accesses.addLoad(NewLoc, IsReadOnlyPtr);
                });
}

// If we write (or read-write) to a single destination and there are no
// other reads in this loop then is it safe to vectorize.
if (NumReadWrites9.1
'NumReadWrites' is not equal to 1
1
'NumReadWrites' is not equal to 1
 == 1 && NumReads == 0) {
  LLVM_DEBUG(dbgs() << "LAA: Found a write-only loop!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Found a write-only loop!\n"
; } } while (false);
  CanVecMem = true;
  return;
}

// Build dependence sets and check whether we need a runtime pointer bounds
// check.
Accesses.buildDependenceSets();
10
←
Calling 'AccessAnalysis::buildDependenceSets'→

// Find pointers with computable bounds. We are going to use this information
// to place a runtime bound check.
bool CanDoRTIfNeeded = Accesses.canCheckPtrAtRT(*PtrRtChecking, PSE->getSE(),
                                                TheLoop, SymbolicStrides);
if (!CanDoRTIfNeeded) {
  recordAnalysis("CantIdentifyArrayBounds") << "cannot identify array bounds";
  LLVM_DEBUG(dbgs() << "LAA: We can't vectorize because we can't find "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: We can't vectorize because we can't find "
 << "the array bounds.\n"; } } while (false)
                    << "the array bounds.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: We can't vectorize because we can't find "
 << "the array bounds.\n"; } } while (false);
  CanVecMem = false;
  return;
}

LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: May be able to perform a memory runtime check if needed.\n"
; } } while (false)
  dbgs() << "LAA: May be able to perform a memory runtime check if needed.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: May be able to perform a memory runtime check if needed.\n"
; } } while (false);

CanVecMem = true;
if (Accesses.isDependencyCheckNeeded()) {
  LLVM_DEBUG(dbgs() << "LAA: Checking memory dependencies\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Checking memory dependencies\n"
; } } while (false);
  CanVecMem = DepChecker->areDepsSafe(
      DependentAccesses, Accesses.getDependenciesToCheck(), SymbolicStrides);
  MaxSafeDepDistBytes = DepChecker->getMaxSafeDepDistBytes();

  if (!CanVecMem && DepChecker->shouldRetryWithRuntimeCheck()) {
    LLVM_DEBUG(dbgs() << "LAA: Retrying with memory checks\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Retrying with memory checks\n"
; } } while (false);

    // Clear the dependency checks. We assume they are not needed.
    Accesses.resetDepChecks(*DepChecker);

    PtrRtChecking->reset();
    PtrRtChecking->Need = true;

    auto *SE = PSE->getSE();
    CanDoRTIfNeeded = Accesses.canCheckPtrAtRT(*PtrRtChecking, SE, TheLoop,
                                               SymbolicStrides, true);

    // Check that we found the bounds for the pointer.
    if (!CanDoRTIfNeeded) {
      recordAnalysis("CantCheckMemDepsAtRunTime")
          << "cannot check memory dependencies at runtime";
      LLVM_DEBUG(dbgs() << "LAA: Can't vectorize with memory checks\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Can't vectorize with memory checks\n"
; } } while (false);
      CanVecMem = false;
      return;
    }

    CanVecMem = true;
  }
}

if (HasConvergentOp) {
  recordAnalysis("CantInsertRuntimeCheckWithConvergent")
    << "cannot add control dependency to convergent operation";
  LLVM_DEBUG(dbgs() << "LAA: We can't vectorize because a runtime check "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: We can't vectorize because a runtime check "
 "would be needed with a convergent operation\n"; } } while (
false)
                       "would be needed with a convergent operation\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: We can't vectorize because a runtime check "
 "would be needed with a convergent operation\n"; } } while (
false);
  CanVecMem = false;
  return;
}

if (CanVecMem)
  LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: No unsafe dependent memory operations in loop.  We"
 << (PtrRtChecking->Need ? "" : " don't") << " need runtime memory checks.\n"
; } } while (false)
      dbgs() << "LAA: No unsafe dependent memory operations in loop.  We"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: No unsafe dependent memory operations in loop.  We"
 << (PtrRtChecking->Need ? "" : " don't") << " need runtime memory checks.\n"
; } } while (false)
             << (PtrRtChecking->Need ? "" : " don't")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: No unsafe dependent memory operations in loop.  We"
 << (PtrRtChecking->Need ? "" : " don't") << " need runtime memory checks.\n"
; } } while (false)
             << " need runtime memory checks.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: No unsafe dependent memory operations in loop.  We"
 << (PtrRtChecking->Need ? "" : " don't") << " need runtime memory checks.\n"
; } } while (false);
else {
  recordAnalysis("UnsafeMemDep")
      << "unsafe dependent memory operations in loop. Use "
         "#pragma loop distribute(enable) to allow loop distribution "
         "to attempt to isolate the offending operations into a separate "
         "loop";
  LLVM_DEBUG(dbgs() << "LAA: unsafe dependent memory operations in loop\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: unsafe dependent memory operations in loop\n"
; } } while (false);
}
2140}

2142bool LoopAccessInfo::blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
                                         DominatorTree *DT)  {
assert(TheLoop->contains(BB) && "Unknown block used")(static_cast <bool> (TheLoop->contains(BB) &&
 "Unknown block used") ? void (0) : __assert_fail ("TheLoop->contains(BB) && \"Unknown block used\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 2144, __extension__
 __PRETTY_FUNCTION__));

// Blocks that do not dominate the latch need predication.
BasicBlock* Latch = TheLoop->getLoopLatch();
return !DT->dominates(BB, Latch);
2149}

2151OptimizationRemarkAnalysis &LoopAccessInfo::recordAnalysis(StringRef RemarkName,
                                                         Instruction *I) {
assert(!Report && "Multiple reports generated")(static_cast <bool> (!Report && "Multiple reports generated"
) ? void (0) : __assert_fail ("!Report && \"Multiple reports generated\""
, "llvm/lib/Analysis/LoopAccessAnalysis.cpp", 2153, __extension__
 __PRETTY_FUNCTION__));

Value *CodeRegion = TheLoop->getHeader();
DebugLoc DL = TheLoop->getStartLoc();

if (I) {
  CodeRegion = I->getParent();
  // If there is no debug location attached to the instruction, revert back to
  // using the loop's.
  if (I->getDebugLoc())
    DL = I->getDebugLoc();
}

Report = std::make_unique<OptimizationRemarkAnalysis>(DEBUG_TYPE"loop-accesses", RemarkName, DL,
                                                 CodeRegion);
return *Report;
2169}

2171bool LoopAccessInfo::isUniform(Value *V) const {
auto *SE = PSE->getSE();
// Since we rely on SCEV for uniformity, if the type is not SCEVable, it is
// never considered uniform.
// TODO: Is this really what we want? Even without FP SCEV, we may want some
// trivially loop-invariant FP values to be considered uniform.
if (!SE->isSCEVable(V->getType()))
  return false;
return (SE->isLoopInvariant(SE->getSCEV(V), TheLoop));
2180}

2182void LoopAccessInfo::collectStridedAccess(Value *MemAccess) {
Value *Ptr = getLoadStorePointerOperand(MemAccess);
if (!Ptr)
  return;

Value *Stride = getStrideFromPointer(Ptr, PSE->getSE(), TheLoop);
if (!Stride)
  return;

LLVM_DEBUG(dbgs() << "LAA: Found a strided access that is a candidate for "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Found a strided access that is a candidate for "
 "versioning:"; } } while (false)
                     "versioning:")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Found a strided access that is a candidate for "
 "versioning:"; } } while (false);
LLVM_DEBUG(dbgs() << "  Ptr: " << *Ptr << " Stride: " << *Stride << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "  Ptr: " << *Ptr <<
 " Stride: " << *Stride << "\n"; } } while (false
);

// Avoid adding the "Stride == 1" predicate when we know that
// Stride >= Trip-Count. Such a predicate will effectively optimize a single
// or zero iteration loop, as Trip-Count <= Stride == 1.
//
// TODO: We are currently not making a very informed decision on when it is
// beneficial to apply stride versioning. It might make more sense that the
// users of this analysis (such as the vectorizer) will trigger it, based on
// their specific cost considerations; For example, in cases where stride
// versioning does  not help resolving memory accesses/dependences, the
// vectorizer should evaluate the cost of the runtime test, and the benefit
// of various possible stride specializations, considering the alternatives
// of using gather/scatters (if available).

const SCEV *StrideExpr = PSE->getSCEV(Stride);
const SCEV *BETakenCount = PSE->getBackedgeTakenCount();

// Match the types so we can compare the stride and the BETakenCount.
// The Stride can be positive/negative, so we sign extend Stride;
// The backedgeTakenCount is non-negative, so we zero extend BETakenCount.
const DataLayout &DL = TheLoop->getHeader()->getModule()->getDataLayout();
uint64_t StrideTypeSize = DL.getTypeAllocSize(StrideExpr->getType());
uint64_t BETypeSize = DL.getTypeAllocSize(BETakenCount->getType());
const SCEV *CastedStride = StrideExpr;
const SCEV *CastedBECount = BETakenCount;
ScalarEvolution *SE = PSE->getSE();
if (BETypeSize >= StrideTypeSize)
  CastedStride = SE->getNoopOrSignExtend(StrideExpr, BETakenCount->getType());
else
  CastedBECount = SE->getZeroExtendExpr(BETakenCount, StrideExpr->getType());
const SCEV *StrideMinusBETaken = SE->getMinusSCEV(CastedStride, CastedBECount);
// Since TripCount == BackEdgeTakenCount + 1, checking:
// "Stride >= TripCount" is equivalent to checking:
// Stride - BETakenCount > 0
if (SE->isKnownPositive(StrideMinusBETaken)) {
  LLVM_DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Stride>=TripCount; No point in versioning as the "
 "Stride==1 predicate will imply that the loop executes " "at most once.\n"
; } } while (false)
      dbgs() << "LAA: Stride>=TripCount; No point in versioning as the "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Stride>=TripCount; No point in versioning as the "
 "Stride==1 predicate will imply that the loop executes " "at most once.\n"
; } } while (false)
                "Stride==1 predicate will imply that the loop executes "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Stride>=TripCount; No point in versioning as the "
 "Stride==1 predicate will imply that the loop executes " "at most once.\n"
; } } while (false)
                "at most once.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Stride>=TripCount; No point in versioning as the "
 "Stride==1 predicate will imply that the loop executes " "at most once.\n"
; } } while (false);
  return;
}
LLVM_DEBUG(dbgs() << "LAA: Found a strided access that we can version.")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-accesses")) { dbgs() << "LAA: Found a strided access that we can version."
; } } while (false);

SymbolicStrides[Ptr] = Stride;
StrideSet.insert(Stride);
2239}

2241LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
                             const TargetLibraryInfo *TLI, AAResults *AA,
                             DominatorTree *DT, LoopInfo *LI)
  : PSE(std::make_unique<PredicatedScalarEvolution>(*SE, *L)),
    PtrRtChecking(std::make_unique<RuntimePointerChecking>(SE)),
    DepChecker(std::make_unique<MemoryDepChecker>(*PSE, L)), TheLoop(L) {
if (canAnalyzeLoop())
  analyzeLoop(AA, LI, TLI, DT);
2249}

2251void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
if (CanVecMem) {
  OS.indent(Depth) << "Memory dependences are safe";
  if (MaxSafeDepDistBytes != -1ULL)
    OS << " with a maximum dependence distance of " << MaxSafeDepDistBytes
       << " bytes";
  if (PtrRtChecking->Need)
    OS << " with run-time checks";
  OS << "\n";
}

if (HasConvergentOp)
  OS.indent(Depth) << "Has convergent operation in loop\n";

if (Report)
  OS.indent(Depth) << "Report: " << Report->getMsg() << "\n";

if (auto *Dependences = DepChecker->getDependences()) {
  OS.indent(Depth) << "Dependences:\n";
  for (auto &Dep : *Dependences) {
    Dep.print(OS, Depth + 2, DepChecker->getMemoryInstructions());
    OS << "\n";
  }
} else
  OS.indent(Depth) << "Too many dependences, not recorded\n";

// List the pair of accesses need run-time checks to prove independence.
PtrRtChecking->print(OS, Depth);
OS << "\n";

OS.indent(Depth) << "Non vectorizable stores to invariant address were "
                 << (HasDependenceInvolvingLoopInvariantAddress ? "" : "not ")
                 << "found in loop.\n";

OS.indent(Depth) << "SCEV assumptions:\n";
PSE->getUnionPredicate().print(OS, Depth);

OS << "\n";

OS.indent(Depth) << "Expressions re-written:\n";
PSE->print(OS, Depth);
2292}

2294LoopAccessLegacyAnalysis::LoopAccessLegacyAnalysis() : FunctionPass(ID) {
initializeLoopAccessLegacyAnalysisPass(*PassRegistry::getPassRegistry());
2296}

2298const LoopAccessInfo &LoopAccessLegacyAnalysis::getInfo(Loop *L) {
auto &LAI = LoopAccessInfoMap[L];

if (!LAI)
  LAI = std::make_unique<LoopAccessInfo>(L, SE, TLI, AA, DT, LI);

return *LAI.get();
2305}

2307void LoopAccessLegacyAnalysis::print(raw_ostream &OS, const Module *M) const {
LoopAccessLegacyAnalysis &LAA = *const_cast<LoopAccessLegacyAnalysis *>(this);

for (Loop *TopLevelLoop : *LI)
  for (Loop *L : depth_first(TopLevelLoop)) {
    OS.indent(2) << L->getHeader()->getName() << ":\n";
    auto &LAI = LAA.getInfo(L);
    LAI.print(OS, 4);
  }
2316}

2318bool LoopAccessLegacyAnalysis::runOnFunction(Function &F) {
SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
TLI = TLIP ? &TLIP->getTLI(F) : nullptr;
AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();

return false;
2327}

2329void LoopAccessLegacyAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
AU.addRequiredTransitive<AAResultsWrapperPass>();
AU.addRequiredTransitive<DominatorTreeWrapperPass>();
AU.addRequiredTransitive<LoopInfoWrapperPass>();

AU.setPreservesAll();
2336}

2338char LoopAccessLegacyAnalysis::ID = 0;
2339static const char laa_name[] = "Loop Access Analysis";
2340#define LAA_NAME"loop-accesses" "loop-accesses"

2342INITIALIZE_PASS_BEGIN(LoopAccessLegacyAnalysis, LAA_NAME, laa_name, false, true)static void *initializeLoopAccessLegacyAnalysisPassOnce(PassRegistry
 &Registry) {
2343INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)initializeAAResultsWrapperPassPass(Registry);
2344INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)initializeScalarEvolutionWrapperPassPass(Registry);
2345INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
2346INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)initializeLoopInfoWrapperPassPass(Registry);
2347INITIALIZE_PASS_END(LoopAccessLegacyAnalysis, LAA_NAME, laa_name, false, true)PassInfo *PI = new PassInfo( laa_name, "loop-accesses", &
LoopAccessLegacyAnalysis::ID, PassInfo::NormalCtor_t(callDefaultCtor
<LoopAccessLegacyAnalysis>), false, true); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeLoopAccessLegacyAnalysisPassFlag
; void llvm::initializeLoopAccessLegacyAnalysisPass(PassRegistry
 &Registry) { llvm::call_once(InitializeLoopAccessLegacyAnalysisPassFlag
, initializeLoopAccessLegacyAnalysisPassOnce, std::ref(Registry
)); }

2349AnalysisKey LoopAccessAnalysis::Key;

2351LoopAccessInfo LoopAccessAnalysis::run(Loop &L, LoopAnalysisManager &AM,
                                     LoopStandardAnalysisResults &AR) {
return LoopAccessInfo(&L, &AR.SE, &AR.TLI, &AR.AA, &AR.DT, &AR.LI);
2354}

2356namespace llvm {

Pass *createLAAPass() {
  return new LoopAccessLegacyAnalysis();
}

2362} // end namespace llvm

←

/build/llvm-toolchain-snapshot-14~++20220125101009+ceec4383681c/llvm/include/llvm/ADT/PointerIntPair.h

1//===- llvm/ADT/PointerIntPair.h - Pair for pointer and int -----*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the PointerIntPair class.
10//
11//===----------------------------------------------------------------------===//
12 
13#ifndef LLVM_ADT_POINTERINTPAIR_H
14#define LLVM_ADT_POINTERINTPAIR_H
15 
16#include "llvm/Support/Compiler.h"
17#include "llvm/Support/PointerLikeTypeTraits.h"
18#include "llvm/Support/type_traits.h"
19#include <cassert>
20#include <cstdint>
21#include <limits>
22 
23namespace llvm {
24 
25template <typename T, typename Enable> struct DenseMapInfo;
26template <typename PointerT, unsigned IntBits, typename PtrTraits>
27struct PointerIntPairInfo;
28 
29/// PointerIntPair - This class implements a pair of a pointer and small
30/// integer.  It is designed to represent this in the space required by one
31/// pointer by bitmangling the integer into the low part of the pointer.  This
32/// can only be done for small integers: typically up to 3 bits, but it depends
33/// on the number of bits available according to PointerLikeTypeTraits for the
34/// type.
35///
36/// Note that PointerIntPair always puts the IntVal part in the highest bits
37/// possible.  For example, PointerIntPair<void*, 1, bool> will put the bit for
38/// the bool into bit #2, not bit #0, which allows the low two bits to be used
39/// for something else.  For example, this allows:
40///   PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool>
41/// ... and the two bools will land in different bits.
42template <typename PointerTy, unsigned IntBits, typename IntType = unsigned,
43          typename PtrTraits = PointerLikeTypeTraits<PointerTy>,
44          typename Info = PointerIntPairInfo<PointerTy, IntBits, PtrTraits>>
45class PointerIntPair {
46  // Used by MSVC visualizer and generally helpful for debugging/visualizing.
47  using InfoTy = Info;
48  intptr_t Value = 0;
49 
50public:
51  constexpr PointerIntPair() = default;
52 
53  PointerIntPair(PointerTy PtrVal, IntType IntVal) {
54    setPointerAndInt(PtrVal, IntVal);
28
←
Passing value via 2nd parameter 'IntVal'→
29
←
Calling 'PointerIntPair::setPointerAndInt'→
55  }
56 
57  explicit PointerIntPair(PointerTy PtrVal) { initWithPointer(PtrVal); }
58 
59  PointerTy getPointer() const { return Info::getPointer(Value); }
60 
61  IntType getInt() const { return (IntType)Info::getInt(Value); }
62 
63  void setPointer(PointerTy PtrVal) LLVM_LVALUE_FUNCTION& {
64    Value = Info::updatePointer(Value, PtrVal);
65  }
66 
67  void setInt(IntType IntVal) LLVM_LVALUE_FUNCTION& {
68    Value = Info::updateInt(Value, static_cast<intptr_t>(IntVal));
69  }
70 
71  void initWithPointer(PointerTy PtrVal) LLVM_LVALUE_FUNCTION& {
72    Value = Info::updatePointer(0, PtrVal);
73  }
74 
75  void setPointerAndInt(PointerTy PtrVal, IntType IntVal) LLVM_LVALUE_FUNCTION& {
76    Value = Info::updateInt(Info::updatePointer(0, PtrVal),
31
←
Calling 'PointerIntPairInfo::updateInt'→
77                            static_cast<intptr_t>(IntVal));
30
←
Passing value via 2nd parameter 'Int'→
78  }
79 
80  PointerTy const *getAddrOfPointer() const {
81    return const_cast<PointerIntPair *>(this)->getAddrOfPointer();
82  }
83 
84  PointerTy *getAddrOfPointer() {
85    assert(Value == reinterpret_cast<intptr_t>(getPointer()) &&(static_cast <bool> (Value == reinterpret_cast<intptr_t
>(getPointer()) && "Can only return the address if IntBits is cleared and "
 "PtrTraits doesn't change the pointer") ? void (0) : __assert_fail
 ("Value == reinterpret_cast<intptr_t>(getPointer()) && \"Can only return the address if IntBits is cleared and \" \"PtrTraits doesn't change the pointer\""
, "llvm/include/llvm/ADT/PointerIntPair.h", 87, __extension__
 __PRETTY_FUNCTION__))
86           "Can only return the address if IntBits is cleared and "(static_cast <bool> (Value == reinterpret_cast<intptr_t
>(getPointer()) && "Can only return the address if IntBits is cleared and "
 "PtrTraits doesn't change the pointer") ? void (0) : __assert_fail
 ("Value == reinterpret_cast<intptr_t>(getPointer()) && \"Can only return the address if IntBits is cleared and \" \"PtrTraits doesn't change the pointer\""
, "llvm/include/llvm/ADT/PointerIntPair.h", 87, __extension__
 __PRETTY_FUNCTION__))
87           "PtrTraits doesn't change the pointer")(static_cast <bool> (Value == reinterpret_cast<intptr_t
>(getPointer()) && "Can only return the address if IntBits is cleared and "
 "PtrTraits doesn't change the pointer") ? void (0) : __assert_fail
 ("Value == reinterpret_cast<intptr_t>(getPointer()) && \"Can only return the address if IntBits is cleared and \" \"PtrTraits doesn't change the pointer\""
, "llvm/include/llvm/ADT/PointerIntPair.h", 87, __extension__
 __PRETTY_FUNCTION__));
88    return reinterpret_cast<PointerTy *>(&Value);
89  }
90 
91  void *getOpaqueValue() const { return reinterpret_cast<void *>(Value); }
92 
93  void setFromOpaqueValue(void *Val) LLVM_LVALUE_FUNCTION& {
94    Value = reinterpret_cast<intptr_t>(Val);
95  }
96 
97  static PointerIntPair getFromOpaqueValue(void *V) {
98    PointerIntPair P;
99    P.setFromOpaqueValue(V);
100    return P;
101  }
102 
103  // Allow PointerIntPairs to be created from const void * if and only if the
104  // pointer type could be created from a const void *.
105  static PointerIntPair getFromOpaqueValue(const void *V) {
106    (void)PtrTraits::getFromVoidPointer(V);
107    return getFromOpaqueValue(const_cast<void *>(V));
108  }
109 
110  bool operator==(const PointerIntPair &RHS) const {
111    return Value == RHS.Value;
112  }
113 
114  bool operator!=(const PointerIntPair &RHS) const {
115    return Value != RHS.Value;
116  }
117 
118  bool operator<(const PointerIntPair &RHS) const { return Value < RHS.Value; }
119  bool operator>(const PointerIntPair &RHS) const { return Value > RHS.Value; }
120 
121  bool operator<=(const PointerIntPair &RHS) const {
122    return Value <= RHS.Value;
123  }
124 
125  bool operator>=(const PointerIntPair &RHS) const {
126    return Value >= RHS.Value;
127  }
128};
129 
130// Specialize is_trivially_copyable to avoid limitation of llvm::is_trivially_copyable
131// when compiled with gcc 4.9.
132template <typename PointerTy, unsigned IntBits, typename IntType,
133          typename PtrTraits,
134          typename Info>
135struct is_trivially_copyable<PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info>> : std::true_type {
136#ifdef HAVE_STD_IS_TRIVIALLY_COPYABLE
137  static_assert(std::is_trivially_copyable<PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info>>::value,
138                "inconsistent behavior between llvm:: and std:: implementation of is_trivially_copyable");
139#endif
140};
141 
142 
143template <typename PointerT, unsigned IntBits, typename PtrTraits>
144struct PointerIntPairInfo {
145  static_assert(PtrTraits::NumLowBitsAvailable <
146                    std::numeric_limits<uintptr_t>::digits,
147                "cannot use a pointer type that has all bits free");
148  static_assert(IntBits <= PtrTraits::NumLowBitsAvailable,
149                "PointerIntPair with integer size too large for pointer");
150  enum MaskAndShiftConstants : uintptr_t {
151    /// PointerBitMask - The bits that come from the pointer.
152    PointerBitMask =
153        ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable) - 1),
154 
155    /// IntShift - The number of low bits that we reserve for other uses, and
156    /// keep zero.
157    IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable - IntBits,
158 
159    /// IntMask - This is the unshifted mask for valid bits of the int type.
160    IntMask = (uintptr_t)(((intptr_t)1 << IntBits) - 1),
161 
162    // ShiftedIntMask - This is the bits for the integer shifted in place.
163    ShiftedIntMask = (uintptr_t)(IntMask << IntShift)
164  };
165 
166  static PointerT getPointer(intptr_t Value) {
167    return PtrTraits::getFromVoidPointer(
168        reinterpret_cast<void *>(Value & PointerBitMask));
169  }
170 
171  static intptr_t getInt(intptr_t Value) {
172    return (Value >> IntShift) & IntMask;
173  }
174 
175  static intptr_t updatePointer(intptr_t OrigValue, PointerT Ptr) {
176    intptr_t PtrWord =
177        reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr));
178    assert((PtrWord & ~PointerBitMask) == 0 &&(static_cast <bool> ((PtrWord & ~PointerBitMask) ==
 0 && "Pointer is not sufficiently aligned") ? void (
0) : __assert_fail ("(PtrWord & ~PointerBitMask) == 0 && \"Pointer is not sufficiently aligned\""
, "llvm/include/llvm/ADT/PointerIntPair.h", 179, __extension__
 __PRETTY_FUNCTION__))
179           "Pointer is not sufficiently aligned")(static_cast <bool> ((PtrWord & ~PointerBitMask) ==
 0 && "Pointer is not sufficiently aligned") ? void (
0) : __assert_fail ("(PtrWord & ~PointerBitMask) == 0 && \"Pointer is not sufficiently aligned\""
, "llvm/include/llvm/ADT/PointerIntPair.h", 179, __extension__
 __PRETTY_FUNCTION__));
180    // Preserve all low bits, just update the pointer.
181    return PtrWord | (OrigValue & ~PointerBitMask);
182  }
183 
184  static intptr_t updateInt(intptr_t OrigValue, intptr_t Int) {
185    intptr_t IntWord = static_cast<intptr_t>(Int);
32
←
'IntWord' initialized to the value of 'Int'→
186    assert((IntWord & ~IntMask) == 0 && "Integer too large for field")(static_cast <bool> ((IntWord & ~IntMask) == 0 &&
 "Integer too large for field") ? void (0) : __assert_fail ("(IntWord & ~IntMask) == 0 && \"Integer too large for field\""
, "llvm/include/llvm/ADT/PointerIntPair.h", 186, __extension__
 __PRETTY_FUNCTION__));
33
←
'?' condition is true→
187 
188    // Preserve all bits other than the ones we are updating.
189    return (OrigValue & ~ShiftedIntMask) | IntWord << IntShift;
34
←
The result of the left shift is undefined due to shifting '0' by '2', which is unrepresentable in the unsigned version of the return type 'intptr_t'
190  }
191};
192 
193// Provide specialization of DenseMapInfo for PointerIntPair.
194template <typename PointerTy, unsigned IntBits, typename IntType>
195struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType>, void> {
196  using Ty = PointerIntPair<PointerTy, IntBits, IntType>;
197 
198  static Ty getEmptyKey() {
199    uintptr_t Val = static_cast<uintptr_t>(-1);
200    Val <<= PointerLikeTypeTraits<Ty>::NumLowBitsAvailable;
201    return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val));
202  }
203 
204  static Ty getTombstoneKey() {
205    uintptr_t Val = static_cast<uintptr_t>(-2);
206    Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable;
207    return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val));
208  }
209 
210  static unsigned getHashValue(Ty V) {
211    uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue());
212    return unsigned(IV) ^ unsigned(IV >> 9);
213  }
214 
215  static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; }
216};
217 
218// Teach SmallPtrSet that PointerIntPair is "basically a pointer".
219template <typename PointerTy, unsigned IntBits, typename IntType,
220          typename PtrTraits>
221struct PointerLikeTypeTraits<
222    PointerIntPair<PointerTy, IntBits, IntType, PtrTraits>> {
223  static inline void *
224  getAsVoidPointer(const PointerIntPair<PointerTy, IntBits, IntType> &P) {
225    return P.getOpaqueValue();
226  }
227 
228  static inline PointerIntPair<PointerTy, IntBits, IntType>
229  getFromVoidPointer(void *P) {
230    return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P);
231  }
232 
233  static inline PointerIntPair<PointerTy, IntBits, IntType>
234  getFromVoidPointer(const void *P) {
235    return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P);
236  }
237 
238  static constexpr int NumLowBitsAvailable =
239      PtrTraits::NumLowBitsAvailable - IntBits;
240};
241 
242} // end namespace llvm
243 
244#endif // LLVM_ADT_POINTERINTPAIR_H