Dynamic Recompilation - An Introduction

Calling dynamically generated code

As announced yesterday I'll provide a simple example now that shows how to call dynamically generated code. For some this might be even more intimidating, but those who looked up how function pointers work in C and have a slight understanding of x86 assembly it should make clear how that calling process works.

This code has been written with GCC in mind, but it should work with any C compiler on any x86 operating system that passes function arguments on the stack.

I originally wrote this example with some ARM machine code instead of x86, and all that I had to change was the definition of the code[] array.
That's the nice thing about working with a function pointer to call dynamic code, apart from the generated code everything else is totally portable to any system with a C compiler.

A warning to those working with harvard architecture processors (ie. those with split instruction and data caches):
After copying the code and before calling it you'll have to flush the caches, otherwise the code will be in the data cache but not in the instruction cache and the processor will get into trouble.

While x86 processors nowadays have split L1 caches as well it's not a problem on these because they solve such issues in hardware due to transpartent compatibility with x86 processors that still had a unified cache.

Ok, so much for dynamically generated code...
Anyone still with me?

When is using a dynarec reasonable?

Those who are still following this thread probably noticed that dynamic recompilation is far from being trivial, and I haven't even touched the more complex issues yet.

This leads to the ultimate question: When does it make sense to use dynamic recompilation anyway?

The advantages of dynamic recompilation are:

• more speed
• more speed (nothing else really)

The disadvantages of dynamic recompilation are:

• quite complicated
• hard to debug
• not as exact as interpretive emulation
• not portable to systems with other processors
• problems with self-modifying code

This means, as long as you can pull the whole emulation off at a decent speed by using traditional emulation (perferable even a portable solution), just do it and don't give dynamic recompilation a second thought.
Although I've seen people toying with dynarecs for 6502 and similar 8-bit processors it's not worth the hassle, since a nice CPU core written in C would be portable to different systems and should run at full speed on any current and even most older computers.

Even most 16-bit processors should be tried in interpretive emulation before thinking of dynamic recompilation. One of the few reasonable 16-bit candidates would be the 68000, because it is widely used and quite complex, so a dynarec for it might speed up a lot of emulators if you stick to the same API.

Where dynamic recompilation really shines is 32-bit and 64-bit processors, because it makes sense to do operations on hardware registers when the original code does so. Especially the MIPS (used in PSX and N64, eg.) and SuperH (Saturn eg.) processors with their simple instruction set should be emulated via dynamic recompilation to get a decent speed.

One thing to keep in mind is that an emulator with a dynarec needs a lot of RAM, because it not only needs at least the same amount of memory as a traditional emulator but additionally also memory for the translation cache, ie. the code blocks that have already been translated.

Eventually, it's a good idea to start with interpretive emulation to see if that's fast enough and switch to dynamic recompilation when it isn't. During the switching process it's a good idea to keep both CPU emulations to test the dynarec against the interpreter which should make debugging a little easier.

Threaded Interpreter - The compromise

Some emulators that claim to use dynamic recompilation actually utilize a technique called threaded interpretation, eg. Generator does that (http://www.squish.net/generator/docs.html).

How does threaded interpretation differ from dynamic recompilation and what do they have in common?

Both techniques work on code blocks and "translate" these into some other representation. This means that both share the disadvantage of needing more memory than a traditional emulator and having problems when the already translated code should be changed by the translation (keyword: self-modifying code).

But instead of translating to code threaded interpretation fills the translation cache with addresses to the instruction emulation routines instead, ie. each instruction found in the source binary will be translated to an address and parameters that point to a piece of code in the emulator that emulates this instruction.

The only thing that you spare compared to a traditional emulator so far is the repetive decoding of all instructions in a block. But threaded emulation can take one further step. Due to having to analyze a whole block of code you can find out which condition flags need to be calculated for an instruction, ie. if a certain flag is overwritten by the side-effect of a following instruction before it can be tested or taken as input by another it doesn't have to be calculated. Since calculation of condition flags often can need more than half the time to emulate an instruction this approach can lead to a noticable speed improvement.
The emulator Generator mentioned above has two different emulation functions for each single instruction, one that calculates all flags and another that doesn't calculate any flags. The address of one of these functions will be added to the translation cache as appropriate.

The advantage of threaded emulation is that it can be portable when it is programmed in a high-level lamguage (like C) and works with function pointers.
The disadvantage is that you cannot access hardware registers directly (unless the instruction routines are written in assembly and you are using static register allocation, but then it wouldn't be portable and you could also use dynamic recompilation), so you still need to access the register file in memory every time an instruction reads or alters a register.

I think that should be enough about threaded interpreting...
Maybe I should cover register allocation next, since I already mentioned it here.

Intermediate Summary

Ok, maybe I should sum up some of the stuff here that no one can complain about too much information ;-)

Dynamic recompilation also known as dynamic binary translation is the process of translating binary code blocks during runtime into the binary code of the host machine.

The translated code is collected in a translation cache.

In a dispatcher loop the dynarec decides if certain code blocks still have to be translated and eventually calls the translated code.

The generated code is ideally called using a function pointer.
Here is an example how the function pointer code above has to be changed to get the same result on an ARM processor based machine:

As you can see only the code[] array (that would be the generated code in a real dynarec) has to be changed. The switch from "unsigned char" to "unsigned long" has only been made due to the fact that ARM has 32-bit fixed lenght instructions, but since we cast it to the function pointer later there is no difference.

Of course the code generator has to be different on each processor, but it makes sense to make everything else portable, thus you only have to write a new code generator but not a totally new emulator.

Mind you that an ARM processor with separate instruction and data caches (eg. the StrongARM) needs its caches to be flushed before the code can be called, but that's operating system specific and I won't go into that detail here.

Register Allocation

One of the big advantages of dynamic recompilation is that you can actually use the registers of the host machine when an emulated instruction uses registers. This can not only reduce the amount of instructions needed to emulate another instruction but also minimize slow memory accesses for every referenced register.
The process of mapping the emulated registers to the registers of the host machine is called register allocation.

Unfortunately a lot of dynarecs in emulators still fetch all needed register values from the register file (just a memory structure where the contents of all registers of the emulated processor) in the beginning of each emulated instruction and write the result back to the register file afterwards. Only a little better are those that don't store the value of the result register if it is used as input in the following instruction.
This really spoils a large part of what dynamic recompilation is about, but still seen quite often in "real world" examples.

There are two different methods of allocating registers:

Static register allocation: This means that in every translated block the same emulated registers are always allocated to the same host registers. When the host machine has enough registers to hold all emulated registers this is the optimal solution, but there are also some advantages even if it has fewer registers (mainly related to timing and translation block handling; I'll cover that later). In the latter case this means that only some of the emulated registers are held in host registers (ideally the most often used ones) and for the remaining ones the register file is accessed.

Dynamic register allocation: In every translation block the registers are allocated differently. Ideally you load the values of the emulated registers into the host registers at the beginning of the block and store those that were modified back to the register file before the block returns control to the dispatcher loop. If there aren't enough registers to hold all registers used in the block you'll have store the value held in a host register to free it for the next one.

Implementation wise static register allocation is rather easy, because you always use the same host registers to hold specific emulated registers and access the memory locations in the register file for all the others. This also means that you always load the same register values and store them to the same memory locations afterwards no matter what translated code block you are executing. So you only need one setup/clean-up code for all blocks which is occasionally called glue code because it's the thing that connects the emulator and the generated code.

The implementation of dynamic register allocation is a bit more complicated though. First of all there is more bookkeeping to do, since the emulator has to remember these facts:

• which host register holds which emulated register: you need to know if the register is already in use and where to store the value to if you need to free the register
• which emulated register is held in which host register: this tells you if the register is already allocated, and if it is you know which register to use in the generated code
• has the value held in the host register been modified? This isn't really necessary, but it's a good idea not to store a value to the register file that hasn't been changed since you spare another unnecessary memory access.

How does register replacement work when you run out of registers?
There are very many methods that could be applied, and probably only one would be ideal, which basically means that you replace that register which isn't needed in that block anymore. Since you do have the entire block you could actually go through it backwards to find out if there is a register the code doesn't use anymore, but that can be a bit tedious.
That ideal solution reminded me of the best but theoretical solution for a page replacement algorithm in operating systems, so I came up with the idea of using another page replacement algorithm called second chance, which is similar to LRU (least recently used) but simpler to implement.
For that algorithm you set a reference flag for the host register every time it is referenced during code generation. When you need a register you go through all host registers in a circle (using a modulo operation with the maximal number of host registers), pick the next register register where the reference flag isn't set, while unsetting the reference flag of all registers you have to skip. Probably sounds a bit weird, but it's easy to implement and should lead to good results.
Of course if you come up with an easy implementation of the optimal solution that would be perfect.

I guess that's the most important things about register allocation...
If you want to know how to handle 64-bit registers on the IA-32 then take a look at the 1964 documentation (http://e64.wwemu.com/emus/1964/1964_recompiler_doc_101.pdf).

Translation Caching

Our next topic is the translation cache. But I won't go into detail how the generated code blocks are actually stored and freed, since I haven't given it too much thought yet. Although it is most likely that it's a good idea to allocate a large block of memory via the operating system and then make your own arena managament in that chunk for performance reasons.

The most interesting thing is how to remember which block is already translated and how to do that fast.
For 8-bit processors which normally have a 16-bit address range it would be easy to simply make an array of addresses and mark each single address when it is the start address of a recompiled block. But for those processors where dynamic recompilation is really interesting, this simple approach does not work, even if you take into account that most of the processors only permit aligned instructions. So other, less memory consuming methods have to be found.

When you come straight from computer science studies the most obvious solution would be a hash. That means a value is mapped through a special hash function (often containing a modulo operation to define the confines) onto a much smaller range array. The advantage is that in the best case you only perform the simply function and get the key to the memory location where you find the address of the recompiled code with one memory access (or a zero if it hasn't been recompiled yet). The problem is that the hash function is likely to generate the same key for different values, which happens more often when the hash array is too small and/or the hash function isn't that good. When this happens you get a so-called collision, which has to be solved somehow. The typical solution is to do a linked list of all values that collided, but that means that you need several lookups since you'll have to search the list in linear order until you find what you want.
So hashing is a possible solution, but not necessarily the best one.

Another problem that might have to be solved during the translation cache lookup is to detect self-modifying code. If the code behaves nicely you can skip that, but if self-modifying code occurs from time to time you'll have to detect it.
The typical computer science solution would likely be to run some kind of checksum (eg. CRC) over the original code, and regenerate the checksum every time the block is about to be executed. If the checksum has changed the block has to be translated again.
The problem here is that checksums can be fooled when several values (in the case instruction encodings) change but the change is not visable in the checksum. Also recalculating the checksum before every run of the code should hit on performance hard.

Since traditional solutions aren't perfect let's see what alternatives there are...

A drity trick that UltraHLE is said to be using works as follows:
Instead of using a data structure to memorize which blocks have been translated, the first instruction of the block is replaced by an illegal instruction that also contains the offset to the generated code - since MIPS has 32-bit instructions that's quite possible. So the emulator just takes a look at the start of the block to recognize if it has been translated already or if it has to be translated still. A side-effect is that code that modifies the first instruction of the block leads to the block being translated again automatically.
The disadvantage is that self-modifying code is only detected when the illegal instruction is replaced, and since you modify the original code you might run into problems when that block is actually just a sub-block of a larger block that might run into that illegal instruction. This could be handled of course, when the original instruction is stored somewhere, but it makes things a bit more complicated.

The elegant solution would be a paged translation map. When you don't know what to do in emulation, it often helps to take a look at how the hardware does things.
Most of the processors that are interesting candidates for dynamic recompilation organize their memory in pages, ie. the higher part of the address is the page number and the lower part is the page offset. The typical page size is 4K, which means that in a 32-bit address space you'd have 20-bit for the page number and 12-bit for the page offset. Even if you want to keep track of all possible pages (which isn't normally necessary) you'd need 1MB (= 20-bit address range) x 4 byte (size of an address on a 32-bit system) = 4MB, which might sound like much but actually keeps track of all pages in a 4GB address range. Now you still need 4KB x 4 byte = 16KB per page to have all the addresses, but you only need to keep track of pages that actually contain code, so that's far less than you might assume, and when you have a processor like MIPS where all instructions have to be aligned to 32-bit (ie. the start address of each instruction has the lower two bits cleared) it's only 4K.
When the emulation jumps to a certain address you first look at the page (by shifting the address right by 12 bit) to see if code in tat page has already been translated. If there is no translated code yet you allocate a new memory location that is large enough to hold all addresses for that page, enter a pointer to that area in the page number entry, and finally enter the address to the translated code in the location of the page offset at which the original code block starts.
The lookup needs just two memory accesses, one to find the find the location of the page directory via the page number and another to look up the address of the translated code via the page offset in the page directory.
I hope this doesn't sound too complicated, because it really isn't...

The paged transmap also allows for a solution to identify self-modifying code. Every time a write access is performed it is checked if the page number for that access indicates that code on that page has been translated, the cached code for that page is freed and the address in the page number entry cleared to force a recompilation of the code. This might sound crude, but in paged environments data and code are normally on different pages, so it is really likely that the code has been modified.

Since I was talking about Harvard architectures (ie. split integer and data caches) before, there is another way to detact self-modifying code in that case. Since those architectures have to flush their caches you can try to trace that (either some system call or the processor operation) and free the appropriate code that is no longer valid. According to an article (http://devworld.apple.com/technotes/pt/pt_39.html) the official 68K emulator for PowerMacs uses that solution.

Direct Translation

Using direct translation the code block is processed linearly and each instruction is translated separately. Often the code that generates the translation is placed directly after the decoding of the instruction, ie. the instruction decode look very much like the one from an interpretive emulator, with the exception that machine code is generated instead of the instruction being simulated.

The advantage of that method is that you can simply transform an interpretive emulator into a dynamic recompilator.

But there are many disadavtages.
First of all, optimizing the code is very hard because you could only reasonable do a one or two instruction lookahead to test if the current instruction could be combined with the following ones for a better translation.
Retargetting the dynarec to a different host processor can be quite tedious, since you'll have to go through the whole decoder loop, which should actually be portable.

Unfortunately I see code like that much too often in real-world examples.

The VIP Desaster

Once I past the direct translation stage - I was heading in that direction and I didn't like it, which was one of the reasons why I stalled my dynarec and started research again - I thought of making the dynamic recompiler more portable.

Wouldn't it be cool to have some virtual intermediate processor (VIP, ie. the original code is translated to VIP "instructions", which are then translated to target instructions) and enable dynamic recompilation between a whole lot processors without too many translators (just two per processor, one that translates to VIP while the other translates from VIP)?

I thought so, and since I didn't know of the failed UNCOL project (they tried to define some kind of universal machine language and it didn't work out, but I guess I wouldn't have cared anyway) I started analyzing maybed dozens of processor architectures, and after several months I knew much more about several architectures, but I gave up on the VIP idea.

It is true that basically all that processors do is calculate, but there are surprisingly many differences...
Just take the number of logical instructions, where some architectures have just the standard ones while others have a whole lot combinations. Or the fact that some architectures handle the carry flag differently during subtraction (ie. they borrow) while others don't have any flags at all.
The biggest difference so probably the division, where some architectures also calculate the remainder, others have a separate instruction to calculate the reminder, and some require you to calculate the reminder via multiplication. Also some architectures produce results only on special registers, do division steps (ie. only calculate a certain amount of bits of the result per instruction), or don't have a division instruction at all.
If you also add strange instuctions like the "add and branch" from PA-RISC you get a whole lot of different instructions.

With the VIP there would be two extremes, either you end up having all possible instructions from all architectures you know (and there will be stil many you don't know), or you make it very simple and compose translations for more complex instructions with a sequence of VIP instructions. Either way it's bad:
When you make the VIP too complex porting will be very tedious since you'd have to provide translations for hundreds and hundreds VIP instructions for each new host processor and no one will want to do that, which nullifies the whole idea behind using the VIP in the first place.
If you make it simple, then it will be a charm to port, but the quality of the target code will be very bad, as it is very hard to optimize code, when even very simple original instructions end up as being a long sequence in VIP, eg. since many processors have different condition flags and some don't have any those couldn't be handled in a simple VIP, and you'd have to translate these into separate VIP instructions, which could transform a very simple ADD instruction into a long VIP sequence.
Finding a compromise between these extremes will be very hard and most likely result in narrowing the number of supported architectures, which again ruins the idea of using a VIP.

So that isn't really a good idea either...

Decoder-Translator-Abstraction

Ok, since the first two approaches to translation aren't that recommended, what else could be done?
In my opinion, the translator should make it easy to optimize translations and should be not too closely linked to the instruction decode to make porting easier.

The best solution is probably to generate a block decode structure, ie. as the instructions of a block are decoded the decode information is added to a structure (you might even add some additional information about register and flag use), which is then handed to the translator that is a totally different module.

This method is relatively fast, since you don't do several translations as with the VIP and lookaheads are much easier in pre-decoded block structure than in direct translation, which also leads to peephole-optimization being much easier.

You still have to write a special translator for each host system, but since the translator is a separate module that communicates with the decoder via a data structure porting is a much cleaner process. Not to mention that you are able to do very specific optimization, which probably would not be possible if you were using a stronger abstraction.

Code Generation

After some days without new information I think I should talk a little about code generation, since I don't want to dive into the platform specific translations yet.

One possiblity that is used by a few dynarecs are preassembled routines, ie. the covers (the code that represents a certain operation, in our case an instruction of the original code) are written in assembly (althought I know at least one example where they are hacked in hex code) and translated during the compilation of the emulator.
Those covers contain only placeholders where register references, addresses, or immediate values should be. After the whole cover has been copied to the target memory location the placeholders have to be patched with the appropriate values. Due to this fact the range of possible instruction formats is somewhat limited unless you want to make the whole process too complicated.
Obviously this method isn't that flexible and also won't lead to optimized code, as you have to translate each instruction all by itself instead of being able to combine two or three instructions to make a faster semantic translation of the code sequence.

Other methods typically use code emitter functions for covers. Those functions directly write exacutable instructions to a memory location. The difference here is how readable the code is. Often it's like this:
Some readers might recognize the ARM example code I was using for the demonstration of the dynamic function call. I only changed it to show how values like the immediate #1 in the ADD instruction tend to be added to such code.
Of course this is already more flexible than preassembled code, but it isn't very readable and even harder to edit. Mind you that you won't even find the comments that tell you which instruction is generated in some example dynarecs I found.

To improve the last method you should use either functions or macros to make the code emitters more readable and also easier to use, which might look like this in the end:
With a few dozen code emitters like these you should be able to program and edit covers quite easily after some practice, and it is clear what they do even without the comments.

This is probably one of the last basics I can explain without using too much assembly. So are there any things you don't understand fully yet and that should be better explained before I continue?

What I have left now are topics about timing issues, specific translation problems, and code optimization, but those are very specific in most cases and maybe not that interesting for most. After that I'll probably have to pass or just answer questions, because I don't really have too much knowlegde of more in-depth stuff to continue. I didn't plan to fully explain a dynamic recompiler anyway