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/TargetLibraryInfo.h"
  19 #include "llvm/Analysis/ValueTracking.h"
  20 #include "llvm/IR/DiagnosticInfo.h"
  21 #include "llvm/IR/Dominators.h"
  22 #include "llvm/IR/IRBuilder.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Support/raw_ostream.h"
  25 #include "llvm/Analysis/VectorUtils.h"
  26 using namespace llvm;
  27
  28 #define DEBUG_TYPE "loop-accesses"
  29
  30 static cl::opt<unsigned, true>
  31 VectorizationFactor("force-vector-width", cl::Hidden,
  32                     cl::desc("Sets the SIMD width. Zero is autoselect."),
  33                     cl::location(VectorizerParams::VectorizationFactor));
  34 unsigned VectorizerParams::VectorizationFactor;
  35
  36 static cl::opt<unsigned, true>
  37 VectorizationInterleave("force-vector-interleave", cl::Hidden,
  38                         cl::desc("Sets the vectorization interleave count. "
  39                                  "Zero is autoselect."),
  40                         cl::location(
  41                             VectorizerParams::VectorizationInterleave));
  42 unsigned VectorizerParams::VectorizationInterleave;
  43
  44 static cl::opt<unsigned, true> RuntimeMemoryCheckThreshold(
  45     "runtime-memory-check-threshold", cl::Hidden,
  46     cl::desc("When performing memory disambiguation checks at runtime do not "
  47              "generate more than this number of comparisons (default = 8)."),
  48     cl::location(VectorizerParams::RuntimeMemoryCheckThreshold), cl::init(8));
  49 unsigned VectorizerParams::RuntimeMemoryCheckThreshold;
  50
  51 /// \brief The maximum iterations used to merge memory checks
  52 static cl::opt<unsigned> MemoryCheckMergeThreshold(
  53     "memory-check-merge-threshold", cl::Hidden,
  54     cl::desc("Maximum number of comparisons done when trying to merge "
  55              "runtime memory checks. (default = 100)"),
  56     cl::init(100));
  57
  58 /// Maximum SIMD width.
  59 const unsigned VectorizerParams::MaxVectorWidth = 64;
  60
  61 /// \brief We collect interesting dependences up to this threshold.
  62 static cl::opt<unsigned> MaxInterestingDependence(
  63     "max-interesting-dependences", cl::Hidden,
  64     cl::desc("Maximum number of interesting dependences collected by "
  65              "loop-access analysis (default = 100)"),
  66     cl::init(100));
  67
  68 bool VectorizerParams::isInterleaveForced() {
  69   return ::VectorizationInterleave.getNumOccurrences() > 0;
  70 }
  71
  72 void LoopAccessReport::emitAnalysis(const LoopAccessReport &Message,
  73                                     const Function *TheFunction,
  74                                     const Loop *TheLoop,
  75                                     const char *PassName) {
  76   DebugLoc DL = TheLoop->getStartLoc();
  77   if (const Instruction *I = Message.getInstr())
  78     DL = I->getDebugLoc();
  79   emitOptimizationRemarkAnalysis(TheFunction->getContext(), PassName,
  80                                  *TheFunction, DL, Message.str());
  81 }
  82
  83 Value *llvm::stripIntegerCast(Value *V) {
  84   if (CastInst *CI = dyn_cast<CastInst>(V))
  85     if (CI->getOperand(0)->getType()->isIntegerTy())
  86       return CI->getOperand(0);
  87   return V;
  88 }
  89
  90 const SCEV *llvm::replaceSymbolicStrideSCEV(ScalarEvolution *SE,
  91                                             const ValueToValueMap &PtrToStride,
  92                                             Value *Ptr, Value *OrigPtr) {
  93
  94   const SCEV *OrigSCEV = SE->getSCEV(Ptr);
  95
  96   // If there is an entry in the map return the SCEV of the pointer with the
  97   // symbolic stride replaced by one.
  98   ValueToValueMap::const_iterator SI =
  99       PtrToStride.find(OrigPtr ? OrigPtr : Ptr);
 100   if (SI != PtrToStride.end()) {
 101     Value *StrideVal = SI->second;
 102
 103     // Strip casts.
 104     StrideVal = stripIntegerCast(StrideVal);
 105
 106     // Replace symbolic stride by one.
 107     Value *One = ConstantInt::get(StrideVal->getType(), 1);
 108     ValueToValueMap RewriteMap;
 109     RewriteMap[StrideVal] = One;
 110
 111     const SCEV *ByOne =
 112         SCEVParameterRewriter::rewrite(OrigSCEV, *SE, RewriteMap, true);
 113     DEBUG(dbgs() << "LAA: Replacing SCEV: " << *OrigSCEV << " by: " << *ByOne
 114                  << "\n");
 115     return ByOne;
 116   }
 117
 118   // Otherwise, just return the SCEV of the original pointer.
 119   return SE->getSCEV(Ptr);
 120 }
 121
 122 void LoopAccessInfo::RuntimePointerCheck::insert(
 123     Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId, unsigned ASId,
 124     const ValueToValueMap &Strides) {
 125   // Get the stride replaced scev.
 126   const SCEV *Sc = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
 127   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
 128   assert(AR && "Invalid addrec expression");
 129   const SCEV *Ex = SE->getBackedgeTakenCount(Lp);
 130   const SCEV *ScEnd = AR->evaluateAtIteration(Ex, *SE);
 131   Pointers.push_back(Ptr);
 132   Starts.push_back(AR->getStart());
 133   Ends.push_back(ScEnd);
 134   IsWritePtr.push_back(WritePtr);
 135   DependencySetId.push_back(DepSetId);
 136   AliasSetId.push_back(ASId);
 137   Exprs.push_back(Sc);
 138 }
 139
 140 bool LoopAccessInfo::RuntimePointerCheck::needsChecking(
 141     const CheckingPtrGroup &M, const CheckingPtrGroup &N,
 142     const SmallVectorImpl<int> *PtrPartition) const {
 143   for (unsigned I = 0, EI = M.Members.size(); EI != I; ++I)
 144     for (unsigned J = 0, EJ = N.Members.size(); EJ != J; ++J)
 145       if (needsChecking(M.Members[I], N.Members[J], PtrPartition))
 146         return true;
 147   return false;
 148 }
 149
 150 /// Compare \p I and \p J and return the minimum.
 151 /// Return nullptr in case we couldn't find an answer.
 152 static const SCEV *getMinFromExprs(const SCEV *I, const SCEV *J,
 153                                    ScalarEvolution *SE) {
 154   const SCEV *Diff = SE->getMinusSCEV(J, I);
 155   const SCEVConstant *C = dyn_cast<const SCEVConstant>(Diff);
 156
 157   if (!C)
 158     return nullptr;
 159   if (C->getValue()->isNegative())
 160     return J;
 161   return I;
 162 }
 163
 164 bool LoopAccessInfo::RuntimePointerCheck::CheckingPtrGroup::addPointer(
 165     unsigned Index) {
 166   // Compare the starts and ends with the known minimum and maximum
 167   // of this set. We need to know how we compare against the min/max
 168   // of the set in order to be able to emit memchecks.
 169   const SCEV *Min0 = getMinFromExprs(RtCheck.Starts[Index], Low, RtCheck.SE);
 170   if (!Min0)
 171     return false;
 172
 173   const SCEV *Min1 = getMinFromExprs(RtCheck.Ends[Index], High, RtCheck.SE);
 174   if (!Min1)
 175     return false;
 176
 177   // Update the low bound  expression if we've found a new min value.
 178   if (Min0 == RtCheck.Starts[Index])
 179     Low = RtCheck.Starts[Index];
 180
 181   // Update the high bound expression if we've found a new max value.
 182   if (Min1 != RtCheck.Ends[Index])
 183     High = RtCheck.Ends[Index];
 184
 185   Members.push_back(Index);
 186   return true;
 187 }
 188
 189 void LoopAccessInfo::RuntimePointerCheck::groupChecks(
 190     MemoryDepChecker::DepCandidates &DepCands,
 191     bool UseDependencies) {
 192   // We build the groups from dependency candidates equivalence classes
 193   // because:
 194   //    - We know that pointers in the same equivalence class share
 195   //      the same underlying object and therefore there is a chance
 196   //      that we can compare pointers
 197   //    - We wouldn't be able to merge two pointers for which we need
 198   //      to emit a memcheck. The classes in DepCands are already
 199   //      conveniently built such that no two pointers in the same
 200   //      class need checking against each other.
 201
 202   // We use the following (greedy) algorithm to construct the groups
 203   // For every pointer in the equivalence class:
 204   //   For each existing group:
 205   //   - if the difference between this pointer and the min/max bounds
 206   //     of the group is a constant, then make the pointer part of the
 207   //     group and update the min/max bounds of that group as required.
 208
 209   CheckingGroups.clear();
 210
 211   // If we don't have the dependency partitions, construct a new
 212   // checking pointer group for each pointer.
 213   if (!UseDependencies) {
 214     for (unsigned I = 0; I < Pointers.size(); ++I)
 215       CheckingGroups.push_back(CheckingPtrGroup(I, *this));
 216     return;
 217   }
 218
 219   unsigned TotalComparisons = 0;
 220
 221   DenseMap<Value *, unsigned> PositionMap;
 222   for (unsigned Pointer = 0; Pointer < Pointers.size(); ++Pointer)
 223     PositionMap[Pointers[Pointer]] = Pointer;
 224
 225   // Go through all equivalence classes, get the the "pointer check groups"
 226   // and add them to the overall solution.
 227   for (auto DI = DepCands.begin(), DE = DepCands.end(); DI != DE; ++DI) {
 228     if (!DI->isLeader())
 229       continue;
 230
 231     SmallVector<CheckingPtrGroup, 2> Groups;
 232
 233     for (auto MI = DepCands.member_begin(DI), ME = DepCands.member_end();
 234          MI != ME; ++MI) {
 235       unsigned Pointer = PositionMap[MI->getPointer()];
 236       bool Merged = false;
 237
 238       // Go through all the existing sets and see if we can find one
 239       // which can include this pointer.
 240       for (CheckingPtrGroup &Group : Groups) {
 241         // Don't perform more than a certain amount of comparisons.
 242         // This should limit the cost of grouping the pointers to something
 243         // reasonable.  If we do end up hitting this threshold, the algorithm
 244         // will create separate groups for all remaining pointers.
 245         if (TotalComparisons > MemoryCheckMergeThreshold)
 246           break;
 247
 248         TotalComparisons++;
 249
 250         if (Group.addPointer(Pointer)) {
 251           Merged = true;
 252           break;
 253         }
 254       }
 255
 256       if (!Merged)
 257         // We couldn't add this pointer to any existing set or the threshold
 258         // for the number of comparisons has been reached. Create a new group
 259         // to hold the current pointer.
 260         Groups.push_back(CheckingPtrGroup(Pointer, *this));
 261     }
 262
 263     // We've computed the grouped checks for this partition.
 264     // Save the results and continue with the next one.
 265     std::copy(Groups.begin(), Groups.end(), std::back_inserter(CheckingGroups));
 266   }
 267 }
 268
 269 bool LoopAccessInfo::RuntimePointerCheck::needsChecking(
 270     unsigned I, unsigned J, const SmallVectorImpl<int> *PtrPartition) const {
 271   // No need to check if two readonly pointers intersect.
 272   if (!IsWritePtr[I] && !IsWritePtr[J])
 273     return false;
 274
 275   // Only need to check pointers between two different dependency sets.
 276   if (DependencySetId[I] == DependencySetId[J])
 277     return false;
 278
 279   // Only need to check pointers in the same alias set.
 280   if (AliasSetId[I] != AliasSetId[J])
 281     return false;
 282
 283   // If PtrPartition is set omit checks between pointers of the same partition.
 284   // Partition number -1 means that the pointer is used in multiple partitions.
 285   // In this case we can't omit the check.
 286   if (PtrPartition && (*PtrPartition)[I] != -1 &&
 287       (*PtrPartition)[I] == (*PtrPartition)[J])
 288     return false;
 289
 290   return true;
 291 }
 292
 293 void LoopAccessInfo::RuntimePointerCheck::print(
 294     raw_ostream &OS, unsigned Depth,
 295     const SmallVectorImpl<int> *PtrPartition) const {
 296
 297   OS.indent(Depth) << "Run-time memory checks:\n";
 298
 299   unsigned N = 0;
 300   for (unsigned I = 0; I < CheckingGroups.size(); ++I)
 301     for (unsigned J = I + 1; J < CheckingGroups.size(); ++J)
 302       if (needsChecking(CheckingGroups[I], CheckingGroups[J], PtrPartition)) {
 303         OS.indent(Depth) << "Check " << N++ << ":\n";
 304         OS.indent(Depth + 2) << "Comparing group " << I << ":\n";
 305
 306         for (unsigned K = 0; K < CheckingGroups[I].Members.size(); ++K) {
 307           OS.indent(Depth + 2) << *Pointers[CheckingGroups[I].Members[K]]
 308                                << "\n";
 309           if (PtrPartition)
 310             OS << " (Partition: "
 311                << (*PtrPartition)[CheckingGroups[I].Members[K]] << ")"
 312                << "\n";
 313         }
 314
 315         OS.indent(Depth + 2) << "Against group " << J << ":\n";
 316
 317         for (unsigned K = 0; K < CheckingGroups[J].Members.size(); ++K) {
 318           OS.indent(Depth + 2) << *Pointers[CheckingGroups[J].Members[K]]
 319                                << "\n";
 320           if (PtrPartition)
 321             OS << " (Partition: "
 322                << (*PtrPartition)[CheckingGroups[J].Members[K]] << ")"
 323                << "\n";
 324         }
 325       }
 326
 327   OS.indent(Depth) << "Grouped accesses:\n";
 328   for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
 329     OS.indent(Depth + 2) << "Group " << I << ":\n";
 330     OS.indent(Depth + 4) << "(Low: " << *CheckingGroups[I].Low
 331                          << " High: " << *CheckingGroups[I].High << ")\n";
 332     for (unsigned J = 0; J < CheckingGroups[I].Members.size(); ++J) {
 333       OS.indent(Depth + 6) << "Member: " << *Exprs[CheckingGroups[I].Members[J]]
 334                            << "\n";
 335     }
 336   }
 337 }
 338
 339 unsigned LoopAccessInfo::RuntimePointerCheck::getNumberOfChecks(
 340     const SmallVectorImpl<int> *PtrPartition) const {
 341
 342   unsigned NumPartitions = CheckingGroups.size();
 343   unsigned CheckCount = 0;
 344
 345   for (unsigned I = 0; I < NumPartitions; ++I)
 346     for (unsigned J = I + 1; J < NumPartitions; ++J)
 347       if (needsChecking(CheckingGroups[I], CheckingGroups[J], PtrPartition))
 348         CheckCount++;
 349   return CheckCount;
 350 }
 351
 352 bool LoopAccessInfo::RuntimePointerCheck::needsAnyChecking(
 353     const SmallVectorImpl<int> *PtrPartition) const {
 354   unsigned NumPointers = Pointers.size();
 355
 356   for (unsigned I = 0; I < NumPointers; ++I)
 357     for (unsigned J = I + 1; J < NumPointers; ++J)
 358       if (needsChecking(I, J, PtrPartition))
 359         return true;
 360   return false;
 361 }
 362
 363 namespace {
 364 /// \brief Analyses memory accesses in a loop.
 365 ///
 366 /// Checks whether run time pointer checks are needed and builds sets for data
 367 /// dependence checking.
 368 class AccessAnalysis {
 369 public:
 370   /// \brief Read or write access location.
 371   typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
 372   typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet;
 373
 374   AccessAnalysis(const DataLayout &Dl, AliasAnalysis *AA, LoopInfo *LI,
 375                  MemoryDepChecker::DepCandidates &DA)
 376       : DL(Dl), AST(*AA), LI(LI), DepCands(DA), IsRTCheckNeeded(false) {}
 377
 378   /// \brief Register a load  and whether it is only read from.
 379   void addLoad(MemoryLocation &Loc, bool IsReadOnly) {
 380     Value *Ptr = const_cast<Value*>(Loc.Ptr);
 381     AST.add(Ptr, MemoryLocation::UnknownSize, Loc.AATags);
 382     Accesses.insert(MemAccessInfo(Ptr, false));
 383     if (IsReadOnly)
 384       ReadOnlyPtr.insert(Ptr);
 385   }
 386
 387   /// \brief Register a store.
 388   void addStore(MemoryLocation &Loc) {
 389     Value *Ptr = const_cast<Value*>(Loc.Ptr);
 390     AST.add(Ptr, MemoryLocation::UnknownSize, Loc.AATags);
 391     Accesses.insert(MemAccessInfo(Ptr, true));
 392   }
 393
 394   /// \brief Check whether we can check the pointers at runtime for
 395   /// non-intersection. Returns true when we have 0 pointers
 396   /// (a check on 0 pointers for non-intersection will always return true).
 397   bool canCheckPtrAtRT(LoopAccessInfo::RuntimePointerCheck &RtCheck,
 398                        bool &NeedRTCheck, ScalarEvolution *SE, Loop *TheLoop,
 399                        const ValueToValueMap &Strides,
 400                        bool ShouldCheckStride = false);
 401
 402   /// \brief Goes over all memory accesses, checks whether a RT check is needed
 403   /// and builds sets of dependent accesses.
 404   void buildDependenceSets() {
 405     processMemAccesses();
 406   }
 407
 408   bool isRTCheckNeeded() { return IsRTCheckNeeded; }
 409
 410   bool isDependencyCheckNeeded() { return !CheckDeps.empty(); }
 411
 412   /// We decided that no dependence analysis would be used.  Reset the state.
 413   void resetDepChecks(MemoryDepChecker &DepChecker) {
 414     CheckDeps.clear();
 415     DepChecker.clearInterestingDependences();
 416   }
 417
 418   MemAccessInfoSet &getDependenciesToCheck() { return CheckDeps; }
 419
 420 private:
 421   typedef SetVector<MemAccessInfo> PtrAccessSet;
 422
 423   /// \brief Go over all memory access and check whether runtime pointer checks
 424   /// are needed /// and build sets of dependency check candidates.
 425   void processMemAccesses();
 426
 427   /// Set of all accesses.
 428   PtrAccessSet Accesses;
 429
 430   const DataLayout &DL;
 431
 432   /// Set of accesses that need a further dependence check.
 433   MemAccessInfoSet CheckDeps;
 434
 435   /// Set of pointers that are read only.
 436   SmallPtrSet<Value*, 16> ReadOnlyPtr;
 437
 438   /// An alias set tracker to partition the access set by underlying object and
 439   //intrinsic property (such as TBAA metadata).
 440   AliasSetTracker AST;
 441
 442   LoopInfo *LI;
 443
 444   /// Sets of potentially dependent accesses - members of one set share an
 445   /// underlying pointer. The set "CheckDeps" identfies which sets really need a
 446   /// dependence check.
 447   MemoryDepChecker::DepCandidates &DepCands;
 448
 449   bool IsRTCheckNeeded;
 450 };
 451
 452 } // end anonymous namespace
 453
 454 /// \brief Check whether a pointer can participate in a runtime bounds check.
 455 static bool hasComputableBounds(ScalarEvolution *SE,
 456                                 const ValueToValueMap &Strides, Value *Ptr) {
 457   const SCEV *PtrScev = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
 458   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
 459   if (!AR)
 460     return false;
 461
 462   return AR->isAffine();
 463 }
 464
 465 bool AccessAnalysis::canCheckPtrAtRT(
 466     LoopAccessInfo::RuntimePointerCheck &RtCheck, bool &NeedRTCheck,
 467     ScalarEvolution *SE, Loop *TheLoop, const ValueToValueMap &StridesMap,
 468     bool ShouldCheckStride) {
 469   // Find pointers with computable bounds. We are going to use this information
 470   // to place a runtime bound check.
 471   bool CanDoRT = true;
 472
 473   NeedRTCheck = false;
 474   if (!IsRTCheckNeeded) return true;
 475
 476   bool IsDepCheckNeeded = isDependencyCheckNeeded();
 477
 478   // We assign a consecutive id to access from different alias sets.
 479   // Accesses between different groups doesn't need to be checked.
 480   unsigned ASId = 1;
 481   for (auto &AS : AST) {
 482     int NumReadPtrChecks = 0;
 483     int NumWritePtrChecks = 0;
 484
 485     // We assign consecutive id to access from different dependence sets.
 486     // Accesses within the same set don't need a runtime check.
 487     unsigned RunningDepId = 1;
 488     DenseMap<Value *, unsigned> DepSetId;
 489
 490     for (auto A : AS) {
 491       Value *Ptr = A.getValue();
 492       bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true));
 493       MemAccessInfo Access(Ptr, IsWrite);
 494
 495       if (IsWrite)
 496         ++NumWritePtrChecks;
 497       else
 498         ++NumReadPtrChecks;
 499
 500       if (hasComputableBounds(SE, StridesMap, Ptr) &&
 501           // When we run after a failing dependency check we have to make sure
 502           // we don't have wrapping pointers.
 503           (!ShouldCheckStride ||
 504            isStridedPtr(SE, Ptr, TheLoop, StridesMap) == 1)) {
 505         // The id of the dependence set.
 506         unsigned DepId;
 507
 508         if (IsDepCheckNeeded) {
 509           Value *Leader = DepCands.getLeaderValue(Access).getPointer();
 510           unsigned &LeaderId = DepSetId[Leader];
 511           if (!LeaderId)
 512             LeaderId = RunningDepId++;
 513           DepId = LeaderId;
 514         } else
 515           // Each access has its own dependence set.
 516           DepId = RunningDepId++;
 517
 518         RtCheck.insert(TheLoop, Ptr, IsWrite, DepId, ASId, StridesMap);
 519
 520         DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
 521       } else {
 522         DEBUG(dbgs() << "LAA: Can't find bounds for ptr:" << *Ptr << '\n');
 523         CanDoRT = false;
 524       }
 525     }
 526
 527     // If we have at least two writes or one write and a read then we need to
 528     // check them.  But there is no need to checks if there is only one
 529     // dependence set for this alias set.
 530     //
 531     // Note that this function computes CanDoRT and NeedRTCheck independently.
 532     // For example CanDoRT=false, NeedRTCheck=false means that we have a pointer
 533     // for which we couldn't find the bounds but we don't actually need to emit
 534     // any checks so it does not matter.
 535     if (!(IsDepCheckNeeded && CanDoRT && RunningDepId == 2))
 536       NeedRTCheck |= (NumWritePtrChecks >= 2 || (NumReadPtrChecks >= 1 &&
 537                                                  NumWritePtrChecks >= 1));
 538
 539     ++ASId;
 540   }
 541
 542   // If the pointers that we would use for the bounds comparison have different
 543   // address spaces, assume the values aren't directly comparable, so we can't
 544   // use them for the runtime check. We also have to assume they could
 545   // overlap. In the future there should be metadata for whether address spaces
 546   // are disjoint.
 547   unsigned NumPointers = RtCheck.Pointers.size();
 548   for (unsigned i = 0; i < NumPointers; ++i) {
 549     for (unsigned j = i + 1; j < NumPointers; ++j) {
 550       // Only need to check pointers between two different dependency sets.
 551       if (RtCheck.DependencySetId[i] == RtCheck.DependencySetId[j])
 552        continue;
 553       // Only need to check pointers in the same alias set.
 554       if (RtCheck.AliasSetId[i] != RtCheck.AliasSetId[j])
 555         continue;
 556
 557       Value *PtrI = RtCheck.Pointers[i];
 558       Value *PtrJ = RtCheck.Pointers[j];
 559
 560       unsigned ASi = PtrI->getType()->getPointerAddressSpace();
 561       unsigned ASj = PtrJ->getType()->getPointerAddressSpace();
 562       if (ASi != ASj) {
 563         DEBUG(dbgs() << "LAA: Runtime check would require comparison between"
 564                        " different address spaces\n");
 565         return false;
 566       }
 567     }
 568   }
 569
 570   if (NeedRTCheck && CanDoRT)
 571     RtCheck.groupChecks(DepCands, IsDepCheckNeeded);
 572
 573   return CanDoRT;
 574 }
 575
 576 void AccessAnalysis::processMemAccesses() {
 577   // We process the set twice: first we process read-write pointers, last we
 578   // process read-only pointers. This allows us to skip dependence tests for
 579   // read-only pointers.
 580
 581   DEBUG(dbgs() << "LAA: Processing memory accesses...\n");
 582   DEBUG(dbgs() << "  AST: "; AST.dump());
 583   DEBUG(dbgs() << "LAA:   Accesses(" << Accesses.size() << "):\n");
 584   DEBUG({
 585     for (auto A : Accesses)
 586       dbgs() << "\t" << *A.getPointer() << " (" <<
 587                 (A.getInt() ? "write" : (ReadOnlyPtr.count(A.getPointer()) ?
 588                                          "read-only" : "read")) << ")\n";
 589   });
 590
 591   // The AliasSetTracker has nicely partitioned our pointers by metadata
 592   // compatibility and potential for underlying-object overlap. As a result, we
 593   // only need to check for potential pointer dependencies within each alias
 594   // set.
 595   for (auto &AS : AST) {
 596     // Note that both the alias-set tracker and the alias sets themselves used
 597     // linked lists internally and so the iteration order here is deterministic
 598     // (matching the original instruction order within each set).
 599
 600     bool SetHasWrite = false;
 601
 602     // Map of pointers to last access encountered.
 603     typedef DenseMap<Value*, MemAccessInfo> UnderlyingObjToAccessMap;
 604     UnderlyingObjToAccessMap ObjToLastAccess;
 605
 606     // Set of access to check after all writes have been processed.
 607     PtrAccessSet DeferredAccesses;
 608
 609     // Iterate over each alias set twice, once to process read/write pointers,
 610     // and then to process read-only pointers.
 611     for (int SetIteration = 0; SetIteration < 2; ++SetIteration) {
 612       bool UseDeferred = SetIteration > 0;
 613       PtrAccessSet &S = UseDeferred ? DeferredAccesses : Accesses;
 614
 615       for (auto AV : AS) {
 616         Value *Ptr = AV.getValue();
 617
 618         // For a single memory access in AliasSetTracker, Accesses may contain
 619         // both read and write, and they both need to be handled for CheckDeps.
 620         for (auto AC : S) {
 621           if (AC.getPointer() != Ptr)
 622             continue;
 623
 624           bool IsWrite = AC.getInt();
 625
 626           // If we're using the deferred access set, then it contains only
 627           // reads.
 628           bool IsReadOnlyPtr = ReadOnlyPtr.count(Ptr) && !IsWrite;
 629           if (UseDeferred && !IsReadOnlyPtr)
 630             continue;
 631           // Otherwise, the pointer must be in the PtrAccessSet, either as a
 632           // read or a write.
 633           assert(((IsReadOnlyPtr && UseDeferred) || IsWrite ||
 634                   S.count(MemAccessInfo(Ptr, false))) &&
 635                  "Alias-set pointer not in the access set?");
 636
 637           MemAccessInfo Access(Ptr, IsWrite);
 638           DepCands.insert(Access);
 639
 640           // Memorize read-only pointers for later processing and skip them in
 641           // the first round (they need to be checked after we have seen all
 642           // write pointers). Note: we also mark pointer that are not
 643           // consecutive as "read-only" pointers (so that we check
 644           // "a[b[i]] +="). Hence, we need the second check for "!IsWrite".
 645           if (!UseDeferred && IsReadOnlyPtr) {
 646             DeferredAccesses.insert(Access);
 647             continue;
 648           }
 649
 650           // If this is a write - check other reads and writes for conflicts. If
 651           // this is a read only check other writes for conflicts (but only if
 652           // there is no other write to the ptr - this is an optimization to
 653           // catch "a[i] = a[i] + " without having to do a dependence check).
 654           if ((IsWrite || IsReadOnlyPtr) && SetHasWrite) {
 655             CheckDeps.insert(Access);
 656             IsRTCheckNeeded = true;
 657           }
 658
 659           if (IsWrite)
 660             SetHasWrite = true;
 661
 662           // Create sets of pointers connected by a shared alias set and
 663           // underlying object.
 664           typedef SmallVector<Value *, 16> ValueVector;
 665           ValueVector TempObjects;
 666
 667           GetUnderlyingObjects(Ptr, TempObjects, DL, LI);
 668           DEBUG(dbgs() << "Underlying objects for pointer " << *Ptr << "\n");
 669           for (Value *UnderlyingObj : TempObjects) {
 670             UnderlyingObjToAccessMap::iterator Prev =
 671                 ObjToLastAccess.find(UnderlyingObj);
 672             if (Prev != ObjToLastAccess.end())
 673               DepCands.unionSets(Access, Prev->second);
 674
 675             ObjToLastAccess[UnderlyingObj] = Access;
 676             DEBUG(dbgs() << "  " << *UnderlyingObj << "\n");
 677           }
 678         }
 679       }
 680     }
 681   }
 682 }
 683
 684 static bool isInBoundsGep(Value *Ptr) {
 685   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr))
 686     return GEP->isInBounds();
 687   return false;
 688 }
 689
 690 /// \brief Return true if an AddRec pointer \p Ptr is unsigned non-wrapping,
 691 /// i.e. monotonically increasing/decreasing.
 692 static bool isNoWrapAddRec(Value *Ptr, const SCEVAddRecExpr *AR,
 693                            ScalarEvolution *SE, const Loop *L) {
 694   // FIXME: This should probably only return true for NUW.
 695   if (AR->getNoWrapFlags(SCEV::NoWrapMask))
 696     return true;
 697
 698   // Scalar evolution does not propagate the non-wrapping flags to values that
 699   // are derived from a non-wrapping induction variable because non-wrapping
 700   // could be flow-sensitive.
 701   //
 702   // Look through the potentially overflowing instruction to try to prove
 703   // non-wrapping for the *specific* value of Ptr.
 704
 705   // The arithmetic implied by an inbounds GEP can't overflow.
 706   auto *GEP = dyn_cast<GetElementPtrInst>(Ptr);
 707   if (!GEP || !GEP->isInBounds())
 708     return false;
 709
 710   // Make sure there is only one non-const index and analyze that.
 711   Value *NonConstIndex = nullptr;
 712   for (auto Index = GEP->idx_begin(); Index != GEP->idx_end(); ++Index)
 713     if (!isa<ConstantInt>(*Index)) {
 714       if (NonConstIndex)
 715         return false;
 716       NonConstIndex = *Index;
 717     }
 718   if (!NonConstIndex)
 719     // The recurrence is on the pointer, ignore for now.
 720     return false;
 721
 722   // The index in GEP is signed.  It is non-wrapping if it's derived from a NSW
 723   // AddRec using a NSW operation.
 724   if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(NonConstIndex))
 725     if (OBO->hasNoSignedWrap() &&
 726         // Assume constant for other the operand so that the AddRec can be
 727         // easily found.
 728         isa<ConstantInt>(OBO->getOperand(1))) {
 729       auto *OpScev = SE->getSCEV(OBO->getOperand(0));
 730
 731       if (auto *OpAR = dyn_cast<SCEVAddRecExpr>(OpScev))
 732         return OpAR->getLoop() == L && OpAR->getNoWrapFlags(SCEV::FlagNSW);
 733     }
 734
 735   return false;
 736 }
 737
 738 /// \brief Check whether the access through \p Ptr has a constant stride.
 739 int llvm::isStridedPtr(ScalarEvolution *SE, Value *Ptr, const Loop *Lp,
 740                        const ValueToValueMap &StridesMap) {
 741   const Type *Ty = Ptr->getType();
 742   assert(Ty->isPointerTy() && "Unexpected non-ptr");
 743
 744   // Make sure that the pointer does not point to aggregate types.
 745   const PointerType *PtrTy = cast<PointerType>(Ty);
 746   if (PtrTy->getElementType()->isAggregateType()) {
 747     DEBUG(dbgs() << "LAA: Bad stride - Not a pointer to a scalar type"
 748           << *Ptr << "\n");
 749     return 0;
 750   }
 751
 752   const SCEV *PtrScev = replaceSymbolicStrideSCEV(SE, StridesMap, Ptr);
 753
 754   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
 755   if (!AR) {
 756     DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer "
 757           << *Ptr << " SCEV: " << *PtrScev << "\n");
 758     return 0;
 759   }
 760
 761   // The accesss function must stride over the innermost loop.
 762   if (Lp != AR->getLoop()) {
 763     DEBUG(dbgs() << "LAA: Bad stride - Not striding over innermost loop " <<
 764           *Ptr << " SCEV: " << *PtrScev << "\n");
 765   }
 766
 767   // The address calculation must not wrap. Otherwise, a dependence could be
 768   // inverted.
 769   // An inbounds getelementptr that is a AddRec with a unit stride
 770   // cannot wrap per definition. The unit stride requirement is checked later.
 771   // An getelementptr without an inbounds attribute and unit stride would have
 772   // to access the pointer value "0" which is undefined behavior in address
 773   // space 0, therefore we can also vectorize this case.
 774   bool IsInBoundsGEP = isInBoundsGep(Ptr);
 775   bool IsNoWrapAddRec = isNoWrapAddRec(Ptr, AR, SE, Lp);
 776   bool IsInAddressSpaceZero = PtrTy->getAddressSpace() == 0;
 777   if (!IsNoWrapAddRec && !IsInBoundsGEP && !IsInAddressSpaceZero) {
 778     DEBUG(dbgs() << "LAA: Bad stride - Pointer may wrap in the address space "
 779           << *Ptr << " SCEV: " << *PtrScev << "\n");
 780     return 0;
 781   }
 782
 783   // Check the step is constant.
 784   const SCEV *Step = AR->getStepRecurrence(*SE);
 785
 786   // Calculate the pointer stride and check if it is consecutive.
 787   const SCEVConstant *C = dyn_cast<SCEVConstant>(Step);
 788   if (!C) {
 789     DEBUG(dbgs() << "LAA: Bad stride - Not a constant strided " << *Ptr <<
 790           " SCEV: " << *PtrScev << "\n");
 791     return 0;
 792   }
 793
 794   auto &DL = Lp->getHeader()->getModule()->getDataLayout();
 795   int64_t Size = DL.getTypeAllocSize(PtrTy->getElementType());
 796   const APInt &APStepVal = C->getValue()->getValue();
 797
 798   // Huge step value - give up.
 799   if (APStepVal.getBitWidth() > 64)
 800     return 0;
 801
 802   int64_t StepVal = APStepVal.getSExtValue();
 803
 804   // Strided access.
 805   int64_t Stride = StepVal / Size;
 806   int64_t Rem = StepVal % Size;
 807   if (Rem)
 808     return 0;
 809
 810   // If the SCEV could wrap but we have an inbounds gep with a unit stride we
 811   // know we can't "wrap around the address space". In case of address space
 812   // zero we know that this won't happen without triggering undefined behavior.
 813   if (!IsNoWrapAddRec && (IsInBoundsGEP || IsInAddressSpaceZero) &&
 814       Stride != 1 && Stride != -1)
 815     return 0;
 816
 817   return Stride;
 818 }
 819
 820 bool MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) {
 821   switch (Type) {
 822   case NoDep:
 823   case Forward:
 824   case BackwardVectorizable:
 825     return true;
 826
 827   case Unknown:
 828   case ForwardButPreventsForwarding:
 829   case Backward:
 830   case BackwardVectorizableButPreventsForwarding:
 831     return false;
 832   }
 833   llvm_unreachable("unexpected DepType!");
 834 }
 835
 836 bool MemoryDepChecker::Dependence::isInterestingDependence(DepType Type) {
 837   switch (Type) {
 838   case NoDep:
 839   case Forward:
 840     return false;
 841
 842   case BackwardVectorizable:
 843   case Unknown:
 844   case ForwardButPreventsForwarding:
 845   case Backward:
 846   case BackwardVectorizableButPreventsForwarding:
 847     return true;
 848   }
 849   llvm_unreachable("unexpected DepType!");
 850 }
 851
 852 bool MemoryDepChecker::Dependence::isPossiblyBackward() const {
 853   switch (Type) {
 854   case NoDep:
 855   case Forward:
 856   case ForwardButPreventsForwarding:
 857     return false;
 858
 859   case Unknown:
 860   case BackwardVectorizable:
 861   case Backward:
 862   case BackwardVectorizableButPreventsForwarding:
 863     return true;
 864   }
 865   llvm_unreachable("unexpected DepType!");
 866 }
 867
 868 bool MemoryDepChecker::couldPreventStoreLoadForward(unsigned Distance,
 869                                                     unsigned TypeByteSize) {
 870   // If loads occur at a distance that is not a multiple of a feasible vector
 871   // factor store-load forwarding does not take place.
 872   // Positive dependences might cause troubles because vectorizing them might
 873   // prevent store-load forwarding making vectorized code run a lot slower.
 874   //   a[i] = a[i-3] ^ a[i-8];
 875   //   The stores to a[i:i+1] don't align with the stores to a[i-3:i-2] and
 876   //   hence on your typical architecture store-load forwarding does not take
 877   //   place. Vectorizing in such cases does not make sense.
 878   // Store-load forwarding distance.
 879   const unsigned NumCyclesForStoreLoadThroughMemory = 8*TypeByteSize;
 880   // Maximum vector factor.
 881   unsigned MaxVFWithoutSLForwardIssues =
 882     VectorizerParams::MaxVectorWidth * TypeByteSize;
 883   if(MaxSafeDepDistBytes < MaxVFWithoutSLForwardIssues)
 884     MaxVFWithoutSLForwardIssues = MaxSafeDepDistBytes;
 885
 886   for (unsigned vf = 2*TypeByteSize; vf <= MaxVFWithoutSLForwardIssues;
 887        vf *= 2) {
 888     if (Distance % vf && Distance / vf < NumCyclesForStoreLoadThroughMemory) {
 889       MaxVFWithoutSLForwardIssues = (vf >>=1);
 890       break;
 891     }
 892   }
 893
 894   if (MaxVFWithoutSLForwardIssues< 2*TypeByteSize) {
 895     DEBUG(dbgs() << "LAA: Distance " << Distance <<
 896           " that could cause a store-load forwarding conflict\n");
 897     return true;
 898   }
 899
 900   if (MaxVFWithoutSLForwardIssues < MaxSafeDepDistBytes &&
 901       MaxVFWithoutSLForwardIssues !=
 902       VectorizerParams::MaxVectorWidth * TypeByteSize)
 903     MaxSafeDepDistBytes = MaxVFWithoutSLForwardIssues;
 904   return false;
 905 }
 906
 907 /// \brief Check the dependence for two accesses with the same stride \p Stride.
 908 /// \p Distance is the positive distance and \p TypeByteSize is type size in
 909 /// bytes.
 910 ///
 911 /// \returns true if they are independent.
 912 static bool areStridedAccessesIndependent(unsigned Distance, unsigned Stride,
 913                                           unsigned TypeByteSize) {
 914   assert(Stride > 1 && "The stride must be greater than 1");
 915   assert(TypeByteSize > 0 && "The type size in byte must be non-zero");
 916   assert(Distance > 0 && "The distance must be non-zero");
 917
 918   // Skip if the distance is not multiple of type byte size.
 919   if (Distance % TypeByteSize)
 920     return false;
 921
 922   unsigned ScaledDist = Distance / TypeByteSize;
 923
 924   // No dependence if the scaled distance is not multiple of the stride.
 925   // E.g.
 926   //      for (i = 0; i < 1024 ; i += 4)
 927   //        A[i+2] = A[i] + 1;
 928   //
 929   // Two accesses in memory (scaled distance is 2, stride is 4):
 930   //     | A[0] |      |      |      | A[4] |      |      |      |
 931   //     |      |      | A[2] |      |      |      | A[6] |      |
 932   //
 933   // E.g.
 934   //      for (i = 0; i < 1024 ; i += 3)
 935   //        A[i+4] = A[i] + 1;
 936   //
 937   // Two accesses in memory (scaled distance is 4, stride is 3):
 938   //     | A[0] |      |      | A[3] |      |      | A[6] |      |      |
 939   //     |      |      |      |      | A[4] |      |      | A[7] |      |
 940   return ScaledDist % Stride;
 941 }
 942
 943 MemoryDepChecker::Dependence::DepType
 944 MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
 945                               const MemAccessInfo &B, unsigned BIdx,
 946                               const ValueToValueMap &Strides) {
 947   assert (AIdx < BIdx && "Must pass arguments in program order");
 948
 949   Value *APtr = A.getPointer();
 950   Value *BPtr = B.getPointer();
 951   bool AIsWrite = A.getInt();
 952   bool BIsWrite = B.getInt();
 953
 954   // Two reads are independent.
 955   if (!AIsWrite && !BIsWrite)
 956     return Dependence::NoDep;
 957
 958   // We cannot check pointers in different address spaces.
 959   if (APtr->getType()->getPointerAddressSpace() !=
 960       BPtr->getType()->getPointerAddressSpace())
 961     return Dependence::Unknown;
 962
 963   const SCEV *AScev = replaceSymbolicStrideSCEV(SE, Strides, APtr);
 964   const SCEV *BScev = replaceSymbolicStrideSCEV(SE, Strides, BPtr);
 965
 966   int StrideAPtr = isStridedPtr(SE, APtr, InnermostLoop, Strides);
 967   int StrideBPtr = isStridedPtr(SE, BPtr, InnermostLoop, Strides);
 968
 969   const SCEV *Src = AScev;
 970   const SCEV *Sink = BScev;
 971
 972   // If the induction step is negative we have to invert source and sink of the
 973   // dependence.
 974   if (StrideAPtr < 0) {
 975     //Src = BScev;
 976     //Sink = AScev;
 977     std::swap(APtr, BPtr);
 978     std::swap(Src, Sink);
 979     std::swap(AIsWrite, BIsWrite);
 980     std::swap(AIdx, BIdx);
 981     std::swap(StrideAPtr, StrideBPtr);
 982   }
 983
 984   const SCEV *Dist = SE->getMinusSCEV(Sink, Src);
 985
 986   DEBUG(dbgs() << "LAA: Src Scev: " << *Src << "Sink Scev: " << *Sink
 987         << "(Induction step: " << StrideAPtr <<  ")\n");
 988   DEBUG(dbgs() << "LAA: Distance for " << *InstMap[AIdx] << " to "
 989         << *InstMap[BIdx] << ": " << *Dist << "\n");
 990
 991   // Need consecutive accesses. We don't want to vectorize
 992   // "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in
 993   // the address space.
 994   if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){
 995     DEBUG(dbgs() << "Non-consecutive pointer access\n");
 996     return Dependence::Unknown;
 997   }
 998
 999   const SCEVConstant *C = dyn_cast<SCEVConstant>(Dist);
1000   if (!C) {
1001     DEBUG(dbgs() << "LAA: Dependence because of non-constant distance\n");
1002     ShouldRetryWithRuntimeCheck = true;
1003     return Dependence::Unknown;
1004   }
1005
1006   Type *ATy = APtr->getType()->getPointerElementType();
1007   Type *BTy = BPtr->getType()->getPointerElementType();
1008   auto &DL = InnermostLoop->getHeader()->getModule()->getDataLayout();
1009   unsigned TypeByteSize = DL.getTypeAllocSize(ATy);
1010
1011   // Negative distances are not plausible dependencies.
1012   const APInt &Val = C->getValue()->getValue();
1013   if (Val.isNegative()) {
1014     bool IsTrueDataDependence = (AIsWrite && !BIsWrite);
1015     if (IsTrueDataDependence &&
1016         (couldPreventStoreLoadForward(Val.abs().getZExtValue(), TypeByteSize) ||
1017          ATy != BTy))
1018       return Dependence::ForwardButPreventsForwarding;
1019
1020     DEBUG(dbgs() << "LAA: Dependence is negative: NoDep\n");
1021     return Dependence::Forward;
1022   }
1023
1024   // Write to the same location with the same size.
1025   // Could be improved to assert type sizes are the same (i32 == float, etc).
1026   if (Val == 0) {
1027     if (ATy == BTy)
1028       return Dependence::NoDep;
1029     DEBUG(dbgs() << "LAA: Zero dependence difference but different types\n");
1030     return Dependence::Unknown;
1031   }
1032
1033   assert(Val.isStrictlyPositive() && "Expect a positive value");
1034
1035   if (ATy != BTy) {
1036     DEBUG(dbgs() <<
1037           "LAA: ReadWrite-Write positive dependency with different types\n");
1038     return Dependence::Unknown;
1039   }
1040
1041   unsigned Distance = (unsigned) Val.getZExtValue();
1042
1043   unsigned Stride = std::abs(StrideAPtr);
1044   if (Stride > 1 &&
1045       areStridedAccessesIndependent(Distance, Stride, TypeByteSize)) {
1046     DEBUG(dbgs() << "LAA: Strided accesses are independent\n");
1047     return Dependence::NoDep;
1048   }
1049
1050   // Bail out early if passed-in parameters make vectorization not feasible.
1051   unsigned ForcedFactor = (VectorizerParams::VectorizationFactor ?
1052                            VectorizerParams::VectorizationFactor : 1);
1053   unsigned ForcedUnroll = (VectorizerParams::VectorizationInterleave ?
1054                            VectorizerParams::VectorizationInterleave : 1);
1055   // The minimum number of iterations for a vectorized/unrolled version.
1056   unsigned MinNumIter = std::max(ForcedFactor * ForcedUnroll, 2U);
1057
1058   // It's not vectorizable if the distance is smaller than the minimum distance
1059   // needed for a vectroized/unrolled version. Vectorizing one iteration in
1060   // front needs TypeByteSize * Stride. Vectorizing the last iteration needs
1061   // TypeByteSize (No need to plus the last gap distance).
1062   //
1063   // E.g. Assume one char is 1 byte in memory and one int is 4 bytes.
1064   //      foo(int *A) {
1065   //        int *B = (int *)((char *)A + 14);
1066   //        for (i = 0 ; i < 1024 ; i += 2)
1067   //          B[i] = A[i] + 1;
1068   //      }
1069   //
1070   // Two accesses in memory (stride is 2):
1071   //     | A[0] |      | A[2] |      | A[4] |      | A[6] |      |
1072   //                              | B[0] |      | B[2] |      | B[4] |
1073   //
1074   // Distance needs for vectorizing iterations except the last iteration:
1075   // 4 * 2 * (MinNumIter - 1). Distance needs for the last iteration: 4.
1076   // So the minimum distance needed is: 4 * 2 * (MinNumIter - 1) + 4.
1077   //
1078   // If MinNumIter is 2, it is vectorizable as the minimum distance needed is
1079   // 12, which is less than distance.
1080   //
1081   // If MinNumIter is 4 (Say if a user forces the vectorization factor to be 4),
1082   // the minimum distance needed is 28, which is greater than distance. It is
1083   // not safe to do vectorization.
1084   unsigned MinDistanceNeeded =
1085       TypeByteSize * Stride * (MinNumIter - 1) + TypeByteSize;
1086   if (MinDistanceNeeded > Distance) {
1087     DEBUG(dbgs() << "LAA: Failure because of positive distance " << Distance
1088                  << '\n');
1089     return Dependence::Backward;
1090   }
1091
1092   // Unsafe if the minimum distance needed is greater than max safe distance.
1093   if (MinDistanceNeeded > MaxSafeDepDistBytes) {
1094     DEBUG(dbgs() << "LAA: Failure because it needs at least "
1095                  << MinDistanceNeeded << " size in bytes");
1096     return Dependence::Backward;
1097   }
1098
1099   // Positive distance bigger than max vectorization factor.
1100   // FIXME: Should use max factor instead of max distance in bytes, which could
1101   // not handle different types.
1102   // E.g. Assume one char is 1 byte in memory and one int is 4 bytes.
1103   //      void foo (int *A, char *B) {
1104   //        for (unsigned i = 0; i < 1024; i++) {
1105   //          A[i+2] = A[i] + 1;
1106   //          B[i+2] = B[i] + 1;
1107   //        }
1108   //      }
1109   //
1110   // This case is currently unsafe according to the max safe distance. If we
1111   // analyze the two accesses on array B, the max safe dependence distance
1112   // is 2. Then we analyze the accesses on array A, the minimum distance needed
1113   // is 8, which is less than 2 and forbidden vectorization, But actually
1114   // both A and B could be vectorized by 2 iterations.
1115   MaxSafeDepDistBytes =
1116       Distance < MaxSafeDepDistBytes ? Distance : MaxSafeDepDistBytes;
1117
1118   bool IsTrueDataDependence = (!AIsWrite && BIsWrite);
1119   if (IsTrueDataDependence &&
1120       couldPreventStoreLoadForward(Distance, TypeByteSize))
1121     return Dependence::BackwardVectorizableButPreventsForwarding;
1122
1123   DEBUG(dbgs() << "LAA: Positive distance " << Val.getSExtValue()
1124                << " with max VF = "
1125                << MaxSafeDepDistBytes / (TypeByteSize * Stride) << '\n');
1126
1127   return Dependence::BackwardVectorizable;
1128 }
1129
1130 bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets,
1131                                    MemAccessInfoSet &CheckDeps,
1132                                    const ValueToValueMap &Strides) {
1133
1134   MaxSafeDepDistBytes = -1U;
1135   while (!CheckDeps.empty()) {
1136     MemAccessInfo CurAccess = *CheckDeps.begin();
1137
1138     // Get the relevant memory access set.
1139     EquivalenceClasses<MemAccessInfo>::iterator I =
1140       AccessSets.findValue(AccessSets.getLeaderValue(CurAccess));
1141
1142     // Check accesses within this set.
1143     EquivalenceClasses<MemAccessInfo>::member_iterator AI, AE;
1144     AI = AccessSets.member_begin(I), AE = AccessSets.member_end();
1145
1146     // Check every access pair.
1147     while (AI != AE) {
1148       CheckDeps.erase(*AI);
1149       EquivalenceClasses<MemAccessInfo>::member_iterator OI = std::next(AI);
1150       while (OI != AE) {
1151         // Check every accessing instruction pair in program order.
1152         for (std::vector<unsigned>::iterator I1 = Accesses[*AI].begin(),
1153              I1E = Accesses[*AI].end(); I1 != I1E; ++I1)
1154           for (std::vector<unsigned>::iterator I2 = Accesses[*OI].begin(),
1155                I2E = Accesses[*OI].end(); I2 != I2E; ++I2) {
1156             auto A = std::make_pair(&*AI, *I1);
1157             auto B = std::make_pair(&*OI, *I2);
1158
1159             assert(*I1 != *I2);
1160             if (*I1 > *I2)
1161               std::swap(A, B);
1162
1163             Dependence::DepType Type =
1164                 isDependent(*A.first, A.second, *B.first, B.second, Strides);
1165             SafeForVectorization &= Dependence::isSafeForVectorization(Type);
1166
1167             // Gather dependences unless we accumulated MaxInterestingDependence
1168             // dependences.  In that case return as soon as we find the first
1169             // unsafe dependence.  This puts a limit on this quadratic
1170             // algorithm.
1171             if (RecordInterestingDependences) {
1172               if (Dependence::isInterestingDependence(Type))
1173                 InterestingDependences.push_back(
1174                     Dependence(A.second, B.second, Type));
1175
1176               if (InterestingDependences.size() >= MaxInterestingDependence) {
1177                 RecordInterestingDependences = false;
1178                 InterestingDependences.clear();
1179                 DEBUG(dbgs() << "Too many dependences, stopped recording\n");
1180               }
1181             }
1182             if (!RecordInterestingDependences && !SafeForVectorization)
1183               return false;
1184           }
1185         ++OI;
1186       }
1187       AI++;
1188     }
1189   }
1190
1191   DEBUG(dbgs() << "Total Interesting Dependences: "
1192                << InterestingDependences.size() << "\n");
1193   return SafeForVectorization;
1194 }
1195
1196 SmallVector<Instruction *, 4>
1197 MemoryDepChecker::getInstructionsForAccess(Value *Ptr, bool isWrite) const {
1198   MemAccessInfo Access(Ptr, isWrite);
1199   auto &IndexVector = Accesses.find(Access)->second;
1200
1201   SmallVector<Instruction *, 4> Insts;
1202   std::transform(IndexVector.begin(), IndexVector.end(),
1203                  std::back_inserter(Insts),
1204                  [&](unsigned Idx) { return this->InstMap[Idx]; });
1205   return Insts;
1206 }
1207
1208 const char *MemoryDepChecker::Dependence::DepName[] = {
1209     "NoDep", "Unknown", "Forward", "ForwardButPreventsForwarding", "Backward",
1210     "BackwardVectorizable", "BackwardVectorizableButPreventsForwarding"};
1211
1212 void MemoryDepChecker::Dependence::print(
1213     raw_ostream &OS, unsigned Depth,
1214     const SmallVectorImpl<Instruction *> &Instrs) const {
1215   OS.indent(Depth) << DepName[Type] << ":\n";
1216   OS.indent(Depth + 2) << *Instrs[Source] << " -> \n";
1217   OS.indent(Depth + 2) << *Instrs[Destination] << "\n";
1218 }
1219
1220 bool LoopAccessInfo::canAnalyzeLoop() {
1221   // We need to have a loop header.
1222   DEBUG(dbgs() << "LAA: Found a loop: " <<
1223         TheLoop->getHeader()->getName() << '\n');
1224
1225     // We can only analyze innermost loops.
1226   if (!TheLoop->empty()) {
1227     DEBUG(dbgs() << "LAA: loop is not the innermost loop\n");
1228     emitAnalysis(LoopAccessReport() << "loop is not the innermost loop");
1229     return false;
1230   }
1231
1232   // We must have a single backedge.
1233   if (TheLoop->getNumBackEdges() != 1) {
1234     DEBUG(dbgs() << "LAA: loop control flow is not understood by analyzer\n");
1235     emitAnalysis(
1236         LoopAccessReport() <<
1237         "loop control flow is not understood by analyzer");
1238     return false;
1239   }
1240
1241   // We must have a single exiting block.
1242   if (!TheLoop->getExitingBlock()) {
1243     DEBUG(dbgs() << "LAA: loop control flow is not understood by analyzer\n");
1244     emitAnalysis(
1245         LoopAccessReport() <<
1246         "loop control flow is not understood by analyzer");
1247     return false;
1248   }
1249
1250   // We only handle bottom-tested loops, i.e. loop in which the condition is
1251   // checked at the end of each iteration. With that we can assume that all
1252   // instructions in the loop are executed the same number of times.
1253   if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) {
1254     DEBUG(dbgs() << "LAA: loop control flow is not understood by analyzer\n");
1255     emitAnalysis(
1256         LoopAccessReport() <<
1257         "loop control flow is not understood by analyzer");
1258     return false;
1259   }
1260
1261   // ScalarEvolution needs to be able to find the exit count.
1262   const SCEV *ExitCount = SE->getBackedgeTakenCount(TheLoop);
1263   if (ExitCount == SE->getCouldNotCompute()) {
1264     emitAnalysis(LoopAccessReport() <<
1265                  "could not determine number of loop iterations");
1266     DEBUG(dbgs() << "LAA: SCEV could not compute the loop exit count.\n");
1267     return false;
1268   }
1269
1270   return true;
1271 }
1272
1273 void LoopAccessInfo::analyzeLoop(const ValueToValueMap &Strides) {
1274
1275   typedef SmallVector<Value*, 16> ValueVector;
1276   typedef SmallPtrSet<Value*, 16> ValueSet;
1277
1278   // Holds the Load and Store *instructions*.
1279   ValueVector Loads;
1280   ValueVector Stores;
1281
1282   // Holds all the different accesses in the loop.
1283   unsigned NumReads = 0;
1284   unsigned NumReadWrites = 0;
1285
1286   PtrRtCheck.Pointers.clear();
1287   PtrRtCheck.Need = false;
1288
1289   const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel();
1290
1291   // For each block.
1292   for (Loop::block_iterator bb = TheLoop->block_begin(),
1293        be = TheLoop->block_end(); bb != be; ++bb) {
1294
1295     // Scan the BB and collect legal loads and stores.
1296     for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
1297          ++it) {
1298
1299       // If this is a load, save it. If this instruction can read from memory
1300       // but is not a load, then we quit. Notice that we don't handle function
1301       // calls that read or write.
1302       if (it->mayReadFromMemory()) {
1303         // Many math library functions read the rounding mode. We will only
1304         // vectorize a loop if it contains known function calls that don't set
1305         // the flag. Therefore, it is safe to ignore this read from memory.
1306         CallInst *Call = dyn_cast<CallInst>(it);
1307         if (Call && getIntrinsicIDForCall(Call, TLI))
1308           continue;
1309
1310         // If the function has an explicit vectorized counterpart, we can safely
1311         // assume that it can be vectorized.
1312         if (Call && !Call->isNoBuiltin() && Call->getCalledFunction() &&
1313             TLI->isFunctionVectorizable(Call->getCalledFunction()->getName()))
1314           continue;
1315
1316         LoadInst *Ld = dyn_cast<LoadInst>(it);
1317         if (!Ld || (!Ld->isSimple() && !IsAnnotatedParallel)) {
1318           emitAnalysis(LoopAccessReport(Ld)
1319                        << "read with atomic ordering or volatile read");
1320           DEBUG(dbgs() << "LAA: Found a non-simple load.\n");
1321           CanVecMem = false;
1322           return;
1323         }
1324         NumLoads++;
1325         Loads.push_back(Ld);
1326         DepChecker.addAccess(Ld);
1327         continue;
1328       }
1329
1330       // Save 'store' instructions. Abort if other instructions write to memory.
1331       if (it->mayWriteToMemory()) {
1332         StoreInst *St = dyn_cast<StoreInst>(it);
1333         if (!St) {
1334           emitAnalysis(LoopAccessReport(it) <<
1335                        "instruction cannot be vectorized");
1336           CanVecMem = false;
1337           return;
1338         }
1339         if (!St->isSimple() && !IsAnnotatedParallel) {
1340           emitAnalysis(LoopAccessReport(St)
1341                        << "write with atomic ordering or volatile write");
1342           DEBUG(dbgs() << "LAA: Found a non-simple store.\n");
1343           CanVecMem = false;
1344           return;
1345         }
1346         NumStores++;
1347         Stores.push_back(St);
1348         DepChecker.addAccess(St);
1349       }
1350     } // Next instr.
1351   } // Next block.
1352
1353   // Now we have two lists that hold the loads and the stores.
1354   // Next, we find the pointers that they use.
1355
1356   // Check if we see any stores. If there are no stores, then we don't
1357   // care if the pointers are *restrict*.
1358   if (!Stores.size()) {
1359     DEBUG(dbgs() << "LAA: Found a read-only loop!\n");
1360     CanVecMem = true;
1361     return;
1362   }
1363
1364   MemoryDepChecker::DepCandidates DependentAccesses;
1365   AccessAnalysis Accesses(TheLoop->getHeader()->getModule()->getDataLayout(),
1366                           AA, LI, DependentAccesses);
1367
1368   // Holds the analyzed pointers. We don't want to call GetUnderlyingObjects
1369   // multiple times on the same object. If the ptr is accessed twice, once
1370   // for read and once for write, it will only appear once (on the write
1371   // list). This is okay, since we are going to check for conflicts between
1372   // writes and between reads and writes, but not between reads and reads.
1373   ValueSet Seen;
1374
1375   ValueVector::iterator I, IE;
1376   for (I = Stores.begin(), IE = Stores.end(); I != IE; ++I) {
1377     StoreInst *ST = cast<StoreInst>(*I);
1378     Value* Ptr = ST->getPointerOperand();
1379     // Check for store to loop invariant address.
1380     StoreToLoopInvariantAddress |= isUniform(Ptr);
1381     // If we did *not* see this pointer before, insert it to  the read-write
1382     // list. At this phase it is only a 'write' list.
1383     if (Seen.insert(Ptr).second) {
1384       ++NumReadWrites;
1385
1386       MemoryLocation Loc = MemoryLocation::get(ST);
1387       // The TBAA metadata could have a control dependency on the predication
1388       // condition, so we cannot rely on it when determining whether or not we
1389       // need runtime pointer checks.
1390       if (blockNeedsPredication(ST->getParent(), TheLoop, DT))
1391         Loc.AATags.TBAA = nullptr;
1392
1393       Accesses.addStore(Loc);
1394     }
1395   }
1396
1397   if (IsAnnotatedParallel) {
1398     DEBUG(dbgs()
1399           << "LAA: A loop annotated parallel, ignore memory dependency "
1400           << "checks.\n");
1401     CanVecMem = true;
1402     return;
1403   }
1404
1405   for (I = Loads.begin(), IE = Loads.end(); I != IE; ++I) {
1406     LoadInst *LD = cast<LoadInst>(*I);
1407     Value* Ptr = LD->getPointerOperand();
1408     // If we did *not* see this pointer before, insert it to the
1409     // read list. If we *did* see it before, then it is already in
1410     // the read-write list. This allows us to vectorize expressions
1411     // such as A[i] += x;  Because the address of A[i] is a read-write
1412     // pointer. This only works if the index of A[i] is consecutive.
1413     // If the address of i is unknown (for example A[B[i]]) then we may
1414     // read a few words, modify, and write a few words, and some of the
1415     // words may be written to the same address.
1416     bool IsReadOnlyPtr = false;
1417     if (Seen.insert(Ptr).second || !isStridedPtr(SE, Ptr, TheLoop, Strides)) {
1418       ++NumReads;
1419       IsReadOnlyPtr = true;
1420     }
1421
1422     MemoryLocation Loc = MemoryLocation::get(LD);
1423     // The TBAA metadata could have a control dependency on the predication
1424     // condition, so we cannot rely on it when determining whether or not we
1425     // need runtime pointer checks.
1426     if (blockNeedsPredication(LD->getParent(), TheLoop, DT))
1427       Loc.AATags.TBAA = nullptr;
1428
1429     Accesses.addLoad(Loc, IsReadOnlyPtr);
1430   }
1431
1432   // If we write (or read-write) to a single destination and there are no
1433   // other reads in this loop then is it safe to vectorize.
1434   if (NumReadWrites == 1 && NumReads == 0) {
1435     DEBUG(dbgs() << "LAA: Found a write-only loop!\n");
1436     CanVecMem = true;
1437     return;
1438   }
1439
1440   // Build dependence sets and check whether we need a runtime pointer bounds
1441   // check.
1442   Accesses.buildDependenceSets();
1443
1444   // Find pointers with computable bounds. We are going to use this information
1445   // to place a runtime bound check.
1446   bool NeedRTCheck;
1447   bool CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck,
1448                                           NeedRTCheck, SE,
1449                                           TheLoop, Strides);
1450
1451   DEBUG(dbgs() << "LAA: We need to do "
1452                << PtrRtCheck.getNumberOfChecks(nullptr)
1453                << " pointer comparisons.\n");
1454
1455   // Check that we found the bounds for the pointer.
1456   if (CanDoRT)
1457     DEBUG(dbgs() << "LAA: We can perform a memory runtime check if needed.\n");
1458   else if (NeedRTCheck) {
1459     emitAnalysis(LoopAccessReport() << "cannot identify array bounds");
1460     DEBUG(dbgs() << "LAA: We can't vectorize because we can't find " <<
1461           "the array bounds.\n");
1462     PtrRtCheck.reset();
1463     CanVecMem = false;
1464     return;
1465   }
1466
1467   PtrRtCheck.Need = NeedRTCheck;
1468
1469   CanVecMem = true;
1470   if (Accesses.isDependencyCheckNeeded()) {
1471     DEBUG(dbgs() << "LAA: Checking memory dependencies\n");
1472     CanVecMem = DepChecker.areDepsSafe(
1473         DependentAccesses, Accesses.getDependenciesToCheck(), Strides);
1474     MaxSafeDepDistBytes = DepChecker.getMaxSafeDepDistBytes();
1475
1476     if (!CanVecMem && DepChecker.shouldRetryWithRuntimeCheck()) {
1477       DEBUG(dbgs() << "LAA: Retrying with memory checks\n");
1478       NeedRTCheck = true;
1479
1480       // Clear the dependency checks. We assume they are not needed.
1481       Accesses.resetDepChecks(DepChecker);
1482
1483       PtrRtCheck.reset();
1484       PtrRtCheck.Need = true;
1485
1486       CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NeedRTCheck, SE,
1487                                          TheLoop, Strides, true);
1488
1489       // Check that we found the bounds for the pointer.
1490       if (NeedRTCheck && !CanDoRT) {
1491         emitAnalysis(LoopAccessReport()
1492                      << "cannot check memory dependencies at runtime");
1493         DEBUG(dbgs() << "LAA: Can't vectorize with memory checks\n");
1494         PtrRtCheck.reset();
1495         CanVecMem = false;
1496         return;
1497       }
1498
1499       CanVecMem = true;
1500     }
1501   }
1502
1503   if (CanVecMem)
1504     DEBUG(dbgs() << "LAA: No unsafe dependent memory operations in loop.  We"
1505                  << (NeedRTCheck ? "" : " don't")
1506                  << " need a runtime memory check.\n");
1507   else {
1508     emitAnalysis(LoopAccessReport() <<
1509                  "unsafe dependent memory operations in loop");
1510     DEBUG(dbgs() << "LAA: unsafe dependent memory operations in loop\n");
1511   }
1512 }
1513
1514 bool LoopAccessInfo::blockNeedsPredication(BasicBlock *BB, Loop *TheLoop,
1515                                            DominatorTree *DT)  {
1516   assert(TheLoop->contains(BB) && "Unknown block used");
1517
1518   // Blocks that do not dominate the latch need predication.
1519   BasicBlock* Latch = TheLoop->getLoopLatch();
1520   return !DT->dominates(BB, Latch);
1521 }
1522
1523 void LoopAccessInfo::emitAnalysis(LoopAccessReport &Message) {
1524   assert(!Report && "Multiple reports generated");
1525   Report = Message;
1526 }
1527
1528 bool LoopAccessInfo::isUniform(Value *V) const {
1529   return (SE->isLoopInvariant(SE->getSCEV(V), TheLoop));
1530 }
1531
1532 // FIXME: this function is currently a duplicate of the one in
1533 // LoopVectorize.cpp.
1534 static Instruction *getFirstInst(Instruction *FirstInst, Value *V,
1535                                  Instruction *Loc) {
1536   if (FirstInst)
1537     return FirstInst;
1538   if (Instruction *I = dyn_cast<Instruction>(V))
1539     return I->getParent() == Loc->getParent() ? I : nullptr;
1540   return nullptr;
1541 }
1542
1543 std::pair<Instruction *, Instruction *> LoopAccessInfo::addRuntimeCheck(
1544     Instruction *Loc, const SmallVectorImpl<int> *PtrPartition) const {
1545   if (!PtrRtCheck.Need)
1546     return std::make_pair(nullptr, nullptr);
1547
1548   SmallVector<TrackingVH<Value>, 2> Starts;
1549   SmallVector<TrackingVH<Value>, 2> Ends;
1550
1551   LLVMContext &Ctx = Loc->getContext();
1552   SCEVExpander Exp(*SE, DL, "induction");
1553   Instruction *FirstInst = nullptr;
1554
1555   for (unsigned i = 0; i < PtrRtCheck.CheckingGroups.size(); ++i) {
1556     const RuntimePointerCheck::CheckingPtrGroup &CG =
1557         PtrRtCheck.CheckingGroups[i];
1558     Value *Ptr = PtrRtCheck.Pointers[CG.Members[0]];
1559     const SCEV *Sc = SE->getSCEV(Ptr);
1560
1561     if (SE->isLoopInvariant(Sc, TheLoop)) {
1562       DEBUG(dbgs() << "LAA: Adding RT check for a loop invariant ptr:" << *Ptr
1563                    << "\n");
1564       Starts.push_back(Ptr);
1565       Ends.push_back(Ptr);
1566     } else {
1567       unsigned AS = Ptr->getType()->getPointerAddressSpace();
1568
1569       // Use this type for pointer arithmetic.
1570       Type *PtrArithTy = Type::getInt8PtrTy(Ctx, AS);
1571       Value *Start = nullptr, *End = nullptr;
1572
1573       DEBUG(dbgs() << "LAA: Adding RT check for range:\n");
1574       Start = Exp.expandCodeFor(CG.Low, PtrArithTy, Loc);
1575       End = Exp.expandCodeFor(CG.High, PtrArithTy, Loc);
1576       DEBUG(dbgs() << "Start: " << *CG.Low << " End: " << *CG.High << "\n");
1577       Starts.push_back(Start);
1578       Ends.push_back(End);
1579     }
1580   }
1581
1582   IRBuilder<> ChkBuilder(Loc);
1583   // Our instructions might fold to a constant.
1584   Value *MemoryRuntimeCheck = nullptr;
1585   for (unsigned i = 0; i < PtrRtCheck.CheckingGroups.size(); ++i) {
1586     for (unsigned j = i + 1; j < PtrRtCheck.CheckingGroups.size(); ++j) {
1587       const RuntimePointerCheck::CheckingPtrGroup &CGI =
1588           PtrRtCheck.CheckingGroups[i];
1589       const RuntimePointerCheck::CheckingPtrGroup &CGJ =
1590           PtrRtCheck.CheckingGroups[j];
1591
1592       if (!PtrRtCheck.needsChecking(CGI, CGJ, PtrPartition))
1593         continue;
1594
1595       unsigned AS0 = Starts[i]->getType()->getPointerAddressSpace();
1596       unsigned AS1 = Starts[j]->getType()->getPointerAddressSpace();
1597
1598       assert((AS0 == Ends[j]->getType()->getPointerAddressSpace()) &&
1599              (AS1 == Ends[i]->getType()->getPointerAddressSpace()) &&
1600              "Trying to bounds check pointers with different address spaces");
1601
1602       Type *PtrArithTy0 = Type::getInt8PtrTy(Ctx, AS0);
1603       Type *PtrArithTy1 = Type::getInt8PtrTy(Ctx, AS1);
1604
1605       Value *Start0 = ChkBuilder.CreateBitCast(Starts[i], PtrArithTy0, "bc");
1606       Value *Start1 = ChkBuilder.CreateBitCast(Starts[j], PtrArithTy1, "bc");
1607       Value *End0 =   ChkBuilder.CreateBitCast(Ends[i],   PtrArithTy1, "bc");
1608       Value *End1 =   ChkBuilder.CreateBitCast(Ends[j],   PtrArithTy0, "bc");
1609
1610       Value *Cmp0 = ChkBuilder.CreateICmpULE(Start0, End1, "bound0");
1611       FirstInst = getFirstInst(FirstInst, Cmp0, Loc);
1612       Value *Cmp1 = ChkBuilder.CreateICmpULE(Start1, End0, "bound1");
1613       FirstInst = getFirstInst(FirstInst, Cmp1, Loc);
1614       Value *IsConflict = ChkBuilder.CreateAnd(Cmp0, Cmp1, "found.conflict");
1615       FirstInst = getFirstInst(FirstInst, IsConflict, Loc);
1616       if (MemoryRuntimeCheck) {
1617         IsConflict = ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict,
1618                                          "conflict.rdx");
1619         FirstInst = getFirstInst(FirstInst, IsConflict, Loc);
1620       }
1621       MemoryRuntimeCheck = IsConflict;
1622     }
1623   }
1624
1625   if (!MemoryRuntimeCheck)
1626     return std::make_pair(nullptr, nullptr);
1627
1628   // We have to do this trickery because the IRBuilder might fold the check to a
1629   // constant expression in which case there is no Instruction anchored in a
1630   // the block.
1631   Instruction *Check = BinaryOperator::CreateAnd(MemoryRuntimeCheck,
1632                                                  ConstantInt::getTrue(Ctx));
1633   ChkBuilder.Insert(Check, "memcheck.conflict");
1634   FirstInst = getFirstInst(FirstInst, Check, Loc);
1635   return std::make_pair(FirstInst, Check);
1636 }
1637
1638 LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
1639                                const DataLayout &DL,
1640                                const TargetLibraryInfo *TLI, AliasAnalysis *AA,
1641                                DominatorTree *DT, LoopInfo *LI,
1642                                const ValueToValueMap &Strides)
1643     : PtrRtCheck(SE), DepChecker(SE, L), TheLoop(L), SE(SE), DL(DL), TLI(TLI),
1644       AA(AA), DT(DT), LI(LI), NumLoads(0), NumStores(0),
1645       MaxSafeDepDistBytes(-1U), CanVecMem(false),
1646       StoreToLoopInvariantAddress(false) {
1647   if (canAnalyzeLoop())
1648     analyzeLoop(Strides);
1649 }
1650
1651 void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
1652   if (CanVecMem) {
1653     if (PtrRtCheck.Need)
1654       OS.indent(Depth) << "Memory dependences are safe with run-time checks\n";
1655     else
1656       OS.indent(Depth) << "Memory dependences are safe\n";
1657   }
1658
1659   if (Report)
1660     OS.indent(Depth) << "Report: " << Report->str() << "\n";
1661
1662   if (auto *InterestingDependences = DepChecker.getInterestingDependences()) {
1663     OS.indent(Depth) << "Interesting Dependences:\n";
1664     for (auto &Dep : *InterestingDependences) {
1665       Dep.print(OS, Depth + 2, DepChecker.getMemoryInstructions());
1666       OS << "\n";
1667     }
1668   } else
1669     OS.indent(Depth) << "Too many interesting dependences, not recorded\n";
1670
1671   // List the pair of accesses need run-time checks to prove independence.
1672   PtrRtCheck.print(OS, Depth);
1673   OS << "\n";
1674
1675   OS.indent(Depth) << "Store to invariant address was "
1676                    << (StoreToLoopInvariantAddress ? "" : "not ")
1677                    << "found in loop.\n";
1678 }
1679
1680 const LoopAccessInfo &
1681 LoopAccessAnalysis::getInfo(Loop *L, const ValueToValueMap &Strides) {
1682   auto &LAI = LoopAccessInfoMap[L];
1683
1684 #ifndef NDEBUG
1685   assert((!LAI || LAI->NumSymbolicStrides == Strides.size()) &&
1686          "Symbolic strides changed for loop");
1687 #endif
1688
1689   if (!LAI) {
1690     const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
1691     LAI = llvm::make_unique<LoopAccessInfo>(L, SE, DL, TLI, AA, DT, LI,
1692                                             Strides);
1693 #ifndef NDEBUG
1694     LAI->NumSymbolicStrides = Strides.size();
1695 #endif
1696   }
1697   return *LAI.get();
1698 }
1699
1700 void LoopAccessAnalysis::print(raw_ostream &OS, const Module *M) const {
1701   LoopAccessAnalysis &LAA = *const_cast<LoopAccessAnalysis *>(this);
1702
1703   ValueToValueMap NoSymbolicStrides;
1704
1705   for (Loop *TopLevelLoop : *LI)
1706     for (Loop *L : depth_first(TopLevelLoop)) {
1707       OS.indent(2) << L->getHeader()->getName() << ":\n";
1708       auto &LAI = LAA.getInfo(L, NoSymbolicStrides);
1709       LAI.print(OS, 4);
1710     }
1711 }
1712
1713 bool LoopAccessAnalysis::runOnFunction(Function &F) {
1714   SE = &getAnalysis<ScalarEvolution>();
1715   auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
1716   TLI = TLIP ? &TLIP->getTLI() : nullptr;
1717   AA = &getAnalysis<AliasAnalysis>();
1718   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1719   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1720
1721   return false;
1722 }
1723
1724 void LoopAccessAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
1725     AU.addRequired<ScalarEvolution>();
1726     AU.addRequired<AliasAnalysis>();
1727     AU.addRequired<DominatorTreeWrapperPass>();
1728     AU.addRequired<LoopInfoWrapperPass>();
1729
1730     AU.setPreservesAll();
1731 }
1732
1733 char LoopAccessAnalysis::ID = 0;
1734 static const char laa_name[] = "Loop Access Analysis";
1735 #define LAA_NAME "loop-accesses"
1736
1737 INITIALIZE_PASS_BEGIN(LoopAccessAnalysis, LAA_NAME, laa_name, false, true)
1738 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
1739 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
1740 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1741 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
1742 INITIALIZE_PASS_END(LoopAccessAnalysis, LAA_NAME, laa_name, false, true)
1743
1744 namespace llvm {
1745   Pass *createLAAPass() {
1746     return new LoopAccessAnalysis();
1747   }
1748 }