Minimal set of Assembly Instructions for an Intermediate Language?

Question

I was wondering the following:

Is it possible to create a small set of Assembly Instructions that together can do all operations possible? Or maybe asked differently what are the Must-Have assembly instructions for about any architecture?

(For example, Jump and Add would be necessary to do about anything)

I hope you guys can help me!

To provide some background information: I am trying to design an Intermediate Language for my compiler and I'd like to use as few instructions as possible (where then later a bunch of those instructions could be substituted for one Complex Instruction for specific architectures). But of course the IL itself should be portable.

Answer 1

The minimum is one instruction and it was even implemented in reality in the carbone nanotube computer or the MAXQ chip

Although only one is enough but in fact it's much more complicated than you thought, and often needs more instruction to do the same work. If you need the chip's speed to be "usable" then IMO it should have at least some common instructions:

• 1 conditional jump instruction: jump on equal (or not equal)
• 1 SUB instruction for arithmetics. This way you can do both addition and subtraction easily without a negate instruction
• 1 bitwise instruction: NAND (or NOR), with one of this you can do any logic operations needed
• 1 MOV instruction
• 1 load/store instruction

With sub or bitwise instruction you can do a move data so depend on your architecture and the opcode size you may remove MOV or load/store to simpify it even more.

Answer 2

I think you want the opposite. Instead of making an IL that is as simple as possible, you want one that is very expressive. The more expressive the IL is, the easier it may be to optimize for a specific architecture.

It is easier to expand a complex IL operation into many individual instructions than it is to coalesce many simple IL operations into a complicated instruction. You might not need multiply, since it can be done with jump and add instructions. But when you're compiling for a chip which has a hardware multiply, you'd have to analyze the IL to determine this was an "add loop" and covert it back into a multiply. That's a lot more work than coming across a multiply and saying "hmm, this architecture can't do that, I guess we'll have to make it an add loop."

Another example, you might think your IL doesn't need floating point operations, since some ARM chips have to do floating point in software anyways. But some ARM chips don't have to do that, and if your IL doesn't support FP operations then you'll need to convert complicated software FP IL back into a single hardware instruction.

It's better to match your IL to the most advanced and complicated hardware features, and then "fall back" to "software emulation" of those features on processors that don't have them.