After another bump on the bumpy road

I have spent some time fixing bugs and improving the performance of the compiled code and the JIT emulation overall. As a result here is the recent update:

• Implementation of TST.x mem, NOT.x Dy, EXT.x Dy
• Reverted the change for stopping the compiled block when the special flag is set. This change is not needed for the Kickstart and it doesn't seem to have any effect, but slows down the compiled code.
• Removed hack for MOVE.z Ax,-(Ax) and MOVE.z Ax,(Ax)+ instruction implementations.
• Fixed pre-decrement and post-increment addressing modes for destination. Re-enabled MOVE.x mem,mem and EOR.x reg,mem instructions, which were disabled previously to let the Kickstart running without the addressing mode fixes.
• Fixed register dependency in some memory addressing modes.
• Temporarily removed checking for the tiny blocks, ignoring these blocks is just not the right solution for avoiding the overhead of block calling.
• Added ignoring blocks of pure unsupported instructions: these will be executed by the interpretive emulation.
• Fixed blocking of small blocks, the block was not raised in the cache list.

Lots of small changes and fixes as you can see.

Probably, the most important fix was the one for the pre-decrement and post-increment addressing modes, this was blocking the Kickstart for a while from booting and this is why I had to remove the support of those two instructions I mentioned in the changes list.
As it turned out the root of this bug was a limitation of the implementation. Each addressing mode has two compiler function: one is called before the instruction compiling, one is called after that. But the situation is not always that simple, for example in this case:

MOVE.L (A7),-(A7)

This is a common instruction for copying the memory to a lower address (like moving the content of an array one step toward the beginning, in this case the content of the stack). Seems so innocent, isn't it? :)
Why this one was an issue: the handler for the destination address is called before the instruction and since it is a destination addressing mode it decremented the address in the emulated A7 register. But then the instruction was compiled, which used the address from the A7 register as a source. So, what actually happened was something like this:

MOVE.L -(A7),(A7)

Now you can see: this operation is (mostly) pointless, it copies the data from the one address to the same address. (Although, sometimes it might make sense in the communication with the hardware, but this wasn't the case right now, obviously.)

What was the fix? Pretty simple: I moved the destination address modification to the address handler which is executed after the instruction was compiled. This was a solution for this specific case, but I also had to make sure that all the other combinations are working which might be possible with the indirect addressing. One of the trickiest was:

MOVE.L (Ax)+,(Ax)

You can try to guess why. :)

Anyway, finally this bug is out of the way and I can go on with implementing the missing instructions. Some of them are done, but yet lots to go.

There was one more important change in this update: I removed the limit for the consecutive block length when a special condition was triggered by some instruction. I found it completely pointless, everything seems to be working without this condition. There was a bad side-effect of this limit: after an instruction triggered a special condition for the emulation all the following instructions are compiled one-by-one into separate blocks. The overhead for calling these tiny blocks was huge, this is why I introduced the rule of ignoring any block which was smaller than 3 instructions. But in this case lots of the code was not JIT compiled at all. (As some of you guys mentioned: the JIT LED was mostly dark - lots of blocks were not compiled.) This is fixed now, although I am a bit afraid of the side-effect of delaying the handling of the special conditions. We will see how it goes.

I also spent some time on updating my old tool: DiskDaisy. The recent updates for AmigaOS4.1 triggered a bug in that app. Sometimes it is nice doing something completely different for a while, you know. :)

:dancing banana: (sort of)

After more than four months of chasing my own tail on this problem, I had managed to fix up the JIT compiling to let the Kickstart boot using compiled code. (See disclaimer below...)

*Phew*, there were times when I thought I am not going to write this down ever in the blog. I was this >> << close to give it up on some days. Since the world hasn't ended in 2012, I realized I have to go on, there is no escape.

I am proud to announce: the project stepped into Alpha stage on SourceForge with this update. Details of the changes are:

For the Kickstart boot these fixes were needed:

• Added compiling stop (jump) flag to instructions which might trigger interrupt for supervisor mode: OR.W #imm,SR, AND.W #imm,SR, EOR.W #imm,SR
• Temporary registers are flushed at the end of the compiling cycle, but before the code generation.
• Stop the block processing when the special flags were set in the block (an interrupt might be triggered).
• Reload the emulated program counter register when the block finishes with a supported instruction.
• Fixed wrong function epilog implementation: the return address was read from the wrong position in the stack.
• Old executed instruction pointer and emulated PC register is synchronized on PC reload.

Other fixes for the bugs I have discovered while I extensively debugged the emulation:

• Fixed missing releasing of the compiling buffer on quitting the emulator (memory leak).
• Prevent compiling of tiny blocks (less than 4 instructions in a row): the overhead of the block calling is too much.
• Fixed compiling buffer overflow checking and misleading help text for the compiling buffer unit size.
• Removed supported status for not-yet-implemented EOR.x reg,mem instruction, which was added accidentally before.

(Disclaimer) Before all of you rejoice in dancing banana overload on the user portal of your choice, there is a catch: the Kickstart is not able to start up with JIT compiled instructions, only if the original interpretive instructions are called one-by-one from the compiled code.
So, there is no practical use of the sources yet, but this was the big question: is the compiled code handling able to deal with something as complex as the Kickstart? And for a long time the answer was: no.

Some über-geeky details about the fixes (you like when I'm talking dirty, right?):

As you can see from the changes there were numerous problems around the code, all of these changes were needed for the final result. There were the usual ridiculous issues like a missing negative sign in the function Epilog (line 2308) when it tried to read back the return address from the stack - from the wrong offset.
It essentially means that the execution returned from every compiled block to the parent function instead of the block call loop. The funny familiar feeling that every coder experiences sooner or later: how on EARTH this thing ever worked? ;)

The trickiest part was finding the bug about the interrupt handling: I waded through a few hundred gigabytes of debug dump following the execution. Unfortunately, I was not able to compare the different execution sessions as I mentioned earlier in the comments for the previous post.

At last, I have found out that the OS is switching between User and Supervisor mode in the Exec.lib/Supervisor() function using the special OR immediate instruction by flipping the S flag in the Status Register. This step triggers an exception which is captured by the OS and the position of the triggering instruction identified in the ROM exactly.
The bug was: I never considered this OR instruction to be similar to a TRAP or an ILLEGAL instruction, which instructions change the Program Counter by raising an exception - which is essentially a jump. Thus the compiling hadn't stopped to give back the execution to the interpretive emulation.
As a result the compiled block contained the next instruction after the OR consecutively and later the exception was triggered separately: train-wrecking the boot completely. The only way to get out of there for the OS was to reboot, this is how the reboot-loop happened.

Promises?
Now, it gets a lot easier to fix up the different instruction implementations and implement the rest of the missing instructions. As soon as the former is done the OS will be usable and the latter can be done gradually.

I would like to thank to Toni Wilen for his hints regarding the possible ways of tracking down bugs inside UAE. His suggestions gave me ideas which eventually led to the required fixes.

Yet lot more work should be done, but at least I can see the light at the end of the tunnel. (What a cliché, man. Put yourself together!)

And finally, here is a picture of me, made by my wife to capture the moment when the freakin’ thing started up for the very first time:

OMG, who is this ork-face?

See you all soon(ish) – my holiday is over tomorrow (#sadface).

Optimize It

I am back from the holidays for sometime now, but I got swamped instantly by the work in my daytime job. I had very little energy on the project in the nights, which was spent on two things: chasing that #@!% bug which is killing me and implementing the data-flow optimization.

Needless to say that I failed to track down the bug again, just like every time I spent hours on looking at couple megabytes of log dumps. Next time I will try a new approach, suggested by Stephen Fellner: reducing the code complexity while the bug can be reproduced.
We will see how it goes. The processor cache emulation is certainly complicates things, that can be eliminated at least.

While I acknowledged the failure again, I gathered all my previous thoughts and implemented the data-flow based optimization which does a really nice job.

The update is small, but highly important again:

• Implementation of code optimization.
• New configuration was introduced: comp_optimize to turn it on/off.
• Bugs in the register input/output flag specifications are fixed.
• Fixed too small string buffer in the 68k disassembler, previously the debugger crashed every time when memory was disassembled to the screen.
• Implementation of MOVEM.x regs,-(Ay)

What, how and why?

As I tried to explain earlier in this post some of the compiled code is completely useless. The emulated instruction consists of the following parts usually:

• Initialization of certain temporary registers;
• Executing the actual operation;
• Alter the arithmetic flags according to the result;
• Save the result somewhere (into memory)

Some of these operations are not common or can be done for a series of instructions ahead, like loading the previous data for the emulated registers into temporary registers, but there are parts that cannot be avoided if we examine the emulated instruction out of its context.

For example the arithmetic flags are overwritten quite often by the following instructions, what means: if the next instruction(s) are not depending directly on the flag results then we can remove the code that generates these.

Typically, if we (as mighty humans) look at the instructions in a block we can easily identify the context, we can tell mostly which instructions produce usable results and what is not important. Like in most of the cases simple for a human, but it is a really complex job for the code compiler.

As I previously described: the emulated code is broken up into macroblocks by the precompiling. These blocks represent an "atomic" operation, like load data into temporary register, compare two registers or calculate certain arithmetic flags from the previous result.
When I started working on this concept I figured out that if I would be able to identify exactly for each macroblocks the previous result(s) that it is depending on and the result(s) that it produces then I can evaluate the dependencies between the subsequent macroblocks.

Going with the flow

For Petunia I already implemented a similar concept, but that was limited to the flag usage and it is not able to split up the emulation of the arithmetic flags into individual flag registers: it is either emulated completely or removed completely. (Which means that even if we needed only the C register later the rarely used X register will be calculated too, usually after the C register was already done. If you don't understand the reason behind this: don't worry - you need to know more about 68k assembly.)

For E-UAE the implementation is radically different. For any macroblock there is the possibility of specifying each and every emulated register, flag or temporary register as dependecy (input) and/or as result (output).

In the recent changes I implemented the rather simple solution for calculating the data-flow for each registers after all macroblocks are collected for a block of instructions.

It is capable of finding out for each macroblock whether the produced results are relevant for the following instructions in the block or not. If not then that macroblock can be eliminated from the compiled code because no instruction is depending on its results.

 

How to use it

Although, the optimization is completely safe (it won't remove any code that is essential) while the emulation is not stable enough there might be some bugs. So, I introduced a new configuration for turning it on/off, called: comp_optimize.
It replaces the comp_nf configuration from the x86 JIT implementation, because it is not just about the flags (nf = no flags).

If it was set to true then the data-flow calculation is done and some macroblocks will be removed. By setting it to false the emulation compiles all the instructions fully into the buffer.

 

The results

And finally some speed tests... Compared to the previously published Mandelbrot test results the actual numbers are:

Interpretive: 108 seconds;
JIT compiled without optimization: 52 seconds;
JIT compiled with optimization: 32 seconds.

That is roughly 40% speed increase in the case of this (heavily arithmetic) test.

The test system was: Micro AmigaOne (G3/800 MHz) - let's compare it to WinUAE that is running on my laptop (Intel Core i3 M350/2.27 GHz):

JIT compiled with all the possible optimizations turned on: 9 seconds.

It would be a tough job to compare these two computers, but I am pretty sure that my laptop is more than 3.5x faster than that poor old G3 machine.

I am really content with these results for now.

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

The Big X on the Map

Just a very quick update: things are slowly evolving, so DON'T PANIC.

Some more words about what has happened recently: I had some trouble with my Amiga, turned out as a PSU problem. Luckily it is already fixed with a "new" case for the poor girl.

I am fighting with the rather chaotic E-UAE sources, so I made a few steps to make it easier to edit the whole project: I managed to put together a cross-compiling environment from Windows. *booo-booo*

Compiling is much faster on the muscle x86 processor (*booo-booo*) and there are some advanced tools to do some heavy lifting when it comes to source code editing. I must also admit that since I use source version control at work, I barely can go on without it.

With the help of Cygwin, Eclipse CDT, TortoiseSVN, VisualSVN Server, FileZilla Server and a simple script on the Amiga side I was able to assemble a semi-automatic build and test deployment environment.

Thanks to Zerohero for the detailed cross-compiling setup description.

Rainy Day with Copper-rendered Rainbows

The sky is cloudy, sometimes sudden showers are soaking the insanely green grass and I am forced into the shabby unit we rented half a year ago. Time to move - popping into my mind quite often these days, but that is a completely different matter.

There are only a few things distracting me from working on E-UAE, I tried to concentrate working on it with a great strength. (Apage Satanas: Facebook! I clearly miss the times when I was developing Flamingo. I was sitting in my curtained flat all day, no internet, no phone, no tv: the best environment for creating your own little pet creature and take over the world, MUHAHAH...)

I was trying to compile E-UAE since my last post, but I am clearly not really fond of the multi-platform environment. Configure script is a bad dog: never behaves. (Linux developers must have an insane amount of time and patience.)

Finally, after running into the never-ending circle of deleting all, copy back, adjusting, configuring and do the make for the hundredth time: I was able to compile E-UAE sources, and the binary is even working. YAY! \o/

I am happy that I can start on tinkering with the JIT implementation, but I have to admit that my Amiga developer skills became a bit rusty in the last three years, since I hardly had time to spend on development.

I fought big time with the path of include files, still getting flooded with complaints about missing prototypes for the AOS functions, but at least that is only a warning. (Not that I can live with compile-time warnings for my code, but I really don't have enough strength to find what minor thing needs fine tuning in the compiling to get rid of these warnings safely.)

It took me an hour today to find out that TimeDelay function is part of the (obsolete) libamiga and this is why the linking failed every time. There was an easy fix for that: just remove the check for AOS4 from the sources and let it fall back to the DOS/Delay() function. Not a proper solution, because Delay() is badly inaccurate, but at least I was able to compile and fire it up.

The compiling on the uA1 is awesomely slow and eating up all the memory, so I had to turn on the swapping. I seriously considering the cross-compiling from my windows laptop, and let the A1 do the testing functionality only. It was a very long time since I tried cross-compiling for the OS kernel, back in the days when it was impossible to compile it on AOS4. It was painful, I had to use Cygwin and a number of tricks to get it working. Then copied the compiled binary to my Amiga 4000 on a floppy disk for testing... *Sigh* I was soo patient, I am amazed now. ;)

Speaking of which: I still need net connection for the uA1, that would be essential for the cross-compiling.

Anyway, let's go back to experimenting. The first test will be implementing a very-very simple form of the poor-man's JIT, which will do nothing more than "compiling" the executed code into series of calls to the interpretive instruction implementation functions. The outcome will be an environment, where I still have all the already implemented instructions, but I can replace them one-by-one with the real JIT instructions. Something what I needed when developed Petunia, but there was no interpretive emulator to back up the missing instructions.