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