## Optimizing for branches

### Order by frequency

Rearrange nested branches so that frequently taken branches are evaluated first, so that the number of branches taken dynamically is reduced. Thus, replace the sequences

``````
if( usually_true )
if( usually_false ) /* both branches generally evaluated */

if( usually_true &&
usually_false ) /* both branches generally evaluated */

if( usually_false ||
usually_true ) /* both branches generally evaluated */
``````

with the sequences

``````
if( usually_false ) /* usually don't fall through to second branch */
if( usually_true )

if( usually_false &&
usually_true ) /* in false case, only one branch evaluated */

if( usually_true ||
usually_false ) /* in true case, only one branch evaluated */
``````

### Group branches

Sometime a large number of conditionals have to be evaluated, but most of the time none of them are true. In that case, it is sometimes possible to replace them with a single test that checks to see if any of them are true, and then proceeds with the individual checks. A simple example is:

``````
if( err_code & ERR_1 ) {
}
/* ... */
else if( err_code & ERR_N_1 ) {
}
else if( err_code & ERR_N ) {
}
else {
/* no errors; common case! */
}

/* replace above code with more efficient */
if( err_code & (ERR_1|...|ERR_N) ) {
if( err_code & ERR_1 ) {
}
/* ... */
else if( err_code & ERR_N_1 ) {
}
else {
assert( err_code & ERR_N );
}
}
else {
/* no errors; common case! */
}
``````

With this kind of a transform, in the common case only one branch is executed instead of the previous N.

Another example that sometimes arises is:

``````
if( x < 0 ) {
}
else if( x == 0 ) {
}
else {
/* common case! */
}

/* replace with more efficient */
if( x <= 0 ) {
if( x < 0 ) {
}
else {
assert( x == 0 );
}
}
else {
/* common case */
}
``````

### Equivalent sequences

It is sometimes possible to replace a branchy sequence with a straight-line sequence that has identical semantics. For instance:

``````
if( x > 0 ) {
z = 0;
}

/*  right arithmetic x by 31
* mask is 0 if x > 0, else all 1s
*/
/* and z with 0s if x > 0, giving 0
* otherwise and with all 1s, giving z
*/
• It relies on ints being 32 bits (fixable by using `(sizeof(int)*CHAR_BITS)-1` instead of `31`)
• It relies on right shifts of `int` being a sign-extending right