llvm dev - Jun 2015 - [LLVMdev] Legalizing SelectionDAGs with illegal pointer type

Hi,

I recently started helping with the LLVM AVR backend [1]. The AVR is an 8 bit
core with pointer type i16. That makes pointers illegal in the SelectionDAG. As
far as I understand it, it is the backends job to legalize these nodes by using
the ReplaceNodeResults/LowerOperation callbacks. Is that about right?

I have the feeling that the symbolic nodes carrying pointers, like FrameIndex
are special and I have no idea how to properly legalize them. Is that even
possible? Is it possible without modifying core LLVM? If it requires modifying
core would that be a welcome contribution?

One approach could be to build FrameIndex nodes with two result values instead
of one, providing the pointer as a pair. Does that make sense? I think in a way
it does since at least the AVR load/store instructions in fact use a register
pair. Has anybody been down that road?

For the curious the code I'm talking about is on a branch [2].

Thanks for your help,

d

[1] AVR backend: https://github.com/avr-llvm/llvm
[2] Pure 8 bit branch: https://github.com/avr-llvm/llvm/pull/129

> 
> Hi,
> 
> I recently started helping with the LLVM AVR backend [1]. The AVR is an 8
bit core with pointer type i16. That makes pointers illegal in the SelectionDAG.
As far as I understand it, it is the backends job to legalize these nodes by
using the ReplaceNodeResults/LowerOperation callbacks. Is that about right?
> 
> I have the feeling that the symbolic nodes carrying pointers, like
FrameIndex are special and I have no idea how to properly legalize them. Is that
even possible? Is it possible without modifying core LLVM? If it requires
modifying core would that be a welcome contribution?
> 
> One approach could be to build FrameIndex nodes with two result values
instead of one, providing the pointer as a pair. Does that make sense? I think
in a way it does since at least the AVR load/store instructions in fact use a
register pair. Has anybody been down that road?
This is a really interesting topic that I’m not sure anyone has quite
satisfactorily solved yet. It would be great to have an in-tree LLVM backend
with a non-legal pointer type so that solutions to these problems were more
likely to happen!

We maintain an out of tree backend for at least one target that has an i64
pointer type but for which i64 is illegal (much like AVR, 6502, etc).
Unfortunately, the solution is extremely ugly; it lowers loads and stores during
combine1 (before legalization), which is way less than ideal. It also uses
32-bit frameindexes (it treats the stack as 32-bit despite global pointers being
64-bit), so I don’t think that provides a usable template for a solution here,
unfortunately.

—escha

> On 27.06.2015, at 17:13, escha <escha at apple.com> wrote:
> 
>> 
>> Hi,
>> 
>> I recently started helping with the LLVM AVR backend [1]. The AVR is an
8 bit core with pointer type i16. That makes pointers illegal in the
SelectionDAG. As far as I understand it, it is the backends job to legalize
these nodes by using the ReplaceNodeResults/LowerOperation callbacks. Is that
about right?
>> 
>> I have the feeling that the symbolic nodes carrying pointers, like
FrameIndex are special and I have no idea how to properly legalize them. Is that
even possible? Is it possible without modifying core LLVM? If it requires
modifying core would that be a welcome contribution?
>> 
>> One approach could be to build FrameIndex nodes with two result values
instead of one, providing the pointer as a pair. Does that make sense? I think
in a way it does since at least the AVR load/store instructions in fact use a
register pair. Has anybody been down that road?
> 
> This is a really interesting topic that I’m not sure anyone has quite
satisfactorily solved yet. It would be great to have an in-tree LLVM backend
with a non-legal pointer type so that solutions to these problems were more
likely to happen!
Hm, yeah. I fear as long as there is no (good) way to write such a backend they
are simply not tree-worthy. So it’s a bit like the chicken and the egg.

Let’s skin this cat another way. Like, I’m not totally opposed to telling LLVM
about the register pair class. We just don’t want it to assume anything about
available operations. Instead we want to manually opt-in for certain ops only. I
had a quick stab at using the isTypeDesirableForOp(…) callback, making the
pointer type... very undesirable. But I still got i16 operations all over the
graph. So, one thing to do is to find out why that is not working as expected.

Another thing I noticed is that “Expand” internally has two meanings. Expand by
splitting and expand by using other operators. This distinction is currently
unreachable from the backend perspective. I have the feeling that most of the
tools we need are already there. We just need a little more control…

d
> 
> We maintain an out of tree backend for at least one target that has an i64
pointer type but for which i64 is illegal (much like AVR, 6502, etc).
Unfortunately, the solution is extremely ugly; it lowers loads and stores during
combine1 (before legalization), which is way less than ideal. It also uses
32-bit frameindexes (it treats the stack as 32-bit despite global pointers being
64-bit), so I don’t think that provides a usable template for a solution here,
unfortunately.
> 
> —escha

On 27 Jun 2015, at 16:13, escha <escha at apple.com>
wrote:
> 
>> 
>> Hi,
>> 
>> I recently started helping with the LLVM AVR backend [1]. The AVR is an
8 bit core with pointer type i16. That makes pointers illegal in the
SelectionDAG. As far as I understand it, it is the backends job to legalize
these nodes by using the ReplaceNodeResults/LowerOperation callbacks. Is that
about right?
>> 
>> I have the feeling that the symbolic nodes carrying pointers, like
FrameIndex are special and I have no idea how to properly legalize them. Is that
even possible? Is it possible without modifying core LLVM? If it requires
modifying core would that be a welcome contribution?
>> 
>> One approach could be to build FrameIndex nodes with two result values
instead of one, providing the pointer as a pair. Does that make sense? I think
in a way it does since at least the AVR load/store instructions in fact use a
register pair. Has anybody been down that road?
> 
> This is a really interesting topic that I’m not sure anyone has quite
satisfactorily solved yet. It would be great to have an in-tree LLVM backend
with a non-legal pointer type so that solutions to these problems were more
likely to happen!
> 
> We maintain an out of tree backend for at least one target that has an i64
pointer type but for which i64 is illegal (much like AVR, 6502, etc).
Unfortunately, the solution is extremely ugly; it lowers loads and stores during
combine1 (before legalization), which is way less than ideal. It also uses
32-bit frameindexes (it treats the stack as 32-bit despite global pointers being
64-bit), so I don’t think that provides a usable template for a solution here,
unfortunately.
If it would help, one of the changes that we’ve made is to add separate PTRADD,
INTTOPTR and PTRTOINT nodes to SelectionDAG, which makes it possible to keep
pointer types distinct.  We currently have an iFATPTR type, which is not ideal -
we’d like to replace this with a set of PTR32 to PTR256 types.  I’d be happy to
prioritise extracting these patches for upstreaming if that would be useful to
others.

David