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