LLVM API Documentation

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