[VectorCombine] make cost calc consistent for binops and cmps

[spatel]

Summary

Code duplication (subsequently removed by refactoring) allowed a logic discrepancy to creep in here.

We were being conservative about creating a vector binop -- but not a vector cmp -- in the case where a vector op has the same estimated cost as the scalar op. We want to be more aggressive here because that can allow other combines based on reduced instruction count/uses.

We can reverse the transform in DAGCombiner (potentially with a more accurate cost model) if this causes regressions.

AFAIK, this does not conflict with InstCombine. We have a scalarize transform there, but it relies on finding a constant operand or a matching insertelement, so that means it eliminates an extractelement from the sequence (so we won't have 2 extracts by the time we get here if InstCombine succeeds).

[lebedev.ri]

We have the reverse transform with target hook in DAGCombiner already -- scalarizeExtractedBinop() -- so that provides a later opportunity to invert (potentially with a more accurate cost model).

I'm a little bit lost there.
Unless i'm not reading it right, even if the TLI.shouldScalarizeBinop(Vec) returns true,
the code only scalarizes if at least one of the vector operands is constant.

[spatel]

In D75062#1889707, @lebedev.ri wrote:

We have the reverse transform with target hook in DAGCombiner already -- scalarizeExtractedBinop() -- so that provides a later opportunity to invert (potentially with a more accurate cost model).

I'm a little bit lost there.
Unless i'm not reading it right, even if the TLI.shouldScalarizeBinop(Vec) returns true,
the code only scalarizes if at least one of the vector operands is constant.

Oops, I misread it - I saw an x86 FP example like:

define float @fadd_extract(<4 x float> %x, <4 x float> %y) {
  %a = fadd <4 x float> %x, %y
  %r = extractelement <4 x float> %a, i32 0
  ret float %r
}

...but that's handled by the x86-specific scalarizeExtEltFP().

I can try to make scalarizeExtractedBinop() stronger, but I'll need to find a target/example where it is a win (the extracts need to be free, or the vector op needs to be pretty expensive?). Or we just see if this causes wins or regressions for anyone as-is?

[spatel]

For reference, a motivating case for VectorCombine that I'm hoping to build up to (not there yet because we need a shuffle):
https://bugs.llvm.org/show_bug.cgi?id=42633

If we make the cost calc conservative, then we probably forego creating a vector op on that example for some targets even though it's a likely win.

Another possibility is that targets will need to have more complex cost modeling for extract/insert (D74976) - but that's probably not enough by itself to get all of the missed vectorizations we've seen.

[lebedev.ri]

In D75062#1889774, @spatel wrote:

In D75062#1889707, @lebedev.ri wrote:

We have the reverse transform with target hook in DAGCombiner already -- scalarizeExtractedBinop() -- so that provides a later opportunity to invert (potentially with a more accurate cost model).

I'm a little bit lost there.
Unless i'm not reading it right, even if the TLI.shouldScalarizeBinop(Vec) returns true,
the code only scalarizes if at least one of the vector operands is constant.

Oops, I misread it - I saw an x86 FP example like:

define float @fadd_extract(<4 x float> %x, <4 x float> %y) {
  %a = fadd <4 x float> %x, %y
  %r = extractelement <4 x float> %a, i32 0
  ret float %r
}

...but that's handled by the x86-specific scalarizeExtEltFP().

I can try to make scalarizeExtractedBinop() stronger, but I'll need to find a target/example where it is a win (the extracts need to be free, or the vector op needs to be pretty expensive?). Or we just see if this causes wins or regressions for anyone as-is?

I think that either scalarizeExtractedBinop() should actually be able to do the inverse transform,
or this patch's description shouldn't say scalarizeExtractedBinop() can do inverse transform.

[spatel]

In D75062#1889864, @lebedev.ri wrote:

In D75062#1889774, @spatel wrote:

In D75062#1889707, @lebedev.ri wrote:

We have the reverse transform with target hook in DAGCombiner already -- scalarizeExtractedBinop() -- so that provides a later opportunity to invert (potentially with a more accurate cost model).

I'm a little bit lost there.
Unless i'm not reading it right, even if the TLI.shouldScalarizeBinop(Vec) returns true,
the code only scalarizes if at least one of the vector operands is constant.

Oops, I misread it - I saw an x86 FP example like:

define float @fadd_extract(<4 x float> %x, <4 x float> %y) {
  %a = fadd <4 x float> %x, %y
  %r = extractelement <4 x float> %a, i32 0
  ret float %r
}

...but that's handled by the x86-specific scalarizeExtEltFP().

I can try to make scalarizeExtractedBinop() stronger, but I'll need to find a target/example where it is a win (the extracts need to be free, or the vector op needs to be pretty expensive?). Or we just see if this causes wins or regressions for anyone as-is?

I think that either scalarizeExtractedBinop() should actually be able to do the inverse transform,
or this patch's description shouldn't say scalarizeExtractedBinop() can do inverse transform.

Changing the description/comments is easy. :)
I'm willing to see if that works out. And if there are problems, I can adjust the DAGCombiner code.

[lebedev.ri]

SGTM, the difference wasn't really intentional on my side, i just kind-of not caught it.

[thakis]

Looks like this broke tests everywhere, eg http://45.33.8.238/linux/11165/step_7.txt

Can you take a look please?

[spatel]

In D75062#1891209, @thakis wrote:

Looks like this broke tests everywhere, eg http://45.33.8.238/linux/11165/step_7.txt

Can you take a look please?

Thanks. This hit an over-reaching clang test (again). Should be fixed with:
rG83f4372f3a70

[spatel]

This patch partly fixed a bug report that came in after approval:
https://bugs.llvm.org/show_bug.cgi?id=45015

I added a more complete test to detect that set of problems here:
rGf452f7b95a8c

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

if (Ext0->getOperand(0) == Ext1->getOperand(0)) {
     NewCost = VectorOpCost + ExtractCost + HasUseTax * ExtractCost;
   } else {
     // Handle the general case. Each extract is actually a different value:
     // opcode (extelt V0, C), (extelt V1, C) --> extelt (opcode V0, V1), C
     OldCost = 2 * ExtractCost + ScalarOpCost;
     NewCost = VectorOpCost + ExtractCost + !Ext0->hasOneUse() * ExtractCost +
               !Ext1->hasOneUse() * ExtractCost;
   }
-  // TODO: The cost comparison should not differ based on opcode. Either we
-  //       want to be uniformly more or less aggressive in deciding if a vector
-  //       operation should replace the scalar operation.
-  return IsBinOp ? OldCost <= NewCost : OldCost < NewCost;
+  // Aggressively form a vector op if the cost is equal because the transform
+  // may enable further optimization.
+  // Codegen can reverse this transform (scalarize) if it was not profitable.
+  return OldCost < NewCost;
 }
 
 /// Try to reduce extract element costs by converting scalar compares to vector
 /// compares followed by extract.
 /// cmp (ext0 V0, C), (ext1 V1, C)
 static void foldExtExtCmp(Instruction *Ext0, Instruction *Ext1,
                           Instruction &I, const TargetTransformInfo &TTI) {
   assert(isa<CmpInst>(&I) && "Expected a compare");

llvm/test/Transforms/VectorCombine/X86/extract-binop.ll

 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %e0 = extractelement <16 x i8> %x, i32 0
   %e1 = extractelement <16 x i8> %y, i32 0
   %r = sdiv i8 %e0, %e1
   ret i8 %r
 }
 
-; Negative test - extracts are free and vector op has same cost as scalar.
+; Extracts are free and vector op has same cost as scalar, but we
+; speculatively transform to vector to create more optimization
+; opportunities..
 
 define double @ext0_ext0_fadd(<2 x double> %x, <2 x double> %y) {
 ; CHECK-LABEL: @ext0_ext0_fadd(
-; CHECK-NEXT:    [[E0:%.*]] = extractelement <2 x double> [[X:%.*]], i32 0
-; CHECK-NEXT:    [[E1:%.*]] = extractelement <2 x double> [[Y:%.*]], i32 0
-; CHECK-NEXT:    [[R:%.*]] = fadd double [[E0]], [[E1]]
-; CHECK-NEXT:    ret double [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd <2 x double> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = extractelement <2 x double> [[TMP1]], i32 0
+; CHECK-NEXT:    ret double [[TMP2]]
 ;
   %e0 = extractelement <2 x double> %x, i32 0
   %e1 = extractelement <2 x double> %y, i32 0
   %r = fadd double %e0, %e1
   ret double %r
 }
 
 ; Eliminating extract is profitable. Flags propagate.

 ; CHECK-NEXT:    ret double [[R]]
 ;
   %e0 = extractelement <2 x double> %x, i32 1
   %e1 = extractelement <4 x double> %y, i32 1
   %r = fadd fast double %e0, %e1
   ret double %r
 }
 
-; Negative test - disguised same vector operand; scalar code is cheaper than general case.
+; Disguised same vector operand; scalar code is not cheaper (with default
+; x86 target), so aggressively form vector binop.
 
 define i32 @ext1_ext1_add_same_vec(<4 x i32> %x) {
 ; CHECK-LABEL: @ext1_ext1_add_same_vec(
-; CHECK-NEXT:    [[E0:%.*]] = extractelement <4 x i32> [[X:%.*]], i32 1
-; CHECK-NEXT:    [[E1:%.*]] = extractelement <4 x i32> [[X]], i32 1
-; CHECK-NEXT:    [[R:%.*]] = add i32 [[E0]], [[E1]]
-; CHECK-NEXT:    ret i32 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add <4 x i32> [[X:%.*]], [[X]]
+; CHECK-NEXT:    [[TMP2:%.*]] = extractelement <4 x i32> [[TMP1]], i32 1
+; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %e0 = extractelement <4 x i32> %x, i32 1
   %e1 = extractelement <4 x i32> %x, i32 1
   %r = add i32 %e0, %e1
   ret i32 %r
 }
 
-; Negative test - same vector operand; scalar code is cheaper than general case.
+; Functionally equivalent to above test; should transform as above.
 
 define i32 @ext1_ext1_add_same_vec_cse(<4 x i32> %x) {
 ; CHECK-LABEL: @ext1_ext1_add_same_vec_cse(
-; CHECK-NEXT:    [[E0:%.*]] = extractelement <4 x i32> [[X:%.*]], i32 1
-; CHECK-NEXT:    [[R:%.*]] = add i32 [[E0]], [[E0]]
-; CHECK-NEXT:    ret i32 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add <4 x i32> [[X:%.*]], [[X]]
+; CHECK-NEXT:    [[TMP2:%.*]] = extractelement <4 x i32> [[TMP1]], i32 1
+; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %e0 = extractelement <4 x i32> %x, i32 1
   %r = add i32 %e0, %e0
   ret i32 %r
 }
 
 declare void @use_i8(i8)
 

 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %e = extractelement <16 x i8> %x, i32 0
   call void @use_i8(i8 %e)
   %r = add i8 %e, %e
   ret i8 %r
 }
 
-; Negative test - vector code would not be cheaper.
+; Vector code costs the same as scalar, so aggressively form vector op.
 
 define i8 @ext1_ext1_add_uses1(<16 x i8> %x, <16 x i8> %y) {
 ; CHECK-LABEL: @ext1_ext1_add_uses1(
 ; CHECK-NEXT:    [[E0:%.*]] = extractelement <16 x i8> [[X:%.*]], i32 0
 ; CHECK-NEXT:    call void @use_i8(i8 [[E0]])
-; CHECK-NEXT:    [[E1:%.*]] = extractelement <16 x i8> [[Y:%.*]], i32 0
-; CHECK-NEXT:    [[R:%.*]] = add i8 [[E0]], [[E1]]
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add <16 x i8> [[X]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = extractelement <16 x i8> [[TMP1]], i32 0
+; CHECK-NEXT:    ret i8 [[TMP2]]
 ;
   %e0 = extractelement <16 x i8> %x, i32 0
   call void @use_i8(i8 %e0)
   %e1 = extractelement <16 x i8> %y, i32 0
   %r = add i8 %e0, %e1
   ret i8 %r
 }
 
-; Negative test - vector code would not be cheaper.
+; Vector code costs the same as scalar, so aggressively form vector op.
 
 define i8 @ext1_ext1_add_uses2(<16 x i8> %x, <16 x i8> %y) {
 ; CHECK-LABEL: @ext1_ext1_add_uses2(
-; CHECK-NEXT:    [[E0:%.*]] = extractelement <16 x i8> [[X:%.*]], i32 0
 ; CHECK-NEXT:    [[E1:%.*]] = extractelement <16 x i8> [[Y:%.*]], i32 0
 ; CHECK-NEXT:    call void @use_i8(i8 [[E1]])
-; CHECK-NEXT:    [[R:%.*]] = add i8 [[E0]], [[E1]]
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add <16 x i8> [[X:%.*]], [[Y]]
+; CHECK-NEXT:    [[TMP2:%.*]] = extractelement <16 x i8> [[TMP1]], i32 0
+; CHECK-NEXT:    ret i8 [[TMP2]]
 ;
   %e0 = extractelement <16 x i8> %x, i32 0
   %e1 = extractelement <16 x i8> %y, i32 0
   call void @use_i8(i8 %e1)
   %r = add i8 %e0, %e1
   ret i8 %r
 }