Early-clobber constraint in TableGen

All,

I've attached a small patch that adds a new early-clobber operand constraint option to TableGen and would like to get feedback before proceding.

As background, the ARM store-exclusive instruction (STREX) stores a success result code in a register operand, and that register cannot be the same register as either the source of the value to be stored, or the base address. Specifically.
   STREX Rd, Rm, [Rn] // Store Rm to the address contained in Rn, store zero in Rd if successful, one in Rd if not.
If Rd == Rm or Rd == Rn, the behaviour is undefined.

To model this, we need to be able to specify in the tablegen instruction description that Rd is an early-clobber register so that the allocator will not use the same register for it as for Rm or Rn.

The syntax is simple:

contraint-list: constraint-list ',' constraint
   > constraint

constraint: '@early' operand
  > operand '=' operand

operand: '$' identifier

MachineIntr::addOperand() checks the target instruction description for the constraint when adding register operands and sets IsEarlyClobber if it's present.

For a usage example, I've included in the patch the modification to use the constraint for the STREX ARM instruction.

Thoughts?

Thanks in advance!

-Jim

early.patch (5.59 KB)

For a usage example, I've included in the patch the modification to
use the constraint for the STREX ARM instruction.

Your example is:

constraints = "@early $success"

Why not spell it as:

constraints = "$success != $src", "$success != $ptr"

The grammar would change to something like:

constraint: operand '!=' operand
  > operand '=' operand

This seems more intuitive and more generally applicable. I could see a use
for this in other architectures. From reading your example, without the
background I wouldn't know what "@early" means.

It may be slightly more difficult to code up for TableGen but in the long
term it's worth it.

                            -Dave

For a usage example, I’ve included in the patch the modification to

use the constraint for the STREX ARM instruction.

Your example is:

constraints = “@early $success”

Why not spell it as:

constraints = “$success != $src”, “$success != $ptr”

This was my first thought as well; however, I decided against it. I think it’s best, at least for now, to expose an interface in tablegen to express the early-clobber semantics that the back-end already supports rather than adding something completely new.

Doing more would require significantly surgery on both tablegen and the register allocation framework to support. The handling of early-clobber register definitions is already in place in the allocator, and this approach simply provides a means of specifying it in the tablegen files. I think that’s likely something we’d want separately from a more general purpose solution in any case, as it’s analogous to the inline assembler ‘&’ constraint, for example.

Do you have specific examples in mind that would be expressible with something more complicated that aren’t handleable via an early-clobber constraint?

The grammar would change to something like:

constraint: operand ‘!=’ operand

operand ‘=’ operand

This seems more intuitive and more generally applicable. I could see a use
for this in other architectures. From reading your example, without the
background I wouldn’t know what “@early” means.

Perhaps spelling it out more fully with “earlyclobber” rather than “early” would help?

Thanks for the feedback!

-Jim

Do you have specific examples in mind that would be expressible with
something more complicated that aren't handleable via an early-clobber
constraint?

Not offhand, no. I'm mostly concerned about the readability of .td files.

Perhaps spelling it out more fully with "earlyclobber" rather than
"early" would help?

That's better. Is there any way you could convince TableGen to recognize
that 'constraints = "$success != $src", "$success != $ptr"' is semantically
equivalent to earlyclobber? Maybe check that the common operand in both
contraints is declared to interfere with all other operands and if that's
so, mark it earlyclobber.

When I'm writing .td files I really don't want to be concerned with the
nitty-gritty details of how the backend is implemented. I just want to
express the semantics I want. I think that was the motivation for the
switch from isThreeAddress to "$src = $dst."

I have no objection going with "earlyclobber" initially but we should think
about ways to abstract codegen semantics whenever we can. If we can replace
"earlyclobber" with something clearer later on, all the better.
"earlycloibber" is a really bad name, though. Perhaps spell it "uniquereg"
or something else that gets at what it actually means?

It seems to me the root problem here is that the instruction has two outputs
and we don't want the output to be allocated to the same register as the
inputs. We have no way to express multiple outputs in TableGen.

As it happens, AVX has similar problems with its semantics for VSQRTSS/SD. In
fact the semantics there are even worse, to the point where I'm not going to
think any more about it. :slight_smile:

                            -Dave

Do you have specific examples in mind that would be expressible with
something more complicated that aren't handleable via an early-clobber
constraint?

Not offhand, no. I'm mostly concerned about the readability of .td files.

Perhaps spelling it out more fully with "earlyclobber" rather than
"early" would help?

That's better. Is there any way you could convince TableGen to recognize
that 'constraints = "$success != $src", "$success != $ptr"' is semantically
equivalent to earlyclobber? Maybe check that the common operand in both
contraints is declared to interfere with all other operands and if that's
so, mark it earlyclobber.

It would be possible, yes. I'm concerned that would imply that one could specify a constraint that the output register couldn't overlap with one input register, but could with another, which isn't expressible. Thus my preference for specifying the constraint solely as an attribute of the output register rather than referencing the other operands explicitly.

When I'm writing .td files I really don't want to be concerned with the
nitty-gritty details of how the backend is implemented. I just want to
express the semantics I want. I think that was the motivation for the
switch from isThreeAddress to "$src = $dst."

I agree. We're definitely on the same page about what the goals are.

I have no objection going with "earlyclobber" initially but we should think
about ways to abstract codegen semantics whenever we can. If we can replace
"earlyclobber" with something clearer later on, all the better.
"earlycloibber" is a really bad name, though. Perhaps spell it "uniquereg"
or something else that gets at what it actually means?

I'm not hugely tied to the name. I chose it because it matches the usage in GCC documentation for inline assembly with the same concepts and how the concept is expressed elsewhere in the compiler. If I'm not mistaken, due to the GCC nomenclature, the linux kernel also refers to this sort of thing as an early-clobber.

It seems to me the root problem here is that the instruction has two outputs
and we don't want the output to be allocated to the same register as the
inputs. We have no way to express multiple outputs in TableGen.

Close, but not precisely. The issue is that the values in the input registers may still be needed in the hardware at the instruction stage where the output register needs to be written, or some other such timing issue that if the registers are the same the hardware can't guarantee proper access ordering for correct behavior. From LLVM's perspective, the instruction has only one output (the success value), and also has a side-effect (the store to memory). Another example of this issue is the ARM integer multiply instruction (MUL) on pre-v6 architectures, where if the destination register and the first source register are the same, the behaviour is undefined.

The name is trying to capture the idea that the hardware may clobber the value in the destination register early enough in the execution of the instruction that it could conflict with reading the value from the source register if they are the same.

I think you're right that it's best to go ahead with this for now and then if a better solution is arrived at later, we can update things to use that.

Regards,
-Jim

> That's better. Is there any way you could convince TableGen to
> recognize
> that 'constraints = "$success != $src", "$success != $ptr"' is
> semantically
> equivalent to earlyclobber? Maybe check that the common operand in
> both
> contraints is declared to interfere with all other operands and if
> that's
> so, mark it earlyclobber.

It would be possible, yes. I'm concerned that would imply that one
could specify a constraint that the output register couldn't overlap
with one input register, but could with another, which isn't
expressible.

Not right now, though, but I don't think it would be hard to add. I'm
not saying you should add that now, though.

Thus my preference for specifying the constraint solely
as an attribute of the output register rather than referencing the
other operands explicitly.

Yep, I understand the simplicity argument.

I'm not hugely tied to the name. I chose it because it matches the
usage in GCC documentation for inline assembly with the same concepts
and how the concept is expressed elsewhere in the compiler. If I'm not
mistaken, due to the GCC nomenclature, the linux kernel also refers to
this sort of thing as an early-clobber.

This is my own bias speaking, but gcc has some fantastically stupid names
for things. I don't necessarily see it as meritorious to follow its
example.

> It seems to me the root problem here is that the instruction has two
> outputs
> and we don't want the output to be allocated to the same register as
> the
> inputs. We have no way to express multiple outputs in TableGen.

Close, but not precisely. The issue is that the values in the input
registers may still be needed in the hardware at the instruction stage
where the output register needs to be written, or some other such
timing issue that if the registers are the same the hardware can't
guarantee proper access ordering for correct behavior. From LLVM's

Right, you are of course more correct here.

The name is trying to capture the idea that the hardware may clobber
the value in the destination register early enough in the execution of
the instruction that it could conflict with reading the value from the
source register if they are the same.

Yep.

I think you're right that it's best to go ahead with this for now and
then if a better solution is arrived at later, we can update things to
use that.

I'm fine with that. Not that my opinion matters more than anyone else's. :slight_smile:

                                  -Dave

I'm not hugely tied to the name. I chose it because it matches the
usage in GCC documentation for inline assembly with the same concepts
and how the concept is expressed elsewhere in the compiler. If I'm not
mistaken, due to the GCC nomenclature, the linux kernel also refers to
this sort of thing as an early-clobber.

This is my own bias speaking, but gcc has some fantastically stupid names
for things. I don't necessarily see it as meritorious to follow its
example.

I agree with this, "earlyclobber" doesn't mean obviously mean anything to me, unless I were to already have read the GCC manual, which probably shouldn't be a prerequisite for understanding .td files. For instance, LLVM replaced "three-address" with an actual meaningful constraint pattern at some point in the recent past, which was nice.

I think you're right that it's best to go ahead with this for now and
then if a better solution is arrived at later, we can update things to
use that.

Sure, getting something working now is probably more valuable than waiting around for the perfect solution to present itself.

Nate