llvm dev - Jun 2019 - Support 64-bit pointers in open source RV32 GPU ISA using register pairs and address space ID’s

>
> Hi Reshabh, and congratulations on being selected for GSoC. I haven't
> looked at supporting larger than native-width pointers on a target
> before. I'd thought that AVR might be relevant (given it uses 16-bit
> pointers but has 8-bit GPRs). See the description here
> <http://lists.llvm.org/pipermail/llvm-dev/2019-January/129089.html>.
>
Many thanks Alex, the AVR backend looks like a very promising reference.
I'm planning to follow their approach.

On Mon, Jun 10, 2019 at 9:33 PM Alex Bradbury <asb at lowrisc.org> wrote:
> On Wed, 5 Jun 2019 at 08:41, Reshabh Sharma via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> >
> > Hello everyone,
> >
> > We are working on extending RISC-V LLVM backend which will help us to
> achieve the goal of improving programmability in the second generation
> design of our open source RISC-V manycore processor (bjump.org/manycore).
> >
> > We started with supporting 64 bit pointers in RISCV 32 bit backend
using
> address spaces and register pairs. We aim to support 64 bit pointers in
> address space 1 using a pair of i32 registers. The 64 bit address will be
> stored in two i32 registers and we will add custom load/store instructions
> to concat the data from the two registers for getting the 64 bit address at
> the hardware level.
> >
> > We started with updating the data layout string to
> "e-m:e-p:32:32-p1:64:64-i64:64-n32-S128" and we are stuck in the
> legalization phase.
> >
> > Example for node "i64 = TargetGlobalAddress<[3 x i64]
addrspace(1)*
> @foo> 0", it does not automatically expand the i64 result into two
i32. We
> tried to convert i64 into v2i32 so that it can pass the legalizer but that
> does not seem to work well. Is there any simpler way to handle this?
> >
> > We would be happy to hear your views and suggestions on this :)
>
> Hi Reshabh, and congratulations on being selected for GSoC. I haven't
> looked at supporting larger than native-width pointers on a target
> before. I'd thought that AVR might be relevant (given it uses 16-bit
> pointers but has 8-bit GPRs). See the description here
> <http://lists.llvm.org/pipermail/llvm-dev/2019-January/129089.html>.
> CCing Dylan McKay in case he has any thoughts.
>
> Best,
>
> Alex
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190611/7d17dd42/attachment.html>

The AVR backend's approach does require some workarounds for the legalizer
as it stands.

On AVR, there are 31 8-bit general purpose registers. Only the last six,
R26-R31, may be used for pointer operations, giving us a maximum of three
pointer registers at any one time (commonly named X, Y, and Z). Although
the AVR does have 16-bit registers, only the memory load/store instructions
(LD, LDD, ST, STD, LPM, ...) are defined for 16-bit values. Every other
16-bit operation must be expanded into two 8-bit ones, including ADD, SUB,
MUL, bitshifts, comparisons.. everything.

The legalizer is where this expansion should happen. The legalizer bases
it's lowering logic on the size of the *largest legal integer type*. The
legalizer defines the size of this as the size of the largest CPU register
(I cannot find the source of this. The implicit assumption is that if a
value is small enough to be stored in a CPU register, then the operation
must be legal and thus no further expansion (i16->2x i8) happens. The
legalizer does not know that i16 addition, subtraction, bitshifting, is
illegal and emits an ISel node that the silicon can never fulfill. The
legalizer, in each of the case statements for the different node types it
handles, decides whether an *operation* is legal or should be expanded, but
approximates this by simply checking if the underlying *type* is legal. The
impedance mismatch occurs because even though a value is small enough to be
stored in hardware ("is a legal integer type"), it does not
necessarily
mean that the hardware for executing that operation exists.

This means that on AVR, the legalizer never expands out to 8-bit nodes,
always leaving technically illegal 16-bit DAGs for instruction selection
and TableGen pattern matching. To work around this, on every single of the
dozens of hardware instructions that can't be expanded further, we've
added
dozens of 16-bit pseudoinstructions along with handcrafted MachineInst
expansion logic, performing the expansion in the AVRExpandPseudoInsts pass
<https://github.com/llvm/llvm-project/blob/master/llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp>.
It's quite a maintenance burden, along with a lot of mostly-redundant code,
that should be able to be replicated higher up at the legalizer level,
where expansion logic is handed target-independently, avoiding a lot of the
finicky details at the MachineInst level. The better solution would be to
generalize the legalizer so that it understands the distinction between
legal types and legal operations.

I believe this problem could affect you if you added the 64-bit register
pair to the lists in RISCVRegisterInfo.td, as then 64-bit would be the
largest legal integer type, causing expansion to halt and stop before
lowering to i32 or smaller. It's been a long time since I've looked into
the legalizer regarding this though, and I imagine AVR is a little more
constrained than RISC-V, so perhaps YMMV.

I just had another read of your original message and this sticks out:

Example for node "i64 = TargetGlobalAddress<[3 x i64] addrspace(1)*
@foo>
> 0", it does not automatically expand the i64 result into two i32. We
tried
> to convert i64 into v2i32 so that it can pass the legalizer but that does
> not seem to work well. Is there any simpler way to handle this?
>
Sounds pretty similar.

I've described the issue a couple times before:

   -
  
http://llvm.1065342.n5.nabble.com/llvm-dev-Status-of-the-AVR-backend-2019-LLVM-7-0-td125084.html#backend-implementation-maintenance-pain-points
   - https://github.com/avr-llvm/llvm/issues/163#issuecomment-143044993




On Tue, Jun 11, 2019 at 8:08 PM Reshabh Sharma <reshabhsh at gmail.com>
wrote:
> Hi Reshabh, and congratulations on being selected for GSoC. I haven't
>> looked at supporting larger than native-width pointers on a target
>> before. I'd thought that AVR might be relevant (given it uses
16-bit
>> pointers but has 8-bit GPRs). See the description here
>>
<http://lists.llvm.org/pipermail/llvm-dev/2019-January/129089.html>.
>>
>
> Many thanks Alex, the AVR backend looks like a very promising reference.
> I'm planning to follow their approach.
>
> On Mon, Jun 10, 2019 at 9:33 PM Alex Bradbury <asb at lowrisc.org>
wrote:
>
>> On Wed, 5 Jun 2019 at 08:41, Reshabh Sharma via llvm-dev
>> <llvm-dev at lists.llvm.org> wrote:
>> >
>> > Hello everyone,
>> >
>> > We are working on extending RISC-V LLVM backend which will help us
to
>> achieve the goal of improving programmability in the second generation
>> design of our open source RISC-V manycore processor
(bjump.org/manycore).
>> >
>> > We started with supporting 64 bit pointers in RISCV 32 bit backend
>> using address spaces and register pairs. We aim to support 64 bit
pointers
>> in address space 1 using a pair of i32 registers. The 64 bit address
will
>> be stored in two i32 registers and we will add custom load/store
>> instructions to concat the data from the two registers for getting the
64
>> bit address at the hardware level.
>> >
>> > We started with updating the data layout string to
>> "e-m:e-p:32:32-p1:64:64-i64:64-n32-S128" and we are stuck in
the
>> legalization phase.
>> >
>> > Example for node "i64 = TargetGlobalAddress<[3 x i64]
addrspace(1)*
>> @foo> 0", it does not automatically expand the i64 result into
two i32. We
>> tried to convert i64 into v2i32 so that it can pass the legalizer but
that
>> does not seem to work well. Is there any simpler way to handle this?
>> >
>> > We would be happy to hear your views and suggestions on this :)
>>
>> Hi Reshabh, and congratulations on being selected for GSoC. I
haven't
>> looked at supporting larger than native-width pointers on a target
>> before. I'd thought that AVR might be relevant (given it uses
16-bit
>> pointers but has 8-bit GPRs). See the description here
>>
<http://lists.llvm.org/pipermail/llvm-dev/2019-January/129089.html>.
>> CCing Dylan McKay in case he has any thoughts.
>>
>> Best,
>>
>> Alex
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190613/86d9ef51/attachment.html>

Million thanks Dylan for the write up and sharing your experience with AVR
backend, this was really helpful.

 The better solution would be to generalize the legalizer so that
it
> understands the distinction between legal types and legal operations.
>
This makes sense to me, though I was not aware about the troubles caused by
adding the register pair and making i64 legal. I am planning to use a
wrapper node for all 64 bit GlobalAddress in address space 1 (I saw this in
AVR backend). This looks quite promising but I'm not super sure that will
this work.

I believe this problem could affect you if you added the 64-bit
register
> pair to the lists in RISCVRegisterInfo.td, as then 64-bit would be the
> largest legal integer type, causing expansion to halt and stop before
> lowering to i32 or smaller. It's been a long time since I've looked
into
> the legalizer regarding this though, and I imagine AVR is a little more
> constrained than RISC-V, so perhaps YMMV.
>
I see, making 64 bit legal using register pair might affect other things a
lot (as you mentioned about the maintenance challenge).

- Reshabh

On Thu, Jun 13, 2019 at 12:27 PM Dylan McKay <me at dylanmckay.io> wrote:
> The AVR backend's approach does require some workarounds for the
legalizer
> as it stands.
>
> On AVR, there are 31 8-bit general purpose registers. Only the last six,
> R26-R31, may be used for pointer operations, giving us a maximum of three
> pointer registers at any one time (commonly named X, Y, and Z). Although
> the AVR does have 16-bit registers, only the memory load/store instructions
> (LD, LDD, ST, STD, LPM, ...) are defined for 16-bit values. Every other
> 16-bit operation must be expanded into two 8-bit ones, including ADD, SUB,
> MUL, bitshifts, comparisons.. everything.
>
> The legalizer is where this expansion should happen. The legalizer bases
> it's lowering logic on the size of the *largest legal integer type*.
The
> legalizer defines the size of this as the size of the largest CPU register
> (I cannot find the source of this. The implicit assumption is that if a
> value is small enough to be stored in a CPU register, then the operation
> must be legal and thus no further expansion (i16->2x i8) happens. The
> legalizer does not know that i16 addition, subtraction, bitshifting, is
> illegal and emits an ISel node that the silicon can never fulfill. The
> legalizer, in each of the case statements for the different node types it
> handles, decides whether an *operation* is legal or should be expanded,
> but approximates this by simply checking if the underlying *type* is
> legal. The impedance mismatch occurs because even though a value is small
> enough to be stored in hardware ("is a legal integer type"), it
does not
> necessarily mean that the hardware for executing that operation exists.
>
> This means that on AVR, the legalizer never expands out to 8-bit nodes,
> always leaving technically illegal 16-bit DAGs for instruction selection
> and TableGen pattern matching. To work around this, on every single of the
> dozens of hardware instructions that can't be expanded further,
we've added
> dozens of 16-bit pseudoinstructions along with handcrafted MachineInst
> expansion logic, performing the expansion in the AVRExpandPseudoInsts pass
>
<https://github.com/llvm/llvm-project/blob/master/llvm/lib/Target/AVR/AVRExpandPseudoInsts.cpp>.
> It's quite a maintenance burden, along with a lot of mostly-redundant
code,
> that should be able to be replicated higher up at the legalizer level,
> where expansion logic is handed target-independently, avoiding a lot of the
> finicky details at the MachineInst level. The better solution would be to
> generalize the legalizer so that it understands the distinction between
> legal types and legal operations.
>
> I believe this problem could affect you if you added the 64-bit register
> pair to the lists in RISCVRegisterInfo.td, as then 64-bit would be the
> largest legal integer type, causing expansion to halt and stop before
> lowering to i32 or smaller. It's been a long time since I've looked
into
> the legalizer regarding this though, and I imagine AVR is a little more
> constrained than RISC-V, so perhaps YMMV.
>
> I just had another read of your original message and this sticks out:
>
> Example for node "i64 = TargetGlobalAddress<[3 x i64] addrspace(1)*
@foo>
>> 0", it does not automatically expand the i64 result into two i32.
We tried
>> to convert i64 into v2i32 so that it can pass the legalizer but that
does
>> not seem to work well. Is there any simpler way to handle this?
>>
>
> Sounds pretty similar.
>
> I've described the issue a couple times before:
>
>    -
>   
http://llvm.1065342.n5.nabble.com/llvm-dev-Status-of-the-AVR-backend-2019-LLVM-7-0-td125084.html#backend-implementation-maintenance-pain-points
>    - https://github.com/avr-llvm/llvm/issues/163#issuecomment-143044993
>
>
>
>
> On Tue, Jun 11, 2019 at 8:08 PM Reshabh Sharma <reshabhsh at
gmail.com>
> wrote:
>
>> Hi Reshabh, and congratulations on being selected for GSoC. I
haven't
>>> looked at supporting larger than native-width pointers on a target
>>> before. I'd thought that AVR might be relevant (given it uses
16-bit
>>> pointers but has 8-bit GPRs). See the description here
>>>
<http://lists.llvm.org/pipermail/llvm-dev/2019-January/129089.html>.
>>>
>>
>> Many thanks Alex, the AVR backend looks like a very promising
reference.
>> I'm planning to follow their approach.
>>
>> On Mon, Jun 10, 2019 at 9:33 PM Alex Bradbury <asb at
lowrisc.org> wrote:
>>
>>> On Wed, 5 Jun 2019 at 08:41, Reshabh Sharma via llvm-dev
>>> <llvm-dev at lists.llvm.org> wrote:
>>> >
>>> > Hello everyone,
>>> >
>>> > We are working on extending RISC-V LLVM backend which will
help us to
>>> achieve the goal of improving programmability in the second
generation
>>> design of our open source RISC-V manycore processor
(bjump.org/manycore
>>> ).
>>> >
>>> > We started with supporting 64 bit pointers in RISCV 32 bit
backend
>>> using address spaces and register pairs. We aim to support 64 bit
pointers
>>> in address space 1 using a pair of i32 registers. The 64 bit
address will
>>> be stored in two i32 registers and we will add custom load/store
>>> instructions to concat the data from the two registers for getting
the 64
>>> bit address at the hardware level.
>>> >
>>> > We started with updating the data layout string to
>>> "e-m:e-p:32:32-p1:64:64-i64:64-n32-S128" and we are stuck
in the
>>> legalization phase.
>>> >
>>> > Example for node "i64 = TargetGlobalAddress<[3 x i64]
addrspace(1)*
>>> @foo> 0", it does not automatically expand the i64 result
into two i32. We
>>> tried to convert i64 into v2i32 so that it can pass the legalizer
but that
>>> does not seem to work well. Is there any simpler way to handle
this?
>>> >
>>> > We would be happy to hear your views and suggestions on this
:)
>>>
>>> Hi Reshabh, and congratulations on being selected for GSoC. I
haven't
>>> looked at supporting larger than native-width pointers on a target
>>> before. I'd thought that AVR might be relevant (given it uses
16-bit
>>> pointers but has 8-bit GPRs). See the description here
>>>
<http://lists.llvm.org/pipermail/llvm-dev/2019-January/129089.html>.
>>> CCing Dylan McKay in case he has any thoughts.
>>>
>>> Best,
>>>
>>> Alex
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190618/33b3dddf/attachment.html>