[LoopCacheAnalysis]: Fix assertion failure during cost computation

[rcraik]

Summary

During calculation of the reference cost, possible type differences between the Stride and TripCount are not taken into account, which can result in assertion failure in ScalarEvolution::getMulExpr that the operand types do not match.

This patch addresses this issue.

[bmahjour]

llvm/lib/Analysis/LoopCacheAnalysis.cpp

287

const Type *WiderType?

llvm/test/Analysis/LoopCacheAnalysis/PowerPC/compute-cost.ll

3

A comment saying what the test is testing would be useful.

11

are dso_local, nocapture, local_unnamed_addr necessary?

[rcraik]

llvm/lib/Analysis/LoopCacheAnalysis.cpp

287

ScalarEvolution::getNoopOrAnyExtend does not take a constant type

[rcraik]

Updated to address comments from @bmahjour in relation to the testcase

[jdoerfert]

Before I saw that the cost has to be a constant I wrote this:

I'm unsure if a sign extend would not be more appropriate for the stride (for the trip count it doesn't matter I guess), but at the end of the day this is "just" a heuristic.
Feel free to update it to sign extend if you feel that it is appropriate. Maybe try out with a negative stride test if you can see a difference.

Given that it has to be a constant it does not matter. If that might change, consider my comment above.

Otherwise, LGTM.

[rcraik]

Update Stride to use sign extension

llvm/lib/Analysis/LoopCacheAnalysis.cpp

CacheCostTy IndexedReference::computeRefCost(const Loop &L,
   // (TripCount*Stride)/CLS, otherwise the cost is TripCount.
   const SCEV *RefCost = TripCount;
 
   if (isConsecutive(L, CLS)) {
     const SCEV *Coeff = getLastCoefficient();
     const SCEV *ElemSize = Sizes.back();
     const SCEV *Stride = SE.getMulExpr(Coeff, ElemSize);
     const SCEV *CacheLineSize = SE.getConstant(Stride->getType(), CLS);
+    Type *WiderType = SE.getWiderType(Stride->getType(), TripCount->getType());
+    Stride = SE.getNoopOrSignExtend(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
     LLVM_DEBUG(dbgs().indent(4)
                << "Access is not consecutive: RefCost=TripCount=" << *RefCost

llvm/test/Analysis/LoopCacheAnalysis/PowerPC/compute-cost.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"
+
+; Check IndexedReference::computeRefCost can handle type differences between
+; Stride and TripCount
+
+; CHECK: Loop 'for.cond' has cost = 64
+
+%struct._Handleitem = type { %struct._Handleitem* }
+
+define void @handle_to_ptr(%struct._Handleitem** %blocks) {
+; Preheader:
+entry:
+  br label %for.cond
+
+; Loop:
+for.cond:                                         ; preds = %for.body, %entry
+  %i.0 = phi i32 [ 1, %entry ], [ %inc, %for.body ]
+  %cmp = icmp ult i32 %i.0, 1024
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %idxprom = zext i32 %i.0 to i64
+  %arrayidx = getelementptr inbounds %struct._Handleitem*, %struct._Handleitem** %blocks, i64 %idxprom
+  store %struct._Handleitem* null, %struct._Handleitem** %arrayidx, align 8
+  %inc = add nuw nsw i32 %i.0, 1
+  br label %for.cond
+
+; Exit blocks
+for.end:                                          ; preds = %for.cond
+  ret void
+
+}