Doomhowl-Interactive/llvm-project
0
0
Fork 0
Code Issues Pull Requests Actions 5 Packages Projects Releases Wiki Activity
Files
main
llvm-project/llvm/test/TableGen/DecoderEmitter/DecoderEmitterBitwidthSpecialization.td
Sergei Barannikov 60bdf09654 [TableGen][DecoderEmitter] Rework table construction/emission (#155889) 
### Current state

We have FilterChooser class, which can be thought of as a **tree of
encodings**. Tree nodes are instances of FilterChooser itself, and come
in two types:

* A node containing single encoding that has *constant* bits in the
specified bit range, a.k.a. singleton node.
* A node containing only child nodes, where each child represents a set
of encodings that have the same *constant* bits in the specified bit
range.

Either of these nodes can have an additional child, which represents a
set of encodings that have some *unknown* bits in the same bit range.

As can be seen, the **data structure is very high level**.

The encoding tree represented by FilterChooser is then converted into a
finite-state machine (FSM), represented as **byte array**. The
translation is straightforward: for each node of the tree we emit a
sequence of opcodes that check encoding bits and predicates for each
encoding. For a singleton node we also emit a terminal "decode" opcode.

The translation is done in one go, and this has negative consequences:

* We miss optimization opportunities.
* We have to use "fixups" when encoding transitions in the FSM since we
don't know the size of the data we want to jump over in advance. We have
to emit the data first and then fix up the location of the jump. This
means the fixup size has to be large enough to encode the longest jump,
so **most of the transitions are encoded inefficiently**.
* Finally, when converting the FSM into human readable form, we have to
**decode the byte array we've just emitted**. This is also done in one
go, so we **can't do any pretty printing**.

### This PR

We introduce an intermediary data structure, decoder tree, that can be
thought as **AST of the decoder program**.
This data structure is **low level** and as such allows for optimization
and analysis.
It resolves all the issues listed above. We now can:
* Emit more optimal opcode sequences.
* Compute the size of the data to be emitted in advance, avoiding
fixups.
* Do pretty printing.

Serialization is done by a new class, DecoderTableEmitter, which
converts the AST into a FSM in **textual form**, streamed right into the
output file.

### Results
* The new approach immediately resulted in 12% total table size savings
across all in-tree targets, without implementing any optimizations on
the AST. Many tables observe ~20% size reduction.
* The generated file is much more readable.
* The implementation is arguably simpler and more straightforward (the
diff is only +150~200 lines, which feels rather small for the benefits
the change gives).
2025-09-20 01:58:53 +00:00

190 lines
7.3 KiB
TableGen
Raw Permalink Blame History

// RUN: llvm-tblgen -gen-disassembler -I %p/../../../include %s | FileCheck %s --check-prefix=CHECK-DEFAULT
// RUN: llvm-tblgen -gen-disassembler -specialize-decoders-per-bitwidth -I %p/../../../include %s | FileCheck %s --check-prefix=CHECK-SPECIALIZE-NO-TABLE
// RUN: llvm-tblgen -gen-disassembler -specialize-decoders-per-bitwidth -use-fn-table-in-decode-to-mcinst -I %p/../../../include %s | FileCheck %s --check-prefix=CHECK-SPECIALIZE-TABLE
include "llvm/Target/Target.td"
def archInstrInfo : InstrInfo { }
def arch : Target {
let InstructionSet = archInstrInfo;
}
let Namespace = "arch" in {
def R0 : Register<"r0">;
def R1 : Register<"r1">;
def R2 : Register<"r2">;
def R3 : Register<"r3">;
}
def Regs : RegisterClass<"Regs", [i32], 32, (add R0, R1, R2, R3)>;
// Bit 0 of the encoding determines the size (8 or 16 bits).
// Bits {3..1} define the number of operands encoded.
class Instruction8Bit<int NumOps> : Instruction {
let Size = 1;
let OutOperandList = (outs);
field bits<8> Inst;
let Inst{0} = 0;
let Inst{3-1} = NumOps;
}
class Instruction16Bit<int NumOps> : Instruction {
let Size = 2;
let OutOperandList = (outs);
field bits<16> Inst;
let Inst{0} = 1;
let Inst{3-1} = NumOps;
}
// Define instructions to generate 4 cases in decodeToMCInst.
// Each register operand needs 2 bits to encode.
// An instruction with no inputs.
def Inst0 : Instruction8Bit<0> {
let Inst{7-4} = 0;
let InOperandList = (ins);
let AsmString = "Inst0";
}
// An instruction with a single input.
def Inst1 : Instruction8Bit<1> {
bits<2> r0;
let Inst{5-4} = r0;
let Inst{7-6} = 0;
let InOperandList = (ins Regs:$r0);
let AsmString = "Inst1";
}
// An instruction with two inputs.
def Inst2 : Instruction16Bit<2> {
bits<2> r0;
bits<2> r1;
let Inst{5-4} = r0;
let Inst{7-6} = r1;
let Inst{15-8} = 0;
let InOperandList = (ins Regs:$r0, Regs:$r1);
let AsmString = "Inst2";
}
// An instruction with three inputs. .
def Inst3 : Instruction16Bit<3> {
bits<2> r0;
bits<2> r1;
bits<2> r2;
let Inst{5-4} = r0;
let Inst{7-6} = r1;
let Inst{9-8} = r2;
let Inst{15-10} = 0;
let InOperandList = (ins Regs:$r0, Regs:$r1, Regs:$r2);
let AsmString = "Inst3";
}
// -----------------------------------------------------------------------------
// In the default case, we emit a single decodeToMCinst function and DecodeIdx
// is shared across all bitwidths.
// CHECK-DEFAULT-LABEL: DecoderTable8
// CHECK-DEFAULT: using decoder 0
// CHECK-DEFAULT: using decoder 1
// CHECK-DEFAULT: };
// CHECK-DEFAULT-LABEL: DecoderTable16
// CHECK-DEFAULT: using decoder 2
// CHECK-DEFAULT: using decoder 3
// CHECK-DEFAULT: };
// CHECK-DEFAULT-LABEL: template <typename InsnType>
// CHECK-DEFAULT-NEXT: static DecodeStatus decodeToMCInst
// CHECK-DEFAULT: case 0
// CHECK-DEFAULT: case 1
// CHECK-DEFAULT: case 2
// CHECK-DEFAULT: case 3
// -----------------------------------------------------------------------------
// When we specialize per bitwidth, we emit 2 decodeToMCInst functions and
// DecodeIdx is assigned per bit width.
// CHECK-SPECIALIZE-NO-TABLE-LABEL: DecoderTable8
// CHECK-SPECIALIZE-NO-TABLE: 8, // 0: BitWidth 8
// CHECK-SPECIALIZE-NO-TABLE: using decoder 0
// CHECK-SPECIALIZE-NO-TABLE: using decoder 1
// CHECK-SPECIALIZE-NO-TABLE: };
// CHECK-SPECIALIZE-NO-TABLE-LABEL: template <typename InsnType>
// CHECK-SPECIALIZE-NO-TABLE-NEXT: static std::enable_if_t<InsnBitWidth<InsnType> == 8, DecodeStatus>
// CHECK-SPECIALIZE-NO-TABLE-NEXT: decodeToMCInst
// CHECK-SPECIALIZE-NO-TABLE: case 0
// CHECK-SPECIALIZE-NO-TABLE: case 1
// CHECK-SPECIALIZE-NO-TABLE-LABEL: DecoderTable16
// CHECK-SPECIALIZE-NO-TABLE: 16, // 0: BitWidth 16
// CHECK-SPECIALIZE-NO-TABLE: using decoder 0
// CHECK-SPECIALIZE-NO-TABLE: using decoder 1
// CHECK-SPECIALIZE-NO-TABLE: };
// CHECK-SPECIALIZE-NO-TABLE-LABEL: template <typename InsnType>
// CHECK-SPECIALIZE-NO-TABLE-NEXT: static std::enable_if_t<InsnBitWidth<InsnType> == 16, DecodeStatus>
// CHECK-SPECIALIZE-NO-TABLE-NEXT: decodeToMCInst
// CHECK-SPECIALIZE-NO-TABLE: case 0
// CHECK-SPECIALIZE-NO-TABLE: case 1
// CHECK-SPECIALIZE-NO-TABLE-LABEL: template <typename InsnType>
// CHECK-SPECIALIZE-NO-TABLE-NEXT: decodeInstruction
// CHECK-SPECIALIZE-NO-TABLE: uint32_t BitWidth = decodeULEB128AndIncUnsafe(Ptr);
// CHECK-SPECIALIZE-NO-TABLE-NEXT: assert(InsnBitWidth<InsnType> == BitWidth &&
// -----------------------------------------------------------------------------
// Per bitwidth specialization with function table.
// 8 bit deccoder table, functions, and function table.
// CHECK-SPECIALIZE-TABLE-LABEL: DecoderTable8
// CHECK-SPECIALIZE-TABLE: 8, // 0: BitWidth 8
// CHECK-SPECIALIZE-TABLE: using decoder 0
// CHECK-SPECIALIZE-TABLE: using decoder 1
// CHECK-SPECIALIZE-TABLE: };
// CHECK-SPECIALIZE-TABLE-LABEL: template <typename InsnType>
// CHECK-SPECIALIZE-TABLE-NEXT: static std::enable_if_t<InsnBitWidth<InsnType> == 8, DecodeStatus>
// CHECK-SPECIALIZE-TABLE-NEXT: decodeFn_8bit_0
// CHECK-SPECIALIZE-TABLE-LABEL: template <typename InsnType>
// CHECK-SPECIALIZE-TABLE-NEXT: static std::enable_if_t<InsnBitWidth<InsnType> == 8, DecodeStatus>
// CHECK-SPECIALIZE-TABLE-NEXT: decodeFn_8bit_1
// CHECK-SPECIALIZE-TABLE-LABEL: template <typename InsnType>
// CHECK-SPECIALIZE-TABLE-NEXT: static std::enable_if_t<InsnBitWidth<InsnType> == 8, DecodeStatus>
// CHECK-SPECIALIZE-TABLE-NEXT: decodeToMCInst
// CHECK-SPECIALIZE-TABLE-LABEL: static constexpr DecodeFnTy decodeFnTable[] = {
// CHECK-SPECIALIZE-TABLE-NEXT: decodeFn_8bit_0,
// CHECK-SPECIALIZE-TABLE-NEXT: decodeFn_8bit_1,
// CHECK-SPECIALIZE-TABLE-NEXT: };
// 16 bit deccoder table, functions, and function table.
// CHECK-SPECIALIZE-TABLE-LABEL: DecoderTable16
// CHECK-SPECIALIZE-TABLE: 16, // 0: BitWidth 16
// CHECK-SPECIALIZE-TABLE: using decoder 0
// CHECK-SPECIALIZE-TABLE: using decoder 1
// CHECK-SPECIALIZE-TABLE: };
// CHECK-SPECIALIZE-TABLE-LABEL: template <typename InsnType>
// CHECK-SPECIALIZE-TABLE-NEXT: static std::enable_if_t<InsnBitWidth<InsnType> == 16, DecodeStatus>
// CHECK-SPECIALIZE-TABLE-NEXT: decodeFn_16bit_0
// CHECK-SPECIALIZE-TABLE-LABEL: template <typename InsnType>
// CHECK-SPECIALIZE-TABLE-NEXT: static std::enable_if_t<InsnBitWidth<InsnType> == 16, DecodeStatus>
// CHECK-SPECIALIZE-TABLE-NEXT: decodeFn_16bit_1
// CHECK-SPECIALIZE-TABLE-LABEL: template <typename InsnType>
// CHECK-SPECIALIZE-TABLE-NEXT: static std::enable_if_t<InsnBitWidth<InsnType> == 16, DecodeStatus>
// CHECK-SPECIALIZE-TABLE-NEXT: decodeToMCInst
// CHECK-SPECIALIZE-TABLE-LABEL: static constexpr DecodeFnTy decodeFnTable[] = {
// CHECK-SPECIALIZE-TABLE-NEXT: decodeFn_16bit_0,
// CHECK-SPECIALIZE-TABLE-NEXT: decodeFn_16bit_1,
// CHECK-SPECIALIZE-TABLE-NEXT: };
// CHECK-SPECIALIZE-TABLE-LABEL: template <typename InsnType>
// CHECK-SPECIALIZE-TABLE-NEXT: decodeInstruction
// CHECK-SPECIALIZE-TABLE: uint32_t BitWidth = decodeULEB128AndIncUnsafe(Ptr);
// CHECK-SPECIALIZE-TABLE-NEXT: assert(InsnBitWidth<InsnType> == BitWidth &&
Reference in New Issue View Git Blame Copy Permalink