Page MenuHomePhabricator

[SCEV] Assumption context for GetMinTrailingZeros
Needs RevisionPublic

Authored by gilr on Jan 5 2021, 7:34 AM.

Details

Summary

Let GetMinTrailingZeros() make better use of assumptions by taking an optional context instruction.
The context defaults to null, keeping the API backward-compatible. If a context is provided, the method will neither use nor update the trailing zeros cache.
The context argument is then used by the loop vectorizer and by SCEV::getSmallConstantTripMultiple() to set the context at their given loop.

Diff Detail

Event Timeline

gilr created this revision.Jan 5 2021, 7:34 AM
gilr requested review of this revision.Jan 5 2021, 7:34 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 5 2021, 7:34 AM
gilr added a subscriber: Ayal.Jan 5 2021, 8:20 AM
fhahn added inline comments.Jan 5 2021, 8:53 AM
llvm/lib/Analysis/ScalarEvolution.cpp
6893

Why use the header's terminator here?

llvm/test/Transforms/LoopUnroll/runtime-unroll-assume-no-remainder.ll
8

I think it would be good to combine a few of those related tests in a single file :)

gilr added inline comments.Jan 6 2021, 12:56 AM
llvm/lib/Analysis/ScalarEvolution.cpp
6893

No reason, actually. Will change to first instruction in the header.

llvm/test/Transforms/LoopUnroll/runtime-unroll-assume-no-remainder.ll
8

Ah, good catch on LV (but I better do this separately to keep this patch's changes clear).
(Unroller tests running roughly the same opt command seem to have manual CHECK lines. Not sure how well it would mix with automated CHECKs that need to be updated from time to time)

gilr updated this revision to Diff 314818.Jan 6 2021, 1:01 AM

Addressed comments.

gilr updated this revision to Diff 315063.Jan 7 2021, 12:36 AM

Rebased on top of 7ddbe0cb905ec62d37b284a2e8daf54887a35f94 (merge ..-assume-divisible-TC.ll into ..-divisible-TC.ll)

I would expect that the SCEV change could be testable with just the scev itselfs (-analyze -scalar-evolution), is it not?

llvm/lib/Analysis/ScalarEvolution.cpp
5611–5615

Doesn't this defy the point of the cache?
I think MinTrailingZerosCache's key should be changed to be a std::pair<SCEV*,CxtI*>

fhahn added a comment.Jan 25 2021, 3:33 AM

I think the fix makes sense in isolation, but I am wondering if we could generalize this to automatically apply in more cases. Would it be possible to 'apply' the information from the loop guard directly to the SCEV expression? Like we do for some conditions already: https://github.com/llvm/llvm-project/blob/master/llvm/lib/Analysis/ScalarEvolution.cpp#L13241 ?

gilr added a comment.Jan 25 2021, 4:27 PM

I would expect that the SCEV change could be testable with just the scev itselfs (-analyze -scalar-evolution), is it not?

Right, will add a unit test for this API.

I think the fix makes sense in isolation, but I am wondering if we could generalize this to automatically apply in more cases. Would it be possible to 'apply' the information from the loop guard directly to the SCEV expression? Like we do for some conditions already: https://github.com/llvm/llvm-project/blob/master/llvm/lib/Analysis/ScalarEvolution.cpp#L13241 ?

Will take a look at that. Thanks!

llvm/lib/Analysis/ScalarEvolution.cpp
5611–5615

Doesn't this defy the point of the cache?

This API seems to be used extensively. Since (for now) only the unroller and vectorizer would be providing a non-null context I wasn't sure caching those calls was worth the added space/time of extending the key.

I think MinTrailingZerosCache's key should be changed to be a std::pair<SCEV*,CxtI*>

Will do.

gilr added a comment.Wed, Jan 27, 6:05 AM

Trying to apply Florian's suggestion in D95521 (only for powers of 2 as a first step). This handles the power-of-two case added by PR47904.

lebedev.ri requested changes to this revision.Wed, Jan 27, 6:25 AM
lebedev.ri added inline comments.
llvm/lib/Analysis/ScalarEvolution.cpp
5611–5615

Thinking about this, it's not even so much that it's pessimising the cache, it's actually straight-up upsafe to do.
E.g. given

x = y
if(!(x & 0b1))
  f(x); // x has at least one trailing bit

if we first ask GetMinTrailingZeros(X, "f(x)"), we'll get 1,
and if we then ask GetMinTrailingZeros(X, "x = y"), we'll again get 1, which is obviously not correct.

This revision now requires changes to proceed.Wed, Jan 27, 6:25 AM
gilr added inline comments.Wed, Jan 27, 8:08 AM
llvm/lib/Analysis/ScalarEvolution.cpp
5611–5615

Not sure I follow. If a context is provided the cache is neither queried nor updated, so the call GetMinTrailingZeros(X, "f(x)") shouldn't affect a later GetMinTrailingZeros(X, "x = y") call (or a later GetMinTrailingZeros(X) call). Am I missing something?

lebedev.ri added inline comments.Wed, Jan 27, 8:24 AM
llvm/lib/Analysis/ScalarEvolution.cpp
5611–5615

Err, nope.