Inline Assembly Isn't Always The Answer

The first mystery that puzzled me was why build B - a recompile of the official Bochs 2.3.5 sources using Visual Studio 2003 - was benchmarking faster than the reference build using GCC. A few weeks ago I demonstrated how Visual Studio if anything produces less optimal code than GCC, so I would not expect it to outperform GCC.

The first tool in a developer's bag of tricks is to make sure that you understand the code that you are running, which means verifying that it is in fact running the code that you think you compiled. In this case, I was not! I assumed that the inline assembly found in the source file cpu\hostasm.h was being used, as this contains optimizations specific to x86 hosts. In Visual Studio's compilers, add the compiler switch -FAsc to generate listing files which show the original C/C++ source and the compiled x86 assembly code.

I soon realized that the inline asm was #ifdef-ed by the symbol __i386__, which Visual Studio's compiler does not define. As a result, the VC7.1-built executable was using C++ based routines. In looking at the inline asm, I realized that of course that inline asms wasn't very optimal. Here is an example of that inline asm:

// This file defines some convience inline functions which do the
// dirty work of asm() statements for arithmetic instructions on x86 hosts.
// Essentially these speed up eflags processing since the value of the
// eflags register can be read directly on x86 hosts, after the
// arithmetic operations.

// gcc on i386
#if (defined(__i386__) && defined(__GNUC__) && BX_SupportHostAsms)

#define BX_HostAsm_Add16
static inline void
asmAdd16(Bit16u &sum_16, Bit16u op1_16, Bit16u op2_16, Bit32u &flags32)
{
asm (
"addw %3, %1 \n\t"
"pushfl \n\t"
"popl %0"
: "=g" (flags32), "=r" (sum_16)
: "1" (op1_16), "g" (op2_16)
: "cc"
);
}
 

Do Not Overpack

Travelling lightly is good advices when going on vacation, and it is good advice inside of an interpreter. If you look at the file cpu\cpu.cpp, you will see the Bochs main interpreter loop. Recall how a few weeks ago I gave an example of a simple CPU interpreter loop, one that is structured like this:

void Emulate6502()
{
    register short unsigned int PC, SP, addr;
    register unsigned char A, X, Y, P;
    unsigned char memory[65536];

    memset(memory, 0, 65536);
    load_rom();

    /* set initial power-on values */
    A = X = Y = P = 0;
    SP = 0x1FF;
    PC = peekw(0xFFFC);

    for(;;)
        {
        switch(peekb(PC++))
            {
        default: /* undefined opcode! treat as nop */
        case opNop:
            break;

        case opIncX:
            X++;
            break;

        case opLdaAbs16:
            addr = peekw(PC);
            PC += 2;
            A = peekb(addr);
            break;

...
            }
        }
}

You would not actually write an interpreter in this manner for various efficiency reasons, but the general bytecode interpreter inside of a virtual machine, even inside a Java virtual machine, has such an inner execution loop. Bochs is no exception, using an inner loop to first fetch and decode the next instruction, then to calculate the effective address of that instruction (if it references memory), and then to call a handler which simulates that one instruction. The handler functions are equivalent to each of the "case" statements in the sample above.

To pass information about the current instruction between those three parts of the loop, Bochs uses a common data structure to represent the decoded state of the current instruction. This is defined as the bxInstruction_c class in the source file cpu\cpu.h. In Bochs 2.3.5, a portion of that class looks something like this:

void (BX_CPU_C::*ResolveModrm)(bxInstruction_c *) BX_CPP_AttrRegparmN(1);
void (BX_CPU_C::*execute)(bxInstruction_c *);

// 26..23 ilen (0..15). Leave this one on top so no mask is needed.
// 22..22 mod==c0 (modrm)
// 21..13 b1 (9bits of opcode; 1byte-op=0..255, 2byte-op=256..511.
// 12..12 BxRepeatableZF (pass-thru from fetchdecode attributes)
// 11..11 BxRepeatable (pass-thru from fetchdecode attributes)
// 10...9 repUsed (0=none, 2=0xF2, 3=0xF3).
// 8...8 extend8bit
// 7...7 as64
// 6...6 os64
// 5...5 as32
// 4...4 os32
// 3...3 (unused)
// 2...0 seg
Bit32u metaInfo;

// 27..20 modRM (modrm)
// 19..16 index (sib)
// 15..12 base (sib)
// 11...8 nnn (modrm)
// 7...6 mod (modrm)
// 5...4 scale (sib)
// 3...0 rm (modrm)
Bit32u modRMData;

The decoder fills in the execute field with a function pointer to a handler function which will simulate a given instruction. The execute field cannot be NULL, it must point to a valid function.

The ResolveModrm field contains another function pointer, this one which points to a function which will calculate the instruction's memory effective address. This field can be NULL, since most register operations do not operate on an effective address.

Other details about the instruction, such as the opcode and sub-opcode, the memory addressing mode, the addressing size, etc. are encoded as bitfields in two 32-bit integers called metaInfo and modRMData. These troubled me!

Looking at the code in cpu\fetchdecode.cpp that sets those various fields and bitfields, and the looking at the code in various handlers that reads those fields, I realized there was a lot of unnecessary bit twiddling going on. If you think about it, the fetch and decode stage reads x86 bytecode and extracts various bitfields into integers. Those integer values are then repacked into bitfields in metaInfo or modRMData. The handlers then have to immediately unpack those bitfields back into integers. This is wasteful to say the least, especially considering that the Pentium 4 is fairly inefficient at bitfield operations.

My solution replaced the various bitfields, none of which is bigger than 8 bits in size, with a series of 8-bit integer fields. This avoids the redundant packing and unpacking of bitfields and the associated shifting and masking operations.

Branch Prediction and PGO

In the 1980's and early 1990's, CPU pipelines were short, throughput was at best one instruction per clock cycle, and code optimization was relatively easy to do. A memory load, a memory store, a branch, a jump, a call, or an arithmetic operation all cost about the same - perhaps one clock cycle, two, three, in rare cases 6 or 8. Things like branch predictors and L1/L2 caches did not even exist on more microprocessors, and so programmers didn't have to code for them.

As clock speeds got faster, caches were added to hide the increasing latency of reading memory, which today can be 200 or 300 clock cycles for a "missed" read. To compensate for these "pipeline bubbles", pipelines were made longer so as to be able to work on more instructions. Should one instruction take a long delay to read memory, other instructions could proceed through the CPU pipeline, provided of course there were no data dependencies on the stalled instruction.

Unfortunately, the CPU can only cheat so much. It eventually fetches and decodes a flow control instruction with no specific target address - an indirect jump, an indirect function call, a function return, a conditional branch, or more rarely a trap - where the address of the next instruction is not immediately known. In the case of indirect jumps and function calls/returns, the pipeline usually has to empty such that the address of the indirection can be calculated. In the case of an conditional branch, the pipeline similarly has to empty so that the result of some arithmetic operation, and consequently the arithmetic flags that it updates, can be known with certainty. Only then can a conditional branch either get taken or fall through.

To work around these frequent stalls, engineers developed the concept of speculative execution, which relies on branch prediction to "guess" at the address of the next instruction. If the guess turns out to be correct, or predicted, the pipeline is kept full with valid instructions. If the guess turns out to be wrong, or mispredicted, the CPU pipeline is thrown out and instructions start getting fetched and decoded from the correct address.

A branch misprediction is a costly event, wasting approximately 10 to 20 clock cycles, or in ILP terms, 30 or more instructions that could have completed during that time. Literally, one branch misprediction can be costlier than executing even 20 integer arithmetic operations.

In recent years, programmers have started coming up with branchless code sequences, those which implement something like a C++ "if/else" statement without using flow control. I will get into this concept more next week, but for now, I want you to understand that the worst kind of branches are those with close to a 50-50 probability of getting taken or not taken. Branches that lean heavily in the taken or in the not-taken direction are easier for the hardware to predict.

Also, indirect function calls are easier to predict when the number of possible call targets is small, or even one. For example, if you initialize a function pointer at boot time and never change it again, such as selecting between one of two different square root functions based on some CPU feature, chances are good that the CPU will soon predict the correct function.

What a programmer, even a C++ or Java programmer therefore wants to be on the lookout for are branches and indirections that will be difficult for the hardware to predict. You have to assume the worst in those cases and plan to taking a 10 or 20 clock cycle stall every time such code is executed.

Two such glaring examples are sitting right in the main execution look in Bochs, and it has to do with those two function pointers we just saw - execute and ResolveModrm. Each function pointer is referenced during each guest instruction loop. Both function pointers can end up pointing at dozens of different functions. ResolveModrm points to one of several different address generation functions found in the source files cpu\resolve16.cpp, cpu\resolve32.cpp, and cpu\resolve64.cpp. execute points at one of the many x86 opcode handlers through out the code. Both function pointers can change on each iteration of the loop and can be highly unpredictable.

The code in question is in cpu\cpu.cpp and looks like this:

    if (i->ResolveModrm)
    {
    BX_CPU_CALL_METHODR(i->ResolveModrm, (i));
    }

    BX_CPU_CALL_METHOD(i->execute, (i));

The function pointed to by the i->ResolveModrm pointer is only called if that pointer is non-zero. On the other hand, the i->execute pointer is always called. There is a significant difference here in terms of branch misprediction, in that the address resolution requires two predictions - one to predict whether the pointer is non-NULL, and one to then predict the target address of that pointer. In the worst case, you can end up having two branch misprediction. The execute pointer on the other hand has a worst case of just one branch misprediction.

One thing to consider doing then is to avoid the "if" statement completely and rather always call i->ResolveModrm by replacing the NULL cases with a pointer to a dummy function that simply returns, or what is called a stub function. Which is faster? To check a pointer for being NULL and thus introduce a second branch prediction, or to always call the function even if it just to a stub?

To make this kind of coding decision, you need data, real data based on running real scenarios. A basic question is, what percentage of time is the pointer NULL?

To answer this question, I turned to the Profile Guided Optimization (PGO) feature in Visual Studio. This allows me to run Bochs in a profiler and actually get counts and taken/not-taken percentages for each and every branch in the program. For the particular line of code of the "if" statement, the results were clear:

; 251 : if (i->ResolveModrm)
000ec 8b 03 mov eax, DWORD PTR [ebx]
000ee 85 c0 test eax, eax
000f0 0f 85 4b 02 00 00 jne $LN1201@cpu_loop
; taken 365376736(36%), not-taken 623926243(63%)

Out of approximately one billion x86 instructions simulated, about 36% of the time the pointer is NULL, indicating that about 2 in 3 x86 instructions contain a memory address that needs to be calculated, which thankfully makes sense. Of the remaining time any number of functions get called. Each of those address resolving functions looks something like this, such as these two in cpu\resolve32.cpp:

void BX_CPU_C::Resolve32Mod0Rm7(bxInstruction_c *i)
{
RMAddr(i) = EDI;
}

void BX_CPU_C::Resolve32Mod1or2Rm0(bxInstruction_c *i)
{
RMAddr(i) = EAX + i->displ32u();
}

Each of the dozens of functions is very similar. Some use register EAX, some use ECX, some use EDX, and so on. Some add a displacement to the base register and some do not. I had a hunch that the vast majority of address resolution is in the form [reg] or [reg+displacement], and in fact the profile data showed that 87% of function resolution was of these two forms. And considering that [reg] is really the same as the address [reg+0], it is all the same form. So I decided to trade a branch misprediction for a memory load and an arithmetic ADD operation, by combining 16 such functions into a single function:

void BX_CPU_C::Resolve32DispBase(bxInstruction_c *i)
{
Bit32u base = BX_READ_32BIT_REG(i->sibBase());

RMAddr(i) = base + i->displ32u();
}

This now means that 36% of the time, the pointer is NULL, and 87% of the remaining time, or about 55% of the time, this new Resolve32DispBase function is called. Therefore by using both a stub function, and merging 16 similar functions into one, the "if" and indirect call can be replaced by a single indirect function call which has almost identical probability as the original "if" statement. In other words, one of the two branch mispredictions is just about eliminated.

The moral here is, don't mix "if" statements and indirect function calls if you can combine them into one.

A similar example of such double branch misprediction is in the handlers which simulate the guest x86 conditional branches. The Bochs 2.3.5 code is written so that all conditional branches go to a common JCC handler, such as the one in ctrl_xfer32.cpp. Within that handler is then immediately a switch statement which jumps to one of 16 condition handlers. Only two cases, the Jump Zero and Jump Not Zero instructions (JZ and JNZ) directly jump to a unique handler. The better thing to do was to eliminate the common JCC handler and switch statement completely, and to go with 16 unique handlers for the 16 branch conditions.

PGO's Ironic Twist

So far so good, the clock cycles are just falling off the benchmarks. But I was puzzled by Build D, the PGO-optimized version of Build C, was consistently slower in the benchmarks. After all, it is in theory compiled based on the scenario profiling results, so I would have expected it to be the fastest build of all!

The answer is quite ironic, but for now I will leave this as the puzzle for you to solve for next week, when I will also go into the details of lazy flags evaluation.