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

Wed Jul 1 11:13:23 PDT 2015

On Tue, Jun 30, 2015 at 6:24 PM, Hal Finkel <hfinkel at anl.gov> wrote:

> ----- Original Message -----
> > From: "Bjarke Roune" <broune at google.com>
> > To: "Jingyue Wu" <jingyue at google.com>
> > Cc: llvmdev at cs.uiuc.edu
> > Sent: Tuesday, June 30, 2015 8:16:13 PM
> > Subject: Re: [LLVMdev] Deriving undefined behavior from
> nsw/inbounds/poison for scalar evolution
> >
> > Hi Adam,
> >
> > Jingyue is right. We need to keep things in 32 bits because 64 bit
> > arithmetic is more expensive and because one 64 bit register
> > consumes two 32 bit registers.
> >
>
> What benefit to you get from listing i64 as a legal integer width in the
> DataLayout for NVPTX?
>
>  -Hal
>

That's a good call. I used to misunderstand what DataLayout::isLegalInteger
means; I thought that would prevent codegen from emitting i64 at all. We
will look at how things go with i64 removed from the datalayout string.

>
> >
> >
> > To add a bit more background: we would often emit worse code if we
> > widened in indvars and then narrowed in the NVPTX backend later
> > because we often would not be able to narrow AFAICT. Consider this
> > general pattern where everything is 32 bit:
> >
> >
> > for (int i = a; i < b; i += s) {
> > // ...
> > }
> >
> >
> > Suppose we widen i to be 64 bit:
> >
> >
> >
> > for (int64 i = a; i < b; i += s) {
> > // ...
> > }
> >
> >
> > As an example, suppose a = 0, b = INT_MAX, s = 2. The final value of
> > i that makes the loop terminate would then be INT_MAX+1, so we
> > cannot narrow i to 32 bits. To narrow in general, we have to prove
> > that a, b and s take on only values where narrowing is sound. That's
> > often not possible. I suppose an alternative would be to issue an
> > assume intrinsic restricting the range of i, though I prefer making
> > scalar evolution more powerful since that should be more generally
> > useful.
> >
> >
> > Bjarke
> >
> >
> >
> >
> >
> > On Mon, Jun 29, 2015 at 8:57 PM, Jingyue Wu < jingyue at google.com >
> > wrote:
> >
> >
> >
> > 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
> >
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > 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/9d680158/attachment.html>