Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Phabricator shutdown timeline

[SCEV] Apply conditions involving constants first in applyLoopGuards.
Needs RevisionPublic

Authored by fhahn on May 26 2022, 2:30 PM.



In some cases the order conditions are applied in can pessimize results.
In general, applying conditions with constant operands should lead to
better results. I think ideally we would apply conditions with operands
that are not involved in any other condition first, but processing
conditions with constants should be a good start.

Alternatively we could re-write all collected expressions after
collecting them. But that's likely more expensive.

Depends on D126460.

Fixes #55645.

Diff Detail

Event Timeline

fhahn created this revision.May 26 2022, 2:30 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 26 2022, 2:30 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
fhahn requested review of this revision.May 26 2022, 2:30 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 26 2022, 2:30 PM
nikic added inline comments.May 26 2022, 3:11 PM

I don't understand this comparison function. If A is constant and B is not, this returns that A is smaller than B. If B is constant and A is not then ... this also returns that A is smaller than B?

fhahn planned changes to this revision.May 27 2022, 3:23 AM

Thanks for taking a look! Unfortunately this only worked by accident and I missed that there aren't any tests with the conditions in reverse order.

I think the real issue here is that we need to apply the conditions that constraint the value range first and the rewriting as multiple last.

fhahn updated this revision to Diff 432523.May 27 2022, 4:52 AM

Update sort order to apply conditions that constraint ranges using max/min (predicates != EQ & != NE).

This ensures we rewrite conditons involving URem checks last, which can lead to better results.

alonkom added inline comments.

Even with this sorting won't we lose information about the min/max values of the value?
For example if we know (tc > 0) and (tc % 8 == 0) and we process (tc % 8 == 0) last, AFAIU the SCEV expression will be overridden to (tc / 8) * 8 and we'll lose the fact that the trip count is also positive.

nikic added inline comments.May 30 2022, 3:56 AM

There may be range comparisons using eq/ne as well, with != 0 probably being the only important one. Possibly we should not be collecting Terms but already classified conditions (i.e. either known factor or known range limit)?

mkazantsev added inline comments.Sep 26 2022, 2:56 AM

Use isRelational

mkazantsev requested changes to this revision.Dec 7 2022, 12:04 AM

Marking as "request changes" just to reduce my list. Feel free to update when the comments are addressed!


Precommit test?

This revision now requires changes to proceed.Dec 7 2022, 12:04 AM