[SLP]Do not reduce repeated values, use scalar red ops instead.

[ABataev]

Summary

Metric: size..text

size..text                 results     results0    diff

SingleSource/Regression/C/gcc-c-torture/execute/GCC-C-execute-980605-1.test 445.00 461.00 3.6%
SingleSource/Benchmarks/Adobe-C++/loop_unroll.test 428477.00 428445.00 -0.0%
External/SPEC/CFP2006/447.dealII/447.dealII.test 618849.00 618785.00 -0.0%

For all tests some extra code was optimized, GCC-C-execute has some more
inlining after

[ABataev]

Rebase, ping.

[vdmitrie]

I'll try to look at this closely next week (but not earlier than Monday). Just a quick note about terminology used. The option name "slp-same-scalars-reduction" does not actually tell much about what it actually controls.
Since you basically are trying to optimize away identity operations in reduction sequences I'd suggest you to use name for option and across the code that better reflect that.
The option name could be "-slp-optimize-identity-hor-reduction-ops=true|false" for example.

[ABataev]

Rebase, renamed option, added a test run for false option value

[ABataev]

Rebase, ping!

[ABataev]

Rebase, ping!

[ABataev]

Ping!

[RKSimon]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

11205

Use allConstant() ?

11307

allConstant(Candidates)

[ABataev]

Address comments

[ABataev]

Rebase

[vdmitrie]

I'm sorry for the delay. Was bit overloaded with an internal stuff.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

131

Would the following description
"Allow optimization of original scalar identity operations on matched horizontal reductions."
sound better?
Same question wrt AllowSameScalarReduction variable name. Will AllowHorRdxIdenityOptimization fit better?

It probably makes sense to add a note (as a comment above or into the commit message): will the optimization run if we match a reduction but do not vectorize at the end? Based on test updates it looks like it will run. IMO that should be clearly stated that the pass outcome might not be a vectorized code.

11085

nit: noticed by chance while was refreshing with the code. This call to getRdxKind can be safely replaced with RdxKind.

11201–11202

nit: maybe make it unsigned too (+ deduction rule)?

11314–11323

This code pattern is seen multiple times. Any chance to outline it?
+ (for better readability) swap then/else and remove '!' from condition?

11333

We don't need to collect repeating counters if IsSupportedreusedRdxOp is false.

11337–11338

This code shall form a member of HorizontalReduction class and emitReusedOps() need to assert it can handle a case by calling the former before doing any processing.

11339

This needs a comment. Are you trying to catch a case for special processing when each value used same times? Please describe what is the benefit of catching such cases?
Why are you trying to calculate it this early?

11345

drop_front() ?

11455

Are you trying to repurpose the data?
To be honest, I'd refrain from doing that.

11456–11465

Fuse these loops?

` for (unsigned Cnt = 0; Cnt < NumReducedVals; ++Cnt) {

   if (Cnt >= Pos && Cnt < Pos + ReduxWidth)
     continue;
  ...
}`

11474–11488

Fuse these loops?

11848

Please add a description.

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

11345

drop_front() ?

This was a "nit" actually. drop_front() needs ArrayRef, so it should look like the following:
ArrayRef<std::pair<Value *, unsigned>>(SameValuesCounter.takeVector()).drop_front()

probably not worth the effort to save on just one comparison.

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

11341

"IsSupportedReusedRdxOp && HasReusedScalars" pattern is the most common use.
What about defining it as below
`bool OptReusedScalars = IsSupportedReusedRdxOp &&

SameValuesCounter.size() != NumReducedVals;`

and just check for OptReusedScalars everywhere across the code?
It only used differently at line 12683 but check for HasReusedScalars can be safely dropped there.

11345

Uhh, I did not realize takeVector clears the map.
finally... this one should do the trick:

`all_of(drop_begin(SameValuesCounter),

[&SameValuesCounter](const std::pair<Value *, unsigned> &P) {
  return P.second == SameValuesCounter.begin()->second;
 })`

11952

May be reorganize it a bit to add a return statement? It can produce warning "control reaches end of non-void function [-Wreturn-type]"

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

11333

No, still need it, it is used to produce vector of unique scalars, see line 12577.

11339

It may help to produce better vector ops. Say, we have 8 x aabbccdd. It will require reduction of 8 elements + the built tree still will operate on 4 x element, but the last node will have reshuffle from 4 x vector to 8 x vector + red(8 x ). Instead we may have just red(4 x abcd)*2.

[ABataev]

Address comments

[ABataev]

Rebase

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

11331

This comment line seems to be misplaced.

11859–11877

What I basically see here is that you packed two methods into one and differentiate them by VL argument.
May be just split this method in two ? One to handle identity optimization and another for same scale factor optimization. They seems do not share any essential code, only the switch. But sharing the switch does not look right to me as these optimizations do not fully share reduction kinds.

11939

Are you relying on instcombiner to optimize this further? I mean for example mul X, 2 -> add X, X

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

11859–11877

I thought about it, just in many cases we reuse the same code, so I decided to put it into single switch (just (f)add and xor have special processing).

11939

Yes, because there might be some other numbers, say 3, 4, etc.

[ABataev]

Fix comment

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

11859–11877

I don't buy this kind of savings. Ideally we want to assert that we have one of add/fadd/xor reduction kind when we fall into same scale factor optimization. This is why I advocate for splitting it in two. We do not save a lot on switch which will be handing just 3 cases and default one for the second method. Code inside the switch cases is already separate. So it is easy to do from the very beginning.

[ABataev]

Address comments

[vdmitrie]

Thanks. This revision basically looks good to me. So I'm going to accept it.
@RKSimon , do you have any remarks/comments/concerns?

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

11857–11860

okay :-) that works too

just a n.i.t. remark: you could reduce arguments to just these if the code was a dedicated method:
(Value *VectorizedValue, IRBuilderBase &Builder, ArrayRef<Value *> VL, unsigned Cnt)

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

11857–11860

It is not possible, both SameValuesCounter and TrackedToOrig are used for each elements of VL in the second switch to build correct constant vector.

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

11857–11860

I don't see that.
Isn't the following is the only use of them in this part (under condition VL.empty())?

` unsigned Cnt =

SameValuesCounter.lookup(TrackedToOrig.find(VectorizedValue)->second);

`
Aha, I even overlooked that you don't actually use VL elements in this part too.
So here are the only essential arguments for it:
(Value *VectorizedValue, IRBuilderBase &Builder, unsigned Cnt)

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

11857–11860

Ah, I missed that you said about second switch. I was thinking about first part of the method.
May be I wasn't clear enough.
I meant to have a separate method for the part which is currently under VL.empty().
Value *emitScaleForReusedOps(Value *VectorizedValue, IRBuilderBase &Builder, unsigned Scale) {

... here goes the code which is now under VL.empty() ...

}

[ABataev]

Address comments

[vdmitrie]

Perfect! Looks good. Thanks, Alexey!

[skatkov]

@ABataev, please take a look at https://github.com/llvm/llvm-project/issues/61050

[dyung]

@ABataev, one of our internal tests seems to hit an infinite loop in the compiler after this change. I have filed issue 61224 for the issue, can you take a look?

[ABataev]

In D132261#4172316, @dyung wrote:

@ABataev, one of our internal tests seems to hit an infinite loop in the compiler after this change. I have filed issue 61224 for the issue, can you take a look?

Will check/fix ASAP.

[vdmitrie]

t.ll5 KBDownload

Hi Alexey,
something isn't quite right with the transformation:
$ opt -passes=slp-vectorizer -slp-optimize-identity-hor-reduction-ops=false -S -o j.ll t.ll && llc -O0 j.ll && clang j.s -o a.out && ./a.out
209
$ opt -passes=slp-vectorizer -slp-optimize-identity-hor-reduction-ops=true -S -o j.ll t.ll && llc -O0 j.ll && clang j.s -o a.out && ./a.out
202

[ikelarev]

Hi Alexey,

It turned out that in some cases the transformation introduced in this change doesn't work properly. Let's consider this code:

target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define i32 @main() {
entry:
  %sq = alloca [64 x i32], i32 0, align 16
  
  %0 = getelementptr inbounds [64 x i32], ptr %sq, i64 0, i64 1
  %elt_1 = load i32, ptr %0, align 4
  %1 = getelementptr [64 x i32], ptr %sq, i64 0, i64 2
  %elt_2 = load i32, ptr %1, align 8
  %2 = getelementptr [64 x i32], ptr %sq, i64 0, i64 3
  %elt_3 = load i32, ptr %2, align 4
  %3 = getelementptr [64 x i32], ptr %sq, i64 0, i64 4
  %elt_4 = load i32, ptr %3, align 16  
  
  %4 = add i32 %elt_2, %elt_3
  %5 = add i32 %4, %elt_2
  %6 = add i32 %5, %elt_1  
  %7 = add i32 %6, %elt_4
  %8 = add i32 %7, %elt_3
  %9 = add i32 %8, %elt_2
  %10 = add i32 %9, %elt_1
  
  %call = tail call i32 (ptr, ...) null(ptr null, i32 %10)
  ret i32 0
}

It's easy to see that %10 fianl value is 2*%elt_1 + 3*%elt_2 + 2*%elt_3 + %elt_4. But actually we get this code:

$ opt -S test.ll -passes=slp-vectorizer
...
define i32 @main() {
entry:
  %sq = alloca [64 x i32], i32 0, align 16
  %0 = getelementptr inbounds [64 x i32], ptr %sq, i64 0, i64 1
  %1 = load <4 x i32>, ptr %0, align 4
  %2 = mul <4 x i32> %1, <i32 3, i32 2, i32 2, i32 1>
  %3 = call i32 @llvm.vector.reduce.add.v4i32(<4 x i32> %2)
  %call = tail call i32 (ptr, ...) null(ptr null, i32 %3)
  ret i32 0
}

<i32 3, i32 2, i32 2, i32 1> value doesn't look correct, it should be <i32 2, i32 3, i32 2, i32 1>. Running the test with -slp-optimize-identity-hor-reduction-ops=false gives us this code:

$ opt -S test.ll -passes=slp-vectorizer -slp-optimize-identity-hor-reduction-ops=false
...
define i32 @main() {
entry:
  %sq = alloca [64 x i32], i32 0, align 16
  %0 = getelementptr inbounds [64 x i32], ptr %sq, i64 0, i64 1
  %1 = load <4 x i32>, ptr %0, align 4
  %2 = shufflevector <4 x i32> %1, <4 x i32> poison, <8 x i32> <i32 1, i32 1, i32 1, i32 2, i32 2, i32 0, i32 0, i32 3>
  %3 = call i32 @llvm.vector.reduce.add.v8i32(<8 x i32> %2)
  %call = tail call i32 (ptr, ...) null(ptr null, i32 %3)
  ret i32 0
}

<i32 1, i32 1, i32 1, i32 2, i32 2, i32 0, i32 0, i32 3> consist of two zeros and three ones which is correct which means that the incorrectness was introduced with this change.

[ABataev]

I'll investigate all reports, thanks!

[calebwat]

To add on to the above, the order of the values in the scale vector is determined by the default order of Candidates, and in these test cases there's a mismatch between that order and the lanes that the scalar values are in in the vectorized value.

[ABataev]

Ok, have a fix for the issue, it is very simple. Forgot to take the ordering into account, which can be dropped for the reductions.

[ABataev]

Fixed in c1660006b2809a17e9e33034252306a703fdb720

[Matt]

@ABataev May I ask whether the change to constant folding semantics is intended with -slp-optimize-identity-hor-reduction-ops?

Cf. https://godbolt.org/z/G44xhKcTc

I wonder whether this may be connected to the constant folding similar to createOp related to this patch, https://github.com/llvm/llvm-project/issues/61224, https://github.com/llvm/llvm-project/commit/c411965820eb803dd7eac39f80357cad663b7ba0

• LLVM version 16.0.0

opt -passes=slp-vectorizer

%mul = fmul reassoc nsz float 0x39B4484C00000000, 0x39B4484C00000000
ret float %mul

• LLVM version 17.0.0git

opt -passes=slp-vectorizer -slp-optimize-identity-hor-reduction-ops=0

%mul = fmul reassoc nsz float 0x39B4484C00000000, 0x39B4484C00000000
ret float %mul

• LLVM version 17.0.0git

opt -passes=slp-vectorizer

ret float 0.000000e+00

[ABataev]

In D132261#4317008, @Matt wrote:

@ABataev May I ask whether the change to constant folding semantics is intended with -slp-optimize-identity-hor-reduction-ops?

Cf. https://godbolt.org/z/G44xhKcTc

I wonder whether this may be connected to the constant folding similar to createOp related to this patch, https://github.com/llvm/llvm-project/issues/61224, https://github.com/llvm/llvm-project/commit/c411965820eb803dd7eac39f80357cad663b7ba0

• LLVM version 16.0.0

opt -passes=slp-vectorizer

%mul = fmul reassoc nsz float 0x39B4484C00000000, 0x39B4484C00000000
ret float %mul

• LLVM version 17.0.0git

opt -passes=slp-vectorizer -slp-optimize-identity-hor-reduction-ops=0

%mul = fmul reassoc nsz float 0x39B4484C00000000, 0x39B4484C00000000
ret float %mul

• LLVM version 17.0.0git

opt -passes=slp-vectorizer

ret float 0.000000e+00

Yes, slp-vectorizer may fold constants as a side effect of the reduction optimization.

[Matt]

Thanks!

This explains some of the behavior I've observed.
Context: Downstream implementation with a custom floating-point trapping behavior which generally disables constant folding for would-be trapping operations (such as mutiplying 1e-30f * 1e-30f which would result FE_UNDERFLOW due to underflow to zero).

The issue I've observed is exactly like in https://github.com/llvm/llvm-project/issues/61224, i.e., an infinite loop.
I suppose this is due to the fact that FMul (as in the example above) is not constant folded.

I think I may be able to deal with this downstream if I can prevent the constant folding alone while not regressing back to the infinite loop as in issue 61224 (I suppose that run into the infinite loop as the pass at this point didn't expect non-constant-folded instructions?).
As a workaround I may be able to disable AllowHorRdxIdenityOptimization whenever the custom trapping is enabled.
For my context, I'm wondering, would you happen to know whether disabling the constant-folding alone without running into an infinite loop issue is even possible?

I've noticed there are 4 occurrences of AllowHorRdxIdenityOptimization and I can try to experiment selective disablement (I presume the allConstant branches are mostly relevant here) but thought I'd ask just in case this is a general issue.

[ABataev]

In D132261#4317112, @Matt wrote:

Thanks!

This explains some of the behavior I've observed.
Context: Downstream implementation with a custom floating-point trapping behavior which generally disables constant folding for would-be trapping operations (such as mutiplying 1e-30f * 1e-30f which would result FE_UNDERFLOW due to underflow to zero).

The issue I've observed is exactly like in https://github.com/llvm/llvm-project/issues/61224, i.e., an infinite loop.
I suppose this is due to the fact that FMul (as in the example above) is not constant folded.

I think I may be able to deal with this downstream if I can prevent the constant folding alone while not regressing back to the infinite loop as in issue 61224 (I suppose that run into the infinite loop as the pass at this point didn't expect non-constant-folded instructions?).
As a workaround I may be able to disable AllowHorRdxIdenityOptimization whenever the custom trapping is enabled.
For my context, I'm wondering, would you happen to know whether disabling the constant-folding alone without running into an infinite loop issue is even possible?

I've noticed there are 4 occurrences of AllowHorRdxIdenityOptimization and I can try to experiment selective disablement (I presume the allConstant branches are mostly relevant here) but thought I'd ask just in case this is a general issue.

Yes, use -slp-optimize-identity-hor-reduction-ops=false to disable constant optimizations. Meanwhile I will try to provide a more general fix for the problem.

[Matt]

Thank you!

[ABataev]

In D132261#4317118, @Matt wrote:

Thank you!

Try after d726f99d43a5bcbcdb63dbb3e2213733f3ca0259

[Matt]

Just tested with the commit and appears to be working--thank you once again!