[LoopVectorize][CostModel] Update cost model for fmuladd intrinsic

[RosieSumpter]

Summary

This patch updates the cost model for ordered reductions so that a call
to the llvm.fmuladd intrinsic is modelled as a normal fmul instruction
plus the cost of an ordered fadd reduction.

Depends on D111555

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7276

Could this be handled in TTI.getArithmeticReductionCost? What about other potential users of fmuladd reductions, like the SLP vectorizer?

[RosieSumpter]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7276

Hi Florian, I did discuss this option with @david-arm, but it would mean changing the interface of getArithmeticReductionCost (e.g. by adding an optional Instruction* argument) to be able to determine if it's a call to the fmuladd intrinsic. David also made the point that the fmul isn't actually part of the reduction cost, so perhaps it doesn't make sense to ask for an fmuladd reduction cost? If you would prefer it to be there though I'm happy to make the change.

For the SLP vectorizer, it doesn't handle the fmuladd at the moment (I've added an assert for this in D111555 for safety)

[RosieSumpter]

Created getFMulAddReductionCost. This means the code which calculates the total cost of the fmuladd is moved out of the vectorizer, but avoids changing the interface for getArithmeticReductionCost.

[david-arm]

llvm/test/Transforms/LoopVectorize/AArch64/scalable-strict-fadd.ll

398 ↗

(On Diff #379740)

Hi @RosieSumpter, do you know why these CHECK lines have changed? It doesn't seem like your patch should affect these tests because these loops are forced to use a certain VF anyway.

[RosieSumpter]

llvm/test/Transforms/LoopVectorize/AArch64/scalable-strict-fadd.ll

398 ↗

(On Diff #379740)

Hi @david-arm, good point. The reason the test has changed is because of adding FMulAdd as an allowed recurrence kind to AArch64TTIImpl::isLegalToVectorizeReduction. I now see that it probably makes more sense for this particular change to be in D111555, so I'll do that now.

[RosieSumpter]

• Moved the addition of FMulAdd as a recurrence kind in AArch64TTIImpl::isLegalToVectorizeReduction to D111555
• There are no longer changes to the scalable-strict-fadd.ll test

[paulwalker-arm]

llvm/include/llvm/CodeGen/BasicTTIImpl.h

2177–2185

Do we need a new TTI interface for this? To my mind the costing side of TTI exists to cost real entities and in this instance the IR has no discrete concept for an FMA reduction.

Instead what we have is LoopVectorize pretending such a concept exists that is knows ahead of time it will simulate with separate fmul and ordered_fadd_reduce operations. For this reason I think it would be better to explicitly cost that exact idiom within the same code that is using it.

So I guess I'm saying that if you move these three lines into LoopVectorize.cpp the patch can be much smaller and you're not creating a new interface for something that doesn't really exist.

[RosieSumpter]

llvm/include/llvm/CodeGen/BasicTTIImpl.h

2177–2185

Hi Paul, thanks for having a look at this. Initially I did put the cost calculation into the vectorizer, but there was some discussion (also a comment from @fhahn) about whether it would make more sense in TTI.getArithmeticReductionCost and, to avoid changing the interface for getArithmeticReductionCost, @david-arm and @sdesmalen suggested adding the new getFMulAddReductionCost. I am happy to change it back to LoopVectorize.cpp if that seems like the better option.

[paulwalker-arm]

Thanks for the extra info @RosieSumpter. As I see it @fhahn was just asking a question of which I personally would have answered no, presenting the same rational as my previous comment. I guess we'll have to wait for others to respond.

[david-arm]

llvm/include/llvm/CodeGen/BasicTTIImpl.h

2177–2185

For what it's worth, I personally think it makes a bit more sense to calculate the costs separately in the vectoriser because in my mind at least the fmul isn't part of the reduction, since we are always going to widen it into a normal vector operation. I suggested adding a new interface as a compromise, so we can avoid over-complicating (and avoid making this patch significantly larger) the existing getArithmeticReductionCost method. I wouldn't block the patch over this though!

[RosieSumpter]

• Removed the new getFMulAddReductionCost TTI interface
• Moved the cost calculation back to the vectorizer

[RosieSumpter]

Thanks for the comments @paulwalker-arm and @david-arm. I've moved the fmul cost calculation back to the vectorizer since this seems like the more favourable option.

[paulwalker-arm]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7267–7272

Perhaps I've misunderstood something? because this code looks more complicated (or perhaps just more verbose) than the previous patch. I guess I'm struggling why different versions of getArithmeticInstrCost are being called between the two. I just assumed you'd add something like:

   InstructionCost BaseCost = TTI.getArithmeticReductionCost(                        
       RdxDesc.getOpcode(), VectorTy, RdxDesc.getFastMathFlags(), CostKind);         
                                                                                    
+  // For llvm.fmuladd based reductions we must include the cost of the normal       
+  // vector fmul that will occur prior to the fadd reduction.                       
+  if (RdxDesc.getRecurrenceKind() == RecurKind::FMulAdd)                            
+    BaseCost += TTI.getArithmeticInstrCost(Instruction::FMul, VectorTy, CostKind);  

   // If we're using ordered reductions then we can just return the base cost
   // here, since getArithmeticReductionCost calculates the full ordered
   // reduction cost when FP reassociation is not allowed.
   if (useOrderedReductions(RdxDesc))                                                
     return BaseCost;

[RosieSumpter]

• Make use of default parameters when calling getArithmeticInstrCost
• Move addition of FMul cost

[sdesmalen]

This cost calculation seems correct to me. For in-loop reductions it calculates the cost as a single fmul + fadd *reduction*. If this is not an in-loop reduction, or if fmuladd is not used in a reduction, it will follow the regular code-path to get the cost of this intrinsic (either as an FMA or separate fmul+fadd).

So, LGTM! (Please address the minor nits before you commit)

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7938

nit: redundant comment (i.e. the code says as much)

7939

nit: unnecessary curly braces.

7940

nit: redundant comment.

llvm/include/llvm/Analysis/TargetTransformInfo.h

   InstructionCost getArithmeticReductionCost(
       unsigned Opcode, VectorType *Ty, Optional<FastMathFlags> FMF,
       TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput) const;
 
   InstructionCost getMinMaxReductionCost(
       VectorType *Ty, VectorType *CondTy, bool IsUnsigned,
       TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput) const;
 
+  /// Calculate the cost of a call to the llvm.fmuladd intrinsic. This is
+  /// modeled as the cost of a normal fmul instruction plus the cost of an fadd
+  /// reduction.
+  InstructionCost getFMulAddReductionCost(
+      VectorType *Ty, Optional<FastMathFlags> FMF,
+      TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput) const;
+
   /// Calculate the cost of an extended reduction pattern, similar to
   /// getArithmeticReductionCost of an Add reduction with an extension and
   /// optional multiply. This is the cost of as:
   /// ResTy vecreduce.add(ext(Ty A)), or if IsMLA flag is set then:
   /// ResTy vecreduce.add(mul(ext(Ty A), ext(Ty B)). The reduction happens
   /// on a VectorType with ResTy elements and Ty lanes.
   InstructionCost getExtendedAddReductionCost(
       bool IsMLA, bool IsUnsigned, Type *ResTy, VectorType *Ty,
virtual InstructionCost getInterleavedMemoryOpCost(
       bool UseMaskForCond = false, bool UseMaskForGaps = false) = 0;
   virtual InstructionCost
   getArithmeticReductionCost(unsigned Opcode, VectorType *Ty,
                              Optional<FastMathFlags> FMF,
                              TTI::TargetCostKind CostKind) = 0;
   virtual InstructionCost
   getMinMaxReductionCost(VectorType *Ty, VectorType *CondTy, bool IsUnsigned,
                          TTI::TargetCostKind CostKind) = 0;
+  virtual InstructionCost
+  getFMulAddReductionCost(VectorType *Ty, Optional<FastMathFlags> FMF,
+                          TTI::TargetCostKind CostKind) = 0;
   virtual InstructionCost getExtendedAddReductionCost(
       bool IsMLA, bool IsUnsigned, Type *ResTy, VectorType *Ty,
       TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput) = 0;
   virtual InstructionCost
   getIntrinsicInstrCost(const IntrinsicCostAttributes &ICA,
                         TTI::TargetCostKind CostKind) = 0;
   virtual InstructionCost getCallInstrCost(Function *F, Type *RetTy,
                                            ArrayRef<Type *> Tys,
getArithmeticReductionCost(unsigned Opcode, VectorType *Ty,
                              TTI::TargetCostKind CostKind) override {
     return Impl.getArithmeticReductionCost(Opcode, Ty, FMF, CostKind);
   }
   InstructionCost
   getMinMaxReductionCost(VectorType *Ty, VectorType *CondTy, bool IsUnsigned,
                          TTI::TargetCostKind CostKind) override {
     return Impl.getMinMaxReductionCost(Ty, CondTy, IsUnsigned, CostKind);
   }
+  InstructionCost
+  getFMulAddReductionCost(VectorType *Ty, Optional<FastMathFlags> FMF,
+                          TTI::TargetCostKind CostKind) override {
+    return Impl.getFMulAddReductionCost(Ty, FMF, CostKind);
+  }
   InstructionCost getExtendedAddReductionCost(
       bool IsMLA, bool IsUnsigned, Type *ResTy, VectorType *Ty,
       TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput) override {
     return Impl.getExtendedAddReductionCost(IsMLA, IsUnsigned, ResTy, Ty,
                                             CostKind);
   }
   InstructionCost getIntrinsicInstrCost(const IntrinsicCostAttributes &ICA,
                                         TTI::TargetCostKind CostKind) override {

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

InstructionCost getArithmeticReductionCost(unsigned, VectorType *,
     return 1;
   }
 
   InstructionCost getMinMaxReductionCost(VectorType *, VectorType *, bool,
                                          TTI::TargetCostKind) const {
     return 1;
   }
 
+  InstructionCost getFMulAddReductionCost(VectorType *, Optional<FastMathFlags>,
+                                          TTI::TargetCostKind) const {
+    return 1;
+  }
+
   InstructionCost
   getExtendedAddReductionCost(bool IsMLA, bool IsUnsigned, Type *ResTy,
                               VectorType *Ty,
                               TTI::TargetCostKind CostKind) const {
     return 1;
   }
 
   InstructionCost getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) const {

llvm/include/llvm/CodeGen/BasicTTIImpl.h

MinMaxCost +=
          thisT()->getCmpSelInstrCost(Instruction::Select, Ty, CondTy,
                                      CmpInst::BAD_ICMP_PREDICATE, CostKind));
     // The last min/max should be in vector registers and we counted it above.
     // So just need a single extractelement.
     return ShuffleCost + MinMaxCost +
            thisT()->getVectorInstrCost(Instruction::ExtractElement, Ty, 0);
   }
 
+  InstructionCost getFMulAddReductionCost(VectorType *Ty,
+                                          Optional<FastMathFlags> FMF,
+                                          TTI::TargetCostKind CostKind) {
+    InstructionCost FAddReductionCost = thisT()->getArithmeticReductionCost(
+        Instruction::FAdd, Ty, FMF, CostKind);
+    InstructionCost FMulCost =
+        thisT()->getArithmeticInstrCost(Instruction::FMul, Ty, CostKind);
+    return FMulCost + FAddReductionCost;
+  }
+
   InstructionCost getExtendedAddReductionCost(bool IsMLA, bool IsUnsigned,
                                               Type *ResTy, VectorType *Ty,
                                               TTI::TargetCostKind CostKind) {
     // Without any native support, this is equivalent to the cost of
     // vecreduce.add(ext) or if IsMLA vecreduce.add(mul(ext, ext))
     VectorType *ExtTy = VectorType::get(ResTy, Ty);
     InstructionCost RedCost = thisT()->getArithmeticReductionCost(
         Instruction::Add, ExtTy, None, CostKind);

llvm/lib/Analysis/TargetTransformInfo.cpp

InstructionCost TargetTransformInfo::getMinMaxReductionCost(
     VectorType *Ty, VectorType *CondTy, bool IsUnsigned,
     TTI::TargetCostKind CostKind) const {
   InstructionCost Cost =
       TTIImpl->getMinMaxReductionCost(Ty, CondTy, IsUnsigned, CostKind);
   assert(Cost >= 0 && "TTI should not produce negative costs!");
   return Cost;
 }
 
+InstructionCost TargetTransformInfo::getFMulAddReductionCost(
+    VectorType *Ty, Optional<FastMathFlags> FMF,
+    TTI::TargetCostKind CostKind) const {
+  InstructionCost Cost = TTIImpl->getFMulAddReductionCost(Ty, FMF, CostKind);
+  assert(Cost >= 0 && "TTI should not produce negative costs!");
+  return Cost;
+}
+
 InstructionCost TargetTransformInfo::getExtendedAddReductionCost(
     bool IsMLA, bool IsUnsigned, Type *ResTy, VectorType *Ty,
     TTI::TargetCostKind CostKind) const {
   return TTIImpl->getExtendedAddReductionCost(IsMLA, IsUnsigned, ResTy, Ty,
                                               CostKind);
 }
 
 InstructionCost

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

Optional<InstructionCost> LoopVectorizationCostModel::getReductionPatternCost(
   Instruction *LastChain = InLoopReductionImmediateChains[RetI];
   Instruction *ReductionPhi = LastChain;
   while (!isa<PHINode>(ReductionPhi))
     ReductionPhi = InLoopReductionImmediateChains[ReductionPhi];
 
   const RecurrenceDescriptor &RdxDesc =
       Legal->getReductionVars()[cast<PHINode>(ReductionPhi)];
 
-  InstructionCost BaseCost = TTI.getArithmeticReductionCost(
+  InstructionCost BaseCost;
+  if (RdxDesc.getRecurrenceKind() == RecurKind::FMulAdd)
+    // Recognize a call to the llvm.fmuladd intrinsic.
+    BaseCost = TTI.getFMulAddReductionCost(VectorTy, RdxDesc.getFastMathFlags(),
+                                           CostKind);
+  else
+    BaseCost = TTI.getArithmeticReductionCost(
         RdxDesc.getOpcode(), VectorTy, RdxDesc.getFastMathFlags(), CostKind);
 
   // If we're using ordered reductions then we can just return the base cost
   // here, since getArithmeticReductionCost calculates the full ordered
   // reduction cost when FP reassociation is not allowed.
   if (useOrderedReductions(RdxDesc))
     return BaseCost;
 
   // Get the operand that was not the reduction chain and match it to one of the
   // patterns, returning the better cost if it is found.
   Instruction *RedOp = RetI->getOperand(1) == LastChain
                            ? dyn_cast<Instruction>(RetI->getOperand(0))
                            : dyn_cast<Instruction>(RetI->getOperand(1));
 
   VectorTy = VectorType::get(I->getOperand(0)->getType(), VectorTy);
 
   Instruction *Op0, *Op1;
   if (RedOp &&
       match(RedOp,
             m_ZExtOrSExt(m_Mul(m_Instruction(Op0), m_Instruction(Op1)))) &&
if (canTruncateToMinimalBitwidth(I, VF)) {
         VectorTy =
             smallestIntegerVectorType(ToVectorTy(I->getType(), VF), MinVecTy);
       }
     }
 
     return TTI.getCastInstrCost(Opcode, VectorTy, SrcVecTy, CCH, CostKind, I);
   }
   case Instruction::Call: {
+    // Recognize a call to the llvm.fmuladd intrinsic.
+    if (RecurrenceDescriptor::isFMulAddIntrinsic(I)) {
+      // Detect reduction patterns.
+      if (auto RedCost = getReductionPatternCost(I, VF, VectorTy, CostKind))
+        return *RedCost;
+    }
     bool NeedToScalarize;
     CallInst *CI = cast<CallInst>(I);
     InstructionCost CallCost = getVectorCallCost(CI, VF, NeedToScalarize);
     if (getVectorIntrinsicIDForCall(CI, TLI)) {
       InstructionCost IntrinsicCost = getVectorIntrinsicCost(CI, VF);
       return std::min(CallCost, IntrinsicCost);
     }
     return CallCost;

llvm/test/Transforms/LoopVectorize/AArch64/strict-fadd-cost.ll

for.body:
   %add = fadd double %0, %sum.07
   %iv.next = add nuw nsw i64 %iv, 1
   %exitcond.not = icmp eq i64 %iv.next, %n
   br i1 %exitcond.not, label %for.end, label %for.body
 
 for.end:
   ret double %add
 }
+
+; CHECK-VF4: Found an estimated cost of 23 for VF 4 For instruction:   %muladd = tail call float @llvm.fmuladd.f32(float %0, float %1, float %sum.07)
+; CHECK-VF8: Found an estimated cost of 46 for VF 8 For instruction:   %muladd = tail call float @llvm.fmuladd.f32(float %0, float %1, float %sum.07)
+
+define float @fmuladd_strict32(float* %a, float* %b, i64 %n) {
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ]
+  %sum.07 = phi float [ 0.000000e+00, %entry ], [ %muladd, %for.body ]
+  %arrayidx = getelementptr inbounds float, float* %a, i64 %iv
+  %0 = load float, float* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds float, float* %b, i64 %iv
+  %1 = load float, float* %arrayidx2, align 4
+  %muladd = tail call float @llvm.fmuladd.f32(float %0, float %1, float %sum.07)
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond.not = icmp eq i64 %iv.next, %n
+  br i1 %exitcond.not, label %for.end, label %for.body
+
+for.end:
+  ret float %muladd
+}
+
+declare float @llvm.fmuladd.f32(float, float, float)
+
+; CHECK-VF4: Found an estimated cost of 22 for VF 4 For instruction:   %muladd = tail call double @llvm.fmuladd.f64(double %0, double %1, double %sum.07)
+; CHECK-VF8: Found an estimated cost of 44 for VF 8 For instruction:   %muladd = tail call double @llvm.fmuladd.f64(double %0, double %1, double %sum.07)
+
+define double @fmuladd_strict64(double* %a, double* %b, i64 %n) {
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ]
+  %sum.07 = phi double [ 0.000000e+00, %entry ], [ %muladd, %for.body ]
+  %arrayidx = getelementptr inbounds double, double* %a, i64 %iv
+  %0 = load double, double* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds double, double* %b, i64 %iv
+  %1 = load double, double* %arrayidx2, align 4
+  %muladd = tail call double @llvm.fmuladd.f64(double %0, double %1, double %sum.07)
+  %iv.next = add nuw nsw i64 %iv, 1
+  %exitcond.not = icmp eq i64 %iv.next, %n
+  br i1 %exitcond.not, label %for.end, label %for.body
+
+for.end:
+  ret double %muladd
+}
+
+declare double @llvm.fmuladd.f64(double, double, double)