I've Been Thinking About This For Awhile Now.

[Exophase]

My epilogue code sets the PC and saves whatever registers need to be saved. I don't store the mapping anywhere else.

Two observations:

1) Here you're calling all non-RAM accesses exceptions, when obviously almost none of them will actually cause exceptions, except in games that use the TLB. The differentiation is important.
2) Storing code that flushes the registers and saves the PC takes up a lot more space than storing the information necessary to do this. That information could be stored separate from the code, so long as you have some way to get to it.

Having an epilogue for every store, and presumably every load, has got to be chewing through a lot of translation cache. If you do want to have this carried out by the code instead of looked up somehow I'd go about it like this:

// Assume the z flag (arbitrarily chosen) determines if a memory access is non-inlined if it's true
bleq extended_store_unique
...

extended_store_unique:
mov r11, pc // Helps us find table entries
b extended_store_generic
.word EMULATED_PC
.byte REGISTER_MAPPING ...

extended_store_generic:
// Do something that handles generic store, and if it causes an exception z flag is set (assume r11 and lr are not damaged; use addne pc, lr, #X if you want to skip something in the inlined code)
bxne lr  

mov r0, [r11]
add r1, r11, #4
bl raise_exception
// Returns translated block address in r0
bx r0

Not rigorously checked, could have problems, but I hope the point is clear. The idea is to minimize the amount of storage necessary for each exception handler.

 

[ari64]

My epilogue code sets the PC and saves whatever registers need to be saved. I don't store the mapping anywhere else.

Two observations:

1) Here you're calling all non-RAM accesses exceptions, when obviously almost none of them will actually cause exceptions, except in games that use the TLB. The differentiation is important.
2) Storing code that flushes the registers and saves the PC takes up a lot more space than storing the information necessary to do this. That information could be stored separate from the code, so long as you have some way to get to it.

Having an epilogue for every store, and presumably every load, has got to be chewing through a lot of translation cache.

Since the SH-2 in the 32X has no MMU, I'm wondering what sort of interrupt Notaz was referring to. I assumed it was something where he needs to save the CPU state, including the cycle count and all the registers.

In my MIPS emulator, the epilogue code for loads and stores uses around 30-40% of the space in the cache.

BTW, returning to lr+4 is not going to make the branch predictor work.

As for the branches jumping into delay slots, it was about 1% of branches in the cases I saw, resulting in about 5% of the blocks being partially duplicated. Not a huge problem, just enough to be annoying.

 

[Exophase]

Since the SH-2 in the 32X has no MMU, I'm wondering what sort of interrupt Notaz was referring to. I assumed it was something where he needs to save the CPU state, including the cycle count and all the registers.

Yes, you need to save all that. I guess outputting a cycle counter update before the stores isn't that big of a deal. There's usually someplace you can schedule something like that.

Sometimes stores can cause interrupts to trigger, rather than exceptions that are directly due to storing in an unallowed location. For instance, if you write to an external interrupt enable mask you can allow a pending interrupt to slip through. Also, if you write to somewhere that puts the CPU to sleep (I don't know if such a feature is present on 32X) then you'll need this. Finally, if the write causes self-modifying code either directly or due to DMA, it might need to know the PC to recover. Depending on your self modifying code strategy. If it modifies the code in the same block then you'll almost certainly need it. I'd like to say I haven't seen things that do that, but sadly I have.

In my MIPS emulator, the epilogue code for loads and stores uses around 30-40% of the space in the cache.

That's kinda a lot.

BTW, returning to lr+4 is not going to make the branch predictor work.

And you said you have what, about 10,000 trapped loads/stores per second? Somehow doesn't seem like a great concern to be mispredicting there on them. Chances are pretty good your hard branches in those relatively one off paths aren't going to be predicted either. But if you feel that strongly about it I'm sure there are ways to deal with an inlined store that follows in a non-destructive fashion with some creative pointer manipulation. And then a bx lr would probably be predicted every time.

As for the branches jumping into delay slots, it was about 1% of branches in the cases I saw, resulting in about 5% of the blocks being partially duplicated. Not a huge problem, just enough to be annoying.

Yeah, that doesn't really sound like much to get worked up over. I'm sure you have a lot more redundant code from other things.

 

[notaz]

Sometimes stores can cause interrupts to trigger, rather than exceptions that are directly due to storing in an unallowed location. For instance, if you write to an external interrupt enable mask you can allow a pending interrupt to slip through.

That's exactly what I was referring to, currently I don't handle this at all and some games don't boot or misbehave due to missed/late external interrupts.

 

[ari64]

In my MIPS emulator, the epilogue code for loads and stores uses around 30-40% of the space in the cache.

That's kinda a lot.

It needs to store the cycle count, registers, and program counter. I suppose you could get the return address from r14 and then look this stuff up in some sort of table. Or load a pointer into some other register.

Notaz claims to be using static register mapping, so maybe he doesn't need to look up the register mapping. I don't know how you statically map 16 SH2 registers onto 12 or 13 ARM registers though.

BTW, returning to lr+4 is not going to make the branch predictor work.

And you said you have what, about 10,000 trapped loads/stores per second? Somehow doesn't seem like a great concern to be mispredicting there on them. Chances are pretty good your hard branches in those relatively one off paths aren't going to be predicted either. But if you feel that strongly about it I'm sure there are ways to deal with an inlined store that follows in a non-destructive fashion with some creative pointer manipulation. And then a bx lr would probably be predicted every time.

The bx won't be predicted if you've modified r14, since the predictor uses its own stack. If there aren't a lot of these cases then it's not a big problem. The 32X memory map seems a bit more complex than N64, so I don't know how well it would work out in practice. Based on the memory map notaz posted in the other thread, it looks like all of the stuff you'd want to trap is below 0x2000000 or above 0x80000000, so maybe you could do a signed compare against 0x2000000 and trap everything less than that.

As for the branches jumping into delay slots, it was about 1% of branches in the cases I saw, resulting in about 5% of the blocks being partially duplicated. Not a huge problem, just enough to be annoying.

Yeah, that doesn't really sound like much to get worked up over. I'm sure you have a lot more redundant code from other things.

I've found redundant recompilation from jumps into delay slots, jumps to locations that weren't anticipated, returns from interrupts, and incorrectly predicting that code would not use 64-bit registers and compiling it 32-bit. The last case you don't have to worry about for SH2 on ARM.

 

[Exophase]

Notaz claims to be using static register mapping, so maybe he doesn't need to look up the register mapping. I don't know how you statically map 16 SH2 registers onto 12 or 13 ARM registers though.

By not mapping the (statistically analyzed to be) least used ones. Register usage for any platform is typically far from evenly distributed, so for the last few you might not miss an awful lot of the time. Compare the result to a typical dynamic allocation scheme which allows no mapping inbetween blocks and flushes registers that appear live but aren't and I really doubt you'll find that this approach isn't superior.

The bx won't be predicted if you've modified r14, since the predictor uses its own stack.

Why do you think that r14 would have been changed by that position? Or do you mean if it's modified but restored? Because in that case it'll be predicted, precisely because of the return stack...

If there aren't a lot of these cases then it's not a big problem. The 32X memory map seems a bit more complex than N64, so I don't know how well it would work out in practice. Based on the memory map notaz posted in the other thread, it looks like all of the stuff you'd want to trap is below 0x2000000 or above 0x80000000, so maybe you could do a signed compare against 0x2000000 and trap everything less than that.

I doubt he'd want to use something like the approach you're using here, it'd most likely be better to use a table. It's still a matter of locations with side-effects vs those without, and most accesses tend to not have side effects.

I've found redundant recompilation from jumps into delay slots, jumps to locations that weren't anticipated, returns from interrupts, and incorrectly predicting that code would not use 64-bit registers and compiling it 32-bit. The last case you don't have to worry about for SH2 on ARM.

What about the simpler case when block A branches into the middle of block B? Or do you not consider this redundant?

 

[notaz]

Notaz claims to be using static register mapping, so maybe he doesn't need to look up the register mapping. I don't know how you statically map 16 SH2 registers onto 12 or 13 ARM registers though.

The ones that are not statically mapped are cached on temporaries, I currently just flush them all before every call to memhandlers.

Based on the memory map notaz posted in the other thread, it looks like all of the stuff you'd want to trap is below 0x2000000 or above 0x80000000, so maybe you could do a signed compare against 0x2000000 and trap everything less than that.

There is evil framebuffer "overwrite mode" at 0x04020000 that needs special treatment - writes with value 0 are ignored there (and some games use that). Might work for reads, but there could be something relying on mirroring though.

 

[notaz]

BTW the results of my register usage profiling were (after running 7 games for I think 100 sec):

27.115% R0  1033124113
19.049% R1   725804485
10.528% R2   401123347
 5.765% R4   219641750
 4.768% R3   181685947
 4.440% R7   169170713
 3.207% SP   122202175
 3.015% R5   114866766
 2.726% R8   103879266
 2.547% R6    97045170
 2.255% PR    85925738
 1.963% R14   74802373
 1.936% R10   73770572
 1.769% R9    67384688
 1.688% MACL  64307284
 1.623% R11   61836795
 1.532% R12   58379313
 1.471% R13   56037376
 1.448% GBR   55172021
 1.154% MACH  43974086
 0.000% VBR       7611

 

[ari64]

Notaz claims to be using static register mapping, so maybe he doesn't need to look up the register mapping. I don't know how you statically map 16 SH2 registers onto 12 or 13 ARM registers though.

The ones that are not statically mapped are cached on temporaries, I currently just flush them all before every call to memhandlers.

So we're basically doing the same thing, generating code to flush the dynamically allocated registers.

Based on the memory map notaz posted in the other thread, it looks like all of the stuff you'd want to trap is below 0x2000000 or above 0x80000000, so maybe you could do a signed compare against 0x2000000 and trap everything less than that.

There is evil framebuffer "overwrite mode" at 0x04020000 that needs special treatment - writes with value 0 are ignored there (and some games use that). Might work for reads, but there could be something relying on mirroring though.

Yuck. Maybe you could have a look up table with a bit that determines whether you write to memory or call a function. Something like:

(r0=value, r1=address, r2=lut)

 lsr r3, r1, #25
 ldr r3, [r2, r3 lsl #2]
 adds r3, r3, r3
 strcc r0, [r1, r3]
 mov r14, pc
 movcs pc, r3

 

[notaz]

Yeah I'm already using that (this idea has been brought up at these forums several times), just not inlining yet. Don't like the missing mirroring handling though (which is taking most of address space, as some SH2 address lines are simply not connected), who knows what may be relying on it.

 

[Paradox]

so what are you guys talking about

I hope it has something to do with developing a DS emulator.

 

[mali]

Don't disturb the wizards while they do their magic. It might burn your face off

 

[DaMummy]

no but seriously, what are all these developers doing in the general talk forum? who let them out of their cages? we need these masterminds back in the cubicle sweatshop

 

[Exophase]

BTW the results of my register usage profiling were (after running 7 games for I think 100 sec):

 27.115% R0  1033124113
 19.049% R1   725804485
 10.528% R2   401123347
  5.765% R4   219641750
  4.768% R3   181685947
  4.440% R7   169170713
  3.207% SP   122202175
  3.015% R5   114866766
  2.726% R8   103879266
  2.547% R6    97045170
  2.255% PR    85925738
  1.963% R14   74802373
  1.936% R10   73770572
  1.769% R9    67384688
  1.688% MACL  64307284
  1.623% R11   61836795
  1.532% R12   58379313
  1.471% R13   56037376
  1.448% GBR   55172021
  1.154% MACH  43974086
  0.000% VBR       7611

Wow, that's impressive. Even on x86 you could possibly get over 70% hit rates with static allocation.

So we're basically doing the same thing, generating code to flush the dynamically allocated registers.

I hope notaz doesn't mind me speaking for him, but I think that his code is unconditionally flushing the dynamically allocated registers before all loads/stores, not generating code to handle flushing them if the accesses cause exceptions.

Yuck. Maybe you could have a look up table with a bit that determines whether you write to memory or call a function. Something like:
(r0=value, r1=address, r2=lut)

lsr r3, r1, #25
ldr r3, [r2, r3 lsl #2]
adds r3, r3, r3
strcc r0, [r1, r3]
mov r14, pc
movcs pc, r3

Yeah, that's similar to what I do in Temper. Of course, in ARMv5+ you get blx, should be able to do that instead of the last two lines, unless there's a problem I'm not seeing with it. But, good call on making the store conditional, now there shouldn't be a reason to do the mispredicting lr + 4 return.

 

[ari64]

The bx won't be predicted if you've modified r14, since the predictor uses its own stack.

Why do you think that r14 would have been changed by that position? Or do you mean if it's modified but restored? Because in that case it'll be predicted, precisely because of the return stack...

I was thinking of something like this:

 bl subroutine
 word 0x12345678
...
subroutine:
 add lr, lr, #4
 ...
 bx lr

I've found redundant recompilation from jumps into delay slots, jumps to locations that weren't anticipated, returns from interrupts, and incorrectly predicting that code would not use 64-bit registers and compiling it 32-bit. The last case you don't have to worry about for SH2 on ARM.

What about the simpler case when block A branches into the middle of block B? Or do you not consider this redundant?

That falls into the category of "jumps to locations that weren't anticipated".

The way I designed this is it looks at all the branches in the block to see where they jump to. Then for those locations, entry code is generated that loads all the dynamically allocated registers at that point. These entry points go into the global jump table, so that other things can jump there. These are used during returns from interrupts, or if another block jumps there.

It is possible that if block A branches into the middle of block B that it might jump to a location for which no entry point was generated. In that case, part of block B would be recompiled.

Yuck. Maybe you could have a look up table with a bit that determines whether you write to memory or call a function. Something like:
(r0=value, r1=address, r2=lut)

lsr r3, r1, #25
ldr r3, [r2, r3 lsl #2]
adds r3, r3, r3
strcc r0, [r1, r3]
mov r14, pc
movcs pc, r3

Yeah, that's similar to what I do in Temper. Of course, in ARMv5+ you get blx, should be able to do that instead of the last two lines, unless there's a problem I'm not seeing with it. But, good call on making the store conditional, now there shouldn't be a reason to do the mispredicting lr + 4 return.

Yes, blx is preferable. I thought the whole point of the lr + 4 was to put a pointer to the register mapping (and possibly program counter and cycle count adjustment) in that space. In that case you could use a movw instruction to load the pointer instead, assuming that a 16-bit value is sufficient, which it should be if it's just an offset to a constant pool at the end of the block.

 

[borgqueenx]

so what are you guys talking about

I hope it has something to do with developing a DS emulator.

go some posts back. they are talking about N64 and/or gpsp. Or general development of emulators.
Not about DS emulation unfortunatly.

 

[Exophase]

  bl subroutine
  word 0x12345678
 ...
 subroutine:
  add lr, lr, #4
  ...
  bx lr

Yeah, such a trick would never be expected to work

That falls into the category of "jumps to locations that weren't anticipated".

The way I designed this is it looks at all the branches in the block to see where they jump to. Then for those locations, entry code is generated that loads all the dynamically allocated registers at that point. These entry points go into the global jump table, so that other things can jump there. These are used during returns from interrupts, or if another block jumps there.

It is possible that if block A branches into the middle of block B that it might jump to a location for which no entry point was generated. In that case, part of block B would be recompiled.

Okay, my basic question is this.. do you continue block analysis after a subroutine call so that branches to before the subroutine call are anticipated? Because otherwise that would be unanticipated, and I think would contribute the most to branches into the middle of blocks (for instance, a loop that has function calls inside it). You likely wouldn't see these as entry points within the first block. Naturally, the subroutine call will be a block end even if you have very high confidence that control will resume to after it, so you will have to exit the block, but if you can look ahead and determine that the portion afterwards will enter the block then you can prepare for it like you've mentioned. For my purposes there hasn't really been enough of a reason to do this, and I preferred to avoid keeping internal branch targets in the external block entry table where possible.

Minimizing block redundancy is a tradeoff - you have to break any propagation analysis at the entry point. Where the compromise should be made is a very difficult question.

Both solutions generate roughly the same number of instructions to flush the registers, the difference is that I avoid executing them most of the time.

Your solution requires more instructions because it has to branch back into the main block, not to mention calls to common code (if not generated uniquely then the same functions would be used to interface this). And the weaving out of the block is harder on code cache pressure. Nonetheless, with notaz's situation where most of the registers are statically allocated he will probably see many branches that don't have any dynamic allocations before them at all. It's not really a comparable situation.

Yes, blx is preferable. I thought the whole point of the lr + 4 was to put a pointer to the register mapping (and possibly program counter and cycle count adjustment) in that space. In that case you could use a movw instruction to load the pointer instead, assuming that a 16-bit value is sufficient, which it should be if it's just an offset to a constant pool at the end of the block.

There are various ways to handle it, each with different tradeoffs. This solution requires knowing where the block ends. Personally I would prefer to have the inlined memory instructions not have to worry about specifying anything. So a block at the end can be keyed per-PC offset for lookups, and possibly marked with something that helps you seek it. This would take more space than putting them relative to the loads/stores themselves but less space than having instructions to load the stuff.

 

[Vlynndar]

You know, what I like about this thread is that I have no idea what you're talking about. I still listen, though.

I feel like a freshly rescued native-to-an-alien-planet standing on the bridge of a science-fiction starship, listening to the brave rescuers discussing how to get their engine working again.

 

[ari64]

That falls into the category of "jumps to locations that weren't anticipated".

The way I designed this is it looks at all the branches in the block to see where they jump to. Then for those locations, entry code is generated that loads all the dynamically allocated registers at that point. These entry points go into the global jump table, so that other things can jump there. These are used during returns from interrupts, or if another block jumps there.

It is possible that if block A branches into the middle of block B that it might jump to a location for which no entry point was generated. In that case, part of block B would be recompiled.

Okay, my basic question is this.. do you continue block analysis after a subroutine call so that branches to before the subroutine call are anticipated?

Yes.

Because otherwise that would be unanticipated, and I think would contribute the most to branches into the middle of blocks (for instance, a loop that has function calls inside it). You likely wouldn't see these as entry points within the first block. Naturally, the subroutine call will be a block end even if you have very high confidence that control will resume to after it, so you will have to exit the block, but if you can look ahead and determine that the portion afterwards will enter the block then you can prepare for it like you've mentioned. For my purposes there hasn't really been enough of a reason to do this, and I preferred to avoid keeping internal branch targets in the external block entry table where possible.

I have to have them in the external block entry table because those internal branches check the cycle count and generate interrupts. When the interrupt returns, it needs to look up those addresses. So I generate entry points for both the branch target and the fall-thru (instruction after the branch).

Minimizing block redundancy is a tradeoff - you have to break any propagation analysis at the entry point. Where the compromise should be made is a very difficult question.

I do end constant propagation at these points, but it's actually pretty rare to find a branch target between a LUI/ADDI pair.

The only analysis that is broken is where I cut down a 64-bit register to 32 bits. Obviously if any register contains an actual 64-bit value, then that entry point can not be used. There are flags in the entry table to identify this situation, and these are checked in jump_eret and get_addr_32 before jumping to any such entry point.

Both solutions generate roughly the same number of instructions to flush the registers, the difference is that I avoid executing them most of the time.

Your solution requires more instructions because it has to branch back into the main block, not to mention calls to common code (if not generated uniquely then the same functions would be used to interface this). And the weaving out of the block is harder on code cache pressure. Nonetheless, with notaz's situation where most of the registers are statically allocated he will probably see many branches that don't have any dynamic allocations before them at all. It's not really a comparable situation.

Yes, there is one additional instruction to jump back into the main block. The reason I put this outside the main block is so that in the common case where it writes directly to memory and generates no interrupt, this extra code never gets executed and never gets loaded into the cache.

The reason that writing out registers takes so much space for MIPS emulation is that 32-bit values must be sign-extended to 64 bits. For ARM->ARM recompilation (as in a DS emulator) this would not need so many instructions.

Yes, blx is preferable. I thought the whole point of the lr + 4 was to put a pointer to the register mapping (and possibly program counter and cycle count adjustment) in that space. In that case you could use a movw instruction to load the pointer instead, assuming that a 16-bit value is sufficient, which it should be if it's just an offset to a constant pool at the end of the block.

There are various ways to handle it, each with different tradeoffs. This solution requires knowing where the block ends. Personally I would prefer to have the inlined memory instructions not have to worry about specifying anything. So a block at the end can be keyed per-PC offset for lookups, and possibly marked with something that helps you seek it. This would take more space than putting them relative to the loads/stores themselves but less space than having instructions to load the stuff.

I don't know in advance where the block ends. To generate the constant pool, I put the values into a queue, and at the end of the block write it out then patch the instructions that reference it. If you don't want to have instructions that load this stuff then I suppose you could put an invalid instruction at the end of the block, then search forward from r14 until you find it, then search from there until you find the data for the location you want. I hope interrupts are infrequent because this will be slow. Or do a binary search tree on r14. But seriously, we are talking about what, 10 bytes of data? It's not that big of a deal.

 

[Exophase]

Yes.

Okay, so the main difference between this approach and having the function return generate the new block is that you'll be able to branch back into the first block, I guess. From a temporal locality of reference point of view I'm not sure if the redundancy hit is a big deal, since hopefully the big tight loops that are run the most won't be full of functions. Of course, in the real world they probably are.. inlining small leaf functions for other reasons might minimize this.

Maybe something I'll have to experiment with later >_>

I have to have them in the external block entry table because those internal branches check the cycle count and generate interrupts. When the interrupt returns, it needs to look up those addresses. So I generate entry points for both the branch target and the fall-thru (instruction after the branch).

If you have the PC at the time of the interrupt (which you need regardless) then you can create a new external block entry table, only as necessary. If this table is hashed then it's a good idea to keep the number of entries down.

I do end constant propagation at these points, but it's actually pretty rare to find a branch target between a LUI/ADDI pair.

The only analysis that is broken is where I cut down a 64-bit register to 32 bits. Obviously if any register contains an actual 64-bit value, then that entry point can not be used. There are flags in the entry table to identify this situation, and these are checked in jump_eret and get_addr_32 before jumping to any such entry point.

I think correctly handling dynamic register allocation against breaks is the bigger problem, but maybe you are somehow folding the two allocation graphs together.

The reason that writing out registers takes so much space for MIPS emulation is that 32-bit values must be sign-extended to 64 bits. For ARM->ARM recompilation (as in a DS emulator) this would not need so many instructions.

For ARM->ARM I would definitely use notaz's approach of static register allocation for most then a small potential for dynamic allocation in the 1 or 2 registers that have to be kept free as temporaries anyway. These would get spilled so often when used as temporaries anyway, I doubt it'd be worth an awful lot to make their spilling conditional around loads and stores.

For GBA (and even DS) emulation you'll see a lot of Thumb code which makes a lot of the registers even less referenced.

I don't know in advance where the block ends. To generate the constant pool, I put the values into a queue, and at the end of the block write it out then patch the instructions that reference it. If you don't want to have instructions that load this stuff then I suppose you could put an invalid instruction at the end of the block, then search forward from r14 until you find it, then search from there until you find the data for the location you want. I hope interrupts are infrequent because this will be slow. Or do a binary search tree on r14. But seriously, we are talking about what, 10 bytes of data? It's not that big of a deal.

The invalid instruction approach is what I was thinking. To clarify, when you say interrupts you really just mean exceptions or interrupts caused by/after loads or stores, which in an architecture without MMU would usually be very infrequent. Interrupts that happen as a result of cycle counting can be dealt with by a separate mechanism.

The actual scheme I have in mind right now is to have interrupts only checked at the start of blocks. Blocks would internal patch forward branches within the same block, but not backwards branches (loops) - yes, this will mean more redundant code generated, but it simplifies a lot of things. Information needed for the interrupt (PC) would be stored in a header before the start of the block. Since interrupts can only happen at the start of blocks it means that nothing special needs to be done for cycle counting or register allocation, since those affairs are already in order, and it's easy to store things before the block starts.

Interrupts that happen due to stores will have to have their information stored either at the end of the block or in a global table. I too considered binary searching a keyed table based on return address; the good thing about this approach is that you don't have to sort the list as you add to it because the translation buffer indexes will be naturally incrementing as you go. You could have a small hash table to speed it up, but really I think these operations will be so infrequent that it doesn't really matter. You would also need it for self modifying code that modifies the same block you're currently in, although that should only happen for stores too.