llvm dev - Jun 2019 - Bug: Library functions for ISD::SRA, ISD::SHL, and ISD::SRL

Hi Eli,

Thanks for pointing to the CTLZ_ZERO_UNDEF “LibCall” implementation. I have not
it in the version that I am currently using, so it’s nice to know that it’s
implemented now.

Incidentally, the CTLZ… implementation is IDENTICAL to what I am proposing for
the Shifts. This is not just adding support for “out-of-tree-targets”, but
giving consistency to the fact that we have perfectly defined LibCalls for
Shifts, but they can’t be used because there’s an omission in the sources.

I only proposed to add a missing case statement to the ConvertNodeToLibCall.

To my understanding this is totally harmless to any existing or future targets
because all what it does is to call the Library function when setOperationAction
is set to “LibCall”. This is not different that any other case, and you just
confirmed that you added the same for the CTLZ… functions.  So I do not
understand what you mean by “terrible quality in a lot of cases”:  Targets with
native shift support are not affected, and neither are targets with custom
lowering.

I would suggest that you look in more detail at the actual implementation of the
ConvertNodeToLibCall and from where it is called and its actual purpose. There’s
nothing else required. So I would appreciate that you elaborate on why you think
that this is not a good idea.

Thanks,

John Lluch

> On 10 Jun 2019, at 21:09, Eli Friedman <efriedma at quicinc.com>
wrote:
> 
> All in-tree targets have variable shift instructions for native integer
types, except for AVR.  And AVR implements custom lowering.  I’m not sure what
else would be required to actually make marking a shift as “libcall” actually
work well; technically, the change you’re proposing might produce valid code,
but it would be terrible quality in a lot of cases.  So I’m not eager to add
partial support just for out-of-tree targets.
>  
> Marking CTLZ_ZERO_UNDEF as “LibCall” was implemented in
https://reviews.llvm.org/D47917 <https://reviews.llvm.org/D47917> . 
Probably straightforward to extend that to cover CTTZ_ZERO_UNDEF and CTPOP.
>  
> -Eli
>  
> From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Joan
Lluch via llvm-dev
> Sent: Monday, June 10, 2019 8:31 AM
> To: llvm-dev <llvm-dev at lists.llvm.org>
> Subject: [EXT] [llvm-dev] Bug: Library functions for ISD::SRA, ISD::SHL,
and ISD::SRL
>  
> LLVM appears to support Library functions for ISD::SRA ,ISD::SHL, and
ISD::SRL, as they are properly defined in RuntimeLibCalls.def.
>  
> The library functions defined in RuntimeLibCalls.def (among others) are
these:
>  
> HANDLE_LIBCALL(SRA_I16, "__ashrhi3")
> HANDLE_LIBCALL(SRA_I32, "__ashrsi3")
> HANDLE_LIBCALL(SRA_I64, "__ashrdi3")
>  
> However, setting
>  
> setOperationAction(ISD::SRA, MVT::i16, LibCall);
>  
> in the TargetLowering constructor causes LLVM to stop with an assert as the
shift instruction can’t be selected.
>  
> The problem is in SelectionDAGLegalize::ConvertNodeToLibcall because
there’s no switch case for any of the Shift instructions.
>  
> The problem gets solved by just adding switch cases like this (and similar
for the other shift instructions):
>  
> case ISD::SRA:
>       Results.push_back(ExpandIntLibCall(Node, false,
>                                        RTLIB::SRA_I16,
>                                        RTLIB::SRA_I16, RTLIB::SRA_I32,
>                                        RTLIB::SRA_I64, RTLIB::SRA_I128));
>  
> I think this is a BUG by omission of necessary switch cases.
>  
>  
> Similarly, the following ISD codes  ISD::CTTZ, ISD::CTLZ, ISD::CTPOP do not
define any Library calls, despite LLVM being able to fully expand them into
rather large code for targets that do not natively implement them.
> I regard this also as an omission/bug, because not all targets would
benefit from the custom expansion of these ISD codes, which as said can get
unnecessarily long and costly.
> Instead, LLVM should have them available as possible LibCalls.
>  
> Any comments or opinions on these subjects are appreciated
>  
> Joan Lluch
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190611/d7902e68/attachment.html>

The legalization itself is simple; the issue all the places that assume shifts
are legal.  For example, you probably don’t want “a+a” to become a libcall.

-Eli

From: Joan Lluch <joan.lluch at icloud.com>
Sent: Monday, June 10, 2019 3:05 PM
To: Eli Friedman <efriedma at quicinc.com>
Cc: llvm-dev <llvm-dev at lists.llvm.org>
Subject: [EXT] Re: [llvm-dev] Bug: Library functions for ISD::SRA, ISD::SHL, and
ISD::SRL

Hi Eli,

Thanks for pointing to the CTLZ_ZERO_UNDEF “LibCall” implementation. I have not
it in the version that I am currently using, so it’s nice to know that it’s
implemented now.

Incidentally, the CTLZ… implementation is IDENTICAL to what I am proposing for
the Shifts. This is not just adding support for “out-of-tree-targets”, but
giving consistency to the fact that we have perfectly defined LibCalls for
Shifts, but they can’t be used because there’s an omission in the sources.

I only proposed to add a missing case statement to the ConvertNodeToLibCall.

To my understanding this is totally harmless to any existing or future targets
because all what it does is to call the Library function when setOperationAction
is set to “LibCall”. This is not different that any other case, and you just
confirmed that you added the same for the CTLZ… functions.  So I do not
understand what you mean by “terrible quality in a lot of cases”:  Targets with
native shift support are not affected, and neither are targets with custom
lowering.

I would suggest that you look in more detail at the actual implementation of the
ConvertNodeToLibCall and from where it is called and its actual purpose. There’s
nothing else required. So I would appreciate that you elaborate on why you think
that this is not a good idea.

Thanks,

John Lluch


On 10 Jun 2019, at 21:09, Eli Friedman <efriedma at
quicinc.com<mailto:efriedma at quicinc.com>> wrote:

All in-tree targets have variable shift instructions for native integer types,
except for AVR.  And AVR implements custom lowering.  I’m not sure what else
would be required to actually make marking a shift as “libcall” actually work
well; technically, the change you’re proposing might produce valid code, but it
would be terrible quality in a lot of cases.  So I’m not eager to add partial
support just for out-of-tree targets.

Marking CTLZ_ZERO_UNDEF as “LibCall” was implemented in
https://reviews.llvm.org/D47917 .  Probably straightforward to extend that to
cover CTTZ_ZERO_UNDEF and CTPOP.

-Eli

From: llvm-dev <llvm-dev-bounces at lists.llvm.org<mailto:llvm-dev-bounces
at lists.llvm.org>> On Behalf Of Joan Lluch via llvm-dev
Sent: Monday, June 10, 2019 8:31 AM
To: llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>
Subject: [EXT] [llvm-dev] Bug: Library functions for ISD::SRA, ISD::SHL, and
ISD::SRL

LLVM appears to support Library functions for ISD::SRA ,ISD::SHL, and ISD::SRL,
as they are properly defined in RuntimeLibCalls.def.

The library functions defined in RuntimeLibCalls.def (among others) are these:

HANDLE_LIBCALL(SRA_I16, "__ashrhi3")
HANDLE_LIBCALL(SRA_I32, "__ashrsi3")
HANDLE_LIBCALL(SRA_I64, "__ashrdi3")

However, setting

setOperationAction(ISD::SRA, MVT::i16, LibCall);

in the TargetLowering constructor causes LLVM to stop with an assert as the
shift instruction can’t be selected.

The problem is in SelectionDAGLegalize::ConvertNodeToLibcall because there’s no
switch case for any of the Shift instructions.

The problem gets solved by just adding switch cases like this (and similar for
the other shift instructions):

case ISD::SRA:
      Results.push_back(ExpandIntLibCall(Node, false,
                                       RTLIB::SRA_I16,
                                       RTLIB::SRA_I16, RTLIB::SRA_I32,
                                       RTLIB::SRA_I64, RTLIB::SRA_I128));

I think this is a BUG by omission of necessary switch cases.


Similarly, the following ISD codes  ISD::CTTZ, ISD::CTLZ, ISD::CTPOP do not
define any Library calls, despite LLVM being able to fully expand them into
rather large code for targets that do not natively implement them.
I regard this also as an omission/bug, because not all targets would benefit
from the custom expansion of these ISD codes, which as said can get
unnecessarily long and costly.
Instead, LLVM should have them available as possible LibCalls.

Any comments or opinions on these subjects are appreciated

Joan Lluch

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190611/ddc0c0c6/attachment.html>

Hi Eli,

First of all, please I would appreciate that you try to not confuse my limited
use of English with stupidity or lack or criteria in other subjects. I’m not
English native, so please keep that in mind. You have been significantly helpful
in the recent past so please keep on.

Interestingly, you made a mention of a related but not identical issue. It is
true that most (or all) processors support constant shift instructions so that
LLVM can safely assume that constant shifts are legal. I don’t think that LLVM
makes any explicit assumption that variable shifts are legal too though, but if
it does, then this is not either a problem.

We need to make the distinction between constant shifts and variable shifts. The
later are generally supported only by the major processors, but not in the
general case. In particular the AVR and the MSP430 targets do not have native
support for them. In both cases variable shifts are dealt with by means of a
custom inserter. This is just a possible way to implement them, but not the
easiest or the cleaner one in my opinion.

Another possibility is to implement Custom lower for constant shifts, but to
generate a lib call (or an intrinsic) for the variable shifts. The lib call can
be generated as part of the Custom lowering, and this is the implementation that
I chose for my target, however, the LLVM infrastructure does not make this
particularly straightforward for two reasons:

- First, there’s no working support for ‘LibCall’ lowering of shifts, this is
broken by the omission of the case statement that I mentioned,
- Second,  there’s no simple way that I am aware to make LLVM to create a lib
call from the Custom lowering implementation;

I am not going to strongly suggest how to solve this problem, but just to state
that there’s an actual problem or at least an oddity on the way that shifts are
(or can be) dealt with.

To me, the first thing we need to do is to actually have LibCall
operationActions working for shifts. This is also as a matter of code
consistency if you want, and doing this alone doesn’t break anything: ultimately
it’s the responsibility of the target to chose whether it uses it or not.

Additionally, we should specify a way to fall through to LibCall lowering from a
Custom lower implementation, if required or requested by the target. For example
by providing a public path or a hook to ConvertNodeToLibCall, and/or by making
the Custom implementation returning something that is recognised by the
SelectionDAGLegalize code as a request for a LibCall fall through. Currently,
the fall through mechanism after Custom lowering goes directly to the Expand
code

Yet another approach would be that LLVM would explicitly made a distinction
between constant and variable shifts, so that they can be lowered in separated
ways, but I rather prefer the approach above because it’s more generic and it
would widen the custom lowering implementation possibilities for targets with
partial support of LLVM  instructions.

In my opinion, it’s not right to consider any "out of tree targets",
(whatever that means) as not worth for LLVM improvement. The LLVM project has
traditionally focused on major processors for a good reason, but the grow of the
IoT and the recent popularisation of many 8 and 16 bit architectures for
embedded and control applications make it worth a LLVM focus shift to the
particular needs of these smaller processors. Incidentally, the AVR and the
MSP430 still remain as ‘experimental’ targets.

Just my two cents anyway, and sorry for my English.

John Lluch

> On 11 Jun 2019, at 02:16, Eli Friedman <efriedma at quicinc.com>
wrote:
> 
> The legalization itself is simple; the issue all the places that assume
shifts are legal.  For example, you probably don’t want “a+a” to become a
libcall.
>  
> -Eli
>  
> From: Joan Lluch <joan.lluch at icloud.com> 
> Sent: Monday, June 10, 2019 3:05 PM
> To: Eli Friedman <efriedma at quicinc.com>
> Cc: llvm-dev <llvm-dev at lists.llvm.org>
> Subject: [EXT] Re: [llvm-dev] Bug: Library functions for ISD::SRA,
ISD::SHL, and ISD::SRL
>  
> Hi Eli,
>  
> Thanks for pointing to the CTLZ_ZERO_UNDEF “LibCall” implementation. I have
not it in the version that I am currently using, so it’s nice to know that it’s
implemented now.
>  
> Incidentally, the CTLZ… implementation is IDENTICAL to what I am proposing
for the Shifts. This is not just adding support for “out-of-tree-targets”, but
giving consistency to the fact that we have perfectly defined LibCalls for
Shifts, but they can’t be used because there’s an omission in the sources.
>  
> I only proposed to add a missing case statement to the
ConvertNodeToLibCall.
>  
> To my understanding this is totally harmless to any existing or future
targets because all what it does is to call the Library function when
setOperationAction is set to “LibCall”. This is not different that any other
case, and you just confirmed that you added the same for the CTLZ… functions. 
So I do not understand what you mean by “terrible quality in a lot of cases”: 
Targets with native shift support are not affected, and neither are targets with
custom lowering.
>  
> I would suggest that you look in more detail at the actual implementation
of the ConvertNodeToLibCall and from where it is called and its actual purpose.
There’s nothing else required. So I would appreciate that you elaborate on why
you think that this is not a good idea.
>  
> Thanks,
>  
> John Lluch
>  
>  
> On 10 Jun 2019, at 21:09, Eli Friedman <efriedma at quicinc.com
<mailto:efriedma at quicinc.com>> wrote:
>  
> All in-tree targets have variable shift instructions for native integer
types, except for AVR.  And AVR implements custom lowering.  I’m not sure what
else would be required to actually make marking a shift as “libcall” actually
work well; technically, the change you’re proposing might produce valid code,
but it would be terrible quality in a lot of cases.  So I’m not eager to add
partial support just for out-of-tree targets.
>  
> Marking CTLZ_ZERO_UNDEF as “LibCall” was implemented in
https://reviews.llvm.org/D47917 <https://reviews.llvm.org/D47917> . 
Probably straightforward to extend that to cover CTTZ_ZERO_UNDEF and CTPOP.
>  
> -Eli
>  
> From: llvm-dev <llvm-dev-bounces at lists.llvm.org
<mailto:llvm-dev-bounces at lists.llvm.org>> On Behalf Of Joan Lluch
via llvm-dev
> Sent: Monday, June 10, 2019 8:31 AM
> To: llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>>
> Subject: [EXT] [llvm-dev] Bug: Library functions for ISD::SRA, ISD::SHL,
and ISD::SRL
>  
> LLVM appears to support Library functions for ISD::SRA ,ISD::SHL, and
ISD::SRL, as they are properly defined in RuntimeLibCalls.def.
>  
> The library functions defined in RuntimeLibCalls.def (among others) are
these:
>  
> HANDLE_LIBCALL(SRA_I16, "__ashrhi3")
> HANDLE_LIBCALL(SRA_I32, "__ashrsi3")
> HANDLE_LIBCALL(SRA_I64, "__ashrdi3")
>  
> However, setting
>  
> setOperationAction(ISD::SRA, MVT::i16, LibCall);
>  
> in the TargetLowering constructor causes LLVM to stop with an assert as the
shift instruction can’t be selected.
>  
> The problem is in SelectionDAGLegalize::ConvertNodeToLibcall because
there’s no switch case for any of the Shift instructions.
>  
> The problem gets solved by just adding switch cases like this (and similar
for the other shift instructions):
>  
> case ISD::SRA:
>       Results.push_back(ExpandIntLibCall(Node, false,
>                                        RTLIB::SRA_I16,
>                                        RTLIB::SRA_I16, RTLIB::SRA_I32,
>                                        RTLIB::SRA_I64, RTLIB::SRA_I128));
>  
> I think this is a BUG by omission of necessary switch cases.
>  
>  
> Similarly, the following ISD codes  ISD::CTTZ, ISD::CTLZ, ISD::CTPOP do not
define any Library calls, despite LLVM being able to fully expand them into
rather large code for targets that do not natively implement them.
> I regard this also as an omission/bug, because not all targets would
benefit from the custom expansion of these ISD codes, which as said can get
unnecessarily long and costly.
> Instead, LLVM should have them available as possible LibCalls.
>  
> Any comments or opinions on these subjects are appreciated
>  
> Joan Lluch
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190611/6b227956/attachment.html>