X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FDependenceAnalysis.cpp;h=d0784f1e678dba3e87ef396a7fb8c18a015831b3;hb=6290308366a93cf4730f3c23bb8a4ab72e78e082;hp=450dcbce750e1032f823e6a0740839f5661802f0;hpb=26ba4953091491989eb21feb68fef27ca3f280af;p=oota-llvm.git diff --git a/lib/Analysis/DependenceAnalysis.cpp b/lib/Analysis/DependenceAnalysis.cpp index 450dcbce750..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,8 +51,6 @@ // // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "da" - #include "llvm/Analysis/DependenceAnalysis.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" @@ -60,14 +58,17 @@ #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(); @@ -653,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; } @@ -927,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; } @@ -938,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; } @@ -1270,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) { @@ -2189,7 +2194,7 @@ const SCEVConstant *getConstantPart(const SCEVMulExpr *Product) { if (const SCEVConstant *Constant = dyn_cast(Product->getOperand(Op))) return Constant; } - return NULL; + return nullptr; } @@ -2641,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), @@ -2682,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); @@ -2724,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, @@ -2771,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, @@ -2824,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(); @@ -2867,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; } @@ -2883,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; } @@ -2977,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)) { @@ -3143,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(), @@ -3171,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; +} //===----------------------------------------------------------------------===// @@ -3208,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. @@ -3228,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. } @@ -3280,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); @@ -3417,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"); @@ -3470,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; } @@ -3505,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: @@ -3528,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); } @@ -3541,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"); @@ -3553,7 +3637,7 @@ 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; } } } @@ -3588,11 +3672,11 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, } } if (AllEqual) - return NULL; + return nullptr; } FullDependence *Final = new FullDependence(Result); - Result.DV = NULL; + Result.DV = nullptr; return Final; } @@ -3698,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); @@ -3759,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; @@ -3798,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) @@ -3839,5 +3929,5 @@ const SCEV *DependenceAnalysis::getSplitIteration(const Dependence *Dep, } } llvm_unreachable("somehow reached end of routine"); - return NULL; + return nullptr; }