Re: branch predictions

[Joern Rennecke <amylaar at cygnus dot co dot uk>]

> I was looking at the results of block reordering and noticed a couple
> bad predictions that resulted in poor block orderings.
> 
> The particular case I was looking at we had a point in the cfg where
> one path unconditionally led to a loop, the other path unconditionally
> led to the function's exit.
> 
> We didn't predict anything and with the 50-50 'guess' we ended up
> mis-predicting the branch to start the key loop for the function and
> laying out blocks in a bad way.
> 
> I can think of three heuristics which would work to resolve this problem.
> 
> 	1. Given two successors, if one unconditionally exits and the
> 	other does not, then predict the path which does not unconditionally
> 	exit.
> 
> 	2. Given two successors, if one passes control to a loop that it
> 	dominates and the other does not, then predict the path to the
> 	dominated loop.
> 
> 	3. If we do not have any kind of prediction and one of the blocks
> 	physically follows the current block, then predict the block which
> 	physically follows the current block.  ie, don't rearrange code
> 	at random ;-)  
> 
> I did a very quick and dirty implementation of #1.  That allowed us to
> properly predict the key branch and we got the desired code.

Huh?  You are again predicting the branch to start the loop.

If the loop takes any significant amount of time, then mispredicting the
branch to exit when the loop actually starts should be neglegible, as
long as we lay out the loop itself well.

However, if the function takes an early exit, we better predict that
correctly, since otherwise the misprediction can cause a significant
increase of the total runtime of the function.