Mupen64Plus

[ldesnogu]

Because if you remove a block you have to remove everything that's linked to it, recursively. Tracking such a thing is not worth it when you're going to end up removing a major chunk of your blocks that way anyway. You'll end up fragmenting memory pretty heavily this way too.

The Dynamo paper made it clear that it flushed the entire cache for these reasons. I don't know if this "RIO" is different in this regard, since I've never heard of it.

I'm sure you'll find this interesting: http://www.burningcutlery.com/docs/phd.pdf
See section 6.3 for code cache flushing and compaction.

Also, the description you gave of QEMU's dispatcher makes it clear that this is not happening there either.

Huh? What exactly in what I wrote makes you think so?

Just to be clear, when I say "direct linking" I mean a translated direct branch from one block to another. If it goes through any kind of indirect lookup then it's not direct linking, even if there's a cached value stored somewhere to make it faster than doing a full emulated PC to translated block conversion (plus potential new block compilation). No matter how you slice it, this is going to be considerably slower than the alternative.

We use the same terminology

 

[Exophase]

I'm sure you'll find this interesting: http://www.burningcu...om/docs/phd.pdf
See section 6.3 for code cache flushing and compaction.

404, give me another link

Huh? What exactly in what I wrote makes you think so?

You wrote that QEMU switches back to the dispatcher between every block's execution to check for IRQs. If you do that you can't directly link, it has to go to the dispatcher.

 

[ldesnogu]

404, give me another link

Try this: http://www.burningcutlery.com/derek/docs/phd.pdf

You wrote that QEMU switches back to the dispatcher between every block's execution to check for IRQs. If you do that you can't directly link, it has to go to the dispatcher.

I probably was not clear enough: I meant that it takes the opportunity of going back to the dispatch loop to check for interrupts The main thing QEMU lacks at this moment is indirect branch linking; each indirect branch goes back to the dispatch loop and that certainly isn't good.

@ari64: Sorry for the out topic discussion, I hope it contains some useful information for you...

 

[ari64]

See section 6.3 for code cache flushing and compaction.

It describes a similar eviction system, a circular buffer with least-recently-created (FIFO) eviction.

DynamoRIO doesn't delete everything though, it leaves some blocks and then has to work around these when generating new code. I found it a lot easier to delete everything and recompile blocks as necessary. Only around 14% of the blocks are up for eviction at any one time, so it doesn't have to recompile much.

 

[Exophase]

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.

 

[calc84maniac]

So does sound emulation work, at least in theory? Or would that require a bit of work as well?

 

[midna25]

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.

And everyone said it was impossible. I'm not getting my hopes up, but whenever anyone says "This'll never happen" or "You can't do this" as far as open source crap goes, it always ends up getting done.

 

[dflemstr]

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.

And everyone said it was impossible. I'm not getting my hopes up, but whenever anyone says "This'll never happen" or "You can't do this" as far as open source crap goes, it always ends up getting done.

+1, for some reason, more difficult problems are preferred in the OSS world. See this:
http://xkcd.com/619/

 

[craigix]

People said it was impossible on the Wiz, not the Pandora.

 

[ari64]

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.

This "trouble" is less than 10 lines of code in ll_kill_pointers(). It's not a complex thing, and wouldn't be difficult to change if you wanted to experiment.

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?

Ends on an unconditional branch. I also set a limit of 4096 instructions, but nothing comes close to this. The most I've seen is around 600-700 instructions.

Originally, it would continue compiling past JAL instructions, but then I encountered junk like this:

  803ab170: JAL 803ab1c0
  803ab174: SLL r0,r0,0
  803ab178: JAL 80081e30
  803ab17c: SLL r0,r0,0
  803ab180: LB r17,r0+214
  803ab184: SLL r0,r0,0
  803ab188: SLL r0,r0,0
  803ab18c: DSRL r1,r5,22
  803ab190: SLL r0,r18,0
  803ab194: LB r26,r1+ffffb1c0
  803ab198: LB r26,r1+ffffb1c0
  803ab19c: LB r26,r1+ffffb1c8
  803ab1a0: LB r26,r1+ffffb1d0
  803ab1a4: LB r26,r1+ffffb20c
  803ab1a8: LDR r3,r19+6261
  803ab1ac: ???
  803ab1b0: SLL r0,r0,0
  803ab1b4: LD r4,r21+ffffdea9
  803ab1b8: SLL r0,r0,0
  803ab1bc: SLL r0,r0,0
  803ab1c0: JR r31
  803ab1c4: ADDIU r2,r0,4

I have no clue what the purpose of this is. Maybe Rareware was deliberately trying to break emulators.

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.

It's hard to guarantee that. I know the bootcode has a call that doesn't return. Also, I do occasionally blow away the call stack, for example when the comparison fails in verify_code, but that's fairly infrequent.

If the hash table entry is in the L1 cache and the correct address is in the BTB, then it should be pretty fast. So maybe this isn't a big problem.

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.

If you inline calls, and a write hits a certain address (self-modifying code) you can't just invalidate a small range around that address, you have to find and invalidate blocks all over. This is a seperate issue from expiring old blocks to free memory.

 

[ari64]

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:

It you're referring to the cmp/bvc, it should look familiar, Daedalus does something very similar.

- 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..

There is a preferred mapping, which is r1->r1, r2->r2...r7->r7, r8->r0, r9->r1, etc. This helps with branches, as things are usually in the same registers, however if it runs out of registers, then it will use whatever registers are available.

- 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.

I hadn't seriously considered it, but it would be possible. The page size is 4K because that's the native page size on the r4300, although almost no N64 games actually use the MMU. (And if any do use the MMU, they probably won't work, since I haven't tested this.)

- 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.

To schedule instructions this way would require an instruction-reordering pass after code generation. This could be done but would take some work. I guess the Cortex-A9 CPU will do this in hardware. It might be almost as effective to simply change the register allocation so that registers are allocated/loaded one instruction before they are needed.

- 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..

I can't see any advantage to this. r29 is generally used as a stack, so the example code is in fact using the stack.

And of cousre any other optimization plans you have, or tricks you're currently doing, I'd love to hear.

Something could probably be done to improve the floating point performance. Currently it calls libc/libm, which I assume is softvfp. However, floating point operations are typically less than 5% of the instructions in most N64 games, so it's not a showstopper.

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.

I don't think I have the correct binary blob to test hardware acceleration, so maybe someone more familiar with this can comment.

Also some of the textures are clearly not right. I don't know if this is a bug in mesa or rice video, but it doesn't happen on x86.

 

[ari64]

So does sound emulation work, at least in theory? Or would that require a bit of work as well?

In theory. I don't have any hardware to test it, but I can't think of any reason why it wouldn't work, other than it increases CPU usage 10-20%.

 

[Exophase]

It you're referring to the cmp/bvc, it should look familiar, Daedalus does something very similar.

Indeed, I'm familiar with it. It's just nice that here you don't need to use a register. Was just hoping you were aware of the simple mapping, and fortunately you are.

There is a preferred mapping, which is r1->r1, r2->r2...r7->r7, r8->r0, r9->r1, etc. This helps with branches, as things are usually in the same registers, however if it runs out of registers, then it will use whatever registers are available.

Okay, so it's a kind of mix between static and dynamic. But I was referring to dynamic between blocks.

I hadn't seriously considered it, but it would be possible. The page size is 4K because that's the native page size on the r4300, although almost no N64 games actually use the MMU. (And if any do use the MMU, they probably won't work, since I haven't tested this.)

Would at least cut down the generated code size a bit. I'm always nervous about blowing away L1 icache with huge translated code blocks. Past a certain amount I'd move things to a function (probably for a store like that).

To schedule instructions this way would require an instruction-reordering pass after code generation. This could be done but would take some work. I guess the Cortex-A9 CPU will do this in hardware. It might be almost as effective to simply change the register allocation so that registers are allocated/loaded one instruction before they are needed.

Right, it's not the easiest thing in the world to do. But you'd be able to exploit parallelism a little more in general. If you can manage the register space for that then it should at least help a little, yeah.

I can't see any advantage to this. r29 is generally used as a stack, so the example code is in fact using the stack.

You're right, I missed that, but because it was an add and I was looking for loads/stores. What I also mean by shadow stack pointer is to assume that the stack is always in RAM, and loads/stores plus additions and subtractions can go to the shadow stack. So long as games don't copy from the stack pointer to other registers much (ie, frame pointer..) then it should be faster this way. Of course it also fails if games use the stack pointer on memory that has to be trapped, but I doubt they do.

Something could probably be done to improve the floating point performance. Currently it calls libc/libm, which I assume is softvfp. However, floating point operations are typically less than 5% of the instructions in most N64 games, so it's not a showstopper.

Yes, definitely start outputting VFP code, if not NEON code (where possible), however..

By 5% do you mean of executable space or of code that's being ran? Because if only 5% of executed code is floating point then that means the Wiz probably can do N64 emulation afterall. In which case, I wonder if you'd be interested in attempting a port there too.

I don't think I have the correct binary blob to test hardware acceleration, so maybe someone more familiar with this can comment.

Also some of the textures are clearly not right. I don't know if this is a bug in mesa or rice video, but it doesn't happen on x86.

Instead, if you're interested you can test OpenGL ES on x86, using PowerVR's wrapper. I'm sure that'd make it a lot easier for someone else to port it.

 

[cowai]

Someone please send Ari some hardware.

 

[Exophase]

It seems to me like he already has something, although exactly what I'm not sure.

 

[Adventus]

Very impressive.

Is most the floating point computations done in the graphics plugins? I had a look at rice_video and Glide64, they seem like a very good target for NEON.... most are already SSE optimized. From initial impressions I think we could port rice_video pretty easy using NanoGL. Porting Glide64 might be a bit harder since the glide wrapper uses shaders.

BTW. I'm pretty close to done on a NEON-ized softfp/hardfp math library (in my sig), however i need some hardwae to test it.

 

[MonkeyChops]

ari, if you don't mind me asking, how long have you been working on this project?

I think that most of us here were hoping that someone was lurking behind the scenes with a n64 project. Its awesome that you made that dream come true. You sir, are my hero. Thank you.

 

[ari64]

Something could probably be done to improve the floating point performance. Currently it calls libc/libm, which I assume is softvfp. However, floating point operations are typically less than 5% of the instructions in most N64 games, so it's not a showstopper.

Yes, definitely start outputting VFP code, if not NEON code (where possible), however..

By 5% do you mean of executable space or of code that's being ran? Because if only 5% of executed code is floating point then that means the Wiz probably can do N64 emulation afterall. In which case, I wonder if you'd be interested in attempting a port there too.

Code that's being ran. There's no specific profiling support in the dynarec, but I added a counter to the code generator in float_assemble() to see how many times this code got run. It was 2.02% of instructions in Super Mario 64, and 3.54% in Ocarina of Time. The latter is probably more typical, Super Mario 64 spends a lot of time in its idle loop.

The problem with Wiz isn't the floating point, it's that the CPU is slower overall, the RAM is a lot slower, and there is no L2 cache. I don't have a Wiz, but go ahead and try it if you do. You'll have to replace the UXTH instructions with ARM9 code, and you might as well get rid of the PLD instructions since these do nothing on the ARM926EJ.

Instead, if you're interested you can test OpenGL ES on x86, using PowerVR's wrapper. I'm sure that'd make it a lot easier for someone else to port it.

I guess I'd have to do something like: mupen -> NanoGL -> wrapper -> OpenGL
I wonder if I can get that to build...

 

[Exophase]

I'm aware how much Wiz sucks compared to Pandora, and for what reasons. It's just that people find N64 emulation on PSP worthwhile, even if it's far from realtime speed. If floats are not executed too often then something on Wiz can potentially be about PSP level, barring the difference a lack of VFPU makes in assisting RSP T&L + clipping.

Unfortunately I can't port anything to Wiz right now and I'm not really a porting kind of person.. but I have a good feeling someone else would be up to the task. Quite possibly Pickle?

I think that converting from OGL to OGL ES2 won't be that bad. I'm not well familiar with Rice, but I would guess that it'd already be using shaders in order to get the blend modes correct. Might just have to convert primitive state commands to VBOs. I bet Adventus would be willing to take a look at it.

By the way, how many instructions per frame are we looking at here? I take it you're doing a fixed number of cycles per instruction and it's probably something like 2 90MHz cycles, so that'd mean 45 million per second? How complex are the idle loops? Can you give any examples of what they're like?

 

[zodttd]

Hi Ari64!

Thank you so much for this! Amazing work! I'm looking through the sources as we speak.

I'm very much looking forward to porting this to the Apple iPhone 3gs. My port's source will be available on my github.com/zodttd.

You have no clue how happy you just made me!

Thanks again,
ZodTTD