LLVM API Documentation

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