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

On Wed, Jul 1, 2015 at 3:07 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> ----- 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: [...]
> > 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?
>
> I agree that LSR should be doing that anyway. I think we originally made
i64 legal because "illegal" sounds more serious than just "not
the ideal
size for this hardware" and PTX does have an i64 type, it's just slower
and
takes more register space after compilation to SASS. I did a quick review
of all the calls to isLegalInteger, fitsInLegalInteger,
getLargestLegalIntTypeSize, getSmallestLegalIntType. Here's the parts that
jumped out at me and my hunch about whether its better for i64 to be legal
or illegal in that place for PTX:

 1) Strongly favors legal: LSR only considers legal induction variables.
 2) Favors legal: In FindLoopCounter from IndVarSimplify, I think it should
be ok to find an i64 loop counter if there is nothing better to be found.
 3) Favors legal: In SROA, we should probably prefer i64 to
non-virtual-register alternatives that are harder to analyze.
 4) Favors illegal: InstCombineCasts folds casts into PHIs in some limited
circumstances for legal types. It's probably better not to do that for i64
for PTX.
 5) Slightly favors legal: For
TargetTransformInfoImplBase::getOperationCost, IntToPtr and PtrToInt and
truncate should probably still be free for i64, since the pointer is 64 bit
too.
 6) Slightly favors legal: In combineLoadToOperationType from
InstCombineLoadStoreAlloca.cpp, there's really no reason that i64 cannot be
used, since it would be replacing another 64-bit type (e.g. double) that
also takes 2 registers.

On the whole, having i64 legal seems better as things stand, though if some
of these (especially 1) were changed to deal differently with illegal
types, then making i64 illegal might be marginally better due to 4.

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

----- Original Message -----
> From: "Bjarke Roune" <broune at google.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "LLVM Developers Mailing List" <llvmdev at
cs.uiuc.edu>, "Jingyue Wu" <jingyue at google.com>
> Sent: Wednesday, July 1, 2015 8:02:10 PM
> Subject: Re: [LLVMdev] Deriving undefined behavior from nsw/inbounds/poison
for scalar evolution
> 
> 
> 
> 
> On Wed, Jul 1, 2015 at 3:07 PM, Hal Finkel < hfinkel at anl.gov >
wrote:
> 
> 
> ----- 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: [...]
> > 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?
> 
> I agree that LSR should be doing that anyway. I think we originally
> made i64 legal because "illegal" sounds more serious than just
"not
> the ideal size for this hardware" and PTX does have an i64 type,
> it's just slower and takes more register space after compilation to
> SASS. I did a quick review of all the calls to isLegalInteger,
> fitsInLegalInteger, getLargestLegalIntTypeSize,
> getSmallestLegalIntType. Here's the parts that jumped out at me and
> my hunch about whether its better for i64 to be legal or illegal in
> that place for PTX:
> 
> 1) Strongly favors legal: LSR only considers legal induction
> variables.
> 2) Favors legal: In FindLoopCounter from IndVarSimplify, I think it
> should be ok to find an i64 loop counter if there is nothing better
> to be found. 3) Favors legal: In SROA, we should probably prefer i64
> to non-virtual-register alternatives that are harder to analyze.
> 4) Favors illegal: InstCombineCasts folds casts into PHIs in some
> limited circumstances for legal types. It's probably better not to
> do that for i64 for PTX.
> 
> 5) Slightly favors legal: For
> TargetTransformInfoImplBase::getOperationCost, IntToPtr and PtrToInt
> and truncate should probably still be free for i64, since the
> pointer is 64 bit too.
> 6) Slightly favors legal: In combineLoadToOperationType from
> InstCombineLoadStoreAlloca.cpp, there's really no reason that i64
> cannot be used, since it would be replacing another 64-bit type
> (e.g. double) that also takes 2 registers.
> 
> 
> On the whole, having i64 legal seems better as things stand, though
> if some of these (especially 1) were changed to deal differently
> with illegal types, then making i64 illegal might be marginally
> better due to 4.
> 
Ah, this is very interesting.

My underlying view here is that since i64 is not really a legal type in the
hardware, we should not mark it as a legal type. What differs here from the
normal situation is where the legalization is done. Normally we have the SDAG do
this, but in this case, the legalization is done by some other part of the
software stack post-LLVM. However, since the IR level optimizers should not
contain explicit knowledge of how legalization is done later, this difference
should be irrelevant at the IR level.

I think that the correct approach here is to "fix" the few things
you've identified so that they work reasonably for 32-bit architectures with
64-bit pointers, and then remove i64 from the set of legal integer types in
DataLayout for NVPTX. I suspect this will yield the best end result for
everyone.

Thanks again,
Hal 
> 
> 
> Bjarke
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory