Expand description
Static branch prediction: which way a branch goes, when there is no profile that says.
Design: section 11.2 of spec/optimizer/11-profile-and-frequency.md.
§Ten predictors and not fifty five
GCC has fifty five, in gcc/predict.def, each naming a syntactic situation and the rate at
which the guess turned out right when somebody measured it. Ten of those are for Fortran, and
a long tail of the rest sit below sixty five percent. Section 11.2 keeps ten: the ones that
survive both cuts. A predictor at fifty nine percent moves a probability nine points off even,
and nothing downstream of a frequency decides differently over nine points, so it costs a
branch of code here and buys nothing.
The numbers themselves are Ball and Larus’s and Wu and Larus’s, from the middle of the 1990s,
and they have held up because they are facts about how people write programs rather than about
any machine. They live in rucc_cost::heuristics with the document that argued for them, the
way section 40.12 says every threshold has to.
§First match
The predictors are ordered and the first one that applies decides. GCC computes both this and a
Dempster-Shafer combination of every predictor that applies, and uses first match by default;
this does the part GCC uses. The order is the order section 11.2 lists them in and it is the
part of this file most worth getting right, because it is where the predictors disagree that
the order is doing anything at all. __builtin_expect is first because a user who wrote it
meant it, and the cold attribute is near the top for the same reason.
§What a prediction is worth
Every probability out of here is Quality::Guessed, with one exception: a block with one
way out takes it, and that is Quality::Precise because it is not a guess. So a function
with no branches in it gets precise frequencies, which is the right answer and comes out of the
arithmetic rather than out of a special case.
§Where the noreturn predictor gets its answer
Two places, and only the first needs a call graph. The IR says it directly: the front end emits
Opcode::Unreachable after a call to a noreturn function, so a block from which no return
is reachable is a block control does not come back from, and that is a walk backwards from the
returns. The other place is the callee’s own attributes, which are per function and not at the
call site, so a caller that has the module hands them over in Callees. A function pass that
has only its function passes Callees::nothing and keeps the first answer, which is most of
what the predictor was for: C error handling is if (x) { report(); abort(); } and it is the
abort that shows up as unreachable.
Structs§
- Callees
- What the predictors know about the functions this one calls.
- Predictions
- How likely each edge out of each block is.
Enums§
- Predictor
- Which predictor decided a branch.