diff --git a/llvm/include/llvm/Analysis/LoopCacheAnalysis.h b/llvm/include/llvm/Analysis/LoopCacheAnalysis.h --- a/llvm/include/llvm/Analysis/LoopCacheAnalysis.h +++ b/llvm/include/llvm/Analysis/LoopCacheAnalysis.h @@ -107,6 +107,13 @@ /// smaller than the cache line size \p CLS. bool isConsecutive(const Loop &L, unsigned CLS) const; + /// Retrieve the index of the subscript corresponding to the given loop \p + /// L. Return a zero-based positive index if the subscript index is + /// succesfully located and a negative value otherwise. For example given the + /// indexed reference 'A[i][2j+1][3k+2]', the call + /// 'getSubscriptIndex(loop-k)' would return value 2. + unsigned getSubscriptIndex(const Loop &L) const; + /// Return the coefficient used in the rightmost dimension. const SCEV *getLastCoefficient() const; diff --git a/llvm/lib/Analysis/LoopCacheAnalysis.cpp b/llvm/lib/Analysis/LoopCacheAnalysis.cpp --- a/llvm/lib/Analysis/LoopCacheAnalysis.cpp +++ b/llvm/lib/Analysis/LoopCacheAnalysis.cpp @@ -103,14 +103,24 @@ return StepRec == &ElemSize; } -/// Compute the trip count for the given loop \p L. Return the SCEV expression -/// for the trip count or nullptr if it cannot be computed. -static const SCEV *computeTripCount(const Loop &L, ScalarEvolution &SE) { +/// Compute the trip count for the given loop \p L or assume a default value if +/// it is not a compile time constant. Return the SCEV expression for the trip +/// count. +static const SCEV *computeTripCount(const Loop &L, const SCEV &ElemSize, + ScalarEvolution &SE) { const SCEV *BackedgeTakenCount = SE.getBackedgeTakenCount(&L); - if (isa(BackedgeTakenCount) || - !isa(BackedgeTakenCount)) - return nullptr; - return SE.getTripCountFromExitCount(BackedgeTakenCount); + const SCEV *TripCount = (!isa(BackedgeTakenCount) && + isa(BackedgeTakenCount)) + ? SE.getTripCountFromExitCount(BackedgeTakenCount) + : nullptr; + + if (!TripCount) { + LLVM_DEBUG(dbgs() << "Trip count of loop " << L.getName() + << " could not be computed, using DefaultTripCount\n"); + TripCount = SE.getConstant(ElemSize.getType(), DefaultTripCount); + } + + return TripCount; } //===----------------------------------------------------------------------===// @@ -274,22 +284,18 @@ return 1; } - const SCEV *TripCount = computeTripCount(L, SE); - if (!TripCount) { - LLVM_DEBUG(dbgs() << "Trip count of loop " << L.getName() - << " could not be computed, using DefaultTripCount\n"); - const SCEV *ElemSize = Sizes.back(); - TripCount = SE.getConstant(ElemSize->getType(), DefaultTripCount); - } + const SCEV *TripCount = computeTripCount(L, *Sizes.back(), SE); + assert(TripCount && "Expecting valid TripCount"); LLVM_DEBUG(dbgs() << "TripCount=" << *TripCount << "\n"); - // If the indexed reference is 'consecutive' the cost is - // (TripCount*Stride)/CLS, otherwise the cost is TripCount. - const SCEV *RefCost = TripCount; - + const SCEV *RefCost = nullptr; if (isConsecutive(L, CLS)) { + // If the indexed reference is 'consecutive' the cost is + // (TripCount*Stride)/CLS. const SCEV *Coeff = getLastCoefficient(); const SCEV *ElemSize = Sizes.back(); + assert(Coeff->getType() == ElemSize->getType() && + "Expecting the same type"); const SCEV *Stride = SE.getMulExpr(Coeff, ElemSize); Type *WiderType = SE.getWiderType(Stride->getType(), TripCount->getType()); const SCEV *CacheLineSize = SE.getConstant(WiderType, CLS); @@ -303,10 +309,33 @@ LLVM_DEBUG(dbgs().indent(4) << "Access is consecutive: RefCost=(TripCount*Stride)/CLS=" << *RefCost << "\n"); - } else + } else { + // If the indexed reference is not 'consecutive' the cost is proportional to + // the trip count and the depth of the dimension which the subject loop + // subscript is accessing. We try to estimate this by multiplying the cost + // by the trip counts of loops corresponding to the inner dimensions. For + // example, given the indexed reference 'A[i][j][k]', and assuming the + // i-loop is in the innermost position, the cost would be equal to the + // iterations of the i-loop multiplied by iterations of the j-loop. + RefCost = TripCount; + + unsigned Index = getSubscriptIndex(L); + assert(Index >= 0 && "Cound not locate a valid Index"); + + for (unsigned I = Index + 1; I < getNumSubscripts() - 1; ++I) { + const SCEVAddRecExpr *AR = dyn_cast(getSubscript(I)); + assert(AR && AR->getLoop() && "Expecting valid loop"); + const SCEV *TripCount = + computeTripCount(*AR->getLoop(), *Sizes.back(), SE); + Type *WiderType = SE.getWiderType(RefCost->getType(), TripCount->getType()); + RefCost = SE.getMulExpr(SE.getNoopOrAnyExtend(RefCost, WiderType), + SE.getNoopOrAnyExtend(TripCount, WiderType)); + } + LLVM_DEBUG(dbgs().indent(4) - << "Access is not consecutive: RefCost=TripCount=" << *RefCost - << "\n"); + << "Access is not consecutive: RefCost=" << *RefCost << "\n"); + } + assert(RefCost && "Expecting a valid RefCost"); // Attempt to fold RefCost into a constant. if (auto ConstantCost = dyn_cast(RefCost)) @@ -424,6 +453,16 @@ return SE.isKnownPredicate(ICmpInst::ICMP_ULT, Stride, CacheLineSize); } +unsigned IndexedReference::getSubscriptIndex(const Loop &L) const { + for (auto Idx : seq(0, getNumSubscripts())) { + const SCEVAddRecExpr *AR = dyn_cast(getSubscript(Idx)); + if (AR && AR->getLoop() == &L) { + return Idx; + } + } + return -1; +} + const SCEV *IndexedReference::getLastCoefficient() const { const SCEV *LastSubscript = getLastSubscript(); auto *AR = cast(LastSubscript); diff --git a/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/matvecmul.ll b/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/matvecmul.ll --- a/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/matvecmul.ll +++ b/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/matvecmul.ll @@ -14,9 +14,9 @@ ; y[k+1][j][i][l] = y[k+1][j][i][l] + b[k][j][i][m][l]*x[k][j][i][m] ; } -; CHECK-DAG: Loop 'k_loop' has cost = 30000000000 -; CHECK-DAG: Loop 'j_loop' has cost = 30000000000 -; CHECK-DAG: Loop 'i_loop' has cost = 30000000000 +; CHECK-DAG: Loop 'k_loop' has cost = 10200000000000000 +; CHECK-DAG: Loop 'j_loop' has cost = 102000000000000 +; CHECK-DAG: Loop 'i_loop' has cost = 1020000000000 ; CHECK-DAG: Loop 'm_loop' has cost = 10700000000 ; CHECK-DAG: Loop 'l_loop' has cost = 1300000000 diff --git a/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/single-store.ll b/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/single-store.ll --- a/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/single-store.ll +++ b/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/single-store.ll @@ -10,7 +10,7 @@ ; A[2*i+3][3*j-4][2*k+7] = 1; ; } -; CHECK-DAG: Loop 'for.i' has cost = 1000000 +; CHECK-DAG: Loop 'for.i' has cost = 100000000 ; CHECK-DAG: Loop 'for.j' has cost = 1000000 ; CHECK-DAG: Loop 'for.k' has cost = 60000