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 ?
X86 mov is turing complete: mov-only compiler
11–20 of 60 posts
Re: X86 mov is turing complete: mov-only compiler
#12That'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…
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 of information in a register that you need to move to another register before making or returning from a call.
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.)
Re: X86 mov is turing complete: mov-only compiler
#13Earlier quoted context omitted.
If you're going down that path, all of x86 is used as a 'bytecode' that turns into microcode instructions anyway in modern processors.
Not exactly, most instructions are not "microcoded" for performance reasons. But there is a class of instructions that is.
Intel 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
Re: X86 mov is turing complete: mov-only compiler
#14[deleted]
Re: X86 mov is turing complete: mov-only compiler
#15Sounds 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.
http://copy.sh/v86/
It's turtles all the way down.
Re: X86 mov is turing complete: mov-only compiler
#16Earlier 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…
Do you have a citation for the 168GP registers, just wondering if Intel have "offically" stated the number they use in a given microarch.
Re: X86 mov is turing complete: mov-only compiler
#17Earlier quoted context omitted.
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…
Do you have a citation for the 168GP registers, just wondering if Intel have "offically" stated the number they use in a given microarch.
You can find an official Intel source for Haswell in here (page 15): http://pages.cs.wisc.edu/~rajwar/papers/ieee_micro_haswell.p...
Re: X86 mov is turing complete: mov-only compiler
#18Earlier quoted context omitted.
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…
Do you have a citation for the 168GP registers, just wondering if Intel have "offically" stated the number they use in a given microarch.
I might be misreading this, but I think it's on slide 24 of this PDF http://www.hotchips.org/wp-content/uploads/hc_archives/hc25/...
Re: X86 mov is turing complete: mov-only compiler
#19Earlier quoted context omitted.
Not exactly, most instructions are not "microcoded" for performance reasons. But there is a class of instructions that is.
Intel 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
For 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.
Re: X86 mov is turing complete: mov-only compiler
#20It's a superset of the One Instruction Computer
https://en.wikipedia.org/wiki/One_instruction_set_computer