Review options between using CodeBeads v.s. TSFlags for encoding M68k instructions

[Quuxplusone]

Bugzilla Link	PR48792
Status	NEW
Importance	P enhancement
Reported by	Min-Yih Hsu (minyihh@uci.edu)
Reported on	2021-01-18 10:50:06 -0800
Last modified on	2021-11-10 13:39:03 -0800
Version	trunk
Hardware	PC All
CC	glaubitz@physik.fu-berlin.de, llvm-bugs@lists.llvm.org, llvm-dev@redking.me.uk, minyihh@uci.edu, rickytaylor26@gmail.com
Fixed by commit(s)
Attachments
Blocks	PR48791
Blocked by
See also

Normally a backend uses MCInstrDesc::TSFlags, a 64-bits bit vector, to carry all the instructions' encoding info. However, M68k's current encoding scheme -- which might not be the optimal one -- requires at least 24 bytes to carry all the necessary info. As a workaround, M68k created a specialized TableGen backend, CodeBeads, to generate an auxiliary encoding table that can carry arbitrary length instruction encodings.

Nevertheless, we always prefer to reuse the existing infrastructures. Therefore this bug is used for tracking the status of refactoring M68k's current encoding scheme into a more concise form. For example, try to fit every encoding info into the 64-bits TSFlags, or use TSFlags as a index/pointer to another auxiliary encoding table.

For more discussion on this topic, please refer to https://reviews.llvm.org/D88385.

[Quuxplusone]

Hi,

Preface: I haven't worked much with the LLVM backend infrastructure much before
looking at the M68k target.

I've had a look at the instruction encoding over the past few days and I'm
finding the number of instruction definitions to be overwhelming. There is
currently one instruction defined per operand per addressing mode.

I've been playing about with an LLD implementation and I'm currently finding it
hard to implement relaxation to 32-bit operands due to the number of
instruction permutations.

Additionally, my proof-of-concept disassembler is not very efficient since it
needs to consider the entire instruction length (which can be up to 22 bytes
IIRC). This could be implemented as radix-tree-style code generator, which
would be efficient, but quite complicated.

So I spent some time looking through the processor manual for the M68k and I've
observed a few things:

- Almost every instruction can be identified from just the first word.
- Whilst lots of memory operand modes are illegal for particular instructions,
almost all are encoded in the same way.

So, instead of the code beads code, could we:

- Use a MCTargetExpr subclass to represent the standard M68k memory operand?
- Include a 16-bit value & mask for the first instruction word?
- Have a few special cases in the emitter & disassembler code for outlier
instructions?

Relaxation would be much easier to implement as there are fewer instructions
and relaxation per-operand could be implemented once. The only complication is
knowing which operand modes are valid for a given instruction, to know when to
expand into a (load + op).

Disassembly could just check the first word (even checking the highest 4 bits
in a switch maybe) which would be fast and straight-forward to follow. There
would need to be a few special cases though.

There would still need to be multiple instruction definitions in some cases but
they would be rare.

I've not thought much about ensuring only valid instruction permutations get
parsed and emitted.

(If this isn't the right place to discuss possible solutions, please point me
in the right direction!)

Ricky,

[Quuxplusone]

Hi Ricky!

Thanks a lot for the detailed analysis.

(In reply to Ricky Taylor from comment #1)
> I've had a look at the instruction encoding over the past few days and I'm
> finding the number of instruction definitions to be overwhelming. There is
> currently one instruction defined per operand per addressing mode.

I agree, I was overwhelmed by the number of definitions as well!

> (If this isn't the right place to discuss possible solutions, please point
> me in the right direction!)

I think the best place to bring this up is the LLVM mailing list (llvm-dev) as
your will be visible to a much broader audience there.

Thanks for already digging into this. I hope that it won't take too long
anymore until the backend gets merged so that we can start working on these
issues on the way to production.

[Quuxplusone]

Alright, I've just scratched a plan for the new instruction encoder, here is the writeup that includes the background, previous attempts, and proposed solutions: https://gist.github.com/mshockwave/1c961425c79f1de5000f645d922833bb

I've also prototyped the new features proposed in that document and it worked as expected for common instruction types.

[Quuxplusone]

(In reply to Min-Yih Hsu from comment #3)

Alright, I've just scratched a plan for the new instruction encoder, here is the writeup that includes the background, previous attempts, and proposed solutions: https://gist.github.com/mshockwave/1c961425c79f1de5000f645d922833bb

I've also prototyped the new features proposed in that document and it worked as expected for common instruction types.

I have to admit that this doesn't fully solve the problem of requiring a TG definition per instruction type per addressing mode, but I think the new syntax is much better:

def ADD32dp : MxBiArOp<"add", MxARID32, ...>, MxAddrMode_p;
def ADD32dk : MxBiArOp<"add", MxARID32, ...>, MxAddrMode_k;
...

And I think we can further factor this out with foreach (or multiclass?):

foreach AM = ["p", "k", ...] in
def ADD32d#AM : MxBiArOp<"add", MxARID32, ...>, !cast<MxAddrMode>("MxAddrMode_"#AM);