Expand description
What values an integer can hold: a few intervals, and the bits that are known.
Design: spec/optimizer/10-value-ranges.md, sections 10.2, 10.4 and 10.7. This module is the
representation and ops is the arithmetic over it. The on-demand query that walks back
through branch conditions to answer what a value is at a point is the piece that comes after.
Knowing a value is in [0, 63] is what removes a bounds check, narrows a sixty four bit
multiply to thirty two, proves a shift count is in range, folds a comparison, and tells the
switch lowering which of eleven cases are unreachable. Section 10.5 counts six consumers and
says the first two are most of the value, which is the argument for building this well rather
than building it large.
§Three parts and not one
Intervals, plural. A range is a union of disjoint intervals rather than one [min, max],
because the single most useful fact in a C compiler is that a value is not zero, and that is
not one interval in every reading. It is what a null check produces and what a division needs.
Section 10.2 asks for a small fixed number of them, and this carries PAIRS with anything
beyond that collapsing to the hull, because an unbounded pair count is how a range
implementation becomes a memory problem.
Known bits, on the same object. A mask says which bits are unknown and a value says what
the rest are. Section 10.2 says keeping this beside the interval rather than in a lattice of
its own is the thing a from-scratch implementation gets wrong, because the two refine each
other: the low three bits being zero says the value is a multiple of eight, which narrows an
interval, and an interval of [0, 15] says the top bits are zero. Range::narrow is where
that happens and every operation that builds a range ends by calling it.
Pointers are separate. Not here. A pointer range is about null and about provenance and
forcing it through integer interval arithmetic produces a pointer in [0x1000, 0x2000] that
no target promised. Section 10.2 says GCC split prange out of irange in GCC 14 for this
reason, and rucc’s split is that this module is about integers and the pointer facts live with
the provenance in alias.rs, which already has them.
Floats have no range here at all. Section 10.2 says to skip them in M4: the interesting facts about a float are whether it is a NaN and what its sign is, the consumers are few, and the traps around signed zero and NaN comparison are many.
§Bit patterns, not signed numbers
GCC’s irange holds bounds in the domain of its tree type, which carries a signedness. An IR
type here does not: i32 is thirty two bits and the instruction says how to read them, which
is why there is an icmp slt and an icmp ult. So the intervals in this module are over the
unsigned reading of the bit pattern, from zero to 2^width - 1, and the signed facts are
recovered from them by Range::signed_bounds, which splits at the sign boundary.
This is a departure from the document and it is worth saying why. The property section 10.2
cares about is that a range can say a value is not zero, and in this domain that is the one
interval [1, max] rather than the two the document’s example has. What it costs is that a
small signed range around zero, [-5, 5], is two intervals rather than one. Both fit in
PAIRS, both are exact, and the domain that matches the IR is the one where the arithmetic
is exact, because every operation in the IR is defined on bit patterns modulo 2^width.
§How this is wrong
Section 10.7 names three ways and ops answers two of them. Wrapping: [100, 200] + [100, 200] in eight bits is not [200, 400], and every operation there is defined modulo the
width. Signed overflow: in a signed type without -fwrapv it may be assumed not to have
happened, so the flags the instruction carries are an argument to every operation that can
overflow rather than a check somewhere upstream, because a range computed under one assumption
and used under the other is a miscompilation.
The third is the one still open: precision loss is invisible. A range that fell back to everything because of a missing case produces correct code that is slower, forever, with no signal. There is no counter here yet because a count is only meaningful per query, and the query is what comes next.
Modules§
- ops
- What an operation does to a range, forwards and backwards.
- query
- Asking what a value is at a point, and answering it by walking backwards from there.