Expand description
Asking what a value is at a point, and answering it by walking backwards from there.
Design: spec/optimizer/10-value-ranges.md sections 10.1, 10.3 and 10.6. The representation
is super::Range and the arithmetic over it is super::ops. This is the part that reads
a function.
§On demand, and why that is the whole design
The textbook version of this analysis is a forward propagation: start every value at empty, iterate over the control flow graph to a fixed point, keep a range per value. Section 10.1 says what is wrong with it, and it is not the running time. It is that the range such a pass stores is the range at the definition, and the question anyone actually has is the range at a use, which is narrower by every branch in between. A pass that answers the first question precisely and the second one not at all has computed the wrong thing carefully.
So Ranges::at takes a value and a block and walks backwards. The definition of the value
gives a first answer, the branches that dominate the block narrow it, and nothing is computed
for a value nobody asked about. Section 10.1 measured the ratio the other way round and rucc
has fewer consumers than GCC does, so the ratio here is worse.
§Inverting the condition, which is where the precision is
if (x < 10) tells you about x and that is easy. if (x + 3 < 10) tells you about x + 3,
and the fact worth having is that x is at most six. GCC calls the machinery that gets from
one to the other GORI, and it is the inverse half of the table in super::ops applied along
the chain from the condition back to the value being asked about.
Ranges::at does that walk. It is bounded, because the chain can be as long as the function
and because a walk that is not bounded is a compile time bug waiting for the right input.
Options::logical_depth is how deep it goes, and it is GCC’s ranger-logical-depth, whose
default is the same six.
§The oracle, which knows things intervals cannot say
a < b is not a fact about the range of either. If both are [0, 100] the intervals say
nothing, and yet a branch may have proved it. Section 10.3 says to keep this and to keep it
small, so Ranges::relation answers from what was recorded on the dominating edges plus one
step of composition, and it is keyed by block because a < b holds on one edge and not on the
other one out of the same branch. Section 10.7 lists a relation recorded without its block as
a way to be wrong, and it is the one that would show up as a miscompilation rather than as a
missed optimization.
§The cache is bounded on purpose
A cache holding a range per value per block is quadratic in function size, and section 10.6
points out that the input which makes that hurt is not hypothetical: generated parsers have
tens of thousands of blocks and it is why GCC has vrp-sparse-threshold at all. So the cache
here holds one range per value at its definition and at most Options::refinements
block-specific answers beside it. Past that, a query for a new block gets the definition
range, which is correct and less precise, and Counts::fallbacks says how often that
happened. The bound is a parameter rather than a constant because the right number is an
empirical question and section 10.6 says GCC’s numbers are a record of bug reports.
§How this is wrong
A value carried around a loop is not pinned down. The walk assumes the range of the type for a value it is already in the middle of computing, which is what makes it terminate, so what comes back for a loop counter is one step of the recurrence applied to everything rather than the interval a fixed point would reach. That is sound, because every operation here over-approximates and the assumption it started from does too, and it is loose. There is no widening in M4 to tighten it, and the honest place to close the gap is document 07’s scalar evolution, which already knows the shape of a loop-carried value and is a better answer than a widening operator guessing at one.
Ranges derived from an overflow flag are ranges derived from undefined behaviour, and section
10.7 says those have to be visible. Counts::assumed counts them, which is less than that
section asks for: it wants -fdump-ranges to mark them and name the line, and the dump is not
here yet.
Precision loss is the failure mode with no symptom. Counts::losses breaks the queries that
came back knowing nothing down by the opcode that lost it, which is how the table in
super::ops grows by evidence rather than by guesswork.