On Tue, 24 Jun 2025 16:37:12 -0500
Segher Boessenkool <seg...@kernel.crashing.org> wrote:
> Hi!
>
> On Tue, Jun 24, 2025 at 09:32:58AM +0100, David Laight wrote:
> > > So GCC uses the 'unlikely' variant of the branch instruction to force
> > > the correct prediction, doesn't it ?
> >
> > Nope...
> > Most architectures don't have likely/unlikely variants of branches.
>
> In GCC, "likely" means 80%. "Very likely" means 99.95%. Most things get
> something more appropriate than such coarse things predicted.
>
> Most of the time GCC uses these predicted branch probabilities to lay
> out code in such a way that the fall-through path is the expected one.
That is fine provided the cpu doesn't predict the 'taken' path.
If you write:
if (unlikely(x))
continue;
gcc is very likely to generate a backwards conditional branch that
will get predicted taken (by a cpu without dynamic branch prediction).
You need to but something (an asm comment will do) before the 'continue'
to force gcc to generate a forwards (predicted not taken) branch to
the backwards jump.
> Target backends can do special things with it as well, but usually that
> isn't necessary.
>
> There are many different predictors. GCC usually can predict things
> not bad by just looking at the shape of the code, using various
> heuristics. Things like profile-guided optimisation allow to use a
> profile from an actual execution to optimise the code such that it will
> work faster (assuming that future executions of the code will execute
> similarly!)
Without cpu instructions to force static prediction I don't see how that
helps as much as you might think.
Each time the code is loaded into the I-cache the branch predictor state
is likely to have been destroyed by other code.
So the branches get predicted by 'the other code' regardless of any layout.
>
> You also can use __builtin_expect() in the source code, to put coarse
> static prediction in. That is what the kernel "{un,}likely" macros do.
>
> If the compiler knows some branch is not very predictable, it can
> optimise the code knowing that. Like, it could use other strategies
> than conditional branches.
>
> On old CPUs something like "this branch is taken 50% of the time" makes
> it a totally unpredictable branch. But if say it branches exactly every
> second time, it is 100% predicted correctly by more advanced predictors,
> not just 50%.
Only once you are in a code loop.
Dynamic branch prediction is pretty hopeless for linear code.
The first time you execute a branch it is likely to be predicted taken
50% of the time.
(I guess a bit less than 50% - it will be percentage of branches that
are taken.)
>
> To properly model modern branch predictors we need to record a "how
> predictable is this branch" score as well for every branch, not just a
> "how often does it branch instead of falling through" score. We're not
> there yet.
If you are going to adjust the source code you want to determine correct
static prediction for most branches.
That probably requires an 'every other' static prediction.
I spent a lot of time optimising some code to minimise the worst case path,
the first thing I had to do was disable the dynamic branch prediction logic.
David
>
>
> Segher
