X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FDependenceAnalysis.cpp;h=8120736885ca158354211209f3cd3e8d7df42385;hb=97dc647e908223d2eda79590de451805dd16a346;hp=6c987943bb5e46ddff45990aebc218be11820f0c;hpb=570e52c6f17d8819ee4c8595fc79d17a6dc51dd9;p=oota-llvm.git diff --git a/lib/Analysis/DependenceAnalysis.cpp b/lib/Analysis/DependenceAnalysis.cpp index 6c987943bb5..8120736885c 100644 --- a/lib/Analysis/DependenceAnalysis.cpp +++ b/lib/Analysis/DependenceAnalysis.cpp @@ -51,8 +51,6 @@ // // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "da" - #include "llvm/Analysis/DependenceAnalysis.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" @@ -69,6 +67,8 @@ using namespace llvm; +#define DEBUG_TYPE "da" + //===----------------------------------------------------------------------===// // statistics @@ -163,16 +163,15 @@ void dumpExampleDependence(raw_ostream &OS, Function *F, DstI != DstE; ++DstI) { if (isa(*DstI) || isa(*DstI)) { OS << "da analyze - "; - if (Dependence *D = DA->depends(&*SrcI, &*DstI, true)) { + if (auto D = DA->depends(&*SrcI, &*DstI, true)) { D->dump(OS); for (unsigned Level = 1; Level <= D->getLevels(); Level++) { if (D->isSplitable(Level)) { OS << "da analyze - split level = " << Level; - OS << ", iteration = " << *DA->getSplitIteration(D, Level); + OS << ", iteration = " << *DA->getSplitIteration(*D, Level); OS << "!\n"; } } - delete D; } else OS << "none!\n"; @@ -2438,11 +2437,14 @@ bool DependenceAnalysis::banerjeeMIVtest(const SCEV *Src, ++BanerjeeApplications; DEBUG(dbgs() << " Src = " << *Src << '\n'); const SCEV *A0; - CoefficientInfo *A = collectCoeffInfo(Src, true, A0); + auto AOwner = collectCoeffInfo(Src, true, A0); + auto A = AOwner.get(); DEBUG(dbgs() << " Dst = " << *Dst << '\n'); const SCEV *B0; - CoefficientInfo *B = collectCoeffInfo(Dst, false, B0); - BoundInfo *Bound = new BoundInfo[MaxLevels + 1]; + auto BOwner = collectCoeffInfo(Dst, false, B0); + auto B = BOwner.get(); + auto BoundOwner = make_unique(MaxLevels + 1); + auto Bound = BoundOwner.get(); const SCEV *Delta = SE->getMinusSCEV(B0, A0); DEBUG(dbgs() << "\tDelta = " << *Delta << '\n'); @@ -2499,9 +2501,6 @@ bool DependenceAnalysis::banerjeeMIVtest(const SCEV *Src, ++BanerjeeIndependence; Disproved = true; } - delete [] Bound; - delete [] A; - delete [] B; return Disproved; } @@ -2819,12 +2818,12 @@ const SCEV *DependenceAnalysis::getNegativePart(const SCEV *X) const { // Walks through the subscript, // collecting each coefficient, the associated loop bounds, // and recording its positive and negative parts for later use. -DependenceAnalysis::CoefficientInfo * +std::unique_ptr DependenceAnalysis::collectCoeffInfo(const SCEV *Subscript, bool SrcFlag, const SCEV *&Constant) const { const SCEV *Zero = SE->getConstant(Subscript->getType(), 0); - CoefficientInfo *CI = new CoefficientInfo[MaxLevels + 1]; + auto CI = make_unique(MaxLevels + 1); for (unsigned K = 1; K <= MaxLevels; ++K) { CI[K].Coeff = Zero; CI[K].PosPart = Zero; @@ -3180,59 +3179,55 @@ void DependenceAnalysis::updateDirection(Dependence::DVEntry &Level, /// 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 { +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; - SmallVector SrcSubscripts, DstSubscripts, SrcSizes, DstSizes; - const SCEV *RemainderS = SrcAR->delinearize(*SE, SrcSubscripts, SrcSizes); - const SCEV *RemainderD = DstAR->delinearize(*SE, DstSubscripts, DstSizes); + // First step: collect parametric terms in both array references. + SmallVector Terms; + SrcAR->collectParametricTerms(*SE, Terms); + DstAR->collectParametricTerms(*SE, Terms); - int size = SrcSubscripts.size(); - // Fail when there is only a subscript: that's a linearized access function. - if (size < 2) - return false; - - int dstSize = DstSubscripts.size(); - // Fail when the number of subscripts in Src and Dst differ. - if (size != dstSize) - return false; + // Second step: find subscript sizes. + SmallVector Sizes; + SE->findArrayDimensions(Terms, Sizes, ElementSize); - // Fail when the size of any of the subscripts in Src and Dst differs: the - // dependence analysis assumes that elements in the same array have same size. - // SCEV delinearization does not have a context based on which it would decide - // globally the size of subscripts that would best fit all the array accesses. - for (int i = 0; i < size; ++i) - if (SrcSizes[i] != DstSizes[i]) - return false; + // Third step: compute the access functions for each subscript. + SmallVector SrcSubscripts, DstSubscripts; + SrcAR->computeAccessFunctions(*SE, SrcSubscripts, Sizes); + DstAR->computeAccessFunctions(*SE, DstSubscripts, Sizes); - // When the difference in remainders is different than a constant it might be - // that the base address of the arrays is not the same. - const SCEV *DiffRemainders = SE->getMinusSCEV(RemainderS, RemainderD); - if (!isa(DiffRemainders)) + // 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; - // Normalize the last dimension: integrate the size of the "scalar dimension" - // and the remainder of the delinearization. - DstSubscripts[size-1] = SE->getMulExpr(DstSubscripts[size-1], - DstSizes[size-1]); - SrcSubscripts[size-1] = SE->getMulExpr(SrcSubscripts[size-1], - SrcSizes[size-1]); - SrcSubscripts[size-1] = SE->getAddExpr(SrcSubscripts[size-1], RemainderS); - DstSubscripts[size-1] = SE->getAddExpr(DstSubscripts[size-1], RemainderD); + int size = SrcSubscripts.size(); -#ifndef NDEBUG - DEBUG(errs() << "\nSrcSubscripts: "); - for (int i = 0; i < size; i++) - DEBUG(errs() << *SrcSubscripts[i]); - DEBUG(errs() << "\nDstSubscripts: "); - for (int i = 0; i < size; i++) - DEBUG(errs() << *DstSubscripts[i]); -#endif + 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 @@ -3281,9 +3276,9 @@ static void dumpSmallBitVector(SmallBitVector &BV) { // // Care is required to keep the routine below, getSplitIteration(), // up to date with respect to this routine. -Dependence *DependenceAnalysis::depends(Instruction *Src, - Instruction *Dst, - bool PossiblyLoopIndependent) { +std::unique_ptr +DependenceAnalysis::depends(Instruction *Src, Instruction *Dst, + bool PossiblyLoopIndependent) { if (Src == Dst) PossiblyLoopIndependent = false; @@ -3295,7 +3290,7 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, if (!isLoadOrStore(Src) || !isLoadOrStore(Dst)) { // can only analyze simple loads and stores, i.e., no calls, invokes, etc. DEBUG(dbgs() << "can only handle simple loads and stores\n"); - return new Dependence(Src, Dst); + return make_unique(Src, Dst); } Value *SrcPtr = getPointerOperand(Src); @@ -3306,7 +3301,7 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, case AliasAnalysis::PartialAlias: // cannot analyse objects if we don't understand their aliasing. DEBUG(dbgs() << "can't analyze may or partial alias\n"); - return new Dependence(Src, Dst); + return make_unique(Src, Dst); case AliasAnalysis::NoAlias: // If the objects noalias, they are distinct, accesses are independent. DEBUG(dbgs() << "no alias\n"); @@ -3363,7 +3358,7 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, } if (Delinearize && Pairs == 1 && CommonLevels > 1 && - tryDelinearize(Pair[0].Src, Pair[0].Dst, Pair)) { + tryDelinearize(Pair[0].Src, Pair[0].Dst, Pair, SE->getElementSize(Src))) { DEBUG(dbgs() << " delinerized GEP\n"); Pairs = Pair.size(); } @@ -3679,7 +3674,8 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, return nullptr; } - FullDependence *Final = new FullDependence(Result); + std::unique_ptr Final; + Final.reset(new FullDependence(Result)); Result.DV = nullptr; return Final; } @@ -3733,13 +3729,12 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, // // breaks the dependence and allows us to vectorize/parallelize // both loops. -const SCEV *DependenceAnalysis::getSplitIteration(const Dependence *Dep, +const SCEV *DependenceAnalysis::getSplitIteration(const Dependence &Dep, unsigned SplitLevel) { - assert(Dep && "expected a pointer to a Dependence"); - assert(Dep->isSplitable(SplitLevel) && + assert(Dep.isSplitable(SplitLevel) && "Dep should be splitable at SplitLevel"); - Instruction *Src = Dep->getSrc(); - Instruction *Dst = Dep->getDst(); + Instruction *Src = Dep.getSrc(); + Instruction *Dst = Dep.getDst(); assert(Src->mayReadFromMemory() || Src->mayWriteToMemory()); assert(Dst->mayReadFromMemory() || Dst->mayWriteToMemory()); assert(isLoadOrStore(Src)); @@ -3787,7 +3782,7 @@ const SCEV *DependenceAnalysis::getSplitIteration(const Dependence *Dep, } if (Delinearize && Pairs == 1 && CommonLevels > 1 && - tryDelinearize(Pair[0].Src, Pair[0].Dst, Pair)) { + tryDelinearize(Pair[0].Src, Pair[0].Dst, Pair, SE->getElementSize(Src))) { DEBUG(dbgs() << " delinerized GEP\n"); Pairs = Pair.size(); }