[LV] Interleave to expose ILP for small loops with scalar reductions.

[AaronLiu]

Summary

Interleave for small loops that have reductions inside,
which breaks dependencies and expose ILP.

This gives very significant performance improvements for some benchmarks.
Because small loops could be in very hot functions in real applications.

[AaronLiu]

A little bit of format change.

[AaronLiu]

Ping...

[bmahjour]

The rationale for allowing more aggressive interleaving on small loops with reductions makes sense to me, and this is going to be off by default, so I think it should be fine. But I'll let others comment first.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5523

IC reported here may be different from the interleave count that is finally returned from this function. It's probably better not to emit it here since it's not finalized. The VF is also available elsewhere in the debug trace, so not sure if it's worth changing this debug output.

5564

What's the significance of the value 2 here?

[AaronLiu]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5523

Thanks for the review @bmahjour! Correct, IC may be different from the interleave count that is finally returned, add debug options here for IC is to show before and after "Interleaving to expose ILP". For example if you add "-mllvm -debug-only=loop-vectorize" for the clang/clang++ invocation, after compiling the provided testcase, you will get something like the following output:
...
LV: Loop cost is 8
LV: IC is 8
LV: VF is 1
LV: Interleaving to expose ILP.
...
LV: Interleave Count is 4
Setting best plan to VF=1, UF=4
...
There are only two lines added here, comparing with tons of debug output for all instructions by the LV costmodel and digraph VPlan debug output, this is very little. And I find that the very little info is very useful for knowing what's going on at this point.

5564

Still use the above output as an example: the normal IC is 8, and SmallIC is definitely no more than 2 after calculation. SmallIC is too small and will not benefit SLP, and the provided testcase will not be vectorized. The normal IC is a little bit big in some rare situation when resources are too limited, for example in full width runs when all CPUs are running. The division by 2 here make it not that aggressive as the normal IC, but still can vectorize the testcase.

[bmahjour]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

5564

Ok. It would be useful to have a brief comment in the code about this.

[AaronLiu]

Add comments to address code review.

[AaronLiu]

Update comments to address code review.

[lebedev.ri]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

251

Can cost model be used for this instead?

[AaronLiu]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

251

Thanks for the comment. This is the cost model tuning.

[spatel]

IIUC, we should add a test under test/Transforms/PhaseOrdering with -O2 to show the cooperative effect of the 2 vectorizers rather than a stand-alone SLP test.
If you can push that test with full baseline CHECK lines and then apply this patch and show test diffs, that would make it much easier to tell what is intended with this patch.

[AaronLiu]

In D81416#2095961, @spatel wrote:

IIUC, we should add a test under test/Transforms/PhaseOrdering with -O2 to show the cooperative effect of the 2 vectorizers rather than a stand-alone SLP test.
If you can push that test with full baseline CHECK lines and then apply this patch and show test diffs, that would make it much easier to tell what is intended with this patch.

Thanks for the comment. This patch does not intend to change or test phase ordering. In this patch, we interleave for small loops with scalar reductions which cannot be vectorized by LV, and later on SLP captures the opportunities. Interleaving is done by LV, and vectorization is done by SLP.

[spatel]

In D81416#2096034, @AaronLiu wrote:

In D81416#2095961, @spatel wrote:

IIUC, we should add a test under test/Transforms/PhaseOrdering with -O2 to show the cooperative effect of the 2 vectorizers rather than a stand-alone SLP test.
If you can push that test with full baseline CHECK lines and then apply this patch and show test diffs, that would make it much easier to tell what is intended with this patch.

Thanks for the comment. This patch does not intend to change or test phase ordering. In this patch, we interleave for small loops with scalar reductions which cannot be vectorized by LV, and later on SLP captures the opportunities. Interleaving is done by LV, and vectorization is done by SLP.

We use PhaseOrdering tests to ensure that the end result of >1 IR pass (usually the entire pipeline of -O* settings) produces the expected result. That may be stretching the meaning of PhaseOrdering, but that would be less fragile than the stand-alone SLP test. This patch isn't changing anything in SLP, so the test you are adding to SLP is independent of this patch, right?

[AaronLiu]

We use PhaseOrdering tests to ensure that the end result of >1 IR pass (usually the entire pipeline of -O* settings) produces the expected result. That may be stretching the meaning of PhaseOrdering, but that would be less fragile than the stand-alone SLP test. This patch isn't changing anything in SLP, so the test you are adding to SLP is independent of this patch, right?

Correct, this patch isn't changing anything in SLP.

[AaronLiu]

Add llvm/test/Transforms/PhaseOrdering/interleave_LV_SLP.ll

[AaronLiu]

In D81416#2095961, @spatel wrote:

IIUC, we should add a test under test/Transforms/PhaseOrdering with -O2 to show the cooperative effect of the 2 vectorizers rather than a stand-alone SLP test.
If you can push that test with full baseline CHECK lines and then apply this patch and show test diffs, that would make it much easier to tell what is intended with this patch.

Hi Sanjay,

I add a test: llvm/test/Transforms/PhaseOrdering/interleave_LV_SLP.ll
Please let me know whether that is what you wanted.

Thanks!

[AaronLiu]

Ping...

[xbolva00]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

253

Turn on by default?

If you ran some benchmarks and no regressions, I see no reason why this should be off by default.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

253

It would be good to at least give some details on the benchmarks run. Ideally they would include MultiSource & various version of SPEC on X86 and ideally also other platforms.

[bmahjour]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

253

The current measurements are done on IBM Power. It would be good if someone with access to other types of performance machines could help measure the impact of this change on other platforms. If not, can we leave the default enablement to a future patch?

In general, how are performance testing on multiple platforms performed by the community, prior to enabling a feature?

[xbolva00]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

253

@dmgreen arm
@nikic x86?

[dmgreen]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

253

This sounds like unrolling to me. But with pointer runtime checks to allow extra ILP?

Something like that would usually be a target decision, in the unroller controlled by getUnrollingPreferences or for the vectorizer controlled by other calls like enableAggressiveInterleaving. Targets can then opt in to the feature if they expect to find them useful.

If it is expected to be more universally applicable then you can try and just enable it and see if people report regressions. But some X86 benchmarks using the llvm testsuite would probably be prudent first.

The (sub)target I run on most (MVE) will not enable interleaving nor AggressiveInterleaving, so probably isn't very helpful for performance numbers.

[spatel]

In D81416#2099655, @AaronLiu wrote:

I add a test: llvm/test/Transforms/PhaseOrdering/interleave_LV_SLP.ll
Please let me know whether that is what you wanted.

Thanks - that was the start of what I requested, but not complete. I've added the test here using auto-generated CHECK lines that show baseline (without this patch) results:
rGdf79443

Please rebase and update that file using the script at llvm/utils/update_test_checks.py.
I don't think we need to duplicate the test in the SLP folder now that we have coverage for this example in PhaseOrdering, but if you think that is still useful, that can be added independently of this patch.

[nikic]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

253

@xbolva00 I don't have any run-time numbers, I only check compile-time (there's no impact there at least).

[AaronLiu]

In D81416#2108976, @spatel wrote:

In D81416#2099655, @AaronLiu wrote:

I add a test: llvm/test/Transforms/PhaseOrdering/interleave_LV_SLP.ll
Please let me know whether that is what you wanted.

Thanks - that was the start of what I requested, but not complete. I've added the test here using auto-generated CHECK lines that show baseline (without this patch) results:
rGdf79443

Please rebase and update that file using the script at llvm/utils/update_test_checks.py.
I don't think we need to duplicate the test in the SLP folder now that we have coverage for this example in PhaseOrdering, but if you think that is still useful, that can be added independently of this patch.

Thanks - I rebase and update PhaseOrdering/interleave_LV_SLP.ll using auto-generated CHECK lines that show baseline (with this patch) results.
I think all the four testcases are related to this patch, and I prefer to keep the testcase in this patch. The four testcases all serve different purposes:

• PhaseOrdering/interleave_LV_SLP.ll shows that with the option in this patch on, instructions were vectorized. But which vectorizer make it work? We cannot tell.
• Vectorize/LoopVectorize.cpp tells us that LV cannot vectorize the code, but interleave the instructions to expose ILP.
• SLPVectorizer/PowerPC/interleave_SLP.ll demonstrates that after interleaving by LV, then SLP captures the opportunities and vectorize the instructions.
• The one you added in PhaseOrdering/interleave-vectorization.ll show that without this patch(equivalently with the option in this patch off), the same testcase both LV and SLP cannot vectorize the instructions.

[spatel]

In D81416#2110070, @AaronLiu wrote:

I think all the four testcases are related to this patch, and I prefer to keep the testcase in this patch. The four testcases all serve different purposes:

• PhaseOrdering/interleave_LV_SLP.ll shows that with the option in this patch on, instructions were vectorized. But which vectorizer make it work? We cannot tell.
• Vectorize/LoopVectorize.cpp tells us that LV cannot vectorize the code, but interleave the instructions to expose ILP.
• SLPVectorizer/PowerPC/interleave_SLP.ll demonstrates that after interleaving by LV, then SLP captures the opportunities and vectorize the instructions.
• The one you added in PhaseOrdering/interleave-vectorization.ll show that without this patch(equivalently with the option in this patch off), the same testcase both LV and SLP cannot vectorize the instructions.

This still isn't quite what I was hoping for. Can you just add "-interleave-small-loop-scalar-reduction=true" to the RUN lines of the file I added and update the CHECK lines using the script? I want this patch to show *the diff* in IR for the proposed code change. I can't easily tell what is changing by comparing 2 different files.

[AaronLiu]

In D81416#2112569, @spatel wrote:

In D81416#2110070, @AaronLiu wrote:

I think all the four testcases are related to this patch, and I prefer to keep the testcase in this patch. The four testcases all serve different purposes:

• PhaseOrdering/interleave_LV_SLP.ll shows that with the option in this patch on, instructions were vectorized. But which vectorizer make it work? We cannot tell.
• Vectorize/LoopVectorize.cpp tells us that LV cannot vectorize the code, but interleave the instructions to expose ILP.
• SLPVectorizer/PowerPC/interleave_SLP.ll demonstrates that after interleaving by LV, then SLP captures the opportunities and vectorize the instructions.
• The one you added in PhaseOrdering/interleave-vectorization.ll show that without this patch(equivalently with the option in this patch off), the same testcase both LV and SLP cannot vectorize the instructions.

This still isn't quite what I was hoping for. Can you just add "-interleave-small-loop-scalar-reduction=true" to the RUN lines of the file I added and update the CHECK lines using the script? I want this patch to show *the diff* in IR for the proposed code change. I can't easily tell what is changing by comparing 2 different files.

The "-interleave-small-loop-scalar-reduction=true" is in the file PhaseOrdering/interleave_LV_SLP.ll already.
If I add "-interleave-small-loop-scalar-reduction=true" to the RUN lines of the file you added(PhaseOrdering/interleave-vectorization.ll) and update the CHECK lines using the script, this will be a completely a dup of the file PhaseOrdering/interleave_LV_SLP.ll in this patch.

In order for "this patch to show *the diff* in IR for the proposed code change" and "easily tell what is changing by comparing 2 different files" in this patch, can you please remove the file you added?

I will add "PhaseOrdering/interleave_LV_SLP_false.ll" which will be "-interleave-small-loop-scalar-reduction=false", and compare with current "PhaseOrdering/interleave_LV_SLP.ll" which is "-interleave-small-loop-scalar-reduction=true".

So we can compare everything in one patch, instead of two patches?

Also this way, there will be no lit failure problems whether change the default option to be "true" or "false".

Thanks!

[spatel]

In D81416#2112690, @AaronLiu wrote:

In order for "this patch to show *the diff* in IR for the proposed code change" and "easily tell what is changing by comparing 2 different files" in this patch, can you please remove the file you added?

I did that here:
rGc336f21

I will add "PhaseOrdering/interleave_LV_SLP_false.ll" which will be "-interleave-small-loop-scalar-reduction=false", and compare with current "PhaseOrdering/interleave_LV_SLP.ll" which is "-interleave-small-loop-scalar-reduction=true".

So we can compare everything in one patch, instead of two patches?

Usually, we add another "RUN" line + FileCheck prefix to a file to show the output differences for a given test when toggling a command-line parameter. I'm not sure why this case is different, but somebody more familiar with LoopVectorize should continue this review.

[AaronLiu]

Update three testcases, and add one more testcase to this patch.

[AaronLiu]

Currently all four testcases serve different purposes, and we can clearly see their differences:

• PhaseOrdering/interleave_LV_SLP_false.ll gives the baseline result, which shows that with the option in this patch off, instructions are not being vectorized.
• PhaseOrdering/interleave_LV_SLP.ll also gives the baseline result, which shows that with the option in this patch on, instructions are being vectorized. But which vectorizer make it work? We cannot tell.
• Vectorize/LoopVectorize.cpp tells us that LV cannot vectorize the code, but interleave the instructions to expose ILP.
• SLPVectorizer/PowerPC/interleave_SLP.ll demonstrates that after interleaving by LV, then SLP captures the opportunities and vectorize the instructions.

[bmahjour]

May I suggest we only test what this patch actually changes? This patch adds an option which when enabled allows interleaving of loops with small trip counts and scalar reductions, so it suffices to test exactly that. That should be covered by llvm/test/Transforms/LoopVectorize/PowerPC/interleave_IC.ll. I think the other test cases can be removed. IMHO adding more tests to make sure SLP vectorization happens (and the like) are redundant, add unnecessary maintenance in the future and are beyond the scope of what this patch is trying to do.

llvm/test/Transforms/LoopVectorize/PowerPC/interleave_IC.ll

2

There is a target triple in the IR too so -mtriple=powerpc64le-unknown-linux should not be necessary. Alternatively you can remove the triple from the IR if that's what the other test cases in this directory do.

llvm/test/Transforms/PhaseOrdering/interleave_LV_SLP.ll

3 ↗

(On Diff #273753)

please see my comment about triple.

[AaronLiu]

In this patch we "Interleave to expose ILP". The whole purpose of this patch is to "expose ILP", and the approach is to "Interleave".

• I worry about that if we remove those testcases, no vectorization(parallelism) results due to this patch can be seen, and people will have no idea where do we "expose ILP"?
• We have ever discussed that what @spatel suggested adding two testcases under PhaseOrdering to show the baseline results with the option in this patch on and off "do make sense".
• The purpose of adding lit tests is to catch future regressions, i.e., if someone make the vectorization not working, we will catch it with the testcases we added.

[AaronLiu]

Update testcases.

[Ayal]

In D81416#2096034, @AaronLiu wrote:

In D81416#2095961, @spatel wrote:

IIUC, we should add a test under test/Transforms/PhaseOrdering with -O2 to show the cooperative effect of the 2 vectorizers rather than a stand-alone SLP test.
If you can push that test with full baseline CHECK lines and then apply this patch and show test diffs, that would make it much easier to tell what is intended with this patch.

Thanks for the comment. This patch does not intend to change or test phase ordering. In this patch, we interleave for small loops with scalar reductions which cannot be vectorized by LV, and later on SLP captures the opportunities. Interleaving is done by LV, and vectorization is done by SLP.

LV *cannot* vectorize the loop, or will not do so? If LV can interleave the loop, it should be able to also/instead vectorize it, unless there are some other obstacles? Is this an issue of LV's cost-model being more conservative than SLP's? If so, would updating LV's cost-model be a (more) appropriate remedy, than convincing LV to unroll for SLP?
The term "small loops" may be confusing; it presumably relates to loops having small number of instructions or low ILP(?), rather than small trip-count.

[AaronLiu]

In the application we try, LV refuse to vectorize due to not profitable, but if we force LV to vectorize and it will crash. Apparently there are some obstacles. There are cases that even if LV fails, SLP could succeed.
Yes, the term small loop is a little bit of confusing. For example a loop which has a small number of instructions but has a huge loop trip count, is the loop small or big? In our example, the loop trip count is small, and also the instruction number is small.

[AaronLiu]

In D81416#2117912, @bmahjour wrote:

May I suggest we only test what this patch actually changes? This patch adds an option which when enabled allows interleaving of loops with small trip counts and scalar reductions, so it suffices to test exactly that. That should be covered by llvm/test/Transforms/LoopVectorize/PowerPC/interleave_IC.ll. I think the other test cases can be removed. IMHO adding more tests to make sure SLP vectorization happens (and the like) are redundant, add unnecessary maintenance in the future and are beyond the scope of what this patch is trying to do.

Will remove other three testcases.

[Ayal]

In D81416#2136421, @AaronLiu wrote:

In the application we try, LV refuse to vectorize due to not profitable, but if we force LV to vectorize and it will crash. Apparently there are some obstacles. There are cases that even if LV fails, SLP could succeed.

In that case, best understand why LV's cost model claims vectorizing the loop is not profitable, which you and SLP know it is; and ideally fix LV's cost model.
A crash due to forced vectorization sounds like a bug, which best be reported and/or fixed.
If cases with concrete "obstacles" are identified preventing LV from vectorizing a loop but allowing SLP to vectorize (part of) it, after LV interleaves the loop, such obstacles could potentially be used to (further) drive LV to interleave the loop.

Yes, the term small loop is a little bit of confusing. For example a loop which has a small number of instructions but has a huge loop trip count, is the loop small or big? In our example, the loop trip count is small, and also the instruction number is small.

Hence the term "small loop" should be more specific; as in "vectorizer-min-trip-count" / "TinyTripCountVectorThreshold".

[AaronLiu]

In that case, best understand why LV's cost model claims vectorizing the loop is not profitable, which you and SLP know it is; and ideally fix LV's cost model.
A crash due to forced vectorization sounds like a bug, which best be reported and/or fixed.
If cases with concrete "obstacles" are identified preventing LV from vectorizing a loop but allowing SLP to vectorize (part of) it, after LV interleaves the loop, such obstacles could potentially be used to (further) drive LV to interleave the loop.

Agree, ideally LV's cost model and its vectorization functionality should be improved in the future to be able to vectorize a lot more instructions.
We see some applications keep being crashed, due to some changes in LV and probably being fixed later on, or because of its own weakness in some aspects.
But all the above are beyond of this patch.
Currently, LV and SLP complement each other, and there are cases that LV fails to vectorize (functionally not being able to do it) but SLP succeed.

Hence the term "small loop" should be more specific; as in "vectorizer-min-trip-count" / "TinyTripCountVectorThreshold".

The "small or tiny" values are relative, and will keep on changing. In the situations we see, it is even more dynamic, the exact trip count is not known, but we know that it is relatively small.

[AaronLiu]

deleted: llvm/test/Transforms/PhaseOrdering/interleave_LV_SLP.ll
deleted: llvm/test/Transforms/PhaseOrdering/interleave_LV_SLP_false.ll
deleted: llvm/test/Transforms/SLPVectorizer/PowerPC/interleave_SLP.ll

[fhahn]

We see some applications keep being crashed, due to some changes in LV and probably being fixed later on, or because of its own weakness in some aspects.

Does the application crash or is the crash in LV? If it is LV, it would be great if you could report it at https://bugs.llvm.org

[AaronLiu]

Thanks! Will keep eyes on it in the future.

[AaronLiu]

Currently there is no SLP involved, and this patch can still give a significant performance improvement for the benchmark.

[AaronLiu]

Remove SLP comments.

[AaronLiu]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

253

The current measurements are done on IBM Power. It would be good if someone with access to other types of performance machines could help measure the impact of this change on other platforms. If not, can we leave the default enablement to a future patch?

Can someone help to test this patch on other platforms? Thanks!

[bmahjour]

Given that interleaving alone (without vectorization) can still cause major performance improvements shows that this is really an interleaving profitability issue, so the heuristic and the option seem ok to me. To enable the option by default we would need more testing on other platforms. That can be done in a separate patch.

Other than the minor comments I've left in the code, the changes look good to me. I'll approve once they are addressed unless of course there are objections or more comments from the reviewers.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

253

small loops with scalar reduction-> loops with small iteration counts that contain scalar reductions

5419

Please remove ScalarReductionCond and just use the conditions directly in the if statement below. Please also update the comments to remove references to this variable.

llvm/test/Transforms/LoopVectorize/PowerPC/interleave_IC.ll

62

[nit] add bb:
%bb apears in the comment on line 66.

[AaronLiu]

Address review comments.

[fhahn]

llvm/test/Transforms/LoopVectorize/PowerPC/interleave_IC.ll

55

Area all those types necessary? Would be good to clean up the test, including the GEPs with null/undef, otherwise the test might be painful to update in the future.

[fhahn]

llvm/test/Transforms/LoopVectorize/PowerPC/interleave_IC.ll

5

If C++ code is included, it would be good if it would be self-contained and build-able. Otherwise I am not sure what value it adds?

[fhahn]

Just to double check, wouldn't it be sufficient if loop-unroll would unroll the loop? Or is this not happening? It seems like loop-unroll would unroll the loop in the test-case.

[AaronLiu]

llvm/test/Transforms/LoopVectorize/PowerPC/interleave_IC.ll

5

We want to show the original problem, but do not want to copy the original code. For easy to understand, we use kind of pseudo C++ code, to show the characteristics of the original code which has reductions inside of nested loops, and indirect references for induction variables and reduction operands, etc. The original self-contained and build-able codes are too complex to show here.

55

The testcase is extracted and reduced from a real application which has very complex and nested data structures. This is the reason why it has those types defined in the IR.

[AaronLiu]

In D81416#2230628, @fhahn wrote:

Just to double check, wouldn't it be sufficient if loop-unroll would unroll the loop? Or is this not happening? It seems like loop-unroll would unroll the loop in the test-case.

It would unroll the loop in the testcase, but it will not break dependence and expose ILP, will not help performance, and actually unroll hurt performance in this case.

[fhahn]

In D81416#2230857, @AaronLiu wrote:

In D81416#2230628, @fhahn wrote:

Just to double check, wouldn't it be sufficient if loop-unroll would unroll the loop? Or is this not happening? It seems like loop-unroll would unroll the loop in the test-case.

It would unroll the loop in the testcase, but it will not break dependence and expose ILP, will not help performance, and actually unroll hurt performance in this case.

I didn't took a very close look, but wouldnt unrolling generate similar code as interleaving, modulo different order of instructions, but with similar compute instructions trees?

Also, it seems like the loop already gets interleaved on current trunk (With IC=2) and this patch makes it more aggressive. Might be good to describe how the IC gets boosted by this option.

llvm/test/Transforms/LoopVectorize/PowerPC/interleave_IC.ll

5

Right, I guess it involves guessing what the types and operators do. I think updating the IR to use more descriptive names rather than tmp* can also go a long why to make things easier to follow.

55

sure, unfortunately the reduction tools are not perfect. Still, ideally the test would be as small as necessary to illustrate the problem. Otherwise it will potentially become a burden when making further changes. There are only a few memory accesses in the test and it should be possible to update them to use regular types.

[fhahn]

In D81416#2231013, @fhahn wrote:

In D81416#2230857, @AaronLiu wrote:

In D81416#2230628, @fhahn wrote:

Just to double check, wouldn't it be sufficient if loop-unroll would unroll the loop? Or is this not happening? It seems like loop-unroll would unroll the loop in the test-case.

It would unroll the loop in the testcase, but it will not break dependence and expose ILP, will not help performance, and actually unroll hurt performance in this case.

I didn't took a very close look, but wouldnt unrolling generate similar code as interleaving, modulo different order of instructions, but with similar compute instructions trees?

But I think unrolling with runtime trip counts can generate a bit more overhead around the loop than interleaving in this case, so interleaving should be better in that case.

[AaronLiu]

llvm/test/Transforms/LoopVectorize/PowerPC/interleave_IC.ll

5

In order not to expose the code, it is required to strip instnamer which produced the temp names.

55

Agree, the reduction tools are not perfect. We tried very hard to reduce the testcase, and this is probably the smallest testcase that we can reduce to. It is not easy to come up with a testcase purely from imagination that use only a few memory accesses which can satisfy constraints such as should be able to legally vectorized by LV and at the same time too expensive to be vectorized and refused by the cost model, and the trip count should be compile time unknown and relatively small in run time.

[AaronLiu]

In D81416#2231013, @fhahn wrote:

In D81416#2230857, @AaronLiu wrote:

In D81416#2230628, @fhahn wrote:

Just to double check, wouldn't it be sufficient if loop-unroll would unroll the loop? Or is this not happening? It seems like loop-unroll would unroll the loop in the test-case.

It would unroll the loop in the testcase, but it will not break dependence and expose ILP, will not help performance, and actually unroll hurt performance in this case.

I didn't took a very close look, but wouldnt unrolling generate similar code as interleaving, modulo different order of instructions, but with similar compute instructions trees?

Also, it seems like the loop already gets interleaved on current trunk (With IC=2) and this patch makes it more aggressive. Might be good to describe how the IC gets boosted by this option.

Correct, not like unroll, interleaving changes the order of reduction instructions and expose ILP.
Also you are right, the loop already gets interleaved on current trunk (With IC=2) and this patch makes it more aggressive but not that aggressive as explained in the code.

[AaronLiu]

In D81416#2231041, @fhahn wrote:

In D81416#2231013, @fhahn wrote:

In D81416#2230857, @AaronLiu wrote:

In D81416#2230628, @fhahn wrote:

Just to double check, wouldn't it be sufficient if loop-unroll would unroll the loop? Or is this not happening? It seems like loop-unroll would unroll the loop in the test-case.

It would unroll the loop in the testcase, but it will not break dependence and expose ILP, will not help performance, and actually unroll hurt performance in this case.

I didn't took a very close look, but wouldnt unrolling generate similar code as interleaving, modulo different order of instructions, but with similar compute instructions trees?

But I think unrolling with runtime trip counts can generate a bit more overhead around the loop than interleaving in this case, so interleaving should be better in that case.

Totally agree!

[fhahn]

llvm/test/Transforms/LoopVectorize/PowerPC/interleave_IC.ll

55

I was not suggesting to come up with a test case from scratch, I was suggesting to inspect the reduced test case to check if there are unnecessary bits, like the types.

If you look at the defined types, they are only used in the entry block and it should be possible to replace them with something like

define dso_local void @test(i32*** %arg, double** %arg1) align 2 {
bb:
  %tpm15 = load i32**, i32*** %arg, align 8
  %tpm19 = load double*, double** %arg1, align 8
  br label %bb22

Similarly, instead of using null as base pointer for GEPs and undef as index, it should be possible to use either a global or a pointe argument as base and remove the UB from the test case.

[AaronLiu]

Address review comments.

[AaronLiu]

Rebase to the latest master.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

cl::desc("Enable the use of the block frequency analysis to access PGO "
              "aggressive in hot regions."));
 
 // Runtime interleave loops for load/store throughput.
 static cl::opt<bool> EnableLoadStoreRuntimeInterleave(
     "enable-loadstore-runtime-interleave", cl::init(true), cl::Hidden,
     cl::desc(
         "Enable runtime interleaving until load/store ports are saturated"));
 
+/// Interleave small loops with scalar reductions.
+static cl::opt<bool> InterleaveSmallLoopScalarReduction(
+    "interleave-small-loop-scalar-reduction", cl::init(false), cl::Hidden,
+    cl::desc("Enable interleaving for loops with small iteration counts that "
+             "contain scalar reductions to expose ILP."));
+
 /// The number of stores in a loop that are allowed to need predication.
 static cl::opt<unsigned> NumberOfStoresToPredicate(
     "vectorize-num-stores-pred", cl::init(1), cl::Hidden,
     cl::desc("Max number of stores to be predicated behind an if."));
 
 static cl::opt<bool> EnableIndVarRegisterHeur(
     "enable-ind-var-reg-heur", cl::init(true), cl::Hidden,
     cl::desc("Count the induction variable only once when interleaving"));
unsigned LoopVectorizationCostModel::selectInterleaveCount(unsigned VF,
 
   if (!isScalarEpilogueAllowed())
     return 1;
 
   // We used the distance for the interleave count.
   if (Legal->getMaxSafeDepDistBytes() != -1U)
     return 1;
 
-  // Do not interleave loops with a relatively small known or estimated trip
-  // count.
   auto BestKnownTC = getSmallBestKnownTC(*PSE.getSE(), TheLoop);
-  if (BestKnownTC && *BestKnownTC < TinyTripCountInterleaveThreshold)
+  const bool HasReductions = !Legal->getReductionVars().empty();
+  // Do not interleave loops with a relatively small known or estimated trip
+  // count. But we will interleave when InterleaveSmallLoopScalarReduction is
+  // enabled, and the code has scalar reductions(HasReductions && VF = 1),
+  // because with the above conditions interleaving can expose ILP and break
+  // cross iteration dependences for reductions.
+  if (BestKnownTC && (*BestKnownTC < TinyTripCountInterleaveThreshold) &&
+      !(InterleaveSmallLoopScalarReduction && HasReductions && VF == 1))
     return 1;
 
   RegisterUsage R = calculateRegisterUsage({VF})[0];
   // We divide by these constants so assume that we have at least one
   // instruction that uses at least one register.
   for (auto& pair : R.MaxLocalUsers) {
     pair.second = std::max(pair.second, 1U);
   }
unsigned LoopVectorizationCostModel::selectInterleaveCount(unsigned VF,
   // that the target and trip count allows.
   if (IC > MaxInterleaveCount)
     IC = MaxInterleaveCount;
   else if (IC < 1)
     IC = 1;
 
   // Interleave if we vectorized this loop and there is a reduction that could
   // benefit from interleaving.
-  if (VF > 1 && !Legal->getReductionVars().empty()) {
+  if (VF > 1 && HasReductions) {
     LLVM_DEBUG(dbgs() << "LV: Interleaving because of reductions.\n");
     return IC;
   }
 
   // Note that if we've already vectorized the loop we will have done the
   // runtime check and so interleaving won't require further checks.
   bool InterleavingRequiresRuntimePointerCheck =
       (VF == 1 && Legal->getRuntimePointerChecking()->Need);
 
   // We want to interleave small loops in order to reduce the loop overhead and
   // potentially expose ILP opportunities.
-  LLVM_DEBUG(dbgs() << "LV: Loop cost is " << LoopCost << '\n');
+  LLVM_DEBUG(dbgs() << "LV: Loop cost is " << LoopCost << '\n'
+                    << "LV: IC is " << IC << '\n'
+                    << "LV: VF is " << VF << '\n');
+  const bool AggressivelyInterleaveReductions =
+      TTI.enableAggressiveInterleaving(HasReductions);
   if (!InterleavingRequiresRuntimePointerCheck && LoopCost < SmallLoopCost) {
     // We assume that the cost overhead is 1 and we use the cost model
     // to estimate the cost of the loop and interleave until the cost of the
     // loop overhead is about 5% of the cost of the loop.
     unsigned SmallIC =
         std::min(IC, (unsigned)PowerOf2Floor(SmallLoopCost / LoopCost));
 
     // Interleave until store/load ports (estimated by max interleave count) are
     // saturated.
     unsigned NumStores = Legal->getNumStores();
     unsigned NumLoads = Legal->getNumLoads();
     unsigned StoresIC = IC / (NumStores ? NumStores : 1);
     unsigned LoadsIC = IC / (NumLoads ? NumLoads : 1);
 
     // If we have a scalar reduction (vector reductions are already dealt with
     // by this point), we can increase the critical path length if the loop
     // we're interleaving is inside another loop. Limit, by default to 2, so the
     // critical path only gets increased by one reduction operation.
-    if (!Legal->getReductionVars().empty() && TheLoop->getLoopDepth() > 1) {
+    if (HasReductions && TheLoop->getLoopDepth() > 1) {
       unsigned F = static_cast<unsigned>(MaxNestedScalarReductionIC);
       SmallIC = std::min(SmallIC, F);
       StoresIC = std::min(StoresIC, F);
       LoadsIC = std::min(LoadsIC, F);
     }
 
     if (EnableLoadStoreRuntimeInterleave &&
         std::max(StoresIC, LoadsIC) > SmallIC) {
       LLVM_DEBUG(
           dbgs() << "LV: Interleaving to saturate store or load ports.\n");
       return std::max(StoresIC, LoadsIC);
     }
 
+    // If there are scalar reductions and TTI has enabled aggressive
+    // interleaving for reductions, we will interleave to expose ILP.
+    if (InterleaveSmallLoopScalarReduction && VF == 1 &&
+        AggressivelyInterleaveReductions) {
+      LLVM_DEBUG(dbgs() << "LV: Interleaving to expose ILP.\n");
+      // Interleave no less than SmallIC but not as aggressive as the normal IC
+      // to satisfy the rare situation when resources are too limited.
+      return std::max(IC / 2, SmallIC);
+    } else {
       LLVM_DEBUG(dbgs() << "LV: Interleaving to reduce branch cost.\n");
       return SmallIC;
     }
+  }
 
   // Interleave if this is a large loop (small loops are already dealt with by
   // this point) that could benefit from interleaving.
-  bool HasReductions = !Legal->getReductionVars().empty();
-  if (TTI.enableAggressiveInterleaving(HasReductions)) {
+  if (AggressivelyInterleaveReductions) {
     LLVM_DEBUG(dbgs() << "LV: Interleaving to expose ILP.\n");
     return IC;
   }
 
   LLVM_DEBUG(dbgs() << "LV: Not Interleaving.\n");
   return 1;
 }
 

llvm/test/Transforms/LoopVectorize/PowerPC/interleave_IC.ll

+; RUN: opt < %s -loop-vectorize -S -mcpu=pwr9 -interleave-small-loop-scalar-reduction=true 2>&1 | FileCheck %s
+; RUN: opt < %s -passes='loop-vectorize' -S -mcpu=pwr9 -interleave-small-loop-scalar-reduction=true 2>&1 | FileCheck %s
+
+;void fun(Vector<double>       &MatrixB,
+;         const Vector<double> &MatrixA,
+;         const unsigned int * const start,
+;         const unsigned int * const end,
+;         const double * val) const
+;{
+;  const unsigned int N=MatrixB.size();
+;  MatrixB = MatrixA;
+;  for (unsigned int row=0; row<N; ++row)
+;  {
+;    double sum = 0;
+;    for (const unsigned int * col=start; col!=end; ++col, ++val)
+;      sum += *val * MatrixB(*col);
+;    MatrixB(row) -= sum;
+;  }
+;}
+
+; CHECK-LABEL: vector.body
+; CHECK: load double, double*
+; CHECK-NEXT: load double, double*
+; CHECK-NEXT: load double, double*
+; CHECK-NEXT: load double, double*
+
+; CHECK: fmul fast double
+; CHECK-NEXT: fmul fast double
+; CHECK-NEXT: fmul fast double
+; CHECK-NEXT: fmul fast double
+
+; CHECK: fadd fast double
+; CHECK-NEXT: fadd fast double
+; CHECK-NEXT: fadd fast double
+; CHECK-NEXT: fadd fast double
+
+target datalayout = "e-m:e-i64:64-n32:64"
+target triple = "powerpc64le-unknown-linux-gnu"
+
+%0 = type { %1, %8 }
+%1 = type { %2, i8, double, %4, %7* }
+%2 = type <{ i32 (...)**, %3, double*, i32 }>
+%3 = type { %7*, i8* }
+%4 = type { %5 }
+%5 = type { %6 }
+%6 = type { i32**, i32**, i32** }
+%7 = type <{ %8, i32, i32, i32, [4 x i8], i64, i32, [4 x i8], i64*, i32*, i8, i8, [6 x i8] }>
+%8 = type { i32 (...)**, i32, %9, %16* }
+%9 = type { %10 }
+%10 = type { %11 }
+%11 = type { %12, %14 }
+%12 = type { %13 }
+%13 = type { i8 }
+%14 = type { %15, i64 }
+%15 = type { i32, %15*, %15*, %15* }
+%16 = type { i32 (...)**, i8* }
+%17 = type { %8, i32, i32, double* }
+
+$test = comdat any
+define dso_local void @test(%0* %arg, %17* dereferenceable(88) %arg1) comdat align 2 {
+bb:
+  %tpm14 = getelementptr %0, %0* %arg, i64 0, i32 0, i32 3, i32 0, i32 0, i32 0
+  %tpm15 = load i32**, i32*** %tpm14, align 8
+  %tpm18 = getelementptr inbounds %17, %17* %arg1, i64 0, i32 3
+  %tpm19 = load double*, double** %tpm18, align 8
+  br label %bb22
+bb22:                                             ; preds = %bb33, %bb
+  %tpm26 = add i64 0, 1
+  %tpm27 = getelementptr inbounds i32, i32* null, i64 %tpm26
+  %tpm28 = getelementptr inbounds i32*, i32** %tpm15, i64 undef
+  %tpm29 = load i32*, i32** %tpm28, align 8
+  %tpm32 = getelementptr inbounds double, double* null, i64 %tpm26
+  br label %bb40
+bb33:                                             ; preds = %bb40
+  %tpm35 = getelementptr inbounds double, double* %tpm19, i64 undef
+  %tpm37 = fsub fast double 0.000000e+00, %tpm50
+  store double %tpm37, double* %tpm35, align 8
+  br label %bb22
+bb40:                                             ; preds = %bb40, %bb22
+  %tpm41 = phi i32* [ %tpm51, %bb40 ], [ %tpm27, %bb22 ]
+  %tpm42 = phi double* [ %tpm52, %bb40 ], [ %tpm32, %bb22 ]
+  %tpm43 = phi double [ %tpm50, %bb40 ], [ 0.000000e+00, %bb22 ]
+  %tpm44 = load double, double* %tpm42, align 8
+  %tpm45 = load i32, i32* %tpm41, align 4
+  %tpm46 = zext i32 %tpm45 to i64
+  %tpm47 = getelementptr inbounds double, double* %tpm19, i64 %tpm46
+  %tpm48 = load double, double* %tpm47, align 8
+  %tpm49 = fmul fast double %tpm48, %tpm44
+  %tpm50 = fadd fast double %tpm49, %tpm43
+  %tpm51 = getelementptr inbounds i32, i32* %tpm41, i64 1
+  %tpm52 = getelementptr inbounds double, double* %tpm42, i64 1
+  %tpm53 = icmp eq i32* %tpm51, %tpm29
+  br i1 %tpm53, label %bb33, label %bb40
+}