[RISCV]Add basic cost model for vector reduce for scalable vector

[liaolucy]

Summary

Fix crash. LLVM ERROR: Invalid size request on a scalable vector, which causing the crash on CodeMetrics:analyzeBasicBlock.

The cost model just reference D93639.

[rogfer01]

Can we test some illegal type here (e.g. vscale x 16 x i64). The patch includes logic for that so it may be worth having it.

llvm/test/Analysis/CostModel/RISCV/scalable-reduce.ll

63

This doesn't seem very realistic (I assume these reductions must be done linearly) but I guess the cost here is measuring number of instructions required rather than latency, right?

[liaolucy]

1. Add a illegal checks. Invalid types will crash.

if(!isTypeLegal(VTy))
  return BaseT::getArithmeticReductionCost(Opcode, VTy, FMF, CostKind);

2. Remove deadcode.

llvm/test/Analysis/CostModel/RISCV/scalable-reduce.ll

63

This doesn't seem very realistic (I assume these reductions must be done linearly) but I guess the cost here is measuring number of instructions required rather than latency, right?

Yes, I don't know where to find the latency information of instructions, just count instructions (are not accurate).

llvm/lib/Target/RISCV/RISCVTargetTransformInfo.h

public:
   InstructionCost getMinMaxReductionCost(VectorType *Ty, VectorType *CondTy,
                                          bool IsUnsigned,
                                          TTI::TargetCostKind CostKind);
 
   InstructionCost getArithmeticReductionCost(unsigned Opcode, VectorType *Ty,
                                              Optional<FastMathFlags> FMF,
                                              TTI::TargetCostKind CostKind);
 
+  InstructionCost getMinMaxReductionCostScalable(VectorType *Ty,
+                                                 VectorType *CondTy,
+                                                 bool IsUnsigned,
+                                                 TTI::TargetCostKind CostKind);
+
+  InstructionCost
+  getArithmeticReductionCostScalable(unsigned Opcode, VectorType *Ty,
+                                     Optional<FastMathFlags> FMF,
+                                     TTI::TargetCostKind CostKind);
+
   bool isLegalMaskedLoadStore(Type *DataType, Align Alignment) {
     if (!ST->hasVInstructions())
       return false;
 
     // Only support fixed vectors if we know the minimum vector size.
     if (isa<FixedVectorType>(DataType) && ST->getMinRVVVectorSizeInBits() == 0)
       return false;
 

llvm/lib/Target/RISCV/RISCVTargetTransformInfo.cpp

case ISD::UINT_TO_FP:
       // Counts of narrow/widen instructions.
       return std::abs(PowDiff);
     }
   }
   return BaseT::getCastInstrCost(Opcode, Dst, Src, CCH, CostKind, I);
 }
 
 InstructionCost
+RISCVTTIImpl::getMinMaxReductionCostScalable(VectorType *Ty, VectorType *CondTy,
+                                             bool IsUnsigned,
+                                             TTI::TargetCostKind CostKind) {
+  // TODO: Add the final reduction cost
+  std::pair<InstructionCost, MVT> LT = TLI->getTypeLegalizationCost(DL, Ty);
+  InstructionCost LegalizationCost = 0;
+  assert((isa<ScalableVectorType>(Ty) && isa<ScalableVectorType>(CondTy)) &&
+         "Both vectors need to be scalable");
+
+  if (LT.first > 1) {
+    Type *LegalVTy = EVT(LT.second).getTypeForEVT(Ty->getContext());
+    unsigned CmpOpcode =
+        Ty->isFPOrFPVectorTy() ? Instruction::FCmp : Instruction::ICmp;
+    LegalizationCost =
+        getCmpSelInstrCost(CmpOpcode, LegalVTy, LegalVTy,
+                           CmpInst::BAD_ICMP_PREDICATE, CostKind) +
+        getCmpSelInstrCost(Instruction::Select, LegalVTy, LegalVTy,
+                           CmpInst::BAD_ICMP_PREDICATE, CostKind);
+    LegalizationCost *= LT.first - 1;
+  }
+
+  return LegalizationCost + 2;
+}
+
+InstructionCost
 RISCVTTIImpl::getMinMaxReductionCost(VectorType *Ty, VectorType *CondTy,
                                      bool IsUnsigned,
                                      TTI::TargetCostKind CostKind) {
-  // FIXME: Only supporting fixed vectors for now.
-  if (!isa<FixedVectorType>(Ty))
-    return BaseT::getMinMaxReductionCost(Ty, CondTy, IsUnsigned, CostKind);
+  if (isa<ScalableVectorType>(Ty))
+    return getMinMaxReductionCostScalable(Ty, CondTy, IsUnsigned, CostKind);
 
   if (!ST->useRVVForFixedLengthVectors())
     return BaseT::getMinMaxReductionCost(Ty, CondTy, IsUnsigned, CostKind);
 
   // Skip if scalar size of Ty is bigger than ELEN.
   if (Ty->getScalarSizeInBits() > ST->getELEN())
     return BaseT::getMinMaxReductionCost(Ty, CondTy, IsUnsigned, CostKind);
 
   // IR Reduction is composed by two vmv and one rvv reduction instruction.
   InstructionCost BaseCost = 2;
   unsigned VL = cast<FixedVectorType>(Ty)->getNumElements();
   std::pair<InstructionCost, MVT> LT = TLI->getTypeLegalizationCost(DL, Ty);
   return (LT.first - 1) + BaseCost + Log2_32_Ceil(VL);
 }
 
+InstructionCost RISCVTTIImpl::getArithmeticReductionCostScalable(
+    unsigned Opcode, VectorType *VTy, Optional<FastMathFlags> FMF,
+    TTI::TargetCostKind CostKind) {
+  // TODO: Add the final reduction cost
+  std::pair<InstructionCost, MVT> LT = TLI->getTypeLegalizationCost(DL, VTy);
+  InstructionCost LegalizationCost = 0;
+  if (LT.first > 1) {
+    Type *LegalVTy = EVT(LT.second).getTypeForEVT(VTy->getContext());
+    LegalizationCost = getArithmeticInstrCost(Opcode, LegalVTy, CostKind);
+    LegalizationCost *= LT.first - 1;
+  }
+
+  int ISD = TLI->InstructionOpcodeToISD(Opcode);
+  assert(ISD && "Invalid opcode");
+
+  switch (ISD) {
+  default:
+    return BaseT::getArithmeticReductionCost(Opcode, VTy, FMF, CostKind);
+  case ISD::ADD:
+  case ISD::AND:
+  case ISD::OR:
+  case ISD::XOR:
+  case ISD::FADD:
+    return LegalizationCost + 2;
+  }
+}
+
 InstructionCost
 RISCVTTIImpl::getArithmeticReductionCost(unsigned Opcode, VectorType *VTy,
                                          Optional<FastMathFlags> FMF,
                                          TTI::TargetCostKind CostKind) {
-  // FIXME: Only supporting fixed vectors for now.
-  if (!isa<FixedVectorType>(VTy))
-    return BaseT::getArithmeticReductionCost(Opcode, VTy, FMF, CostKind);
+
+  if (isa<ScalableVectorType>(VTy))
+    return getArithmeticReductionCostScalable(Opcode, VTy, FMF, CostKind);
 
   // FIXME: Do not support i1 and/or reduction now.
   if (VTy->getElementType()->isIntegerTy(1))
     return BaseT::getArithmeticReductionCost(Opcode, VTy, FMF, CostKind);
 
   if (!ST->useRVVForFixedLengthVectors())
     return BaseT::getArithmeticReductionCost(Opcode, VTy, FMF, CostKind);
 

llvm/test/Analysis/CostModel/RISCV/scalable-reduce.ll

+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
+; RUN: opt < %s -passes='print<cost-model>' 2>&1 -disable-output -S  -mtriple=riscv64 -mattr=+v,+f,+d,+zfh,+experimental-zvfh | FileCheck %s
+
+define void @reductions(<vscale x 4 x i32> %v0, <vscale x 4 x i64> %v1, <vscale x 4 x float> %v2, <vscale x 4 x double> %v3) {
+; CHECK-LABEL: 'reductions'
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %add_nxv4i32 = call i32 @llvm.vector.reduce.add.nxv4i32(<vscale x 4 x i32> %v0)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %add_nxv4i64 = call i64 @llvm.vector.reduce.add.nxv4i64(<vscale x 4 x i64> %v1)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %and_nxv4i32 = call i32 @llvm.vector.reduce.and.nxv4i32(<vscale x 4 x i32> %v0)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %and_nxv4i64 = call i64 @llvm.vector.reduce.and.nxv4i64(<vscale x 4 x i64> %v1)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %or_nxv4i32 = call i32 @llvm.vector.reduce.or.nxv4i32(<vscale x 4 x i32> %v0)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %or_nxv4i64 = call i64 @llvm.vector.reduce.or.nxv4i64(<vscale x 4 x i64> %v1)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %xor_nxv4i32 = call i32 @llvm.vector.reduce.xor.nxv4i32(<vscale x 4 x i32> %v0)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %xor_nxv4i64 = call i64 @llvm.vector.reduce.xor.nxv4i64(<vscale x 4 x i64> %v1)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %umin_nxv4i32 = call i32 @llvm.vector.reduce.umin.nxv4i32(<vscale x 4 x i32> %v0)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %umin_nxv4i64 = call i64 @llvm.vector.reduce.umin.nxv4i64(<vscale x 4 x i64> %v1)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %smin_nxv4i32 = call i32 @llvm.vector.reduce.smin.nxv4i32(<vscale x 4 x i32> %v0)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %smin_nxv4i64 = call i64 @llvm.vector.reduce.smin.nxv4i64(<vscale x 4 x i64> %v1)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %umax_nxv4i32 = call i32 @llvm.vector.reduce.umax.nxv4i32(<vscale x 4 x i32> %v0)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %umax_nxv4i64 = call i64 @llvm.vector.reduce.umax.nxv4i64(<vscale x 4 x i64> %v1)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %smax_nxv4i32 = call i32 @llvm.vector.reduce.smax.nxv4i32(<vscale x 4 x i32> %v0)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %smax_nxv4i64 = call i64 @llvm.vector.reduce.smax.nxv4i64(<vscale x 4 x i64> %v1)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %fadd_nxv4f32 = call fast float @llvm.vector.reduce.fadd.nxv4f32(float 0.000000e+00, <vscale x 4 x float> %v2)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %fadd_nxv4f64 = call fast double @llvm.vector.reduce.fadd.nxv4f64(double 0.000000e+00, <vscale x 4 x double> %v3)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %fmin_nxv4f32 = call fast float @llvm.vector.reduce.fmin.nxv4f32(<vscale x 4 x float> %v2)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %fmin_nxv4f64 = call fast double @llvm.vector.reduce.fmin.nxv4f64(<vscale x 4 x double> %v3)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %fmax_nxv4f32 = call fast float @llvm.vector.reduce.fmax.nxv4f32(<vscale x 4 x float> %v2)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %fmax_nxv4f64 = call fast double @llvm.vector.reduce.fmax.nxv4f64(<vscale x 4 x double> %v3)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: ret void
+;
+  %add_nxv4i32 = call i32 @llvm.vector.reduce.add.nxv4i32(<vscale x 4 x i32> %v0)
+  %add_nxv4i64 = call i64 @llvm.vector.reduce.add.nxv4i64(<vscale x 4 x i64> %v1)
+  %and_nxv4i32 = call i32 @llvm.vector.reduce.and.nxv4i32(<vscale x 4 x i32> %v0)
+  %and_nxv4i64 = call i64 @llvm.vector.reduce.and.nxv4i64(<vscale x 4 x i64> %v1)
+  %or_nxv4i32 = call i32 @llvm.vector.reduce.or.nxv4i32(<vscale x 4 x i32> %v0)
+  %or_nxv4i64 = call i64 @llvm.vector.reduce.or.nxv4i64(<vscale x 4 x i64> %v1)
+  %xor_nxv4i32 = call i32 @llvm.vector.reduce.xor.nxv4i32(<vscale x 4 x i32> %v0)
+  %xor_nxv4i64 = call i64 @llvm.vector.reduce.xor.nxv4i64(<vscale x 4 x i64> %v1)
+  %umin_nxv4i32 = call i32 @llvm.vector.reduce.umin.nxv4i32(<vscale x 4 x i32> %v0)
+  %umin_nxv4i64 = call i64 @llvm.vector.reduce.umin.nxv4i64(<vscale x 4 x i64> %v1)
+  %smin_nxv4i32 = call i32 @llvm.vector.reduce.smin.nxv4i32(<vscale x 4 x i32> %v0)
+  %smin_nxv4i64 = call i64 @llvm.vector.reduce.smin.nxv4i64(<vscale x 4 x i64> %v1)
+  %umax_nxv4i32 = call i32 @llvm.vector.reduce.umax.nxv4i32(<vscale x 4 x i32> %v0)
+  %umax_nxv4i64 = call i64 @llvm.vector.reduce.umax.nxv4i64(<vscale x 4 x i64> %v1)
+  %smax_nxv4i32 = call i32 @llvm.vector.reduce.smax.nxv4i32(<vscale x 4 x i32> %v0)
+  %smax_nxv4i64 = call i64 @llvm.vector.reduce.smax.nxv4i64(<vscale x 4 x i64> %v1)
+
+  %fadd_nxv4f32 = call fast float @llvm.vector.reduce.fadd.nxv4f32(float 0.0, <vscale x 4 x float> %v2)
+  %fadd_nxv4f64 = call fast double @llvm.vector.reduce.fadd.nxv4f64(double 0.0, <vscale x 4 x double> %v3)
+  %fmin_nxv4f32 = call fast float @llvm.vector.reduce.fmin.nxv4f32(<vscale x 4 x float> %v2)
+  %fmin_nxv4f64 = call fast double @llvm.vector.reduce.fmin.nxv4f64(<vscale x 4 x double> %v3)
+  %fmax_nxv4f32 = call fast float @llvm.vector.reduce.fmax.nxv4f32(<vscale x 4 x float> %v2)
+  %fmax_nxv4f64 = call fast double @llvm.vector.reduce.fmax.nxv4f64(<vscale x 4 x double> %v3)
+
+  ret void
+}
+
+define void @strict_fp_reductions(<vscale x 4 x float> %v0, <vscale x 4 x double> %v1) {
+; CHECK-LABEL: 'strict_fp_reductions'
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %fadd_nxv4f32 = call float @llvm.vector.reduce.fadd.nxv4f32(float 0.000000e+00, <vscale x 4 x float> %v0)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 2 for instruction: %fadd_nxv4f64 = call double @llvm.vector.reduce.fadd.nxv4f64(double 0.000000e+00, <vscale x 4 x double> %v1)
+; CHECK-NEXT:  Cost Model: Found an estimated cost of 1 for instruction: ret void
+;
+  %fadd_nxv4f32 = call float @llvm.vector.reduce.fadd.nxv4f32(float 0.0, <vscale x 4 x float> %v0)
+  %fadd_nxv4f64 = call double @llvm.vector.reduce.fadd.nxv4f64(double 0.0, <vscale x 4 x double> %v1)
+
+  ret void
+}
+
+declare i32 @llvm.vector.reduce.add.nxv4i32(<vscale x 4 x i32>)
+declare i64 @llvm.vector.reduce.add.nxv4i64(<vscale x 4 x i64>)
+declare i32 @llvm.vector.reduce.and.nxv4i32(<vscale x 4 x i32>)
+declare i64 @llvm.vector.reduce.and.nxv4i64(<vscale x 4 x i64>)
+declare i32 @llvm.vector.reduce.or.nxv4i32(<vscale x 4 x i32>)
+declare i64 @llvm.vector.reduce.or.nxv4i64(<vscale x 4 x i64>)
+declare i32 @llvm.vector.reduce.xor.nxv4i32(<vscale x 4 x i32>)
+declare i64 @llvm.vector.reduce.xor.nxv4i64(<vscale x 4 x i64>)
+declare i32 @llvm.vector.reduce.umin.nxv4i32(<vscale x 4 x i32>)
+declare i64 @llvm.vector.reduce.umin.nxv4i64(<vscale x 4 x i64>)
+declare i32 @llvm.vector.reduce.smin.nxv4i32(<vscale x 4 x i32>)
+declare i64 @llvm.vector.reduce.smin.nxv4i64(<vscale x 4 x i64>)
+declare i32 @llvm.vector.reduce.umax.nxv4i32(<vscale x 4 x i32>)
+declare i64 @llvm.vector.reduce.umax.nxv4i64(<vscale x 4 x i64>)
+declare i32 @llvm.vector.reduce.smax.nxv4i32(<vscale x 4 x i32>)
+declare i64 @llvm.vector.reduce.smax.nxv4i64(<vscale x 4 x i64>)
+declare float @llvm.vector.reduce.fadd.nxv4f32(float, <vscale x 4 x float>)
+declare double @llvm.vector.reduce.fadd.nxv4f64(double, <vscale x 4 x double>)
+declare float @llvm.vector.reduce.fmin.nxv4f32(<vscale x 4 x float>)
+declare double @llvm.vector.reduce.fmin.nxv4f64(<vscale x 4 x double>)
+declare float @llvm.vector.reduce.fmax.nxv4f32(<vscale x 4 x float>)
+declare double @llvm.vector.reduce.fmax.nxv4f64(<vscale x 4 x double>)
+
+