Page MenuHomePhabricator

[LSR] Fix wrapping bug in lsr-term-fold logic

Authored by reames on Mar 20 2023, 8:12 AM.



The existing logic was unsound, in two ways.

First, due to wrapping on the trip count computation, it could compute a value which convert a loop which exiting on iteration 256, to one which exited at 255. (With i8 trip counts.)

Second, it allowed rewriting when the trip count implies wrapping around the alternate IV. As a trivial example, it allowed rewriting an i128 exit test in terms of an i64 IV. This is obviously wrong.

Note that the test change is fairly minimal - i.e. only the targeted test - but that's only because I precommitted a change which switched the test from 32 to 64 bit pointers. For 32 bit point architectures with 32 bit primary inductions, this transform is almost always unsound to perform.

Diff Detail

Event Timeline

reames created this revision.Mar 20 2023, 8:12 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 20 2023, 8:12 AM
reames requested review of this revision.Mar 20 2023, 8:12 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 20 2023, 8:12 AM
nikic added inline comments.Mar 20 2023, 11:13 AM

Side note, but this code looks like evaluateAtIteration().


Hm, can't we do something like check the nowrap (as in <nw>) flag on the post-inc addrec here?

reames added inline comments.Mar 20 2023, 11:24 AM

I'd noticed that too, I'm just trying to fix this code one bit at a time. It also looks somewhat like LFTR's genLoopLimit and I have yet dug into the three enough to be really sure they compute the same values under all edge cases.


I think you might be on to something here. Let me give this a bit more thought and see if I can find a counter example.

reames added inline comments.Mar 20 2023, 12:07 PM

I tried this out, and on simple tests (e.g. const_tripcount for this transform), we appear to not be inferring no-self-wrap. I think we should, but it looks like we've got some inference problems here.

Mind if I go forward with the current scheme? I'd really like to get this transform into a somewhat sound state.

nikic accepted this revision.Mar 20 2023, 12:35 PM



Yeah, I'm fine with that, thanks for checking.

This revision is now accepted and ready to land.Mar 20 2023, 12:35 PM
This revision was landed with ongoing or failed builds.Mar 20 2023, 1:47 PM
This revision was automatically updated to reflect the committed changes.