Live data from Hacker News

Statically Recompiling NES Games into Native Executables with LLVM and Go

andrewkelley.me

41–50 of 103 posts

Re: Statically Recompiling NES Games into Native Executables with LLVM and Go

#41
post #28

Earlier quoted context omitted.

It's really unfortunate that libcpu didn't take off. Last I checked, they got nowhere with no contributors, and now their site 503s. It was an interesting project.

I think it's more than that. It is not yet clear that this approach can work in the general case without emulation: the halting problem may be in the way.

Correct. If you think about it, the program could prompt the user for the address to jump to, and then the program could go there. In fact, that's exactly what some games (accidentally) do: http://tasvideos.org/2341M.html

It is impossible to solve this statically. This is why dynamic recompilation is more practical.

Re: Statically Recompiling NES Games into Native Executables with LLVM and Go

#42
I had a similar idea to this that I never really put in practice which was doing some sort of static recompilation but to higher level code in order to make open source versions of some NES games that could be used by other people to do the same. Accuracy would not be a concern as big as a pure emulation project.

I never got past the reading phase.

Re: Statically Recompiling NES Games into Native Executables with LLVM and Go

#43

Modern PS2 emulators - which is to say, pcsx2 - uses dynamic recompilation to execute games at useful speed. Static recompilation might not be a useful technique, but did you consider a dynamic version? What caveats are there?

About halfway through the project I realized that static recompilation is pointless and that dynamic is the way to go. I felt like it was worthwhile to at least get to the "able to play super mario 1" checkpoint before quitting. I did not do any investigation into dynamic recompilation other than pondering about it and concluding that it is more practical than static.

Why is static pointless and why is dynamic better? If emulating a newer game console, couldn't you get better performance by running a statically recompiled game, since it doesn't have to do the extra work at runtime? Or better yet, couldn't you cross-recompile a game to run it on a platform that couldn't normally handle emulation of the target platform?

Re: Statically Recompiling NES Games into Native Executables with LLVM and Go

#44
post #2

This is one excellent read! Thanks to the author for writing this down. Not that i'm not interested in the NSA, but this is a welcome diversion. And something I wanted to play with myself for a long time.

Thank you. I do not write often, so this was a challenge for me. Constructive criticism welcome.

I thought it was an excellent experiment and I really appreciate everything you did. I wanted to suggest though, particularly in the "Assembly" part, as an example, that you should link to something like paste bin for the code rather than placing it in-line. Unless you're referring to specific aspects of the code immediately before or after, it's not useful to see the actual code posted in-line, in general. And even then, you should select small snippets of the code (as you did elsewhere in the article). Small nitpick though, thanks for the work, and for writing up everything.

Re: Statically Recompiling NES Games into Native Executables with LLVM and Go

#45
Just a quick note about the disassembly challenge he faced (indirect references), having gone through this before: you can get amazingly good results by cheating a bit. That is to say, rather than assuming you actually have to properly execute through the code path, you can get very close by roughly tracking register assignments when making your initial pass through a block of code. (Even better, if you can track potential ranges of values with later calls into a given block. Some of this depends on how you've implemented your disassembler, though.)

I ended up doing this with a SuperH disassembler (with SH2, due to its two-byte opcode layout, indirect addressing is the order of the day), and by doing basic register assignment tracking and adding a few crude heuristics, I was able to get very usable results. No, the end result won't be "pretty"; you'll be moderately embarrassed to show it off., but it will work. :)

(Heuristics: one structure that I had to manually handle were compiler-generated jump tables; thankfully, for my project, I'd had a bit of help from the compiler that was used, and there were distinct signatures I could key off of.)

If you're even remotely interested in the disassembly aspect of this, I'd recommend learning a bit about a piece of software called IDA Pro: https://www.hex-rays.com/products/ida/ As horrible as the UI of it is, there is simply nothing better on the market for reverse engineering analysis.

Re: Statically Recompiling NES Games into Native Executables with LLVM and Go

#46
post #4

... while it's not really useful for the NES, which is so old that emulating it does not strain even the crudest modern processor, I'd be excited to see this technique applied to newer consoles for lightweight mobile processors.

Personally was very interested in this experiment after seeing this article yesterday: http://www.tested.com/tech/gaming/456272-straightforward-gui...;

Re: Statically Recompiling NES Games into Native Executables with LLVM and Go

#47
post #43

Earlier quoted context omitted.

About halfway through the project I realized that static recompilation is pointless and that dynamic is the way to go. I felt like it was worthwhile to at least get to the "able to play super mario 1" checkpoint before quitting. I did not do any investigation into dynamic recompilation other than pondering about it and concluding that it is more practical than static.

Why is static pointless and why is dynamic better? If emulating a newer game console, couldn't you get better performance by running a statically recompiled game, since it doesn't have to do the extra work at runtime? Or better yet, couldn't you cross-recompile a game to run it on a platform that couldn't normally handle emulation of the target platform?

Dynamic lets you do lots of nasty tricks, and also lets you detect and work around various nasty tricks at runtime (worst case by falling back to emulation). Consider that old games often would use self-modifying code, for example. Reliably statically detecting self-modifying code can be extremely hard even when it's not intentionally obfuscated. But at runtime it is "easy": Write protect all the code pages, and trap page-faults, and either modify the offending code, or fall back to emulation.

In general, I think dynamic approaches are ideal when you're dealing with a "hostile" environment where the software you're translating was written with no expectation that it would be translated, and possibly (like with old games) in a situation where the programmer may have tried to really maximally exploit the hardware, because it means failure to statically determine that something weird is going on can often be counteracted much simpler by detecting attempts at violating your assumptions.

You can do hybrid approaches, and statically make a "best effort" and include similar methods to trap stuff that breaks your assumptions and fall back to JIT or emulation, but if you do that then there's a tradeoff between how much dynamic stuff you need to be able to do before it's easier to just do everything dynamically from the start.

The performance thing is not so easy to ascertain. JIT'ing code takes a bit of time, but not much compared to the expected overall time the program will be run afterwards. Static compilation can spend more time doing optimisations, but JIT's at least in theory have more information to work with (can detect the specific processor version, and use specialised instructions or alter instruction selection, for example, or could at least in theory even do tricks like re-arranging data to get better cache behavior (I have no idea if any existing JITs actually do that) based on profiling access patterns for the current run.

Re: Statically Recompiling NES Games into Native Executables with LLVM and Go

#48
post #17

This is amazing. Also, this is the Dark Magic of programming that I don't think I'll 100% grok in 20 years, but its good to try! edit: now that I think of it, I really need to keep expanding my knowledge. I'm going to go through this post in my terminal and try to at least make the stuff work, so I can start understanding this process. I've been trying to learn Go and C better anyway. Thanks for providing a ground to…

My mantra is "It's all just code." If you want an overview of systems topics, take a look at the webpage for the book "Computer Systems: A Programmer's Perspective": http://csapp.cs.cmu.edu

The CMU professors who made the book also have a course at CMU which uses the book as a textbook. I TAed a course at Virginia Tech that used the textbook. I thought the course does an excellent job in demystifying many systems concepts.

Re: Statically Recompiling NES Games into Native Executables with LLVM and Go

#49
post #45

Just a quick note about the disassembly challenge he faced (indirect references), having gone through this before: you can get amazingly good results by cheating a bit. That is to say, rather than assuming you actually have to properly execute through the code path, you can get very close by roughly tracking register assignments when making your initial pass through a block of code. (Even better, if you can track pot…

Second this. There are a lot of "signatures" in most asm. Programmers for 6502 and derivatives might be a nasty bunch of sadists that love to do weird stuff to save cycles, but even there there are lots and lots of common patterns that often "happened" just because people learned from the same sources, or because it made sense, or because conventions appeared.

I never had a NES, but I had a C64, and the 6502 code wrote there seemed nasty to translate on the surface, with lots and lots of self-modification, for example. But in the end most of the self modification was specific looping patterns because the 6502 can only index 256 values, and so many loops involved writing addresses into the looping code, iterate 256 times, increase the most significant byte directly in the code and see if you'd reached the end, and jump back to iterate 256 times.

Most of this "nasty" stuff is relatively well known by now and much of it is relatively regular and easy to detect.

Re: Statically Recompiling NES Games into Native Executables with LLVM and Go

#50

Earlier quoted context omitted.

I think it's more than that. It is not yet clear that this approach can work in the general case without emulation: the halting problem may be in the way.

Correct. If you think about it, the program could prompt the user for the address to jump to, and then the program could go there. In fact, that's exactly what some games (accidentally) do: http://tasvideos.org/2341M.html It is impossible to solve this statically. This is why dynamic recompilation is more practical.

Sure. It could be argued that "general case" is a bit more restricted than that for actual useful software in the wild, but that would still break any program with a JIT.

Sadly, emulation seems to be the way to go.

Post reply on HN