LCOV - code coverage report
Current view: top level - lib/Analysis - DependenceAnalysis.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 1454 1545 94.1 %
Date: 2017-09-14 15:23:50 Functions: 91 94 96.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===-- DependenceAnalysis.cpp - DA Implementation --------------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // DependenceAnalysis is an LLVM pass that analyses dependences between memory
      11             : // accesses. Currently, it is an (incomplete) implementation of the approach
      12             : // described in
      13             : //
      14             : //            Practical Dependence Testing
      15             : //            Goff, Kennedy, Tseng
      16             : //            PLDI 1991
      17             : //
      18             : // There's a single entry point that analyzes the dependence between a pair
      19             : // of memory references in a function, returning either NULL, for no dependence,
      20             : // or a more-or-less detailed description of the dependence between them.
      21             : //
      22             : // Currently, the implementation cannot propagate constraints between
      23             : // coupled RDIV subscripts and lacks a multi-subscript MIV test.
      24             : // Both of these are conservative weaknesses;
      25             : // that is, not a source of correctness problems.
      26             : //
      27             : // The implementation depends on the GEP instruction to differentiate
      28             : // subscripts. Since Clang linearizes some array subscripts, the dependence
      29             : // analysis is using SCEV->delinearize to recover the representation of multiple
      30             : // subscripts, and thus avoid the more expensive and less precise MIV tests. The
      31             : // delinearization is controlled by the flag -da-delinearize.
      32             : //
      33             : // We should pay some careful attention to the possibility of integer overflow
      34             : // in the implementation of the various tests. This could happen with Add,
      35             : // Subtract, or Multiply, with both APInt's and SCEV's.
      36             : //
      37             : // Some non-linear subscript pairs can be handled by the GCD test
      38             : // (and perhaps other tests).
      39             : // Should explore how often these things occur.
      40             : //
      41             : // Finally, it seems like certain test cases expose weaknesses in the SCEV
      42             : // simplification, especially in the handling of sign and zero extensions.
      43             : // It could be useful to spend time exploring these.
      44             : //
      45             : // Please note that this is work in progress and the interface is subject to
      46             : // change.
      47             : //
      48             : //===----------------------------------------------------------------------===//
      49             : //                                                                            //
      50             : //                   In memory of Ken Kennedy, 1945 - 2007                    //
      51             : //                                                                            //
      52             : //===----------------------------------------------------------------------===//
      53             : 
      54             : #include "llvm/Analysis/DependenceAnalysis.h"
      55             : #include "llvm/ADT/STLExtras.h"
      56             : #include "llvm/ADT/Statistic.h"
      57             : #include "llvm/Analysis/AliasAnalysis.h"
      58             : #include "llvm/Analysis/LoopInfo.h"
      59             : #include "llvm/Analysis/ScalarEvolution.h"
      60             : #include "llvm/Analysis/ScalarEvolutionExpressions.h"
      61             : #include "llvm/Analysis/ValueTracking.h"
      62             : #include "llvm/IR/InstIterator.h"
      63             : #include "llvm/IR/Module.h"
      64             : #include "llvm/IR/Operator.h"
      65             : #include "llvm/Support/CommandLine.h"
      66             : #include "llvm/Support/Debug.h"
      67             : #include "llvm/Support/ErrorHandling.h"
      68             : #include "llvm/Support/raw_ostream.h"
      69             : 
      70             : using namespace llvm;
      71             : 
      72             : #define DEBUG_TYPE "da"
      73             : 
      74             : //===----------------------------------------------------------------------===//
      75             : // statistics
      76             : 
      77             : STATISTIC(TotalArrayPairs, "Array pairs tested");
      78             : STATISTIC(SeparableSubscriptPairs, "Separable subscript pairs");
      79             : STATISTIC(CoupledSubscriptPairs, "Coupled subscript pairs");
      80             : STATISTIC(NonlinearSubscriptPairs, "Nonlinear subscript pairs");
      81             : STATISTIC(ZIVapplications, "ZIV applications");
      82             : STATISTIC(ZIVindependence, "ZIV independence");
      83             : STATISTIC(StrongSIVapplications, "Strong SIV applications");
      84             : STATISTIC(StrongSIVsuccesses, "Strong SIV successes");
      85             : STATISTIC(StrongSIVindependence, "Strong SIV independence");
      86             : STATISTIC(WeakCrossingSIVapplications, "Weak-Crossing SIV applications");
      87             : STATISTIC(WeakCrossingSIVsuccesses, "Weak-Crossing SIV successes");
      88             : STATISTIC(WeakCrossingSIVindependence, "Weak-Crossing SIV independence");
      89             : STATISTIC(ExactSIVapplications, "Exact SIV applications");
      90             : STATISTIC(ExactSIVsuccesses, "Exact SIV successes");
      91             : STATISTIC(ExactSIVindependence, "Exact SIV independence");
      92             : STATISTIC(WeakZeroSIVapplications, "Weak-Zero SIV applications");
      93             : STATISTIC(WeakZeroSIVsuccesses, "Weak-Zero SIV successes");
      94             : STATISTIC(WeakZeroSIVindependence, "Weak-Zero SIV independence");
      95             : STATISTIC(ExactRDIVapplications, "Exact RDIV applications");
      96             : STATISTIC(ExactRDIVindependence, "Exact RDIV independence");
      97             : STATISTIC(SymbolicRDIVapplications, "Symbolic RDIV applications");
      98             : STATISTIC(SymbolicRDIVindependence, "Symbolic RDIV independence");
      99             : STATISTIC(DeltaApplications, "Delta applications");
     100             : STATISTIC(DeltaSuccesses, "Delta successes");
     101             : STATISTIC(DeltaIndependence, "Delta independence");
     102             : STATISTIC(DeltaPropagations, "Delta propagations");
     103             : STATISTIC(GCDapplications, "GCD applications");
     104             : STATISTIC(GCDsuccesses, "GCD successes");
     105             : STATISTIC(GCDindependence, "GCD independence");
     106             : STATISTIC(BanerjeeApplications, "Banerjee applications");
     107             : STATISTIC(BanerjeeIndependence, "Banerjee independence");
     108             : STATISTIC(BanerjeeSuccesses, "Banerjee successes");
     109             : 
     110             : static cl::opt<bool>
     111      289224 : Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore,
     112      289224 :             cl::desc("Try to delinearize array references."));
     113             : 
     114             : //===----------------------------------------------------------------------===//
     115             : // basics
     116             : 
     117             : DependenceAnalysis::Result
     118           0 : DependenceAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
     119           0 :   auto &AA = FAM.getResult<AAManager>(F);
     120           0 :   auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
     121           0 :   auto &LI = FAM.getResult<LoopAnalysis>(F);
     122           0 :   return DependenceInfo(&F, &AA, &SE, &LI);
     123             : }
     124             : 
     125             : AnalysisKey DependenceAnalysis::Key;
     126             : 
     127       25723 : INITIALIZE_PASS_BEGIN(DependenceAnalysisWrapperPass, "da",
     128             :                       "Dependence Analysis", true, true)
     129       25723 : INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
     130       25723 : INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
     131       25723 : INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
     132      156218 : INITIALIZE_PASS_END(DependenceAnalysisWrapperPass, "da", "Dependence Analysis",
     133             :                     true, true)
     134             : 
     135             : char DependenceAnalysisWrapperPass::ID = 0;
     136             : 
     137           0 : FunctionPass *llvm::createDependenceAnalysisWrapperPass() {
     138           0 :   return new DependenceAnalysisWrapperPass();
     139             : }
     140             : 
     141         208 : bool DependenceAnalysisWrapperPass::runOnFunction(Function &F) {
     142         416 :   auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
     143         416 :   auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
     144         416 :   auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     145         624 :   info.reset(new DependenceInfo(&F, &AA, &SE, &LI));
     146         208 :   return false;
     147             : }
     148             : 
     149          50 : DependenceInfo &DependenceAnalysisWrapperPass::getDI() const { return *info; }
     150             : 
     151         416 : void DependenceAnalysisWrapperPass::releaseMemory() { info.reset(); }
     152             : 
     153          43 : void DependenceAnalysisWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
     154          86 :   AU.setPreservesAll();
     155          43 :   AU.addRequiredTransitive<AAResultsWrapperPass>();
     156          43 :   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
     157          43 :   AU.addRequiredTransitive<LoopInfoWrapperPass>();
     158          43 : }
     159             : 
     160             : 
     161             : // Used to test the dependence analyzer.
     162             : // Looks through the function, noting loads and stores.
     163             : // Calls depends() on every possible pair and prints out the result.
     164             : // Ignores all other instructions.
     165         183 : static void dumpExampleDependence(raw_ostream &OS, DependenceInfo *DA) {
     166         183 :   auto *F = DA->getFunction();
     167        4499 :   for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F); SrcI != SrcE;
     168             :        ++SrcI) {
     169       16534 :     if (isa<StoreInst>(*SrcI) || isa<LoadInst>(*SrcI)) {
     170        8024 :       for (inst_iterator DstI = SrcI, DstE = inst_end(F);
     171             :            DstI != DstE; ++DstI) {
     172       27642 :         if (isa<StoreInst>(*DstI) || isa<LoadInst>(*DstI)) {
     173        1665 :           OS << "da analyze - ";
     174        6660 :           if (auto D = DA->depends(&*SrcI, &*DstI, true)) {
     175         922 :             D->dump(OS);
     176        3272 :             for (unsigned Level = 1; Level <= D->getLevels(); Level++) {
     177         714 :               if (D->isSplitable(Level)) {
     178          20 :                 OS << "da analyze - split level = " << Level;
     179          30 :                 OS << ", iteration = " << *DA->getSplitIteration(*D, Level);
     180          10 :                 OS << "!\n";
     181             :               }
     182             :             }
     183             :           }
     184             :           else
     185         743 :             OS << "none!\n";
     186             :         }
     187             :       }
     188             :     }
     189             :   }
     190         183 : }
     191             : 
     192         183 : void DependenceAnalysisWrapperPass::print(raw_ostream &OS,
     193             :                                           const Module *) const {
     194         366 :   dumpExampleDependence(OS, info.get());
     195         183 : }
     196             : 
     197             : //===----------------------------------------------------------------------===//
     198             : // Dependence methods
     199             : 
     200             : // Returns true if this is an input dependence.
     201         105 : bool Dependence::isInput() const {
     202         105 :   return Src->mayReadFromMemory() && Dst->mayReadFromMemory();
     203             : }
     204             : 
     205             : 
     206             : // Returns true if this is an output dependence.
     207         277 : bool Dependence::isOutput() const {
     208         277 :   return Src->mayWriteToMemory() && Dst->mayWriteToMemory();
     209             : }
     210             : 
     211             : 
     212             : // Returns true if this is an flow (aka true)  dependence.
     213         376 : bool Dependence::isFlow() const {
     214         376 :   return Src->mayWriteToMemory() && Dst->mayReadFromMemory();
     215             : }
     216             : 
     217             : 
     218             : // Returns true if this is an anti dependence.
     219         127 : bool Dependence::isAnti() const {
     220         127 :   return Src->mayReadFromMemory() && Dst->mayWriteToMemory();
     221             : }
     222             : 
     223             : 
     224             : // Returns true if a particular level is scalar; that is,
     225             : // if no subscript in the source or destination mention the induction
     226             : // variable associated with the loop at this level.
     227             : // Leave this out of line, so it will serve as a virtual method anchor
     228           0 : bool Dependence::isScalar(unsigned level) const {
     229           0 :   return false;
     230             : }
     231             : 
     232             : 
     233             : //===----------------------------------------------------------------------===//
     234             : // FullDependence methods
     235             : 
     236         915 : FullDependence::FullDependence(Instruction *Source, Instruction *Destination,
     237             :                                bool PossiblyLoopIndependent,
     238         915 :                                unsigned CommonLevels)
     239             :     : Dependence(Source, Destination), Levels(CommonLevels),
     240        2745 :       LoopIndependent(PossiblyLoopIndependent) {
     241         915 :   Consistent = true;
     242         915 :   if (CommonLevels)
     243        2553 :     DV = make_unique<DVEntry[]>(CommonLevels);
     244         915 : }
     245             : 
     246             : // The rest are simple getters that hide the implementation.
     247             : 
     248             : // getDirection - Returns the direction associated with a particular level.
     249        1481 : unsigned FullDependence::getDirection(unsigned Level) const {
     250             :   assert(0 < Level && Level <= Levels && "Level out of range");
     251        2962 :   return DV[Level - 1].Direction;
     252             : }
     253             : 
     254             : 
     255             : // Returns the distance (or NULL) associated with a particular level.
     256         771 : const SCEV *FullDependence::getDistance(unsigned Level) const {
     257             :   assert(0 < Level && Level <= Levels && "Level out of range");
     258        1542 :   return DV[Level - 1].Distance;
     259             : }
     260             : 
     261             : 
     262             : // Returns true if a particular level is scalar; that is,
     263             : // if no subscript in the source or destination mention the induction
     264             : // variable associated with the loop at this level.
     265         633 : bool FullDependence::isScalar(unsigned Level) const {
     266             :   assert(0 < Level && Level <= Levels && "Level out of range");
     267        1266 :   return DV[Level - 1].Scalar;
     268             : }
     269             : 
     270             : 
     271             : // Returns true if peeling the first iteration from this loop
     272             : // will break this dependence.
     273         714 : bool FullDependence::isPeelFirst(unsigned Level) const {
     274             :   assert(0 < Level && Level <= Levels && "Level out of range");
     275        1428 :   return DV[Level - 1].PeelFirst;
     276             : }
     277             : 
     278             : 
     279             : // Returns true if peeling the last iteration from this loop
     280             : // will break this dependence.
     281         714 : bool FullDependence::isPeelLast(unsigned Level) const {
     282             :   assert(0 < Level && Level <= Levels && "Level out of range");
     283        1428 :   return DV[Level - 1].PeelLast;
     284             : }
     285             : 
     286             : 
     287             : // Returns true if splitting this loop will break the dependence.
     288        1428 : bool FullDependence::isSplitable(unsigned Level) const {
     289             :   assert(0 < Level && Level <= Levels && "Level out of range");
     290        2856 :   return DV[Level - 1].Splitable;
     291             : }
     292             : 
     293             : 
     294             : //===----------------------------------------------------------------------===//
     295             : // DependenceInfo::Constraint methods
     296             : 
     297             : // If constraint is a point <X, Y>, returns X.
     298             : // Otherwise assert.
     299          41 : const SCEV *DependenceInfo::Constraint::getX() const {
     300             :   assert(Kind == Point && "Kind should be Point");
     301          41 :   return A;
     302             : }
     303             : 
     304             : 
     305             : // If constraint is a point <X, Y>, returns Y.
     306             : // Otherwise assert.
     307          41 : const SCEV *DependenceInfo::Constraint::getY() const {
     308             :   assert(Kind == Point && "Kind should be Point");
     309          41 :   return B;
     310             : }
     311             : 
     312             : 
     313             : // If constraint is a line AX + BY = C, returns A.
     314             : // Otherwise assert.
     315         112 : const SCEV *DependenceInfo::Constraint::getA() const {
     316             :   assert((Kind == Line || Kind == Distance) &&
     317             :          "Kind should be Line (or Distance)");
     318         112 :   return A;
     319             : }
     320             : 
     321             : 
     322             : // If constraint is a line AX + BY = C, returns B.
     323             : // Otherwise assert.
     324         120 : const SCEV *DependenceInfo::Constraint::getB() const {
     325             :   assert((Kind == Line || Kind == Distance) &&
     326             :          "Kind should be Line (or Distance)");
     327         120 :   return B;
     328             : }
     329             : 
     330             : 
     331             : // If constraint is a line AX + BY = C, returns C.
     332             : // Otherwise assert.
     333          81 : const SCEV *DependenceInfo::Constraint::getC() const {
     334             :   assert((Kind == Line || Kind == Distance) &&
     335             :          "Kind should be Line (or Distance)");
     336          81 :   return C;
     337             : }
     338             : 
     339             : 
     340             : // If constraint is a distance, returns D.
     341             : // Otherwise assert.
     342         279 : const SCEV *DependenceInfo::Constraint::getD() const {
     343             :   assert(Kind == Distance && "Kind should be Distance");
     344         279 :   return SE->getNegativeSCEV(C);
     345             : }
     346             : 
     347             : 
     348             : // Returns the loop associated with this constraint.
     349          94 : const Loop *DependenceInfo::Constraint::getAssociatedLoop() const {
     350             :   assert((Kind == Distance || Kind == Line || Kind == Point) &&
     351             :          "Kind should be Distance, Line, or Point");
     352          94 :   return AssociatedLoop;
     353             : }
     354             : 
     355          13 : void DependenceInfo::Constraint::setPoint(const SCEV *X, const SCEV *Y,
     356             :                                           const Loop *CurLoop) {
     357          13 :   Kind = Point;
     358          13 :   A = X;
     359          13 :   B = Y;
     360          13 :   AssociatedLoop = CurLoop;
     361          13 : }
     362             : 
     363         118 : void DependenceInfo::Constraint::setLine(const SCEV *AA, const SCEV *BB,
     364             :                                          const SCEV *CC, const Loop *CurLoop) {
     365         118 :   Kind = Line;
     366         118 :   A = AA;
     367         118 :   B = BB;
     368         118 :   C = CC;
     369         118 :   AssociatedLoop = CurLoop;
     370         118 : }
     371             : 
     372         529 : void DependenceInfo::Constraint::setDistance(const SCEV *D,
     373             :                                              const Loop *CurLoop) {
     374         529 :   Kind = Distance;
     375        1058 :   A = SE->getOne(D->getType());
     376         529 :   B = SE->getNegativeSCEV(A);
     377         529 :   C = SE->getNegativeSCEV(D);
     378         529 :   AssociatedLoop = CurLoop;
     379         529 : }
     380             : 
     381           7 : void DependenceInfo::Constraint::setEmpty() { Kind = Empty; }
     382             : 
     383        1262 : void DependenceInfo::Constraint::setAny(ScalarEvolution *NewSE) {
     384        1262 :   SE = NewSE;
     385        1262 :   Kind = Any;
     386        1262 : }
     387             : 
     388             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     389             : // For debugging purposes. Dumps the constraint out to OS.
     390             : LLVM_DUMP_METHOD void DependenceInfo::Constraint::dump(raw_ostream &OS) const {
     391             :   if (isEmpty())
     392             :     OS << " Empty\n";
     393             :   else if (isAny())
     394             :     OS << " Any\n";
     395             :   else if (isPoint())
     396             :     OS << " Point is <" << *getX() << ", " << *getY() << ">\n";
     397             :   else if (isDistance())
     398             :     OS << " Distance is " << *getD() <<
     399             :       " (" << *getA() << "*X + " << *getB() << "*Y = " << *getC() << ")\n";
     400             :   else if (isLine())
     401             :     OS << " Line is " << *getA() << "*X + " <<
     402             :       *getB() << "*Y = " << *getC() << "\n";
     403             :   else
     404             :     llvm_unreachable("unknown constraint type in Constraint::dump");
     405             : }
     406             : #endif
     407             : 
     408             : 
     409             : // Updates X with the intersection
     410             : // of the Constraints X and Y. Returns true if X has changed.
     411             : // Corresponds to Figure 4 from the paper
     412             : //
     413             : //            Practical Dependence Testing
     414             : //            Goff, Kennedy, Tseng
     415             : //            PLDI 1991
     416         236 : bool DependenceInfo::intersectConstraints(Constraint *X, const Constraint *Y) {
     417         236 :   ++DeltaApplications;
     418             :   DEBUG(dbgs() << "\tintersect constraints\n");
     419             :   DEBUG(dbgs() << "\t    X ="; X->dump(dbgs()));
     420             :   DEBUG(dbgs() << "\t    Y ="; Y->dump(dbgs()));
     421             :   assert(!Y->isPoint() && "Y must not be a Point");
     422         236 :   if (X->isAny()) {
     423         165 :     if (Y->isAny())
     424             :       return false;
     425         165 :     *X = *Y;
     426         165 :     return true;
     427             :   }
     428          71 :   if (X->isEmpty())
     429             :     return false;
     430          71 :   if (Y->isEmpty()) {
     431           0 :     X->setEmpty();
     432           0 :     return true;
     433             :   }
     434             : 
     435          71 :   if (X->isDistance() && Y->isDistance()) {
     436             :     DEBUG(dbgs() << "\t    intersect 2 distances\n");
     437          49 :     if (isKnownPredicate(CmpInst::ICMP_EQ, X->getD(), Y->getD()))
     438             :       return false;
     439           1 :     if (isKnownPredicate(CmpInst::ICMP_NE, X->getD(), Y->getD())) {
     440           1 :       X->setEmpty();
     441           1 :       ++DeltaSuccesses;
     442           1 :       return true;
     443             :     }
     444             :     // Hmmm, interesting situation.
     445             :     // I guess if either is constant, keep it and ignore the other.
     446           0 :     if (isa<SCEVConstant>(Y->getD())) {
     447           0 :       *X = *Y;
     448           0 :       return true;
     449             :     }
     450             :     return false;
     451             :   }
     452             : 
     453             :   // At this point, the pseudo-code in Figure 4 of the paper
     454             :   // checks if (X->isPoint() && Y->isPoint()).
     455             :   // This case can't occur in our implementation,
     456             :   // since a Point can only arise as the result of intersecting
     457             :   // two Line constraints, and the right-hand value, Y, is never
     458             :   // the result of an intersection.
     459             :   assert(!(X->isPoint() && Y->isPoint()) &&
     460             :          "We shouldn't ever see X->isPoint() && Y->isPoint()");
     461             : 
     462          84 :   if (X->isLine() && Y->isLine()) {
     463             :     DEBUG(dbgs() << "\t    intersect 2 lines\n");
     464          20 :     const SCEV *Prod1 = SE->getMulExpr(X->getA(), Y->getB());
     465          20 :     const SCEV *Prod2 = SE->getMulExpr(X->getB(), Y->getA());
     466          20 :     if (isKnownPredicate(CmpInst::ICMP_EQ, Prod1, Prod2)) {
     467             :       // slopes are equal, so lines are parallel
     468             :       DEBUG(dbgs() << "\t\tsame slope\n");
     469           4 :       Prod1 = SE->getMulExpr(X->getC(), Y->getB());
     470           4 :       Prod2 = SE->getMulExpr(X->getB(), Y->getC());
     471           4 :       if (isKnownPredicate(CmpInst::ICMP_EQ, Prod1, Prod2))
     472             :         return false;
     473           3 :       if (isKnownPredicate(CmpInst::ICMP_NE, Prod1, Prod2)) {
     474           2 :         X->setEmpty();
     475           2 :         ++DeltaSuccesses;
     476           2 :         return true;
     477             :       }
     478             :       return false;
     479             :     }
     480          16 :     if (isKnownPredicate(CmpInst::ICMP_NE, Prod1, Prod2)) {
     481             :       // slopes differ, so lines intersect
     482             :       DEBUG(dbgs() << "\t\tdifferent slopes\n");
     483          16 :       const SCEV *C1B2 = SE->getMulExpr(X->getC(), Y->getB());
     484          16 :       const SCEV *C1A2 = SE->getMulExpr(X->getC(), Y->getA());
     485          16 :       const SCEV *C2B1 = SE->getMulExpr(Y->getC(), X->getB());
     486          16 :       const SCEV *C2A1 = SE->getMulExpr(Y->getC(), X->getA());
     487          16 :       const SCEV *A1B2 = SE->getMulExpr(X->getA(), Y->getB());
     488          16 :       const SCEV *A2B1 = SE->getMulExpr(Y->getA(), X->getB());
     489             :       const SCEVConstant *C1A2_C2A1 =
     490          32 :         dyn_cast<SCEVConstant>(SE->getMinusSCEV(C1A2, C2A1));
     491             :       const SCEVConstant *C1B2_C2B1 =
     492          32 :         dyn_cast<SCEVConstant>(SE->getMinusSCEV(C1B2, C2B1));
     493             :       const SCEVConstant *A1B2_A2B1 =
     494          32 :         dyn_cast<SCEVConstant>(SE->getMinusSCEV(A1B2, A2B1));
     495             :       const SCEVConstant *A2B1_A1B2 =
     496          32 :         dyn_cast<SCEVConstant>(SE->getMinusSCEV(A2B1, A1B2));
     497          16 :       if (!C1B2_C2B1 || !C1A2_C2A1 ||
     498          16 :           !A1B2_A2B1 || !A2B1_A1B2)
     499             :         return false;
     500          32 :       APInt Xtop = C1B2_C2B1->getAPInt();
     501          48 :       APInt Xbot = A1B2_A2B1->getAPInt();
     502          48 :       APInt Ytop = C1A2_C2A1->getAPInt();
     503          48 :       APInt Ybot = A2B1_A1B2->getAPInt();
     504             :       DEBUG(dbgs() << "\t\tXtop = " << Xtop << "\n");
     505             :       DEBUG(dbgs() << "\t\tXbot = " << Xbot << "\n");
     506             :       DEBUG(dbgs() << "\t\tYtop = " << Ytop << "\n");
     507             :       DEBUG(dbgs() << "\t\tYbot = " << Ybot << "\n");
     508          32 :       APInt Xq = Xtop; // these need to be initialized, even
     509          32 :       APInt Xr = Xtop; // though they're just going to be overwritten
     510          16 :       APInt::sdivrem(Xtop, Xbot, Xq, Xr);
     511          32 :       APInt Yq = Ytop;
     512          32 :       APInt Yr = Ytop;
     513          16 :       APInt::sdivrem(Ytop, Ybot, Yq, Yr);
     514          31 :       if (Xr != 0 || Yr != 0) {
     515           1 :         X->setEmpty();
     516           1 :         ++DeltaSuccesses;
     517           1 :         return true;
     518             :       }
     519             :       DEBUG(dbgs() << "\t\tX = " << Xq << ", Y = " << Yq << "\n");
     520          30 :       if (Xq.slt(0) || Yq.slt(0)) {
     521           1 :         X->setEmpty();
     522           1 :         ++DeltaSuccesses;
     523           1 :         return true;
     524             :       }
     525          14 :       if (const SCEVConstant *CUB =
     526          14 :           collectConstantUpperBound(X->getAssociatedLoop(), Prod1->getType())) {
     527          13 :         const APInt &UpperBound = CUB->getAPInt();
     528             :         DEBUG(dbgs() << "\t\tupper bound = " << UpperBound << "\n");
     529          26 :         if (Xq.sgt(UpperBound) || Yq.sgt(UpperBound)) {
     530           1 :           X->setEmpty();
     531           1 :           ++DeltaSuccesses;
     532           1 :           return true;
     533             :         }
     534             :       }
     535          26 :       X->setPoint(SE->getConstant(Xq),
     536          13 :                   SE->getConstant(Yq),
     537             :                   X->getAssociatedLoop());
     538          13 :       ++DeltaSuccesses;
     539          13 :       return true;
     540             :     }
     541             :     return false;
     542             :   }
     543             : 
     544             :   // if (X->isLine() && Y->isPoint()) This case can't occur.
     545             :   assert(!(X->isLine() && Y->isPoint()) && "This case should never occur");
     546             : 
     547           6 :   if (X->isPoint() && Y->isLine()) {
     548             :     DEBUG(dbgs() << "\t    intersect Point and Line\n");
     549           2 :     const SCEV *A1X1 = SE->getMulExpr(Y->getA(), X->getX());
     550           2 :     const SCEV *B1Y1 = SE->getMulExpr(Y->getB(), X->getY());
     551           2 :     const SCEV *Sum = SE->getAddExpr(A1X1, B1Y1);
     552           2 :     if (isKnownPredicate(CmpInst::ICMP_EQ, Sum, Y->getC()))
     553             :       return false;
     554           1 :     if (isKnownPredicate(CmpInst::ICMP_NE, Sum, Y->getC())) {
     555           1 :       X->setEmpty();
     556           1 :       ++DeltaSuccesses;
     557           1 :       return true;
     558             :     }
     559             :     return false;
     560             :   }
     561             : 
     562           0 :   llvm_unreachable("shouldn't reach the end of Constraint intersection");
     563             :   return false;
     564             : }
     565             : 
     566             : 
     567             : //===----------------------------------------------------------------------===//
     568             : // DependenceInfo methods
     569             : 
     570             : // For debugging purposes. Dumps a dependence to OS.
     571         922 : void Dependence::dump(raw_ostream &OS) const {
     572         922 :   bool Splitable = false;
     573         922 :   if (isConfused())
     574         546 :     OS << "confused";
     575             :   else {
     576         376 :     if (isConsistent())
     577         160 :       OS << "consistent ";
     578         376 :     if (isFlow())
     579          99 :       OS << "flow";
     580         277 :     else if (isOutput())
     581         150 :       OS << "output";
     582         127 :     else if (isAnti())
     583          22 :       OS << "anti";
     584         105 :     else if (isInput())
     585         105 :       OS << "input";
     586         376 :     unsigned Levels = getLevels();
     587         376 :     OS << " [";
     588        1090 :     for (unsigned II = 1; II <= Levels; ++II) {
     589         714 :       if (isSplitable(II))
     590          10 :         Splitable = true;
     591         714 :       if (isPeelFirst(II))
     592             :         OS << 'p';
     593         714 :       const SCEV *Distance = getDistance(II);
     594         714 :       if (Distance)
     595             :         OS << *Distance;
     596         620 :       else if (isScalar(II))
     597         245 :         OS << "S";
     598             :       else {
     599         375 :         unsigned Direction = getDirection(II);
     600         375 :         if (Direction == DVEntry::ALL)
     601         291 :           OS << "*";
     602             :         else {
     603          84 :           if (Direction & DVEntry::LT)
     604          42 :             OS << "<";
     605          84 :           if (Direction & DVEntry::EQ)
     606          39 :             OS << "=";
     607          84 :           if (Direction & DVEntry::GT)
     608          50 :             OS << ">";
     609             :         }
     610             :       }
     611         714 :       if (isPeelLast(II))
     612             :         OS << 'p';
     613         714 :       if (II < Levels)
     614         352 :         OS << " ";
     615             :     }
     616         376 :     if (isLoopIndependent())
     617         174 :       OS << "|<";
     618         376 :     OS << "]";
     619         376 :     if (Splitable)
     620          10 :       OS << " splitable";
     621             :   }
     622         922 :   OS << "!\n";
     623         922 : }
     624             : 
     625        1726 : static AliasResult underlyingObjectsAlias(AliasAnalysis *AA,
     626             :                                           const DataLayout &DL, const Value *A,
     627             :                                           const Value *B) {
     628        1726 :   const Value *AObj = GetUnderlyingObject(A, DL);
     629        1726 :   const Value *BObj = GetUnderlyingObject(B, DL);
     630        5178 :   return AA->alias(AObj, DL.getTypeStoreSize(AObj->getType()),
     631        1726 :                    BObj, DL.getTypeStoreSize(BObj->getType()));
     632             : }
     633             : 
     634             : 
     635             : // Returns true if the load or store can be analyzed. Atomic and volatile
     636             : // operations have properties which this analysis does not understand.
     637             : static
     638        3452 : bool isLoadOrStore(const Instruction *I) {
     639        1335 :   if (const LoadInst *LI = dyn_cast<LoadInst>(I))
     640             :     return LI->isUnordered();
     641        2117 :   else if (const StoreInst *SI = dyn_cast<StoreInst>(I))
     642             :     return SI->isUnordered();
     643             :   return false;
     644             : }
     645             : 
     646             : 
     647             : static
     648             : Value *getPointerOperand(Instruction *I) {
     649        1421 :   if (LoadInst *LI = dyn_cast<LoadInst>(I))
     650             :     return LI->getPointerOperand();
     651        2251 :   if (StoreInst *SI = dyn_cast<StoreInst>(I))
     652             :     return SI->getPointerOperand();
     653           0 :   llvm_unreachable("Value is not load or store instruction");
     654             :   return nullptr;
     655             : }
     656             : 
     657             : 
     658             : // Examines the loop nesting of the Src and Dst
     659             : // instructions and establishes their shared loops. Sets the variables
     660             : // CommonLevels, SrcLevels, and MaxLevels.
     661             : // The source and destination instructions needn't be contained in the same
     662             : // loop. The routine establishNestingLevels finds the level of most deeply
     663             : // nested loop that contains them both, CommonLevels. An instruction that's
     664             : // not contained in a loop is at level = 0. MaxLevels is equal to the level
     665             : // of the source plus the level of the destination, minus CommonLevels.
     666             : // This lets us allocate vectors MaxLevels in length, with room for every
     667             : // distinct loop referenced in both the source and destination subscripts.
     668             : // The variable SrcLevels is the nesting depth of the source instruction.
     669             : // It's used to help calculate distinct loops referenced by the destination.
     670             : // Here's the map from loops to levels:
     671             : //            0 - unused
     672             : //            1 - outermost common loop
     673             : //          ... - other common loops
     674             : // CommonLevels - innermost common loop
     675             : //          ... - loops containing Src but not Dst
     676             : //    SrcLevels - innermost loop containing Src but not Dst
     677             : //          ... - loops containing Dst but not Src
     678             : //    MaxLevels - innermost loops containing Dst but not Src
     679             : // Consider the follow code fragment:
     680             : //   for (a = ...) {
     681             : //     for (b = ...) {
     682             : //       for (c = ...) {
     683             : //         for (d = ...) {
     684             : //           A[] = ...;
     685             : //         }
     686             : //       }
     687             : //       for (e = ...) {
     688             : //         for (f = ...) {
     689             : //           for (g = ...) {
     690             : //             ... = A[];
     691             : //           }
     692             : //         }
     693             : //       }
     694             : //     }
     695             : //   }
     696             : // If we're looking at the possibility of a dependence between the store
     697             : // to A (the Src) and the load from A (the Dst), we'll note that they
     698             : // have 2 loops in common, so CommonLevels will equal 2 and the direction
     699             : // vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7.
     700             : // A map from loop names to loop numbers would look like
     701             : //     a - 1
     702             : //     b - 2 = CommonLevels
     703             : //     c - 3
     704             : //     d - 4 = SrcLevels
     705             : //     e - 5
     706             : //     f - 6
     707             : //     g - 7 = MaxLevels
     708         915 : void DependenceInfo::establishNestingLevels(const Instruction *Src,
     709             :                                             const Instruction *Dst) {
     710         915 :   const BasicBlock *SrcBlock = Src->getParent();
     711         915 :   const BasicBlock *DstBlock = Dst->getParent();
     712         915 :   unsigned SrcLevel = LI->getLoopDepth(SrcBlock);
     713         915 :   unsigned DstLevel = LI->getLoopDepth(DstBlock);
     714        1830 :   const Loop *SrcLoop = LI->getLoopFor(SrcBlock);
     715        1830 :   const Loop *DstLoop = LI->getLoopFor(DstBlock);
     716         915 :   SrcLevels = SrcLevel;
     717         915 :   MaxLevels = SrcLevel + DstLevel;
     718         939 :   while (SrcLevel > DstLevel) {
     719          12 :     SrcLoop = SrcLoop->getParentLoop();
     720          12 :     SrcLevel--;
     721             :   }
     722         955 :   while (DstLevel > SrcLevel) {
     723          20 :     DstLoop = DstLoop->getParentLoop();
     724          20 :     DstLevel--;
     725             :   }
     726         995 :   while (SrcLoop != DstLoop) {
     727          40 :     SrcLoop = SrcLoop->getParentLoop();
     728          40 :     DstLoop = DstLoop->getParentLoop();
     729          40 :     SrcLevel--;
     730             :   }
     731         915 :   CommonLevels = SrcLevel;
     732         915 :   MaxLevels -= CommonLevels;
     733         915 : }
     734             : 
     735             : 
     736             : // Given one of the loops containing the source, return
     737             : // its level index in our numbering scheme.
     738        2318 : unsigned DependenceInfo::mapSrcLoop(const Loop *SrcLoop) const {
     739        4636 :   return SrcLoop->getLoopDepth();
     740             : }
     741             : 
     742             : 
     743             : // Given one of the loops containing the destination,
     744             : // return its level index in our numbering scheme.
     745        1585 : unsigned DependenceInfo::mapDstLoop(const Loop *DstLoop) const {
     746        3170 :   unsigned D = DstLoop->getLoopDepth();
     747        1585 :   if (D > CommonLevels)
     748          22 :     return D - CommonLevels + SrcLevels;
     749             :   else
     750             :     return D;
     751             : }
     752             : 
     753             : 
     754             : // Returns true if Expression is loop invariant in LoopNest.
     755       18487 : bool DependenceInfo::isLoopInvariant(const SCEV *Expression,
     756             :                                      const Loop *LoopNest) const {
     757       18487 :   if (!LoopNest)
     758             :     return true;
     759       24679 :   return SE->isLoopInvariant(Expression, LoopNest) &&
     760       12299 :     isLoopInvariant(Expression, LoopNest->getParentLoop());
     761             : }
     762             : 
     763             : 
     764             : 
     765             : // Finds the set of loops from the LoopNest that
     766             : // have a level <= CommonLevels and are referred to by the SCEV Expression.
     767         162 : void DependenceInfo::collectCommonLoops(const SCEV *Expression,
     768             :                                         const Loop *LoopNest,
     769             :                                         SmallBitVector &Loops) const {
     770         822 :   while (LoopNest) {
     771         660 :     unsigned Level = LoopNest->getLoopDepth();
     772         330 :     if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest))
     773         314 :       Loops.set(Level);
     774         330 :     LoopNest = LoopNest->getParentLoop();
     775             :   }
     776         162 : }
     777             : 
     778        1024 : void DependenceInfo::unifySubscriptType(ArrayRef<Subscript *> Pairs) {
     779             : 
     780        1024 :   unsigned widestWidthSeen = 0;
     781             :   Type *widestType;
     782             : 
     783             :   // Go through each pair and find the widest bit to which we need
     784             :   // to extend all of them.
     785        3212 :   for (Subscript *Pair : Pairs) {
     786        1164 :     const SCEV *Src = Pair->Src;
     787        1164 :     const SCEV *Dst = Pair->Dst;
     788        2328 :     IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
     789        2328 :     IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
     790        1164 :     if (SrcTy == nullptr || DstTy == nullptr) {
     791             :       assert(SrcTy == DstTy && "This function only unify integer types and "
     792             :              "expect Src and Dst share the same type "
     793             :              "otherwise.");
     794           0 :       continue;
     795             :     }
     796        1164 :     if (SrcTy->getBitWidth() > widestWidthSeen) {
     797        1024 :       widestWidthSeen = SrcTy->getBitWidth();
     798        1024 :       widestType = SrcTy;
     799             :     }
     800        1164 :     if (DstTy->getBitWidth() > widestWidthSeen) {
     801           0 :       widestWidthSeen = DstTy->getBitWidth();
     802           0 :       widestType = DstTy;
     803             :     }
     804             :   }
     805             : 
     806             : 
     807             :   assert(widestWidthSeen > 0);
     808             : 
     809             :   // Now extend each pair to the widest seen.
     810        3352 :   for (Subscript *Pair : Pairs) {
     811        1164 :     const SCEV *Src = Pair->Src;
     812        1164 :     const SCEV *Dst = Pair->Dst;
     813        2328 :     IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
     814        2328 :     IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
     815        1164 :     if (SrcTy == nullptr || DstTy == nullptr) {
     816             :       assert(SrcTy == DstTy && "This function only unify integer types and "
     817             :              "expect Src and Dst share the same type "
     818             :              "otherwise.");
     819           0 :       continue;
     820             :     }
     821        1164 :     if (SrcTy->getBitWidth() < widestWidthSeen)
     822             :       // Sign-extend Src to widestType
     823           2 :       Pair->Src = SE->getSignExtendExpr(Src, widestType);
     824        1164 :     if (DstTy->getBitWidth() < widestWidthSeen) {
     825             :       // Sign-extend Dst to widestType
     826           4 :       Pair->Dst = SE->getSignExtendExpr(Dst, widestType);
     827             :     }
     828             :   }
     829        1024 : }
     830             : 
     831             : // removeMatchingExtensions - Examines a subscript pair.
     832             : // If the source and destination are identically sign (or zero)
     833             : // extended, it strips off the extension in an effect to simplify
     834             : // the actual analysis.
     835        1218 : void DependenceInfo::removeMatchingExtensions(Subscript *Pair) {
     836        1218 :   const SCEV *Src = Pair->Src;
     837        1218 :   const SCEV *Dst = Pair->Dst;
     838        3656 :   if ((isa<SCEVZeroExtendExpr>(Src) && isa<SCEVZeroExtendExpr>(Dst)) ||
     839        1250 :       (isa<SCEVSignExtendExpr>(Src) && isa<SCEVSignExtendExpr>(Dst))) {
     840          44 :     const SCEVCastExpr *SrcCast = cast<SCEVCastExpr>(Src);
     841          44 :     const SCEVCastExpr *DstCast = cast<SCEVCastExpr>(Dst);
     842          22 :     const SCEV *SrcCastOp = SrcCast->getOperand();
     843          22 :     const SCEV *DstCastOp = DstCast->getOperand();
     844          22 :     if (SrcCastOp->getType() == DstCastOp->getType()) {
     845          22 :       Pair->Src = SrcCastOp;
     846          22 :       Pair->Dst = DstCastOp;
     847             :     }
     848             :   }
     849        1218 : }
     850             : 
     851             : 
     852             : // Examine the scev and return true iff it's linear.
     853             : // Collect any loops mentioned in the set of "Loops".
     854        1281 : bool DependenceInfo::checkSrcSubscript(const SCEV *Src, const Loop *LoopNest,
     855             :                                        SmallBitVector &Loops) {
     856        1271 :   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Src);
     857             :   if (!AddRec)
     858        1277 :     return isLoopInvariant(Src, LoopNest);
     859        1271 :   const SCEV *Start = AddRec->getStart();
     860        1271 :   const SCEV *Step = AddRec->getStepRecurrence(*SE);
     861        1271 :   const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop());
     862        2542 :   if (!isa<SCEVCouldNotCompute>(UB)) {
     863        2528 :     if (SE->getTypeSizeInBits(Start->getType()) <
     864        1264 :         SE->getTypeSizeInBits(UB->getType())) {
     865          16 :       if (!AddRec->getNoWrapFlags())
     866             :         return false;
     867             :     }
     868             :   }
     869        1267 :   if (!isLoopInvariant(Step, LoopNest))
     870             :     return false;
     871        1267 :   Loops.set(mapSrcLoop(AddRec->getLoop()));
     872        1267 :   return checkSrcSubscript(Start, LoopNest, Loops);
     873             : }
     874             : 
     875             : 
     876             : 
     877             : // Examine the scev and return true iff it's linear.
     878             : // Collect any loops mentioned in the set of "Loops".
     879        1200 : bool DependenceInfo::checkDstSubscript(const SCEV *Dst, const Loop *LoopNest,
     880             :                                        SmallBitVector &Loops) {
     881        1188 :   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Dst);
     882             :   if (!AddRec)
     883        1200 :     return isLoopInvariant(Dst, LoopNest);
     884        1188 :   const SCEV *Start = AddRec->getStart();
     885        1188 :   const SCEV *Step = AddRec->getStepRecurrence(*SE);
     886        1188 :   const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop());
     887        2376 :   if (!isa<SCEVCouldNotCompute>(UB)) {
     888        2362 :     if (SE->getTypeSizeInBits(Start->getType()) <
     889        1181 :         SE->getTypeSizeInBits(UB->getType())) {
     890           6 :       if (!AddRec->getNoWrapFlags())
     891             :         return false;
     892             :     }
     893             :   }
     894        1188 :   if (!isLoopInvariant(Step, LoopNest))
     895             :     return false;
     896        1188 :   Loops.set(mapDstLoop(AddRec->getLoop()));
     897        1188 :   return checkDstSubscript(Start, LoopNest, Loops);
     898             : }
     899             : 
     900             : 
     901             : // Examines the subscript pair (the Src and Dst SCEVs)
     902             : // and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear.
     903             : // Collects the associated loops in a set.
     904             : DependenceInfo::Subscript::ClassificationKind
     905        1281 : DependenceInfo::classifyPair(const SCEV *Src, const Loop *SrcLoopNest,
     906             :                              const SCEV *Dst, const Loop *DstLoopNest,
     907             :                              SmallBitVector &Loops) {
     908        2562 :   SmallBitVector SrcLoops(MaxLevels + 1);
     909        2562 :   SmallBitVector DstLoops(MaxLevels + 1);
     910        1281 :   if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops))
     911             :     return Subscript::NonLinear;
     912        1200 :   if (!checkDstSubscript(Dst, DstLoopNest, DstLoops))
     913             :     return Subscript::NonLinear;
     914        1200 :   Loops = SrcLoops;
     915        1200 :   Loops |= DstLoops;
     916        1200 :   unsigned N = Loops.count();
     917        1200 :   if (N == 0)
     918             :     return Subscript::ZIV;
     919         950 :   if (N == 1)
     920             :     return Subscript::SIV;
     921         579 :   if (N == 2 && (SrcLoops.count() == 0 ||
     922         551 :                  DstLoops.count() == 0 ||
     923          31 :                  (SrcLoops.count() == 1 && DstLoops.count() == 1)))
     924             :     return Subscript::RDIV;
     925             :   return Subscript::MIV;
     926             : }
     927             : 
     928             : 
     929             : // A wrapper around SCEV::isKnownPredicate.
     930             : // Looks for cases where we're interested in comparing for equality.
     931             : // If both X and Y have been identically sign or zero extended,
     932             : // it strips off the (confusing) extensions before invoking
     933             : // SCEV::isKnownPredicate. Perhaps, someday, the ScalarEvolution package
     934             : // will be similarly updated.
     935             : //
     936             : // If SCEV::isKnownPredicate can't prove the predicate,
     937             : // we try simple subtraction, which seems to help in some cases
     938             : // involving symbolics.
     939        6305 : bool DependenceInfo::isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *X,
     940             :                                       const SCEV *Y) const {
     941        6305 :   if (Pred == CmpInst::ICMP_EQ ||
     942             :       Pred == CmpInst::ICMP_NE) {
     943        1197 :     if ((isa<SCEVSignExtendExpr>(X) &&
     944        2378 :          isa<SCEVSignExtendExpr>(Y)) ||
     945        1189 :         (isa<SCEVZeroExtendExpr>(X) &&
     946           0 :          isa<SCEVZeroExtendExpr>(Y))) {
     947           0 :       const SCEVCastExpr *CX = cast<SCEVCastExpr>(X);
     948           0 :       const SCEVCastExpr *CY = cast<SCEVCastExpr>(Y);
     949           0 :       const SCEV *Xop = CX->getOperand();
     950           0 :       const SCEV *Yop = CY->getOperand();
     951           0 :       if (Xop->getType() == Yop->getType()) {
     952           0 :         X = Xop;
     953           0 :         Y = Yop;
     954             :       }
     955             :     }
     956             :   }
     957        6305 :   if (SE->isKnownPredicate(Pred, X, Y))
     958             :     return true;
     959             :   // If SE->isKnownPredicate can't prove the condition,
     960             :   // we try the brute-force approach of subtracting
     961             :   // and testing the difference.
     962             :   // By testing with SE->isKnownPredicate first, we avoid
     963             :   // the possibility of overflow when the arguments are constants.
     964        4406 :   const SCEV *Delta = SE->getMinusSCEV(X, Y);
     965        4406 :   switch (Pred) {
     966          96 :   case CmpInst::ICMP_EQ:
     967          96 :     return Delta->isZero();
     968          10 :   case CmpInst::ICMP_NE:
     969          10 :     return SE->isKnownNonZero(Delta);
     970           4 :   case CmpInst::ICMP_SGE:
     971           4 :     return SE->isKnownNonNegative(Delta);
     972           2 :   case CmpInst::ICMP_SLE:
     973           2 :     return SE->isKnownNonPositive(Delta);
     974        3727 :   case CmpInst::ICMP_SGT:
     975        3727 :     return SE->isKnownPositive(Delta);
     976         567 :   case CmpInst::ICMP_SLT:
     977         567 :     return SE->isKnownNegative(Delta);
     978           0 :   default:
     979           0 :     llvm_unreachable("unexpected predicate in isKnownPredicate");
     980             :   }
     981             : }
     982             : 
     983             : 
     984             : // All subscripts are all the same type.
     985             : // Loop bound may be smaller (e.g., a char).
     986             : // Should zero extend loop bound, since it's always >= 0.
     987             : // This routine collects upper bound and extends or truncates if needed.
     988             : // Truncating is safe when subscripts are known not to wrap. Cases without
     989             : // nowrap flags should have been rejected earlier.
     990             : // Return null if no bound available.
     991        2685 : const SCEV *DependenceInfo::collectUpperBound(const Loop *L, Type *T) const {
     992        2685 :   if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
     993        2665 :     const SCEV *UB = SE->getBackedgeTakenCount(L);
     994        2665 :     return SE->getTruncateOrZeroExtend(UB, T);
     995             :   }
     996             :   return nullptr;
     997             : }
     998             : 
     999             : 
    1000             : // Calls collectUpperBound(), then attempts to cast it to SCEVConstant.
    1001             : // If the cast fails, returns NULL.
    1002          92 : const SCEVConstant *DependenceInfo::collectConstantUpperBound(const Loop *L,
    1003             :                                                               Type *T) const {
    1004          92 :   if (const SCEV *UB = collectUpperBound(L, T))
    1005             :     return dyn_cast<SCEVConstant>(UB);
    1006             :   return nullptr;
    1007             : }
    1008             : 
    1009             : 
    1010             : // testZIV -
    1011             : // When we have a pair of subscripts of the form [c1] and [c2],
    1012             : // where c1 and c2 are both loop invariant, we attack it using
    1013             : // the ZIV test. Basically, we test by comparing the two values,
    1014             : // but there are actually three possible results:
    1015             : // 1) the values are equal, so there's a dependence
    1016             : // 2) the values are different, so there's no dependence
    1017             : // 3) the values might be equal, so we have to assume a dependence.
    1018             : //
    1019             : // Return true if dependence disproved.
    1020         250 : bool DependenceInfo::testZIV(const SCEV *Src, const SCEV *Dst,
    1021             :                              FullDependence &Result) const {
    1022             :   DEBUG(dbgs() << "    src = " << *Src << "\n");
    1023             :   DEBUG(dbgs() << "    dst = " << *Dst << "\n");
    1024         250 :   ++ZIVapplications;
    1025         250 :   if (isKnownPredicate(CmpInst::ICMP_EQ, Src, Dst)) {
    1026             :     DEBUG(dbgs() << "    provably dependent\n");
    1027             :     return false; // provably dependent
    1028             :   }
    1029           8 :   if (isKnownPredicate(CmpInst::ICMP_NE, Src, Dst)) {
    1030             :     DEBUG(dbgs() << "    provably independent\n");
    1031             :     ++ZIVindependence;
    1032             :     return true; // provably independent
    1033             :   }
    1034             :   DEBUG(dbgs() << "    possibly dependent\n");
    1035           3 :   Result.Consistent = false;
    1036           3 :   return false; // possibly dependent
    1037             : }
    1038             : 
    1039             : 
    1040             : // strongSIVtest -
    1041             : // From the paper, Practical Dependence Testing, Section 4.2.1
    1042             : //
    1043             : // When we have a pair of subscripts of the form [c1 + a*i] and [c2 + a*i],
    1044             : // where i is an induction variable, c1 and c2 are loop invariant,
    1045             : //  and a is a constant, we can solve it exactly using the Strong SIV test.
    1046             : //
    1047             : // Can prove independence. Failing that, can compute distance (and direction).
    1048             : // In the presence of symbolic terms, we can sometimes make progress.
    1049             : //
    1050             : // If there's a dependence,
    1051             : //
    1052             : //    c1 + a*i = c2 + a*i'
    1053             : //
    1054             : // The dependence distance is
    1055             : //
    1056             : //    d = i' - i = (c1 - c2)/a
    1057             : //
    1058             : // A dependence only exists if d is an integer and abs(d) <= U, where U is the
    1059             : // loop's upper bound. If a dependence exists, the dependence direction is
    1060             : // defined as
    1061             : //
    1062             : //                { < if d > 0
    1063             : //    direction = { = if d = 0
    1064             : //                { > if d < 0
    1065             : //
    1066             : // Return true if dependence disproved.
    1067         535 : bool DependenceInfo::strongSIVtest(const SCEV *Coeff, const SCEV *SrcConst,
    1068             :                                    const SCEV *DstConst, const Loop *CurLoop,
    1069             :                                    unsigned Level, FullDependence &Result,
    1070             :                                    Constraint &NewConstraint) const {
    1071             :   DEBUG(dbgs() << "\tStrong SIV test\n");
    1072             :   DEBUG(dbgs() << "\t    Coeff = " << *Coeff);
    1073             :   DEBUG(dbgs() << ", " << *Coeff->getType() << "\n");
    1074             :   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst);
    1075             :   DEBUG(dbgs() << ", " << *SrcConst->getType() << "\n");
    1076             :   DEBUG(dbgs() << "\t    DstConst = " << *DstConst);
    1077             :   DEBUG(dbgs() << ", " << *DstConst->getType() << "\n");
    1078         535 :   ++StrongSIVapplications;
    1079             :   assert(0 < Level && Level <= CommonLevels && "level out of range");
    1080         535 :   Level--;
    1081             : 
    1082         535 :   const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst);
    1083             :   DEBUG(dbgs() << "\t    Delta = " << *Delta);
    1084             :   DEBUG(dbgs() << ", " << *Delta->getType() << "\n");
    1085             : 
    1086             :   // check that |Delta| < iteration count
    1087         535 :   if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {
    1088             :     DEBUG(dbgs() << "\t    UpperBound = " << *UpperBound);
    1089             :     DEBUG(dbgs() << ", " << *UpperBound->getType() << "\n");
    1090             :     const SCEV *AbsDelta =
    1091         529 :       SE->isKnownNonNegative(Delta) ? Delta : SE->getNegativeSCEV(Delta);
    1092             :     const SCEV *AbsCoeff =
    1093         529 :       SE->isKnownNonNegative(Coeff) ? Coeff : SE->getNegativeSCEV(Coeff);
    1094         529 :     const SCEV *Product = SE->getMulExpr(UpperBound, AbsCoeff);
    1095         529 :     if (isKnownPredicate(CmpInst::ICMP_SGT, AbsDelta, Product)) {
    1096             :       // Distance greater than trip count - no dependence
    1097             :       ++StrongSIVindependence;
    1098             :       ++StrongSIVsuccesses;
    1099             :       return true;
    1100             :     }
    1101             :   }
    1102             : 
    1103             :   // Can we compute distance?
    1104        1595 :   if (isa<SCEVConstant>(Delta) && isa<SCEVConstant>(Coeff)) {
    1105        2579 :     APInt ConstDelta = cast<SCEVConstant>(Delta)->getAPInt();
    1106        2579 :     APInt ConstCoeff = cast<SCEVConstant>(Coeff)->getAPInt();
    1107        1031 :     APInt Distance  = ConstDelta; // these need to be initialized
    1108        1031 :     APInt Remainder = ConstDelta;
    1109         516 :     APInt::sdivrem(ConstDelta, ConstCoeff, Distance, Remainder);
    1110             :     DEBUG(dbgs() << "\t    Distance = " << Distance << "\n");
    1111             :     DEBUG(dbgs() << "\t    Remainder = " << Remainder << "\n");
    1112             :     // Make sure Coeff divides Delta exactly
    1113         516 :     if (Remainder != 0) {
    1114             :       // Coeff doesn't divide Distance, no dependence
    1115           1 :       ++StrongSIVindependence;
    1116           1 :       ++StrongSIVsuccesses;
    1117           2 :       return true;
    1118             :     }
    1119        1030 :     Result.DV[Level].Distance = SE->getConstant(Distance);
    1120         515 :     NewConstraint.setDistance(SE->getConstant(Distance), CurLoop);
    1121         515 :     if (Distance.sgt(0))
    1122          36 :       Result.DV[Level].Direction &= Dependence::DVEntry::LT;
    1123         497 :     else if (Distance.slt(0))
    1124          54 :       Result.DV[Level].Direction &= Dependence::DVEntry::GT;
    1125             :     else
    1126         940 :       Result.DV[Level].Direction &= Dependence::DVEntry::EQ;
    1127         515 :     ++StrongSIVsuccesses;
    1128             :   }
    1129          17 :   else if (Delta->isZero()) {
    1130             :     // since 0/X == 0
    1131          26 :     Result.DV[Level].Distance = Delta;
    1132          13 :     NewConstraint.setDistance(Delta, CurLoop);
    1133          26 :     Result.DV[Level].Direction &= Dependence::DVEntry::EQ;
    1134             :     ++StrongSIVsuccesses;
    1135             :   }
    1136             :   else {
    1137           4 :     if (Coeff->isOne()) {
    1138             :       DEBUG(dbgs() << "\t    Distance = " << *Delta << "\n");
    1139           2 :       Result.DV[Level].Distance = Delta; // since X/1 == X
    1140           1 :       NewConstraint.setDistance(Delta, CurLoop);
    1141             :     }
    1142             :     else {
    1143           3 :       Result.Consistent = false;
    1144           6 :       NewConstraint.setLine(Coeff,
    1145           3 :                             SE->getNegativeSCEV(Coeff),
    1146           3 :                             SE->getNegativeSCEV(Delta), CurLoop);
    1147             :     }
    1148             : 
    1149             :     // maybe we can get a useful direction
    1150           4 :     bool DeltaMaybeZero     = !SE->isKnownNonZero(Delta);
    1151           4 :     bool DeltaMaybePositive = !SE->isKnownNonPositive(Delta);
    1152           4 :     bool DeltaMaybeNegative = !SE->isKnownNonNegative(Delta);
    1153           4 :     bool CoeffMaybePositive = !SE->isKnownNonPositive(Coeff);
    1154           4 :     bool CoeffMaybeNegative = !SE->isKnownNonNegative(Coeff);
    1155             :     // The double negatives above are confusing.
    1156             :     // It helps to read !SE->isKnownNonZero(Delta)
    1157             :     // as "Delta might be Zero"
    1158           4 :     unsigned NewDirection = Dependence::DVEntry::NONE;
    1159           4 :     if ((DeltaMaybePositive && CoeffMaybePositive) ||
    1160             :         (DeltaMaybeNegative && CoeffMaybeNegative))
    1161           4 :       NewDirection = Dependence::DVEntry::LT;
    1162           4 :     if (DeltaMaybeZero)
    1163           4 :       NewDirection |= Dependence::DVEntry::EQ;
    1164           4 :     if ((DeltaMaybeNegative && CoeffMaybePositive) ||
    1165             :         (DeltaMaybePositive && CoeffMaybeNegative))
    1166           4 :       NewDirection |= Dependence::DVEntry::GT;
    1167           8 :     if (NewDirection < Result.DV[Level].Direction)
    1168             :       ++StrongSIVsuccesses;
    1169           8 :     Result.DV[Level].Direction &= NewDirection;
    1170             :   }
    1171             :   return false;
    1172             : }
    1173             : 
    1174             : 
    1175             : // weakCrossingSIVtest -
    1176             : // From the paper, Practical Dependence Testing, Section 4.2.2
    1177             : //
    1178             : // When we have a pair of subscripts of the form [c1 + a*i] and [c2 - a*i],
    1179             : // where i is an induction variable, c1 and c2 are loop invariant,
    1180             : // and a is a constant, we can solve it exactly using the
    1181             : // Weak-Crossing SIV test.
    1182             : //
    1183             : // Given c1 + a*i = c2 - a*i', we can look for the intersection of
    1184             : // the two lines, where i = i', yielding
    1185             : //
    1186             : //    c1 + a*i = c2 - a*i
    1187             : //    2a*i = c2 - c1
    1188             : //    i = (c2 - c1)/2a
    1189             : //
    1190             : // If i < 0, there is no dependence.
    1191             : // If i > upperbound, there is no dependence.
    1192             : // If i = 0 (i.e., if c1 = c2), there's a dependence with distance = 0.
    1193             : // If i = upperbound, there's a dependence with distance = 0.
    1194             : // If i is integral, there's a dependence (all directions).
    1195             : // If the non-integer part = 1/2, there's a dependence (<> directions).
    1196             : // Otherwise, there's no dependence.
    1197             : //
    1198             : // Can prove independence. Failing that,
    1199             : // can sometimes refine the directions.
    1200             : // Can determine iteration for splitting.
    1201             : //
    1202             : // Return true if dependence disproved.
    1203          29 : bool DependenceInfo::weakCrossingSIVtest(
    1204             :     const SCEV *Coeff, const SCEV *SrcConst, const SCEV *DstConst,
    1205             :     const Loop *CurLoop, unsigned Level, FullDependence &Result,
    1206             :     Constraint &NewConstraint, const SCEV *&SplitIter) const {
    1207             :   DEBUG(dbgs() << "\tWeak-Crossing SIV test\n");
    1208             :   DEBUG(dbgs() << "\t    Coeff = " << *Coeff << "\n");
    1209             :   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
    1210             :   DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
    1211          29 :   ++WeakCrossingSIVapplications;
    1212             :   assert(0 < Level && Level <= CommonLevels && "Level out of range");
    1213          29 :   Level--;
    1214          29 :   Result.Consistent = false;
    1215          29 :   const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
    1216             :   DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
    1217          29 :   NewConstraint.setLine(Coeff, Coeff, Delta, CurLoop);
    1218          29 :   if (Delta->isZero()) {
    1219           2 :     Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT);
    1220           2 :     Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT);
    1221           1 :     ++WeakCrossingSIVsuccesses;
    1222           2 :     if (!Result.DV[Level].Direction) {
    1223             :       ++WeakCrossingSIVindependence;
    1224             :       return true;
    1225             :     }
    1226           2 :     Result.DV[Level].Distance = Delta; // = 0
    1227           1 :     return false;
    1228             :   }
    1229          28 :   const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(Coeff);
    1230             :   if (!ConstCoeff)
    1231             :     return false;
    1232             : 
    1233          56 :   Result.DV[Level].Splitable = true;
    1234          28 :   if (SE->isKnownNegative(ConstCoeff)) {
    1235          28 :     ConstCoeff = dyn_cast<SCEVConstant>(SE->getNegativeSCEV(ConstCoeff));
    1236             :     assert(ConstCoeff &&
    1237             :            "dynamic cast of negative of ConstCoeff should yield constant");
    1238          14 :     Delta = SE->getNegativeSCEV(Delta);
    1239             :   }
    1240             :   assert(SE->isKnownPositive(ConstCoeff) && "ConstCoeff should be positive");
    1241             : 
    1242             :   // compute SplitIter for use by DependenceInfo::getSplitIteration()
    1243          84 :   SplitIter = SE->getUDivExpr(
    1244          28 :       SE->getSMaxExpr(SE->getZero(Delta->getType()), Delta),
    1245             :       SE->getMulExpr(SE->getConstant(Delta->getType(), 2), ConstCoeff));
    1246             :   DEBUG(dbgs() << "\t    Split iter = " << *SplitIter << "\n");
    1247             : 
    1248          26 :   const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
    1249             :   if (!ConstDelta)
    1250             :     return false;
    1251             : 
    1252             :   // We're certain that ConstCoeff > 0; therefore,
    1253             :   // if Delta < 0, then no dependence.
    1254             :   DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
    1255             :   DEBUG(dbgs() << "\t    ConstCoeff = " << *ConstCoeff << "\n");
    1256          26 :   if (SE->isKnownNegative(Delta)) {
    1257             :     // No dependence, Delta < 0
    1258             :     ++WeakCrossingSIVindependence;
    1259             :     ++WeakCrossingSIVsuccesses;
    1260             :     return true;
    1261             :   }
    1262             : 
    1263             :   // We're certain that Delta > 0 and ConstCoeff > 0.
    1264             :   // Check Delta/(2*ConstCoeff) against upper loop bound
    1265          25 :   if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {
    1266             :     DEBUG(dbgs() << "\t    UpperBound = " << *UpperBound << "\n");
    1267          25 :     const SCEV *ConstantTwo = SE->getConstant(UpperBound->getType(), 2);
    1268          25 :     const SCEV *ML = SE->getMulExpr(SE->getMulExpr(ConstCoeff, UpperBound),
    1269          25 :                                     ConstantTwo);
    1270             :     DEBUG(dbgs() << "\t    ML = " << *ML << "\n");
    1271          25 :     if (isKnownPredicate(CmpInst::ICMP_SGT, Delta, ML)) {
    1272             :       // Delta too big, no dependence
    1273             :       ++WeakCrossingSIVindependence;
    1274             :       ++WeakCrossingSIVsuccesses;
    1275             :       return true;
    1276             :     }
    1277          24 :     if (isKnownPredicate(CmpInst::ICMP_EQ, Delta, ML)) {
    1278             :       // i = i' = UB
    1279           4 :       Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT);
    1280           4 :       Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT);
    1281           2 :       ++WeakCrossingSIVsuccesses;
    1282           4 :       if (!Result.DV[Level].Direction) {
    1283             :         ++WeakCrossingSIVindependence;
    1284             :         return true;
    1285             :       }
    1286           4 :       Result.DV[Level].Splitable = false;
    1287           6 :       Result.DV[Level].Distance = SE->getZero(Delta->getType());
    1288           2 :       return false;
    1289             :     }
    1290             :   }
    1291             : 
    1292             :   // check that Coeff divides Delta
    1293          44 :   APInt APDelta = ConstDelta->getAPInt();
    1294          66 :   APInt APCoeff = ConstCoeff->getAPInt();
    1295          44 :   APInt Distance = APDelta; // these need to be initialzed
    1296          44 :   APInt Remainder = APDelta;
    1297          22 :   APInt::sdivrem(APDelta, APCoeff, Distance, Remainder);
    1298             :   DEBUG(dbgs() << "\t    Remainder = " << Remainder << "\n");
    1299          22 :   if (Remainder != 0) {
    1300             :     // Coeff doesn't divide Delta, no dependence
    1301             :     ++WeakCrossingSIVindependence;
    1302             :     ++WeakCrossingSIVsuccesses;
    1303             :     return true;
    1304             :   }
    1305             :   DEBUG(dbgs() << "\t    Distance = " << Distance << "\n");
    1306             : 
    1307             :   // if 2*Coeff doesn't divide Delta, then the equal direction isn't possible
    1308          42 :   APInt Two = APInt(Distance.getBitWidth(), 2, true);
    1309          63 :   Remainder = Distance.srem(Two);
    1310             :   DEBUG(dbgs() << "\t    Remainder = " << Remainder << "\n");
    1311          21 :   if (Remainder != 0) {
    1312             :     // Equal direction isn't possible
    1313          10 :     Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::EQ);
    1314             :     ++WeakCrossingSIVsuccesses;
    1315             :   }
    1316          21 :   return false;
    1317             : }
    1318             : 
    1319             : 
    1320             : // Kirch's algorithm, from
    1321             : //
    1322             : //        Optimizing Supercompilers for Supercomputers
    1323             : //        Michael Wolfe
    1324             : //        MIT Press, 1989
    1325             : //
    1326             : // Program 2.1, page 29.
    1327             : // Computes the GCD of AM and BM.
    1328             : // Also finds a solution to the equation ax - by = gcd(a, b).
    1329             : // Returns true if dependence disproved; i.e., gcd does not divide Delta.
    1330          62 : static bool findGCD(unsigned Bits, const APInt &AM, const APInt &BM,
    1331             :                     const APInt &Delta, APInt &G, APInt &X, APInt &Y) {
    1332         248 :   APInt A0(Bits, 1, true), A1(Bits, 0, true);
    1333         248 :   APInt B0(Bits, 0, true), B1(Bits, 1, true);
    1334         124 :   APInt G0 = AM.abs();
    1335         124 :   APInt G1 = BM.abs();
    1336         124 :   APInt Q = G0; // these need to be initialized
    1337         124 :   APInt R = G0;
    1338          62 :   APInt::sdivrem(G0, G1, Q, R);
    1339          80 :   while (R != 0) {
    1340          27 :     APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2;
    1341          27 :     APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2;
    1342           9 :     G0 = G1; G1 = R;
    1343           9 :     APInt::sdivrem(G0, G1, Q, R);
    1344             :   }
    1345          62 :   G = G1;
    1346             :   DEBUG(dbgs() << "\t    GCD = " << G << "\n");
    1347         259 :   X = AM.slt(0) ? -A1 : A1;
    1348         298 :   Y = BM.slt(0) ? B1 : -B1;
    1349             : 
    1350             :   // make sure gcd divides Delta
    1351         186 :   R = Delta.srem(G);
    1352          62 :   if (R != 0)
    1353             :     return true; // gcd doesn't divide Delta, no dependence
    1354         174 :   Q = Delta.sdiv(G);
    1355          58 :   X *= Q;
    1356          58 :   Y *= Q;
    1357          58 :   return false;
    1358             : }
    1359             : 
    1360         173 : static APInt floorOfQuotient(const APInt &A, const APInt &B) {
    1361         346 :   APInt Q = A; // these need to be initialized
    1362         346 :   APInt R = A;
    1363         173 :   APInt::sdivrem(A, B, Q, R);
    1364         173 :   if (R == 0)
    1365             :     return Q;
    1366          91 :   if ((A.sgt(0) && B.sgt(0)) ||
    1367          64 :       (A.slt(0) && B.slt(0)))
    1368             :     return Q;
    1369             :   else
    1370          36 :     return Q - 1;
    1371             : }
    1372             : 
    1373         187 : static APInt ceilingOfQuotient(const APInt &A, const APInt &B) {
    1374         374 :   APInt Q = A; // these need to be initialized
    1375         374 :   APInt R = A;
    1376         187 :   APInt::sdivrem(A, B, Q, R);
    1377         187 :   if (R == 0)
    1378             :     return Q;
    1379          67 :   if ((A.sgt(0) && B.sgt(0)) ||
    1380          22 :       (A.slt(0) && B.slt(0)))
    1381         117 :     return Q + 1;
    1382             :   else
    1383             :     return Q;
    1384             : }
    1385             : 
    1386             : 
    1387             : static
    1388         187 : APInt maxAPInt(APInt A, APInt B) {
    1389         374 :   return A.sgt(B) ? A : B;
    1390             : }
    1391             : 
    1392             : 
    1393             : static
    1394         173 : APInt minAPInt(APInt A, APInt B) {
    1395         346 :   return A.slt(B) ? A : B;
    1396             : }
    1397             : 
    1398             : 
    1399             : // exactSIVtest -
    1400             : // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*i],
    1401             : // where i is an induction variable, c1 and c2 are loop invariant, and a1
    1402             : // and a2 are constant, we can solve it exactly using an algorithm developed
    1403             : // by Banerjee and Wolfe. See Section 2.5.3 in
    1404             : //
    1405             : //        Optimizing Supercompilers for Supercomputers
    1406             : //        Michael Wolfe
    1407             : //        MIT Press, 1989
    1408             : //
    1409             : // It's slower than the specialized tests (strong SIV, weak-zero SIV, etc),
    1410             : // so use them if possible. They're also a bit better with symbolics and,
    1411             : // in the case of the strong SIV test, can compute Distances.
    1412             : //
    1413             : // Return true if dependence disproved.
    1414          53 : bool DependenceInfo::exactSIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,
    1415             :                                   const SCEV *SrcConst, const SCEV *DstConst,
    1416             :                                   const Loop *CurLoop, unsigned Level,
    1417             :                                   FullDependence &Result,
    1418             :                                   Constraint &NewConstraint) const {
    1419             :   DEBUG(dbgs() << "\tExact SIV test\n");
    1420             :   DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << " = AM\n");
    1421             :   DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << " = BM\n");
    1422             :   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
    1423             :   DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
    1424          53 :   ++ExactSIVapplications;
    1425             :   assert(0 < Level && Level <= CommonLevels && "Level out of range");
    1426          53 :   Level--;
    1427          53 :   Result.Consistent = false;
    1428          53 :   const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
    1429             :   DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
    1430          53 :   NewConstraint.setLine(SrcCoeff, SE->getNegativeSCEV(DstCoeff),
    1431             :                         Delta, CurLoop);
    1432          53 :   const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
    1433          53 :   const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
    1434          53 :   const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
    1435          53 :   if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
    1436             :     return false;
    1437             : 
    1438             :   // find gcd
    1439         205 :   APInt G, X, Y;
    1440         123 :   APInt AM = ConstSrcCoeff->getAPInt();
    1441         123 :   APInt BM = ConstDstCoeff->getAPInt();
    1442          41 :   unsigned Bits = AM.getBitWidth();
    1443          41 :   if (findGCD(Bits, AM, BM, ConstDelta->getAPInt(), G, X, Y)) {
    1444             :     // gcd doesn't divide Delta, no dependence
    1445             :     ++ExactSIVindependence;
    1446             :     ++ExactSIVsuccesses;
    1447             :     return true;
    1448             :   }
    1449             : 
    1450             :   DEBUG(dbgs() << "\t    X = " << X << ", Y = " << Y << "\n");
    1451             : 
    1452             :   // since SCEV construction normalizes, LM = 0
    1453          38 :   APInt UM(Bits, 1, true);
    1454          38 :   bool UMvalid = false;
    1455             :   // UM is perhaps unavailable, let's check
    1456          38 :   if (const SCEVConstant *CUB =
    1457          38 :       collectConstantUpperBound(CurLoop, Delta->getType())) {
    1458          36 :     UM = CUB->getAPInt();
    1459             :     DEBUG(dbgs() << "\t    UM = " << UM << "\n");
    1460          36 :     UMvalid = true;
    1461             :   }
    1462             : 
    1463          76 :   APInt TU(APInt::getSignedMaxValue(Bits));
    1464          76 :   APInt TL(APInt::getSignedMinValue(Bits));
    1465             : 
    1466             :   // test(BM/G, LM-X) and test(-BM/G, X-UM)
    1467          76 :   APInt TMUL = BM.sdiv(G);
    1468          38 :   if (TMUL.sgt(0)) {
    1469         288 :     TL = maxAPInt(TL, ceilingOfQuotient(-X, TMUL));
    1470             :     DEBUG(dbgs() << "\t    TL = " << TL << "\n");
    1471          32 :     if (UMvalid) {
    1472         270 :       TU = minAPInt(TU, floorOfQuotient(UM - X, TMUL));
    1473             :       DEBUG(dbgs() << "\t    TU = " << TU << "\n");
    1474             :     }
    1475             :   }
    1476             :   else {
    1477          54 :     TU = minAPInt(TU, floorOfQuotient(-X, TMUL));
    1478             :     DEBUG(dbgs() << "\t    TU = " << TU << "\n");
    1479           6 :     if (UMvalid) {
    1480          54 :       TL = maxAPInt(TL, ceilingOfQuotient(UM - X, TMUL));
    1481             :       DEBUG(dbgs() << "\t    TL = " << TL << "\n");
    1482             :     }
    1483             :   }
    1484             : 
    1485             :   // test(AM/G, LM-Y) and test(-AM/G, Y-UM)
    1486         114 :   TMUL = AM.sdiv(G);
    1487          38 :   if (TMUL.sgt(0)) {
    1488         288 :     TL = maxAPInt(TL, ceilingOfQuotient(-Y, TMUL));
    1489             :     DEBUG(dbgs() << "\t    TL = " << TL << "\n");
    1490          32 :     if (UMvalid) {
    1491         270 :       TU = minAPInt(TU, floorOfQuotient(UM - Y, TMUL));
    1492             :       DEBUG(dbgs() << "\t    TU = " << TU << "\n");
    1493             :     }
    1494             :   }
    1495             :   else {
    1496          54 :     TU = minAPInt(TU, floorOfQuotient(-Y, TMUL));
    1497             :     DEBUG(dbgs() << "\t    TU = " << TU << "\n");
    1498           6 :     if (UMvalid) {
    1499          54 :       TL = maxAPInt(TL, ceilingOfQuotient(UM - Y, TMUL));
    1500             :       DEBUG(dbgs() << "\t    TL = " << TL << "\n");
    1501             :     }
    1502             :   }
    1503          38 :   if (TL.sgt(TU)) {
    1504             :     ++ExactSIVindependence;
    1505             :     ++ExactSIVsuccesses;
    1506             :     return true;
    1507             :   }
    1508             : 
    1509             :   // explore directions
    1510          36 :   unsigned NewDirection = Dependence::DVEntry::NONE;
    1511             : 
    1512             :   // less than
    1513          36 :   APInt SaveTU(TU); // save these
    1514          72 :   APInt SaveTL(TL);
    1515             :   DEBUG(dbgs() << "\t    exploring LT direction\n");
    1516         180 :   TMUL = AM - BM;
    1517          36 :   if (TMUL.sgt(0)) {
    1518         286 :     TL = maxAPInt(TL, ceilingOfQuotient(X - Y + 1, TMUL));
    1519             :     DEBUG(dbgs() << "\t\t    TL = " << TL << "\n");
    1520             :   }
    1521             :   else {
    1522         110 :     TU = minAPInt(TU, floorOfQuotient(X - Y + 1, TMUL));
    1523             :     DEBUG(dbgs() << "\t\t    TU = " << TU << "\n");
    1524             :   }
    1525          36 :   if (TL.sle(TU)) {
    1526          23 :     NewDirection |= Dependence::DVEntry::LT;
    1527             :     ++ExactSIVsuccesses;
    1528             :   }
    1529             : 
    1530             :   // equal
    1531          36 :   TU = SaveTU; // restore
    1532          36 :   TL = SaveTL;
    1533             :   DEBUG(dbgs() << "\t    exploring EQ direction\n");
    1534          36 :   if (TMUL.sgt(0)) {
    1535         234 :     TL = maxAPInt(TL, ceilingOfQuotient(X - Y, TMUL));
    1536             :     DEBUG(dbgs() << "\t\t    TL = " << TL << "\n");
    1537             :   }
    1538             :   else {
    1539          90 :     TU = minAPInt(TU, floorOfQuotient(X - Y, TMUL));
    1540             :     DEBUG(dbgs() << "\t\t    TU = " << TU << "\n");
    1541             :   }
    1542         180 :   TMUL = BM - AM;
    1543          36 :   if (TMUL.sgt(0)) {
    1544          90 :     TL = maxAPInt(TL, ceilingOfQuotient(Y - X, TMUL));
    1545             :     DEBUG(dbgs() << "\t\t    TL = " << TL << "\n");
    1546             :   }
    1547             :   else {
    1548         234 :     TU = minAPInt(TU, floorOfQuotient(Y - X, TMUL));
    1549             :     DEBUG(dbgs() << "\t\t    TU = " << TU << "\n");
    1550             :   }
    1551          36 :   if (TL.sle(TU)) {
    1552          29 :     NewDirection |= Dependence::DVEntry::EQ;
    1553             :     ++ExactSIVsuccesses;
    1554             :   }
    1555             : 
    1556             :   // greater than
    1557          36 :   TU = SaveTU; // restore
    1558          36 :   TL = SaveTL;
    1559             :   DEBUG(dbgs() << "\t    exploring GT direction\n");
    1560          36 :   if (TMUL.sgt(0)) {
    1561         110 :     TL = maxAPInt(TL, ceilingOfQuotient(Y - X + 1, TMUL));
    1562             :     DEBUG(dbgs() << "\t\t    TL = " << TL << "\n");
    1563             :   }
    1564             :   else {
    1565         286 :     TU = minAPInt(TU, floorOfQuotient(Y - X + 1, TMUL));
    1566             :     DEBUG(dbgs() << "\t\t    TU = " << TU << "\n");
    1567             :   }
    1568          36 :   if (TL.sle(TU)) {
    1569          35 :     NewDirection |= Dependence::DVEntry::GT;
    1570             :     ++ExactSIVsuccesses;
    1571             :   }
    1572             : 
    1573             :   // finished
    1574          72 :   Result.DV[Level].Direction &= NewDirection;
    1575          72 :   if (Result.DV[Level].Direction == Dependence::DVEntry::NONE)
    1576             :     ++ExactSIVindependence;
    1577          72 :   return Result.DV[Level].Direction == Dependence::DVEntry::NONE;
    1578             : }
    1579             : 
    1580             : 
    1581             : 
    1582             : // Return true if the divisor evenly divides the dividend.
    1583             : static
    1584          14 : bool isRemainderZero(const SCEVConstant *Dividend,
    1585             :                      const SCEVConstant *Divisor) {
    1586          14 :   const APInt &ConstDividend = Dividend->getAPInt();
    1587          14 :   const APInt &ConstDivisor = Divisor->getAPInt();
    1588          28 :   return ConstDividend.srem(ConstDivisor) == 0;
    1589             : }
    1590             : 
    1591             : 
    1592             : // weakZeroSrcSIVtest -
    1593             : // From the paper, Practical Dependence Testing, Section 4.2.2
    1594             : //
    1595             : // When we have a pair of subscripts of the form [c1] and [c2 + a*i],
    1596             : // where i is an induction variable, c1 and c2 are loop invariant,
    1597             : // and a is a constant, we can solve it exactly using the
    1598             : // Weak-Zero SIV test.
    1599             : //
    1600             : // Given
    1601             : //
    1602             : //    c1 = c2 + a*i
    1603             : //
    1604             : // we get
    1605             : //
    1606             : //    (c1 - c2)/a = i
    1607             : //
    1608             : // If i is not an integer, there's no dependence.
    1609             : // If i < 0 or > UB, there's no dependence.
    1610             : // If i = 0, the direction is <= and peeling the
    1611             : // 1st iteration will break the dependence.
    1612             : // If i = UB, the direction is >= and peeling the
    1613             : // last iteration will break the dependence.
    1614             : // Otherwise, the direction is *.
    1615             : //
    1616             : // Can prove independence. Failing that, we can sometimes refine
    1617             : // the directions. Can sometimes show that first or last
    1618             : // iteration carries all the dependences (so worth peeling).
    1619             : //
    1620             : // (see also weakZeroDstSIVtest)
    1621             : //
    1622             : // Return true if dependence disproved.
    1623          13 : bool DependenceInfo::weakZeroSrcSIVtest(const SCEV *DstCoeff,
    1624             :                                         const SCEV *SrcConst,
    1625             :                                         const SCEV *DstConst,
    1626             :                                         const Loop *CurLoop, unsigned Level,
    1627             :                                         FullDependence &Result,
    1628             :                                         Constraint &NewConstraint) const {
    1629             :   // For the WeakSIV test, it's possible the loop isn't common to
    1630             :   // the Src and Dst loops. If it isn't, then there's no need to
    1631             :   // record a direction.
    1632             :   DEBUG(dbgs() << "\tWeak-Zero (src) SIV test\n");
    1633             :   DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << "\n");
    1634             :   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
    1635             :   DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
    1636          13 :   ++WeakZeroSIVapplications;
    1637             :   assert(0 < Level && Level <= MaxLevels && "Level out of range");
    1638          13 :   Level--;
    1639          13 :   Result.Consistent = false;
    1640          13 :   const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst);
    1641          26 :   NewConstraint.setLine(SE->getZero(Delta->getType()), DstCoeff, Delta,
    1642             :                         CurLoop);
    1643             :   DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
    1644          13 :   if (isKnownPredicate(CmpInst::ICMP_EQ, SrcConst, DstConst)) {
    1645           5 :     if (Level < CommonLevels) {
    1646           8 :       Result.DV[Level].Direction &= Dependence::DVEntry::LE;
    1647           8 :       Result.DV[Level].PeelFirst = true;
    1648             :       ++WeakZeroSIVsuccesses;
    1649             :     }
    1650             :     return false; // dependences caused by first iteration
    1651             :   }
    1652           8 :   const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
    1653             :   if (!ConstCoeff)
    1654             :     return false;
    1655             :   const SCEV *AbsCoeff =
    1656           8 :     SE->isKnownNegative(ConstCoeff) ?
    1657           8 :     SE->getNegativeSCEV(ConstCoeff) : ConstCoeff;
    1658             :   const SCEV *NewDelta =
    1659           8 :     SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta;
    1660             : 
    1661             :   // check that Delta/SrcCoeff < iteration count
    1662             :   // really check NewDelta < count*AbsCoeff
    1663           8 :   if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {
    1664             :     DEBUG(dbgs() << "\t    UpperBound = " << *UpperBound << "\n");
    1665           8 :     const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound);
    1666           8 :     if (isKnownPredicate(CmpInst::ICMP_SGT, NewDelta, Product)) {
    1667             :       ++WeakZeroSIVindependence;
    1668             :       ++WeakZeroSIVsuccesses;
    1669             :       return true;
    1670             :     }
    1671           7 :     if (isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) {
    1672             :       // dependences caused by last iteration
    1673           1 :       if (Level < CommonLevels) {
    1674           2 :         Result.DV[Level].Direction &= Dependence::DVEntry::GE;
    1675           2 :         Result.DV[Level].PeelLast = true;
    1676             :         ++WeakZeroSIVsuccesses;
    1677             :       }
    1678             :       return false;
    1679             :     }
    1680             :   }
    1681             : 
    1682             :   // check that Delta/SrcCoeff >= 0
    1683             :   // really check that NewDelta >= 0
    1684           6 :   if (SE->isKnownNegative(NewDelta)) {
    1685             :     // No dependence, newDelta < 0
    1686             :     ++WeakZeroSIVindependence;
    1687             :     ++WeakZeroSIVsuccesses;
    1688             :     return true;
    1689             :   }
    1690             : 
    1691             :   // if SrcCoeff doesn't divide Delta, then no dependence
    1692          12 :   if (isa<SCEVConstant>(Delta) &&
    1693           8 :       !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) {
    1694             :     ++WeakZeroSIVindependence;
    1695             :     ++WeakZeroSIVsuccesses;
    1696             :     return true;
    1697             :   }
    1698             :   return false;
    1699             : }
    1700             : 
    1701             : 
    1702             : // weakZeroDstSIVtest -
    1703             : // From the paper, Practical Dependence Testing, Section 4.2.2
    1704             : //
    1705             : // When we have a pair of subscripts of the form [c1 + a*i] and [c2],
    1706             : // where i is an induction variable, c1 and c2 are loop invariant,
    1707             : // and a is a constant, we can solve it exactly using the
    1708             : // Weak-Zero SIV test.
    1709             : //
    1710             : // Given
    1711             : //
    1712             : //    c1 + a*i = c2
    1713             : //
    1714             : // we get
    1715             : //
    1716             : //    i = (c2 - c1)/a
    1717             : //
    1718             : // If i is not an integer, there's no dependence.
    1719             : // If i < 0 or > UB, there's no dependence.
    1720             : // If i = 0, the direction is <= and peeling the
    1721             : // 1st iteration will break the dependence.
    1722             : // If i = UB, the direction is >= and peeling the
    1723             : // last iteration will break the dependence.
    1724             : // Otherwise, the direction is *.
    1725             : //
    1726             : // Can prove independence. Failing that, we can sometimes refine
    1727             : // the directions. Can sometimes show that first or last
    1728             : // iteration carries all the dependences (so worth peeling).
    1729             : //
    1730             : // (see also weakZeroSrcSIVtest)
    1731             : //
    1732             : // Return true if dependence disproved.
    1733          20 : bool DependenceInfo::weakZeroDstSIVtest(const SCEV *SrcCoeff,
    1734             :                                         const SCEV *SrcConst,
    1735             :                                         const SCEV *DstConst,
    1736             :                                         const Loop *CurLoop, unsigned Level,
    1737             :                                         FullDependence &Result,
    1738             :                                         Constraint &NewConstraint) const {
    1739             :   // For the WeakSIV test, it's possible the loop isn't common to the
    1740             :   // Src and Dst loops. If it isn't, then there's no need to record a direction.
    1741             :   DEBUG(dbgs() << "\tWeak-Zero (dst) SIV test\n");
    1742             :   DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << "\n");
    1743             :   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
    1744             :   DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
    1745          20 :   ++WeakZeroSIVapplications;
    1746             :   assert(0 < Level && Level <= SrcLevels && "Level out of range");
    1747          20 :   Level--;
    1748          20 :   Result.Consistent = false;
    1749          20 :   const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
    1750          40 :   NewConstraint.setLine(SrcCoeff, SE->getZero(Delta->getType()), Delta,
    1751             :                         CurLoop);
    1752             :   DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
    1753          20 :   if (isKnownPredicate(CmpInst::ICMP_EQ, DstConst, SrcConst)) {
    1754           5 :     if (Level < CommonLevels) {
    1755           6 :       Result.DV[Level].Direction &= Dependence::DVEntry::LE;
    1756           6 :       Result.DV[Level].PeelFirst = true;
    1757             :       ++WeakZeroSIVsuccesses;
    1758             :     }
    1759             :     return false; // dependences caused by first iteration
    1760             :   }
    1761          15 :   const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
    1762             :   if (!ConstCoeff)
    1763             :     return false;
    1764             :   const SCEV *AbsCoeff =
    1765          15 :     SE->isKnownNegative(ConstCoeff) ?
    1766          15 :     SE->getNegativeSCEV(ConstCoeff) : ConstCoeff;
    1767             :   const SCEV *NewDelta =
    1768          15 :     SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta;
    1769             : 
    1770             :   // check that Delta/SrcCoeff < iteration count
    1771             :   // really check NewDelta < count*AbsCoeff
    1772          15 :   if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {
    1773             :     DEBUG(dbgs() << "\t    UpperBound = " << *UpperBound << "\n");
    1774          15 :     const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound);
    1775          15 :     if (isKnownPredicate(CmpInst::ICMP_SGT, NewDelta, Product)) {
    1776             :       ++WeakZeroSIVindependence;
    1777             :       ++WeakZeroSIVsuccesses;
    1778             :       return true;
    1779             :     }
    1780          14 :     if (isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) {
    1781             :       // dependences caused by last iteration
    1782           1 :       if (Level < CommonLevels) {
    1783           2 :         Result.DV[Level].Direction &= Dependence::DVEntry::GE;
    1784           2 :         Result.DV[Level].PeelLast = true;
    1785             :         ++WeakZeroSIVsuccesses;
    1786             :       }
    1787             :       return false;
    1788             :     }
    1789             :   }
    1790             : 
    1791             :   // check that Delta/SrcCoeff >= 0
    1792             :   // really check that NewDelta >= 0
    1793          13 :   if (SE->isKnownNegative(NewDelta)) {
    1794             :     // No dependence, newDelta < 0
    1795             :     ++WeakZeroSIVindependence;
    1796             :     ++WeakZeroSIVsuccesses;
    1797             :     return true;
    1798             :   }
    1799             : 
    1800             :   // if SrcCoeff doesn't divide Delta, then no dependence
    1801          34 :   if (isa<SCEVConstant>(Delta) &&
    1802          20 :       !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) {
    1803             :     ++WeakZeroSIVindependence;
    1804             :     ++WeakZeroSIVsuccesses;
    1805             :     return true;
    1806             :   }
    1807             :   return false;
    1808             : }
    1809             : 
    1810             : 
    1811             : // exactRDIVtest - Tests the RDIV subscript pair for dependence.
    1812             : // Things of the form [c1 + a*i] and [c2 + b*j],
    1813             : // where i and j are induction variable, c1 and c2 are loop invariant,
    1814             : // and a and b are constants.
    1815             : // Returns true if any possible dependence is disproved.
    1816             : // Marks the result as inconsistent.
    1817             : // Works in some cases that symbolicRDIVtest doesn't, and vice versa.
    1818          29 : bool DependenceInfo::exactRDIVtest(const SCEV *SrcCoeff, const SCEV *DstCoeff,
    1819             :                                    const SCEV *SrcConst, const SCEV *DstConst,
    1820             :                                    const Loop *SrcLoop, const Loop *DstLoop,
    1821             :                                    FullDependence &Result) const {
    1822             :   DEBUG(dbgs() << "\tExact RDIV test\n");
    1823             :   DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << " = AM\n");
    1824             :   DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << " = BM\n");
    1825             :   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
    1826             :   DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
    1827          29 :   ++ExactRDIVapplications;
    1828          29 :   Result.Consistent = false;
    1829          29 :   const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
    1830             :   DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
    1831          29 :   const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
    1832          29 :   const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
    1833          29 :   const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
    1834          29 :   if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
    1835             :     return false;
    1836             : 
    1837             :   // find gcd
    1838         105 :   APInt G, X, Y;
    1839          63 :   APInt AM = ConstSrcCoeff->getAPInt();
    1840          63 :   APInt BM = ConstDstCoeff->getAPInt();
    1841          21 :   unsigned Bits = AM.getBitWidth();
    1842          21 :   if (findGCD(Bits, AM, BM, ConstDelta->getAPInt(), G, X, Y)) {
    1843             :     // gcd doesn't divide Delta, no dependence
    1844             :     ++ExactRDIVindependence;
    1845             :     return true;
    1846             :   }
    1847             : 
    1848             :   DEBUG(dbgs() << "\t    X = " << X << ", Y = " << Y << "\n");
    1849             : 
    1850             :   // since SCEV construction seems to normalize, LM = 0
    1851          20 :   APInt SrcUM(Bits, 1, true);
    1852          20 :   bool SrcUMvalid = false;
    1853             :   // SrcUM is perhaps unavailable, let's check
    1854          20 :   if (const SCEVConstant *UpperBound =
    1855          20 :       collectConstantUpperBound(SrcLoop, Delta->getType())) {
    1856          14 :     SrcUM = UpperBound->getAPInt();
    1857             :     DEBUG(dbgs() << "\t    SrcUM = " << SrcUM << "\n");
    1858          14 :     SrcUMvalid = true;
    1859             :   }
    1860             : 
    1861          40 :   APInt DstUM(Bits, 1, true);
    1862          20 :   bool DstUMvalid = false;
    1863             :   // UM is perhaps unavailable, let's check
    1864          20 :   if (const SCEVConstant *UpperBound =
    1865          20 :       collectConstantUpperBound(DstLoop, Delta->getType())) {
    1866          14 :     DstUM = UpperBound->getAPInt();
    1867             :     DEBUG(dbgs() << "\t    DstUM = " << DstUM << "\n");
    1868          14 :     DstUMvalid = true;
    1869             :   }
    1870             : 
    1871          40 :   APInt TU(APInt::getSignedMaxValue(Bits));
    1872          40 :   APInt TL(APInt::getSignedMinValue(Bits));
    1873             : 
    1874             :   // test(BM/G, LM-X) and test(-BM/G, X-UM)
    1875          40 :   APInt TMUL = BM.sdiv(G);
    1876          20 :   if (TMUL.sgt(0)) {
    1877         126 :     TL = maxAPInt(TL, ceilingOfQuotient(-X, TMUL));
    1878             :     DEBUG(dbgs() << "\t    TL = " << TL << "\n");
    1879          14 :     if (SrcUMvalid) {
    1880          81 :       TU = minAPInt(TU, floorOfQuotient(SrcUM - X, TMUL));
    1881             :       DEBUG(dbgs() << "\t    TU = " << TU << "\n");
    1882             :     }
    1883             :   }
    1884             :   else {
    1885          54 :     TU = minAPInt(TU, floorOfQuotient(-X, TMUL));
    1886             :     DEBUG(dbgs() << "\t    TU = " << TU << "\n");
    1887           6 :     if (SrcUMvalid) {
    1888          45 :       TL = maxAPInt(TL, ceilingOfQuotient(SrcUM - X, TMUL));
    1889             :       DEBUG(dbgs() << "\t    TL = " << TL << "\n");
    1890             :     }
    1891             :   }
    1892             : 
    1893             :   // test(AM/G, LM-Y) and test(-AM/G, Y-UM)
    1894          60 :   TMUL = AM.sdiv(G);
    1895          20 :   if (TMUL.sgt(0)) {
    1896         135 :     TL = maxAPInt(TL, ceilingOfQuotient(-Y, TMUL));
    1897             :     DEBUG(dbgs() << "\t    TL = " << TL << "\n");
    1898          15 :     if (DstUMvalid) {
    1899          81 :       TU = minAPInt(TU, floorOfQuotient(DstUM - Y, TMUL));
    1900             :       DEBUG(dbgs() << "\t    TU = " << TU << "\n");
    1901             :     }
    1902             :   }
    1903             :   else {
    1904          45 :     TU = minAPInt(TU, floorOfQuotient(-Y, TMUL));
    1905             :     DEBUG(dbgs() << "\t    TU = " << TU << "\n");
    1906           5 :     if (DstUMvalid) {
    1907          45 :       TL = maxAPInt(TL, ceilingOfQuotient(DstUM - Y, TMUL));
    1908             :       DEBUG(dbgs() << "\t    TL = " << TL << "\n");
    1909             :     }
    1910             :   }
    1911          20 :   if (TL.sgt(TU))
    1912             :     ++ExactRDIVindependence;
    1913          20 :   return TL.sgt(TU);
    1914             : }
    1915             : 
    1916             : 
    1917             : // symbolicRDIVtest -
    1918             : // In Section 4.5 of the Practical Dependence Testing paper,the authors
    1919             : // introduce a special case of Banerjee's Inequalities (also called the
    1920             : // Extreme-Value Test) that can handle some of the SIV and RDIV cases,
    1921             : // particularly cases with symbolics. Since it's only able to disprove
    1922             : // dependence (not compute distances or directions), we'll use it as a
    1923             : // fall back for the other tests.
    1924             : //
    1925             : // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j]
    1926             : // where i and j are induction variables and c1 and c2 are loop invariants,
    1927             : // we can use the symbolic tests to disprove some dependences, serving as a
    1928             : // backup for the RDIV test. Note that i and j can be the same variable,
    1929             : // letting this test serve as a backup for the various SIV tests.
    1930             : //
    1931             : // For a dependence to exist, c1 + a1*i must equal c2 + a2*j for some
    1932             : //  0 <= i <= N1 and some 0 <= j <= N2, where N1 and N2 are the (normalized)
    1933             : // loop bounds for the i and j loops, respectively. So, ...
    1934             : //
    1935             : // c1 + a1*i = c2 + a2*j
    1936             : // a1*i - a2*j = c2 - c1
    1937             : //
    1938             : // To test for a dependence, we compute c2 - c1 and make sure it's in the
    1939             : // range of the maximum and minimum possible values of a1*i - a2*j.
    1940             : // Considering the signs of a1 and a2, we have 4 possible cases:
    1941             : //
    1942             : // 1) If a1 >= 0 and a2 >= 0, then
    1943             : //        a1*0 - a2*N2 <= c2 - c1 <= a1*N1 - a2*0
    1944             : //              -a2*N2 <= c2 - c1 <= a1*N1
    1945             : //
    1946             : // 2) If a1 >= 0 and a2 <= 0, then
    1947             : //        a1*0 - a2*0 <= c2 - c1 <= a1*N1 - a2*N2
    1948             : //                  0 <= c2 - c1 <= a1*N1 - a2*N2
    1949             : //
    1950             : // 3) If a1 <= 0 and a2 >= 0, then
    1951             : //        a1*N1 - a2*N2 <= c2 - c1 <= a1*0 - a2*0
    1952             : //        a1*N1 - a2*N2 <= c2 - c1 <= 0
    1953             : //
    1954             : // 4) If a1 <= 0 and a2 <= 0, then
    1955             : //        a1*N1 - a2*0  <= c2 - c1 <= a1*0 - a2*N2
    1956             : //        a1*N1         <= c2 - c1 <=       -a2*N2
    1957             : //
    1958             : // return true if dependence disproved
    1959         621 : bool DependenceInfo::symbolicRDIVtest(const SCEV *A1, const SCEV *A2,
    1960             :                                       const SCEV *C1, const SCEV *C2,
    1961             :                                       const Loop *Loop1,
    1962             :                                       const Loop *Loop2) const {
    1963         621 :   ++SymbolicRDIVapplications;
    1964             :   DEBUG(dbgs() << "\ttry symbolic RDIV test\n");
    1965             :   DEBUG(dbgs() << "\t    A1 = " << *A1);
    1966             :   DEBUG(dbgs() << ", type = " << *A1->getType() << "\n");
    1967             :   DEBUG(dbgs() << "\t    A2 = " << *A2 << "\n");
    1968             :   DEBUG(dbgs() << "\t    C1 = " << *C1 << "\n");
    1969             :   DEBUG(dbgs() << "\t    C2 = " << *C2 << "\n");
    1970         621 :   const SCEV *N1 = collectUpperBound(Loop1, A1->getType());
    1971         621 :   const SCEV *N2 = collectUpperBound(Loop2, A1->getType());
    1972             :   DEBUG(if (N1) dbgs() << "\t    N1 = " << *N1 << "\n");
    1973             :   DEBUG(if (N2) dbgs() << "\t    N2 = " << *N2 << "\n");
    1974         621 :   const SCEV *C2_C1 = SE->getMinusSCEV(C2, C1);
    1975         621 :   const SCEV *C1_C2 = SE->getMinusSCEV(C1, C2);
    1976             :   DEBUG(dbgs() << "\t    C2 - C1 = " << *C2_C1 << "\n");
    1977             :   DEBUG(dbgs() << "\t    C1 - C2 = " << *C1_C2 << "\n");
    1978         621 :   if (SE->isKnownNonNegative(A1)) {
    1979         526 :     if (SE->isKnownNonNegative(A2)) {
    1980             :       // A1 >= 0 && A2 >= 0
    1981         512 :       if (N1) {
    1982             :         // make sure that c2 - c1 <= a1*N1
    1983         508 :         const SCEV *A1N1 = SE->getMulExpr(A1, N1);
    1984             :         DEBUG(dbgs() << "\t    A1*N1 = " << *A1N1 << "\n");
    1985         508 :         if (isKnownPredicate(CmpInst::ICMP_SGT, C2_C1, A1N1)) {
    1986             :           ++SymbolicRDIVindependence;
    1987             :           return true;
    1988             :         }
    1989             :       }
    1990         510 :       if (N2) {
    1991             :         // make sure that -a2*N2 <= c2 - c1, or a2*N2 >= c1 - c2
    1992         506 :         const SCEV *A2N2 = SE->getMulExpr(A2, N2);
    1993             :         DEBUG(dbgs() << "\t    A2*N2 = " << *A2N2 << "\n");
    1994         506 :         if (isKnownPredicate(CmpInst::ICMP_SLT, A2N2, C1_C2)) {
    1995             :           ++SymbolicRDIVindependence;
    1996             :           return true;
    1997             :         }
    1998             :       }
    1999             :     }
    2000          14 :     else if (SE->isKnownNonPositive(A2)) {
    2001             :       // a1 >= 0 && a2 <= 0
    2002          14 :       if (N1 && N2) {
    2003             :         // make sure that c2 - c1 <= a1*N1 - a2*N2
    2004          14 :         const SCEV *A1N1 = SE->getMulExpr(A1, N1);
    2005          14 :         const SCEV *A2N2 = SE->getMulExpr(A2, N2);
    2006          14 :         const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2);
    2007             :         DEBUG(dbgs() << "\t    A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n");
    2008          14 :         if (isKnownPredicate(CmpInst::ICMP_SGT, C2_C1, A1N1_A2N2)) {
    2009             :           ++SymbolicRDIVindependence;
    2010             :           return true;
    2011             :         }
    2012             :       }
    2013             :       // make sure that 0 <= c2 - c1
    2014          12 :       if (SE->isKnownNegative(C2_C1)) {
    2015             :         ++SymbolicRDIVindependence;
    2016             :         return true;
    2017             :       }
    2018             :     }
    2019             :   }
    2020          95 :   else if (SE->isKnownNonPositive(A1)) {
    2021          79 :     if (SE->isKnownNonNegative(A2)) {
    2022             :       // a1 <= 0 && a2 >= 0
    2023          16 :       if (N1 && N2) {
    2024             :         // make sure that a1*N1 - a2*N2 <= c2 - c1
    2025          16 :         const SCEV *A1N1 = SE->getMulExpr(A1, N1);
    2026          16 :         const SCEV *A2N2 = SE->getMulExpr(A2, N2);
    2027          16 :         const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2);
    2028             :         DEBUG(dbgs() << "\t    A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n");
    2029          16 :         if (isKnownPredicate(CmpInst::ICMP_SGT, A1N1_A2N2, C2_C1)) {
    2030             :           ++SymbolicRDIVindependence;
    2031             :           return true;
    2032             :         }
    2033             :       }
    2034             :       // make sure that c2 - c1 <= 0
    2035          14 :       if (SE->isKnownPositive(C2_C1)) {
    2036             :         ++SymbolicRDIVindependence;
    2037             :         return true;
    2038             :       }
    2039             :     }
    2040          63 :     else if (SE->isKnownNonPositive(A2)) {
    2041             :       // a1 <= 0 && a2 <= 0
    2042          63 :       if (N1) {
    2043             :         // make sure that a1*N1 <= c2 - c1
    2044          63 :         const SCEV *A1N1 = SE->getMulExpr(A1, N1);
    2045             :         DEBUG(dbgs() << "\t    A1*N1 = " << *A1N1 << "\n");
    2046          63 :         if (isKnownPredicate(CmpInst::ICMP_SGT, A1N1, C2_C1)) {
    2047             :           ++SymbolicRDIVindependence;
    2048             :           return true;
    2049             :         }
    2050             :       }
    2051          61 :       if (N2) {
    2052             :         // make sure that c2 - c1 <= -a2*N2, or c1 - c2 >= a2*N2
    2053          61 :         const SCEV *A2N2 = SE->getMulExpr(A2, N2);
    2054             :         DEBUG(dbgs() << "\t    A2*N2 = " << *A2N2 << "\n");
    2055          61 :         if (isKnownPredicate(CmpInst::ICMP_SLT, C1_C2, A2N2)) {
    2056             :           ++SymbolicRDIVindependence;
    2057             :           return true;
    2058             :         }
    2059             :       }
    2060             :     }
    2061             :   }
    2062             :   return false;
    2063             : }
    2064             : 
    2065             : 
    2066             : // testSIV -
    2067             : // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 - a2*i]
    2068             : // where i is an induction variable, c1 and c2 are loop invariant, and a1 and
    2069             : // a2 are constant, we attack it with an SIV test. While they can all be
    2070             : // solved with the Exact SIV test, it's worthwhile to use simpler tests when
    2071             : // they apply; they're cheaper and sometimes more precise.
    2072             : //
    2073             : // Return true if dependence disproved.
    2074         650 : bool DependenceInfo::testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level,
    2075             :                              FullDependence &Result, Constraint &NewConstraint,
    2076             :                              const SCEV *&SplitIter) const {
    2077             :   DEBUG(dbgs() << "    src = " << *Src << "\n");
    2078             :   DEBUG(dbgs() << "    dst = " << *Dst << "\n");
    2079         650 :   const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src);
    2080         650 :   const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst);
    2081         650 :   if (SrcAddRec && DstAddRec) {
    2082         617 :     const SCEV *SrcConst = SrcAddRec->getStart();
    2083         617 :     const SCEV *DstConst = DstAddRec->getStart();
    2084         617 :     const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE);
    2085         617 :     const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE);
    2086         617 :     const Loop *CurLoop = SrcAddRec->getLoop();
    2087             :     assert(CurLoop == DstAddRec->getLoop() &&
    2088             :            "both loops in SIV should be same");
    2089         617 :     Level = mapSrcLoop(CurLoop);
    2090             :     bool disproven;
    2091         617 :     if (SrcCoeff == DstCoeff)
    2092         535 :       disproven = strongSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
    2093             :                                 Level, Result, NewConstraint);
    2094          82 :     else if (SrcCoeff == SE->getNegativeSCEV(DstCoeff))
    2095          29 :       disproven = weakCrossingSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
    2096             :                                       Level, Result, NewConstraint, SplitIter);
    2097             :     else
    2098          53 :       disproven = exactSIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop,
    2099             :                                Level, Result, NewConstraint);
    2100         605 :     return disproven ||
    2101        1221 :       gcdMIVtest(Src, Dst, Result) ||
    2102         604 :       symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop, CurLoop);
    2103             :   }
    2104          33 :   if (SrcAddRec) {
    2105          20 :     const SCEV *SrcConst = SrcAddRec->getStart();
    2106          20 :     const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE);
    2107          20 :     const SCEV *DstConst = Dst;
    2108          20 :     const Loop *CurLoop = SrcAddRec->getLoop();
    2109          20 :     Level = mapSrcLoop(CurLoop);
    2110          20 :     return weakZeroDstSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
    2111          37 :                               Level, Result, NewConstraint) ||
    2112          17 :       gcdMIVtest(Src, Dst, Result);
    2113             :   }
    2114          13 :   if (DstAddRec) {
    2115          13 :     const SCEV *DstConst = DstAddRec->getStart();
    2116          13 :     const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE);
    2117          13 :     const SCEV *SrcConst = Src;
    2118          13 :     const Loop *CurLoop = DstAddRec->getLoop();
    2119          13 :     Level = mapDstLoop(CurLoop);
    2120          13 :     return weakZeroSrcSIVtest(DstCoeff, SrcConst, DstConst,
    2121          22 :                               CurLoop, Level, Result, NewConstraint) ||
    2122           9 :       gcdMIVtest(Src, Dst, Result);
    2123             :   }
    2124           0 :   llvm_unreachable("SIV test expected at least one AddRec");
    2125             :   return false;
    2126             : }
    2127             : 
    2128             : 
    2129             : // testRDIV -
    2130             : // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j]
    2131             : // where i and j are induction variables, c1 and c2 are loop invariant,
    2132             : // and a1 and a2 are constant, we can solve it exactly with an easy adaptation
    2133             : // of the Exact SIV test, the Restricted Double Index Variable (RDIV) test.
    2134             : // It doesn't make sense to talk about distance or direction in this case,
    2135             : // so there's no point in making special versions of the Strong SIV test or
    2136             : // the Weak-crossing SIV test.
    2137             : //
    2138             : // With minor algebra, this test can also be used for things like
    2139             : // [c1 + a1*i + a2*j][c2].
    2140             : //
    2141             : // Return true if dependence disproved.
    2142          29 : bool DependenceInfo::testRDIV(const SCEV *Src, const SCEV *Dst,
    2143             :                               FullDependence &Result) const {
    2144             :   // we have 3 possible situations here:
    2145             :   //   1) [a*i + b] and [c*j + d]
    2146             :   //   2) [a*i + c*j + b] and [d]
    2147             :   //   3) [b] and [a*i + c*j + d]
    2148             :   // We need to find what we've got and get organized
    2149             : 
    2150             :   const SCEV *SrcConst, *DstConst;
    2151             :   const SCEV *SrcCoeff, *DstCoeff;
    2152             :   const Loop *SrcLoop, *DstLoop;
    2153             : 
    2154             :   DEBUG(dbgs() << "    src = " << *Src << "\n");
    2155             :   DEBUG(dbgs() << "    dst = " << *Dst << "\n");
    2156          29 :   const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src);
    2157          29 :   const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst);
    2158          29 :   if (SrcAddRec && DstAddRec) {
    2159          20 :     SrcConst = SrcAddRec->getStart();
    2160          20 :     SrcCoeff = SrcAddRec->getStepRecurrence(*SE);
    2161          20 :     SrcLoop = SrcAddRec->getLoop();
    2162          20 :     DstConst = DstAddRec->getStart();
    2163          20 :     DstCoeff = DstAddRec->getStepRecurrence(*SE);
    2164          20 :     DstLoop = DstAddRec->getLoop();
    2165             :   }
    2166           9 :   else if (SrcAddRec) {
    2167             :     if (const SCEVAddRecExpr *tmpAddRec =
    2168          14 :         dyn_cast<SCEVAddRecExpr>(SrcAddRec->getStart())) {
    2169           7 :       SrcConst = tmpAddRec->getStart();
    2170           7 :       SrcCoeff = tmpAddRec->getStepRecurrence(*SE);
    2171           7 :       SrcLoop = tmpAddRec->getLoop();
    2172           7 :       DstConst = Dst;
    2173           7 :       DstCoeff = SE->getNegativeSCEV(SrcAddRec->getStepRecurrence(*SE));
    2174           7 :       DstLoop = SrcAddRec->getLoop();
    2175             :     }
    2176             :     else
    2177           0 :       llvm_unreachable("RDIV reached by surprising SCEVs");
    2178             :   }
    2179           2 :   else if (DstAddRec) {
    2180             :     if (const SCEVAddRecExpr *tmpAddRec =
    2181           4 :         dyn_cast<SCEVAddRecExpr>(DstAddRec->getStart())) {
    2182           2 :       DstConst = tmpAddRec->getStart();
    2183           2 :       DstCoeff = tmpAddRec->getStepRecurrence(*SE);
    2184           2 :       DstLoop = tmpAddRec->getLoop();
    2185           2 :       SrcConst = Src;
    2186           2 :       SrcCoeff = SE->getNegativeSCEV(DstAddRec->getStepRecurrence(*SE));
    2187           2 :       SrcLoop = DstAddRec->getLoop();
    2188             :     }
    2189             :     else
    2190           0 :       llvm_unreachable("RDIV reached by surprising SCEVs");
    2191             :   }
    2192             :   else
    2193           0 :     llvm_unreachable("RDIV expected at least one AddRec");
    2194          29 :   return exactRDIVtest(SrcCoeff, DstCoeff,
    2195             :                        SrcConst, DstConst,
    2196             :                        SrcLoop, DstLoop,
    2197          17 :                        Result) ||
    2198          46 :     gcdMIVtest(Src, Dst, Result) ||
    2199          17 :     symbolicRDIVtest(SrcCoeff, DstCoeff,
    2200             :                      SrcConst, DstConst,
    2201          29 :                      SrcLoop, DstLoop);
    2202             : }
    2203             : 
    2204             : 
    2205             : // Tests the single-subscript MIV pair (Src and Dst) for dependence.
    2206             : // Return true if dependence disproved.
    2207             : // Can sometimes refine direction vectors.
    2208         200 : bool DependenceInfo::testMIV(const SCEV *Src, const SCEV *Dst,
    2209             :                              const SmallBitVector &Loops,
    2210             :                              FullDependence &Result) const {
    2211             :   DEBUG(dbgs() << "    src = " << *Src << "\n");
    2212             :   DEBUG(dbgs() << "    dst = " << *Dst << "\n");
    2213         200 :   Result.Consistent = false;
    2214         391 :   return gcdMIVtest(Src, Dst, Result) ||
    2215         391 :     banerjeeMIVtest(Src, Dst, Loops, Result);
    2216             : }
    2217             : 
    2218             : 
    2219             : // Given a product, e.g., 10*X*Y, returns the first constant operand,
    2220             : // in this case 10. If there is no constant part, returns NULL.
    2221             : static
    2222             : const SCEVConstant *getConstantPart(const SCEV *Expr) {
    2223             :   if (const auto *Constant = dyn_cast<SCEVConstant>(Expr))
    2224             :     return Constant;
    2225          66 :   else if (const auto *Product = dyn_cast<SCEVMulExpr>(Expr))
    2226         132 :     if (const auto *Constant = dyn_cast<SCEVConstant>(Product->getOperand(0)))
    2227             :       return Constant;
    2228             :   return nullptr;
    2229             : }
    2230             : 
    2231             : 
    2232             : //===----------------------------------------------------------------------===//
    2233             : // gcdMIVtest -
    2234             : // Tests an MIV subscript pair for dependence.
    2235             : // Returns true if any possible dependence is disproved.
    2236             : // Marks the result as inconsistent.
    2237             : // Can sometimes disprove the equal direction for 1 or more loops,
    2238             : // as discussed in Michael Wolfe's book,
    2239             : // High Performance Compilers for Parallel Computing, page 235.
    2240             : //
    2241             : // We spend some effort (code!) to handle cases like
    2242             : // [10*i + 5*N*j + 15*M + 6], where i and j are induction variables,
    2243             : // but M and N are just loop-invariant variables.
    2244             : // This should help us handle linearized subscripts;
    2245             : // also makes this test a useful backup to the various SIV tests.
    2246             : //
    2247             : // It occurs to me that the presence of loop-invariant variables
    2248             : // changes the nature of the test from "greatest common divisor"
    2249             : // to "a common divisor".
    2250         848 : bool DependenceInfo::gcdMIVtest(const SCEV *Src, const SCEV *Dst,
    2251             :                                 FullDependence &Result) const {
    2252             :   DEBUG(dbgs() << "starting gcd\n");
    2253         848 :   ++GCDapplications;
    2254         848 :   unsigned BitWidth = SE->getTypeSizeInBits(Src->getType());
    2255        1696 :   APInt RunningGCD = APInt::getNullValue(BitWidth);
    2256             : 
    2257             :   // Examine Src coefficients.
    2258             :   // Compute running GCD and record source constant.
    2259             :   // Because we're looking for the constant at the end of the chain,
    2260             :   // we can't quit the loop just because the GCD == 1.
    2261         848 :   const SCEV *Coefficients = Src;
    2262             :   while (const SCEVAddRecExpr *AddRec =
    2263        1042 :          dyn_cast<SCEVAddRecExpr>(Coefficients)) {
    2264        1042 :     const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
    2265             :     // If the coefficient is the product of a constant and other stuff,
    2266             :     // we can use the constant in the GCD computation.
    2267        1033 :     const auto *Constant = getConstantPart(Coeff);
    2268        1033 :     if (!Constant)
    2269           9 :       return false;
    2270        3099 :     APInt ConstCoeff = Constant->getAPInt();
    2271        6198 :     RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs());
    2272        1033 :     Coefficients = AddRec->getStart();
    2273        1033 :   }
    2274         839 :   const SCEV *SrcConst = Coefficients;
    2275             : 
    2276             :   // Examine Dst coefficients.
    2277             :   // Compute running GCD and record destination constant.
    2278             :   // Because we're looking for the constant at the end of the chain,
    2279             :   // we can't quit the loop just because the GCD == 1.
    2280         839 :   Coefficients = Dst;
    2281             :   while (const SCEVAddRecExpr *AddRec =
    2282        1022 :          dyn_cast<SCEVAddRecExpr>(Coefficients)) {
    2283        1022 :     const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
    2284             :     // If the coefficient is the product of a constant and other stuff,
    2285             :     // we can use the constant in the GCD computation.
    2286        1021 :     const auto *Constant = getConstantPart(Coeff);
    2287        1021 :     if (!Constant)
    2288           1 :       return false;
    2289        3063 :     APInt ConstCoeff = Constant->getAPInt();
    2290        6126 :     RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs());
    2291        1021 :     Coefficients = AddRec->getStart();
    2292        1021 :   }
    2293         838 :   const SCEV *DstConst = Coefficients;
    2294             : 
    2295         838 :   APInt ExtraGCD = APInt::getNullValue(BitWidth);
    2296         838 :   const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
    2297             :   DEBUG(dbgs() << "    Delta = " << *Delta << "\n");
    2298         838 :   const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Delta);
    2299          14 :   if (const SCEVAddExpr *Sum = dyn_cast<SCEVAddExpr>(Delta)) {
    2300             :     // If Delta is a sum of products, we may be able to make further progress.
    2301          38 :     for (unsigned Op = 0, Ops = Sum->getNumOperands(); Op < Ops; Op++) {
    2302          58 :       const SCEV *Operand = Sum->getOperand(Op);
    2303          58 :       if (isa<SCEVConstant>(Operand)) {
    2304             :         assert(!Constant && "Surprised to find multiple constants");
    2305             :         Constant = cast<SCEVConstant>(Operand);
    2306             :       }
    2307          29 :       else if (const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Operand)) {
    2308             :         // Search for constant operand to participate in GCD;
    2309             :         // If none found; return false.
    2310          12 :         const SCEVConstant *ConstOp = getConstantPart(Product);
    2311             :         if (!ConstOp)
    2312           0 :           return false;
    2313          36 :         APInt ConstOpValue = ConstOp->getAPInt();
    2314          48 :         ExtraGCD = APIntOps::GreatestCommonDivisor(ExtraGCD,
    2315          24 :                                                    ConstOpValue.abs());
    2316             :       }
    2317             :       else
    2318             :         return false;
    2319             :     }
    2320             :   }
    2321         833 :   if (!Constant)
    2322             :     return false;
    2323        2448 :   APInt ConstDelta = cast<SCEVConstant>(Constant)->getAPInt();
    2324             :   DEBUG(dbgs() << "    ConstDelta = " << ConstDelta << "\n");
    2325         816 :   if (ConstDelta == 0)
    2326             :     return false;
    2327        1026 :   RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ExtraGCD);
    2328             :   DEBUG(dbgs() << "    RunningGCD = " << RunningGCD << "\n");
    2329         171 :   APInt Remainder = ConstDelta.srem(RunningGCD);
    2330         171 :   if (Remainder != 0) {
    2331             :     ++GCDindependence;
    2332             :     return true;
    2333             :   }
    2334             : 
    2335             :   // Try to disprove equal directions.
    2336             :   // For example, given a subscript pair [3*i + 2*j] and [i' + 2*j' - 1],
    2337             :   // the code above can't disprove the dependence because the GCD = 1.
    2338             :   // So we consider what happen if i = i' and what happens if j = j'.
    2339             :   // If i = i', we can simplify the subscript to [2*i + 2*j] and [2*j' - 1],
    2340             :   // which is infeasible, so we can disallow the = direction for the i level.
    2341             :   // Setting j = j' doesn't help matters, so we end up with a direction vector
    2342             :   // of [<>, *]
    2343             :   //
    2344             :   // Given A[5*i + 10*j*M + 9*M*N] and A[15*i + 20*j*M - 21*N*M + 5],
    2345             :   // we need to remember that the constant part is 5 and the RunningGCD should
    2346             :   // be initialized to ExtraGCD = 30.
    2347             :   DEBUG(dbgs() << "    ExtraGCD = " << ExtraGCD << '\n');
    2348             : 
    2349             :   bool Improved = false;
    2350             :   Coefficients = Src;
    2351             :   while (const SCEVAddRecExpr *AddRec =
    2352         190 :          dyn_cast<SCEVAddRecExpr>(Coefficients)) {
    2353         190 :     Coefficients = AddRec->getStart();
    2354         190 :     const Loop *CurLoop = AddRec->getLoop();
    2355         190 :     RunningGCD = ExtraGCD;
    2356         190 :     const SCEV *SrcCoeff = AddRec->getStepRecurrence(*SE);
    2357         190 :     const SCEV *DstCoeff = SE->getMinusSCEV(SrcCoeff, SrcCoeff);
    2358         190 :     const SCEV *Inner = Src;
    2359        1029 :     while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) {
    2360         456 :       AddRec = cast<SCEVAddRecExpr>(Inner);
    2361         228 :       const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
    2362         228 :       if (CurLoop == AddRec->getLoop())
    2363             :         ; // SrcCoeff == Coeff
    2364             :       else {
    2365             :         // If the coefficient is the product of a constant and other stuff,
    2366             :         // we can use the constant in the GCD computation.
    2367          66 :         Constant = getConstantPart(Coeff);
    2368          66 :         if (!Constant)
    2369           0 :           return false;
    2370         198 :         APInt ConstCoeff = Constant->getAPInt();
    2371         396 :         RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs());
    2372             :       }
    2373         228 :       Inner = AddRec->getStart();
    2374             :     }
    2375             :     Inner = Dst;
    2376         870 :     while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) {
    2377         356 :       AddRec = cast<SCEVAddRecExpr>(Inner);
    2378         178 :       const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
    2379         178 :       if (CurLoop == AddRec->getLoop())
    2380             :         DstCoeff = Coeff;
    2381             :       else {
    2382             :         // If the coefficient is the product of a constant and other stuff,
    2383             :         // we can use the constant in the GCD computation.
    2384          39 :         Constant = getConstantPart(Coeff);
    2385          39 :         if (!Constant)
    2386           0 :           return false;
    2387         117 :         APInt ConstCoeff = Constant->getAPInt();
    2388         234 :         RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs());
    2389             :       }
    2390         178 :       Inner = AddRec->getStart();
    2391             :     }
    2392         190 :     Delta = SE->getMinusSCEV(SrcCoeff, DstCoeff);
    2393             :     // If the coefficient is the product of a constant and other stuff,
    2394             :     // we can use the constant in the GCD computation.
    2395         189 :     Constant = getConstantPart(Delta);
    2396         189 :     if (!Constant)
    2397             :       // The difference of the two coefficients might not be a product
    2398             :       // or constant, in which case we give up on this direction.
    2399           1 :       continue;
    2400         567 :     APInt ConstCoeff = Constant->getAPInt();
    2401        1134 :     RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs());
    2402             :     DEBUG(dbgs() << "\tRunningGCD = " << RunningGCD << "\n");
    2403         189 :     if (RunningGCD != 0) {
    2404         432 :       Remainder = ConstDelta.srem(RunningGCD);
    2405             :       DEBUG(dbgs() << "\tRemainder = " << Remainder << "\n");
    2406         144 :       if (Remainder != 0) {
    2407          30 :         unsigned Level = mapSrcLoop(CurLoop);
    2408          60 :         Result.DV[Level - 1].Direction &= unsigned(~Dependence::DVEntry::EQ);
    2409          30 :         Improved = true;
    2410             :       }
    2411             :     }
    2412             :   }
    2413             :   if (Improved)
    2414             :     ++GCDsuccesses;
    2415             :   DEBUG(dbgs() << "all done\n");
    2416         161 :   return false;
    2417             : }
    2418             : 
    2419             : 
    2420             : //===----------------------------------------------------------------------===//
    2421             : // banerjeeMIVtest -
    2422             : // Use Banerjee's Inequalities to test an MIV subscript pair.
    2423             : // (Wolfe, in the race-car book, calls this the Extreme Value Test.)
    2424             : // Generally follows the discussion in Section 2.5.2 of
    2425             : //
    2426             : //    Optimizing Supercompilers for Supercomputers
    2427             : //    Michael Wolfe
    2428             : //
    2429             : // The inequalities given on page 25 are simplified in that loops are
    2430             : // normalized so that the lower bound is always 0 and the stride is always 1.
    2431             : // For example, Wolfe gives
    2432             : //
    2433             : //     LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
    2434             : //
    2435             : // where A_k is the coefficient of the kth index in the source subscript,
    2436             : // B_k is the coefficient of the kth index in the destination subscript,
    2437             : // U_k is the upper bound of the kth index, L_k is the lower bound of the Kth
    2438             : // index, and N_k is the stride of the kth index. Since all loops are normalized
    2439             : // by the SCEV package, N_k = 1 and L_k = 0, allowing us to simplify the
    2440             : // equation to
    2441             : //
    2442             : //     LB^<_k = (A^-_k - B_k)^- (U_k - 0 - 1) + (A_k - B_k)0 - B_k 1
    2443             : //            = (A^-_k - B_k)^- (U_k - 1)  - B_k
    2444             : //
    2445             : // Similar simplifications are possible for the other equations.
    2446             : //
    2447             : // When we can't determine the number of iterations for a loop,
    2448             : // we use NULL as an indicator for the worst case, infinity.
    2449             : // When computing the upper bound, NULL denotes +inf;
    2450             : // for the lower bound, NULL denotes -inf.
    2451             : //
    2452             : // Return true if dependence disproved.
    2453         191 : bool DependenceInfo::banerjeeMIVtest(const SCEV *Src, const SCEV *Dst,
    2454             :                                      const SmallBitVector &Loops,
    2455             :                                      FullDependence &Result) const {
    2456             :   DEBUG(dbgs() << "starting Banerjee\n");
    2457         191 :   ++BanerjeeApplications;
    2458             :   DEBUG(dbgs() << "    Src = " << *Src << '\n');
    2459             :   const SCEV *A0;
    2460         191 :   CoefficientInfo *A = collectCoeffInfo(Src, true, A0);
    2461             :   DEBUG(dbgs() << "    Dst = " << *Dst << '\n');
    2462             :   const SCEV *B0;
    2463         191 :   CoefficientInfo *B = collectCoeffInfo(Dst, false, B0);
    2464         191 :   BoundInfo *Bound = new BoundInfo[MaxLevels + 1];
    2465         191 :   const SCEV *Delta = SE->getMinusSCEV(B0, A0);
    2466             :   DEBUG(dbgs() << "\tDelta = " << *Delta << '\n');
    2467             : 
    2468             :   // Compute bounds for all the * directions.
    2469             :   DEBUG(dbgs() << "\tBounds[*]\n");
    2470         646 :   for (unsigned K = 1; K <= MaxLevels; ++K) {
    2471         455 :     Bound[K].Iterations = A[K].Iterations ? A[K].Iterations : B[K].Iterations;
    2472         455 :     Bound[K].Direction = Dependence::DVEntry::ALL;
    2473         455 :     Bound[K].DirSet = Dependence::DVEntry::NONE;
    2474         455 :     findBoundsALL(A, B, Bound, K);
    2475             : #ifndef NDEBUG
    2476             :     DEBUG(dbgs() << "\t    " << K << '\t');
    2477             :     if (Bound[K].Lower[Dependence::DVEntry::ALL])
    2478             :       DEBUG(dbgs() << *Bound[K].Lower[Dependence::DVEntry::ALL] << '\t');
    2479             :     else
    2480             :       DEBUG(dbgs() << "-inf\t");
    2481             :     if (Bound[K].Upper[Dependence::DVEntry::ALL])
    2482             :       DEBUG(dbgs() << *Bound[K].Upper[Dependence::DVEntry::ALL] << '\n');
    2483             :     else
    2484             :       DEBUG(dbgs() << "+inf\n");
    2485             : #endif
    2486             :   }
    2487             : 
    2488             :   // Test the *, *, *, ... case.
    2489         191 :   bool Disproved = false;
    2490         191 :   if (testBounds(Dependence::DVEntry::ALL, 0, Bound, Delta)) {
    2491             :     // Explore the direction vector hierarchy.
    2492         187 :     unsigned DepthExpanded = 0;
    2493             :     unsigned NewDeps = exploreDirections(1, A, B, Bound,
    2494         187 :                                          Loops, DepthExpanded, Delta);
    2495         187 :     if (NewDeps > 0) {
    2496             :       bool Improved = false;
    2497        1077 :       for (unsigned K = 1; K <= CommonLevels; ++K) {
    2498         445 :         if (Loops[K]) {
    2499         772 :           unsigned Old = Result.DV[K - 1].Direction;
    2500         772 :           Result.DV[K - 1].Direction = Old & Bound[K].DirSet;
    2501         772 :           Improved |= Old != Result.DV[K - 1].Direction;
    2502         772 :           if (!Result.DV[K - 1].Direction) {
    2503             :             Improved = false;
    2504             :             Disproved = true;
    2505             :             break;
    2506             :           }
    2507             :         }
    2508             :       }
    2509             :       if (Improved)
    2510             :         ++BanerjeeSuccesses;
    2511             :     }
    2512             :     else {
    2513             :       ++BanerjeeIndependence;
    2514             :       Disproved = true;
    2515             :     }
    2516             :   }
    2517             :   else {
    2518             :     ++BanerjeeIndependence;
    2519             :     Disproved = true;
    2520             :   }
    2521         191 :   delete [] Bound;
    2522         191 :   delete [] A;
    2523         191 :   delete [] B;
    2524         191 :   return Disproved;
    2525             : }
    2526             : 
    2527             : 
    2528             : // Hierarchically expands the direction vector
    2529             : // search space, combining the directions of discovered dependences
    2530             : // in the DirSet field of Bound. Returns the number of distinct
    2531             : // dependences discovered. If the dependence is disproved,
    2532             : // it will return 0.
    2533        1083 : unsigned DependenceInfo::exploreDirections(unsigned Level, CoefficientInfo *A,
    2534             :                                            CoefficientInfo *B, BoundInfo *Bound,
    2535             :                                            const SmallBitVector &Loops,
    2536             :                                            unsigned &DepthExpanded,
    2537             :                                            const SCEV *Delta) const {
    2538        1194 :   if (Level > CommonLevels) {
    2539             :     // record result
    2540             :     DEBUG(dbgs() << "\t[");
    2541        3831 :     for (unsigned K = 1; K <= CommonLevels; ++K) {
    2542        1655 :       if (Loops[K]) {
    2543        1158 :         Bound[K].DirSet |= Bound[K].Direction;
    2544             : #ifndef NDEBUG
    2545             :         switch (Bound[K].Direction) {
    2546             :         case Dependence::DVEntry::LT:
    2547             :           DEBUG(dbgs() << " <");
    2548             :           break;
    2549             :         case Dependence::DVEntry::EQ:
    2550             :           DEBUG(dbgs() << " =");
    2551             :           break;
    2552             :         case Dependence::DVEntry::GT:
    2553             :           DEBUG(dbgs() << " >");
    2554             :           break;
    2555             :         case Dependence::DVEntry::ALL:
    2556             :           DEBUG(dbgs() << " *");
    2557             :           break;
    2558             :         default:
    2559             :           llvm_unreachable("unexpected Bound[K].Direction");
    2560             :         }
    2561             : #endif
    2562             :       }
    2563             :     }
    2564             :     DEBUG(dbgs() << " ]\n");
    2565             :     return 1;
    2566             :   }
    2567         673 :   if (Loops[Level]) {
    2568         562 :     if (Level > DepthExpanded) {
    2569         386 :       DepthExpanded = Level;
    2570             :       // compute bounds for <, =, > at current level
    2571         386 :       findBoundsLT(A, B, Bound, Level);
    2572         386 :       findBoundsGT(A, B, Bound, Level);
    2573         386 :       findBoundsEQ(A, B, Bound, Level);
    2574             : #ifndef NDEBUG
    2575             :       DEBUG(dbgs() << "\tBound for level = " << Level << '\n');
    2576             :       DEBUG(dbgs() << "\t    <\t");
    2577             :       if (Bound[Level].Lower[Dependence::DVEntry::LT])
    2578             :         DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::LT] << '\t');
    2579             :       else
    2580             :         DEBUG(dbgs() << "-inf\t");
    2581             :       if (Bound[Level].Upper[Dependence::DVEntry::LT])
    2582             :         DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::LT] << '\n');
    2583             :       else
    2584             :         DEBUG(dbgs() << "+inf\n");
    2585             :       DEBUG(dbgs() << "\t    =\t");
    2586             :       if (Bound[Level].Lower[Dependence::DVEntry::EQ])
    2587             :         DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::EQ] << '\t');
    2588             :       else
    2589             :         DEBUG(dbgs() << "-inf\t");
    2590             :       if (Bound[Level].Upper[Dependence::DVEntry::EQ])
    2591             :         DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::EQ] << '\n');
    2592             :       else
    2593             :         DEBUG(dbgs() << "+inf\n");
    2594             :       DEBUG(dbgs() << "\t    >\t");
    2595             :       if (Bound[Level].Lower[Dependence::DVEntry::GT])
    2596             :         DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::GT] << '\t');
    2597             :       else
    2598             :         DEBUG(dbgs() << "-inf\t");
    2599             :       if (Bound[Level].Upper[Dependence::DVEntry::GT])
    2600             :         DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::GT] << '\n');
    2601             :       else
    2602             :         DEBUG(dbgs() << "+inf\n");
    2603             : #endif
    2604             :     }
    2605             : 
    2606         562 :     unsigned NewDeps = 0;
    2607             : 
    2608             :     // test bounds for <, *, *, ...
    2609         562 :     if (testBounds(Dependence::DVEntry::LT, Level, Bound, Delta))
    2610         228 :       NewDeps += exploreDirections(Level + 1, A, B, Bound,
    2611             :                                    Loops, DepthExpanded, Delta);
    2612             : 
    2613             :     // Test bounds for =, *, *, ...
    2614         562 :     if (testBounds(Dependence::DVEntry::EQ, Level, Bound, Delta))
    2615         442 :       NewDeps += exploreDirections(Level + 1, A, B, Bound,
    2616             :                                    Loops, DepthExpanded, Delta);
    2617             : 
    2618             :     // test bounds for >, *, *, ...
    2619         562 :     if (testBounds(Dependence::DVEntry::GT, Level, Bound, Delta))
    2620         226 :       NewDeps += exploreDirections(Level + 1, A, B, Bound,
    2621             :                                    Loops, DepthExpanded, Delta);
    2622             : 
    2623         562 :     Bound[Level].Direction = Dependence::DVEntry::ALL;
    2624         562 :     return NewDeps;
    2625             :   }
    2626             :   else
    2627         111 :     return exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded, Delta);
    2628             : }
    2629             : 
    2630             : 
    2631             : // Returns true iff the current bounds are plausible.
    2632        1877 : bool DependenceInfo::testBounds(unsigned char DirKind, unsigned Level,
    2633             :                                 BoundInfo *Bound, const SCEV *Delta) const {
    2634        1877 :   Bound[Level].Direction = DirKind;
    2635        1877 :   if (const SCEV *LowerBound = getLowerBound(Bound))
    2636        1877 :     if (isKnownPredicate(CmpInst::ICMP_SGT, LowerBound, Delta))
    2637             :       return false;
    2638        1470 :   if (const SCEV *UpperBound = getUpperBound(Bound))
    2639        1470 :     if (isKnownPredicate(CmpInst::ICMP_SGT, Delta, UpperBound))
    2640             :       return false;
    2641             :   return true;
    2642             : }
    2643             : 
    2644             : 
    2645             : // Computes the upper and lower bounds for level K
    2646             : // using the * direction. Records them in Bound.
    2647             : // Wolfe gives the equations
    2648             : //
    2649             : //    LB^*_k = (A^-_k - B^+_k)(U_k - L_k) + (A_k - B_k)L_k
    2650             : //    UB^*_k = (A^+_k - B^-_k)(U_k - L_k) + (A_k - B_k)L_k
    2651             : //
    2652             : // Since we normalize loops, we can simplify these equations to
    2653             : //
    2654             : //    LB^*_k = (A^-_k - B^+_k)U_k
    2655             : //    UB^*_k = (A^+_k - B^-_k)U_k
    2656             : //
    2657             : // We must be careful to handle the case where the upper bound is unknown.
    2658             : // Note that the lower bound is always <= 0
    2659             : // and the upper bound is always >= 0.
    2660         455 : void DependenceInfo::findBoundsALL(CoefficientInfo *A, CoefficientInfo *B,
    2661             :                                    BoundInfo *Bound, unsigned K) const {
    2662         455 :   Bound[K].Lower[Dependence::DVEntry::ALL] = nullptr; // Default value = -infinity.
    2663         455 :   Bound[K].Upper[Dependence::DVEntry::ALL] = nullptr; // Default value = +infinity.
    2664         455 :   if (Bound[K].Iterations) {
    2665         391 :     Bound[K].Lower[Dependence::DVEntry::ALL] =
    2666         391 :       SE->getMulExpr(SE->getMinusSCEV(A[K].NegPart, B[K].PosPart),
    2667             :                      Bound[K].Iterations);
    2668         391 :     Bound[K].Upper[Dependence::DVEntry::ALL] =
    2669         391 :       SE->getMulExpr(SE->getMinusSCEV(A[K].PosPart, B[K].NegPart),
    2670             :                      Bound[K].Iterations);
    2671             :   }
    2672             :   else {
    2673             :     // If the difference is 0, we won't need to know the number of iterations.
    2674          64 :     if (isKnownPredicate(CmpInst::ICMP_EQ, A[K].NegPart, B[K].PosPart))
    2675         128 :       Bound[K].Lower[Dependence::DVEntry::ALL] =
    2676         128 :           SE->getZero(A[K].Coeff->getType());
    2677          64 :     if (isKnownPredicate(CmpInst::ICMP_EQ, A[K].PosPart, B[K].NegPart))
    2678         128 :       Bound[K].Upper[Dependence::DVEntry::ALL] =
    2679         128 :           SE->getZero(A[K].Coeff->getType());
    2680             :   }
    2681         455 : }
    2682             : 
    2683             : 
    2684             : // Computes the upper and lower bounds for level K
    2685             : // using the = direction. Records them in Bound.
    2686             : // Wolfe gives the equations
    2687             : //
    2688             : //    LB^=_k = (A_k - B_k)^- (U_k - L_k) + (A_k - B_k)L_k
    2689             : //    UB^=_k = (A_k - B_k)^+ (U_k - L_k) + (A_k - B_k)L_k
    2690             : //
    2691             : // Since we normalize loops, we can simplify these equations to
    2692             : //
    2693             : //    LB^=_k = (A_k - B_k)^- U_k
    2694             : //    UB^=_k = (A_k - B_k)^+ U_k
    2695             : //
    2696             : // We must be careful to handle the case where the upper bound is unknown.
    2697             : // Note that the lower bound is always <= 0
    2698             : // and the upper bound is always >= 0.
    2699         386 : void DependenceInfo::findBoundsEQ(CoefficientInfo *A, CoefficientInfo *B,
    2700             :                                   BoundInfo *Bound, unsigned K) const {
    2701         386 :   Bound[K].Lower[Dependence::DVEntry::EQ] = nullptr; // Default value = -infinity.
    2702         386 :   Bound[K].Upper[Dependence::DVEntry::EQ] = nullptr; // Default value = +infinity.
    2703         386 :   if (Bound[K].Iterations) {
    2704         382 :     const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff);
    2705         382 :     const SCEV *NegativePart = getNegativePart(Delta);
    2706         382 :     Bound[K].Lower[Dependence::DVEntry::EQ] =
    2707         382 :       SE->getMulExpr(NegativePart, Bound[K].Iterations);
    2708         382 :     const SCEV *PositivePart = getPositivePart(Delta);
    2709         382 :     Bound[K].Upper[Dependence::DVEntry::EQ] =
    2710         382 :       SE->getMulExpr(PositivePart, Bound[K].Iterations);
    2711             :   }
    2712             :   else {
    2713             :     // If the positive/negative part of the difference is 0,
    2714             :     // we won't need to know the number of iterations.
    2715           4 :     const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff);
    2716           4 :     const SCEV *NegativePart = getNegativePart(Delta);
    2717           4 :     if (NegativePart->isZero())
    2718           4 :       Bound[K].Lower[Dependence::DVEntry::EQ] = NegativePart; // Zero
    2719           4 :     const SCEV *PositivePart = getPositivePart(Delta);
    2720           4 :     if (PositivePart->isZero())
    2721           4 :       Bound[K].Upper[Dependence::DVEntry::EQ] = PositivePart; // Zero
    2722             :   }
    2723         386 : }
    2724             : 
    2725             : 
    2726             : // Computes the upper and lower bounds for level K
    2727             : // using the < direction. Records them in Bound.
    2728             : // Wolfe gives the equations
    2729             : //
    2730             : //    LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
    2731             : //    UB^<_k = (A^+_k - B_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
    2732             : //
    2733             : // Since we normalize loops, we can simplify these equations to
    2734             : //
    2735             : //    LB^<_k = (A^-_k - B_k)^- (U_k - 1) - B_k
    2736             : //    UB^<_k = (A^+_k - B_k)^+ (U_k - 1) - B_k
    2737             : //
    2738             : // We must be careful to handle the case where the upper bound is unknown.
    2739         386 : void DependenceInfo::findBoundsLT(CoefficientInfo *A, CoefficientInfo *B,
    2740             :                                   BoundInfo *Bound, unsigned K) const {
    2741         386 :   Bound[K].Lower[Dependence::DVEntry::LT] = nullptr; // Default value = -infinity.
    2742         386 :   Bound[K].Upper[Dependence::DVEntry::LT] = nullptr; // Default value = +infinity.
    2743         386 :   if (Bound[K].Iterations) {
    2744         764 :     const SCEV *Iter_1 = SE->getMinusSCEV(
    2745         382 :         Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));
    2746             :     const SCEV *NegPart =
    2747         382 :       getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff));
    2748         382 :     Bound[K].Lower[Dependence::DVEntry::LT] =
    2749         382 :       SE->getMinusSCEV(SE->getMulExpr(NegPart, Iter_1), B[K].Coeff);
    2750             :     const SCEV *PosPart =
    2751         382 :       getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff));
    2752         382 :     Bound[K].Upper[Dependence::DVEntry::LT] =
    2753         382 :       SE->getMinusSCEV(SE->getMulExpr(PosPart, Iter_1), B[K].Coeff);
    2754             :   }
    2755             :   else {
    2756             :     // If the positive/negative part of the difference is 0,
    2757             :     // we won't need to know the number of iterations.
    2758             :     const SCEV *NegPart =
    2759           4 :       getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff));
    2760           4 :     if (NegPart->isZero())
    2761           4 :       Bound[K].Lower[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff);
    2762             :     const SCEV *PosPart =
    2763           4 :       getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff));
    2764           4 :     if (PosPart->isZero())
    2765           4 :       Bound[K].Upper[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff);
    2766             :   }
    2767         386 : }
    2768             : 
    2769             : 
    2770             : // Computes the upper and lower bounds for level K
    2771             : // using the > direction. Records them in Bound.
    2772             : // Wolfe gives the equations
    2773             : //
    2774             : //    LB^>_k = (A_k - B^+_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k
    2775             : //    UB^>_k = (A_k - B^-_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k
    2776             : //
    2777             : // Since we normalize loops, we can simplify these equations to
    2778             : //
    2779             : //    LB^>_k = (A_k - B^+_k)^- (U_k - 1) + A_k
    2780             : //    UB^>_k = (A_k - B^-_k)^+ (U_k - 1) + A_k
    2781             : //
    2782             : // We must be careful to handle the case where the upper bound is unknown.
    2783         386 : void DependenceInfo::findBoundsGT(CoefficientInfo *A, CoefficientInfo *B,
    2784             :                                   BoundInfo *Bound, unsigned K) const {
    2785         386 :   Bound[K].Lower[Dependence::DVEntry::GT] = nullptr; // Default value = -infinity.
    2786         386 :   Bound[K].Upper[Dependence::DVEntry::GT] = nullptr; // Default value = +infinity.
    2787         386 :   if (Bound[K].Iterations) {
    2788         764 :     const SCEV *Iter_1 = SE->getMinusSCEV(
    2789         382 :         Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));
    2790             :     const SCEV *NegPart =
    2791         382 :       getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart));
    2792         382 :     Bound[K].Lower[Dependence::DVEntry::GT] =
    2793         382 :       SE->getAddExpr(SE->getMulExpr(NegPart, Iter_1), A[K].Coeff);
    2794             :     const SCEV *PosPart =
    2795         382 :       getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart));
    2796         382 :     Bound[K].Upper[Dependence::DVEntry::GT] =
    2797         382 :       SE->getAddExpr(SE->getMulExpr(PosPart, Iter_1), A[K].Coeff);
    2798             :   }
    2799             :   else {
    2800             :     // If the positive/negative part of the difference is 0,
    2801             :     // we won't need to know the number of iterations.
    2802           4 :     const SCEV *NegPart = getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart));
    2803           4 :     if (NegPart->isZero())
    2804           4 :       Bound[K].Lower[Dependence::DVEntry::GT] = A[K].Coeff;
    2805           4 :     const SCEV *PosPart = getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart));
    2806           4 :     if (PosPart->isZero())
    2807           4 :       Bound[K].Upper[Dependence::DVEntry::GT] = A[K].Coeff;
    2808             :   }
    2809         386 : }
    2810             : 
    2811             : 
    2812             : // X^+ = max(X, 0)
    2813        1926 : const SCEV *DependenceInfo::getPositivePart(const SCEV *X) const {
    2814        3852 :   return SE->getSMaxExpr(X, SE->getZero(X->getType()));
    2815             : }
    2816             : 
    2817             : 
    2818             : // X^- = min(X, 0)
    2819        1926 : const SCEV *DependenceInfo::getNegativePart(const SCEV *X) const {
    2820        3852 :   return SE->getSMinExpr(X, SE->getZero(X->getType()));
    2821             : }
    2822             : 
    2823             : 
    2824             : // Walks through the subscript,
    2825             : // collecting each coefficient, the associated loop bounds,
    2826             : // and recording its positive and negative parts for later use.
    2827             : DependenceInfo::CoefficientInfo *
    2828         382 : DependenceInfo::collectCoeffInfo(const SCEV *Subscript, bool SrcFlag,
    2829             :                                  const SCEV *&Constant) const {
    2830         764 :   const SCEV *Zero = SE->getZero(Subscript->getType());
    2831         382 :   CoefficientInfo *CI = new CoefficientInfo[MaxLevels + 1];
    2832        1292 :   for (unsigned K = 1; K <= MaxLevels; ++K) {
    2833         910 :     CI[K].Coeff = Zero;
    2834         910 :     CI[K].PosPart = Zero;
    2835         910 :     CI[K].NegPart = Zero;
    2836         910 :     CI[K].Iterations = nullptr;
    2837             :   }
    2838         768 :   while (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Subscript)) {
    2839         768 :     const Loop *L = AddRec->getLoop();
    2840         768 :     unsigned K = SrcFlag ? mapSrcLoop(L) : mapDstLoop(L);
    2841         768 :     CI[K].Coeff = AddRec->getStepRecurrence(*SE);
    2842         768 :     CI[K].PosPart = getPositivePart(CI[K].Coeff);
    2843         768 :     CI[K].NegPart = getNegativePart(CI[K].Coeff);
    2844         768 :     CI[K].Iterations = collectUpperBound(L, Subscript->getType());
    2845         768 :     Subscript = AddRec->getStart();
    2846         768 :   }
    2847         382 :   Constant = Subscript;
    2848             : #ifndef NDEBUG
    2849             :   DEBUG(dbgs() << "\tCoefficient Info\n");
    2850             :   for (unsigned K = 1; K <= MaxLevels; ++K) {
    2851             :     DEBUG(dbgs() << "\t    " << K << "\t" << *CI[K].Coeff);
    2852             :     DEBUG(dbgs() << "\tPos Part = ");
    2853             :     DEBUG(dbgs() << *CI[K].PosPart);
    2854             :     DEBUG(dbgs() << "\tNeg Part = ");
    2855             :     DEBUG(dbgs() << *CI[K].NegPart);
    2856             :     DEBUG(dbgs() << "\tUpper Bound = ");
    2857             :     if (CI[K].Iterations)
    2858             :       DEBUG(dbgs() << *CI[K].Iterations);
    2859             :     else
    2860             :       DEBUG(dbgs() << "+inf");
    2861             :     DEBUG(dbgs() << '\n');
    2862             :   }
    2863             :   DEBUG(dbgs() << "\t    Constant = " << *Subscript << '\n');
    2864             : #endif
    2865         382 :   return CI;
    2866             : }
    2867             : 
    2868             : 
    2869             : // Looks through all the bounds info and
    2870             : // computes the lower bound given the current direction settings
    2871             : // at each level. If the lower bound for any level is -inf,
    2872             : // the result is -inf.
    2873        1877 : const SCEV *DependenceInfo::getLowerBound(BoundInfo *Bound) const {
    2874        1877 :   const SCEV *Sum = Bound[1].Lower[Bound[1].Direction];
    2875        5102 :   for (unsigned K = 2; Sum && K <= MaxLevels; ++K) {
    2876        3225 :     if (Bound[K].Lower[Bound[K].Direction])
    2877        3225 :       Sum = SE->getAddExpr(Sum, Bound[K].Lower[Bound[K].Direction]);
    2878             :     else
    2879             :       Sum = nullptr;
    2880             :   }
    2881        1877 :   return Sum;
    2882             : }
    2883             : 
    2884             : 
    2885             : // Looks through all the bounds info and
    2886             : // computes the upper bound given the current direction settings
    2887             : // at each level. If the upper bound at any level is +inf,
    2888             : // the result is +inf.
    2889        1470 : const SCEV *DependenceInfo::getUpperBound(BoundInfo *Bound) const {
    2890        1470 :   const SCEV *Sum = Bound[1].Upper[Bound[1].Direction];
    2891        4135 :   for (unsigned K = 2; Sum && K <= MaxLevels; ++K) {
    2892        2665 :     if (Bound[K].Upper[Bound[K].Direction])
    2893        2665 :       Sum = SE->getAddExpr(Sum, Bound[K].Upper[Bound[K].Direction]);
    2894             :     else
    2895             :       Sum = nullptr;
    2896             :   }
    2897        1470 :   return Sum;
    2898             : }
    2899             : 
    2900             : 
    2901             : //===----------------------------------------------------------------------===//
    2902             : // Constraint manipulation for Delta test.
    2903             : 
    2904             : // Given a linear SCEV,
    2905             : // return the coefficient (the step)
    2906             : // corresponding to the specified loop.
    2907             : // If there isn't one, return 0.
    2908             : // For example, given a*i + b*j + c*k, finding the coefficient
    2909             : // corresponding to the j loop would yield b.
    2910         130 : const SCEV *DependenceInfo::findCoefficient(const SCEV *Expr,
    2911             :                                             const Loop *TargetLoop) const {
    2912         189 :   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
    2913             :   if (!AddRec)
    2914         189 :     return SE->getZero(Expr->getType());
    2915         189 :   if (AddRec->getLoop() == TargetLoop)
    2916          67 :     return AddRec->getStepRecurrence(*SE);
    2917         122 :   return findCoefficient(AddRec->getStart(), TargetLoop);
    2918             : }
    2919             : 
    2920             : 
    2921             : // Given a linear SCEV,
    2922             : // return the SCEV given by zeroing out the coefficient
    2923             : // corresponding to the specified loop.
    2924             : // For example, given a*i + b*j + c*k, zeroing the coefficient
    2925             : // corresponding to the j loop would yield a*i + c*k.
    2926         129 : const SCEV *DependenceInfo::zeroCoefficient(const SCEV *Expr,
    2927             :                                             const Loop *TargetLoop) const {
    2928         127 :   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
    2929             :   if (!AddRec)
    2930             :     return Expr; // ignore
    2931         127 :   if (AddRec->getLoop() == TargetLoop)
    2932          64 :     return AddRec->getStart();
    2933         189 :   return SE->getAddRecExpr(zeroCoefficient(AddRec->getStart(), TargetLoop),
    2934             :                            AddRec->getStepRecurrence(*SE),
    2935             :                            AddRec->getLoop(),
    2936          63 :                            AddRec->getNoWrapFlags());
    2937             : }
    2938             : 
    2939             : 
    2940             : // Given a linear SCEV Expr,
    2941             : // return the SCEV given by adding some Value to the
    2942             : // coefficient corresponding to the specified TargetLoop.
    2943             : // For example, given a*i + b*j + c*k, adding 1 to the coefficient
    2944             : // corresponding to the j loop would yield a*i + (b+1)*j + c*k.
    2945         111 : const SCEV *DependenceInfo::addToCoefficient(const SCEV *Expr,
    2946             :                                              const Loop *TargetLoop,
    2947             :                                              const SCEV *Value) const {
    2948         111 :   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
    2949             :   if (!AddRec) // create a new addRec
    2950           0 :     return SE->getAddRecExpr(Expr,
    2951             :                              Value,
    2952             :                              TargetLoop,
    2953           0 :                              SCEV::FlagAnyWrap); // Worst case, with no info.
    2954         111 :   if (AddRec->getLoop() == TargetLoop) {
    2955          55 :     const SCEV *Sum = SE->getAddExpr(AddRec->getStepRecurrence(*SE), Value);
    2956          55 :     if (Sum->isZero())
    2957          53 :       return AddRec->getStart();
    2958           4 :     return SE->getAddRecExpr(AddRec->getStart(),
    2959             :                              Sum,
    2960             :                              AddRec->getLoop(),
    2961           2 :                              AddRec->getNoWrapFlags());
    2962             :   }
    2963          56 :   if (SE->isLoopInvariant(AddRec, TargetLoop))
    2964           1 :     return SE->getAddRecExpr(AddRec, Value, TargetLoop, SCEV::FlagAnyWrap);
    2965         165 :   return SE->getAddRecExpr(
    2966             :       addToCoefficient(AddRec->getStart(), TargetLoop, Value),
    2967             :       AddRec->getStepRecurrence(*SE), AddRec->getLoop(),
    2968          55 :       AddRec->getNoWrapFlags());
    2969             : }
    2970             : 
    2971             : 
    2972             : // Review the constraints, looking for opportunities
    2973             : // to simplify a subscript pair (Src and Dst).
    2974             : // Return true if some simplification occurs.
    2975             : // If the simplification isn't exact (that is, if it is conservative
    2976             : // in terms of dependence), set consistent to false.
    2977             : // Corresponds to Figure 5 from the paper
    2978             : //
    2979             : //            Practical Dependence Testing
    2980             : //            Goff, Kennedy, Tseng
    2981             : //            PLDI 1991
    2982          72 : bool DependenceInfo::propagate(const SCEV *&Src, const SCEV *&Dst,
    2983             :                                SmallBitVector &Loops,
    2984             :                                SmallVectorImpl<Constraint> &Constraints,
    2985             :                                bool &Consistent) {
    2986          72 :   bool Result = false;
    2987         221 :   for (unsigned LI : Loops.set_bits()) {
    2988             :     DEBUG(dbgs() << "\t    Constraint[" << LI << "] is");
    2989             :     DEBUG(Constraints[LI].dump(dbgs()));
    2990         298 :     if (Constraints[LI].isDistance())
    2991         116 :       Result |= propagateDistance(Src, Dst, Constraints[LI], Consistent);
    2992         273 :     else if (Constraints[LI].isLine())
    2993          12 :       Result |= propagateLine(Src, Dst, Constraints[LI], Consistent);
    2994         170 :     else if (Constraints[LI].isPoint())
    2995           6 :       Result |= propagatePoint(Src, Dst, Constraints[LI]);
    2996             :   }
    2997          72 :   return Result;
    2998             : }
    2999             : 
    3000             : 
    3001             : // Attempt to propagate a distance
    3002             : // constraint into a subscript pair (Src and Dst).
    3003             : // Return true if some simplification occurs.
    3004             : // If the simplification isn't exact (that is, if it is conservative
    3005             : // in terms of dependence), set consistent to false.
    3006          58 : bool DependenceInfo::propagateDistance(const SCEV *&Src, const SCEV *&Dst,
    3007             :                                        Constraint &CurConstraint,
    3008             :                                        bool &Consistent) {
    3009          58 :   const Loop *CurLoop = CurConstraint.getAssociatedLoop();
    3010             :   DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n");
    3011          58 :   const SCEV *A_K = findCoefficient(Src, CurLoop);
    3012          58 :   if (A_K->isZero())
    3013             :     return false;
    3014          54 :   const SCEV *DA_K = SE->getMulExpr(A_K, CurConstraint.getD());
    3015          54 :   Src = SE->getMinusSCEV(Src, DA_K);
    3016          54 :   Src = zeroCoefficient(Src, CurLoop);
    3017             :   DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n");
    3018             :   DEBUG(dbgs() << "\t\tDst is " << *Dst << "\n");
    3019          54 :   Dst = addToCoefficient(Dst, CurLoop, SE->getNegativeSCEV(A_K));
    3020             :   DEBUG(dbgs() << "\t\tnew Dst is " << *Dst << "\n");
    3021          54 :   if (!findCoefficient(Dst, CurLoop)->isZero())
    3022           3 :     Consistent = false;
    3023             :   return true;
    3024             : }
    3025             : 
    3026             : 
    3027             : // Attempt to propagate a line
    3028             : // constraint into a subscript pair (Src and Dst).
    3029             : // Return true if some simplification occurs.
    3030             : // If the simplification isn't exact (that is, if it is conservative
    3031             : // in terms of dependence), set consistent to false.
    3032           6 : bool DependenceInfo::propagateLine(const SCEV *&Src, const SCEV *&Dst,
    3033             :                                    Constraint &CurConstraint,
    3034             :                                    bool &Consistent) {
    3035           6 :   const Loop *CurLoop = CurConstraint.getAssociatedLoop();
    3036           6 :   const SCEV *A = CurConstraint.getA();
    3037           6 :   const SCEV *B = CurConstraint.getB();
    3038           6 :   const SCEV *C = CurConstraint.getC();
    3039             :   DEBUG(dbgs() << "\t\tA = " << *A << ", B = " << *B << ", C = " << *C << "\n");
    3040             :   DEBUG(dbgs() << "\t\tSrc = " << *Src << "\n");
    3041             :   DEBUG(dbgs() << "\t\tDst = " << *Dst << "\n");
    3042           6 :   if (A->isZero()) {
    3043           1 :     const SCEVConstant *Bconst = dyn_cast<SCEVConstant>(B);
    3044           1 :     const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C);
    3045           1 :     if (!Bconst || !Cconst) return false;
    3046           3 :     APInt Beta = Bconst->getAPInt();
    3047           3 :     APInt Charlie = Cconst->getAPInt();
    3048           2 :     APInt CdivB = Charlie.sdiv(Beta);
    3049             :     assert(Charlie.srem(Beta) == 0 && "C should be evenly divisible by B");
    3050           1 :     const SCEV *AP_K = findCoefficient(Dst, CurLoop);
    3051             :     //    Src = SE->getAddExpr(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB)));
    3052           1 :     Src = SE->getMinusSCEV(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB)));
    3053           1 :     Dst = zeroCoefficient(Dst, CurLoop);
    3054           1 :     if (!findCoefficient(Src, CurLoop)->isZero())
    3055           0 :       Consistent = false;
    3056             :   }
    3057           5 :   else if (B->isZero()) {
    3058           3 :     const SCEVConstant *Aconst = dyn_cast<SCEVConstant>(A);
    3059           3 :     const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C);
    3060           3 :     if (!Aconst || !Cconst) return false;
    3061           9 :     APInt Alpha = Aconst->getAPInt();
    3062           9 :     APInt Charlie = Cconst->getAPInt();
    3063           6 :     APInt CdivA = Charlie.sdiv(Alpha);
    3064             :     assert(Charlie.srem(Alpha) == 0 && "C should be evenly divisible by A");
    3065           3 :     const SCEV *A_K = findCoefficient(Src, CurLoop);
    3066           3 :     Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA)));
    3067           3 :     Src = zeroCoefficient(Src, CurLoop);
    3068           3 :     if (!findCoefficient(Dst, CurLoop)->isZero())
    3069           0 :       Consistent = false;
    3070             :   }
    3071           2 :   else if (isKnownPredicate(CmpInst::ICMP_EQ, A, B)) {
    3072           1 :     const SCEVConstant *Aconst = dyn_cast<SCEVConstant>(A);
    3073           1 :     const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C);
    3074           1 :     if (!Aconst || !Cconst) return false;
    3075           3 :     APInt Alpha = Aconst->getAPInt();
    3076           3 :     APInt Charlie = Cconst->getAPInt();
    3077           2 :     APInt CdivA = Charlie.sdiv(Alpha);
    3078             :     assert(Charlie.srem(Alpha) == 0 && "C should be evenly divisible by A");
    3079           1 :     const SCEV *A_K = findCoefficient(Src, CurLoop);
    3080           1 :     Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA)));
    3081           1 :     Src = zeroCoefficient(Src, CurLoop);
    3082           1 :     Dst = addToCoefficient(Dst, CurLoop, A_K);
    3083           1 :     if (!findCoefficient(Dst, CurLoop)->isZero())
    3084           0 :       Consistent = false;
    3085             :   }
    3086             :   else {
    3087             :     // paper is incorrect here, or perhaps just misleading
    3088           1 :     const SCEV *A_K = findCoefficient(Src, CurLoop);
    3089           1 :     Src = SE->getMulExpr(Src, A);
    3090           1 :     Dst = SE->getMulExpr(Dst, A);
    3091           1 :     Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, C));
    3092           1 :     Src = zeroCoefficient(Src, CurLoop);
    3093           1 :     Dst = addToCoefficient(Dst, CurLoop, SE->getMulExpr(A_K, B));
    3094           1 :     if (!findCoefficient(Dst, CurLoop)->isZero())
    3095           0 :       Consistent = false;
    3096             :   }
    3097             :   DEBUG(dbgs() << "\t\tnew Src = " << *Src << "\n");
    3098             :   DEBUG(dbgs() << "\t\tnew Dst = " << *Dst << "\n");
    3099             :   return true;
    3100             : }
    3101             : 
    3102             : 
    3103             : // Attempt to propagate a point
    3104             : // constraint into a subscript pair (Src and Dst).
    3105             : // Return true if some simplification occurs.
    3106           3 : bool DependenceInfo::propagatePoint(const SCEV *&Src, const SCEV *&Dst,
    3107             :                                     Constraint &CurConstraint) {
    3108           3 :   const Loop *CurLoop = CurConstraint.getAssociatedLoop();
    3109           3 :   const SCEV *A_K = findCoefficient(Src, CurLoop);
    3110           3 :   const SCEV *AP_K = findCoefficient(Dst, CurLoop);
    3111           3 :   const SCEV *XA_K = SE->getMulExpr(A_K, CurConstraint.getX());
    3112           3 :   const SCEV *YAP_K = SE->getMulExpr(AP_K, CurConstraint.getY());
    3113             :   DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n");
    3114           3 :   Src = SE->getAddExpr(Src, SE->getMinusSCEV(XA_K, YAP_K));
    3115           3 :   Src = zeroCoefficient(Src, CurLoop);
    3116             :   DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n");
    3117             :   DEBUG(dbgs() << "\t\tDst is " << *Dst << "\n");
    3118           3 :   Dst = zeroCoefficient(Dst, CurLoop);
    3119             :   DEBUG(dbgs() << "\t\tnew Dst is " << *Dst << "\n");
    3120           3 :   return true;
    3121             : }
    3122             : 
    3123             : 
    3124             : // Update direction vector entry based on the current constraint.
    3125         143 : void DependenceInfo::updateDirection(Dependence::DVEntry &Level,
    3126             :                                      const Constraint &CurConstraint) const {
    3127             :   DEBUG(dbgs() << "\tUpdate direction, constraint =");
    3128             :   DEBUG(CurConstraint.dump(dbgs()));
    3129         143 :   if (CurConstraint.isAny())
    3130             :     ; // use defaults
    3131         143 :   else if (CurConstraint.isDistance()) {
    3132             :     // this one is consistent, the others aren't
    3133         125 :     Level.Scalar = false;
    3134         125 :     Level.Distance = CurConstraint.getD();
    3135         125 :     unsigned NewDirection = Dependence::DVEntry::NONE;
    3136         125 :     if (!SE->isKnownNonZero(Level.Distance)) // if may be zero
    3137         111 :       NewDirection = Dependence::DVEntry::EQ;
    3138         125 :     if (!SE->isKnownNonPositive(Level.Distance)) // if may be positive
    3139           6 :       NewDirection |= Dependence::DVEntry::LT;
    3140         125 :     if (!SE->isKnownNonNegative(Level.Distance)) // if may be negative
    3141           8 :       NewDirection |= Dependence::DVEntry::GT;
    3142         125 :     Level.Direction &= NewDirection;
    3143             :   }
    3144          36 :   else if (CurConstraint.isLine()) {
    3145           6 :     Level.Scalar = false;
    3146           6 :     Level.Distance = nullptr;
    3147             :     // direction should be accurate
    3148             :   }
    3149          12 :   else if (CurConstraint.isPoint()) {
    3150          12 :     Level.Scalar = false;
    3151          12 :     Level.Distance = nullptr;
    3152          12 :     unsigned NewDirection = Dependence::DVEntry::NONE;
    3153          12 :     if (!isKnownPredicate(CmpInst::ICMP_NE,
    3154             :                           CurConstraint.getY(),
    3155             :                           CurConstraint.getX()))
    3156             :       // if X may be = Y
    3157           6 :       NewDirection |= Dependence::DVEntry::EQ;
    3158          12 :     if (!isKnownPredicate(CmpInst::ICMP_SLE,
    3159             :                           CurConstraint.getY(),
    3160             :                           CurConstraint.getX()))
    3161             :       // if Y may be > X
    3162           2 :       NewDirection |= Dependence::DVEntry::LT;
    3163          12 :     if (!isKnownPredicate(CmpInst::ICMP_SGE,
    3164             :                           CurConstraint.getY(),
    3165             :                           CurConstraint.getX()))
    3166             :       // if Y may be < X
    3167           4 :       NewDirection |= Dependence::DVEntry::GT;
    3168          12 :     Level.Direction &= NewDirection;
    3169             :   }
    3170             :   else
    3171           0 :     llvm_unreachable("constraint has unexpected kind");
    3172         143 : }
    3173             : 
    3174             : /// Check if we can delinearize the subscripts. If the SCEVs representing the
    3175             : /// source and destination array references are recurrences on a nested loop,
    3176             : /// this function flattens the nested recurrences into separate recurrences
    3177             : /// for each loop level.
    3178         100 : bool DependenceInfo::tryDelinearize(Instruction *Src, Instruction *Dst,
    3179             :                                     SmallVectorImpl<Subscript> &Pair) {
    3180         100 :   Value *SrcPtr = getPointerOperand(Src);
    3181         100 :   Value *DstPtr = getPointerOperand(Dst);
    3182             : 
    3183         200 :   Loop *SrcLoop = LI->getLoopFor(Src->getParent());
    3184         200 :   Loop *DstLoop = LI->getLoopFor(Dst->getParent());
    3185             : 
    3186             :   // Below code mimics the code in Delinearization.cpp
    3187             :   const SCEV *SrcAccessFn =
    3188         100 :     SE->getSCEVAtScope(SrcPtr, SrcLoop);
    3189             :   const SCEV *DstAccessFn =
    3190         100 :     SE->getSCEVAtScope(DstPtr, DstLoop);
    3191             : 
    3192             :   const SCEVUnknown *SrcBase =
    3193         200 :       dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));
    3194             :   const SCEVUnknown *DstBase =
    3195         200 :       dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));
    3196             : 
    3197         100 :   if (!SrcBase || !DstBase || SrcBase != DstBase)
    3198             :     return false;
    3199             : 
    3200         100 :   const SCEV *ElementSize = SE->getElementSize(Src);
    3201         100 :   if (ElementSize != SE->getElementSize(Dst))
    3202             :     return false;
    3203             : 
    3204         100 :   const SCEV *SrcSCEV = SE->getMinusSCEV(SrcAccessFn, SrcBase);
    3205         100 :   const SCEV *DstSCEV = SE->getMinusSCEV(DstAccessFn, DstBase);
    3206             : 
    3207         100 :   const SCEVAddRecExpr *SrcAR = dyn_cast<SCEVAddRecExpr>(SrcSCEV);
    3208         100 :   const SCEVAddRecExpr *DstAR = dyn_cast<SCEVAddRecExpr>(DstSCEV);
    3209         276 :   if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine())
    3210             :     return false;
    3211             : 
    3212             :   // First step: collect parametric terms in both array references.
    3213          88 :   SmallVector<const SCEV *, 4> Terms;
    3214          88 :   SE->collectParametricTerms(SrcAR, Terms);
    3215          88 :   SE->collectParametricTerms(DstAR, Terms);
    3216             : 
    3217             :   // Second step: find subscript sizes.
    3218         176 :   SmallVector<const SCEV *, 4> Sizes;
    3219          88 :   SE->findArrayDimensions(Terms, Sizes, ElementSize);
    3220             : 
    3221             :   // Third step: compute the access functions for each subscript.
    3222         352 :   SmallVector<const SCEV *, 4> SrcSubscripts, DstSubscripts;
    3223          88 :   SE->computeAccessFunctions(SrcAR, SrcSubscripts, Sizes);
    3224          88 :   SE->computeAccessFunctions(DstAR, DstSubscripts, Sizes);
    3225             : 
    3226             :   // Fail when there is only a subscript: that's a linearized access function.
    3227         110 :   if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 ||
    3228          22 :       SrcSubscripts.size() != DstSubscripts.size())
    3229             :     return false;
    3230             : 
    3231          11 :   int size = SrcSubscripts.size();
    3232             : 
    3233             :   DEBUG({
    3234             :       dbgs() << "\nSrcSubscripts: ";
    3235             :     for (int i = 0; i < size; i++)
    3236             :       dbgs() << *SrcSubscripts[i];
    3237             :     dbgs() << "\nDstSubscripts: ";
    3238             :     for (int i = 0; i < size; i++)
    3239             :       dbgs() << *DstSubscripts[i];
    3240             :     });
    3241             : 
    3242             :   // The delinearization transforms a single-subscript MIV dependence test into
    3243             :   // a multi-subscript SIV dependence test that is easier to compute. So we
    3244             :   // resize Pair to contain as many pairs of subscripts as the delinearization
    3245             :   // has found, and then initialize the pairs following the delinearization.
    3246          11 :   Pair.resize(size);
    3247          33 :   for (int i = 0; i < size; ++i) {
    3248          66 :     Pair[i].Src = SrcSubscripts[i];
    3249          66 :     Pair[i].Dst = DstSubscripts[i];
    3250          66 :     unifySubscriptType(&Pair[i]);
    3251             : 
    3252             :     // FIXME: we should record the bounds SrcSizes[i] and DstSizes[i] that the
    3253             :     // delinearization has found, and add these constraints to the dependence
    3254             :     // check to avoid memory accesses overflow from one dimension into another.
    3255             :     // This is related to the problem of determining the existence of data
    3256             :     // dependences in array accesses using a different number of subscripts: in
    3257             :     // C one can access an array A[100][100]; as A[0][9999], *A[9999], etc.
    3258             :   }
    3259             : 
    3260             :   return true;
    3261             : }
    3262             : 
    3263             : //===----------------------------------------------------------------------===//
    3264             : 
    3265             : #ifndef NDEBUG
    3266             : // For debugging purposes, dump a small bit vector to dbgs().
    3267             : static void dumpSmallBitVector(SmallBitVector &BV) {
    3268             :   dbgs() << "{";
    3269             :   for (unsigned VI : BV.set_bits()) {
    3270             :     dbgs() << VI;
    3271             :     if (BV.find_next(VI) >= 0)
    3272             :       dbgs() << ' ';
    3273             :   }
    3274             :   dbgs() << "}\n";
    3275             : }
    3276             : #endif
    3277             : 
    3278             : // depends -
    3279             : // Returns NULL if there is no dependence.
    3280             : // Otherwise, return a Dependence with as many details as possible.
    3281             : // Corresponds to Section 3.1 in the paper
    3282             : //
    3283             : //            Practical Dependence Testing
    3284             : //            Goff, Kennedy, Tseng
    3285             : //            PLDI 1991
    3286             : //
    3287             : // Care is required to keep the routine below, getSplitIteration(),
    3288             : // up to date with respect to this routine.
    3289             : std::unique_ptr<Dependence>
    3290        1726 : DependenceInfo::depends(Instruction *Src, Instruction *Dst,
    3291             :                         bool PossiblyLoopIndependent) {
    3292        1726 :   if (Src == Dst)
    3293         571 :     PossiblyLoopIndependent = false;
    3294             : 
    3295        3452 :   if ((!Src->mayReadFromMemory() && !Src->mayWriteToMemory()) ||
    3296        2866 :       (!Dst->mayReadFromMemory() && !Dst->mayWriteToMemory()))
    3297             :     // if both instructions don't reference memory, there's no dependence
    3298             :     return nullptr;
    3299             : 
    3300        1726 :   if (!isLoadOrStore(Src) || !isLoadOrStore(Dst)) {
    3301             :     // can only analyze simple loads and stores, i.e., no calls, invokes, etc.
    3302             :     DEBUG(dbgs() << "can only handle simple loads and stores\n");
    3303           0 :     return make_unique<Dependence>(Src, Dst);
    3304             :   }
    3305             : 
    3306        3452 :   Value *SrcPtr = getPointerOperand(Src);
    3307        3452 :   Value *DstPtr = getPointerOperand(Dst);
    3308             : 
    3309        1726 :   switch (underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), DstPtr,
    3310             :                                  SrcPtr)) {
    3311         546 :   case MayAlias:
    3312             :   case PartialAlias:
    3313             :     // cannot analyse objects if we don't understand their aliasing.
    3314             :     DEBUG(dbgs() << "can't analyze may or partial alias\n");
    3315         546 :     return make_unique<Dependence>(Src, Dst);
    3316         275 :   case NoAlias:
    3317             :     // If the objects noalias, they are distinct, accesses are independent.
    3318             :     DEBUG(dbgs() << "no alias\n");
    3319             :     return nullptr;
    3320             :   case MustAlias:
    3321             :     break; // The underlying objects alias; test accesses for dependence.
    3322             :   }
    3323             : 
    3324             :   // establish loop nesting levels
    3325         905 :   establishNestingLevels(Src, Dst);
    3326             :   DEBUG(dbgs() << "    common nesting levels = " << CommonLevels << "\n");
    3327             :   DEBUG(dbgs() << "    maximum nesting levels = " << MaxLevels << "\n");
    3328             : 
    3329        1810 :   FullDependence Result(Src, Dst, PossiblyLoopIndependent, CommonLevels);
    3330         905 :   ++TotalArrayPairs;
    3331             : 
    3332             :   // See if there are GEPs we can use.
    3333         905 :   bool UsefulGEP = false;
    3334         905 :   GEPOperator *SrcGEP = dyn_cast<GEPOperator>(SrcPtr);
    3335         905 :   GEPOperator *DstGEP = dyn_cast<GEPOperator>(DstPtr);
    3336        1525 :   if (SrcGEP && DstGEP &&
    3337        1240 :       SrcGEP->getPointerOperandType() == DstGEP->getPointerOperandType()) {
    3338        1240 :     const SCEV *SrcPtrSCEV = SE->getSCEV(SrcGEP->getPointerOperand());
    3339        1240 :     const SCEV *DstPtrSCEV = SE->getSCEV(DstGEP->getPointerOperand());
    3340             :     DEBUG(dbgs() << "    SrcPtrSCEV = " << *SrcPtrSCEV << "\n");
    3341             :     DEBUG(dbgs() << "    DstPtrSCEV = " << *DstPtrSCEV << "\n");
    3342             : 
    3343        2469 :     UsefulGEP = isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) &&
    3344        1848 :                 isLoopInvariant(DstPtrSCEV, LI->getLoopFor(Dst->getParent())) &&
    3345        3083 :                 (SrcGEP->getNumOperands() == DstGEP->getNumOperands()) &&
    3346         615 :                 isKnownPredicate(CmpInst::ICMP_EQ, SrcPtrSCEV, DstPtrSCEV);
    3347             :   }
    3348        1226 :   unsigned Pairs = UsefulGEP ? SrcGEP->idx_end() - SrcGEP->idx_begin() : 1;
    3349        3620 :   SmallVector<Subscript, 4> Pair(Pairs);
    3350         905 :   if (UsefulGEP) {
    3351             :     DEBUG(dbgs() << "    using GEPs\n");
    3352         613 :     unsigned P = 0;
    3353        1503 :     for (GEPOperator::const_op_iterator SrcIdx = SrcGEP->idx_begin(),
    3354         613 :            SrcEnd = SrcGEP->idx_end(),
    3355         613 :            DstIdx = DstGEP->idx_begin();
    3356        1503 :          SrcIdx != SrcEnd;
    3357             :          ++SrcIdx, ++DstIdx, ++P) {
    3358        1780 :       Pair[P].Src = SE->getSCEV(*SrcIdx);
    3359        1780 :       Pair[P].Dst = SE->getSCEV(*DstIdx);
    3360        2670 :       unifySubscriptType(&Pair[P]);
    3361             :     }
    3362             :   }
    3363             :   else {
    3364             :     DEBUG(dbgs() << "    ignoring GEPs\n");
    3365         292 :     const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
    3366         292 :     const SCEV *DstSCEV = SE->getSCEV(DstPtr);
    3367             :     DEBUG(dbgs() << "    SrcSCEV = " << *SrcSCEV << "\n");
    3368             :     DEBUG(dbgs() << "    DstSCEV = " << *DstSCEV << "\n");
    3369         292 :     Pair[0].Src = SrcSCEV;
    3370         292 :     Pair[0].Dst = DstSCEV;
    3371             :   }
    3372             : 
    3373         905 :   if (Delinearize && CommonLevels > 1) {
    3374         100 :     if (tryDelinearize(Src, Dst, Pair)) {
    3375             :       DEBUG(dbgs() << "    delinearized GEP\n");
    3376          11 :       Pairs = Pair.size();
    3377             :     }
    3378             :   }
    3379             : 
    3380        2098 :   for (unsigned P = 0; P < Pairs; ++P) {
    3381        2386 :     Pair[P].Loops.resize(MaxLevels + 1);
    3382        2386 :     Pair[P].GroupLoops.resize(MaxLevels + 1);
    3383        2386 :     Pair[P].Group.resize(Pairs);
    3384        2386 :     removeMatchingExtensions(&Pair[P]);
    3385        3579 :     Pair[P].Classification =
    3386        5965 :       classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),
    3387        3579 :                    Pair[P].Dst, LI->getLoopFor(Dst->getParent()),
    3388        2386 :                    Pair[P].Loops);
    3389        3579 :     Pair[P].GroupLoops = Pair[P].Loops;
    3390        2386 :     Pair[P].Group.set(P);
    3391             :     DEBUG(dbgs() << "    subscript " << P << "\n");
    3392             :     DEBUG(dbgs() << "\tsrc = " << *Pair[P].Src << "\n");
    3393             :     DEBUG(dbgs() << "\tdst = " << *Pair[P].Dst << "\n");
    3394             :     DEBUG(dbgs() << "\tclass = " << Pair[P].Classification << "\n");
    3395             :     DEBUG(dbgs() << "\tloops = ");
    3396             :     DEBUG(dumpSmallBitVector(Pair[P].Loops));
    3397             :   }
    3398             : 
    3399        1810 :   SmallBitVector Separable(Pairs);
    3400        1810 :   SmallBitVector Coupled(Pairs);
    3401             : 
    3402             :   // Partition subscripts into separable and minimally-coupled groups
    3403             :   // Algorithm in paper is algorithmically better;
    3404             :   // this may be faster in practice. Check someday.
    3405             :   //
    3406             :   // Here's an example of how it works. Consider this code:
    3407             :   //
    3408             :   //   for (i = ...) {
    3409             :   //     for (j = ...) {
    3410             :   //       for (k = ...) {
    3411             :   //         for (l = ...) {
    3412             :   //           for (m = ...) {
    3413             :   //             A[i][j][k][m] = ...;
    3414             :   //             ... = A[0][j][l][i + j];
    3415             :   //           }
    3416             :   //         }
    3417             :   //       }
    3418             :   //     }
    3419             :   //   }
    3420             :   //
    3421             :   // There are 4 subscripts here:
    3422             :   //    0 [i] and [0]
    3423             :   //    1 [j] and [j]
    3424             :   //    2 [k] and [l]
    3425             :   //    3 [m] and [i + j]
    3426             :   //
    3427             :   // We've already classified each subscript pair as ZIV, SIV, etc.,
    3428             :   // and collected all the loops mentioned by pair P in Pair[P].Loops.
    3429             :   // In addition, we've initialized Pair[P].GroupLoops to Pair[P].Loops
    3430             :   // and set Pair[P].Group = {P}.
    3431             :   //
    3432             :   //      Src Dst    Classification Loops  GroupLoops Group
    3433             :   //    0 [i] [0]         SIV       {1}      {1}        {0}
    3434             :   //    1 [j] [j]         SIV       {2}      {2}        {1}
    3435             :   //    2 [k] [l]         RDIV      {3,4}    {3,4}      {2}
    3436             :   //    3 [m] [i + j]     MIV       {1,2,5}  {1,2,5}    {3}
    3437             :   //
    3438             :   // For each subscript SI 0 .. 3, we consider each remaining subscript, SJ.
    3439             :   // So, 0 is compared against 1, 2, and 3; 1 is compared against 2 and 3, etc.
    3440             :   //
    3441             :   // We begin by comparing 0 and 1. The intersection of the GroupLoops is empty.
    3442             :   // Next, 0 and 2. Again, the intersection of their GroupLoops is empty.
    3443             :   // Next 0 and 3. The intersection of their GroupLoop = {1}, not empty,
    3444             :   // so Pair[3].Group = {0,3} and Done = false (that is, 0 will not be added
    3445             :   // to either Separable or Coupled).
    3446             :   //
    3447             :   // Next, we consider 1 and 2. The intersection of the GroupLoops is empty.
    3448             :   // Next, 1 and 3. The intersectionof their GroupLoops = {2}, not empty,
    3449             :   // so Pair[3].Group = {0, 1, 3} and Done = false.
    3450             :   //
    3451             :   // Next, we compare 2 against 3. The intersection of the GroupLoops is empty.
    3452             :   // Since Done remains true, we add 2 to the set of Separable pairs.
    3453             :   //
    3454             :   // Finally, we consider 3. There's nothing to compare it with,
    3455             :   // so Done remains true and we add it to the Coupled set.
    3456             :   // Pair[3].Group = {0, 1, 3} and GroupLoops = {1, 2, 5}.
    3457             :   //
    3458             :   // In the end, we've got 1 separable subscript and 1 coupled group.
    3459        2098 :   for (unsigned SI = 0; SI < Pairs; ++SI) {
    3460        2386 :     if (Pair[SI].Classification == Subscript::NonLinear) {
    3461             :       // ignore these, but collect loops for later
    3462          81 :       ++NonlinearSubscriptPairs;
    3463         243 :       collectCommonLoops(Pair[SI].Src,
    3464         162 :                          LI->getLoopFor(Src->getParent()),
    3465         162 :                          Pair[SI].Loops);
    3466         243 :       collectCommonLoops(Pair[SI].Dst,
    3467         162 :                          LI->getLoopFor(Dst->getParent()),
    3468         162 :                          Pair[SI].Loops);
    3469          81 :       Result.Consistent = false;
    3470        2224 :     } else if (Pair[SI].Classification == Subscript::ZIV) {
    3471             :       // always separable
    3472         250 :       Separable.set(SI);
    3473             :     }
    3474             :     else {
    3475             :       // SIV, RDIV, or MIV, so check for coupled group
    3476         862 :       bool Done = true;
    3477        1172 :       for (unsigned SJ = SI + 1; SJ < Pairs; ++SJ) {
    3478         930 :         SmallBitVector Intersection = Pair[SI].GroupLoops;
    3479         620 :         Intersection &= Pair[SJ].GroupLoops;
    3480         310 :         if (Intersection.any()) {
    3481             :           // accumulate set of all the loops in group
    3482         498 :           Pair[SJ].GroupLoops |= Pair[SI].GroupLoops;
    3483             :           // accumulate set of all subscripts in group
    3484         498 :           Pair[SJ].Group |= Pair[SI].Group;
    3485         166 :           Done = false;
    3486             :         }
    3487             :       }
    3488         862 :       if (Done) {
    3489        1444 :         if (Pair[SI].Group.count() == 1) {
    3490         610 :           Separable.set(SI);
    3491             :           ++SeparableSubscriptPairs;
    3492             :         }
    3493             :         else {
    3494         112 :           Coupled.set(SI);
    3495             :           ++CoupledSubscriptPairs;
    3496             :         }
    3497             :       }
    3498             :     }
    3499             :   }
    3500             : 
    3501             :   DEBUG(dbgs() << "    Separable = ");
    3502             :   DEBUG(dumpSmallBitVector(Separable));
    3503             :   DEBUG(dbgs() << "    Coupled = ");
    3504             :   DEBUG(dumpSmallBitVector(Coupled));
    3505             : 
    3506             :   Constraint NewConstraint;
    3507         905 :   NewConstraint.setAny(SE);
    3508             : 
    3509             :   // test separable subscripts
    3510        1765 :   for (unsigned SI : Separable.set_bits()) {
    3511             :     DEBUG(dbgs() << "testing subscript " << SI);
    3512        1720 :     switch (Pair[SI].Classification) {
    3513         250 :     case Subscript::ZIV:
    3514             :       DEBUG(dbgs() << ", ZIV\n");
    3515         750 :       if (testZIV(Pair[SI].Src, Pair[SI].Dst, Result))
    3516          58 :         return nullptr;
    3517             :       break;
    3518         399 :     case Subscript::SIV: {
    3519             :       DEBUG(dbgs() << ", SIV\n");
    3520             :       unsigned Level;
    3521         399 :       const SCEV *SplitIter = nullptr;
    3522        1197 :       if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level, Result, NewConstraint,
    3523             :                   SplitIter))
    3524          24 :         return nullptr;
    3525         375 :       break;
    3526             :     }
    3527          23 :     case Subscript::RDIV:
    3528             :       DEBUG(dbgs() << ", RDIV\n");
    3529          69 :       if (testRDIV(Pair[SI].Src, Pair[SI].Dst, Result))
    3530             :         return nullptr;
    3531             :       break;
    3532         188 :     case Subscript::MIV:
    3533             :       DEBUG(dbgs() << ", MIV\n");
    3534         752 :       if (testMIV(Pair[SI].Src, Pair[SI].Dst, Pair[SI].Loops, Result))
    3535             :         return nullptr;
    3536             :       break;
    3537           0 :     default:
    3538           0 :       llvm_unreachable("subscript has unexpected classification");
    3539             :     }
    3540             :   }
    3541             : 
    3542         847 :   if (Coupled.count()) {
    3543             :     // test coupled subscript groups
    3544             :     DEBUG(dbgs() << "starting on coupled subscripts\n");
    3545             :     DEBUG(dbgs() << "MaxLevels + 1 = " << MaxLevels + 1 << "\n");
    3546         324 :     SmallVector<Constraint, 4> Constraints(MaxLevels + 1);
    3547         445 :     for (unsigned II = 0; II <= MaxLevels; ++II)
    3548         666 :       Constraints[II].setAny(SE);
    3549         224 :     for (unsigned SI : Coupled.set_bits()) {
    3550             :       DEBUG(dbgs() << "testing subscript group " << SI << " { ");
    3551         324 :       SmallBitVector Group(Pair[SI].Group);
    3552         212 :       SmallBitVector Sivs(Pairs);
    3553         212 :       SmallBitVector Mivs(Pairs);
    3554         212 :       SmallBitVector ConstrainedLevels(MaxLevels + 1);
    3555         212 :       SmallVector<Subscript *, 4> PairsInGroup;
    3556         364 :       for (unsigned SJ : Group.set_bits()) {
    3557             :         DEBUG(dbgs() << SJ << " ");
    3558         504 :         if (Pair[SJ].Classification == Subscript::SIV)
    3559         178 :           Sivs.set(SJ);
    3560             :         else
    3561          74 :           Mivs.set(SJ);
    3562         504 :         PairsInGroup.push_back(&Pair[SJ]);
    3563             :       }
    3564         112 :       unifySubscriptType(PairsInGroup);
    3565             :       DEBUG(dbgs() << "}\n");
    3566         259 :       while (Sivs.any()) {
    3567         156 :         bool Changed = false;
    3568         389 :         for (unsigned SJ : Sivs.set_bits()) {
    3569             :           DEBUG(dbgs() << "testing subscript " << SJ << ", SIV\n");
    3570             :           // SJ is an SIV subscript that's part of the current coupled group
    3571             :           unsigned Level;
    3572         233 :           const SCEV *SplitIter = nullptr;
    3573             :           DEBUG(dbgs() << "SIV\n");
    3574         699 :           if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint,
    3575             :                       SplitIter))
    3576           9 :             return nullptr;
    3577         231 :           ConstrainedLevels.set(Level);
    3578         462 :           if (intersectConstraints(&Constraints[Level], &NewConstraint)) {
    3579         360 :             if (Constraints[Level].isEmpty()) {
    3580           7 :               ++DeltaIndependence;
    3581             :               return nullptr;
    3582             :             }
    3583             :             Changed = true;
    3584             :           }
    3585         224 :           Sivs.reset(SJ);
    3586             :         }
    3587         147 :         if (Changed) {
    3588             :           // propagate, possibly creating new SIVs and ZIVs
    3589             :           DEBUG(dbgs() << "    propagating\n");
    3590             :           DEBUG(dbgs() << "\tMivs = ");
    3591             :           DEBUG(dumpSmallBitVector(Mivs));
    3592         219 :           for (unsigned SJ : Mivs.set_bits()) {
    3593             :             // SJ is an MIV subscript that's part of the current coupled group
    3594             :             DEBUG(dbgs() << "\tSJ = " << SJ << "\n");
    3595         288 :             if (propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops,
    3596             :                           Constraints, Result.Consistent)) {
    3597             :               DEBUG(dbgs() << "\t    Changed\n");
    3598          63 :               ++DeltaPropagations;
    3599         189 :               Pair[SJ].Classification =
    3600         315 :                 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()),
    3601         189 :                              Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()),
    3602         126 :                              Pair[SJ].Loops);
    3603         126 :               switch (Pair[SJ].Classification) {
    3604           0 :               case Subscript::ZIV:
    3605             :                 DEBUG(dbgs() << "ZIV\n");
    3606           0 :                 if (testZIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
    3607           0 :                   return nullptr;
    3608           0 :                 Mivs.reset(SJ);
    3609           0 :                 break;
    3610          55 :               case Subscript::SIV:
    3611          55 :                 Sivs.set(SJ);
    3612          55 :                 Mivs.reset(SJ);
    3613          55 :                 break;
    3614             :               case Subscript::RDIV:
    3615             :               case Subscript::MIV:
    3616             :                 break;
    3617           0 :               default:
    3618           0 :                 llvm_unreachable("bad subscript classification");
    3619             :               }
    3620             :             }
    3621             :           }
    3622             :         }
    3623             :       }
    3624             : 
    3625             :       // test & propagate remaining RDIVs
    3626         121 :       for (unsigned SJ : Mivs.set_bits()) {
    3627          36 :         if (Pair[SJ].Classification == Subscript::RDIV) {
    3628             :           DEBUG(dbgs() << "RDIV test\n");
    3629          18 :           if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
    3630           2 :             return nullptr;
    3631             :           // I don't yet understand how to propagate RDIV results
    3632           4 :           Mivs.reset(SJ);
    3633             :         }
    3634             :       }
    3635             : 
    3636             :       // test remaining MIVs
    3637             :       // This code is temporary.
    3638             :       // Better to somehow test all remaining subscripts simultaneously.
    3639         113 :       for (unsigned SJ : Mivs.set_bits()) {
    3640          24 :         if (Pair[SJ].Classification == Subscript::MIV) {
    3641             :           DEBUG(dbgs() << "MIV test\n");
    3642          48 :           if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops, Result))
    3643           1 :             return nullptr;
    3644             :         }
    3645             :         else
    3646           0 :           llvm_unreachable("expected only MIV subscripts at this point");
    3647             :       }
    3648             : 
    3649             :       // update Result.DV from constraint vector
    3650             :       DEBUG(dbgs() << "    updating\n");
    3651         246 :       for (unsigned SJ : ConstrainedLevels.set_bits()) {
    3652         146 :         if (SJ > CommonLevels)
    3653             :           break;
    3654         429 :         updateDirection(Result.DV[SJ - 1], Constraints[SJ]);
    3655         286 :         if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE)
    3656           0 :           return nullptr;
    3657             :       }
    3658             :     }
    3659             :   }
    3660             : 
    3661             :   // Make sure the Scalar flags are set correctly.
    3662        1670 :   SmallBitVector CompleteLoops(MaxLevels + 1);
    3663        1940 :   for (unsigned SI = 0; SI < Pairs; ++SI)
    3664        2210 :     CompleteLoops |= Pair[SI].Loops;
    3665        3467 :   for (unsigned II = 1; II <= CommonLevels; ++II)
    3666        2632 :     if (CompleteLoops[II])
    3667        2116 :       Result.DV[II - 1].Scalar = false;
    3668             : 
    3669         835 :   if (PossiblyLoopIndependent) {
    3670             :     // Make sure the LoopIndependent flag is set correctly.
    3671             :     // All directions must include equal, otherwise no
    3672             :     // loop-independent dependence is possible.
    3673         933 :     for (unsigned II = 1; II <= CommonLevels; ++II) {
    3674         402 :       if (!(Result.getDirection(II) & Dependence::DVEntry::EQ)) {
    3675          68 :         Result.LoopIndependent = false;
    3676          68 :         break;
    3677             :       }
    3678             :     }
    3679             :   }
    3680             :   else {
    3681             :     // On the other hand, if all directions are equal and there's no
    3682             :     // loop-independent dependence possible, then no dependence exists.
    3683             :     bool AllEqual = true;
    3684        1698 :     for (unsigned II = 1; II <= CommonLevels; ++II) {
    3685         704 :       if (Result.getDirection(II) != Dependence::DVEntry::EQ) {
    3686             :         AllEqual = false;
    3687             :         break;
    3688             :       }
    3689             :     }
    3690         570 :     if (AllEqual)
    3691             :       return nullptr;
    3692             :   }
    3693             : 
    3694        1215 :   return make_unique<FullDependence>(std::move(Result));
    3695             : }
    3696             : 
    3697             : 
    3698             : 
    3699             : //===----------------------------------------------------------------------===//
    3700             : // getSplitIteration -
    3701             : // Rather than spend rarely-used space recording the splitting iteration
    3702             : // during the Weak-Crossing SIV test, we re-compute it on demand.
    3703             : // The re-computation is basically a repeat of the entire dependence test,
    3704             : // though simplified since we know that the dependence exists.
    3705             : // It's tedious, since we must go through all propagations, etc.
    3706             : //
    3707             : // Care is required to keep this code up to date with respect to the routine
    3708             : // above, depends().
    3709             : //
    3710             : // Generally, the dependence analyzer will be used to build
    3711             : // a dependence graph for a function (basically a map from instructions
    3712             : // to dependences). Looking for cycles in the graph shows us loops
    3713             : // that cannot be trivially vectorized/parallelized.
    3714             : //
    3715             : // We can try to improve the situation by examining all the dependences
    3716             : // that make up the cycle, looking for ones we can break.
    3717             : // Sometimes, peeling the first or last iteration of a loop will break
    3718             : // dependences, and we've got flags for those possibilities.
    3719             : // Sometimes, splitting a loop at some other iteration will do the trick,
    3720             : // and we've got a flag for that case. Rather than waste the space to
    3721             : // record the exact iteration (since we rarely know), we provide
    3722             : // a method that calculates the iteration. It's a drag that it must work
    3723             : // from scratch, but wonderful in that it's possible.
    3724             : //
    3725             : // Here's an example:
    3726             : //
    3727             : //    for (i = 0; i < 10; i++)
    3728             : //        A[i] = ...
    3729             : //        ... = A[11 - i]
    3730             : //
    3731             : // There's a loop-carried flow dependence from the store to the load,
    3732             : // found by the weak-crossing SIV test. The dependence will have a flag,
    3733             : // indicating that the dependence can be broken by splitting the loop.
    3734             : // Calling getSplitIteration will return 5.
    3735             : // Splitting the loop breaks the dependence, like so:
    3736             : //
    3737             : //    for (i = 0; i <= 5; i++)
    3738             : //        A[i] = ...
    3739             : //        ... = A[11 - i]
    3740             : //    for (i = 6; i < 10; i++)
    3741             : //        A[i] = ...
    3742             : //        ... = A[11 - i]
    3743             : //
    3744             : // breaks the dependence and allows us to vectorize/parallelize
    3745             : // both loops.
    3746          10 : const SCEV *DependenceInfo::getSplitIteration(const Dependence &Dep,
    3747             :                                               unsigned SplitLevel) {
    3748             :   assert(Dep.isSplitable(SplitLevel) &&
    3749             :          "Dep should be splitable at SplitLevel");
    3750          10 :   Instruction *Src = Dep.getSrc();
    3751          10 :   Instruction *Dst = Dep.getDst();
    3752             :   assert(Src->mayReadFromMemory() || Src->mayWriteToMemory());
    3753             :   assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory());
    3754             :   assert(isLoadOrStore(Src));
    3755             :   assert(isLoadOrStore(Dst));
    3756          10 :   Value *SrcPtr = getPointerOperand(Src);
    3757          10 :   Value *DstPtr = getPointerOperand(Dst);
    3758             :   assert(underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), DstPtr,
    3759             :                                 SrcPtr) == MustAlias);
    3760             : 
    3761             :   // establish loop nesting levels
    3762          10 :   establishNestingLevels(Src, Dst);
    3763             : 
    3764          20 :   FullDependence Result(Src, Dst, false, CommonLevels);
    3765             : 
    3766             :   // See if there are GEPs we can use.
    3767          10 :   bool UsefulGEP = false;
    3768          10 :   GEPOperator *SrcGEP = dyn_cast<GEPOperator>(SrcPtr);
    3769          10 :   GEPOperator *DstGEP = dyn_cast<GEPOperator>(DstPtr);
    3770          20 :   if (SrcGEP && DstGEP &&
    3771          20 :       SrcGEP->getPointerOperandType() == DstGEP->getPointerOperandType()) {
    3772          20 :     const SCEV *SrcPtrSCEV = SE->getSCEV(SrcGEP->getPointerOperand());
    3773          20 :     const SCEV *DstPtrSCEV = SE->getSCEV(DstGEP->getPointerOperand());
    3774          40 :     UsefulGEP = isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) &&
    3775          30 :                 isLoopInvariant(DstPtrSCEV, LI->getLoopFor(Dst->getParent())) &&
    3776          30 :                 (SrcGEP->getNumOperands() == DstGEP->getNumOperands());
    3777             :   }
    3778          20 :   unsigned Pairs = UsefulGEP ? SrcGEP->idx_end() - SrcGEP->idx_begin() : 1;
    3779          40 :   SmallVector<Subscript, 4> Pair(Pairs);
    3780          10 :   if (UsefulGEP) {
    3781          10 :     unsigned P = 0;
    3782          35 :     for (GEPOperator::const_op_iterator SrcIdx = SrcGEP->idx_begin(),
    3783          10 :            SrcEnd = SrcGEP->idx_end(),
    3784          10 :            DstIdx = DstGEP->idx_begin();
    3785          35 :          SrcIdx != SrcEnd;
    3786             :          ++SrcIdx, ++DstIdx, ++P) {
    3787          50 :       Pair[P].Src = SE->getSCEV(*SrcIdx);
    3788          50 :       Pair[P].Dst = SE->getSCEV(*DstIdx);
    3789             :     }
    3790             :   }
    3791             :   else {
    3792           0 :     const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
    3793           0 :     const SCEV *DstSCEV = SE->getSCEV(DstPtr);
    3794           0 :     Pair[0].Src = SrcSCEV;
    3795           0 :     Pair[0].Dst = DstSCEV;
    3796             :   }
    3797             : 
    3798          10 :   if (Delinearize && CommonLevels > 1) {
    3799           0 :     if (tryDelinearize(Src, Dst, Pair)) {
    3800             :       DEBUG(dbgs() << "    delinearized GEP\n");
    3801           0 :       Pairs = Pair.size();
    3802             :     }
    3803             :   }
    3804             : 
    3805          35 :   for (unsigned P = 0; P < Pairs; ++P) {
    3806          50 :     Pair[P].Loops.resize(MaxLevels + 1);
    3807          50 :     Pair[P].GroupLoops.resize(MaxLevels + 1);
    3808          50 :     Pair[P].Group.resize(Pairs);
    3809          50 :     removeMatchingExtensions(&Pair[P]);
    3810          75 :     Pair[P].Classification =
    3811         125 :       classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),
    3812          75 :                    Pair[P].Dst, LI->getLoopFor(Dst->getParent()),
    3813          50 :                    Pair[P].Loops);
    3814          75 :     Pair[P].GroupLoops = Pair[P].Loops;
    3815          50 :     Pair[P].Group.set(P);
    3816             :   }
    3817             : 
    3818          20 :   SmallBitVector Separable(Pairs);
    3819          20 :   SmallBitVector Coupled(Pairs);
    3820             : 
    3821             :   // partition subscripts into separable and minimally-coupled groups
    3822          35 :   for (unsigned SI = 0; SI < Pairs; ++SI) {
    3823          50 :     if (Pair[SI].Classification == Subscript::NonLinear) {
    3824             :       // ignore these, but collect loops for later
    3825           0 :       collectCommonLoops(Pair[SI].Src,
    3826           0 :                          LI->getLoopFor(Src->getParent()),
    3827           0 :                          Pair[SI].Loops);
    3828           0 :       collectCommonLoops(Pair[SI].Dst,
    3829           0 :                          LI->getLoopFor(Dst->getParent()),
    3830           0 :                          Pair[SI].Loops);
    3831           0 :       Result.Consistent = false;
    3832             :     }
    3833          50 :     else if (Pair[SI].Classification == Subscript::ZIV)
    3834           0 :       Separable.set(SI);
    3835             :     else {
    3836             :       // SIV, RDIV, or MIV, so check for coupled group
    3837          25 :       bool Done = true;
    3838          63 :       for (unsigned SJ = SI + 1; SJ < Pairs; ++SJ) {
    3839         114 :         SmallBitVector Intersection = Pair[SI].GroupLoops;
    3840          76 :         Intersection &= Pair[SJ].GroupLoops;
    3841          38 :         if (Intersection.any()) {
    3842             :           // accumulate set of all the loops in group
    3843          30 :           Pair[SJ].GroupLoops |= Pair[SI].GroupLoops;
    3844             :           // accumulate set of all subscripts in group
    3845          30 :           Pair[SJ].Group |= Pair[SI].Group;
    3846          10 :           Done = false;
    3847             :         }
    3848             :       }
    3849          25 :       if (Done) {
    3850          34 :         if (Pair[SI].Group.count() == 1)
    3851          11 :           Separable.set(SI);
    3852             :         else
    3853           6 :           Coupled.set(SI);
    3854             :       }
    3855             :     }
    3856             :   }
    3857             : 
    3858             :   Constraint NewConstraint;
    3859          10 :   NewConstraint.setAny(SE);
    3860             : 
    3861             :   // test separable subscripts
    3862          17 :   for (unsigned SI : Separable.set_bits()) {
    3863          14 :     switch (Pair[SI].Classification) {
    3864           7 :     case Subscript::SIV: {
    3865             :       unsigned Level;
    3866           7 :       const SCEV *SplitIter = nullptr;
    3867          21 :       (void) testSIV(Pair[SI].Src, Pair[SI].Dst, Level,
    3868             :                      Result, NewConstraint, SplitIter);
    3869           7 :       if (Level == SplitLevel) {
    3870             :         assert(SplitIter != nullptr);
    3871           4 :         return SplitIter;
    3872             :       }
    3873           3 :       break;
    3874             :     }
    3875             :     case Subscript::ZIV:
    3876             :     case Subscript::RDIV:
    3877             :     case Subscript::MIV:
    3878             :       break;
    3879           0 :     default:
    3880           0 :       llvm_unreachable("subscript has unexpected classification");
    3881             :     }
    3882             :   }
    3883             : 
    3884           6 :   if (Coupled.count()) {
    3885             :     // test coupled subscript groups
    3886          12 :     SmallVector<Constraint, 4> Constraints(MaxLevels + 1);
    3887          20 :     for (unsigned II = 0; II <= MaxLevels; ++II)
    3888          28 :       Constraints[II].setAny(SE);
    3889          12 :     for (unsigned SI : Coupled.set_bits()) {
    3890          12 :       SmallBitVector Group(Pair[SI].Group);
    3891           6 :       SmallBitVector Sivs(Pairs);
    3892           6 :       SmallBitVector Mivs(Pairs);
    3893           6 :       SmallBitVector ConstrainedLevels(MaxLevels + 1);
    3894          20 :       for (unsigned SJ : Group.set_bits()) {
    3895          28 :         if (Pair[SJ].Classification == Subscript::SIV)
    3896          12 :           Sivs.set(SJ);
    3897             :         else
    3898           2 :           Mivs.set(SJ);
    3899             :       }
    3900           6 :       while (Sivs.any()) {
    3901           6 :         bool Changed = false;
    3902          17 :         for (unsigned SJ : Sivs.set_bits()) {
    3903             :           // SJ is an SIV subscript that's part of the current coupled group
    3904             :           unsigned Level;
    3905          11 :           const SCEV *SplitIter = nullptr;
    3906          33 :           (void) testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level,
    3907             :                          Result, NewConstraint, SplitIter);
    3908          11 :           if (Level == SplitLevel && SplitIter)
    3909           6 :             return SplitIter;
    3910           5 :           ConstrainedLevels.set(Level);
    3911          10 :           if (intersectConstraints(&Constraints[Level], &NewConstraint))
    3912           5 :             Changed = true;
    3913           5 :           Sivs.reset(SJ);
    3914             :         }
    3915           0 :         if (Changed) {
    3916             :           // propagate, possibly creating new SIVs and ZIVs
    3917           0 :           for (unsigned SJ : Mivs.set_bits()) {
    3918             :             // SJ is an MIV subscript that's part of the current coupled group
    3919           0 :             if (propagate(Pair[SJ].Src, Pair[SJ].Dst,
    3920           0 :                           Pair[SJ].Loops, Constraints, Result.Consistent)) {
    3921           0 :               Pair[SJ].Classification =
    3922           0 :                 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()),
    3923           0 :                              Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()),
    3924           0 :                              Pair[SJ].Loops);
    3925           0 :               switch (Pair[SJ].Classification) {
    3926           0 :               case Subscript::ZIV:
    3927           0 :                 Mivs.reset(SJ);
    3928           0 :                 break;
    3929           0 :               case Subscript::SIV:
    3930           0 :                 Sivs.set(SJ);
    3931           0 :                 Mivs.reset(SJ);
    3932           0 :                 break;
    3933             :               case Subscript::RDIV:
    3934             :               case Subscript::MIV:
    3935             :                 break;
    3936           0 :               default:
    3937           0 :                 llvm_unreachable("bad subscript classification");
    3938             :               }
    3939             :             }
    3940             :           }
    3941             :         }
    3942             :       }
    3943             :     }
    3944             :   }
    3945           0 :   llvm_unreachable("somehow reached end of routine");
    3946             :   return nullptr;
    3947      216918 : }

Generated by: LCOV version 1.13