Pocketnes On Gba

[neko]

I was looking at emulators and came across PocketNES, which emulates an 8-bit Nintendo on a 16.78 MHz Game Boy Advance, and started wondering how they did that.

Unlike other optimized emulators of the same era, it does not use dynamic recompilation. This is surprising because the TuxNES developers claimed that this technique gave a 7x speedup over an interpreter. (See http://sourceforge.net/mailarchive/message....O413%403e8.org ) With this optimization, TuxNES ran about a third the speed of an equivalently-clocked native CPU (ie it would have taken a 5.37MHz CPU just to emulate the 1.79MHz NES CPU, without graphics rendering)

That kind of speed would make NES emulation on a GBA possible, but PocketNES does not use a dynamic recompiler, it uses a regular fetch-and-execute-each-instruction interpreter. So how'd Loopy and Flubba do it?

The ARM7TDMI has a 3-stage pipeline, so the instruction lookup plus branch only takes 4 CPU cycles, which is what you would save by using a recompiler. (This would take many more cycles on a Cortex-A8.) Still when you add the cycle count, flag setting, and emulating the actual instruction, you're up to a minimum of 7 cycles per instruction using the interpreter, and probably more like 10 on average.

Anyone know what percent of the CPU time it actually uses? It's got to be using at least half just to emulate the 6502, which doesn't leave much to do the graphics.

 

[lulzfish]

So how'd Loopy and Flubba do it?

Why don't you ask them?

 

[Reesy]

PocketNES is fast because it uses the GBA's graphics hardware to generate the NES graphics.

 

[Exophase]

I was looking at emulators and came across PocketNES, which emulates an 8-bit Nintendo on a 16.78 MHz Game Boy Advance, and started wondering how they did that.

Unlike other optimized emulators of the same era, it does not use dynamic recompilation. This is surprising because the TuxNES developers claimed that this technique gave a 7x speedup over an interpreter. (See http://sourceforge.net/mailarchive/message....O413%403e8.org ) With this optimization, TuxNES ran about a third the speed of an equivalently-clocked native CPU (ie it would have taken a 5.37MHz CPU just to emulate the 1.79MHz NES CPU, without graphics rendering)

That kind of speed would make NES emulation on a GBA possible, but PocketNES does not use a dynamic recompiler, it uses a regular fetch-and-execute-each-instruction interpreter. So how'd Loopy and Flubba do it?

The ARM7TDMI has a 3-stage pipeline, so the instruction lookup plus branch only takes 4 CPU cycles, which is what you would save by using a recompiler. (This would take many more cycles on a Cortex-A8.) Still when you add the cycle count, flag setting, and emulating the actual instruction, you're up to a minimum of 7 cycles per instruction using the interpreter, and probably more like 10 on average.

Anyone know what percent of the CPU time it actually uses? It's got to be using at least half just to emulate the 6502, which doesn't leave much to do the graphics.


It doesn't really take that much to emulate a ~1.7MHz 6502. On average the CPU takes about 4 cycles per instruction, for a typical cap of around 400K instructions per second. At 16.7 million cycles per second, GBA has a budget of a good 40 cycles per instruction for NES emulation. Other parts of NES emulation, including video and audio, are done using GBA hardware and have very little CPU cost.

"Other" optimized emulators of the same era most certainly did not use dynamic recompilation, by and large (look at emulators like NESticle and you'll find that they're interpretive). The numbers you have on TuxNES seem highly misleading when used in this context. First of all, it's comparing an 6502 interpreter that is probably written in C and may have any number of additional inefficiencies. FluBBa's ARM ASM 65xx interpreters are extremely efficient, and do many things that a C compiler would never be able to do.

When you say that TuxNES would have needed a 5.37MHz "native" CPU what does it mean exactly? A 5.37MHz modern x86? Because x86 can typically execute at least 2-3 instructions per cycle, giving it an 8-12x or so instructions per cycle advantage over the 6502. Add in the 3x clock multiplier and we're looking at 24-36 or so cycles per instruction, which is not bad but isn't highly amazing. Of course one has to ask how they came about these numbers to begin with. If the game frequently hits memory accesses that take a lot of overhead to emulate then it'll need many more cycles than the NES would. And a recompiler wouldn't always help enough with that.

I've looked at TuxNES's dynarec before and I didn't see anything that wonderful as far as recompilers go. Generally people haven't bothered with recompilation because NES's video is so much "faster" than its CPU, and it takes a more CPU time to emulate it than it does to interpret the 6502.

Of course you might say this doesn't apply to GBA where hardware is used for the video. That's true, but there are other prohibitive factors that makes dynamic recompilation infeasible on GBA. Mainly, GBA just doesn't have enough memory. Especially fast zero-waitstate memory where you'd want the recompiled code to run out of - it only has 32KB of this, and it has to share it for data and code. There just isn't enough to store and track an appreciable amount of recompiled code when you look at everything else that is needed for emulating NES.

Another factor is that a typical recompiler will sacfrifice cycle precision (in responding to things such as external events, interrupts, etc) in order to emulate a lot of instructions at once without having to check cycles. If you require that cycles are checked after every instruction as they would be in an interpreter then your recompiled code size will balloon up even more. This kind of inaccuracy that typical recompilers add tends to be fine on more modern CPUs, but doesn't work so well on something like NES that is very timing sensitive.

I don't know how much CPU time 6502 interpretation takes in PocketNES, but I do know that it's < 100%, which is all that really matters.

 

[neko]

It doesn't really take that much to emulate a ~1.7MHz 6502. On average the CPU takes about 4 cycles per instruction, for a typical cap of around 400K instructions per second. At 16.7 million cycles per second, GBA has a budget of a good 40 cycles per instruction for NES emulation. Other parts of NES emulation, including video and audio, are done using GBA hardware and have very little CPU cost.

"Other" optimized emulators of the same era most certainly did not use dynamic recompilation, by and large (look at emulators like NESticle and you'll find that they're interpretive). The numbers you have on TuxNES seem highly misleading when used in this context. First of all, it's comparing an 6502 interpreter that is probably written in C and may have any number of additional inefficiencies. FluBBa's ARM ASM 65xx interpreters are extremely efficient, and do many things that a C compiler would never be able to do.

When you say that TuxNES would have needed a 5.37MHz "native" CPU what does it mean exactly? A 5.37MHz modern x86? Because x86 can typically execute at least 2-3 instructions per cycle, giving it an 8-12x or so instructions per cycle advantage over the 6502. Add in the 3x clock multiplier and we're looking at 24-36 or so cycles per instruction, which is not bad but isn't highly amazing. Of course one has to ask how they came about these numbers to begin with. If the game frequently hits memory accesses that take a lot of overhead to emulate then it'll need many more cycles than the NES would. And a recompiler wouldn't always help enough with that.

I've looked at TuxNES's dynarec before and I didn't see anything that wonderful as far as recompilers go. Generally people haven't bothered with recompilation because NES's video is so much "faster" than its CPU, and it takes a more CPU time to emulate it than it does to interpret the 6502.

I don't know how many NES emulators used dynamic recompilation, but it certainly was tried.

I looked at the source code for tuxnes and pocketnes, and they use many of the same optimizations, such as storing the N and Z flags in one location and the C flag in another. Also both seem to have fairly accurate cycle counting, including adding a cycle when crossing page boundaries. PocketNES has an additional optimization where it stores the cycle count and carry flag in the same register.

The TuxNES benchmarks were done on a Celeron 366, which resulted in a speed of 4250 fps, 70x faster than a NES, or the equivalent of a NES running at 125.3 MHz, which gives a clock speed ratio of 125.3/366 = 0.34.

Tuxnes definitely isn't generating 24-36 instructions per 6502 instruction, it's more like 5 or so. If it's using that many pipeline slots, it's due to cache misses or pipeline stalls for other reasons. Intel's CPUs are optimized for 32-bit code, and do not schedule 8-bit instructions well. The celeron seems to be averaging less than one instruction per clock on this code.

Anyway, the RAM limit probably makes this infeasible on the GBA. As for the graphics, it does have to remap the palettes and scale the tiles, which is not completely trivial, and does take some CPU time.

 

[Exophase]

I don't know how many NES emulators used dynamic recompilation, but it certainly was tried.

Not commonly, and not during the early years of NES emulation. It's more of a novelty than anything.

I looked at the source code for tuxnes and pocketnes, and they use many of the same optimizations, such as storing the N and Z flags in one location and the C flag in another. Also both seem to have fairly accurate cycle counting, including adding a cycle when crossing page boundaries. PocketNES has an additional optimization where it stores the cycle count and carry flag in the same register.

It might count cycles accurately, but a typical dynamic recompiler won't check cycles remaining every instruction, for the reasons I gave above. If you're NOT checking every cycle then it makes more sense to retain the emulated flags in the x86 flags register, rather than putting them out to explicit registers.

Of course, having more registers on the ARM side helps a lot, and an interpreter will likely need more registers than a recompiler for 6502 on x86. By the way, there are some improvements that can be made to PocketNES's interpretation, assuming that it uses the same methods as the PCEAdvance code that was derived from it (pretty safe to say, but that's the code I'm more familiar with). Using memory tables instead of function tables is generally more efficient unless there's a high hit rate to memory accesses that need to be trapped and handled through function calls. Also, the registers can be shuffled around more tightly such that the stack pointer gets a register. Or at least, it gets one in my ARM interpreter core for Temper. There are perhaps a few other micro-optimizations here and there that can be done, although overall it's a very highly optimized emulator and I doubt that TuxNES comes anywhere close with just what you mentioned. That is, if the interpreter is only in C. If it was as optimized as PocketNES's then there's no way a recompiler would do 7x better, and yet still only bench as you said.

The TuxNES benchmarks were done on a Celeron 366, which resulted in a speed of 4250 fps, 70x faster than a NES, or the equivalent of a NES running at 125.3 MHz, which gives a clock speed ratio of 125.3/366 = 0.34.

As I said, clock speed ratio is a really terrible metric for performance.

Tuxnes definitely isn't generating 24-36 instructions per 6502 instruction, it's more like 5 or so. If it's using that many pipeline slots, it's due to cache misses or pipeline stalls for other reasons. Intel's CPUs are optimized for 32-bit code, and do not schedule 8-bit instructions well. The celeron seems to be averaging less than one instruction per clock on this code.

Of course it isn't generating that many per instruction, but how often does it branch to outside calls? What kind of overhead is there? You have to think about these things, especially with memory accesses. Unless you have an actual count of how many instructions are executed over a period of time then you can't quote instructions per cycle. Besides that, I doubt that 8bit code is what's dominating the output, although if it does that much worse (I'm skeptical) then some things should be done to try to work around it. 8bit clamping can probably be deferred pretty far off a lot of the time, and flags don't have to be calculated all the time. There are actually a lot of optimizations you can do to improve 6502 code when recompiling.

But if they allow any instruction to exit due to cycles then they can't do ANY of these kinds of lookahead optimizations, in addition to having to check after every instruction. Just doesn't seem worth it to me. There IS a way to get around this, by using a hybrid recompiler/interpreter (I described this in a post on emutalk that I could dig up if you want), but I'm not aware of anyone using this technique.

Anyway, the RAM limit probably makes this infeasible on the GBA. As for the graphics, it does have to remap the palettes and scale the tiles, which is not completely trivial, and does take some CPU time.

I have it on word from FluBBa himself that amount of CPU time is close to negigable for PCE games, so I doubt it's worse for NES games that have simpler graphics. The tiles aren't scaled in software anyway, it's done in hardware as well. The only real work is in caching the tiles from planar to packed format, but it's not that big of a deal. Especially considering that a lot of NES games use tiles from ROM that the game can't change.

 

[neko]

It might count cycles accurately, but a typical dynamic recompiler won't check cycles remaining every instruction, for the reasons I gave above. If you're NOT checking every cycle then it makes more sense to retain the emulated flags in the x86 flags register, rather than putting them out to explicit registers.

Indeed, that is exactly how it works. See http://tuxnes.cvs.sourceforge.net/viewvc/t...uxnes/table.x86

It does save the flags though. I've yet to see a dynarec that optimizes the flags well, except maybe Generator (www.squish.net/generator)

QUOTE
Of course, having more registers on the ARM side helps a lot, and an interpreter will likely need more registers than a recompiler for 6502 on x86. By the way, there are some improvements that can be made to PocketNES's interpretation, assuming that it uses the same methods as the PCEAdvance code that was derived from it (pretty safe to say, but that's the code I'm more familiar with). Using memory tables instead of function tables is generally more efficient unless there's a high hit rate to memory accesses that need to be trapped and handled through function calls. Also, the registers can be shuffled around more tightly such that the stack pointer gets a register. Or at least, it gets one in my ARM interpreter core for Temper. There are perhaps a few other micro-optimizations here and there that can be done, although overall it's a very highly optimized emulator and I doubt that TuxNES comes anywhere close with just what you mentioned. That is, if the interpreter is only in C. If it was as optimized as PocketNES's then there's no way a recompiler would do 7x better, and yet still only bench as you said.

It looks like PocketNES makes function calls for all memory accesses except zero page. I would think a lookup table would be faster. A dynarec is even faster, if it can figure out in advance what the address is (look at the tuxnes code, it generates either a load/store or a call depending on the address).

The main reason PocketNES can get away with all these calls is that the pipeline on the ARM7 is very short, so those branches only incur a 3-cycle penalty, as opposed to 13 cycles on the Cortex-A8 (Pandora). But at 600MHz a few tens of cycles probably isn't that big of a deal anyway, at least not for NES and PCE emulation.

QUOTE
I have it on word from FluBBa himself that amount of CPU time is close to negigable for PCE games, so I doubt it's worse for NES games that have simpler graphics. The tiles aren't scaled in software anyway, it's done in hardware as well. The only real work is in caching the tiles from planar to packed format, but it's not that big of a deal. Especially considering that a lot of NES games use tiles from ROM that the game can't change.


Interesting.

 

[slaanesh]

I love Flubba's emulators. PocketNES is what got me started with the entire handheld emulation scene in the first place. I was think NES emulation on a GBA? I've *got* to try that and promptly bought a GBA and flashcard. It's one of my favourite NES emulators too as it seems fairly accurate and plays without ever slowing down.
PCEAdvance is probably more amazing still. I'd love to see this running on the NDS one day to see it zoom along at fullspeed.

 

[Exophase]

It does save the flags though. I've yet to see a dynarec that optimizes the flags well, except maybe Generator (www.squish.net/generator)

There are recompilers that save native flags inbetween instructions, and a number perform dead flag eliminationg - even gpSP (ARM target) performs both. You might be getting snagged since so many recompilers out there are for MIPS which doesn't have any flags to emulate.

What would be interesting to look at is a sample before/after sequence showing what TuxNES is converting from/to for sequences of real NES code. Actually, I'd love it if more were provided for other recompilers. Maybe I'll provide some of my own some day. A nice compilation of these to show what various recompilers are doing without requiring that you dig through their code to reconstruct it would be very educational. The only one I've seen anything for thus far was StrmnNrmn's Daedalus. He sent them to me personally.

Nonetheless, if it's emitting a cycle check inbetween every instruction (and the comments seem to suggest this) then there are many optimizations it can't do, and it carries a ton of extra overhead and icache pressure per translated instruction. Really takes all the fun out of writing a recompiler - if I were doing something like this I would absolutely go for a hybrid attempt instead (with a very optimized interpreter that uses a compatible register mapping). You can see my thread about it here: http://emutalk.net/showthread.php?t=42433

It looks like PocketNES makes function calls for all memory accesses except zero page. I would think a lookup table would be faster. A dynarec is even faster, if it can figure out in advance what the address is (look at the tuxnes code, it generates either a load/store or a call depending on the address).

Yes, that's one of the big advantages. Fortunately you can do a lot of it w/o analzying inbetween instructions because constant addresses are used a lot. However, I think you'll find that zero page is used much more than absolute w/o index, so it's not a tremendous advantage.

I really find TuxNES's design kind of unfortunate. On the one hand, it has this nice pattern matching system using an external file, which makes it more organized and easier to read. On the other hand it's just way too large and way too hardcoded/handcoded. Instructions can be broken down into modular blocks such that you really don't have to hand code every opcode like this, and if it were done in source it would have been easy to do more generic emitter functions/macros/whatever so you can write in assembly like code instead of writing a bunch of machine code (although the comments help). Porting this to another platform looks like an utter nightmare, and the 1:1 instruction to sequence conversion means you can't do pretty much anything sophisticated in terms of optimizations. Not that you could anyway with cycle checking inbetween blocks, but again, I don't think that's a good way to handle this.

I also think that it's going to inevitably lack support for a lot of games by not including all the special memory handlers for things that aren't just simple load/store instructions. But including support would require hand coding all of the combinations and would make that file huge, even compared to how large it is now. The memory stuff should really be abstracted away from per-instruction emit sequences, but they've really locked themselves into this scheme, which is quite inflexible.

The main reason PocketNES can get away with all these calls is that the pipeline on the ARM7 is very short, so those branches only incur a 3-cycle penalty, as opposed to 13 cycles on the Cortex-A8 (Pandora). But at 600MHz a few tens of cycles probably isn't that big of a deal anyway, at least not for NES and PCE emulation.

For what it's worth, INDIRECT branches take the same amount of time on ARM9 as well, which has a 5-stage pipeline. It's not so much the length of the pipeline as it is the distance between fetch and PC writeback (depending on forwarding). Direct branches on ARM11+ (including Cortex-A8) are predictable and if predicted take 1 or even 0 cycles (read on branch folding).

And you're right, PCE emulation hums along fine at 500MHz on a Pandora board (nearly 4x headroom, with inefficient screen blitting via X11). But you're also right about the issue of unpredicted indirect branches and interpreters on Cortex-A8, it's something I've certainly considered before :/

 

[neko]

What would be interesting to look at is a sample before/after sequence showing what TuxNES is converting from/to for sequences of real NES code.

CODE
$ tuxnes --disassemble smb.nes

[8000] (10010010) -> 12000000
8000: 78-SEI
8001: d8-CLD
8002: a9-LDA #10
8004: 8d-STA 2000
8007: a2-LDX #ff
8009: 9a-TXS
800a: ad-LDA 2002
800d: 10-BPL 800a (-05)
...

To get the x86 code attach gdb and disassemble the address it gives you
CODE
(gdb) disas 0x12000000 0x12000200
Dump of assembler code from 0x12000000 to 0x12000200:
0x12000000: add $0x2,%esi
0x12000003: orl $0x4,0x83eb54c
0x1200000a: add $0x2,%esi
0x1200000d: andb $0xf7,0x83eb54c
0x12000014: mov $0x10,%eax
0x12000019: add $0x2,%esi
0x1200001c: mov $0x10,%edi
0x12000021: lea 0x4(%esi),%esi
0x12000024: mov $0x2000,%ebx
0x12000029: call 0x804d0b2 <OUTPUT>
...



There are three inefficiencies that I can see:

1. It updates the cycle count (%esi) after every instruction
2. It saves the flags (%edi) whether it needs to or not
3. It leaves the mov addr,-4(%esp) crud around after the linker is done

QUOTE
Actually, I'd love it if more were provided for other recompilers. Maybe I'll provide some of my own some day. A nice compilation of these to show what various recompilers are doing without requiring that you dig through their code to reconstruct it would be very educational. The only one I've seen anything for thus far was StrmnNrmn's Daedalus. He sent them to me personally.

That would be nice.

 

[Exophase]

Thanks for the listing, very interesting stuff.

One thing that must be noted is that while it does increment cycles after every instruction it doesn't actually check for overflow after every instruction. I guess I'd have to see a bit more to see where it does - I imagine the BPL ends the block (usually recompilers are like that, although some have conditional exit points) and cycles are probably checked there. This does make the events less granular, or effective higher latency, which is less accurate than checking after every instruction like an interpreter would.

It also means that you can do all of the nice multi-instruction optimizations though. Although not with the TuxNES design, which wouldn't allow the first two improvements you mentioned.

One other thing is that it really doesn't have to pass $2000 for the STA $2000 implementation - I'm sure there's a corresponding function that can be called that knows the address is $2000. If such a specific function isn't being called then that's something else that can be improved.

 

[neko]

Thanks for the listing, very interesting stuff.

One thing that must be noted is that while it does increment cycles after every instruction it doesn't actually check for overflow after every instruction. I guess I'd have to see a bit more to see where it does - I imagine the BPL ends the block (usually recompilers are like that, although some have conditional exit points) and cycles are probably checked there. This does make the events less granular, or effective higher latency, which is less accurate than checking after every instruction like an interpreter would.

The block is much bigger, it continues compiling until it reaches an unconditional branch. I didn't post more since it's very easy to make TuxNES output it, assuming you have a system which can run it.

The BPL gets compiled as follows:

CODE
0x12000052: add $0x3,%esi
0x12000055: mov $0x800d,%ebx
0x1200005a: jns 0x804cec6 <NMI>
0x12000060: test $0x100,%edi
0x12000066: mov $0x800a,%ebx
0x1200006b: movl $0x12000075,-0x4(%esp)
0x12000073: je 0x804ce22 <U>
0x12000079: sub $0x1,%esi

After the first run, the je gets replaced with the correct address (assuming you have --link enabled) so the final conversion of the LDA..BPL is:

CODE
0x12000043: lea 0x4(%esi),%esi
0x12000046: mov $0x2002,%ebx
0x1200004b: call 0x804d071 <INPUT>
0x12000050: mov %edi,%eax
0x12000052: add $0x3,%esi
0x12000055: mov $0x800d,%ebx
0x1200005a: jns 0x804cec6 <NMI>
0x12000060: test $0x100,%edi
0x12000066: mov $0x800a,%ebx
0x1200006b: movl $0x12000075,-0x4(%esp)
0x12000073: je 0x12000043
0x12000079: sub $0x1,%esi

At this point, the movl instruction is superfluous. A better design could get rid of that. Also of note is that unlike PocketNES, the cycle counter counts up rather than down, so it uses jns to check if the sign bit changed.

QUOTE
It also means that you can do all of the nice multi-instruction optimizations though. Although not with the TuxNES design, which wouldn't allow the first two improvements you mentioned.

Yeah, although if you optimize too much then you won't be able to insert the branch shown above. So the compiler would need to figure out where you can jump in and out, and keep the instruction count and flags correct at those points.

QUOTE
One other thing is that it really doesn't have to pass $2000 for the STA $2000 implementation - I'm sure there's a corresponding function that can be called that knows the address is $2000. If such a specific function isn't being called then that's something else that can be improved.

It looks like it doesn't have separate functions. This could be improved, as you describe.

 

[Exophase]

The block is much bigger, it continues compiling until it reaches an unconditional branch. I didn't post more since it's very easy to make TuxNES output it, assuming you have a system which can run it.

Okay, going until an unconditional branch is how gpSP does it too.

At this point, the movl instruction is superfluous. A better design could get rid of that. Also of note is that unlike PocketNES, the cycle counter counts up rather than down, so it uses jns to check if the sign bit changed.

Unfortunately, there's no way they could get rid of it while working within the framework they have. One thing about gpSP is that it performs direct branches "greedily" instead of back patching them at runtime like other recompilers seem to. It'll try to recompile as much as it can, as deep as it can. In practice I find that this doesn't introduce perceptible lag, if that's the concern for avoiding it. The only other benefit I can think of is that it avoids hazardous dead ends that are stubbed out by self modifying code, at runtime. I did have an issue with that once, with some homebrew game. It's manageable by other means though.

Yeah, although if you optimize too much then you won't be able to insert the branch shown above. So the compiler would need to figure out where you can jump in and out, and keep the instruction count and flags correct at those points.

Yes, gpSP figures out sub-block boundaries in a first pass.

However, the only real advantage of not continuing at the end of blocks is that it reduces redundancy of generated code. That is, unless you go really all out and try to do inter-sub-block optimization by folding the constant/allocation set (for NES emulation you won't end up with register allocation anyway though). For flags you don't have to actually worry about it, since the dead flag elimination progresses downwards, not the other way around. I'll leave it to you to convince yourself why this is the case.

 

[neko]

Unfortunately, there's no way they could get rid of it while working within the framework they have. One thing about gpSP is that it performs direct branches "greedily" instead of back patching them at runtime like other recompilers seem to. It'll try to recompile as much as it can, as deep as it can. In practice I find that this doesn't introduce perceptible lag, if that's the concern for avoiding it. The only other benefit I can think of is that it avoids hazardous dead ends that are stubbed out by self modifying code, at runtime. I did have an issue with that once, with some homebrew game. It's manageable by other means though.

It would be possible to keep a list of branches that have been generated, so you can go back and patch them. Then you wouldn't need to add extra instructions for this purpose.

I haven't seen any other examples of back-patching. I know that is one thing that Mupen lacks. Mupen also detects self-modifying code by generating code that marks pages dirty with every write instruction. This generates a lot of extra instructions. It seems like there ought to be a better solution for that, such as triggering pagefaults or unmapping pages in the MMU emulation. TuxNES uses an interpreter for code in RAM, which is obviously not feasible for many other systems. How did your experiments with recompiling self-modifying code turn out?

The only real problem with recompiling as deep as possible is you can end up compiling garbage if you're not careful. Not just dead code, but data that was never meant to be executed as code.

It would be great to make a list of different dynarecs, comparing how they handle self-modifying code, branches, memory mapping, flags, etc.

I really find TuxNES's design kind of unfortunate.
TuxNES is a great example of what to do, and what not to do. It's very simple, you can run it and watch the disassembly, and it's very easy to understand what it's doing. It's also totally unportable, and won't even compile on x86-64.

It's a total hack, it's like they figured out what was necessary to make games run, and the rest is totally incomplete. There are unimplemented instructions, the recompiler walks right across page boundaries, the cycle counting is lax, and yet it runs almost every game perfectly. It's a case study in what you can get away with.

 

[Exophase]

It would be possible to keep a list of branches that have been generated, so you can go back and patch them. Then you wouldn't need to add extra instructions for this purpose.

You mean, hash PC's elsewhere? Yes, that's possible. What I meant to say is that you can't remove instructions from the generated code stream very easily - with TuxNES's system you can't even if you recompile the code again. The output is pretty fixed.

I haven't seen any other examples of back-patching. I know that is one thing that Mupen lacks. Mupen also detects self-modifying code by generating code that marks pages dirty with every write instruction. This generates a lot of extra instructions. It seems like there ought to be a better solution for that, such as triggering pagefaults or unmapping pages in the MMU emulation. TuxNES uses an interpreter for code in RAM, which is obviously not feasible for many other systems. How did your experiments with recompiling self-modifying code turn out?

See Daedalus for another example of a recompiler with back-patching. Of course, as I mentioned before I prefer to avoid it altogether, but there are benefits.. I guess you can call what gpSP does more "forward linking"?

Detecting self-modifying code is unfortunately only a small part of the battle. On platforms that have cache you can use icache clears as a hint, but even on N64 (which has an easy to wipe cache) you're bound to see cases where games don't adhere for this heuristic. Using the OS/MMU to try to help you gives you very weak granularity (1KB at best on ARM) and the cost of weaving out of a page fault on Linux is going to be quite high. For a platform like GBA where there's only 32KB of fast RAM (where self modifying code tends to happen) the granularity is just too poor. Of course, with a reasonable amount of RAM it also means you can trap per-byte and that the overhead isn't too great. Of course, you wouldn't want to generate code sequences for writes when you have to check this - it's not worth it (best to just call an optimized function with a fast calling convention).

Actually dealing with legitimate self modifying code that's highly recurring w/o thrashing performance is a total headache. The strategy I've written on my blog is pretty out of date, here is what I'm currently doing (which still has some glitches):

- All translated code blocks in RAM are kept mutually exclusive, with no overlap. To accomplish this it means that if a block in-compilation hits the start of another block it must halt recompilation and branch to it. More significantly, it means that if you branch into the middle of an existing block that block has to be split: this is accomplished by invalidating the status for the RAM bytes for the block, compiling a new block from the merge PC onwards, then compiling a new block from the start of the old block onwards. This operations are "merge" and "split" and they don't involve deallocating/reusing RAM for old blocks, so there's some waste in translation cache used (but the old cache becomes stale so it doesn't hurt cache pressure).

- When a part of a block is modified, exactly one block is affected due to mutual exclusivity above. The beginning of the block is patched so that when it is executed it branches to a handler which causes a new copy of the block to be compiled, and the beginning of the old block is patched so it now points to the new block. What's important here is if that block is modified again that the ORIGINAL block is patched to link to it, not the most recent one. Otherwise you end up with this chain of branches that keeps growing.

The system seems simple in writing but it's actually really hard to debug and reveals some horrifying things, such as GBA games that use the same instruction as both ARM and Thumb (yes, I'm shocked too). I've also played around with using checksums on blocks in order to keep histories around instead of recompiling new ones. Different strategies can be taken to try to reuse blocks - with the above technique you'll eventually run out of cache no matter what and will force a flush. Unfortunately, you have to flush all the RAM blocks when this happens because of dangling pointers. It also causes fragmentation and linking to float around the compilation, but it drastically reduces the amount you have to flush overall for all the games I've tested it on. Unfortunately, I need to improve the granularity of my SMC detection because it gets to the point where say, a block memory instruction modifies two blocks (historically I've only been detecting the last write, which is fine when you're invalidating the whole cache but here it's not so good).. and I just never got around to doing that. I had such a hard time getting it to work otherwise that it's going to take some effort for me to get myself in the mindset to work on it again >_<

The only real problem with recompiling as deep as possible is you can end up compiling garbage if you're not careful. Not just dead code, but data that was never meant to be executed as code.

Yes, that's what happened to me with the homebrew game (Another World) in gpSP. However, normally it just doesn't happen because that'd mean the code inevitably starts executing garbage.

Simplest response I can give: recompiling garbage can be managed if you know how to restrain it. Also, right now I'm only recompiling blocks up to a certain size, which helps mitigate it as well.

It would be great to make a list of different dynarecs, comparing how they handle self-modifying code, branches, memory mapping, flags, etc.

Would be. I think most of them don't have to worry about SMC much - if the system is slow enough to care about SMC then they don't get dynarec'd, if the system is fast then SMC only really happens when new code is loaded and it's a good idea to throw it all away. I think the memory mapping stuff tends to fall under a few categories for both recompilers and interpreters, I can go over what I've seen.

TuxNES is a great example of what to do, and what not to do. It's very simple, you can run it and watch the disassembly, and it's very easy to understand what it's doing. It's also totally unportable, and won't even compile on x86-64.

It's a total hack, it's like they figured out what was necessary to make games run, and the rest is totally incomplete. There are unimplemented instructions, the recompiler walks right across page boundaries, the cycle counting is lax, and yet it runs almost every game perfectly. It's a case study in what you can get away with.

With all of the lectures I've seen on how sensitive NES is I find that pretty shocking. Maybe people are just uptight about it. Maybe it runs 90+% of games correctly and people won't tolerate less than 0.1% not working? I don't really know. But it's nice knowing that. Although I do wonder, do you have some hard compatability information, or just results of informal testing?

 

[neko]

Yes, that's what happened to me with the homebrew game (Another World) in gpSP. However, normally it just doesn't happen because that'd mean the code inevitably starts executing garbage.

Simplest response I can give: recompiling garbage can be managed if you know how to restrain it. Also, right now I'm only recompiling blocks up to a certain size, which helps mitigate it as well.

Here's an example from Super Mario Bros:

CODE
d961: a9-LDA #0b
d963: d0-BNE d946 (-1f)
d965: 02-BAD
d966: 06-ASL 05
d968: 06-ASL b5
d96a: 16-ASL c9,X
d96c: 12-BAD

So it never actually executes since the branch is always taken, but if your compiler is aggressive about compiling everything then it might try to compile this.

It would be great to make a list of different dynarecs, comparing how they handle self-modifying code, branches, memory mapping, flags, etc.

Would be. I think most of them don't have to worry about SMC much - if the system is slow enough to care about SMC then they don't get dynarec'd, if the system is fast then SMC only really happens when new code is loaded and it's a good idea to throw it all away. I think the memory mapping stuff tends to fall under a few categories for both recompilers and interpreters, I can go over what I've seen.
GBA is kind of a unique case where code runs from RAM, but there is no i-cache. On most modern systems, the instruction cache and pipelining makes self-modifying code impossible, and on older systems most code runs from ROM.

With all of the lectures I've seen on how sensitive NES is I find that pretty shocking. Maybe people are just uptight about it. Maybe it runs 90+% of games correctly and people won't tolerate less than 0.1% not working? I don't really know. But it's nice knowing that. Although I do wonder, do you have some hard compatability information, or just results of informal testing?

The compatibility is my own experience. I ran this on my old desktop ten years ago, and it worked fairly well. There were a few games that didn't work, but it ran 90%.

Emulating the NES isn't that sensitive. If you mess up the timing, then the graphics get glitched on whatever scanline wasn't timed properly. If the vertical scrolling is set on the wrong line then subsequent lines are positioned wrong. Tuxnes actually isn't very far off; there are much worse NES emulators out there.

 

[Exophase]

Here's an example from Super Mario Bros:

CODE
d961: a9-LDA #0b
d963: d0-BNE d946 (-1f)
d965: 02-BAD
d966: 06-ASL 05
d968: 06-ASL b5
d96a: 16-ASL c9,X
d96c: 12-BAD

So it never actually executes since the branch is always taken, but if your compiler is aggressive about compiling everything then it might try to compile this.

The nice thing about this example is that you can actually determine at compile-time that the branch will always succeed. If this is typical for this symptom then it's worth doing this kind of reduction just to get rid of it. However, even if you do end up compiling things that aren't code, the worst that can really happen is you end up compiling all over the ROM space - it'll still end eventually (and NES ROMs aren't that large so you probably won't run out of cache if you gave a liberal amount). You can put a recursion limit on the recompilation to mitigate this as well. This is the very worst case scenario - if the bad code ends up falling off or branching out of the ROM space then you can snip it.

GBA is kind of a unique case where code runs from RAM, but there is no i-cache. On most modern systems, the instruction cache and pipelining makes self-modifying code impossible, and on older systems most code runs from ROM.

GBA is pipelined, and pipelining rarely poses an issue to SMC, unless you modify something that's right in front of you (isn't usually what happens). Instruction cache is only an issue on platforms that aren't coherent, which granted, is most of them, but not all of them. For instance it's something DOSBox has to worry about. With non-coherent i-cache it's still possible to perform self modifying code by clearing part or all of the cache. Most archs with cache have instructions that allow you to do this, and this is a good hint for recompilers. But even on archs that don't, you can still utilize a software routine to do it (but doing more than all of the i-cache gets troublesome). When the cache is small or has poor associativity you sometimes just end up getting lucky. Unfortunately this is something that programs have relied on in the past. At least one N64 game (Super Smash Bros) modifies code without doing anything to clear the cache in a way that's obvious to the recompiler. StrmnNrmn has mentioned this, but he hasn't mentioned how he worked around it.

The compatibility is my own experience. I ran this on my old desktop ten years ago, and it worked fairly well. There were a few games that didn't work, but it ran 90%.

Emulating the NES isn't that sensitive. If you mess up the timing, then the graphics get glitched on whatever scanline wasn't timed properly. If the vertical scrolling is set on the wrong line then subsequent lines are positioned wrong. Tuxnes actually isn't very far off; there are much worse NES emulators out there.



It's those off-by-one-scanline errors that purists go totally apeshit over. I wouldn't really put it past them to declare an emulator utter junk for having some of these problems. 90% otherwise compatibility is probably considered unacceptable as well. But if there's a platform that has the memory and doesn't have the CPU then it'd certainly be worth looking into. Actually, I think it's more appealing for PC-Engine. Possibly for getting it working on archs like iPod (not iPhone). I've thought about schemes to make recompilation worth something on GBA but it's hard to really think of anything :/