brintos / llvm-project-archived public Read only

1//===-- DependenceAnalysis.cpp - DA Implementation --------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// DependenceAnalysis is an LLVM pass that analyses dependences between memory10// accesses. Currently, it is an (incomplete) implementation of the approach11// described in12//13//            Practical Dependence Testing14//            Goff, Kennedy, Tseng15//            PLDI 199116//17// There's a single entry point that analyzes the dependence between a pair18// of memory references in a function, returning either NULL, for no dependence,19// or a more-or-less detailed description of the dependence between them.20//21// Since Clang linearizes some array subscripts, the dependence22// analysis is using SCEV->delinearize to recover the representation of multiple23// subscripts, and thus avoid the more expensive and less precise MIV tests. The24// delinearization is controlled by the flag -da-delinearize.25//26// We should pay some careful attention to the possibility of integer overflow27// in the implementation of the various tests. This could happen with Add,28// Subtract, or Multiply, with both APInt's and SCEV's.29//30// Some non-linear subscript pairs can be handled by the GCD test31// (and perhaps other tests).32// Should explore how often these things occur.33//34// Finally, it seems like certain test cases expose weaknesses in the SCEV35// simplification, especially in the handling of sign and zero extensions.36// It could be useful to spend time exploring these.37//38// Please note that this is work in progress and the interface is subject to39// change.40//41//===----------------------------------------------------------------------===//42//                                                                            //43//                   In memory of Ken Kennedy, 1945 - 2007                    //44//                                                                            //45//===----------------------------------------------------------------------===//46 47#include "llvm/Analysis/DependenceAnalysis.h"48#include "llvm/ADT/Statistic.h"49#include "llvm/Analysis/AliasAnalysis.h"50#include "llvm/Analysis/Delinearization.h"51#include "llvm/Analysis/LoopInfo.h"52#include "llvm/Analysis/ScalarEvolution.h"53#include "llvm/Analysis/ScalarEvolutionExpressions.h"54#include "llvm/Analysis/ValueTracking.h"55#include "llvm/IR/InstIterator.h"56#include "llvm/IR/Module.h"57#include "llvm/InitializePasses.h"58#include "llvm/Support/CommandLine.h"59#include "llvm/Support/Debug.h"60#include "llvm/Support/ErrorHandling.h"61#include "llvm/Support/raw_ostream.h"62 63using namespace llvm;64 65#define DEBUG_TYPE "da"66 67//===----------------------------------------------------------------------===//68// statistics69 70STATISTIC(TotalArrayPairs, "Array pairs tested");71STATISTIC(NonlinearSubscriptPairs, "Nonlinear subscript pairs");72STATISTIC(ZIVapplications, "ZIV applications");73STATISTIC(ZIVindependence, "ZIV independence");74STATISTIC(StrongSIVapplications, "Strong SIV applications");75STATISTIC(StrongSIVsuccesses, "Strong SIV successes");76STATISTIC(StrongSIVindependence, "Strong SIV independence");77STATISTIC(WeakCrossingSIVapplications, "Weak-Crossing SIV applications");78STATISTIC(WeakCrossingSIVsuccesses, "Weak-Crossing SIV successes");79STATISTIC(WeakCrossingSIVindependence, "Weak-Crossing SIV independence");80STATISTIC(ExactSIVapplications, "Exact SIV applications");81STATISTIC(ExactSIVsuccesses, "Exact SIV successes");82STATISTIC(ExactSIVindependence, "Exact SIV independence");83STATISTIC(WeakZeroSIVapplications, "Weak-Zero SIV applications");84STATISTIC(WeakZeroSIVsuccesses, "Weak-Zero SIV successes");85STATISTIC(WeakZeroSIVindependence, "Weak-Zero SIV independence");86STATISTIC(ExactRDIVapplications, "Exact RDIV applications");87STATISTIC(ExactRDIVindependence, "Exact RDIV independence");88STATISTIC(SymbolicRDIVapplications, "Symbolic RDIV applications");89STATISTIC(SymbolicRDIVindependence, "Symbolic RDIV independence");90STATISTIC(GCDapplications, "GCD applications");91STATISTIC(GCDsuccesses, "GCD successes");92STATISTIC(GCDindependence, "GCD independence");93STATISTIC(BanerjeeApplications, "Banerjee applications");94STATISTIC(BanerjeeIndependence, "Banerjee independence");95STATISTIC(BanerjeeSuccesses, "Banerjee successes");96STATISTIC(SameSDLoopsCount, "Loops with Same iteration Space and Depth");97 98static cl::opt<bool>99    Delinearize("da-delinearize", cl::init(true), cl::Hidden,100                cl::desc("Try to delinearize array references."));101static cl::opt<bool> DisableDelinearizationChecks(102    "da-disable-delinearization-checks", cl::Hidden,103    cl::desc(104        "Disable checks that try to statically verify validity of "105        "delinearized subscripts. Enabling this option may result in incorrect "106        "dependence vectors for languages that allow the subscript of one "107        "dimension to underflow or overflow into another dimension."));108 109static cl::opt<unsigned> MIVMaxLevelThreshold(110    "da-miv-max-level-threshold", cl::init(7), cl::Hidden,111    cl::desc("Maximum depth allowed for the recursive algorithm used to "112             "explore MIV direction vectors."));113 114namespace {115 116/// Types of dependence test routines.117enum class DependenceTestType {118  All,119  StrongSIV,120  WeakCrossingSIV,121  ExactSIV,122  WeakZeroSIV,123  ExactRDIV,124  SymbolicRDIV,125  GCDMIV,126  BanerjeeMIV,127};128 129} // anonymous namespace130 131static cl::opt<DependenceTestType> EnableDependenceTest(132    "da-enable-dependence-test", cl::init(DependenceTestType::All),133    cl::ReallyHidden,134    cl::desc("Run only specified dependence test routine and disable others. "135             "The purpose is mainly to exclude the influence of other "136             "dependence test routines in regression tests. If set to All, all "137             "dependence test routines are enabled."),138    cl::values(clEnumValN(DependenceTestType::All, "all",139                          "Enable all dependence test routines."),140               clEnumValN(DependenceTestType::StrongSIV, "strong-siv",141                          "Enable only Strong SIV test."),142               clEnumValN(DependenceTestType::WeakCrossingSIV,143                          "weak-crossing-siv",144                          "Enable only Weak-Crossing SIV test."),145               clEnumValN(DependenceTestType::ExactSIV, "exact-siv",146                          "Enable only Exact SIV test."),147               clEnumValN(DependenceTestType::WeakZeroSIV, "weak-zero-siv",148                          "Enable only Weak-Zero SIV test."),149               clEnumValN(DependenceTestType::ExactRDIV, "exact-rdiv",150                          "Enable only Exact RDIV test."),151               clEnumValN(DependenceTestType::SymbolicRDIV, "symbolic-rdiv",152                          "Enable only Symbolic RDIV test."),153               clEnumValN(DependenceTestType::GCDMIV, "gcd-miv",154                          "Enable only GCD MIV test."),155               clEnumValN(DependenceTestType::BanerjeeMIV, "banerjee-miv",156                          "Enable only Banerjee MIV test.")));157 158// TODO: This flag is disabled by default because it is still under development.159// Enable it or delete this flag when the feature is ready.160static cl::opt<bool> EnableMonotonicityCheck(161    "da-enable-monotonicity-check", cl::init(false), cl::Hidden,162    cl::desc("Check if the subscripts are monotonic. If it's not, dependence "163             "is reported as unknown."));164 165static cl::opt<bool> DumpMonotonicityReport(166    "da-dump-monotonicity-report", cl::init(false), cl::Hidden,167    cl::desc(168        "When printing analysis, dump the results of monotonicity checks."));169 170//===----------------------------------------------------------------------===//171// basics172 173DependenceAnalysis::Result174DependenceAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {175  auto &AA = FAM.getResult<AAManager>(F);176  auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);177  auto &LI = FAM.getResult<LoopAnalysis>(F);178  return DependenceInfo(&F, &AA, &SE, &LI);179}180 181AnalysisKey DependenceAnalysis::Key;182 183INITIALIZE_PASS_BEGIN(DependenceAnalysisWrapperPass, "da",184                      "Dependence Analysis", true, true)185INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)186INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)187INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)188INITIALIZE_PASS_END(DependenceAnalysisWrapperPass, "da", "Dependence Analysis",189                    true, true)190 191char DependenceAnalysisWrapperPass::ID = 0;192 193DependenceAnalysisWrapperPass::DependenceAnalysisWrapperPass()194    : FunctionPass(ID) {}195 196FunctionPass *llvm::createDependenceAnalysisWrapperPass() {197  return new DependenceAnalysisWrapperPass();198}199 200bool DependenceAnalysisWrapperPass::runOnFunction(Function &F) {201  auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();202  auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();203  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();204  info.reset(new DependenceInfo(&F, &AA, &SE, &LI));205  return false;206}207 208DependenceInfo &DependenceAnalysisWrapperPass::getDI() const { return *info; }209 210void DependenceAnalysisWrapperPass::releaseMemory() { info.reset(); }211 212void DependenceAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {213  AU.setPreservesAll();214  AU.addRequiredTransitive<AAResultsWrapperPass>();215  AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();216  AU.addRequiredTransitive<LoopInfoWrapperPass>();217}218 219namespace {220 221/// The property of monotonicity of a SCEV. To define the monotonicity, assume222/// a SCEV defined within N-nested loops. Let i_k denote the iteration number223/// of the k-th loop. Then we can regard the SCEV as an N-ary function:224///225///   F(i_1, i_2, ..., i_N)226///227/// The domain of i_k is the closed range [0, BTC_k], where BTC_k is the228/// backedge-taken count of the k-th loop.229///230/// A function F is said to be "monotonically increasing with respect to the231/// k-th loop" if x <= y implies the following condition:232///233///   F(i_1, ..., i_{k-1}, x, i_{k+1}, ..., i_N) <=234///   F(i_1, ..., i_{k-1}, y, i_{k+1}, ..., i_N)235///236/// where i_1, ..., i_{k-1}, i_{k+1}, ..., i_N, x, and y are elements of their237/// respective domains.238///239/// Likewise F is "monotonically decreasing with respect to the k-th loop"240/// if x <= y implies241///242///   F(i_1, ..., i_{k-1}, x, i_{k+1}, ..., i_N) >=243///   F(i_1, ..., i_{k-1}, y, i_{k+1}, ..., i_N)244///245/// A function F that is monotonically increasing or decreasing with respect to246/// the k-th loop is simply called "monotonic with respect to k-th loop".247///248/// A function F is said to be "multivariate monotonic" when it is monotonic249/// with respect to all of the N loops.250///251/// Since integer comparison can be either signed or unsigned, we need to252/// distinguish monotonicity in the signed sense from that in the unsigned253/// sense. Note that the inequality "x <= y" merely indicates loop progression254/// and is not affected by the difference between signed and unsigned order.255///256/// Currently we only consider monotonicity in a signed sense.257enum class SCEVMonotonicityType {258  /// We don't know anything about the monotonicity of the SCEV.259  Unknown,260 261  /// The SCEV is loop-invariant with respect to the outermost loop. In other262  /// words, the function F corresponding to the SCEV is a constant function.263  Invariant,264 265  /// The function F corresponding to the SCEV is multivariate monotonic in a266  /// signed sense. Note that the multivariate monotonic function may also be a267  /// constant function. The order employed in the definition of monotonicity268  /// is not strict order.269  MultivariateSignedMonotonic,270};271 272struct SCEVMonotonicity {273  SCEVMonotonicity(SCEVMonotonicityType Type,274                   const SCEV *FailurePoint = nullptr);275 276  SCEVMonotonicityType getType() const { return Type; }277 278  const SCEV *getFailurePoint() const { return FailurePoint; }279 280  bool isUnknown() const { return Type == SCEVMonotonicityType::Unknown; }281 282  void print(raw_ostream &OS, unsigned Depth) const;283 284private:285  SCEVMonotonicityType Type;286 287  /// The subexpression that caused Unknown. Mainly for debugging purpose.288  const SCEV *FailurePoint;289};290 291/// Check the monotonicity of a SCEV. Since dependence tests (SIV, MIV, etc.)292/// assume that subscript expressions are (multivariate) monotonic, we need to293/// verify this property before applying those tests. Violating this assumption294/// may cause them to produce incorrect results.295struct SCEVMonotonicityChecker296    : public SCEVVisitor<SCEVMonotonicityChecker, SCEVMonotonicity> {297 298  SCEVMonotonicityChecker(ScalarEvolution *SE) : SE(SE) {}299 300  /// Check the monotonicity of \p Expr. \p Expr must be integer type. If \p301  /// OutermostLoop is not null, \p Expr must be defined in \p OutermostLoop or302  /// one of its nested loops.303  SCEVMonotonicity checkMonotonicity(const SCEV *Expr,304                                     const Loop *OutermostLoop);305 306private:307  ScalarEvolution *SE;308 309  /// The outermost loop that DA is analyzing.310  const Loop *OutermostLoop;311 312  /// A helper to classify \p Expr as either Invariant or Unknown.313  SCEVMonotonicity invariantOrUnknown(const SCEV *Expr);314 315  /// Return true if \p Expr is loop-invariant with respect to the outermost316  /// loop.317  bool isLoopInvariant(const SCEV *Expr) const;318 319  /// A helper to create an Unknown SCEVMonotonicity.320  SCEVMonotonicity createUnknown(const SCEV *FailurePoint) {321    return SCEVMonotonicity(SCEVMonotonicityType::Unknown, FailurePoint);322  }323 324  SCEVMonotonicity visitAddRecExpr(const SCEVAddRecExpr *Expr);325 326  SCEVMonotonicity visitConstant(const SCEVConstant *) {327    return SCEVMonotonicity(SCEVMonotonicityType::Invariant);328  }329  SCEVMonotonicity visitVScale(const SCEVVScale *) {330    return SCEVMonotonicity(SCEVMonotonicityType::Invariant);331  }332 333  // TODO: Handle more cases.334  SCEVMonotonicity visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {335    return invariantOrUnknown(Expr);336  }337  SCEVMonotonicity visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {338    return invariantOrUnknown(Expr);339  }340  SCEVMonotonicity visitAddExpr(const SCEVAddExpr *Expr) {341    return invariantOrUnknown(Expr);342  }343  SCEVMonotonicity visitMulExpr(const SCEVMulExpr *Expr) {344    return invariantOrUnknown(Expr);345  }346  SCEVMonotonicity visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr) {347    return invariantOrUnknown(Expr);348  }349  SCEVMonotonicity visitTruncateExpr(const SCEVTruncateExpr *Expr) {350    return invariantOrUnknown(Expr);351  }352  SCEVMonotonicity visitUDivExpr(const SCEVUDivExpr *Expr) {353    return invariantOrUnknown(Expr);354  }355  SCEVMonotonicity visitSMaxExpr(const SCEVSMaxExpr *Expr) {356    return invariantOrUnknown(Expr);357  }358  SCEVMonotonicity visitUMaxExpr(const SCEVUMaxExpr *Expr) {359    return invariantOrUnknown(Expr);360  }361  SCEVMonotonicity visitSMinExpr(const SCEVSMinExpr *Expr) {362    return invariantOrUnknown(Expr);363  }364  SCEVMonotonicity visitUMinExpr(const SCEVUMinExpr *Expr) {365    return invariantOrUnknown(Expr);366  }367  SCEVMonotonicity visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr) {368    return invariantOrUnknown(Expr);369  }370  SCEVMonotonicity visitUnknown(const SCEVUnknown *Expr) {371    return invariantOrUnknown(Expr);372  }373  SCEVMonotonicity visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {374    return invariantOrUnknown(Expr);375  }376 377  friend struct SCEVVisitor<SCEVMonotonicityChecker, SCEVMonotonicity>;378};379 380} // anonymous namespace381 382// Used to test the dependence analyzer.383// Looks through the function, noting instructions that may access memory.384// Calls depends() on every possible pair and prints out the result.385// Ignores all other instructions.386static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA,387                                  ScalarEvolution &SE, LoopInfo &LI,388                                  bool NormalizeResults) {389  auto *F = DA->getFunction();390 391  if (DumpMonotonicityReport) {392    SCEVMonotonicityChecker Checker(&SE);393    OS << "Monotonicity check:\n";394    for (Instruction &Inst : instructions(F)) {395      if (!isa<LoadInst>(Inst) && !isa<StoreInst>(Inst))396        continue;397      Value *Ptr = getLoadStorePointerOperand(&Inst);398      const Loop *L = LI.getLoopFor(Inst.getParent());399      const Loop *OutermostLoop = L ? L->getOutermostLoop() : nullptr;400      const SCEV *PtrSCEV = SE.getSCEVAtScope(Ptr, L);401      const SCEV *AccessFn = SE.removePointerBase(PtrSCEV);402      SCEVMonotonicity Mon = Checker.checkMonotonicity(AccessFn, OutermostLoop);403      OS.indent(2) << "Inst: " << Inst << "\n";404      OS.indent(4) << "Expr: " << *AccessFn << "\n";405      Mon.print(OS, 4);406    }407    OS << "\n";408  }409 410  for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F); SrcI != SrcE;411       ++SrcI) {412    if (SrcI->mayReadOrWriteMemory()) {413      for (inst_iterator DstI = SrcI, DstE = inst_end(F); DstI != DstE;414           ++DstI) {415        if (DstI->mayReadOrWriteMemory()) {416          OS << "Src:" << *SrcI << " --> Dst:" << *DstI << "\n";417          OS << "  da analyze - ";418          if (auto D = DA->depends(&*SrcI, &*DstI,419                                   /*UnderRuntimeAssumptions=*/true)) {420 421#ifndef NDEBUG422            // Verify that the distance being zero is equivalent to the423            // direction being EQ.424            for (unsigned Level = 1; Level <= D->getLevels(); Level++) {425              const SCEV *Distance = D->getDistance(Level);426              bool IsDistanceZero = Distance && Distance->isZero();427              bool IsDirectionEQ =428                  D->getDirection(Level) == Dependence::DVEntry::EQ;429              assert(IsDistanceZero == IsDirectionEQ &&430                     "Inconsistent distance and direction.");431            }432#endif433 434            // Normalize negative direction vectors if required by clients.435            if (NormalizeResults && D->normalize(&SE))436              OS << "normalized - ";437            D->dump(OS);438          } else439            OS << "none!\n";440        }441      }442    }443  }444}445 446void DependenceAnalysisWrapperPass::print(raw_ostream &OS,447                                          const Module *) const {448  dumpExampleDependence(449      OS, info.get(), getAnalysis<ScalarEvolutionWrapperPass>().getSE(),450      getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), false);451}452 453PreservedAnalyses454DependenceAnalysisPrinterPass::run(Function &F, FunctionAnalysisManager &FAM) {455  OS << "Printing analysis 'Dependence Analysis' for function '" << F.getName()456     << "':\n";457  dumpExampleDependence(OS, &FAM.getResult<DependenceAnalysis>(F),458                        FAM.getResult<ScalarEvolutionAnalysis>(F),459                        FAM.getResult<LoopAnalysis>(F), NormalizeResults);460  return PreservedAnalyses::all();461}462 463//===----------------------------------------------------------------------===//464// Dependence methods465 466// Returns true if this is an input dependence.467bool Dependence::isInput() const {468  return Src->mayReadFromMemory() && Dst->mayReadFromMemory();469}470 471// Returns true if this is an output dependence.472bool Dependence::isOutput() const {473  return Src->mayWriteToMemory() && Dst->mayWriteToMemory();474}475 476// Returns true if this is an flow (aka true)  dependence.477bool Dependence::isFlow() const {478  return Src->mayWriteToMemory() && Dst->mayReadFromMemory();479}480 481// Returns true if this is an anti dependence.482bool Dependence::isAnti() const {483  return Src->mayReadFromMemory() && Dst->mayWriteToMemory();484}485 486// Returns true if a particular level is scalar; that is,487// if no subscript in the source or destination mention the induction488// variable associated with the loop at this level.489// Leave this out of line, so it will serve as a virtual method anchor490bool Dependence::isScalar(unsigned level, bool IsSameSD) const { return false; }491 492//===----------------------------------------------------------------------===//493// FullDependence methods494 495FullDependence::FullDependence(Instruction *Source, Instruction *Destination,496                               const SCEVUnionPredicate &Assumes,497                               bool PossiblyLoopIndependent,498                               unsigned CommonLevels)499    : Dependence(Source, Destination, Assumes), Levels(CommonLevels),500      LoopIndependent(PossiblyLoopIndependent) {501  Consistent = true;502  SameSDLevels = 0;503  if (CommonLevels)504    DV = std::make_unique<DVEntry[]>(CommonLevels);505}506 507// FIXME: in some cases the meaning of a negative direction vector508// may not be straightforward, e.g.,509// for (int i = 0; i < 32; ++i) {510//   Src:    A[i] = ...;511//   Dst:    use(A[31 - i]);512// }513// The dependency is514//   flow { Src[i] -> Dst[31 - i] : when i >= 16 } and515//   anti { Dst[i] -> Src[31 - i] : when i < 16 },516// -- hence a [<>].517// As long as a dependence result contains '>' ('<>', '<=>', "*"), it518// means that a reversed/normalized dependence needs to be considered519// as well. Nevertheless, current isDirectionNegative() only returns520// true with a '>' or '>=' dependency for ease of canonicalizing the521// dependency vector, since the reverse of '<>', '<=>' and "*" is itself.522bool FullDependence::isDirectionNegative() const {523  for (unsigned Level = 1; Level <= Levels; ++Level) {524    unsigned char Direction = DV[Level - 1].Direction;525    if (Direction == Dependence::DVEntry::EQ)526      continue;527    if (Direction == Dependence::DVEntry::GT ||528        Direction == Dependence::DVEntry::GE)529      return true;530    return false;531  }532  return false;533}534 535bool FullDependence::normalize(ScalarEvolution *SE) {536  if (!isDirectionNegative())537    return false;538 539  LLVM_DEBUG(dbgs() << "Before normalizing negative direction vectors:\n";540             dump(dbgs()););541  std::swap(Src, Dst);542  for (unsigned Level = 1; Level <= Levels; ++Level) {543    unsigned char Direction = DV[Level - 1].Direction;544    // Reverse the direction vector, this means LT becomes GT545    // and GT becomes LT.546    unsigned char RevDirection = Direction & Dependence::DVEntry::EQ;547    if (Direction & Dependence::DVEntry::LT)548      RevDirection |= Dependence::DVEntry::GT;549    if (Direction & Dependence::DVEntry::GT)550      RevDirection |= Dependence::DVEntry::LT;551    DV[Level - 1].Direction = RevDirection;552    // Reverse the dependence distance as well.553    if (DV[Level - 1].Distance != nullptr)554      DV[Level - 1].Distance = SE->getNegativeSCEV(DV[Level - 1].Distance);555  }556 557  LLVM_DEBUG(dbgs() << "After normalizing negative direction vectors:\n";558             dump(dbgs()););559  return true;560}561 562// The rest are simple getters that hide the implementation.563 564// getDirection - Returns the direction associated with a particular common or565// SameSD level.566unsigned FullDependence::getDirection(unsigned Level, bool IsSameSD) const {567  return getDVEntry(Level, IsSameSD).Direction;568}569 570// Returns the distance (or NULL) associated with a particular common or571// SameSD level.572const SCEV *FullDependence::getDistance(unsigned Level, bool IsSameSD) const {573  return getDVEntry(Level, IsSameSD).Distance;574}575 576// Returns true if a particular regular or SameSD level is scalar; that is,577// if no subscript in the source or destination mention the induction variable578// associated with the loop at this level.579bool FullDependence::isScalar(unsigned Level, bool IsSameSD) const {580  return getDVEntry(Level, IsSameSD).Scalar;581}582 583// Returns true if peeling the first iteration from this regular or SameSD584// loop level will break this dependence.585bool FullDependence::isPeelFirst(unsigned Level, bool IsSameSD) const {586  return getDVEntry(Level, IsSameSD).PeelFirst;587}588 589// Returns true if peeling the last iteration from this regular or SameSD590// loop level will break this dependence.591bool FullDependence::isPeelLast(unsigned Level, bool IsSameSD) const {592  return getDVEntry(Level, IsSameSD).PeelLast;593}594 595// inSameSDLoops - Returns true if this level is an SameSD level, i.e.,596// performed across two separate loop nests that have the Same iteration space597// and Depth.598bool FullDependence::inSameSDLoops(unsigned Level) const {599  assert(0 < Level && Level <= static_cast<unsigned>(Levels) + SameSDLevels &&600         "Level out of range");601  return Level > Levels;602}603 604//===----------------------------------------------------------------------===//605// SCEVMonotonicity606 607SCEVMonotonicity::SCEVMonotonicity(SCEVMonotonicityType Type,608                                   const SCEV *FailurePoint)609    : Type(Type), FailurePoint(FailurePoint) {610  assert(611      ((Type == SCEVMonotonicityType::Unknown) == (FailurePoint != nullptr)) &&612      "FailurePoint must be provided iff Type is Unknown");613}614 615void SCEVMonotonicity::print(raw_ostream &OS, unsigned Depth) const {616  OS.indent(Depth) << "Monotonicity: ";617  switch (Type) {618  case SCEVMonotonicityType::Unknown:619    assert(FailurePoint && "FailurePoint must be provided for Unknown");620    OS << "Unknown\n";621    OS.indent(Depth) << "Reason: " << *FailurePoint << "\n";622    break;623  case SCEVMonotonicityType::Invariant:624    OS << "Invariant\n";625    break;626  case SCEVMonotonicityType::MultivariateSignedMonotonic:627    OS << "MultivariateSignedMonotonic\n";628    break;629  }630}631 632bool SCEVMonotonicityChecker::isLoopInvariant(const SCEV *Expr) const {633  return !OutermostLoop || SE->isLoopInvariant(Expr, OutermostLoop);634}635 636SCEVMonotonicity SCEVMonotonicityChecker::invariantOrUnknown(const SCEV *Expr) {637  if (isLoopInvariant(Expr))638    return SCEVMonotonicity(SCEVMonotonicityType::Invariant);639  return createUnknown(Expr);640}641 642SCEVMonotonicity643SCEVMonotonicityChecker::checkMonotonicity(const SCEV *Expr,644                                           const Loop *OutermostLoop) {645  assert((!OutermostLoop || OutermostLoop->isOutermost()) &&646         "OutermostLoop must be outermost");647  assert(Expr->getType()->isIntegerTy() && "Expr must be integer type");648  this->OutermostLoop = OutermostLoop;649  return visit(Expr);650}651 652/// We only care about an affine AddRec at the moment. For an affine AddRec,653/// the monotonicity can be inferred from its nowrap property. For example, let654/// X and Y be loop-invariant, and assume Y is non-negative. An AddRec655/// {X,+.Y}<nsw> implies:656///657///   X <=s (X + Y) <=s ((X + Y) + Y) <=s ...658///659/// Thus, we can conclude that the AddRec is monotonically increasing with660/// respect to the associated loop in a signed sense. The similar reasoning661/// applies when Y is non-positive, leading to a monotonically decreasing662/// AddRec.663SCEVMonotonicity664SCEVMonotonicityChecker::visitAddRecExpr(const SCEVAddRecExpr *Expr) {665  if (!Expr->isAffine() || !Expr->hasNoSignedWrap())666    return createUnknown(Expr);667 668  const SCEV *Start = Expr->getStart();669  const SCEV *Step = Expr->getStepRecurrence(*SE);670 671  SCEVMonotonicity StartMon = visit(Start);672  if (StartMon.isUnknown())673    return StartMon;674 675  if (!isLoopInvariant(Step))676    return createUnknown(Expr);677 678  return SCEVMonotonicity(SCEVMonotonicityType::MultivariateSignedMonotonic);679}680 681//===----------------------------------------------------------------------===//682// DependenceInfo methods683 684// For debugging purposes. Dumps a dependence to OS.685void Dependence::dump(raw_ostream &OS) const {686  if (isConfused())687    OS << "confused";688  else {689    if (isConsistent())690      OS << "consistent ";691    if (isFlow())692      OS << "flow";693    else if (isOutput())694      OS << "output";695    else if (isAnti())696      OS << "anti";697    else if (isInput())698      OS << "input";699    dumpImp(OS);700    unsigned SameSDLevels = getSameSDLevels();701    if (SameSDLevels > 0) {702      OS << " / assuming " << SameSDLevels << " loop level(s) fused: ";703      dumpImp(OS, true);704    }705  }706  OS << "!\n";707 708  SCEVUnionPredicate Assumptions = getRuntimeAssumptions();709  if (!Assumptions.isAlwaysTrue()) {710    OS << "  Runtime Assumptions:\n";711    Assumptions.print(OS, 2);712  }713}714 715// For debugging purposes. Dumps a dependence to OS with or without considering716// the SameSD levels.717void Dependence::dumpImp(raw_ostream &OS, bool IsSameSD) const {718  unsigned Levels = getLevels();719  unsigned SameSDLevels = getSameSDLevels();720  bool OnSameSD = false;721  unsigned LevelNum = Levels;722  if (IsSameSD)723    LevelNum += SameSDLevels;724  OS << " [";725  for (unsigned II = 1; II <= LevelNum; ++II) {726    if (!OnSameSD && inSameSDLoops(II))727      OnSameSD = true;728    if (isPeelFirst(II, OnSameSD))729      OS << 'p';730    const SCEV *Distance = getDistance(II, OnSameSD);731    if (Distance)732      OS << *Distance;733    else if (isScalar(II, OnSameSD))734      OS << "S";735    else {736      unsigned Direction = getDirection(II, OnSameSD);737      if (Direction == DVEntry::ALL)738        OS << "*";739      else {740        if (Direction & DVEntry::LT)741          OS << "<";742        if (Direction & DVEntry::EQ)743          OS << "=";744        if (Direction & DVEntry::GT)745          OS << ">";746      }747    }748    if (isPeelLast(II, OnSameSD))749      OS << 'p';750    if (II < LevelNum)751      OS << " ";752  }753  if (isLoopIndependent())754    OS << "|<";755  OS << "]";756}757 758// Returns NoAlias/MayAliass/MustAlias for two memory locations based upon their759// underlaying objects. If LocA and LocB are known to not alias (for any reason:760// tbaa, non-overlapping regions etc), then it is known there is no dependecy.761// Otherwise the underlying objects are checked to see if they point to762// different identifiable objects.763static AliasResult underlyingObjectsAlias(AAResults *AA, const DataLayout &DL,764                                          const MemoryLocation &LocA,765                                          const MemoryLocation &LocB) {766  // Check the original locations (minus size) for noalias, which can happen for767  // tbaa, incompatible underlying object locations, etc.768  MemoryLocation LocAS =769      MemoryLocation::getBeforeOrAfter(LocA.Ptr, LocA.AATags);770  MemoryLocation LocBS =771      MemoryLocation::getBeforeOrAfter(LocB.Ptr, LocB.AATags);772  BatchAAResults BAA(*AA);773  BAA.enableCrossIterationMode();774 775  if (BAA.isNoAlias(LocAS, LocBS))776    return AliasResult::NoAlias;777 778  // Check the underlying objects are the same779  const Value *AObj = getUnderlyingObject(LocA.Ptr);780  const Value *BObj = getUnderlyingObject(LocB.Ptr);781 782  // If the underlying objects are the same, they must alias783  if (AObj == BObj)784    return AliasResult::MustAlias;785 786  // We may have hit the recursion limit for underlying objects, or have787  // underlying objects where we don't know they will alias.788  if (!isIdentifiedObject(AObj) || !isIdentifiedObject(BObj))789    return AliasResult::MayAlias;790 791  // Otherwise we know the objects are different and both identified objects so792  // must not alias.793  return AliasResult::NoAlias;794}795 796// Returns true if the load or store can be analyzed. Atomic and volatile797// operations have properties which this analysis does not understand.798static bool isLoadOrStore(const Instruction *I) {799  if (const LoadInst *LI = dyn_cast<LoadInst>(I))800    return LI->isUnordered();801  else if (const StoreInst *SI = dyn_cast<StoreInst>(I))802    return SI->isUnordered();803  return false;804}805 806// Returns true if two loops have the Same iteration Space and Depth. To be807// more specific, two loops have SameSD if they are in the same nesting808// depth and have the same backedge count. SameSD stands for Same iteration809// Space and Depth.810bool DependenceInfo::haveSameSD(const Loop *SrcLoop,811                                const Loop *DstLoop) const {812  if (SrcLoop == DstLoop)813    return true;814 815  if (SrcLoop->getLoopDepth() != DstLoop->getLoopDepth())816    return false;817 818  if (!SrcLoop || !SrcLoop->getLoopLatch() || !DstLoop ||819      !DstLoop->getLoopLatch())820    return false;821 822  const SCEV *SrcUB = nullptr, *DstUP = nullptr;823  if (SE->hasLoopInvariantBackedgeTakenCount(SrcLoop))824    SrcUB = SE->getBackedgeTakenCount(SrcLoop);825  if (SE->hasLoopInvariantBackedgeTakenCount(DstLoop))826    DstUP = SE->getBackedgeTakenCount(DstLoop);827 828  if (SrcUB != nullptr && DstUP != nullptr) {829    Type *WiderType = SE->getWiderType(SrcUB->getType(), DstUP->getType());830    SrcUB = SE->getNoopOrZeroExtend(SrcUB, WiderType);831    DstUP = SE->getNoopOrZeroExtend(DstUP, WiderType);832 833    if (SE->isKnownPredicate(ICmpInst::ICMP_EQ, SrcUB, DstUP))834      return true;835  }836 837  return false;838}839 840// Examines the loop nesting of the Src and Dst841// instructions and establishes their shared loops. Sets the variables842// CommonLevels, SrcLevels, and MaxLevels.843// The source and destination instructions needn't be contained in the same844// loop. The routine establishNestingLevels finds the level of most deeply845// nested loop that contains them both, CommonLevels. An instruction that's846// not contained in a loop is at level = 0. MaxLevels is equal to the level847// of the source plus the level of the destination, minus CommonLevels.848// This lets us allocate vectors MaxLevels in length, with room for every849// distinct loop referenced in both the source and destination subscripts.850// The variable SrcLevels is the nesting depth of the source instruction.851// It's used to help calculate distinct loops referenced by the destination.852// Here's the map from loops to levels:853//            0 - unused854//            1 - outermost common loop855//          ... - other common loops856// CommonLevels - innermost common loop857//          ... - loops containing Src but not Dst858//    SrcLevels - innermost loop containing Src but not Dst859//          ... - loops containing Dst but not Src860//    MaxLevels - innermost loops containing Dst but not Src861// Consider the follow code fragment:862//   for (a = ...) {863//     for (b = ...) {864//       for (c = ...) {865//         for (d = ...) {866//           A[] = ...;867//         }868//       }869//       for (e = ...) {870//         for (f = ...) {871//           for (g = ...) {872//             ... = A[];873//           }874//         }875//       }876//     }877//   }878// If we're looking at the possibility of a dependence between the store879// to A (the Src) and the load from A (the Dst), we'll note that they880// have 2 loops in common, so CommonLevels will equal 2 and the direction881// vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7.882// A map from loop names to loop numbers would look like883//     a - 1884//     b - 2 = CommonLevels885//     c - 3886//     d - 4 = SrcLevels887//     e - 5888//     f - 6889//     g - 7 = MaxLevels890// SameSDLevels counts the number of levels after common levels that are891// not common but have the same iteration space and depth. Internally this892// is checked using haveSameSD. Assume that in this code fragment, levels c and893// e have the same iteration space and depth, but levels d and f does not. Then894// SameSDLevels is set to 1. In that case the level numbers for the previous895// code look like896//     a   - 1897//     b   - 2898//     c,e - 3 = CommonLevels899//     d   - 4 = SrcLevels900//     f   - 5901//     g   - 6 = MaxLevels902void DependenceInfo::establishNestingLevels(const Instruction *Src,903                                            const Instruction *Dst) {904  const BasicBlock *SrcBlock = Src->getParent();905  const BasicBlock *DstBlock = Dst->getParent();906  unsigned SrcLevel = LI->getLoopDepth(SrcBlock);907  unsigned DstLevel = LI->getLoopDepth(DstBlock);908  const Loop *SrcLoop = LI->getLoopFor(SrcBlock);909  const Loop *DstLoop = LI->getLoopFor(DstBlock);910  SrcLevels = SrcLevel;911  MaxLevels = SrcLevel + DstLevel;912  SameSDLevels = 0;913  while (SrcLevel > DstLevel) {914    SrcLoop = SrcLoop->getParentLoop();915    SrcLevel--;916  }917  while (DstLevel > SrcLevel) {918    DstLoop = DstLoop->getParentLoop();919    DstLevel--;920  }921 922  // find the first common level and count the SameSD levels leading to it923  while (SrcLoop != DstLoop) {924    SameSDLevels++;925    if (!haveSameSD(SrcLoop, DstLoop))926      SameSDLevels = 0;927    SrcLoop = SrcLoop->getParentLoop();928    DstLoop = DstLoop->getParentLoop();929    SrcLevel--;930  }931  CommonLevels = SrcLevel;932  MaxLevels -= CommonLevels;933}934 935// Given one of the loops containing the source, return936// its level index in our numbering scheme.937unsigned DependenceInfo::mapSrcLoop(const Loop *SrcLoop) const {938  return SrcLoop->getLoopDepth();939}940 941// Given one of the loops containing the destination,942// return its level index in our numbering scheme.943unsigned DependenceInfo::mapDstLoop(const Loop *DstLoop) const {944  unsigned D = DstLoop->getLoopDepth();945  if (D > CommonLevels)946    // This tries to make sure that we assign unique numbers to src and dst when947    // the memory accesses reside in different loops that have the same depth.948    return D - CommonLevels + SrcLevels;949  else950    return D;951}952 953// Returns true if Expression is loop invariant in LoopNest.954bool DependenceInfo::isLoopInvariant(const SCEV *Expression,955                                     const Loop *LoopNest) const {956  // Unlike ScalarEvolution::isLoopInvariant() we consider an access outside of957  // any loop as invariant, because we only consier expression evaluation at a958  // specific position (where the array access takes place), and not across the959  // entire function.960  if (!LoopNest)961    return true;962 963  // If the expression is invariant in the outermost loop of the loop nest, it964  // is invariant anywhere in the loop nest.965  return SE->isLoopInvariant(Expression, LoopNest->getOutermostLoop());966}967 968// Finds the set of loops from the LoopNest that969// have a level <= CommonLevels and are referred to by the SCEV Expression.970void DependenceInfo::collectCommonLoops(const SCEV *Expression,971                                        const Loop *LoopNest,972                                        SmallBitVector &Loops) const {973  while (LoopNest) {974    unsigned Level = LoopNest->getLoopDepth();975    if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest))976      Loops.set(Level);977    LoopNest = LoopNest->getParentLoop();978  }979}980 981void DependenceInfo::unifySubscriptType(ArrayRef<Subscript *> Pairs) {982 983  unsigned widestWidthSeen = 0;984  Type *widestType;985 986  // Go through each pair and find the widest bit to which we need987  // to extend all of them.988  for (Subscript *Pair : Pairs) {989    const SCEV *Src = Pair->Src;990    const SCEV *Dst = Pair->Dst;991    IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());992    IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());993    if (SrcTy == nullptr || DstTy == nullptr) {994      assert(SrcTy == DstTy &&995             "This function only unify integer types and "996             "expect Src and Dst share the same type otherwise.");997      continue;998    }999    if (SrcTy->getBitWidth() > widestWidthSeen) {1000      widestWidthSeen = SrcTy->getBitWidth();1001      widestType = SrcTy;1002    }1003    if (DstTy->getBitWidth() > widestWidthSeen) {1004      widestWidthSeen = DstTy->getBitWidth();1005      widestType = DstTy;1006    }1007  }1008 1009  assert(widestWidthSeen > 0);1010 1011  // Now extend each pair to the widest seen.1012  for (Subscript *Pair : Pairs) {1013    const SCEV *Src = Pair->Src;1014    const SCEV *Dst = Pair->Dst;1015    IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());1016    IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());1017    if (SrcTy == nullptr || DstTy == nullptr) {1018      assert(SrcTy == DstTy &&1019             "This function only unify integer types and "1020             "expect Src and Dst share the same type otherwise.");1021      continue;1022    }1023    if (SrcTy->getBitWidth() < widestWidthSeen)1024      // Sign-extend Src to widestType1025      Pair->Src = SE->getSignExtendExpr(Src, widestType);1026    if (DstTy->getBitWidth() < widestWidthSeen) {1027      // Sign-extend Dst to widestType1028      Pair->Dst = SE->getSignExtendExpr(Dst, widestType);1029    }1030  }1031}1032 1033// removeMatchingExtensions - Examines a subscript pair.1034// If the source and destination are identically sign (or zero)1035// extended, it strips off the extension in an effect to simplify1036// the actual analysis.1037void DependenceInfo::removeMatchingExtensions(Subscript *Pair) {1038  const SCEV *Src = Pair->Src;1039  const SCEV *Dst = Pair->Dst;1040  if ((isa<SCEVZeroExtendExpr>(Src) && isa<SCEVZeroExtendExpr>(Dst)) ||1041      (isa<SCEVSignExtendExpr>(Src) && isa<SCEVSignExtendExpr>(Dst))) {1042    const SCEVIntegralCastExpr *SrcCast = cast<SCEVIntegralCastExpr>(Src);1043    const SCEVIntegralCastExpr *DstCast = cast<SCEVIntegralCastExpr>(Dst);1044    const SCEV *SrcCastOp = SrcCast->getOperand();1045    const SCEV *DstCastOp = DstCast->getOperand();1046    if (SrcCastOp->getType() == DstCastOp->getType()) {1047      Pair->Src = SrcCastOp;1048      Pair->Dst = DstCastOp;1049    }1050  }1051}1052 1053// Examine the scev and return true iff it's affine.1054// Collect any loops mentioned in the set of "Loops".1055bool DependenceInfo::checkSubscript(const SCEV *Expr, const Loop *LoopNest,1056                                    SmallBitVector &Loops, bool IsSrc) {1057  const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);1058  if (!AddRec)1059    return isLoopInvariant(Expr, LoopNest);1060 1061  // The AddRec must depend on one of the containing loops. Otherwise,1062  // mapSrcLoop and mapDstLoop return indices outside the intended range. This1063  // can happen when a subscript in one loop references an IV from a sibling1064  // loop that could not be replaced with a concrete exit value by1065  // getSCEVAtScope.1066  const Loop *L = LoopNest;1067  while (L && AddRec->getLoop() != L)1068    L = L->getParentLoop();1069  if (!L)1070    return false;1071 1072  const SCEV *Start = AddRec->getStart();1073  const SCEV *Step = AddRec->getStepRecurrence(*SE);1074  if (!isLoopInvariant(Step, LoopNest))1075    return false;1076  if (IsSrc)1077    Loops.set(mapSrcLoop(AddRec->getLoop()));1078  else1079    Loops.set(mapDstLoop(AddRec->getLoop()));1080  return checkSubscript(Start, LoopNest, Loops, IsSrc);1081}1082 1083// Examine the scev and return true iff it's linear.1084// Collect any loops mentioned in the set of "Loops".1085bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest,1086                                       SmallBitVector &Loops) {1087  return checkSubscript(Src, LoopNest, Loops, true);1088}1089 1090// Examine the scev and return true iff it's linear.1091// Collect any loops mentioned in the set of "Loops".1092bool DependenceInfo::checkDstSubscript(const SCEV *Dst, const Loop *LoopNest,1093                                       SmallBitVector &Loops) {1094  return checkSubscript(Dst, LoopNest, Loops, false);1095}1096 1097// Examines the subscript pair (the Src and Dst SCEVs)1098// and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear.1099// Collects the associated loops in a set.1100DependenceInfo::Subscript::ClassificationKind1101DependenceInfo::classifyPair(const SCEV *Src, const Loop *SrcLoopNest,1102                             const SCEV *Dst, const Loop *DstLoopNest,1103                             SmallBitVector &Loops) {1104  SmallBitVector SrcLoops(MaxLevels + 1);1105  SmallBitVector DstLoops(MaxLevels + 1);1106  if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops))1107    return Subscript::NonLinear;1108  if (!checkDstSubscript(Dst, DstLoopNest, DstLoops))1109    return Subscript::NonLinear;1110  Loops = SrcLoops;1111  Loops |= DstLoops;1112  unsigned N = Loops.count();1113  if (N == 0)1114    return Subscript::ZIV;1115  if (N == 1)1116    return Subscript::SIV;1117  if (N == 2 && (SrcLoops.count() == 0 || DstLoops.count() == 0 ||1118                 (SrcLoops.count() == 1 && DstLoops.count() == 1)))1119    return Subscript::RDIV;1120  return Subscript::MIV;1121}1122 1123// A wrapper around SCEV::isKnownPredicate.1124// Looks for cases where we're interested in comparing for equality.1125// If both X and Y have been identically sign or zero extended,1126// it strips off the (confusing) extensions before invoking1127// SCEV::isKnownPredicate. Perhaps, someday, the ScalarEvolution package1128// will be similarly updated.1129//1130// If SCEV::isKnownPredicate can't prove the predicate,1131// we try simple subtraction, which seems to help in some cases1132// involving symbolics.1133bool DependenceInfo::isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *X,1134                                      const SCEV *Y) const {1135  if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE) {1136    if ((isa<SCEVSignExtendExpr>(X) && isa<SCEVSignExtendExpr>(Y)) ||1137        (isa<SCEVZeroExtendExpr>(X) && isa<SCEVZeroExtendExpr>(Y))) {1138      const SCEVIntegralCastExpr *CX = cast<SCEVIntegralCastExpr>(X);1139      const SCEVIntegralCastExpr *CY = cast<SCEVIntegralCastExpr>(Y);1140      const SCEV *Xop = CX->getOperand();1141      const SCEV *Yop = CY->getOperand();1142      if (Xop->getType() == Yop->getType()) {1143        X = Xop;1144        Y = Yop;1145      }1146    }1147  }1148  if (SE->isKnownPredicate(Pred, X, Y))1149    return true;1150  // If SE->isKnownPredicate can't prove the condition,1151  // we try the brute-force approach of subtracting1152  // and testing the difference.1153  // By testing with SE->isKnownPredicate first, we avoid1154  // the possibility of overflow when the arguments are constants.1155  const SCEV *Delta = SE->getMinusSCEV(X, Y);1156  switch (Pred) {1157  case CmpInst::ICMP_EQ:1158    return Delta->isZero();1159  case CmpInst::ICMP_NE:1160    return SE->isKnownNonZero(Delta);1161  case CmpInst::ICMP_SGE:1162    return SE->isKnownNonNegative(Delta);1163  case CmpInst::ICMP_SLE:1164    return SE->isKnownNonPositive(Delta);1165  case CmpInst::ICMP_SGT:1166    return SE->isKnownPositive(Delta);1167  case CmpInst::ICMP_SLT:1168    return SE->isKnownNegative(Delta);1169  default:1170    llvm_unreachable("unexpected predicate in isKnownPredicate");1171  }1172}1173 1174// All subscripts are all the same type.1175// Loop bound may be smaller (e.g., a char).1176// Should zero extend loop bound, since it's always >= 0.1177// This routine collects upper bound and extends or truncates if needed.1178// Truncating is safe when subscripts are known not to wrap. Cases without1179// nowrap flags should have been rejected earlier.1180// Return null if no bound available.1181const SCEV *DependenceInfo::collectUpperBound(const Loop *L, Type *T) const {1182  if (SE->hasLoopInvariantBackedgeTakenCount(L)) {1183    const SCEV *UB = SE->getBackedgeTakenCount(L);1184    return SE->getTruncateOrZeroExtend(UB, T);1185  }1186  return nullptr;1187}1188 1189// Calls collectUpperBound(), then attempts to cast it to SCEVConstant.1190// If the cast fails, returns NULL.1191const SCEVConstant *DependenceInfo::collectConstantUpperBound(const Loop *L,1192                                                              Type *T) const {1193  if (const SCEV *UB = collectUpperBound(L, T))1194    return dyn_cast<SCEVConstant>(UB);1195  return nullptr;1196}1197 1198/// Returns \p A - \p B if it guaranteed not to signed wrap. Otherwise returns1199/// nullptr. \p A and \p B must have the same integer type.1200static const SCEV *minusSCEVNoSignedOverflow(const SCEV *A, const SCEV *B,1201                                             ScalarEvolution &SE) {1202  if (SE.willNotOverflow(Instruction::Sub, /*Signed=*/true, A, B))1203    return SE.getMinusSCEV(A, B);1204  return nullptr;1205}1206 1207/// Returns \p A * \p B if it guaranteed not to signed wrap. Otherwise returns1208/// nullptr. \p A and \p B must have the same integer type.1209static const SCEV *mulSCEVNoSignedOverflow(const SCEV *A, const SCEV *B,1210                                           ScalarEvolution &SE) {1211  if (SE.willNotOverflow(Instruction::Mul, /*Signed=*/true, A, B))1212    return SE.getMulExpr(A, B);1213  return nullptr;1214}1215 1216/// Returns the absolute value of \p A. In the context of dependence analysis,1217/// we need an absolute value in a mathematical sense. If \p A is the signed1218/// minimum value, we cannot represent it unless extending the original type.1219/// Thus if we cannot prove that \p A is not the signed minimum value, returns1220/// nullptr.1221static const SCEV *absSCEVNoSignedOverflow(const SCEV *A, ScalarEvolution &SE) {1222  IntegerType *Ty = cast<IntegerType>(A->getType());1223  if (!Ty)1224    return nullptr;1225 1226  const SCEV *SMin =1227      SE.getConstant(APInt::getSignedMinValue(Ty->getBitWidth()));1228  if (!SE.isKnownPredicate(CmpInst::ICMP_NE, A, SMin))1229    return nullptr;1230  return SE.getAbsExpr(A, /*IsNSW=*/true);1231}1232 1233/// Returns true iff \p Test is enabled.1234static bool isDependenceTestEnabled(DependenceTestType Test) {1235  if (EnableDependenceTest == DependenceTestType::All)1236    return true;1237  return EnableDependenceTest == Test;1238}1239 1240// testZIV -1241// When we have a pair of subscripts of the form [c1] and [c2],1242// where c1 and c2 are both loop invariant, we attack it using1243// the ZIV test. Basically, we test by comparing the two values,1244// but there are actually three possible results:1245// 1) the values are equal, so there's a dependence1246// 2) the values are different, so there's no dependence1247// 3) the values might be equal, so we have to assume a dependence.1248//1249// Return true if dependence disproved.1250bool DependenceInfo::testZIV(const SCEV *Src, const SCEV *Dst,1251                             FullDependence &Result) const {1252  LLVM_DEBUG(dbgs() << "    src = " << *Src << "\n");1253  LLVM_DEBUG(dbgs() << "    dst = " << *Dst << "\n");1254  ++ZIVapplications;1255  if (isKnownPredicate(CmpInst::ICMP_EQ, Src, Dst)) {1256    LLVM_DEBUG(dbgs() << "    provably dependent\n");1257    return false; // provably dependent1258  }1259  if (isKnownPredicate(CmpInst::ICMP_NE, Src, Dst)) {1260    LLVM_DEBUG(dbgs() << "    provably independent\n");1261    ++ZIVindependence;1262    return true; // provably independent1263  }1264  LLVM_DEBUG(dbgs() << "    possibly dependent\n");1265  Result.Consistent = false;1266  return false; // possibly dependent1267}1268 1269// strongSIVtest -1270// From the paper, Practical Dependence Testing, Section 4.2.11271//1272// When we have a pair of subscripts of the form [c1 + a*i] and [c2 + a*i],1273// where i is an induction variable, c1 and c2 are loop invariant,1274//  and a is a constant, we can solve it exactly using the Strong SIV test.1275//1276// Can prove independence. Failing that, can compute distance (and direction).1277// In the presence of symbolic terms, we can sometimes make progress.1278//1279// If there's a dependence,1280//1281//    c1 + a*i = c2 + a*i'1282//1283// The dependence distance is1284//1285//    d = i' - i = (c1 - c2)/a1286//1287// A dependence only exists if d is an integer and abs(d) <= U, where U is the1288// loop's upper bound. If a dependence exists, the dependence direction is1289// defined as1290//1291//                { < if d > 01292//    direction = { = if d = 01293//                { > if d < 01294//1295// Return true if dependence disproved.1296bool DependenceInfo::strongSIVtest(const SCEV *Coeff, const SCEV *SrcConst,1297                                   const SCEV *DstConst, const Loop *CurSrcLoop,1298                                   const Loop *CurDstLoop, unsigned Level,1299                                   FullDependence &Result) const {1300  if (!isDependenceTestEnabled(DependenceTestType::StrongSIV))1301    return false;1302 1303  LLVM_DEBUG(dbgs() << "\tStrong SIV test\n");1304  LLVM_DEBUG(dbgs() << "\t    Coeff = " << *Coeff);1305  LLVM_DEBUG(dbgs() << ", " << *Coeff->getType() << "\n");1306  LLVM_DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst);1307  LLVM_DEBUG(dbgs() << ", " << *SrcConst->getType() << "\n");1308  LLVM_DEBUG(dbgs() << "\t    DstConst = " << *DstConst);1309  LLVM_DEBUG(dbgs() << ", " << *DstConst->getType() << "\n");1310  ++StrongSIVapplications;1311  assert(0 < Level && Level <= CommonLevels && "level out of range");1312  Level--;1313 1314  const SCEV *Delta = minusSCEVNoSignedOverflow(SrcConst, DstConst, *SE);1315  if (!Delta) {1316    Result.Consistent = false;1317    return false;1318  }1319  LLVM_DEBUG(dbgs() << "\t    Delta = " << *Delta);1320  LLVM_DEBUG(dbgs() << ", " << *Delta->getType() << "\n");1321 1322  // check that |Delta| < iteration count1323  bool IsDeltaLarge = [&] {1324    const SCEV *UpperBound = collectUpperBound(CurSrcLoop, Delta->getType());1325    if (!UpperBound)1326      return false;1327 1328    LLVM_DEBUG(dbgs() << "\t    UpperBound = " << *UpperBound);1329    LLVM_DEBUG(dbgs() << ", " << *UpperBound->getType() << "\n");1330    const SCEV *AbsDelta = absSCEVNoSignedOverflow(Delta, *SE);1331    const SCEV *AbsCoeff = absSCEVNoSignedOverflow(Coeff, *SE);1332    if (!AbsDelta || !AbsCoeff)1333      return false;1334    const SCEV *Product = mulSCEVNoSignedOverflow(UpperBound, AbsCoeff, *SE);1335    if (!Product)1336      return false;1337    return isKnownPredicate(CmpInst::ICMP_SGT, AbsDelta, Product);1338  }();1339  if (IsDeltaLarge) {1340    // Distance greater than trip count - no dependence1341    ++StrongSIVindependence;1342    ++StrongSIVsuccesses;1343    return true;1344  }1345 1346  // Can we compute distance?1347  if (isa<SCEVConstant>(Delta) && isa<SCEVConstant>(Coeff)) {1348    APInt ConstDelta = cast<SCEVConstant>(Delta)->getAPInt();1349    APInt ConstCoeff = cast<SCEVConstant>(Coeff)->getAPInt();1350    APInt Distance = ConstDelta; // these need to be initialized1351    APInt Remainder = ConstDelta;1352    APInt::sdivrem(ConstDelta, ConstCoeff, Distance, Remainder);1353    LLVM_DEBUG(dbgs() << "\t    Distance = " << Distance << "\n");1354    LLVM_DEBUG(dbgs() << "\t    Remainder = " << Remainder << "\n");1355    // Make sure Coeff divides Delta exactly1356    if (Remainder != 0) {1357      // Coeff doesn't divide Distance, no dependence1358      ++StrongSIVindependence;1359      ++StrongSIVsuccesses;1360      return true;1361    }1362    Result.DV[Level].Distance = SE->getConstant(Distance);1363    if (Distance.sgt(0))1364      Result.DV[Level].Direction &= Dependence::DVEntry::LT;1365    else if (Distance.slt(0))1366      Result.DV[Level].Direction &= Dependence::DVEntry::GT;1367    else1368      Result.DV[Level].Direction &= Dependence::DVEntry::EQ;1369    ++StrongSIVsuccesses;1370  } else if (Delta->isZero()) {1371    // since 0/X == 01372    Result.DV[Level].Distance = Delta;1373    Result.DV[Level].Direction &= Dependence::DVEntry::EQ;1374    ++StrongSIVsuccesses;1375  } else {1376    if (Coeff->isOne()) {1377      LLVM_DEBUG(dbgs() << "\t    Distance = " << *Delta << "\n");1378      Result.DV[Level].Distance = Delta; // since X/1 == X1379    } else {1380      Result.Consistent = false;1381    }1382 1383    // maybe we can get a useful direction1384    bool DeltaMaybeZero = !SE->isKnownNonZero(Delta);1385    bool DeltaMaybePositive = !SE->isKnownNonPositive(Delta);1386    bool DeltaMaybeNegative = !SE->isKnownNonNegative(Delta);1387    bool CoeffMaybePositive = !SE->isKnownNonPositive(Coeff);1388    bool CoeffMaybeNegative = !SE->isKnownNonNegative(Coeff);1389    // The double negatives above are confusing.1390    // It helps to read !SE->isKnownNonZero(Delta)1391    // as "Delta might be Zero"1392    unsigned NewDirection = Dependence::DVEntry::NONE;1393    if ((DeltaMaybePositive && CoeffMaybePositive) ||1394        (DeltaMaybeNegative && CoeffMaybeNegative))1395      NewDirection = Dependence::DVEntry::LT;1396    if (DeltaMaybeZero)1397      NewDirection |= Dependence::DVEntry::EQ;1398    if ((DeltaMaybeNegative && CoeffMaybePositive) ||1399        (DeltaMaybePositive && CoeffMaybeNegative))1400      NewDirection |= Dependence::DVEntry::GT;1401    if (NewDirection < Result.DV[Level].Direction)1402      ++StrongSIVsuccesses;1403    Result.DV[Level].Direction &= NewDirection;1404  }1405  return false;1406}1407 1408// weakCrossingSIVtest -1409// From the paper, Practical Dependence Testing, Section 4.2.21410//1411// When we have a pair of subscripts of the form [c1 + a*i] and [c2 - a*i],1412// where i is an induction variable, c1 and c2 are loop invariant,1413// and a is a constant, we can solve it exactly using the1414// Weak-Crossing SIV test.1415//1416// Given c1 + a*i = c2 - a*i', we can look for the intersection of1417// the two lines, where i = i', yielding1418//1419//    c1 + a*i = c2 - a*i1420//    2a*i = c2 - c11421//    i = (c2 - c1)/2a1422//1423// If i < 0, there is no dependence.1424// If i > upperbound, there is no dependence.1425// If i = 0 (i.e., if c1 = c2), there's a dependence with distance = 0.1426// If i = upperbound, there's a dependence with distance = 0.1427// If i is integral, there's a dependence (all directions).1428// If the non-integer part = 1/2, there's a dependence (<> directions).1429// Otherwise, there's no dependence.1430//1431// Can prove independence. Failing that,1432// can sometimes refine the directions.1433// Can determine iteration for splitting.1434//1435// Return true if dependence disproved.1436bool DependenceInfo::weakCrossingSIVtest(const SCEV *Coeff,1437                                         const SCEV *SrcConst,1438                                         const SCEV *DstConst,1439                                         const Loop *CurSrcLoop,1440                                         const Loop *CurDstLoop, unsigned Level,1441                                         FullDependence &Result) const {1442  if (!isDependenceTestEnabled(DependenceTestType::WeakCrossingSIV))1443    return false;1444 1445  LLVM_DEBUG(dbgs() << "\tWeak-Crossing SIV test\n");1446  LLVM_DEBUG(dbgs() << "\t    Coeff = " << *Coeff << "\n");1447  LLVM_DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");1448  LLVM_DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");1449  ++WeakCrossingSIVapplications;1450  assert(0 < Level && Level <= CommonLevels && "Level out of range");1451  Level--;1452  Result.Consistent = false;1453  const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);1454  LLVM_DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");1455  if (Delta->isZero()) {1456    Result.DV[Level].Direction &= ~Dependence::DVEntry::LT;1457    Result.DV[Level].Direction &= ~Dependence::DVEntry::GT;1458    ++WeakCrossingSIVsuccesses;1459    if (!Result.DV[Level].Direction) {1460      ++WeakCrossingSIVindependence;1461      return true;1462    }1463    Result.DV[Level].Distance = Delta; // = 01464    return false;1465  }1466  const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(Coeff);1467  if (!ConstCoeff)1468    return false;1469 1470  if (SE->isKnownNegative(ConstCoeff)) {1471    ConstCoeff = dyn_cast<SCEVConstant>(SE->getNegativeSCEV(ConstCoeff));1472    assert(ConstCoeff &&1473           "dynamic cast of negative of ConstCoeff should yield constant");1474    Delta = SE->getNegativeSCEV(Delta);1475  }1476  assert(SE->isKnownPositive(ConstCoeff) && "ConstCoeff should be positive");1477 1478  const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);1479  if (!ConstDelta)1480    return false;1481 1482  // We're certain that ConstCoeff > 0; therefore,1483  // if Delta < 0, then no dependence.1484  LLVM_DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");1485  LLVM_DEBUG(dbgs() << "\t    ConstCoeff = " << *ConstCoeff << "\n");1486  if (SE->isKnownNegative(Delta)) {1487    // No dependence, Delta < 01488    ++WeakCrossingSIVindependence;1489    ++WeakCrossingSIVsuccesses;1490    return true;1491  }1492 1493  // We're certain that Delta > 0 and ConstCoeff > 0.1494  // Check Delta/(2*ConstCoeff) against upper loop bound1495  if (const SCEV *UpperBound =1496          collectUpperBound(CurSrcLoop, Delta->getType())) {1497    LLVM_DEBUG(dbgs() << "\t    UpperBound = " << *UpperBound << "\n");1498    const SCEV *ConstantTwo = SE->getConstant(UpperBound->getType(), 2);1499    const SCEV *ML =1500        SE->getMulExpr(SE->getMulExpr(ConstCoeff, UpperBound), ConstantTwo);1501    LLVM_DEBUG(dbgs() << "\t    ML = " << *ML << "\n");1502    if (isKnownPredicate(CmpInst::ICMP_SGT, Delta, ML)) {1503      // Delta too big, no dependence1504      ++WeakCrossingSIVindependence;1505      ++WeakCrossingSIVsuccesses;1506      return true;1507    }1508    if (isKnownPredicate(CmpInst::ICMP_EQ, Delta, ML)) {1509      // i = i' = UB1510      Result.DV[Level].Direction &= ~Dependence::DVEntry::LT;1511      Result.DV[Level].Direction &= ~Dependence::DVEntry::GT;1512      ++WeakCrossingSIVsuccesses;1513      if (!Result.DV[Level].Direction) {1514        ++WeakCrossingSIVindependence;1515        return true;1516      }1517      Result.DV[Level].Distance = SE->getZero(Delta->getType());1518      return false;1519    }1520  }1521 1522  // check that Coeff divides Delta1523  APInt APDelta = ConstDelta->getAPInt();1524  APInt APCoeff = ConstCoeff->getAPInt();1525  APInt Distance = APDelta; // these need to be initialzed1526  APInt Remainder = APDelta;1527  APInt::sdivrem(APDelta, APCoeff, Distance, Remainder);1528  LLVM_DEBUG(dbgs() << "\t    Remainder = " << Remainder << "\n");1529  if (Remainder != 0) {1530    // Coeff doesn't divide Delta, no dependence1531    ++WeakCrossingSIVindependence;1532    ++WeakCrossingSIVsuccesses;1533    return true;1534  }1535  LLVM_DEBUG(dbgs() << "\t    Distance = " << Distance << "\n");1536 1537  // if 2*Coeff doesn't divide Delta, then the equal direction isn't possible1538  APInt Two = APInt(Distance.getBitWidth(), 2, true);1539  Remainder = Distance.srem(Two);1540  LLVM_DEBUG(dbgs() << "\t    Remainder = " << Remainder << "\n");1541  if (Remainder != 0) {1542    // Equal direction isn't possible1543    Result.DV[Level].Direction &= ~Dependence::DVEntry::EQ;1544    ++WeakCrossingSIVsuccesses;1545  }1546  return false;1547}1548 1549// Kirch's algorithm, from1550//1551//        Optimizing Supercompilers for Supercomputers1552//        Michael Wolfe1553//        MIT Press, 19891554//1555// Program 2.1, page 29.1556// Computes the GCD of AM and BM.1557// Also finds a solution to the equation ax - by = gcd(a, b).1558// Returns true if dependence disproved; i.e., gcd does not divide Delta.1559static bool findGCD(unsigned Bits, const APInt &AM, const APInt &BM,1560                    const APInt &Delta, APInt &G, APInt &X, APInt &Y) {1561  APInt A0(Bits, 1, true), A1(Bits, 0, true);1562  APInt B0(Bits, 0, true), B1(Bits, 1, true);1563  APInt G0 = AM.abs();1564  APInt G1 = BM.abs();1565  APInt Q = G0; // these need to be initialized1566  APInt R = G0;1567  APInt::sdivrem(G0, G1, Q, R);1568  while (R != 0) {1569    // clang-format off1570    APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2;1571    APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2;1572    G0 = G1; G1 = R;1573    // clang-format on1574    APInt::sdivrem(G0, G1, Q, R);1575  }1576  G = G1;1577  LLVM_DEBUG(dbgs() << "\t    GCD = " << G << "\n");1578  X = AM.slt(0) ? -A1 : A1;1579  Y = BM.slt(0) ? B1 : -B1;1580 1581  // make sure gcd divides Delta1582  R = Delta.srem(G);1583  if (R != 0)1584    return true; // gcd doesn't divide Delta, no dependence1585  Q = Delta.sdiv(G);1586  return false;1587}1588 1589static APInt floorOfQuotient(const APInt &A, const APInt &B) {1590  APInt Q = A; // these need to be initialized1591  APInt R = A;1592  APInt::sdivrem(A, B, Q, R);1593  if (R == 0)1594    return Q;1595  if ((A.sgt(0) && B.sgt(0)) || (A.slt(0) && B.slt(0)))1596    return Q;1597  else1598    return Q - 1;1599}1600 1601static APInt ceilingOfQuotient(const APInt &A, const APInt &B) {1602  APInt Q = A; // these need to be initialized1603  APInt R = A;1604  APInt::sdivrem(A, B, Q, R);1605  if (R == 0)1606    return Q;1607  if ((A.sgt(0) && B.sgt(0)) || (A.slt(0) && B.slt(0)))1608    return Q + 1;1609  else1610    return Q;1611}1612 1613/// Given an affine expression of the form A*k + B, where k is an arbitrary1614/// integer, infer the possible range of k based on the known range of the1615/// affine expression. If we know A*k + B is non-negative, i.e.,1616///1617///   A*k + B >= 01618///1619/// we can derive the following inequalities for k when A is positive:1620///1621///   k >= -B / A1622///1623/// Since k is an integer, it means k is greater than or equal to the1624/// ceil(-B / A).1625///1626/// If the upper bound of the affine expression \p UB is passed, the following1627/// inequality can be derived as well:1628///1629///   A*k + B <= UB1630///1631/// which leads to:1632///1633///   k <= (UB - B) / A1634///1635/// Again, as k is an integer, it means k is less than or equal to the1636/// floor((UB - B) / A).1637///1638/// The similar logic applies when A is negative, but the inequalities sign flip1639/// while working with them.1640///1641/// Preconditions: \p A is non-zero, and we know A*k + B is non-negative.1642static std::pair<std::optional<APInt>, std::optional<APInt>>1643inferDomainOfAffine(const APInt &A, const APInt &B,1644                    const std::optional<APInt> &UB) {1645  assert(A != 0 && "A must be non-zero");1646  std::optional<APInt> TL, TU;1647  if (A.sgt(0)) {1648    TL = ceilingOfQuotient(-B, A);1649    LLVM_DEBUG(dbgs() << "\t    Possible TL = " << *TL << "\n");1650    // New bound check - modification to Banerjee's e3 check1651    if (UB) {1652      // TODO?: Overflow check for UB - B1653      TU = floorOfQuotient(*UB - B, A);1654      LLVM_DEBUG(dbgs() << "\t    Possible TU = " << *TU << "\n");1655    }1656  } else {1657    TU = floorOfQuotient(-B, A);1658    LLVM_DEBUG(dbgs() << "\t    Possible TU = " << *TU << "\n");1659    // New bound check - modification to Banerjee's e3 check1660    if (UB) {1661      // TODO?: Overflow check for UB - B1662      TL = ceilingOfQuotient(*UB - B, A);1663      LLVM_DEBUG(dbgs() << "\t    Possible TL = " << *TL << "\n");1664    }1665  }1666  return std::make_pair(TL, TU);1667}1668 1669// exactSIVtest -1670// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*i],1671// where i is an induction variable, c1 and c2 are loop invariant, and a11672// and a2 are constant, we can solve it exactly using an algorithm developed1673// by Banerjee and Wolfe. See Algorithm 6.2.1 (case 2.5) in:1674//1675//        Dependence Analysis for Supercomputing1676//        Utpal Banerjee1677//        Kluwer Academic Publishers, 19881678//1679// It's slower than the specialized tests (strong SIV, weak-zero SIV, etc),1680// so use them if possible. They're also a bit better with symbolics and,1681// in the case of the strong SIV test, can compute Distances.1682//1683// Return true if dependence disproved.1684//1685// This is a modified version of the original Banerjee algorithm. The original1686// only tested whether Dst depends on Src. This algorithm extends that and1687// returns all the dependencies that exist between Dst and Src.1688bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,1689                                  const SCEV *SrcConst, const SCEV *DstConst,1690                                  const Loop *CurSrcLoop,1691                                  const Loop *CurDstLoop, unsigned Level,1692                                  FullDependence &Result) const {1693  if (!isDependenceTestEnabled(DependenceTestType::ExactSIV))1694    return false;1695 1696  LLVM_DEBUG(dbgs() << "\tExact SIV test\n");1697  LLVM_DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << " = AM\n");1698  LLVM_DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << " = BM\n");1699  LLVM_DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");1700  LLVM_DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");1701  ++ExactSIVapplications;1702  assert(0 < Level && Level <= CommonLevels && "Level out of range");1703  Level--;1704  Result.Consistent = false;1705  const SCEV *Delta = minusSCEVNoSignedOverflow(DstConst, SrcConst, *SE);1706  if (!Delta)1707    return false;1708  LLVM_DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");1709  const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);1710  const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);1711  const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);1712  if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)1713    return false;1714 1715  // find gcd1716  APInt G, X, Y;1717  APInt AM = ConstSrcCoeff->getAPInt();1718  APInt BM = ConstDstCoeff->getAPInt();1719  APInt CM = ConstDelta->getAPInt();1720  unsigned Bits = AM.getBitWidth();1721  if (findGCD(Bits, AM, BM, CM, G, X, Y)) {1722    // gcd doesn't divide Delta, no dependence1723    ++ExactSIVindependence;1724    ++ExactSIVsuccesses;1725    return true;1726  }1727 1728  LLVM_DEBUG(dbgs() << "\t    X = " << X << ", Y = " << Y << "\n");1729 1730  // since SCEV construction normalizes, LM = 01731  std::optional<APInt> UM;1732  // UM is perhaps unavailable, let's check1733  if (const SCEVConstant *CUB =1734          collectConstantUpperBound(CurSrcLoop, Delta->getType())) {1735    UM = CUB->getAPInt();1736    LLVM_DEBUG(dbgs() << "\t    UM = " << *UM << "\n");1737  }1738 1739  APInt TU(APInt::getSignedMaxValue(Bits));1740  APInt TL(APInt::getSignedMinValue(Bits));1741  APInt TC = CM.sdiv(G);1742  APInt TX = X * TC;1743  APInt TY = Y * TC;1744  LLVM_DEBUG(dbgs() << "\t    TC = " << TC << "\n");1745  LLVM_DEBUG(dbgs() << "\t    TX = " << TX << "\n");1746  LLVM_DEBUG(dbgs() << "\t    TY = " << TY << "\n");1747 1748  APInt TB = BM.sdiv(G);1749  APInt TA = AM.sdiv(G);1750 1751  // At this point, we have the following equations:1752  //1753  //   TA*i0 - TB*i1 = TC1754  //1755  // Also, we know that the all pairs of (i0, i1) can be expressed as:1756  //1757  //   (TX + k*TB, TY + k*TA)1758  //1759  // where k is an arbitrary integer.1760  auto [TL0, TU0] = inferDomainOfAffine(TB, TX, UM);1761  auto [TL1, TU1] = inferDomainOfAffine(TA, TY, UM);1762 1763  auto CreateVec = [](const std::optional<APInt> &V0,1764                      const std::optional<APInt> &V1) {1765    SmallVector<APInt, 2> Vec;1766    if (V0)1767      Vec.push_back(*V0);1768    if (V1)1769      Vec.push_back(*V1);1770    return Vec;1771  };1772 1773  SmallVector<APInt, 2> TLVec = CreateVec(TL0, TL1);1774  SmallVector<APInt, 2> TUVec = CreateVec(TU0, TU1);1775 1776  LLVM_DEBUG(dbgs() << "\t    TA = " << TA << "\n");1777  LLVM_DEBUG(dbgs() << "\t    TB = " << TB << "\n");1778 1779  if (TLVec.empty() || TUVec.empty())1780    return false;1781  TL = APIntOps::smax(TLVec.front(), TLVec.back());1782  TU = APIntOps::smin(TUVec.front(), TUVec.back());1783  LLVM_DEBUG(dbgs() << "\t    TL = " << TL << "\n");1784  LLVM_DEBUG(dbgs() << "\t    TU = " << TU << "\n");1785 1786  if (TL.sgt(TU)) {1787    ++ExactSIVindependence;1788    ++ExactSIVsuccesses;1789    return true;1790  }1791 1792  // explore directions1793  unsigned NewDirection = Dependence::DVEntry::NONE;1794  APInt LowerDistance, UpperDistance;1795  // TODO: Overflow check may be needed.1796  if (TA.sgt(TB)) {1797    LowerDistance = (TY - TX) + (TA - TB) * TL;1798    UpperDistance = (TY - TX) + (TA - TB) * TU;1799  } else {1800    LowerDistance = (TY - TX) + (TA - TB) * TU;1801    UpperDistance = (TY - TX) + (TA - TB) * TL;1802  }1803 1804  LLVM_DEBUG(dbgs() << "\t    LowerDistance = " << LowerDistance << "\n");1805  LLVM_DEBUG(dbgs() << "\t    UpperDistance = " << UpperDistance << "\n");1806 1807  APInt Zero(Bits, 0, true);1808  if (LowerDistance.sle(Zero) && UpperDistance.sge(Zero)) {1809    NewDirection |= Dependence::DVEntry::EQ;1810    ++ExactSIVsuccesses;1811  }1812  if (LowerDistance.slt(0)) {1813    NewDirection |= Dependence::DVEntry::GT;1814    ++ExactSIVsuccesses;1815  }1816  if (UpperDistance.sgt(0)) {1817    NewDirection |= Dependence::DVEntry::LT;1818    ++ExactSIVsuccesses;1819  }1820 1821  // finished1822  Result.DV[Level].Direction &= NewDirection;1823  if (Result.DV[Level].Direction == Dependence::DVEntry::NONE)1824    ++ExactSIVindependence;1825  LLVM_DEBUG(dbgs() << "\t    Result = ");1826  LLVM_DEBUG(Result.dump(dbgs()));1827  return Result.DV[Level].Direction == Dependence::DVEntry::NONE;1828}1829 1830// Return true if the divisor evenly divides the dividend.1831static bool isRemainderZero(const SCEVConstant *Dividend,1832                            const SCEVConstant *Divisor) {1833  const APInt &ConstDividend = Dividend->getAPInt();1834  const APInt &ConstDivisor = Divisor->getAPInt();1835  return ConstDividend.srem(ConstDivisor) == 0;1836}1837 1838// weakZeroSrcSIVtest -1839// From the paper, Practical Dependence Testing, Section 4.2.21840//1841// When we have a pair of subscripts of the form [c1] and [c2 + a*i],1842// where i is an induction variable, c1 and c2 are loop invariant,1843// and a is a constant, we can solve it exactly using the1844// Weak-Zero SIV test.1845//1846// Given1847//1848//    c1 = c2 + a*i1849//1850// we get1851//1852//    (c1 - c2)/a = i1853//1854// If i is not an integer, there's no dependence.1855// If i < 0 or > UB, there's no dependence.1856// If i = 0, the direction is >= and peeling the1857// 1st iteration will break the dependence.1858// If i = UB, the direction is <= and peeling the1859// last iteration will break the dependence.1860// Otherwise, the direction is *.1861//1862// Can prove independence. Failing that, we can sometimes refine1863// the directions. Can sometimes show that first or last1864// iteration carries all the dependences (so worth peeling).1865//1866// (see also weakZeroDstSIVtest)1867//1868// Return true if dependence disproved.1869bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *DstCoeff,1870                                        const SCEV *SrcConst,1871                                        const SCEV *DstConst,1872                                        const Loop *CurSrcLoop,1873                                        const Loop *CurDstLoop, unsigned Level,1874                                        FullDependence &Result) const {1875  if (!isDependenceTestEnabled(DependenceTestType::WeakZeroSIV))1876    return false;1877 1878  // For the WeakSIV test, it's possible the loop isn't common to1879  // the Src and Dst loops. If it isn't, then there's no need to1880  // record a direction.1881  LLVM_DEBUG(dbgs() << "\tWeak-Zero (src) SIV test\n");1882  LLVM_DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << "\n");1883  LLVM_DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");1884  LLVM_DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");1885  ++WeakZeroSIVapplications;1886  assert(0 < Level && Level <= MaxLevels && "Level out of range");1887  Level--;1888  Result.Consistent = false;1889  const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst);1890  LLVM_DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");1891  if (isKnownPredicate(CmpInst::ICMP_EQ, SrcConst, DstConst)) {1892    if (Level < CommonLevels) {1893      Result.DV[Level].Direction &= Dependence::DVEntry::GE;1894      Result.DV[Level].PeelFirst = true;1895      ++WeakZeroSIVsuccesses;1896    }1897    return false; // dependences caused by first iteration1898  }1899  const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(DstCoeff);1900  if (!ConstCoeff)1901    return false;1902 1903  // Since ConstCoeff is constant, !isKnownNegative means it's non-negative.1904  // TODO: Bail out if it's a signed minimum value.1905  const SCEV *AbsCoeff = SE->isKnownNegative(ConstCoeff)1906                             ? SE->getNegativeSCEV(ConstCoeff)1907                             : ConstCoeff;1908  const SCEV *NewDelta =1909      SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta;1910 1911  // check that Delta/SrcCoeff < iteration count1912  // really check NewDelta < count*AbsCoeff1913  if (const SCEV *UpperBound =1914          collectUpperBound(CurSrcLoop, Delta->getType())) {1915    LLVM_DEBUG(dbgs() << "\t    UpperBound = " << *UpperBound << "\n");1916    const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound);1917    if (isKnownPredicate(CmpInst::ICMP_SGT, NewDelta, Product)) {1918      ++WeakZeroSIVindependence;1919      ++WeakZeroSIVsuccesses;1920      return true;1921    }1922    if (isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) {1923      // dependences caused by last iteration1924      if (Level < CommonLevels) {1925        Result.DV[Level].Direction &= Dependence::DVEntry::LE;1926        Result.DV[Level].PeelLast = true;1927        ++WeakZeroSIVsuccesses;1928      }1929      return false;1930    }1931  }1932 1933  // check that Delta/SrcCoeff >= 01934  // really check that NewDelta >= 01935  if (SE->isKnownNegative(NewDelta)) {1936    // No dependence, newDelta < 01937    ++WeakZeroSIVindependence;1938    ++WeakZeroSIVsuccesses;1939    return true;1940  }1941 1942  // if SrcCoeff doesn't divide Delta, then no dependence1943  if (isa<SCEVConstant>(Delta) &&1944      !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) {1945    ++WeakZeroSIVindependence;1946    ++WeakZeroSIVsuccesses;1947    return true;1948  }1949  return false;1950}1951 1952// weakZeroDstSIVtest -1953// From the paper, Practical Dependence Testing, Section 4.2.21954//1955// When we have a pair of subscripts of the form [c1 + a*i] and [c2],1956// where i is an induction variable, c1 and c2 are loop invariant,1957// and a is a constant, we can solve it exactly using the1958// Weak-Zero SIV test.1959//1960// Given1961//1962//    c1 + a*i = c21963//1964// we get1965//1966//    i = (c2 - c1)/a1967//1968// If i is not an integer, there's no dependence.1969// If i < 0 or > UB, there's no dependence.1970// If i = 0, the direction is <= and peeling the1971// 1st iteration will break the dependence.1972// If i = UB, the direction is >= and peeling the1973// last iteration will break the dependence.1974// Otherwise, the direction is *.1975//1976// Can prove independence. Failing that, we can sometimes refine1977// the directions. Can sometimes show that first or last1978// iteration carries all the dependences (so worth peeling).1979//1980// (see also weakZeroSrcSIVtest)1981//1982// Return true if dependence disproved.1983bool DependenceInfo::weakZeroDstSIVtest(const SCEV *SrcCoeff,1984                                        const SCEV *SrcConst,1985                                        const SCEV *DstConst,1986                                        const Loop *CurSrcLoop,1987                                        const Loop *CurDstLoop, unsigned Level,1988                                        FullDependence &Result) const {1989  if (!isDependenceTestEnabled(DependenceTestType::WeakZeroSIV))1990    return false;1991 1992  // For the WeakSIV test, it's possible the loop isn't common to the1993  // Src and Dst loops. If it isn't, then there's no need to record a direction.1994  LLVM_DEBUG(dbgs() << "\tWeak-Zero (dst) SIV test\n");1995  LLVM_DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << "\n");1996  LLVM_DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");1997  LLVM_DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");1998  ++WeakZeroSIVapplications;1999  assert(0 < Level && Level <= SrcLevels && "Level out of range");2000  Level--;2001  Result.Consistent = false;2002  const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);2003  LLVM_DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");2004  if (isKnownPredicate(CmpInst::ICMP_EQ, DstConst, SrcConst)) {2005    if (Level < CommonLevels) {2006      Result.DV[Level].Direction &= Dependence::DVEntry::LE;2007      Result.DV[Level].PeelFirst = true;2008      ++WeakZeroSIVsuccesses;2009    }2010    return false; // dependences caused by first iteration2011  }2012  const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(SrcCoeff);2013  if (!ConstCoeff)2014    return false;2015 2016  // Since ConstCoeff is constant, !isKnownNegative means it's non-negative.2017  // TODO: Bail out if it's a signed minimum value.2018  const SCEV *AbsCoeff = SE->isKnownNegative(ConstCoeff)2019                             ? SE->getNegativeSCEV(ConstCoeff)2020                             : ConstCoeff;2021  const SCEV *NewDelta =2022      SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta;2023 2024  // check that Delta/SrcCoeff < iteration count2025  // really check NewDelta < count*AbsCoeff2026  if (const SCEV *UpperBound =2027          collectUpperBound(CurSrcLoop, Delta->getType())) {2028    LLVM_DEBUG(dbgs() << "\t    UpperBound = " << *UpperBound << "\n");2029    const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound);2030    if (isKnownPredicate(CmpInst::ICMP_SGT, NewDelta, Product)) {2031      ++WeakZeroSIVindependence;2032      ++WeakZeroSIVsuccesses;2033      return true;2034    }2035    if (isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) {2036      // dependences caused by last iteration2037      if (Level < CommonLevels) {2038        Result.DV[Level].Direction &= Dependence::DVEntry::GE;2039        Result.DV[Level].PeelLast = true;2040        ++WeakZeroSIVsuccesses;2041      }2042      return false;2043    }2044  }2045 2046  // check that Delta/SrcCoeff >= 02047  // really check that NewDelta >= 02048  if (SE->isKnownNegative(NewDelta)) {2049    // No dependence, newDelta < 02050    ++WeakZeroSIVindependence;2051    ++WeakZeroSIVsuccesses;2052    return true;2053  }2054 2055  // if SrcCoeff doesn't divide Delta, then no dependence2056  if (isa<SCEVConstant>(Delta) &&2057      !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) {2058    ++WeakZeroSIVindependence;2059    ++WeakZeroSIVsuccesses;2060    return true;2061  }2062  return false;2063}2064 2065// exactRDIVtest - Tests the RDIV subscript pair for dependence.2066// Things of the form [c1 + a*i] and [c2 + b*j],2067// where i and j are induction variable, c1 and c2 are loop invariant,2068// and a and b are constants.2069// Returns true if any possible dependence is disproved.2070// Marks the result as inconsistent.2071// Works in some cases that symbolicRDIVtest doesn't, and vice versa.2072bool DependenceInfo::exactRDIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,2073                                   const SCEV *SrcConst, const SCEV *DstConst,2074                                   const Loop *SrcLoop, const Loop *DstLoop,2075                                   FullDependence &Result) const {2076  if (!isDependenceTestEnabled(DependenceTestType::ExactRDIV))2077    return false;2078 2079  LLVM_DEBUG(dbgs() << "\tExact RDIV test\n");2080  LLVM_DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << " = AM\n");2081  LLVM_DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << " = BM\n");2082  LLVM_DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");2083  LLVM_DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");2084  ++ExactRDIVapplications;2085  Result.Consistent = false;2086  const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);2087  LLVM_DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");2088  const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);2089  const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);2090  const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);2091  if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)2092    return false;2093 2094  // find gcd2095  APInt G, X, Y;2096  APInt AM = ConstSrcCoeff->getAPInt();2097  APInt BM = ConstDstCoeff->getAPInt();2098  APInt CM = ConstDelta->getAPInt();2099  unsigned Bits = AM.getBitWidth();2100  if (findGCD(Bits, AM, BM, CM, G, X, Y)) {2101    // gcd doesn't divide Delta, no dependence2102    ++ExactRDIVindependence;2103    return true;2104  }2105 2106  LLVM_DEBUG(dbgs() << "\t    X = " << X << ", Y = " << Y << "\n");2107 2108  // since SCEV construction seems to normalize, LM = 02109  std::optional<APInt> SrcUM;2110  // SrcUM is perhaps unavailable, let's check2111  if (const SCEVConstant *UpperBound =2112          collectConstantUpperBound(SrcLoop, Delta->getType())) {2113    SrcUM = UpperBound->getAPInt();2114    LLVM_DEBUG(dbgs() << "\t    SrcUM = " << *SrcUM << "\n");2115  }2116 2117  std::optional<APInt> DstUM;2118  // UM is perhaps unavailable, let's check2119  if (const SCEVConstant *UpperBound =2120          collectConstantUpperBound(DstLoop, Delta->getType())) {2121    DstUM = UpperBound->getAPInt();2122    LLVM_DEBUG(dbgs() << "\t    DstUM = " << *DstUM << "\n");2123  }2124 2125  APInt TU(APInt::getSignedMaxValue(Bits));2126  APInt TL(APInt::getSignedMinValue(Bits));2127  APInt TC = CM.sdiv(G);2128  APInt TX = X * TC;2129  APInt TY = Y * TC;2130  LLVM_DEBUG(dbgs() << "\t    TC = " << TC << "\n");2131  LLVM_DEBUG(dbgs() << "\t    TX = " << TX << "\n");2132  LLVM_DEBUG(dbgs() << "\t    TY = " << TY << "\n");2133 2134  APInt TB = BM.sdiv(G);2135  APInt TA = AM.sdiv(G);2136 2137  // At this point, we have the following equations:2138  //2139  //   TA*i - TB*j = TC2140  //2141  // Also, we know that the all pairs of (i, j) can be expressed as:2142  //2143  //   (TX + k*TB, TY + k*TA)2144  //2145  // where k is an arbitrary integer.2146  auto [TL0, TU0] = inferDomainOfAffine(TB, TX, SrcUM);2147  auto [TL1, TU1] = inferDomainOfAffine(TA, TY, DstUM);2148 2149  LLVM_DEBUG(dbgs() << "\t    TA = " << TA << "\n");2150  LLVM_DEBUG(dbgs() << "\t    TB = " << TB << "\n");2151 2152  auto CreateVec = [](const std::optional<APInt> &V0,2153                      const std::optional<APInt> &V1) {2154    SmallVector<APInt, 2> Vec;2155    if (V0)2156      Vec.push_back(*V0);2157    if (V1)2158      Vec.push_back(*V1);2159    return Vec;2160  };2161 2162  SmallVector<APInt, 2> TLVec = CreateVec(TL0, TL1);2163  SmallVector<APInt, 2> TUVec = CreateVec(TU0, TU1);2164  if (TLVec.empty() || TUVec.empty())2165    return false;2166 2167  TL = APIntOps::smax(TLVec.front(), TLVec.back());2168  TU = APIntOps::smin(TUVec.front(), TUVec.back());2169  LLVM_DEBUG(dbgs() << "\t    TL = " << TL << "\n");2170  LLVM_DEBUG(dbgs() << "\t    TU = " << TU << "\n");2171 2172  if (TL.sgt(TU))2173    ++ExactRDIVindependence;2174  return TL.sgt(TU);2175}2176 2177// symbolicRDIVtest -2178// In Section 4.5 of the Practical Dependence Testing paper,the authors2179// introduce a special case of Banerjee's Inequalities (also called the2180// Extreme-Value Test) that can handle some of the SIV and RDIV cases,2181// particularly cases with symbolics. Since it's only able to disprove2182// dependence (not compute distances or directions), we'll use it as a2183// fall back for the other tests.2184//2185// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j]2186// where i and j are induction variables and c1 and c2 are loop invariants,2187// we can use the symbolic tests to disprove some dependences, serving as a2188// backup for the RDIV test. Note that i and j can be the same variable,2189// letting this test serve as a backup for the various SIV tests.2190//2191// For a dependence to exist, c1 + a1*i must equal c2 + a2*j for some2192//  0 <= i <= N1 and some 0 <= j <= N2, where N1 and N2 are the (normalized)2193// loop bounds for the i and j loops, respectively. So, ...2194//2195// c1 + a1*i = c2 + a2*j2196// a1*i - a2*j = c2 - c12197//2198// To test for a dependence, we compute c2 - c1 and make sure it's in the2199// range of the maximum and minimum possible values of a1*i - a2*j.2200// Considering the signs of a1 and a2, we have 4 possible cases:2201//2202// 1) If a1 >= 0 and a2 >= 0, then2203//        a1*0 - a2*N2 <= c2 - c1 <= a1*N1 - a2*02204//              -a2*N2 <= c2 - c1 <= a1*N12205//2206// 2) If a1 >= 0 and a2 <= 0, then2207//        a1*0 - a2*0 <= c2 - c1 <= a1*N1 - a2*N22208//                  0 <= c2 - c1 <= a1*N1 - a2*N22209//2210// 3) If a1 <= 0 and a2 >= 0, then2211//        a1*N1 - a2*N2 <= c2 - c1 <= a1*0 - a2*02212//        a1*N1 - a2*N2 <= c2 - c1 <= 02213//2214// 4) If a1 <= 0 and a2 <= 0, then2215//        a1*N1 - a2*0  <= c2 - c1 <= a1*0 - a2*N22216//        a1*N1         <= c2 - c1 <=       -a2*N22217//2218// return true if dependence disproved2219bool DependenceInfo::symbolicRDIVtest(const SCEV *A1, const SCEV *A2,2220                                      const SCEV *C1, const SCEV *C2,2221                                      const Loop *Loop1,2222                                      const Loop *Loop2) const {2223  if (!isDependenceTestEnabled(DependenceTestType::SymbolicRDIV))2224    return false;2225 2226  ++SymbolicRDIVapplications;2227  LLVM_DEBUG(dbgs() << "\ttry symbolic RDIV test\n");2228  LLVM_DEBUG(dbgs() << "\t    A1 = " << *A1);2229  LLVM_DEBUG(dbgs() << ", type = " << *A1->getType() << "\n");2230  LLVM_DEBUG(dbgs() << "\t    A2 = " << *A2 << "\n");2231  LLVM_DEBUG(dbgs() << "\t    C1 = " << *C1 << "\n");2232  LLVM_DEBUG(dbgs() << "\t    C2 = " << *C2 << "\n");2233  const SCEV *N1 = collectUpperBound(Loop1, A1->getType());2234  const SCEV *N2 = collectUpperBound(Loop2, A1->getType());2235  LLVM_DEBUG(if (N1) dbgs() << "\t    N1 = " << *N1 << "\n");2236  LLVM_DEBUG(if (N2) dbgs() << "\t    N2 = " << *N2 << "\n");2237  const SCEV *C2_C1 = SE->getMinusSCEV(C2, C1);2238  const SCEV *C1_C2 = SE->getMinusSCEV(C1, C2);2239  LLVM_DEBUG(dbgs() << "\t    C2 - C1 = " << *C2_C1 << "\n");2240  LLVM_DEBUG(dbgs() << "\t    C1 - C2 = " << *C1_C2 << "\n");2241  if (SE->isKnownNonNegative(A1)) {2242    if (SE->isKnownNonNegative(A2)) {2243      // A1 >= 0 && A2 >= 02244      if (N1) {2245        // make sure that c2 - c1 <= a1*N12246        const SCEV *A1N1 = SE->getMulExpr(A1, N1);2247        LLVM_DEBUG(dbgs() << "\t    A1*N1 = " << *A1N1 << "\n");2248        if (isKnownPredicate(CmpInst::ICMP_SGT, C2_C1, A1N1)) {2249          ++SymbolicRDIVindependence;2250          return true;2251        }2252      }2253      if (N2) {2254        // make sure that -a2*N2 <= c2 - c1, or a2*N2 >= c1 - c22255        const SCEV *A2N2 = SE->getMulExpr(A2, N2);2256        LLVM_DEBUG(dbgs() << "\t    A2*N2 = " << *A2N2 << "\n");2257        if (isKnownPredicate(CmpInst::ICMP_SLT, A2N2, C1_C2)) {2258          ++SymbolicRDIVindependence;2259          return true;2260        }2261      }2262    } else if (SE->isKnownNonPositive(A2)) {2263      // a1 >= 0 && a2 <= 02264      if (N1 && N2) {2265        // make sure that c2 - c1 <= a1*N1 - a2*N22266        const SCEV *A1N1 = SE->getMulExpr(A1, N1);2267        const SCEV *A2N2 = SE->getMulExpr(A2, N2);2268        const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2);2269        LLVM_DEBUG(dbgs() << "\t    A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n");2270        if (isKnownPredicate(CmpInst::ICMP_SGT, C2_C1, A1N1_A2N2)) {2271          ++SymbolicRDIVindependence;2272          return true;2273        }2274      }2275      // make sure that 0 <= c2 - c12276      if (SE->isKnownNegative(C2_C1)) {2277        ++SymbolicRDIVindependence;2278        return true;2279      }2280    }2281  } else if (SE->isKnownNonPositive(A1)) {2282    if (SE->isKnownNonNegative(A2)) {2283      // a1 <= 0 && a2 >= 02284      if (N1 && N2) {2285        // make sure that a1*N1 - a2*N2 <= c2 - c12286        const SCEV *A1N1 = SE->getMulExpr(A1, N1);2287        const SCEV *A2N2 = SE->getMulExpr(A2, N2);2288        const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2);2289        LLVM_DEBUG(dbgs() << "\t    A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n");2290        if (isKnownPredicate(CmpInst::ICMP_SGT, A1N1_A2N2, C2_C1)) {2291          ++SymbolicRDIVindependence;2292          return true;2293        }2294      }2295      // make sure that c2 - c1 <= 02296      if (SE->isKnownPositive(C2_C1)) {2297        ++SymbolicRDIVindependence;2298        return true;2299      }2300    } else if (SE->isKnownNonPositive(A2)) {2301      // a1 <= 0 && a2 <= 02302      if (N1) {2303        // make sure that a1*N1 <= c2 - c12304        const SCEV *A1N1 = SE->getMulExpr(A1, N1);2305        LLVM_DEBUG(dbgs() << "\t    A1*N1 = " << *A1N1 << "\n");2306        if (isKnownPredicate(CmpInst::ICMP_SGT, A1N1, C2_C1)) {2307          ++SymbolicRDIVindependence;2308          return true;2309        }2310      }2311      if (N2) {2312        // make sure that c2 - c1 <= -a2*N2, or c1 - c2 >= a2*N22313        const SCEV *A2N2 = SE->getMulExpr(A2, N2);2314        LLVM_DEBUG(dbgs() << "\t    A2*N2 = " << *A2N2 << "\n");2315        if (isKnownPredicate(CmpInst::ICMP_SLT, C1_C2, A2N2)) {2316          ++SymbolicRDIVindependence;2317          return true;2318        }2319      }2320    }2321  }2322  return false;2323}2324 2325// testSIV -2326// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 - a2*i]2327// where i is an induction variable, c1 and c2 are loop invariant, and a1 and2328// a2 are constant, we attack it with an SIV test. While they can all be2329// solved with the Exact SIV test, it's worthwhile to use simpler tests when2330// they apply; they're cheaper and sometimes more precise.2331//2332// Return true if dependence disproved.2333bool DependenceInfo::testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level,2334                             FullDependence &Result) const {2335  LLVM_DEBUG(dbgs() << "    src = " << *Src << "\n");2336  LLVM_DEBUG(dbgs() << "    dst = " << *Dst << "\n");2337  const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src);2338  const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst);2339  if (SrcAddRec && DstAddRec) {2340    const SCEV *SrcConst = SrcAddRec->getStart();2341    const SCEV *DstConst = DstAddRec->getStart();2342    const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE);2343    const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE);2344    const Loop *CurSrcLoop = SrcAddRec->getLoop();2345    const Loop *CurDstLoop = DstAddRec->getLoop();2346    assert(haveSameSD(CurSrcLoop, CurDstLoop) &&2347           "Loops in the SIV test should have the same iteration space and "2348           "depth");2349    Level = mapSrcLoop(CurSrcLoop);2350    bool disproven;2351    if (SrcCoeff == DstCoeff)2352      disproven = strongSIVtest(SrcCoeff, SrcConst, DstConst, CurSrcLoop,2353                                CurDstLoop, Level, Result);2354    else if (SrcCoeff == SE->getNegativeSCEV(DstCoeff))2355      disproven = weakCrossingSIVtest(SrcCoeff, SrcConst, DstConst, CurSrcLoop,2356                                      CurDstLoop, Level, Result);2357    else2358      disproven = exactSIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst,2359                               CurSrcLoop, CurDstLoop, Level, Result);2360    return disproven || gcdMIVtest(Src, Dst, Result) ||2361           symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurSrcLoop,2362                            CurDstLoop);2363  }2364  if (SrcAddRec) {2365    const SCEV *SrcConst = SrcAddRec->getStart();2366    const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE);2367    const SCEV *DstConst = Dst;2368    const Loop *CurSrcLoop = SrcAddRec->getLoop();2369    Level = mapSrcLoop(CurSrcLoop);2370    return weakZeroDstSIVtest(SrcCoeff, SrcConst, DstConst, CurSrcLoop,2371                              CurSrcLoop, Level, Result) ||2372           gcdMIVtest(Src, Dst, Result);2373  }2374  if (DstAddRec) {2375    const SCEV *DstConst = DstAddRec->getStart();2376    const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE);2377    const SCEV *SrcConst = Src;2378    const Loop *CurDstLoop = DstAddRec->getLoop();2379    Level = mapDstLoop(CurDstLoop);2380    return weakZeroSrcSIVtest(DstCoeff, SrcConst, DstConst, CurDstLoop,2381                              CurDstLoop, Level, Result) ||2382           gcdMIVtest(Src, Dst, Result);2383  }2384  llvm_unreachable("SIV test expected at least one AddRec");2385  return false;2386}2387 2388// testRDIV -2389// When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j]2390// where i and j are induction variables, c1 and c2 are loop invariant,2391// and a1 and a2 are constant, we can solve it exactly with an easy adaptation2392// of the Exact SIV test, the Restricted Double Index Variable (RDIV) test.2393// It doesn't make sense to talk about distance or direction in this case,2394// so there's no point in making special versions of the Strong SIV test or2395// the Weak-crossing SIV test.2396//2397// With minor algebra, this test can also be used for things like2398// [c1 + a1*i + a2*j][c2].2399//2400// Return true if dependence disproved.2401bool DependenceInfo::testRDIV(const SCEV *Src, const SCEV *Dst,2402                              FullDependence &Result) const {2403  // we have 3 possible situations here:2404  //   1) [a*i + b] and [c*j + d]2405  //   2) [a*i + c*j + b] and [d]2406  //   3) [b] and [a*i + c*j + d]2407  // We need to find what we've got and get organized2408 2409  const SCEV *SrcConst, *DstConst;2410  const SCEV *SrcCoeff, *DstCoeff;2411  const Loop *SrcLoop, *DstLoop;2412 2413  LLVM_DEBUG(dbgs() << "    src = " << *Src << "\n");2414  LLVM_DEBUG(dbgs() << "    dst = " << *Dst << "\n");2415  const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src);2416  const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst);2417  if (SrcAddRec && DstAddRec) {2418    SrcConst = SrcAddRec->getStart();2419    SrcCoeff = SrcAddRec->getStepRecurrence(*SE);2420    SrcLoop = SrcAddRec->getLoop();2421    DstConst = DstAddRec->getStart();2422    DstCoeff = DstAddRec->getStepRecurrence(*SE);2423    DstLoop = DstAddRec->getLoop();2424  } else if (SrcAddRec) {2425    if (const SCEVAddRecExpr *tmpAddRec =2426            dyn_cast<SCEVAddRecExpr>(SrcAddRec->getStart())) {2427      SrcConst = tmpAddRec->getStart();2428      SrcCoeff = tmpAddRec->getStepRecurrence(*SE);2429      SrcLoop = tmpAddRec->getLoop();2430      DstConst = Dst;2431      DstCoeff = SE->getNegativeSCEV(SrcAddRec->getStepRecurrence(*SE));2432      DstLoop = SrcAddRec->getLoop();2433    } else2434      llvm_unreachable("RDIV reached by surprising SCEVs");2435  } else if (DstAddRec) {2436    if (const SCEVAddRecExpr *tmpAddRec =2437            dyn_cast<SCEVAddRecExpr>(DstAddRec->getStart())) {2438      DstConst = tmpAddRec->getStart();2439      DstCoeff = tmpAddRec->getStepRecurrence(*SE);2440      DstLoop = tmpAddRec->getLoop();2441      SrcConst = Src;2442      SrcCoeff = SE->getNegativeSCEV(DstAddRec->getStepRecurrence(*SE));2443      SrcLoop = DstAddRec->getLoop();2444    } else2445      llvm_unreachable("RDIV reached by surprising SCEVs");2446  } else2447    llvm_unreachable("RDIV expected at least one AddRec");2448  return exactRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, SrcLoop, DstLoop,2449                       Result) ||2450         gcdMIVtest(Src, Dst, Result) ||2451         symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, SrcLoop,2452                          DstLoop);2453}2454 2455// Tests the single-subscript MIV pair (Src and Dst) for dependence.2456// Return true if dependence disproved.2457// Can sometimes refine direction vectors.2458bool DependenceInfo::testMIV(const SCEV *Src, const SCEV *Dst,2459                             const SmallBitVector &Loops,2460                             FullDependence &Result) const {2461  LLVM_DEBUG(dbgs() << "    src = " << *Src << "\n");2462  LLVM_DEBUG(dbgs() << "    dst = " << *Dst << "\n");2463  Result.Consistent = false;2464  return gcdMIVtest(Src, Dst, Result) ||2465         banerjeeMIVtest(Src, Dst, Loops, Result);2466}2467 2468/// Given a SCEVMulExpr, returns its first operand if its first operand is a2469/// constant and the product doesn't overflow in a signed sense. Otherwise,2470/// returns std::nullopt. For example, given (10 * X * Y)<nsw>, it returns 10.2471/// Notably, if it doesn't have nsw, the multiplication may overflow, and if2472/// so, it may not a multiple of 10.2473static std::optional<APInt> getConstanCoefficient(const SCEV *Expr) {2474  if (const auto *Constant = dyn_cast<SCEVConstant>(Expr))2475    return Constant->getAPInt();2476  if (const auto *Product = dyn_cast<SCEVMulExpr>(Expr))2477    if (const auto *Constant = dyn_cast<SCEVConstant>(Product->getOperand(0)))2478      if (Product->hasNoSignedWrap())2479        return Constant->getAPInt();2480  return std::nullopt;2481}2482 2483bool DependenceInfo::accumulateCoefficientsGCD(const SCEV *Expr,2484                                               const Loop *CurLoop,2485                                               const SCEV *&CurLoopCoeff,2486                                               APInt &RunningGCD) const {2487  // If RunningGCD is already 1, exit early.2488  // TODO: It might be better to continue the recursion to find CurLoopCoeff.2489  if (RunningGCD == 1)2490    return true;2491 2492  const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);2493  if (!AddRec) {2494    assert(isLoopInvariant(Expr, CurLoop) &&2495           "Expected loop invariant expression");2496    return true;2497  }2498 2499  assert(AddRec->isAffine() && "Unexpected Expr");2500  const SCEV *Start = AddRec->getStart();2501  const SCEV *Step = AddRec->getStepRecurrence(*SE);2502  if (AddRec->getLoop() == CurLoop) {2503    CurLoopCoeff = Step;2504  } else {2505    std::optional<APInt> ConstCoeff = getConstanCoefficient(Step);2506 2507    // If the coefficient is the product of a constant and other stuff, we can2508    // use the constant in the GCD computation.2509    if (!ConstCoeff)2510      return false;2511 2512    // TODO: What happens if ConstCoeff is the "most negative" signed number2513    // (e.g. -128 for 8 bit wide APInt)?2514    RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff->abs());2515  }2516 2517  return accumulateCoefficientsGCD(Start, CurLoop, CurLoopCoeff, RunningGCD);2518}2519 2520//===----------------------------------------------------------------------===//2521// gcdMIVtest -2522// Tests an MIV subscript pair for dependence.2523// Returns true if any possible dependence is disproved.2524// Marks the result as inconsistent.2525// Can sometimes disprove the equal direction for 1 or more loops,2526// as discussed in Michael Wolfe's book,2527// High Performance Compilers for Parallel Computing, page 235.2528//2529// We spend some effort (code!) to handle cases like2530// [10*i + 5*N*j + 15*M + 6], where i and j are induction variables,2531// but M and N are just loop-invariant variables.2532// This should help us handle linearized subscripts;2533// also makes this test a useful backup to the various SIV tests.2534//2535// It occurs to me that the presence of loop-invariant variables2536// changes the nature of the test from "greatest common divisor"2537// to "a common divisor".2538bool DependenceInfo::gcdMIVtest(const SCEV *Src, const SCEV *Dst,2539                                FullDependence &Result) const {2540  if (!isDependenceTestEnabled(DependenceTestType::GCDMIV))2541    return false;2542 2543  LLVM_DEBUG(dbgs() << "starting gcd\n");2544  ++GCDapplications;2545  unsigned BitWidth = SE->getTypeSizeInBits(Src->getType());2546  APInt RunningGCD = APInt::getZero(BitWidth);2547 2548  // Examine Src coefficients.2549  // Compute running GCD and record source constant.2550  // Because we're looking for the constant at the end of the chain,2551  // we can't quit the loop just because the GCD == 1.2552  const SCEV *Coefficients = Src;2553  while (const SCEVAddRecExpr *AddRec =2554             dyn_cast<SCEVAddRecExpr>(Coefficients)) {2555    const SCEV *Coeff = AddRec->getStepRecurrence(*SE);2556    // If the coefficient is the product of a constant and other stuff,2557    // we can use the constant in the GCD computation.2558    std::optional<APInt> ConstCoeff = getConstanCoefficient(Coeff);2559    if (!ConstCoeff)2560      return false;2561    RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff->abs());2562    Coefficients = AddRec->getStart();2563  }2564  const SCEV *SrcConst = Coefficients;2565 2566  // Examine Dst coefficients.2567  // Compute running GCD and record destination constant.2568  // Because we're looking for the constant at the end of the chain,2569  // we can't quit the loop just because the GCD == 1.2570  Coefficients = Dst;2571  while (const SCEVAddRecExpr *AddRec =2572             dyn_cast<SCEVAddRecExpr>(Coefficients)) {2573    const SCEV *Coeff = AddRec->getStepRecurrence(*SE);2574    // If the coefficient is the product of a constant and other stuff,2575    // we can use the constant in the GCD computation.2576    std::optional<APInt> ConstCoeff = getConstanCoefficient(Coeff);2577    if (!ConstCoeff)2578      return false;2579    RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff->abs());2580    Coefficients = AddRec->getStart();2581  }2582  const SCEV *DstConst = Coefficients;2583 2584  APInt ExtraGCD = APInt::getZero(BitWidth);2585  const SCEV *Delta = minusSCEVNoSignedOverflow(DstConst, SrcConst, *SE);2586  if (!Delta)2587    return false;2588  LLVM_DEBUG(dbgs() << "    Delta = " << *Delta << "\n");2589  const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Delta);2590  if (!Constant)2591    return false;2592  APInt ConstDelta = cast<SCEVConstant>(Constant)->getAPInt();2593  LLVM_DEBUG(dbgs() << "    ConstDelta = " << ConstDelta << "\n");2594  if (ConstDelta == 0)2595    return false;2596  LLVM_DEBUG(dbgs() << "    RunningGCD = " << RunningGCD << "\n");2597  APInt Remainder = ConstDelta.srem(RunningGCD);2598  if (Remainder != 0) {2599    ++GCDindependence;2600    return true;2601  }2602 2603  // Try to disprove equal directions.2604  // For example, given a subscript pair [3*i + 2*j] and [i' + 2*j' - 1],2605  // the code above can't disprove the dependence because the GCD = 1.2606  // So we consider what happen if i = i' and what happens if j = j'.2607  // If i = i', we can simplify the subscript to [2*i + 2*j] and [2*j' - 1],2608  // which is infeasible, so we can disallow the = direction for the i level.2609  // Setting j = j' doesn't help matters, so we end up with a direction vector2610  // of [<>, *]2611  //2612  // Given A[5*i + 10*j*M + 9*M*N] and A[15*i + 20*j*M - 21*N*M + 5],2613  // we need to remember that the constant part is 5 and the RunningGCD should2614  // be initialized to ExtraGCD = 30.2615  LLVM_DEBUG(dbgs() << "    ExtraGCD = " << ExtraGCD << '\n');2616 2617  bool Improved = false;2618  Coefficients = Src;2619  while (const SCEVAddRecExpr *AddRec =2620             dyn_cast<SCEVAddRecExpr>(Coefficients)) {2621    Coefficients = AddRec->getStart();2622    const Loop *CurLoop = AddRec->getLoop();2623    RunningGCD = ExtraGCD;2624    const SCEV *SrcCoeff = AddRec->getStepRecurrence(*SE);2625    const SCEV *DstCoeff = SE->getMinusSCEV(SrcCoeff, SrcCoeff);2626 2627    if (!accumulateCoefficientsGCD(Src, CurLoop, SrcCoeff, RunningGCD) ||2628        !accumulateCoefficientsGCD(Dst, CurLoop, DstCoeff, RunningGCD))2629      return false;2630 2631    Delta = SE->getMinusSCEV(SrcCoeff, DstCoeff);2632    // If the coefficient is the product of a constant and other stuff,2633    // we can use the constant in the GCD computation.2634    std::optional<APInt> ConstCoeff = getConstanCoefficient(Delta);2635    if (!ConstCoeff)2636      // The difference of the two coefficients might not be a product2637      // or constant, in which case we give up on this direction.2638      continue;2639    RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff->abs());2640    LLVM_DEBUG(dbgs() << "\tRunningGCD = " << RunningGCD << "\n");2641    if (RunningGCD != 0) {2642      Remainder = ConstDelta.srem(RunningGCD);2643      LLVM_DEBUG(dbgs() << "\tRemainder = " << Remainder << "\n");2644      if (Remainder != 0) {2645        unsigned Level = mapSrcLoop(CurLoop);2646        Result.DV[Level - 1].Direction &= ~Dependence::DVEntry::EQ;2647        Improved = true;2648      }2649    }2650  }2651  if (Improved)2652    ++GCDsuccesses;2653  LLVM_DEBUG(dbgs() << "all done\n");2654  return false;2655}2656 2657//===----------------------------------------------------------------------===//2658// banerjeeMIVtest -2659// Use Banerjee's Inequalities to test an MIV subscript pair.2660// (Wolfe, in the race-car book, calls this the Extreme Value Test.)2661// Generally follows the discussion in Section 2.5.2 of2662//2663//    Optimizing Supercompilers for Supercomputers2664//    Michael Wolfe2665//2666// The inequalities given on page 25 are simplified in that loops are2667// normalized so that the lower bound is always 0 and the stride is always 1.2668// For example, Wolfe gives2669//2670//     LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k2671//2672// where A_k is the coefficient of the kth index in the source subscript,2673// B_k is the coefficient of the kth index in the destination subscript,2674// U_k is the upper bound of the kth index, L_k is the lower bound of the Kth2675// index, and N_k is the stride of the kth index. Since all loops are normalized2676// by the SCEV package, N_k = 1 and L_k = 0, allowing us to simplify the2677// equation to2678//2679//     LB^<_k = (A^-_k - B_k)^- (U_k - 0 - 1) + (A_k - B_k)0 - B_k 12680//            = (A^-_k - B_k)^- (U_k - 1)  - B_k2681//2682// Similar simplifications are possible for the other equations.2683//2684// When we can't determine the number of iterations for a loop,2685// we use NULL as an indicator for the worst case, infinity.2686// When computing the upper bound, NULL denotes +inf;2687// for the lower bound, NULL denotes -inf.2688//2689// Return true if dependence disproved.2690bool DependenceInfo::banerjeeMIVtest(const SCEV *Src, const SCEV *Dst,2691                                     const SmallBitVector &Loops,2692                                     FullDependence &Result) const {2693  if (!isDependenceTestEnabled(DependenceTestType::BanerjeeMIV))2694    return false;2695 2696  LLVM_DEBUG(dbgs() << "starting Banerjee\n");2697  ++BanerjeeApplications;2698  LLVM_DEBUG(dbgs() << "    Src = " << *Src << '\n');2699  const SCEV *A0;2700  CoefficientInfo *A = collectCoeffInfo(Src, true, A0);2701  LLVM_DEBUG(dbgs() << "    Dst = " << *Dst << '\n');2702  const SCEV *B0;2703  CoefficientInfo *B = collectCoeffInfo(Dst, false, B0);2704  BoundInfo *Bound = new BoundInfo[MaxLevels + 1];2705  const SCEV *Delta = SE->getMinusSCEV(B0, A0);2706  LLVM_DEBUG(dbgs() << "\tDelta = " << *Delta << '\n');2707 2708  // Compute bounds for all the * directions.2709  LLVM_DEBUG(dbgs() << "\tBounds[*]\n");2710  for (unsigned K = 1; K <= MaxLevels; ++K) {2711    Bound[K].Iterations = A[K].Iterations ? A[K].Iterations : B[K].Iterations;2712    Bound[K].Direction = Dependence::DVEntry::ALL;2713    Bound[K].DirSet = Dependence::DVEntry::NONE;2714    findBoundsALL(A, B, Bound, K);2715#ifndef NDEBUG2716    LLVM_DEBUG(dbgs() << "\t    " << K << '\t');2717    if (Bound[K].Lower[Dependence::DVEntry::ALL])2718      LLVM_DEBUG(dbgs() << *Bound[K].Lower[Dependence::DVEntry::ALL] << '\t');2719    else2720      LLVM_DEBUG(dbgs() << "-inf\t");2721    if (Bound[K].Upper[Dependence::DVEntry::ALL])2722      LLVM_DEBUG(dbgs() << *Bound[K].Upper[Dependence::DVEntry::ALL] << '\n');2723    else2724      LLVM_DEBUG(dbgs() << "+inf\n");2725#endif2726  }2727 2728  // Test the *, *, *, ... case.2729  bool Disproved = false;2730  if (testBounds(Dependence::DVEntry::ALL, 0, Bound, Delta)) {2731    // Explore the direction vector hierarchy.2732    unsigned DepthExpanded = 0;2733    unsigned NewDeps =2734        exploreDirections(1, A, B, Bound, Loops, DepthExpanded, Delta);2735    if (NewDeps > 0) {2736      bool Improved = false;2737      for (unsigned K = 1; K <= CommonLevels; ++K) {2738        if (Loops[K]) {2739          unsigned Old = Result.DV[K - 1].Direction;2740          Result.DV[K - 1].Direction = Old & Bound[K].DirSet;2741          Improved |= Old != Result.DV[K - 1].Direction;2742          if (!Result.DV[K - 1].Direction) {2743            Improved = false;2744            Disproved = true;2745            break;2746          }2747        }2748      }2749      if (Improved)2750        ++BanerjeeSuccesses;2751    } else {2752      ++BanerjeeIndependence;2753      Disproved = true;2754    }2755  } else {2756    ++BanerjeeIndependence;2757    Disproved = true;2758  }2759  delete[] Bound;2760  delete[] A;2761  delete[] B;2762  return Disproved;2763}2764 2765// Hierarchically expands the direction vector2766// search space, combining the directions of discovered dependences2767// in the DirSet field of Bound. Returns the number of distinct2768// dependences discovered. If the dependence is disproved,2769// it will return 0.2770unsigned DependenceInfo::exploreDirections(unsigned Level, CoefficientInfo *A,2771                                           CoefficientInfo *B, BoundInfo *Bound,2772                                           const SmallBitVector &Loops,2773                                           unsigned &DepthExpanded,2774                                           const SCEV *Delta) const {2775  // This algorithm has worst case complexity of O(3^n), where 'n' is the number2776  // of common loop levels. To avoid excessive compile-time, pessimize all the2777  // results and immediately return when the number of common levels is beyond2778  // the given threshold.2779  if (CommonLevels > MIVMaxLevelThreshold) {2780    LLVM_DEBUG(dbgs() << "Number of common levels exceeded the threshold. MIV "2781                         "direction exploration is terminated.\n");2782    for (unsigned K = 1; K <= CommonLevels; ++K)2783      if (Loops[K])2784        Bound[K].DirSet = Dependence::DVEntry::ALL;2785    return 1;2786  }2787 2788  if (Level > CommonLevels) {2789    // record result2790    LLVM_DEBUG(dbgs() << "\t[");2791    for (unsigned K = 1; K <= CommonLevels; ++K) {2792      if (Loops[K]) {2793        Bound[K].DirSet |= Bound[K].Direction;2794#ifndef NDEBUG2795        switch (Bound[K].Direction) {2796        case Dependence::DVEntry::LT:2797          LLVM_DEBUG(dbgs() << " <");2798          break;2799        case Dependence::DVEntry::EQ:2800          LLVM_DEBUG(dbgs() << " =");2801          break;2802        case Dependence::DVEntry::GT:2803          LLVM_DEBUG(dbgs() << " >");2804          break;2805        case Dependence::DVEntry::ALL:2806          LLVM_DEBUG(dbgs() << " *");2807          break;2808        default:2809          llvm_unreachable("unexpected Bound[K].Direction");2810        }2811#endif2812      }2813    }2814    LLVM_DEBUG(dbgs() << " ]\n");2815    return 1;2816  }2817  if (Loops[Level]) {2818    if (Level > DepthExpanded) {2819      DepthExpanded = Level;2820      // compute bounds for <, =, > at current level2821      findBoundsLT(A, B, Bound, Level);2822      findBoundsGT(A, B, Bound, Level);2823      findBoundsEQ(A, B, Bound, Level);2824#ifndef NDEBUG2825      LLVM_DEBUG(dbgs() << "\tBound for level = " << Level << '\n');2826      LLVM_DEBUG(dbgs() << "\t    <\t");2827      if (Bound[Level].Lower[Dependence::DVEntry::LT])2828        LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::LT]2829                          << '\t');2830      else2831        LLVM_DEBUG(dbgs() << "-inf\t");2832      if (Bound[Level].Upper[Dependence::DVEntry::LT])2833        LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::LT]2834                          << '\n');2835      else2836        LLVM_DEBUG(dbgs() << "+inf\n");2837      LLVM_DEBUG(dbgs() << "\t    =\t");2838      if (Bound[Level].Lower[Dependence::DVEntry::EQ])2839        LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::EQ]2840                          << '\t');2841      else2842        LLVM_DEBUG(dbgs() << "-inf\t");2843      if (Bound[Level].Upper[Dependence::DVEntry::EQ])2844        LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::EQ]2845                          << '\n');2846      else2847        LLVM_DEBUG(dbgs() << "+inf\n");2848      LLVM_DEBUG(dbgs() << "\t    >\t");2849      if (Bound[Level].Lower[Dependence::DVEntry::GT])2850        LLVM_DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::GT]2851                          << '\t');2852      else2853        LLVM_DEBUG(dbgs() << "-inf\t");2854      if (Bound[Level].Upper[Dependence::DVEntry::GT])2855        LLVM_DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::GT]2856                          << '\n');2857      else2858        LLVM_DEBUG(dbgs() << "+inf\n");2859#endif2860    }2861 2862    unsigned NewDeps = 0;2863 2864    // test bounds for <, *, *, ...2865    if (testBounds(Dependence::DVEntry::LT, Level, Bound, Delta))2866      NewDeps += exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded,2867                                   Delta);2868 2869    // Test bounds for =, *, *, ...2870    if (testBounds(Dependence::DVEntry::EQ, Level, Bound, Delta))2871      NewDeps += exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded,2872                                   Delta);2873 2874    // test bounds for >, *, *, ...2875    if (testBounds(Dependence::DVEntry::GT, Level, Bound, Delta))2876      NewDeps += exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded,2877                                   Delta);2878 2879    Bound[Level].Direction = Dependence::DVEntry::ALL;2880    return NewDeps;2881  } else2882    return exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded,2883                             Delta);2884}2885 2886// Returns true iff the current bounds are plausible.2887bool DependenceInfo::testBounds(unsigned char DirKind, unsigned Level,2888                                BoundInfo *Bound, const SCEV *Delta) const {2889  Bound[Level].Direction = DirKind;2890  if (const SCEV *LowerBound = getLowerBound(Bound))2891    if (isKnownPredicate(CmpInst::ICMP_SGT, LowerBound, Delta))2892      return false;2893  if (const SCEV *UpperBound = getUpperBound(Bound))2894    if (isKnownPredicate(CmpInst::ICMP_SGT, Delta, UpperBound))2895      return false;2896  return true;2897}2898 2899// Computes the upper and lower bounds for level K2900// using the * direction. Records them in Bound.2901// Wolfe gives the equations2902//2903//    LB^*_k = (A^-_k - B^+_k)(U_k - L_k) + (A_k - B_k)L_k2904//    UB^*_k = (A^+_k - B^-_k)(U_k - L_k) + (A_k - B_k)L_k2905//2906// Since we normalize loops, we can simplify these equations to2907//2908//    LB^*_k = (A^-_k - B^+_k)U_k2909//    UB^*_k = (A^+_k - B^-_k)U_k2910//2911// We must be careful to handle the case where the upper bound is unknown.2912// Note that the lower bound is always <= 02913// and the upper bound is always >= 0.2914void DependenceInfo::findBoundsALL(CoefficientInfo *A, CoefficientInfo *B,2915                                   BoundInfo *Bound, unsigned K) const {2916  Bound[K].Lower[Dependence::DVEntry::ALL] =2917      nullptr; // Default value = -infinity.2918  Bound[K].Upper[Dependence::DVEntry::ALL] =2919      nullptr; // Default value = +infinity.2920  if (Bound[K].Iterations) {2921    Bound[K].Lower[Dependence::DVEntry::ALL] = SE->getMulExpr(2922        SE->getMinusSCEV(A[K].NegPart, B[K].PosPart), Bound[K].Iterations);2923    Bound[K].Upper[Dependence::DVEntry::ALL] = SE->getMulExpr(2924        SE->getMinusSCEV(A[K].PosPart, B[K].NegPart), Bound[K].Iterations);2925  } else {2926    // If the difference is 0, we won't need to know the number of iterations.2927    if (isKnownPredicate(CmpInst::ICMP_EQ, A[K].NegPart, B[K].PosPart))2928      Bound[K].Lower[Dependence::DVEntry::ALL] =2929          SE->getZero(A[K].Coeff->getType());2930    if (isKnownPredicate(CmpInst::ICMP_EQ, A[K].PosPart, B[K].NegPart))2931      Bound[K].Upper[Dependence::DVEntry::ALL] =2932          SE->getZero(A[K].Coeff->getType());2933  }2934}2935 2936// Computes the upper and lower bounds for level K2937// using the = direction. Records them in Bound.2938// Wolfe gives the equations2939//2940//    LB^=_k = (A_k - B_k)^- (U_k - L_k) + (A_k - B_k)L_k2941//    UB^=_k = (A_k - B_k)^+ (U_k - L_k) + (A_k - B_k)L_k2942//2943// Since we normalize loops, we can simplify these equations to2944//2945//    LB^=_k = (A_k - B_k)^- U_k2946//    UB^=_k = (A_k - B_k)^+ U_k2947//2948// We must be careful to handle the case where the upper bound is unknown.2949// Note that the lower bound is always <= 02950// and the upper bound is always >= 0.2951void DependenceInfo::findBoundsEQ(CoefficientInfo *A, CoefficientInfo *B,2952                                  BoundInfo *Bound, unsigned K) const {2953  Bound[K].Lower[Dependence::DVEntry::EQ] =2954      nullptr; // Default value = -infinity.2955  Bound[K].Upper[Dependence::DVEntry::EQ] =2956      nullptr; // Default value = +infinity.2957  if (Bound[K].Iterations) {2958    const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff);2959    const SCEV *NegativePart = getNegativePart(Delta);2960    Bound[K].Lower[Dependence::DVEntry::EQ] =2961        SE->getMulExpr(NegativePart, Bound[K].Iterations);2962    const SCEV *PositivePart = getPositivePart(Delta);2963    Bound[K].Upper[Dependence::DVEntry::EQ] =2964        SE->getMulExpr(PositivePart, Bound[K].Iterations);2965  } else {2966    // If the positive/negative part of the difference is 0,2967    // we won't need to know the number of iterations.2968    const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff);2969    const SCEV *NegativePart = getNegativePart(Delta);2970    if (NegativePart->isZero())2971      Bound[K].Lower[Dependence::DVEntry::EQ] = NegativePart; // Zero2972    const SCEV *PositivePart = getPositivePart(Delta);2973    if (PositivePart->isZero())2974      Bound[K].Upper[Dependence::DVEntry::EQ] = PositivePart; // Zero2975  }2976}2977 2978// Computes the upper and lower bounds for level K2979// using the < direction. Records them in Bound.2980// Wolfe gives the equations2981//2982//    LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k2983//    UB^<_k = (A^+_k - B_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k2984//2985// Since we normalize loops, we can simplify these equations to2986//2987//    LB^<_k = (A^-_k - B_k)^- (U_k - 1) - B_k2988//    UB^<_k = (A^+_k - B_k)^+ (U_k - 1) - B_k2989//2990// We must be careful to handle the case where the upper bound is unknown.2991void DependenceInfo::findBoundsLT(CoefficientInfo *A, CoefficientInfo *B,2992                                  BoundInfo *Bound, unsigned K) const {2993  Bound[K].Lower[Dependence::DVEntry::LT] =2994      nullptr; // Default value = -infinity.2995  Bound[K].Upper[Dependence::DVEntry::LT] =2996      nullptr; // Default value = +infinity.2997  if (Bound[K].Iterations) {2998    const SCEV *Iter_1 = SE->getMinusSCEV(2999        Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));3000    const SCEV *NegPart =3001        getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff));3002    Bound[K].Lower[Dependence::DVEntry::LT] =3003        SE->getMinusSCEV(SE->getMulExpr(NegPart, Iter_1), B[K].Coeff);3004    const SCEV *PosPart =3005        getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff));3006    Bound[K].Upper[Dependence::DVEntry::LT] =3007        SE->getMinusSCEV(SE->getMulExpr(PosPart, Iter_1), B[K].Coeff);3008  } else {3009    // If the positive/negative part of the difference is 0,3010    // we won't need to know the number of iterations.3011    const SCEV *NegPart =3012        getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff));3013    if (NegPart->isZero())3014      Bound[K].Lower[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff);3015    const SCEV *PosPart =3016        getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff));3017    if (PosPart->isZero())3018      Bound[K].Upper[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff);3019  }3020}3021 3022// Computes the upper and lower bounds for level K3023// using the > direction. Records them in Bound.3024// Wolfe gives the equations3025//3026//    LB^>_k = (A_k - B^+_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k3027//    UB^>_k = (A_k - B^-_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k3028//3029// Since we normalize loops, we can simplify these equations to3030//3031//    LB^>_k = (A_k - B^+_k)^- (U_k - 1) + A_k3032//    UB^>_k = (A_k - B^-_k)^+ (U_k - 1) + A_k3033//3034// We must be careful to handle the case where the upper bound is unknown.3035void DependenceInfo::findBoundsGT(CoefficientInfo *A, CoefficientInfo *B,3036                                  BoundInfo *Bound, unsigned K) const {3037  Bound[K].Lower[Dependence::DVEntry::GT] =3038      nullptr; // Default value = -infinity.3039  Bound[K].Upper[Dependence::DVEntry::GT] =3040      nullptr; // Default value = +infinity.3041  if (Bound[K].Iterations) {3042    const SCEV *Iter_1 = SE->getMinusSCEV(3043        Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));3044    const SCEV *NegPart =3045        getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart));3046    Bound[K].Lower[Dependence::DVEntry::GT] =3047        SE->getAddExpr(SE->getMulExpr(NegPart, Iter_1), A[K].Coeff);3048    const SCEV *PosPart =3049        getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart));3050    Bound[K].Upper[Dependence::DVEntry::GT] =3051        SE->getAddExpr(SE->getMulExpr(PosPart, Iter_1), A[K].Coeff);3052  } else {3053    // If the positive/negative part of the difference is 0,3054    // we won't need to know the number of iterations.3055    const SCEV *NegPart =3056        getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart));3057    if (NegPart->isZero())3058      Bound[K].Lower[Dependence::DVEntry::GT] = A[K].Coeff;3059    const SCEV *PosPart =3060        getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart));3061    if (PosPart->isZero())3062      Bound[K].Upper[Dependence::DVEntry::GT] = A[K].Coeff;3063  }3064}3065 3066// X^+ = max(X, 0)3067const SCEV *DependenceInfo::getPositivePart(const SCEV *X) const {3068  return SE->getSMaxExpr(X, SE->getZero(X->getType()));3069}3070 3071// X^- = min(X, 0)3072const SCEV *DependenceInfo::getNegativePart(const SCEV *X) const {3073  return SE->getSMinExpr(X, SE->getZero(X->getType()));3074}3075 3076// Walks through the subscript,3077// collecting each coefficient, the associated loop bounds,3078// and recording its positive and negative parts for later use.3079DependenceInfo::CoefficientInfo *3080DependenceInfo::collectCoeffInfo(const SCEV *Subscript, bool SrcFlag,3081                                 const SCEV *&Constant) const {3082  const SCEV *Zero = SE->getZero(Subscript->getType());3083  CoefficientInfo *CI = new CoefficientInfo[MaxLevels + 1];3084  for (unsigned K = 1; K <= MaxLevels; ++K) {3085    CI[K].Coeff = Zero;3086    CI[K].PosPart = Zero;3087    CI[K].NegPart = Zero;3088    CI[K].Iterations = nullptr;3089  }3090  while (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Subscript)) {3091    const Loop *L = AddRec->getLoop();3092    unsigned K = SrcFlag ? mapSrcLoop(L) : mapDstLoop(L);3093    CI[K].Coeff = AddRec->getStepRecurrence(*SE);3094    CI[K].PosPart = getPositivePart(CI[K].Coeff);3095    CI[K].NegPart = getNegativePart(CI[K].Coeff);3096    CI[K].Iterations = collectUpperBound(L, Subscript->getType());3097    Subscript = AddRec->getStart();3098  }3099  Constant = Subscript;3100#ifndef NDEBUG3101  LLVM_DEBUG(dbgs() << "\tCoefficient Info\n");3102  for (unsigned K = 1; K <= MaxLevels; ++K) {3103    LLVM_DEBUG(dbgs() << "\t    " << K << "\t" << *CI[K].Coeff);3104    LLVM_DEBUG(dbgs() << "\tPos Part = ");3105    LLVM_DEBUG(dbgs() << *CI[K].PosPart);3106    LLVM_DEBUG(dbgs() << "\tNeg Part = ");3107    LLVM_DEBUG(dbgs() << *CI[K].NegPart);3108    LLVM_DEBUG(dbgs() << "\tUpper Bound = ");3109    if (CI[K].Iterations)3110      LLVM_DEBUG(dbgs() << *CI[K].Iterations);3111    else3112      LLVM_DEBUG(dbgs() << "+inf");3113    LLVM_DEBUG(dbgs() << '\n');3114  }3115  LLVM_DEBUG(dbgs() << "\t    Constant = " << *Subscript << '\n');3116#endif3117  return CI;3118}3119 3120// Looks through all the bounds info and3121// computes the lower bound given the current direction settings3122// at each level. If the lower bound for any level is -inf,3123// the result is -inf.3124const SCEV *DependenceInfo::getLowerBound(BoundInfo *Bound) const {3125  const SCEV *Sum = Bound[1].Lower[Bound[1].Direction];3126  for (unsigned K = 2; Sum && K <= MaxLevels; ++K) {3127    if (Bound[K].Lower[Bound[K].Direction])3128      Sum = SE->getAddExpr(Sum, Bound[K].Lower[Bound[K].Direction]);3129    else3130      Sum = nullptr;3131  }3132  return Sum;3133}3134 3135// Looks through all the bounds info and3136// computes the upper bound given the current direction settings3137// at each level. If the upper bound at any level is +inf,3138// the result is +inf.3139const SCEV *DependenceInfo::getUpperBound(BoundInfo *Bound) const {3140  const SCEV *Sum = Bound[1].Upper[Bound[1].Direction];3141  for (unsigned K = 2; Sum && K <= MaxLevels; ++K) {3142    if (Bound[K].Upper[Bound[K].Direction])3143      Sum = SE->getAddExpr(Sum, Bound[K].Upper[Bound[K].Direction]);3144    else3145      Sum = nullptr;3146  }3147  return Sum;3148}3149 3150/// Check if we can delinearize the subscripts. If the SCEVs representing the3151/// source and destination array references are recurrences on a nested loop,3152/// this function flattens the nested recurrences into separate recurrences3153/// for each loop level.3154bool DependenceInfo::tryDelinearize(Instruction *Src, Instruction *Dst,3155                                    SmallVectorImpl<Subscript> &Pair) {3156  assert(isLoadOrStore(Src) && "instruction is not load or store");3157  assert(isLoadOrStore(Dst) && "instruction is not load or store");3158  Value *SrcPtr = getLoadStorePointerOperand(Src);3159  Value *DstPtr = getLoadStorePointerOperand(Dst);3160  Loop *SrcLoop = LI->getLoopFor(Src->getParent());3161  Loop *DstLoop = LI->getLoopFor(Dst->getParent());3162  const SCEV *SrcAccessFn = SE->getSCEVAtScope(SrcPtr, SrcLoop);3163  const SCEV *DstAccessFn = SE->getSCEVAtScope(DstPtr, DstLoop);3164  const SCEVUnknown *SrcBase =3165      dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));3166  const SCEVUnknown *DstBase =3167      dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));3168 3169  if (!SrcBase || !DstBase || SrcBase != DstBase)3170    return false;3171 3172  SmallVector<const SCEV *, 4> SrcSubscripts, DstSubscripts;3173 3174  if (!tryDelinearizeFixedSize(Src, Dst, SrcAccessFn, DstAccessFn,3175                               SrcSubscripts, DstSubscripts) &&3176      !tryDelinearizeParametricSize(Src, Dst, SrcAccessFn, DstAccessFn,3177                                    SrcSubscripts, DstSubscripts))3178    return false;3179 3180  assert(isLoopInvariant(SrcBase, SrcLoop) &&3181         isLoopInvariant(DstBase, DstLoop) &&3182         "Expected SrcBase and DstBase to be loop invariant");3183 3184  int Size = SrcSubscripts.size();3185  LLVM_DEBUG({3186    dbgs() << "\nSrcSubscripts: ";3187    for (int I = 0; I < Size; I++)3188      dbgs() << *SrcSubscripts[I];3189    dbgs() << "\nDstSubscripts: ";3190    for (int I = 0; I < Size; I++)3191      dbgs() << *DstSubscripts[I];3192  });3193 3194  // The delinearization transforms a single-subscript MIV dependence test into3195  // a multi-subscript SIV dependence test that is easier to compute. So we3196  // resize Pair to contain as many pairs of subscripts as the delinearization3197  // has found, and then initialize the pairs following the delinearization.3198  Pair.resize(Size);3199  SCEVMonotonicityChecker MonChecker(SE);3200  const Loop *OutermostLoop = SrcLoop ? SrcLoop->getOutermostLoop() : nullptr;3201  for (int I = 0; I < Size; ++I) {3202    Pair[I].Src = SrcSubscripts[I];3203    Pair[I].Dst = DstSubscripts[I];3204    unifySubscriptType(&Pair[I]);3205 3206    if (EnableMonotonicityCheck) {3207      if (MonChecker.checkMonotonicity(Pair[I].Src, OutermostLoop).isUnknown())3208        return false;3209      if (MonChecker.checkMonotonicity(Pair[I].Dst, OutermostLoop).isUnknown())3210        return false;3211    }3212  }3213 3214  return true;3215}3216 3217/// Try to delinearize \p SrcAccessFn and \p DstAccessFn if the underlying3218/// arrays accessed are fixed-size arrays. Return true if delinearization was3219/// successful.3220bool DependenceInfo::tryDelinearizeFixedSize(3221    Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn,3222    const SCEV *DstAccessFn, SmallVectorImpl<const SCEV *> &SrcSubscripts,3223    SmallVectorImpl<const SCEV *> &DstSubscripts) {3224  LLVM_DEBUG({3225    const SCEVUnknown *SrcBase =3226        dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));3227    const SCEVUnknown *DstBase =3228        dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));3229    assert(SrcBase && DstBase && SrcBase == DstBase &&3230           "expected src and dst scev unknowns to be equal");3231  });3232 3233  const SCEV *ElemSize = SE->getElementSize(Src);3234  assert(ElemSize == SE->getElementSize(Dst) && "Different element sizes");3235  SmallVector<const SCEV *, 4> SrcSizes, DstSizes;3236  if (!delinearizeFixedSizeArray(*SE, SE->removePointerBase(SrcAccessFn),3237                                 SrcSubscripts, SrcSizes, ElemSize) ||3238      !delinearizeFixedSizeArray(*SE, SE->removePointerBase(DstAccessFn),3239                                 DstSubscripts, DstSizes, ElemSize))3240    return false;3241 3242  // Check that the two size arrays are non-empty and equal in length and3243  // value.3244  if (SrcSizes.size() != DstSizes.size() ||3245      !std::equal(SrcSizes.begin(), SrcSizes.end(), DstSizes.begin())) {3246    SrcSubscripts.clear();3247    DstSubscripts.clear();3248    return false;3249  }3250 3251  assert(SrcSubscripts.size() == DstSubscripts.size() &&3252         "Expected equal number of entries in the list of SrcSubscripts and "3253         "DstSubscripts.");3254 3255  Value *SrcPtr = getLoadStorePointerOperand(Src);3256  Value *DstPtr = getLoadStorePointerOperand(Dst);3257 3258  // In general we cannot safely assume that the subscripts recovered from GEPs3259  // are in the range of values defined for their corresponding array3260  // dimensions. For example some C language usage/interpretation make it3261  // impossible to verify this at compile-time. As such we can only delinearize3262  // iff the subscripts are positive and are less than the range of the3263  // dimension.3264  if (!DisableDelinearizationChecks) {3265    if (!validateDelinearizationResult(*SE, SrcSizes, SrcSubscripts, SrcPtr) ||3266        !validateDelinearizationResult(*SE, DstSizes, DstSubscripts, DstPtr)) {3267      SrcSubscripts.clear();3268      DstSubscripts.clear();3269      return false;3270    }3271  }3272  LLVM_DEBUG({3273    dbgs() << "Delinearized subscripts of fixed-size array\n"3274           << "SrcGEP:" << *SrcPtr << "\n"3275           << "DstGEP:" << *DstPtr << "\n";3276  });3277  return true;3278}3279 3280bool DependenceInfo::tryDelinearizeParametricSize(3281    Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn,3282    const SCEV *DstAccessFn, SmallVectorImpl<const SCEV *> &SrcSubscripts,3283    SmallVectorImpl<const SCEV *> &DstSubscripts) {3284 3285  Value *SrcPtr = getLoadStorePointerOperand(Src);3286  Value *DstPtr = getLoadStorePointerOperand(Dst);3287  const SCEVUnknown *SrcBase =3288      dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));3289  const SCEVUnknown *DstBase =3290      dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));3291  assert(SrcBase && DstBase && SrcBase == DstBase &&3292         "expected src and dst scev unknowns to be equal");3293 3294  const SCEV *ElementSize = SE->getElementSize(Src);3295  if (ElementSize != SE->getElementSize(Dst))3296    return false;3297 3298  const SCEV *SrcSCEV = SE->getMinusSCEV(SrcAccessFn, SrcBase);3299  const SCEV *DstSCEV = SE->getMinusSCEV(DstAccessFn, DstBase);3300 3301  const SCEVAddRecExpr *SrcAR = dyn_cast<SCEVAddRecExpr>(SrcSCEV);3302  const SCEVAddRecExpr *DstAR = dyn_cast<SCEVAddRecExpr>(DstSCEV);3303  if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine())3304    return false;3305 3306  // First step: collect parametric terms in both array references.3307  SmallVector<const SCEV *, 4> Terms;3308  collectParametricTerms(*SE, SrcAR, Terms);3309  collectParametricTerms(*SE, DstAR, Terms);3310 3311  // Second step: find subscript sizes.3312  SmallVector<const SCEV *, 4> Sizes;3313  findArrayDimensions(*SE, Terms, Sizes, ElementSize);3314 3315  // Third step: compute the access functions for each subscript.3316  computeAccessFunctions(*SE, SrcAR, SrcSubscripts, Sizes);3317  computeAccessFunctions(*SE, DstAR, DstSubscripts, Sizes);3318 3319  // Fail when there is only a subscript: that's a linearized access function.3320  if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 ||3321      SrcSubscripts.size() != DstSubscripts.size())3322    return false;3323 3324  // Statically check that the array bounds are in-range. The first subscript we3325  // don't have a size for and it cannot overflow into another subscript, so is3326  // always safe. The others need to be 0 <= subscript[i] < bound, for both src3327  // and dst.3328  // FIXME: It may be better to record these sizes and add them as constraints3329  // to the dependency checks.3330  if (!DisableDelinearizationChecks)3331    if (!validateDelinearizationResult(*SE, Sizes, SrcSubscripts, SrcPtr) ||3332        !validateDelinearizationResult(*SE, Sizes, DstSubscripts, DstPtr))3333      return false;3334 3335  return true;3336}3337 3338//===----------------------------------------------------------------------===//3339 3340#ifndef NDEBUG3341// For debugging purposes, dump a small bit vector to dbgs().3342static void dumpSmallBitVector(SmallBitVector &BV) {3343  dbgs() << "{";3344  for (unsigned VI : BV.set_bits()) {3345    dbgs() << VI;3346    if (BV.find_next(VI) >= 0)3347      dbgs() << ' ';3348  }3349  dbgs() << "}\n";3350}3351#endif3352 3353bool DependenceInfo::invalidate(Function &F, const PreservedAnalyses &PA,3354                                FunctionAnalysisManager::Invalidator &Inv) {3355  // Check if the analysis itself has been invalidated.3356  auto PAC = PA.getChecker<DependenceAnalysis>();3357  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Function>>())3358    return true;3359 3360  // Check transitive dependencies.3361  return Inv.invalidate<AAManager>(F, PA) ||3362         Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||3363         Inv.invalidate<LoopAnalysis>(F, PA);3364}3365 3366// depends -3367// Returns NULL if there is no dependence.3368// Otherwise, return a Dependence with as many details as possible.3369// Corresponds to Section 3.1 in the paper3370//3371//            Practical Dependence Testing3372//            Goff, Kennedy, Tseng3373//            PLDI 19913374//3375std::unique_ptr<Dependence>3376DependenceInfo::depends(Instruction *Src, Instruction *Dst,3377                        bool UnderRuntimeAssumptions) {3378  SmallVector<const SCEVPredicate *, 4> Assume;3379  bool PossiblyLoopIndependent = true;3380  if (Src == Dst)3381    PossiblyLoopIndependent = false;3382 3383  if (!(Src->mayReadOrWriteMemory() && Dst->mayReadOrWriteMemory()))3384    // if both instructions don't reference memory, there's no dependence3385    return nullptr;3386 3387  if (!isLoadOrStore(Src) || !isLoadOrStore(Dst)) {3388    // can only analyze simple loads and stores, i.e., no calls, invokes, etc.3389    LLVM_DEBUG(dbgs() << "can only handle simple loads and stores\n");3390    return std::make_unique<Dependence>(Src, Dst,3391                                        SCEVUnionPredicate(Assume, *SE));3392  }3393 3394  const MemoryLocation &DstLoc = MemoryLocation::get(Dst);3395  const MemoryLocation &SrcLoc = MemoryLocation::get(Src);3396 3397  switch (underlyingObjectsAlias(AA, F->getDataLayout(), DstLoc, SrcLoc)) {3398  case AliasResult::MayAlias:3399  case AliasResult::PartialAlias:3400    // cannot analyse objects if we don't understand their aliasing.3401    LLVM_DEBUG(dbgs() << "can't analyze may or partial alias\n");3402    return std::make_unique<Dependence>(Src, Dst,3403                                        SCEVUnionPredicate(Assume, *SE));3404  case AliasResult::NoAlias:3405    // If the objects noalias, they are distinct, accesses are independent.3406    LLVM_DEBUG(dbgs() << "no alias\n");3407    return nullptr;3408  case AliasResult::MustAlias:3409    break; // The underlying objects alias; test accesses for dependence.3410  }3411 3412  if (DstLoc.Size != SrcLoc.Size || !DstLoc.Size.isPrecise() ||3413      !SrcLoc.Size.isPrecise()) {3414    // The dependence test gets confused if the size of the memory accesses3415    // differ.3416    LLVM_DEBUG(dbgs() << "can't analyze must alias with different sizes\n");3417    return std::make_unique<Dependence>(Src, Dst,3418                                        SCEVUnionPredicate(Assume, *SE));3419  }3420 3421  Value *SrcPtr = getLoadStorePointerOperand(Src);3422  Value *DstPtr = getLoadStorePointerOperand(Dst);3423  const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);3424  const SCEV *DstSCEV = SE->getSCEV(DstPtr);3425  LLVM_DEBUG(dbgs() << "    SrcSCEV = " << *SrcSCEV << "\n");3426  LLVM_DEBUG(dbgs() << "    DstSCEV = " << *DstSCEV << "\n");3427  const SCEV *SrcBase = SE->getPointerBase(SrcSCEV);3428  const SCEV *DstBase = SE->getPointerBase(DstSCEV);3429  if (SrcBase != DstBase) {3430    // If two pointers have different bases, trying to analyze indexes won't3431    // work; we can't compare them to each other. This can happen, for example,3432    // if one is produced by an LCSSA PHI node.3433    //3434    // We check this upfront so we don't crash in cases where getMinusSCEV()3435    // returns a SCEVCouldNotCompute.3436    LLVM_DEBUG(dbgs() << "can't analyze SCEV with different pointer base\n");3437    return std::make_unique<Dependence>(Src, Dst,3438                                        SCEVUnionPredicate(Assume, *SE));3439  }3440 3441  // Even if the base pointers are the same, they may not be loop-invariant. It3442  // could lead to incorrect results, as we're analyzing loop-carried3443  // dependencies. Src and Dst can be in different loops, so we need to check3444  // the base pointer is invariant in both loops.3445  Loop *SrcLoop = LI->getLoopFor(Src->getParent());3446  Loop *DstLoop = LI->getLoopFor(Dst->getParent());3447  if (!isLoopInvariant(SrcBase, SrcLoop) ||3448      !isLoopInvariant(DstBase, DstLoop)) {3449    LLVM_DEBUG(dbgs() << "The base pointer is not loop invariant.\n");3450    return std::make_unique<Dependence>(Src, Dst,3451                                        SCEVUnionPredicate(Assume, *SE));3452  }3453 3454  uint64_t EltSize = SrcLoc.Size.toRaw();3455  const SCEV *SrcEv = SE->getMinusSCEV(SrcSCEV, SrcBase);3456  const SCEV *DstEv = SE->getMinusSCEV(DstSCEV, DstBase);3457 3458  // Check that memory access offsets are multiples of element sizes.3459  if (!SE->isKnownMultipleOf(SrcEv, EltSize, Assume) ||3460      !SE->isKnownMultipleOf(DstEv, EltSize, Assume)) {3461    LLVM_DEBUG(dbgs() << "can't analyze SCEV with different offsets\n");3462    return std::make_unique<Dependence>(Src, Dst,3463                                        SCEVUnionPredicate(Assume, *SE));3464  }3465 3466  if (!Assume.empty() && !UnderRuntimeAssumptions) {3467    // Runtime assumptions needed but not allowed.3468    return std::make_unique<Dependence>(Src, Dst,3469                                        SCEVUnionPredicate(Assume, *SE));3470  }3471 3472  unsigned Pairs = 1;3473  SmallVector<Subscript, 2> Pair(Pairs);3474  Pair[0].Src = SrcEv;3475  Pair[0].Dst = DstEv;3476 3477  SCEVMonotonicityChecker MonChecker(SE);3478  const Loop *OutermostLoop = SrcLoop ? SrcLoop->getOutermostLoop() : nullptr;3479  if (EnableMonotonicityCheck)3480    if (MonChecker.checkMonotonicity(Pair[0].Src, OutermostLoop).isUnknown() ||3481        MonChecker.checkMonotonicity(Pair[0].Dst, OutermostLoop).isUnknown())3482      return std::make_unique<Dependence>(Src, Dst,3483                                          SCEVUnionPredicate(Assume, *SE));3484 3485  if (Delinearize) {3486    if (tryDelinearize(Src, Dst, Pair)) {3487      LLVM_DEBUG(dbgs() << "    delinearized\n");3488      Pairs = Pair.size();3489    }3490  }3491 3492  // Establish loop nesting levels considering SameSD loops as common3493  establishNestingLevels(Src, Dst);3494 3495  LLVM_DEBUG(dbgs() << "    common nesting levels = " << CommonLevels << "\n");3496  LLVM_DEBUG(dbgs() << "    maximum nesting levels = " << MaxLevels << "\n");3497  LLVM_DEBUG(dbgs() << "    SameSD nesting levels = " << SameSDLevels << "\n");3498 3499  // Modify common levels to consider the SameSD levels in the tests3500  CommonLevels += SameSDLevels;3501  MaxLevels -= SameSDLevels;3502  if (SameSDLevels > 0) {3503    // Not all tests are handled yet over SameSD loops3504    // Revoke if there are any tests other than ZIV, SIV or RDIV3505    for (unsigned P = 0; P < Pairs; ++P) {3506      SmallBitVector Loops;3507      Subscript::ClassificationKind TestClass =3508          classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),3509                       Pair[P].Dst, LI->getLoopFor(Dst->getParent()), Loops);3510 3511      if (TestClass != Subscript::ZIV && TestClass != Subscript::SIV &&3512          TestClass != Subscript::RDIV) {3513        // Revert the levels to not consider the SameSD levels3514        CommonLevels -= SameSDLevels;3515        MaxLevels += SameSDLevels;3516        SameSDLevels = 0;3517        break;3518      }3519    }3520  }3521 3522  if (SameSDLevels > 0)3523    SameSDLoopsCount++;3524 3525  FullDependence Result(Src, Dst, SCEVUnionPredicate(Assume, *SE),3526                        PossiblyLoopIndependent, CommonLevels);3527  ++TotalArrayPairs;3528 3529  for (unsigned P = 0; P < Pairs; ++P) {3530    assert(Pair[P].Src->getType()->isIntegerTy() && "Src must be an integer");3531    assert(Pair[P].Dst->getType()->isIntegerTy() && "Dst must be an integer");3532    Pair[P].Loops.resize(MaxLevels + 1);3533    Pair[P].GroupLoops.resize(MaxLevels + 1);3534    Pair[P].Group.resize(Pairs);3535    removeMatchingExtensions(&Pair[P]);3536    Pair[P].Classification =3537        classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()), Pair[P].Dst,3538                     LI->getLoopFor(Dst->getParent()), Pair[P].Loops);3539    Pair[P].GroupLoops = Pair[P].Loops;3540    Pair[P].Group.set(P);3541    LLVM_DEBUG(dbgs() << "    subscript " << P << "\n");3542    LLVM_DEBUG(dbgs() << "\tsrc = " << *Pair[P].Src << "\n");3543    LLVM_DEBUG(dbgs() << "\tdst = " << *Pair[P].Dst << "\n");3544    LLVM_DEBUG(dbgs() << "\tclass = " << Pair[P].Classification << "\n");3545    LLVM_DEBUG(dbgs() << "\tloops = ");3546    LLVM_DEBUG(dumpSmallBitVector(Pair[P].Loops));3547  }3548 3549  // Test each subscript individually3550  for (unsigned SI = 0; SI < Pairs; ++SI) {3551    LLVM_DEBUG(dbgs() << "testing subscript " << SI);3552    switch (Pair[SI].Classification) {3553    case Subscript::NonLinear:3554      // ignore these, but collect loops for later3555      ++NonlinearSubscriptPairs;3556      collectCommonLoops(Pair[SI].Src, LI->getLoopFor(Src->getParent()),3557                         Pair[SI].Loops);3558      collectCommonLoops(Pair[SI].Dst, LI->getLoopFor(Dst->getParent()),3559                         Pair[SI].Loops);3560      Result.Consistent = false;3561      break;3562    case Subscript::ZIV:3563      LLVM_DEBUG(dbgs() << ", ZIV\n");3564      if (testZIV(Pair[SI].Src, Pair[SI].Dst, Result))3565        return nullptr;3566      break;3567    case Subscript::SIV: {3568      LLVM_DEBUG(dbgs() << ", SIV\n");3569      unsigned Level;3570      if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level, Result))3571        return nullptr;3572      break;3573    }3574    case Subscript::RDIV:3575      LLVM_DEBUG(dbgs() << ", RDIV\n");3576      if (testRDIV(Pair[SI].Src, Pair[SI].Dst, Result))3577        return nullptr;3578      break;3579    case Subscript::MIV:3580      LLVM_DEBUG(dbgs() << ", MIV\n");3581      if (testMIV(Pair[SI].Src, Pair[SI].Dst, Pair[SI].Loops, Result))3582        return nullptr;3583      break;3584    }3585  }3586 3587  // Make sure the Scalar flags are set correctly.3588  SmallBitVector CompleteLoops(MaxLevels + 1);3589  for (unsigned SI = 0; SI < Pairs; ++SI)3590    CompleteLoops |= Pair[SI].Loops;3591  for (unsigned II = 1; II <= CommonLevels; ++II)3592    if (CompleteLoops[II])3593      Result.DV[II - 1].Scalar = false;3594 3595  // Set the distance to zero if the direction is EQ.3596  // TODO: Ideally, the distance should be set to 0 immediately simultaneously3597  // with the corresponding direction being set to EQ.3598  for (unsigned II = 1; II <= Result.getLevels(); ++II) {3599    if (Result.getDirection(II) == Dependence::DVEntry::EQ) {3600      if (Result.DV[II - 1].Distance == nullptr)3601        Result.DV[II - 1].Distance = SE->getZero(SrcSCEV->getType());3602      else3603        assert(Result.DV[II - 1].Distance->isZero() &&3604               "Inconsistency between distance and direction");3605    }3606 3607#ifndef NDEBUG3608    // Check that the converse (i.e., if the distance is zero, then the3609    // direction is EQ) holds.3610    const SCEV *Distance = Result.getDistance(II);3611    if (Distance && Distance->isZero())3612      assert(Result.getDirection(II) == Dependence::DVEntry::EQ &&3613             "Distance is zero, but direction is not EQ");3614#endif3615  }3616 3617  if (SameSDLevels > 0) {3618    // Extracting SameSD levels from the common levels3619    // Reverting CommonLevels and MaxLevels to their original values3620    assert(CommonLevels >= SameSDLevels);3621    CommonLevels -= SameSDLevels;3622    MaxLevels += SameSDLevels;3623    std::unique_ptr<FullDependence::DVEntry[]> DV, DVSameSD;3624    DV = std::make_unique<FullDependence::DVEntry[]>(CommonLevels);3625    DVSameSD = std::make_unique<FullDependence::DVEntry[]>(SameSDLevels);3626    for (unsigned Level = 0; Level < CommonLevels; ++Level)3627      DV[Level] = Result.DV[Level];3628    for (unsigned Level = 0; Level < SameSDLevels; ++Level)3629      DVSameSD[Level] = Result.DV[CommonLevels + Level];3630    Result.DV = std::move(DV);3631    Result.DVSameSD = std::move(DVSameSD);3632    Result.Levels = CommonLevels;3633    Result.SameSDLevels = SameSDLevels;3634    // Result is not consistent if it considers SameSD levels3635    Result.Consistent = false;3636  }3637 3638  if (PossiblyLoopIndependent) {3639    // Make sure the LoopIndependent flag is set correctly.3640    // All directions must include equal, otherwise no3641    // loop-independent dependence is possible.3642    for (unsigned II = 1; II <= CommonLevels; ++II) {3643      if (!(Result.getDirection(II) & Dependence::DVEntry::EQ)) {3644        Result.LoopIndependent = false;3645        break;3646      }3647    }3648  } else {3649    // On the other hand, if all directions are equal and there's no3650    // loop-independent dependence possible, then no dependence exists.3651    bool AllEqual = true;3652    for (unsigned II = 1; II <= CommonLevels; ++II) {3653      if (Result.getDirection(II) != Dependence::DVEntry::EQ) {3654        AllEqual = false;3655        break;3656      }3657    }3658    if (AllEqual)3659      return nullptr;3660  }3661 3662  return std::make_unique<FullDependence>(std::move(Result));3663}3664