<html><head><meta http-equiv="Content-Type" content="text/html; charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">(This is a long proposal. If you prefer, here is the web version: <a href="https://gist.github.com/mshockwave/66e98d099256deefc062633909bb7b5b" class="">https://gist.github.com/mshockwave/66e98d099256deefc062633909bb7b5b</a>)<div class=""><br class=""></div><div class="">## Background<br class="">CodeEmitterGen is a TableGen backend that generates instruction encoder functions for `MCCodeEmitter` from a concise TableGen syntax. It is, however, almost exclusively designed for targets that use fixed-length instructions. It's nearly impossible to use this infrastructure to describe instruction encoding scheme for ISAs with variable-length instructions, like X86 and M68k.<br class=""><br class="">To have a better understanding on this problem, let's look at an example. For a fixed-length instruction ISA, developers write the following TableGen syntax to describe an instruction encoding:<br class="">```<br class="">class MyInst<(outs GR64:$dst), (ins GR64, i16imm:$imm)> : Instruction {<br class=""> bits<32> Inst;<br class=""><br class=""> bits<4> dst;<br class=""> bits<16> imm;<br class=""> let Inst{31-28} = 0b1011;<br class=""> ...<br class=""> let Inst{19-16} = dst;<br class=""> let Inst{15-0} = imm;<br class="">}<br class="">```<br class="">The `Inst` field tells us the length of an instruction -- 32 bits in this case. Each bit in this field describes the encoded value, which is either a concrete value or symbolic one like `dst` and `imm` in the example above. The `dst` and `imm` variables correspond to the output operand (`$dst`) and the second input operand (`$imm`), respectively. Meaning, the encoder function (generated by CodeEmitterGen) will eventually insert the encoding for these two operands into the right bit ranges (bit 19\~16 for `dst` and 15\~0 for `imm`).<br class=""><br class="">Though this TableGen syntax fits well for fixed-length instructions, it imposes some difficulties to instructions with variable length and memory poerands with complex addressing modes:<br class=""> 1. The bit width of the `Inst` field is fixed. Though we can declare the field with maximum instruction size in the ISA, it requires extra code to adjust the final instruction size.<br class=""> 2. Operand encoding can only be placed at fixed bit positions. However, the size of an operand in a variable-length instruction might vary.<br class=""> 3. In the situation where a single logical operand is consisting of multiple MachineOperand-s / MCOperand-s, the current syntax cannot reference a sub-operand. Which means we can only reference the entire logical operand at places where we actually should put sub-operands. Making the TG code less readable and bring more burden to the operand encoding functions (because they don't know which sub-operand to encode).<br class=""><br class="">In short, we need a more flexible CodeEmitterGen infrastructure for variable-length instructions: describe the instruction encoding in a "position independent" fashion and be able to reference sub-operands with ease.<br class=""><br class="">## Proposal<br class="">We propose a new infrastructure, called VarLenCodeEmitterGen, to solve the aforementioned shortcomings. It is consisting of new TableGen syntax and some modifications to the existing CodeEmitterGen TableGen backend.<br class=""><br class="">Suppose we are dealing with an instruction `MyVarInst`:<br class="">```<br class="">class MyMemOperand<dag sub_ops> : Operand<iPTR> {<br class=""> let MIOperandInfo = sub_ops;<br class="">}<br class=""><br class="">class MyVarInst<MyMemOperand memory_op> : Instruction {<br class=""> let OutOperandList = (outs GR64:$dst);<br class=""> let InOperandList = (ins memory_operand:$src);<br class="">}<br class="">```<br class="">It has the following encoding format:<br class="">```<br class=""><div style="color: rgb(54, 54, 54); background-color: rgb(255, 255, 255); font-family: Menlo, Monaco, "Courier New", monospace; font-size: 20px; line-height: 30px; white-space: pre;" class=""><div class="">15 8 0</div><div class="">----------------------------------------------------</div><div class="">| Fixed bits | Sub-operand 0 in source operand |</div><div class="">----------------------------------------------------</div><div class="">X 16</div><div class="">----------------------------------------------------</div><div class="">| Sub-operand 1 in source operand |</div><div class="">----------------------------------------------------</div><div class=""> X + 4 X + 1</div><div class=""> ------------------------------------</div><div class=""> | Destination register |</div><div class=""> ------------------------------------</div></div>```<br class="">We have two different kinds of memory operands:<br class="">```<br class="">def MemOp16 : MyMemOperand<(ops GR64:$reg, i16imm:$offset)>;<br class="">def MemOp16 : MyMemOperand<(ops GR64:$reg, i32imm:$offset)>;<br class=""><br class="">def FOO16 : MyVarInst<MemOp16>;<br class="">def FOO32 : MyVarInst<MemOp32>;<br class="">```<br class="">So the size of `FOO16` and `FOO32` will be 36 and 52 bits, respectively.<br class=""><br class="">To express the encoding, first, we modify `MyVarInst` and `MyMemOperand`:<br class="">```<br class="">class MyMemOperand<dag sub_ops> : Operand<iPTR> {<br class=""> let MIOperandInfo = sub_ops;<br class=""> dag Base;<br class=""> dag Extension;<br class="">}<br class=""><br class="">class MyVarInst<MyMemOperand memory_op> : Instruction {<br class=""> dag Inst;<br class=""><br class=""> let OutOperandList = (outs GR64:$dst);<br class=""> let InOperandList = (ins memory_op:$src);<br class=""><br class=""> let Inst = (seq<br class=""> (seq:$dec /*Fixed bits*/0b10110111, memory_op.Base),<br class=""> memory_op.Extension,<br class=""> // Destination register<br class=""> (operand "$dst", 4)<br class=""> );<br class="">}<br class="">```<br class="">Then, we use a slightly different representation for `MemOp16` and `MemOp32`:<br class="">```<br class="">class MemOp16<string op_name> : MyMemOperand<(ops GR64:$reg, i16imm:$offset)> {<br class=""> let Base = (operand "$"#op_name#".reg", 8);<br class=""> let Extension = (operand "$"#op_name#".offset", 16);<br class="">}<br class=""><br class="">class MemOp32<string op_name> : MyMemOperand<(ops GR64:$reg, i32imm:$offset)> {<br class=""> let Base = (operand "$"#op_name#".reg", 8);<br class=""> let Extension = (operand "$"#op_name#".offset", 32);<br class="">}<br class=""><br class="">def FOO16 : MyVarInst<MemOp16<"src">>;<br class="">def FOO32 : MyVarInst<MemOp32<"src">>;<br class="">```<br class=""><br class="">This new TableGen syntax uses `dag` rather than `bits<N>` for the `Inst` field. Allowing instructions to place their operand (and sub-operand) encodings without worrying about the actual bit positions. The new syntax is underpinned by two new DAG operators: `seq` and `operand`.<br class=""><br class="">The `seq` operator sequentially places its arguments -- fragments of encoding -- from LSB to MSB. If the operator is "tagged" by `$dec`, it goes from MSB to LSB instead. The `operand` operator references the encoding of an operand. Its first DAG argument is a string referencing the name of an operand in either `InOperandList` or `OutOperandList` of an instruction. We can also reference an sub-operand using syntax like `$<operand name>.<sub-operand name>`. The second DAG argument for `operand` is the bit width of the encoded operand. The other variant of `operand` is having two arguments instead of one that follow the operand referencing string. More specifically:<br class="">```<br class="">(operand "$src.reg", 8, 4)<br class="">```<br class="">In this case, 8 and 4 represents a bit range -- high bit and low bit, respectively -- to the encoded `$src.reg` operand.<br class=""><br class="">Finally, a new sub-component added to the existing CodeEmitterGen TableGen backend, VarLenCodeEmitterGen, will turn the above syntax into a C++ encoder function -- `MCCodeEmitter::getBinaryCodeForInstr` -- that uses the same mechanism as the fixed-length instruction version (except few details, like it always uses APInt to store the result).<br class=""><br class="">We think the proposed solution has the following advantages:<br class=""> - Flexible and versatile in terms of expressing instruction encodings.<br class=""> - The TableGen syntax is easy to read, write and understand.<br class=""> - Only adds a few new TableGen syntax.<br class=""> - Tightly integrated with the existing CodeEmitterGen.<br class=""><br class="">### Previous approaches<br class="">Both X86 and M68k -- the only two LLVM targets with variable-length instructions -- are using custom instruction encoders. X86 leverages TSFlags in `MCInst` to carry encoding info. Simply speaking, X86 enumerates and numbers every possible combinations of operands and stores the corresponding index into a segment of TSFlags for an instruction. This approach, of course, requires none trivial amount of workforce to maintain.<br class=""><br class="">M68k, on the other hand, uses an obscured infrastructure called code beads. It is conceptually similar to the VarLenCodeEmitterGen we're proposing here -- concatenating encoding fragments. Except that the syntax is bulky and it uses too many specialized TableGen infrastructures, including a separate TableGen backend, that make the maintainence really really hard.<br class=""><br class="">## Patches<br class="">TableGen modifications: <a href="https://reviews.llvm.org/D115128" class="">https://reviews.llvm.org/D115128</a><br class=""><br class="">## FAQ<br class=""> - Do I need to toggle some flags -- either a command line flag or a TableGen bit field -- to use the new code emitter scheme?<br class=""> - No, having a `dag` type `Inst` field will automatically opt-in this new code emitter scheme.<br class=""> - Can I adopt this for fixed-length instructions?<br class=""> - Absolutely yes. But it's not recommended because CodeEmitterGen can generate more optimal encoder functions for fixed-length instructions. The TableGen syntax of CodeEmitterGen makes more sense for fixed-length instructions, too.<br class=""> - Can X86 adopt this infrastructure?<br class=""> - Theoritically, yes (In practice? I dunno).<br class=""> - What about the disassembler? Can we TableGen-enerate the corresponding disassembling functions?<br class=""> - Since we have a structural description of the encoded instruction, it's probably easier to create a disassembler from the new TableGen syntax. But I haven't worked on that yet.<br class=""><br class=""></div></body></html>