[HN Gopher] x86 is Turing-complete with no registers (2014)
___________________________________________________________________
x86 is Turing-complete with no registers (2014)
Author : todsacerdoti
Score : 71 points
Date : 2023-01-03 16:22 UTC (6 hours ago)
(HTM) web link (mainisusuallyafunction.blogspot.com)
(TXT) w3m dump (mainisusuallyafunction.blogspot.com)
| thamer wrote:
| > 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?
| hinkley wrote:
| Everyone is finding a roundabout way to say "self modifying
| code"
| monocasa wrote:
| No 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.
| jstanley wrote:
| I'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 wrote:
| Or 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 wrote:
| Because by being indirect, you can change the jump target in
| 0x400000 via the result of alu ops.
| pclmulqdq wrote:
| A similarly funny x86 project compiles programs only to "MOV"
| instructions. It's very much Turing complete.
|
| https://github.com/xoreaxeaxeax/movfuscator
| simcop2387 wrote:
| The coolest proof of it being Turing complete is that there's a
| port of doom to it too
| pclmulqdq wrote:
| I think we're going to need a register-free Doom port too.
| robinsonb5 wrote:
| A 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 wrote:
| Some 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
| klelatti wrote:
| That's a really interesting question (on code density) - can
| you share your conclusions or even your project?
| dang wrote:
| Discussed at the time:
|
| _x86 is Turing-complete with no registers_ -
| https://news.ycombinator.com/item?id=7224061 - Feb 2014 (23
| comments)
| timerol wrote:
| Really 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]
| peter_d_sherman wrote:
| >"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-a...
| saagarjha wrote:
| x86 is Turing-complete with no instructions, too:
| https://github.com/jbangert/trapcc
| eesmith wrote:
| fwiw, 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
|
| [2] http://www.cs.jhu.edu/~sam/ccs243-mason.pdf
|
| [3] http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf
|
| [4] https://github.com/jbangert/trapcc
| helf wrote:
| Ok this is ridiculously entertaining. Thanks!
| wolf550e wrote:
| Add [2014] to title.
| tinus_hn wrote:
| Ask nicely.
| chungy wrote:
| Nice is overrated. The GP clearly identifies a problem and
| suggests a solution.
| saagarjha wrote:
| Nice is _never_ overrated.
| klodolph wrote:
| The original comment is as nice as it needs to be.
| saagarjha wrote:
| Done.
| woodruffw wrote:
| This 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.
| commandlinefan wrote:
| I can't find the exact quote or attribute it, but a good take
| was "the x86 instruction set isn't particularly complex - it
| just doesn't make a lot of sense".
| hangonhn wrote:
| This might be a bit of a tangent but what's the advantages and
| disadvantages of register-memory vs. load-store? Thanks!
| __s wrote:
| register-memory will involve a more complicated encoding (to
| designate addressing modes, tho arguably register/memory is
| only 1 bit, but that halves your register count for the same
| size encoding, & it gets messy because your addressing
| encoding itself will want to reference registers & then you
| add in offsets/scaling for r1+r2*4) & screws up cycle
| accurate instruction timing (because memory latency is cache
| dependent)
| oso2k wrote:
| RM machines usually have more Memory Modes with which to
| access memory. You can do a math op while indirectly
| accessing a memory address that depends on a calculation of
| that address and add and offset to it. So that makes
| programming many things easier. It's a little more how humans
| learn and think of math. Think using arrays, lists, vectors,
| hashes, trees. However, this often generates data
| dependencies which makes pipelining and ILP require more work
| to achieve efficiently. It also often makes the code dense.
|
| https://en.m.wikipedia.org/wiki/Register%E2%80%93memory_arch.
| ..
|
| LS is generally found in RISC machines and is also generally
| considered far easier to implement pipelining and ILP. Fewer
| and often simpler Memory Modes, more obvious or simpler to
| deduce data dependencies. But it often takes a few more
| instructions to complete an algorithm or even a simple
| expression. Less code density.
|
| https://en.m.wikipedia.org/wiki/Load%E2%80%93store_architect.
| ..
|
| There's also stack machines which approximate math well
| especially if you like RPN/prefix notation. They just tends
| to make logical constructs like loops look unfamiliar when
| compared to math or typical/popular programming languages. So
| it makes programming easy, compiling easy since it's
| relatively natural to analyze & compile expressions. Also,
| instructions can be extremely compact such as single bytes.
|
| https://en.m.wikipedia.org/wiki/Stack_machine
|
| Another slightly related take was VLIW. You take snippets of
| instructions (Basic Blocks in PL) that are known to fit
| certain pipelining or data dependencies rules. Theses blocks
| of code can then be executed concurrently since you have well
| established criteria. However making compilers able to
| predict when blocks should execute in the presence of a
| complex single processor turned out to make writing the
| compilers very complex.
|
| https://en.m.wikipedia.org/wiki/Very_long_instruction_word
| woodruffw wrote:
| In principle, load-store architectures are simpler to
| implement, simpler to write compilers for, simpler to write
| speculative optimizations for, and have denser/simpler
| instruction encodings. Similarly in principle, register-
| memory architectures are simpler to write assembly for as a
| human, and simpler to write _different_ speculative
| optimizations for.
| rwaksmunski wrote:
| I would imagine load-store to be simpler to implement in
| hardware.
| tenebrisalietum wrote:
| Idk ... 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.
| MobiusHorizons wrote:
| I 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.
| woodruffw wrote:
| I 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).
| rcgorton wrote:
| [dead]
| Someone wrote:
| So, 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?
___________________________________________________________________
(page generated 2023-01-03 23:01 UTC)