This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
branch predictions
- To: jle at cygnus dot com
- Subject: branch predictions
- From: Jeffrey A Law <law at cygnus dot com>
- Date: Thu, 04 May 2000 03:11:29 -0600
- cc: gcc at gcc dot gnu dot org
- Reply-To: 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