6 ms·
x86 is Turing-complete with no registers (2014)
- pclmulqdq 4y agoA similarly funny x86 project compiles programs only to "MOV" instructions. It's very much Turing complete. https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator
- simcop2387 4y agoThe coolest proof of it being Turing complete is that there's a port of doom to it too
- pclmulqdq 4y agoI think we're going to need a register-free Doom port too.
- robinsonb5 4y agoA few years ago a YouTube video about the movfuscator set me wondering about just how minimalist an instruction set could be without hurting code density (unsurprisingly programming with just MOVs yields spectacularly bad code density!) - and ultimately led to me embarking on my own toy CPU project!
- retrac 4y agoSome one-instruction machines are surprisingly code-efficient. Consider an instruction with four fields: A B C D. Words and addresses are normal two's-complement integers. Every cycle, the machine takes the value at address A, subtracts the value at address B, and stores it in address C. If the result of this, as a signed integer, is 0 or negative, it jumps to address D. Otherwise it take the next instruction. Using temporary values in RAM, self-modifying code and some constants, everything can be implemented with this single instruction. And a lot of it surprisingly efficiently. Some assembly-style syntax for such a machine: A B C D #0 #0 tmp destination Jump to destination. 0 - 0 = 0, so jump to D. The # is syntactic sugar for an immediate literal. The value is placed in an address and that address is used. Tmp is a memory address, a temporary scratch value. In my made-up syntax here this is implicit if there's no 4th field given: // move is simple src #0 dst // subtract srca srcb dst // negate #0 src dst Addition is an exercise left for the reader :) Let's use * as the current address in the program, known at compile/assembly time. We can do a cheap subroutine call: #0 (*+3) retaddress subroutine Negative of the return address of the next instruction is in retaddress. Result will always be negative for sensible addresses, so jump to subroutine. To return, just write the negative again back to the D field of an instruction: #0 retaddress (*+5) #0 #0 tmp tmp // last field will now have return address, jump Of course, writing self-modifying code without checking it is guaranteed to not work. I probably got the offsets and stuff wrong. But hopefully it gives the idea. Doing the same with the address fields lets you do arbitrary indirection and address calls and make a stack. Often 2 - 5 instructions. Everything a typical RISC machine can do can be done in 1 - 30 instructions. Except multiply, divide, and bitwise boolean operations on the whole word, because you have test and branch on each bit in an inconvenient way. I'm sure something more efficient is possible, but it's quite an improvement on the classic subleq code density. One-instruction set computer: https://esolangs.org/wiki/OISC https://esolangs.org/wiki/OISC
- klelatti 4y agoThat’s a really interesting question (on code density) - can you share your conclusions or even your project?
- robinsonb5 4y agoThe project was this: http://retroramblings.net/?page_id=1339 http://retroramblings.net/?page_id=1339 I ended up using a fixed instruction width of 8 bits, with eight classical registers (one of which is the program counter), and also a "temp" register which is used implicitly for opcodes which need a second operand. The code density is comparable to m68k and x86, better than 32-bit RISC ISAs, but not as good as the 16-bit compressed representations of 32-bit RISC ISAs.
- klelatti 4y agoThanks so much! Looks like a really great project. I'll have a full look through the blog later but just the summary of the code density results is very interesting (at http://retroramblings.net/?p=1414 http://retroramblings.net/?p=1414). Do you have a gut feel for what is happening here and why the compressed 32 RISC ISAs do so well compared to yours?
- robinsonb5 4y agoI think there are three reasons: one is that the code my compiler backend produces is "ok" but not fantastic (though it's somewhat better now than it was when that article was written) - another is that I have only 8 registers, and only five are available for the code generator to play with, so I have to spill registers onto the stack sooner than more register-rich ISAs - and finally my simplistic 8-bit instructions don't do as much as a RISC ISA's 16-bit instructions, so some of the advantage of them being only a single byte is lost.
- klelatti 4y agoThat makes a lot of sense. Thanks again for sharing such an interesting project.
- wolf550e 4y agoAdd [2014] to title.
- tinus_hn 4y agoAsk nicely.
- chungy 4y agoNice is overrated. The GP clearly identifies a problem and suggests a solution.
- saagarjha 4y agoNice is never overrated.
- chungy 4y agoIt is when there's a demand for toxic niceness. Not every situation requires fluffy words.
- saagarjha 4y agoWhen making a request it is traditional to recognize that you are asking a favor, however small, of someone else, and using a "please" can help signal that you are aware of this. Or, if you have an aversion to the p-word, just phrasing it as an appeal, e.g. "Can someone add [2014] to the title?", can help distinguish your ask from an order. I fail to see any toxicity in this phrasing. Of course, I changed the title regardless, so it's not like it "really mattered"; I wouldn't have replied to this conversation if someone didn't start this thread. I certainly don't intend to demand anything from anyone. But kindness is generally free or very cheap, so I find it to be smarter to err on the side of being nice. And that's on top of whatever moral framework or whatever you may have that guides you to be considerate, hold doors open for other people, whatever, that you do to make the world a better place.
- 4y ago
- woodruffw 4y agoThis is a funny result in the RISC and ARM world, but it makes perfect sense in x86: x86 is a register-memory architecture instead of a load-store architecture, so memory is (effectively) an extremely large register bank.
- tenebrisalietum 4y agoIdk ... this is like saying your local grocery store is effectively your extremely large kitchen, it ignores the logistics and cost of access that create planning or out-of-order requirements for best performance. > so memory is (effectively) an extremely large register bank. This was true-ish however in the late 70's/early 80's/1Mhz CPU days - but registers were always better even if slightly. The 6502, for example, could load the X register with an immediate value in 2 cycles, or from zero page (first 256 bytes of RAM) in 3 cycles, or from an arbitrary 16-bit address in 4 cycles. The few register-to-register operations all work in 2 cycles. (Then you have the TMS9900 that actually did use RAM as registers - only having 3 - one for the program counter, one for the status register, and a "workspace pointer" that told the CPU where the fake 'registers' lived.) Of course, x86 has elaborate caching mechanisms to help. Your freezer is still in your kitchen (cache), but you still have limited space you actually use to do work (countertop). What RAM is basically a superfast I/O device (which is why memory-mapped I/O is a thing). It's funny that the IBM mainframe for RAM - "storage" - kinda made more and more sense the more that RAM speed diverged from CPU speed.
- woodruffw 4y agoI meant in the computation-theoretic sense: x86 doesn’t distinguish between types of operands in the way that load-store architectures do, which means that this result (TC without register operands) is not a surprising one. You obviously shouldn’t use RAM as a naive replacement for GPRs in normal code (unless the goal is extremely fast JIT compilation where minimizing spills is not important).
- MobiusHorizons 4y agoI believe the parent was talking about the abstraction provided by the ISA, not whether it was a good way to program. None of this experiment cares about the execution speed at all, it merely concerns itself with the technical feasibility of the technique in the ISA. This would not be possible at all in a load store oriented ISA, because you can’t ever do an alu instruction without first loading into a register.
- timerol 4y agoReally cool article, but it's sad to read through all of the spam in the comments section. There appear to be 2 legitimate comments out of a few hundred
- deleted 4y ago[deleted]
- saagarjha 4y agox86 is Turing-complete with no instructions, too: https://github.com/jbangert/trapcc https://github.com/jbangert/trapcc
- helf 4y agoOk this is ridiculously entertaining. Thanks!
- eesmith 4y agofwiw, linked to from the article: > As others have shown, we can compute using alphanumeric machine code[1] or English sentences[2], using only the mov instruction[3], or using the MMU[4] as it handles a never-ending double-fault. Here is my contribution to this genre of Turing tarpit: x86 is Turing-complete with no registers. [1] http://www.phrack.org/issues.html?issue=57&id=15#article http://www.phrack.org/issues.html?issue=57&id=15#article [2] http://www.cs.jhu.edu/~sam/ccs243-mason.pdf http://www.cs.jhu.edu/~sam/ccs243-mason.pdf [3] http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf [4] https://github.com/jbangert/trapcc https://github.com/jbangert/trapcc
- thamer 4y ago> Conditional control flow is possible thanks to this gem of an instruction: ff242500004000 jmp qword [0x400000] How is this "conditional"? The article explains that it simply "jumps to whatever address is stored as a 64-bit quantity at address 0x400000", but where's the condition here?
- jstanley 4y agoI'm guessing: Create a 2-element array of branch targets. Compute a boolean condition function (0 or 1). Index into the 2-element array with this 0 or 1 value and write it into 0x400000, then jmp qword [0x400000].
- monocasa 4y agoOr know the difference between the addresses of the true pathway and the false pathway, multiply your 0 or 1 result by that difference and add that to whichever pathway's base is lower. No lookup table needed.
- monocasa 4y agoBecause by being indirect, you can change the jump target in 0x400000 via the result of alu ops.
- hinkley 4y agoEveryone is finding a roundabout way to say “self modifying code”
- monocasa 4y agoNo self modifying code needed, simply embracing pointer arithmetic more than is typically allowed without your sanity being brought into question. This technique works just fine with no changes to page permissions and W^X.
- ant6n 4y agoChanging and then calling a function pointer stored at some memory address isn’t really insane.
- peter_d_sherman 4y ago>"In a RISC architecture, every memory access is a register load or store, and our task would be completely impossible. But x86 does not have this property." In any architecture, including x86, every memory access is an ALU load or store, and our task would be completely impossible. >"But x86 does not have this property." The x86 does have this property(!) -- but it is hidden/abstracted away from the programmer -- by the use of x86 microcode between x86 instructions -- and the ALU... But -- an interesting and educational article nonetheless... All x86 registers -- are basically just abstracted views of an ALU and/or Memory (both possibilities are merged into one "view", depending on which CPU operation happened last!) -- which is now may be cached by the CPU (as opposed to being a direct view of the ALU) -- at a given CPU/ALU state/time...(!) https://www.joelonsoftware.com/2002/11/11/the-law-of-leaky-abstractions/ https://www.joelonsoftware.com/2002/11/11/the-law-of-leaky-a...
- Someone 4y agoSo, how much work would it be to tweak LLVM to output code for this hypothetical register-less x86? Is its architecture even flexible enough to support such a CPU?
- dang 4y agoDiscussed at the time: x86 is Turing-complete with no registers - https://news.ycombinator.com/item?id=7224061 https://news.ycombinator.com/item?id=7224061 - Feb 2014 (23 comments)
- rcgorton 4y ago[dead]