Expand description
Block frequency: how often a block runs, relative to the function it is in.
Design: sections 11.3, 11.4 and 11.5 of spec/optimizer/11-profile-and-frequency.md.
§From probabilities to frequencies
crate::predict answers a local question, which is which way one branch goes. Almost every
consumer wants the global one instead: inlining, unrolling, block layout, spill placement and
if-conversion all ask how often this block runs compared with the function entry, and if that
answer is wrong they are all wrong together in a way that is very hard to attribute to anything.
The frequency of a block is the sum, over the edges into it, of the source’s frequency times the probability of the edge, with the entry pinned at one. On an acyclic graph that is one pass in reverse postorder. On a loop it is not, because the header’s frequency depends on the latch’s and the latch’s depends on the header’s.
Wu and Larus’s answer, which is the one section 11.3 asks for, is to take the loops from the
inside out. For each loop, work out the cyclic probability, which is how likely the loop is to
go round again, and then the header runs 1 / (1 - p) times for every entry to it, that being
the sum of the geometric series. The rest of the loop follows from the header by the acyclic
rule. So the whole computation is one walk of the loop forest to get a number per loop and then
one reverse-postorder walk of the function with the back edges left out, and Frequency does
the series and the clamp in Frequency::repeated_while.
§The two ways this breaks, and what is done about them
A loop whose exit no predictor recognised has a cyclic probability of certainty, and one over
zero is not a frequency. The count is capped at MAX_PREDICTED_ITERATIONS, which is section
11.2’s max-predicted-iterations, and the cap lives inside the type so that no caller can skip
it. A capped header is recorded, because it is the one place where the sum of what arrives does
not equal what is there, and the check in Frequencies::problems would otherwise report the
cap as a bug.
Nested loops multiply, so frequencies overflow. That is section 11.6’s first entry, and the
defence is that Frequency saturates rather than wrapping and says it has.
§Irreducible regions
A region with two entries has no header, so there is no series to sum and no well defined
frequency for anything in it. Document 06.4 declines to transform these and this is where the
consequence lands: the blocks get a frequency computed as though the edges that go backwards in
reverse postorder were not there, which is wrong but bounded, and they are marked so a consumer
can decline them. GCC does the same. Frequencies::is_reliable is the mark, and it spreads
forward, because a block whose frequency was computed from a wrong one is wrong too.
Structs§
- Frequencies
- How often every block in a function runs, with the entry at one.