llvm dev - Jul 2019 - Glue to connect two nodes in LLVM backend

Hello everyone,

I wanted to attach a node without affecting the present nodes in any way. I
tried to use MVT::Glue for that but I think I'm missing something as I
could not achieve the below state.

LUI                         LUI
  |                             |
ADDI ----GLUE---- ADDI
  |
store

I've few question about this and Glue node in general, I'll be happy to
get
some help on this :)
1. Is Gluing the right approach or there is something better for such use
case?
2. If I do something like DAG.getNode(ISD::ADDI, DL, MVT::Glue, LUINode,
OtherADDINode). How will it know that the other ADDI node should be glued
and not LUI. I seriously feel I'm missing something.

Many thanks,
Reshabh
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190711/7a7b34d4/attachment.html>

Hi Reshabh

I was able to implement a custom backend for a particular architecture but
I'm unsure if I understand your question. What you mean by “LUI”?. Also I
think there’s no "ISD:ADDI” (?).

The third parameter of the DAG.getNode is the result type. If the node has a
single result you can specify a simple MVT, otherwise you must create a SDVTList
by calling DAG.getVTList.  In your example you set the result of the DAG.getNode
to be a MVT:Glue, but there’s no other result that you can use. I assume this is
not what you want. The input types are given by the nodes that you pass as
operands. Nodes with a glue only result are useful to implement things such as
compare instructions that do not produce regular values. However, even in this
case it is generally better to just add the flags as the instruction output and
forget about the glue.

You can connect nodes in any way you want. Nodes can have input glues and output
glues. Gluing nodes means that they will be executed in a defined order, but you
should not need to do so if you already have regular values that you can connect
in the way that will do what you want.

John

> On 11 Jul 2019, at 19:53, Reshabh Sharma via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hello everyone,
> 
> I wanted to attach a node without affecting the present nodes in any way. I
tried to use MVT::Glue for that but I think I'm missing something as I could
not achieve the below state.
> 
> LUI                         LUI
>   |                             |
> ADDI ----GLUE---- ADDI 
>   |
> store
> 
> I've few question about this and Glue node in general, I'll be
happy to get some help on this :)
> 1. Is Gluing the right approach or there is something better for such use
case?
> 2. If I do something like DAG.getNode(ISD::ADDI, DL, MVT::Glue, LUINode,
OtherADDINode). How will it know that the other ADDI node should be glued and
not LUI. I seriously feel I'm missing something.
> 
> Many thanks,
> Reshabh
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

On Thu, 11 Jul 2019 at 18:53, Reshabh Sharma via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> 1. Is Gluing the right approach or there is something better for such use
case?
I would expect the store to take an i64 operand as its address
(otherwise, in just what sense are your pointers 64-bit?), and
wouldn't expect to need glue at all.

There are two key legalization steps here:

1. Taking an i64:GlobalAddress and converting it into an
ISD::BUILD_PAIR of two nodes computing the low & high 32-bits of the
address.
2. Whatever replaces the store splitting its 64-bit pointer operand
into 2 32-bit values (via the inverse, ISD::EXTRACT_ELEMENT).

The combiner will eliminate the extra nodes from these steps, leading
to a single customized store taking two well-defined 32-bit operands.
All values would be tracked directly, and not need glue to convey a
side-channel of information. I think trying to use glue is misguided.
> 2. If I do something like DAG.getNode(ISD::ADDI, DL, MVT::Glue, LUINode,
OtherADDINode). How will it know that the other ADDI node should be glued and
not LUI. I seriously feel I'm missing something.
Again, I don't think Glue applies here, but I will try to describe how
it *is* used elsewhere a little...

If two nodes need glueing, that information is conveyed via a special
extra operand of type MVT::Glue. Some nodes produce this in addition
to their real outputs, and others consume it in addition to their real
inputs. Implementation-wise in your case you'd:

1. Create the OtherADDI node with an extra[*] output type MVT::Glue
beyond what would be expected (it should be the last output type).
2. Add that particular edge as an extra input (aside from the normal
inputs) to the ADDI you're creating now. If it's a duplicate, that
probably means you didn't need the glue in the first place because
normal dependency tracking would handle the situation. Otherwise, your
node now has an extra MVT::Glue edge that tracks this hidden
dependency. The glue should also be the last operand.

You also have to declare this kind of relationship in TableGen if
you're planning to use these nodes there, via SDNPInGlue and
SDNPOutGlue.

Cheers.

Tim.

[*] I wouldn't be surprised if this meant you needed a new
ISD::ADDIWithGlue instead. I haven't done it in years, but you should
be prepared in case a single node with two different output profiles
is more than LLVM can cope with.

On Fri, Jul 12, 2019 at 1:28 AM Joan Lluch <joan.lluch at icloud.com>
wrote:
> Hi Reshabh
>
> I was able to implement a custom backend for a particular architecture but
> I'm unsure if I understand your question. What you mean by “LUI”?. Also
I
> think there’s no "ISD:ADDI” (?).

Sorry, my bad. LUI and ADDI are present in RISCV ISA.

>
>
The third parameter of the DAG.getNode is the result type. If the node
has
> a single result you can specify a simple MVT, otherwise you must create a
> SDVTList by calling DAG.getVTList.  In your example you set the result of
> the DAG.getNode to be a MVT:Glue, but there’s no other result that you can
> use. I assume this is not what you want. The input types are given by the
> nodes that you pass as operands. Nodes with a glue only result are useful
> to implement things such as compare instructions that do not produce
> regular values. However, even in this case it is generally better to just
> add the flags as the instruction output and forget about the glue.
>
> You can connect nodes in any way you want. Nodes can have input glues and
> output glues. Gluing nodes means that they will be executed in a defined
> order, but you should not need to do so if you already have regular values
> that you can connect in the way that will do what you want.
>
Many thanks Joan, I was not aware about the SDVTList. After knowing more
about MVT::Glue, I guess we might not need it and either a wrapper or as
you said connecting them will just work.

John
>
>
> > On 11 Jul 2019, at 19:53, Reshabh Sharma via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
> >
> > Hello everyone,
> >
> > I wanted to attach a node without affecting the present nodes in any
> way. I tried to use MVT::Glue for that but I think I'm missing
something as
> I could not achieve the below state.
> >
> > LUI                         LUI
> >   |                             |
> > ADDI ----GLUE---- ADDI
> >   |
> > store
> >
> > I've few question about this and Glue node in general, I'll be
happy to
> get some help on this :)
> > 1. Is Gluing the right approach or there is something better for such
> use case?
> > 2. If I do something like DAG.getNode(ISD::ADDI, DL, MVT::Glue,
LUINode,
> OtherADDINode). How will it know that the other ADDI node should be glued
> and not LUI. I seriously feel I'm missing something.
> >
> > Many thanks,
> > Reshabh
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190716/64d0d3ba/attachment.html>

Sorry Tim, I clicked on reply instead of reply all.

On Fri, Jul 12, 2019 at 2:15 AM Tim Northover <t.p.northover at gmail.com>
wrote:
> On Thu, 11 Jul 2019 at 18:53, Reshabh Sharma via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> > 1. Is Gluing the right approach or there is something better for such
> use case?
>
> I would expect the store to take an i64 operand as its address
> (otherwise, in just what sense are your pointers 64-bit?), and
> wouldn't expect to need glue at all.
>
I think we might not need a i64 operand at all (won't they be pain during
the legalization as we are working on RV32), as we plan to introduce new
load/store like NEW_STORE rd rs1 rs2 (where rs1 has lower 32 bits of 64 bit
address and rs2 have higher 32 bits).
>
> There are two key legalization steps here:
>
> 1. Taking an i64:GlobalAddress and converting it into an
> ISD::BUILD_PAIR of two nodes computing the low & high 32-bits of the
> address.
>
The use of BUILD_PAIR sounds really promising (I was considering to use a
custom wrapper node to do the same thing). I took some time to try to make
it work but I guess the legalizer fails after seeing a node with result
type i64. I tried to be sure about it but it does not fail when it tries to
legalize the BUILD_PAIR node with return type i64 instead it fails when it
try to legalize the store node having this as an operand.

When I tried to replace BUILD_PAIR with a WRAPPER node which does the same
thing but had a return type MVT::Glue (I was not sure so just used this,
MVT::Other might be a better option?). Something like this,
t16: i32 = ADDI t15, ...
t20: i32 = ADDI t19, ...
t21: glue = RISCVISD::WRAPPER t16, t20
This passed the legalizer and failed at the instruction selection (which it
should).

What do you think about it? I think the reason for failure (using
BUILD_PAIR) is the i64 result which is not legal so the codegen tries to
expand it over store, in which it fails as it does not know how to do that.

2. Whatever replaces the store splitting its 64-bit pointer
operand
> into 2 32-bit values (via the inverse, ISD::EXTRACT_ELEMENT).
>
> The combiner will eliminate the extra nodes from these steps, leading
> to a single customized store taking two well-defined 32-bit operands.
> All values would be tracked directly, and not need glue to convey a
> side-channel of information. I think trying to use glue is misguided.
>
Yes, now I agree that this is a far better way to deal with it.

>
> > 2. If I do something like DAG.getNode(ISD::ADDI, DL, MVT::Glue,
LUINode,
> OtherADDINode). How will it know that the other ADDI node should be glued
> and not LUI. I seriously feel I'm missing something.
>
> Again, I don't think Glue applies here, but I will try to describe how
> it *is* used elsewhere a little...
>
> If two nodes need glueing, that information is conveyed via a special
> extra operand of type MVT::Glue. Some nodes produce this in addition
> to their real outputs, and others consume it in addition to their real
> inputs. Implementation-wise in your case you'd:
>
> 1. Create the OtherADDI node with an extra[*] output type MVT::Glue
> beyond what would be expected (it should be the last output type).
> 2. Add that particular edge as an extra input (aside from the normal
> inputs) to the ADDI you're creating now. If it's a duplicate, that
> probably means you didn't need the glue in the first place because
> normal dependency tracking would handle the situation. Otherwise, your
> node now has an extra MVT::Glue edge that tracks this hidden
> dependency. The glue should also be the last operand.
>
> You also have to declare this kind of relationship in TableGen if
> you're planning to use these nodes there, via SDNPInGlue and
> SDNPOutGlue.
>
>
Million thanks Tim, I was not aware about quite a many things. I'm happy I
got to know new things. The BUILD_PAIR approach looks a lot cleaner than
the Glue one.

On Fri, Jul 12, 2019 at 2:15 AM Tim Northover <t.p.northover at gmail.com>
wrote:
> On Thu, 11 Jul 2019 at 18:53, Reshabh Sharma via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> > 1. Is Gluing the right approach or there is something better for such
> use case?
>
> I would expect the store to take an i64 operand as its address
> (otherwise, in just what sense are your pointers 64-bit?), and
> wouldn't expect to need glue at all.
>
> There are two key legalization steps here:
>
> 1. Taking an i64:GlobalAddress and converting it into an
> ISD::BUILD_PAIR of two nodes computing the low & high 32-bits of the
> address.
> 2. Whatever replaces the store splitting its 64-bit pointer operand
> into 2 32-bit values (via the inverse, ISD::EXTRACT_ELEMENT).
>
> The combiner will eliminate the extra nodes from these steps, leading
> to a single customized store taking two well-defined 32-bit operands.
> All values would be tracked directly, and not need glue to convey a
> side-channel of information. I think trying to use glue is misguided.
>
> > 2. If I do something like DAG.getNode(ISD::ADDI, DL, MVT::Glue,
LUINode,
> OtherADDINode). How will it know that the other ADDI node should be glued
> and not LUI. I seriously feel I'm missing something.
>
> Again, I don't think Glue applies here, but I will try to describe how
> it *is* used elsewhere a little...
>
> If two nodes need glueing, that information is conveyed via a special
> extra operand of type MVT::Glue. Some nodes produce this in addition
> to their real outputs, and others consume it in addition to their real
> inputs. Implementation-wise in your case you'd:
>
> 1. Create the OtherADDI node with an extra[*] output type MVT::Glue
> beyond what would be expected (it should be the last output type).
> 2. Add that particular edge as an extra input (aside from the normal
> inputs) to the ADDI you're creating now. If it's a duplicate, that
> probably means you didn't need the glue in the first place because
> normal dependency tracking would handle the situation. Otherwise, your
> node now has an extra MVT::Glue edge that tracks this hidden
> dependency. The glue should also be the last operand.
>
> You also have to declare this kind of relationship in TableGen if
> you're planning to use these nodes there, via SDNPInGlue and
> SDNPOutGlue.
>
> Cheers.
>
> Tim.
>
> [*] I wouldn't be surprised if this meant you needed a new
> ISD::ADDIWithGlue instead. I haven't done it in years, but you should
> be prepared in case a single node with two different output profiles
> is more than LLVM can cope with.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190716/d4efefb3/attachment.html>

On Tue, 16 Jul 2019 at 16:24, Reshabh Sharma <reshabhsh at gmail.com>
wrote:
>> I would expect the store to take an i64 operand as its address
>> (otherwise, in just what sense are your pointers 64-bit?), and
>> wouldn't expect to need glue at all.
>
> I think we might not need a i64 operand at all (won't they be pain
during the legalization as we are working on RV32), as we plan to introduce new
load/store like NEW_STORE rd rs1 rs2 (where rs1 has lower 32 bits of 64 bit
address and rs2 have higher 32 bits).
That makes sense, and should interact well with the pair/extract idiom
(with some minor annoyance to create those stores taking two sources).
> The use of BUILD_PAIR sounds really promising (I was considering to use a
custom wrapper node to do the same thing). I took some time to try to make it
work but I guess the legalizer fails after seeing a node with result type i64. I
tried to be sure about it but it does not fail when it tries to legalize the
BUILD_PAIR node with return type i64 instead it fails when it try to legalize
the store node having this as an operand.
> What do you think about it? I think the reason for failure (using
BUILD_PAIR) is the i64 result which is not legal so the codegen tries to expand
it over store, in which it fails as it does not know how to do that.
If it's not feeding directly into an EXTRACT of the usual i64 ->
(i32,i32) type legalization[*] kind (I think EXTRACT_ELEMENT) then I
would expect failure. So you need to replace your store with the
custom RS1, RS2 variant at the type legalization phase. That's very
early, and might not even have hooks. If you're finding that then the
first DAG-combine phase runs before type legalization, and definitely
can be hooked to replace all stores with your custom node.

Cheers.

Tim.

[*] In case this term isn't familiar, the sequence of DAG phases goes
something like:

Combine 1 -> Type legalization -> Combine 2 -> Legalization ->
Selection

After type legalization (for you) *nothing* should have type i64, so
if you need to replace things you have to do it before then. I believe
a part of type legalization will fold BUILD_PAIR/EXTRACT_ELEMENT pairs
to eliminate incidental/trivial i64s.

Million thanks Tim, your replies always take us to a better and much
cleaner approach.

On Wed, Jul 17, 2019 at 12:47 AM Tim Northover <t.p.northover at
gmail.com>
wrote:
> On Tue, 16 Jul 2019 at 16:24, Reshabh Sharma <reshabhsh at gmail.com>
wrote:
> >> I would expect the store to take an i64 operand as its address
> >> (otherwise, in just what sense are your pointers 64-bit?), and
> >> wouldn't expect to need glue at all.
> >
> > I think we might not need a i64 operand at all (won't they be pain
> during the legalization as we are working on RV32), as we plan to introduce
> new load/store like NEW_STORE rd rs1 rs2 (where rs1 has lower 32 bits of 64
> bit address and rs2 have higher 32 bits).
>
> That makes sense, and should interact well with the pair/extract idiom
> (with some minor annoyance to create those stores taking two sources).
>
> > The use of BUILD_PAIR sounds really promising (I was considering to
use
> a custom wrapper node to do the same thing). I took some time to try to
> make it work but I guess the legalizer fails after seeing a node with
> result type i64. I tried to be sure about it but it does not fail when it
> tries to legalize the BUILD_PAIR node with return type i64 instead it fails
> when it try to legalize the store node having this as an operand.
>
> > What do you think about it? I think the reason for failure (using
> BUILD_PAIR) is the i64 result which is not legal so the codegen tries to
> expand it over store, in which it fails as it does not know how to do that.
>
> If it's not feeding directly into an EXTRACT of the usual i64 ->
> (i32,i32) type legalization[*] kind (I think EXTRACT_ELEMENT) then I
> would expect failure. So you need to replace your store with the
> custom RS1, RS2 variant at the type legalization phase. That's very
> early, and might not even have hooks. If you're finding that then the
> first DAG-combine phase runs before type legalization, and definitely
> can be hooked to replace all stores with your custom node.
>
> Yeah this seems far better, we should be doing this already. Last week
(after reading your reply) I tried to do this at the type legalization
phase. I could successfully replace store node with the custom store (but
things didn't go well).
I am replacing the following store node:

ch = store<(store 4 into `i32 addrspace(1)* getelementptr inbounds ([1 x
i32], [1 x i32] addrspace(1)* @foo, i32 0, i32 0)`, addrspace 1)> t4,
Constant:i32<87>, GlobalAddress:i64<[1 x i32] addrspace(1)* @foo> 0,
undef:i64

where,
t4 : ch = store<(store 4 into %ir.retval)> t0, Constant:i32<0>,
FrameIndex:i32<0>, undef:i32
t0 : ch = EntryToken

into:

ch = CUSTOM_STORE Constant:i32<87>, tx, ty, t4

where tx and ty are ADDI for Hi and Lo.

If I don't keep t4 in the operand list, it fails at second DAG combiner
phase, saying entry node not found. I found your reply on a thread about
chaining loads and stores(
http://lists.llvm.org/pipermail/llvm-dev/2017-June/114783.html) and it
makes some sense to me that we need to have the custom store chained as it
was before(?) and when I tried that, it failed an assertion at the end of
scheduler, saying "#operands for dag node doesn't match .td file!"
(This
makes some sense to me, as per .td file it should have three operand not
four(?)). Can you please suggest something for this, I don't have any
backup plan to make this work (I'm stuck).

SelectionDAG after instruction selection (Line 11 has the CUSTOM_STORE)

   1.   t0: ch = EntryToken
   2.       t5: i32 = ADDI Register:i32 $x0, TargetConstant:i32<4>
   3.         t34: i32,ch = CopyFromReg t0, Register:i32 $x0
   4.       t4: ch = SW<Mem:(store 4 into %ir.retval)> t34,
   TargetFrameIndex:i32<0>, TargetConstant:i32<0>, t0
   5.     t7: ch = SW<Mem:(store 4 into %ir.a)> t5,
   TargetFrameIndex:i32<1>, TargetConstant:i32<0>, t4
   6.     t8: i32 = ADDI Register:i32 $x0, TargetConstant:i32<87>
   7.       t19: i32 = LUI TargetGlobalAddress:i32<[1 x i32] addrspace(1)*
   @foo> 0 [TF=2]
   8.     t20: i32 = ADDI t19, TargetGlobalAddress:i32<[1 x i32]
   addrspace(1)* @foo> 0 [TF=3]
   9.       t23: i32 = LUI TargetGlobalAddress:i32<[1 x i32] addrspace(1)*
   @foo> 0 [TF=4]
   10.     t24: i32 = ADDI t23, TargetGlobalAddress:i32<[1 x i32]
   addrspace(1)* @foo> 0 [TF=1]
   11.   t27: ch = CUSTOM_STORE t8, t20, t24, t7
   12.     t13: i32,ch = LW<Mem:(dereferenceable load 4 from %ir.a)>
   TargetFrameIndex:i32<1>, TargetConstant:i32<0>, t27
   13.   t15: ch,glue = CopyToReg t27, Register:i32 $x10, t13
   14.   t16: ch = PseudoRET Register:i32 $x10, t15, t15:1



Cheers.
>
> Tim.
>
> [*] In case this term isn't familiar, the sequence of DAG phases goes
> something like:
>
> Combine 1 -> Type legalization -> Combine 2 -> Legalization ->
Selection
>
> After type legalization (for you) *nothing* should have type i64, so
> if you need to replace things you have to do it before then. I believe
> a part of type legalization will fold BUILD_PAIR/EXTRACT_ELEMENT pairs
> to eliminate incidental/trivial i64s.
>
Many thanks
Reshabh
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190722/b8b49613/attachment.html>