Peeking behind the curtain

What's new

I have just uploaded a small update again to the Subversion repository. In this update you can find the following changes:

• Implementation of all form of the following addressing modes for both as source and as destination addressing:
• immediate long, word, byte;
• indirect addressing: (Ax);
• indirect addressing with pre-decrement: -(Ax);
• indirect addressing with post-increment: (Ax)+;
• Implementation of instructions:
• MOVE.x #imm,Dy;
• MOVEA.x #imm,Ay;
• MOVEQ #imm,Rx;
• MOVE.x Rx,Ry
• Code was refactored to avoid repetition of the same code chunks in the addressing modes and instructions.
• Implementation dumping the compiled code to the console.
• New configuration (comp_log_compiled) is also added to turn it on/off.

Featuring...

It is always exciting to find out some magic details about the internal behavior of a complex system. I remember when I realized for the first time how the texts are stored in the Commodore Plus/4 games, back in the days. I was amazed how I can change the text that showed up on the bottom scroll of Tycoon Tex.

Let me offer some small excitement to you all: I just implemented a funny little feature in the E-UAE JIT engine. Now we can turn on dumping the compiled code to the console, together with the original Motorola 68k instruction that was compiled and the macroblocks that describe the intermediate translation form.

The purpose of this feature wasn’t (purely) the entertainment, but I was really fed up with the situation that the generated code cannot be debugged properly. Previously, I added a trap instruction (tw) into the translated code at some point, so I was able to have a look on the output from the Grim Reaper window (which was awesome, but let’s not mix it up with actual debugging).

Too bad that GDB is so limited: it cannot debug into any code segment that wasn’t loaded by DOS (like generated code). Not to mention how cumbersome the console interface is... (Or am I missing something? Enlight me please.)

I would like to thank Frank Wille the sources for the PowerPC disassembler that makes it possible to list the translated code.

How to turn on this feature: there are two settings that control the logging. These are:

• comp_log – if it was set to “true” or “yes” then the JIT logging is turned on and dumped to the standard output.
• comp_log_compiled – if it was set to “true” or “yes” then the compiled code is listed through the JIT logs.

Let’s see a small demonstration of this feature, shall we? (Not for the faint-hearted!)

The following list is the output from the very simple test code: iamalive.asm, slightly edited and formatted for educational purposes...

1. M68k: ADD.L #$00000001,D1
1. Mblk: load_memory_long
   Dism: lwz r15,64(r14)
   Mblk: load_memory_long
   Dism: lwz r3,68(r14)
   Mblk: rotate_and_copy_bits
   Dism: rlwimi r15,r3,16,26,26
   
2. Mblk: load_memory_long
   Dism: lwz r3,4(r14)
   
3. Mblk: load_register_long
   Dism: li r4,1
   
4. Mblk: add_with_flags
   Dism: addco. r3,r3,r4
   
5. Mblk: copy_nzcv_flags_to_register
   Dism: mcrxr cr2
   Dism: mfcr r15
   Mblk: rotate_and_copy_bits
   Dism: rlwimi r15,r15,16,26,26
   
2. M68k: MOVE.W D1,(A0,$0180) == $00dff180
1. Mblk: load_memory_long
   Dism: lwz r4,32(r14)
   
2. Mblk: add_register_imm
   Dism: addi r5,r4,384
   
3. Mblk: check_word_register
   Dism: extsh. r0,r3
   Mblk: copy_nz_flags_to_register
   Dism: mfcr r6
   Mblk: rotate_and_copy_bits
   Dism: rlwimi r15,r6,0,0,2
   Mblk: rotate_and_mask_bits
   Dism: rlwinm r15,r15,0,11,8
   
4. Mblk: save_memory_long
   Dism: stw r3,4(r14)
   
5. Mblk: save_memory_spec
   Dism: mr r4,r3
   Dism: mr r3,r5
   Dism: rlwinm r0,r3,18,14,29
   Dism: lis r5,27315
   Dism: ori r5,r5,23016
   Dism: lwzx r5,r5,r0
   Dism: lwz r5,16(r5)
   Dism: mtlr r5
   Dism: blrl
   
3. M68k: BT.B #$fffffff8 == 0000001a (TRUE)
1. Mblk: save_memory_long
   Dism: stw r15,64(r14)
   Mblk: save_memory_word
   Dism: sth r15,68(r14)
   
2. Mblk: load_register_long
   Dism: lis r3,27606
   Dism: ori r3,r3,45096
   Mblk: save_memory_long
   Dism: stw r3,76(r14)
   
3. Mblk: opcode_unsupported
   Dism: li r3,24824
   Dism: lis r4,27315
   Dism: ori r4,r4,21752
   Dism: bl 0x7f91acc0
   
   
4. Done compiling

Colorful, isn't it? :)

Okay, let's try to understand what is going on.

I marked the three Motorola 68k instruction that was compiled here with orange color, the code roughly looks like this:

1. Increase register D0 by one;

2. Put the content of register D0 to the address that is calculated by using register A0 plus offset of 0x180 (A0 was initialized previously with the value: 0xDFF000, which is the base of the custom chipset memory area) - in layman terms: load it to the background color.

3. Go back to step 1.

Now, let's see the second level of the list:

First of all the prefix "Mblk:" marks the macroblocks (white), "Dism:" is the actual PowerPC code (yellow).

As I already mentioned earlier: some macroblocks can be optimized away (although it is not implemented yet), and a macroblock means at least one PowerPC instruction, but it can be a series of instructions also.

The steps can be interpreted roughly as:

1.1. Load the arithmetic flags from the memory where the interpretive emulator stores them.

1.2. Load the previous content of the emulated D0 register into a PPC register.

1.3. Load the constant for the add instruction (one) into a PPC register.

1.4. Add the second register to the first one (increase D0 by one).

1.5. Save the arithmetic flags after the operation.

2.1. Load the previous content of the emulated A0 register into a PPC register.

2.2. Add the offset (0x180) to the content of A0 and load it into a new PPC register.

2.3. Check the content of the emulated D0 register to set up the arithmetic flags according to it.

2.4. Save back the modified D0 register to the memory for the interpretive emulator.

2.5. Calculate the offset and load the function address for the memory write operation handler and call it (namely the custom chipset write handler). This is a function from the interpretive emulation and it was written in C, therefore we must store all volatile registers back to the memory, the C code won't preserve these. (This is why we stored the D0 register in step 2.4.)

3.1. Save the arithmetic flags back to memory where the interpretive emulator stores them. (These were kept in a non-volatile register, so these were preserved while we called the helper function in step 2.5.)

3.2. Update the emulated PC register to the current state for the following instructions.

3.3. Call the interpretive emulation for the branch instruction (because it is not implemented yet, so we reuse the interpretive implementation).

4. Done. Phew.

Funny, eh? :)

If you are not familiar with assmebly then don't stretch yourself too much by trying to understand this techno-blahblah.

For the rest: who can spot what can be optimized on the compiled code?

Foundations of the House

To show some progress I checked in a massive changeset into the SourceForge SVN that represents the implementation of the following features:

• Macroblock collection and handling
• Code generation from the macroblock buffer
• Macroblocks for many basic high level instructions that are used for the code translation intermediate representation
• Temporary register allocation/freeing, flushing
• Emulated 68k register mapping to temporary registers, automatic loading/saving from/to the interpretive emulator Regs structure
• Compiling of pre- and post-code for the translated block
• Temporary PPC register, emulated M68k register and flag flow-tracking for macroblocks
• Basic functions for flag emulation implementation

Sounds quite a big chunk of work, and to tell you the truth it really was. As it seems so far my initial plans are working, the macroblocks are the implementation of the Microcode-VLIW-like approach I explained previously.

What is still missing for your happiness: there is no addressing mode and instruction implementation yet. So, basically this is still not too useful for the average users, thus there is no binary release yet.

But all of these are the foundations of the house and now I can go on with building the walls, which will be much more perceptive: addressing modes and instructions.

Unfortunately, I wasn't able to find the bug that blocks the Kickstart from running, maybe an other Kickstart file might help, we will see.

In the meanwhile enjoy this beautiful diagram of the (oversimplified) method of compiling in this implementation:

Code translation flow diagram

Blueprints

It is time to celebrate: finally my Amiga configuration is complete. It took more than a half year after moving to the opposite side of the globe (from Hungary to New Zealand). I dragged my poor, old A1-XE with me in a suitcase; unfortunately it didn't survive the flight. :(

Stephen “Cobra” Fellner lent a uA1 to me in a compact case, I couldn't be grateful enough for it. (Not to mention the tons of helps they gave us to start our new life here from scratch...)

Piece-by-piece the machine was completed; the final item was an old Philips monitor from TradeMe.

It is also time to reorganize priorities in my (rather limited) free time. Cut back on beaches, bushwalks and especially on Facebook. :P

But enough from whining, this is a technical blog after all and the autumn is coming rapidly with lotsa rain...

Let's scheme!

A JIT compiler similar to a programming language compiler, the main difference is the source: while a programming language source is human readable text (or that would be the goal, at least), the source in this case is machine code from a different processor.

The upside is the machine code has very strict rules, easier to interpret. The downside is it must be precisely known in every minor detail and there are undocumented features and side-effects that have to be implemented correctly. (How to find out these: good question; usually with countless hours of debugging crashing applications.)

Why JIT called just-in-time compiling: the program code translated to natively executable code while it is emulated. It means every time the execution reaches a point in the program that wasn’t reached before then the compiler takes a chunk from the emulated code and translates it to native code then the execution flow goes on. (Some JIT compilers are able to translate the whole executable right after loading, but that is only possible in special cases.)

The compilation process can be either fairly simple or overly complicated, depending on the actual method. The final result must be directly executable on the host system; in other case it would be inefficient and probably useless. (It would require an interpreter to execute, rarely makes any sense.)

There are different approaches to the compilation process, which one is the best choice depends on multiple factors.

Poor man’s JIT

For example the most simplistic method produces a series of jump instructions for execution of source data fetching, operation execution, result store. Everything else is done by a library of functions in the emulation environment. This solution gets rid of the interpretation of every instruction code at every (re-)execution, but it is next to impossible to do any optimization which would involve the source- and destination handling together with the operation; not to mention a wider span of instructions.

Why anybody would try such an inefficient solution: if the interpreter is already implemented then requires significantly less work to turn it into a JIT compiler by this way. Also the translated code needs (lots of) memory, such implementation is lightweight on the memory usage.

Stamping Lil’ Roses and Rainbows

Slightly better approach is creating templates for certain addressing modes and operations that can be copied into the translated code (almost) directly. Not every instruction incarnation needs its own template; it is possible filling up some gaps regarding the specifics to the actual instruction, such as the involved registers.

This is the most common approach, flexible and efficient, if implemented properly. With some tweaking it is even possible to adjust the templates to handle special cases, such as optimizing arithmetic flag emulation away when consecutive instructions would overwrite it anyway. This is how Petunia works and as I found out recently, something similar that WinUAE implements.

However, templates are a bit rigid sometimes and still not to easy (or even impossible) to join together more, than two instructions in a specific optimization, which would make use of certain aspect of the target processor. Creating truly flexible templates could result a big mess in translation functions.

Big Planz I haz it

I had a couple years after finishing (the never-ever finished) Petunia playing around with scenarios in my mind where emulated code builds up this or that way. Finally, I came to the conclusion that there is a possible better way to implement JIT compiling, and that is similar to the microcode, that used often in CISC processors.

Microcode is for reducing the complexity of the machine code instruction by implementing it as a series of very simple “wired” instructions and an “interpreter” executes the simple instructions one-by-one at each clock cycle.

Combining this technique with the VLIW approach, when the simple instructions are executed out-of-order, or even can be eliminated completely the result might be lot more optimal on the generated code.

How do I intend to implement… Similarly to the templates, each emulated instruction will be prepared as a series of virtual instructions. The compiler in the first round collects the virtual instructions for each emulated instructions into a buffer for a defined chunk of the emulated code.

In the second round an optimizer runs trough the buffer while trying to apply modifications on the virtual instructions according to predefined rules. At this level the virtual instructions and the original (emulated) instructions have no connection at all anymore, each virtual instruction can be handled, reorganized, eliminated on its own.

The third round is the code emitter: turns the virtual instructions into natively executable code using actual code templates.

I am sure it wasn’t me who thought on this solution for the first time, but never read about similar approach before in the case of the JIT compiling. Programming language compilers do similar code translation to maintain the portability of the compiler between the different processor architectures. (Code emitter has to be adapted, the rest of the compiler needs no modification.)

Predicted Roadblocks

Once I heard: if you were not able to summarize the problem then you won't be able to find the solution either. Let's find out the possible problems with JIT compiling for the complete machine emulation then.

1. Memory access emulation

Unless the 68k emulation in OS4 the UAE is a complete machine emulation. While an application is running it reads and writes memory (no news to anybody, I guess). If the accessed memory is plain data then there is not much to do with it: the application can do whatever it was planned for.

Unfortunately there are two types of memory access that needs special care: accessing hardware registers and writing into the executed code area. For the latter see below at self-modifying code, the former is lot more easily to handle.

Solution: basically what needed is incorporate the functions from UAE that are called for each memory accesses into the translated code.

2. Self-modifying code

The 68k processors don't make difference between data and code, although the AmigaOS itself is able to recognize what part of the loaded executable contains actual code. The difference was never enforced to the developers with all of its up- and downsides, they found it out by the hard way what can of worms is hidden there, when the processors with cache (like 68020) appeared in Amigas. Several self-modifying game and demo fails running on the cached code memory, because the code cache and the data cache is separated.

In AmigaOS4 I was able to get information from DOS.library regarding the loaded and removed code segments. By using this information I could tell which memory areas are cleared, I simply dropped the translated code for those.

With UAE the situation is completely different: any byte in the memory is potential target for modifying. It means the translated code must be dropped and retranslated; otherwise it would conserve the previously translated state.

Solution: probably I must extend the memory access checking and drop the translated code when it gets modified. I have to revisit this topic later on; checking for translated code at every memory access might be too slow.

3. Translated code lookup

When the execution jumps, branches to a new memory address the emulator has to know whether there is an already translated code or the new address was never hit before, new translation is needed. The translated parts are sometimes following each other, but often the programs are wondering around in the memory with no logic to follow.

Solution: Petunia had the same problem, I created a two level look-up table for the translated code segments for each address in the address space; a bit memory-hungry, but very quick for finding the address of the translated code.

As Michael Jackson would say: This is it. These are the initial plans, more details must follow, but first thing first: let’s try to compile E-UAE… :)