LLVM  mainline
DependenceAnalysis.cpp
Go to the documentation of this file.
00001 //===-- DependenceAnalysis.cpp - DA Implementation --------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // DependenceAnalysis is an LLVM pass that analyses dependences between memory
00011 // accesses. Currently, it is an (incomplete) implementation of the approach
00012 // described in
00013 //
00014 //            Practical Dependence Testing
00015 //            Goff, Kennedy, Tseng
00016 //            PLDI 1991
00017 //
00018 // There's a single entry point that analyzes the dependence between a pair
00019 // of memory references in a function, returning either NULL, for no dependence,
00020 // or a more-or-less detailed description of the dependence between them.
00021 //
00022 // Currently, the implementation cannot propagate constraints between
00023 // coupled RDIV subscripts and lacks a multi-subscript MIV test.
00024 // Both of these are conservative weaknesses;
00025 // that is, not a source of correctness problems.
00026 //
00027 // The implementation depends on the GEP instruction to differentiate
00028 // subscripts. Since Clang linearizes some array subscripts, the dependence
00029 // analysis is using SCEV->delinearize to recover the representation of multiple
00030 // subscripts, and thus avoid the more expensive and less precise MIV tests. The
00031 // delinearization is controlled by the flag -da-delinearize.
00032 //
00033 // We should pay some careful attention to the possibility of integer overflow
00034 // in the implementation of the various tests. This could happen with Add,
00035 // Subtract, or Multiply, with both APInt's and SCEV's.
00036 //
00037 // Some non-linear subscript pairs can be handled by the GCD test
00038 // (and perhaps other tests).
00039 // Should explore how often these things occur.
00040 //
00041 // Finally, it seems like certain test cases expose weaknesses in the SCEV
00042 // simplification, especially in the handling of sign and zero extensions.
00043 // It could be useful to spend time exploring these.
00044 //
00045 // Please note that this is work in progress and the interface is subject to
00046 // change.
00047 //
00048 //===----------------------------------------------------------------------===//
00049 //                                                                            //
00050 //                   In memory of Ken Kennedy, 1945 - 2007                    //
00051 //                                                                            //
00052 //===----------------------------------------------------------------------===//
00053 
00054 #include "llvm/Analysis/DependenceAnalysis.h"
00055 #include "llvm/ADT/STLExtras.h"
00056 #include "llvm/ADT/Statistic.h"
00057 #include "llvm/Analysis/AliasAnalysis.h"
00058 #include "llvm/Analysis/LoopInfo.h"
00059 #include "llvm/Analysis/ScalarEvolution.h"
00060 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
00061 #include "llvm/Analysis/ValueTracking.h"
00062 #include "llvm/IR/InstIterator.h"
00063 #include "llvm/IR/Module.h"
00064 #include "llvm/IR/Operator.h"
00065 #include "llvm/Support/CommandLine.h"
00066 #include "llvm/Support/Debug.h"
00067 #include "llvm/Support/ErrorHandling.h"
00068 #include "llvm/Support/raw_ostream.h"
00069 
00070 using namespace llvm;
00071 
00072 #define DEBUG_TYPE "da"
00073 
00074 //===----------------------------------------------------------------------===//
00075 // statistics
00076 
00077 STATISTIC(TotalArrayPairs, "Array pairs tested");
00078 STATISTIC(SeparableSubscriptPairs, "Separable subscript pairs");
00079 STATISTIC(CoupledSubscriptPairs, "Coupled subscript pairs");
00080 STATISTIC(NonlinearSubscriptPairs, "Nonlinear subscript pairs");
00081 STATISTIC(ZIVapplications, "ZIV applications");
00082 STATISTIC(ZIVindependence, "ZIV independence");
00083 STATISTIC(StrongSIVapplications, "Strong SIV applications");
00084 STATISTIC(StrongSIVsuccesses, "Strong SIV successes");
00085 STATISTIC(StrongSIVindependence, "Strong SIV independence");
00086 STATISTIC(WeakCrossingSIVapplications, "Weak-Crossing SIV applications");
00087 STATISTIC(WeakCrossingSIVsuccesses, "Weak-Crossing SIV successes");
00088 STATISTIC(WeakCrossingSIVindependence, "Weak-Crossing SIV independence");
00089 STATISTIC(ExactSIVapplications, "Exact SIV applications");
00090 STATISTIC(ExactSIVsuccesses, "Exact SIV successes");
00091 STATISTIC(ExactSIVindependence, "Exact SIV independence");
00092 STATISTIC(WeakZeroSIVapplications, "Weak-Zero SIV applications");
00093 STATISTIC(WeakZeroSIVsuccesses, "Weak-Zero SIV successes");
00094 STATISTIC(WeakZeroSIVindependence, "Weak-Zero SIV independence");
00095 STATISTIC(ExactRDIVapplications, "Exact RDIV applications");
00096 STATISTIC(ExactRDIVindependence, "Exact RDIV independence");
00097 STATISTIC(SymbolicRDIVapplications, "Symbolic RDIV applications");
00098 STATISTIC(SymbolicRDIVindependence, "Symbolic RDIV independence");
00099 STATISTIC(DeltaApplications, "Delta applications");
00100 STATISTIC(DeltaSuccesses, "Delta successes");
00101 STATISTIC(DeltaIndependence, "Delta independence");
00102 STATISTIC(DeltaPropagations, "Delta propagations");
00103 STATISTIC(GCDapplications, "GCD applications");
00104 STATISTIC(GCDsuccesses, "GCD successes");
00105 STATISTIC(GCDindependence, "GCD independence");
00106 STATISTIC(BanerjeeApplications, "Banerjee applications");
00107 STATISTIC(BanerjeeIndependence, "Banerjee independence");
00108 STATISTIC(BanerjeeSuccesses, "Banerjee successes");
00109 
00110 static cl::opt<bool>
00111 Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore,
00112             cl::desc("Try to delinearize array references."));
00113 
00114 //===----------------------------------------------------------------------===//
00115 // basics
00116 
00117 INITIALIZE_PASS_BEGIN(DependenceAnalysis, "da",
00118                       "Dependence Analysis", true, true)
00119 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
00120 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
00121 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
00122 INITIALIZE_PASS_END(DependenceAnalysis, "da",
00123                     "Dependence Analysis", true, true)
00124 
00125 char DependenceAnalysis::ID = 0;
00126 
00127 
00128 FunctionPass *llvm::createDependenceAnalysisPass() {
00129   return new DependenceAnalysis();
00130 }
00131 
00132 
00133 bool DependenceAnalysis::runOnFunction(Function &F) {
00134   this->F = &F;
00135   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
00136   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
00137   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
00138   return false;
00139 }
00140 
00141 
00142 void DependenceAnalysis::releaseMemory() {
00143 }
00144 
00145 
00146 void DependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
00147   AU.setPreservesAll();
00148   AU.addRequiredTransitive<AAResultsWrapperPass>();
00149   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
00150   AU.addRequiredTransitive<LoopInfoWrapperPass>();
00151 }
00152 
00153 
00154 // Used to test the dependence analyzer.
00155 // Looks through the function, noting loads and stores.
00156 // Calls depends() on every possible pair and prints out the result.
00157 // Ignores all other instructions.
00158 static
00159 void dumpExampleDependence(raw_ostream &OS, Function *F,
00160                            DependenceAnalysis *DA) {
00161   for (inst_iterator SrcI = inst_begin(F), SrcE = inst_end(F);
00162        SrcI != SrcE; ++SrcI) {
00163     if (isa<StoreInst>(*SrcI) || isa<LoadInst>(*SrcI)) {
00164       for (inst_iterator DstI = SrcI, DstE = inst_end(F);
00165            DstI != DstE; ++DstI) {
00166         if (isa<StoreInst>(*DstI) || isa<LoadInst>(*DstI)) {
00167           OS << "da analyze - ";
00168           if (auto D = DA->depends(&*SrcI, &*DstI, true)) {
00169             D->dump(OS);
00170             for (unsigned Level = 1; Level <= D->getLevels(); Level++) {
00171               if (D->isSplitable(Level)) {
00172                 OS << "da analyze - split level = " << Level;
00173                 OS << ", iteration = " << *DA->getSplitIteration(*D, Level);
00174                 OS << "!\n";
00175               }
00176             }
00177           }
00178           else
00179             OS << "none!\n";
00180         }
00181       }
00182     }
00183   }
00184 }
00185 
00186 
00187 void DependenceAnalysis::print(raw_ostream &OS, const Module*) const {
00188   dumpExampleDependence(OS, F, const_cast<DependenceAnalysis *>(this));
00189 }
00190 
00191 //===----------------------------------------------------------------------===//
00192 // Dependence methods
00193 
00194 // Returns true if this is an input dependence.
00195 bool Dependence::isInput() const {
00196   return Src->mayReadFromMemory() && Dst->mayReadFromMemory();
00197 }
00198 
00199 
00200 // Returns true if this is an output dependence.
00201 bool Dependence::isOutput() const {
00202   return Src->mayWriteToMemory() && Dst->mayWriteToMemory();
00203 }
00204 
00205 
00206 // Returns true if this is an flow (aka true)  dependence.
00207 bool Dependence::isFlow() const {
00208   return Src->mayWriteToMemory() && Dst->mayReadFromMemory();
00209 }
00210 
00211 
00212 // Returns true if this is an anti dependence.
00213 bool Dependence::isAnti() const {
00214   return Src->mayReadFromMemory() && Dst->mayWriteToMemory();
00215 }
00216 
00217 
00218 // Returns true if a particular level is scalar; that is,
00219 // if no subscript in the source or destination mention the induction
00220 // variable associated with the loop at this level.
00221 // Leave this out of line, so it will serve as a virtual method anchor
00222 bool Dependence::isScalar(unsigned level) const {
00223   return false;
00224 }
00225 
00226 
00227 //===----------------------------------------------------------------------===//
00228 // FullDependence methods
00229 
00230 FullDependence::FullDependence(Instruction *Source, Instruction *Destination,
00231                                bool PossiblyLoopIndependent,
00232                                unsigned CommonLevels)
00233     : Dependence(Source, Destination), Levels(CommonLevels),
00234       LoopIndependent(PossiblyLoopIndependent) {
00235   Consistent = true;
00236   if (CommonLevels)
00237     DV = make_unique<DVEntry[]>(CommonLevels);
00238 }
00239 
00240 // The rest are simple getters that hide the implementation.
00241 
00242 // getDirection - Returns the direction associated with a particular level.
00243 unsigned FullDependence::getDirection(unsigned Level) const {
00244   assert(0 < Level && Level <= Levels && "Level out of range");
00245   return DV[Level - 1].Direction;
00246 }
00247 
00248 
00249 // Returns the distance (or NULL) associated with a particular level.
00250 const SCEV *FullDependence::getDistance(unsigned Level) const {
00251   assert(0 < Level && Level <= Levels && "Level out of range");
00252   return DV[Level - 1].Distance;
00253 }
00254 
00255 
00256 // Returns true if a particular level is scalar; that is,
00257 // if no subscript in the source or destination mention the induction
00258 // variable associated with the loop at this level.
00259 bool FullDependence::isScalar(unsigned Level) const {
00260   assert(0 < Level && Level <= Levels && "Level out of range");
00261   return DV[Level - 1].Scalar;
00262 }
00263 
00264 
00265 // Returns true if peeling the first iteration from this loop
00266 // will break this dependence.
00267 bool FullDependence::isPeelFirst(unsigned Level) const {
00268   assert(0 < Level && Level <= Levels && "Level out of range");
00269   return DV[Level - 1].PeelFirst;
00270 }
00271 
00272 
00273 // Returns true if peeling the last iteration from this loop
00274 // will break this dependence.
00275 bool FullDependence::isPeelLast(unsigned Level) const {
00276   assert(0 < Level && Level <= Levels && "Level out of range");
00277   return DV[Level - 1].PeelLast;
00278 }
00279 
00280 
00281 // Returns true if splitting this loop will break the dependence.
00282 bool FullDependence::isSplitable(unsigned Level) const {
00283   assert(0 < Level && Level <= Levels && "Level out of range");
00284   return DV[Level - 1].Splitable;
00285 }
00286 
00287 
00288 //===----------------------------------------------------------------------===//
00289 // DependenceAnalysis::Constraint methods
00290 
00291 // If constraint is a point <X, Y>, returns X.
00292 // Otherwise assert.
00293 const SCEV *DependenceAnalysis::Constraint::getX() const {
00294   assert(Kind == Point && "Kind should be Point");
00295   return A;
00296 }
00297 
00298 
00299 // If constraint is a point <X, Y>, returns Y.
00300 // Otherwise assert.
00301 const SCEV *DependenceAnalysis::Constraint::getY() const {
00302   assert(Kind == Point && "Kind should be Point");
00303   return B;
00304 }
00305 
00306 
00307 // If constraint is a line AX + BY = C, returns A.
00308 // Otherwise assert.
00309 const SCEV *DependenceAnalysis::Constraint::getA() const {
00310   assert((Kind == Line || Kind == Distance) &&
00311          "Kind should be Line (or Distance)");
00312   return A;
00313 }
00314 
00315 
00316 // If constraint is a line AX + BY = C, returns B.
00317 // Otherwise assert.
00318 const SCEV *DependenceAnalysis::Constraint::getB() const {
00319   assert((Kind == Line || Kind == Distance) &&
00320          "Kind should be Line (or Distance)");
00321   return B;
00322 }
00323 
00324 
00325 // If constraint is a line AX + BY = C, returns C.
00326 // Otherwise assert.
00327 const SCEV *DependenceAnalysis::Constraint::getC() const {
00328   assert((Kind == Line || Kind == Distance) &&
00329          "Kind should be Line (or Distance)");
00330   return C;
00331 }
00332 
00333 
00334 // If constraint is a distance, returns D.
00335 // Otherwise assert.
00336 const SCEV *DependenceAnalysis::Constraint::getD() const {
00337   assert(Kind == Distance && "Kind should be Distance");
00338   return SE->getNegativeSCEV(C);
00339 }
00340 
00341 
00342 // Returns the loop associated with this constraint.
00343 const Loop *DependenceAnalysis::Constraint::getAssociatedLoop() const {
00344   assert((Kind == Distance || Kind == Line || Kind == Point) &&
00345          "Kind should be Distance, Line, or Point");
00346   return AssociatedLoop;
00347 }
00348 
00349 
00350 void DependenceAnalysis::Constraint::setPoint(const SCEV *X,
00351                                               const SCEV *Y,
00352                                               const Loop *CurLoop) {
00353   Kind = Point;
00354   A = X;
00355   B = Y;
00356   AssociatedLoop = CurLoop;
00357 }
00358 
00359 
00360 void DependenceAnalysis::Constraint::setLine(const SCEV *AA,
00361                                              const SCEV *BB,
00362                                              const SCEV *CC,
00363                                              const Loop *CurLoop) {
00364   Kind = Line;
00365   A = AA;
00366   B = BB;
00367   C = CC;
00368   AssociatedLoop = CurLoop;
00369 }
00370 
00371 
00372 void DependenceAnalysis::Constraint::setDistance(const SCEV *D,
00373                                                  const Loop *CurLoop) {
00374   Kind = Distance;
00375   A = SE->getOne(D->getType());
00376   B = SE->getNegativeSCEV(A);
00377   C = SE->getNegativeSCEV(D);
00378   AssociatedLoop = CurLoop;
00379 }
00380 
00381 
00382 void DependenceAnalysis::Constraint::setEmpty() {
00383   Kind = Empty;
00384 }
00385 
00386 
00387 void DependenceAnalysis::Constraint::setAny(ScalarEvolution *NewSE) {
00388   SE = NewSE;
00389   Kind = Any;
00390 }
00391 
00392 
00393 // For debugging purposes. Dumps the constraint out to OS.
00394 void DependenceAnalysis::Constraint::dump(raw_ostream &OS) const {
00395   if (isEmpty())
00396     OS << " Empty\n";
00397   else if (isAny())
00398     OS << " Any\n";
00399   else if (isPoint())
00400     OS << " Point is <" << *getX() << ", " << *getY() << ">\n";
00401   else if (isDistance())
00402     OS << " Distance is " << *getD() <<
00403       " (" << *getA() << "*X + " << *getB() << "*Y = " << *getC() << ")\n";
00404   else if (isLine())
00405     OS << " Line is " << *getA() << "*X + " <<
00406       *getB() << "*Y = " << *getC() << "\n";
00407   else
00408     llvm_unreachable("unknown constraint type in Constraint::dump");
00409 }
00410 
00411 
00412 // Updates X with the intersection
00413 // of the Constraints X and Y. Returns true if X has changed.
00414 // Corresponds to Figure 4 from the paper
00415 //
00416 //            Practical Dependence Testing
00417 //            Goff, Kennedy, Tseng
00418 //            PLDI 1991
00419 bool DependenceAnalysis::intersectConstraints(Constraint *X,
00420                                               const Constraint *Y) {
00421   ++DeltaApplications;
00422   DEBUG(dbgs() << "\tintersect constraints\n");
00423   DEBUG(dbgs() << "\t    X ="; X->dump(dbgs()));
00424   DEBUG(dbgs() << "\t    Y ="; Y->dump(dbgs()));
00425   assert(!Y->isPoint() && "Y must not be a Point");
00426   if (X->isAny()) {
00427     if (Y->isAny())
00428       return false;
00429     *X = *Y;
00430     return true;
00431   }
00432   if (X->isEmpty())
00433     return false;
00434   if (Y->isEmpty()) {
00435     X->setEmpty();
00436     return true;
00437   }
00438 
00439   if (X->isDistance() && Y->isDistance()) {
00440     DEBUG(dbgs() << "\t    intersect 2 distances\n");
00441     if (isKnownPredicate(CmpInst::ICMP_EQ, X->getD(), Y->getD()))
00442       return false;
00443     if (isKnownPredicate(CmpInst::ICMP_NE, X->getD(), Y->getD())) {
00444       X->setEmpty();
00445       ++DeltaSuccesses;
00446       return true;
00447     }
00448     // Hmmm, interesting situation.
00449     // I guess if either is constant, keep it and ignore the other.
00450     if (isa<SCEVConstant>(Y->getD())) {
00451       *X = *Y;
00452       return true;
00453     }
00454     return false;
00455   }
00456 
00457   // At this point, the pseudo-code in Figure 4 of the paper
00458   // checks if (X->isPoint() && Y->isPoint()).
00459   // This case can't occur in our implementation,
00460   // since a Point can only arise as the result of intersecting
00461   // two Line constraints, and the right-hand value, Y, is never
00462   // the result of an intersection.
00463   assert(!(X->isPoint() && Y->isPoint()) &&
00464          "We shouldn't ever see X->isPoint() && Y->isPoint()");
00465 
00466   if (X->isLine() && Y->isLine()) {
00467     DEBUG(dbgs() << "\t    intersect 2 lines\n");
00468     const SCEV *Prod1 = SE->getMulExpr(X->getA(), Y->getB());
00469     const SCEV *Prod2 = SE->getMulExpr(X->getB(), Y->getA());
00470     if (isKnownPredicate(CmpInst::ICMP_EQ, Prod1, Prod2)) {
00471       // slopes are equal, so lines are parallel
00472       DEBUG(dbgs() << "\t\tsame slope\n");
00473       Prod1 = SE->getMulExpr(X->getC(), Y->getB());
00474       Prod2 = SE->getMulExpr(X->getB(), Y->getC());
00475       if (isKnownPredicate(CmpInst::ICMP_EQ, Prod1, Prod2))
00476         return false;
00477       if (isKnownPredicate(CmpInst::ICMP_NE, Prod1, Prod2)) {
00478         X->setEmpty();
00479         ++DeltaSuccesses;
00480         return true;
00481       }
00482       return false;
00483     }
00484     if (isKnownPredicate(CmpInst::ICMP_NE, Prod1, Prod2)) {
00485       // slopes differ, so lines intersect
00486       DEBUG(dbgs() << "\t\tdifferent slopes\n");
00487       const SCEV *C1B2 = SE->getMulExpr(X->getC(), Y->getB());
00488       const SCEV *C1A2 = SE->getMulExpr(X->getC(), Y->getA());
00489       const SCEV *C2B1 = SE->getMulExpr(Y->getC(), X->getB());
00490       const SCEV *C2A1 = SE->getMulExpr(Y->getC(), X->getA());
00491       const SCEV *A1B2 = SE->getMulExpr(X->getA(), Y->getB());
00492       const SCEV *A2B1 = SE->getMulExpr(Y->getA(), X->getB());
00493       const SCEVConstant *C1A2_C2A1 =
00494         dyn_cast<SCEVConstant>(SE->getMinusSCEV(C1A2, C2A1));
00495       const SCEVConstant *C1B2_C2B1 =
00496         dyn_cast<SCEVConstant>(SE->getMinusSCEV(C1B2, C2B1));
00497       const SCEVConstant *A1B2_A2B1 =
00498         dyn_cast<SCEVConstant>(SE->getMinusSCEV(A1B2, A2B1));
00499       const SCEVConstant *A2B1_A1B2 =
00500         dyn_cast<SCEVConstant>(SE->getMinusSCEV(A2B1, A1B2));
00501       if (!C1B2_C2B1 || !C1A2_C2A1 ||
00502           !A1B2_A2B1 || !A2B1_A1B2)
00503         return false;
00504       APInt Xtop = C1B2_C2B1->getAPInt();
00505       APInt Xbot = A1B2_A2B1->getAPInt();
00506       APInt Ytop = C1A2_C2A1->getAPInt();
00507       APInt Ybot = A2B1_A1B2->getAPInt();
00508       DEBUG(dbgs() << "\t\tXtop = " << Xtop << "\n");
00509       DEBUG(dbgs() << "\t\tXbot = " << Xbot << "\n");
00510       DEBUG(dbgs() << "\t\tYtop = " << Ytop << "\n");
00511       DEBUG(dbgs() << "\t\tYbot = " << Ybot << "\n");
00512       APInt Xq = Xtop; // these need to be initialized, even
00513       APInt Xr = Xtop; // though they're just going to be overwritten
00514       APInt::sdivrem(Xtop, Xbot, Xq, Xr);
00515       APInt Yq = Ytop;
00516       APInt Yr = Ytop;
00517       APInt::sdivrem(Ytop, Ybot, Yq, Yr);
00518       if (Xr != 0 || Yr != 0) {
00519         X->setEmpty();
00520         ++DeltaSuccesses;
00521         return true;
00522       }
00523       DEBUG(dbgs() << "\t\tX = " << Xq << ", Y = " << Yq << "\n");
00524       if (Xq.slt(0) || Yq.slt(0)) {
00525         X->setEmpty();
00526         ++DeltaSuccesses;
00527         return true;
00528       }
00529       if (const SCEVConstant *CUB =
00530           collectConstantUpperBound(X->getAssociatedLoop(), Prod1->getType())) {
00531         APInt UpperBound = CUB->getAPInt();
00532         DEBUG(dbgs() << "\t\tupper bound = " << UpperBound << "\n");
00533         if (Xq.sgt(UpperBound) || Yq.sgt(UpperBound)) {
00534           X->setEmpty();
00535           ++DeltaSuccesses;
00536           return true;
00537         }
00538       }
00539       X->setPoint(SE->getConstant(Xq),
00540                   SE->getConstant(Yq),
00541                   X->getAssociatedLoop());
00542       ++DeltaSuccesses;
00543       return true;
00544     }
00545     return false;
00546   }
00547 
00548   // if (X->isLine() && Y->isPoint()) This case can't occur.
00549   assert(!(X->isLine() && Y->isPoint()) && "This case should never occur");
00550 
00551   if (X->isPoint() && Y->isLine()) {
00552     DEBUG(dbgs() << "\t    intersect Point and Line\n");
00553     const SCEV *A1X1 = SE->getMulExpr(Y->getA(), X->getX());
00554     const SCEV *B1Y1 = SE->getMulExpr(Y->getB(), X->getY());
00555     const SCEV *Sum = SE->getAddExpr(A1X1, B1Y1);
00556     if (isKnownPredicate(CmpInst::ICMP_EQ, Sum, Y->getC()))
00557       return false;
00558     if (isKnownPredicate(CmpInst::ICMP_NE, Sum, Y->getC())) {
00559       X->setEmpty();
00560       ++DeltaSuccesses;
00561       return true;
00562     }
00563     return false;
00564   }
00565 
00566   llvm_unreachable("shouldn't reach the end of Constraint intersection");
00567   return false;
00568 }
00569 
00570 
00571 //===----------------------------------------------------------------------===//
00572 // DependenceAnalysis methods
00573 
00574 // For debugging purposes. Dumps a dependence to OS.
00575 void Dependence::dump(raw_ostream &OS) const {
00576   bool Splitable = false;
00577   if (isConfused())
00578     OS << "confused";
00579   else {
00580     if (isConsistent())
00581       OS << "consistent ";
00582     if (isFlow())
00583       OS << "flow";
00584     else if (isOutput())
00585       OS << "output";
00586     else if (isAnti())
00587       OS << "anti";
00588     else if (isInput())
00589       OS << "input";
00590     unsigned Levels = getLevels();
00591     OS << " [";
00592     for (unsigned II = 1; II <= Levels; ++II) {
00593       if (isSplitable(II))
00594         Splitable = true;
00595       if (isPeelFirst(II))
00596         OS << 'p';
00597       const SCEV *Distance = getDistance(II);
00598       if (Distance)
00599         OS << *Distance;
00600       else if (isScalar(II))
00601         OS << "S";
00602       else {
00603         unsigned Direction = getDirection(II);
00604         if (Direction == DVEntry::ALL)
00605           OS << "*";
00606         else {
00607           if (Direction & DVEntry::LT)
00608             OS << "<";
00609           if (Direction & DVEntry::EQ)
00610             OS << "=";
00611           if (Direction & DVEntry::GT)
00612             OS << ">";
00613         }
00614       }
00615       if (isPeelLast(II))
00616         OS << 'p';
00617       if (II < Levels)
00618         OS << " ";
00619     }
00620     if (isLoopIndependent())
00621       OS << "|<";
00622     OS << "]";
00623     if (Splitable)
00624       OS << " splitable";
00625   }
00626   OS << "!\n";
00627 }
00628 
00629 static AliasResult underlyingObjectsAlias(AliasAnalysis *AA,
00630                                           const DataLayout &DL, const Value *A,
00631                                           const Value *B) {
00632   const Value *AObj = GetUnderlyingObject(A, DL);
00633   const Value *BObj = GetUnderlyingObject(B, DL);
00634   return AA->alias(AObj, DL.getTypeStoreSize(AObj->getType()),
00635                    BObj, DL.getTypeStoreSize(BObj->getType()));
00636 }
00637 
00638 
00639 // Returns true if the load or store can be analyzed. Atomic and volatile
00640 // operations have properties which this analysis does not understand.
00641 static
00642 bool isLoadOrStore(const Instruction *I) {
00643   if (const LoadInst *LI = dyn_cast<LoadInst>(I))
00644     return LI->isUnordered();
00645   else if (const StoreInst *SI = dyn_cast<StoreInst>(I))
00646     return SI->isUnordered();
00647   return false;
00648 }
00649 
00650 
00651 static
00652 Value *getPointerOperand(Instruction *I) {
00653   if (LoadInst *LI = dyn_cast<LoadInst>(I))
00654     return LI->getPointerOperand();
00655   if (StoreInst *SI = dyn_cast<StoreInst>(I))
00656     return SI->getPointerOperand();
00657   llvm_unreachable("Value is not load or store instruction");
00658   return nullptr;
00659 }
00660 
00661 
00662 // Examines the loop nesting of the Src and Dst
00663 // instructions and establishes their shared loops. Sets the variables
00664 // CommonLevels, SrcLevels, and MaxLevels.
00665 // The source and destination instructions needn't be contained in the same
00666 // loop. The routine establishNestingLevels finds the level of most deeply
00667 // nested loop that contains them both, CommonLevels. An instruction that's
00668 // not contained in a loop is at level = 0. MaxLevels is equal to the level
00669 // of the source plus the level of the destination, minus CommonLevels.
00670 // This lets us allocate vectors MaxLevels in length, with room for every
00671 // distinct loop referenced in both the source and destination subscripts.
00672 // The variable SrcLevels is the nesting depth of the source instruction.
00673 // It's used to help calculate distinct loops referenced by the destination.
00674 // Here's the map from loops to levels:
00675 //            0 - unused
00676 //            1 - outermost common loop
00677 //          ... - other common loops
00678 // CommonLevels - innermost common loop
00679 //          ... - loops containing Src but not Dst
00680 //    SrcLevels - innermost loop containing Src but not Dst
00681 //          ... - loops containing Dst but not Src
00682 //    MaxLevels - innermost loops containing Dst but not Src
00683 // Consider the follow code fragment:
00684 //   for (a = ...) {
00685 //     for (b = ...) {
00686 //       for (c = ...) {
00687 //         for (d = ...) {
00688 //           A[] = ...;
00689 //         }
00690 //       }
00691 //       for (e = ...) {
00692 //         for (f = ...) {
00693 //           for (g = ...) {
00694 //             ... = A[];
00695 //           }
00696 //         }
00697 //       }
00698 //     }
00699 //   }
00700 // If we're looking at the possibility of a dependence between the store
00701 // to A (the Src) and the load from A (the Dst), we'll note that they
00702 // have 2 loops in common, so CommonLevels will equal 2 and the direction
00703 // vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7.
00704 // A map from loop names to loop numbers would look like
00705 //     a - 1
00706 //     b - 2 = CommonLevels
00707 //     c - 3
00708 //     d - 4 = SrcLevels
00709 //     e - 5
00710 //     f - 6
00711 //     g - 7 = MaxLevels
00712 void DependenceAnalysis::establishNestingLevels(const Instruction *Src,
00713                                                 const Instruction *Dst) {
00714   const BasicBlock *SrcBlock = Src->getParent();
00715   const BasicBlock *DstBlock = Dst->getParent();
00716   unsigned SrcLevel = LI->getLoopDepth(SrcBlock);
00717   unsigned DstLevel = LI->getLoopDepth(DstBlock);
00718   const Loop *SrcLoop = LI->getLoopFor(SrcBlock);
00719   const Loop *DstLoop = LI->getLoopFor(DstBlock);
00720   SrcLevels = SrcLevel;
00721   MaxLevels = SrcLevel + DstLevel;
00722   while (SrcLevel > DstLevel) {
00723     SrcLoop = SrcLoop->getParentLoop();
00724     SrcLevel--;
00725   }
00726   while (DstLevel > SrcLevel) {
00727     DstLoop = DstLoop->getParentLoop();
00728     DstLevel--;
00729   }
00730   while (SrcLoop != DstLoop) {
00731     SrcLoop = SrcLoop->getParentLoop();
00732     DstLoop = DstLoop->getParentLoop();
00733     SrcLevel--;
00734   }
00735   CommonLevels = SrcLevel;
00736   MaxLevels -= CommonLevels;
00737 }
00738 
00739 
00740 // Given one of the loops containing the source, return
00741 // its level index in our numbering scheme.
00742 unsigned DependenceAnalysis::mapSrcLoop(const Loop *SrcLoop) const {
00743   return SrcLoop->getLoopDepth();
00744 }
00745 
00746 
00747 // Given one of the loops containing the destination,
00748 // return its level index in our numbering scheme.
00749 unsigned DependenceAnalysis::mapDstLoop(const Loop *DstLoop) const {
00750   unsigned D = DstLoop->getLoopDepth();
00751   if (D > CommonLevels)
00752     return D - CommonLevels + SrcLevels;
00753   else
00754     return D;
00755 }
00756 
00757 
00758 // Returns true if Expression is loop invariant in LoopNest.
00759 bool DependenceAnalysis::isLoopInvariant(const SCEV *Expression,
00760                                          const Loop *LoopNest) const {
00761   if (!LoopNest)
00762     return true;
00763   return SE->isLoopInvariant(Expression, LoopNest) &&
00764     isLoopInvariant(Expression, LoopNest->getParentLoop());
00765 }
00766 
00767 
00768 
00769 // Finds the set of loops from the LoopNest that
00770 // have a level <= CommonLevels and are referred to by the SCEV Expression.
00771 void DependenceAnalysis::collectCommonLoops(const SCEV *Expression,
00772                                             const Loop *LoopNest,
00773                                             SmallBitVector &Loops) const {
00774   while (LoopNest) {
00775     unsigned Level = LoopNest->getLoopDepth();
00776     if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest))
00777       Loops.set(Level);
00778     LoopNest = LoopNest->getParentLoop();
00779   }
00780 }
00781 
00782 void DependenceAnalysis::unifySubscriptType(ArrayRef<Subscript *> Pairs) {
00783 
00784   unsigned widestWidthSeen = 0;
00785   Type *widestType;
00786 
00787   // Go through each pair and find the widest bit to which we need
00788   // to extend all of them.
00789   for (unsigned i = 0; i < Pairs.size(); i++) {
00790     const SCEV *Src = Pairs[i]->Src;
00791     const SCEV *Dst = Pairs[i]->Dst;
00792     IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
00793     IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
00794     if (SrcTy == nullptr || DstTy == nullptr) {
00795       assert(SrcTy == DstTy && "This function only unify integer types and "
00796              "expect Src and Dst share the same type "
00797              "otherwise.");
00798       continue;
00799     }
00800     if (SrcTy->getBitWidth() > widestWidthSeen) {
00801       widestWidthSeen = SrcTy->getBitWidth();
00802       widestType = SrcTy;
00803     }
00804     if (DstTy->getBitWidth() > widestWidthSeen) {
00805       widestWidthSeen = DstTy->getBitWidth();
00806       widestType = DstTy;
00807     }
00808   }
00809 
00810 
00811   assert(widestWidthSeen > 0);
00812 
00813   // Now extend each pair to the widest seen.
00814   for (unsigned i = 0; i < Pairs.size(); i++) {
00815     const SCEV *Src = Pairs[i]->Src;
00816     const SCEV *Dst = Pairs[i]->Dst;
00817     IntegerType *SrcTy = dyn_cast<IntegerType>(Src->getType());
00818     IntegerType *DstTy = dyn_cast<IntegerType>(Dst->getType());
00819     if (SrcTy == nullptr || DstTy == nullptr) {
00820       assert(SrcTy == DstTy && "This function only unify integer types and "
00821              "expect Src and Dst share the same type "
00822              "otherwise.");
00823       continue;
00824     }
00825     if (SrcTy->getBitWidth() < widestWidthSeen)
00826       // Sign-extend Src to widestType
00827       Pairs[i]->Src = SE->getSignExtendExpr(Src, widestType);
00828     if (DstTy->getBitWidth() < widestWidthSeen) {
00829       // Sign-extend Dst to widestType
00830       Pairs[i]->Dst = SE->getSignExtendExpr(Dst, widestType);
00831     }
00832   }
00833 }
00834 
00835 // removeMatchingExtensions - Examines a subscript pair.
00836 // If the source and destination are identically sign (or zero)
00837 // extended, it strips off the extension in an effect to simplify
00838 // the actual analysis.
00839 void DependenceAnalysis::removeMatchingExtensions(Subscript *Pair) {
00840   const SCEV *Src = Pair->Src;
00841   const SCEV *Dst = Pair->Dst;
00842   if ((isa<SCEVZeroExtendExpr>(Src) && isa<SCEVZeroExtendExpr>(Dst)) ||
00843       (isa<SCEVSignExtendExpr>(Src) && isa<SCEVSignExtendExpr>(Dst))) {
00844     const SCEVCastExpr *SrcCast = cast<SCEVCastExpr>(Src);
00845     const SCEVCastExpr *DstCast = cast<SCEVCastExpr>(Dst);
00846     const SCEV *SrcCastOp = SrcCast->getOperand();
00847     const SCEV *DstCastOp = DstCast->getOperand();
00848     if (SrcCastOp->getType() == DstCastOp->getType()) {
00849       Pair->Src = SrcCastOp;
00850       Pair->Dst = DstCastOp;
00851     }
00852   }
00853 }
00854 
00855 
00856 // Examine the scev and return true iff it's linear.
00857 // Collect any loops mentioned in the set of "Loops".
00858 bool DependenceAnalysis::checkSrcSubscript(const SCEV *Src,
00859                                            const Loop *LoopNest,
00860                                            SmallBitVector &Loops) {
00861   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Src);
00862   if (!AddRec)
00863     return isLoopInvariant(Src, LoopNest);
00864   const SCEV *Start = AddRec->getStart();
00865   const SCEV *Step = AddRec->getStepRecurrence(*SE);
00866   const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop());
00867   if (!isa<SCEVCouldNotCompute>(UB)) {
00868     if (SE->getTypeSizeInBits(Start->getType()) <
00869         SE->getTypeSizeInBits(UB->getType())) {
00870       if (!AddRec->getNoWrapFlags())
00871         return false;
00872     }
00873   }
00874   if (!isLoopInvariant(Step, LoopNest))
00875     return false;
00876   Loops.set(mapSrcLoop(AddRec->getLoop()));
00877   return checkSrcSubscript(Start, LoopNest, Loops);
00878 }
00879 
00880 
00881 
00882 // Examine the scev and return true iff it's linear.
00883 // Collect any loops mentioned in the set of "Loops".
00884 bool DependenceAnalysis::checkDstSubscript(const SCEV *Dst,
00885                                            const Loop *LoopNest,
00886                                            SmallBitVector &Loops) {
00887   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Dst);
00888   if (!AddRec)
00889     return isLoopInvariant(Dst, LoopNest);
00890   const SCEV *Start = AddRec->getStart();
00891   const SCEV *Step = AddRec->getStepRecurrence(*SE);
00892   const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop());
00893   if (!isa<SCEVCouldNotCompute>(UB)) {
00894     if (SE->getTypeSizeInBits(Start->getType()) <
00895         SE->getTypeSizeInBits(UB->getType())) {
00896       if (!AddRec->getNoWrapFlags())
00897         return false;
00898     }
00899   }
00900   if (!isLoopInvariant(Step, LoopNest))
00901     return false;
00902   Loops.set(mapDstLoop(AddRec->getLoop()));
00903   return checkDstSubscript(Start, LoopNest, Loops);
00904 }
00905 
00906 
00907 // Examines the subscript pair (the Src and Dst SCEVs)
00908 // and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear.
00909 // Collects the associated loops in a set.
00910 DependenceAnalysis::Subscript::ClassificationKind
00911 DependenceAnalysis::classifyPair(const SCEV *Src, const Loop *SrcLoopNest,
00912                                  const SCEV *Dst, const Loop *DstLoopNest,
00913                                  SmallBitVector &Loops) {
00914   SmallBitVector SrcLoops(MaxLevels + 1);
00915   SmallBitVector DstLoops(MaxLevels + 1);
00916   if (!checkSrcSubscript(Src, SrcLoopNest, SrcLoops))
00917     return Subscript::NonLinear;
00918   if (!checkDstSubscript(Dst, DstLoopNest, DstLoops))
00919     return Subscript::NonLinear;
00920   Loops = SrcLoops;
00921   Loops |= DstLoops;
00922   unsigned N = Loops.count();
00923   if (N == 0)
00924     return Subscript::ZIV;
00925   if (N == 1)
00926     return Subscript::SIV;
00927   if (N == 2 && (SrcLoops.count() == 0 ||
00928                  DstLoops.count() == 0 ||
00929                  (SrcLoops.count() == 1 && DstLoops.count() == 1)))
00930     return Subscript::RDIV;
00931   return Subscript::MIV;
00932 }
00933 
00934 
00935 // A wrapper around SCEV::isKnownPredicate.
00936 // Looks for cases where we're interested in comparing for equality.
00937 // If both X and Y have been identically sign or zero extended,
00938 // it strips off the (confusing) extensions before invoking
00939 // SCEV::isKnownPredicate. Perhaps, someday, the ScalarEvolution package
00940 // will be similarly updated.
00941 //
00942 // If SCEV::isKnownPredicate can't prove the predicate,
00943 // we try simple subtraction, which seems to help in some cases
00944 // involving symbolics.
00945 bool DependenceAnalysis::isKnownPredicate(ICmpInst::Predicate Pred,
00946                                           const SCEV *X,
00947                                           const SCEV *Y) const {
00948   if (Pred == CmpInst::ICMP_EQ ||
00949       Pred == CmpInst::ICMP_NE) {
00950     if ((isa<SCEVSignExtendExpr>(X) &&
00951          isa<SCEVSignExtendExpr>(Y)) ||
00952         (isa<SCEVZeroExtendExpr>(X) &&
00953          isa<SCEVZeroExtendExpr>(Y))) {
00954       const SCEVCastExpr *CX = cast<SCEVCastExpr>(X);
00955       const SCEVCastExpr *CY = cast<SCEVCastExpr>(Y);
00956       const SCEV *Xop = CX->getOperand();
00957       const SCEV *Yop = CY->getOperand();
00958       if (Xop->getType() == Yop->getType()) {
00959         X = Xop;
00960         Y = Yop;
00961       }
00962     }
00963   }
00964   if (SE->isKnownPredicate(Pred, X, Y))
00965     return true;
00966   // If SE->isKnownPredicate can't prove the condition,
00967   // we try the brute-force approach of subtracting
00968   // and testing the difference.
00969   // By testing with SE->isKnownPredicate first, we avoid
00970   // the possibility of overflow when the arguments are constants.
00971   const SCEV *Delta = SE->getMinusSCEV(X, Y);
00972   switch (Pred) {
00973   case CmpInst::ICMP_EQ:
00974     return Delta->isZero();
00975   case CmpInst::ICMP_NE:
00976     return SE->isKnownNonZero(Delta);
00977   case CmpInst::ICMP_SGE:
00978     return SE->isKnownNonNegative(Delta);
00979   case CmpInst::ICMP_SLE:
00980     return SE->isKnownNonPositive(Delta);
00981   case CmpInst::ICMP_SGT:
00982     return SE->isKnownPositive(Delta);
00983   case CmpInst::ICMP_SLT:
00984     return SE->isKnownNegative(Delta);
00985   default:
00986     llvm_unreachable("unexpected predicate in isKnownPredicate");
00987   }
00988 }
00989 
00990 
00991 // All subscripts are all the same type.
00992 // Loop bound may be smaller (e.g., a char).
00993 // Should zero extend loop bound, since it's always >= 0.
00994 // This routine collects upper bound and extends or truncates if needed.
00995 // Truncating is safe when subscripts are known not to wrap. Cases without
00996 // nowrap flags should have been rejected earlier.
00997 // Return null if no bound available.
00998 const SCEV *DependenceAnalysis::collectUpperBound(const Loop *L,
00999                                                   Type *T) const {
01000   if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
01001     const SCEV *UB = SE->getBackedgeTakenCount(L);
01002     return SE->getTruncateOrZeroExtend(UB, T);
01003   }
01004   return nullptr;
01005 }
01006 
01007 
01008 // Calls collectUpperBound(), then attempts to cast it to SCEVConstant.
01009 // If the cast fails, returns NULL.
01010 const SCEVConstant *DependenceAnalysis::collectConstantUpperBound(const Loop *L,
01011                                                                   Type *T
01012                                                                   ) const {
01013   if (const SCEV *UB = collectUpperBound(L, T))
01014     return dyn_cast<SCEVConstant>(UB);
01015   return nullptr;
01016 }
01017 
01018 
01019 // testZIV -
01020 // When we have a pair of subscripts of the form [c1] and [c2],
01021 // where c1 and c2 are both loop invariant, we attack it using
01022 // the ZIV test. Basically, we test by comparing the two values,
01023 // but there are actually three possible results:
01024 // 1) the values are equal, so there's a dependence
01025 // 2) the values are different, so there's no dependence
01026 // 3) the values might be equal, so we have to assume a dependence.
01027 //
01028 // Return true if dependence disproved.
01029 bool DependenceAnalysis::testZIV(const SCEV *Src,
01030                                  const SCEV *Dst,
01031                                  FullDependence &Result) const {
01032   DEBUG(dbgs() << "    src = " << *Src << "\n");
01033   DEBUG(dbgs() << "    dst = " << *Dst << "\n");
01034   ++ZIVapplications;
01035   if (isKnownPredicate(CmpInst::ICMP_EQ, Src, Dst)) {
01036     DEBUG(dbgs() << "    provably dependent\n");
01037     return false; // provably dependent
01038   }
01039   if (isKnownPredicate(CmpInst::ICMP_NE, Src, Dst)) {
01040     DEBUG(dbgs() << "    provably independent\n");
01041     ++ZIVindependence;
01042     return true; // provably independent
01043   }
01044   DEBUG(dbgs() << "    possibly dependent\n");
01045   Result.Consistent = false;
01046   return false; // possibly dependent
01047 }
01048 
01049 
01050 // strongSIVtest -
01051 // From the paper, Practical Dependence Testing, Section 4.2.1
01052 //
01053 // When we have a pair of subscripts of the form [c1 + a*i] and [c2 + a*i],
01054 // where i is an induction variable, c1 and c2 are loop invariant,
01055 //  and a is a constant, we can solve it exactly using the Strong SIV test.
01056 //
01057 // Can prove independence. Failing that, can compute distance (and direction).
01058 // In the presence of symbolic terms, we can sometimes make progress.
01059 //
01060 // If there's a dependence,
01061 //
01062 //    c1 + a*i = c2 + a*i'
01063 //
01064 // The dependence distance is
01065 //
01066 //    d = i' - i = (c1 - c2)/a
01067 //
01068 // A dependence only exists if d is an integer and abs(d) <= U, where U is the
01069 // loop's upper bound. If a dependence exists, the dependence direction is
01070 // defined as
01071 //
01072 //                { < if d > 0
01073 //    direction = { = if d = 0
01074 //                { > if d < 0
01075 //
01076 // Return true if dependence disproved.
01077 bool DependenceAnalysis::strongSIVtest(const SCEV *Coeff,
01078                                        const SCEV *SrcConst,
01079                                        const SCEV *DstConst,
01080                                        const Loop *CurLoop,
01081                                        unsigned Level,
01082                                        FullDependence &Result,
01083                                        Constraint &NewConstraint) const {
01084   DEBUG(dbgs() << "\tStrong SIV test\n");
01085   DEBUG(dbgs() << "\t    Coeff = " << *Coeff);
01086   DEBUG(dbgs() << ", " << *Coeff->getType() << "\n");
01087   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst);
01088   DEBUG(dbgs() << ", " << *SrcConst->getType() << "\n");
01089   DEBUG(dbgs() << "\t    DstConst = " << *DstConst);
01090   DEBUG(dbgs() << ", " << *DstConst->getType() << "\n");
01091   ++StrongSIVapplications;
01092   assert(0 < Level && Level <= CommonLevels && "level out of range");
01093   Level--;
01094 
01095   const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst);
01096   DEBUG(dbgs() << "\t    Delta = " << *Delta);
01097   DEBUG(dbgs() << ", " << *Delta->getType() << "\n");
01098 
01099   // check that |Delta| < iteration count
01100   if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {
01101     DEBUG(dbgs() << "\t    UpperBound = " << *UpperBound);
01102     DEBUG(dbgs() << ", " << *UpperBound->getType() << "\n");
01103     const SCEV *AbsDelta =
01104       SE->isKnownNonNegative(Delta) ? Delta : SE->getNegativeSCEV(Delta);
01105     const SCEV *AbsCoeff =
01106       SE->isKnownNonNegative(Coeff) ? Coeff : SE->getNegativeSCEV(Coeff);
01107     const SCEV *Product = SE->getMulExpr(UpperBound, AbsCoeff);
01108     if (isKnownPredicate(CmpInst::ICMP_SGT, AbsDelta, Product)) {
01109       // Distance greater than trip count - no dependence
01110       ++StrongSIVindependence;
01111       ++StrongSIVsuccesses;
01112       return true;
01113     }
01114   }
01115 
01116   // Can we compute distance?
01117   if (isa<SCEVConstant>(Delta) && isa<SCEVConstant>(Coeff)) {
01118     APInt ConstDelta = cast<SCEVConstant>(Delta)->getAPInt();
01119     APInt ConstCoeff = cast<SCEVConstant>(Coeff)->getAPInt();
01120     APInt Distance  = ConstDelta; // these need to be initialized
01121     APInt Remainder = ConstDelta;
01122     APInt::sdivrem(ConstDelta, ConstCoeff, Distance, Remainder);
01123     DEBUG(dbgs() << "\t    Distance = " << Distance << "\n");
01124     DEBUG(dbgs() << "\t    Remainder = " << Remainder << "\n");
01125     // Make sure Coeff divides Delta exactly
01126     if (Remainder != 0) {
01127       // Coeff doesn't divide Distance, no dependence
01128       ++StrongSIVindependence;
01129       ++StrongSIVsuccesses;
01130       return true;
01131     }
01132     Result.DV[Level].Distance = SE->getConstant(Distance);
01133     NewConstraint.setDistance(SE->getConstant(Distance), CurLoop);
01134     if (Distance.sgt(0))
01135       Result.DV[Level].Direction &= Dependence::DVEntry::LT;
01136     else if (Distance.slt(0))
01137       Result.DV[Level].Direction &= Dependence::DVEntry::GT;
01138     else
01139       Result.DV[Level].Direction &= Dependence::DVEntry::EQ;
01140     ++StrongSIVsuccesses;
01141   }
01142   else if (Delta->isZero()) {
01143     // since 0/X == 0
01144     Result.DV[Level].Distance = Delta;
01145     NewConstraint.setDistance(Delta, CurLoop);
01146     Result.DV[Level].Direction &= Dependence::DVEntry::EQ;
01147     ++StrongSIVsuccesses;
01148   }
01149   else {
01150     if (Coeff->isOne()) {
01151       DEBUG(dbgs() << "\t    Distance = " << *Delta << "\n");
01152       Result.DV[Level].Distance = Delta; // since X/1 == X
01153       NewConstraint.setDistance(Delta, CurLoop);
01154     }
01155     else {
01156       Result.Consistent = false;
01157       NewConstraint.setLine(Coeff,
01158                             SE->getNegativeSCEV(Coeff),
01159                             SE->getNegativeSCEV(Delta), CurLoop);
01160     }
01161 
01162     // maybe we can get a useful direction
01163     bool DeltaMaybeZero     = !SE->isKnownNonZero(Delta);
01164     bool DeltaMaybePositive = !SE->isKnownNonPositive(Delta);
01165     bool DeltaMaybeNegative = !SE->isKnownNonNegative(Delta);
01166     bool CoeffMaybePositive = !SE->isKnownNonPositive(Coeff);
01167     bool CoeffMaybeNegative = !SE->isKnownNonNegative(Coeff);
01168     // The double negatives above are confusing.
01169     // It helps to read !SE->isKnownNonZero(Delta)
01170     // as "Delta might be Zero"
01171     unsigned NewDirection = Dependence::DVEntry::NONE;
01172     if ((DeltaMaybePositive && CoeffMaybePositive) ||
01173         (DeltaMaybeNegative && CoeffMaybeNegative))
01174       NewDirection = Dependence::DVEntry::LT;
01175     if (DeltaMaybeZero)
01176       NewDirection |= Dependence::DVEntry::EQ;
01177     if ((DeltaMaybeNegative && CoeffMaybePositive) ||
01178         (DeltaMaybePositive && CoeffMaybeNegative))
01179       NewDirection |= Dependence::DVEntry::GT;
01180     if (NewDirection < Result.DV[Level].Direction)
01181       ++StrongSIVsuccesses;
01182     Result.DV[Level].Direction &= NewDirection;
01183   }
01184   return false;
01185 }
01186 
01187 
01188 // weakCrossingSIVtest -
01189 // From the paper, Practical Dependence Testing, Section 4.2.2
01190 //
01191 // When we have a pair of subscripts of the form [c1 + a*i] and [c2 - a*i],
01192 // where i is an induction variable, c1 and c2 are loop invariant,
01193 // and a is a constant, we can solve it exactly using the
01194 // Weak-Crossing SIV test.
01195 //
01196 // Given c1 + a*i = c2 - a*i', we can look for the intersection of
01197 // the two lines, where i = i', yielding
01198 //
01199 //    c1 + a*i = c2 - a*i
01200 //    2a*i = c2 - c1
01201 //    i = (c2 - c1)/2a
01202 //
01203 // If i < 0, there is no dependence.
01204 // If i > upperbound, there is no dependence.
01205 // If i = 0 (i.e., if c1 = c2), there's a dependence with distance = 0.
01206 // If i = upperbound, there's a dependence with distance = 0.
01207 // If i is integral, there's a dependence (all directions).
01208 // If the non-integer part = 1/2, there's a dependence (<> directions).
01209 // Otherwise, there's no dependence.
01210 //
01211 // Can prove independence. Failing that,
01212 // can sometimes refine the directions.
01213 // Can determine iteration for splitting.
01214 //
01215 // Return true if dependence disproved.
01216 bool DependenceAnalysis::weakCrossingSIVtest(const SCEV *Coeff,
01217                                              const SCEV *SrcConst,
01218                                              const SCEV *DstConst,
01219                                              const Loop *CurLoop,
01220                                              unsigned Level,
01221                                              FullDependence &Result,
01222                                              Constraint &NewConstraint,
01223                                              const SCEV *&SplitIter) const {
01224   DEBUG(dbgs() << "\tWeak-Crossing SIV test\n");
01225   DEBUG(dbgs() << "\t    Coeff = " << *Coeff << "\n");
01226   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
01227   DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
01228   ++WeakCrossingSIVapplications;
01229   assert(0 < Level && Level <= CommonLevels && "Level out of range");
01230   Level--;
01231   Result.Consistent = false;
01232   const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
01233   DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
01234   NewConstraint.setLine(Coeff, Coeff, Delta, CurLoop);
01235   if (Delta->isZero()) {
01236     Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT);
01237     Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT);
01238     ++WeakCrossingSIVsuccesses;
01239     if (!Result.DV[Level].Direction) {
01240       ++WeakCrossingSIVindependence;
01241       return true;
01242     }
01243     Result.DV[Level].Distance = Delta; // = 0
01244     return false;
01245   }
01246   const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(Coeff);
01247   if (!ConstCoeff)
01248     return false;
01249 
01250   Result.DV[Level].Splitable = true;
01251   if (SE->isKnownNegative(ConstCoeff)) {
01252     ConstCoeff = dyn_cast<SCEVConstant>(SE->getNegativeSCEV(ConstCoeff));
01253     assert(ConstCoeff &&
01254            "dynamic cast of negative of ConstCoeff should yield constant");
01255     Delta = SE->getNegativeSCEV(Delta);
01256   }
01257   assert(SE->isKnownPositive(ConstCoeff) && "ConstCoeff should be positive");
01258 
01259   // compute SplitIter for use by DependenceAnalysis::getSplitIteration()
01260   SplitIter = SE->getUDivExpr(
01261       SE->getSMaxExpr(SE->getZero(Delta->getType()), Delta),
01262       SE->getMulExpr(SE->getConstant(Delta->getType(), 2), ConstCoeff));
01263   DEBUG(dbgs() << "\t    Split iter = " << *SplitIter << "\n");
01264 
01265   const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
01266   if (!ConstDelta)
01267     return false;
01268 
01269   // We're certain that ConstCoeff > 0; therefore,
01270   // if Delta < 0, then no dependence.
01271   DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
01272   DEBUG(dbgs() << "\t    ConstCoeff = " << *ConstCoeff << "\n");
01273   if (SE->isKnownNegative(Delta)) {
01274     // No dependence, Delta < 0
01275     ++WeakCrossingSIVindependence;
01276     ++WeakCrossingSIVsuccesses;
01277     return true;
01278   }
01279 
01280   // We're certain that Delta > 0 and ConstCoeff > 0.
01281   // Check Delta/(2*ConstCoeff) against upper loop bound
01282   if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {
01283     DEBUG(dbgs() << "\t    UpperBound = " << *UpperBound << "\n");
01284     const SCEV *ConstantTwo = SE->getConstant(UpperBound->getType(), 2);
01285     const SCEV *ML = SE->getMulExpr(SE->getMulExpr(ConstCoeff, UpperBound),
01286                                     ConstantTwo);
01287     DEBUG(dbgs() << "\t    ML = " << *ML << "\n");
01288     if (isKnownPredicate(CmpInst::ICMP_SGT, Delta, ML)) {
01289       // Delta too big, no dependence
01290       ++WeakCrossingSIVindependence;
01291       ++WeakCrossingSIVsuccesses;
01292       return true;
01293     }
01294     if (isKnownPredicate(CmpInst::ICMP_EQ, Delta, ML)) {
01295       // i = i' = UB
01296       Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::LT);
01297       Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::GT);
01298       ++WeakCrossingSIVsuccesses;
01299       if (!Result.DV[Level].Direction) {
01300         ++WeakCrossingSIVindependence;
01301         return true;
01302       }
01303       Result.DV[Level].Splitable = false;
01304       Result.DV[Level].Distance = SE->getZero(Delta->getType());
01305       return false;
01306     }
01307   }
01308 
01309   // check that Coeff divides Delta
01310   APInt APDelta = ConstDelta->getAPInt();
01311   APInt APCoeff = ConstCoeff->getAPInt();
01312   APInt Distance = APDelta; // these need to be initialzed
01313   APInt Remainder = APDelta;
01314   APInt::sdivrem(APDelta, APCoeff, Distance, Remainder);
01315   DEBUG(dbgs() << "\t    Remainder = " << Remainder << "\n");
01316   if (Remainder != 0) {
01317     // Coeff doesn't divide Delta, no dependence
01318     ++WeakCrossingSIVindependence;
01319     ++WeakCrossingSIVsuccesses;
01320     return true;
01321   }
01322   DEBUG(dbgs() << "\t    Distance = " << Distance << "\n");
01323 
01324   // if 2*Coeff doesn't divide Delta, then the equal direction isn't possible
01325   APInt Two = APInt(Distance.getBitWidth(), 2, true);
01326   Remainder = Distance.srem(Two);
01327   DEBUG(dbgs() << "\t    Remainder = " << Remainder << "\n");
01328   if (Remainder != 0) {
01329     // Equal direction isn't possible
01330     Result.DV[Level].Direction &= unsigned(~Dependence::DVEntry::EQ);
01331     ++WeakCrossingSIVsuccesses;
01332   }
01333   return false;
01334 }
01335 
01336 
01337 // Kirch's algorithm, from
01338 //
01339 //        Optimizing Supercompilers for Supercomputers
01340 //        Michael Wolfe
01341 //        MIT Press, 1989
01342 //
01343 // Program 2.1, page 29.
01344 // Computes the GCD of AM and BM.
01345 // Also finds a solution to the equation ax - by = gcd(a, b).
01346 // Returns true if dependence disproved; i.e., gcd does not divide Delta.
01347 static
01348 bool findGCD(unsigned Bits, APInt AM, APInt BM, APInt Delta,
01349              APInt &G, APInt &X, APInt &Y) {
01350   APInt A0(Bits, 1, true), A1(Bits, 0, true);
01351   APInt B0(Bits, 0, true), B1(Bits, 1, true);
01352   APInt G0 = AM.abs();
01353   APInt G1 = BM.abs();
01354   APInt Q = G0; // these need to be initialized
01355   APInt R = G0;
01356   APInt::sdivrem(G0, G1, Q, R);
01357   while (R != 0) {
01358     APInt A2 = A0 - Q*A1; A0 = A1; A1 = A2;
01359     APInt B2 = B0 - Q*B1; B0 = B1; B1 = B2;
01360     G0 = G1; G1 = R;
01361     APInt::sdivrem(G0, G1, Q, R);
01362   }
01363   G = G1;
01364   DEBUG(dbgs() << "\t    GCD = " << G << "\n");
01365   X = AM.slt(0) ? -A1 : A1;
01366   Y = BM.slt(0) ? B1 : -B1;
01367 
01368   // make sure gcd divides Delta
01369   R = Delta.srem(G);
01370   if (R != 0)
01371     return true; // gcd doesn't divide Delta, no dependence
01372   Q = Delta.sdiv(G);
01373   X *= Q;
01374   Y *= Q;
01375   return false;
01376 }
01377 
01378 
01379 static
01380 APInt floorOfQuotient(APInt A, APInt B) {
01381   APInt Q = A; // these need to be initialized
01382   APInt R = A;
01383   APInt::sdivrem(A, B, Q, R);
01384   if (R == 0)
01385     return Q;
01386   if ((A.sgt(0) && B.sgt(0)) ||
01387       (A.slt(0) && B.slt(0)))
01388     return Q;
01389   else
01390     return Q - 1;
01391 }
01392 
01393 
01394 static
01395 APInt ceilingOfQuotient(APInt A, APInt B) {
01396   APInt Q = A; // these need to be initialized
01397   APInt R = A;
01398   APInt::sdivrem(A, B, Q, R);
01399   if (R == 0)
01400     return Q;
01401   if ((A.sgt(0) && B.sgt(0)) ||
01402       (A.slt(0) && B.slt(0)))
01403     return Q + 1;
01404   else
01405     return Q;
01406 }
01407 
01408 
01409 static
01410 APInt maxAPInt(APInt A, APInt B) {
01411   return A.sgt(B) ? A : B;
01412 }
01413 
01414 
01415 static
01416 APInt minAPInt(APInt A, APInt B) {
01417   return A.slt(B) ? A : B;
01418 }
01419 
01420 
01421 // exactSIVtest -
01422 // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*i],
01423 // where i is an induction variable, c1 and c2 are loop invariant, and a1
01424 // and a2 are constant, we can solve it exactly using an algorithm developed
01425 // by Banerjee and Wolfe. See Section 2.5.3 in
01426 //
01427 //        Optimizing Supercompilers for Supercomputers
01428 //        Michael Wolfe
01429 //        MIT Press, 1989
01430 //
01431 // It's slower than the specialized tests (strong SIV, weak-zero SIV, etc),
01432 // so use them if possible. They're also a bit better with symbolics and,
01433 // in the case of the strong SIV test, can compute Distances.
01434 //
01435 // Return true if dependence disproved.
01436 bool DependenceAnalysis::exactSIVtest(const SCEV *SrcCoeff,
01437                                       const SCEV *DstCoeff,
01438                                       const SCEV *SrcConst,
01439                                       const SCEV *DstConst,
01440                                       const Loop *CurLoop,
01441                                       unsigned Level,
01442                                       FullDependence &Result,
01443                                       Constraint &NewConstraint) const {
01444   DEBUG(dbgs() << "\tExact SIV test\n");
01445   DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << " = AM\n");
01446   DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << " = BM\n");
01447   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
01448   DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
01449   ++ExactSIVapplications;
01450   assert(0 < Level && Level <= CommonLevels && "Level out of range");
01451   Level--;
01452   Result.Consistent = false;
01453   const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
01454   DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
01455   NewConstraint.setLine(SrcCoeff, SE->getNegativeSCEV(DstCoeff),
01456                         Delta, CurLoop);
01457   const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
01458   const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
01459   const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
01460   if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
01461     return false;
01462 
01463   // find gcd
01464   APInt G, X, Y;
01465   APInt AM = ConstSrcCoeff->getAPInt();
01466   APInt BM = ConstDstCoeff->getAPInt();
01467   unsigned Bits = AM.getBitWidth();
01468   if (findGCD(Bits, AM, BM, ConstDelta->getAPInt(), G, X, Y)) {
01469     // gcd doesn't divide Delta, no dependence
01470     ++ExactSIVindependence;
01471     ++ExactSIVsuccesses;
01472     return true;
01473   }
01474 
01475   DEBUG(dbgs() << "\t    X = " << X << ", Y = " << Y << "\n");
01476 
01477   // since SCEV construction normalizes, LM = 0
01478   APInt UM(Bits, 1, true);
01479   bool UMvalid = false;
01480   // UM is perhaps unavailable, let's check
01481   if (const SCEVConstant *CUB =
01482       collectConstantUpperBound(CurLoop, Delta->getType())) {
01483     UM = CUB->getAPInt();
01484     DEBUG(dbgs() << "\t    UM = " << UM << "\n");
01485     UMvalid = true;
01486   }
01487 
01488   APInt TU(APInt::getSignedMaxValue(Bits));
01489   APInt TL(APInt::getSignedMinValue(Bits));
01490 
01491   // test(BM/G, LM-X) and test(-BM/G, X-UM)
01492   APInt TMUL = BM.sdiv(G);
01493   if (TMUL.sgt(0)) {
01494     TL = maxAPInt(TL, ceilingOfQuotient(-X, TMUL));
01495     DEBUG(dbgs() << "\t    TL = " << TL << "\n");
01496     if (UMvalid) {
01497       TU = minAPInt(TU, floorOfQuotient(UM - X, TMUL));
01498       DEBUG(dbgs() << "\t    TU = " << TU << "\n");
01499     }
01500   }
01501   else {
01502     TU = minAPInt(TU, floorOfQuotient(-X, TMUL));
01503     DEBUG(dbgs() << "\t    TU = " << TU << "\n");
01504     if (UMvalid) {
01505       TL = maxAPInt(TL, ceilingOfQuotient(UM - X, TMUL));
01506       DEBUG(dbgs() << "\t    TL = " << TL << "\n");
01507     }
01508   }
01509 
01510   // test(AM/G, LM-Y) and test(-AM/G, Y-UM)
01511   TMUL = AM.sdiv(G);
01512   if (TMUL.sgt(0)) {
01513     TL = maxAPInt(TL, ceilingOfQuotient(-Y, TMUL));
01514     DEBUG(dbgs() << "\t    TL = " << TL << "\n");
01515     if (UMvalid) {
01516       TU = minAPInt(TU, floorOfQuotient(UM - Y, TMUL));
01517       DEBUG(dbgs() << "\t    TU = " << TU << "\n");
01518     }
01519   }
01520   else {
01521     TU = minAPInt(TU, floorOfQuotient(-Y, TMUL));
01522     DEBUG(dbgs() << "\t    TU = " << TU << "\n");
01523     if (UMvalid) {
01524       TL = maxAPInt(TL, ceilingOfQuotient(UM - Y, TMUL));
01525       DEBUG(dbgs() << "\t    TL = " << TL << "\n");
01526     }
01527   }
01528   if (TL.sgt(TU)) {
01529     ++ExactSIVindependence;
01530     ++ExactSIVsuccesses;
01531     return true;
01532   }
01533 
01534   // explore directions
01535   unsigned NewDirection = Dependence::DVEntry::NONE;
01536 
01537   // less than
01538   APInt SaveTU(TU); // save these
01539   APInt SaveTL(TL);
01540   DEBUG(dbgs() << "\t    exploring LT direction\n");
01541   TMUL = AM - BM;
01542   if (TMUL.sgt(0)) {
01543     TL = maxAPInt(TL, ceilingOfQuotient(X - Y + 1, TMUL));
01544     DEBUG(dbgs() << "\t\t    TL = " << TL << "\n");
01545   }
01546   else {
01547     TU = minAPInt(TU, floorOfQuotient(X - Y + 1, TMUL));
01548     DEBUG(dbgs() << "\t\t    TU = " << TU << "\n");
01549   }
01550   if (TL.sle(TU)) {
01551     NewDirection |= Dependence::DVEntry::LT;
01552     ++ExactSIVsuccesses;
01553   }
01554 
01555   // equal
01556   TU = SaveTU; // restore
01557   TL = SaveTL;
01558   DEBUG(dbgs() << "\t    exploring EQ direction\n");
01559   if (TMUL.sgt(0)) {
01560     TL = maxAPInt(TL, ceilingOfQuotient(X - Y, TMUL));
01561     DEBUG(dbgs() << "\t\t    TL = " << TL << "\n");
01562   }
01563   else {
01564     TU = minAPInt(TU, floorOfQuotient(X - Y, TMUL));
01565     DEBUG(dbgs() << "\t\t    TU = " << TU << "\n");
01566   }
01567   TMUL = BM - AM;
01568   if (TMUL.sgt(0)) {
01569     TL = maxAPInt(TL, ceilingOfQuotient(Y - X, TMUL));
01570     DEBUG(dbgs() << "\t\t    TL = " << TL << "\n");
01571   }
01572   else {
01573     TU = minAPInt(TU, floorOfQuotient(Y - X, TMUL));
01574     DEBUG(dbgs() << "\t\t    TU = " << TU << "\n");
01575   }
01576   if (TL.sle(TU)) {
01577     NewDirection |= Dependence::DVEntry::EQ;
01578     ++ExactSIVsuccesses;
01579   }
01580 
01581   // greater than
01582   TU = SaveTU; // restore
01583   TL = SaveTL;
01584   DEBUG(dbgs() << "\t    exploring GT direction\n");
01585   if (TMUL.sgt(0)) {
01586     TL = maxAPInt(TL, ceilingOfQuotient(Y - X + 1, TMUL));
01587     DEBUG(dbgs() << "\t\t    TL = " << TL << "\n");
01588   }
01589   else {
01590     TU = minAPInt(TU, floorOfQuotient(Y - X + 1, TMUL));
01591     DEBUG(dbgs() << "\t\t    TU = " << TU << "\n");
01592   }
01593   if (TL.sle(TU)) {
01594     NewDirection |= Dependence::DVEntry::GT;
01595     ++ExactSIVsuccesses;
01596   }
01597 
01598   // finished
01599   Result.DV[Level].Direction &= NewDirection;
01600   if (Result.DV[Level].Direction == Dependence::DVEntry::NONE)
01601     ++ExactSIVindependence;
01602   return Result.DV[Level].Direction == Dependence::DVEntry::NONE;
01603 }
01604 
01605 
01606 
01607 // Return true if the divisor evenly divides the dividend.
01608 static
01609 bool isRemainderZero(const SCEVConstant *Dividend,
01610                      const SCEVConstant *Divisor) {
01611   APInt ConstDividend = Dividend->getAPInt();
01612   APInt ConstDivisor = Divisor->getAPInt();
01613   return ConstDividend.srem(ConstDivisor) == 0;
01614 }
01615 
01616 
01617 // weakZeroSrcSIVtest -
01618 // From the paper, Practical Dependence Testing, Section 4.2.2
01619 //
01620 // When we have a pair of subscripts of the form [c1] and [c2 + a*i],
01621 // where i is an induction variable, c1 and c2 are loop invariant,
01622 // and a is a constant, we can solve it exactly using the
01623 // Weak-Zero SIV test.
01624 //
01625 // Given
01626 //
01627 //    c1 = c2 + a*i
01628 //
01629 // we get
01630 //
01631 //    (c1 - c2)/a = i
01632 //
01633 // If i is not an integer, there's no dependence.
01634 // If i < 0 or > UB, there's no dependence.
01635 // If i = 0, the direction is <= and peeling the
01636 // 1st iteration will break the dependence.
01637 // If i = UB, the direction is >= and peeling the
01638 // last iteration will break the dependence.
01639 // Otherwise, the direction is *.
01640 //
01641 // Can prove independence. Failing that, we can sometimes refine
01642 // the directions. Can sometimes show that first or last
01643 // iteration carries all the dependences (so worth peeling).
01644 //
01645 // (see also weakZeroDstSIVtest)
01646 //
01647 // Return true if dependence disproved.
01648 bool DependenceAnalysis::weakZeroSrcSIVtest(const SCEV *DstCoeff,
01649                                             const SCEV *SrcConst,
01650                                             const SCEV *DstConst,
01651                                             const Loop *CurLoop,
01652                                             unsigned Level,
01653                                             FullDependence &Result,
01654                                             Constraint &NewConstraint) const {
01655   // For the WeakSIV test, it's possible the loop isn't common to
01656   // the Src and Dst loops. If it isn't, then there's no need to
01657   // record a direction.
01658   DEBUG(dbgs() << "\tWeak-Zero (src) SIV test\n");
01659   DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << "\n");
01660   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
01661   DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
01662   ++WeakZeroSIVapplications;
01663   assert(0 < Level && Level <= MaxLevels && "Level out of range");
01664   Level--;
01665   Result.Consistent = false;
01666   const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst);
01667   NewConstraint.setLine(SE->getZero(Delta->getType()), DstCoeff, Delta,
01668                         CurLoop);
01669   DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
01670   if (isKnownPredicate(CmpInst::ICMP_EQ, SrcConst, DstConst)) {
01671     if (Level < CommonLevels) {
01672       Result.DV[Level].Direction &= Dependence::DVEntry::LE;
01673       Result.DV[Level].PeelFirst = true;
01674       ++WeakZeroSIVsuccesses;
01675     }
01676     return false; // dependences caused by first iteration
01677   }
01678   const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
01679   if (!ConstCoeff)
01680     return false;
01681   const SCEV *AbsCoeff =
01682     SE->isKnownNegative(ConstCoeff) ?
01683     SE->getNegativeSCEV(ConstCoeff) : ConstCoeff;
01684   const SCEV *NewDelta =
01685     SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta;
01686 
01687   // check that Delta/SrcCoeff < iteration count
01688   // really check NewDelta < count*AbsCoeff
01689   if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {
01690     DEBUG(dbgs() << "\t    UpperBound = " << *UpperBound << "\n");
01691     const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound);
01692     if (isKnownPredicate(CmpInst::ICMP_SGT, NewDelta, Product)) {
01693       ++WeakZeroSIVindependence;
01694       ++WeakZeroSIVsuccesses;
01695       return true;
01696     }
01697     if (isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) {
01698       // dependences caused by last iteration
01699       if (Level < CommonLevels) {
01700         Result.DV[Level].Direction &= Dependence::DVEntry::GE;
01701         Result.DV[Level].PeelLast = true;
01702         ++WeakZeroSIVsuccesses;
01703       }
01704       return false;
01705     }
01706   }
01707 
01708   // check that Delta/SrcCoeff >= 0
01709   // really check that NewDelta >= 0
01710   if (SE->isKnownNegative(NewDelta)) {
01711     // No dependence, newDelta < 0
01712     ++WeakZeroSIVindependence;
01713     ++WeakZeroSIVsuccesses;
01714     return true;
01715   }
01716 
01717   // if SrcCoeff doesn't divide Delta, then no dependence
01718   if (isa<SCEVConstant>(Delta) &&
01719       !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) {
01720     ++WeakZeroSIVindependence;
01721     ++WeakZeroSIVsuccesses;
01722     return true;
01723   }
01724   return false;
01725 }
01726 
01727 
01728 // weakZeroDstSIVtest -
01729 // From the paper, Practical Dependence Testing, Section 4.2.2
01730 //
01731 // When we have a pair of subscripts of the form [c1 + a*i] and [c2],
01732 // where i is an induction variable, c1 and c2 are loop invariant,
01733 // and a is a constant, we can solve it exactly using the
01734 // Weak-Zero SIV test.
01735 //
01736 // Given
01737 //
01738 //    c1 + a*i = c2
01739 //
01740 // we get
01741 //
01742 //    i = (c2 - c1)/a
01743 //
01744 // If i is not an integer, there's no dependence.
01745 // If i < 0 or > UB, there's no dependence.
01746 // If i = 0, the direction is <= and peeling the
01747 // 1st iteration will break the dependence.
01748 // If i = UB, the direction is >= and peeling the
01749 // last iteration will break the dependence.
01750 // Otherwise, the direction is *.
01751 //
01752 // Can prove independence. Failing that, we can sometimes refine
01753 // the directions. Can sometimes show that first or last
01754 // iteration carries all the dependences (so worth peeling).
01755 //
01756 // (see also weakZeroSrcSIVtest)
01757 //
01758 // Return true if dependence disproved.
01759 bool DependenceAnalysis::weakZeroDstSIVtest(const SCEV *SrcCoeff,
01760                                             const SCEV *SrcConst,
01761                                             const SCEV *DstConst,
01762                                             const Loop *CurLoop,
01763                                             unsigned Level,
01764                                             FullDependence &Result,
01765                                             Constraint &NewConstraint) const {
01766   // For the WeakSIV test, it's possible the loop isn't common to the
01767   // Src and Dst loops. If it isn't, then there's no need to record a direction.
01768   DEBUG(dbgs() << "\tWeak-Zero (dst) SIV test\n");
01769   DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << "\n");
01770   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
01771   DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
01772   ++WeakZeroSIVapplications;
01773   assert(0 < Level && Level <= SrcLevels && "Level out of range");
01774   Level--;
01775   Result.Consistent = false;
01776   const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
01777   NewConstraint.setLine(SrcCoeff, SE->getZero(Delta->getType()), Delta,
01778                         CurLoop);
01779   DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
01780   if (isKnownPredicate(CmpInst::ICMP_EQ, DstConst, SrcConst)) {
01781     if (Level < CommonLevels) {
01782       Result.DV[Level].Direction &= Dependence::DVEntry::LE;
01783       Result.DV[Level].PeelFirst = true;
01784       ++WeakZeroSIVsuccesses;
01785     }
01786     return false; // dependences caused by first iteration
01787   }
01788   const SCEVConstant *ConstCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
01789   if (!ConstCoeff)
01790     return false;
01791   const SCEV *AbsCoeff =
01792     SE->isKnownNegative(ConstCoeff) ?
01793     SE->getNegativeSCEV(ConstCoeff) : ConstCoeff;
01794   const SCEV *NewDelta =
01795     SE->isKnownNegative(ConstCoeff) ? SE->getNegativeSCEV(Delta) : Delta;
01796 
01797   // check that Delta/SrcCoeff < iteration count
01798   // really check NewDelta < count*AbsCoeff
01799   if (const SCEV *UpperBound = collectUpperBound(CurLoop, Delta->getType())) {
01800     DEBUG(dbgs() << "\t    UpperBound = " << *UpperBound << "\n");
01801     const SCEV *Product = SE->getMulExpr(AbsCoeff, UpperBound);
01802     if (isKnownPredicate(CmpInst::ICMP_SGT, NewDelta, Product)) {
01803       ++WeakZeroSIVindependence;
01804       ++WeakZeroSIVsuccesses;
01805       return true;
01806     }
01807     if (isKnownPredicate(CmpInst::ICMP_EQ, NewDelta, Product)) {
01808       // dependences caused by last iteration
01809       if (Level < CommonLevels) {
01810         Result.DV[Level].Direction &= Dependence::DVEntry::GE;
01811         Result.DV[Level].PeelLast = true;
01812         ++WeakZeroSIVsuccesses;
01813       }
01814       return false;
01815     }
01816   }
01817 
01818   // check that Delta/SrcCoeff >= 0
01819   // really check that NewDelta >= 0
01820   if (SE->isKnownNegative(NewDelta)) {
01821     // No dependence, newDelta < 0
01822     ++WeakZeroSIVindependence;
01823     ++WeakZeroSIVsuccesses;
01824     return true;
01825   }
01826 
01827   // if SrcCoeff doesn't divide Delta, then no dependence
01828   if (isa<SCEVConstant>(Delta) &&
01829       !isRemainderZero(cast<SCEVConstant>(Delta), ConstCoeff)) {
01830     ++WeakZeroSIVindependence;
01831     ++WeakZeroSIVsuccesses;
01832     return true;
01833   }
01834   return false;
01835 }
01836 
01837 
01838 // exactRDIVtest - Tests the RDIV subscript pair for dependence.
01839 // Things of the form [c1 + a*i] and [c2 + b*j],
01840 // where i and j are induction variable, c1 and c2 are loop invariant,
01841 // and a and b are constants.
01842 // Returns true if any possible dependence is disproved.
01843 // Marks the result as inconsistent.
01844 // Works in some cases that symbolicRDIVtest doesn't, and vice versa.
01845 bool DependenceAnalysis::exactRDIVtest(const SCEV *SrcCoeff,
01846                                        const SCEV *DstCoeff,
01847                                        const SCEV *SrcConst,
01848                                        const SCEV *DstConst,
01849                                        const Loop *SrcLoop,
01850                                        const Loop *DstLoop,
01851                                        FullDependence &Result) const {
01852   DEBUG(dbgs() << "\tExact RDIV test\n");
01853   DEBUG(dbgs() << "\t    SrcCoeff = " << *SrcCoeff << " = AM\n");
01854   DEBUG(dbgs() << "\t    DstCoeff = " << *DstCoeff << " = BM\n");
01855   DEBUG(dbgs() << "\t    SrcConst = " << *SrcConst << "\n");
01856   DEBUG(dbgs() << "\t    DstConst = " << *DstConst << "\n");
01857   ++ExactRDIVapplications;
01858   Result.Consistent = false;
01859   const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
01860   DEBUG(dbgs() << "\t    Delta = " << *Delta << "\n");
01861   const SCEVConstant *ConstDelta = dyn_cast<SCEVConstant>(Delta);
01862   const SCEVConstant *ConstSrcCoeff = dyn_cast<SCEVConstant>(SrcCoeff);
01863   const SCEVConstant *ConstDstCoeff = dyn_cast<SCEVConstant>(DstCoeff);
01864   if (!ConstDelta || !ConstSrcCoeff || !ConstDstCoeff)
01865     return false;
01866 
01867   // find gcd
01868   APInt G, X, Y;
01869   APInt AM = ConstSrcCoeff->getAPInt();
01870   APInt BM = ConstDstCoeff->getAPInt();
01871   unsigned Bits = AM.getBitWidth();
01872   if (findGCD(Bits, AM, BM, ConstDelta->getAPInt(), G, X, Y)) {
01873     // gcd doesn't divide Delta, no dependence
01874     ++ExactRDIVindependence;
01875     return true;
01876   }
01877 
01878   DEBUG(dbgs() << "\t    X = " << X << ", Y = " << Y << "\n");
01879 
01880   // since SCEV construction seems to normalize, LM = 0
01881   APInt SrcUM(Bits, 1, true);
01882   bool SrcUMvalid = false;
01883   // SrcUM is perhaps unavailable, let's check
01884   if (const SCEVConstant *UpperBound =
01885       collectConstantUpperBound(SrcLoop, Delta->getType())) {
01886     SrcUM = UpperBound->getAPInt();
01887     DEBUG(dbgs() << "\t    SrcUM = " << SrcUM << "\n");
01888     SrcUMvalid = true;
01889   }
01890 
01891   APInt DstUM(Bits, 1, true);
01892   bool DstUMvalid = false;
01893   // UM is perhaps unavailable, let's check
01894   if (const SCEVConstant *UpperBound =
01895       collectConstantUpperBound(DstLoop, Delta->getType())) {
01896     DstUM = UpperBound->getAPInt();
01897     DEBUG(dbgs() << "\t    DstUM = " << DstUM << "\n");
01898     DstUMvalid = true;
01899   }
01900 
01901   APInt TU(APInt::getSignedMaxValue(Bits));
01902   APInt TL(APInt::getSignedMinValue(Bits));
01903 
01904   // test(BM/G, LM-X) and test(-BM/G, X-UM)
01905   APInt TMUL = BM.sdiv(G);
01906   if (TMUL.sgt(0)) {
01907     TL = maxAPInt(TL, ceilingOfQuotient(-X, TMUL));
01908     DEBUG(dbgs() << "\t    TL = " << TL << "\n");
01909     if (SrcUMvalid) {
01910       TU = minAPInt(TU, floorOfQuotient(SrcUM - X, TMUL));
01911       DEBUG(dbgs() << "\t    TU = " << TU << "\n");
01912     }
01913   }
01914   else {
01915     TU = minAPInt(TU, floorOfQuotient(-X, TMUL));
01916     DEBUG(dbgs() << "\t    TU = " << TU << "\n");
01917     if (SrcUMvalid) {
01918       TL = maxAPInt(TL, ceilingOfQuotient(SrcUM - X, TMUL));
01919       DEBUG(dbgs() << "\t    TL = " << TL << "\n");
01920     }
01921   }
01922 
01923   // test(AM/G, LM-Y) and test(-AM/G, Y-UM)
01924   TMUL = AM.sdiv(G);
01925   if (TMUL.sgt(0)) {
01926     TL = maxAPInt(TL, ceilingOfQuotient(-Y, TMUL));
01927     DEBUG(dbgs() << "\t    TL = " << TL << "\n");
01928     if (DstUMvalid) {
01929       TU = minAPInt(TU, floorOfQuotient(DstUM - Y, TMUL));
01930       DEBUG(dbgs() << "\t    TU = " << TU << "\n");
01931     }
01932   }
01933   else {
01934     TU = minAPInt(TU, floorOfQuotient(-Y, TMUL));
01935     DEBUG(dbgs() << "\t    TU = " << TU << "\n");
01936     if (DstUMvalid) {
01937       TL = maxAPInt(TL, ceilingOfQuotient(DstUM - Y, TMUL));
01938       DEBUG(dbgs() << "\t    TL = " << TL << "\n");
01939     }
01940   }
01941   if (TL.sgt(TU))
01942     ++ExactRDIVindependence;
01943   return TL.sgt(TU);
01944 }
01945 
01946 
01947 // symbolicRDIVtest -
01948 // In Section 4.5 of the Practical Dependence Testing paper,the authors
01949 // introduce a special case of Banerjee's Inequalities (also called the
01950 // Extreme-Value Test) that can handle some of the SIV and RDIV cases,
01951 // particularly cases with symbolics. Since it's only able to disprove
01952 // dependence (not compute distances or directions), we'll use it as a
01953 // fall back for the other tests.
01954 //
01955 // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j]
01956 // where i and j are induction variables and c1 and c2 are loop invariants,
01957 // we can use the symbolic tests to disprove some dependences, serving as a
01958 // backup for the RDIV test. Note that i and j can be the same variable,
01959 // letting this test serve as a backup for the various SIV tests.
01960 //
01961 // For a dependence to exist, c1 + a1*i must equal c2 + a2*j for some
01962 //  0 <= i <= N1 and some 0 <= j <= N2, where N1 and N2 are the (normalized)
01963 // loop bounds for the i and j loops, respectively. So, ...
01964 //
01965 // c1 + a1*i = c2 + a2*j
01966 // a1*i - a2*j = c2 - c1
01967 //
01968 // To test for a dependence, we compute c2 - c1 and make sure it's in the
01969 // range of the maximum and minimum possible values of a1*i - a2*j.
01970 // Considering the signs of a1 and a2, we have 4 possible cases:
01971 //
01972 // 1) If a1 >= 0 and a2 >= 0, then
01973 //        a1*0 - a2*N2 <= c2 - c1 <= a1*N1 - a2*0
01974 //              -a2*N2 <= c2 - c1 <= a1*N1
01975 //
01976 // 2) If a1 >= 0 and a2 <= 0, then
01977 //        a1*0 - a2*0 <= c2 - c1 <= a1*N1 - a2*N2
01978 //                  0 <= c2 - c1 <= a1*N1 - a2*N2
01979 //
01980 // 3) If a1 <= 0 and a2 >= 0, then
01981 //        a1*N1 - a2*N2 <= c2 - c1 <= a1*0 - a2*0
01982 //        a1*N1 - a2*N2 <= c2 - c1 <= 0
01983 //
01984 // 4) If a1 <= 0 and a2 <= 0, then
01985 //        a1*N1 - a2*0  <= c2 - c1 <= a1*0 - a2*N2
01986 //        a1*N1         <= c2 - c1 <=       -a2*N2
01987 //
01988 // return true if dependence disproved
01989 bool DependenceAnalysis::symbolicRDIVtest(const SCEV *A1,
01990                                           const SCEV *A2,
01991                                           const SCEV *C1,
01992                                           const SCEV *C2,
01993                                           const Loop *Loop1,
01994                                           const Loop *Loop2) const {
01995   ++SymbolicRDIVapplications;
01996   DEBUG(dbgs() << "\ttry symbolic RDIV test\n");
01997   DEBUG(dbgs() << "\t    A1 = " << *A1);
01998   DEBUG(dbgs() << ", type = " << *A1->getType() << "\n");
01999   DEBUG(dbgs() << "\t    A2 = " << *A2 << "\n");
02000   DEBUG(dbgs() << "\t    C1 = " << *C1 << "\n");
02001   DEBUG(dbgs() << "\t    C2 = " << *C2 << "\n");
02002   const SCEV *N1 = collectUpperBound(Loop1, A1->getType());
02003   const SCEV *N2 = collectUpperBound(Loop2, A1->getType());
02004   DEBUG(if (N1) dbgs() << "\t    N1 = " << *N1 << "\n");
02005   DEBUG(if (N2) dbgs() << "\t    N2 = " << *N2 << "\n");
02006   const SCEV *C2_C1 = SE->getMinusSCEV(C2, C1);
02007   const SCEV *C1_C2 = SE->getMinusSCEV(C1, C2);
02008   DEBUG(dbgs() << "\t    C2 - C1 = " << *C2_C1 << "\n");
02009   DEBUG(dbgs() << "\t    C1 - C2 = " << *C1_C2 << "\n");
02010   if (SE->isKnownNonNegative(A1)) {
02011     if (SE->isKnownNonNegative(A2)) {
02012       // A1 >= 0 && A2 >= 0
02013       if (N1) {
02014         // make sure that c2 - c1 <= a1*N1
02015         const SCEV *A1N1 = SE->getMulExpr(A1, N1);
02016         DEBUG(dbgs() << "\t    A1*N1 = " << *A1N1 << "\n");
02017         if (isKnownPredicate(CmpInst::ICMP_SGT, C2_C1, A1N1)) {
02018           ++SymbolicRDIVindependence;
02019           return true;
02020         }
02021       }
02022       if (N2) {
02023         // make sure that -a2*N2 <= c2 - c1, or a2*N2 >= c1 - c2
02024         const SCEV *A2N2 = SE->getMulExpr(A2, N2);
02025         DEBUG(dbgs() << "\t    A2*N2 = " << *A2N2 << "\n");
02026         if (isKnownPredicate(CmpInst::ICMP_SLT, A2N2, C1_C2)) {
02027           ++SymbolicRDIVindependence;
02028           return true;
02029         }
02030       }
02031     }
02032     else if (SE->isKnownNonPositive(A2)) {
02033       // a1 >= 0 && a2 <= 0
02034       if (N1 && N2) {
02035         // make sure that c2 - c1 <= a1*N1 - a2*N2
02036         const SCEV *A1N1 = SE->getMulExpr(A1, N1);
02037         const SCEV *A2N2 = SE->getMulExpr(A2, N2);
02038         const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2);
02039         DEBUG(dbgs() << "\t    A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n");
02040         if (isKnownPredicate(CmpInst::ICMP_SGT, C2_C1, A1N1_A2N2)) {
02041           ++SymbolicRDIVindependence;
02042           return true;
02043         }
02044       }
02045       // make sure that 0 <= c2 - c1
02046       if (SE->isKnownNegative(C2_C1)) {
02047         ++SymbolicRDIVindependence;
02048         return true;
02049       }
02050     }
02051   }
02052   else if (SE->isKnownNonPositive(A1)) {
02053     if (SE->isKnownNonNegative(A2)) {
02054       // a1 <= 0 && a2 >= 0
02055       if (N1 && N2) {
02056         // make sure that a1*N1 - a2*N2 <= c2 - c1
02057         const SCEV *A1N1 = SE->getMulExpr(A1, N1);
02058         const SCEV *A2N2 = SE->getMulExpr(A2, N2);
02059         const SCEV *A1N1_A2N2 = SE->getMinusSCEV(A1N1, A2N2);
02060         DEBUG(dbgs() << "\t    A1*N1 - A2*N2 = " << *A1N1_A2N2 << "\n");
02061         if (isKnownPredicate(CmpInst::ICMP_SGT, A1N1_A2N2, C2_C1)) {
02062           ++SymbolicRDIVindependence;
02063           return true;
02064         }
02065       }
02066       // make sure that c2 - c1 <= 0
02067       if (SE->isKnownPositive(C2_C1)) {
02068         ++SymbolicRDIVindependence;
02069         return true;
02070       }
02071     }
02072     else if (SE->isKnownNonPositive(A2)) {
02073       // a1 <= 0 && a2 <= 0
02074       if (N1) {
02075         // make sure that a1*N1 <= c2 - c1
02076         const SCEV *A1N1 = SE->getMulExpr(A1, N1);
02077         DEBUG(dbgs() << "\t    A1*N1 = " << *A1N1 << "\n");
02078         if (isKnownPredicate(CmpInst::ICMP_SGT, A1N1, C2_C1)) {
02079           ++SymbolicRDIVindependence;
02080           return true;
02081         }
02082       }
02083       if (N2) {
02084         // make sure that c2 - c1 <= -a2*N2, or c1 - c2 >= a2*N2
02085         const SCEV *A2N2 = SE->getMulExpr(A2, N2);
02086         DEBUG(dbgs() << "\t    A2*N2 = " << *A2N2 << "\n");
02087         if (isKnownPredicate(CmpInst::ICMP_SLT, C1_C2, A2N2)) {
02088           ++SymbolicRDIVindependence;
02089           return true;
02090         }
02091       }
02092     }
02093   }
02094   return false;
02095 }
02096 
02097 
02098 // testSIV -
02099 // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 - a2*i]
02100 // where i is an induction variable, c1 and c2 are loop invariant, and a1 and
02101 // a2 are constant, we attack it with an SIV test. While they can all be
02102 // solved with the Exact SIV test, it's worthwhile to use simpler tests when
02103 // they apply; they're cheaper and sometimes more precise.
02104 //
02105 // Return true if dependence disproved.
02106 bool DependenceAnalysis::testSIV(const SCEV *Src,
02107                                  const SCEV *Dst,
02108                                  unsigned &Level,
02109                                  FullDependence &Result,
02110                                  Constraint &NewConstraint,
02111                                  const SCEV *&SplitIter) const {
02112   DEBUG(dbgs() << "    src = " << *Src << "\n");
02113   DEBUG(dbgs() << "    dst = " << *Dst << "\n");
02114   const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src);
02115   const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst);
02116   if (SrcAddRec && DstAddRec) {
02117     const SCEV *SrcConst = SrcAddRec->getStart();
02118     const SCEV *DstConst = DstAddRec->getStart();
02119     const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE);
02120     const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE);
02121     const Loop *CurLoop = SrcAddRec->getLoop();
02122     assert(CurLoop == DstAddRec->getLoop() &&
02123            "both loops in SIV should be same");
02124     Level = mapSrcLoop(CurLoop);
02125     bool disproven;
02126     if (SrcCoeff == DstCoeff)
02127       disproven = strongSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
02128                                 Level, Result, NewConstraint);
02129     else if (SrcCoeff == SE->getNegativeSCEV(DstCoeff))
02130       disproven = weakCrossingSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
02131                                       Level, Result, NewConstraint, SplitIter);
02132     else
02133       disproven = exactSIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop,
02134                                Level, Result, NewConstraint);
02135     return disproven ||
02136       gcdMIVtest(Src, Dst, Result) ||
02137       symbolicRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, CurLoop, CurLoop);
02138   }
02139   if (SrcAddRec) {
02140     const SCEV *SrcConst = SrcAddRec->getStart();
02141     const SCEV *SrcCoeff = SrcAddRec->getStepRecurrence(*SE);
02142     const SCEV *DstConst = Dst;
02143     const Loop *CurLoop = SrcAddRec->getLoop();
02144     Level = mapSrcLoop(CurLoop);
02145     return weakZeroDstSIVtest(SrcCoeff, SrcConst, DstConst, CurLoop,
02146                               Level, Result, NewConstraint) ||
02147       gcdMIVtest(Src, Dst, Result);
02148   }
02149   if (DstAddRec) {
02150     const SCEV *DstConst = DstAddRec->getStart();
02151     const SCEV *DstCoeff = DstAddRec->getStepRecurrence(*SE);
02152     const SCEV *SrcConst = Src;
02153     const Loop *CurLoop = DstAddRec->getLoop();
02154     Level = mapDstLoop(CurLoop);
02155     return weakZeroSrcSIVtest(DstCoeff, SrcConst, DstConst,
02156                               CurLoop, Level, Result, NewConstraint) ||
02157       gcdMIVtest(Src, Dst, Result);
02158   }
02159   llvm_unreachable("SIV test expected at least one AddRec");
02160   return false;
02161 }
02162 
02163 
02164 // testRDIV -
02165 // When we have a pair of subscripts of the form [c1 + a1*i] and [c2 + a2*j]
02166 // where i and j are induction variables, c1 and c2 are loop invariant,
02167 // and a1 and a2 are constant, we can solve it exactly with an easy adaptation
02168 // of the Exact SIV test, the Restricted Double Index Variable (RDIV) test.
02169 // It doesn't make sense to talk about distance or direction in this case,
02170 // so there's no point in making special versions of the Strong SIV test or
02171 // the Weak-crossing SIV test.
02172 //
02173 // With minor algebra, this test can also be used for things like
02174 // [c1 + a1*i + a2*j][c2].
02175 //
02176 // Return true if dependence disproved.
02177 bool DependenceAnalysis::testRDIV(const SCEV *Src,
02178                                   const SCEV *Dst,
02179                                   FullDependence &Result) const {
02180   // we have 3 possible situations here:
02181   //   1) [a*i + b] and [c*j + d]
02182   //   2) [a*i + c*j + b] and [d]
02183   //   3) [b] and [a*i + c*j + d]
02184   // We need to find what we've got and get organized
02185 
02186   const SCEV *SrcConst, *DstConst;
02187   const SCEV *SrcCoeff, *DstCoeff;
02188   const Loop *SrcLoop, *DstLoop;
02189 
02190   DEBUG(dbgs() << "    src = " << *Src << "\n");
02191   DEBUG(dbgs() << "    dst = " << *Dst << "\n");
02192   const SCEVAddRecExpr *SrcAddRec = dyn_cast<SCEVAddRecExpr>(Src);
02193   const SCEVAddRecExpr *DstAddRec = dyn_cast<SCEVAddRecExpr>(Dst);
02194   if (SrcAddRec && DstAddRec) {
02195     SrcConst = SrcAddRec->getStart();
02196     SrcCoeff = SrcAddRec->getStepRecurrence(*SE);
02197     SrcLoop = SrcAddRec->getLoop();
02198     DstConst = DstAddRec->getStart();
02199     DstCoeff = DstAddRec->getStepRecurrence(*SE);
02200     DstLoop = DstAddRec->getLoop();
02201   }
02202   else if (SrcAddRec) {
02203     if (const SCEVAddRecExpr *tmpAddRec =
02204         dyn_cast<SCEVAddRecExpr>(SrcAddRec->getStart())) {
02205       SrcConst = tmpAddRec->getStart();
02206       SrcCoeff = tmpAddRec->getStepRecurrence(*SE);
02207       SrcLoop = tmpAddRec->getLoop();
02208       DstConst = Dst;
02209       DstCoeff = SE->getNegativeSCEV(SrcAddRec->getStepRecurrence(*SE));
02210       DstLoop = SrcAddRec->getLoop();
02211     }
02212     else
02213       llvm_unreachable("RDIV reached by surprising SCEVs");
02214   }
02215   else if (DstAddRec) {
02216     if (const SCEVAddRecExpr *tmpAddRec =
02217         dyn_cast<SCEVAddRecExpr>(DstAddRec->getStart())) {
02218       DstConst = tmpAddRec->getStart();
02219       DstCoeff = tmpAddRec->getStepRecurrence(*SE);
02220       DstLoop = tmpAddRec->getLoop();
02221       SrcConst = Src;
02222       SrcCoeff = SE->getNegativeSCEV(DstAddRec->getStepRecurrence(*SE));
02223       SrcLoop = DstAddRec->getLoop();
02224     }
02225     else
02226       llvm_unreachable("RDIV reached by surprising SCEVs");
02227   }
02228   else
02229     llvm_unreachable("RDIV expected at least one AddRec");
02230   return exactRDIVtest(SrcCoeff, DstCoeff,
02231                        SrcConst, DstConst,
02232                        SrcLoop, DstLoop,
02233                        Result) ||
02234     gcdMIVtest(Src, Dst, Result) ||
02235     symbolicRDIVtest(SrcCoeff, DstCoeff,
02236                      SrcConst, DstConst,
02237                      SrcLoop, DstLoop);
02238 }
02239 
02240 
02241 // Tests the single-subscript MIV pair (Src and Dst) for dependence.
02242 // Return true if dependence disproved.
02243 // Can sometimes refine direction vectors.
02244 bool DependenceAnalysis::testMIV(const SCEV *Src,
02245                                  const SCEV *Dst,
02246                                  const SmallBitVector &Loops,
02247                                  FullDependence &Result) const {
02248   DEBUG(dbgs() << "    src = " << *Src << "\n");
02249   DEBUG(dbgs() << "    dst = " << *Dst << "\n");
02250   Result.Consistent = false;
02251   return gcdMIVtest(Src, Dst, Result) ||
02252     banerjeeMIVtest(Src, Dst, Loops, Result);
02253 }
02254 
02255 
02256 // Given a product, e.g., 10*X*Y, returns the first constant operand,
02257 // in this case 10. If there is no constant part, returns NULL.
02258 static
02259 const SCEVConstant *getConstantPart(const SCEVMulExpr *Product) {
02260   for (unsigned Op = 0, Ops = Product->getNumOperands(); Op < Ops; Op++) {
02261     if (const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Product->getOperand(Op)))
02262       return Constant;
02263   }
02264   return nullptr;
02265 }
02266 
02267 
02268 //===----------------------------------------------------------------------===//
02269 // gcdMIVtest -
02270 // Tests an MIV subscript pair for dependence.
02271 // Returns true if any possible dependence is disproved.
02272 // Marks the result as inconsistent.
02273 // Can sometimes disprove the equal direction for 1 or more loops,
02274 // as discussed in Michael Wolfe's book,
02275 // High Performance Compilers for Parallel Computing, page 235.
02276 //
02277 // We spend some effort (code!) to handle cases like
02278 // [10*i + 5*N*j + 15*M + 6], where i and j are induction variables,
02279 // but M and N are just loop-invariant variables.
02280 // This should help us handle linearized subscripts;
02281 // also makes this test a useful backup to the various SIV tests.
02282 //
02283 // It occurs to me that the presence of loop-invariant variables
02284 // changes the nature of the test from "greatest common divisor"
02285 // to "a common divisor".
02286 bool DependenceAnalysis::gcdMIVtest(const SCEV *Src,
02287                                     const SCEV *Dst,
02288                                     FullDependence &Result) const {
02289   DEBUG(dbgs() << "starting gcd\n");
02290   ++GCDapplications;
02291   unsigned BitWidth = SE->getTypeSizeInBits(Src->getType());
02292   APInt RunningGCD = APInt::getNullValue(BitWidth);
02293 
02294   // Examine Src coefficients.
02295   // Compute running GCD and record source constant.
02296   // Because we're looking for the constant at the end of the chain,
02297   // we can't quit the loop just because the GCD == 1.
02298   const SCEV *Coefficients = Src;
02299   while (const SCEVAddRecExpr *AddRec =
02300          dyn_cast<SCEVAddRecExpr>(Coefficients)) {
02301     const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
02302     const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Coeff);
02303     if (const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Coeff))
02304       // If the coefficient is the product of a constant and other stuff,
02305       // we can use the constant in the GCD computation.
02306       Constant = getConstantPart(Product);
02307     if (!Constant)
02308       return false;
02309     APInt ConstCoeff = Constant->getAPInt();
02310     RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs());
02311     Coefficients = AddRec->getStart();
02312   }
02313   const SCEV *SrcConst = Coefficients;
02314 
02315   // Examine Dst coefficients.
02316   // Compute running GCD and record destination constant.
02317   // Because we're looking for the constant at the end of the chain,
02318   // we can't quit the loop just because the GCD == 1.
02319   Coefficients = Dst;
02320   while (const SCEVAddRecExpr *AddRec =
02321          dyn_cast<SCEVAddRecExpr>(Coefficients)) {
02322     const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
02323     const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Coeff);
02324     if (const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Coeff))
02325       // If the coefficient is the product of a constant and other stuff,
02326       // we can use the constant in the GCD computation.
02327       Constant = getConstantPart(Product);
02328     if (!Constant)
02329       return false;
02330     APInt ConstCoeff = Constant->getAPInt();
02331     RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs());
02332     Coefficients = AddRec->getStart();
02333   }
02334   const SCEV *DstConst = Coefficients;
02335 
02336   APInt ExtraGCD = APInt::getNullValue(BitWidth);
02337   const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst);
02338   DEBUG(dbgs() << "    Delta = " << *Delta << "\n");
02339   const SCEVConstant *Constant = dyn_cast<SCEVConstant>(Delta);
02340   if (const SCEVAddExpr *Sum = dyn_cast<SCEVAddExpr>(Delta)) {
02341     // If Delta is a sum of products, we may be able to make further progress.
02342     for (unsigned Op = 0, Ops = Sum->getNumOperands(); Op < Ops; Op++) {
02343       const SCEV *Operand = Sum->getOperand(Op);
02344       if (isa<SCEVConstant>(Operand)) {
02345         assert(!Constant && "Surprised to find multiple constants");
02346         Constant = cast<SCEVConstant>(Operand);
02347       }
02348       else if (const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Operand)) {
02349         // Search for constant operand to participate in GCD;
02350         // If none found; return false.
02351         const SCEVConstant *ConstOp = getConstantPart(Product);
02352         if (!ConstOp)
02353           return false;
02354         APInt ConstOpValue = ConstOp->getAPInt();
02355         ExtraGCD = APIntOps::GreatestCommonDivisor(ExtraGCD,
02356                                                    ConstOpValue.abs());
02357       }
02358       else
02359         return false;
02360     }
02361   }
02362   if (!Constant)
02363     return false;
02364   APInt ConstDelta = cast<SCEVConstant>(Constant)->getAPInt();
02365   DEBUG(dbgs() << "    ConstDelta = " << ConstDelta << "\n");
02366   if (ConstDelta == 0)
02367     return false;
02368   RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ExtraGCD);
02369   DEBUG(dbgs() << "    RunningGCD = " << RunningGCD << "\n");
02370   APInt Remainder = ConstDelta.srem(RunningGCD);
02371   if (Remainder != 0) {
02372     ++GCDindependence;
02373     return true;
02374   }
02375 
02376   // Try to disprove equal directions.
02377   // For example, given a subscript pair [3*i + 2*j] and [i' + 2*j' - 1],
02378   // the code above can't disprove the dependence because the GCD = 1.
02379   // So we consider what happen if i = i' and what happens if j = j'.
02380   // If i = i', we can simplify the subscript to [2*i + 2*j] and [2*j' - 1],
02381   // which is infeasible, so we can disallow the = direction for the i level.
02382   // Setting j = j' doesn't help matters, so we end up with a direction vector
02383   // of [<>, *]
02384   //
02385   // Given A[5*i + 10*j*M + 9*M*N] and A[15*i + 20*j*M - 21*N*M + 5],
02386   // we need to remember that the constant part is 5 and the RunningGCD should
02387   // be initialized to ExtraGCD = 30.
02388   DEBUG(dbgs() << "    ExtraGCD = " << ExtraGCD << '\n');
02389 
02390   bool Improved = false;
02391   Coefficients = Src;
02392   while (const SCEVAddRecExpr *AddRec =
02393          dyn_cast<SCEVAddRecExpr>(Coefficients)) {
02394     Coefficients = AddRec->getStart();
02395     const Loop *CurLoop = AddRec->getLoop();
02396     RunningGCD = ExtraGCD;
02397     const SCEV *SrcCoeff = AddRec->getStepRecurrence(*SE);
02398     const SCEV *DstCoeff = SE->getMinusSCEV(SrcCoeff, SrcCoeff);
02399     const SCEV *Inner = Src;
02400     while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) {
02401       AddRec = cast<SCEVAddRecExpr>(Inner);
02402       const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
02403       if (CurLoop == AddRec->getLoop())
02404         ; // SrcCoeff == Coeff
02405       else {
02406         if (const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Coeff))
02407           // If the coefficient is the product of a constant and other stuff,
02408           // we can use the constant in the GCD computation.
02409           Constant = getConstantPart(Product);
02410         else
02411           Constant = cast<SCEVConstant>(Coeff);
02412         APInt ConstCoeff = Constant->getAPInt();
02413         RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs());
02414       }
02415       Inner = AddRec->getStart();
02416     }
02417     Inner = Dst;
02418     while (RunningGCD != 1 && isa<SCEVAddRecExpr>(Inner)) {
02419       AddRec = cast<SCEVAddRecExpr>(Inner);
02420       const SCEV *Coeff = AddRec->getStepRecurrence(*SE);
02421       if (CurLoop == AddRec->getLoop())
02422         DstCoeff = Coeff;
02423       else {
02424         if (const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Coeff))
02425           // If the coefficient is the product of a constant and other stuff,
02426           // we can use the constant in the GCD computation.
02427           Constant = getConstantPart(Product);
02428         else
02429           Constant = cast<SCEVConstant>(Coeff);
02430         APInt ConstCoeff = Constant->getAPInt();
02431         RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs());
02432       }
02433       Inner = AddRec->getStart();
02434     }
02435     Delta = SE->getMinusSCEV(SrcCoeff, DstCoeff);
02436     if (const SCEVMulExpr *Product = dyn_cast<SCEVMulExpr>(Delta))
02437       // If the coefficient is the product of a constant and other stuff,
02438       // we can use the constant in the GCD computation.
02439       Constant = getConstantPart(Product);
02440     else if (isa<SCEVConstant>(Delta))
02441       Constant = cast<SCEVConstant>(Delta);
02442     else {
02443       // The difference of the two coefficients might not be a product
02444       // or constant, in which case we give up on this direction.
02445       continue;
02446     }
02447     APInt ConstCoeff = Constant->getAPInt();
02448     RunningGCD = APIntOps::GreatestCommonDivisor(RunningGCD, ConstCoeff.abs());
02449     DEBUG(dbgs() << "\tRunningGCD = " << RunningGCD << "\n");
02450     if (RunningGCD != 0) {
02451       Remainder = ConstDelta.srem(RunningGCD);
02452       DEBUG(dbgs() << "\tRemainder = " << Remainder << "\n");
02453       if (Remainder != 0) {
02454         unsigned Level = mapSrcLoop(CurLoop);
02455         Result.DV[Level - 1].Direction &= unsigned(~Dependence::DVEntry::EQ);
02456         Improved = true;
02457       }
02458     }
02459   }
02460   if (Improved)
02461     ++GCDsuccesses;
02462   DEBUG(dbgs() << "all done\n");
02463   return false;
02464 }
02465 
02466 
02467 //===----------------------------------------------------------------------===//
02468 // banerjeeMIVtest -
02469 // Use Banerjee's Inequalities to test an MIV subscript pair.
02470 // (Wolfe, in the race-car book, calls this the Extreme Value Test.)
02471 // Generally follows the discussion in Section 2.5.2 of
02472 //
02473 //    Optimizing Supercompilers for Supercomputers
02474 //    Michael Wolfe
02475 //
02476 // The inequalities given on page 25 are simplified in that loops are
02477 // normalized so that the lower bound is always 0 and the stride is always 1.
02478 // For example, Wolfe gives
02479 //
02480 //     LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
02481 //
02482 // where A_k is the coefficient of the kth index in the source subscript,
02483 // B_k is the coefficient of the kth index in the destination subscript,
02484 // U_k is the upper bound of the kth index, L_k is the lower bound of the Kth
02485 // index, and N_k is the stride of the kth index. Since all loops are normalized
02486 // by the SCEV package, N_k = 1 and L_k = 0, allowing us to simplify the
02487 // equation to
02488 //
02489 //     LB^<_k = (A^-_k - B_k)^- (U_k - 0 - 1) + (A_k - B_k)0 - B_k 1
02490 //            = (A^-_k - B_k)^- (U_k - 1)  - B_k
02491 //
02492 // Similar simplifications are possible for the other equations.
02493 //
02494 // When we can't determine the number of iterations for a loop,
02495 // we use NULL as an indicator for the worst case, infinity.
02496 // When computing the upper bound, NULL denotes +inf;
02497 // for the lower bound, NULL denotes -inf.
02498 //
02499 // Return true if dependence disproved.
02500 bool DependenceAnalysis::banerjeeMIVtest(const SCEV *Src,
02501                                          const SCEV *Dst,
02502                                          const SmallBitVector &Loops,
02503                                          FullDependence &Result) const {
02504   DEBUG(dbgs() << "starting Banerjee\n");
02505   ++BanerjeeApplications;
02506   DEBUG(dbgs() << "    Src = " << *Src << '\n');
02507   const SCEV *A0;
02508   CoefficientInfo *A = collectCoeffInfo(Src, true, A0);
02509   DEBUG(dbgs() << "    Dst = " << *Dst << '\n');
02510   const SCEV *B0;
02511   CoefficientInfo *B = collectCoeffInfo(Dst, false, B0);
02512   BoundInfo *Bound = new BoundInfo[MaxLevels + 1];
02513   const SCEV *Delta = SE->getMinusSCEV(B0, A0);
02514   DEBUG(dbgs() << "\tDelta = " << *Delta << '\n');
02515 
02516   // Compute bounds for all the * directions.
02517   DEBUG(dbgs() << "\tBounds[*]\n");
02518   for (unsigned K = 1; K <= MaxLevels; ++K) {
02519     Bound[K].Iterations = A[K].Iterations ? A[K].Iterations : B[K].Iterations;
02520     Bound[K].Direction = Dependence::DVEntry::ALL;
02521     Bound[K].DirSet = Dependence::DVEntry::NONE;
02522     findBoundsALL(A, B, Bound, K);
02523 #ifndef NDEBUG
02524     DEBUG(dbgs() << "\t    " << K << '\t');
02525     if (Bound[K].Lower[Dependence::DVEntry::ALL])
02526       DEBUG(dbgs() << *Bound[K].Lower[Dependence::DVEntry::ALL] << '\t');
02527     else
02528       DEBUG(dbgs() << "-inf\t");
02529     if (Bound[K].Upper[Dependence::DVEntry::ALL])
02530       DEBUG(dbgs() << *Bound[K].Upper[Dependence::DVEntry::ALL] << '\n');
02531     else
02532       DEBUG(dbgs() << "+inf\n");
02533 #endif
02534   }
02535 
02536   // Test the *, *, *, ... case.
02537   bool Disproved = false;
02538   if (testBounds(Dependence::DVEntry::ALL, 0, Bound, Delta)) {
02539     // Explore the direction vector hierarchy.
02540     unsigned DepthExpanded = 0;
02541     unsigned NewDeps = exploreDirections(1, A, B, Bound,
02542                                          Loops, DepthExpanded, Delta);
02543     if (NewDeps > 0) {
02544       bool Improved = false;
02545       for (unsigned K = 1; K <= CommonLevels; ++K) {
02546         if (Loops[K]) {
02547           unsigned Old = Result.DV[K - 1].Direction;
02548           Result.DV[K - 1].Direction = Old & Bound[K].DirSet;
02549           Improved |= Old != Result.DV[K - 1].Direction;
02550           if (!Result.DV[K - 1].Direction) {
02551             Improved = false;
02552             Disproved = true;
02553             break;
02554           }
02555         }
02556       }
02557       if (Improved)
02558         ++BanerjeeSuccesses;
02559     }
02560     else {
02561       ++BanerjeeIndependence;
02562       Disproved = true;
02563     }
02564   }
02565   else {
02566     ++BanerjeeIndependence;
02567     Disproved = true;
02568   }
02569   delete [] Bound;
02570   delete [] A;
02571   delete [] B;
02572   return Disproved;
02573 }
02574 
02575 
02576 // Hierarchically expands the direction vector
02577 // search space, combining the directions of discovered dependences
02578 // in the DirSet field of Bound. Returns the number of distinct
02579 // dependences discovered. If the dependence is disproved,
02580 // it will return 0.
02581 unsigned DependenceAnalysis::exploreDirections(unsigned Level,
02582                                                CoefficientInfo *A,
02583                                                CoefficientInfo *B,
02584                                                BoundInfo *Bound,
02585                                                const SmallBitVector &Loops,
02586                                                unsigned &DepthExpanded,
02587                                                const SCEV *Delta) const {
02588   if (Level > CommonLevels) {
02589     // record result
02590     DEBUG(dbgs() << "\t[");
02591     for (unsigned K = 1; K <= CommonLevels; ++K) {
02592       if (Loops[K]) {
02593         Bound[K].DirSet |= Bound[K].Direction;
02594 #ifndef NDEBUG
02595         switch (Bound[K].Direction) {
02596         case Dependence::DVEntry::LT:
02597           DEBUG(dbgs() << " <");
02598           break;
02599         case Dependence::DVEntry::EQ:
02600           DEBUG(dbgs() << " =");
02601           break;
02602         case Dependence::DVEntry::GT:
02603           DEBUG(dbgs() << " >");
02604           break;
02605         case Dependence::DVEntry::ALL:
02606           DEBUG(dbgs() << " *");
02607           break;
02608         default:
02609           llvm_unreachable("unexpected Bound[K].Direction");
02610         }
02611 #endif
02612       }
02613     }
02614     DEBUG(dbgs() << " ]\n");
02615     return 1;
02616   }
02617   if (Loops[Level]) {
02618     if (Level > DepthExpanded) {
02619       DepthExpanded = Level;
02620       // compute bounds for <, =, > at current level
02621       findBoundsLT(A, B, Bound, Level);
02622       findBoundsGT(A, B, Bound, Level);
02623       findBoundsEQ(A, B, Bound, Level);
02624 #ifndef NDEBUG
02625       DEBUG(dbgs() << "\tBound for level = " << Level << '\n');
02626       DEBUG(dbgs() << "\t    <\t");
02627       if (Bound[Level].Lower[Dependence::DVEntry::LT])
02628         DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::LT] << '\t');
02629       else
02630         DEBUG(dbgs() << "-inf\t");
02631       if (Bound[Level].Upper[Dependence::DVEntry::LT])
02632         DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::LT] << '\n');
02633       else
02634         DEBUG(dbgs() << "+inf\n");
02635       DEBUG(dbgs() << "\t    =\t");
02636       if (Bound[Level].Lower[Dependence::DVEntry::EQ])
02637         DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::EQ] << '\t');
02638       else
02639         DEBUG(dbgs() << "-inf\t");
02640       if (Bound[Level].Upper[Dependence::DVEntry::EQ])
02641         DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::EQ] << '\n');
02642       else
02643         DEBUG(dbgs() << "+inf\n");
02644       DEBUG(dbgs() << "\t    >\t");
02645       if (Bound[Level].Lower[Dependence::DVEntry::GT])
02646         DEBUG(dbgs() << *Bound[Level].Lower[Dependence::DVEntry::GT] << '\t');
02647       else
02648         DEBUG(dbgs() << "-inf\t");
02649       if (Bound[Level].Upper[Dependence::DVEntry::GT])
02650         DEBUG(dbgs() << *Bound[Level].Upper[Dependence::DVEntry::GT] << '\n');
02651       else
02652         DEBUG(dbgs() << "+inf\n");
02653 #endif
02654     }
02655 
02656     unsigned NewDeps = 0;
02657 
02658     // test bounds for <, *, *, ...
02659     if (testBounds(Dependence::DVEntry::LT, Level, Bound, Delta))
02660       NewDeps += exploreDirections(Level + 1, A, B, Bound,
02661                                    Loops, DepthExpanded, Delta);
02662 
02663     // Test bounds for =, *, *, ...
02664     if (testBounds(Dependence::DVEntry::EQ, Level, Bound, Delta))
02665       NewDeps += exploreDirections(Level + 1, A, B, Bound,
02666                                    Loops, DepthExpanded, Delta);
02667 
02668     // test bounds for >, *, *, ...
02669     if (testBounds(Dependence::DVEntry::GT, Level, Bound, Delta))
02670       NewDeps += exploreDirections(Level + 1, A, B, Bound,
02671                                    Loops, DepthExpanded, Delta);
02672 
02673     Bound[Level].Direction = Dependence::DVEntry::ALL;
02674     return NewDeps;
02675   }
02676   else
02677     return exploreDirections(Level + 1, A, B, Bound, Loops, DepthExpanded, Delta);
02678 }
02679 
02680 
02681 // Returns true iff the current bounds are plausible.
02682 bool DependenceAnalysis::testBounds(unsigned char DirKind,
02683                                     unsigned Level,
02684                                     BoundInfo *Bound,
02685                                     const SCEV *Delta) const {
02686   Bound[Level].Direction = DirKind;
02687   if (const SCEV *LowerBound = getLowerBound(Bound))
02688     if (isKnownPredicate(CmpInst::ICMP_SGT, LowerBound, Delta))
02689       return false;
02690   if (const SCEV *UpperBound = getUpperBound(Bound))
02691     if (isKnownPredicate(CmpInst::ICMP_SGT, Delta, UpperBound))
02692       return false;
02693   return true;
02694 }
02695 
02696 
02697 // Computes the upper and lower bounds for level K
02698 // using the * direction. Records them in Bound.
02699 // Wolfe gives the equations
02700 //
02701 //    LB^*_k = (A^-_k - B^+_k)(U_k - L_k) + (A_k - B_k)L_k
02702 //    UB^*_k = (A^+_k - B^-_k)(U_k - L_k) + (A_k - B_k)L_k
02703 //
02704 // Since we normalize loops, we can simplify these equations to
02705 //
02706 //    LB^*_k = (A^-_k - B^+_k)U_k
02707 //    UB^*_k = (A^+_k - B^-_k)U_k
02708 //
02709 // We must be careful to handle the case where the upper bound is unknown.
02710 // Note that the lower bound is always <= 0
02711 // and the upper bound is always >= 0.
02712 void DependenceAnalysis::findBoundsALL(CoefficientInfo *A,
02713                                        CoefficientInfo *B,
02714                                        BoundInfo *Bound,
02715                                        unsigned K) const {
02716   Bound[K].Lower[Dependence::DVEntry::ALL] = nullptr; // Default value = -infinity.
02717   Bound[K].Upper[Dependence::DVEntry::ALL] = nullptr; // Default value = +infinity.
02718   if (Bound[K].Iterations) {
02719     Bound[K].Lower[Dependence::DVEntry::ALL] =
02720       SE->getMulExpr(SE->getMinusSCEV(A[K].NegPart, B[K].PosPart),
02721                      Bound[K].Iterations);
02722     Bound[K].Upper[Dependence::DVEntry::ALL] =
02723       SE->getMulExpr(SE->getMinusSCEV(A[K].PosPart, B[K].NegPart),
02724                      Bound[K].Iterations);
02725   }
02726   else {
02727     // If the difference is 0, we won't need to know the number of iterations.
02728     if (isKnownPredicate(CmpInst::ICMP_EQ, A[K].NegPart, B[K].PosPart))
02729       Bound[K].Lower[Dependence::DVEntry::ALL] =
02730           SE->getZero(A[K].Coeff->getType());
02731     if (isKnownPredicate(CmpInst::ICMP_EQ, A[K].PosPart, B[K].NegPart))
02732       Bound[K].Upper[Dependence::DVEntry::ALL] =
02733           SE->getZero(A[K].Coeff->getType());
02734   }
02735 }
02736 
02737 
02738 // Computes the upper and lower bounds for level K
02739 // using the = direction. Records them in Bound.
02740 // Wolfe gives the equations
02741 //
02742 //    LB^=_k = (A_k - B_k)^- (U_k - L_k) + (A_k - B_k)L_k
02743 //    UB^=_k = (A_k - B_k)^+ (U_k - L_k) + (A_k - B_k)L_k
02744 //
02745 // Since we normalize loops, we can simplify these equations to
02746 //
02747 //    LB^=_k = (A_k - B_k)^- U_k
02748 //    UB^=_k = (A_k - B_k)^+ U_k
02749 //
02750 // We must be careful to handle the case where the upper bound is unknown.
02751 // Note that the lower bound is always <= 0
02752 // and the upper bound is always >= 0.
02753 void DependenceAnalysis::findBoundsEQ(CoefficientInfo *A,
02754                                       CoefficientInfo *B,
02755                                       BoundInfo *Bound,
02756                                       unsigned K) const {
02757   Bound[K].Lower[Dependence::DVEntry::EQ] = nullptr; // Default value = -infinity.
02758   Bound[K].Upper[Dependence::DVEntry::EQ] = nullptr; // Default value = +infinity.
02759   if (Bound[K].Iterations) {
02760     const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff);
02761     const SCEV *NegativePart = getNegativePart(Delta);
02762     Bound[K].Lower[Dependence::DVEntry::EQ] =
02763       SE->getMulExpr(NegativePart, Bound[K].Iterations);
02764     const SCEV *PositivePart = getPositivePart(Delta);
02765     Bound[K].Upper[Dependence::DVEntry::EQ] =
02766       SE->getMulExpr(PositivePart, Bound[K].Iterations);
02767   }
02768   else {
02769     // If the positive/negative part of the difference is 0,
02770     // we won't need to know the number of iterations.
02771     const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff);
02772     const SCEV *NegativePart = getNegativePart(Delta);
02773     if (NegativePart->isZero())
02774       Bound[K].Lower[Dependence::DVEntry::EQ] = NegativePart; // Zero
02775     const SCEV *PositivePart = getPositivePart(Delta);
02776     if (PositivePart->isZero())
02777       Bound[K].Upper[Dependence::DVEntry::EQ] = PositivePart; // Zero
02778   }
02779 }
02780 
02781 
02782 // Computes the upper and lower bounds for level K
02783 // using the < direction. Records them in Bound.
02784 // Wolfe gives the equations
02785 //
02786 //    LB^<_k = (A^-_k - B_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
02787 //    UB^<_k = (A^+_k - B_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k - B_k N_k
02788 //
02789 // Since we normalize loops, we can simplify these equations to
02790 //
02791 //    LB^<_k = (A^-_k - B_k)^- (U_k - 1) - B_k
02792 //    UB^<_k = (A^+_k - B_k)^+ (U_k - 1) - B_k
02793 //
02794 // We must be careful to handle the case where the upper bound is unknown.
02795 void DependenceAnalysis::findBoundsLT(CoefficientInfo *A,
02796                                       CoefficientInfo *B,
02797                                       BoundInfo *Bound,
02798                                       unsigned K) const {
02799   Bound[K].Lower[Dependence::DVEntry::LT] = nullptr; // Default value = -infinity.
02800   Bound[K].Upper[Dependence::DVEntry::LT] = nullptr; // Default value = +infinity.
02801   if (Bound[K].Iterations) {
02802     const SCEV *Iter_1 = SE->getMinusSCEV(
02803         Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));
02804     const SCEV *NegPart =
02805       getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff));
02806     Bound[K].Lower[Dependence::DVEntry::LT] =
02807       SE->getMinusSCEV(SE->getMulExpr(NegPart, Iter_1), B[K].Coeff);
02808     const SCEV *PosPart =
02809       getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff));
02810     Bound[K].Upper[Dependence::DVEntry::LT] =
02811       SE->getMinusSCEV(SE->getMulExpr(PosPart, Iter_1), B[K].Coeff);
02812   }
02813   else {
02814     // If the positive/negative part of the difference is 0,
02815     // we won't need to know the number of iterations.
02816     const SCEV *NegPart =
02817       getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff));
02818     if (NegPart->isZero())
02819       Bound[K].Lower[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff);
02820     const SCEV *PosPart =
02821       getPositivePart(SE->getMinusSCEV(A[K].PosPart, B[K].Coeff));
02822     if (PosPart->isZero())
02823       Bound[K].Upper[Dependence::DVEntry::LT] = SE->getNegativeSCEV(B[K].Coeff);
02824   }
02825 }
02826 
02827 
02828 // Computes the upper and lower bounds for level K
02829 // using the > direction. Records them in Bound.
02830 // Wolfe gives the equations
02831 //
02832 //    LB^>_k = (A_k - B^+_k)^- (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k
02833 //    UB^>_k = (A_k - B^-_k)^+ (U_k - L_k - N_k) + (A_k - B_k)L_k + A_k N_k
02834 //
02835 // Since we normalize loops, we can simplify these equations to
02836 //
02837 //    LB^>_k = (A_k - B^+_k)^- (U_k - 1) + A_k
02838 //    UB^>_k = (A_k - B^-_k)^+ (U_k - 1) + A_k
02839 //
02840 // We must be careful to handle the case where the upper bound is unknown.
02841 void DependenceAnalysis::findBoundsGT(CoefficientInfo *A,
02842                                       CoefficientInfo *B,
02843                                       BoundInfo *Bound,
02844                                       unsigned K) const {
02845   Bound[K].Lower[Dependence::DVEntry::GT] = nullptr; // Default value = -infinity.
02846   Bound[K].Upper[Dependence::DVEntry::GT] = nullptr; // Default value = +infinity.
02847   if (Bound[K].Iterations) {
02848     const SCEV *Iter_1 = SE->getMinusSCEV(
02849         Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType()));
02850     const SCEV *NegPart =
02851       getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart));
02852     Bound[K].Lower[Dependence::DVEntry::GT] =
02853       SE->getAddExpr(SE->getMulExpr(NegPart, Iter_1), A[K].Coeff);
02854     const SCEV *PosPart =
02855       getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart));
02856     Bound[K].Upper[Dependence::DVEntry::GT] =
02857       SE->getAddExpr(SE->getMulExpr(PosPart, Iter_1), A[K].Coeff);
02858   }
02859   else {
02860     // If the positive/negative part of the difference is 0,
02861     // we won't need to know the number of iterations.
02862     const SCEV *NegPart = getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart));
02863     if (NegPart->isZero())
02864       Bound[K].Lower[Dependence::DVEntry::GT] = A[K].Coeff;
02865     const SCEV *PosPart = getPositivePart(SE->getMinusSCEV(A[K].Coeff, B[K].NegPart));
02866     if (PosPart->isZero())
02867       Bound[K].Upper[Dependence::DVEntry::GT] = A[K].Coeff;
02868   }
02869 }
02870 
02871 
02872 // X^+ = max(X, 0)
02873 const SCEV *DependenceAnalysis::getPositivePart(const SCEV *X) const {
02874   return SE->getSMaxExpr(X, SE->getZero(X->getType()));
02875 }
02876 
02877 
02878 // X^- = min(X, 0)
02879 const SCEV *DependenceAnalysis::getNegativePart(const SCEV *X) const {
02880   return SE->getSMinExpr(X, SE->getZero(X->getType()));
02881 }
02882 
02883 
02884 // Walks through the subscript,
02885 // collecting each coefficient, the associated loop bounds,
02886 // and recording its positive and negative parts for later use.
02887 DependenceAnalysis::CoefficientInfo *
02888 DependenceAnalysis::collectCoeffInfo(const SCEV *Subscript,
02889                                      bool SrcFlag,
02890                                      const SCEV *&Constant) const {
02891   const SCEV *Zero = SE->getZero(Subscript->getType());
02892   CoefficientInfo *CI = new CoefficientInfo[MaxLevels + 1];
02893   for (unsigned K = 1; K <= MaxLevels; ++K) {
02894     CI[K].Coeff = Zero;
02895     CI[K].PosPart = Zero;
02896     CI[K].NegPart = Zero;
02897     CI[K].Iterations = nullptr;
02898   }
02899   while (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Subscript)) {
02900     const Loop *L = AddRec->getLoop();
02901     unsigned K = SrcFlag ? mapSrcLoop(L) : mapDstLoop(L);
02902     CI[K].Coeff = AddRec->getStepRecurrence(*SE);
02903     CI[K].PosPart = getPositivePart(CI[K].Coeff);
02904     CI[K].NegPart = getNegativePart(CI[K].Coeff);
02905     CI[K].Iterations = collectUpperBound(L, Subscript->getType());
02906     Subscript = AddRec->getStart();
02907   }
02908   Constant = Subscript;
02909 #ifndef NDEBUG
02910   DEBUG(dbgs() << "\tCoefficient Info\n");
02911   for (unsigned K = 1; K <= MaxLevels; ++K) {
02912     DEBUG(dbgs() << "\t    " << K << "\t" << *CI[K].Coeff);
02913     DEBUG(dbgs() << "\tPos Part = ");
02914     DEBUG(dbgs() << *CI[K].PosPart);
02915     DEBUG(dbgs() << "\tNeg Part = ");
02916     DEBUG(dbgs() << *CI[K].NegPart);
02917     DEBUG(dbgs() << "\tUpper Bound = ");
02918     if (CI[K].Iterations)
02919       DEBUG(dbgs() << *CI[K].Iterations);
02920     else
02921       DEBUG(dbgs() << "+inf");
02922     DEBUG(dbgs() << '\n');
02923   }
02924   DEBUG(dbgs() << "\t    Constant = " << *Subscript << '\n');
02925 #endif
02926   return CI;
02927 }
02928 
02929 
02930 // Looks through all the bounds info and
02931 // computes the lower bound given the current direction settings
02932 // at each level. If the lower bound for any level is -inf,
02933 // the result is -inf.
02934 const SCEV *DependenceAnalysis::getLowerBound(BoundInfo *Bound) const {
02935   const SCEV *Sum = Bound[1].Lower[Bound[1].Direction];
02936   for (unsigned K = 2; Sum && K <= MaxLevels; ++K) {
02937     if (Bound[K].Lower[Bound[K].Direction])
02938       Sum = SE->getAddExpr(Sum, Bound[K].Lower[Bound[K].Direction]);
02939     else
02940       Sum = nullptr;
02941   }
02942   return Sum;
02943 }
02944 
02945 
02946 // Looks through all the bounds info and
02947 // computes the upper bound given the current direction settings
02948 // at each level. If the upper bound at any level is +inf,
02949 // the result is +inf.
02950 const SCEV *DependenceAnalysis::getUpperBound(BoundInfo *Bound) const {
02951   const SCEV *Sum = Bound[1].Upper[Bound[1].Direction];
02952   for (unsigned K = 2; Sum && K <= MaxLevels; ++K) {
02953     if (Bound[K].Upper[Bound[K].Direction])
02954       Sum = SE->getAddExpr(Sum, Bound[K].Upper[Bound[K].Direction]);
02955     else
02956       Sum = nullptr;
02957   }
02958   return Sum;
02959 }
02960 
02961 
02962 //===----------------------------------------------------------------------===//
02963 // Constraint manipulation for Delta test.
02964 
02965 // Given a linear SCEV,
02966 // return the coefficient (the step)
02967 // corresponding to the specified loop.
02968 // If there isn't one, return 0.
02969 // For example, given a*i + b*j + c*k, finding the coefficient
02970 // corresponding to the j loop would yield b.
02971 const SCEV *DependenceAnalysis::findCoefficient(const SCEV *Expr,
02972                                                 const Loop *TargetLoop)  const {
02973   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
02974   if (!AddRec)
02975     return SE->getZero(Expr->getType());
02976   if (AddRec->getLoop() == TargetLoop)
02977     return AddRec->getStepRecurrence(*SE);
02978   return findCoefficient(AddRec->getStart(), TargetLoop);
02979 }
02980 
02981 
02982 // Given a linear SCEV,
02983 // return the SCEV given by zeroing out the coefficient
02984 // corresponding to the specified loop.
02985 // For example, given a*i + b*j + c*k, zeroing the coefficient
02986 // corresponding to the j loop would yield a*i + c*k.
02987 const SCEV *DependenceAnalysis::zeroCoefficient(const SCEV *Expr,
02988                                                 const Loop *TargetLoop)  const {
02989   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
02990   if (!AddRec)
02991     return Expr; // ignore
02992   if (AddRec->getLoop() == TargetLoop)
02993     return AddRec->getStart();
02994   return SE->getAddRecExpr(zeroCoefficient(AddRec->getStart(), TargetLoop),
02995                            AddRec->getStepRecurrence(*SE),
02996                            AddRec->getLoop(),
02997                            AddRec->getNoWrapFlags());
02998 }
02999 
03000 
03001 // Given a linear SCEV Expr,
03002 // return the SCEV given by adding some Value to the
03003 // coefficient corresponding to the specified TargetLoop.
03004 // For example, given a*i + b*j + c*k, adding 1 to the coefficient
03005 // corresponding to the j loop would yield a*i + (b+1)*j + c*k.
03006 const SCEV *DependenceAnalysis::addToCoefficient(const SCEV *Expr,
03007                                                  const Loop *TargetLoop,
03008                                                  const SCEV *Value)  const {
03009   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Expr);
03010   if (!AddRec) // create a new addRec
03011     return SE->getAddRecExpr(Expr,
03012                              Value,
03013                              TargetLoop,
03014                              SCEV::FlagAnyWrap); // Worst case, with no info.
03015   if (AddRec->getLoop() == TargetLoop) {
03016     const SCEV *Sum = SE->getAddExpr(AddRec->getStepRecurrence(*SE), Value);
03017     if (Sum->isZero())
03018       return AddRec->getStart();
03019     return SE->getAddRecExpr(AddRec->getStart(),
03020                              Sum,
03021                              AddRec->getLoop(),
03022                              AddRec->getNoWrapFlags());
03023   }
03024   if (SE->isLoopInvariant(AddRec, TargetLoop))
03025     return SE->getAddRecExpr(AddRec, Value, TargetLoop, SCEV::FlagAnyWrap);
03026   return SE->getAddRecExpr(
03027       addToCoefficient(AddRec->getStart(), TargetLoop, Value),
03028       AddRec->getStepRecurrence(*SE), AddRec->getLoop(),
03029       AddRec->getNoWrapFlags());
03030 }
03031 
03032 
03033 // Review the constraints, looking for opportunities
03034 // to simplify a subscript pair (Src and Dst).
03035 // Return true if some simplification occurs.
03036 // If the simplification isn't exact (that is, if it is conservative
03037 // in terms of dependence), set consistent to false.
03038 // Corresponds to Figure 5 from the paper
03039 //
03040 //            Practical Dependence Testing
03041 //            Goff, Kennedy, Tseng
03042 //            PLDI 1991
03043 bool DependenceAnalysis::propagate(const SCEV *&Src,
03044                                    const SCEV *&Dst,
03045                                    SmallBitVector &Loops,
03046                                    SmallVectorImpl<Constraint> &Constraints,
03047                                    bool &Consistent) {
03048   bool Result = false;
03049   for (int LI = Loops.find_first(); LI >= 0; LI = Loops.find_next(LI)) {
03050     DEBUG(dbgs() << "\t    Constraint[" << LI << "] is");
03051     DEBUG(Constraints[LI].dump(dbgs()));
03052     if (Constraints[LI].isDistance())
03053       Result |= propagateDistance(Src, Dst, Constraints[LI], Consistent);
03054     else if (Constraints[LI].isLine())
03055       Result |= propagateLine(Src, Dst, Constraints[LI], Consistent);
03056     else if (Constraints[LI].isPoint())
03057       Result |= propagatePoint(Src, Dst, Constraints[LI]);
03058   }
03059   return Result;
03060 }
03061 
03062 
03063 // Attempt to propagate a distance
03064 // constraint into a subscript pair (Src and Dst).
03065 // Return true if some simplification occurs.
03066 // If the simplification isn't exact (that is, if it is conservative
03067 // in terms of dependence), set consistent to false.
03068 bool DependenceAnalysis::propagateDistance(const SCEV *&Src,
03069                                            const SCEV *&Dst,
03070                                            Constraint &CurConstraint,
03071                                            bool &Consistent) {
03072   const Loop *CurLoop = CurConstraint.getAssociatedLoop();
03073   DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n");
03074   const SCEV *A_K = findCoefficient(Src, CurLoop);
03075   if (A_K->isZero())
03076     return false;
03077   const SCEV *DA_K = SE->getMulExpr(A_K, CurConstraint.getD());
03078   Src = SE->getMinusSCEV(Src, DA_K);
03079   Src = zeroCoefficient(Src, CurLoop);
03080   DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n");
03081   DEBUG(dbgs() << "\t\tDst is " << *Dst << "\n");
03082   Dst = addToCoefficient(Dst, CurLoop, SE->getNegativeSCEV(A_K));
03083   DEBUG(dbgs() << "\t\tnew Dst is " << *Dst << "\n");
03084   if (!findCoefficient(Dst, CurLoop)->isZero())
03085     Consistent = false;
03086   return true;
03087 }
03088 
03089 
03090 // Attempt to propagate a line
03091 // constraint into a subscript pair (Src and Dst).
03092 // Return true if some simplification occurs.
03093 // If the simplification isn't exact (that is, if it is conservative
03094 // in terms of dependence), set consistent to false.
03095 bool DependenceAnalysis::propagateLine(const SCEV *&Src,
03096                                        const SCEV *&Dst,
03097                                        Constraint &CurConstraint,
03098                                        bool &Consistent) {
03099   const Loop *CurLoop = CurConstraint.getAssociatedLoop();
03100   const SCEV *A = CurConstraint.getA();
03101   const SCEV *B = CurConstraint.getB();
03102   const SCEV *C = CurConstraint.getC();
03103   DEBUG(dbgs() << "\t\tA = " << *A << ", B = " << *B << ", C = " << *C << "\n");
03104   DEBUG(dbgs() << "\t\tSrc = " << *Src << "\n");
03105   DEBUG(dbgs() << "\t\tDst = " << *Dst << "\n");
03106   if (A->isZero()) {
03107     const SCEVConstant *Bconst = dyn_cast<SCEVConstant>(B);
03108     const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C);
03109     if (!Bconst || !Cconst) return false;
03110     APInt Beta = Bconst->getAPInt();
03111     APInt Charlie = Cconst->getAPInt();
03112     APInt CdivB = Charlie.sdiv(Beta);
03113     assert(Charlie.srem(Beta) == 0 && "C should be evenly divisible by B");
03114     const SCEV *AP_K = findCoefficient(Dst, CurLoop);
03115     //    Src = SE->getAddExpr(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB)));
03116     Src = SE->getMinusSCEV(Src, SE->getMulExpr(AP_K, SE->getConstant(CdivB)));
03117     Dst = zeroCoefficient(Dst, CurLoop);
03118     if (!findCoefficient(Src, CurLoop)->isZero())
03119       Consistent = false;
03120   }
03121   else if (B->isZero()) {
03122     const SCEVConstant *Aconst = dyn_cast<SCEVConstant>(A);
03123     const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C);
03124     if (!Aconst || !Cconst) return false;
03125     APInt Alpha = Aconst->getAPInt();
03126     APInt Charlie = Cconst->getAPInt();
03127     APInt CdivA = Charlie.sdiv(Alpha);
03128     assert(Charlie.srem(Alpha) == 0 && "C should be evenly divisible by A");
03129     const SCEV *A_K = findCoefficient(Src, CurLoop);
03130     Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA)));
03131     Src = zeroCoefficient(Src, CurLoop);
03132     if (!findCoefficient(Dst, CurLoop)->isZero())
03133       Consistent = false;
03134   }
03135   else if (isKnownPredicate(CmpInst::ICMP_EQ, A, B)) {
03136     const SCEVConstant *Aconst = dyn_cast<SCEVConstant>(A);
03137     const SCEVConstant *Cconst = dyn_cast<SCEVConstant>(C);
03138     if (!Aconst || !Cconst) return false;
03139     APInt Alpha = Aconst->getAPInt();
03140     APInt Charlie = Cconst->getAPInt();
03141     APInt CdivA = Charlie.sdiv(Alpha);
03142     assert(Charlie.srem(Alpha) == 0 && "C should be evenly divisible by A");
03143     const SCEV *A_K = findCoefficient(Src, CurLoop);
03144     Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, SE->getConstant(CdivA)));
03145     Src = zeroCoefficient(Src, CurLoop);
03146     Dst = addToCoefficient(Dst, CurLoop, A_K);
03147     if (!findCoefficient(Dst, CurLoop)->isZero())
03148       Consistent = false;
03149   }
03150   else {
03151     // paper is incorrect here, or perhaps just misleading
03152     const SCEV *A_K = findCoefficient(Src, CurLoop);
03153     Src = SE->getMulExpr(Src, A);
03154     Dst = SE->getMulExpr(Dst, A);
03155     Src = SE->getAddExpr(Src, SE->getMulExpr(A_K, C));
03156     Src = zeroCoefficient(Src, CurLoop);
03157     Dst = addToCoefficient(Dst, CurLoop, SE->getMulExpr(A_K, B));
03158     if (!findCoefficient(Dst, CurLoop)->isZero())
03159       Consistent = false;
03160   }
03161   DEBUG(dbgs() << "\t\tnew Src = " << *Src << "\n");
03162   DEBUG(dbgs() << "\t\tnew Dst = " << *Dst << "\n");
03163   return true;
03164 }
03165 
03166 
03167 // Attempt to propagate a point
03168 // constraint into a subscript pair (Src and Dst).
03169 // Return true if some simplification occurs.
03170 bool DependenceAnalysis::propagatePoint(const SCEV *&Src,
03171                                         const SCEV *&Dst,
03172                                         Constraint &CurConstraint) {
03173   const Loop *CurLoop = CurConstraint.getAssociatedLoop();
03174   const SCEV *A_K = findCoefficient(Src, CurLoop);
03175   const SCEV *AP_K = findCoefficient(Dst, CurLoop);
03176   const SCEV *XA_K = SE->getMulExpr(A_K, CurConstraint.getX());
03177   const SCEV *YAP_K = SE->getMulExpr(AP_K, CurConstraint.getY());
03178   DEBUG(dbgs() << "\t\tSrc is " << *Src << "\n");
03179   Src = SE->getAddExpr(Src, SE->getMinusSCEV(XA_K, YAP_K));
03180   Src = zeroCoefficient(Src, CurLoop);
03181   DEBUG(dbgs() << "\t\tnew Src is " << *Src << "\n");
03182   DEBUG(dbgs() << "\t\tDst is " << *Dst << "\n");
03183   Dst = zeroCoefficient(Dst, CurLoop);
03184   DEBUG(dbgs() << "\t\tnew Dst is " << *Dst << "\n");
03185   return true;
03186 }
03187 
03188 
03189 // Update direction vector entry based on the current constraint.
03190 void DependenceAnalysis::updateDirection(Dependence::DVEntry &Level,
03191                                          const Constraint &CurConstraint
03192                                          ) const {
03193   DEBUG(dbgs() << "\tUpdate direction, constraint =");
03194   DEBUG(CurConstraint.dump(dbgs()));
03195   if (CurConstraint.isAny())
03196     ; // use defaults
03197   else if (CurConstraint.isDistance()) {
03198     // this one is consistent, the others aren't
03199     Level.Scalar = false;
03200     Level.Distance = CurConstraint.getD();
03201     unsigned NewDirection = Dependence::DVEntry::NONE;
03202     if (!SE->isKnownNonZero(Level.Distance)) // if may be zero
03203       NewDirection = Dependence::DVEntry::EQ;
03204     if (!SE->isKnownNonPositive(Level.Distance)) // if may be positive
03205       NewDirection |= Dependence::DVEntry::LT;
03206     if (!SE->isKnownNonNegative(Level.Distance)) // if may be negative
03207       NewDirection |= Dependence::DVEntry::GT;
03208     Level.Direction &= NewDirection;
03209   }
03210   else if (CurConstraint.isLine()) {
03211     Level.Scalar = false;
03212     Level.Distance = nullptr;
03213     // direction should be accurate
03214   }
03215   else if (CurConstraint.isPoint()) {
03216     Level.Scalar = false;
03217     Level.Distance = nullptr;
03218     unsigned NewDirection = Dependence::DVEntry::NONE;
03219     if (!isKnownPredicate(CmpInst::ICMP_NE,
03220                           CurConstraint.getY(),
03221                           CurConstraint.getX()))
03222       // if X may be = Y
03223       NewDirection |= Dependence::DVEntry::EQ;
03224     if (!isKnownPredicate(CmpInst::ICMP_SLE,
03225                           CurConstraint.getY(),
03226                           CurConstraint.getX()))
03227       // if Y may be > X
03228       NewDirection |= Dependence::DVEntry::LT;
03229     if (!isKnownPredicate(CmpInst::ICMP_SGE,
03230                           CurConstraint.getY(),
03231                           CurConstraint.getX()))
03232       // if Y may be < X
03233       NewDirection |= Dependence::DVEntry::GT;
03234     Level.Direction &= NewDirection;
03235   }
03236   else
03237     llvm_unreachable("constraint has unexpected kind");
03238 }
03239 
03240 /// Check if we can delinearize the subscripts. If the SCEVs representing the
03241 /// source and destination array references are recurrences on a nested loop,
03242 /// this function flattens the nested recurrences into separate recurrences
03243 /// for each loop level.
03244 bool DependenceAnalysis::tryDelinearize(Instruction *Src,
03245                                         Instruction *Dst,
03246                                         SmallVectorImpl<Subscript> &Pair)
03247 {
03248   Value *SrcPtr = getPointerOperand(Src);
03249   Value *DstPtr = getPointerOperand(Dst);
03250 
03251   Loop *SrcLoop = LI->getLoopFor(Src->getParent());
03252   Loop *DstLoop = LI->getLoopFor(Dst->getParent());
03253 
03254   // Below code mimics the code in Delinearization.cpp
03255   const SCEV *SrcAccessFn =
03256     SE->getSCEVAtScope(SrcPtr, SrcLoop);
03257   const SCEV *DstAccessFn =
03258     SE->getSCEVAtScope(DstPtr, DstLoop);
03259 
03260   const SCEVUnknown *SrcBase =
03261       dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcAccessFn));
03262   const SCEVUnknown *DstBase =
03263       dyn_cast<SCEVUnknown>(SE->getPointerBase(DstAccessFn));
03264 
03265   if (!SrcBase || !DstBase || SrcBase != DstBase)
03266     return false;
03267 
03268   const SCEV *ElementSize = SE->getElementSize(Src);
03269   if (ElementSize != SE->getElementSize(Dst))
03270     return false;
03271 
03272   const SCEV *SrcSCEV = SE->getMinusSCEV(SrcAccessFn, SrcBase);
03273   const SCEV *DstSCEV = SE->getMinusSCEV(DstAccessFn, DstBase);
03274 
03275   const SCEVAddRecExpr *SrcAR = dyn_cast<SCEVAddRecExpr>(SrcSCEV);
03276   const SCEVAddRecExpr *DstAR = dyn_cast<SCEVAddRecExpr>(DstSCEV);
03277   if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine())
03278     return false;
03279 
03280   // First step: collect parametric terms in both array references.
03281   SmallVector<const SCEV *, 4> Terms;
03282   SE->collectParametricTerms(SrcAR, Terms);
03283   SE->collectParametricTerms(DstAR, Terms);
03284 
03285   // Second step: find subscript sizes.
03286   SmallVector<const SCEV *, 4> Sizes;
03287   SE->findArrayDimensions(Terms, Sizes, ElementSize);
03288 
03289   // Third step: compute the access functions for each subscript.
03290   SmallVector<const SCEV *, 4> SrcSubscripts, DstSubscripts;
03291   SE->computeAccessFunctions(SrcAR, SrcSubscripts, Sizes);
03292   SE->computeAccessFunctions(DstAR, DstSubscripts, Sizes);
03293 
03294   // Fail when there is only a subscript: that's a linearized access function.
03295   if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 ||
03296       SrcSubscripts.size() != DstSubscripts.size())
03297     return false;
03298 
03299   int size = SrcSubscripts.size();
03300 
03301   DEBUG({
03302       dbgs() << "\nSrcSubscripts: ";
03303     for (int i = 0; i < size; i++)
03304       dbgs() << *SrcSubscripts[i];
03305     dbgs() << "\nDstSubscripts: ";
03306     for (int i = 0; i < size; i++)
03307       dbgs() << *DstSubscripts[i];
03308     });
03309 
03310   // The delinearization transforms a single-subscript MIV dependence test into
03311   // a multi-subscript SIV dependence test that is easier to compute. So we
03312   // resize Pair to contain as many pairs of subscripts as the delinearization
03313   // has found, and then initialize the pairs following the delinearization.
03314   Pair.resize(size);
03315   for (int i = 0; i < size; ++i) {
03316     Pair[i].Src = SrcSubscripts[i];
03317     Pair[i].Dst = DstSubscripts[i];
03318     unifySubscriptType(&Pair[i]);
03319 
03320     // FIXME: we should record the bounds SrcSizes[i] and DstSizes[i] that the
03321     // delinearization has found, and add these constraints to the dependence
03322     // check to avoid memory accesses overflow from one dimension into another.
03323     // This is related to the problem of determining the existence of data
03324     // dependences in array accesses using a different number of subscripts: in
03325     // C one can access an array A[100][100]; as A[0][9999], *A[9999], etc.
03326   }
03327 
03328   return true;
03329 }
03330 
03331 //===----------------------------------------------------------------------===//
03332 
03333 #ifndef NDEBUG
03334 // For debugging purposes, dump a small bit vector to dbgs().
03335 static void dumpSmallBitVector(SmallBitVector &BV) {
03336   dbgs() << "{";
03337   for (int VI = BV.find_first(); VI >= 0; VI = BV.find_next(VI)) {
03338     dbgs() << VI;
03339     if (BV.find_next(VI) >= 0)
03340       dbgs() << ' ';
03341   }
03342   dbgs() << "}\n";
03343 }
03344 #endif
03345 
03346 // depends -
03347 // Returns NULL if there is no dependence.
03348 // Otherwise, return a Dependence with as many details as possible.
03349 // Corresponds to Section 3.1 in the paper
03350 //
03351 //            Practical Dependence Testing
03352 //            Goff, Kennedy, Tseng
03353 //            PLDI 1991
03354 //
03355 // Care is required to keep the routine below, getSplitIteration(),
03356 // up to date with respect to this routine.
03357 std::unique_ptr<Dependence>
03358 DependenceAnalysis::depends(Instruction *Src, Instruction *Dst,
03359                             bool PossiblyLoopIndependent) {
03360   if (Src == Dst)
03361     PossiblyLoopIndependent = false;
03362 
03363   if ((!Src->mayReadFromMemory() && !Src->mayWriteToMemory()) ||
03364       (!Dst->mayReadFromMemory() && !Dst->mayWriteToMemory()))
03365     // if both instructions don't reference memory, there's no dependence
03366     return nullptr;
03367 
03368   if (!isLoadOrStore(Src) || !isLoadOrStore(Dst)) {
03369     // can only analyze simple loads and stores, i.e., no calls, invokes, etc.
03370     DEBUG(dbgs() << "can only handle simple loads and stores\n");
03371     return make_unique<Dependence>(Src, Dst);
03372   }
03373 
03374   Value *SrcPtr = getPointerOperand(Src);
03375   Value *DstPtr = getPointerOperand(Dst);
03376 
03377   switch (underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), DstPtr,
03378                                  SrcPtr)) {
03379   case MayAlias:
03380   case PartialAlias:
03381     // cannot analyse objects if we don't understand their aliasing.
03382     DEBUG(dbgs() << "can't analyze may or partial alias\n");
03383     return make_unique<Dependence>(Src, Dst);
03384   case NoAlias:
03385     // If the objects noalias, they are distinct, accesses are independent.
03386     DEBUG(dbgs() << "no alias\n");
03387     return nullptr;
03388   case MustAlias:
03389     break; // The underlying objects alias; test accesses for dependence.
03390   }
03391 
03392   // establish loop nesting levels
03393   establishNestingLevels(Src, Dst);
03394   DEBUG(dbgs() << "    common nesting levels = " << CommonLevels << "\n");
03395   DEBUG(dbgs() << "    maximum nesting levels = " << MaxLevels << "\n");
03396 
03397   FullDependence Result(Src, Dst, PossiblyLoopIndependent, CommonLevels);
03398   ++TotalArrayPairs;
03399 
03400   // See if there are GEPs we can use.
03401   bool UsefulGEP = false;
03402   GEPOperator *SrcGEP = dyn_cast<GEPOperator>(SrcPtr);
03403   GEPOperator *DstGEP = dyn_cast<GEPOperator>(DstPtr);
03404   if (SrcGEP && DstGEP &&
03405       SrcGEP->getPointerOperandType() == DstGEP->getPointerOperandType()) {
03406     const SCEV *SrcPtrSCEV = SE->getSCEV(SrcGEP->getPointerOperand());
03407     const SCEV *DstPtrSCEV = SE->getSCEV(DstGEP->getPointerOperand());
03408     DEBUG(dbgs() << "    SrcPtrSCEV = " << *SrcPtrSCEV << "\n");
03409     DEBUG(dbgs() << "    DstPtrSCEV = " << *DstPtrSCEV << "\n");
03410 
03411     UsefulGEP = isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) &&
03412                 isLoopInvariant(DstPtrSCEV, LI->getLoopFor(Dst->getParent())) &&
03413                 (SrcGEP->getNumOperands() == DstGEP->getNumOperands());
03414   }
03415   unsigned Pairs = UsefulGEP ? SrcGEP->idx_end() - SrcGEP->idx_begin() : 1;
03416   SmallVector<Subscript, 4> Pair(Pairs);
03417   if (UsefulGEP) {
03418     DEBUG(dbgs() << "    using GEPs\n");
03419     unsigned P = 0;
03420     for (GEPOperator::const_op_iterator SrcIdx = SrcGEP->idx_begin(),
03421            SrcEnd = SrcGEP->idx_end(),
03422            DstIdx = DstGEP->idx_begin();
03423          SrcIdx != SrcEnd;
03424          ++SrcIdx, ++DstIdx, ++P) {
03425       Pair[P].Src = SE->getSCEV(*SrcIdx);
03426       Pair[P].Dst = SE->getSCEV(*DstIdx);
03427       unifySubscriptType(&Pair[P]);
03428     }
03429   }
03430   else {
03431     DEBUG(dbgs() << "    ignoring GEPs\n");
03432     const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
03433     const SCEV *DstSCEV = SE->getSCEV(DstPtr);
03434     DEBUG(dbgs() << "    SrcSCEV = " << *SrcSCEV << "\n");
03435     DEBUG(dbgs() << "    DstSCEV = " << *DstSCEV << "\n");
03436     Pair[0].Src = SrcSCEV;
03437     Pair[0].Dst = DstSCEV;
03438   }
03439 
03440   if (Delinearize && CommonLevels > 1) {
03441     if (tryDelinearize(Src, Dst, Pair)) {
03442       DEBUG(dbgs() << "    delinerized GEP\n");
03443       Pairs = Pair.size();
03444     }
03445   }
03446 
03447   for (unsigned P = 0; P < Pairs; ++P) {
03448     Pair[P].Loops.resize(MaxLevels + 1);
03449     Pair[P].GroupLoops.resize(MaxLevels + 1);
03450     Pair[P].Group.resize(Pairs);
03451     removeMatchingExtensions(&Pair[P]);
03452     Pair[P].Classification =
03453       classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),
03454                    Pair[P].Dst, LI->getLoopFor(Dst->getParent()),
03455                    Pair[P].Loops);
03456     Pair[P].GroupLoops = Pair[P].Loops;
03457     Pair[P].Group.set(P);
03458     DEBUG(dbgs() << "    subscript " << P << "\n");
03459     DEBUG(dbgs() << "\tsrc = " << *Pair[P].Src << "\n");
03460     DEBUG(dbgs() << "\tdst = " << *Pair[P].Dst << "\n");
03461     DEBUG(dbgs() << "\tclass = " << Pair[P].Classification << "\n");
03462     DEBUG(dbgs() << "\tloops = ");
03463     DEBUG(dumpSmallBitVector(Pair[P].Loops));
03464   }
03465 
03466   SmallBitVector Separable(Pairs);
03467   SmallBitVector Coupled(Pairs);
03468 
03469   // Partition subscripts into separable and minimally-coupled groups
03470   // Algorithm in paper is algorithmically better;
03471   // this may be faster in practice. Check someday.
03472   //
03473   // Here's an example of how it works. Consider this code:
03474   //
03475   //   for (i = ...) {
03476   //     for (j = ...) {
03477   //       for (k = ...) {
03478   //         for (l = ...) {
03479   //           for (m = ...) {
03480   //             A[i][j][k][m] = ...;
03481   //             ... = A[0][j][l][i + j];
03482   //           }
03483   //         }
03484   //       }
03485   //     }
03486   //   }
03487   //
03488   // There are 4 subscripts here:
03489   //    0 [i] and [0]
03490   //    1 [j] and [j]
03491   //    2 [k] and [l]
03492   //    3 [m] and [i + j]
03493   //
03494   // We've already classified each subscript pair as ZIV, SIV, etc.,
03495   // and collected all the loops mentioned by pair P in Pair[P].Loops.
03496   // In addition, we've initialized Pair[P].GroupLoops to Pair[P].Loops
03497   // and set Pair[P].Group = {P}.
03498   //
03499   //      Src Dst    Classification Loops  GroupLoops Group
03500   //    0 [i] [0]         SIV       {1}      {1}        {0}
03501   //    1 [j] [j]         SIV       {2}      {2}        {1}
03502   //    2 [k] [l]         RDIV      {3,4}    {3,4}      {2}
03503   //    3 [m] [i + j]     MIV       {1,2,5}  {1,2,5}    {3}
03504   //
03505   // For each subscript SI 0 .. 3, we consider each remaining subscript, SJ.
03506   // So, 0 is compared against 1, 2, and 3; 1 is compared against 2 and 3, etc.
03507   //
03508   // We begin by comparing 0 and 1. The intersection of the GroupLoops is empty.
03509   // Next, 0 and 2. Again, the intersection of their GroupLoops is empty.
03510   // Next 0 and 3. The intersection of their GroupLoop = {1}, not empty,
03511   // so Pair[3].Group = {0,3} and Done = false (that is, 0 will not be added
03512   // to either Separable or Coupled).
03513   //
03514   // Next, we consider 1 and 2. The intersection of the GroupLoops is empty.
03515   // Next, 1 and 3. The intersectionof their GroupLoops = {2}, not empty,
03516   // so Pair[3].Group = {0, 1, 3} and Done = false.
03517   //
03518   // Next, we compare 2 against 3. The intersection of the GroupLoops is empty.
03519   // Since Done remains true, we add 2 to the set of Separable pairs.
03520   //
03521   // Finally, we consider 3. There's nothing to compare it with,
03522   // so Done remains true and we add it to the Coupled set.
03523   // Pair[3].Group = {0, 1, 3} and GroupLoops = {1, 2, 5}.
03524   //
03525   // In the end, we've got 1 separable subscript and 1 coupled group.
03526   for (unsigned SI = 0; SI < Pairs; ++SI) {
03527     if (Pair[SI].Classification == Subscript::NonLinear) {
03528       // ignore these, but collect loops for later
03529       ++NonlinearSubscriptPairs;
03530       collectCommonLoops(Pair[SI].Src,
03531                          LI->getLoopFor(Src->getParent()),
03532                          Pair[SI].Loops);
03533       collectCommonLoops(Pair[SI].Dst,
03534                          LI->getLoopFor(Dst->getParent()),
03535                          Pair[SI].Loops);
03536       Result.Consistent = false;
03537     } else if (Pair[SI].Classification == Subscript::ZIV) {
03538       // always separable
03539       Separable.set(SI);
03540     }
03541     else {
03542       // SIV, RDIV, or MIV, so check for coupled group
03543       bool Done = true;
03544       for (unsigned SJ = SI + 1; SJ < Pairs; ++SJ) {
03545         SmallBitVector Intersection = Pair[SI].GroupLoops;
03546         Intersection &= Pair[SJ].GroupLoops;
03547         if (Intersection.any()) {
03548           // accumulate set of all the loops in group
03549           Pair[SJ].GroupLoops |= Pair[SI].GroupLoops;
03550           // accumulate set of all subscripts in group
03551           Pair[SJ].Group |= Pair[SI].Group;
03552           Done = false;
03553         }
03554       }
03555       if (Done) {
03556         if (Pair[SI].Group.count() == 1) {
03557           Separable.set(SI);
03558           ++SeparableSubscriptPairs;
03559         }
03560         else {
03561           Coupled.set(SI);
03562           ++CoupledSubscriptPairs;
03563         }
03564       }
03565     }
03566   }
03567 
03568   DEBUG(dbgs() << "    Separable = ");
03569   DEBUG(dumpSmallBitVector(Separable));
03570   DEBUG(dbgs() << "    Coupled = ");
03571   DEBUG(dumpSmallBitVector(Coupled));
03572 
03573   Constraint NewConstraint;
03574   NewConstraint.setAny(SE);
03575 
03576   // test separable subscripts
03577   for (int SI = Separable.find_first(); SI >= 0; SI = Separable.find_next(SI)) {
03578     DEBUG(dbgs() << "testing subscript " << SI);
03579     switch (Pair[SI].Classification) {
03580     case Subscript::ZIV:
03581       DEBUG(dbgs() << ", ZIV\n");
03582       if (testZIV(Pair[SI].Src, Pair[SI].Dst, Result))
03583         return nullptr;
03584       break;
03585     case Subscript::SIV: {
03586       DEBUG(dbgs() << ", SIV\n");
03587       unsigned Level;
03588       const SCEV *SplitIter = nullptr;
03589       if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level, Result, NewConstraint,
03590                   SplitIter))
03591         return nullptr;
03592       break;
03593     }
03594     case Subscript::RDIV:
03595       DEBUG(dbgs() << ", RDIV\n");
03596       if (testRDIV(Pair[SI].Src, Pair[SI].Dst, Result))
03597         return nullptr;
03598       break;
03599     case Subscript::MIV:
03600       DEBUG(dbgs() << ", MIV\n");
03601       if (testMIV(Pair[SI].Src, Pair[SI].Dst, Pair[SI].Loops, Result))
03602         return nullptr;
03603       break;
03604     default:
03605       llvm_unreachable("subscript has unexpected classification");
03606     }
03607   }
03608 
03609   if (Coupled.count()) {
03610     // test coupled subscript groups
03611     DEBUG(dbgs() << "starting on coupled subscripts\n");
03612     DEBUG(dbgs() << "MaxLevels + 1 = " << MaxLevels + 1 << "\n");
03613     SmallVector<Constraint, 4> Constraints(MaxLevels + 1);
03614     for (unsigned II = 0; II <= MaxLevels; ++II)
03615       Constraints[II].setAny(SE);
03616     for (int SI = Coupled.find_first(); SI >= 0; SI = Coupled.find_next(SI)) {
03617       DEBUG(dbgs() << "testing subscript group " << SI << " { ");
03618       SmallBitVector Group(Pair[SI].Group);
03619       SmallBitVector Sivs(Pairs);
03620       SmallBitVector Mivs(Pairs);
03621       SmallBitVector ConstrainedLevels(MaxLevels + 1);
03622       SmallVector<Subscript *, 4> PairsInGroup;
03623       for (int SJ = Group.find_first(); SJ >= 0; SJ = Group.find_next(SJ)) {
03624         DEBUG(dbgs() << SJ << " ");
03625         if (Pair[SJ].Classification == Subscript::SIV)
03626           Sivs.set(SJ);
03627         else
03628           Mivs.set(SJ);
03629         PairsInGroup.push_back(&Pair[SJ]);
03630       }
03631       unifySubscriptType(PairsInGroup);
03632       DEBUG(dbgs() << "}\n");
03633       while (Sivs.any()) {
03634         bool Changed = false;
03635         for (int SJ = Sivs.find_first(); SJ >= 0; SJ = Sivs.find_next(SJ)) {
03636           DEBUG(dbgs() << "testing subscript " << SJ << ", SIV\n");
03637           // SJ is an SIV subscript that's part of the current coupled group
03638           unsigned Level;
03639           const SCEV *SplitIter = nullptr;
03640           DEBUG(dbgs() << "SIV\n");
03641           if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint,
03642                       SplitIter))
03643             return nullptr;
03644           ConstrainedLevels.set(Level);
03645           if (intersectConstraints(&Constraints[Level], &NewConstraint)) {
03646             if (Constraints[Level].isEmpty()) {
03647               ++DeltaIndependence;
03648               return nullptr;
03649             }
03650             Changed = true;
03651           }
03652           Sivs.reset(SJ);
03653         }
03654         if (Changed) {
03655           // propagate, possibly creating new SIVs and ZIVs
03656           DEBUG(dbgs() << "    propagating\n");
03657           DEBUG(dbgs() << "\tMivs = ");
03658           DEBUG(dumpSmallBitVector(Mivs));
03659           for (int SJ = Mivs.find_first(); SJ >= 0; SJ = Mivs.find_next(SJ)) {
03660             // SJ is an MIV subscript that's part of the current coupled group
03661             DEBUG(dbgs() << "\tSJ = " << SJ << "\n");
03662             if (propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops,
03663                           Constraints, Result.Consistent)) {
03664               DEBUG(dbgs() << "\t    Changed\n");
03665               ++DeltaPropagations;
03666               Pair[SJ].Classification =
03667                 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()),
03668                              Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()),
03669                              Pair[SJ].Loops);
03670               switch (Pair[SJ].Classification) {
03671               case Subscript::ZIV:
03672                 DEBUG(dbgs() << "ZIV\n");
03673                 if (testZIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
03674                   return nullptr;
03675                 Mivs.reset(SJ);
03676                 break;
03677               case Subscript::SIV:
03678                 Sivs.set(SJ);
03679                 Mivs.reset(SJ);
03680                 break;
03681               case Subscript::RDIV:
03682               case Subscript::MIV:
03683                 break;
03684               default:
03685                 llvm_unreachable("bad subscript classification");
03686               }
03687             }
03688           }
03689         }
03690       }
03691 
03692       // test & propagate remaining RDIVs
03693       for (int SJ = Mivs.find_first(); SJ >= 0; SJ = Mivs.find_next(SJ)) {
03694         if (Pair[SJ].Classification == Subscript::RDIV) {
03695           DEBUG(dbgs() << "RDIV test\n");
03696           if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result))
03697             return nullptr;
03698           // I don't yet understand how to propagate RDIV results
03699           Mivs.reset(SJ);
03700         }
03701       }
03702 
03703       // test remaining MIVs
03704       // This code is temporary.
03705       // Better to somehow test all remaining subscripts simultaneously.
03706       for (int SJ = Mivs.find_first(); SJ >= 0; SJ = Mivs.find_next(SJ)) {
03707         if (Pair[SJ].Classification == Subscript::MIV) {
03708           DEBUG(dbgs() << "MIV test\n");
03709           if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops, Result))
03710             return nullptr;
03711         }
03712         else
03713           llvm_unreachable("expected only MIV subscripts at this point");
03714       }
03715 
03716       // update Result.DV from constraint vector
03717       DEBUG(dbgs() << "    updating\n");
03718       for (int SJ = ConstrainedLevels.find_first(); SJ >= 0;
03719            SJ = ConstrainedLevels.find_next(SJ)) {
03720         if (SJ > (int)CommonLevels)
03721           break;
03722         updateDirection(Result.DV[SJ - 1], Constraints[SJ]);
03723         if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE)
03724           return nullptr;
03725       }
03726     }
03727   }
03728 
03729   // Make sure the Scalar flags are set correctly.
03730   SmallBitVector CompleteLoops(MaxLevels + 1);
03731   for (unsigned SI = 0; SI < Pairs; ++SI)
03732     CompleteLoops |= Pair[SI].Loops;
03733   for (unsigned II = 1; II <= CommonLevels; ++II)
03734     if (CompleteLoops[II])
03735       Result.DV[II - 1].Scalar = false;
03736 
03737   if (PossiblyLoopIndependent) {
03738     // Make sure the LoopIndependent flag is set correctly.
03739     // All directions must include equal, otherwise no
03740     // loop-independent dependence is possible.
03741     for (unsigned II = 1; II <= CommonLevels; ++II) {
03742       if (!(Result.getDirection(II) & Dependence::DVEntry::EQ)) {
03743         Result.LoopIndependent = false;
03744         break;
03745       }
03746     }
03747   }
03748   else {
03749     // On the other hand, if all directions are equal and there's no
03750     // loop-independent dependence possible, then no dependence exists.
03751     bool AllEqual = true;
03752     for (unsigned II = 1; II <= CommonLevels; ++II) {
03753       if (Result.getDirection(II) != Dependence::DVEntry::EQ) {
03754         AllEqual = false;
03755         break;
03756       }
03757     }
03758     if (AllEqual)
03759       return nullptr;
03760   }
03761 
03762   return make_unique<FullDependence>(std::move(Result));
03763 }
03764 
03765 
03766 
03767 //===----------------------------------------------------------------------===//
03768 // getSplitIteration -
03769 // Rather than spend rarely-used space recording the splitting iteration
03770 // during the Weak-Crossing SIV test, we re-compute it on demand.
03771 // The re-computation is basically a repeat of the entire dependence test,
03772 // though simplified since we know that the dependence exists.
03773 // It's tedious, since we must go through all propagations, etc.
03774 //
03775 // Care is required to keep this code up to date with respect to the routine
03776 // above, depends().
03777 //
03778 // Generally, the dependence analyzer will be used to build
03779 // a dependence graph for a function (basically a map from instructions
03780 // to dependences). Looking for cycles in the graph shows us loops
03781 // that cannot be trivially vectorized/parallelized.
03782 //
03783 // We can try to improve the situation by examining all the dependences
03784 // that make up the cycle, looking for ones we can break.
03785 // Sometimes, peeling the first or last iteration of a loop will break
03786 // dependences, and we've got flags for those possibilities.
03787 // Sometimes, splitting a loop at some other iteration will do the trick,
03788 // and we've got a flag for that case. Rather than waste the space to
03789 // record the exact iteration (since we rarely know), we provide
03790 // a method that calculates the iteration. It's a drag that it must work
03791 // from scratch, but wonderful in that it's possible.
03792 //
03793 // Here's an example:
03794 //
03795 //    for (i = 0; i < 10; i++)
03796 //        A[i] = ...
03797 //        ... = A[11 - i]
03798 //
03799 // There's a loop-carried flow dependence from the store to the load,
03800 // found by the weak-crossing SIV test. The dependence will have a flag,
03801 // indicating that the dependence can be broken by splitting the loop.
03802 // Calling getSplitIteration will return 5.
03803 // Splitting the loop breaks the dependence, like so:
03804 //
03805 //    for (i = 0; i <= 5; i++)
03806 //        A[i] = ...
03807 //        ... = A[11 - i]
03808 //    for (i = 6; i < 10; i++)
03809 //        A[i] = ...
03810 //        ... = A[11 - i]
03811 //
03812 // breaks the dependence and allows us to vectorize/parallelize
03813 // both loops.
03814 const  SCEV *DependenceAnalysis::getSplitIteration(const Dependence &Dep,
03815                                                    unsigned SplitLevel) {
03816   assert(Dep.isSplitable(SplitLevel) &&
03817          "Dep should be splitable at SplitLevel");
03818   Instruction *Src = Dep.getSrc();
03819   Instruction *Dst = Dep.getDst();
03820   assert(Src->mayReadFromMemory() || Src->mayWriteToMemory());
03821   assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory());
03822   assert(isLoadOrStore(Src));
03823   assert(isLoadOrStore(Dst));
03824   Value *SrcPtr = getPointerOperand(Src);
03825   Value *DstPtr = getPointerOperand(Dst);
03826   assert(underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), DstPtr,
03827                                 SrcPtr) == MustAlias);
03828 
03829   // establish loop nesting levels
03830   establishNestingLevels(Src, Dst);
03831 
03832   FullDependence Result(Src, Dst, false, CommonLevels);
03833 
03834   // See if there are GEPs we can use.
03835   bool UsefulGEP = false;
03836   GEPOperator *SrcGEP = dyn_cast<GEPOperator>(SrcPtr);
03837   GEPOperator *DstGEP = dyn_cast<GEPOperator>(DstPtr);
03838   if (SrcGEP && DstGEP &&
03839       SrcGEP->getPointerOperandType() == DstGEP->getPointerOperandType()) {
03840     const SCEV *SrcPtrSCEV = SE->getSCEV(SrcGEP->getPointerOperand());
03841     const SCEV *DstPtrSCEV = SE->getSCEV(DstGEP->getPointerOperand());
03842     UsefulGEP = isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) &&
03843                 isLoopInvariant(DstPtrSCEV, LI->getLoopFor(Dst->getParent())) &&
03844                 (SrcGEP->getNumOperands() == DstGEP->getNumOperands());
03845   }
03846   unsigned Pairs = UsefulGEP ? SrcGEP->idx_end() - SrcGEP->idx_begin() : 1;
03847   SmallVector<Subscript, 4> Pair(Pairs);
03848   if (UsefulGEP) {
03849     unsigned P = 0;
03850     for (GEPOperator::const_op_iterator SrcIdx = SrcGEP->idx_begin(),
03851            SrcEnd = SrcGEP->idx_end(),
03852            DstIdx = DstGEP->idx_begin();
03853          SrcIdx != SrcEnd;
03854          ++SrcIdx, ++DstIdx, ++P) {
03855       Pair[P].Src = SE->getSCEV(*SrcIdx);
03856       Pair[P].Dst = SE->getSCEV(*DstIdx);
03857     }
03858   }
03859   else {
03860     const SCEV *SrcSCEV = SE->getSCEV(SrcPtr);
03861     const SCEV *DstSCEV = SE->getSCEV(DstPtr);
03862     Pair[0].Src = SrcSCEV;
03863     Pair[0].Dst = DstSCEV;
03864   }
03865 
03866   if (Delinearize && CommonLevels > 1) {
03867     if (tryDelinearize(Src, Dst, Pair)) {
03868       DEBUG(dbgs() << "    delinerized GEP\n");
03869       Pairs = Pair.size();
03870     }
03871   }
03872 
03873   for (unsigned P = 0; P < Pairs; ++P) {
03874     Pair[P].Loops.resize(MaxLevels + 1);
03875     Pair[P].GroupLoops.resize(MaxLevels + 1);
03876     Pair[P].Group.resize(Pairs);
03877     removeMatchingExtensions(&Pair[P]);
03878     Pair[P].Classification =
03879       classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()),
03880                    Pair[P].Dst, LI->getLoopFor(Dst->getParent()),
03881                    Pair[P].Loops);
03882     Pair[P].GroupLoops = Pair[P].Loops;
03883     Pair[P].Group.set(P);
03884   }
03885 
03886   SmallBitVector Separable(Pairs);
03887   SmallBitVector Coupled(Pairs);
03888 
03889   // partition subscripts into separable and minimally-coupled groups
03890   for (unsigned SI = 0; SI < Pairs; ++SI) {
03891     if (Pair[SI].Classification == Subscript::NonLinear) {
03892       // ignore these, but collect loops for later
03893       collectCommonLoops(Pair[SI].Src,
03894                          LI->getLoopFor(Src->getParent()),
03895                          Pair[SI].Loops);
03896       collectCommonLoops(Pair[SI].Dst,
03897                          LI->getLoopFor(Dst->getParent()),
03898                          Pair[SI].Loops);
03899       Result.Consistent = false;
03900     }
03901     else if (Pair[SI].Classification == Subscript::ZIV)
03902       Separable.set(SI);
03903     else {
03904       // SIV, RDIV, or MIV, so check for coupled group
03905       bool Done = true;
03906       for (unsigned SJ = SI + 1; SJ < Pairs; ++SJ) {
03907         SmallBitVector Intersection = Pair[SI].GroupLoops;
03908         Intersection &= Pair[SJ].GroupLoops;
03909         if (Intersection.any()) {
03910           // accumulate set of all the loops in group
03911           Pair[SJ].GroupLoops |= Pair[SI].GroupLoops;
03912           // accumulate set of all subscripts in group
03913           Pair[SJ].Group |= Pair[SI].Group;
03914           Done = false;
03915         }
03916       }
03917       if (Done) {
03918         if (Pair[SI].Group.count() == 1)
03919           Separable.set(SI);
03920         else
03921           Coupled.set(SI);
03922       }
03923     }
03924   }
03925 
03926   Constraint NewConstraint;
03927   NewConstraint.setAny(SE);
03928 
03929   // test separable subscripts
03930   for (int SI = Separable.find_first(); SI >= 0; SI = Separable.find_next(SI)) {
03931     switch (Pair[SI].Classification) {
03932     case Subscript::SIV: {
03933       unsigned Level;
03934       const SCEV *SplitIter = nullptr;
03935       (void) testSIV(Pair[SI].Src, Pair[SI].Dst, Level,
03936                      Result, NewConstraint, SplitIter);
03937       if (Level == SplitLevel) {
03938         assert(SplitIter != nullptr);
03939         return SplitIter;
03940       }
03941       break;
03942     }
03943     case Subscript::ZIV:
03944     case Subscript::RDIV:
03945     case Subscript::MIV:
03946       break;
03947     default:
03948       llvm_unreachable("subscript has unexpected classification");
03949     }
03950   }
03951 
03952   if (Coupled.count()) {
03953     // test coupled subscript groups
03954     SmallVector<Constraint, 4> Constraints(MaxLevels + 1);
03955     for (unsigned II = 0; II <= MaxLevels; ++II)
03956       Constraints[II].setAny(SE);
03957     for (int SI = Coupled.find_first(); SI >= 0; SI = Coupled.find_next(SI)) {
03958       SmallBitVector Group(Pair[SI].Group);
03959       SmallBitVector Sivs(Pairs);
03960       SmallBitVector Mivs(Pairs);
03961       SmallBitVector ConstrainedLevels(MaxLevels + 1);
03962       for (int SJ = Group.find_first(); SJ >= 0; SJ = Group.find_next(SJ)) {
03963         if (Pair[SJ].Classification == Subscript::SIV)
03964           Sivs.set(SJ);
03965         else
03966           Mivs.set(SJ);
03967       }
03968       while (Sivs.any()) {
03969         bool Changed = false;
03970         for (int SJ = Sivs.find_first(); SJ >= 0; SJ = Sivs.find_next(SJ)) {
03971           // SJ is an SIV subscript that's part of the current coupled group
03972           unsigned Level;
03973           const SCEV *SplitIter = nullptr;
03974           (void) testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level,
03975                          Result, NewConstraint, SplitIter);
03976           if (Level == SplitLevel && SplitIter)
03977             return SplitIter;
03978           ConstrainedLevels.set(Level);
03979           if (intersectConstraints(&Constraints[Level], &NewConstraint))
03980             Changed = true;
03981           Sivs.reset(SJ);
03982         }
03983         if (Changed) {
03984           // propagate, possibly creating new SIVs and ZIVs
03985           for (int SJ = Mivs.find_first(); SJ >= 0; SJ = Mivs.find_next(SJ)) {
03986             // SJ is an MIV subscript that's part of the current coupled group
03987             if (propagate(Pair[SJ].Src, Pair[SJ].Dst,
03988                           Pair[SJ].Loops, Constraints, Result.Consistent)) {
03989               Pair[SJ].Classification =
03990                 classifyPair(Pair[SJ].Src, LI->getLoopFor(Src->getParent()),
03991                              Pair[SJ].Dst, LI->getLoopFor(Dst->getParent()),
03992                              Pair[SJ].Loops);
03993               switch (Pair[SJ].Classification) {
03994               case Subscript::ZIV:
03995                 Mivs.reset(SJ);
03996                 break;
03997               case Subscript::SIV:
03998                 Sivs.set(SJ);
03999                 Mivs.reset(SJ);
04000                 break;
04001               case Subscript::RDIV:
04002               case Subscript::MIV:
04003                 break;
04004               default:
04005                 llvm_unreachable("bad subscript classification");
04006               }
04007             }
04008           }
04009         }
04010       }
04011     }
04012   }
04013   llvm_unreachable("somehow reached end of routine");
04014   return nullptr;
04015 }