Intel ARCHITECTURE IA-32 - Manual (Page 97)

General Optimization Guidelines
2
2-25
indirect branch into a tree where one or more indirect branches are preceded
by conditional branches to those targets. Apply this “peeling” procedure to the
common target of an indirect branch that correlates to branch history.
The purpose of this rule is to reduce the total number of mispredictions
by enhancing the predictability of branches, even at the expense of
adding more branches. The added branches must be very predictable for
this to be worthwhile. One reason for such predictability is a strong
correlation with preceding branch history, that is, the directions taken on
preceding branches are a good indicator of the direction of the branch
under consideration.
Example 2-8 shows a simple example of the correlation between a target
of a preceding conditional branch with a target of an indirect branch.
Correlation can be difficult to determine analytically, either for a
compiler or sometimes for an assembly language programmer. It may be
fruitful to evaluate performance with and without this peeling, to get the
Example 2-8 Indirect Branch With Two Favored Targets
function ()
{
int n = rand(); // random integer 0 to RAND_MAX
if( !(n & 0x01) ){ // n will be 0 half the times
n = 0; // updates branch history to predict taken
}
// indirect branches with multiple taken targets
// may have lower prediction rates
switch (n) {
case 0: handle_0(); break; // common target, correlated with
// branch history that is forward taken
case 1: handle_1(); break;// uncommon
case 3: handle_3(); break;// uncommon
default: handle_other(); // common target
}
}