X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FDependenceAnalysis.cpp;h=d0784f1e678dba3e87ef396a7fb8c18a015831b3;hb=6290308366a93cf4730f3c23bb8a4ab72e78e082;hp=385e779a59a7d4e7b600e16781e3e2f9b61c527e;hpb=6ee74f52e987036ced56293d50580f8208b863f5;p=oota-llvm.git diff --git a/lib/Analysis/DependenceAnalysis.cpp b/lib/Analysis/DependenceAnalysis.cpp index 385e779a59a..d0784f1e678 100644 --- a/lib/Analysis/DependenceAnalysis.cpp +++ b/lib/Analysis/DependenceAnalysis.cpp @@ -24,11 +24,11 @@ // Both of these are conservative weaknesses; // that is, not a source of correctness problems. // -// The implementation depends on the GEP instruction to -// differentiate subscripts. Since Clang linearizes subscripts -// for most arrays, we give up some precision (though the existing MIV tests -// will help). We trust that the GEP instruction will eventually be extended. -// In the meantime, we should explore Maslov's ideas about delinearization. +// The implementation depends on the GEP instruction to differentiate +// subscripts. Since Clang linearizes some array subscripts, the dependence +// analysis is using SCEV->delinearize to recover the representation of multiple +// subscripts, and thus avoid the more expensive and less precise MIV tests. The +// delinearization is controlled by the flag -da-delinearize. // // We should pay some careful attention to the possibility of integer overflow // in the implementation of the various tests. This could happen with Add, @@ -51,23 +51,24 @@ // // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "da" - #include "llvm/Analysis/DependenceAnalysis.h" #include "llvm/ADT/Statistic.h" -#include "llvm/Operator.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/LoopInfo.h" -#include "llvm/Analysis/ValueTracking.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/InstIterator.h" +#include "llvm/IR/Operator.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" -#include "llvm/Support/InstIterator.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; +#define DEBUG_TYPE "da" + //===----------------------------------------------------------------------===// // statistics @@ -104,6 +105,10 @@ STATISTIC(BanerjeeApplications, "Banerjee applications"); STATISTIC(BanerjeeIndependence, "Banerjee independence"); STATISTIC(BanerjeeSuccesses, "Banerjee successes"); +static cl::opt +Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore, + cl::desc("Try to delinearize array references.")); + //===----------------------------------------------------------------------===// // basics @@ -229,7 +234,7 @@ FullDependence::FullDependence(Instruction *Source, Levels(CommonLevels), LoopIndependent(PossiblyLoopIndependent) { Consistent = true; - DV = CommonLevels ? new DVEntry[CommonLevels] : NULL; + DV = CommonLevels ? new DVEntry[CommonLevels] : nullptr; } // The rest are simple getters that hide the implementation. @@ -508,7 +513,7 @@ bool DependenceAnalysis::intersectConstraints(Constraint *X, APInt Xr = Xtop; // though they're just going to be overwritten APInt::sdivrem(Xtop, Xbot, Xq, Xr); APInt Yq = Ytop; - APInt Yr = Ytop;; + APInt Yr = Ytop; APInt::sdivrem(Ytop, Ybot, Yq, Yr); if (Xr != 0 || Yr != 0) { X->setEmpty(); @@ -583,42 +588,40 @@ void Dependence::dump(raw_ostream &OS) const { else if (isInput()) OS << "input"; unsigned Levels = getLevels(); - if (Levels) { - OS << " ["; - for (unsigned II = 1; II <= Levels; ++II) { - if (isSplitable(II)) - Splitable = true; - if (isPeelFirst(II)) - OS << 'p'; - const SCEV *Distance = getDistance(II); - if (Distance) - OS << *Distance; - else if (isScalar(II)) - OS << "S"; + OS << " ["; + for (unsigned II = 1; II <= Levels; ++II) { + if (isSplitable(II)) + Splitable = true; + if (isPeelFirst(II)) + OS << 'p'; + const SCEV *Distance = getDistance(II); + if (Distance) + OS << *Distance; + else if (isScalar(II)) + OS << "S"; + else { + unsigned Direction = getDirection(II); + if (Direction == DVEntry::ALL) + OS << "*"; else { - unsigned Direction = getDirection(II); - if (Direction == DVEntry::ALL) - OS << "*"; - else { - if (Direction & DVEntry::LT) - OS << "<"; - if (Direction & DVEntry::EQ) - OS << "="; - if (Direction & DVEntry::GT) - OS << ">"; - } + if (Direction & DVEntry::LT) + OS << "<"; + if (Direction & DVEntry::EQ) + OS << "="; + if (Direction & DVEntry::GT) + OS << ">"; } - if (isPeelLast(II)) - OS << 'p'; - if (II < Levels) - OS << " "; } - if (isLoopIndependent()) - OS << "|<"; - OS << "]"; - if (Splitable) - OS << " splitable"; + if (isPeelLast(II)) + OS << 'p'; + if (II < Levels) + OS << " "; } + if (isLoopIndependent()) + OS << "|<"; + OS << "]"; + if (Splitable) + OS << " splitable"; } OS << "!\n"; } @@ -655,7 +658,7 @@ Value *getPointerOperand(Instruction *I) { if (StoreInst *SI = dyn_cast(I)) return SI->getPointerOperand(); llvm_unreachable("Value is not load or store instruction"); - return 0; + return nullptr; } @@ -929,7 +932,7 @@ const SCEV *DependenceAnalysis::collectUpperBound(const Loop *L, const SCEV *UB = SE->getBackedgeTakenCount(L); return SE->getNoopOrZeroExtend(UB, T); } - return NULL; + return nullptr; } @@ -940,7 +943,7 @@ const SCEVConstant *DependenceAnalysis::collectConstantUpperBound(const Loop *L, ) const { if (const SCEV *UB = collectUpperBound(L, T)) return dyn_cast(UB); - return NULL; + return nullptr; } @@ -1272,8 +1275,8 @@ bool DependenceAnalysis::weakCrossingSIVtest(const SCEV *Coeff, // // Program 2.1, page 29. // Computes the GCD of AM and BM. -// Also finds a solution to the equation ax - by = gdc(a, b). -// Returns true iff the gcd divides Delta. +// Also finds a solution to the equation ax - by = gcd(a, b). +// Returns true if dependence disproved; i.e., gcd does not divide Delta. static bool findGCD(unsigned Bits, APInt AM, APInt BM, APInt Delta, APInt &G, APInt &X, APInt &Y) { @@ -2191,7 +2194,7 @@ const SCEVConstant *getConstantPart(const SCEVMulExpr *Product) { if (const SCEVConstant *Constant = dyn_cast(Product->getOperand(Op))) return Constant; } - return NULL; + return nullptr; } @@ -2212,7 +2215,7 @@ const SCEVConstant *getConstantPart(const SCEVMulExpr *Product) { // // It occurs to me that the presence of loop-invariant variables // changes the nature of the test from "greatest common divisor" -// to "a common divisor!" +// to "a common divisor". bool DependenceAnalysis::gcdMIVtest(const SCEV *Src, const SCEV *Dst, FullDependence &Result) const { @@ -2643,8 +2646,8 @@ void DependenceAnalysis::findBoundsALL(CoefficientInfo *A, CoefficientInfo *B, BoundInfo *Bound, unsigned K) const { - Bound[K].Lower[Dependence::DVEntry::ALL] = NULL; // Default value = -infinity. - Bound[K].Upper[Dependence::DVEntry::ALL] = NULL; // Default value = +infinity. + Bound[K].Lower[Dependence::DVEntry::ALL] = nullptr; // Default value = -infinity. + Bound[K].Upper[Dependence::DVEntry::ALL] = nullptr; // Default value = +infinity. if (Bound[K].Iterations) { Bound[K].Lower[Dependence::DVEntry::ALL] = SE->getMulExpr(SE->getMinusSCEV(A[K].NegPart, B[K].PosPart), @@ -2684,8 +2687,8 @@ void DependenceAnalysis::findBoundsEQ(CoefficientInfo *A, CoefficientInfo *B, BoundInfo *Bound, unsigned K) const { - Bound[K].Lower[Dependence::DVEntry::EQ] = NULL; // Default value = -infinity. - Bound[K].Upper[Dependence::DVEntry::EQ] = NULL; // Default value = +infinity. + Bound[K].Lower[Dependence::DVEntry::EQ] = nullptr; // Default value = -infinity. + Bound[K].Upper[Dependence::DVEntry::EQ] = nullptr; // Default value = +infinity. if (Bound[K].Iterations) { const SCEV *Delta = SE->getMinusSCEV(A[K].Coeff, B[K].Coeff); const SCEV *NegativePart = getNegativePart(Delta); @@ -2726,8 +2729,8 @@ void DependenceAnalysis::findBoundsLT(CoefficientInfo *A, CoefficientInfo *B, BoundInfo *Bound, unsigned K) const { - Bound[K].Lower[Dependence::DVEntry::LT] = NULL; // Default value = -infinity. - Bound[K].Upper[Dependence::DVEntry::LT] = NULL; // Default value = +infinity. + Bound[K].Lower[Dependence::DVEntry::LT] = nullptr; // Default value = -infinity. + Bound[K].Upper[Dependence::DVEntry::LT] = nullptr; // Default value = +infinity. if (Bound[K].Iterations) { const SCEV *Iter_1 = SE->getMinusSCEV(Bound[K].Iterations, @@ -2773,8 +2776,8 @@ void DependenceAnalysis::findBoundsGT(CoefficientInfo *A, CoefficientInfo *B, BoundInfo *Bound, unsigned K) const { - Bound[K].Lower[Dependence::DVEntry::GT] = NULL; // Default value = -infinity. - Bound[K].Upper[Dependence::DVEntry::GT] = NULL; // Default value = +infinity. + Bound[K].Lower[Dependence::DVEntry::GT] = nullptr; // Default value = -infinity. + Bound[K].Upper[Dependence::DVEntry::GT] = nullptr; // Default value = +infinity. if (Bound[K].Iterations) { const SCEV *Iter_1 = SE->getMinusSCEV(Bound[K].Iterations, @@ -2826,7 +2829,7 @@ DependenceAnalysis::collectCoeffInfo(const SCEV *Subscript, CI[K].Coeff = Zero; CI[K].PosPart = Zero; CI[K].NegPart = Zero; - CI[K].Iterations = NULL; + CI[K].Iterations = nullptr; } while (const SCEVAddRecExpr *AddRec = dyn_cast(Subscript)) { const Loop *L = AddRec->getLoop(); @@ -2869,7 +2872,7 @@ const SCEV *DependenceAnalysis::getLowerBound(BoundInfo *Bound) const { if (Bound[K].Lower[Bound[K].Direction]) Sum = SE->getAddExpr(Sum, Bound[K].Lower[Bound[K].Direction]); else - Sum = NULL; + Sum = nullptr; } return Sum; } @@ -2885,7 +2888,7 @@ const SCEV *DependenceAnalysis::getUpperBound(BoundInfo *Bound) const { if (Bound[K].Upper[Bound[K].Direction]) Sum = SE->getAddExpr(Sum, Bound[K].Upper[Bound[K].Direction]); else - Sum = NULL; + Sum = nullptr; } return Sum; } @@ -2953,6 +2956,11 @@ const SCEV *DependenceAnalysis::addToCoefficient(const SCEV *Expr, AddRec->getLoop(), AddRec->getNoWrapFlags()); } + if (SE->isLoopInvariant(AddRec, TargetLoop)) + return SE->getAddRecExpr(AddRec, + Value, + TargetLoop, + SCEV::FlagAnyWrap); return SE->getAddRecExpr(addToCoefficient(AddRec->getStart(), TargetLoop, Value), AddRec->getStepRecurrence(*SE), @@ -2974,7 +2982,7 @@ const SCEV *DependenceAnalysis::addToCoefficient(const SCEV *Expr, bool DependenceAnalysis::propagate(const SCEV *&Src, const SCEV *&Dst, SmallBitVector &Loops, - SmallVector &Constraints, + SmallVectorImpl &Constraints, bool &Consistent) { bool Result = false; for (int LI = Loops.find_first(); LI >= 0; LI = Loops.find_next(LI)) { @@ -3140,12 +3148,12 @@ void DependenceAnalysis::updateDirection(Dependence::DVEntry &Level, } else if (CurConstraint.isLine()) { Level.Scalar = false; - Level.Distance = NULL; + Level.Distance = nullptr; // direction should be accurate } else if (CurConstraint.isPoint()) { Level.Scalar = false; - Level.Distance = NULL; + Level.Distance = nullptr; unsigned NewDirection = Dependence::DVEntry::NONE; if (!isKnownPredicate(CmpInst::ICMP_NE, CurConstraint.getY(), @@ -3168,6 +3176,79 @@ void DependenceAnalysis::updateDirection(Dependence::DVEntry &Level, llvm_unreachable("constraint has unexpected kind"); } +/// Check if we can delinearize the subscripts. If the SCEVs representing the +/// source and destination array references are recurrences on a nested loop, +/// this function flattens the nested recurrences into separate recurrences +/// for each loop level. +bool DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV, + const SCEV *DstSCEV, + SmallVectorImpl &Pair, + const SCEV *ElementSize) const { + const SCEVUnknown *SrcBase = + dyn_cast(SE->getPointerBase(SrcSCEV)); + const SCEVUnknown *DstBase = + dyn_cast(SE->getPointerBase(DstSCEV)); + + if (!SrcBase || !DstBase || SrcBase != DstBase) + return false; + + SrcSCEV = SE->getMinusSCEV(SrcSCEV, SrcBase); + DstSCEV = SE->getMinusSCEV(DstSCEV, DstBase); + + const SCEVAddRecExpr *SrcAR = dyn_cast(SrcSCEV); + const SCEVAddRecExpr *DstAR = dyn_cast(DstSCEV); + if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine()) + return false; + + // First step: collect parametric terms in both array references. + SmallVector Terms; + SrcAR->collectParametricTerms(*SE, Terms); + DstAR->collectParametricTerms(*SE, Terms); + + // Second step: find subscript sizes. + SmallVector Sizes; + SE->findArrayDimensions(Terms, Sizes, ElementSize); + + // Third step: compute the access functions for each subscript. + SmallVector SrcSubscripts, DstSubscripts; + SrcAR->computeAccessFunctions(*SE, SrcSubscripts, Sizes); + DstAR->computeAccessFunctions(*SE, DstSubscripts, Sizes); + + // Fail when there is only a subscript: that's a linearized access function. + if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 || + SrcSubscripts.size() != DstSubscripts.size()) + return false; + + int size = SrcSubscripts.size(); + + DEBUG({ + dbgs() << "\nSrcSubscripts: "; + for (int i = 0; i < size; i++) + dbgs() << *SrcSubscripts[i]; + dbgs() << "\nDstSubscripts: "; + for (int i = 0; i < size; i++) + dbgs() << *DstSubscripts[i]; + }); + + // The delinearization transforms a single-subscript MIV dependence test into + // a multi-subscript SIV dependence test that is easier to compute. So we + // resize Pair to contain as many pairs of subscripts as the delinearization + // has found, and then initialize the pairs following the delinearization. + Pair.resize(size); + for (int i = 0; i < size; ++i) { + Pair[i].Src = SrcSubscripts[i]; + Pair[i].Dst = DstSubscripts[i]; + + // FIXME: we should record the bounds SrcSizes[i] and DstSizes[i] that the + // delinearization has found, and add these constraints to the dependence + // check to avoid memory accesses overflow from one dimension into another. + // This is related to the problem of determining the existence of data + // dependences in array accesses using a different number of subscripts: in + // C one can access an array A[100][100]; as A[0][9999], *A[9999], etc. + } + + return true; +} //===----------------------------------------------------------------------===// @@ -3205,7 +3286,7 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, if ((!Src->mayReadFromMemory() && !Src->mayWriteToMemory()) || (!Dst->mayReadFromMemory() && !Dst->mayWriteToMemory())) // if both instructions don't reference memory, there's no dependence - return NULL; + return nullptr; if (!isLoadOrStore(Src) || !isLoadOrStore(Dst)) { // can only analyze simple loads and stores, i.e., no calls, invokes, etc. @@ -3225,7 +3306,7 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, case AliasAnalysis::NoAlias: // If the objects noalias, they are distinct, accesses are independent. DEBUG(dbgs() << "no alias\n"); - return NULL; + return nullptr; case AliasAnalysis::MustAlias: break; // The underlying objects alias; test accesses for dependence. } @@ -3277,6 +3358,12 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, Pair[0].Dst = DstSCEV; } + if (Delinearize && Pairs == 1 && CommonLevels > 1 && + tryDelinearize(Pair[0].Src, Pair[0].Dst, Pair, SE->getElementSize(Src))) { + DEBUG(dbgs() << " delinerized GEP\n"); + Pairs = Pair.size(); + } + for (unsigned P = 0; P < Pairs; ++P) { Pair[P].Loops.resize(MaxLevels + 1); Pair[P].GroupLoops.resize(MaxLevels + 1); @@ -3414,26 +3501,26 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, case Subscript::ZIV: DEBUG(dbgs() << ", ZIV\n"); if (testZIV(Pair[SI].Src, Pair[SI].Dst, Result)) - return NULL; + return nullptr; break; case Subscript::SIV: { DEBUG(dbgs() << ", SIV\n"); unsigned Level; - const SCEV *SplitIter = NULL; + const SCEV *SplitIter = nullptr; if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level, Result, NewConstraint, SplitIter)) - return NULL; + return nullptr; break; } case Subscript::RDIV: DEBUG(dbgs() << ", RDIV\n"); if (testRDIV(Pair[SI].Src, Pair[SI].Dst, Result)) - return NULL; + return nullptr; break; case Subscript::MIV: DEBUG(dbgs() << ", MIV\n"); if (testMIV(Pair[SI].Src, Pair[SI].Dst, Pair[SI].Loops, Result)) - return NULL; + return nullptr; break; default: llvm_unreachable("subscript has unexpected classification"); @@ -3467,16 +3554,16 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, DEBUG(dbgs() << "testing subscript " << SJ << ", SIV\n"); // SJ is an SIV subscript that's part of the current coupled group unsigned Level; - const SCEV *SplitIter = NULL; + const SCEV *SplitIter = nullptr; DEBUG(dbgs() << "SIV\n"); if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint, SplitIter)) - return NULL; + return nullptr; ConstrainedLevels.set(Level); if (intersectConstraints(&Constraints[Level], &NewConstraint)) { if (Constraints[Level].isEmpty()) { ++DeltaIndependence; - return NULL; + return nullptr; } Changed = true; } @@ -3502,7 +3589,7 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, case Subscript::ZIV: DEBUG(dbgs() << "ZIV\n"); if (testZIV(Pair[SJ].Src, Pair[SJ].Dst, Result)) - return NULL; + return nullptr; Mivs.reset(SJ); break; case Subscript::SIV: @@ -3525,7 +3612,7 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, if (Pair[SJ].Classification == Subscript::RDIV) { DEBUG(dbgs() << "RDIV test\n"); if (testRDIV(Pair[SJ].Src, Pair[SJ].Dst, Result)) - return NULL; + return nullptr; // I don't yet understand how to propagate RDIV results Mivs.reset(SJ); } @@ -3538,7 +3625,7 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, if (Pair[SJ].Classification == Subscript::MIV) { DEBUG(dbgs() << "MIV test\n"); if (testMIV(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops, Result)) - return NULL; + return nullptr; } else llvm_unreachable("expected only MIV subscripts at this point"); @@ -3550,12 +3637,12 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, SJ >= 0; SJ = ConstrainedLevels.find_next(SJ)) { updateDirection(Result.DV[SJ - 1], Constraints[SJ]); if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE) - return NULL; + return nullptr; } } } - // make sure Scalar flags are set correctly + // Make sure the Scalar flags are set correctly. SmallBitVector CompleteLoops(MaxLevels + 1); for (unsigned SI = 0; SI < Pairs; ++SI) CompleteLoops |= Pair[SI].Loops; @@ -3563,8 +3650,10 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, if (CompleteLoops[II]) Result.DV[II - 1].Scalar = false; - // make sure loopIndepent flag is set correctly if (PossiblyLoopIndependent) { + // Make sure the LoopIndependent flag is set correctly. + // All directions must include equal, otherwise no + // loop-independent dependence is possible. for (unsigned II = 1; II <= CommonLevels; ++II) { if (!(Result.getDirection(II) & Dependence::DVEntry::EQ)) { Result.LoopIndependent = false; @@ -3572,9 +3661,22 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, } } } + else { + // On the other hand, if all directions are equal and there's no + // loop-independent dependence possible, then no dependence exists. + bool AllEqual = true; + for (unsigned II = 1; II <= CommonLevels; ++II) { + if (Result.getDirection(II) != Dependence::DVEntry::EQ) { + AllEqual = false; + break; + } + } + if (AllEqual) + return nullptr; + } FullDependence *Final = new FullDependence(Result); - Result.DV = NULL; + Result.DV = nullptr; return Final; } @@ -3680,6 +3782,12 @@ const SCEV *DependenceAnalysis::getSplitIteration(const Dependence *Dep, Pair[0].Dst = DstSCEV; } + if (Delinearize && Pairs == 1 && CommonLevels > 1 && + tryDelinearize(Pair[0].Src, Pair[0].Dst, Pair, SE->getElementSize(Src))) { + DEBUG(dbgs() << " delinerized GEP\n"); + Pairs = Pair.size(); + } + for (unsigned P = 0; P < Pairs; ++P) { Pair[P].Loops.resize(MaxLevels + 1); Pair[P].GroupLoops.resize(MaxLevels + 1); @@ -3741,11 +3849,11 @@ const SCEV *DependenceAnalysis::getSplitIteration(const Dependence *Dep, switch (Pair[SI].Classification) { case Subscript::SIV: { unsigned Level; - const SCEV *SplitIter = NULL; + const SCEV *SplitIter = nullptr; (void) testSIV(Pair[SI].Src, Pair[SI].Dst, Level, Result, NewConstraint, SplitIter); if (Level == SplitLevel) { - assert(SplitIter != NULL); + assert(SplitIter != nullptr); return SplitIter; } break; @@ -3780,7 +3888,7 @@ const SCEV *DependenceAnalysis::getSplitIteration(const Dependence *Dep, for (int SJ = Sivs.find_first(); SJ >= 0; SJ = Sivs.find_next(SJ)) { // SJ is an SIV subscript that's part of the current coupled group unsigned Level; - const SCEV *SplitIter = NULL; + const SCEV *SplitIter = nullptr; (void) testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint, SplitIter); if (Level == SplitLevel && SplitIter) @@ -3821,5 +3929,5 @@ const SCEV *DependenceAnalysis::getSplitIteration(const Dependence *Dep, } } llvm_unreachable("somehow reached end of routine"); - return NULL; + return nullptr; }