[SCEV] More precise trip multiples

[caojoshua]

Summary

We currently have getMinTrailingZeros(), from which we can get a SCEV's
multiple by computing 1 << MinTrailingZeroes. However, this only gets us
multiples that are a power of 2. This patch introduces a way to get max
constant multiples that are not just a power of 2. The logic is similar
to that of getMinTrailingZeros. getMinTrailingZerosImpl is replaced by
computing the max constant multiple, and counting the number of trailing
bits.

I have so far found this useful in two places:

1. Computing unsigned constant ranges. For example, if we have i8 {10,+,10}<nuw>, we know the max constant it can be is 250.

2. My original intent was to use this in getSmallConstantTripMultiples, but it has no effect right now due to change from D110587. For example, if we have backedge count (6 * %N) - 1, the trip count becomes 1 + zext((6 * %N) - 1), and we cannot say that 6 is a multiple of the SCEV. I plan to look further into this separately.

The implementation assumes the value is unsigned. It can probably be
extended to handle signed values as well.

If the code sees that a SCEV does not have <nuw>, it will fall back to
finding the max multiple that is a power of 2. Multiples that are a
power of 2 will still be a multiple even after the SCEV overflows. This
does not apply to other values.

[caojoshua]

Small code updates

[caojoshua]

Move a code comment

[nikic]

Precommit tests please.

llvm/lib/Analysis/ScalarEvolution.cpp

6325

APInt::getOneBitSet

6328

I don't think this is correct. trunc(X nuw* C) is not, in general, the same as trunc(X) nuw* trunc(C).

6378

minimum

[caojoshua]

In D141823#4055951, @nikic wrote:

Precommit tests please.

What is precommit test? I've been running llvm-lit llvm/test

llvm/lib/Analysis/ScalarEvolution.cpp

6328

Thats a good point. Need to think about this. I think we can fall back to count min trailing zeros.

[nikic]

In D141823#4056673, @caojoshua wrote:

In D141823#4055951, @nikic wrote:

Precommit tests please.

What is precommit test? I've been running llvm-lit llvm/test

Commit the new tests with baseline checks (without your patch), and then rebase on top, so it only shows diffs.

[caojoshua]

• Fix typos
• Don't assume multiples hold through truncation, unless they are a power of 2
• only show diffs for updated test outputs

[caojoshua]

In D141823#4057047, @nikic wrote:

In D141823#4056673, @caojoshua wrote:

In D141823#4055951, @nikic wrote:

Precommit tests please.

What is precommit test? I've been running llvm-lit llvm/test

Commit the new tests with baseline checks (without your patch), and then rebase on top, so it only shows diffs.

Thanks. I've done this for the newest revision. I see why this is preferable, but unless I think I'm missing something, this should be included somewhere in LLVM docs i.e. https://llvm.org/docs/CodeReview.html or https://llvm.org/docs/TestingGuide.html.

I have another question. When patches get approved, should owners squash the commits before pushing? Or push two separate commits.

[caojoshua]

ping

[nikic]

In D141823#4057780, @caojoshua wrote:

In D141823#4057047, @nikic wrote:

In D141823#4056673, @caojoshua wrote:

In D141823#4055951, @nikic wrote:

Precommit tests please.

What is precommit test? I've been running llvm-lit llvm/test

Commit the new tests with baseline checks (without your patch), and then rebase on top, so it only shows diffs.

Thanks. I've done this for the newest revision. I see why this is preferable, but unless I think I'm missing something, this should be included somewhere in LLVM docs i.e. https://llvm.org/docs/CodeReview.html or https://llvm.org/docs/TestingGuide.html.

I've put up https://reviews.llvm.org/D142441 to update the TestingGuide.

I have another question. When patches get approved, should owners squash the commits before pushing? Or push two separate commits.

It should be two separate commits. In fact, you can just land the test commit now, without waiting for the patch to be approved.

I believe this patch needs a rebase, because of some recent refactorings.

My original intent was to use this in getSmallConstantTripMultiples, but it has no effect right now due to change from D110587. For example, if we have backedge count (6 * %N) - 1, the trip count becomes 1 + zext((6 * %N) - 1), and we cannot say that 6 is a multiple of the SCEV. I plan to look further into this separately.

I wonder if it might make sense to address this first? I'm a bit worried that the only test coverage for this functionality we have right now is very indirect, by the effect the multiple has on ranges. It would be great if we could test this functionality directly based on the trip multiple.

[nikic]

Logic looks about right to me.

When I tested the original patch, there was a significant impact on compile-time: http://llvm-compile-time-tracker.com/compare.php?from=68a534e9bf69e7e5f081a515e05f1d3cb4c21761&to=8f3c56e720e64e569f930190b246e4af61be2323&stat=instructions:u But I'm not sure if it's avoidable :(

llvm/include/llvm/Analysis/ScalarEvolution.h

961

than -> then

965

Missing doc comment.

llvm/lib/Analysis/ScalarEvolution.cpp

6307

Unnecessary reference

6345–6347

6354

Unnecessary braces

6371

6380

Or use the same operands().drop_front() style as above.

8269

So, is getRawData() here supposed to be an implicit truncate? Let's not do that...

[caojoshua]

I wonder if it might make sense to address this first? I'm a bit worried that the only test coverage for this functionality we have right now is very indirect, by the effect the multiple has on ranges. It would be great if we could test this functionality directly based on the trip multiple.

This does make sense. Let me try to get this working.

When I tested the original patch, there was a significant impact on compile-time: http://llvm-compile-time-tracker.com/compare.php?from=68a534e9bf69e7e5f081a515e05f1d3cb4c21761&to=8f3c56e720e64e569f930190b246e4af61be2323&stat=instructions:u But I'm not sure if it's avoidable :(

I was not expecting those numbers. Computing multiples is very similar to GetMinTrailingZeros. The main difference I can think of is that multiples uses GreatestCommonDivisor, but I don't think it should be too expensive, and in most cases it probably just returns 1. I'll look into this as well.

[mkazantsev]

I think this needs stronger test coverage. At least I want tests for all operations (either IR tests or unittests in CPP, whatever is easier) exercising corner case scenarios, such as bit width overflow with mul.

llvm/include/llvm/Analysis/ScalarEvolution.h

971

Separate NFC?

llvm/lib/Analysis/ScalarEvolution.cpp

6309

Why zero and not APInt::getOneBitSet(BitWidth, BitWidth - 1)? Zero is not even a power of 2, how to interpret that?

6320

/*param name/* nullptr

6373

Early bail if GCD has become 1? It won't get any better anyways.

[caojoshua]

In D141823#4092531, @mkazantsev wrote:

I think this needs stronger test coverage. At least I want tests for all operations (either IR tests or unittests in CPP, whatever is easier) exercising corner case scenarios, such as bit width overflow with mul.

Agree that more test coverage is needed here. I'd like to go with nikic's suggestion to figure out the issues with trip multiples first. I think that will make testing this much easier.

llvm/include/llvm/Analysis/ScalarEvolution.h

971

You're right. I'll take this out.

[mkazantsev]

Marking as "request changes" to shrink my review list, will take a look once comments are addressed.