Whoops

It turns out that exophase had already suggested two of the three optimisations I implemented this weekend in a conversation we had way back in February.

Whoops! It's been such a long time, I'd totally forgotten we'd talked about it. I really should pay more attention sometimes - if I had been you might have seen some of these improvements way back in R9. Sorry exophase - kudos for spotting this so long ago!

-StrmnNrmn

Interesting Dynarec Hack

I was playing around with the code generation a couple of evenings ago, and realised that if I made a certain assumption, I could drastically speed up specific types of memory accesses.

When I discussed load/store handling on Sunday, I presented the new code that is typically generated for handling a load such as 'lw $t0, 0x24($t1)' on the N64:

  ADDIU     a0 = s1 + 0x0024    # add offset to base register
  SLT       t0 = (a0  BEQ       t0 != r0 --> _Trampoline_XYZ123 # branch to trampoline if invalid
  ADDU      a1 = a0 + s7        # add offset to emulated ram
  LW        s0 <- 0x0000(a1)    # load data

(I'll ignore all the extra code which is generated, and just concentrate on the 5 instructions above which correspond to the expected path of execution.)

Of the 5 instructions that are generated, two - the SLT and BEQ - are just there for performing error handling in the case that the address is invalid, a hardware register (i.e. for memory-mapped I/O), or a virtual address. I'll call this error handling for short.

If we were generating code in an idealised environment where we didn't have to perform error handling, we could drop the SLT/BEQ instructions to get this:

  ADDIU     a0 = s1 + 0x0024    # add offset to base register
  ADDU      a1 = a0 + s7        # add offset to emulated ram
  LW        s0 <- 0x0000(a1)    # load data

We could then optimise this even further and perform the offset calculation directly as a part of the LW instruction:

  ADDU      a1 = s1 + s7        # add offset to emulated ram
  LW        s0 <- 0x0024(a1)    # load data

In this idealised situation we could reduce an emulated load to just two instructions, with no branches. That's a pretty good saving!

The problem is that the environment we're generating code from is not 'ideal', and it's hard to know in advance of time which memory accesses are going to directly access physical ram, and which are going to access hardware registers or require virtual address translation. For that reason, we have to place a guard around every memory access to make sure that it behaves correctly. At least, that was the way I was thinking until earlier in the week.

What I realised on Monday is that I can make an assumption that lets me remove the error handling code for certain types of load/stores. The assumption is that when the N64 accesses any memory through the stack pointer ($sp) register, the address is always going to be valid, physical memory.

The assumption relies on the fact that most roms don't do anything particularly clever with their stack pointers - it gets set up for each thread to point at a valid region of memory then the game just runs along, pushing and popping values from it as the code executes. Of course, if the assumption is wrong then the emulator will just crash and grind to a halt in a unpredictable manner :)

It was straightforward to add a hack to the code generation to exploit this kind of behaviour, and the results have been better than I expected - I'm seeing at least a 10% speed up, and the code expansion factor (the ratio of generated bytes of instructions to input bytes) has dropped from around 5.0x to 4.0x. Stability has been excellent too - I've run about 8 roms with the hack so far, and all of them have run perfectly.

I think one of the reasons the hack has such an impact is that a lot of the memory accesses in a typical C program are through the stack. Here's an example snippet from the entry to a function on the N64, where the compiler emitted code to store the return address and arguments:

SW        ra -> 0x0014(sp)
SW        a0 -> 0x0058(sp)
SW        a1 -> 0x005c(sp)
SW        a2 -> 0x0060(sp)

When I look through disassembly for the roms I'm working on, it's very common to see lots of sequential loads/stores relative to the stack pointer like this.

Previously Daedalus generated around 20 instructions (including 5 branches) for the above snippet. With the hack, the generated code now looks like this:

ADDU      t1 = s1 + s7
SW        s4 -> 0x0014(t1)
ADDU      t1 = s1 + s7
SW        s3 -> 0x0058(t1)
ADDU      t1 = s1 + s7
SW        s2 -> 0x005c(t1)
ADDU      t1 = s1 + s7
SW        s5 -> 0x0060(t1)

8 instructions, 0 branches. What's more, it looks like with a little work, I could eliminate 3 redundant address calculations:

ADDU      t1 = s1 + s7
SW        s4 -> 0x0014(t1)
SW        s3 -> 0x0058(t1)
SW        s2 -> 0x005c(t1)
SW        s5 -> 0x0060(t1)

Now that would be efficient :)

I still want to do lots of testing with the hack. I want to find out if there are roms that don't work with the hack enabled, and how common a problem it is. It's such a significant optimisation though that I'm certain I'll be adding it as an option in Daedalus R13. The results of my testing will probably determine whether I default it to on or off though.

So far Daedalus R13 is shaping up to be significantly faster than R12. I'm still not sure when I'll be ready to release it, but you'll hear about it here first.

-StrmnNrmn

Dynarec Improvements

I've had a fairly productive week working on optimising the Dynarec Engine. It's been a few months since I worked on improving the code generation (as opposed to simply fixing bugs), so it's taken me a while to get back up to speed.

At the end of each fragment, I perform a little housekeeping to check whether it's necessary to exit from the dynarec system to handle various events. For instance, if a vertical blank is due this can result in me calling out to the graphics code to flip the current display buffers. The check simply involves updating the N64's COUNT register, and checking to see whether there are any time-dependent interrupts to process (namely vertical blank or COMPARE interrupts.)

I had an idea on the train into work on Monday I realised that there were a couple of ways in which I could make this more efficient. Firstly, the mechanism I was using to keep track of pending events was relatively complex, involving maintaining doublely-linked lists of events. I realised that if I simplified this code it would make it much easier for the dynarec engine to update and check this structure directly rather than calling out to C code.

The other idea I had on the train was to split up the function I was calling to do this testing into two different versions. There are two ways that the dynarec engine can be exited - either through a normal instruction, or a branch delay instruction (i.e. an instruction immediately following a branch.) My handler function catered for both of these cases by taking a flag as an argument. I realised that by providing a separate version of this function for each type I could remove the need to pass this flag as an argument, which saved a couple of instructions from the epilogue of each fragment.

These two small changes only took a couple of hours to implement, but yielded a 3-5% speedup on the various roms I tested. They also slightly reduced the amount of memory needed for the dynarec system, improving cache usage along the way.

The next significant optimisation I made this week was to improve the way I was handling the code generation for load/stores. Here's what the generated code for 'lw $t0, 0x24($t1)' looks like in Daedalus R12 (assume t1 is cached in s1, and t0 is cached in s0 on the PSP):

  ADDIU     a0 = s1 + 0x0024     # add offset to base register
  SLT       t0 = (a0<s6)      # compare to upper limit
  ADDU      a1 = a0 + s7         # add offset to emulated ram
  BNEL      t0 != r0 --> cont # valid address?
  LW        s0 <- 0x0000(a1)  # load data
  J         _HandleLoadStore_XYZ123 # handle vmem, illegal access etc
  NOP
cont:
  # s0 now holds the loaded value,
  # or we've exited from dynarec with an exception

There are a couple of things to note here. Firstly, I use s6 and s7 on the PSP to hold two constants throughout execution. s6 is either 0x80400000 or 0x80800000 depending on whether the N64 being emulated has the Expansion Pak installed. s7 is set to be (emulated_ram_base - 0x80000000). Keeping these values in registers prevents me from using them for caching N64 registers, but the cost is far outweighed by the more streamlined code. As it happens, I also use s8 to hold the base pointer for most of the N64 CPU state (registers, pc, branch delay flag etc) for the same reason.

So the code first adds on the required offset. It then checks that the resulting address is in the range 0x80000000..0x80400000, and sets t0 to 1 if this is the case, or clears it otherwise*. It then adds on the offset (emulated_ram_base - 0x80000000) which gives it the translated address on the psp in a1. The use of BNEL 'Branch Not Equal Likely' is carefully chosen - the 'Likely' bit means that the following instruction is only executed if the branch is taken. If I had used a plain 'BNE', the emulator could often crash dereferencing memory with the following LW 'Load Word'.

Assuming the address is out of range, the branch and load are skipped, and control is passed to a specially constructed handler function. I've called it _HandleLoadStore_XYZ123 for the benefit of discussion, but the name isn't actually generated, it's just meant to indicate that it's unique for this memory access. The handler function is too complex to describe here, but it's sufficient to say that it returns control to the label 'cont' if the memory access was performed ok (e.g. it might have been a virtual address), else it bails out of the dynarec engine and triggers an exception.

When I originally wrote the above code I didn't think it was possible to improve it any further. I didn't like the J/NOP pair, but I saw them as a necessary evil. All 'off trace' code is generated in a second dynarec buffer which is about 3MiB from the primary buffer - too far for a branch which has a maximum range of +/-128KiB. I used the BNEL to skip past the Jump 'J' instruction which can transfer control anywhere in memory.

What I realised over the weekend was that I could place a 'trampoline' with a jump to the handler function immediately following the code for the fragment. Fragments tend to be relatively short - short enough to be within the range of a branch instruction. With this in mind, I rewrote the code generation for load and store instructions to remove the J/NOP pair from the main flow of the trace:

  ADDIU     a0 = s1 + 0x0024    # add offset to base register
  SLT       t0 = (a0<s6)     # compare to upper limit
  BEQ       t0 != r0 --> _Trampoline_XYZ123 # branch to trampoline if invalid
  ADDU      a1 = a0 + s7        # add offset to emulated ram
  LW        s0 <- 0x0000(a1) # load data
cont:
  # s0 now holds the loaded value,
  # or we've exited from dynarec with an exception
  #
  # rest of fragment code follows
  # ...
  
  
_Trampoline_XYZ123:
  # handler returns control to 'cont'
  J     _HandleLoadStore_XYZ123  
  NOP

The end result is that this removes two instructions from the main path through the fragment. Although in the common case five instructions are executed in both snippets of code, the second example is much more instruction cache friendly as the 'cold' J/NOP instructions are moved to the end of the fragment. I've heard that there is a performance penalty for branch-likely instructions on modern MIPS implementations, so it's nice to get rid of the BNEL too.

As with the first optimisation, this change yielded a further 3-5% speedup.

The final optimisation I've made this weekend is to improve the way I deal with fragments that loop back to themselves as they exit. Here's a simple example:

8018e014 LB        t8 <- 0x0000(a1)
8018e018 LB        t9 <- 0x0000(a0)
8018e01c ADDIU     a0 = a0 + 0x0001
8018e020 XOR       a2 = t8 ^ t9
8018e024 SLTU      a2 = (r0<a2)
8018e028 BEQ       a2 == r0 --> 0x8018e038
8018e02c ADDIU     a1 = a1 + 0x0001
8018e038 LB        t0 <- 0x0000(a0)
8018e03c NOP
8018e040 BEQ       t0 == r0 --> 0x8018e058
8018e044 NOP
8018e048 LB        t1 <- 0x0000(a1)
8018e04c NOP
8018e050 BNE       t1 != r0 --> 0x8018e014
8018e054 NOP

I'm not sure exactly what this code is doing - it looks like a loop implementing something like strcmp() - but it's one of the most executed fragments of code in the front end of Mario 64.

The key thing to notice about this fragment is that the last branch target loops back to the first instruction. In R12, I don't perform any specific optimisation for this scenario, so I flush any dirty registers that have been cached as I exit, and immediately reload them when I re-enter the fragment. Simplified pseudo-assembly for R12 looks something like this:

enter_8018e014:
  load n64 registers into cached regs
  
  perform various calculations on cached regs
  
  if some-condition
      flush dirty cached regs back to n64 regs
      goto enter_8018e038
  
  perform various calculations on cached regs
  
  flush dirty cached regs back to n64 regs
  
  if ok-to-continue
      goto enter_8018e014
exit_8018e014:
  ...
  
enter_8018e038:
 ...

The key thing to notice is that we load and flush the cached registers on every iteration through the loop. Ideally we'd just load them once, loop as much as possible, and then flush them back to memory before exiting. I've spent the day re-working the way the dynamic recompiler handles situations such as this. This is what the current code looks like:

enter_8018e014:
  load n64 registers into cached regs
  mark modified regs as dirty

loop: 
  perform various calculations on cached regs
  
  if some-condition
      flush dirty cached regs back to n64 regs
      goto enter_8018e038
  
  perform various calculations on cached regs
   
  if ok-to-continue
      goto loop

  flush dirty cached regs back to n64 regs
exit_8018e014:
  ...
  
enter_8018e038:
 ...

In this version, the registers are loaded and stored outside of the inner loop. They may still be flushed during the loop, but only if we branch to another trace. Before we enter the inner loop, we need to mark all the cached registers as being dirty, so that they're correctly flushed whenever we finally exit the loop.

This new method is much more efficient when it comes to handling tight-inner loops such as the assembly shown above. I still have some work to do in improving my register allocation, but the changes I've made today yield a 5-6% speedup. Combined with the other two optimisations I've described, I'm currently seeing an overall 10-15% speedup over R12.

I'm quite excited about the progress I've made so far with R13. I still have lots of ideas for other optimisations I want to implement for R13 which I'll talk about over the coming days. I don't have any release date in mind for R13 at the moment, so there's no point in asking me yet :)

-StrmnNrmn


*The SLT instruction is essentially doing 'bool inrange = address >= 0x80000000 && address < (0x80000000+ramsize)'. I think the fact that this can be expressed in a single instruction is both beautiful and extremely fortunate :)

333 MHz

On startup Daedalus increases the default clock frequency of the PSP's cpu from 222MHz to 333MHz for a 'free' 50% speedup. I use 'free' in quotes because this comes at the expense of drawing more power so the battery runs out of charge faster.

I've been asked if I'm going to support 333MHz many times, so I wanted to put this question to rest for once and for all. The answer is yes - I believe this has been the case since R1 :)

-StrmnNrmn

R11 Sometime on Sunday

I'm very close to having R11 ready for release, and I'm aiming to have everything finished some time tomorrow morning (that's Sunday morning, UK time.)

I've spent the day putting in number of changes to the way that Daedalus allocates memory for various lookup tables. Namely, I've replaced a couple of stl maps I was using to keep track of cached textures and dynarec fragments with sorted vectors, which should help reduce fragmentation and improve cache usage. Basically it should make things even more stable and give another small speedup.

I've also been through and updated the rom.ini file I talked about a couple of weeks ago to make sure that it contains accurate information for the save type. I noticed that many of the entries for European roms were undefined, which can cause various compatibility problems. Hopefully this should mean that a few more European roms are working in R11.

Finally I realised that there was a dynarec issue which was preventing Super Smash Bros from going in-game. Although that's not fixed (that's something for R12) I have disabled dynarec for SSB by default. With my various texture cache fixes SSB is now running in-game, albeit with messed up graphics and at just 15 fps. Here's a teaser screenshot of SSB running in R11:



Given how many people have been asking for SSB compatibility to be improved, I'm pretty sure this is going to be my main focus for R12. If I can fix the dynarec issue it looks like this is going to run at a solid 25-30fps or more.

Anyway, check back sometime over the next 12 hours for R11 (I'm off to bed for now, let's hope I don't lie in :)

-StrmnNrmn

R10 Plan of Action

Before I went away on holiday I asked you what you thought I should look at working on for the next release of Daedalus. Over 200 of you replied, and I've greatly enjoyed reading what you've had to say. There were some brilliant suggestions, so many thanks for your contributions.

It seems pretty clear to me that speed is the single biggest issue that most people want to see addressed. Many people also mentioned compatibility and savestate or save game support, but in nowhere near the same kind of numbers as those wanting speed improvements.

Based on your feedback my current plan is to release Daedalus R10 at the end of March, focusing mostly on speed improvements. If I can fit in any easy compatibility fixes, I'll do this too*.

Several people have asked what possibilities remain for optimisation. Here's a short list of things I know need more work:

• In many games, a lot of the time spent executing dynamically recompiled code is doing things which can potentially be emulated at a high level. For instance, over 5% of the time spent executing dynarec code in Mario64 is just converting matrices from floating point to fixed point format. Another 4-5% of the time is spent in a loop invalidating areas of the data cache (which is irrelevent in an emulator.)
• Some of the most expensive fragments are those which branch to themselves (i.e. those doing many loops). I can optimise for this to avoid loading and flushing cached registers on each iteration through the loop.
  
• I can implement a frameskip option (I had intended to implement this for R9, but forgot!)
• I can make use of the Media Engine (as Exophase suggested in conversation, as the ME can't access VRAM, it might make more sense to execute Audio and Display Lists on the main CPU, and run the N64 CPU emulation on the PSP ME)
• There are certain situations where I fail to create fragments in the dynamic recompiler - for instance if the code being recompiled writes to a hardware register, this triggers an interrupt and causes fragment generation to be aborted. I should be able to deal with situations such as this more gracefully.
• The fragment generator can do a lot more to improve register caching, and eliminating redundant 64-bit operations.
• There are many situations where N64 roms busy wait. I detect very simple occurances of this, but not all of them. If I manually identify more complex examples I can have the fragment generator optimise them away.
  
• Some roms are causing the dynarec fragment cache to be repeatedly dumped and recreated (I think Banjo Kazooie is one example of this). Fixing this may just involve tweaking a couple of magic numbers.
• I currently optimise memory accesses under the assumption that most accesses are in the range 0x80000000 - 0x80800000, which is incorrect in the case of roms that make heavy use of virtual memory, or access RAM through the mirrored range at 0xa0000000. I can improve the trace recorder to collect information on which range a memory access fell in, and generate code to speculatively optimise for this.
• Now that the dynarec engine is producing much better code, the cost of display list processing is becoming more significant, and may finally be worth profiling and optimising.

That's quite a big list, so I doubt I'll be able to work on these things before the end of March, but I think it shows there's still a lot of scope for further optimisation.

-StrmnNrmn

*Just this morning, I figured out why the Expansion Pak support was broken, so Majora's Mask and a couple of other games relying on this are booting correctly now :)

Behold! An update!

Wow, it's been a long time since the last update. A really long time. How did that happen?

I've always found it quite hard to find the time to update the blog. Usually when I have some free time in the evenings (that's free time spent doing things other than eating, socialising, and getting stuff ready for work), the choices I have are:

• Do some new development on Daedalus
• Play games/watch TV/relax
• Reply to a few emails/comments, post a new entry here
  

Unfortunately over the past half year or so the first two bullet points have won out. So, apologies for neglecting the 'outside world' for so long. On the plus side, the existance of the first bullet points means that I have lots of exciting new developments to talk about over the next few days :)

I'm going to finish off this reintroduction with a broad overview of some of the stuff I've been working on. This is all stuff that will be present in R9, which I'd like to release this month.

• Added support for RGBA 4444 and 5551 textures, saving a bunch of memory in the front end.
• Tidied up all the texture conversion code, fixing a few bugs in the process
• Fixed the width/height of FillRect calls in 1 and 2 cycle mode (fixed a few small graphical issues)
  
• Fixed a blending bug (fixed a few small graphical issues)
  
• Use 16-bit textures on the PSP to represent 16-bit N64 textures. Saves time converting, saves memory, and faster rendering
• Added mirrored texture support (this fixes lots of small graphical glitches)
• Fixed a LoadTile bug, allowing a couple of hacks to be removed (this also fixes various small graphical glitches)
• Added some new blend modes for various roms
• Fixed the Tri2 command for F3DLX microcodes
• Fixed a bug in busy-wait detection (this wasn't working correctly with dynarec code, net result is a small speedup)
• Fixed a few dynarec stability issues (relating to exceptions occuring mid-trace)
• Added audio support :)
• Added the ability to dump textures (developer builds only at the moment)
• Fixed screenshots. Again.
• Implemented cmp.s, cvt.s, cvt.w, mtc1, mfc1, bc1f, bc1t, j, cfc1, ctc1, daddu, trunc.w.s, bc1t, bc1f, bc1tl, bcifl, bnel, beql, blezl, bgtzl, bltzl, blezl in dynarec (this gives a decent speedup)
• Avoid setting the branch delay flag and current PC in generated dynarec code unless absolutely necessary (this gives another small speedup)
• Much better memory access handling in dynamically recompiled code (this gives a BIG speedup :)
• Use a second code buffer for generated dynarec code, to avoid polluting the instruction cache (this gives another small speedup)
• Further improve the memory access handling in generated dynarec code (another small speedup)
• Fix register usage analysis for lwc1/swc1/mfc1/mtc1 which was preventing base registers used in these instructions from being cached (another small speedup)
• Have compensation blocks restore nobbled registers, so on-trace code does't need to reload (another small speedup)

There's quite a lot in that list, so I highlighted the two most significant points. In summary R9 will be much faster, with audio support. I'll write a bit more about these changes in particular over the next few days (promise!)

-StrmnNrmn