I expect it'd make very little difference overall. Most branches are very short. The MIPS instruction set allows for conditional branches of +/-128K, but in practice they're rarely more than 4K. The only branches longer than this are call/return pairs (JAL/JR r31) for which we mostly end up doing indirection anyway.
All the more reason not to have to require going through the trouble of cleaning links between the 2MB regions.
Originally I tried to compile fairly large blocks, so that all the local branches would be included. This ended up compiling a lot of useless junk, so now it compiles very small blocks.
What's your block definition? Ends on a branch, conditional or otherwise? Ends before hitting so many instructions too?
There really isn't a good way to optimize call/ret pairs. The calls are fine, these can be directly linked to the target, but the returns are harder. What I ended up doing was to look up the addresses in a hash table. To get a good hit rate on the hash table (~99%) it has to be fairly big, as you're looking at around 10000-15000 active entries for a typical N64 game. I used 65536 bins, with up to 2 entries per bin. To prevent cache misses, it does a PLD (or PREFETCH on x86) instruction on the hash table entry during the JAL, so that the line will be in the cache upon return. However, PLD goes to the L2 cache on Cortex-A8, so it still ends up using 8 cycles for the L1 miss, plus 13 cycles for the branch misprediction, plus a few cycles to calculate the hash.
An indirect branch is not a guaranteed mispredict, if the BTB has the correct address.. so I guess if you return to the same place a lot you might avoid it. Course, it could still be in L1 cache too, by that logic ;p
Do you think any games perfectly honor that jr ra always corresponds to the last jal subroutine call? Because you could have an option to push around real addresses for those. Then the A8's call stack would help you.
There are some theoretical ways to optimize this, but they tend to be difficult in practice. One thing is that approximately 50% of subroutines are only called from one location, so you could jump directly back to the caller. The problem here is that often the code is compiled as several small blocks, so by the time you find the return (JR r31) instruction it isn't trivial to find the original entry point. This would work for small subroutines though. For really small subroutines, it would also be possible to inline them when you compile the caller, but this really screws up cache invalidation, since if you invalidate this memory location, you'd have to invalidate everything that inlined it too.
Good, even more likely that the BTB will hit correctly and that it'll be in L1 cache! If the calls are close enough together. The invalidation vs. inlining part is all the more reason to segregate indirection by 2MB block, I think.
Your code generation looks great, I think that people won't have much to worry about getting good speed N64 emulation out of this. I really like how simple the memory map emulation is, not that it's news to me regarding N64 but just seeing it is nice, especially since you don't need a register for it on ARM. It's at least one nice break you have emulating N64 over other things.. Just a few questions:
- Any plans for any global register allocation strategies? Of course this would help with the 64bit stuff too, I think. Not that pretty much anything would be at all simple to implement..
- Are you considering using MMU protection (mmap) for the self modifying code check on the store? Since you're using the same page granularity anyway, which kind of suggests to me that you plan for it later.
- Any plans on scheduling for Cortex-A8? Naturally this will make the register allocation more constricted but with a lot of loads in the picture it seems worthwhile.
- Option for shadow stack pointer? Of course, since the example code is not even using the stack I can't tell if you aren't already..
And of cousre any other optimization plans you have, or tricks you're currently doing, I'd love to hear.
I can't imagine this current OpenGL ES problem is going to be a huge barrier. Pandora could very well launch with good N64 emulation.