[LoopCacheAnalysis] Improve cost heuristic.

[etiotto]

Summary

Improve the cache cost estimation for indexed references that are not consecutive. For example, given the indexed reference 'A[i][j][k]', and assuming the j-loop is in the innermost position in the loop nest containing the array reference, the cost would be equal to the RefCost cost times the iterations of the j-loop (rather than just the RefCost).

[bmahjour]

llvm/include/llvm/Analysis/LoopCacheAnalysis.h

107

would be useful to mention that the index is zero-based. ie: "Retrive the zero-based \p Index of the subscript ..."

llvm/lib/Analysis/LoopCacheAnalysis.cpp

310

but in the code below we multiply the trip count for all indexes starting from the given loop up to the loop for the second last subscript.

320

why getNumSubscripts() - 1 instead of just getNumSubscripts() ?

[Meinersbur]

llvm/lib/Analysis/LoopCacheAnalysis.cpp

106–119

[sugggestion]

if (auto *TripCount = dyn_cast<SCEVConstant>(BackedgeTakenCount)) 
  return SE.getAddExpr(BackedgeTakenCount, SE.getOne(BackedgeTakenCount->getType())

LLVM_DEBUG(dbgs() << "Trip count of loop " << L.getName() << " could not be computed, using DefaultTripCount\n");
return SE.getConstant(ElemSize.getType(), DefaultTripCount);

107

isa<SCEVCouldNotCompute> is redundant: the object cannot be SCEVCouldNotCompute and SCEVConstant at the same time

452

What if:

• Multiple subscripts are using the loop variables?
• A subscript uses multiple loop variables (eg. i+j)?
• SCEVAddRecExpr is processed further, e.g. negated?

llvm/include/llvm/Analysis/LoopCacheAnalysis.h

private:
   bool isLoopInvariant(const Loop &L) const;
 
   /// Return true if the indexed reference is 'consecutive' in loop \p L.
   /// An indexed reference is 'consecutive' if the only coefficient that uses
   /// the loop induction variable is the rightmost one, and the access stride is
   /// smaller than the cache line size \p CLS.
   bool isConsecutive(const Loop &L, unsigned CLS) const;
 
+  /// Retrieve the \p Index of the subscript corresponding to the given loop \p
+  /// L. Return true if the subscript index is succesfully located and false
+  /// otherwise. For example given the indexed reference 'A[i][2j+1][3k+2][l]',
+  /// the call 'getSubscriptIndex(loop-k,Index)' would fill \p Index with the
+  /// value 2 and return true.
+  bool getSubscriptIndex(const Loop &L, unsigned &Index) const;
+
   /// Return the coefficient used in the rightmost dimension.
   const SCEV *getLastCoefficient() const;
 
   /// Return true if the coefficient corresponding to induction variable of
   /// loop \p L in the given \p Subscript is zero or is loop invariant in \p L.
   bool isCoeffForLoopZeroOrInvariant(const SCEV &Subscript,
                                      const Loop &L) const;
 

llvm/lib/Analysis/LoopCacheAnalysis.cpp

static bool isOneDimensionalArray(const SCEV &AccessFn, const SCEV &ElemSize,
 
   const SCEV *StepRec = AR->getStepRecurrence(SE);
   if (StepRec && SE.isKnownNegative(StepRec))
     StepRec = SE.getNegativeSCEV(StepRec);
 
   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<SCEVCouldNotCompute>(BackedgeTakenCount) ||
-      !isa<SCEVConstant>(BackedgeTakenCount))
-    return nullptr;
+  const SCEV *TripCount =
+      (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) &&
+       isa<SCEVConstant>(BackedgeTakenCount))
+          ? SE.getAddExpr(BackedgeTakenCount,
+                          SE.getOne(BackedgeTakenCount->getType()))
+          : 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 SE.getAddExpr(BackedgeTakenCount,
-                       SE.getOne(BackedgeTakenCount->getType()));
+  return TripCount;
 }
 
 //===----------------------------------------------------------------------===//
 // IndexedReference implementation
 //
 raw_ostream &llvm::operator<<(raw_ostream &OS, const IndexedReference &R) {
   if (!R.IsValid) {
     OS << R.StoreOrLoadInst;
CacheCostTy IndexedReference::computeRefCost(const Loop &L,
   });
 
   // If the indexed reference is loop invariant the cost is one.
   if (isLoopInvariant(L)) {
     LLVM_DEBUG(dbgs().indent(4) << "Reference is loop invariant: RefCost=1\n");
     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);
     const SCEV *CacheLineSize = SE.getConstant(Stride->getType(), CLS);
     Type *WiderType = SE.getWiderType(Stride->getType(), TripCount->getType());
     if (SE.isKnownNegative(Stride))
       Stride = SE.getNegativeSCEV(Stride);
     Stride = SE.getNoopOrAnyExtend(Stride, WiderType);
     TripCount = SE.getNoopOrAnyExtend(TripCount, WiderType);
     const SCEV *Numerator = SE.getMulExpr(Stride, TripCount);
     RefCost = SE.getUDivExpr(Numerator, CacheLineSize);
 
     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 equal to the
+    // number of iterations associated with the subscript corresponding to the
+    // loop. For example, given the indexed reference 'A[i][j][k]', and assuming
+    // the j-loop is in the innermost position, the cost would be equal to the
+    // iterations of the j-loop.
+    RefCost = TripCount;
+
+    unsigned Index = 0;
+    bool Found = getSubscriptIndex(L, Index);
+    assert(Found && "Cound not locate a valid Index");
+
+    for (unsigned I = Index + 1; I < getNumSubscripts() - 1; ++I) {
+      const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(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<SCEVConstant>(RefCost))
     return ConstantCost->getValue()->getSExtValue();
 
   LLVM_DEBUG(dbgs().indent(4)
              << "RefCost is not a constant! Setting to RefCost=InvalidCost "
                 "(invalid value).\n");
bool IndexedReference::isConsecutive(const Loop &L, unsigned CLS) const {
   const SCEV *ElemSize = Sizes.back();
   const SCEV *Stride = SE.getMulExpr(Coeff, ElemSize);
   const SCEV *CacheLineSize = SE.getConstant(Stride->getType(), CLS);
 
   Stride = SE.isKnownNegative(Stride) ? SE.getNegativeSCEV(Stride) : Stride;
   return SE.isKnownPredicate(ICmpInst::ICMP_ULT, Stride, CacheLineSize);
 }
 
+bool IndexedReference::getSubscriptIndex(const Loop &L, unsigned &Index) const {
+  for (auto Idx : seq<unsigned>(0, getNumSubscripts())) {
+    const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(getSubscript(Idx));
+    if (AR && AR->getLoop() == &L) {
+      Index = Idx;
+      return true;
+    }
+  }
+  return false;
+}
+
 const SCEV *IndexedReference::getLastCoefficient() const {
   const SCEV *LastSubscript = getLastSubscript();
   assert(isa<SCEVAddRecExpr>(LastSubscript) &&
          "Expecting a SCEV add recurrence expression");
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(LastSubscript);
   return AR->getStepRecurrence(SE);
 }
 

llvm/test/Analysis/LoopCacheAnalysis/PowerPC/matvecmul.ll

 ; RUN: opt < %s -passes='print<loop-cache-cost>' -disable-output 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-n32:64"
 target triple = "powerpc64le-unknown-linux-gnu"
 
 ; void matvecmul(const double *__restrict y, const double * __restrict x, const double * __restrict b,
 ;    const int * __restrict nb, const int * __restrict nx, const int * __restrict ny, const int * __restrict nz) {
 ;
 ;   for (int k=1;k<nz,++k) 
 ;      for (int j=1;j<ny,++j)
 ;        for (int i=1;i<nx,++i)
 ;          for (int l=1;l<nb,++l)
 ;            for (int m=1;m<nb,++m)
 ;                 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
 
 %_elem_type_of_double = type <{ double }>
 
 ; Function Attrs: norecurse nounwind
 define void @mat_vec_mpy([0 x %_elem_type_of_double]* noalias %y, [0 x %_elem_type_of_double]* noalias readonly %x,
     [0 x %_elem_type_of_double]* noalias readonly %b, i32* noalias readonly %nb, i32* noalias readonly %nx,