Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

X86 mov is turing complete: mov-only compiler

github.com

Post reply on HN
Print view View original

51–60 of 60 posts

Re: X86 mov is turing complete: mov-only compiler

#51

Post by sklogic »

gnu8 wrote: post #32

This 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?

An extreme example:

http://laughtonelectronics.com/Arcana/One-bit%20computer/One...

A bit less extreme: http://www.sccs.swarthmore.edu/users/06/adem/engin/e25/final...

Re: X86 mov is turing complete: mov-only compiler

#52

Post by ackalker »

Sir_Cmpwn wrote: post #29
andrewflnr wrote: post #24

Earlier quoted context omitted.

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.

From README.md:

    M/o/Vfuscator 2.0 is a complete C compiler, and will be available soon.
Just be patient, or submit patches :-)

Re: X86 mov is turing complete: mov-only compiler

#53

Post by 0xe2-0x9a-0x9b »

DSMan195276 wrote: post #36
Rexxar wrote: post #11

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 ?

It 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 assemb…

"compiling anything more complex then BF is a real challenge in itself because of the branching problem."

That's not true.

Re: X86 mov is turing complete: mov-only compiler

#54

Post by 0xe2-0x9a-0x9b »

Rexxar wrote: post #11

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 ?

It 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.

Re: X86 mov is turing complete: mov-only compiler

#55

Post by nitrogen »

DSMan195276 wrote: post #39
billforsternz wrote: post #25

Forgive 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…

You're right, they never actually do any jumping. From what I can tell, they use a variable called `on` to control where every set of commands write their results too. They do some funky `mov` stuff to do a comparison, and then set `on` with that comparison. They use a stack of `on` variables and then pop off the value of `on` from that stack when you exit a loop. They cheat to get a jump without using anything but `…

Could one use self-modifying code (such as rewriting the SIGILL handler) to simplify this a bit?

Re: X86 mov is turing complete: mov-only compiler

#56

Post by pslam »

userbinator wrote: post #7
pslam wrote: post #3

That'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.

Yes, and these are effectively 3 different instructions sharing the same mnenomic. If you assemble them:

        mov     0x1000(%rax,%rax), %eax
        mov     %eax, 0x1000(%rax,%rax)
        mov     $7, %eax
You get:

        0000000000000000	8b840000100000  	movl	0x1000(%rax,%rax), %eax
        0000000000000007	89840000100000  	movl	%eax, 0x1000(%rax,%rax)
        000000000000000e	b807000000      	movl	$0x7, %eax
Which is basically 0x8b->Load, 0x89->Store, 0xb8->Constant.

Re: X86 mov is turing complete: mov-only compiler

#57

Post by StillBored »

vardump wrote: post #10
pslam wrote: post #3

That'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…

ARM mov can be used as a JMP . Program counter is in fact register R15 in ARM.

This changed with V8, IIRC the PC can only be updated on branch or an exception...

Re: X86 mov is turing complete: mov-only compiler

#58

Post by mastax »

shaftoe wrote: post #15
cordite wrote: post #4

Sounds 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.

I'm not sure if I'm more amazed by how slow that is or how fast it is.

Oh the world we live in: playing minesweeper in a graphical OS running in a javascript x86 emulator.

Re: X86 mov is turing complete: mov-only compiler

#59

Post by 0xe2-0x9a-0x9b »

gnu8 wrote: post #32

This 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?

"a processor that only executed mov instructions, which would be extremely simple"

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.

Re: X86 mov is turing complete: mov-only compiler

#60

Post by masklinn »

ackalker wrote: post #52
Sir_Cmpwn wrote: post #29

Earlier quoted context omitted.

I meant that this software compiles brainfuck, rather than C. I was expecting a C compiler from the description.

From README.md: M/o/Vfuscator 2.0 is a complete C compiler, and will be available soon. Just be patient, or submit patches :-)

Would be an interesting LLVM code generator too.
Post reply on HN