Lesson 17.2 — Range and bit-level analyses: LVI, ConstantRange, KnownBits, DemandedBits¶

Techniques: LLVM's LazyValueInfo (demand-driven ranges with edge refinement) and CorrelatedValuePropagation; ConstantRange arithmetic (wrapped intervals) and the soundness of its transfer functions; known bits (KnownBits, computeKnownBits); demanded bits and bit-tracking DCE (DemandedBits, BDCE) · Pebble implements: none of them (the lab and exercises stay with constants); this lesson is theory, drills of Ch 14 (widening) and LLVM case studies · Prerequisites: Lesson 17.1; abstract interpretation and intervals (Lesson 14.7) · Time: 5–6 hours

1. Problem and motivation¶

Constants are the top of a much larger hierarchy of facts. Knowing that x lies in \([0, 1000]\) lets a compiler replace sdiv x, 8 by a cheaper udiv, delete a bounds check, or fold x > 2000 to false; knowing that the low four bits of x << 4 are zero folds (x << 4 | 3) & 12 to 0; knowing that only the low byte of a value is ever used lets it delete the computation of the other 24 bits. LLVM computes these facts with four cooperating analyses, each a small abstract domain (Ch 14, Lesson 14.7) engineered for speed. This lesson treats each as a technique with its own domain, transfer functions and soundness argument, and shows them at work in opt.

LazyValueInfo and correlated value propagation¶

LVI answers one question on demand: what range does value v have at the start of block B? It combines the range computed from v's definition with the constraints imposed by the branches on every path into B (on the false edge of x < 0, x is \(\geq 0\)). Unlike SCCP it is demand-driven and path-sensitive at edges: there is a fact per (value, block) pair, computed only when a client asks [LLVM-LVI]. Its clients are jump threading (Lesson 17.7) and correlated value propagation (CVP), which rewrites instructions using the facts: signed to unsigned division, narrower division, nsw/nuw flags, folded compares [LLVM-CVP]. It descends from value-range propagation (Harrison 1977, and Patterson's VRP 1995, cited in Lesson 14.7) and has GCC's Ranger as its counterpart [GCC-RANGER].

ConstantRange arithmetic¶

LVI, SCCP and InstCombine share one domain: ConstantRange, an interval of \(w\)-bit integers that may wrap around [LLVM-ConstantRange]. Wrapped intervals matter because machine integers are modular: [250, 3) over i8 is a perfectly good set (250…255, 0, 1, 2) that no ordinary interval can express without losing everything. The domain needs a sound transfer function for every LLVM operation; this lesson proves the one for addition and shows where the union loses precision.

Known bits¶

KnownBits tracks, for each bit of a value, whether it is known 0, known 1 or unknown: the domain of "parity-like" facts that ranges cannot express (a multiple of 16 has its low four bits zero whatever its range) [LLVM-KnownBits]. computeKnownBits is a demand-driven query over the use-def graph with a depth limit rather than a fixed-point solver [LLVM-ValueTracking]; InstCombine calls it constantly.

Demanded bits and bit-tracking DCE¶

DemandedBits runs backwards: which bits of each value can influence an observable result? A value truncated to i8 demands only 8 bits of its operand; a shift by 24 moves the demand. BDCE deletes instructions none of whose bits are demanded and drops flags that no longer hold [LLVM-DemandedBits, LLVM-BDCE]. This is dead-code elimination at bit granularity (Lesson 17.3 at the level of bits).

2. Definitions and algorithms¶

Throughout, \(w\) is the bit width and arithmetic on bit patterns is modulo \(2^w\).

Definition 17.2.1 (Wrapped interval, ConstantRange)

A wrapped interval of width \(w\) is the empty set, the full set \(\mathbb{Z}_{2^w}\), or a pair \([\ell, u)\) with \(\ell \neq u\) denoting \(\gamma([\ell, u)) = \{\, \ell + i \bmod 2^w \mid 0 \leq i < (u - \ell) \bmod 2^w \,\}\). Its size is \(\lvert [\ell, u) \rvert = (u - \ell) \bmod 2^w\) (full: \(2^w\), empty: 0). It wraps when \(u < \ell\) as unsigned numbers. Wrapped intervals ordered by \(\gamma\)-inclusion form a poset but not a lattice: two intervals can have two incomparable minimal upper bounds.

Wrapped intervals over i8

\([160, 192)\) has size 32. \([160, 29)\) wraps: it is \(\{160, \dots, 255, 0, \dots, 28\}\), size 125. LLVM prints \([160, 29)\) over i8 in signed form as range(i8 -96, 29).

Definition 17.2.2 (Sound and best abstract transformers)

For a binary operation \(\mathit{op}\) on \(\mathbb{Z}_{2^w}\) and a domain with concretization \(\gamma\), an abstract transformer \(\mathit{op}^\sharp\) is sound if \(\{\, \mathit{op}(a, b) \mid a \in \gamma(A),\ b \in \gamma(B) \,\} \subseteq \gamma(\mathit{op}^\sharp(A, B))\) for all \(A, B\); it is best if moreover no other domain element with this property has a smaller concretization (Ch 14, Lemma 14.7.3).

Algorithm 17.2.3 (ConstantRange addition and union)

Input: wrapped intervals \(A, B\) of width \(w\).
Output: \(A +^\sharp B\) and \(A \sqcup^\sharp B\).
Precondition: \(A\), \(B\) well formed (Definition 17.2.1).
Postcondition: both results are sound (Lemmas 17.2.9, 17.2.10); Union returns a smallest single wrapped interval containing both.
Invariant: none (straight-line code); sizes are compared as unsigned \((w{+}1)\)-bit numbers.

function Add(A, B):                                    # ConstantRange::add
    if A = ∅ or B = ∅: return ∅
    if A = full or B = full: return full
    [ℓ1, u1) ← A; [ℓ2, u2) ← B
    ℓ ← ℓ1 + ℓ2;  u ← u1 + u2 − 1                      # mod 2^w
    if ℓ = u: return full
    R ← [ℓ, u)
    if |R| < |A| or |R| < |B|: return full             # the size wrapped: overflowed
    return R
function Union(A, B):                                  # ConstantRange::unionWith, simplified
    if A = ∅: return B;  if B = ∅: return A
    candidates ← { [ℓ1, u2), [ℓ2, u1) }                # each covers A and B going "one way round"
    keep those whose γ contains γ(A) ∪ γ(B)
    return one of minimal size (full if none is smaller than 2^w)

Definition 17.2.4 (Known bits)

A known-bits value of width \(w\) is a pair of masks \((Z, O)\) with \(Z \mathbin{\&} O = 0\); bit \(k\) is known zero if \(Z_k = 1\), known one if \(O_k = 1\), unknown otherwise. \(\gamma(Z, O) = \{\, x \mid x \mathbin{\&} Z = 0,\ x \mathbin{\&} O = O \,\}\). The order is \((Z, O) \sqsubseteq (Z', O')\) iff \(Z' \subseteq Z\) and \(O' \subseteq O\) bitwise (fewer known bits is higher); the join is \((Z \mathbin{\&} Z', O \mathbin{\&} O')\). A conflict (\(Z \mathbin{\&} O \neq 0\)) encodes the empty set.

Known bits of the lesson's example

For %a = shl i32 %x, 4: \(Z = \mathtt{0xF}\), \(O = 0\) (low four bits zero). For %b = or %a, 3: \(Z = \mathtt{0xC}\), \(O = \mathtt{0x3}\). For %c = and %b, 12: \(Z = \mathtt{0xFFFFFFFF}\): the constant 0.

Algorithm 17.2.5 (Known bits of a sum, ripple-carry abstraction)

Input: known bits \((Z_a, O_a)\), \((Z_b, O_b)\) of width \(w\).
Output: known bits \((Z_s, O_s)\) of \(a + b \bmod 2^w\).
Precondition: no conflicts in the inputs.
Postcondition: sound (Lemma 17.2.11); on all pairs of 4-bit inputs it equals the best transformer and LLVM's word-parallel computeForAddCarry (checked exhaustively when this lesson was written).
Invariant: before processing bit \(k\), the abstract carry \(c \in \{0, 1, ?\}\) over-approximates the concrete carry into bit \(k\) for every \(a \in \gamma(Z_a, O_a)\), \(b \in \gamma(Z_b, O_b)\).

function KnownAdd(a, b):
    c ← 0;  Zs ← 0;  Os ← 0
    for k in 0 .. w−1:
        x ← Bit(a, k); y ← Bit(b, k)                   # each 0, 1 or ?
        if x, y, c are all known:
            if x ⊕ y ⊕ c = 1: Os[k] ← 1 else: Zs[k] ← 1
        known1 ← number of 1s among the known ones of (x, y, c)
        known0 ← number of 0s among the known ones of (x, y, c)
        c ← (known1 ≥ 2) ? 1 : (known0 ≥ 2) ? 0 : ?     # the majority is decided
    return (Zs, Os)
function Bit(v, k): return Zv[k] ? 0 : Ov[k] ? 1 : ?

Definition 17.2.6 (Demanded bits)

Let the roots be instructions whose results are observable in full (stores, returns, calls, branches, anything with side effects), and let a use of value \(v\) by instruction \(I\) have the operand transfer \(t_{I,k} : \{0,1\}^{w_I} \to \{0,1\}^{w_v}\) mapping the bits of \(I\) that are demanded to the bits of operand \(k\) that can influence them (e.g. trunc to 8 bits: \(t(D) = D \mathbin{\&} \mathtt{0xFF}\); lshr by \(s\): \(t(D) = D \ll s\); add/sub/mul: all bits up to the highest demanded one, since carries only move upward). The demanded bits \(\mathrm{DB}\) are the least solution of \(\mathrm{DB}(v) = \bigcup_{(I, k)\text{ uses } v} t_{I,k}(\mathrm{DB}(I))\), with \(\mathrm{DB}(I)\) = all ones for roots.

Algorithm 17.2.7 (Demanded bits and bit-tracking DCE)

Input: a function in SSA form.
Output: \(\mathrm{DB}(v)\) for every integer value; the function with every non-root value whose \(\mathrm{DB}\) is 0 replaced by 0.
Precondition: the operand transfers are sound in the sense of Theorem 17.2.12.
Postcondition: \(\mathrm{DB}\) is the least solution of Definition 17.2.6; the rewritten function has the same observable behavior (Theorem 17.2.12).
Invariant: \(\mathrm{DB}\) only grows; every value whose users' demands changed since its last visit is on the worklist.

function DemandedBits(F):
    DB[v] ← 0 for all v;  W ← []
    for each root I: DB[I] ← all ones; push I on W
    while W ≠ []:
        I ← pop W
        for each operand k of I that is an instruction v:
            new ← DB[v] | Transfer(I, k, DB[I])        # Definition 17.2.6
            if new ≠ DB[v]: DB[v] ← new; push v on W
    return DB
function BDCE(F):
    DB ← DemandedBits(F)
    for each non-root integer instruction I with DB[I] = 0:
        replace all uses of I by 0; delete I
    drop nsw/nuw/exact on instructions whose operands changed    # they may no longer hold

LVI's query procedure ties ranges to blocks and edges:

Algorithm 17.2.8 (LazyValueInfo query, simplified)

Input: a value \(v\) and a block \(B\) (the query "range of \(v\) at the start of \(B\)").
Output: a wrapped interval \(\mathrm{LV}(v, B)\) (or overdefined = full).
Precondition: SSA form; the cache holds only finished results.
Postcondition: the result contains every value \(v\) can have when control enters \(B\) (Theorem 17.2.13).
Invariant: every (value, block) pair on the stack is being computed; a pair met again while on the stack is answered "full" (cycles are pessimistic).

function LV(v, B):
    if v is a constant: return [v, v+1)
    if (v, B) in Cache: return Cache[(v, B)]
    if (v, B) on Stack: return full                    # a cycle: give up on it
    push (v, B) on Stack
    if v is defined in B:
        R ← Transfer(def(v), LV(operand, B) for each operand)    # Algorithm 17.2.3 etc.
    else if B is the entry: R ← full
    else: R ← ⊔ over predecessors P of B of EdgeValue(v, P, B)
    pop Stack; Cache[(v, B)] ← R; return R
function EdgeValue(v, P, B):
    R ← LV(v, P) restricted to the end of P             # the value leaving P
    if P ends in `br (v pred c), T, F`:
        R ← R ∩ (the set of v satisfying the predicate, or its negation, for the edge to B)
    return R

3. Worked example¶

LazyValueInfo and correlated value propagation¶

The function bucket of the §7 box (after mem2reg):

int bucket(int x) {
  if (x < 0 || x > 1000)
    return -1;
  int q = x / 8;
  int r = x % 8;
  if (x > 2000)
    return 99;
  return q + r;
}

CVP asks LVI for %x at if.end4 (the block after both tests; the x > 2000 test was threaded away by jump-threading in the box) and for the operands of the divisions. The queries unfold as follows (ranges over i32, signed view):

query	how it is answered	result
`LV(%x, entry)`	`%x` is an argument and `entry` is the entry block	full
`EdgeValue(%x, entry → lor.lhs.false)`	full ∩ ¬(`%x <s 0`)	\([0, 2^{31})\)
`LV(%x, lor.lhs.false)`	single predecessor	\([0, 2^{31})\)
`EdgeValue(%x, lor.lhs.false → if.end4)`	\([0, 2^{31})\) ∩ ¬(`%x >s 1000`)	\([0, 1001)\)
`LV(%x, if.end4)`	single predecessor	\([0, 1001)\)
`%div = sdiv %x, 8`	\([0, 1001) \mathbin{/^\sharp} [8, 9)\)	\([0, 126)\)
`%rem = srem %x, 8`	nonnegative dividend, divisor 8	\([0, 8)\)
`%add = add nsw %div, %rem`	Algorithm 17.2.3: \([0+0, 126+8-1) = [0, 133)\)	\([0, 133)\)
`LV(%retval.0, return)`	phi: \([0, 133) \sqcup [-1, 0)\)	\([-1, 133)\)

Every row appears in the print<lazy-value-info> output of the §7 box. CVP then uses them: \([0, 1001)\) is nonnegative, so sdiv/srem become udiv/urem, and it fits in 16 bits, so they are narrowed to i16; x > 2000 on \([0, 1001)\) is false.

ConstantRange arithmetic¶

Algorithm 17.2.3 on the i8 function ranges of the §7 box (SCCP computes these ranges with LLVM's lattice):

value	operation	computation	range
`%a`	`and %x, 15`	known bits give \([0, 16)\)	\([0, 16)\)
`%b`	`add %a, 100`	\([0+100, 16+101-1) = [100, 116)\), size 16	\([100, 116)\)
`%d`	`mul %b, 2`	unsigned \([100 \cdot 2, 115 \cdot 2] = [200, 230]\) fits in 8 bits	\([200, 231)\)
`%e`	`sub %d, 40`	\([160, 191)\)	\([160, 191)\)
`%f`	`lshr %d, 3`	\([25, 29)\)	\([25, 29)\)
`%p`	phi: Union	candidates \([25, 191)\) (size 166) and \([160, 29)\) (wraps, size 125): the smaller	\([160, 29)\)
`%q`	`icmp ult %p, 200`	\([160, 29)\) contains 200…255: not always true	unknown
`%s`	`add %p, zext(%q)`	\([160, 29) + [0, 2) = [160, 30)\), size 126	\([160, 30)\) = `range(i8 -96, 30)`

The union is the lesson: every value of %p lies in \(\{25..28\} \cup \{160..190\}\), entirely below 200, but no single wrapped interval containing it is, so %q cannot be folded. A set of two intervals would have folded it (§6).

Known bits¶

Algorithm 17.2.5 and the rules for shl, or, and on @known (§7 box), all bits written most significant first for the low byte:

value	rule	known zero (low byte)	known one (low byte)
`%a = shl %x, 4`	shifted-in zeros	`00001111`	`00000000`
`%b = or %a, 3`	\(O = O_a \mid 3\), \(Z = Z_a \mathbin{\&} \lnot 3\)	`00001100`	`00000011`
`%c = and %b, 12`	\(Z = Z_b \mid \lnot 12\), \(O = O_b \mathbin{\&} 12\)	`11111111` (all 32 bits)	`00000000`
`%d = and %y, 255`	\(Z = \lnot 255\)	bits 8–31	none
`%e = icmp ult %d, 256`	max value of `%d` is 255 < 256	—	`1` (true)
`%g = add %c, zext %e`	Algorithm 17.2.5 on \(0 + 1\)	all but bit 0	bit 0

%g is fully known: InstCombine replaces the function body by ret i32 1. A ripple step of Algorithm 17.2.5 at bit 0: \(x = 0\) (all of %c known), \(y = 1\), \(c = 0\): sum bit 1, carry 0 (two known zeros), and every higher bit sums \(0 + 0 + 0\).

Demanded bits and bit-tracking DCE¶

Algorithm 17.2.7 on @lowbyte of the §7 box. The root is ret i8 %t, which demands all 8 bits:

step	pop	operand transfers	demanded bits after
1	`%t = trunc %w to i8`	`trunc`: \(\mathtt{0xFF}\)	`%w`: 0xff
2	`%w = or %v, %k`	`or`: same bits for both operands	`%v`: 0xff, `%k`: 0xff
3	`%k = xor %x, 1`	`xor`: same bits	`%x` (argument): 0xff
4	`%v = shl %h, 8`	`shl` by 8: \(\mathtt{0xFF} \gg 8 = 0\)	`%h`: 0 (no change: nothing pushed)

%h and %m are never pushed with a nonzero demand: DB(%h) = DB(%m) = 0. BDCE replaces %h by 0 and deletes %h and %m (the box shows %v = shl i32 0, 8).

Try it

Ch 14's ./course drill widening --seed 3 practices interval iteration with widening, the fixed-point side of range analysis; the tables of this section are reproduced by the opt commands in §7.

4. Invariants and correctness¶

Lemma 17.2.9 (ConstantRange addition is sound)

For wrapped intervals \(A\), \(B\) of width \(w\), \(\mathrm{Add}(A, B)\) of Algorithm 17.2.3 satisfies \(\{\, a + b \mid a \in \gamma(A), b \in \gamma(B) \,\} \subseteq \gamma(\mathrm{Add}(A, B))\).

Proof

Empty and full inputs are immediate. Otherwise let \(n_1 = \lvert A \rvert\), \(n_2 = \lvert B \rvert\), so every \(a \in \gamma(A)\) is \(\ell_1 + i\) with \(0 \leq i < n_1\) and every \(b\) is \(\ell_2 + j\) with \(0 \leq j < n_2\) (Definition 17.2.1). Then \(a + b = (\ell_1 + \ell_2) + (i + j)\) with \(0 \leq i + j \leq n_1 + n_2 - 2\). Case \(n_1 + n_2 - 1 < 2^w\): the set \(\{\ell + k \mid 0 \leq k < n_1 + n_2 - 1\}\) with \(\ell = \ell_1 + \ell_2\) is the interval \([\ell, \ell + n_1 + n_2 - 1)\), and \(\ell + n_1 + n_2 - 1 \equiv (\ell_1 + n_1) + (\ell_2 + n_2) - 1 = u_1 + u_2 - 1 = u\); its size \(n_1 + n_2 - 1 \geq \max(n_1, n_2)\), so the overflow test does not fire and the result \([\ell, u)\) contains every sum. Case \(n_1 + n_2 - 1 \geq 2^w\): then \(R\)'s computed size is \((n_1 + n_2 - 1) \bmod 2^w = n_1 + n_2 - 1 - 2^w \leq n_1 - 1 < n_1\) (as \(n_2 \leq 2^w\)), so \(\lvert R \rvert < \lvert A \rvert\) and the algorithm returns full (the case \(\ell = u\) is size 0 or \(2^w\), also full). Full contains everything.

Lemma 17.2.10 (ConstantRange union is sound, and loses precision)

\(\gamma(A) \cup \gamma(B) \subseteq \gamma(\mathrm{Union}(A, B))\), and there are \(A\), \(B\) with \(\lvert \mathrm{Union}(A, B) \rvert > \lvert \gamma(A) \cup \gamma(B) \rvert\) for every choice of result.

Proof

Union returns a candidate only if its \(\gamma\) contains both sets, or full; either way the inclusion holds. For the second claim take \(A = [25, 29)\), \(B = [160, 191)\) over i8 (the §3 example). A wrapped interval containing 25 and 190 contains either all of \(25..190\) (going up from 25) or all of \(190..255, 0..25\) (going up from 190); the first has at least 166 elements, the second at least 92, while \(\lvert \gamma(A) \cup \gamma(B) \rvert = 4 + 31 = 35\). The minimal candidates are \([25, 191)\) and \([160, 29)\) and LLVM picks the smaller, 125 elements: 90 values that never occur are included.

Lemma 17.2.11 (Known-bits addition is sound)

For all \(a \in \gamma(Z_a, O_a)\) and \(b \in \gamma(Z_b, O_b)\), \((a + b) \bmod 2^w \in \gamma(\mathrm{KnownAdd})\).

Proof

Fix concrete \(a\), \(b\) and let \(c_k\) be the concrete carry into bit \(k\) of the schoolbook addition (\(c_0 = 0\), \(c_{k+1} = \mathrm{maj}(a_k, b_k, c_k)\), sum bit \(s_k = a_k \oplus b_k \oplus c_k\)). Prove the loop invariant by induction on \(k\): the abstract carry \(c\) is either "?" or equal to \(c_k\). Base: \(c = 0 = c_0\). Step: if two of \(x, y, c\) are known 1, then the corresponding concrete bits are 1 (known bits are exact by the definition of \(\gamma\), and the carry by hypothesis), so \(c_{k+1} = 1\); symmetrically for 0; otherwise \(c\) becomes "?". The algorithm sets a sum bit only when \(x, y, c\) are all known, in which case they equal \(a_k, b_k, c_k\) and the set bit is \(s_k\). So every known output bit equals the corresponding bit of \(a + b\): \(a + b \in \gamma(Z_s, O_s)\).

Theorem 17.2.12 (Bit-tracking DCE preserves behavior)

Assume each operand transfer is sound in the sense: if two values of operand \(k\) agree on the bits \(t_{I,k}(D)\), then the results of \(I\) agree on the bits \(D\) (other operands fixed). Then replacing every non-root value whose demanded bits are 0 by any value of its type leaves every root's inputs unchanged on every execution; in particular BDCE preserves observable behavior.

Proof

Compare an execution of the original program with the execution of the rewritten one on the same input, step by step, and prove by induction on the number of executed instructions that every executed value \(v\) agrees between the two runs on the bits \(\mathrm{DB}(v)\). A replaced value has \(\mathrm{DB}(v) = 0\): agreement on no bits holds trivially. For any other instruction \(I\) with operands \(v_1, \dots\): by the induction hypothesis they agree on \(\mathrm{DB}(v_k) \supseteq t_{I,k}(\mathrm{DB}(I))\) (the least solution of Definition 17.2.6 is closed under the equation), so by the transfer property applied one operand at a time, the results agree on \(\mathrm{DB}(I)\). Roots demand all bits, so their operands agree completely; hence stores, calls, returns and branches behave identically, and so does control flow. Flags such as nsw are dropped because a changed undemanded operand bit can make them false (they would then produce poison; Ch 13).

Theorem 17.2.13 (LVI is sound)

If Algorithm 17.2.8 returns \(R\) for \((v, B)\), every execution that enters \(B\) after defining \(v\) has \(v \in \gamma(R)\).

Proof

By induction on the recursion (the stack gives a well-founded order on finished queries). A cycle answer is full, trivially sound. For \(v\) defined in \(B\), soundness of the transfer functions (Lemma 17.2.9 and its siblings) applied to sound operand ranges. For a join, control enters \(B\) from some predecessor \(P\); the value leaving \(P\) is in \(\gamma(\mathrm{LV}(v, P))\) by induction, and it satisfies the branch predicate that selected the edge \(P \to B\), so it lies in the intersection EdgeValue computes, which is contained in the join.

What breaks it. LVI is sound but not a fixed point: on cycles it answers "full" instead of iterating, so it is less precise than SCCP-with-ranges on loops (a loop counter that SCCP bounds after widening is overdefined for LVI). KnownBits' computeKnownBits stops at a recursion depth (6 in LLVM 23) and returns "unknown" beyond it: sound, not complete.

5. Complexity¶

Variables: \(w\) bit width, \(I\) instructions, \(U\) uses, \(n\) blocks, \(d\) the recursion depth limit of computeKnownBits.

Technique	Time (worst)	Time (typical)	Space	Justification
LVI query + CVP	\(O(n \cdot I)\) cache entries, each a join over predecessors; capped at 500 stack steps per query	a few cache hits per query	\(O(n \cdot I)\) ranges	one entry per (value, block); `MaxProcessedPerValue = 500` bounds a query [LLVM-LVI]
ConstantRange ops	\(O(1)\) `APInt` operations for add/sub/union; mul and div compute several candidate ranges	\(O(1)\)	\(O(w)\) bits	Algorithm 17.2.3 is straight-line
KnownBits query	\(O(2^d)\) per query (binary operators recurse into two operands)	small: most chains are short	\(O(w)\)	recursion tree of depth \(\leq d\)
DemandedBits + BDCE	\(O(w \cdot U)\) transfer applications	linear	\(O(w \cdot I)\)	each demand mask only grows, at most \(w\) times per value (the lattice height)

Pathological case for ConstantRange: the union of \(k\) singletons \(\{0\}, \{2\}, \dots, \{2(k-1)\}\) joined by one phi gives \([0, 2k-1)\), size \(2k - 1\) for \(k\) values; with singletons spread over the whole space (\(\{0, 64, 128, 192\}\) over i8) the best single interval has 193 elements for 4 values, and a following comparison can never be folded. At scale: CVP and LVI are among LLVM's more expensive scalar passes on huge functions precisely because of the per-block cache; the 500-step cap exists for that reason (see the comment above MaxProcessedPerValue in [LLVM-LVI]).

Multi-range / sets of intervals — GCC's Ranger represents a value as a union of up to several subranges (irange) [GCC-RANGER]; LLVM's ConstantRangeList exists for a few uses. Trade-off: folds the %q of §3, costs more per operation.
Relational and symbolic ranges — ranges relative to other values (\(i < n\)) instead of constants (octagons, Ch 14 Lesson 14.7); LLVM's ScalarEvolution does symbolic ranges for loops (Ch 18). Trade-off: precision for loop bounds, cubic domains.
Fixed-point range analysis — SCCP with the constantrange lattice iterates to a fixed point with widening after MaxNumRangeExtensions [LLVM-SCCP]; LVI instead answers on demand with pessimistic cycles. Trade-off: loops vs. per-block, per-edge precision.
Combined domains — LLVM derives ranges from known bits and vice versa (ConstantRange::fromKnownBits, KnownBits::makeConstant); the reduced product of the two domains is more precise than either (Ch 14 Lesson 14.7 §6).
Demanded elements — the same backward analysis over vector lanes (SimplifyDemandedVectorElts in InstCombine). Trade-off: another dimension of masks.
Assumptions and metadata — llvm.assume, !range metadata, noundef and range() attributes feed all four analyses; LLVM 23 writes range() return attributes after SCCP (the Lesson 17.1 box).

7. In real compilers¶

LazyValueInfo and correlated value propagation¶

LLVM: llvm/lib/Analysis/LazyValueInfo.cpp — LazyValueInfoImpl::solve (the stack, the 500-step cap), solveBlockValue, getEdgeValue (branch constraints) [LLVM-LVI]; llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp — narrowSDivOrSRem, processUDivOrURem [LLVM-CVP]. GCC's counterpart is Ranger (gcc/gimple-range.cc, gimple_ranger::range_of_stmt) with multi-ranges, used by VRP and jump threading [GCC-RANGER].

LVI's per-block ranges and what CVP does with them

Reproduce (clang 23.1.2, opt 23.1.2):

cat > cvp.c <<'EOF'
int bucket(int x) {
  if (x < 0 || x > 1000)
    return -1;
  int q = x / 8;
  int r = x % 8;
  if (x > 2000)
    return 99;
  return q + r;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm cvp.c -o cvp.O0.ll
opt -passes=mem2reg -S cvp.O0.ll -o cvp.ll
opt -passes='jump-threading,print<lazy-value-info>' -disable-output cvp.ll 2>&1 | grep -E "LatticeVal for: '(i32 %x|  %div|  %rem|  %add|  %retval)" 
opt -passes=correlated-propagation -S cvp.ll | sed -n '/^if.end:/,/^if.then3/p'

Output:

; LatticeVal for: 'i32 %x' is: overdefined
; LatticeVal for: 'i32 %x' is: constantrange<0, -2147483648>
; LatticeVal for: 'i32 %x' is: constantrange<0, 1001>
; LatticeVal for: '  %div = sdiv i32 %x, 8' in BB: '%if.end4' is: constantrange<0, 126>
; LatticeVal for: '  %rem = srem i32 %x, 8' in BB: '%if.end4' is: constantrange<0, 8>
; LatticeVal for: '  %add = add nsw i32 %div, %rem' in BB: '%if.end4' is: constantrange<0, 133>
; LatticeVal for: 'i32 %x' is: overdefined
; LatticeVal for: '  %retval.0 = phi i32 [ %add, %if.end4 ], [ -1, %entry ], [ -1, %lor.lhs.false ]' in BB: '%return' is: constantrange<-1, 133>
if.end:                                           ; preds = %lor.lhs.false
  %div1.lhs.trunc = trunc i32 %x to i16
  %div12 = udiv i16 %div1.lhs.trunc, 8
  %div1.zext = zext i16 %div12 to i32
  %rem3.lhs.trunc = trunc i32 %x to i16
  %rem34 = urem i16 %rem3.lhs.trunc, 8
  %rem3.zext = zext i16 %rem34 to i32
  br i1 false, label %if.then3, label %if.end4

if.then3:                                         ; preds = %if.end

What to notice: the ranges of %x per block are the §3 table: overdefined in entry, \([0, 2^{31})\) after x < 0 failed, \([0, 1001)\) after x > 1000 failed. CVP turns the signed divisions into unsigned 16-bit ones and the x > 2000 test into br i1 false (jump threading removed it in the first run). The print<lazy-value-info> printer only shows what a client already queried, which is why the first command runs jump-threading before it.

ConstantRange arithmetic¶

LLVM: llvm/lib/IR/ConstantRange.cpp — ConstantRange::add, ConstantRange::multiply, ConstantRange::unionWith [LLVM-ConstantRange]. SCCP's range lattice, LVI, InstCombine and the range() attribute all use it.

ConstantRange through SCCP: flags, ranges, and a lossy union

Reproduce (opt 23.1.2):

cat > cr.ll <<'EOF'
define i8 @ranges(i8 %x, i1 %c) {
entry:
  %a = and i8 %x, 15          ; [0, 16)
  %b = add i8 %a, 100         ; [100, 116)
  %d = mul i8 %b, 2           ; [200, 231) as unsigned; wraps as signed
  br i1 %c, label %l, label %r
l:
  %e = sub i8 %d, 40          ; [160, 191)
  br label %j
r:
  %f = lshr i8 %d, 3          ; [25, 29)
  br label %j
j:
  %p = phi i8 [ %e, %l ], [ %f, %r ]
  %q = icmp ult i8 %p, 200    ; always true: both ranges lie below 200
  %z = zext i1 %q to i8
  %s = add i8 %p, %z
  ret i8 %s
}
EOF
opt -passes=sccp -S cr.ll | sed -n '/^define/,/^}/p'

Output:

define range(i8 -96, 30) i8 @ranges(i8 %x, i1 %c) {
entry:
  %a = and i8 %x, 15
  %b = add nuw nsw i8 %a, 100
  %d = mul nuw i8 %b, 2
  br i1 %c, label %l, label %r

l:                                                ; preds = %entry
  %e = sub nuw nsw i8 %d, 40
  br label %j

r:                                                ; preds = %entry
  %f = lshr i8 %d, 3
  br label %j

j:                                                ; preds = %r, %l
  %p = phi i8 [ %e, %l ], [ %f, %r ]
  %q = icmp ult i8 %p, -56
  %z = zext i1 %q to i8
  %s = add nsw i8 %p, %z
  ret i8 %s
}

What to notice: the ranges proved nuw/nsw on %b, %d and %e (no wrap within the range), and the return range range(i8 -96, 30) is \([160, 30)\), the §3 table's last row. The comment in the input is wrong: %q is not folded, because the union at %p had to wrap around (Lemma 17.2.10). -56 is how LLVM prints 200 as a signed i8.

Known bits¶

LLVM: llvm/lib/Support/KnownBits.cpp — KnownBits::computeForAddSub and the static computeForAddCarry, which computes the result of Algorithm 17.2.5 word-parallel from the minimum and maximum possible sums [LLVM-KnownBits]; llvm/lib/Analysis/ValueTracking.cpp — computeKnownBits, the recursive query [LLVM-ValueTracking]. GCC tracks the same facts as "nonzero bits" masks next to its ranges.

InstCombine folds a function from known bits alone

Reproduce (opt 23.1.2):

cat > kb.ll <<'EOF'
define i32 @known(i32 %x, i32 %y) {
  %a = shl i32 %x, 4          ; low 4 bits are zero
  %b = or i32 %a, 3           ; low 4 bits are 0011
  %c = and i32 %b, 12         ; bits 2-3 of 0011 are zero: always 0
  %d = and i32 %y, 255
  %e = icmp ult i32 %d, 256   ; %d < 256 always
  %f = zext i1 %e to i32
  %g = add i32 %c, %f
  ret i32 %g
}
EOF
opt -passes=instcombine -S kb.ll | sed -n '/^define/,/^}/p'

Output:

define i32 @known(i32 %x, i32 %y) {
  ret i32 1
}

What to notice: no value here is a constant for SCCP (%x and %y are unknown), yet every bit of %c is known zero and %e is known true: the known-bits domain is incomparable with the constant and range domains. The table in §3 follows InstCombine's reasoning bit by bit.

Demanded bits and bit-tracking DCE¶

LLVM: llvm/lib/Analysis/DemandedBits.cpp — DemandedBits::determineLiveOperandBits holds the operand transfers of Definition 17.2.6 [LLVM-DemandedBits]; llvm/lib/Transforms/Scalar/BDCE.cpp — bitTrackingDCE [LLVM-BDCE]. InstCombine has its own forward/backward variant, SimplifyDemandedBits.

print and bdce

Reproduce (opt 23.1.2):

cat > bdce.ll <<'EOF'
define i8 @lowbyte(i32 %x, i32 %y) {
  %m = mul i32 %x, %y         ; its low 24 bits never reach the result
  %h = lshr i32 %m, 24
  %k = xor i32 %x, 1          ; this one reaches it
  %v = shl i32 %h, 8          ; bits 8 and up: truncated away
  %w = or i32 %v, %k
  %t = trunc i32 %w to i8
  ret i8 %t
}
EOF
opt -passes='print<demanded-bits>' -disable-output bdce.ll 2>&1 | grep -v ' in ' | sort
opt -passes=bdce -S bdce.ll | sed -n '/^define/,/^}/p'

Output:

DemandedBits: 0x0 for   %h = lshr i32 %m, 24
DemandedBits: 0x0 for   %m = mul i32 %x, %y
DemandedBits: 0xff for   %k = xor i32 %x, 1
DemandedBits: 0xff for   %t = trunc i32 %w to i8
DemandedBits: 0xff for   %v = shl i32 %h, 8
DemandedBits: 0xff for   %w = or i32 %v, %k
Printing analysis 'Demanded Bits Analysis' for function 'lowbyte':
define i8 @lowbyte(i32 %x, i32 %y) {
  %k = xor i32 %x, 1
  %v = shl i32 0, 8
  %w = or i32 %v, %k
  %t = trunc i32 %w to i8
  ret i8 %t
}

What to notice: (the printer's order follows a hash map, so the command sorts it.) The demands are the §3 trace: 0xff flows back from the trunc, shl by 8 turns it into 0 for %h, and nothing reaches %m. BDCE replaced %h by 0 and deleted %h and %m — a multiplication removed although its result is used, because none of its bits matter.

Find where LLVM does it. In llvm/lib/Analysis/LazyValueInfo.cpp, find the constant that bounds how many (block, value) pairs one query may process before LVI gives up and caches "overdefined". What is its name and value? (Quiz llvm-where-lvi-cap.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
LazyValueInfo + CVP	Per-block, per-edge ranges (branch facts); pessimistic on cycles	demand-driven, cached per (value, block); capped at 500 steps	Ranges on request; rewrites divisions, flags, compares	High (cache invalidation, edge constraints)	CVP, jump threading (LLVM); Ranger/VRP (GCC)
ConstantRange arithmetic	Wrapped intervals; sound transformers; one interval per value (union loses)	\(O(1)\) per operation	Ranges printed as `range(...)`, `!range`	Medium (every opcode, signed/unsigned views)	SCCP's lattice, LVI, InstCombine, attributes
Known bits	Per-bit facts; incomparable with ranges; best transformer for add	query \(O(2^d)\) with depth cap \(d\)	Zero/one masks	Low per rule, many rules	InstCombine, alignment, SelectionDAG
Demanded bits + BDCE	Backward; removes computations of undemanded bits	\(O(w \cdot U)\)	Masks per value	Low	BDCE, InstCombine's SimplifyDemandedBits, vectorizer width

Choose LVI + CVP when branch conditions constrain values (bounds checks, guarded divisions) and you need facts at specific blocks without solving the whole function. Choose ConstantRange as the value domain of any range analysis over machine integers: it is the right shape for modular arithmetic. Choose known bits when code manipulates bits (masks, shifts, alignment): ranges cannot see them. Choose demanded bits when values are truncated or masked later: it is the only one of the four that runs backwards.

9. Assessment¶

Quiz: lvi-edge-range, llvm-where-lvi-cap (tag lvi-cvp); range-add, range-union-loss (tag constant-range); known-bits-and, known-bits-vs-range (tag known-bits); demanded-bits-shl, bdce-safety (tag demanded-bits).
Drill: no dedicated drill: the domains are exercised by Ch 14's widening drill (interval iteration) and by the quiz's computational questions (range addition, union, known bits of and, demanded bits through a shift), each with a fresh instance. The four techniques have no small closed-form traces beyond those, which the quiz covers.
Flashcards: tags lvi-cvp, constant-range, known-bits, demanded-bits.
Exercises: none required; ★ extend your pebble-sccp lattice with ConstantRange (a stretch goal in exercises.md).

References¶

See the chapter references.

Lesson 17.2 — Range and bit-level analyses: LVI, ConstantRange, KnownBits, DemandedBits¶

1. Problem and motivation¶

LazyValueInfo and correlated value propagation¶

ConstantRange arithmetic¶

Known bits¶

Demanded bits and bit-tracking DCE¶

2. Definitions and algorithms¶

3. Worked example¶

LazyValueInfo and correlated value propagation¶

ConstantRange arithmetic¶

Known bits¶

Demanded bits and bit-tracking DCE¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

7. In real compilers¶

LazyValueInfo and correlated value propagation¶

ConstantRange arithmetic¶

Known bits¶

Demanded bits and bit-tracking DCE¶

8. Comparison¶

9. Assessment¶

References¶