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

31–40 of 60 posts

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

#31

Post by nickodell »

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…

It's not just mov's. There's a non-branching jump at the end that loops back to the beginning. Termination is accomplished by reading from address 0.

It's based on this paper: http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

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

#32

Post by gnu8 »

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?

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

#33

Post by thaumasiotes »

Buge wrote: post #30
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…

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.

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

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

#34

Post by [deleted] »

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?

[deleted]

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

#35

Post by asdfaoeu »

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?

Might want to look at the examples. They turn an equality check into two register stores and a load.

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

#36

Post by DSMan195276 »

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

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

#37

Post by [deleted] »

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…

[deleted]

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

#38

Post by gizmo686 »

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?

Well, 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.

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

#39

Post by DSMan195276 »

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

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

#40

Post by Buge »

thaumasiotes wrote: post #33
Buge wrote: post #30

Earlier quoted context omitted.

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.

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

I 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.
Post reply on HN