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