branch predictions

[Jeffrey A Law <law at cygnus dot com>]

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.


Thoughts?
jeff