X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FDependenceAnalysis.cpp;h=8e39665f50d0ec5483826d539bc0b728c8237f68;hb=d44ba4a7c6103a1e0543f02b342d87f17063560a;hp=4998f2812bca417a150c2c8dc4322a6b81bc9ac3;hpb=0f06462959bcf8224e72b7c739659292dddbdc87;p=oota-llvm.git diff --git a/lib/Analysis/DependenceAnalysis.cpp b/lib/Analysis/DependenceAnalysis.cpp index 4998f2812bc..8e39665f50d 100644 --- a/lib/Analysis/DependenceAnalysis.cpp +++ b/lib/Analysis/DependenceAnalysis.cpp @@ -52,6 +52,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/DependenceAnalysis.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/LoopInfo.h" @@ -59,6 +60,7 @@ #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/InstIterator.h" +#include "llvm/IR/Module.h" #include "llvm/IR/Operator.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" @@ -114,9 +116,9 @@ Delinearize("da-delinearize", cl::init(false), cl::Hidden, cl::ZeroOrMore, INITIALIZE_PASS_BEGIN(DependenceAnalysis, "da", "Dependence Analysis", true, true) -INITIALIZE_PASS_DEPENDENCY(LoopInfo) -INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) -INITIALIZE_AG_DEPENDENCY(AliasAnalysis) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_END(DependenceAnalysis, "da", "Dependence Analysis", true, true) @@ -130,9 +132,9 @@ FunctionPass *llvm::createDependenceAnalysisPass() { bool DependenceAnalysis::runOnFunction(Function &F) { this->F = &F; - AA = &getAnalysis(); - SE = &getAnalysis(); - LI = &getAnalysis(); + AA = &getAnalysis().getAAResults(); + SE = &getAnalysis().getSE(); + LI = &getAnalysis().getLoopInfo(); return false; } @@ -143,9 +145,9 @@ void DependenceAnalysis::releaseMemory() { void DependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); - AU.addRequiredTransitive(); - AU.addRequiredTransitive(); - AU.addRequiredTransitive(); + AU.addRequiredTransitive(); + AU.addRequiredTransitive(); + AU.addRequiredTransitive(); } @@ -225,15 +227,14 @@ bool Dependence::isScalar(unsigned level) const { //===----------------------------------------------------------------------===// // FullDependence methods -FullDependence::FullDependence(Instruction *Source, - Instruction *Destination, +FullDependence::FullDependence(Instruction *Source, Instruction *Destination, bool PossiblyLoopIndependent, - unsigned CommonLevels) : - Dependence(Source, Destination), - Levels(CommonLevels), - LoopIndependent(PossiblyLoopIndependent) { + unsigned CommonLevels) + : Dependence(Source, Destination), Levels(CommonLevels), + LoopIndependent(PossiblyLoopIndependent) { Consistent = true; - DV = CommonLevels ? new DVEntry[CommonLevels] : nullptr; + if (CommonLevels) + DV = make_unique(CommonLevels); } // The rest are simple getters that hide the implementation. @@ -371,7 +372,7 @@ void DependenceAnalysis::Constraint::setLine(const SCEV *AA, void DependenceAnalysis::Constraint::setDistance(const SCEV *D, const Loop *CurLoop) { Kind = Distance; - A = SE->getConstant(D->getType(), 1); + A = SE->getOne(D->getType()); B = SE->getNegativeSCEV(A); C = SE->getNegativeSCEV(D); AssociatedLoop = CurLoop; @@ -625,16 +626,13 @@ void Dependence::dump(raw_ostream &OS) const { OS << "!\n"; } - - -static -AliasAnalysis::AliasResult underlyingObjectsAlias(AliasAnalysis *AA, - const Value *A, - const Value *B) { - const Value *AObj = GetUnderlyingObject(A); - const Value *BObj = GetUnderlyingObject(B); - return AA->alias(AObj, AA->getTypeStoreSize(AObj->getType()), - BObj, AA->getTypeStoreSize(BObj->getType())); +static AliasResult underlyingObjectsAlias(AliasAnalysis *AA, + const DataLayout &DL, const Value *A, + const Value *B) { + const Value *AObj = GetUnderlyingObject(A, DL); + const Value *BObj = GetUnderlyingObject(B, DL); + return AA->alias(AObj, DL.getTypeStoreSize(AObj->getType()), + BObj, DL.getTypeStoreSize(BObj->getType())); } @@ -781,6 +779,58 @@ void DependenceAnalysis::collectCommonLoops(const SCEV *Expression, } } +void DependenceAnalysis::unifySubscriptType(ArrayRef Pairs) { + + unsigned widestWidthSeen = 0; + Type *widestType; + + // Go through each pair and find the widest bit to which we need + // to extend all of them. + for (unsigned i = 0; i < Pairs.size(); i++) { + const SCEV *Src = Pairs[i]->Src; + const SCEV *Dst = Pairs[i]->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."); + continue; + } + if (SrcTy->getBitWidth() > widestWidthSeen) { + widestWidthSeen = SrcTy->getBitWidth(); + widestType = SrcTy; + } + if (DstTy->getBitWidth() > widestWidthSeen) { + widestWidthSeen = DstTy->getBitWidth(); + widestType = DstTy; + } + } + + + assert(widestWidthSeen > 0); + + // Now extend each pair to the widest seen. + for (unsigned i = 0; i < Pairs.size(); i++) { + const SCEV *Src = Pairs[i]->Src; + const SCEV *Dst = Pairs[i]->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."); + continue; + } + if (SrcTy->getBitWidth() < widestWidthSeen) + // Sign-extend Src to widestType + Pairs[i]->Src = SE->getSignExtendExpr(Src, widestType); + if (DstTy->getBitWidth() < widestWidthSeen) { + // Sign-extend Dst to widestType + Pairs[i]->Dst = SE->getSignExtendExpr(Dst, widestType); + } + } +} // removeMatchingExtensions - Examines a subscript pair. // If the source and destination are identically sign (or zero) @@ -793,9 +843,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; } } } @@ -811,6 +863,14 @@ bool DependenceAnalysis::checkSrcSubscript(const SCEV *Src, return isLoopInvariant(Src, LoopNest); const SCEV *Start = AddRec->getStart(); const SCEV *Step = AddRec->getStepRecurrence(*SE); + const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop()); + if (!isa(UB)) { + if (SE->getTypeSizeInBits(Start->getType()) < + SE->getTypeSizeInBits(UB->getType())) { + if (!AddRec->getNoWrapFlags()) + return false; + } + } if (!isLoopInvariant(Step, LoopNest)) return false; Loops.set(mapSrcLoop(AddRec->getLoop())); @@ -829,6 +889,14 @@ bool DependenceAnalysis::checkDstSubscript(const SCEV *Dst, return isLoopInvariant(Dst, LoopNest); const SCEV *Start = AddRec->getStart(); const SCEV *Step = AddRec->getStepRecurrence(*SE); + const SCEV *UB = SE->getBackedgeTakenCount(AddRec->getLoop()); + if (!isa(UB)) { + if (SE->getTypeSizeInBits(Start->getType()) < + SE->getTypeSizeInBits(UB->getType())) { + if (!AddRec->getNoWrapFlags()) + return false; + } + } if (!isLoopInvariant(Step, LoopNest)) return false; Loops.set(mapDstLoop(AddRec->getLoop())); @@ -923,13 +991,15 @@ bool DependenceAnalysis::isKnownPredicate(ICmpInst::Predicate Pred, // All subscripts are all the same type. // Loop bound may be smaller (e.g., a char). // Should zero extend loop bound, since it's always >= 0. -// This routine collects upper bound and extends if needed. +// This routine collects upper bound and extends or truncates if needed. +// Truncating is safe when subscripts are known not to wrap. Cases without +// nowrap flags should have been rejected earlier. // Return null if no bound available. const SCEV *DependenceAnalysis::collectUpperBound(const Loop *L, Type *T) const { if (SE->hasLoopInvariantBackedgeTakenCount(L)) { const SCEV *UB = SE->getBackedgeTakenCount(L); - return SE->getNoopOrZeroExtend(UB, T); + return SE->getTruncateOrZeroExtend(UB, T); } return nullptr; } @@ -1187,11 +1257,9 @@ bool DependenceAnalysis::weakCrossingSIVtest(const SCEV *Coeff, assert(SE->isKnownPositive(ConstCoeff) && "ConstCoeff should be positive"); // compute SplitIter for use by DependenceAnalysis::getSplitIteration() - SplitIter = - SE->getUDivExpr(SE->getSMaxExpr(SE->getConstant(Delta->getType(), 0), - Delta), - SE->getMulExpr(SE->getConstant(Delta->getType(), 2), - ConstCoeff)); + SplitIter = SE->getUDivExpr( + SE->getSMaxExpr(SE->getZero(Delta->getType()), Delta), + SE->getMulExpr(SE->getConstant(Delta->getType(), 2), ConstCoeff)); DEBUG(dbgs() << "\t Split iter = " << *SplitIter << "\n"); const SCEVConstant *ConstDelta = dyn_cast(Delta); @@ -1233,7 +1301,7 @@ bool DependenceAnalysis::weakCrossingSIVtest(const SCEV *Coeff, return true; } Result.DV[Level].Splitable = false; - Result.DV[Level].Distance = SE->getConstant(Delta->getType(), 0); + Result.DV[Level].Distance = SE->getZero(Delta->getType()); return false; } } @@ -1596,8 +1664,8 @@ bool DependenceAnalysis::weakZeroSrcSIVtest(const SCEV *DstCoeff, Level--; Result.Consistent = false; const SCEV *Delta = SE->getMinusSCEV(SrcConst, DstConst); - NewConstraint.setLine(SE->getConstant(Delta->getType(), 0), - DstCoeff, Delta, CurLoop); + NewConstraint.setLine(SE->getZero(Delta->getType()), DstCoeff, Delta, + CurLoop); DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); if (isKnownPredicate(CmpInst::ICMP_EQ, SrcConst, DstConst)) { if (Level < CommonLevels) { @@ -1706,8 +1774,8 @@ bool DependenceAnalysis::weakZeroDstSIVtest(const SCEV *SrcCoeff, Level--; Result.Consistent = false; const SCEV *Delta = SE->getMinusSCEV(DstConst, SrcConst); - NewConstraint.setLine(SrcCoeff, SE->getConstant(Delta->getType(), 0), - Delta, CurLoop); + NewConstraint.setLine(SrcCoeff, SE->getZero(Delta->getType()), Delta, + CurLoop); DEBUG(dbgs() << "\t Delta = " << *Delta << "\n"); if (isKnownPredicate(CmpInst::ICMP_EQ, DstConst, SrcConst)) { if (Level < CommonLevels) { @@ -2659,10 +2727,10 @@ void DependenceAnalysis::findBoundsALL(CoefficientInfo *A, // If the difference is 0, we won't need to know the number of iterations. if (isKnownPredicate(CmpInst::ICMP_EQ, A[K].NegPart, B[K].PosPart)) Bound[K].Lower[Dependence::DVEntry::ALL] = - SE->getConstant(A[K].Coeff->getType(), 0); + SE->getZero(A[K].Coeff->getType()); if (isKnownPredicate(CmpInst::ICMP_EQ, A[K].PosPart, B[K].NegPart)) Bound[K].Upper[Dependence::DVEntry::ALL] = - SE->getConstant(A[K].Coeff->getType(), 0); + SE->getZero(A[K].Coeff->getType()); } } @@ -2731,9 +2799,8 @@ void DependenceAnalysis::findBoundsLT(CoefficientInfo *A, 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, - SE->getConstant(Bound[K].Iterations->getType(), 1)); + const SCEV *Iter_1 = SE->getMinusSCEV( + Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType())); const SCEV *NegPart = getNegativePart(SE->getMinusSCEV(A[K].NegPart, B[K].Coeff)); Bound[K].Lower[Dependence::DVEntry::LT] = @@ -2778,9 +2845,8 @@ void DependenceAnalysis::findBoundsGT(CoefficientInfo *A, 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, - SE->getConstant(Bound[K].Iterations->getType(), 1)); + const SCEV *Iter_1 = SE->getMinusSCEV( + Bound[K].Iterations, SE->getOne(Bound[K].Iterations->getType())); const SCEV *NegPart = getNegativePart(SE->getMinusSCEV(A[K].Coeff, B[K].PosPart)); Bound[K].Lower[Dependence::DVEntry::GT] = @@ -2805,13 +2871,13 @@ void DependenceAnalysis::findBoundsGT(CoefficientInfo *A, // X^+ = max(X, 0) const SCEV *DependenceAnalysis::getPositivePart(const SCEV *X) const { - return SE->getSMaxExpr(X, SE->getConstant(X->getType(), 0)); + return SE->getSMaxExpr(X, SE->getZero(X->getType())); } // X^- = min(X, 0) const SCEV *DependenceAnalysis::getNegativePart(const SCEV *X) const { - return SE->getSMinExpr(X, SE->getConstant(X->getType(), 0)); + return SE->getSMinExpr(X, SE->getZero(X->getType())); } @@ -2822,7 +2888,7 @@ DependenceAnalysis::CoefficientInfo * DependenceAnalysis::collectCoeffInfo(const SCEV *Subscript, bool SrcFlag, const SCEV *&Constant) const { - const SCEV *Zero = SE->getConstant(Subscript->getType(), 0); + const SCEV *Zero = SE->getZero(Subscript->getType()); CoefficientInfo *CI = new CoefficientInfo[MaxLevels + 1]; for (unsigned K = 1; K <= MaxLevels; ++K) { CI[K].Coeff = Zero; @@ -2900,13 +2966,13 @@ const SCEV *DependenceAnalysis::getUpperBound(BoundInfo *Bound) const { // return the coefficient (the step) // corresponding to the specified loop. // If there isn't one, return 0. -// For example, given a*i + b*j + c*k, zeroing the coefficient +// For example, given a*i + b*j + c*k, finding the coefficient // corresponding to the j loop would yield b. const SCEV *DependenceAnalysis::findCoefficient(const SCEV *Expr, const Loop *TargetLoop) const { const SCEVAddRecExpr *AddRec = dyn_cast(Expr); if (!AddRec) - return SE->getConstant(Expr->getType(), 0); + return SE->getZero(Expr->getType()); if (AddRec->getLoop() == TargetLoop) return AddRec->getStepRecurrence(*SE); return findCoefficient(AddRec->getStart(), TargetLoop); @@ -2956,15 +3022,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()); } @@ -3179,20 +3241,36 @@ 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 SCEV *ElementSize) const { +bool DependenceAnalysis::tryDelinearize(Instruction *Src, + Instruction *Dst, + SmallVectorImpl &Pair) +{ + Value *SrcPtr = getPointerOperand(Src); + Value *DstPtr = getPointerOperand(Dst); + + Loop *SrcLoop = LI->getLoopFor(Src->getParent()); + Loop *DstLoop = LI->getLoopFor(Dst->getParent()); + + // Below code mimics the code in Delinearization.cpp + const SCEV *SrcAccessFn = + SE->getSCEVAtScope(SrcPtr, SrcLoop); + const SCEV *DstAccessFn = + SE->getSCEVAtScope(DstPtr, DstLoop); + const SCEVUnknown *SrcBase = - dyn_cast(SE->getPointerBase(SrcSCEV)); + dyn_cast(SE->getPointerBase(SrcAccessFn)); const SCEVUnknown *DstBase = - dyn_cast(SE->getPointerBase(DstSCEV)); + dyn_cast(SE->getPointerBase(DstAccessFn)); if (!SrcBase || !DstBase || SrcBase != DstBase) return false; - SrcSCEV = SE->getMinusSCEV(SrcSCEV, SrcBase); - DstSCEV = SE->getMinusSCEV(DstSCEV, DstBase); + const SCEV *ElementSize = SE->getElementSize(Src); + if (ElementSize != SE->getElementSize(Dst)) + return false; + + const SCEV *SrcSCEV = SE->getMinusSCEV(SrcAccessFn, SrcBase); + const SCEV *DstSCEV = SE->getMinusSCEV(DstAccessFn, DstBase); const SCEVAddRecExpr *SrcAR = dyn_cast(SrcSCEV); const SCEVAddRecExpr *DstAR = dyn_cast(DstSCEV); @@ -3201,8 +3279,8 @@ bool DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV, // First step: collect parametric terms in both array references. SmallVector Terms; - SrcAR->collectParametricTerms(*SE, Terms); - DstAR->collectParametricTerms(*SE, Terms); + SE->collectParametricTerms(SrcAR, Terms); + SE->collectParametricTerms(DstAR, Terms); // Second step: find subscript sizes. SmallVector Sizes; @@ -3210,8 +3288,8 @@ bool DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV, // Third step: compute the access functions for each subscript. SmallVector SrcSubscripts, DstSubscripts; - SrcAR->computeAccessFunctions(*SE, SrcSubscripts, Sizes); - DstAR->computeAccessFunctions(*SE, DstSubscripts, Sizes); + SE->computeAccessFunctions(SrcAR, SrcSubscripts, Sizes); + SE->computeAccessFunctions(DstAR, DstSubscripts, Sizes); // Fail when there is only a subscript: that's a linearized access function. if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 || @@ -3237,6 +3315,7 @@ bool DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV, 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 @@ -3264,7 +3343,6 @@ static void dumpSmallBitVector(SmallBitVector &BV) { } #endif - // depends - // Returns NULL if there is no dependence. // Otherwise, return a Dependence with as many details as possible. @@ -3296,17 +3374,18 @@ DependenceAnalysis::depends(Instruction *Src, Instruction *Dst, Value *SrcPtr = getPointerOperand(Src); Value *DstPtr = getPointerOperand(Dst); - switch (underlyingObjectsAlias(AA, DstPtr, SrcPtr)) { - case AliasAnalysis::MayAlias: - case AliasAnalysis::PartialAlias: + switch (underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), DstPtr, + SrcPtr)) { + case MayAlias: + case PartialAlias: // cannot analyse objects if we don't understand their aliasing. DEBUG(dbgs() << "can't analyze may or partial alias\n"); return make_unique(Src, Dst); - case AliasAnalysis::NoAlias: + case NoAlias: // If the objects noalias, they are distinct, accesses are independent. DEBUG(dbgs() << "no alias\n"); return nullptr; - case AliasAnalysis::MustAlias: + case MustAlias: break; // The underlying objects alias; test accesses for dependence. } @@ -3329,9 +3408,9 @@ DependenceAnalysis::depends(Instruction *Src, Instruction *Dst, DEBUG(dbgs() << " SrcPtrSCEV = " << *SrcPtrSCEV << "\n"); DEBUG(dbgs() << " DstPtrSCEV = " << *DstPtrSCEV << "\n"); - UsefulGEP = - isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) && - isLoopInvariant(DstPtrSCEV, LI->getLoopFor(Dst->getParent())); + UsefulGEP = isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) && + isLoopInvariant(DstPtrSCEV, LI->getLoopFor(Dst->getParent())) && + (SrcGEP->getNumOperands() == DstGEP->getNumOperands()); } unsigned Pairs = UsefulGEP ? SrcGEP->idx_end() - SrcGEP->idx_begin() : 1; SmallVector Pair(Pairs); @@ -3345,6 +3424,7 @@ DependenceAnalysis::depends(Instruction *Src, Instruction *Dst, ++SrcIdx, ++DstIdx, ++P) { Pair[P].Src = SE->getSCEV(*SrcIdx); Pair[P].Dst = SE->getSCEV(*DstIdx); + unifySubscriptType(&Pair[P]); } } else { @@ -3357,10 +3437,11 @@ DependenceAnalysis::depends(Instruction *Src, Instruction *Dst, 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(); + if (Delinearize && CommonLevels > 1) { + if (tryDelinearize(Src, Dst, Pair)) { + DEBUG(dbgs() << " delinerized GEP\n"); + Pairs = Pair.size(); + } } for (unsigned P = 0; P < Pairs; ++P) { @@ -3453,8 +3534,7 @@ DependenceAnalysis::depends(Instruction *Src, Instruction *Dst, LI->getLoopFor(Dst->getParent()), Pair[SI].Loops); Result.Consistent = false; - } - else if (Pair[SI].Classification == Subscript::ZIV) { + } else if (Pair[SI].Classification == Subscript::ZIV) { // always separable Separable.set(SI); } @@ -3506,8 +3586,8 @@ DependenceAnalysis::depends(Instruction *Src, Instruction *Dst, DEBUG(dbgs() << ", SIV\n"); unsigned Level; const SCEV *SplitIter = nullptr; - if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level, - Result, NewConstraint, SplitIter)) + if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level, Result, NewConstraint, + SplitIter)) return nullptr; break; } @@ -3539,13 +3619,16 @@ DependenceAnalysis::depends(Instruction *Src, Instruction *Dst, SmallBitVector Sivs(Pairs); SmallBitVector Mivs(Pairs); SmallBitVector ConstrainedLevels(MaxLevels + 1); + SmallVector PairsInGroup; for (int SJ = Group.find_first(); SJ >= 0; SJ = Group.find_next(SJ)) { DEBUG(dbgs() << SJ << " "); if (Pair[SJ].Classification == Subscript::SIV) Sivs.set(SJ); else Mivs.set(SJ); + PairsInGroup.push_back(&Pair[SJ]); } + unifySubscriptType(PairsInGroup); DEBUG(dbgs() << "}\n"); while (Sivs.any()) { bool Changed = false; @@ -3555,8 +3638,8 @@ DependenceAnalysis::depends(Instruction *Src, Instruction *Dst, unsigned Level; const SCEV *SplitIter = nullptr; DEBUG(dbgs() << "SIV\n"); - if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, - Result, NewConstraint, SplitIter)) + if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint, + SplitIter)) return nullptr; ConstrainedLevels.set(Level); if (intersectConstraints(&Constraints[Level], &NewConstraint)) { @@ -3632,8 +3715,10 @@ DependenceAnalysis::depends(Instruction *Src, Instruction *Dst, // update Result.DV from constraint vector DEBUG(dbgs() << " updating\n"); - for (int SJ = ConstrainedLevels.find_first(); - SJ >= 0; SJ = ConstrainedLevels.find_next(SJ)) { + for (int SJ = ConstrainedLevels.find_first(); SJ >= 0; + SJ = ConstrainedLevels.find_next(SJ)) { + if (SJ > (int)CommonLevels) + break; updateDirection(Result.DV[SJ - 1], Constraints[SJ]); if (Result.DV[SJ - 1].Direction == Dependence::DVEntry::NONE) return nullptr; @@ -3674,9 +3759,7 @@ DependenceAnalysis::depends(Instruction *Src, Instruction *Dst, return nullptr; } - auto Final = make_unique(Result); - Result.DV = nullptr; - return std::move(Final); + return make_unique(std::move(Result)); } @@ -3740,8 +3823,8 @@ const SCEV *DependenceAnalysis::getSplitIteration(const Dependence &Dep, assert(isLoadOrStore(Dst)); Value *SrcPtr = getPointerOperand(Src); Value *DstPtr = getPointerOperand(Dst); - assert(underlyingObjectsAlias(AA, DstPtr, SrcPtr) == - AliasAnalysis::MustAlias); + assert(underlyingObjectsAlias(AA, F->getParent()->getDataLayout(), DstPtr, + SrcPtr) == MustAlias); // establish loop nesting levels establishNestingLevels(Src, Dst); @@ -3756,9 +3839,9 @@ const SCEV *DependenceAnalysis::getSplitIteration(const Dependence &Dep, SrcGEP->getPointerOperandType() == DstGEP->getPointerOperandType()) { const SCEV *SrcPtrSCEV = SE->getSCEV(SrcGEP->getPointerOperand()); const SCEV *DstPtrSCEV = SE->getSCEV(DstGEP->getPointerOperand()); - UsefulGEP = - isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) && - isLoopInvariant(DstPtrSCEV, LI->getLoopFor(Dst->getParent())); + UsefulGEP = isLoopInvariant(SrcPtrSCEV, LI->getLoopFor(Src->getParent())) && + isLoopInvariant(DstPtrSCEV, LI->getLoopFor(Dst->getParent())) && + (SrcGEP->getNumOperands() == DstGEP->getNumOperands()); } unsigned Pairs = UsefulGEP ? SrcGEP->idx_end() - SrcGEP->idx_begin() : 1; SmallVector Pair(Pairs); @@ -3780,10 +3863,11 @@ 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(); + if (Delinearize && CommonLevels > 1) { + if (tryDelinearize(Src, Dst, Pair)) { + DEBUG(dbgs() << " delinerized GEP\n"); + Pairs = Pair.size(); + } } for (unsigned P = 0; P < Pairs; ++P) {