llvm dev - Nov 2019 - Question about physical registers in ISel

To get into more detail, I'm trying to update WebAssembly's `call`
instruction. `call` is currently constrained to return one or zero
arguments, so in TableGen we have a separate call Instruction for each
possible return type. But I need to update calls to return arbitrarily many
values of any combination of WebAssembly types, so even if we imposed some
reasonable artificial limit like 8 return values, this approach would
require generating billions of Instructions in TableGen. So that won't work.

The other approach is to have just one call instruction that has variadic
outputs as well as inputs. This is the approach I am pursuing now, and I
have it working through the lowering to MachineSDNodes, but the approach is
breaking down in the InstrEmitter because it is trying to use physical
registers.

WebAssembly is a stack machine, so all instructions including calls push
their results onto the value stack as opposed to placing them in registers.
The value stack is not in memory and not addressable, so it is not the same
as the normal stack of call frames, which we also have. Instead, the value
stack takes the place of registers. The way we model the value stack is by
using virtual registers exclusively in the MachineInst layer, then
rearranging (i.e. "stackifying") the instructions and removing all
registers entirely right before lowering to MC. We skip register allocation
entirely, since WebAssembly does not have registers to allocate. We use
virtual registers instead of physical registers because the value stack can
contain an unbounded number of values.

In order to fit this modeling, I need a new virtual register to be
allocated for each def of the generalized call instruction. The
stackification passes in the WebAssembly backend will correctly interpret
this as the call's return values being pushed onto the value stack.

The other option I am considering would be to lower calls to contain a
chain of glued pseudo nodes that each explicitly defs a single register,
the collapsing that chain of nodes back into a single MachineInstruction
using a custom inserter hook. That seems similar to your suggestion of
using a pseudo, but I do still need to get just a single call
MachineInstruction after instruction selection. Using an ephemeral chain of
pseudo nodes seems like a hack, since it is working around a modeling
mismatch between the InstrEmitter and the WebAssembly backend.

To avoid that workaround, I would prefer to add a bit named something like
"implicitDefsAreVirtual" that I could just set for all WebAssembly
instructions. WebAssembly is the only upstream stack machine target, but
other downstream stack machine targets such as TON Labs' TVM have adopted
our approach of using virtual registers and would also benefit from having
such a bit.

On Tue, Nov 19, 2019 at 9:04 AM Quentin Colombet <qcolombet at apple.com>
wrote:
> Hi Thomas,
>
> If you know a specific instruction pushes a value on the stack and want to
> represent that as a virtual register (as opposed to a frame index for
> instance), you could use an explicit def with a pseudo that you later lower
> to your actual instruction with the stack access.
>
> I am not sold on the bit approach for now. It seems to me that we are
> working around a proper modeling. If you want to pursue with that approach,
> I would need more information on the semantic of that bit, how it is going
> to be used, what problem it solves and so on, to give a better opinion.
>
> Cheers,
> Q
>
> Le 18 nov. 2019 à 19:35, Thomas Lively <tlively at google.com> a
écrit :
>
> 
> Hi Quentin,
>
> Thanks, that explanation makes sense. I can see that in a normal register
> machine, implicitly defs must be physical registers. In a stack machine
> like WebAssembly, though, implicit defs are known to be pushed onto the
> value stack just like any other defs. Slots on the value stack are
> represented by virtual registers until stackification, so for WebAssembly
> we do need the implicit defs to be stored in virtual registers. I guess the
> best thing to do for now would be to add a bit to the MCInstrDesc carrying
> this information.
>
> Thomas
>
> On Mon, Nov 18, 2019 at 6:53 PM Quentin Colombet <qcolombet at
apple.com>
> wrote:
>
>> Hi Thomas,
>>
>> The reason is simply because an implicit def of a virtual register
>> doesn’t make sense in theory.
>>
>> The rationale is let say that an instruction implicitly defines a
virtual
>> register. The implicit aspect of it means that this information cannot
be
>> “seen”. Thus, when we finally emit the instruction, there is nothing in
the
>> encoding or anywhere that is going to tell where the value has been
>> physically defined.
>>
>> The only way something is implicitly defined is when everybody knows
>> where the value is going to end up and that’s only achievable in a
physical
>> register.
>>
>> Cheers,
>> -Quentin
>>
>> On Nov 18, 2019, at 6:21 PM, Thomas Lively via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>> Hi all,
>>
>> I need to figure out why InstrEmitter::EmitMachineNode assumes that
when
>> the number of outputs of a MachineSDNode is greater than the number of
defs
>> in the corresponding MCInstrDesc, the outputs in the difference will be
>> placed into physical registers as opposed to virtual registers.
>>
>> The specific line in question is:
>>     bool HasPhysRegOuts = NumResults > NumDefs &&
>> II.getImplicitDefs()!=nullptr;
>>
>> Where NumResults is the number of outputs in the MachineSDNode and
>> NumDefs comes from the MCInstrDesc and ultimately the TableGen
definition
>> of the instruction. I do not know why this assumption is made or what
code
>> depends on it, but it is over 12 years old:
>>
https://github.com/llvm/llvm-project/commit/c5549fc3a055710a3958a5b3164db3fa167c720c#diff-9dfdb934cb2b01ba001da4bbf3c5cb3cR632
>> .
>>
>> The context for this question is that I am trying to implement an
>> instruction for the WebAssembly backend that returns a variable number
of
>> operands. I am following the example of ARM's load multiple
instructions,
>> but this assertion in the instruction emitter is causing problems
because
>> WebAssembly, unlike ARM, does not use physical registers at all. Also,
>> almost all WebAssembly instructions have an implicit def of the
register
>> that represents the argument stack, so II.getImplicitDefs() is
necessarily
>> non-null.
>>
>> I am open to ideas about the best way forward. I am currently thinking
>> that if this assumption is important for most targets, I might need to
add
>> a new bit to MCInstrDesc to disable this assumption.
>> _______________________________________________
>> 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/20191119/56a0bce7/attachment.html>

It sounds to me that we should fix SDISel to accept both physical and virtual
definitions on variadic instructions. Though I wouldn’t bother adding the
support for implicit virtual definition.

I don’t think we need a bit to allow if we go that direction.
> On Nov 19, 2019, at 10:29 AM, Thomas Lively <tlively at google.com>
wrote:
> 
> To get into more detail, I'm trying to update WebAssembly's `call`
instruction. `call` is currently constrained to return one or zero arguments, so
in TableGen we have a separate call Instruction for each possible return type.
But I need to update calls to return arbitrarily many values of any combination
of WebAssembly types, so even if we imposed some reasonable artificial limit
like 8 return values, this approach would require generating billions of
Instructions in TableGen. So that won't work.
> 
> The other approach is to have just one call instruction that has variadic
outputs as well as inputs. This is the approach I am pursuing now, and I have it
working through the lowering to MachineSDNodes, but the approach is breaking
down in the InstrEmitter because it is trying to use physical registers.
> 
> WebAssembly is a stack machine, so all instructions including calls push
their results onto the value stack as opposed to placing them in registers. The
value stack is not in memory and not addressable, so it is not the same as the
normal stack of call frames, which we also have. Instead, the value stack takes
the place of registers. The way we model the value stack is by using virtual
registers exclusively in the MachineInst layer, then rearranging (i.e.
"stackifying") the instructions and removing all registers entirely
right before lowering to MC. We skip register allocation entirely, since
WebAssembly does not have registers to allocate. We use virtual registers
instead of physical registers because the value stack can contain an unbounded
number of values.
> 
> In order to fit this modeling, I need a new virtual register to be
allocated for each def of the generalized call instruction. The stackification
passes in the WebAssembly backend will correctly interpret this as the
call's return values being pushed onto the value stack.
> 
> The other option I am considering would be to lower calls to contain a
chain of glued pseudo nodes that each explicitly defs a single register, the
collapsing that chain of nodes back into a single MachineInstruction using a
custom inserter hook. That seems similar to your suggestion of using a pseudo,
but I do still need to get just a single call MachineInstruction after
instruction selection. Using an ephemeral chain of pseudo nodes seems like a
hack, since it is working around a modeling mismatch between the InstrEmitter
and the WebAssembly backend.
> 
> To avoid that workaround, I would prefer to add a bit named something like
"implicitDefsAreVirtual" that I could just set for all WebAssembly
instructions. WebAssembly is the only upstream stack machine target, but other
downstream stack machine targets such as TON Labs' TVM have adopted our
approach of using virtual registers and would also benefit from having such a
bit.
> 
> On Tue, Nov 19, 2019 at 9:04 AM Quentin Colombet <qcolombet at apple.com
<mailto:qcolombet at apple.com>> wrote:
> Hi Thomas,
> 
> If you know a specific instruction pushes a value on the stack and want to
represent that as a virtual register (as opposed to a frame index for instance),
you could use an explicit def with a pseudo that you later lower to your actual
instruction with the stack access.
> 
> I am not sold on the bit approach for now. It seems to me that we are
working around a proper modeling. If you want to pursue with that approach, I
would need more information on the semantic of that bit, how it is going to be
used, what problem it solves and so on, to give a better opinion.
> 
> Cheers,
> Q
> 
>> Le 18 nov. 2019 à 19:35, Thomas Lively <tlively at google.com
<mailto:tlively at google.com>> a écrit :
>> 
>> 
>> Hi Quentin,
>> 
>> Thanks, that explanation makes sense. I can see that in a normal
register machine, implicitly defs must be physical registers. In a stack machine
like WebAssembly, though, implicit defs are known to be pushed onto the value
stack just like any other defs. Slots on the value stack are represented by
virtual registers until stackification, so for WebAssembly we do need the
implicit defs to be stored in virtual registers. I guess the best thing to do
for now would be to add a bit to the MCInstrDesc carrying this information.
>> 
>> Thomas
>> 
>> On Mon, Nov 18, 2019 at 6:53 PM Quentin Colombet <qcolombet at
apple.com <mailto:qcolombet at apple.com>> wrote:
>> Hi Thomas,
>> 
>> The reason is simply because an implicit def of a virtual register
doesn’t make sense in theory.
>> 
>> The rationale is let say that an instruction implicitly defines a
virtual register. The implicit aspect of it means that this information cannot
be “seen”. Thus, when we finally emit the instruction, there is nothing in the
encoding or anywhere that is going to tell where the value has been physically
defined.
>> 
>> The only way something is implicitly defined is when everybody knows
where the value is going to end up and that’s only achievable in a physical
register.
>> 
>> Cheers,
>> -Quentin
>> 
>>> On Nov 18, 2019, at 6:21 PM, Thomas Lively via llvm-dev
<llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>
wrote:
>>> 
>>> Hi all,
>>> 
>>> I need to figure out why InstrEmitter::EmitMachineNode assumes that
when the number of outputs of a MachineSDNode is greater than the number of defs
in the corresponding MCInstrDesc, the outputs in the difference will be placed
into physical registers as opposed to virtual registers.
>>> 
>>> The specific line in question is:
>>>     bool HasPhysRegOuts = NumResults > NumDefs &&
II.getImplicitDefs()!=nullptr;
>>> 
>>> Where NumResults is the number of outputs in the MachineSDNode and
NumDefs comes from the MCInstrDesc and ultimately the TableGen definition of the
instruction. I do not know why this assumption is made or what code depends on
it, but it is over 12 years old:
https://github.com/llvm/llvm-project/commit/c5549fc3a055710a3958a5b3164db3fa167c720c#diff-9dfdb934cb2b01ba001da4bbf3c5cb3cR632
<https://github.com/llvm/llvm-project/commit/c5549fc3a055710a3958a5b3164db3fa167c720c#diff-9dfdb934cb2b01ba001da4bbf3c5cb3cR632>.
>>> 
>>> The context for this question is that I am trying to implement an
instruction for the WebAssembly backend that returns a variable number of
operands. I am following the example of ARM's load multiple instructions,
but this assertion in the instruction emitter is causing problems because
WebAssembly, unlike ARM, does not use physical registers at all. Also, almost
all WebAssembly instructions have an implicit def of the register that
represents the argument stack, so II.getImplicitDefs() is necessarily non-null.
>>> 
>>> I am open to ideas about the best way forward. I am currently
thinking that if this assumption is important for most targets, I might need to
add a new bit to MCInstrDesc to disable this assumption.
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>
>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<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/20191119/95f42e0f/attachment.html>

Can you elaborate on the fix you are thinking of? I'm not sure what
you're
thinking should change.

On Tue, Nov 19, 2019 at 3:51 PM Quentin Colombet <qcolombet at apple.com>
wrote:
> It sounds to me that we should fix SDISel to accept both physical and
> virtual definitions on variadic instructions. Though I wouldn’t bother
> adding the support for implicit virtual definition.
>
> I don’t think we need a bit to allow if we go that direction.
>
> On Nov 19, 2019, at 10:29 AM, Thomas Lively <tlively at google.com>
wrote:
>
> To get into more detail, I'm trying to update WebAssembly's `call`
> instruction. `call` is currently constrained to return one or zero
> arguments, so in TableGen we have a separate call Instruction for each
> possible return type. But I need to update calls to return arbitrarily many
> values of any combination of WebAssembly types, so even if we imposed some
> reasonable artificial limit like 8 return values, this approach would
> require generating billions of Instructions in TableGen. So that won't
work.
>
> The other approach is to have just one call instruction that has variadic
> outputs as well as inputs. This is the approach I am pursuing now, and I
> have it working through the lowering to MachineSDNodes, but the approach is
> breaking down in the InstrEmitter because it is trying to use physical
> registers.
>
> WebAssembly is a stack machine, so all instructions including calls push
> their results onto the value stack as opposed to placing them in registers.
> The value stack is not in memory and not addressable, so it is not the same
> as the normal stack of call frames, which we also have. Instead, the value
> stack takes the place of registers. The way we model the value stack is by
> using virtual registers exclusively in the MachineInst layer, then
> rearranging (i.e. "stackifying") the instructions and removing
all
> registers entirely right before lowering to MC. We skip register allocation
> entirely, since WebAssembly does not have registers to allocate. We use
> virtual registers instead of physical registers because the value stack can
> contain an unbounded number of values.
>
> In order to fit this modeling, I need a new virtual register to be
> allocated for each def of the generalized call instruction. The
> stackification passes in the WebAssembly backend will correctly interpret
> this as the call's return values being pushed onto the value stack.
>
> The other option I am considering would be to lower calls to contain a
> chain of glued pseudo nodes that each explicitly defs a single register,
> the collapsing that chain of nodes back into a single MachineInstruction
> using a custom inserter hook. That seems similar to your suggestion of
> using a pseudo, but I do still need to get just a single call
> MachineInstruction after instruction selection. Using an ephemeral chain of
> pseudo nodes seems like a hack, since it is working around a modeling
> mismatch between the InstrEmitter and the WebAssembly backend.
>
> To avoid that workaround, I would prefer to add a bit named something like
> "implicitDefsAreVirtual" that I could just set for all
WebAssembly
> instructions. WebAssembly is the only upstream stack machine target, but
> other downstream stack machine targets such as TON Labs' TVM have
adopted
> our approach of using virtual registers and would also benefit from having
> such a bit.
>
> On Tue, Nov 19, 2019 at 9:04 AM Quentin Colombet <qcolombet at
apple.com>
> wrote:
>
>> Hi Thomas,
>>
>> If you know a specific instruction pushes a value on the stack and want
>> to represent that as a virtual register (as opposed to a frame index
for
>> instance), you could use an explicit def with a pseudo that you later
lower
>> to your actual instruction with the stack access.
>>
>> I am not sold on the bit approach for now. It seems to me that we are
>> working around a proper modeling. If you want to pursue with that
approach,
>> I would need more information on the semantic of that bit, how it is
going
>> to be used, what problem it solves and so on, to give a better opinion.
>>
>> Cheers,
>> Q
>>
>> Le 18 nov. 2019 à 19:35, Thomas Lively <tlively at google.com> a
écrit :
>>
>> 
>> Hi Quentin,
>>
>> Thanks, that explanation makes sense. I can see that in a normal
register
>> machine, implicitly defs must be physical registers. In a stack machine
>> like WebAssembly, though, implicit defs are known to be pushed onto the
>> value stack just like any other defs. Slots on the value stack are
>> represented by virtual registers until stackification, so for
WebAssembly
>> we do need the implicit defs to be stored in virtual registers. I guess
the
>> best thing to do for now would be to add a bit to the MCInstrDesc
carrying
>> this information.
>>
>> Thomas
>>
>> On Mon, Nov 18, 2019 at 6:53 PM Quentin Colombet <qcolombet at
apple.com>
>> wrote:
>>
>>> Hi Thomas,
>>>
>>> The reason is simply because an implicit def of a virtual register
>>> doesn’t make sense in theory.
>>>
>>> The rationale is let say that an instruction implicitly defines a
>>> virtual register. The implicit aspect of it means that this
information
>>> cannot be “seen”. Thus, when we finally emit the instruction, there
is
>>> nothing in the encoding or anywhere that is going to tell where the
value
>>> has been physically defined.
>>>
>>> The only way something is implicitly defined is when everybody
knows
>>> where the value is going to end up and that’s only achievable in a
physical
>>> register.
>>>
>>> Cheers,
>>> -Quentin
>>>
>>> On Nov 18, 2019, at 6:21 PM, Thomas Lively via llvm-dev <
>>> llvm-dev at lists.llvm.org> wrote:
>>>
>>> Hi all,
>>>
>>> I need to figure out why InstrEmitter::EmitMachineNode assumes that
when
>>> the number of outputs of a MachineSDNode is greater than the number
of defs
>>> in the corresponding MCInstrDesc, the outputs in the difference
will be
>>> placed into physical registers as opposed to virtual registers.
>>>
>>> The specific line in question is:
>>>     bool HasPhysRegOuts = NumResults > NumDefs &&
>>> II.getImplicitDefs()!=nullptr;
>>>
>>> Where NumResults is the number of outputs in the MachineSDNode and
>>> NumDefs comes from the MCInstrDesc and ultimately the TableGen
definition
>>> of the instruction. I do not know why this assumption is made or
what code
>>> depends on it, but it is over 12 years old:
>>>
https://github.com/llvm/llvm-project/commit/c5549fc3a055710a3958a5b3164db3fa167c720c#diff-9dfdb934cb2b01ba001da4bbf3c5cb3cR632
>>> .
>>>
>>> The context for this question is that I am trying to implement an
>>> instruction for the WebAssembly backend that returns a variable
number of
>>> operands. I am following the example of ARM's load multiple
instructions,
>>> but this assertion in the instruction emitter is causing problems
because
>>> WebAssembly, unlike ARM, does not use physical registers at all.
Also,
>>> almost all WebAssembly instructions have an implicit def of the
register
>>> that represents the argument stack, so II.getImplicitDefs() is
necessarily
>>> non-null.
>>>
>>> I am open to ideas about the best way forward. I am currently
thinking
>>> that if this assumption is important for most targets, I might need
to add
>>> a new bit to MCInstrDesc to disable this assumption.
>>> _______________________________________________
>>> 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/20191119/285b419b/attachment.html>