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

[Bjarke Roune]

*** 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.

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)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150626/263e0f6f/attachment.html>