[LLVMdev] Deriving undefined behavior from nsw/inbounds/poison for scalar evolution

[Andrew Trick]

> On Jun 30, 2015, at 4:30 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> 
> ----- Original Message -----
>> From: "Bjarke Roune" <broune at google.com>
>> To: llvmdev at cs.uiuc.edu
>> Sent: Friday, June 26, 2015 6:01:35 PM
>> Subject: [LLVMdev] Deriving undefined behavior from nsw/inbounds/poison for	scalar evolution
>> 
>> 
>> 
>> 
>> *** Summary
>> I'd like to propose (and implement) functionality in LLVM to
>> determine when a poison value from an instruction is guaranteed to
>> produce undefined behavior. I want to use that to improve handling
>> of nsw, inbounds etc. flags in scalar evolution and LSR. I imagine
>> that there would be other uses for it. I'd like feedback on this
>> idea before I proceed with it.
>> 
>> 
>> 
>> 
>> *** Details
>> Poison values do produce undefined behavior if the poison becomes
>> externally observable. A load or store to a poison address value is
>> externally observable and I'd like to use that in a simple analysis
>> pass to derive guarantees that certain overflows would produce
>> undefined behavior, not just poison.
>> 
>> 
>> Scalar evolution (and hence LSR) cannot currently make much use of
>> the nsw and similar flags on instructions. That is because two
>> instructions can map to the same scev even if one instruction has
>> the nsw flag and the other one does not. If we applied the nsw flag
>> to the scev, the scev for the instruction without the nsw flag would
>> then incorrectly have the nsw flag.
>> 
>> 
>> Scalar evolution would be able to use the nsw flag from an
>> instruction for recurrences when the loop header dominates the
>> entire loop, the instruction with nsw post-dominates the loop header
>> and undefined behavior is guaranteed on wrap via the poison value
>> analysis pass that I'd like to write.
>> 
> 
> My understanding is that SCEV currently only uses no-wrap flags that it can independently prove, in part, because SCEVExpander might be used to materialize the expressions outside of the loop body (in the pre-header, for example). Andy, can you comment on the constraints here?

I was hesitant to jump in for fear of rehashing all of the poison/nsw issues and failing to do it justice. But I'll try to give a quick summary:

The IR optimizer is free to transform operations in any way that preserves observable side effects. So when no-wrap flags appear on a side-effect free operation what does it mean? I say that those flags only have meaning with respect to that operation's transitive uses that induce side effects (hence poison).

Now the idea behind SCEV is to provide an abstract representation of an expression independent of any constraints that do not effect the value of the expression. That allows expressions to be canonicalized and gracefully reduced. Value equivalence becomes expression identity.

The poses a conundrum whenever we have multiple IR values with expression equivalence but different constraints. The users of one IR value may anticipate nsw behavior, while the users of another IR value do not. There's no guarantee of control equivalence across all these users, so the same constraints don't need to hold across them.

The current compromise is to allow nsw to creep into SCEV only in the case of recurrences. The primary need for SCEV is for induction variable analysis, so we mainly care about the presence of flags on recurrences. In order to optimize as expected based on C/C++ undefined behavior, SCEV has to play loose with the poison rules as Sanjoy pointed out. Essentially, we assume that an IR value marked nsw has an observable use if it is live across loop iterations. Even if this is not strictly true in IR, it's almost certain that undefined behavior semantics would still cover us in that case.

I think that Sanjoy's work on inferring nsw on SCEV recurrences from constraints present in the IR is great and avoids the issue above (if you prove nsw for an expression within a loop, the def-use chain no longer matters).

I also like what Adam did recently in relying on SCEV nsw on a recurrence but analyzing address expressions at IR level.

In general, I like progress in the direction of strengthening LLVM's analysis of value ranges along with adding metadata and explicit markers like llvm.assume, rather than relying on poison and undefined behevior, which I view as an unfortunate legacy.

Andy

>> 
>> 
>> What do you think? Do we already have something similar to this?
>> 
>> 
>> 
>> Bjarke
>> 
>> 
>> 
>> 
>> 
>> 
>> 
>> *** PS: What got me thinking about this:
>> My immediate motivation is that I'd like LSR to be able to create
>> induction variables for expressions like &ptr[i + offset] where i
>> and offset are 32 bit integers, ptr is a loop-invariant 64 bit
>> pointer, i is an induction variable and offset is loop-invariant.
>> For that to happen, scalar evolution needs to propagate the nsw flag
>> from i + offset to the scev so that it can transform
>> 
>> 
>> ((4 * (sext i32 {%offset,+,1}<nw><%loop> to i64))<nsw> + %ptr)<nsw>
>> 
>> 
>> 
>> to
>> 
>> 
>> 
>> {((4 * (sext i32 %offset to i64)) + %ptr),+,4}<nsw><%loop>
>> 
>> 
>> 
>> Currently the inner <nsw> is actually <nw>, which blocks the
>> transformation (the outer two nsw's shouldn't currently be there
>> either, as it's the same issue for inbounds on GEP: see llvm bug
>> 23527)
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu>         http://llvm.cs.uiuc.edu <http://llvm.cs.uiuc.edu/>
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev <http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
>> 
> 
> -- 
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150701/98633e54/attachment.html>