thr3ads.net - llvm dev - [LLVMdev] Deriving undefined behavior from nsw/inbounds/poison for scalar evolution [Jul 2015]

If this information is useful, please help other people find it:
Share via:

Jingyue Wu

2015-Jun-30 03:57 UTC

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

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>

Bjarke Roune

2015-Jul-01 01:16 UTC

head link

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

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

Hal Finkel

2015-Jul-01 01:24 UTC

head link

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

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

Adam Nemet

2015-Jul-01 05:35 UTC

head link

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

> On 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
<https://llvm.org/bugs/show_bug.cgi?id=21148>). For this reason, we
disabled indvar widening in NVPTX in http://reviews.llvm.org/D6196
<http://reviews.llvm.org/D6196>.
> 
> Hope it helps. 
Hi Jingyue,

But at the same time, if I understand correctly, you do want to LSR the address
arithmetic (scale by 4 and the 64-bit addition to the base) into a 64-bit
increment of 4.  Correct?

Adam
> 
> Jingyue
> 
> On Mon, Jun 29, 2015 at 11:59 AM Adam Nemet <anemet at apple.com
<mailto:anemet at apple.com>> wrote:
> 
> > On Jun 26, 2015, at 4:01 PM, Bjarke Roune <broune at google.com
<mailto: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 <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>
> 
> 
> _______________________________________________
> 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>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150630/57fb4313/attachment.html>

Adam Nemet

2015-Jul-01 05:54 UTC

head link

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

Hi Bjarke,
> On Jun 30, 2015, at 6:16 PM, Bjarke Roune <broune at google.com>
wrote:
> 
> 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.
> 
> 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.
Is the original program defined for s = 2 and b = INT_MAX?  Seems to me that
last increment (INT_MAX - 1 + 2) before the exit condition should generate a
poison?  (From the original post, it seemed you were assuming C/C++ overflow
rules.)

Adam
> 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
<mailto: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
<https://llvm.org/bugs/show_bug.cgi?id=21148>). For this reason, we
disabled indvar widening in NVPTX in http://reviews.llvm.org/D6196
<http://reviews.llvm.org/D6196>.
> 
> Hope it helps. 
> 
> Jingyue
> 
> On Mon, Jun 29, 2015 at 11:59 AM Adam Nemet <anemet at apple.com
<mailto:anemet at apple.com>> wrote:
> 
> > On Jun 26, 2015, at 4:01 PM, Bjarke Roune <broune at google.com
<mailto: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 <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>
> 
> 
> _______________________________________________
> 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>
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150630/e368fb67/attachment.html>

Jingyue Wu

2015-Jul-01 17:06 UTC

head link

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

Right. What I forgot to say is that a 64-bit add is still legal but just
roughly twice as expensive as a 32-bit add. Then, if we do the math, the
cost w/ LSR is in general less than that w/o LSR. Consider for example

for (int i = ...; ...; ++i) {
  .. a[i + 5] ...
}

Computing &a[i + 5] w/o LSR costs 4 machine instructions on typical NVIDIA
GPUs.
i + 5 // 32-bit add. cost = 1
4 * (i + 5) // 32-bit wide multiply. cost = 1
a + 4 * (i + 5) // 64-bit add. cost = 2

Computing that w/ LSR costs only 2 machine instructions.
<previous address> + <stride> // 64-bit add. cost = 2.

LSR only promotes a variable to an indvar when doing that reduces the cost
(computed per TTI). So we are good as long as NVPTX's cost model is
correct.

Hope that makes sense.

Jingyue

On Tue, Jun 30, 2015 at 10:35 PM, Adam Nemet <anemet at apple.com> wrote:
>
> On 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.
>
>
> Hi Jingyue,
>
> But at the same time, if I understand correctly, you do want to LSR the
> address arithmetic (scale by 4 and the 64-bit addition to the base) into a
> 64-bit increment of 4.  Correct?
>
> Adam
>
>
> 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/20150701/0912ec08/attachment.html>

llvm dev - Jul 2015 - [LLVMdev] Deriving undefined behavior from nsw/inbounds/poison for scalar evolution

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

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

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

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

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

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