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

[Jingyue Wu]

Hi Adam,

Indvar widening can sometimes be harmful for architectures (e.g. NVPTX and
AMDGPU) where wider integer operations are more expensive (
https://llvm.org/bugs/show_bug.cgi?id=21148). For this reason, we disabled
indvar widening in NVPTX in http://reviews.llvm.org/D6196.

Hope it helps.

Jingyue

On Mon, Jun 29, 2015 at 11:59 AM Adam Nemet <anemet at apple.com> wrote:

>
> > On Jun 26, 2015, at 4:01 PM, Bjarke Roune <broune at google.com> wrote:
> >
> > *** 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>
>
> I guess what I am missing here why indvars does not create an i64
> induction variable for this?
>
> Adam
>
>
> >
> > 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         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150630/fac963bd/attachment.html>