single instruction

2 Articles

One Instruction To Rule Them All: C Compiler Emits Only MOV

May 21, 2021 by 17 Comments

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.

Continue reading “One Instruction To Rule Them All: C Compiler Emits Only MOV” →

A Turing-Complete CPU From RAM

February 20, 2020 by 16 Comments

Building a general-purpose computer means that you’ll have to take a lot of use cases into consideration, and while the end product might be useful for a lot of situations, it will inherently contain a lot of inefficiencies. On the other hand, if you want your computer to do one thing and do it very well, you can optimize to extremes and still get results. This computer, built from RAM, is just such an example.

The single task in this case was to build a computer that can compute the Fibonacci sequence.  Since it only does one thing, another part of the computer that can be simplified (besides the parts list) is the instruction set. In this case, the computer uses a single instruction: byte-byte-jump. Essentially all this computer does is copy one byte to another, and then perform an unconditional jump. Doing this single task properly is enough to build every other operation from, so this was chosen for simplicity even though the science behind why this works is a little less intuitive.

Of course, a single instruction set requires a lot of clock cycles to work (around 200 for a single operation). The hardware used in this build is also interesting and although it uses a Raspberry Pi to handle some of the minutiae, it’s still mostly done entirely in RAM chips, only cost around $15, and is a fascinating illustration of some of the more interesting fundamentals of computer science. If you’re interested, you can build similar computers out of 74-series chips as well.