4 ms·
X86 mov is turing complete: mov-only compiler
- pokle 11y agoHN discussion of the paper that this is based on: https://news.ycombinator.com/item?id=6309631 https://news.ycombinator.com/item?id=6309631
- jordigh 11y agoThat paper is so funny: Finding Turing-completeness in unlikely places has long been a pastime of bored computer scientists. And 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. Well, I guess someone has implemented it now!
- cwre 11y agoAlso: > 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.
- pslam 11y agoThat's a fun program. Similar techniques to this are used to create "ROP" (return-oriented programming) exploits. You get enough building blocks to get general purpose programming, and it's "just" matter of mapping to those building blocks. 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.
- vardump 11y agoARM mov can be used as a JMP <addr in reg>. Program counter is in fact register R15 in ARM.
- StillBored 11y agoThis changed with V8, IIRC the PC can only be updated on branch or an exception...
- jimmaswell 11y agoIf you're going down that path, all of x86 is used as a 'bytecode' that turns into microcode instructions anyway in modern processors.
- pmalynin 11y agoNot exactly, most instructions are not "microcoded" for performance reasons. But there is a class of instructions that is.
- delroth 11y agoIntel CPUs translate x86 to some internal RISC-like "uops" before doing optimizations and execution. This is a widely documented fact (though Intel doesn't really talk publicly about it as far as I know): see for example §2.1 in http://www.agner.org/optimize/microarchitecture.pdf http://www.agner.org/optimize/microarchitecture.pdf
- userbinator 11y agoFor marketing reasons, Intel made quite a big commotion over the fact that its Pentium was "RISC-like" when it was first released, but in reality what it meant was using a decoder that could emit multiple uops in parallel instead of sequentially like it was in the 486. Even CPUs considered RISC today, like ARMs, need to decode instructions into one or more wider uops for efficient execution.
- 11y ago
- cordite 11y agoSounds like if we make a JS to BF transpiler, then we can complete this with any language that can be transpiled to JS. Just imagine the applications of this! The next step would be to make this into an eventual Quine.
- Sir_Cmpwn 11y agoThe Github description is misleading: > The single instruction C compiler I was seriously impressed until I got further down.
- andrewflnr 11y agoWell, if it reaches a point where it can compile itself, you'll get your compiler written with just one instruction (assuming that's what you were hoping for).
- Sir_Cmpwn 11y agoI meant that this software compiles brainfuck, rather than C. I was expecting a C compiler from the description.
- Rexxar 11y agoIs there a way to estimate how many time slower would be a program compiled to use only "mov" instead of standard instructions ? 3x, 10x, 100x, more ?
- deleted 11y ago[deleted]
- DSMan195276 11y agoIt depends. In this case, I would say it would be at least 100x, probably much more. But, that's because this only compiles BF (It is basically a POC after-all), and thus you have to use that as an intermediate language. BF is extremely un-optimal, and the compiler here spits out a completely unoptimized one-to-one conversion of the BF source to assembly that uses only `mov` instructions. Thus, the size of the assembly will balloon extremely quickly simply because it takes a lot of BF to express fairly simple things. Branching using only `mov` is also impossible, so the code instead uses a flag to control where the assembly writes it's results. Because of this, even when you hit the condition of a loop, if your condition check is before the loop's code, then it results in you running the entire loop's code another time, and just throwing out the results. It's extremely wasteful. 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.
- 0xe2-0x9a-0x9b 11y ago"compiling anything more complex then BF is a real challenge in itself because of the branching problem." That's not true.
- 0xe2-0x9a-0x9b 11y agoIt is very hard to estimate the relative speed of a mov-only CPU (with a jump at the end of the program). The mov-only restriction applies only to how a program is input into the machine, it does not restrict the CPU architecture in any way. Obviously, the CPU would first analyze the whole mov-only program and convert it into something that is closer to x86 instructions: arithmetic instructions, unconditional jumps, conditional jumps. The success of this procedure, and ultimately the execution speed, depends on how many mov-patterns the CPU can recognize. 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.
- deleted 11y ago[deleted]
- bsder 11y agoIt's a superset of the One Instruction Computer https://en.wikipedia.org/wiki/One_instruction_set_computer https://en.wikipedia.org/wiki/One_instruction_set_computer
- spiritplumber 11y agoCould be good to defeat RF snooping attacks.
- M2Ys4U 11y agoWho needs instructions? Page faults are Turing complete: https://github.com/jbangert/trapcc https://github.com/jbangert/trapcc
- billforsternz 11y agoForgive my ignorance but I thought being Turing complete was important because a Turing complete machine can in principle perform any arbitrary computation. As far as I know the program counter cannot be a destination for an X86 MOV. So you can't branch with only MOVs. How can you do an arbitrary computation if you can't branch? 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.
- jacobwcarlson 11y agohttp://www.cl.cam.ac.uk/~sd601/papers/mov.pdf http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf
- Buge 11y agoIt also uses a single jmp instruction to branch back to the start in a loop. 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.
- thaumasiotes 11y ago> 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.
- Buge 11y agoI thought it was trying to implement markdown by italicizing half my sentence when I put * in. Markdown was what popped into my mind when I saw that behavior. It would be nice if I could find a way of escaping them without having to insert spaces where I don't want spaces.
- gnu8 11y agoThis is almost surely a dumb question, but what would happen if someone made a processor that only executed mov instructions, which would be extremely simple, and presumably would be really goddamn fast. Would that be competitive with today's fastest CPUs? If it were, what would be the advantages and disadvantages of this design?
- deleted 11y ago[deleted]
- asdfaoeu 11y agoMight want to look at the examples. They turn an equality check into two register stores and a load.
- gizmo686 11y agoWell, Turing machines do not have random access memory (which changes the big-theta complexity of algorithms), and that operations such as multiplications would be complicated and multi-cycle, whereas conventional CPUs can easily parralize them. 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.
- userbinator 11y agowhat would happen if someone made a processor that only executed mov instructions, which would be extremely simple, and presumably would be really goddamn fast. The laws of physics get in the way. It's essentially the same reason why clock frequencies have stopped going up.
- sklogic 11y agoAn extreme example: http://laughtonelectronics.com/Arcana/One-bit%20computer/One-bit%20computer.html http://laughtonelectronics.com/Arcana/One-bit%20computer/One... A bit less extreme: http://www.sccs.swarthmore.edu/users/06/adem/engin/e25/finale/ http://www.sccs.swarthmore.edu/users/06/adem/engin/e25/final...
- 0xe2-0x9a-0x9b 11y ago
- exabrial 11y ago"-O" enables optimizations Replaces movs with less movs??
- makeset 11y agoFewer.
- raverbashing 11y agoWhen I read the title I thought "ah of course cmov is turing complete", but no, it's only mov apparently. Which is quite amazing (and probably dog slow)
- liotier 11y agoExtremely Reduced Instruction Set Computer. Or is it a Ridiculous Instruction Set ?
- __alexs 11y agoOne instruction set computer. https://en.wikipedia.org/wiki/One_instruction_set_computer https://en.wikipedia.org/wiki/One_instruction_set_computer