X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FDependenceAnalysis.cpp;h=092df5c15cdebc98817868ee3deb15b31665169f;hb=bb660fc192c341012f5f1686b6792be807a6d38b;hp=6c987943bb5e46ddff45990aebc218be11820f0c;hpb=570e52c6f17d8819ee4c8595fc79d17a6dc51dd9;p=oota-llvm.git diff --git a/lib/Analysis/DependenceAnalysis.cpp b/lib/Analysis/DependenceAnalysis.cpp index 6c987943bb5..092df5c15cd 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"; @@ -782,6 +781,25 @@ void DependenceAnalysis::collectCommonLoops(const SCEV *Expression, } } +void DependenceAnalysis::unifySubscriptType(Subscript *Pair) { + const SCEV *Src = Pair->Src; + const SCEV *Dst = Pair->Dst; + IntegerType *SrcTy = dyn_cast(Src->getType()); + IntegerType *DstTy = dyn_cast(Dst->getType()); + if (SrcTy == nullptr || DstTy == nullptr) { + assert(SrcTy == DstTy && "This function only unify integer types and " + "expect Src and Dst share the same type " + "otherwise."); + return; + } + if (SrcTy->getBitWidth() > DstTy->getBitWidth()) { + // Sign-extend Dst to typeof(Src) if typeof(Src) is wider than typeof(Dst). + Pair->Dst = SE->getSignExtendExpr(Dst, SrcTy); + } else if (SrcTy->getBitWidth() < DstTy->getBitWidth()) { + // Sign-extend Src to typeof(Dst) if typeof(Dst) is wider than typeof(Src). + Pair->Src = SE->getSignExtendExpr(Src, DstTy); + } +} // removeMatchingExtensions - Examines a subscript pair. // If the source and destination are identically sign (or zero) @@ -794,9 +812,11 @@ void DependenceAnalysis::removeMatchingExtensions(Subscript *Pair) { (isa(Src) && isa(Dst))) { const SCEVCastExpr *SrcCast = cast(Src); const SCEVCastExpr *DstCast = cast(Dst); - if (SrcCast->getType() == DstCast->getType()) { - Pair->Src = SrcCast->getOperand(); - Pair->Dst = DstCast->getOperand(); + const SCEV *SrcCastOp = SrcCast->getOperand(); + const SCEV *DstCastOp = DstCast->getOperand(); + if (SrcCastOp->getType() == DstCastOp->getType()) { + Pair->Src = SrcCastOp; + Pair->Dst = DstCastOp; } } } @@ -2957,15 +2977,11 @@ const SCEV *DependenceAnalysis::addToCoefficient(const SCEV *Expr, 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), - AddRec->getLoop(), - AddRec->getNoWrapFlags()); + return SE->getAddRecExpr(AddRec, Value, TargetLoop, SCEV::FlagAnyWrap); + return SE->getAddRecExpr( + addToCoefficient(AddRec->getStart(), TargetLoop, Value), + AddRec->getStepRecurrence(*SE), AddRec->getLoop(), + AddRec->getNoWrapFlags()); } @@ -3180,59 +3196,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 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); - - int size = SrcSubscripts.size(); - // Fail when there is only a subscript: that's a linearized access function. - if (size < 2) - return false; + // First step: collect parametric terms in both array references. + SmallVector Terms; + SrcAR->collectParametricTerms(*SE, Terms); + DstAR->collectParametricTerms(*SE, Terms); - 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 @@ -3242,6 +3254,7 @@ DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV, const SCEV *DstSCEV, for (int i = 0; i < size; ++i) { Pair[i].Src = SrcSubscripts[i]; Pair[i].Dst = DstSubscripts[i]; + unifySubscriptType(&Pair[i]); // FIXME: we should record the bounds SrcSizes[i] and DstSizes[i] that the // delinearization has found, and add these constraints to the dependence @@ -3281,9 +3294,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 +3308,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 +3319,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"); @@ -3350,6 +3363,7 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, ++SrcIdx, ++DstIdx, ++P) { Pair[P].Src = SE->getSCEV(*SrcIdx); Pair[P].Dst = SE->getSCEV(*DstIdx); + unifySubscriptType(&Pair[P]); } } else { @@ -3363,7 +3377,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,9 +3693,9 @@ Dependence *DependenceAnalysis::depends(Instruction *Src, return nullptr; } - FullDependence *Final = new FullDependence(Result); + auto Final = make_unique(Result); Result.DV = nullptr; - return Final; + return std::move(Final); } @@ -3733,13 +3747,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 +3800,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(); }