TTI: Honour cost model for estimating cost of vector-intrinsic and calls.

[mzolotukhin]

Summary

TTI: Honour cost model for estimating cost of vector-intrinsic and calls.
Update tests in correspondance with changes in cost model.

This is the fifth of 6 patches for enabling vectorization of calls.

[hfinkel]

include/llvm/CodeGen/BasicTTIImpl.h

548

Why are you changing the default cost for intrinsics from one to ten? I believe it used to be one, and that was because we made an explicit decision to make intrinsics default to something cheap.

[mzolotukhin]

include/llvm/CodeGen/BasicTTIImpl.h

548

I made two changes here:

1. Change 10 * Cost * Num to ScalarCalls * ScalarCost + ScalarizationOverhead. I believe factor 10 initially was used to model the scalarization overhead, but now we can estimate it more accurately.

2. Change ScalarCalls + ScalarizationCost to ScalarCalls*10 + ScalarizationCost. To me it looked a bit inconsistent: when an unknown intrinsic has a vector type, we returned ScalarCalls + ScalarizationCost (effectively, ScalarCost is implicitly assumed to be 1). However, for known intrinsics scalar cost is 10 (unless the operation is legal and we know exact cost). I can revert this change, but the original code just looked a bit odd to me.

However, I can find explanation like "we expect all unknown intrinsics to be lowered to somewhat cheap (cost=1), in contrast to the listed ones, which will definitely be lowered to an expensive libcall (cost=10)". If that's the case, I agree that the original code is correct.

[hfinkel]

include/llvm/CodeGen/BasicTTIImpl.h

548

However, I can find explanation like "we expect all unknown intrinsics to be lowered to somewhat cheap (cost=1), in contrast to the listed ones, which will definitely be lowered to an expensive libcall (cost=10)". If that's the case, I agree that the original code is correct.

Yes, I believe that was the logic, and the original code was consistent with that reasoning.

[mzolotukhin]

• Address Hal's remark: do not change cost of scalar intrinsics from 1 to 10.

[mzolotukhin]

• Readjust tests back.

[hfinkel]

LGTM.

[mzolotukhin]

Thanks, committed in r232528!

include/llvm/CodeGen/BasicTTIImpl.h

public:
   unsigned getIntrinsicInstrCost(Intrinsic::ID IID, Type *RetTy,
                                  ArrayRef<Type *> Tys) {
     unsigned ISD = 0;
     switch (IID) {
     default: {
       // Assume that we need to scalarize this intrinsic.
       unsigned ScalarizationCost = 0;
       unsigned ScalarCalls = 1;
+      Type *ScalarRetTy = RetTy;
       if (RetTy->isVectorTy()) {
         ScalarizationCost = getScalarizationOverhead(RetTy, true, false);
         ScalarCalls = std::max(ScalarCalls, RetTy->getVectorNumElements());
+        ScalarRetTy = RetTy->getScalarType();
       }
+      SmallVector<Type *, 4> ScalarTys;
       for (unsigned i = 0, ie = Tys.size(); i != ie; ++i) {
-        if (Tys[i]->isVectorTy()) {
-          ScalarizationCost += getScalarizationOverhead(Tys[i], false, true);
-          ScalarCalls = std::max(ScalarCalls, Tys[i]->getVectorNumElements());
+        Type *Ty = Tys[i];
+        if (Ty->isVectorTy()) {
+          ScalarizationCost += getScalarizationOverhead(Ty, false, true);
+          ScalarCalls = std::max(ScalarCalls, Ty->getVectorNumElements());
+          Ty = Ty->getScalarType();
         }
+        ScalarTys.push_back(Ty);
       }
+      if (ScalarCalls == 1)
+        return 1; // Return cost of a scalar intrinsic. Assume it to be cheap.
+
+      unsigned ScalarCost = static_cast<T *>(this)->getIntrinsicInstrCost(
+          IID, ScalarRetTy, ScalarTys);
 
-      return ScalarCalls + ScalarizationCost;
+      return ScalarCalls * ScalarCost + ScalarizationCost;
     }
     // Look for intrinsics that can be lowered directly or turned into a scalar
     // intrinsic call.
     case Intrinsic::sqrt:
       ISD = ISD::FSQRT;
       break;
     case Intrinsic::sin:
       ISD = ISD::FSIN;
if (IID == Intrinsic::fmuladd)
                  ->getArithmeticInstrCost(BinaryOperator::FMul, RetTy) +
              static_cast<T *>(this)
                  ->getArithmeticInstrCost(BinaryOperator::FAdd, RetTy);
 
     // Else, assume that we need to scalarize this intrinsic. For math builtins
     // this will emit a costly libcall, adding call overhead and spills. Make it
     // very expensive.
     if (RetTy->isVectorTy()) {
-      unsigned Num = RetTy->getVectorNumElements();
-      unsigned Cost = static_cast<T *>(this)->getIntrinsicInstrCost(
-          IID, RetTy->getScalarType(), Tys);
-      return 10 * Cost * Num;
+      unsigned ScalarizationCost = getScalarizationOverhead(RetTy, true, false);
+      unsigned ScalarCalls = RetTy->getVectorNumElements();
+      SmallVector<Type *, 4> ScalarTys;
+      for (unsigned i = 0, ie = Tys.size(); i != ie; ++i) {
+        Type *Ty = Tys[i];
+        if (Ty->isVectorTy())
+          Ty = Ty->getScalarType();
+        ScalarTys.push_back(Ty);
+      }
+      unsigned ScalarCost = static_cast<T *>(this)->getIntrinsicInstrCost(
+          IID, RetTy->getScalarType(), ScalarTys);
+      for (unsigned i = 0, ie = Tys.size(); i != ie; ++i) {
+        if (Tys[i]->isVectorTy()) {
+          ScalarizationCost += getScalarizationOverhead(Tys[i], false, true);
+          ScalarCalls = std::max(ScalarCalls, Tys[i]->getVectorNumElements());
+        }
+      }
+
+      return ScalarCalls * ScalarCost + ScalarizationCost;
     }
 
     // This is going to be turned into a library call, make it expensive.
     return 10;
   }
 
   /// Compute a cost of the given call instruction.
   /// \param F Called function.

test/Analysis/CostModel/X86/intrinsic-cost.ll

vector.body:                                      ; preds = %vector.body, %vector.ph
   %index.next = add i64 %index, 4
   %3 = icmp eq i64 %index.next, 1024
   br i1 %3, label %for.end, label %vector.body
 
 for.end:                                          ; preds = %vector.body
   ret void
 
 ; CORE2: Printing analysis 'Cost Model Analysis' for function 'test1':
-; CORE2: Cost Model: Found an estimated cost of 400 for instruction:   %2 = call <4 x float> @llvm.ceil.v4f32(<4 x float> %wide.load)
+; CORE2: Cost Model: Found an estimated cost of 46 for instruction:   %2 = call <4 x float> @llvm.ceil.v4f32(<4 x float> %wide.load)
 
 ; COREI7: Printing analysis 'Cost Model Analysis' for function 'test1':
 ; COREI7: Cost Model: Found an estimated cost of 1 for instruction:   %2 = call <4 x float> @llvm.ceil.v4f32(<4 x float> %wide.load)
 
 }
 
 declare <4 x float> @llvm.ceil.v4f32(<4 x float>)  nounwind readnone
 
vector.body:                                      ; preds = %vector.body, %vector.ph
   %index.next = add i64 %index, 4
   %3 = icmp eq i64 %index.next, 1024
   br i1 %3, label %for.end, label %vector.body
 
 for.end:                                          ; preds = %vector.body
   ret void
 
 ; CORE2: Printing analysis 'Cost Model Analysis' for function 'test2':
-; CORE2: Cost Model: Found an estimated cost of 400 for instruction:   %2 = call <4 x float> @llvm.nearbyint.v4f32(<4 x float> %wide.load)
+; CORE2: Cost Model: Found an estimated cost of 46 for instruction:   %2 = call <4 x float> @llvm.nearbyint.v4f32(<4 x float> %wide.load)
 
 ; COREI7: Printing analysis 'Cost Model Analysis' for function 'test2':
 ; COREI7: Cost Model: Found an estimated cost of 1 for instruction:   %2 = call <4 x float> @llvm.nearbyint.v4f32(<4 x float> %wide.load)
 
 }
 
 declare <4 x float> @llvm.nearbyint.v4f32(<4 x float>)  nounwind readnone
 

test/Analysis/CostModel/X86/scalarize.ll

 declare %i4 @llvm.ctpop.v4i32(%i4)
 declare %i8 @llvm.ctpop.v2i64(%i8)
 
 ; CHECK32-LABEL: test_scalarized_intrinsics
 ; CHECK64-LABEL: test_scalarized_intrinsics
 define void @test_scalarized_intrinsics() {
         %r1 = add %i8 undef, undef
 
-; CHECK32: cost of 12 {{.*}}bswap.v4i32
-; CHECK64: cost of 12 {{.*}}bswap.v4i32
+; CHECK32: cost of 48 {{.*}}bswap.v4i32
+; CHECK64: cost of 48 {{.*}}bswap.v4i32
         %r2 = call %i4 @llvm.bswap.v4i32(%i4 undef)
-; CHECK32: cost of 10 {{.*}}bswap.v2i64
-; CHECK64: cost of 6 {{.*}}bswap.v2i64
+; CHECK32: cost of 28 {{.*}}bswap.v2i64
+; CHECK64: cost of 24 {{.*}}bswap.v2i64
         %r3 = call %i8 @llvm.bswap.v2i64(%i8 undef)
 
-; CHECK32: cost of 12 {{.*}}ctpop.v4i32
-; CHECK64: cost of 12 {{.*}}ctpop.v4i32
+; CHECK32: cost of 48 {{.*}}ctpop.v4i32
+; CHECK64: cost of 48 {{.*}}ctpop.v4i32
         %r4 = call %i4 @llvm.ctpop.v4i32(%i4 undef)
-; CHECK32: cost of 10 {{.*}}ctpop.v2i64
-; CHECK64: cost of 6 {{.*}}ctpop.v2i64
+; CHECK32: cost of 28 {{.*}}ctpop.v2i64
+; CHECK64: cost of 24 {{.*}}ctpop.v2i64
         %r5 = call %i8 @llvm.ctpop.v2i64(%i8 undef)
 
 ; CHECK32: ret
 ; CHECK64: ret
         ret void
 }

test/Transforms/LoopVectorize/X86/vect.omp.force.ll

 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.8.0"
 
 ;
 ; The source code for the test:
 ;
 ; #include <math.h>
-; void foo(float* restrict A, float * restrict B, int size)
+; void foo(float* restrict A, float * restrict B)
 ; {
-;   for (int i = 0; i < size; ++i) A[i] = sinf(B[i]);
+;   for (int i = 0; i < 1000; i+=2) A[i] = sinf(B[i]);
 ; }
 ;
 
 ;
 ; This loop will be vectorized, although the scalar cost is lower than any of vector costs, but vectorization is explicitly forced in metadata.
 ;
 
-define void @vectorized(float* noalias nocapture %A, float* noalias nocapture %B, i32 %size) {
+define void @vectorized(float* noalias nocapture %A, float* noalias nocapture %B) {
 entry:
-  %cmp6 = icmp sgt i32 %size, 0
-  br i1 %cmp6, label %for.body.preheader, label %for.end
-
-for.body.preheader:
   br label %for.body
 
 for.body:
-  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
   %arrayidx = getelementptr inbounds float, float* %B, i64 %indvars.iv
   %0 = load float, float* %arrayidx, align 4, !llvm.mem.parallel_loop_access !1
   %call = tail call float @llvm.sin.f32(float %0)
   %arrayidx2 = getelementptr inbounds float, float* %A, i64 %indvars.iv
   store float %call, float* %arrayidx2, align 4, !llvm.mem.parallel_loop_access !1
-  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 2
   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
-  %exitcond = icmp eq i32 %lftr.wideiv, %size
+  %exitcond = icmp eq i32 %lftr.wideiv, 1000
   br i1 %exitcond, label %for.end.loopexit, label %for.body, !llvm.loop !1
 
 for.end.loopexit:
   br label %for.end
 
 for.end:
   ret void
 }
 
 !1 = !{!1, !2}
 !2 = !{!"llvm.loop.vectorize.enable", i1 true}
 
 ;
 ; This method will not be vectorized, as scalar cost is lower than any of vector costs.
 ;
 
-define void @not_vectorized(float* noalias nocapture %A, float* noalias nocapture %B, i32 %size) {
+define void @not_vectorized(float* noalias nocapture %A, float* noalias nocapture %B) {
 entry:
-  %cmp6 = icmp sgt i32 %size, 0
-  br i1 %cmp6, label %for.body.preheader, label %for.end
-
-for.body.preheader:
   br label %for.body
 
 for.body:
-  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %for.body.preheader ]
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
   %arrayidx = getelementptr inbounds float, float* %B, i64 %indvars.iv
   %0 = load float, float* %arrayidx, align 4, !llvm.mem.parallel_loop_access !3
   %call = tail call float @llvm.sin.f32(float %0)
   %arrayidx2 = getelementptr inbounds float, float* %A, i64 %indvars.iv
   store float %call, float* %arrayidx2, align 4, !llvm.mem.parallel_loop_access !3
-  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 2
   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
-  %exitcond = icmp eq i32 %lftr.wideiv, %size
+  %exitcond = icmp eq i32 %lftr.wideiv, 1000
   br i1 %exitcond, label %for.end.loopexit, label %for.body, !llvm.loop !3
 
 for.end.loopexit:
   br label %for.end
 
 for.end:
   ret void
 }
 
 declare float @llvm.sin.f32(float) nounwind readnone
 
 ; Dummy metadata
 !3 = !{!3}