Upon rereading it, it seems the real insurmountable challenge is interrupts! It always seems like at that level of detail with this stuff, it becomes a decision to go slower in order to simulate NES hardware accurately. But my question is: how much code depends on that accuracy, and how much can you compromise for speed? A further question I have is can you do a cross game analysis of the whole NES library and find common patterns, reused functions, that you decompile into a kind of high level conversion that would hopefully or gloss over the need for specific functions to have that low level accuracy.
You can go well beyond several of the NES's limitations by fiddling with PPU parameters between scanlines, but that takes careful timing and almost nothing actually does that. Might only be democoders. If you're willing to ignore the possibility that someone did that, you should be able to just process a whole frame's worth of PPU at NMI time.
Super Mario Bros spends most of its time in an infinite loop, waiting for NMI to pull it out so it can start processing the next frame. If NMI triggers before this, you get a lag frame. Plenty of popular emulators get the wrong lag frames, but only speedrunners and TASers really care. So, for this game, you could possibly toss out the timing entirely and trigger NMI when you hit a busy loop. Your emulator will completely ignore all lag frames, but most people won't notice for at least this game.
(It's been over a decade since I was into ROM hacking so my memory could be faulty on any of this.)
One of the Ninja Turtles games shifts the x scroll back and forth a couple times per line during some of the opening screens. Skate or Die changes which CHROM bank to use for background tiles a couple times per frame in its inter-level screens. I solve that by logging PPU writes (address, value, cycle it would be received). In practice, most of those mid-frame writes don't change anything that matters to the CPU, but I need the info for rendering.
Rendering the scene at NMI without logging writes to the PPU works for a lot of games, but there are plenty that do mid-frame PPU changes (and it starts getting more difficult with more-advanced mappers including their own interrupts).
another approach could be getting runtime information from a running emulator, and record it onto a file the compiler could use to close the gaps you need but can't get from static analysis.
Unless the interrupt handler is trivially simple, you can't know how many cycles it will take to finish.
This has in fact been achieved in games like super mario world or pokemon!
It seems to me sometimes that educated programmers call halting problem too early on situations like this where you don't actually need a rock solid "provably correct" compiler, just a compiler that does something reasonable in this bounded set of cases, and we don't mind that much if it crashes sometimes, since it's not like an NES game is a rocket or a therac.
I assume the trouble with interrupts is the "interrupting", as the location to jump to could be kept in a prefilled table like stormbrew suggested for JMPs.
If the target instruction-set doesn't have any way of "interrupting" that could be used, could it instead be solved by inserting a compact interrupt check between every "line" of assembly?
Which makes me naively wonder if you could just run interrupts on a parallel thread.