X86 mov is turing complete: mov-only compiler(github.com) |
X86 mov is turing complete: mov-only compiler(github.com) |
Finding Turing-completeness in unlikely places has long been a
pastime of bored computer scientists.
Removing all but the mov instruction from future iterations of the
x86 architecture would have many advantages: the instruction
format would be greatly simplified, the expensive decode unit
would become much cheaper, and silicon currently used for complex
functional units could be repurposed as even more cache. As long
as someone else implements the compiler.
> Thus, while it has been known for quite some time that x86 has far too many instructions, we can now contribute the novel result that it also has far too many registers.
X86 "mov" is a bit of a cheat, though. It's a single mnemonic for what's really dozens of quite different instructions. For example, ARM has "mov" for register-register operations, but "ldr/str" for register-memory, while X86 just uses mov for everything. Even ARM mov optionally puts a barrel shifter into the path, so it's not that pure either.
Of course, modern processors don't really care about register-register moves because they have hundreds of hidden intermediate registers and register renaming which makes those types of moves "free." (e.g. Haswell has 168 GP registers, only 16 of which are exposed through the AMD64 ISA.)
mov 0x1000(%rax,%rax), %eax
mov %eax, 0x1000(%rax,%rax)
mov $7, %eax
0000000000000000 8b840000100000 movl 0x1000(%rax,%rax), %eax
0000000000000007 89840000100000 movl %eax, 0x1000(%rax,%rax)
000000000000000e b807000000 movl $0x7, %eax
Based on this POC alone, it's pretty much impossible to guess how much slower a real `mov` only compiler would be vs. a regular compiler. It depends a lot on how much of this can be optimized. Directly compiling C to this via clang or gcc would be a good start. I have no idea how much work that would take though, and compiling anything more complex then BF is a real challenge in itself because of the branching problem.
That's not true.
Compilers would need to produce code that consists of standardized mov-only code patterns. This would help keep the CPU architectures relatively simple.
Coming very close to native x86 performance seems possible, at least in theory.
Just imagine the applications of this!
The next step would be to make this into an eventual Quine.
It's turtles all the way down.
Oh the world we live in: playing minesweeper in a graphical OS running in a javascript x86 emulator.
> The single instruction C compiler
I was seriously impressed until I got further down.
Maybe you have to reorganize if(a) { b; } else { c; } as a kind of permuted b; followed by c; such that either the permuted b; or the permuted c; are effectively no-ops depending on the value of a.
Replaces movs with less movs??
If you were comparing the performs of mov-only programs, a specialized cpu would likely be faster. Otherwise, there is a good reason we do not actually use Turing machines.
http://laughtonelectronics.com/Arcana/One-bit%20computer/One...
A bit less extreme: http://www.sccs.swarthmore.edu/users/06/adem/engin/e25/final...
The laws of physics get in the way. It's essentially the same reason why clock frequencies have stopped going up.
I believe such a CPU wouldn't end up simple due to competition for better performance. It would end up being more complex than x86 CPUs.
Or is it a Ridiculous Instruction Set ?
Which is quite amazing (and probably dog slow)
They cheat to get a jump without using anything but `mov`'s by executing an illegal set of `cs` using `mov`, and then use the sigill generated to execute a signal handler, which is just the same spot that the code starts at. IMO, it doesn't really count, so a `mov`-only program requires at least one jmp instruction to work.
I think loops are achieved by simply running the code to the end without saving any of the results, and then hitting the singal and going back to the beginning - ignoring all the code until you hit the loop you're executing. But, the `mov` code is fairly hard to understand so I could be wrong on that.
Two values a and b can be compared by storing 0 into * a and 1 into * b. Then a == b if * a is 1. Then this value can be used to index into an array to provide different behavior based on if a == b.
Edit: apparently HN doesn't allow me to escape * with \, which the markdown spec says I should be able to do.
So? What does the markdown spec have to do with... anything? The XML spec says you have to begin your comment with a version number declaration, but you're not doing that.
It's based on this paper: http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf
Even CPUs considered RISC today, like ARMs, need to decode instructions into one or more wider uops for efficient execution.
In any case I believe the point of the GP is that any necessary copy can be done by going through memory, so register-register moves can be dispensed with where minimalism is the goal.