Is 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]
X86 mov is turing complete: mov-only compiler
21–30 of 60 posts
Re: X86 mov is turing complete: mov-only compiler
#22Could be good to defeat RF snooping attacks.
Re: X86 mov is turing complete: mov-only compiler
#23Who needs instructions? Page faults are Turing complete: https://github.com/jbangert/trapcc
Re: X86 mov is turing complete: mov-only compiler
#24The Github description is misleading: > The single instruction C compiler I was seriously impressed until I got further down.
Well, 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).
Re: X86 mov is turing complete: mov-only compiler
#25Forgive 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.
Re: X86 mov is turing complete: mov-only compiler
#26Earlier quoted context omitted.
Even if they weren't a single mnemonic, if you read the paper you'll find that reg = mem[reg + C], mem[reg + C] = reg, and reg = C appear to be the only 3 instruction types that are actually needed; these are only register-memory and register-constant data transfers. Even register-register isn't needed.
register-register movs are needed because compilers are not the world's smartest code generators, and we don't have an infinite number of registers. The biggest problem arises when some calling convention expects certain things to be in certain registers - unless you do some pretty extreme long term planning in your register allocation code in the compiler, you're pretty likely to eventually wind up with some piece o…
Note that you don't need a dumb compiler, register pressure, or an instruction with physical register constraints to require a copy. Two-address instructions suffice: simply have a register for the first operand that contains a value that is used later. A copy is required to preserve the value stomped by the mutating instruction.
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.
Re: X86 mov is turing complete: mov-only compiler
#27HN discussion of the paper that this is based on: https://news.ycombinator.com/item?id=6309631
That 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 repurpose…
Also:
> 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.
Re: X86 mov is turing complete: mov-only compiler
#28Forgive 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 b…
Re: X86 mov is turing complete: mov-only compiler
#29The Github description is misleading: > The single instruction C compiler I was seriously impressed until I got further down.
Well, 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).
I meant that this software compiles brainfuck, rather than C. I was expecting a C compiler from the description.
Re: X86 mov is turing complete: mov-only compiler
#30Forgive 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 b…
It 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.