4 ms·

I think you’d find the opposite - that NES games use lots of weird unstructured or dynamic code tricks that make automated AOT static recompilation very difficu

by wk_end 5y ago

I think you’d find the opposite - that NES games use lots of weird unstructured or dynamic code tricks that make automated AOT static recompilation very difficult or impossible, in most cases. These things tend to be more common on older CPUs and in hand-written assembly code, not less.

derefr 5y ago
You're talking about this stuff: https://andrewkelley.me/post/jamulator.html#dirty-assembly-tricks https://andrewkelley.me/post/jamulator.html#dirty-assembly-t... Personally, I disagree with the author of that article's conclusion here, that the [only] "solution is to embed an interpreter runtime in the generated binary." You can statically recompile this code! You "just" need to run a concolic interpreter over the code, generating out new static instruction streams for each possible phi-node (branch) state, and then coalescing them back together where you find you've generated the same instruction stream. You can early-terminate these spec-exec paths when you find yourself back at an instruction postdominated by entirely static code [within the body of the unrolled runtime coroutine sequence]. Might sound like an unbounded exponential check, but in practice 1. merging back together will usually happen within, at most, five instructions, because these are almost always last-minute bit-packing-hacks to get code to fit within a given constrained ROM image size; and 2. there are always only two concolically-discoverable valid interpretations of a given instruction stream (if doing mid-instruction jumps), and only one concolically-discoverable valid interpretation of data-as-code / RAM-as-code. (NES games don't assemble and JIT arbitrary code streams. They don't have the work RAM for it. They're at most unpacking existing, non-arbitrary code streams; or taking something that is primarily a code stream, and then reusing it as data elsewhere, maybe a PRNG seed, or a 1-bit noise texture.) A large part of my job lately is decompiling and "reconstructing meaning" for object code compiled for lousy underspecified abstract-machine architectures. There are a lot of modern compiler-theoretic tools and tricks that can make short work of "statically" recompiling any but the hardest of hard cases. They're sadly virtually unknown outside of academia, though (probably because they're based on various graphical transformations of the code proposed after the Dragon Book was published, which is the point in history where most people in industry's knowledge of compilers seems to stop.)
- wk_end 5y ago
  Well, I know a good deal about old video game systems but you clearly know more about (re/de)compilers than I do, so although still skeptical I’ll defer to your expertise, while vaguely gesturing towards “lots of people would love the performance gains of static recompilation in our emulators, if it’s feasible please advance the state of the art” :) Pretty sure you’re still going to be stymied by things like cycle-counted code to line up I/O writes with the state of the hardware, though. I don’t suppose there’s tricks for that.
  - anyfoo 5y ago
    Cycle-accurate transpiling, now that sounds like a fun project. I think it would "only" have to be cycle-accurate between specific events, e.g. access to specific registers. (No idea how feasible this whole thing could be.)
    - monocasa 5y ago
      I remain skeptical (but would love to be proven wrong!). Most of the point of recompiling (JIT or AOT) is to amortize instruction decode and dispatch costs versus an interpreter. If you have to do the cycle accurate bookkeeping anyway, you're most of the way to the overhead of an interpreter again. There'll be some savings around partial instruction streams that don't have effects outside the CPU core that can just be run as a burst, but I'm not sure it'll be a game changing amount.
    - NobodyNada 5y ago
      > I think it would "only" have to be cycle-accurate between specific events, e.g. access to specific registers. That’s correct — but one of those events is external interrupts (from the graphics, audio, or cartridge hardware), which complicates things a bit since your “checkpoints” can be anywhere in the code rather than just at a specific set of register accesses. You could work around this by tracking cycles per-basic-block while running transpiled code, and falling back to cycle-accurate software emulation when you get close to a hardware interrupt.
- 5y ago
djmips 5y ago
Remember that NES games run from ROM for the most part. Wasting precious RAM on code is a vast minority of the cases.

by wk_end 5y ago

derefr 5y ago

You're talking about this stuff: https://andrewkelley.me/post/jamulator.html#dirty-assembly-tricks https://andrewkelley.me/post/jamulator.html#dirty-assembly-t... Personally, I disagree with the author of that article's conclusion here, that the [only] "solution is to embed an interpreter runtime in the generated binary." You can statically recompile this code! You "just" need to run a concolic interpreter over the code, generating out new static instruction streams for each possible phi-node (branch) state, and then coalescing them back together where you find you've generated the same instruction stream. You can early-terminate these spec-exec paths when you find yourself back at an instruction postdominated by entirely static code [within the body of the unrolled runtime coroutine sequence]. Might sound like an unbounded exponential check, but in practice 1. merging back together will usually happen within, at most, five instructions, because these are almost always last-minute bit-packing-hacks to get code to fit within a given constrained ROM image size; and 2. there are always only two concolically-discoverable valid interpretations of a given instruction stream (if doing mid-instruction jumps), and only one concolically-discoverable valid interpretation of data-as-code / RAM-as-code. (NES games don't assemble and JIT arbitrary code streams. They don't have the work RAM for it. They're at most unpacking existing, non-arbitrary code streams; or taking something that is primarily a code stream, and then reusing it as data elsewhere, maybe a PRNG seed, or a 1-bit noise texture.) A large part of my job lately is decompiling and "reconstructing meaning" for object code compiled for lousy underspecified abstract-machine architectures. There are a lot of modern compiler-theoretic tools and tricks that can make short work of "statically" recompiling any but the hardest of hard cases. They're sadly virtually unknown outside of academia, though (probably because they're based on various graphical transformations of the code proposed after the Dragon Book was published, which is the point in history where most people in industry's knowledge of compilers seems to stop.)

wk_end 5y ago
Well, I know a good deal about old video game systems but you clearly know more about (re/de)compilers than I do, so although still skeptical I’ll defer to your expertise, while vaguely gesturing towards “lots of people would love the performance gains of static recompilation in our emulators, if it’s feasible please advance the state of the art” :) Pretty sure you’re still going to be stymied by things like cycle-counted code to line up I/O writes with the state of the hardware, though. I don’t suppose there’s tricks for that.
- anyfoo 5y ago
  Cycle-accurate transpiling, now that sounds like a fun project. I think it would "only" have to be cycle-accurate between specific events, e.g. access to specific registers. (No idea how feasible this whole thing could be.)
  - monocasa 5y ago
    I remain skeptical (but would love to be proven wrong!). Most of the point of recompiling (JIT or AOT) is to amortize instruction decode and dispatch costs versus an interpreter. If you have to do the cycle accurate bookkeeping anyway, you're most of the way to the overhead of an interpreter again. There'll be some savings around partial instruction streams that don't have effects outside the CPU core that can just be run as a burst, but I'm not sure it'll be a game changing amount.
  - NobodyNada 5y ago
    > I think it would "only" have to be cycle-accurate between specific events, e.g. access to specific registers. That’s correct — but one of those events is external interrupts (from the graphics, audio, or cartridge hardware), which complicates things a bit since your “checkpoints” can be anywhere in the code rather than just at a specific set of register accesses. You could work around this by tracking cycles per-basic-block while running transpiled code, and falling back to cycle-accurate software emulation when you get close to a hardware interrupt.
5y ago

djmips 5y ago

Remember that NES games run from ROM for the most part. Wasting precious RAM on code is a vast minority of the cases.