Page MenuHomePhabricator

[SimplifyIndvar] Replace the srem used by IV if we can prove both of its operands are non-negative
ClosedPublic

Authored by etherzhhb on Sep 19 2017, 7:17 PM.

Details

Summary

Since now SCEV can handle 'urem', an 'urem' is a better canonical form than an 'srem' because it has well-defined behavior

This is a follow up of D34598

Diff Detail

Repository
rL LLVM

Event Timeline

etherzhhb created this revision.Sep 19 2017, 7:17 PM
sanjoy requested changes to this revision.Sep 19 2017, 8:55 PM
sanjoy added inline comments.
lib/Transforms/Utils/SimplifyIndVar.cpp
306 ↗(On Diff #115954)

Instead of creating another function this way, I thin a cleaner design would be to create a couple of small functions for the "i % n --> i if i is in [0,n).", "i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n)." cases and this case, and call them from SimplifyIndvar::eliminateIVRemainder.

This revision now requires changes to proceed.Sep 19 2017, 8:55 PM
etherzhhb edited edge metadata.

Update patch to address reviewer's request

etherzhhb marked an inline comment as done.Sep 20 2017, 12:35 AM

Update comment

Update comment

sanjoy requested changes to this revision.Sep 20 2017, 10:16 AM

This is looking close; only some nitpicky comments inline

lib/Transforms/Utils/SimplifyIndVar.cpp
340 ↗(On Diff #115974)

Can we share this work amongst the three helpers? Something like:

  • Pass in NumeratorNonNegative and DenominatorNonNegative bools to this function, and only NumeratorNonNegative to the other two.
  • Compute these bools in simplifyIVRemainder as needed
373 ↗(On Diff #115974)

This specific function doesn't add much IMHO -- I'd just inline it out.

402 ↗(On Diff #115974)

Let's keep calling these N and D -- perhaps you could differentiate the Value * and the SCEV * by a suffix (N vs NValue)?

410 ↗(On Diff #115974)

s/By/With/ in the names

417 ↗(On Diff #115974)

Going by the other function names, how about calling this replaceSRemWithURem?

This revision now requires changes to proceed.Sep 20 2017, 10:16 AM
etherzhhb added inline comments.Sep 20 2017, 10:51 AM
lib/Transforms/Utils/SimplifyIndVar.cpp
340 ↗(On Diff #115974)

Sure, I will do this. I think this whole simplifyIVRemainder will not process if NumeratorNonNegative is false, is that correct?

sanjoy added inline comments.Sep 20 2017, 10:59 AM
lib/Transforms/Utils/SimplifyIndVar.cpp
340 ↗(On Diff #115974)

Yes, but I think it may be cleaner to pass it in to the helpers; that way the dependency of the transform is clearer. And just returning from the helpers if it isn't set seems fine.

etherzhhb updated this revision to Diff 116137.Sep 20 2017, 8:38 PM
etherzhhb edited edge metadata.

update patch based on the comments

etherzhhb marked 7 inline comments as done.Sep 20 2017, 8:38 PM
etherzhhb updated this revision to Diff 116189.Sep 21 2017, 7:52 AM

Update comment

sanjoy accepted this revision.Sep 23 2017, 2:39 PM

LGTM with comments addressed.

lib/Transforms/Utils/SimplifyIndVar.cpp
344 ↗(On Diff #116189)

I'd prefer to give this a more specific name -- how about "iv.rem"? The exact name does not matter as long as folks can grep the symbol name in LLVM and find this file.

366 ↗(On Diff #116189)

Minor thing: I'd have written this as:

const SCEV *N = SE->getSCEVAtScope(SE->getSCEV(NValue), ICmpLoop);

// Later, after the check on !UsedAsNumerator && !IsSigned
const SCEV *D = SE->getSCEVAtScope(SE->getSCEV(DValue), ICmpLoop);
401 ↗(On Diff #116189)

I'm not sure if this is safe -- it seems like Changed is piped all the way through to IndVarSimplify's return value to the pass manager (if nothing changed, it will tell the PM that all analyses are preserved).

Even if this is safe, I suspect you'll need to do Changed |= UsedAsNumerator. In this case, please add a one liner on why this is safe.

This revision is now accepted and ready to land.Sep 23 2017, 2:39 PM
etherzhhb added inline comments.Sep 25 2017, 8:58 AM
lib/Transforms/Utils/SimplifyIndVar.cpp
401 ↗(On Diff #116189)

Thanks for you reminder on this, I have a feeling that this may not be safe as well. Let me have a closer look

etherzhhb updated this revision to Diff 116565.Sep 25 2017, 9:29 AM

address comments from the reviewer

etherzhhb marked 4 inline comments as done.Sep 25 2017, 9:29 AM
This revision was automatically updated to reflect the committed changes.