This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Match 'zext (trunc A to iB) to iY' as URem.
ClosedPublic

Authored by fhahn on Oct 20 2020, 1:41 PM.

Details

Summary

URem operations with constant power-of-2 second operands are modeled as
such. This patch on its own has very little impact (e.g. no changes in
CodeGen for MultiSource/SPEC2000/SPEC2006 on X86 -O3 -flto), but I'll
soon post follow-up patches that make use of it to more accurately
determine the trip multiple.

Diff Detail

Event Timeline

fhahn created this revision.Oct 20 2020, 1:41 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 20 2020, 1:41 PM
fhahn requested review of this revision.Oct 20 2020, 1:41 PM

I would expect that you should be able to showcase the effect with opt -analyze -scalar-evolution-based test:
https://godbolt.org/z/xddz8d (because there's zext(A % B) --> zext(A) % zext(B) matchURem()-driven fold)

llvm/lib/Analysis/ScalarEvolution.cpp
12693

What if Expr isn't an zext itself, but it is used by zext (which is the case in the single user of this method)?

12696–12697

What if we had zext(zext(trunc)), so we end up with a wider type than A was?

mkazantsev added inline comments.Oct 23 2020, 3:37 AM
llvm/lib/Analysis/ScalarEvolution.cpp
12703

I think getPowerOf2 would be a useful utility function in SCEV. Consider factoring out (maybe as separate patch).

12704

1u << X will overflowan become zero if X > 32. Consider using APInt.

llvm/unittests/Analysis/ScalarEvolutionTest.cpp
67

static?

mkazantsev added inline comments.Oct 23 2020, 3:39 AM
llvm/unittests/Analysis/ScalarEvolutionTest.cpp
1334

Could you please make a 64-bit version of this test to catch bug with 1u << size if it happens?

fhahn updated this revision to Diff 300551.Oct 25 2020, 12:42 PM

Address comments: use APInt instead unsigned for shift, handle different zext sizes, add test with divisor > 1 << 32.

Thanks!

I would expect that you should be able to showcase the effect with opt -analyze -scalar-evolution-based test:
https://godbolt.org/z/xddz8d (because there's zext(A % B) --> zext(A) % zext(B) matchURem()-driven fold)

Not sure if that's possible, because the expression is already in the form zext (trunc ... to iX) to iY and I think if there was an outer zext, it would be already folded into the inner zext.

llvm/lib/Analysis/ScalarEvolution.cpp
12693

Hm, I not sure what to do about that case. I think we need to zext (trunc) combo to match that.

12696–12697

Originally the code had a check to ensure the type of the starting expression matched the type of A, but I now updated things to do a ZExt on demand to make A match the type of Expr.

12704

Thanks, updated to use APInt and added a test where the LHS is > 1 << 32.

fhahn updated this revision to Diff 300552.Oct 25 2020, 12:49 PM

make matchURem static in test class

mkazantsev accepted this revision.Oct 25 2020, 9:14 PM

Looks good, thanks!

llvm/lib/Analysis/ScalarEvolution.cpp
12698

{} not needed

12699

if (auto *Trunc = ...

This revision is now accepted and ready to land.Oct 25 2020, 9:14 PM
This revision was landed with ongoing or failed builds.Oct 29 2020, 3:48 AM
This revision was automatically updated to reflect the committed changes.
fhahn added a comment.Oct 29 2020, 3:48 AM

Thanks! Adjusted the comments in the committed version