# Branching is bad (in machine code)

by David JonesA modern CPU executes machine instructions at great speed,
and part of this speed comes from *pipelined execution*.
This is where the procedure to execute an instruction is
broken down into many steps,
with the steps being joined together to make a pipeline.
Classically, these steps are *Fetch*, *Decode*, *Execute*,
*Write-back*, but these days pipelines are deeper and have more stages.
This improves speed because the sections of the pipeline can
execute concurrently.
Once the first instruction has been fetched
it proceeds to decode;
while it is being decoded, the next instruction is fetched.

The optimal case is when all stages of the pipeline take the same time, and they are all occupied. A 4-stage pipeline permits 4 instructions to be executed concurrently. In principle this works well, until it becomes unclear where the next instruction comes from.

A conditional branch instruction tests some processor state (such as whether the carry flag is set, or whether a register is zero) and then continues execution at either the next instruction, or branches to a new instruction stream whose address is specified by the branch instruction.

In pipelined execution, branch instructions are bad news.
That's because you don't know where the next instruction comes
from until after you've executed the branch.
In our classic 4-stage pipeline we should have fetched and
decoded it by then!
The typical solution to this is to attempt a *branch prediction*
and *speculatively execute* the new stream.
Later, when the results of the branch are known,
the fate of the speculative instructions is known and they are
either discarded (if the prediction is wrong) or marked for
completion (if the prediction was right).

The Wikipedia article on Branch Prediction provides a pretty good overview.

If the prediction is incorrect then we suffer a *misprediction penalty*.
The speculatively executed instructions are discarded and
the CPU has to wait while instructions are fetched from
the new instructions stream.

Each branch instruction comes with the burden of misprediction. Better to reduce the branch instructions you use, right?

I am implementing a Forth system in 64-bit Intel assembly language. It is a silly project, but it keeps me happy and implementing it gives me a few very geeky anecdotes.

# Implementing ABS

One of these anecdotes is eliminating branches
from the implemention of ABS.
`ABS`

is a procedure that computes the *absolute value* of a number.
In the version I am implementing,
the input is a signed 64-bit integer,
and the output is the positive integer with the same magnitude.

The first version I implement is on github.

When you remove the Forth procedure entry and exit code, it's basically:

```
mov rax, [rbp-8] ; NASM syntax, destination on left
test rax, rax
jns .pos
neg rax
pos: mov [rbp-8], rax
```

Having executed `test rax, rax`

, the `jns`

instruction
Jumps if Not Signed.
In this case Signed means "has the sign bit set" which means
negative;
So if `rax`

is 0 or positive the jump is taken and
so the `neg rax`

instruction is skipped.
`neg rax`

negates `rax`

.

This is roughly equivalent to the pseudo code:

```
if rax < 0:
rax = -rax
```

And this does implement ABS.

But it contains a conditional branch.

# Branchless

In a whimsical moment I decided to "improve" the code by making it branchless.

The new version is also on github.

The code is:

```
; Convert carry flag to Forth boolean in rcx
mov rcx, rax
shl rcx, 1
sbb rcx, rcx
; rcx is now 0 or -1
; If rcx is -1, negate the old-school way.
xor rax, rcx
sub rax, rcx
mov [rbp-8], rax
```

Observations: more code; more comments are required; the comments are (slightly) misleading.

In the first comment, "Forth boolean" means a value that is either 0 or -1. And while it is true that the carry flag is converted, first the sign flag is shifted into the carry flag.

The new implementation is in two parts:
1. compute a value, in `rcx`

, that is either 0 or -1; then,
2. cunningly use this to either negate `rax`

or leave it unchanged.

The first part also involves a bit of cunning:

The "Subtract with Borrow" instruction computes
`(Rd - Rs) - B`

where `Rd`

is the destination register,
`Rs`

is a source register, and
`B`

is the borrow (aka carry) flag which is either 0 or 1.

In `sbb rcx, rcx`

the source and destination are the same:
the value computed is `(Rd - Rd) - B`

,
which is the same as `- B`

.
so the result is 0 when the carry flag is 0,
and -1 when the carry flag is 1.

This is a neat trick to turn a carry flag into 0 or -1. Wish I had thought of it, but I didn't. I found it somewhere on the internet, and now I can't find out where. [update: it was probably from this blog article]

# 2's complement

The second part relies on 2's complement notation. -1 is 0b1111...1111 (64 bits, all set to 1). 0b1111...1111 - S is the same as 0b1111...1111 XOR S (because there are no borrows). We want to compute 0 - S. Well, -1 - S is nearly right. Just add 1 to the answer:

0 - S == (1 - 1) - S == 1 + (-1 - S)

And adding 1 is the same as subtracting -1.

How does this all help? We want to compute:

0 - S

which is the same as

1 + (-1 - S)

same as

(-1 - S) - (-1)

same as

(S XOR -1) - (-1)

same as

(S XOR RCX) - RCX

when RCX is -1.

So, when RCX is -1 we can negate S by
computing `(S XOR RCX) - RCX`

.

When RCX is 0 note that `(S XOR 0) - 0`

is S.
So S is unchanged.

Perfect, that's exactly what we want.

# This is an Improvement?

Well, there's a reason I used scare quotes around "improve", above.

There are fewer branches. That's good.

There is more code. That's bad.

More registers are used. That's bad too.

Ideally I would benchmark, but I haven't.
`ABS`

is such a small part of even an unrealistic benchmark.
There are so many other branches,
that removing one is going to make a tiny difference.

So no benchmark. But I am warmed by the satisfaction that there is one fewer branch in the code. :)