Page MenuHomePhabricator

[SCEV] Allow negative steps for LT exit count computation
Needs ReviewPublic

Authored by reames on Fri, Jun 11, 11:35 AM.

Details

Summary

This bit of code is incredibly suspicious. It allows fully unknown (but potentially negative) steps, but not steps known to be negative. The comment about scev flag inference is worrying, but also not correct to my knowledge.

At best, this might be covering up some related miscompile. However, there's no test in tree for it, the review history doesn't include obvious motivation, and the C++ example doesn't appear to give wrong results when hand translated to IR. I think it's time to remove this and see what falls out.

Diff Detail

Event Timeline

reames created this revision.Fri, Jun 11, 11:35 AM
reames requested review of this revision.Fri, Jun 11, 11:35 AM
Herald added a project: Restricted Project. · View Herald TranscriptFri, Jun 11, 11:35 AM
efriedma added inline comments.Sun, Jun 13, 6:56 PM
llvm/lib/Analysis/ScalarEvolution.cpp
11462

Does the logic here actually work correctly for step=0? It looks like we end up dividing by zero.

If we can prove the step is non-zero, loopIsFiniteByAssumption seems too aggressive; a lack of abnormal exits should be enough. We'll hit UB after a finite number of steps.

Using isKnownPositive doesn't really make sense in the unsigned case; an unsigned number can't be negative.

reames added inline comments.Mon, Jun 14, 9:54 AM
llvm/lib/Analysis/ScalarEvolution.cpp
11462

Step can't be zero, or the loop would be infinite. Though, actually, writing that, I see a latent bug here. The loop could be finite *because we took another exit*, the step of this IV could still be zero, and we could still have a divide by zero along this path.

I don't think that has anything to do with this change though.

p.s. Yes, we can infer non-zero other ways. I even have one patch out to do that right now. :)

efriedma added inline comments.Mon, Jun 14, 10:38 AM
llvm/lib/Analysis/ScalarEvolution.cpp
11462

I agree this patch makes sense, just saying it might expose other issues.

*because we took another exit*

Even if we take this exit. If the backedge-taken count is zero, the step doesn't matter.

reames added inline comments.Tue, Jun 15, 8:58 AM
llvm/lib/Analysis/ScalarEvolution.cpp
11462

Eli, I think you're missing the point slightly. For the induction step to be zero, and for this to be the sole exit, then the loop must be infinite. Since mustprogress infinite loops are undefined, any result from this function is allowed. If there's a divide by zero which causes a compiler crash, that would be bad, but literally any result is legal at that point.

efriedma added inline comments.Tue, Jun 15, 11:55 AM
llvm/lib/Analysis/ScalarEvolution.cpp
11462

If the induction step is zero, and this is the sole exit, the loop is either infinite, or has a backedge-taken count of zero. See, for example, https://godbolt.org/z/9djfj1Ycq .

reames added inline comments.Tue, Jun 15, 12:15 PM
llvm/lib/Analysis/ScalarEvolution.cpp
11462

Gah, yeah, you're correct. No idea why I didn't see that the first time.