Page MenuHomePhabricator

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

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.