This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Use constant range of RHS to prove NUW on narrow IV in trip count logic
ClosedPublic

Authored by reames on Sep 8 2021, 11:10 AM.

Details

Summary

The basic idea here is that given a zero extended narrow IV, we can prove the inner IV to be NUW if we can prove there's a value the inner IV must take before overflow which must exit the loop.

This is a follow to D108651.

Diff Detail

Event Timeline

reames created this revision.Sep 8 2021, 11:10 AM
reames requested review of this revision.Sep 8 2021, 11:10 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 8 2021, 11:10 AM
efriedma added inline comments.Sep 13 2021, 3:45 PM
llvm/lib/Analysis/ScalarEvolution.cpp
11661

Why is the StrideMax == 0 special case necessary?

11665

What is APInt::getMaxValue(InnerBitWidth) - StrideMax the limit of?

I guess you're looking for the smallest possible value of AR at the step before it overflows. If that value forces the loop to exit, then the loop must exit before the overflow. A conservative way to figure that is based on the stride itself: just use the smallest value X such that X+Stride might overflow.

A comment would be helpful.

Also, I think you might be off by one here? Limit is one less than the value X I described. But maybe that cancels out somehow...

reames updated this revision to Diff 373028.Sep 16 2021, 12:11 PM

address review comment with better comments, also fixed a bug noticed in the process. I used max in two places, whereas one of them needed to be a min for the required purpose.

Planning to land the test, then rebase this.

reames updated this revision to Diff 373037.Sep 16 2021, 12:49 PM

Rebase over landed tests.

One question for reviewers - We don't currently get any value in handling non-constant strides because (due to limitations in flag inference), we basically never conclude the that step is non-zero from data flow. (We might from control flow, but that doesn't influence constant ranges.) Should I keep the complexity? Or just drop it to constant non-zero step and be done?

ping

p.s. In offline discussion, @nlewycky suggested a nice generalization of this idea in terms of invertible operations once we've proven the value being compared against is in the co-domain of the LHS. I want to land this as is, but I'm hoping to leverage that idea into a generalization both here, and in IndVarSimplify.

ping - this has been outstanding for a while and is blocking progress for me, any chance I can get someone to review?

JFYI, all of the other approaches I've mentioned in the review thread so far have not panned out. I can cover some cases with each, but not the motivating example. This patch's use of mustprogress to disprove the infinite loop case is critical. Every time I tried implementing this differently, I ended up just re-implementing this same idea without the infrastructure that SCEV already provides for this. I think this really does have to be in SCEV's trip count logic.

JFYI, all of the other approaches I've mentioned in the review thread so far have not panned out.

As often happens, taking a fresh look at something reveals another approach. I've posted https://reviews.llvm.org/D111836 which isn't really a replacement for this patch, but tackles problems in the same area, and is probably easier to review/justify.

reames updated this revision to Diff 385125.EditedNov 5 2021, 10:50 AM

Drop the must-exit logic entirely. As recently demonstrated in the indvars approach, none of the original motivating examples actually require it after we incorporate more precise range reasoning.

Add applyLoopGuards to constrain RHS, and fix an off by one bug which resulted in inprecise results at the edge. Additionally, include tests specifically focused on the edge case to demonstrate the correctness of said change.

As can now be seen by the test changes in finite-exit-comparisons.ll (the test file exercising the new indvars logic), this sometimes lets us to LFTR an exit test instead of rotating/narrowing. I've manually confirmed that we generate exit tests for all of the examples, why some still hit the rotate path will be investigated separately. (Edit: See https://bugs.llvm.org/show_bug.cgi?id=52423 for result of that investigation. Its an LFTR limitation we should fix.) I'm hoping to be able to delete that logic again entirely, but well, we'll see.

@nikic, @mkazantsev, @fhahn - Given the the must-exit logic has been removed and this is now pretty much just basic constant range reasoning, I'd greatly appreciate a review so we can get this in. After implementing the indvars approach, I'm more convinced than ever that SCEV really should just be able to compute a trip count for these loops. Everything else seems like a massive hack.

nikic accepted this revision.Nov 5 2021, 2:23 PM

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp
11659
This revision is now accepted and ready to land.Nov 5 2021, 2:23 PM