[llvm-dev] Question about physical registers in ISel

Tue Nov 19 16:22:10 PST 2019

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>