llvm dev - Jul 2015 - [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

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>

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
>
>
LSR only considers legal widths, so I think that then we could not generate
a 64 bit induction variable to get a pointer induction variable if we make
64 bit illegal. From IVUsers.cpp:

  // LSR is not APInt clean, do not touch integers bigger than
64-bits.  // Also avoid creating IVs of non-native types. For example,
we don't want a  // 64-bit IV in 32-bit code just because the loop has
one 64-bit cast.  uint64_t
<https://cs.corp.google.com/#piper///depot/google3/third_party/grte/v4_x86/release/usr/grte/v4/include/stdint.h&l=55&ct=xref_jump_to_def&cl=GROK&gsn=uint64_t>
Width
<https://cs.corp.google.com/#piper///depot/google3/third_party/llvm/llvm/lib/Analysis/IVUsers.cpp&l=136&ct=xref_usages&gs=cpp:llvm::class-IVUsers::AddUsersImpl(llvm::Instruction%2520*,%2520llvm::SmallPtrSetImpl%253Cllvm::Loop%2520*%253E%2520&amp;)::Width
at
google3/third_party/llvm/llvm/lib/Analysis/IVUsers.cpp:5494%257Cdef&gsn=Width>
= SE
<https://cs.corp.google.com/#piper///depot/google3/third_party/llvm/llvm/include/llvm/Analysis/IVUsers.h&l=124&ct=xref_jump_to_def&cl=GROK&gsn=SE>->getTypeSizeInBits
<https://cs.corp.google.com/#piper///depot/google3/third_party/llvm/llvm/lib/Analysis/ScalarEvolution.cpp&l=3256&ct=xref_jump_to_def&cl=GROK&gsn=getTypeSizeInBits>(I
<https://cs.corp.google.com/#piper///depot/google3/third_party/llvm/llvm/lib/Analysis/IVUsers.cpp&l=115&ct=xref_jump_to_def&cl=GROK&gsn=I>->getType
<https://cs.corp.google.com/#piper///depot/google3/third_party/llvm/llvm/include/llvm/IR/Value.h&l=222&ct=xref_jump_to_def&cl=GROK&gsn=getType>());
 if (Width
<https://cs.corp.google.com/#piper///depot/google3/third_party/llvm/llvm/lib/Analysis/IVUsers.cpp&l=136&ct=xref_jump_to_def&cl=GROK&gsn=Width>
> 64 || !DL
<https://cs.corp.google.com/#piper///depot/google3/third_party/llvm/llvm/lib/Analysis/IVUsers.cpp&l=117&ct=xref_jump_to_def&cl=GROK&gsn=DL>.isLegalInteger
<https://cs.corp.google.com/#piper///depot/google3/third_party/llvm/llvm/include/llvm/IR/DataLayout.h&l=239&ct=xref_jump_to_def&cl=GROK&gsn=isLegalInteger>(Width
<https://cs.corp.google.com/#piper///depot/google3/third_party/llvm/llvm/lib/Analysis/IVUsers.cpp&l=136&ct=xref_jump_to_def&cl=GROK&gsn=Width>))
   return false;


When I wrote "we need to keep things in 32 bits", I meant that some 32
bit
induction variables should stay in 32 bits, but we do want 64 bit induction
variables in some common cases. The usual such case is for pointer
induction variables, since pointers are 64 bit. Another case is if we get
programs where the indices are already 64 bit in the input program - we
still want to do strength reduction in that case. This happens naturally
when using a size_t as the index.

It may be that we would benefit from changing some of the callers of
isLegalInteger, like the one above, to handle illegal bit widths better and
then at that point we'd want to make 64 bit illegal.

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

----- Original Message -----
> From: "Bjarke Roune" <broune at google.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: llvmdev at cs.uiuc.edu, "Jingyue Wu" <jingyue at
google.com>
> Sent: Wednesday, July 1, 2015 2:27:59 PM
> Subject: Re: [LLVMdev] Deriving undefined behavior from nsw/inbounds/poison
for scalar evolution
> 
> 
> 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
>
> LSR only considers legal widths, so I think that then we could not
> generate a 64 bit induction variable to get a pointer induction
> variable if we make 64 bit illegal. From IVUsers.cpp:
I understand, but LSR is run very late, and already considers various
target-specific costs (addressing modes, etc.). LSR can be fixed easily if
that's the only relevant issue (and maybe LSR should be doing this anyway
for 64-bit types on 32-bit systems?). Do you get any benefit from the
'canonicalizing' transformation passes from having i64 being listed as a
legal integer width in DataLayout?

 -Hal
> 
> 
> // LSR is not APInt clean, do not touch integers bigger than 64-bits.
> // Also avoid creating IVs of non-native types. For example, we
> don't want a // 64-bit IV in 32-bit code just because the loop has
> one 64-bit cast. uint64_t Width = SE -> getTypeSizeInBits ( I ->
> getType ()); if ( Width > 64 || ! DL . isLegalInteger ( Width ))
> return false ;
> 
> 
> When I wrote "we need to keep things in 32 bits", I meant that
some
> 32 bit induction variables should stay in 32 bits, but we do want 64
> bit induction variables in some common cases. The usual such case is
> for pointer induction variables, since pointers are 64 bit. Another
> case is if we get programs where the indices are already 64 bit in
> the input program - we still want to do strength reduction in that
> case. This happens naturally when using a size_t as the index.
> 
> 
> 
> It may be that we would benefit from changing some of the callers of
> isLegalInteger, like the one above, to handle illegal bit widths
> better and then at that point we'd want to make 64 bit illegal.
> 
> 
> Bjarke
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory