One Instruction to Rule Them All: C Compiler Emits only MOV

How many instructions do you need to successfully compile C code? Let’s see, you’d need some jump instructions, some arithmetic functions, and — of course — move instructions, right? Turns out you only need the move instruction, which — on x86, at least — is Turing complete.

While the effort is a bit tongue-in-cheek, we have to admit that if you were trying to create your own CPU, this would make for a simple architecture and might have power or complexity advantages, so maybe someone will find a practical use for it after all. If you wanted a C compiler for a simple CPU, this wouldn’t require much to emulate at a byte-code level, either.

How does it work? The best way to answer that is to look at the presentation slides on the GItHub site. Everything works through clever usage of memory locations and dummy addresses to do nothing. Efficient? Maybe not. But it does work.

For example, if you want to test to see if x and y are equal

mov [x],0
mov [y],1
mov R,[x]

That hides a lot of detail, of course, but the idea is that if Y doesn’t equal X, you’ll write a 1 to some random memory location (which better not be important; that’s one of the details). If X and Y are equal, you’ll overwrite with a 1. So R winds up with a 0 if X and Y are different or a 1 if they are the same.

In practical terms, if you want to translate something like “if (x==y) x=100” you wind up setting an integer pointer to either point to X or to a dummy location using the above trick (just substitute the address of X for 1 and the dummy address for the 0). Then you store the 100 to that integer pointer. With no branches, each line of code executes.

In fact, though, the compiler makes a few compromises including using a jump to call external functions and a floating point instruction. You can avoid both by recompiling libraries and adding the MOV-only floating point emulator, which is entertaining, but probably not very performant.

This reminded us of several “one instruction” computers we’ve seen in the past (including mine). While this is a bit of a strange compiler target, it is hardly the strangest one we’ve seen.