Statically Recompiling NES Games into Native Executables with LLVM and Go • Hacker News Board

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

#61

Post by Someone » Fri, Jun 07, 2013, 6:42 PM UTC

AndyKelley wrote: post #10

Pxtl wrote: 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.

I hinted at the end what kind of technique I think might actually be useful: For example, one such technique is to identify a section of code, make some assumptions based on heuristics which allow for highly optimized native code generation, and then detect if those assumptions are broken. If the assumptions are broken, the generated native code is tossed, and emulation takes over. However, if the assumptions are uph…

You probably know it, but that approach is used everywhere, for example in JavaScript and ruby, where it is typically is impossible to prove much about your program (in some dark corner of the program, someone might redefine that function that appears to add one to a number, if the program is run on Thursdays)

I also have a minor, minor nitpick on the article: I think you should point out that those INY instructions, in general, are insufficient to increase 16-bit pointers. You have to check for wraparound, and increase the high byte if a value wraps to zero. Somebody must have checked (or hoped) that that didn't happen with these tables (developing with the long, safe form and replacing it by the short form before release is tricky, as shortening the code will move entry points)

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

#62

Post by nitrogen » Fri, Jun 07, 2013, 7:19 PM UTC

exch wrote: post #54

tibbon wrote: 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…

I've looked at this sort of stuff as utter voodoo for a long time. Then I ran into this book[1], and everything just kind of 'clicked' into place in my head. I can't recommend this book often enough. [1]: http://www.nand2tetris.org/book.php In short: It gives you a hands-on approach in designing and building your own computer and programming language, to end up writing and running your own games on the system. * It s…

Firefox indicates that nand2tetris.org has been reported as an attack page. Has the site been compromised? Anybody know how to contact the author?

Edit: just noticed the original Edit mentioning that you contacted one of the authors.

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

#63

Post by chadseibert » Fri, Jun 07, 2013, 7:22 PM UTC

acdha wrote: post #37

quux wrote: post #14

This is interesting. If this project can output LLVM byte code, then you could also codegen to javascript with emscripten and make a web based version of a NES game.

See also https://github.com/jsmess/jsmess which is a port of an existing emulator codebase using emscripten

I'm not quite sure what the point of this project is, as MESS is rather slow when built natively [1]. Perhaps some of the lower end systems can be emulated, albeit slowly.

[1] http://www.mess.org/faq#it_works_but_it_is_way_too_slow

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

#64

Post by nitrogen » Fri, Jun 07, 2013, 7:25 PM UTC

comex wrote: post #51

Somewhat off-topic, but to defend gcc against clang, here is a modern version of gcc with the correct warning option: $ gcc-4.8 -std=gnu99 -Wall -o test test.c test.c: In function 'main': test.c:6:5: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses] if (foo & 0x80 == 0x80) { ^ gcc 4.9 will have colored diagnostics, too. Cool project, though.

This would be a great way, on a compiler or project that doesn't have this warning enabled, to conceal a deliberate bug and have it appear to be accidental.

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

#65

Post by chadseibert » Fri, Jun 07, 2013, 7:26 PM UTC

I agree; this is quite amazing work! I've been meaning to do something like this; perhaps generate a native executable or something similar.

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

#66

Post by scrame » Fri, Jun 07, 2013, 7:40 PM UTC

exch wrote: post #54

tibbon wrote: 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…

I've looked at this sort of stuff as utter voodoo for a long time. Then I ran into this book[1], and everything just kind of 'clicked' into place in my head. I can't recommend this book often enough. [1]: http://www.nand2tetris.org/book.php In short: It gives you a hands-on approach in designing and building your own computer and programming language, to end up writing and running your own games on the system. * It s…

The Book, TECS [The Elements of Computing Systems] is great, but the version I have was missing a lot of stuff. There were certain parts of the hardware design that were missing or not really completeable with what was provided, and not a lot of follow-up resources.

The original guy who built a CPU in minecraft actually built it based on some of the exercises in that book. Good stuff overall.

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

#67

Post by tmzt » Fri, Jun 07, 2013, 8:14 PM UTC

exch wrote: post #54

tibbon wrote: 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…

I've looked at this sort of stuff as utter voodoo for a long time. Then I ran into this book[1], and everything just kind of 'clicked' into place in my head. I can't recommend this book often enough. [1]: http://www.nand2tetris.org/book.php In short: It gives you a hands-on approach in designing and building your own computer and programming language, to end up writing and running your own games on the system. * It s…

Might be a good candidate to port to asm.js or even just javascript, there are platforms without Java where this could be a valuable teaching tool.

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

#68

Post by tmzt » Fri, Jun 07, 2013, 8:14 PM UTC

exch wrote: post #54

tibbon wrote: 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…

I've looked at this sort of stuff as utter voodoo for a long time. Then I ran into this book[1], and everything just kind of 'clicked' into place in my head. I can't recommend this book often enough. [1]: http://www.nand2tetris.org/book.php In short: It gives you a hands-on approach in designing and building your own computer and programming language, to end up writing and running your own games on the system. * It s…

Might be a good candidate to port to asm.js or even just javascript, there are platforms without Java where this could be a valuable teaching tool.

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

#69

Post by delroth » Fri, Jun 07, 2013, 8:28 PM UTC

logic wrote: 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…

Constant propagation is not really cheating though: it's a completely safe and accurate optimization. We use that in the PPC->X86 Jit of the Dolphin Emulator to reduce register pressure and use the fact that X86 instructions can have 32 bit constants (while PPC is usually limited to 16 bit consts, and 32 bit values are loaded with 2 instructions: lis/ori). If you implement it properly, you can actually brag about it :) (we have an abstract object that can be either an X86 register or a constant value, and instruction handlers handle these two cases differently - when they can't, the constant is loaded to a register).

+1 for IDA Pro. It's a shame this software is so expensive. The UI is actually pretty decent when you get used to it, and there are a ton of good plugins.

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

#70

Post by delroth » Fri, Jun 07, 2013, 8:31 PM UTC

jmhain wrote: post #43

AndyKelley wrote: post #15

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?

You can't: as long as you have self mutating code (including loading more code in memory from another place), static recompiling is simply not possible. It's not a matter of being "better", it's the only solution.

As video game consoles start looking more and more like PCs, self mutating code starts to be less frequent and more easily detectable. On the Nintendo 3DS for example, only the OS can allocate executable pages, and executable pages are forced read-only. This means you could in theory do static recompilation of a 3DS game. This is the only case I know of though - all other recent video game consoles allow self mutating code or dynamic code loading.