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