Branch Prediction

Static Branch Prediction

Back-Branch-Taken

The branch is predicted to be taken if a negative displacement, such as at the bottom of a loop. A flow through (branch not taken), would be a misprediction!

Forward-Branch-Not-Taken

The branch is predicted not to be taken if a positive displacement such as a jump further down the code. The instruction pointer is expected to just flow through the branch instruction. A jump would be a misprediction.

$L1:   nop
       nop
       jne    $L1    ;



Back-Branch-Taken
   
       jz     $L2    ;



Forward-Branch-Not-Taken
       nop
$L2:   nop

Branching Hints

A prefix of 3Eh (HT) is a hint to take the branch. A prefix of 2eh (HNT) is a hint not to take a branch (flow through). Only set if contrary to a static branch prediction. Sometimes there are no elements to test, so at the top of a function one might have an if conditional ( size =0) empty test.

test ecx,ecx
  db 3eh   ; Hint to take the branch
  jz $L9
   
           ; Insert looping code here
   
$L9:

The default static prediction is to not branch as the jz is a forward-branch and the prediction logic does a flow through, but the 3eh says to override and take the branch as the length is typically expected to be zero most of the time.

AMD Branch Prediction

The same rules for Intel apply here but with some minor changes. The AMD K6-2 chip uses a two-level 8192 entry branch prediction table. It is more effective to use only 8-bit displacements. Code with small loops should be aligned on 16-byte boundaries and code with loops that do not fit in the prefetch should be aligned on 32-byte boundaries. Small loops should be unrolled but large loops should not, due to inefficient use of the L1 instruction cache. A mispredicted branch is from one to four clocks. The penalty for a bad prediction if the branch is not in BTB is three clock cycles.

Branch Optimization

Removing branches from your code such as unrolling loops makes it more efficient by removing the possibility of misprediction. This is discussed in more detail in the next chapter. One method is to use the SETcc instruction to set Boolean flags. Another method is to use CMOV or FCMOV instructions to copy data. These methods can sometimes be manipulated to duplicate the same effect you were trying to achieve with the Jcc instruction without any possible prediction failure that would cost cycles.

For example, the following is the signed integer absolute number function n = ABS(n), which uses a Jcc instruction.

test  eax,eax   ; Test if negative
       jns   $Abs1     ; Jump if positive
   
       neg   eax       ; Invert number, two's complement
   
$Abs1:                 ; eax is positive

As an alternative, we can do this without a Jcc instruction:

mov    ecx,eax
sar    ecx,31          ; all 1's if neg, all 0's if pos
xor    eax,ecx         ; At this point we are one's complement
sub    eax,ecx         ; n(1)=n+1 = two's complement

So you see, we did an ABS() function without any Jcc instructions; just a sleight of hand using general-purpose instructions. Admittedly this technique will not work on everything, but it will help in your optimizations. In Chapter 11 we will go into more detail.

Destination addresses of a jump should be code aligned to take advantage of the instruction prefetch.

align   16

Of course the Align statement must not be in the code flow, as unknown bytes are added to align the code, So it must always occur outside a function, thus after a JMP or RET statement. Another alignment type would be for fine-tuning on a byte-by-byte basis such as:

org   $+3

which aligns by moving the origin pointer from the $ current location by three bytes, effectively adding three unknown bytes. Typically you will find it paired with an alignment to create a fixed alignment point. This prevents any alignment of a previous function affecting the alignment of a following function.

align  16 
org     $+3

Inside the code flow you can add nondestructive instructions such as the following to help align your code. Your flags may be altered but not the registers.

nop              ; 1 byte
      mov    eax,eax   ; 2 bytes

66h

mov    ax,ax     ; 3 bytes

Let's start by examining a C type strlen() function designed to find the number of bytes in a zero- terminated ASCII string:

uint strlen(char *p)
{
    uint cnt = 0;
   
    while (*p++)
        cnt++;
   
    return cnt;
}

Let's try that in assembly and align the code to a 16-byte boundary:

align 16

00000000   54               push   ebp
00000001   8B EC            mov    ebp,esp
00000003   8B 54 24 08      mov    edx,[ebp+arg1] ; String
   
00000007   B8 FFFFFFFF      mov    eax,1
   
0000000C   40         $L1:  inc    eax
0000000D   8A 0A            mov    cl,[edx]       ; Get a character
0000000F   42               inc    edx
00000010   84 C9            test   cl,cl
00000012   75 F8            jnz    $L1            ; 0 terminator?
   
00000014   5D               pop    ebp
00000015   C3               ret                   ; return eax (length)
00000016

As you have probably noted, the entire function occupies 16h (22) bytes (000h..016h). It also has an efficiency problem. The 16-byte prefetch is first loaded with address 0000h000fh, executes up to and including the "inc edx" and then reloads the prefetch with the next 16 bytes, address 0010h001fh. The code then executes up to address 0013h and then the prefetch has to be reloaded with 0000h again. This continues over and over again until the zero terminator is encountered. Now if we tweak the alignment a tad we can contain this $L1 loop within one prefetch:

align 16
                            org $+4
   
00000004   54               push   ebp
00000005   8B EC            mov    ebp,esp
00000007   8B 54 24 08      mov    edx,[ebp+arg1] ; String
   
0000000B   B8 FFFFFFFF      mov    eax,1
   
00000010   40         $L1:  inc    eax
00000011   8A 0A            mov    cl,[edx]       ; Get a character
00000013   42               inc    edx
00000014   84 C9            test   cl,cl
00000016   75 F8            jnz    $L1            ; 0 terminator?
   
00000018   5D               pop    ebp
00000019   C3               ret                   ; return eax (length)
0000001A