Page MenuHomePhabricator

[IndVars] Use knowledge about execution on last iteration when removing checks

Authored by mkazantsev on Sep 24 2020, 3:27 AM.



If we know that some check will not be executed on the last iteration, we can use this
fact to eliminate its check.

Diff Detail

Event Timeline

mkazantsev created this revision.Sep 24 2020, 3:27 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 24 2020, 3:27 AM
mkazantsev requested review of this revision.Sep 24 2020, 3:27 AM
mkazantsev added reviewers: fhahn, lebedev.ri, sanjoy, reames.
reames requested changes to this revision.Sep 28 2020, 9:56 AM

Marking as Needs Changes purely to indicate I'm holding off on reviewing this in depth until changes this is built upon have all landed. Please refresh at that point.

Max, have you looked at SCEV->isLoopInvariantPredicate? It tries to handle some of the same reasoning. It might be useable directly here, or if not, can the logic maybe be consolidated in one place rather than two? I have not looked at this in depth yet, but that'll be the question I'm asking myself when reviewing this in detail.

This revision now requires changes to proceed.Sep 28 2020, 9:56 AM
mkazantsev planned changes to this revision.Sep 29 2020, 10:00 PM
mkazantsev updated this revision to Diff 295172.
mkazantsev added reviewers: ebrevnov, apilipenko.

Opening after underlying patches have been merged.

ebrevnov added inline comments.Oct 27 2020, 7:22 AM

I think we better avoid adding SkipLastIter parameter since we should be able to cover all cases with existing MaxIter and it just unnecessarily complicates the API.


Let's move this to the caller.


I suggest to adjust MaxIter here. It should greatly simplify the logic in this loop.

mkazantsev planned changes to this revision.Oct 28 2020, 3:03 AM
mkazantsev marked 3 inline comments as done.Oct 28 2020, 10:51 PM

Move last iter adjustment into lambda.

ebrevnov added inline comments.Oct 30 2020, 2:03 AM

Please rework the comment so it is crystal clear that we actually call OptimizeCond for both MaxIter and MaxIter -1. And the reason is implementation limitation in SCEV which is unable to prove that MaxIter-1 < MaxIter.

Tried to make the comment more clear.

ebrevnov accepted this revision.Oct 30 2020, 3:04 AM

LGTM. But let chance for others to comment. Thanks.

ebrevnov requested changes to this revision.Oct 30 2020, 3:18 AM
ebrevnov added inline comments.

NIT1: please list all captured values explicitly. Maybe capture SkipLastIter by value?
NIT2: please think of moving handling of SkipLastIter case to this lambda. In this case we will "hide" complexity from the main loop.


This lambda may be called twice with SkipLastIter equal to true for each exit. As a result MaxIter may be decremented by 2 for particular exit.

This revision now requires changes to proceed.Oct 30 2020, 3:18 AM
mkazantsev added inline comments.Nov 2 2020, 2:28 AM

As for nit 1: will do;
As for nit 2: this logic is going to grow more complex in further patch (see dependency), so, to avoid copy-paste, I'd rather keep it as is.


This cannot happen because MaxIter is local.

mkazantsev updated this revision to Diff 302232.Nov 2 2020, 2:59 AM
mkazantsev marked 3 inline comments as done.
This revision was not accepted when it landed; it landed in state Needs Review.Nov 2 2020, 10:39 PM
This revision was automatically updated to reflect the committed changes.