This is an archive of the discontinued LLVM Phabricator instance.

ScalarEvolution: Add URem support
AcceptedPublic

Authored by alexandre.isoard on Jun 24 2017, 11:52 AM.

Details

Summary

Add URem support to SCEV.

In LLVM IR the following code:

%r = urem <ty> %t, %b

is equivalent to:

%q = udiv <ty> %t, %b
%s = mul <ty> nuw %q, %b
%r = sub <ty> nuw %t, %q ; (t / b) * b + (t % b) = t

As UDiv, Mul and Sub are already supported by SCEV, URem can be implemented with minimal effort this way.

We implement two special cases:

  • if %b is 1, the result is always 0
  • if %b is a power-of-two, we produce a zext(trunc(%t)) instead

Diff Detail

Event Timeline

etherzhhb resigned from this revision.Jun 26 2017, 3:15 PM

This is correct, as far as I can tell... but I'd like to see an example of a loop where this is useful.

Added an additional testcase with a loop.

It is a loop iterating over the cells of a [5 x [7 x i8]] array in increasing order.

mkazantsev added inline comments.
lib/Analysis/ScalarEvolution.cpp
5782

Can we handle RHS = 1 separately and return constant 0 in this case?

lib/Analysis/ScalarEvolution.cpp
5782

That is doable, although I am not sure about the saved time as:

  • getUDivExpr detect division by 1
  • getMulExpr detect the multiplication by 1
  • getMinusSCEV detect the subtraction of equal SCEV

But it might be useful to separate the code into a getURemExpr.

efriedma added inline comments.Jun 28 2017, 11:01 AM
lib/Analysis/ScalarEvolution.cpp
5782

Yes, getURemExpr would be nice.

test/Analysis/ScalarEvolution/flattened.ll
1 ↗(On Diff #104382)

"tee /dev/fd/2" is not portable.

Not sure why you need it, anyway; -analyze output goes to stdout.

14 ↗(On Diff #104382)

CHECK-NEXT

test/Analysis/ScalarEvolution/flattened.ll
1 ↗(On Diff #104382)

Oops. That is a hack I use to print all of the stdout when the test case fail. (instead of the best matching line only)

I forgot to remove it.

14 ↗(On Diff #104382)

Indeed. I add that in the next update.

Updated testcase, outlined into a getURemExpr and added a x urem 1 shortcut.

alexandre.isoard marked 7 inline comments as done.Jun 28 2017, 11:28 AM
efriedma added inline comments.Jun 28 2017, 11:34 AM
lib/Analysis/ScalarEvolution.cpp
2957

"X urem 1 --> X"????

Fixed the short-circuit. (should be 0, not x)

efriedma accepted this revision.Jun 28 2017, 11:38 AM

LGTM with one minor comment.

lib/Analysis/ScalarEvolution.cpp
2958

Please add a test for this.

This revision is now accepted and ready to land.Jun 28 2017, 11:38 AM
lib/Analysis/ScalarEvolution.cpp
2957

End here I was thinking I revolutionized all modern cryptography.

grosser accepted this revision.Jun 29 2017, 10:53 PM

Very nice.

sanjoy accepted this revision.Jul 3 2017, 12:33 PM
sanjoy added inline comments.
test/Analysis/ScalarEvolution/flattened.ll
5 ↗(On Diff #104482)

I'd suggest adding a CHECK-LABEL: @foo( here and in the other test.

alexandre.isoard edited the summary of this revision. (Show Details)

I added handling for urem by a power-of-two so as to fix the failing test-case.

alexandre.isoard marked 3 inline comments as done.Aug 15 2017, 9:32 AM
alexandre.isoard requested review of this revision.Aug 15 2017, 9:40 AM
alexandre.isoard edited edge metadata.

Please check I didn't introduce new errors (off by one?).

Note that I did not add code to normalize zext(trunc(%a))+shl(lshr(%a)) into %a, yet.
That will be done in a future independent patch.

efriedma added inline comments.Aug 15 2017, 11:31 AM
lib/Analysis/ScalarEvolution.cpp
2962

Redundant check: zero isn't a power of two.

2968

There's a logBase2 helper on APInt.

test/Analysis/ScalarEvolution/flattened-0.ll
5

CHECK-LABEL

alexandre.isoard marked 3 inline comments as done.

Updated the test cases and simplified the power-of-two special case.

Hello, is there any modifications I didn't apply or do you have any change you would like to see?

This revision is now accepted and ready to land.Aug 31 2017, 6:41 PM
sanjoy resigned from this revision.Jan 29 2022, 5:44 PM