LCOV - code coverage report
Current view: top level - lib/Analysis - LoopAccessAnalysis.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 658 681 96.6 %
Date: 2018-10-20 13:21:21 Functions: 55 57 96.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- LoopAccessAnalysis.cpp - Loop Access Analysis Implementation --------==//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // The implementation for the loop memory dependence that was originally
      11             : // developed for the loop vectorizer.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #include "llvm/Analysis/LoopAccessAnalysis.h"
      16             : #include "llvm/ADT/APInt.h"
      17             : #include "llvm/ADT/DenseMap.h"
      18             : #include "llvm/ADT/DepthFirstIterator.h"
      19             : #include "llvm/ADT/EquivalenceClasses.h"
      20             : #include "llvm/ADT/PointerIntPair.h"
      21             : #include "llvm/ADT/STLExtras.h"
      22             : #include "llvm/ADT/SetVector.h"
      23             : #include "llvm/ADT/SmallPtrSet.h"
      24             : #include "llvm/ADT/SmallSet.h"
      25             : #include "llvm/ADT/SmallVector.h"
      26             : #include "llvm/ADT/iterator_range.h"
      27             : #include "llvm/Analysis/AliasAnalysis.h"
      28             : #include "llvm/Analysis/AliasSetTracker.h"
      29             : #include "llvm/Analysis/LoopAnalysisManager.h"
      30             : #include "llvm/Analysis/LoopInfo.h"
      31             : #include "llvm/Analysis/MemoryLocation.h"
      32             : #include "llvm/Analysis/OptimizationRemarkEmitter.h"
      33             : #include "llvm/Analysis/ScalarEvolution.h"
      34             : #include "llvm/Analysis/ScalarEvolutionExpander.h"
      35             : #include "llvm/Analysis/ScalarEvolutionExpressions.h"
      36             : #include "llvm/Analysis/TargetLibraryInfo.h"
      37             : #include "llvm/Analysis/ValueTracking.h"
      38             : #include "llvm/Analysis/VectorUtils.h"
      39             : #include "llvm/IR/BasicBlock.h"
      40             : #include "llvm/IR/Constants.h"
      41             : #include "llvm/IR/DataLayout.h"
      42             : #include "llvm/IR/DebugLoc.h"
      43             : #include "llvm/IR/DerivedTypes.h"
      44             : #include "llvm/IR/DiagnosticInfo.h"
      45             : #include "llvm/IR/Dominators.h"
      46             : #include "llvm/IR/Function.h"
      47             : #include "llvm/IR/IRBuilder.h"
      48             : #include "llvm/IR/InstrTypes.h"
      49             : #include "llvm/IR/Instruction.h"
      50             : #include "llvm/IR/Instructions.h"
      51             : #include "llvm/IR/Operator.h"
      52             : #include "llvm/IR/PassManager.h"
      53             : #include "llvm/IR/Type.h"
      54             : #include "llvm/IR/Value.h"
      55             : #include "llvm/IR/ValueHandle.h"
      56             : #include "llvm/Pass.h"
      57             : #include "llvm/Support/Casting.h"
      58             : #include "llvm/Support/CommandLine.h"
      59             : #include "llvm/Support/Debug.h"
      60             : #include "llvm/Support/ErrorHandling.h"
      61             : #include "llvm/Support/raw_ostream.h"
      62             : #include <algorithm>
      63             : #include <cassert>
      64             : #include <cstdint>
      65             : #include <cstdlib>
      66             : #include <iterator>
      67             : #include <utility>
      68             : #include <vector>
      69             : 
      70             : using namespace llvm;
      71             : 
      72             : #define DEBUG_TYPE "loop-accesses"
      73             : 
      74             : static cl::opt<unsigned, true>
      75             : VectorizationFactor("force-vector-width", cl::Hidden,
      76             :                     cl::desc("Sets the SIMD width. Zero is autoselect."),
      77             :                     cl::location(VectorizerParams::VectorizationFactor));
      78             : unsigned VectorizerParams::VectorizationFactor;
      79             : 
      80             : static cl::opt<unsigned, true>
      81             : VectorizationInterleave("force-vector-interleave", cl::Hidden,
      82             :                         cl::desc("Sets the vectorization interleave count. "
      83             :                                  "Zero is autoselect."),
      84             :                         cl::location(
      85             :                             VectorizerParams::VectorizationInterleave));
      86             : unsigned VectorizerParams::VectorizationInterleave;
      87             : 
      88             : static cl::opt<unsigned, true> RuntimeMemoryCheckThreshold(
      89             :     "runtime-memory-check-threshold", cl::Hidden,
      90             :     cl::desc("When performing memory disambiguation checks at runtime do not "
      91             :              "generate more than this number of comparisons (default = 8)."),
      92             :     cl::location(VectorizerParams::RuntimeMemoryCheckThreshold), cl::init(8));
      93             : unsigned VectorizerParams::RuntimeMemoryCheckThreshold;
      94             : 
      95             : /// The maximum iterations used to merge memory checks
      96             : static cl::opt<unsigned> MemoryCheckMergeThreshold(
      97             :     "memory-check-merge-threshold", cl::Hidden,
      98             :     cl::desc("Maximum number of comparisons done when trying to merge "
      99             :              "runtime memory checks. (default = 100)"),
     100             :     cl::init(100));
     101             : 
     102             : /// Maximum SIMD width.
     103             : const unsigned VectorizerParams::MaxVectorWidth = 64;
     104             : 
     105             : /// We collect dependences up to this threshold.
     106             : static cl::opt<unsigned>
     107             :     MaxDependences("max-dependences", cl::Hidden,
     108             :                    cl::desc("Maximum number of dependences collected by "
     109             :                             "loop-access analysis (default = 100)"),
     110             :                    cl::init(100));
     111             : 
     112             : /// This enables versioning on the strides of symbolically striding memory
     113             : /// accesses in code like the following.
     114             : ///   for (i = 0; i < N; ++i)
     115             : ///     A[i * Stride1] += B[i * Stride2] ...
     116             : ///
     117             : /// Will be roughly translated to
     118             : ///    if (Stride1 == 1 && Stride2 == 1) {
     119             : ///      for (i = 0; i < N; i+=4)
     120             : ///       A[i:i+3] += ...
     121             : ///    } else
     122             : ///      ...
     123             : static cl::opt<bool> EnableMemAccessVersioning(
     124             :     "enable-mem-access-versioning", cl::init(true), cl::Hidden,
     125             :     cl::desc("Enable symbolic stride memory access versioning"));
     126             : 
     127             : /// Enable store-to-load forwarding conflict detection. This option can
     128             : /// be disabled for correctness testing.
     129             : static cl::opt<bool> EnableForwardingConflictDetection(
     130             :     "store-to-load-forwarding-conflict-detection", cl::Hidden,
     131             :     cl::desc("Enable conflict detection in loop-access analysis"),
     132             :     cl::init(true));
     133             : 
     134        4831 : bool VectorizerParams::isInterleaveForced() {
     135        4831 :   return ::VectorizationInterleave.getNumOccurrences() > 0;
     136             : }
     137             : 
     138          43 : Value *llvm::stripIntegerCast(Value *V) {
     139             :   if (auto *CI = dyn_cast<CastInst>(V))
     140           6 :     if (CI->getOperand(0)->getType()->isIntegerTy())
     141             :       return CI->getOperand(0);
     142             :   return V;
     143             : }
     144             : 
     145       29549 : const SCEV *llvm::replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE,
     146             :                                             const ValueToValueMap &PtrToStride,
     147             :                                             Value *Ptr, Value *OrigPtr) {
     148       29549 :   const SCEV *OrigSCEV = PSE.getSCEV(Ptr);
     149             : 
     150             :   // If there is an entry in the map return the SCEV of the pointer with the
     151             :   // symbolic stride replaced by one.
     152             :   ValueToValueMap::const_iterator SI =
     153       59098 :       PtrToStride.find(OrigPtr ? OrigPtr : Ptr);
     154       29549 :   if (SI != PtrToStride.end()) {
     155          43 :     Value *StrideVal = SI->second;
     156             : 
     157             :     // Strip casts.
     158          43 :     StrideVal = stripIntegerCast(StrideVal);
     159             : 
     160          43 :     ScalarEvolution *SE = PSE.getSE();
     161          43 :     const auto *U = cast<SCEVUnknown>(SE->getSCEV(StrideVal));
     162             :     const auto *CT =
     163          43 :         static_cast<const SCEVConstant *>(SE->getOne(StrideVal->getType()));
     164             : 
     165          43 :     PSE.addPredicate(*SE->getEqualPredicate(U, CT));
     166          43 :     auto *Expr = PSE.getSCEV(Ptr);
     167             : 
     168             :     LLVM_DEBUG(dbgs() << "LAA: Replacing SCEV: " << *OrigSCEV
     169             :                       << " by: " << *Expr << "\n");
     170          43 :     return Expr;
     171             :   }
     172             : 
     173             :   // Otherwise, just return the SCEV of the original pointer.
     174             :   return OrigSCEV;
     175             : }
     176             : 
     177             : /// Calculate Start and End points of memory access.
     178             : /// Let's assume A is the first access and B is a memory access on N-th loop
     179             : /// iteration. Then B is calculated as:
     180             : ///   B = A + Step*N .
     181             : /// Step value may be positive or negative.
     182             : /// N is a calculated back-edge taken count:
     183             : ///     N = (TripCount > 0) ? RoundDown(TripCount -1 , VF) : 0
     184             : /// Start and End points are calculated in the following way:
     185             : /// Start = UMIN(A, B) ; End = UMAX(A, B) + SizeOfElt,
     186             : /// where SizeOfElt is the size of single memory access in bytes.
     187             : ///
     188             : /// There is no conflict when the intervals are disjoint:
     189             : /// NoConflict = (P2.Start >= P1.End) || (P1.Start >= P2.End)
     190        4271 : void RuntimePointerChecking::insert(Loop *Lp, Value *Ptr, bool WritePtr,
     191             :                                     unsigned DepSetId, unsigned ASId,
     192             :                                     const ValueToValueMap &Strides,
     193             :                                     PredicatedScalarEvolution &PSE) {
     194             :   // Get the stride replaced scev.
     195        4271 :   const SCEV *Sc = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);
     196        4271 :   ScalarEvolution *SE = PSE.getSE();
     197             : 
     198             :   const SCEV *ScStart;
     199             :   const SCEV *ScEnd;
     200             : 
     201        4271 :   if (SE->isLoopInvariant(Sc, Lp))
     202        1858 :     ScStart = ScEnd = Sc;
     203             :   else {
     204        2413 :     const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
     205             :     assert(AR && "Invalid addrec expression");
     206        2413 :     const SCEV *Ex = PSE.getBackedgeTakenCount();
     207             : 
     208        2413 :     ScStart = AR->getStart();
     209        2413 :     ScEnd = AR->evaluateAtIteration(Ex, *SE);
     210        2413 :     const SCEV *Step = AR->getStepRecurrence(*SE);
     211             : 
     212             :     // For expressions with negative step, the upper bound is ScStart and the
     213             :     // lower bound is ScEnd.
     214             :     if (const auto *CStep = dyn_cast<SCEVConstant>(Step)) {
     215        2391 :       if (CStep->getValue()->isNegative())
     216             :         std::swap(ScStart, ScEnd);
     217             :     } else {
     218             :       // Fallback case: the step is not constant, but we can still
     219             :       // get the upper and lower bounds of the interval by using min/max
     220             :       // expressions.
     221          22 :       ScStart = SE->getUMinExpr(ScStart, ScEnd);
     222          44 :       ScEnd = SE->getUMaxExpr(AR->getStart(), ScEnd);
     223             :     }
     224             :     // Add the size of the pointed element to ScEnd.
     225             :     unsigned EltSize =
     226        2413 :       Ptr->getType()->getPointerElementType()->getScalarSizeInBits() / 8;
     227        2413 :     const SCEV *EltSizeSCEV = SE->getConstant(ScEnd->getType(), EltSize);
     228        2413 :     ScEnd = SE->getAddExpr(ScEnd, EltSizeSCEV);
     229             :   }
     230             : 
     231        4271 :   Pointers.emplace_back(Ptr, ScStart, ScEnd, WritePtr, DepSetId, ASId, Sc);
     232        4271 : }
     233             : 
     234             : SmallVector<RuntimePointerChecking::PointerCheck, 4>
     235         680 : RuntimePointerChecking::generateChecks() const {
     236             :   SmallVector<PointerCheck, 4> Checks;
     237             : 
     238        2625 :   for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
     239        4232 :     for (unsigned J = I + 1; J < CheckingGroups.size(); ++J) {
     240             :       const RuntimePointerChecking::CheckingPtrGroup &CGI = CheckingGroups[I];
     241             :       const RuntimePointerChecking::CheckingPtrGroup &CGJ = CheckingGroups[J];
     242             : 
     243        2287 :       if (needsChecking(CGI, CGJ))
     244        1946 :         Checks.push_back(std::make_pair(&CGI, &CGJ));
     245             :     }
     246             :   }
     247         680 :   return Checks;
     248             : }
     249             : 
     250         680 : void RuntimePointerChecking::generateChecks(
     251             :     MemoryDepChecker::DepCandidates &DepCands, bool UseDependencies) {
     252             :   assert(Checks.empty() && "Checks is not empty");
     253         680 :   groupChecks(DepCands, UseDependencies);
     254         680 :   Checks = generateChecks();
     255         680 : }
     256             : 
     257        2287 : bool RuntimePointerChecking::needsChecking(const CheckingPtrGroup &M,
     258             :                                            const CheckingPtrGroup &N) const {
     259        2765 :   for (unsigned I = 0, EI = M.Members.size(); EI != I; ++I)
     260        2947 :     for (unsigned J = 0, EJ = N.Members.size(); EJ != J; ++J)
     261        7407 :       if (needsChecking(M.Members[I], N.Members[J]))
     262             :         return true;
     263             :   return false;
     264             : }
     265             : 
     266             : /// Compare \p I and \p J and return the minimum.
     267             : /// Return nullptr in case we couldn't find an answer.
     268        3279 : static const SCEV *getMinFromExprs(const SCEV *I, const SCEV *J,
     269             :                                    ScalarEvolution *SE) {
     270        3279 :   const SCEV *Diff = SE->getMinusSCEV(J, I);
     271             :   const SCEVConstant *C = dyn_cast<const SCEVConstant>(Diff);
     272             : 
     273             :   if (!C)
     274             :     return nullptr;
     275        3264 :   if (C->getValue()->isNegative())
     276         636 :     return J;
     277             :   return I;
     278             : }
     279             : 
     280        1647 : bool RuntimePointerChecking::CheckingPtrGroup::addPointer(unsigned Index) {
     281        1647 :   const SCEV *Start = RtCheck.Pointers[Index].Start;
     282        1647 :   const SCEV *End = RtCheck.Pointers[Index].End;
     283             : 
     284             :   // Compare the starts and ends with the known minimum and maximum
     285             :   // of this set. We need to know how we compare against the min/max
     286             :   // of the set in order to be able to emit memchecks.
     287        1647 :   const SCEV *Min0 = getMinFromExprs(Start, Low, RtCheck.SE);
     288        1647 :   if (!Min0)
     289             :     return false;
     290             : 
     291        1632 :   const SCEV *Min1 = getMinFromExprs(End, High, RtCheck.SE);
     292        1632 :   if (!Min1)
     293             :     return false;
     294             : 
     295             :   // Update the low bound  expression if we've found a new min value.
     296        1632 :   if (Min0 == Start)
     297        1088 :     Low = Start;
     298             : 
     299             :   // Update the high bound expression if we've found a new max value.
     300        1632 :   if (Min1 != End)
     301          92 :     High = End;
     302             : 
     303        1632 :   Members.push_back(Index);
     304        1632 :   return true;
     305             : }
     306             : 
     307         680 : void RuntimePointerChecking::groupChecks(
     308             :     MemoryDepChecker::DepCandidates &DepCands, bool UseDependencies) {
     309             :   // We build the groups from dependency candidates equivalence classes
     310             :   // because:
     311             :   //    - We know that pointers in the same equivalence class share
     312             :   //      the same underlying object and therefore there is a chance
     313             :   //      that we can compare pointers
     314             :   //    - We wouldn't be able to merge two pointers for which we need
     315             :   //      to emit a memcheck. The classes in DepCands are already
     316             :   //      conveniently built such that no two pointers in the same
     317             :   //      class need checking against each other.
     318             : 
     319             :   // We use the following (greedy) algorithm to construct the groups
     320             :   // For every pointer in the equivalence class:
     321             :   //   For each existing group:
     322             :   //   - if the difference between this pointer and the min/max bounds
     323             :   //     of the group is a constant, then make the pointer part of the
     324             :   //     group and update the min/max bounds of that group as required.
     325             : 
     326         680 :   CheckingGroups.clear();
     327             : 
     328             :   // If we need to check two pointers to the same underlying object
     329             :   // with a non-constant difference, we shouldn't perform any pointer
     330             :   // grouping with those pointers. This is because we can easily get
     331             :   // into cases where the resulting check would return false, even when
     332             :   // the accesses are safe.
     333             :   //
     334             :   // The following example shows this:
     335             :   // for (i = 0; i < 1000; ++i)
     336             :   //   a[5000 + i * m] = a[i] + a[i + 9000]
     337             :   //
     338             :   // Here grouping gives a check of (5000, 5000 + 1000 * m) against
     339             :   // (0, 10000) which is always false. However, if m is 1, there is no
     340             :   // dependence. Not grouping the checks for a[i] and a[i + 9000] allows
     341             :   // us to perform an accurate check in this case.
     342             :   //
     343             :   // The above case requires that we have an UnknownDependence between
     344             :   // accesses to the same underlying object. This cannot happen unless
     345             :   // ShouldRetryWithRuntimeCheck is set, and therefore UseDependencies
     346             :   // is also false. In this case we will use the fallback path and create
     347             :   // separate checking groups for all pointers.
     348             : 
     349             :   // If we don't have the dependency partitions, construct a new
     350             :   // checking pointer group for each pointer. This is also required
     351             :   // for correctness, because in this case we can have checking between
     352             :   // pointers to the same underlying object.
     353         680 :   if (!UseDependencies) {
     354          69 :     for (unsigned I = 0; I < Pointers.size(); ++I)
     355          98 :       CheckingGroups.push_back(CheckingPtrGroup(I, *this));
     356          20 :     return;
     357             :   }
     358             : 
     359             :   unsigned TotalComparisons = 0;
     360             : 
     361             :   DenseMap<Value *, unsigned> PositionMap;
     362        3318 :   for (unsigned Index = 0; Index < Pointers.size(); ++Index)
     363        2658 :     PositionMap[Pointers[Index].PointerValue] = Index;
     364             : 
     365             :   // We need to keep track of what pointers we've already seen so we
     366             :   // don't process them twice.
     367         660 :   SmallSet<unsigned, 2> Seen;
     368             : 
     369             :   // Go through all equivalence classes, get the "pointer check groups"
     370             :   // and add them to the overall solution. We use the order in which accesses
     371             :   // appear in 'Pointers' to enforce determinism.
     372        3318 :   for (unsigned I = 0; I < Pointers.size(); ++I) {
     373             :     // We've seen this pointer before, and therefore already processed
     374             :     // its equivalence class.
     375        2658 :     if (Seen.count(I))
     376         771 :       continue;
     377             : 
     378             :     MemoryDepChecker::MemAccessInfo Access(Pointers[I].PointerValue,
     379        1887 :                                            Pointers[I].IsWritePtr);
     380             : 
     381        1887 :     SmallVector<CheckingPtrGroup, 2> Groups;
     382        1887 :     auto LeaderI = DepCands.findValue(DepCands.getLeaderValue(Access));
     383             : 
     384             :     // Because DepCands is constructed by visiting accesses in the order in
     385             :     // which they appear in alias sets (which is deterministic) and the
     386             :     // iteration order within an equivalence class member is only dependent on
     387             :     // the order in which unions and insertions are performed on the
     388             :     // equivalence class, the iteration order is deterministic.
     389             :     for (auto MI = DepCands.member_begin(LeaderI), ME = DepCands.member_end();
     390        5415 :          MI != ME; ++MI) {
     391        7056 :       unsigned Pointer = PositionMap[MI->getPointer()];
     392             :       bool Merged = false;
     393             :       // Mark this pointer as seen.
     394        3528 :       Seen.insert(Pointer);
     395             : 
     396             :       // Go through all the existing sets and see if we can find one
     397             :       // which can include this pointer.
     398        3543 :       for (CheckingPtrGroup &Group : Groups) {
     399             :         // Don't perform more than a certain amount of comparisons.
     400             :         // This should limit the cost of grouping the pointers to something
     401             :         // reasonable.  If we do end up hitting this threshold, the algorithm
     402             :         // will create separate groups for all remaining pointers.
     403        1647 :         if (TotalComparisons > MemoryCheckMergeThreshold)
     404             :           break;
     405             : 
     406        1647 :         TotalComparisons++;
     407             : 
     408        1647 :         if (Group.addPointer(Pointer)) {
     409             :           Merged = true;
     410             :           break;
     411             :         }
     412             :       }
     413             : 
     414        3528 :       if (!Merged)
     415             :         // We couldn't add this pointer to any existing set or the threshold
     416             :         // for the number of comparisons has been reached. Create a new group
     417             :         // to hold the current pointer.
     418        3792 :         Groups.push_back(CheckingPtrGroup(Pointer, *this));
     419             :     }
     420             : 
     421             :     // We've computed the grouped checks for this partition.
     422             :     // Save the results and continue with the next one.
     423        1887 :     std::copy(Groups.begin(), Groups.end(), std::back_inserter(CheckingGroups));
     424             :   }
     425             : }
     426             : 
     427          60 : bool RuntimePointerChecking::arePointersInSamePartition(
     428             :     const SmallVectorImpl<int> &PtrToPartition, unsigned PtrIdx1,
     429             :     unsigned PtrIdx2) {
     430         120 :   return (PtrToPartition[PtrIdx1] != -1 &&
     431         120 :           PtrToPartition[PtrIdx1] == PtrToPartition[PtrIdx2]);
     432             : }
     433             : 
     434        2556 : bool RuntimePointerChecking::needsChecking(unsigned I, unsigned J) const {
     435        2556 :   const PointerInfo &PointerI = Pointers[I];
     436        2556 :   const PointerInfo &PointerJ = Pointers[J];
     437             : 
     438             :   // No need to check if two readonly pointers intersect.
     439        2556 :   if (!PointerI.IsWritePtr && !PointerJ.IsWritePtr)
     440             :     return false;
     441             : 
     442             :   // Only need to check pointers between two different dependency sets.
     443        2024 :   if (PointerI.DependencySetId == PointerJ.DependencySetId)
     444             :     return false;
     445             : 
     446             :   // Only need to check pointers in the same alias set.
     447        2008 :   if (PointerI.AliasSetId != PointerJ.AliasSetId)
     448           2 :     return false;
     449             : 
     450             :   return true;
     451             : }
     452             : 
     453         105 : void RuntimePointerChecking::printChecks(
     454             :     raw_ostream &OS, const SmallVectorImpl<PointerCheck> &Checks,
     455             :     unsigned Depth) const {
     456             :   unsigned N = 0;
     457         186 :   for (const auto &Check : Checks) {
     458          81 :     const auto &First = Check.first->Members, &Second = Check.second->Members;
     459             : 
     460          81 :     OS.indent(Depth) << "Check " << N++ << ":\n";
     461             : 
     462          81 :     OS.indent(Depth + 2) << "Comparing group (" << Check.first << "):\n";
     463         191 :     for (unsigned K = 0; K < First.size(); ++K)
     464         110 :       OS.indent(Depth + 2) << *Pointers[First[K]].PointerValue << "\n";
     465             : 
     466          81 :     OS.indent(Depth + 2) << "Against group (" << Check.second << "):\n";
     467         169 :     for (unsigned K = 0; K < Second.size(); ++K)
     468          88 :       OS.indent(Depth + 2) << *Pointers[Second[K]].PointerValue << "\n";
     469             :   }
     470         105 : }
     471             : 
     472         105 : void RuntimePointerChecking::print(raw_ostream &OS, unsigned Depth) const {
     473             : 
     474         105 :   OS.indent(Depth) << "Run-time memory checks:\n";
     475         105 :   printChecks(OS, Checks, Depth);
     476             : 
     477         105 :   OS.indent(Depth) << "Grouped accesses:\n";
     478         206 :   for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
     479             :     const auto &CG = CheckingGroups[I];
     480             : 
     481         101 :     OS.indent(Depth + 2) << "Group " << &CG << ":\n";
     482         101 :     OS.indent(Depth + 4) << "(Low: " << *CG.Low << " High: " << *CG.High
     483         101 :                          << ")\n";
     484         228 :     for (unsigned J = 0; J < CG.Members.size(); ++J) {
     485         127 :       OS.indent(Depth + 6) << "Member: " << *Pointers[CG.Members[J]].Expr
     486         127 :                            << "\n";
     487             :     }
     488             :   }
     489         105 : }
     490             : 
     491             : namespace {
     492             : 
     493             : /// Analyses memory accesses in a loop.
     494             : ///
     495             : /// Checks whether run time pointer checks are needed and builds sets for data
     496             : /// dependence checking.
     497             : class AccessAnalysis {
     498             : public:
     499             :   /// Read or write access location.
     500             :   typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
     501             :   typedef SmallVector<MemAccessInfo, 8> MemAccessInfoList;
     502             : 
     503        1588 :   AccessAnalysis(const DataLayout &Dl, Loop *TheLoop, AliasAnalysis *AA,
     504             :                  LoopInfo *LI, MemoryDepChecker::DepCandidates &DA,
     505             :                  PredicatedScalarEvolution &PSE)
     506        1588 :       : DL(Dl), TheLoop(TheLoop), AST(*AA), LI(LI), DepCands(DA),
     507        1588 :         IsRTCheckAnalysisNeeded(false), PSE(PSE) {}
     508             : 
     509             :   /// Register a load  and whether it is only read from.
     510        3903 :   void addLoad(MemoryLocation &Loc, bool IsReadOnly) {
     511        3903 :     Value *Ptr = const_cast<Value*>(Loc.Ptr);
     512        3903 :     AST.add(Ptr, LocationSize::unknown(), Loc.AATags);
     513        7806 :     Accesses.insert(MemAccessInfo(Ptr, false));
     514        3903 :     if (IsReadOnly)
     515        3659 :       ReadOnlyPtr.insert(Ptr);
     516        3903 :   }
     517             : 
     518             :   /// Register a store.
     519        3676 :   void addStore(MemoryLocation &Loc) {
     520        3676 :     Value *Ptr = const_cast<Value*>(Loc.Ptr);
     521        3676 :     AST.add(Ptr, LocationSize::unknown(), Loc.AATags);
     522        7352 :     Accesses.insert(MemAccessInfo(Ptr, true));
     523        3676 :   }
     524             : 
     525             :   /// Check if we can emit a run-time no-alias check for \p Access.
     526             :   ///
     527             :   /// Returns true if we can emit a run-time no alias check for \p Access.
     528             :   /// If we can check this access, this also adds it to a dependence set and
     529             :   /// adds a run-time to check for it to \p RtCheck. If \p Assume is true,
     530             :   /// we will attempt to use additional run-time checks in order to get
     531             :   /// the bounds of the pointer.
     532             :   bool createCheckForAccess(RuntimePointerChecking &RtCheck,
     533             :                             MemAccessInfo Access,
     534             :                             const ValueToValueMap &Strides,
     535             :                             DenseMap<Value *, unsigned> &DepSetId,
     536             :                             Loop *TheLoop, unsigned &RunningDepId,
     537             :                             unsigned ASId, bool ShouldCheckStride,
     538             :                             bool Assume);
     539             : 
     540             :   /// Check whether we can check the pointers at runtime for
     541             :   /// non-intersection.
     542             :   ///
     543             :   /// Returns true if we need no check or if we do and we can generate them
     544             :   /// (i.e. the pointers have computable bounds).
     545             :   bool canCheckPtrAtRT(RuntimePointerChecking &RtCheck, ScalarEvolution *SE,
     546             :                        Loop *TheLoop, const ValueToValueMap &Strides,
     547             :                        bool ShouldCheckWrap = false);
     548             : 
     549             :   /// Goes over all memory accesses, checks whether a RT check is needed
     550             :   /// and builds sets of dependent accesses.
     551             :   void buildDependenceSets() {
     552        1327 :     processMemAccesses();
     553             :   }
     554             : 
     555             :   /// Initial processing of memory accesses determined that we need to
     556             :   /// perform dependency checking.
     557             :   ///
     558             :   /// Note that this can later be cleared if we retry memcheck analysis without
     559             :   /// dependency checking (i.e. ShouldRetryWithRuntimeCheck).
     560        1029 :   bool isDependencyCheckNeeded() { return !CheckDeps.empty(); }
     561             : 
     562             :   /// We decided that no dependence analysis would be used.  Reset the state.
     563             :   void resetDepChecks(MemoryDepChecker &DepChecker) {
     564             :     CheckDeps.clear();
     565             :     DepChecker.clearDependences();
     566             :   }
     567             : 
     568             :   MemAccessInfoList &getDependenciesToCheck() { return CheckDeps; }
     569             : 
     570             : private:
     571             :   typedef SetVector<MemAccessInfo> PtrAccessSet;
     572             : 
     573             :   /// Go over all memory access and check whether runtime pointer checks
     574             :   /// are needed and build sets of dependency check candidates.
     575             :   void processMemAccesses();
     576             : 
     577             :   /// Set of all accesses.
     578             :   PtrAccessSet Accesses;
     579             : 
     580             :   const DataLayout &DL;
     581             : 
     582             :   /// The loop being checked.
     583             :   const Loop *TheLoop;
     584             : 
     585             :   /// List of accesses that need a further dependence check.
     586             :   MemAccessInfoList CheckDeps;
     587             : 
     588             :   /// Set of pointers that are read only.
     589             :   SmallPtrSet<Value*, 16> ReadOnlyPtr;
     590             : 
     591             :   /// An alias set tracker to partition the access set by underlying object and
     592             :   //intrinsic property (such as TBAA metadata).
     593             :   AliasSetTracker AST;
     594             : 
     595             :   LoopInfo *LI;
     596             : 
     597             :   /// Sets of potentially dependent accesses - members of one set share an
     598             :   /// underlying pointer. The set "CheckDeps" identfies which sets really need a
     599             :   /// dependence check.
     600             :   MemoryDepChecker::DepCandidates &DepCands;
     601             : 
     602             :   /// Initial processing of memory accesses determined that we may need
     603             :   /// to add memchecks.  Perform the analysis to determine the necessary checks.
     604             :   ///
     605             :   /// Note that, this is different from isDependencyCheckNeeded.  When we retry
     606             :   /// memcheck analysis without dependency checking
     607             :   /// (i.e. ShouldRetryWithRuntimeCheck), isDependencyCheckNeeded is cleared
     608             :   /// while this remains set if we have potentially dependent accesses.
     609             :   bool IsRTCheckAnalysisNeeded;
     610             : 
     611             :   /// The SCEV predicate containing all the SCEV-related assumptions.
     612             :   PredicatedScalarEvolution &PSE;
     613             : };
     614             : 
     615             : } // end anonymous namespace
     616             : 
     617             : /// Check whether a pointer can participate in a runtime bounds check.
     618             : /// If \p Assume, try harder to prove that we can compute the bounds of \p Ptr
     619             : /// by adding run-time checks (overflow checks) if necessary.
     620        4650 : static bool hasComputableBounds(PredicatedScalarEvolution &PSE,
     621             :                                 const ValueToValueMap &Strides, Value *Ptr,
     622             :                                 Loop *L, bool Assume) {
     623        4650 :   const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);
     624             : 
     625             :   // The bounds for loop-invariant pointer is trivial.
     626        4650 :   if (PSE.getSE()->isLoopInvariant(PtrScev, L))
     627             :     return true;
     628             : 
     629             :   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
     630             : 
     631        2792 :   if (!AR && Assume)
     632         145 :     AR = PSE.getAsAddRec(Ptr);
     633             : 
     634        2792 :   if (!AR)
     635             :     return false;
     636             : 
     637        2419 :   return AR->isAffine();
     638             : }
     639             : 
     640             : /// Check whether a pointer address cannot wrap.
     641          51 : static bool isNoWrap(PredicatedScalarEvolution &PSE,
     642             :                      const ValueToValueMap &Strides, Value *Ptr, Loop *L) {
     643          51 :   const SCEV *PtrScev = PSE.getSCEV(Ptr);
     644          51 :   if (PSE.getSE()->isLoopInvariant(PtrScev, L))
     645             :     return true;
     646             : 
     647          48 :   int64_t Stride = getPtrStride(PSE, Ptr, L, Strides);
     648          48 :   if (Stride == 1 || PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW))
     649          44 :     return true;
     650             : 
     651             :   return false;
     652             : }
     653             : 
     654        4650 : bool AccessAnalysis::createCheckForAccess(RuntimePointerChecking &RtCheck,
     655             :                                           MemAccessInfo Access,
     656             :                                           const ValueToValueMap &StridesMap,
     657             :                                           DenseMap<Value *, unsigned> &DepSetId,
     658             :                                           Loop *TheLoop, unsigned &RunningDepId,
     659             :                                           unsigned ASId, bool ShouldCheckWrap,
     660             :                                           bool Assume) {
     661             :   Value *Ptr = Access.getPointer();
     662             : 
     663        4650 :   if (!hasComputableBounds(PSE, StridesMap, Ptr, TheLoop, Assume))
     664             :     return false;
     665             : 
     666             :   // When we run after a failing dependency check we have to make sure
     667             :   // we don't have wrapping pointers.
     668        4273 :   if (ShouldCheckWrap && !isNoWrap(PSE, StridesMap, Ptr, TheLoop)) {
     669           4 :     auto *Expr = PSE.getSCEV(Ptr);
     670           4 :     if (!Assume || !isa<SCEVAddRecExpr>(Expr))
     671             :       return false;
     672           2 :     PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
     673             :   }
     674             : 
     675             :   // The id of the dependence set.
     676             :   unsigned DepId;
     677             : 
     678        4271 :   if (isDependencyCheckNeeded()) {
     679        4222 :     Value *Leader = DepCands.getLeaderValue(Access).getPointer();
     680             :     unsigned &LeaderId = DepSetId[Leader];
     681        4222 :     if (!LeaderId)
     682        2691 :       LeaderId = RunningDepId++;
     683        4222 :     DepId = LeaderId;
     684             :   } else
     685             :     // Each access has its own dependence set.
     686          49 :     DepId = RunningDepId++;
     687             : 
     688             :   bool IsWrite = Access.getInt();
     689        4271 :   RtCheck.insert(TheLoop, Ptr, IsWrite, DepId, ASId, StridesMap, PSE);
     690             :   LLVM_DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
     691             : 
     692        4271 :   return true;
     693             :  }
     694             : 
     695        1347 : bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
     696             :                                      ScalarEvolution *SE, Loop *TheLoop,
     697             :                                      const ValueToValueMap &StridesMap,
     698             :                                      bool ShouldCheckWrap) {
     699             :   // Find pointers with computable bounds. We are going to use this information
     700             :   // to place a runtime bound check.
     701             :   bool CanDoRT = true;
     702             : 
     703             :   bool NeedRTCheck = false;
     704        1347 :   if (!IsRTCheckAnalysisNeeded) return true;
     705             : 
     706             :   bool IsDepCheckNeeded = isDependencyCheckNeeded();
     707             : 
     708             :   // We assign a consecutive id to access from different alias sets.
     709             :   // Accesses between different groups doesn't need to be checked.
     710             :   unsigned ASId = 1;
     711        2290 :   for (auto &AS : AST) {
     712             :     int NumReadPtrChecks = 0;
     713             :     int NumWritePtrChecks = 0;
     714             :     bool CanDoAliasSetRT = true;
     715             : 
     716             :     // We assign consecutive id to access from different dependence sets.
     717             :     // Accesses within the same set don't need a runtime check.
     718        1261 :     unsigned RunningDepId = 1;
     719             :     DenseMap<Value *, unsigned> DepSetId;
     720             : 
     721             :     SmallVector<MemAccessInfo, 4> Retries;
     722             : 
     723        5758 :     for (auto A : AS) {
     724             :       Value *Ptr = A.getValue();
     725        4497 :       bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true));
     726             :       MemAccessInfo Access(Ptr, IsWrite);
     727             : 
     728        4497 :       if (IsWrite)
     729        3096 :         ++NumWritePtrChecks;
     730             :       else
     731        1401 :         ++NumReadPtrChecks;
     732             : 
     733        4497 :       if (!createCheckForAccess(RtCheck, Access, StridesMap, DepSetId, TheLoop,
     734             :                                 RunningDepId, ASId, ShouldCheckWrap, false)) {
     735             :         LLVM_DEBUG(dbgs() << "LAA: Can't find bounds for ptr:" << *Ptr << '\n');
     736         251 :         Retries.push_back(Access);
     737             :         CanDoAliasSetRT = false;
     738             :       }
     739             :     }
     740             : 
     741             :     // If we have at least two writes or one write and a read then we need to
     742             :     // check them.  But there is no need to checks if there is only one
     743             :     // dependence set for this alias set.
     744             :     //
     745             :     // Note that this function computes CanDoRT and NeedRTCheck independently.
     746             :     // For example CanDoRT=false, NeedRTCheck=false means that we have a pointer
     747             :     // for which we couldn't find the bounds but we don't actually need to emit
     748             :     // any checks so it does not matter.
     749             :     bool NeedsAliasSetRTCheck = false;
     750        1261 :     if (!(IsDepCheckNeeded && CanDoAliasSetRT && RunningDepId == 2))
     751         941 :       NeedsAliasSetRTCheck = (NumWritePtrChecks >= 2 ||
     752         542 :                              (NumReadPtrChecks >= 1 && NumWritePtrChecks >= 1));
     753             : 
     754             :     // We need to perform run-time alias checks, but some pointers had bounds
     755             :     // that couldn't be checked.
     756        1261 :     if (NeedsAliasSetRTCheck && !CanDoAliasSetRT) {
     757             :       // Reset the CanDoSetRt flag and retry all accesses that have failed.
     758             :       // We know that we need these checks, so we can now be more aggressive
     759             :       // and add further checks if required (overflow checks).
     760             :       CanDoAliasSetRT = true;
     761         165 :       for (auto Access : Retries)
     762         153 :         if (!createCheckForAccess(RtCheck, Access, StridesMap, DepSetId,
     763             :                                   TheLoop, RunningDepId, ASId,
     764             :                                   ShouldCheckWrap, /*Assume=*/true)) {
     765             :           CanDoAliasSetRT = false;
     766             :           break;
     767             :         }
     768             :     }
     769             : 
     770             :     CanDoRT &= CanDoAliasSetRT;
     771        1261 :     NeedRTCheck |= NeedsAliasSetRTCheck;
     772        1261 :     ++ASId;
     773             :   }
     774             : 
     775             :   // If the pointers that we would use for the bounds comparison have different
     776             :   // address spaces, assume the values aren't directly comparable, so we can't
     777             :   // use them for the runtime check. We also have to assume they could
     778             :   // overlap. In the future there should be metadata for whether address spaces
     779             :   // are disjoint.
     780        1029 :   unsigned NumPointers = RtCheck.Pointers.size();
     781        5278 :   for (unsigned i = 0; i < NumPointers; ++i) {
     782       18810 :     for (unsigned j = i + 1; j < NumPointers; ++j) {
     783             :       // Only need to check pointers between two different dependency sets.
     784       14561 :       if (RtCheck.Pointers[i].DependencySetId ==
     785       29122 :           RtCheck.Pointers[j].DependencySetId)
     786             :        continue;
     787             :       // Only need to check pointers in the same alias set.
     788       11926 :       if (RtCheck.Pointers[i].AliasSetId != RtCheck.Pointers[j].AliasSetId)
     789             :         continue;
     790             : 
     791             :       Value *PtrI = RtCheck.Pointers[i].PointerValue;
     792             :       Value *PtrJ = RtCheck.Pointers[j].PointerValue;
     793             : 
     794       11920 :       unsigned ASi = PtrI->getType()->getPointerAddressSpace();
     795       11920 :       unsigned ASj = PtrJ->getType()->getPointerAddressSpace();
     796       11920 :       if (ASi != ASj) {
     797             :         LLVM_DEBUG(
     798             :             dbgs() << "LAA: Runtime check would require comparison between"
     799             :                       " different address spaces\n");
     800             :         return false;
     801             :       }
     802             :     }
     803             :   }
     804             : 
     805        1020 :   if (NeedRTCheck && CanDoRT)
     806         680 :     RtCheck.generateChecks(DepCands, IsDepCheckNeeded);
     807             : 
     808             :   LLVM_DEBUG(dbgs() << "LAA: We need to do " << RtCheck.getNumberOfChecks()
     809             :                     << " pointer comparisons.\n");
     810             : 
     811        1020 :   RtCheck.Need = NeedRTCheck;
     812             : 
     813        1020 :   bool CanDoRTIfNeeded = !NeedRTCheck || CanDoRT;
     814        1020 :   if (!CanDoRTIfNeeded)
     815             :     RtCheck.reset();
     816             :   return CanDoRTIfNeeded;
     817             : }
     818             : 
     819        1327 : void AccessAnalysis::processMemAccesses() {
     820             :   // We process the set twice: first we process read-write pointers, last we
     821             :   // process read-only pointers. This allows us to skip dependence tests for
     822             :   // read-only pointers.
     823             : 
     824             :   LLVM_DEBUG(dbgs() << "LAA: Processing memory accesses...\n");
     825             :   LLVM_DEBUG(dbgs() << "  AST: "; AST.dump());
     826             :   LLVM_DEBUG(dbgs() << "LAA:   Accesses(" << Accesses.size() << "):\n");
     827             :   LLVM_DEBUG({
     828             :     for (auto A : Accesses)
     829             :       dbgs() << "\t" << *A.getPointer() << " (" <<
     830             :                 (A.getInt() ? "write" : (ReadOnlyPtr.count(A.getPointer()) ?
     831             :                                          "read-only" : "read")) << ")\n";
     832             :   });
     833             : 
     834             :   // The AliasSetTracker has nicely partitioned our pointers by metadata
     835             :   // compatibility and potential for underlying-object overlap. As a result, we
     836             :   // only need to check for potential pointer dependencies within each alias
     837             :   // set.
     838        3321 :   for (auto &AS : AST) {
     839             :     // Note that both the alias-set tracker and the alias sets themselves used
     840             :     // linked lists internally and so the iteration order here is deterministic
     841             :     // (matching the original instruction order within each set).
     842             : 
     843             :     bool SetHasWrite = false;
     844             : 
     845             :     // Map of pointers to last access encountered.
     846             :     typedef DenseMap<Value*, MemAccessInfo> UnderlyingObjToAccessMap;
     847             :     UnderlyingObjToAccessMap ObjToLastAccess;
     848             : 
     849             :     // Set of access to check after all writes have been processed.
     850        1994 :     PtrAccessSet DeferredAccesses;
     851             : 
     852             :     // Iterate over each alias set twice, once to process read/write pointers,
     853             :     // and then to process read-only pointers.
     854        5982 :     for (int SetIteration = 0; SetIteration < 2; ++SetIteration) {
     855        3988 :       bool UseDeferred = SetIteration > 0;
     856        3988 :       PtrAccessSet &S = UseDeferred ? DeferredAccesses : Accesses;
     857             : 
     858       14412 :       for (auto AV : AS) {
     859             :         Value *Ptr = AV.getValue();
     860             : 
     861             :         // For a single memory access in AliasSetTracker, Accesses may contain
     862             :         // both read and write, and they both need to be handled for CheckDeps.
     863      102662 :         for (auto AC : S) {
     864       92238 :           if (AC.getPointer() != Ptr)
     865       85248 :             continue;
     866             : 
     867             :           bool IsWrite = AC.getInt();
     868             : 
     869             :           // If we're using the deferred access set, then it contains only
     870             :           // reads.
     871       10429 :           bool IsReadOnlyPtr = ReadOnlyPtr.count(Ptr) && !IsWrite;
     872       10429 :           if (UseDeferred && !IsReadOnlyPtr)
     873             :             continue;
     874             :           // Otherwise, the pointer must be in the PtrAccessSet, either as a
     875             :           // read or a write.
     876             :           assert(((IsReadOnlyPtr && UseDeferred) || IsWrite ||
     877             :                   S.count(MemAccessInfo(Ptr, false))) &&
     878             :                  "Alias-set pointer not in the access set?");
     879             : 
     880             :           MemAccessInfo Access(Ptr, IsWrite);
     881       10429 :           DepCands.insert(Access);
     882             : 
     883             :           // Memorize read-only pointers for later processing and skip them in
     884             :           // the first round (they need to be checked after we have seen all
     885             :           // write pointers). Note: we also mark pointer that are not
     886             :           // consecutive as "read-only" pointers (so that we check
     887             :           // "a[b[i]] +="). Hence, we need the second check for "!IsWrite".
     888       10429 :           if (!UseDeferred && IsReadOnlyPtr) {
     889        3439 :             DeferredAccesses.insert(Access);
     890        3439 :             continue;
     891             :           }
     892             : 
     893             :           // If this is a write - check other reads and writes for conflicts. If
     894             :           // this is a read only check other writes for conflicts (but only if
     895             :           // there is no other write to the ptr - this is an optimization to
     896             :           // catch "a[i] = a[i] + " without having to do a dependence check).
     897        6990 :           if ((IsWrite || IsReadOnlyPtr) && SetHasWrite) {
     898        4934 :             CheckDeps.push_back(Access);
     899        4934 :             IsRTCheckAnalysisNeeded = true;
     900             :           }
     901             : 
     902        6990 :           if (IsWrite)
     903             :             SetHasWrite = true;
     904             : 
     905             :           // Create sets of pointers connected by a shared alias set and
     906             :           // underlying object.
     907             :           typedef SmallVector<Value *, 16> ValueVector;
     908             :           ValueVector TempObjects;
     909             : 
     910        6990 :           GetUnderlyingObjects(Ptr, TempObjects, DL, LI);
     911             :           LLVM_DEBUG(dbgs()
     912             :                      << "Underlying objects for pointer " << *Ptr << "\n");
     913       14246 :           for (Value *UnderlyingObj : TempObjects) {
     914             :             // nullptr never alias, don't join sets for pointer that have "null"
     915             :             // in their UnderlyingObjects list.
     916        7339 :             if (isa<ConstantPointerNull>(UnderlyingObj) &&
     917          83 :                 !NullPointerIsDefined(
     918         166 :                     TheLoop->getHeader()->getParent(),
     919             :                     UnderlyingObj->getType()->getPointerAddressSpace()))
     920          83 :               continue;
     921             : 
     922             :             UnderlyingObjToAccessMap::iterator Prev =
     923        7173 :                 ObjToLastAccess.find(UnderlyingObj);
     924        7173 :             if (Prev != ObjToLastAccess.end())
     925        3449 :               DepCands.unionSets(Access, Prev->second);
     926             : 
     927        7173 :             ObjToLastAccess[UnderlyingObj] = Access;
     928             :             LLVM_DEBUG(dbgs() << "  " << *UnderlyingObj << "\n");
     929             :           }
     930             :         }
     931             :       }
     932             :     }
     933             :   }
     934        1327 : }
     935             : 
     936             : static bool isInBoundsGep(Value *Ptr) {
     937             :   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr))
     938        8867 :     return GEP->isInBounds();
     939             :   return false;
     940             : }
     941             : 
     942             : /// Return true if an AddRec pointer \p Ptr is unsigned non-wrapping,
     943             : /// i.e. monotonically increasing/decreasing.
     944        1349 : static bool isNoWrapAddRec(Value *Ptr, const SCEVAddRecExpr *AR,
     945             :                            PredicatedScalarEvolution &PSE, const Loop *L) {
     946             :   // FIXME: This should probably only return true for NUW.
     947        1349 :   if (AR->getNoWrapFlags(SCEV::NoWrapMask))
     948             :     return true;
     949             : 
     950             :   // Scalar evolution does not propagate the non-wrapping flags to values that
     951             :   // are derived from a non-wrapping induction variable because non-wrapping
     952             :   // could be flow-sensitive.
     953             :   //
     954             :   // Look through the potentially overflowing instruction to try to prove
     955             :   // non-wrapping for the *specific* value of Ptr.
     956             : 
     957             :   // The arithmetic implied by an inbounds GEP can't overflow.
     958             :   auto *GEP = dyn_cast<GetElementPtrInst>(Ptr);
     959         255 :   if (!GEP || !GEP->isInBounds())
     960          37 :     return false;
     961             : 
     962             :   // Make sure there is only one non-const index and analyze that.
     963             :   Value *NonConstIndex = nullptr;
     964         617 :   for (Value *Index : make_range(GEP->idx_begin(), GEP->idx_end()))
     965         380 :     if (!isa<ConstantInt>(Index)) {
     966         237 :       if (NonConstIndex)
     967             :         return false;
     968             :       NonConstIndex = Index;
     969             :     }
     970         237 :   if (!NonConstIndex)
     971             :     // The recurrence is on the pointer, ignore for now.
     972             :     return false;
     973             : 
     974             :   // The index in GEP is signed.  It is non-wrapping if it's derived from a NSW
     975             :   // AddRec using a NSW operation.
     976             :   if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(NonConstIndex))
     977         220 :     if (OBO->hasNoSignedWrap() &&
     978             :         // Assume constant for other the operand so that the AddRec can be
     979             :         // easily found.
     980          66 :         isa<ConstantInt>(OBO->getOperand(1))) {
     981          33 :       auto *OpScev = PSE.getSCEV(OBO->getOperand(0));
     982             : 
     983             :       if (auto *OpAR = dyn_cast<SCEVAddRecExpr>(OpScev))
     984          33 :         return OpAR->getLoop() == L && OpAR->getNoWrapFlags(SCEV::FlagNSW);
     985             :     }
     986             : 
     987             :   return false;
     988             : }
     989             : 
     990             : /// Check whether the access through \p Ptr has a constant stride.
     991       19572 : int64_t llvm::getPtrStride(PredicatedScalarEvolution &PSE, Value *Ptr,
     992             :                            const Loop *Lp, const ValueToValueMap &StridesMap,
     993             :                            bool Assume, bool ShouldCheckWrap) {
     994       19572 :   Type *Ty = Ptr->getType();
     995             :   assert(Ty->isPointerTy() && "Unexpected non-ptr");
     996             : 
     997             :   // Make sure that the pointer does not point to aggregate types.
     998             :   auto *PtrTy = cast<PointerType>(Ty);
     999       19572 :   if (PtrTy->getElementType()->isAggregateType()) {
    1000             :     LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not a pointer to a scalar type"
    1001             :                       << *Ptr << "\n");
    1002             :     return 0;
    1003             :   }
    1004             : 
    1005       19572 :   const SCEV *PtrScev = replaceSymbolicStrideSCEV(PSE, StridesMap, Ptr);
    1006             : 
    1007             :   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
    1008       19572 :   if (Assume && !AR)
    1009        6609 :     AR = PSE.getAsAddRec(Ptr);
    1010             : 
    1011       19572 :   if (!AR) {
    1012             :     LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer " << *Ptr
    1013             :                       << " SCEV: " << *PtrScev << "\n");
    1014             :     return 0;
    1015             :   }
    1016             : 
    1017             :   // The accesss function must stride over the innermost loop.
    1018       11164 :   if (Lp != AR->getLoop()) {
    1019             :     LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not striding over innermost loop "
    1020             :                       << *Ptr << " SCEV: " << *AR << "\n");
    1021             :     return 0;
    1022             :   }
    1023             : 
    1024             :   // The address calculation must not wrap. Otherwise, a dependence could be
    1025             :   // inverted.
    1026             :   // An inbounds getelementptr that is a AddRec with a unit stride
    1027             :   // cannot wrap per definition. The unit stride requirement is checked later.
    1028             :   // An getelementptr without an inbounds attribute and unit stride would have
    1029             :   // to access the pointer value "0" which is undefined behavior in address
    1030             :   // space 0, therefore we can also vectorize this case.
    1031             :   bool IsInBoundsGEP = isInBoundsGep(Ptr);
    1032        1534 :   bool IsNoWrapAddRec = !ShouldCheckWrap ||
    1033       12452 :     PSE.hasNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW) ||
    1034        1349 :     isNoWrapAddRec(Ptr, AR, PSE, Lp);
    1035       11140 :   if (!IsNoWrapAddRec && !IsInBoundsGEP &&
    1036          37 :       NullPointerIsDefined(Lp->getHeader()->getParent(),
    1037             :                            PtrTy->getAddressSpace())) {
    1038           3 :     if (Assume) {
    1039           2 :       PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
    1040             :       IsNoWrapAddRec = true;
    1041             :       LLVM_DEBUG(dbgs() << "LAA: Pointer may wrap in the address space:\n"
    1042             :                         << "LAA:   Pointer: " << *Ptr << "\n"
    1043             :                         << "LAA:   SCEV: " << *AR << "\n"
    1044             :                         << "LAA:   Added an overflow assumption\n");
    1045             :     } else {
    1046             :       LLVM_DEBUG(
    1047             :           dbgs() << "LAA: Bad stride - Pointer may wrap in the address space "
    1048             :                  << *Ptr << " SCEV: " << *AR << "\n");
    1049             :       return 0;
    1050             :     }
    1051             :   }
    1052             : 
    1053             :   // Check the step is constant.
    1054       11102 :   const SCEV *Step = AR->getStepRecurrence(*PSE.getSE());
    1055             : 
    1056             :   // Calculate the pointer stride and check if it is constant.
    1057             :   const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
    1058             :   if (!C) {
    1059             :     LLVM_DEBUG(dbgs() << "LAA: Bad stride - Not a constant strided " << *Ptr
    1060             :                       << " SCEV: " << *AR << "\n");
    1061             :     return 0;
    1062             :   }
    1063             : 
    1064       11081 :   auto &DL = Lp->getHeader()->getModule()->getDataLayout();
    1065       11081 :   int64_t Size = DL.getTypeAllocSize(PtrTy->getElementType());
    1066             :   const APInt &APStepVal = C->getAPInt();
    1067             : 
    1068             :   // Huge step value - give up.
    1069       11081 :   if (APStepVal.getBitWidth() > 64)
    1070             :     return 0;
    1071             : 
    1072             :   int64_t StepVal = APStepVal.getSExtValue();
    1073             : 
    1074             :   // Strided access.
    1075       11081 :   int64_t Stride = StepVal / Size;
    1076       11081 :   int64_t Rem = StepVal % Size;
    1077       11081 :   if (Rem)
    1078             :     return 0;
    1079             : 
    1080             :   // If the SCEV could wrap but we have an inbounds gep with a unit stride we
    1081             :   // know we can't "wrap around the address space". In case of address space
    1082             :   // zero we know that this won't happen without triggering undefined behavior.
    1083       11081 :   if (!IsNoWrapAddRec && Stride != 1 && Stride != -1 &&
    1084          28 :       (IsInBoundsGEP || !NullPointerIsDefined(Lp->getHeader()->getParent(),
    1085             :                                               PtrTy->getAddressSpace()))) {
    1086          63 :     if (Assume) {
    1087             :       // We can avoid this case by adding a run-time check.
    1088             :       LLVM_DEBUG(dbgs() << "LAA: Non unit strided pointer which is not either "
    1089             :                         << "inbouds or in address space 0 may wrap:\n"
    1090             :                         << "LAA:   Pointer: " << *Ptr << "\n"
    1091             :                         << "LAA:   SCEV: " << *AR << "\n"
    1092             :                         << "LAA:   Added an overflow assumption\n");
    1093          54 :       PSE.setNoOverflow(Ptr, SCEVWrapPredicate::IncrementNUSW);
    1094             :     } else
    1095             :       return 0;
    1096             :   }
    1097             : 
    1098             :   return Stride;
    1099             : }
    1100             : 
    1101      103785 : bool llvm::sortPtrAccesses(ArrayRef<Value *> VL, const DataLayout &DL,
    1102             :                            ScalarEvolution &SE,
    1103             :                            SmallVectorImpl<unsigned> &SortedIndices) {
    1104             :   assert(llvm::all_of(
    1105             :              VL, [](const Value *V) { return V->getType()->isPointerTy(); }) &&
    1106             :          "Expected list of pointer operands.");
    1107             :   SmallVector<std::pair<int64_t, Value *>, 4> OffValPairs;
    1108             :   OffValPairs.reserve(VL.size());
    1109             : 
    1110             :   // Walk over the pointers, and map each of them to an offset relative to
    1111             :   // first pointer in the array.
    1112      103785 :   Value *Ptr0 = VL[0];
    1113      103785 :   const SCEV *Scev0 = SE.getSCEV(Ptr0);
    1114      103785 :   Value *Obj0 = GetUnderlyingObject(Ptr0, DL);
    1115             : 
    1116      103785 :   llvm::SmallSet<int64_t, 4> Offsets;
    1117      327625 :   for (auto *Ptr : VL) {
    1118             :     // TODO: Outline this code as a special, more time consuming, version of
    1119             :     // computeConstantDifference() function.
    1120      451832 :     if (Ptr->getType()->getPointerAddressSpace() !=
    1121      225916 :         Ptr0->getType()->getPointerAddressSpace())
    1122        2076 :       return false;
    1123             :     // If a pointer refers to a different underlying object, bail - the
    1124             :     // pointers are by definition incomparable.
    1125      225916 :     Value *CurrObj = GetUnderlyingObject(Ptr, DL);
    1126      225916 :     if (CurrObj != Obj0)
    1127             :       return false;
    1128             : 
    1129      223977 :     const SCEV *Scev = SE.getSCEV(Ptr);
    1130      223977 :     const auto *Diff = dyn_cast<SCEVConstant>(SE.getMinusSCEV(Scev, Scev0));
    1131             :     // The pointers may not have a constant offset from each other, or SCEV
    1132             :     // may just not be smart enough to figure out they do. Regardless,
    1133             :     // there's nothing we can do.
    1134             :     if (!Diff)
    1135             :       return false;
    1136             : 
    1137             :     // Check if the pointer with the same offset is found.
    1138      223842 :     int64_t Offset = Diff->getAPInt().getSExtValue();
    1139      223842 :     if (!Offsets.insert(Offset).second)
    1140             :       return false;
    1141      223840 :     OffValPairs.emplace_back(Offset, Ptr);
    1142             :   }
    1143             :   SortedIndices.clear();
    1144      101709 :   SortedIndices.resize(VL.size());
    1145             :   std::iota(SortedIndices.begin(), SortedIndices.end(), 0);
    1146             : 
    1147             :   // Sort the memory accesses and keep the order of their uses in UseOrder.
    1148             :   std::stable_sort(SortedIndices.begin(), SortedIndices.end(),
    1149             :                    [&OffValPairs](unsigned Left, unsigned Right) {
    1150      447070 :                      return OffValPairs[Left].first < OffValPairs[Right].first;
    1151             :                    });
    1152             : 
    1153             :   // Check if the order is consecutive already.
    1154      101709 :   if (llvm::all_of(SortedIndices, [&SortedIndices](const unsigned I) {
    1155           0 :         return I == SortedIndices[I];
    1156             :       }))
    1157             :     SortedIndices.clear();
    1158             : 
    1159             :   return true;
    1160             : }
    1161             : 
    1162             : /// Take the address space operand from the Load/Store instruction.
    1163             : /// Returns -1 if this is not a valid Load/Store instruction.
    1164      896512 : static unsigned getAddressSpaceOperand(Value *I) {
    1165             :   if (LoadInst *L = dyn_cast<LoadInst>(I))
    1166       12426 :     return L->getPointerAddressSpace();
    1167             :   if (StoreInst *S = dyn_cast<StoreInst>(I))
    1168      884086 :     return S->getPointerAddressSpace();
    1169             :   return -1;
    1170             : }
    1171             : 
    1172             : /// Returns true if the memory operations \p A and \p B are consecutive.
    1173      448256 : bool llvm::isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL,
    1174             :                                ScalarEvolution &SE, bool CheckType) {
    1175             :   Value *PtrA = getLoadStorePointerOperand(A);
    1176             :   Value *PtrB = getLoadStorePointerOperand(B);
    1177      448256 :   unsigned ASA = getAddressSpaceOperand(A);
    1178      448256 :   unsigned ASB = getAddressSpaceOperand(B);
    1179             : 
    1180             :   // Check that the address spaces match and that the pointers are valid.
    1181      448256 :   if (!PtrA || !PtrB || (ASA != ASB))
    1182             :     return false;
    1183             : 
    1184             :   // Make sure that A and B are different pointers.
    1185      448246 :   if (PtrA == PtrB)
    1186             :     return false;
    1187             : 
    1188             :   // Make sure that A and B have the same type if required.
    1189      442766 :   if (CheckType && PtrA->getType() != PtrB->getType())
    1190             :     return false;
    1191             : 
    1192             :   unsigned IdxWidth = DL.getIndexSizeInBits(ASA);
    1193      419955 :   Type *Ty = cast<PointerType>(PtrA->getType())->getElementType();
    1194             :   APInt Size(IdxWidth, DL.getTypeStoreSize(Ty));
    1195             : 
    1196             :   APInt OffsetA(IdxWidth, 0), OffsetB(IdxWidth, 0);
    1197             :   PtrA = PtrA->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetA);
    1198             :   PtrB = PtrB->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetB);
    1199             : 
    1200             :   //  OffsetDelta = OffsetB - OffsetA;
    1201      419955 :   const SCEV *OffsetSCEVA = SE.getConstant(OffsetA);
    1202      419955 :   const SCEV *OffsetSCEVB = SE.getConstant(OffsetB);
    1203      419955 :   const SCEV *OffsetDeltaSCEV = SE.getMinusSCEV(OffsetSCEVB, OffsetSCEVA);
    1204             :   const SCEVConstant *OffsetDeltaC = dyn_cast<SCEVConstant>(OffsetDeltaSCEV);
    1205             :   const APInt &OffsetDelta = OffsetDeltaC->getAPInt();
    1206             :   // Check if they are based on the same pointer. That makes the offsets
    1207             :   // sufficient.
    1208      419955 :   if (PtrA == PtrB)
    1209             :     return OffsetDelta == Size;
    1210             : 
    1211             :   // Compute the necessary base pointer delta to have the necessary final delta
    1212             :   // equal to the size.
    1213             :   // BaseDelta = Size - OffsetDelta;
    1214        9336 :   const SCEV *SizeSCEV = SE.getConstant(Size);
    1215        9336 :   const SCEV *BaseDelta = SE.getMinusSCEV(SizeSCEV, OffsetDeltaSCEV);
    1216             : 
    1217             :   // Otherwise compute the distance with SCEV between the base pointers.
    1218        9336 :   const SCEV *PtrSCEVA = SE.getSCEV(PtrA);
    1219        9336 :   const SCEV *PtrSCEVB = SE.getSCEV(PtrB);
    1220        9336 :   const SCEV *X = SE.getAddExpr(PtrSCEVA, BaseDelta);
    1221        9336 :   return X == PtrSCEVB;
    1222             : }
    1223             : 
    1224        5077 : bool MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) {
    1225             :   switch (Type) {
    1226             :   case NoDep:
    1227             :   case Forward:
    1228             :   case BackwardVectorizable:
    1229             :     return true;
    1230             : 
    1231             :   case Unknown:
    1232             :   case ForwardButPreventsForwarding:
    1233             :   case Backward:
    1234             :   case BackwardVectorizableButPreventsForwarding:
    1235             :     return false;
    1236             :   }
    1237           0 :   llvm_unreachable("unexpected DepType!");
    1238             : }
    1239             : 
    1240         123 : bool MemoryDepChecker::Dependence::isBackward() const {
    1241         123 :   switch (Type) {
    1242             :   case NoDep:
    1243             :   case Forward:
    1244             :   case ForwardButPreventsForwarding:
    1245             :   case Unknown:
    1246             :     return false;
    1247             : 
    1248          51 :   case BackwardVectorizable:
    1249             :   case Backward:
    1250             :   case BackwardVectorizableButPreventsForwarding:
    1251          51 :     return true;
    1252             :   }
    1253           0 :   llvm_unreachable("unexpected DepType!");
    1254             : }
    1255             : 
    1256          23 : bool MemoryDepChecker::Dependence::isPossiblyBackward() const {
    1257          23 :   return isBackward() || Type == Unknown;
    1258             : }
    1259             : 
    1260           0 : bool MemoryDepChecker::Dependence::isForward() const {
    1261           0 :   switch (Type) {
    1262             :   case Forward:
    1263             :   case ForwardButPreventsForwarding:
    1264             :     return true;
    1265             : 
    1266             :   case NoDep:
    1267             :   case Unknown:
    1268             :   case BackwardVectorizable:
    1269             :   case Backward:
    1270             :   case BackwardVectorizableButPreventsForwarding:
    1271             :     return false;
    1272             :   }
    1273           0 :   llvm_unreachable("unexpected DepType!");
    1274             : }
    1275             : 
    1276          47 : bool MemoryDepChecker::couldPreventStoreLoadForward(uint64_t Distance,
    1277             :                                                     uint64_t TypeByteSize) {
    1278             :   // If loads occur at a distance that is not a multiple of a feasible vector
    1279             :   // factor store-load forwarding does not take place.
    1280             :   // Positive dependences might cause troubles because vectorizing them might
    1281             :   // prevent store-load forwarding making vectorized code run a lot slower.
    1282             :   //   a[i] = a[i-3] ^ a[i-8];
    1283             :   //   The stores to a[i:i+1] don't align with the stores to a[i-3:i-2] and
    1284             :   //   hence on your typical architecture store-load forwarding does not take
    1285             :   //   place. Vectorizing in such cases does not make sense.
    1286             :   // Store-load forwarding distance.
    1287             : 
    1288             :   // After this many iterations store-to-load forwarding conflicts should not
    1289             :   // cause any slowdowns.
    1290          47 :   const uint64_t NumItersForStoreLoadThroughMemory = 8 * TypeByteSize;
    1291             :   // Maximum vector factor.
    1292             :   uint64_t MaxVFWithoutSLForwardIssues = std::min(
    1293          47 :       VectorizerParams::MaxVectorWidth * TypeByteSize, MaxSafeDepDistBytes);
    1294             : 
    1295             :   // Compute the smallest VF at which the store and load would be misaligned.
    1296          96 :   for (uint64_t VF = 2 * TypeByteSize; VF <= MaxVFWithoutSLForwardIssues;
    1297          49 :        VF *= 2) {
    1298             :     // If the number of vector iteration between the store and the load are
    1299             :     // small we could incur conflicts.
    1300          89 :     if (Distance % VF && Distance / VF < NumItersForStoreLoadThroughMemory) {
    1301          40 :       MaxVFWithoutSLForwardIssues = (VF >>= 1);
    1302          40 :       break;
    1303             :     }
    1304             :   }
    1305             : 
    1306          47 :   if (MaxVFWithoutSLForwardIssues < 2 * TypeByteSize) {
    1307             :     LLVM_DEBUG(
    1308             :         dbgs() << "LAA: Distance " << Distance
    1309             :                << " that could cause a store-load forwarding conflict\n");
    1310             :     return true;
    1311             :   }
    1312             : 
    1313          25 :   if (MaxVFWithoutSLForwardIssues < MaxSafeDepDistBytes &&
    1314             :       MaxVFWithoutSLForwardIssues !=
    1315             :           VectorizerParams::MaxVectorWidth * TypeByteSize)
    1316          18 :     MaxSafeDepDistBytes = MaxVFWithoutSLForwardIssues;
    1317             :   return false;
    1318             : }
    1319             : 
    1320             : /// Given a non-constant (unknown) dependence-distance \p Dist between two
    1321             : /// memory accesses, that have the same stride whose absolute value is given
    1322             : /// in \p Stride, and that have the same type size \p TypeByteSize,
    1323             : /// in a loop whose takenCount is \p BackedgeTakenCount, check if it is
    1324             : /// possible to prove statically that the dependence distance is larger
    1325             : /// than the range that the accesses will travel through the execution of
    1326             : /// the loop. If so, return true; false otherwise. This is useful for
    1327             : /// example in loops such as the following (PR31098):
    1328             : ///     for (i = 0; i < D; ++i) {
    1329             : ///                = out[i];
    1330             : ///       out[i+D] =
    1331             : ///     }
    1332          50 : static bool isSafeDependenceDistance(const DataLayout &DL, ScalarEvolution &SE,
    1333             :                                      const SCEV &BackedgeTakenCount,
    1334             :                                      const SCEV &Dist, uint64_t Stride,
    1335             :                                      uint64_t TypeByteSize) {
    1336             : 
    1337             :   // If we can prove that
    1338             :   //      (**) |Dist| > BackedgeTakenCount * Step
    1339             :   // where Step is the absolute stride of the memory accesses in bytes,
    1340             :   // then there is no dependence.
    1341             :   //
    1342             :   // Ratioanle:
    1343             :   // We basically want to check if the absolute distance (|Dist/Step|)
    1344             :   // is >= the loop iteration count (or > BackedgeTakenCount).
    1345             :   // This is equivalent to the Strong SIV Test (Practical Dependence Testing,
    1346             :   // Section 4.2.1); Note, that for vectorization it is sufficient to prove
    1347             :   // that the dependence distance is >= VF; This is checked elsewhere.
    1348             :   // But in some cases we can prune unknown dependence distances early, and
    1349             :   // even before selecting the VF, and without a runtime test, by comparing
    1350             :   // the distance against the loop iteration count. Since the vectorized code
    1351             :   // will be executed only if LoopCount >= VF, proving distance >= LoopCount
    1352             :   // also guarantees that distance >= VF.
    1353             :   //
    1354          50 :   const uint64_t ByteStride = Stride * TypeByteSize;
    1355          50 :   const SCEV *Step = SE.getConstant(BackedgeTakenCount.getType(), ByteStride);
    1356          50 :   const SCEV *Product = SE.getMulExpr(&BackedgeTakenCount, Step);
    1357             : 
    1358             :   const SCEV *CastedDist = &Dist;
    1359             :   const SCEV *CastedProduct = Product;
    1360          50 :   uint64_t DistTypeSize = DL.getTypeAllocSize(Dist.getType());
    1361          50 :   uint64_t ProductTypeSize = DL.getTypeAllocSize(Product->getType());
    1362             : 
    1363             :   // The dependence distance can be positive/negative, so we sign extend Dist;
    1364             :   // The multiplication of the absolute stride in bytes and the
    1365             :   // backdgeTakenCount is non-negative, so we zero extend Product.
    1366          50 :   if (DistTypeSize > ProductTypeSize)
    1367           0 :     CastedProduct = SE.getZeroExtendExpr(Product, Dist.getType());
    1368             :   else
    1369          50 :     CastedDist = SE.getNoopOrSignExtend(&Dist, Product->getType());
    1370             : 
    1371             :   // Is  Dist - (BackedgeTakenCount * Step) > 0 ?
    1372             :   // (If so, then we have proven (**) because |Dist| >= Dist)
    1373          50 :   const SCEV *Minus = SE.getMinusSCEV(CastedDist, CastedProduct);
    1374          50 :   if (SE.isKnownPositive(Minus))
    1375             :     return true;
    1376             : 
    1377             :   // Second try: Is  -Dist - (BackedgeTakenCount * Step) > 0 ?
    1378             :   // (If so, then we have proven (**) because |Dist| >= -1*Dist)
    1379          34 :   const SCEV *NegDist = SE.getNegativeSCEV(CastedDist);
    1380          34 :   Minus = SE.getMinusSCEV(NegDist, CastedProduct);
    1381          34 :   if (SE.isKnownPositive(Minus))
    1382           8 :     return true;
    1383             : 
    1384             :   return false;
    1385             : }
    1386             : 
    1387             : /// Check the dependence for two accesses with the same stride \p Stride.
    1388             : /// \p Distance is the positive distance and \p TypeByteSize is type size in
    1389             : /// bytes.
    1390             : ///
    1391             : /// \returns true if they are independent.
    1392             : static bool areStridedAccessesIndependent(uint64_t Distance, uint64_t Stride,
    1393             :                                           uint64_t TypeByteSize) {
    1394             :   assert(Stride > 1 && "The stride must be greater than 1");
    1395             :   assert(TypeByteSize > 0 && "The type size in byte must be non-zero");
    1396             :   assert(Distance > 0 && "The distance must be non-zero");
    1397             : 
    1398             :   // Skip if the distance is not multiple of type byte size.
    1399         167 :   if (Distance % TypeByteSize)
    1400             :     return false;
    1401             : 
    1402         155 :   uint64_t ScaledDist = Distance / TypeByteSize;
    1403             : 
    1404             :   // No dependence if the scaled distance is not multiple of the stride.
    1405             :   // E.g.
    1406             :   //      for (i = 0; i < 1024 ; i += 4)
    1407             :   //        A[i+2] = A[i] + 1;
    1408             :   //
    1409             :   // Two accesses in memory (scaled distance is 2, stride is 4):
    1410             :   //     | A[0] |      |      |      | A[4] |      |      |      |
    1411             :   //     |      |      | A[2] |      |      |      | A[6] |      |
    1412             :   //
    1413             :   // E.g.
    1414             :   //      for (i = 0; i < 1024 ; i += 3)
    1415             :   //        A[i+4] = A[i] + 1;
    1416             :   //
    1417             :   // Two accesses in memory (scaled distance is 4, stride is 3):
    1418             :   //     | A[0] |      |      | A[3] |      |      | A[6] |      |      |
    1419             :   //     |      |      |      |      | A[4] |      |      | A[7] |      |
    1420         155 :   return ScaledDist % Stride;
    1421             : }
    1422             : 
    1423             : MemoryDepChecker::Dependence::DepType
    1424        5077 : MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
    1425             :                               const MemAccessInfo &B, unsigned BIdx,
    1426             :                               const ValueToValueMap &Strides) {
    1427             :   assert (AIdx < BIdx && "Must pass arguments in program order");
    1428             : 
    1429        5077 :   Value *APtr = A.getPointer();
    1430        5077 :   Value *BPtr = B.getPointer();
    1431             :   bool AIsWrite = A.getInt();
    1432             :   bool BIsWrite = B.getInt();
    1433             : 
    1434             :   // Two reads are independent.
    1435        5077 :   if (!AIsWrite && !BIsWrite)
    1436             :     return Dependence::NoDep;
    1437             : 
    1438             :   // We cannot check pointers in different address spaces.
    1439        7616 :   if (APtr->getType()->getPointerAddressSpace() !=
    1440        3808 :       BPtr->getType()->getPointerAddressSpace())
    1441             :     return Dependence::Unknown;
    1442             : 
    1443        3808 :   int64_t StrideAPtr = getPtrStride(PSE, APtr, InnermostLoop, Strides, true);
    1444        3808 :   int64_t StrideBPtr = getPtrStride(PSE, BPtr, InnermostLoop, Strides, true);
    1445             : 
    1446        3808 :   const SCEV *Src = PSE.getSCEV(APtr);
    1447        3808 :   const SCEV *Sink = PSE.getSCEV(BPtr);
    1448             : 
    1449             :   // If the induction step is negative we have to invert source and sink of the
    1450             :   // dependence.
    1451        3808 :   if (StrideAPtr < 0) {
    1452             :     std::swap(APtr, BPtr);
    1453             :     std::swap(Src, Sink);
    1454             :     std::swap(AIsWrite, BIsWrite);
    1455             :     std::swap(AIdx, BIdx);
    1456             :     std::swap(StrideAPtr, StrideBPtr);
    1457             :   }
    1458             : 
    1459        3808 :   const SCEV *Dist = PSE.getSE()->getMinusSCEV(Sink, Src);
    1460             : 
    1461             :   LLVM_DEBUG(dbgs() << "LAA: Src Scev: " << *Src << "Sink Scev: " << *Sink
    1462             :                     << "(Induction step: " << StrideAPtr << ")\n");
    1463             :   LLVM_DEBUG(dbgs() << "LAA: Distance for " << *InstMap[AIdx] << " to "
    1464             :                     << *InstMap[BIdx] << ": " << *Dist << "\n");
    1465             : 
    1466             :   // Need accesses with constant stride. We don't want to vectorize
    1467             :   // "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in
    1468             :   // the address space.
    1469        3808 :   if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){
    1470             :     LLVM_DEBUG(dbgs() << "Pointer access with non-constant stride\n");
    1471             :     return Dependence::Unknown;
    1472             :   }
    1473             : 
    1474         542 :   Type *ATy = APtr->getType()->getPointerElementType();
    1475         542 :   Type *BTy = BPtr->getType()->getPointerElementType();
    1476         542 :   auto &DL = InnermostLoop->getHeader()->getModule()->getDataLayout();
    1477         542 :   uint64_t TypeByteSize = DL.getTypeAllocSize(ATy);
    1478         542 :   uint64_t Stride = std::abs(StrideAPtr);
    1479             :   const SCEVConstant *C = dyn_cast<SCEVConstant>(Dist);
    1480             :   if (!C) {
    1481         100 :     if (TypeByteSize == DL.getTypeAllocSize(BTy) &&
    1482          50 :         isSafeDependenceDistance(DL, *(PSE.getSE()),
    1483          50 :                                  *(PSE.getBackedgeTakenCount()), *Dist, Stride,
    1484             :                                  TypeByteSize))
    1485             :       return Dependence::NoDep;
    1486             : 
    1487             :     LLVM_DEBUG(dbgs() << "LAA: Dependence because of non-constant distance\n");
    1488          26 :     ShouldRetryWithRuntimeCheck = true;
    1489          26 :     return Dependence::Unknown;
    1490             :   }
    1491             : 
    1492             :   const APInt &Val = C->getAPInt();
    1493             :   int64_t Distance = Val.getSExtValue();
    1494             : 
    1495             :   // Attempt to prove strided accesses independent.
    1496         647 :   if (std::abs(Distance) > 0 && Stride > 1 && ATy == BTy &&
    1497         167 :       areStridedAccessesIndependent(std::abs(Distance), Stride, TypeByteSize)) {
    1498             :     LLVM_DEBUG(dbgs() << "LAA: Strided accesses are independent\n");
    1499             :     return Dependence::NoDep;
    1500             :   }
    1501             : 
    1502             :   // Negative distances are not plausible dependencies.
    1503         359 :   if (Val.isNegative()) {
    1504          94 :     bool IsTrueDataDependence = (AIsWrite && !BIsWrite);
    1505          46 :     if (IsTrueDataDependence && EnableForwardingConflictDetection &&
    1506         146 :         (couldPreventStoreLoadForward(Val.abs().getZExtValue(), TypeByteSize) ||
    1507             :          ATy != BTy)) {
    1508             :       LLVM_DEBUG(dbgs() << "LAA: Forward but may prevent st->ld forwarding\n");
    1509             :       return Dependence::ForwardButPreventsForwarding;
    1510             :     }
    1511             : 
    1512             :     LLVM_DEBUG(dbgs() << "LAA: Dependence is negative\n");
    1513          77 :     return Dependence::Forward;
    1514             :   }
    1515             : 
    1516             :   // Write to the same location with the same size.
    1517             :   // Could be improved to assert type sizes are the same (i32 == float, etc).
    1518         265 :   if (Val == 0) {
    1519         113 :     if (ATy == BTy)
    1520             :       return Dependence::Forward;
    1521             :     LLVM_DEBUG(
    1522             :         dbgs() << "LAA: Zero dependence difference but different types\n");
    1523           0 :     return Dependence::Unknown;
    1524             :   }
    1525             : 
    1526             :   assert(Val.isStrictlyPositive() && "Expect a positive value");
    1527             : 
    1528         152 :   if (ATy != BTy) {
    1529             :     LLVM_DEBUG(
    1530             :         dbgs()
    1531             :         << "LAA: ReadWrite-Write positive dependency with different types\n");
    1532             :     return Dependence::Unknown;
    1533             :   }
    1534             : 
    1535             :   // Bail out early if passed-in parameters make vectorization not feasible.
    1536         150 :   unsigned ForcedFactor = (VectorizerParams::VectorizationFactor ?
    1537         150 :                            VectorizerParams::VectorizationFactor : 1);
    1538         150 :   unsigned ForcedUnroll = (VectorizerParams::VectorizationInterleave ?
    1539         150 :                            VectorizerParams::VectorizationInterleave : 1);
    1540             :   // The minimum number of iterations for a vectorized/unrolled version.
    1541         150 :   unsigned MinNumIter = std::max(ForcedFactor * ForcedUnroll, 2U);
    1542             : 
    1543             :   // It's not vectorizable if the distance is smaller than the minimum distance
    1544             :   // needed for a vectroized/unrolled version. Vectorizing one iteration in
    1545             :   // front needs TypeByteSize * Stride. Vectorizing the last iteration needs
    1546             :   // TypeByteSize (No need to plus the last gap distance).
    1547             :   //
    1548             :   // E.g. Assume one char is 1 byte in memory and one int is 4 bytes.
    1549             :   //      foo(int *A) {
    1550             :   //        int *B = (int *)((char *)A + 14);
    1551             :   //        for (i = 0 ; i < 1024 ; i += 2)
    1552             :   //          B[i] = A[i] + 1;
    1553             :   //      }
    1554             :   //
    1555             :   // Two accesses in memory (stride is 2):
    1556             :   //     | A[0] |      | A[2] |      | A[4] |      | A[6] |      |
    1557             :   //                              | B[0] |      | B[2] |      | B[4] |
    1558             :   //
    1559             :   // Distance needs for vectorizing iterations except the last iteration:
    1560             :   // 4 * 2 * (MinNumIter - 1). Distance needs for the last iteration: 4.
    1561             :   // So the minimum distance needed is: 4 * 2 * (MinNumIter - 1) + 4.
    1562             :   //
    1563             :   // If MinNumIter is 2, it is vectorizable as the minimum distance needed is
    1564             :   // 12, which is less than distance.
    1565             :   //
    1566             :   // If MinNumIter is 4 (Say if a user forces the vectorization factor to be 4),
    1567             :   // the minimum distance needed is 28, which is greater than distance. It is
    1568             :   // not safe to do vectorization.
    1569         150 :   uint64_t MinDistanceNeeded =
    1570         150 :       TypeByteSize * Stride * (MinNumIter - 1) + TypeByteSize;
    1571         150 :   if (MinDistanceNeeded > static_cast<uint64_t>(Distance)) {
    1572             :     LLVM_DEBUG(dbgs() << "LAA: Failure because of positive distance "
    1573             :                       << Distance << '\n');
    1574             :     return Dependence::Backward;
    1575             :   }
    1576             : 
    1577             :   // Unsafe if the minimum distance needed is greater than max safe distance.
    1578          47 :   if (MinDistanceNeeded > MaxSafeDepDistBytes) {
    1579             :     LLVM_DEBUG(dbgs() << "LAA: Failure because it needs at least "
    1580             :                       << MinDistanceNeeded << " size in bytes");
    1581             :     return Dependence::Backward;
    1582             :   }
    1583             : 
    1584             :   // Positive distance bigger than max vectorization factor.
    1585             :   // FIXME: Should use max factor instead of max distance in bytes, which could
    1586             :   // not handle different types.
    1587             :   // E.g. Assume one char is 1 byte in memory and one int is 4 bytes.
    1588             :   //      void foo (int *A, char *B) {
    1589             :   //        for (unsigned i = 0; i < 1024; i++) {
    1590             :   //          A[i+2] = A[i] + 1;
    1591             :   //          B[i+2] = B[i] + 1;
    1592             :   //        }
    1593             :   //      }
    1594             :   //
    1595             :   // This case is currently unsafe according to the max safe distance. If we
    1596             :   // analyze the two accesses on array B, the max safe dependence distance
    1597             :   // is 2. Then we analyze the accesses on array A, the minimum distance needed
    1598             :   // is 8, which is less than 2 and forbidden vectorization, But actually
    1599             :   // both A and B could be vectorized by 2 iterations.
    1600          47 :   MaxSafeDepDistBytes =
    1601          47 :       std::min(static_cast<uint64_t>(Distance), MaxSafeDepDistBytes);
    1602             : 
    1603          47 :   bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
    1604          50 :   if (IsTrueDataDependence && EnableForwardingConflictDetection &&
    1605          24 :       couldPreventStoreLoadForward(Distance, TypeByteSize))
    1606             :     return Dependence::BackwardVectorizableButPreventsForwarding;
    1607             : 
    1608          42 :   uint64_t MaxVF = MaxSafeDepDistBytes / (TypeByteSize * Stride);
    1609             :   LLVM_DEBUG(dbgs() << "LAA: Positive distance " << Val.getSExtValue()
    1610             :                     << " with max VF = " << MaxVF << '\n');
    1611          42 :   uint64_t MaxVFInBits = MaxVF * TypeByteSize * 8;
    1612          42 :   MaxSafeRegisterWidth = std::min(MaxSafeRegisterWidth, MaxVFInBits);
    1613          42 :   return Dependence::BackwardVectorizable;
    1614             : }
    1615             : 
    1616         872 : bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
    1617             :                                    MemAccessInfoList &CheckDeps,
    1618             :                                    const ValueToValueMap &Strides) {
    1619             : 
    1620         872 :   MaxSafeDepDistBytes = -1;
    1621             :   SmallPtrSet<MemAccessInfo, 8> Visited;
    1622        3606 :   for (MemAccessInfo CurAccess : CheckDeps) {
    1623        2746 :     if (Visited.count(CurAccess))
    1624             :       continue;
    1625             : 
    1626             :     // Get the relevant memory access set.
    1627             :     EquivalenceClasses<MemAccessInfo>::iterator I =
    1628        1672 :       AccessSets.findValue(AccessSets.getLeaderValue(CurAccess));
    1629             : 
    1630             :     // Check accesses within this set.
    1631             :     EquivalenceClasses<MemAccessInfo>::member_iterator AI =
    1632             :         AccessSets.member_begin(I);
    1633             :     EquivalenceClasses<MemAccessInfo>::member_iterator AE =
    1634             :         AccessSets.member_end();
    1635             : 
    1636             :     // Check every access pair.
    1637        5002 :     while (AI != AE) {
    1638        3342 :       Visited.insert(*AI);
    1639             :       EquivalenceClasses<MemAccessInfo>::member_iterator OI = std::next(AI);
    1640        6971 :       while (OI != AE) {
    1641             :         // Check every accessing instruction pair in program order.
    1642        3641 :         for (std::vector<unsigned>::iterator I1 = Accesses[*AI].begin(),
    1643        7620 :              I1E = Accesses[*AI].end(); I1 != I1E; ++I1)
    1644             :           for (std::vector<unsigned>::iterator I2 = Accesses[*OI].begin(),
    1645        9056 :                I2E = Accesses[*OI].end(); I2 != I2E; ++I2) {
    1646        5077 :             auto A = std::make_pair(&*AI, *I1);
    1647        5077 :             auto B = std::make_pair(&*OI, *I2);
    1648             : 
    1649             :             assert(*I1 != *I2);
    1650        5077 :             if (*I1 > *I2)
    1651             :               std::swap(A, B);
    1652             : 
    1653             :             Dependence::DepType Type =
    1654        5077 :                 isDependent(*A.first, A.second, *B.first, B.second, Strides);
    1655        5077 :             SafeForVectorization &= Dependence::isSafeForVectorization(Type);
    1656             : 
    1657             :             // Gather dependences unless we accumulated MaxDependences
    1658             :             // dependences.  In that case return as soon as we find the first
    1659             :             // unsafe dependence.  This puts a limit on this quadratic
    1660             :             // algorithm.
    1661        5077 :             if (RecordDependences) {
    1662        5077 :               if (Type != Dependence::NoDep)
    1663        7302 :                 Dependences.push_back(Dependence(A.second, B.second, Type));
    1664             : 
    1665       10154 :               if (Dependences.size() >= MaxDependences) {
    1666          12 :                 RecordDependences = false;
    1667             :                 Dependences.clear();
    1668             :                 LLVM_DEBUG(dbgs()
    1669             :                            << "Too many dependences, stopped recording\n");
    1670             :               }
    1671             :             }
    1672        5077 :             if (!RecordDependences && !SafeForVectorization)
    1673             :               return false;
    1674             :           }
    1675             :         ++OI;
    1676             :       }
    1677             :       AI++;
    1678             :     }
    1679             :   }
    1680             : 
    1681             :   LLVM_DEBUG(dbgs() << "Total Dependences: " << Dependences.size() << "\n");
    1682         860 :   return SafeForVectorization;
    1683             : }
    1684             : 
    1685             : SmallVector<Instruction *, 4>
    1686         112 : MemoryDepChecker::getInstructionsForAccess(Value *Ptr, bool isWrite) const {
    1687             :   MemAccessInfo Access(Ptr, isWrite);
    1688         112 :   auto &IndexVector = Accesses.find(Access)->second;
    1689             : 
    1690             :   SmallVector<Instruction *, 4> Insts;
    1691             :   transform(IndexVector,
    1692             :                  std::back_inserter(Insts),
    1693         224 :                  [&](unsigned Idx) { return this->InstMap[Idx]; });
    1694         112 :   return Insts;
    1695             : }
    1696             : 
    1697             : const char *MemoryDepChecker::Dependence::DepName[] = {
    1698             :     "NoDep", "Unknown", "Forward", "ForwardButPreventsForwarding", "Backward",
    1699             :     "BackwardVectorizable", "BackwardVectorizableButPreventsForwarding"};
    1700             : 
    1701          78 : void MemoryDepChecker::Dependence::print(
    1702             :     raw_ostream &OS, unsigned Depth,
    1703             :     const SmallVectorImpl<Instruction *> &Instrs) const {
    1704          78 :   OS.indent(Depth) << DepName[Type] << ":\n";
    1705          78 :   OS.indent(Depth + 2) << *Instrs[Source] << " -> \n";
    1706          78 :   OS.indent(Depth + 2) << *Instrs[Destination] << "\n";
    1707          78 : }
    1708             : 
    1709        5128 : bool LoopAccessInfo::canAnalyzeLoop() {
    1710             :   // We need to have a loop header.
    1711             :   LLVM_DEBUG(dbgs() << "LAA: Found a loop in "
    1712             :                     << TheLoop->getHeader()->getParent()->getName() << ": "
    1713             :                     << TheLoop->getHeader()->getName() << '\n');
    1714             : 
    1715             :   // We can only analyze innermost loops.
    1716       10256 :   if (!TheLoop->empty()) {
    1717             :     LLVM_DEBUG(dbgs() << "LAA: loop is not the innermost loop\n");
    1718          11 :     recordAnalysis("NotInnerMostLoop") << "loop is not the innermost loop";
    1719          11 :     return false;
    1720             :   }
    1721             : 
    1722             :   // We must have a single backedge.
    1723        5117 :   if (TheLoop->getNumBackEdges() != 1) {
    1724             :     LLVM_DEBUG(
    1725             :         dbgs() << "LAA: loop control flow is not understood by analyzer\n");
    1726             :     recordAnalysis("CFGNotUnderstood")
    1727           0 :         << "loop control flow is not understood by analyzer";
    1728           0 :     return false;
    1729             :   }
    1730             : 
    1731             :   // We must have a single exiting block.
    1732        5117 :   if (!TheLoop->getExitingBlock()) {
    1733             :     LLVM_DEBUG(
    1734             :         dbgs() << "LAA: loop control flow is not understood by analyzer\n");
    1735             :     recordAnalysis("CFGNotUnderstood")
    1736        1592 :         << "loop control flow is not understood by analyzer";
    1737        1592 :     return false;
    1738             :   }
    1739             : 
    1740             :   // We only handle bottom-tested loops, i.e. loop in which the condition is
    1741             :   // checked at the end of each iteration. With that we can assume that all
    1742             :   // instructions in the loop are executed the same number of times.
    1743        3525 :   if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) {
    1744             :     LLVM_DEBUG(
    1745             :         dbgs() << "LAA: loop control flow is not understood by analyzer\n");
    1746             :     recordAnalysis("CFGNotUnderstood")
    1747         127 :         << "loop control flow is not understood by analyzer";
    1748         127 :     return false;
    1749             :   }
    1750             : 
    1751             :   // ScalarEvolution needs to be able to find the exit count.
    1752        3398 :   const SCEV *ExitCount = PSE->getBackedgeTakenCount();
    1753        3398 :   if (ExitCount == PSE->getSE()->getCouldNotCompute()) {
    1754             :     recordAnalysis("CantComputeNumberOfIterations")
    1755        1108 :         << "could not determine number of loop iterations";
    1756             :     LLVM_DEBUG(dbgs() << "LAA: SCEV could not compute the loop exit count.\n");
    1757        1108 :     return false;
    1758             :   }
    1759             : 
    1760             :   return true;
    1761             : }
    1762             : 
    1763        2290 : void LoopAccessInfo::analyzeLoop(AliasAnalysis *AA, LoopInfo *LI,
    1764             :                                  const TargetLibraryInfo *TLI,
    1765             :                                  DominatorTree *DT) {
    1766             :   typedef SmallPtrSet<Value*, 16> ValueSet;
    1767             : 
    1768             :   // Holds the Load and Store instructions.
    1769             :   SmallVector<LoadInst *, 16> Loads;
    1770             :   SmallVector<StoreInst *, 16> Stores;
    1771             : 
    1772             :   // Holds all the different accesses in the loop.
    1773             :   unsigned NumReads = 0;
    1774             :   unsigned NumReadWrites = 0;
    1775             : 
    1776             :   PtrRtChecking->Pointers.clear();
    1777        2290 :   PtrRtChecking->Need = false;
    1778             : 
    1779        2290 :   const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel();
    1780             : 
    1781             :   // For each block.
    1782        5221 :   for (BasicBlock *BB : TheLoop->blocks()) {
    1783             :     // Scan the BB and collect legal loads and stores.
    1784       40425 :     for (Instruction &I : *BB) {
    1785             :       // If this is a load, save it. If this instruction can read from memory
    1786             :       // but is not a load, then we quit. Notice that we don't handle function
    1787             :       // calls that read or write.
    1788       37494 :       if (I.mayReadFromMemory()) {
    1789             :         // Many math library functions read the rounding mode. We will only
    1790             :         // vectorize a loop if it contains known function calls that don't set
    1791             :         // the flag. Therefore, it is safe to ignore this read from memory.
    1792             :         auto *Call = dyn_cast<CallInst>(&I);
    1793         385 :         if (Call && getVectorIntrinsicIDForCall(Call, TLI))
    1794        5240 :           continue;
    1795             : 
    1796             :         // If the function has an explicit vectorized counterpart, we can safely
    1797             :         // assume that it can be vectorized.
    1798        5569 :         if (Call && !Call->isNoBuiltin() && Call->getCalledFunction() &&
    1799         308 :             TLI->isFunctionVectorizable(Call->getCalledFunction()->getName()))
    1800             :           continue;
    1801             : 
    1802        5563 :         auto *Ld = dyn_cast<LoadInst>(&I);
    1803        5567 :         if (!Ld || (!Ld->isSimple() && !IsAnnotatedParallel)) {
    1804             :           recordAnalysis("NonSimpleLoad", Ld)
    1805         714 :               << "read with atomic ordering or volatile read";
    1806             :           LLVM_DEBUG(dbgs() << "LAA: Found a non-simple load.\n");
    1807         357 :           CanVecMem = false;
    1808         357 :           return;
    1809             :         }
    1810        5206 :         NumLoads++;
    1811        5206 :         Loads.push_back(Ld);
    1812        5206 :         DepChecker->addAccess(Ld);
    1813        5206 :         if (EnableMemAccessVersioning)
    1814        5198 :           collectStridedAccess(Ld);
    1815        5206 :         continue;
    1816             :       }
    1817             : 
    1818             :       // Save 'store' instructions. Abort if other instructions write to memory.
    1819       31897 :       if (I.mayWriteToMemory()) {
    1820        4260 :         auto *St = dyn_cast<StoreInst>(&I);
    1821        4260 :         if (!St) {
    1822             :           recordAnalysis("CantVectorizeInstruction", St)
    1823           0 :               << "instruction cannot be vectorized";
    1824           0 :           CanVecMem = false;
    1825           0 :           return;
    1826             :         }
    1827           0 :         if (!St->isSimple() && !IsAnnotatedParallel) {
    1828             :           recordAnalysis("NonSimpleStore", St)
    1829           0 :               << "write with atomic ordering or volatile write";
    1830             :           LLVM_DEBUG(dbgs() << "LAA: Found a non-simple store.\n");
    1831           0 :           CanVecMem = false;
    1832           0 :           return;
    1833             :         }
    1834        4260 :         NumStores++;
    1835        4260 :         Stores.push_back(St);
    1836        4260 :         DepChecker->addAccess(St);
    1837        4260 :         if (EnableMemAccessVersioning)
    1838        4256 :           collectStridedAccess(St);
    1839             :       }
    1840             :     } // Next instr.
    1841             :   } // Next block.
    1842             : 
    1843             :   // Now we have two lists that hold the loads and the stores.
    1844             :   // Next, we find the pointers that they use.
    1845             : 
    1846             :   // Check if we see any stores. If there are no stores, then we don't
    1847             :   // care if the pointers are *restrict*.
    1848        1933 :   if (!Stores.size()) {
    1849             :     LLVM_DEBUG(dbgs() << "LAA: Found a read-only loop!\n");
    1850         345 :     CanVecMem = true;
    1851         345 :     return;
    1852             :   }
    1853             : 
    1854             :   MemoryDepChecker::DepCandidates DependentAccesses;
    1855             :   AccessAnalysis Accesses(TheLoop->getHeader()->getModule()->getDataLayout(),
    1856        2778 :                           TheLoop, AA, LI, DependentAccesses, *PSE);
    1857             : 
    1858             :   // Holds the analyzed pointers. We don't want to call GetUnderlyingObjects
    1859             :   // multiple times on the same object. If the ptr is accessed twice, once
    1860             :   // for read and once for write, it will only appear once (on the write
    1861             :   // list). This is okay, since we are going to check for conflicts between
    1862             :   // writes and between reads and writes, but not between reads and reads.
    1863             :   ValueSet Seen;
    1864             : 
    1865             :   // Record uniform store addresses to identify if we have multiple stores
    1866             :   // to the same address.
    1867             :   ValueSet UniformStores;
    1868             : 
    1869        5501 :   for (StoreInst *ST : Stores) {
    1870             :     Value *Ptr = ST->getPointerOperand();
    1871             : 
    1872        3913 :     if (isUniform(Ptr))
    1873        1962 :       HasMultipleStoresToLoopInvariantAddress |=
    1874        1962 :           !UniformStores.insert(Ptr).second;
    1875             : 
    1876             :     // If we did *not* see this pointer before, insert it to  the read-write
    1877             :     // list. At this phase it is only a 'write' list.
    1878        3913 :     if (Seen.insert(Ptr).second) {
    1879        3676 :       ++NumReadWrites;
    1880             : 
    1881        3676 :       MemoryLocation Loc = MemoryLocation::get(ST);
    1882             :       // The TBAA metadata could have a control dependency on the predication
    1883             :       // condition, so we cannot rely on it when determining whether or not we
    1884             :       // need runtime pointer checks.
    1885        3676 :       if (blockNeedsPredication(ST->getParent(), TheLoop, DT))
    1886         475 :         Loc.AATags.TBAA = nullptr;
    1887             : 
    1888        3676 :       Accesses.addStore(Loc);
    1889             :     }
    1890             :   }
    1891             : 
    1892        1588 :   if (IsAnnotatedParallel) {
    1893             :     LLVM_DEBUG(
    1894             :         dbgs() << "LAA: A loop annotated parallel, ignore memory dependency "
    1895             :                << "checks.\n");
    1896           9 :     CanVecMem = true;
    1897           9 :     return;
    1898             :   }
    1899             : 
    1900        5482 :   for (LoadInst *LD : Loads) {
    1901             :     Value *Ptr = LD->getPointerOperand();
    1902             :     // If we did *not* see this pointer before, insert it to the
    1903             :     // read list. If we *did* see it before, then it is already in
    1904             :     // the read-write list. This allows us to vectorize expressions
    1905             :     // such as A[i] += x;  Because the address of A[i] is a read-write
    1906             :     // pointer. This only works if the index of A[i] is consecutive.
    1907             :     // If the address of i is unknown (for example A[B[i]]) then we may
    1908             :     // read a few words, modify, and write a few words, and some of the
    1909             :     // words may be written to the same address.
    1910             :     bool IsReadOnlyPtr = false;
    1911        6008 :     if (Seen.insert(Ptr).second ||
    1912        4210 :         !getPtrStride(*PSE, Ptr, TheLoop, SymbolicStrides)) {
    1913        3659 :       ++NumReads;
    1914             :       IsReadOnlyPtr = true;
    1915             :     }
    1916             : 
    1917        3903 :     MemoryLocation Loc = MemoryLocation::get(LD);
    1918             :     // The TBAA metadata could have a control dependency on the predication
    1919             :     // condition, so we cannot rely on it when determining whether or not we
    1920             :     // need runtime pointer checks.
    1921        3903 :     if (blockNeedsPredication(LD->getParent(), TheLoop, DT))
    1922         477 :       Loc.AATags.TBAA = nullptr;
    1923             : 
    1924        3903 :     Accesses.addLoad(Loc, IsReadOnlyPtr);
    1925             :   }
    1926             : 
    1927             :   // If we write (or read-write) to a single destination and there are no
    1928             :   // other reads in this loop then is it safe to vectorize.
    1929        1579 :   if (NumReadWrites == 1 && NumReads == 0) {
    1930             :     LLVM_DEBUG(dbgs() << "LAA: Found a write-only loop!\n");
    1931         252 :     CanVecMem = true;
    1932         252 :     return;
    1933             :   }
    1934             : 
    1935             :   // Build dependence sets and check whether we need a runtime pointer bounds
    1936             :   // check.
    1937             :   Accesses.buildDependenceSets();
    1938             : 
    1939             :   // Find pointers with computable bounds. We are going to use this information
    1940             :   // to place a runtime bound check.
    1941        2654 :   bool CanDoRTIfNeeded = Accesses.canCheckPtrAtRT(*PtrRtChecking, PSE->getSE(),
    1942        1327 :                                                   TheLoop, SymbolicStrides);
    1943        1327 :   if (!CanDoRTIfNeeded) {
    1944         137 :     recordAnalysis("CantIdentifyArrayBounds") << "cannot identify array bounds";
    1945             :     LLVM_DEBUG(dbgs() << "LAA: We can't vectorize because we can't find "
    1946             :                       << "the array bounds.\n");
    1947         137 :     CanVecMem = false;
    1948         137 :     return;
    1949             :   }
    1950             : 
    1951             :   LLVM_DEBUG(
    1952             :       dbgs() << "LAA: We can perform a memory runtime check if needed.\n");
    1953             : 
    1954        1190 :   CanVecMem = true;
    1955        1190 :   if (Accesses.isDependencyCheckNeeded()) {
    1956             :     LLVM_DEBUG(dbgs() << "LAA: Checking memory dependencies\n");
    1957         872 :     CanVecMem = DepChecker->areDepsSafe(
    1958             :         DependentAccesses, Accesses.getDependenciesToCheck(), SymbolicStrides);
    1959         872 :     MaxSafeDepDistBytes = DepChecker->getMaxSafeDepDistBytes();
    1960             : 
    1961         872 :     if (!CanVecMem && DepChecker->shouldRetryWithRuntimeCheck()) {
    1962             :       LLVM_DEBUG(dbgs() << "LAA: Retrying with memory checks\n");
    1963             : 
    1964             :       // Clear the dependency checks. We assume they are not needed.
    1965             :       Accesses.resetDepChecks(*DepChecker);
    1966             : 
    1967             :       PtrRtChecking->reset();
    1968          20 :       PtrRtChecking->Need = true;
    1969             : 
    1970          20 :       auto *SE = PSE->getSE();
    1971          40 :       CanDoRTIfNeeded = Accesses.canCheckPtrAtRT(*PtrRtChecking, SE, TheLoop,
    1972             :                                                  SymbolicStrides, true);
    1973             : 
    1974             :       // Check that we found the bounds for the pointer.
    1975          20 :       if (!CanDoRTIfNeeded) {
    1976             :         recordAnalysis("CantCheckMemDepsAtRunTime")
    1977           0 :             << "cannot check memory dependencies at runtime";
    1978             :         LLVM_DEBUG(dbgs() << "LAA: Can't vectorize with memory checks\n");
    1979           0 :         CanVecMem = false;
    1980           0 :         return;
    1981             :       }
    1982             : 
    1983          20 :       CanVecMem = true;
    1984             :     }
    1985             :   }
    1986             : 
    1987        1190 :   if (CanVecMem)
    1988             :     LLVM_DEBUG(
    1989             :         dbgs() << "LAA: No unsafe dependent memory operations in loop.  We"
    1990             :                << (PtrRtChecking->Need ? "" : " don't")
    1991             :                << " need runtime memory checks.\n");
    1992             :   else {
    1993             :     recordAnalysis("UnsafeMemDep")
    1994             :         << "unsafe dependent memory operations in loop. Use "
    1995             :            "#pragma loop distribute(enable) to allow loop distribution "
    1996             :            "to attempt to isolate the offending operations into a separate "
    1997         688 :            "loop";
    1998             :     LLVM_DEBUG(dbgs() << "LAA: unsafe dependent memory operations in loop\n");
    1999             :   }
    2000             : }
    2001             : 
    2002       35834 : bool LoopAccessInfo::blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
    2003             :                                            DominatorTree *DT)  {
    2004             :   assert(TheLoop->contains(BB) && "Unknown block used");
    2005             : 
    2006             :   // Blocks that do not dominate the latch need predication.
    2007       35834 :   BasicBlock* Latch = TheLoop->getLoopLatch();
    2008       35834 :   return !DT->dominates(BB, Latch);
    2009             : }
    2010             : 
    2011        3676 : OptimizationRemarkAnalysis &LoopAccessInfo::recordAnalysis(StringRef RemarkName,
    2012             :                                                            Instruction *I) {
    2013             :   assert(!Report && "Multiple reports generated");
    2014             : 
    2015        3676 :   Value *CodeRegion = TheLoop->getHeader();
    2016        3676 :   DebugLoc DL = TheLoop->getStartLoc();
    2017             : 
    2018        3676 :   if (I) {
    2019           4 :     CodeRegion = I->getParent();
    2020             :     // If there is no debug location attached to the instruction, revert back to
    2021             :     // using the loop's.
    2022           4 :     if (I->getDebugLoc())
    2023             :       DL = I->getDebugLoc();
    2024             :   }
    2025             : 
    2026        7352 :   Report = make_unique<OptimizationRemarkAnalysis>(DEBUG_TYPE, RemarkName, DL,
    2027             :                                                    CodeRegion);
    2028        3676 :   return *Report;
    2029             : }
    2030             : 
    2031        8233 : bool LoopAccessInfo::isUniform(Value *V) const {
    2032        8233 :   auto *SE = PSE->getSE();
    2033             :   // Since we rely on SCEV for uniformity, if the type is not SCEVable, it is
    2034             :   // never considered uniform.
    2035             :   // TODO: Is this really what we want? Even without FP SCEV, we may want some
    2036             :   // trivially loop-invariant FP values to be considered uniform.
    2037        8233 :   if (!SE->isSCEVable(V->getType()))
    2038             :     return false;
    2039        7706 :   return (SE->isLoopInvariant(SE->getSCEV(V), TheLoop));
    2040             : }
    2041             : 
    2042             : // FIXME: this function is currently a duplicate of the one in
    2043             : // LoopVectorize.cpp.
    2044             : static Instruction *getFirstInst(Instruction *FirstInst, Value *V,
    2045             :                                  Instruction *Loc) {
    2046        1436 :   if (FirstInst)
    2047             :     return FirstInst;
    2048             :   if (Instruction *I = dyn_cast<Instruction>(V))
    2049         227 :     return I->getParent() == Loc->getParent() ? I : nullptr;
    2050             :   return nullptr;
    2051             : }
    2052             : 
    2053             : namespace {
    2054             : 
    2055             : /// IR Values for the lower and upper bounds of a pointer evolution.  We
    2056             : /// need to use value-handles because SCEV expansion can invalidate previously
    2057             : /// expanded values.  Thus expansion of a pointer can invalidate the bounds for
    2058             : /// a previous one.
    2059             : struct PointerBounds {
    2060             :   TrackingVH<Value> Start;
    2061             :   TrackingVH<Value> End;
    2062             : };
    2063             : 
    2064             : } // end anonymous namespace
    2065             : 
    2066             : /// Expand code for the lower and upper bound of the pointer group \p CG
    2067             : /// in \p TheLoop.  \return the values for the bounds.
    2068             : static PointerBounds
    2069         718 : expandBounds(const RuntimePointerChecking::CheckingPtrGroup *CG, Loop *TheLoop,
    2070             :              Instruction *Loc, SCEVExpander &Exp, ScalarEvolution *SE,
    2071             :              const RuntimePointerChecking &PtrRtChecking) {
    2072         718 :   Value *Ptr = PtrRtChecking.Pointers[CG->Members[0]].PointerValue;
    2073         718 :   const SCEV *Sc = SE->getSCEV(Ptr);
    2074             : 
    2075         718 :   unsigned AS = Ptr->getType()->getPointerAddressSpace();
    2076         718 :   LLVMContext &Ctx = Loc->getContext();
    2077             : 
    2078             :   // Use this type for pointer arithmetic.
    2079         718 :   Type *PtrArithTy = Type::getInt8PtrTy(Ctx, AS);
    2080             : 
    2081         718 :   if (SE->isLoopInvariant(Sc, TheLoop)) {
    2082             :     LLVM_DEBUG(dbgs() << "LAA: Adding RT check for a loop invariant ptr:"
    2083             :                       << *Ptr << "\n");
    2084             :     // Ptr could be in the loop body. If so, expand a new one at the correct
    2085             :     // location.
    2086             :     Instruction *Inst = dyn_cast<Instruction>(Ptr);
    2087           8 :     Value *NewPtr = (Inst && TheLoop->contains(Inst))
    2088           4 :                         ? Exp.expandCodeFor(Sc, PtrArithTy, Loc)
    2089             :                         : Ptr;
    2090             :     // We must return a half-open range, which means incrementing Sc.
    2091          29 :     const SCEV *ScPlusOne = SE->getAddExpr(Sc, SE->getOne(PtrArithTy));
    2092          29 :     Value *NewPtrPlusOne = Exp.expandCodeFor(ScPlusOne, PtrArithTy, Loc);
    2093             :     return {NewPtr, NewPtrPlusOne};
    2094             :   } else {
    2095             :     Value *Start = nullptr, *End = nullptr;
    2096             :     LLVM_DEBUG(dbgs() << "LAA: Adding RT check for range:\n");
    2097         689 :     Start = Exp.expandCodeFor(CG->Low, PtrArithTy, Loc);
    2098         689 :     End = Exp.expandCodeFor(CG->High, PtrArithTy, Loc);
    2099             :     LLVM_DEBUG(dbgs() << "Start: " << *CG->Low << " End: " << *CG->High
    2100             :                       << "\n");
    2101             :     return {Start, End};
    2102             :   }
    2103             : }
    2104             : 
    2105             : /// Turns a collection of checks into a collection of expanded upper and
    2106             : /// lower bounds for both pointers in the check.
    2107         238 : static SmallVector<std::pair<PointerBounds, PointerBounds>, 4> expandBounds(
    2108             :     const SmallVectorImpl<RuntimePointerChecking::PointerCheck> &PointerChecks,
    2109             :     Loop *L, Instruction *Loc, ScalarEvolution *SE, SCEVExpander &Exp,
    2110             :     const RuntimePointerChecking &PtrRtChecking) {
    2111             :   SmallVector<std::pair<PointerBounds, PointerBounds>, 4> ChecksWithBounds;
    2112             : 
    2113             :   // Here we're relying on the SCEV Expander's cache to only emit code for the
    2114             :   // same bounds once.
    2115             :   transform(
    2116             :       PointerChecks, std::back_inserter(ChecksWithBounds),
    2117             :       [&](const RuntimePointerChecking::PointerCheck &Check) {
    2118             :         PointerBounds
    2119             :           First = expandBounds(Check.first, L, Loc, Exp, SE, PtrRtChecking),
    2120             :           Second = expandBounds(Check.second, L, Loc, Exp, SE, PtrRtChecking);
    2121             :         return std::make_pair(First, Second);
    2122         238 :       });
    2123             : 
    2124         238 :   return ChecksWithBounds;
    2125             : }
    2126             : 
    2127         238 : std::pair<Instruction *, Instruction *> LoopAccessInfo::addRuntimeChecks(
    2128             :     Instruction *Loc,
    2129             :     const SmallVectorImpl<RuntimePointerChecking::PointerCheck> &PointerChecks)
    2130             :     const {
    2131         238 :   const DataLayout &DL = TheLoop->getHeader()->getModule()->getDataLayout();
    2132         238 :   auto *SE = PSE->getSE();
    2133         476 :   SCEVExpander Exp(*SE, DL, "induction");
    2134             :   auto ExpandedChecks =
    2135         476 :       expandBounds(PointerChecks, TheLoop, Loc, SE, Exp, *PtrRtChecking);
    2136             : 
    2137         238 :   LLVMContext &Ctx = Loc->getContext();
    2138             :   Instruction *FirstInst = nullptr;
    2139         238 :   IRBuilder<> ChkBuilder(Loc);
    2140             :   // Our instructions might fold to a constant.
    2141             :   Value *MemoryRuntimeCheck = nullptr;
    2142             : 
    2143         597 :   for (const auto &Check : ExpandedChecks) {
    2144             :     const PointerBounds &A = Check.first, &B = Check.second;
    2145             :     // Check if two pointers (A and B) conflict where conflict is computed as:
    2146             :     // start(A) <= end(B) && start(B) <= end(A)
    2147         359 :     unsigned AS0 = A.Start->getType()->getPointerAddressSpace();
    2148         359 :     unsigned AS1 = B.Start->getType()->getPointerAddressSpace();
    2149             : 
    2150             :     assert((AS0 == B.End->getType()->getPointerAddressSpace()) &&
    2151             :            (AS1 == A.End->getType()->getPointerAddressSpace()) &&
    2152             :            "Trying to bounds check pointers with different address spaces");
    2153             : 
    2154         359 :     Type *PtrArithTy0 = Type::getInt8PtrTy(Ctx, AS0);
    2155         359 :     Type *PtrArithTy1 = Type::getInt8PtrTy(Ctx, AS1);
    2156             : 
    2157         359 :     Value *Start0 = ChkBuilder.CreateBitCast(A.Start, PtrArithTy0, "bc");
    2158         359 :     Value *Start1 = ChkBuilder.CreateBitCast(B.Start, PtrArithTy1, "bc");
    2159         359 :     Value *End0 =   ChkBuilder.CreateBitCast(A.End,   PtrArithTy1, "bc");
    2160         359 :     Value *End1 =   ChkBuilder.CreateBitCast(B.End,   PtrArithTy0, "bc");
    2161             : 
    2162             :     // [A|B].Start points to the first accessed byte under base [A|B].
    2163             :     // [A|B].End points to the last accessed byte, plus one.
    2164             :     // There is no conflict when the intervals are disjoint:
    2165             :     // NoConflict = (B.Start >= A.End) || (A.Start >= B.End)
    2166             :     //
    2167             :     // bound0 = (B.Start < A.End)
    2168             :     // bound1 = (A.Start < B.End)
    2169             :     //  IsConflict = bound0 & bound1
    2170         359 :     Value *Cmp0 = ChkBuilder.CreateICmpULT(Start0, End1, "bound0");
    2171             :     FirstInst = getFirstInst(FirstInst, Cmp0, Loc);
    2172         359 :     Value *Cmp1 = ChkBuilder.CreateICmpULT(Start1, End0, "bound1");
    2173             :     FirstInst = getFirstInst(FirstInst, Cmp1, Loc);
    2174         359 :     Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict");
    2175             :     FirstInst = getFirstInst(FirstInst, IsConflict, Loc);
    2176         359 :     if (MemoryRuntimeCheck) {
    2177             :       IsConflict =
    2178         132 :           ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict, "conflict.rdx");
    2179             :       FirstInst = getFirstInst(FirstInst, IsConflict, Loc);
    2180             :     }
    2181             :     MemoryRuntimeCheck = IsConflict;
    2182             :   }
    2183             : 
    2184         238 :   if (!MemoryRuntimeCheck)
    2185          11 :     return std::make_pair(nullptr, nullptr);
    2186             : 
    2187             :   // We have to do this trickery because the IRBuilder might fold the check to a
    2188             :   // constant expression in which case there is no Instruction anchored in a
    2189             :   // the block.
    2190         227 :   Instruction *Check = BinaryOperator::CreateAnd(MemoryRuntimeCheck,
    2191         227 :                                                  ConstantInt::getTrue(Ctx));
    2192         227 :   ChkBuilder.Insert(Check, "memcheck.conflict");
    2193             :   FirstInst = getFirstInst(FirstInst, Check, Loc);
    2194             :   return std::make_pair(FirstInst, Check);
    2195             : }
    2196             : 
    2197             : std::pair<Instruction *, Instruction *>
    2198         906 : LoopAccessInfo::addRuntimeChecks(Instruction *Loc) const {
    2199         906 :   if (!PtrRtChecking->Need)
    2200         708 :     return std::make_pair(nullptr, nullptr);
    2201             : 
    2202         198 :   return addRuntimeChecks(Loc, PtrRtChecking->getChecks());
    2203             : }
    2204             : 
    2205        9454 : void LoopAccessInfo::collectStridedAccess(Value *MemAccess) {
    2206             :   Value *Ptr = nullptr;
    2207             :   if (LoadInst *LI = dyn_cast<LoadInst>(MemAccess))
    2208             :     Ptr = LI->getPointerOperand();
    2209             :   else if (StoreInst *SI = dyn_cast<StoreInst>(MemAccess))
    2210             :     Ptr = SI->getPointerOperand();
    2211             :   else
    2212             :     return;
    2213             : 
    2214       18908 :   Value *Stride = getStrideFromPointer(Ptr, PSE->getSE(), TheLoop);
    2215        9454 :   if (!Stride)
    2216             :     return;
    2217             : 
    2218             :   LLVM_DEBUG(dbgs() << "LAA: Found a strided access that is a candidate for "
    2219             :                        "versioning:");
    2220             :   LLVM_DEBUG(dbgs() << "  Ptr: " << *Ptr << " Stride: " << *Stride << "\n");
    2221             : 
    2222             :   // Avoid adding the "Stride == 1" predicate when we know that
    2223             :   // Stride >= Trip-Count. Such a predicate will effectively optimize a single
    2224             :   // or zero iteration loop, as Trip-Count <= Stride == 1.
    2225             :   //
    2226             :   // TODO: We are currently not making a very informed decision on when it is
    2227             :   // beneficial to apply stride versioning. It might make more sense that the
    2228             :   // users of this analysis (such as the vectorizer) will trigger it, based on
    2229             :   // their specific cost considerations; For example, in cases where stride
    2230             :   // versioning does  not help resolving memory accesses/dependences, the
    2231             :   // vectorizer should evaluate the cost of the runtime test, and the benefit
    2232             :   // of various possible stride specializations, considering the alternatives
    2233             :   // of using gather/scatters (if available).
    2234             : 
    2235          15 :   const SCEV *StrideExpr = PSE->getSCEV(Stride);
    2236          15 :   const SCEV *BETakenCount = PSE->getBackedgeTakenCount();
    2237             : 
    2238             :   // Match the types so we can compare the stride and the BETakenCount.
    2239             :   // The Stride can be positive/negative, so we sign extend Stride;
    2240             :   // The backdgeTakenCount is non-negative, so we zero extend BETakenCount.
    2241          15 :   const DataLayout &DL = TheLoop->getHeader()->getModule()->getDataLayout();
    2242          15 :   uint64_t StrideTypeSize = DL.getTypeAllocSize(StrideExpr->getType());
    2243          15 :   uint64_t BETypeSize = DL.getTypeAllocSize(BETakenCount->getType());
    2244             :   const SCEV *CastedStride = StrideExpr;
    2245             :   const SCEV *CastedBECount = BETakenCount;
    2246          15 :   ScalarEvolution *SE = PSE->getSE();
    2247          15 :   if (BETypeSize >= StrideTypeSize)
    2248          13 :     CastedStride = SE->getNoopOrSignExtend(StrideExpr, BETakenCount->getType());
    2249             :   else
    2250           2 :     CastedBECount = SE->getZeroExtendExpr(BETakenCount, StrideExpr->getType());
    2251          15 :   const SCEV *StrideMinusBETaken = SE->getMinusSCEV(CastedStride, CastedBECount);
    2252             :   // Since TripCount == BackEdgeTakenCount + 1, checking:
    2253             :   // "Stride >= TripCount" is equivalent to checking:
    2254             :   // Stride - BETakenCount > 0
    2255          15 :   if (SE->isKnownPositive(StrideMinusBETaken)) {
    2256             :     LLVM_DEBUG(
    2257             :         dbgs() << "LAA: Stride>=TripCount; No point in versioning as the "
    2258             :                   "Stride==1 predicate will imply that the loop executes "
    2259             :                   "at most once.\n");
    2260             :     return;
    2261             :   }
    2262             :   LLVM_DEBUG(dbgs() << "LAA: Found a strided access that we can version.");
    2263             : 
    2264          13 :   SymbolicStrides[Ptr] = Stride;
    2265          13 :   StrideSet.insert(Stride);
    2266             : }
    2267             : 
    2268        5128 : LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
    2269             :                                const TargetLibraryInfo *TLI, AliasAnalysis *AA,
    2270        5128 :                                DominatorTree *DT, LoopInfo *LI)
    2271             :     : PSE(llvm::make_unique<PredicatedScalarEvolution>(*SE, *L)),
    2272             :       PtrRtChecking(llvm::make_unique<RuntimePointerChecking>(SE)),
    2273             :       DepChecker(llvm::make_unique<MemoryDepChecker>(*PSE, L)), TheLoop(L),
    2274             :       NumLoads(0), NumStores(0), MaxSafeDepDistBytes(-1), CanVecMem(false),
    2275        5128 :       HasMultipleStoresToLoopInvariantAddress(false) {
    2276        5128 :   if (canAnalyzeLoop())
    2277        2290 :     analyzeLoop(AA, LI, TLI, DT);
    2278        5128 : }
    2279             : 
    2280         105 : void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
    2281         105 :   if (CanVecMem) {
    2282          66 :     OS.indent(Depth) << "Memory dependences are safe";
    2283          66 :     if (MaxSafeDepDistBytes != -1ULL)
    2284          12 :       OS << " with a maximum dependence distance of " << MaxSafeDepDistBytes
    2285          12 :          << " bytes";
    2286          66 :     if (PtrRtChecking->Need)
    2287          26 :       OS << " with run-time checks";
    2288          66 :     OS << "\n";
    2289             :   }
    2290             : 
    2291         105 :   if (Report)
    2292         117 :     OS.indent(Depth) << "Report: " << Report->getMsg() << "\n";
    2293             : 
    2294             :   if (auto *Dependences = DepChecker->getDependences()) {
    2295         105 :     OS.indent(Depth) << "Dependences:\n";
    2296         183 :     for (auto &Dep : *Dependences) {
    2297          78 :       Dep.print(OS, Depth + 2, DepChecker->getMemoryInstructions());
    2298          78 :       OS << "\n";
    2299             :     }
    2300             :   } else
    2301           0 :     OS.indent(Depth) << "Too many dependences, not recorded\n";
    2302             : 
    2303             :   // List the pair of accesses need run-time checks to prove independence.
    2304         105 :   PtrRtChecking->print(OS, Depth);
    2305         105 :   OS << "\n";
    2306             : 
    2307         105 :   OS.indent(Depth) << "Multiple stores to invariant address were "
    2308         208 :                    << (HasMultipleStoresToLoopInvariantAddress ? "" : "not ")
    2309         105 :                    << "found in loop.\n";
    2310             : 
    2311         105 :   OS.indent(Depth) << "SCEV assumptions:\n";
    2312         105 :   PSE->getUnionPredicate().print(OS, Depth);
    2313             : 
    2314         105 :   OS << "\n";
    2315             : 
    2316         105 :   OS.indent(Depth) << "Expressions re-written:\n";
    2317         105 :   PSE->print(OS, Depth);
    2318         105 : }
    2319             : 
    2320        4547 : const LoopAccessInfo &LoopAccessLegacyAnalysis::getInfo(Loop *L) {
    2321        4547 :   auto &LAI = LoopAccessInfoMap[L];
    2322             : 
    2323        4547 :   if (!LAI)
    2324        9094 :     LAI = llvm::make_unique<LoopAccessInfo>(L, SE, TLI, AA, DT, LI);
    2325             : 
    2326        4547 :   return *LAI.get();
    2327             : }
    2328             : 
    2329          48 : void LoopAccessLegacyAnalysis::print(raw_ostream &OS, const Module *M) const {
    2330             :   LoopAccessLegacyAnalysis &LAA = *const_cast<LoopAccessLegacyAnalysis *>(this);
    2331             : 
    2332          97 :   for (Loop *TopLevelLoop : *LI)
    2333         152 :     for (Loop *L : depth_first(TopLevelLoop)) {
    2334          54 :       OS.indent(2) << L->getHeader()->getName() << ":\n";
    2335          54 :       auto &LAI = LAA.getInfo(L);
    2336          54 :       LAI.print(OS, 4);
    2337             :     }
    2338          48 : }
    2339             : 
    2340       41254 : bool LoopAccessLegacyAnalysis::runOnFunction(Function &F) {
    2341       41254 :   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
    2342       41254 :   auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
    2343       41254 :   TLI = TLIP ? &TLIP->getTLI() : nullptr;
    2344       41254 :   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
    2345       41254 :   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
    2346       41254 :   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
    2347             : 
    2348       41254 :   return false;
    2349             : }
    2350             : 
    2351        4548 : void LoopAccessLegacyAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
    2352             :     AU.addRequired<ScalarEvolutionWrapperPass>();
    2353             :     AU.addRequired<AAResultsWrapperPass>();
    2354             :     AU.addRequired<DominatorTreeWrapperPass>();
    2355             :     AU.addRequired<LoopInfoWrapperPass>();
    2356             : 
    2357             :     AU.setPreservesAll();
    2358        4548 : }
    2359             : 
    2360             : char LoopAccessLegacyAnalysis::ID = 0;
    2361             : static const char laa_name[] = "Loop Access Analysis";
    2362             : #define LAA_NAME "loop-accesses"
    2363             : 
    2364       33326 : INITIALIZE_PASS_BEGIN(LoopAccessLegacyAnalysis, LAA_NAME, laa_name, false, true)
    2365       33326 : INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
    2366       33326 : INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
    2367       33326 : INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
    2368       33326 : INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
    2369      233370 : INITIALIZE_PASS_END(LoopAccessLegacyAnalysis, LAA_NAME, laa_name, false, true)
    2370             : 
    2371             : AnalysisKey LoopAccessAnalysis::Key;
    2372             : 
    2373         108 : LoopAccessInfo LoopAccessAnalysis::run(Loop &L, LoopAnalysisManager &AM,
    2374             :                                        LoopStandardAnalysisResults &AR) {
    2375         108 :   return LoopAccessInfo(&L, &AR.SE, &AR.TLI, &AR.AA, &AR.DT, &AR.LI);
    2376             : }
    2377             : 
    2378             : namespace llvm {
    2379             : 
    2380           0 :   Pass *createLAAPass() {
    2381           0 :     return new LoopAccessLegacyAnalysis();
    2382             :   }
    2383             : 
    2384             : } // end namespace llvm

Generated by: LCOV version 1.13