TableGen: use of "add" keyword while creating Registers

Beginners
1

I came across the following code, while studying how to create the RegisterInfo.td file for a custom backend:

First, a register type is declared

multiclass MOSReg8<bits<16> num, string name> {
  def LSB : MOSReg<!add(num, 1), name#"LSB">;

  def NAME : MOSReg<num, name> {
    let SubRegs = [!cast<Register>(NAME#LSB)];
    let SubRegIndices = [sublsb];
  }
}

Using the above class, register instances are defined

defm A : MOSReg8<0, "a">;
defm X : MOSReg8<2, "x">;

Later, a RegisterClass is declared

class MOSRegClass<list<ValueType> regTypes, int alignment, dag regList>
     : RegisterClass<"MOS", regTypes, alignment, regList>;

class MOSReg8Class<dag RegList>: MOSRegClass<[i8], 8, RegList>;

Using this class, what exactly did we do here

// Single register classes.
let isPressureFineGrained = true in {
  def Ac : MOSReg8Class<(add A)>;
  def Xc : MOSReg8Class<(add X)>;
}

So, I have two questions:

  1. Why did we perform two def/defms, if register was defined as A, what is Ac?
  2. What is the meaning of add A in the def of Ac? To which parameter does this argument map to?
2

This includes some guess work on my part, without seeing the context.

I think c means class. So Ac is a class of register that only includes the register A.

When you decide what registers to use that’ll be done by classes. For example on AArch64 we have 32 and 64 bit registers, so we’d have a class that contains all the 32 bit registers. So it’s probably not uncommon to have a “class” that only contains one register.

This is what the first part generates at least: (I replaced some types that were not present)

------------- Classes -----------------
class MOSReg<int MOSReg:_foo = ?, string MOSReg:_bar = ?> {
}
------------- Defs -----------------
def A {	// MOSReg
}
def ALSB {	// MOSReg
}
def X {	// MOSReg
}
def XLSB {	// MOSReg
}

You can see this if you pass the file to llvm-tblgen, though you may have to manually add some include paths.

This is constructing a DAG, though I couldn’t track down where add is defined. This is the operator and I think those can be custom. Certainly 1   TableGen Programmer’s Reference — LLVM 17.0.0git documentation doesn’t have a list of them.

In this case I assume it is simply adding the def A to the DAG then passing that as the <dag RegList> to MOSReg8Class, which passes it on as dag regList for MOSRegClass.

Side note: if you are looking for a way to experiment with small snippets of Tablegen, Jupyter notebooks are very convenient - llvm-project/llvm/utils/TableGen/jupyter at main · llvm/llvm-project · GitHub

For this I pasted your snippets into a notebook and stubbed out some of the missing bits just to see what was generated.

2 Likes
3

@mysterymath may also be around to comment given this is from llvm-mos.

1 Like
4

Why did we perform two def/defms, if register was defined as A, what is Ac?

Yes, A is defined as a Register. Ac is a RegisterClass.

The defm uses the multiclass to define two records, the LSB one and the NAME one. It defines the two records A and ALSB, both of Register type (Register class).

The def Ac defines a RegisterClass instance.

(Sorry if you know this already, I’m just writing how I would think of it.) The multiclass does not itself define a class or instance, but is a mechanism for generating the two records inside it. The parent class of instances of those two records is not the multiclass but MOSReg as written in the def. So A is a Register. Then you need at least one RegisterClass to put it in, in this case Ac.

What is the meaning of add A in the def of Ac? To which parameter does this argument map to?

add A adds Register A to RegisterClass Ac. The A refers to the definition of A in this file. The add is an operation on a set, described in llvm/include/llvm/Target/Target.td:

// The memberList in a RegisterClass is a dag of set operations. TableGen
// evaluates these set operations and expand them into register lists. These
// are the most common operation, see test/TableGen/SetTheory.td for more
// examples of what is possible:
// (add R0, R1, R2) - Set Union. Each argument can be an individual register, a
// register class, or a sub-expression. This is also the way to simply list
// registers.

Below that passage it says that set operators are “defined in TargetSelectionDAG.td”. In that file we find a def add, but it is defined as a SelectionDAG operator. I’m guessing what makes add a set operation in the right context is its use by the SetTheory class in llvm/include/llvm/TableGen/SetTheory.h, which is used in llvm/utils/TableGen/CodeGenRegisters.cpp. The function of things like “add” is not described only in its TD definition, but in its use by TableGen C++ code.

The Backend document also describes creating a RegisterClass and using add:

https://llvm.org/docs/WritingAnLLVMBackend.html#defining-a-register-class

2 Likes
5

The above comments are great, so I’ll just add the little bit of llvm-mos specific information about why we modeled things this way.

If you look at a 6502 instruction like ADC abs (add with carry, absolute), it reads and writes A and C, writes the N and Z flags, and takes a memory location as operand. The most straightforward way to model the register interactions would be to use implicit uses and defs. I initially modelled the whole instruction set this way.

The issue is that on most targets, implicit def use chains of physical registers are relatively uncommon; they’re primarily used to shuffle values temporarily into e.g. a specific set of registers that e.g. a multiplication operation uses. It’s even less common to have multiple chains of such operands going in and out of the same instruction. There’s quite a few optimizations that make really quick snap judgments or just quit completely in such cases. This is overwhelmingly common on the 6502, so it overall produced really strange optimization behavior, and it seemed that a lot of passes would need adjustment to handle these cases well.

Accordingly, we cheated a bit by modelling most of these as single-register classes. This allows most optimization passes to do their business without modification. It leaves it to the register allocator to notice that there’s actually only one place to put things, and to insert the necessary copies to make that work. Greedy regalloc did an okay job of this, and it only took a little adjustment to make it do a pretty darn good job.

The isPressureFineGrained Tablegen thing is also a consequence of this. There’s an optimization that merges together register classes when accounting for register pressure. Since some of our register classes are extremely constrained, we added a tablegen param to disable this and keep a detailed accounting of their pressure.

1 Like