[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

[vdmitrie]

The patch is seems trying to move SLP vectorizer into InstCombine territory. I'm not sure why we should do that. Did you try to analyze which specific patterns helped in for example GCC-C-execute test?
Can these represent any cases where instcombine could be improved instead? It is difficult to access this patch based on test changes as a lot of SLP vectorizer tests were not designed as capable to run through instcombine.
If you run "-instcombine -slp-vectorizer" instead of just -slp-vectorizer then how many of the affected LIT tests would still benefit from the patch?

[ABataev]

In D132261#3821385, @vdmitrie wrote:

The patch is seems trying to move SLP vectorizer into InstCombine territory. I'm not sure why we should do that. Did you try to analyze which specific patterns helped in for example GCC-C-execute test?
Can these represent any cases where instcombine could be improved instead? It is difficult to access this patch based on test changes as a lot of SLP vectorizer tests were not designed as capable to run through instcombine.
If you run "-instcombine -slp-vectorizer" instead of just -slp-vectorizer then how many of the affected LIT tests would still benefit from the patch?

Most of these test will be optimized for sure, since they are pretty simple. But looks like there are some other places, where reduction analysis in SLP is better than the similar analysis in instcombiner. Also, if we can do some optimization here, it shall reduce compile time, since instcombiner consumes lots of time

[ABataev]

Rebase

[ABataev]

Now the difference is even more:

            test-suite :: SingleSource/Benchmarks/Adobe-C++/loop_unroll.test   431225.00   431288.00  0.0%
       test-suite :: External/SPEC/CFP2017rate/510.parest_r/510.parest_r.test  2198241.00  2198465.00  0.0%
                      test-suite :: MultiSource/Applications/SPASS/SPASS.test   530608.00   530640.00  0.0%
        test-suite :: External/SPEC/CINT2006/400.perlbench/400.perlbench.test  1135953.00  1135937.00 -0.0%
               test-suite :: External/SPEC/CFP2006/447.dealII/447.dealII.test   651440.00   651360.00 -0.0%
test-suite :: MultiSource/Benchmarks/DOE-ProxyApps-C/SimpleMOC/SimpleMOC.test    48631.00    48311.00 -0.7%

InstCombine can simplify most of the currently not optimized stuff, but requires extra passes (like ReassociatePass) and extra compile time, while we can do it easily in SLP vectorizer, since we already have all required data. PhaseOrdering tests are the proves.

[ABataev]

Ping

[vdmitrie]

A couple of general thoughts. Can you please add a knob that allows to turn off the optimization? And can some sort of debug tracing be added? Such as values that has been optimized away?

[ABataev]

Address comments

[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

12066

Use allConstant() ?

12175

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.

11880

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

12057

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

12182–12191

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

12201

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

12205–12206

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.

12207

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?

12213

drop_front() ?

12325

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

12326–12335

Fuse these loops?

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

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

12340–12371

Fuse these loops?

12749

Please add a description.

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

12213

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

12209

"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.

12213

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;
 })`

12853

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

12201

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

12207

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

12199

This comment line seems to be misplaced.

12760–12778

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.

12840

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

12760–12778

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).

12840

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

[ABataev]

Fix comment

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

12760–12778

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

12758–12761

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

12758–12761

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

12758–12761

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

12758–12761

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.