I've Been Thinking About This For Awhile Now.

[Paradox]

exophase, do you realise you are quoting yourself and replying to your own quotes? @_@;;;

 

[Exophase]

exophase, do you realise you are quoting yourself and replying to your own quotes? @_@;;;

Actually I just got the name field wrong when copying and pasting it. I'm not actually quoting myself, I'm quoting Ari64 >_<

 

[Vlynndar]

Aw, darnit. I was just ready to get a nice signature.

 

[ari64]

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 timed the difference between ending the block at the call and continuing. Continuing the blocks resulted in code that ran 3-5% faster. There were a few cases where it went off the end of the block and compiled junk. So I will need to do something about that, such as switching strategies when encountering invalid instructions.

Inlining leaf functions is great from a performance point of view, but hell from a SMC point of view. If something touches that leaf function, you have to wipe out every block that inlined it. And keep lists of blocks that inline other blocks, to be able to do this.

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.

That's an interesting idea. It would be possible to put the entry point right after the exit point, so that a return (bx r14) would take you there. The only problem is that in the cases where there are no dynamically allocated registers, you end up with an extra jump there. (If there are no dynamically allocated registers, then I don't normally create a special entry point, just a jump into the block.) It might be useful for the specific case of MMU exceptions, which can return to locations that nothing else would jump to.

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.

I'm not quite sure what you're getting at here. If there is a difference in the dynamically allocated registers at the branch and the location it jumps to, then I insert instructions to load/store those registers.

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.

Checking at the start of a block instead of the end can be advantageous if you want to preserve flags to use them for conditional branches at the end. Then you only have to save flags at the start of blocks where you know that the block will check the flags. But how are you handling loops, recompiling every loop as a separate block?

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.

Currently I'm not handling pagefaults properly... Basically I push the callee-saved registers, call memhandlers, restore the registers, and jump back into the block. Since there's already a jump there, I will probably go with the end-of-the-block approach, and load the register mapping from after the jump.

 

[Exophase]

I timed the difference between ending the block at the call and continuing. Continuing the blocks resulted in code that ran 3-5% faster. There were a few cases where it went off the end of the block and compiled junk. So I will need to do something about that, such as switching strategies when encountering invalid instructions.

Is the performance improvement due to having better register allocation carry over for local branches? Or do you think that the decrease in icache pressure is a major contributor?

Inlining leaf functions is great from a performance point of view, but hell from a SMC point of view. If something touches that leaf function, you have to wipe out every block that inlined it. And keep lists of blocks that inline other blocks, to be able to do this.

Damn, you're right. Of course, that only applies if you're doing something more involved than wiping out the entire cache on code modifications. For some modification patterns this will be sufficient.

I'm not quite sure what you're getting at here. If there is a difference in the dynamically allocated registers at the branch and the location it jumps to, then I insert instructions to load/store those registers.

Ah okay, if it's handled at the branch then what I'm saying is moot.

Checking at the start of a block instead of the end can be advantageous if you want to preserve flags to use them for conditional branches at the end. Then you only have to save flags at the start of blocks where you know that the block will check the flags.

Yes, you are right; better likelihood for dead flags is another advantage I forgot to mention.

But how are you handling loops, recompiling every loop as a separate block?

Yes. I don't know how much cache space this will waste - the more nested loops are the worse it'll become. But if programs are spending a good deal of their time in relatively long loops it shouldn't add a lot of icache pressure.

Currently I'm not handling pagefaults properly... Basically I push the callee-saved registers, call memhandlers, restore the registers, and jump back into the block. Since there's already a jump there, I will probably go with the end-of-the-block approach, and load the register mapping from after the jump.

I know you've mentioned this approach before, but are you currently running into any problems with it?

 

[ari64]

I timed the difference between ending the block at the call and continuing. Continuing the blocks resulted in code that ran 3-5% faster. There were a few cases where it went off the end of the block and compiled junk. So I will need to do something about that, such as switching strategies when encountering invalid instructions.

Is the performance improvement due to having better register allocation carry over for local branches? Or do you think that the decrease in icache pressure is a major contributor?

Both, and also if the liveness analysis indicates that a register won't be used at the branch target then it doesn't need to be saved.

Ah okay, if it's handled at the branch then what I'm saying is moot.

How else would you do it?

Currently I'm not handling pagefaults properly... Basically I push the callee-saved registers, call memhandlers, restore the registers, and jump back into the block. Since there's already a jump there, I will probably go with the end-of-the-block approach, and load the register mapping from after the jump.

I know you've mentioned this approach before, but are you currently running into any problems with it?

Well the reason I did this is because very few N64 games cause pagefaults. So it's a lot quicker to just shove the registers on the stack and restore them, rather than storing them in their proper places.

The problem of course is, if a memory access does cause a pagefault then I need to restore the registers, figure out the mapping, and then save them properly.

Another issue is that I originally wrote this on x86, but newer gcc uses movdqa on stack data, which will fail if the stack is not aligned to 16 bytes. So now I need to fix all this stack usage. (4-byte alignment on ARM is fine.)