Page MenuHomePhabricator

[SCEV] Cache wrap facts for positive IVs w/LT exits
Changes PlannedPublic

Authored by reames on Mon, Jun 7, 2:42 PM.

Details

Reviewers
nikic
Summary

A skeptical review here is appreciated. I believe this is safe, but overflow code generally makes my brain hurt.

p.s. For step=1, we can also cache the same fact. I am deliberately not doing so to minimize test diffs in this change.

Diff Detail

Event Timeline

reames created this revision.Mon, Jun 7, 2:42 PM
reames requested review of this revision.Mon, Jun 7, 2:42 PM
Herald added a project: Restricted Project. · View Herald TranscriptMon, Jun 7, 2:42 PM
nikic added inline comments.Tue, Jun 8, 9:50 AM
llvm/lib/Analysis/ScalarEvolution.cpp
11518

If we consider the canIVOverflowOnLT() case, the only thin this guarantees is that RHS + Stride - 1 does not overflow, it doesn't make a direct statement about the addrec.

If the loop exits before reaching this exit (for simplicity: abnormal exit on first iteration), then I don't think we can really make any statement about the nowrap behavior of the addrec.

nikic requested changes to this revision.Wed, Jun 9, 9:48 AM

Per above comment

This revision now requires changes to proceed.Wed, Jun 9, 9:48 AM
reames added inline comments.Wed, Jun 9, 2:08 PM
llvm/lib/Analysis/ScalarEvolution.cpp
11518

Right, but we know that the result of the expression being considered must reach a conditional branch, and that conditional branch must dominate the latch. Given that, we know that if this condition did overflow, then the iteration of the loop would be UB unless we exit from some other exit before this one. In either case, that seems to give an upper bound on the trip count which does imply that AddRec can't overflow in a well defined loop doesn't it?

nikic accepted this revision.Wed, Jun 9, 2:58 PM

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp
11518

Ah yes, you're right. It does still provide an upper bound. I got this mixed up with concerns from D101722. I've played around with some examples and convinced myself that this is correct...

This revision is now accepted and ready to land.Wed, Jun 9, 2:58 PM
nikic added inline comments.Wed, Jun 9, 3:16 PM
llvm/lib/Analysis/ScalarEvolution.cpp
11518

After thinking about it some more, there is still one case that may be problematic. What if the addrec starts out above the RHS (meaning the loop exits after the first iteration). I'm thinking something like this:

; Assume %start is larger than 200.
define void @test(i8 %start) {
entry:
  br label %loop

loop:
  %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
  %iv.next = add i8 %iv, 2
  call void @use_and_exit(i8 %iv.next)
  %cond = icmp ult i8 %iv.next, 200 
  br i1 %cond, label %loop, label %exit

exit:
  ret void
}

declare void @use_and_exit(i8)

I believe your change would now infer that {2 + %start,+,2} is <nuw>, but if @use_and_exit() exits beforehand that is not necessarily a given.

reames planned changes to this revision.Fri, Jun 11, 10:30 AM

Change appears to be wrong as written, discussing why before adjusting.

llvm/lib/Analysis/ScalarEvolution.cpp
11518

I think you're correct, and that this change is wrong. But I think the reasoning on why is bit different than your phrasing. Let me try to describe why, and you can tell me if this matches what you're thinking.

In order for the flags computed by canIVOverflowOnLT to hold for the IV in general, we need to know that a poison value for the comparison must reach a branch (or other full UB use). If after poison has been generated, but before the undefined use, the loop exits, the overflow flag might not hold. This can happen when either a) there's an abnormal or normal exit before this one which isn't control dependent on this IV. If that happens, users of the IV might see a wrapped value even though we've proved this exit can't be taken after overflow.

(Aside, this is specific to the canIVOverflowOnLT path. I believe the isUBOnWrap path is sufficiently conservative to not have this issue.)

If the IV starts at a value above the RHS, the loop may exit on the first iteration. But, and this is the key bit, assuming the exit taken is control dependent on the IV, we can still infer the nowrap flag. Why? There's two addrecs here. There's IV = {start, +, 2}, and IV.next = {start + 2, +, 2}. The exit test is in terms of the later. Given that, the first iteration of %iv.next can't wrap, or we wouldn't be in the exit on first iteration case. Hm, I do notice this argument is specific to the step and rhs values here. If rhs was say, 0, I think this argument collapses. Maybe we have another latent issue here?

nikic added inline comments.Fri, Jun 11, 11:36 AM
llvm/lib/Analysis/ScalarEvolution.cpp
11518

Sorry for the back and forth here. I just realized something important: We're talking about nowrap flags on addrecs here, not on the incrementing add itself. And nowrap flags on addrecs are directly tied to the trip count. An addrec for a loop with zero iterations is always nuw/nsw. So maybe there's no problem here after all?

reames added inline comments.Fri, Jun 11, 12:45 PM
llvm/lib/Analysis/ScalarEvolution.cpp
11518

Oh, I see your point, but let me rephrase again.

For a loop with exits on the first iteration, the exiting value of the addrec is the start value. For a post-inc IV, that start value is the start of the pre-inc IV + the step. The computation of that start value might overflow, but there's no further application of the step, and thus the *addrec* is trivially nsw/nuw.

Though, unless I'm missing something, this only addresses the second part of my last response. I believe the poison not reaching branch instruction issue still exists, and isn't iteration 1 specific. I believe that could happen on *any* iteration which happens to be the final iteration, but not exiting through *this* exit.

reames added inline comments.Fri, Jun 11, 12:47 PM
llvm/lib/Analysis/ScalarEvolution.cpp
11518

Sorry for the back and forth here.

Also, just wanted to explicitly say please don't be sorry, this back and forth is really helpful for me in figuring out exactly what's going on with this (insanely complicated) set of code. I really appreciate the discussion.

nikic added inline comments.Fri, Jun 11, 2:04 PM
llvm/lib/Analysis/ScalarEvolution.cpp
11518

Though, unless I'm missing something, this only addresses the second part of my last response. I believe the poison not reaching branch instruction issue still exists, and isn't iteration 1 specific. I believe that could happen on *any* iteration which happens to be the final iteration, but not exiting through *this* exit.

I think it should cover that case as well. Nowrap flags on addrecs don't make a statement about overflow behavior on the last loop iteration, so it should be okay even if there is a prior exit (on the last iteration).