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

Generated by: LCOV version 1.13