lib/Analysis/LoopAccessAnalysis.cpp

   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/Analysis/LoopInfo.h"
  17 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  18 #include "llvm/Analysis/ValueTracking.h"
  19 #include "llvm/IR/DiagnosticInfo.h"
  20 #include "llvm/IR/Dominators.h"
  21 #include "llvm/IR/IRBuilder.h"
  22 #include "llvm/Support/Debug.h"
  23 #include "llvm/Transforms/Utils/VectorUtils.h"
  24 using namespace llvm;
  25
  26 #define DEBUG_TYPE "loop-accesses"
  27
  28 void VectorizationReport::emitAnalysis(VectorizationReport &Message,
  29                                        const Function *TheFunction,
  30                                        const Loop *TheLoop,
  31                                        const char *PassName) {
  32   DebugLoc DL = TheLoop->getStartLoc();
  33   if (Instruction *I = Message.getInstr())
  34     DL = I->getDebugLoc();
  35   emitOptimizationRemarkAnalysis(TheFunction->getContext(), PassName,
  36                                  *TheFunction, DL, Message.str());
  37 }
  38
  39 Value *llvm::stripIntegerCast(Value *V) {
  40   if (CastInst *CI = dyn_cast<CastInst>(V))
  41     if (CI->getOperand(0)->getType()->isIntegerTy())
  42       return CI->getOperand(0);
  43   return V;
  44 }
  45
  46 const SCEV *llvm::replaceSymbolicStrideSCEV(ScalarEvolution *SE,
  47                                             ValueToValueMap &PtrToStride,
  48                                             Value *Ptr, Value *OrigPtr) {
  49
  50   const SCEV *OrigSCEV = SE->getSCEV(Ptr);
  51
  52   // If there is an entry in the map return the SCEV of the pointer with the
  53   // symbolic stride replaced by one.
  54   ValueToValueMap::iterator SI = PtrToStride.find(OrigPtr ? OrigPtr : Ptr);
  55   if (SI != PtrToStride.end()) {
  56     Value *StrideVal = SI->second;
  57
  58     // Strip casts.
  59     StrideVal = stripIntegerCast(StrideVal);
  60
  61     // Replace symbolic stride by one.
  62     Value *One = ConstantInt::get(StrideVal->getType(), 1);
  63     ValueToValueMap RewriteMap;
  64     RewriteMap[StrideVal] = One;
  65
  66     const SCEV *ByOne =
  67         SCEVParameterRewriter::rewrite(OrigSCEV, *SE, RewriteMap, true);
  68     DEBUG(dbgs() << "LAA: Replacing SCEV: " << *OrigSCEV << " by: " << *ByOne
  69                  << "\n");
  70     return ByOne;
  71   }
  72
  73   // Otherwise, just return the SCEV of the original pointer.
  74   return SE->getSCEV(Ptr);
  75 }
  76
  77 void LoopAccessInfo::RuntimePointerCheck::insert(ScalarEvolution *SE, Loop *Lp,
  78                                                  Value *Ptr, bool WritePtr,
  79                                                  unsigned DepSetId,
  80                                                  unsigned ASId,
  81                                                  ValueToValueMap &Strides) {
  82   // Get the stride replaced scev.
  83   const SCEV *Sc = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
  84   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
  85   assert(AR && "Invalid addrec expression");
  86   const SCEV *Ex = SE->getBackedgeTakenCount(Lp);
  87   const SCEV *ScEnd = AR->evaluateAtIteration(Ex, *SE);
  88   Pointers.push_back(Ptr);
  89   Starts.push_back(AR->getStart());
  90   Ends.push_back(ScEnd);
  91   IsWritePtr.push_back(WritePtr);
  92   DependencySetId.push_back(DepSetId);
  93   AliasSetId.push_back(ASId);
  94 }
  95
  96 namespace {
  97 /// \brief Analyses memory accesses in a loop.
  98 ///
  99 /// Checks whether run time pointer checks are needed and builds sets for data
 100 /// dependence checking.
 101 class AccessAnalysis {
 102 public:
 103   /// \brief Read or write access location.
 104   typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
 105   typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet;
 106
 107   /// \brief Set of potential dependent memory accesses.
 108   typedef EquivalenceClasses<MemAccessInfo> DepCandidates;
 109
 110   AccessAnalysis(const DataLayout *Dl, AliasAnalysis *AA, DepCandidates &DA) :
 111     DL(Dl), AST(*AA), DepCands(DA), IsRTCheckNeeded(false) {}
 112
 113   /// \brief Register a load  and whether it is only read from.
 114   void addLoad(AliasAnalysis::Location &Loc, bool IsReadOnly) {
 115     Value *Ptr = const_cast<Value*>(Loc.Ptr);
 116     AST.add(Ptr, AliasAnalysis::UnknownSize, Loc.AATags);
 117     Accesses.insert(MemAccessInfo(Ptr, false));
 118     if (IsReadOnly)
 119       ReadOnlyPtr.insert(Ptr);
 120   }
 121
 122   /// \brief Register a store.
 123   void addStore(AliasAnalysis::Location &Loc) {
 124     Value *Ptr = const_cast<Value*>(Loc.Ptr);
 125     AST.add(Ptr, AliasAnalysis::UnknownSize, Loc.AATags);
 126     Accesses.insert(MemAccessInfo(Ptr, true));
 127   }
 128
 129   /// \brief Check whether we can check the pointers at runtime for
 130   /// non-intersection.
 131   bool canCheckPtrAtRT(LoopAccessInfo::RuntimePointerCheck &RtCheck,
 132                        unsigned &NumComparisons,
 133                        ScalarEvolution *SE, Loop *TheLoop,
 134                        ValueToValueMap &Strides,
 135                        bool ShouldCheckStride = false);
 136
 137   /// \brief Goes over all memory accesses, checks whether a RT check is needed
 138   /// and builds sets of dependent accesses.
 139   void buildDependenceSets() {
 140     processMemAccesses();
 141   }
 142
 143   bool isRTCheckNeeded() { return IsRTCheckNeeded; }
 144
 145   bool isDependencyCheckNeeded() { return !CheckDeps.empty(); }
 146   void resetDepChecks() { CheckDeps.clear(); }
 147
 148   MemAccessInfoSet &getDependenciesToCheck() { return CheckDeps; }
 149
 150 private:
 151   typedef SetVector<MemAccessInfo> PtrAccessSet;
 152
 153   /// \brief Go over all memory access and check whether runtime pointer checks
 154   /// are needed /// and build sets of dependency check candidates.
 155   void processMemAccesses();
 156
 157   /// Set of all accesses.
 158   PtrAccessSet Accesses;
 159
 160   /// Set of accesses that need a further dependence check.
 161   MemAccessInfoSet CheckDeps;
 162
 163   /// Set of pointers that are read only.
 164   SmallPtrSet<Value*, 16> ReadOnlyPtr;
 165
 166   const DataLayout *DL;
 167
 168   /// An alias set tracker to partition the access set by underlying object and
 169   //intrinsic property (such as TBAA metadata).
 170   AliasSetTracker AST;
 171
 172   /// Sets of potentially dependent accesses - members of one set share an
 173   /// underlying pointer. The set "CheckDeps" identfies which sets really need a
 174   /// dependence check.
 175   DepCandidates &DepCands;
 176
 177   bool IsRTCheckNeeded;
 178 };
 179
 180 } // end anonymous namespace
 181
 182 /// \brief Check whether a pointer can participate in a runtime bounds check.
 183 static bool hasComputableBounds(ScalarEvolution *SE, ValueToValueMap &Strides,
 184                                 Value *Ptr) {
 185   const SCEV *PtrScev = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
 186   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
 187   if (!AR)
 188     return false;
 189
 190   return AR->isAffine();
 191 }
 192
 193 /// \brief Check the stride of the pointer and ensure that it does not wrap in
 194 /// the address space.
 195 static int isStridedPtr(ScalarEvolution *SE, const DataLayout *DL, Value *Ptr,
 196                         const Loop *Lp, ValueToValueMap &StridesMap);
 197
 198 bool AccessAnalysis::canCheckPtrAtRT(
 199     LoopAccessInfo::RuntimePointerCheck &RtCheck,
 200     unsigned &NumComparisons, ScalarEvolution *SE, Loop *TheLoop,
 201     ValueToValueMap &StridesMap, bool ShouldCheckStride) {
 202   // Find pointers with computable bounds. We are going to use this information
 203   // to place a runtime bound check.
 204   bool CanDoRT = true;
 205
 206   bool IsDepCheckNeeded = isDependencyCheckNeeded();
 207   NumComparisons = 0;
 208
 209   // We assign a consecutive id to access from different alias sets.
 210   // Accesses between different groups doesn't need to be checked.
 211   unsigned ASId = 1;
 212   for (auto &AS : AST) {
 213     unsigned NumReadPtrChecks = 0;
 214     unsigned NumWritePtrChecks = 0;
 215
 216     // We assign consecutive id to access from different dependence sets.
 217     // Accesses within the same set don't need a runtime check.
 218     unsigned RunningDepId = 1;
 219     DenseMap<Value *, unsigned> DepSetId;
 220
 221     for (auto A : AS) {
 222       Value *Ptr = A.getValue();
 223       bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true));
 224       MemAccessInfo Access(Ptr, IsWrite);
 225
 226       if (IsWrite)
 227         ++NumWritePtrChecks;
 228       else
 229         ++NumReadPtrChecks;
 230
 231       if (hasComputableBounds(SE, StridesMap, Ptr) &&
 232           // When we run after a failing dependency check we have to make sure we
 233           // don't have wrapping pointers.
 234           (!ShouldCheckStride ||
 235            isStridedPtr(SE, DL, Ptr, TheLoop, StridesMap) == 1)) {
 236         // The id of the dependence set.
 237         unsigned DepId;
 238
 239         if (IsDepCheckNeeded) {
 240           Value *Leader = DepCands.getLeaderValue(Access).getPointer();
 241           unsigned &LeaderId = DepSetId[Leader];
 242           if (!LeaderId)
 243             LeaderId = RunningDepId++;
 244           DepId = LeaderId;
 245         } else
 246           // Each access has its own dependence set.
 247           DepId = RunningDepId++;
 248
 249         RtCheck.insert(SE, TheLoop, Ptr, IsWrite, DepId, ASId, StridesMap);
 250
 251         DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
 252       } else {
 253         CanDoRT = false;
 254       }
 255     }
 256
 257     if (IsDepCheckNeeded && CanDoRT && RunningDepId == 2)
 258       NumComparisons += 0; // Only one dependence set.
 259     else {
 260       NumComparisons += (NumWritePtrChecks * (NumReadPtrChecks +
 261                                               NumWritePtrChecks - 1));
 262     }
 263
 264     ++ASId;
 265   }
 266
 267   // If the pointers that we would use for the bounds comparison have different
 268   // address spaces, assume the values aren't directly comparable, so we can't
 269   // use them for the runtime check. We also have to assume they could
 270   // overlap. In the future there should be metadata for whether address spaces
 271   // are disjoint.
 272   unsigned NumPointers = RtCheck.Pointers.size();
 273   for (unsigned i = 0; i < NumPointers; ++i) {
 274     for (unsigned j = i + 1; j < NumPointers; ++j) {
 275       // Only need to check pointers between two different dependency sets.
 276       if (RtCheck.DependencySetId[i] == RtCheck.DependencySetId[j])
 277        continue;
 278       // Only need to check pointers in the same alias set.
 279       if (RtCheck.AliasSetId[i] != RtCheck.AliasSetId[j])
 280         continue;
 281
 282       Value *PtrI = RtCheck.Pointers[i];
 283       Value *PtrJ = RtCheck.Pointers[j];
 284
 285       unsigned ASi = PtrI->getType()->getPointerAddressSpace();
 286       unsigned ASj = PtrJ->getType()->getPointerAddressSpace();
 287       if (ASi != ASj) {
 288         DEBUG(dbgs() << "LAA: Runtime check would require comparison between"
 289                        " different address spaces\n");
 290         return false;
 291       }
 292     }
 293   }
 294
 295   return CanDoRT;
 296 }
 297
 298 void AccessAnalysis::processMemAccesses() {
 299   // We process the set twice: first we process read-write pointers, last we
 300   // process read-only pointers. This allows us to skip dependence tests for
 301   // read-only pointers.
 302
 303   DEBUG(dbgs() << "LAA: Processing memory accesses...\n");
 304   DEBUG(dbgs() << "  AST: "; AST.dump());
 305   DEBUG(dbgs() << "LAA:   Accesses:\n");
 306   DEBUG({
 307     for (auto A : Accesses)
 308       dbgs() << "\t" << *A.getPointer() << " (" <<
 309                 (A.getInt() ? "write" : (ReadOnlyPtr.count(A.getPointer()) ?
 310                                          "read-only" : "read")) << ")\n";
 311   });
 312
 313   // The AliasSetTracker has nicely partitioned our pointers by metadata
 314   // compatibility and potential for underlying-object overlap. As a result, we
 315   // only need to check for potential pointer dependencies within each alias
 316   // set.
 317   for (auto &AS : AST) {
 318     // Note that both the alias-set tracker and the alias sets themselves used
 319     // linked lists internally and so the iteration order here is deterministic
 320     // (matching the original instruction order within each set).
 321
 322     bool SetHasWrite = false;
 323
 324     // Map of pointers to last access encountered.
 325     typedef DenseMap<Value*, MemAccessInfo> UnderlyingObjToAccessMap;
 326     UnderlyingObjToAccessMap ObjToLastAccess;
 327
 328     // Set of access to check after all writes have been processed.
 329     PtrAccessSet DeferredAccesses;
 330
 331     // Iterate over each alias set twice, once to process read/write pointers,
 332     // and then to process read-only pointers.
 333     for (int SetIteration = 0; SetIteration < 2; ++SetIteration) {
 334       bool UseDeferred = SetIteration > 0;
 335       PtrAccessSet &S = UseDeferred ? DeferredAccesses : Accesses;
 336
 337       for (auto AV : AS) {
 338         Value *Ptr = AV.getValue();
 339
 340         // For a single memory access in AliasSetTracker, Accesses may contain
 341         // both read and write, and they both need to be handled for CheckDeps.
 342         for (auto AC : S) {
 343           if (AC.getPointer() != Ptr)
 344             continue;
 345
 346           bool IsWrite = AC.getInt();
 347
 348           // If we're using the deferred access set, then it contains only
 349           // reads.
 350           bool IsReadOnlyPtr = ReadOnlyPtr.count(Ptr) && !IsWrite;
 351           if (UseDeferred && !IsReadOnlyPtr)
 352             continue;
 353           // Otherwise, the pointer must be in the PtrAccessSet, either as a
 354           // read or a write.
 355           assert(((IsReadOnlyPtr && UseDeferred) || IsWrite ||
 356                   S.count(MemAccessInfo(Ptr, false))) &&
 357                  "Alias-set pointer not in the access set?");
 358
 359           MemAccessInfo Access(Ptr, IsWrite);
 360           DepCands.insert(Access);
 361
 362           // Memorize read-only pointers for later processing and skip them in
 363           // the first round (they need to be checked after we have seen all
 364           // write pointers). Note: we also mark pointer that are not
 365           // consecutive as "read-only" pointers (so that we check
 366           // "a[b[i]] +="). Hence, we need the second check for "!IsWrite".
 367           if (!UseDeferred && IsReadOnlyPtr) {
 368             DeferredAccesses.insert(Access);
 369             continue;
 370           }
 371
 372           // If this is a write - check other reads and writes for conflicts. If
 373           // this is a read only check other writes for conflicts (but only if
 374           // there is no other write to the ptr - this is an optimization to
 375           // catch "a[i] = a[i] + " without having to do a dependence check).
 376           if ((IsWrite || IsReadOnlyPtr) && SetHasWrite) {
 377             CheckDeps.insert(Access);
 378             IsRTCheckNeeded = true;
 379           }
 380
 381           if (IsWrite)
 382             SetHasWrite = true;
 383
 384           // Create sets of pointers connected by a shared alias set and
 385           // underlying object.
 386           typedef SmallVector<Value *, 16> ValueVector;
 387           ValueVector TempObjects;
 388           GetUnderlyingObjects(Ptr, TempObjects, DL);
 389           for (Value *UnderlyingObj : TempObjects) {
 390             UnderlyingObjToAccessMap::iterator Prev =
 391                 ObjToLastAccess.find(UnderlyingObj);
 392             if (Prev != ObjToLastAccess.end())
 393               DepCands.unionSets(Access, Prev->second);
 394
 395             ObjToLastAccess[UnderlyingObj] = Access;
 396           }
 397         }
 398       }
 399     }
 400   }
 401 }
 402
 403 namespace {
 404 /// \brief Checks memory dependences among accesses to the same underlying
 405 /// object to determine whether there vectorization is legal or not (and at
 406 /// which vectorization factor).
 407 ///
 408 /// This class works under the assumption that we already checked that memory
 409 /// locations with different underlying pointers are "must-not alias".
 410 /// We use the ScalarEvolution framework to symbolically evalutate access
 411 /// functions pairs. Since we currently don't restructure the loop we can rely
 412 /// on the program order of memory accesses to determine their safety.
 413 /// At the moment we will only deem accesses as safe for:
 414 ///  * A negative constant distance assuming program order.
 415 ///
 416 ///      Safe: tmp = a[i + 1];     OR     a[i + 1] = x;
 417 ///            a[i] = tmp;                y = a[i];
 418 ///
 419 ///   The latter case is safe because later checks guarantuee that there can't
 420 ///   be a cycle through a phi node (that is, we check that "x" and "y" is not
 421 ///   the same variable: a header phi can only be an induction or a reduction, a
 422 ///   reduction can't have a memory sink, an induction can't have a memory
 423 ///   source). This is important and must not be violated (or we have to
 424 ///   resort to checking for cycles through memory).
 425 ///
 426 ///  * A positive constant distance assuming program order that is bigger
 427 ///    than the biggest memory access.
 428 ///
 429 ///     tmp = a[i]        OR              b[i] = x
 430 ///     a[i+2] = tmp                      y = b[i+2];
 431 ///
 432 ///     Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively.
 433 ///
 434 ///  * Zero distances and all accesses have the same size.
 435 ///
 436 class MemoryDepChecker {
 437 public:
 438   typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
 439   typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet;
 440
 441   MemoryDepChecker(ScalarEvolution *Se, const DataLayout *Dl, const Loop *L)
 442       : SE(Se), DL(Dl), InnermostLoop(L), AccessIdx(0),
 443         ShouldRetryWithRuntimeCheck(false) {}
 444
 445   /// \brief Register the location (instructions are given increasing numbers)
 446   /// of a write access.
 447   void addAccess(StoreInst *SI) {
 448     Value *Ptr = SI->getPointerOperand();
 449     Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
 450     InstMap.push_back(SI);
 451     ++AccessIdx;
 452   }
 453
 454   /// \brief Register the location (instructions are given increasing numbers)
 455   /// of a write access.
 456   void addAccess(LoadInst *LI) {
 457     Value *Ptr = LI->getPointerOperand();
 458     Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx);
 459     InstMap.push_back(LI);
 460     ++AccessIdx;
 461   }
 462
 463   /// \brief Check whether the dependencies between the accesses are safe.
 464   ///
 465   /// Only checks sets with elements in \p CheckDeps.
 466   bool areDepsSafe(AccessAnalysis::DepCandidates &AccessSets,
 467                    MemAccessInfoSet &CheckDeps, ValueToValueMap &Strides);
 468
 469   /// \brief The maximum number of bytes of a vector register we can vectorize
 470   /// the accesses safely with.
 471   unsigned getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; }
 472
 473   /// \brief In same cases when the dependency check fails we can still
 474   /// vectorize the loop with a dynamic array access check.
 475   bool shouldRetryWithRuntimeCheck() { return ShouldRetryWithRuntimeCheck; }
 476
 477 private:
 478   ScalarEvolution *SE;
 479   const DataLayout *DL;
 480   const Loop *InnermostLoop;
 481
 482   /// \brief Maps access locations (ptr, read/write) to program order.
 483   DenseMap<MemAccessInfo, std::vector<unsigned> > Accesses;
 484
 485   /// \brief Memory access instructions in program order.
 486   SmallVector<Instruction *, 16> InstMap;
 487
 488   /// \brief The program order index to be used for the next instruction.
 489   unsigned AccessIdx;
 490
 491   // We can access this many bytes in parallel safely.
 492   unsigned MaxSafeDepDistBytes;
 493
 494   /// \brief If we see a non-constant dependence distance we can still try to
 495   /// vectorize this loop with runtime checks.
 496   bool ShouldRetryWithRuntimeCheck;
 497
 498   /// \brief Check whether there is a plausible dependence between the two
 499   /// accesses.
 500   ///
 501   /// Access \p A must happen before \p B in program order. The two indices
 502   /// identify the index into the program order map.
 503   ///
 504   /// This function checks  whether there is a plausible dependence (or the
 505   /// absence of such can't be proved) between the two accesses. If there is a
 506   /// plausible dependence but the dependence distance is bigger than one
 507   /// element access it records this distance in \p MaxSafeDepDistBytes (if this
 508   /// distance is smaller than any other distance encountered so far).
 509   /// Otherwise, this function returns true signaling a possible dependence.
 510   bool isDependent(const MemAccessInfo &A, unsigned AIdx,
 511                    const MemAccessInfo &B, unsigned BIdx,
 512                    ValueToValueMap &Strides);
 513
 514   /// \brief Check whether the data dependence could prevent store-load
 515   /// forwarding.
 516   bool couldPreventStoreLoadForward(unsigned Distance, unsigned TypeByteSize);
 517 };
 518
 519 } // end anonymous namespace
 520
 521 static bool isInBoundsGep(Value *Ptr) {
 522   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr))
 523     return GEP->isInBounds();
 524   return false;
 525 }
 526
 527 /// \brief Check whether the access through \p Ptr has a constant stride.
 528 static int isStridedPtr(ScalarEvolution *SE, const DataLayout *DL, Value *Ptr,
 529                         const Loop *Lp, ValueToValueMap &StridesMap) {
 530   const Type *Ty = Ptr->getType();
 531   assert(Ty->isPointerTy() && "Unexpected non-ptr");
 532
 533   // Make sure that the pointer does not point to aggregate types.
 534   const PointerType *PtrTy = cast<PointerType>(Ty);
 535   if (PtrTy->getElementType()->isAggregateType()) {
 536     DEBUG(dbgs() << "LAA: Bad stride - Not a pointer to a scalar type"
 537           << *Ptr << "\n");
 538     return 0;
 539   }
 540
 541   const SCEV *PtrScev = replaceSymbolicStrideSCEV(SE, StridesMap, Ptr);
 542
 543   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
 544   if (!AR) {
 545     DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer "
 546           << *Ptr << " SCEV: " << *PtrScev << "\n");
 547     return 0;
 548   }
 549
 550   // The accesss function must stride over the innermost loop.
 551   if (Lp != AR->getLoop()) {
 552     DEBUG(dbgs() << "LAA: Bad stride - Not striding over innermost loop " <<
 553           *Ptr << " SCEV: " << *PtrScev << "\n");
 554   }
 555
 556   // The address calculation must not wrap. Otherwise, a dependence could be
 557   // inverted.
 558   // An inbounds getelementptr that is a AddRec with a unit stride
 559   // cannot wrap per definition. The unit stride requirement is checked later.
 560   // An getelementptr without an inbounds attribute and unit stride would have
 561   // to access the pointer value "0" which is undefined behavior in address
 562   // space 0, therefore we can also vectorize this case.
 563   bool IsInBoundsGEP = isInBoundsGep(Ptr);
 564   bool IsNoWrapAddRec = AR->getNoWrapFlags(SCEV::NoWrapMask);
 565   bool IsInAddressSpaceZero = PtrTy->getAddressSpace() == 0;
 566   if (!IsNoWrapAddRec && !IsInBoundsGEP && !IsInAddressSpaceZero) {
 567     DEBUG(dbgs() << "LAA: Bad stride - Pointer may wrap in the address space "
 568           << *Ptr << " SCEV: " << *PtrScev << "\n");
 569     return 0;
 570   }
 571
 572   // Check the step is constant.
 573   const SCEV *Step = AR->getStepRecurrence(*SE);
 574
 575   // Calculate the pointer stride and check if it is consecutive.
 576   const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
 577   if (!C) {
 578     DEBUG(dbgs() << "LAA: Bad stride - Not a constant strided " << *Ptr <<
 579           " SCEV: " << *PtrScev << "\n");
 580     return 0;
 581   }
 582
 583   int64_t Size = DL->getTypeAllocSize(PtrTy->getElementType());
 584   const APInt &APStepVal = C->getValue()->getValue();
 585
 586   // Huge step value - give up.
 587   if (APStepVal.getBitWidth() > 64)
 588     return 0;
 589
 590   int64_t StepVal = APStepVal.getSExtValue();
 591
 592   // Strided access.
 593   int64_t Stride = StepVal / Size;
 594   int64_t Rem = StepVal % Size;
 595   if (Rem)
 596     return 0;
 597
 598   // If the SCEV could wrap but we have an inbounds gep with a unit stride we
 599   // know we can't "wrap around the address space". In case of address space
 600   // zero we know that this won't happen without triggering undefined behavior.
 601   if (!IsNoWrapAddRec && (IsInBoundsGEP || IsInAddressSpaceZero) &&
 602       Stride != 1 && Stride != -1)
 603     return 0;
 604
 605   return Stride;
 606 }
 607
 608 bool MemoryDepChecker::couldPreventStoreLoadForward(unsigned Distance,
 609                                                     unsigned TypeByteSize) {
 610   // If loads occur at a distance that is not a multiple of a feasible vector
 611   // factor store-load forwarding does not take place.
 612   // Positive dependences might cause troubles because vectorizing them might
 613   // prevent store-load forwarding making vectorized code run a lot slower.
 614   //   a[i] = a[i-3] ^ a[i-8];
 615   //   The stores to a[i:i+1] don't align with the stores to a[i-3:i-2] and
 616   //   hence on your typical architecture store-load forwarding does not take
 617   //   place. Vectorizing in such cases does not make sense.
 618   // Store-load forwarding distance.
 619   const unsigned NumCyclesForStoreLoadThroughMemory = 8*TypeByteSize;
 620   // Maximum vector factor.
 621   unsigned MaxVFWithoutSLForwardIssues =
 622     VectorizerParams::MaxVectorWidth * TypeByteSize;
 623   if(MaxSafeDepDistBytes < MaxVFWithoutSLForwardIssues)
 624     MaxVFWithoutSLForwardIssues = MaxSafeDepDistBytes;
 625
 626   for (unsigned vf = 2*TypeByteSize; vf <= MaxVFWithoutSLForwardIssues;
 627        vf *= 2) {
 628     if (Distance % vf && Distance / vf < NumCyclesForStoreLoadThroughMemory) {
 629       MaxVFWithoutSLForwardIssues = (vf >>=1);
 630       break;
 631     }
 632   }
 633
 634   if (MaxVFWithoutSLForwardIssues< 2*TypeByteSize) {
 635     DEBUG(dbgs() << "LAA: Distance " << Distance <<
 636           " that could cause a store-load forwarding conflict\n");
 637     return true;
 638   }
 639
 640   if (MaxVFWithoutSLForwardIssues < MaxSafeDepDistBytes &&
 641       MaxVFWithoutSLForwardIssues !=
 642       VectorizerParams::MaxVectorWidth * TypeByteSize)
 643     MaxSafeDepDistBytes = MaxVFWithoutSLForwardIssues;
 644   return false;
 645 }
 646
 647 bool MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
 648                                    const MemAccessInfo &B, unsigned BIdx,
 649                                    ValueToValueMap &Strides) {
 650   assert (AIdx < BIdx && "Must pass arguments in program order");
 651
 652   Value *APtr = A.getPointer();
 653   Value *BPtr = B.getPointer();
 654   bool AIsWrite = A.getInt();
 655   bool BIsWrite = B.getInt();
 656
 657   // Two reads are independent.
 658   if (!AIsWrite && !BIsWrite)
 659     return false;
 660
 661   // We cannot check pointers in different address spaces.
 662   if (APtr->getType()->getPointerAddressSpace() !=
 663       BPtr->getType()->getPointerAddressSpace())
 664     return true;
 665
 666   const SCEV *AScev = replaceSymbolicStrideSCEV(SE, Strides, APtr);
 667   const SCEV *BScev = replaceSymbolicStrideSCEV(SE, Strides, BPtr);
 668
 669   int StrideAPtr = isStridedPtr(SE, DL, APtr, InnermostLoop, Strides);
 670   int StrideBPtr = isStridedPtr(SE, DL, BPtr, InnermostLoop, Strides);
 671
 672   const SCEV *Src = AScev;
 673   const SCEV *Sink = BScev;
 674
 675   // If the induction step is negative we have to invert source and sink of the
 676   // dependence.
 677   if (StrideAPtr < 0) {
 678     //Src = BScev;
 679     //Sink = AScev;
 680     std::swap(APtr, BPtr);
 681     std::swap(Src, Sink);
 682     std::swap(AIsWrite, BIsWrite);
 683     std::swap(AIdx, BIdx);
 684     std::swap(StrideAPtr, StrideBPtr);
 685   }
 686
 687   const SCEV *Dist = SE->getMinusSCEV(Sink, Src);
 688
 689   DEBUG(dbgs() << "LAA: Src Scev: " << *Src << "Sink Scev: " << *Sink
 690         << "(Induction step: " << StrideAPtr <<  ")\n");
 691   DEBUG(dbgs() << "LAA: Distance for " << *InstMap[AIdx] << " to "
 692         << *InstMap[BIdx] << ": " << *Dist << "\n");
 693
 694   // Need consecutive accesses. We don't want to vectorize
 695   // "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in
 696   // the address space.
 697   if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){
 698     DEBUG(dbgs() << "Non-consecutive pointer access\n");
 699     return true;
 700   }
 701
 702   const SCEVConstant *C = dyn_cast<SCEVConstant>(Dist);
 703   if (!C) {
 704     DEBUG(dbgs() << "LAA: Dependence because of non-constant distance\n");
 705     ShouldRetryWithRuntimeCheck = true;
 706     return true;
 707   }
 708
 709   Type *ATy = APtr->getType()->getPointerElementType();
 710   Type *BTy = BPtr->getType()->getPointerElementType();
 711   unsigned TypeByteSize = DL->getTypeAllocSize(ATy);
 712
 713   // Negative distances are not plausible dependencies.
 714   const APInt &Val = C->getValue()->getValue();
 715   if (Val.isNegative()) {
 716     bool IsTrueDataDependence = (AIsWrite && !BIsWrite);
 717     if (IsTrueDataDependence &&
 718         (couldPreventStoreLoadForward(Val.abs().getZExtValue(), TypeByteSize) ||
 719          ATy != BTy))
 720       return true;
 721
 722     DEBUG(dbgs() << "LAA: Dependence is negative: NoDep\n");
 723     return false;
 724   }
 725
 726   // Write to the same location with the same size.
 727   // Could be improved to assert type sizes are the same (i32 == float, etc).
 728   if (Val == 0) {
 729     if (ATy == BTy)
 730       return false;
 731     DEBUG(dbgs() << "LAA: Zero dependence difference but different types\n");
 732     return true;
 733   }
 734
 735   assert(Val.isStrictlyPositive() && "Expect a positive value");
 736
 737   // Positive distance bigger than max vectorization factor.
 738   if (ATy != BTy) {
 739     DEBUG(dbgs() <<
 740           "LAA: ReadWrite-Write positive dependency with different types\n");
 741     return false;
 742   }
 743
 744   unsigned Distance = (unsigned) Val.getZExtValue();
 745
 746   // Bail out early if passed-in parameters make vectorization not feasible.
 747   unsigned ForcedFactor = (VectorizerParams::VectorizationFactor ?
 748                            VectorizerParams::VectorizationFactor : 1);
 749   unsigned ForcedUnroll = (VectorizerParams::VectorizationInterleave ?
 750                            VectorizerParams::VectorizationInterleave : 1);
 751
 752   // The distance must be bigger than the size needed for a vectorized version
 753   // of the operation and the size of the vectorized operation must not be
 754   // bigger than the currrent maximum size.
 755   if (Distance < 2*TypeByteSize ||
 756       2*TypeByteSize > MaxSafeDepDistBytes ||
 757       Distance < TypeByteSize * ForcedUnroll * ForcedFactor) {
 758     DEBUG(dbgs() << "LAA: Failure because of Positive distance "
 759         << Val.getSExtValue() << '\n');
 760     return true;
 761   }
 762
 763   MaxSafeDepDistBytes = Distance < MaxSafeDepDistBytes ?
 764     Distance : MaxSafeDepDistBytes;
 765
 766   bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
 767   if (IsTrueDataDependence &&
 768       couldPreventStoreLoadForward(Distance, TypeByteSize))
 769      return true;
 770
 771   DEBUG(dbgs() << "LAA: Positive distance " << Val.getSExtValue() <<
 772         " with max VF = " << MaxSafeDepDistBytes / TypeByteSize << '\n');
 773
 774   return false;
 775 }
 776
 777 bool MemoryDepChecker::areDepsSafe(AccessAnalysis::DepCandidates &AccessSets,
 778                                    MemAccessInfoSet &CheckDeps,
 779                                    ValueToValueMap &Strides) {
 780
 781   MaxSafeDepDistBytes = -1U;
 782   while (!CheckDeps.empty()) {
 783     MemAccessInfo CurAccess = *CheckDeps.begin();
 784
 785     // Get the relevant memory access set.
 786     EquivalenceClasses<MemAccessInfo>::iterator I =
 787       AccessSets.findValue(AccessSets.getLeaderValue(CurAccess));
 788
 789     // Check accesses within this set.
 790     EquivalenceClasses<MemAccessInfo>::member_iterator AI, AE;
 791     AI = AccessSets.member_begin(I), AE = AccessSets.member_end();
 792
 793     // Check every access pair.
 794     while (AI != AE) {
 795       CheckDeps.erase(*AI);
 796       EquivalenceClasses<MemAccessInfo>::member_iterator OI = std::next(AI);
 797       while (OI != AE) {
 798         // Check every accessing instruction pair in program order.
 799         for (std::vector<unsigned>::iterator I1 = Accesses[*AI].begin(),
 800              I1E = Accesses[*AI].end(); I1 != I1E; ++I1)
 801           for (std::vector<unsigned>::iterator I2 = Accesses[*OI].begin(),
 802                I2E = Accesses[*OI].end(); I2 != I2E; ++I2) {
 803             if (*I1 < *I2 && isDependent(*AI, *I1, *OI, *I2, Strides))
 804               return false;
 805             if (*I2 < *I1 && isDependent(*OI, *I2, *AI, *I1, Strides))
 806               return false;
 807           }
 808         ++OI;
 809       }
 810       AI++;
 811     }
 812   }
 813   return true;
 814 }
 815
 816 void LoopAccessInfo::analyzeLoop(ValueToValueMap &Strides) {
 817
 818   typedef SmallVector<Value*, 16> ValueVector;
 819   typedef SmallPtrSet<Value*, 16> ValueSet;
 820
 821   // Holds the Load and Store *instructions*.
 822   ValueVector Loads;
 823   ValueVector Stores;
 824
 825   // Holds all the different accesses in the loop.
 826   unsigned NumReads = 0;
 827   unsigned NumReadWrites = 0;
 828
 829   PtrRtCheck.Pointers.clear();
 830   PtrRtCheck.Need = false;
 831
 832   const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel();
 833   MemoryDepChecker DepChecker(SE, DL, TheLoop);
 834
 835   // For each block.
 836   for (Loop::block_iterator bb = TheLoop->block_begin(),
 837        be = TheLoop->block_end(); bb != be; ++bb) {
 838
 839     // Scan the BB and collect legal loads and stores.
 840     for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
 841          ++it) {
 842
 843       // If this is a load, save it. If this instruction can read from memory
 844       // but is not a load, then we quit. Notice that we don't handle function
 845       // calls that read or write.
 846       if (it->mayReadFromMemory()) {
 847         // Many math library functions read the rounding mode. We will only
 848         // vectorize a loop if it contains known function calls that don't set
 849         // the flag. Therefore, it is safe to ignore this read from memory.
 850         CallInst *Call = dyn_cast<CallInst>(it);
 851         if (Call && getIntrinsicIDForCall(Call, TLI))
 852           continue;
 853
 854         LoadInst *Ld = dyn_cast<LoadInst>(it);
 855         if (!Ld || (!Ld->isSimple() && !IsAnnotatedParallel)) {
 856           emitAnalysis(VectorizationReport(Ld)
 857                        << "read with atomic ordering or volatile read");
 858           DEBUG(dbgs() << "LAA: Found a non-simple load.\n");
 859           CanVecMem = false;
 860           return;
 861         }
 862         NumLoads++;
 863         Loads.push_back(Ld);
 864         DepChecker.addAccess(Ld);
 865         continue;
 866       }
 867
 868       // Save 'store' instructions. Abort if other instructions write to memory.
 869       if (it->mayWriteToMemory()) {
 870         StoreInst *St = dyn_cast<StoreInst>(it);
 871         if (!St) {
 872           emitAnalysis(VectorizationReport(it) <<
 873                        "instruction cannot be vectorized");
 874           CanVecMem = false;
 875           return;
 876         }
 877         if (!St->isSimple() && !IsAnnotatedParallel) {
 878           emitAnalysis(VectorizationReport(St)
 879                        << "write with atomic ordering or volatile write");
 880           DEBUG(dbgs() << "LAA: Found a non-simple store.\n");
 881           CanVecMem = false;
 882           return;
 883         }
 884         NumStores++;
 885         Stores.push_back(St);
 886         DepChecker.addAccess(St);
 887       }
 888     } // Next instr.
 889   } // Next block.
 890
 891   // Now we have two lists that hold the loads and the stores.
 892   // Next, we find the pointers that they use.
 893
 894   // Check if we see any stores. If there are no stores, then we don't
 895   // care if the pointers are *restrict*.
 896   if (!Stores.size()) {
 897     DEBUG(dbgs() << "LAA: Found a read-only loop!\n");
 898     CanVecMem = true;
 899     return;
 900   }
 901
 902   AccessAnalysis::DepCandidates DependentAccesses;
 903   AccessAnalysis Accesses(DL, AA, DependentAccesses);
 904
 905   // Holds the analyzed pointers. We don't want to call GetUnderlyingObjects
 906   // multiple times on the same object. If the ptr is accessed twice, once
 907   // for read and once for write, it will only appear once (on the write
 908   // list). This is okay, since we are going to check for conflicts between
 909   // writes and between reads and writes, but not between reads and reads.
 910   ValueSet Seen;
 911
 912   ValueVector::iterator I, IE;
 913   for (I = Stores.begin(), IE = Stores.end(); I != IE; ++I) {
 914     StoreInst *ST = cast<StoreInst>(*I);
 915     Value* Ptr = ST->getPointerOperand();
 916
 917     if (isUniform(Ptr)) {
 918       emitAnalysis(
 919           VectorizationReport(ST)
 920           << "write to a loop invariant address could not be vectorized");
 921       DEBUG(dbgs() << "LAA: We don't allow storing to uniform addresses\n");
 922       CanVecMem = false;
 923       return;
 924     }
 925
 926     // If we did *not* see this pointer before, insert it to  the read-write
 927     // list. At this phase it is only a 'write' list.
 928     if (Seen.insert(Ptr).second) {
 929       ++NumReadWrites;
 930
 931       AliasAnalysis::Location Loc = AA->getLocation(ST);
 932       // The TBAA metadata could have a control dependency on the predication
 933       // condition, so we cannot rely on it when determining whether or not we
 934       // need runtime pointer checks.
 935       if (blockNeedsPredication(ST->getParent(), TheLoop, DT))
 936         Loc.AATags.TBAA = nullptr;
 937
 938       Accesses.addStore(Loc);
 939     }
 940   }
 941
 942   if (IsAnnotatedParallel) {
 943     DEBUG(dbgs()
 944           << "LAA: A loop annotated parallel, ignore memory dependency "
 945           << "checks.\n");
 946     CanVecMem = true;
 947     return;
 948   }
 949
 950   for (I = Loads.begin(), IE = Loads.end(); I != IE; ++I) {
 951     LoadInst *LD = cast<LoadInst>(*I);
 952     Value* Ptr = LD->getPointerOperand();
 953     // If we did *not* see this pointer before, insert it to the
 954     // read list. If we *did* see it before, then it is already in
 955     // the read-write list. This allows us to vectorize expressions
 956     // such as A[i] += x;  Because the address of A[i] is a read-write
 957     // pointer. This only works if the index of A[i] is consecutive.
 958     // If the address of i is unknown (for example A[B[i]]) then we may
 959     // read a few words, modify, and write a few words, and some of the
 960     // words may be written to the same address.
 961     bool IsReadOnlyPtr = false;
 962     if (Seen.insert(Ptr).second ||
 963         !isStridedPtr(SE, DL, Ptr, TheLoop, Strides)) {
 964       ++NumReads;
 965       IsReadOnlyPtr = true;
 966     }
 967
 968     AliasAnalysis::Location Loc = AA->getLocation(LD);
 969     // The TBAA metadata could have a control dependency on the predication
 970     // condition, so we cannot rely on it when determining whether or not we
 971     // need runtime pointer checks.
 972     if (blockNeedsPredication(LD->getParent(), TheLoop, DT))
 973       Loc.AATags.TBAA = nullptr;
 974
 975     Accesses.addLoad(Loc, IsReadOnlyPtr);
 976   }
 977
 978   // If we write (or read-write) to a single destination and there are no
 979   // other reads in this loop then is it safe to vectorize.
 980   if (NumReadWrites == 1 && NumReads == 0) {
 981     DEBUG(dbgs() << "LAA: Found a write-only loop!\n");
 982     CanVecMem = true;
 983     return;
 984   }
 985
 986   // Build dependence sets and check whether we need a runtime pointer bounds
 987   // check.
 988   Accesses.buildDependenceSets();
 989   bool NeedRTCheck = Accesses.isRTCheckNeeded();
 990
 991   // Find pointers with computable bounds. We are going to use this information
 992   // to place a runtime bound check.
 993   unsigned NumComparisons = 0;
 994   bool CanDoRT = false;
 995   if (NeedRTCheck)
 996     CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE, TheLoop,
 997                                        Strides);
 998
 999   DEBUG(dbgs() << "LAA: We need to do " << NumComparisons <<
1000         " pointer comparisons.\n");
1001
1002   // If we only have one set of dependences to check pointers among we don't
1003   // need a runtime check.
1004   if (NumComparisons == 0 && NeedRTCheck)
1005     NeedRTCheck = false;
1006
1007   // Check that we did not collect too many pointers or found an unsizeable
1008   // pointer.
1009   if (!CanDoRT ||
1010       NumComparisons > VectorizerParams::RuntimeMemoryCheckThreshold) {
1011     PtrRtCheck.reset();
1012     CanDoRT = false;
1013   }
1014
1015   if (CanDoRT) {
1016     DEBUG(dbgs() << "LAA: We can perform a memory runtime check if needed.\n");
1017   }
1018
1019   if (NeedRTCheck && !CanDoRT) {
1020     emitAnalysis(VectorizationReport() << "cannot identify array bounds");
1021     DEBUG(dbgs() << "LAA: We can't vectorize because we can't find " <<
1022           "the array bounds.\n");
1023     PtrRtCheck.reset();
1024     CanVecMem = false;
1025     return;
1026   }
1027
1028   PtrRtCheck.Need = NeedRTCheck;
1029
1030   CanVecMem = true;
1031   if (Accesses.isDependencyCheckNeeded()) {
1032     DEBUG(dbgs() << "LAA: Checking memory dependencies\n");
1033     CanVecMem = DepChecker.areDepsSafe(
1034         DependentAccesses, Accesses.getDependenciesToCheck(), Strides);
1035     MaxSafeDepDistBytes = DepChecker.getMaxSafeDepDistBytes();
1036
1037     if (!CanVecMem && DepChecker.shouldRetryWithRuntimeCheck()) {
1038       DEBUG(dbgs() << "LAA: Retrying with memory checks\n");
1039       NeedRTCheck = true;
1040
1041       // Clear the dependency checks. We assume they are not needed.
1042       Accesses.resetDepChecks();
1043
1044       PtrRtCheck.reset();
1045       PtrRtCheck.Need = true;
1046
1047       CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE,
1048                                          TheLoop, Strides, true);
1049       // Check that we did not collect too many pointers or found an unsizeable
1050       // pointer.
1051       if (!CanDoRT ||
1052           NumComparisons > VectorizerParams::RuntimeMemoryCheckThreshold) {
1053         if (!CanDoRT && NumComparisons > 0)
1054           emitAnalysis(VectorizationReport()
1055                        << "cannot check memory dependencies at runtime");
1056         else
1057           emitAnalysis(VectorizationReport()
1058                        << NumComparisons << " exceeds limit of "
1059                        << VectorizerParams::RuntimeMemoryCheckThreshold
1060                        << " dependent memory operations checked at runtime");
1061         DEBUG(dbgs() << "LAA: Can't vectorize with memory checks\n");
1062         PtrRtCheck.reset();
1063         CanVecMem = false;
1064         return;
1065       }
1066
1067       CanVecMem = true;
1068     }
1069   }
1070
1071   if (!CanVecMem)
1072     emitAnalysis(VectorizationReport() <<
1073                  "unsafe dependent memory operations in loop");
1074
1075   DEBUG(dbgs() << "LAA: We" << (NeedRTCheck ? "" : " don't") <<
1076         " need a runtime memory check.\n");
1077 }
1078
1079 bool LoopAccessInfo::blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
1080                                            DominatorTree *DT)  {
1081   assert(TheLoop->contains(BB) && "Unknown block used");
1082
1083   // Blocks that do not dominate the latch need predication.
1084   BasicBlock* Latch = TheLoop->getLoopLatch();
1085   return !DT->dominates(BB, Latch);
1086 }
1087
1088 void LoopAccessInfo::emitAnalysis(VectorizationReport &Message) {
1089   assert(!Report && "Multiple report generated");
1090   Report = Message;
1091 }
1092
1093 bool LoopAccessInfo::isUniform(Value *V) {
1094   return (SE->isLoopInvariant(SE->getSCEV(V), TheLoop));
1095 }
1096
1097 // FIXME: this function is currently a duplicate of the one in
1098 // LoopVectorize.cpp.
1099 static Instruction *getFirstInst(Instruction *FirstInst, Value *V,
1100                                  Instruction *Loc) {
1101   if (FirstInst)
1102     return FirstInst;
1103   if (Instruction *I = dyn_cast<Instruction>(V))
1104     return I->getParent() == Loc->getParent() ? I : nullptr;
1105   return nullptr;
1106 }
1107
1108 std::pair<Instruction *, Instruction *>
1109 LoopAccessInfo::addRuntimeCheck(Instruction *Loc) {
1110   Instruction *tnullptr = nullptr;
1111   if (!PtrRtCheck.Need)
1112     return std::pair<Instruction *, Instruction *>(tnullptr, tnullptr);
1113
1114   unsigned NumPointers = PtrRtCheck.Pointers.size();
1115   SmallVector<TrackingVH<Value> , 2> Starts;
1116   SmallVector<TrackingVH<Value> , 2> Ends;
1117
1118   LLVMContext &Ctx = Loc->getContext();
1119   SCEVExpander Exp(*SE, "induction");
1120   Instruction *FirstInst = nullptr;
1121
1122   for (unsigned i = 0; i < NumPointers; ++i) {
1123     Value *Ptr = PtrRtCheck.Pointers[i];
1124     const SCEV *Sc = SE->getSCEV(Ptr);
1125
1126     if (SE->isLoopInvariant(Sc, TheLoop)) {
1127       DEBUG(dbgs() << "LAA: Adding RT check for a loop invariant ptr:" <<
1128             *Ptr <<"\n");
1129       Starts.push_back(Ptr);
1130       Ends.push_back(Ptr);
1131     } else {
1132       DEBUG(dbgs() << "LAA: Adding RT check for range:" << *Ptr << '\n');
1133       unsigned AS = Ptr->getType()->getPointerAddressSpace();
1134
1135       // Use this type for pointer arithmetic.
1136       Type *PtrArithTy = Type::getInt8PtrTy(Ctx, AS);
1137
1138       Value *Start = Exp.expandCodeFor(PtrRtCheck.Starts[i], PtrArithTy, Loc);
1139       Value *End = Exp.expandCodeFor(PtrRtCheck.Ends[i], PtrArithTy, Loc);
1140       Starts.push_back(Start);
1141       Ends.push_back(End);
1142     }
1143   }
1144
1145   IRBuilder<> ChkBuilder(Loc);
1146   // Our instructions might fold to a constant.
1147   Value *MemoryRuntimeCheck = nullptr;
1148   for (unsigned i = 0; i < NumPointers; ++i) {
1149     for (unsigned j = i+1; j < NumPointers; ++j) {
1150       // No need to check if two readonly pointers intersect.
1151       if (!PtrRtCheck.IsWritePtr[i] && !PtrRtCheck.IsWritePtr[j])
1152         continue;
1153
1154       // Only need to check pointers between two different dependency sets.
1155       if (PtrRtCheck.DependencySetId[i] == PtrRtCheck.DependencySetId[j])
1156        continue;
1157       // Only need to check pointers in the same alias set.
1158       if (PtrRtCheck.AliasSetId[i] != PtrRtCheck.AliasSetId[j])
1159         continue;
1160
1161       unsigned AS0 = Starts[i]->getType()->getPointerAddressSpace();
1162       unsigned AS1 = Starts[j]->getType()->getPointerAddressSpace();
1163
1164       assert((AS0 == Ends[j]->getType()->getPointerAddressSpace()) &&
1165              (AS1 == Ends[i]->getType()->getPointerAddressSpace()) &&
1166              "Trying to bounds check pointers with different address spaces");
1167
1168       Type *PtrArithTy0 = Type::getInt8PtrTy(Ctx, AS0);
1169       Type *PtrArithTy1 = Type::getInt8PtrTy(Ctx, AS1);
1170
1171       Value *Start0 = ChkBuilder.CreateBitCast(Starts[i], PtrArithTy0, "bc");
1172       Value *Start1 = ChkBuilder.CreateBitCast(Starts[j], PtrArithTy1, "bc");
1173       Value *End0 =   ChkBuilder.CreateBitCast(Ends[i],   PtrArithTy1, "bc");
1174       Value *End1 =   ChkBuilder.CreateBitCast(Ends[j],   PtrArithTy0, "bc");
1175
1176       Value *Cmp0 = ChkBuilder.CreateICmpULE(Start0, End1, "bound0");
1177       FirstInst = getFirstInst(FirstInst, Cmp0, Loc);
1178       Value *Cmp1 = ChkBuilder.CreateICmpULE(Start1, End0, "bound1");
1179       FirstInst = getFirstInst(FirstInst, Cmp1, Loc);
1180       Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict");
1181       FirstInst = getFirstInst(FirstInst, IsConflict, Loc);
1182       if (MemoryRuntimeCheck) {
1183         IsConflict = ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict,
1184                                          "conflict.rdx");
1185         FirstInst = getFirstInst(FirstInst, IsConflict, Loc);
1186       }
1187       MemoryRuntimeCheck = IsConflict;
1188     }
1189   }
1190
1191   // We have to do this trickery because the IRBuilder might fold the check to a
1192   // constant expression in which case there is no Instruction anchored in a
1193   // the block.
1194   Instruction *Check = BinaryOperator::CreateAnd(MemoryRuntimeCheck,
1195                                                  ConstantInt::getTrue(Ctx));
1196   ChkBuilder.Insert(Check, "memcheck.conflict");
1197   FirstInst = getFirstInst(FirstInst, Check, Loc);
1198   return std::make_pair(FirstInst, Check);
1199 }
1200
1201 LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
1202                                const DataLayout *DL,
1203                                const TargetLibraryInfo *TLI, AliasAnalysis *AA,
1204                                DominatorTree *DT, ValueToValueMap &Strides)
1205     : TheLoop(L), SE(SE), DL(DL), TLI(TLI), AA(AA), DT(DT), NumLoads(0),
1206       NumStores(0), MaxSafeDepDistBytes(-1U), CanVecMem(false) {
1207   analyzeLoop(Strides);
1208 }
1209
1210 LoopAccessInfo &LoopAccessAnalysis::getInfo(Loop *L, ValueToValueMap &Strides) {
1211   auto &LAI = LoopAccessInfoMap[L];
1212
1213 #ifndef NDEBUG
1214   assert((!LAI || LAI->NumSymbolicStrides == Strides.size()) &&
1215          "Symbolic strides changed for loop");
1216 #endif
1217
1218   if (!LAI) {
1219     LAI = make_unique<LoopAccessInfo>(L, SE, DL, TLI, AA, DT, Strides);
1220 #ifndef NDEBUG
1221     LAI->NumSymbolicStrides = Strides.size();
1222 #endif
1223   }
1224   return *LAI.get();
1225 }
1226
1227 bool LoopAccessAnalysis::runOnFunction(Function &F) {
1228   SE = &getAnalysis<ScalarEvolution>();
1229   DL = F.getParent()->getDataLayout();
1230   auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
1231   TLI = TLIP ? &TLIP->getTLI() : nullptr;
1232   AA = &getAnalysis<AliasAnalysis>();
1233   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1234
1235   return false;
1236 }
1237
1238 void LoopAccessAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
1239     AU.addRequired<ScalarEvolution>();
1240     AU.addRequired<AliasAnalysis>();
1241     AU.addRequired<DominatorTreeWrapperPass>();
1242
1243     AU.setPreservesAll();
1244 }
1245
1246 char LoopAccessAnalysis::ID = 0;
1247 static const char laa_name[] = "Loop Access Analysis";
1248 #define LAA_NAME "loop-accesses"
1249
1250 INITIALIZE_PASS_BEGIN(LoopAccessAnalysis, LAA_NAME, laa_name, false, true)
1251 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
1252 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
1253 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1254 INITIALIZE_PASS_END(LoopAccessAnalysis, LAA_NAME, laa_name, false, true)
1255
1256 namespace llvm {
1257   Pass *createLAAPass() {
1258     return new LoopAccessAnalysis();
1259   }
1260 }