Lesson 13.7 — Local strength reduction: multiplication and division by constants

Techniques: multiplication by constants (shift-and-add decompositions, signed-digit recoding, factoring; Bernstein 1986); division by invariant integers (Granlund and Montgomery 1994; Warren's Hacker's Delight, ch. 10) · Pebble implements: the power-of-two cases in pebble-peephole (rules R10–R14, exercise E2); the general cases are left to LLVM's back end, which pebblec uses · Lab: ch13-rewrite-check verifies magic-number rewrites exhaustively on small widths (Part B) · Prerequisites: Lesson 13.2 · Time: 4 hours

An integer division costs 20–90 cycles on current x86-64 cores; a multiplication about 3; a shift or an add 1. So compilers replace x * 10 by (x + 4x) * 2 and — far less obviously — x / 7 by a multiplication by the "magic number" \(\lceil 2^{35} / 7 \rceil\) followed by a shift. This is local strength reduction: replacing an expensive operation by a cheaper sequence, one instruction at a time. (Strength reduction of induction variables across loop iterations is a different technique, in Ch 18.) This lesson gives the algorithms and, for division, a complete proof of when a multiply-and-shift computes \(\lfloor x / d \rfloor\) exactly — the theorem every compiler's divider relies on.

1. Problem and motivation

Given mul x, C or udiv/sdiv/urem/srem x, d with a constant, produce an equivalent sequence of cheaper instructions. The IR keeps udiv x, 7 (it is simpler to analyze), and the back end expands it during instruction selection: in LLVM, TargetLowering::BuildUDIV/BuildSDIV in SelectionDAG and the GlobalISel combiner; in GCC, expand_divmod in expmed.cc. Pebble's pebblec relies on LLVM for this; its own pebble-peephole handles the power-of-two cases, which are canonicalizations as well (R10–R14).

Multiplication by constants

Every constant is a sum of powers of two, so x * C is a sum of shifted copies of x. Bernstein studied the optimal decomposition into shifts, adds and subtracts as a search problem and gave the algorithm that most compilers adapted [Ber86]; signed-digit recoding (non-adjacent form, Reitwiesner 1960 [Rei60]) reduces the number of add/subtract operations, and factoring \(C\) (e.g. \(45 = 9 \times 5\)) exploits instructions such as x86 lea, which computes a + b·{1,2,4,8} in one instruction.

Division by invariant integers

Division by a constant \(d\) can be replaced by multiplying with an approximation \(m \approx 2^{k}/d\) and taking the high bits. The difficulty is choosing \(m\) and \(k\) so that the result is exact for every \(N\)-bit dividend. Granlund and Montgomery gave the construction and proof for unsigned and signed division, and implemented it in GCC [GM94]; Warren's Hacker's Delight gives the algorithms that LLVM's DivisionByConstantInfo cites [War13, ch. 10]. Magenheimer et al. (1988) had earlier described the technique for HP PA-RISC.

2. Definitions and algorithms

Multiplication by constants

Definition 13.7.1 (Shift-add chain and signed-digit representation)

A shift-add chain for \(C\) is a sequence \(y_0 = x\), \(y_j = (y_a \ll s) \pm y_b\) or \(y_j = y_a \ll s\) (\(a, b < j\)), whose last element equals \(C \cdot x\) for every \(x\) (modulo \(2^N\)). Its cost is the number of additions and subtractions (shifts are often free inside lea or ARM shifted operands). A signed-digit representation of \(C\) is \(C = \sum_{i} c_i 2^i\) with \(c_i \in \{-1, 0, 1\}\); its weight is the number of non-zero digits. The non-adjacent form (NAF) is the one with \(c_i c_{i+1} = 0\) for all \(i\).

Algorithm 13.7.2 (Multiplication by a constant via the NAF)

• Input: \(C \ge 1\) and a register holding \(x\) (\(N\)-bit).
• Output: a shift-add chain computing \(C \cdot x \bmod 2^N\).
• Precondition: none (\(C\) may be any non-zero constant; negative \(C\) multiplies by \(-C\) and negates).
• Postcondition: the chain has weight\((\mathrm{NAF}(C)) - 1\) additions/subtractions (Proposition 13.7.8).
• Invariant: in NAF, \(C_{\mathrm{orig}} = \sum_{i < j} c_i 2^i + 2^j \cdot c\) after \(j\) iterations.

function NAF(C):                       # digits c_0, c_1, ... least significant first
    digits ← []
    while C > 0:
        if C is odd:
            c ← 2 − (C mod 4)          # +1 if C ≡ 1 (mod 4), −1 if C ≡ 3 (mod 4)
            C ← C − c
        else:
            c ← 0
        digits.append(c);  C ← C / 2
    return digits

function MulByConst(x, C):
    acc ← none
    for i, c in enumerate(NAF(C)) with c ≠ 0, from the most significant digit down:
        term ← x << i
        acc ← term if acc = none else (acc + term if c = +1 else acc − term)
    return acc

Production compilers compare this against factoring \(C\) and against a single mul, with a per-target cost model (Bernstein's search [Ber86]; LLVM X86ISelLowering.cpp combineMul, TargetLowering::decomposeMulByConstant).

Division by invariant integers

Definition 13.7.3 (Magic multiplier)

Let \(N \ge 1\), \(1 \le d < 2^N\), \(\ell \ge 0\). The magic multiplier for \((d, N, \ell)\) is \(m = \lceil 2^{N+\ell} / d \rceil\), and its error is \(e = m d - 2^{N+\ell}\), so \(0 \le e < d\). The candidate quotient of \(0 \le x < 2^N\) is \(\hat q(x) = \lfloor m x / 2^{N+\ell} \rfloor\), computed as the high \(N\) bits of the \(2N\)-bit product \(m x\) shifted right by \(\ell\) (when \(m < 2^N\)).

Theorem 13.7.4 (Granlund–Montgomery)

If \(2^{N+\ell} \le m d \le 2^{N+\ell} + 2^{\ell}\), then \(\lfloor m x / 2^{N+\ell} \rfloor = \lfloor x / d \rfloor\) for every integer \(0 \le x < 2^N\). For \(\ell = \lceil \log_2 d \rceil\) the multiplier \(m = \lceil 2^{N+\ell}/d \rceil\) satisfies the hypothesis and \(m < 2^{N+1}\).

Proof

Write \(m d = 2^{N+\ell} + e\) with \(0 \le e \le 2^{\ell}\), and \(x = q d + r\) with \(0 \le r \le d - 1\). Then

\[ \frac{m x}{2^{N+\ell}} = \frac{x (2^{N+\ell} + e)}{d\, 2^{N+\ell}} = \frac{x}{d} + \frac{e x}{d\, 2^{N+\ell}} = q + \frac{r}{d} + \varepsilon, \qquad 0 \le \varepsilon = \frac{e x}{d\, 2^{N+\ell}} < \frac{2^{\ell}\, 2^{N}}{d\, 2^{N+\ell}} = \frac{1}{d}. \]

Hence \(q \le m x / 2^{N+\ell} < q + (d-1)/d + 1/d = q + 1\), so the floor is \(q\). For the second claim: with \(\ell = \lceil \log_2 d \rceil\), \(d \le 2^{\ell}\), and \(m = \lceil 2^{N+\ell}/d \rceil\) has \(0 \le e = md - 2^{N+\ell} \le d - 1 < 2^{\ell}\). Since \(d > 2^{\ell - 1}\) (or \(d = 1\), \(\ell = 0\), \(m = 2^N\)), \(2^{N+\ell}/d < 2^{N+1}\), and \(m < 2^{N+1}\) because \(\ell \le N\) excludes the only way the ceiling could reach \(2^{N+1}\) (it would need \(d(2^{N+1} - 1) < 2^{N+\ell}\), i.e. \(d \le 2^{\ell-1}\)).

Definition 13.7.5 (\(n_c\))

\(n_c = 2^N - 1 - (2^N \bmod d)\) is the largest \(x < 2^N\) with \(x \bmod d = d - 1\). (For \(d = 7\), \(N = 32\): \(2^{32} \bmod 7 = 4\), \(n_c = 4294967291\).)

Theorem 13.7.6 (Exact criterion)

With \(m\) and \(e\) as in Definition 13.7.3, \(\lfloor m x / 2^{N+\ell} \rfloor = \lfloor x / d \rfloor\) for every \(0 \le x < 2^N\) if and only if \(e \cdot n_c < 2^{N+\ell}\).

Proof

As in Theorem 13.7.4, for \(x = q d + r\), \(m x / 2^{N+\ell} = q + (r + e x / 2^{N+\ell}) / d\), and \(e x \ge 0\), so the floor equals \(q\) iff \(r + e x / 2^{N+\ell} < d\), i.e.

\[ e\, x < (d - r)\, 2^{N+\ell}. \qquad (\ast) \]

(⇒) Take \(x = n_c\), \(r = d - 1\): \((\ast)\) says \(e\, n_c < 2^{N+\ell}\). (⇐) Let \(t = 2^N \bmod d\), so the \(x < 2^N\) with \(x > n_c\) are \(n_c + 1, \dots, n_c + t\), with remainders \(0, \dots, t - 1\). Case \(x \le n_c\): \(e x \le e\, n_c < 2^{N+\ell} \le (d - r)\, 2^{N+\ell}\). Case \(x > n_c\): then \(r \le t - 1 \le d - 2\), so \(d - r \ge 2\), and \(x \le n_c + t\). Since \(n_c \ge d - 1\) (as \(d - 1 < 2^N\)) and \(t \le d - 1\), the hypothesis gives \(e\, t \le e\,(d - 1) \le e\, n_c < 2^{N+\ell}\). Hence \(e x \le e\, n_c + e\, t < 2 \cdot 2^{N+\ell} \le (d - r)\, 2^{N+\ell}\). So \((\ast)\) holds for every \(x\).

Theorem 13.7.4 is the special case \(e \le 2^{\ell}\) (then \(e\, n_c < 2^{\ell} 2^{N}\)); the exact criterion sometimes allows a smaller \(\ell\) (for \(d = 35\), \(N = 8\): \(\ell = 5\) instead of 6).

Algorithm 13.7.7 (Unsigned division by a constant)

• Input: \(N\), a constant \(d\) with \(2 \le d < 2^N\) not a power of two, a register \(x\).
• Output: a multiply/shift sequence computing \(\lfloor x / d \rfloor\) for every \(N\)-bit \(x\).
• Precondition: the machine has an \(N \times N \to 2N\) unsigned multiply (mulhu: the high half).
• Postcondition: the sequence's result equals \(\lfloor x/d \rfloor\) (Theorems 13.7.6 and 13.7.9).
• Invariant: in the search, every \(\ell' < \ell\) tried so far fails the criterion.

function Magic(d, N):
    n_c ← 2^N − 1 − (2^N mod d)
    for ℓ in 0, 1, 2, ...:
        m ← ⌈2^(N+ℓ) / d⌉;  e ← m·d − 2^(N+ℓ)
        if e · n_c < 2^(N+ℓ): return (m, ℓ)          # Theorem 13.7.6; ℓ ≤ ⌈log2 d⌉ always works

function EmitUDiv(x, d, N):
    (m, ℓ) ← Magic(d, N)
    if m < 2^N:
        return mulhu(x, m) >> ℓ                        # one multiply, one shift
    else:                                              # m has N+1 bits: m = 2^N + m'
        h ← mulhu(x, m − 2^N)
        return (((x − h) >> 1) + h) >> (ℓ − 1)         # the "add" fix-up, no overflow

EmitUDiv for \(N\)-bit \(x\) on a machine with \(2N\)-bit multiplies can instead compute \((x \cdot (m \ll (2N - N - \ell))) \gg 2N\) with a \(2N \times 2N\) multiply (LLVM's "widen" variant, box in §7). The drill magic-division computes Magic.

3. Worked example

Multiplication by constants

x * 45 with Algorithm 13.7.2: NAF(45), least significant digit first:

step	\(C\)	\(C \bmod 4\)	digit \(c\)	\(C\) after
1	45	1	+1	(45 − 1)/2 = 22
2	22	— (even)	0	11
3	11	3	−1	(11 + 1)/2 = 6
4	6	—	0	3
5	3	3	−1	(3 + 1)/2 = 2
6	2	—	0	1
7	1	1	+1	0

So \(45 = 2^6 - 2^4 - 2^2 + 1\) (weight 4) and MulByConst emits (x<<6) − (x<<4) − (x<<2) + x: 3 add/subtract operations — the same as the binary \(101101_2\) (weight 4). Factoring does better on x86: \(45 = 9 \times 5\), two lea instructions (lea r, [x + 8x]; lea r, [r + 4r]), which clang emits (box in §7). For \(7 = 2^3 - 1\) the NAF has weight 2 (one subtraction), binary \(111_2\) weight 3 (two additions).

Division by invariant integers

Magic(7, 32) (the magic-division drill's trace), \(n_c = 4294967291\):

\(\ell\)	\(m\)	\(e = 7m - 2^{32+\ell}\)	\(e\,n_c\)	\(2^{32+\ell}\)	GM: \(e \le 2^\ell\)?	exact: \(e n_c < 2^{32+\ell}\)?
0	613 566 757	3	12 884 901 873	4 294 967 296	no	no
1	1 227 133 514	6	25 769 803 746	8 589 934 592	no	no
2	2 454 267 027	5	21 474 836 455	17 179 869 184	no	no
3	4 908 534 053	3	12 884 901 873	34 359 738 368	yes	yes

\(m = 4\,908\,534\,053 = 2^{32} + 613\,566\,757\) needs 33 bits, so EmitUDiv uses the fix-up with \(m' = 613\,566\,757\) (0x24924925): for \(x = 100\), \(h = \lfloor 100 \cdot 613566757 / 2^{32} \rfloor = 14\), \(((100 - 14) \gg 1) + 14 = 57\), \(57 \gg 2 = 14 = \lfloor 100/7 \rfloor\). This is GCC's sequence exactly (imul 613566757; shr 32; sub; shr; add; shr 2, box in §7). For \(d = 3\): \(\ell = 1\), \(m = 2\,863\,311\,531\) (0xAAAAAAAB) \(< 2^{32}\), total shift 33; for \(d = 10\): \(\ell = 3\), \(m\) = 0xCCCCCCCD, shift 35 — both in the box.

Signed division (Warren's algorithm, [War13, ch. 10], Figure 10-1) for \(d = 7\), \(N = 32\) gives \(M = -1\,840\,700\,269\) (0x92492493) and \(s = 2\): \(q = \mathrm{mulhs}(M, x) + x\) (because \(M < 0 < d\)), then \(q \gg_s 2\), then add 1 if negative. For \(x = -100\): \(\mathrm{mulhs} = \lfloor -1840700269 \cdot (-100) / 2^{32} \rfloor = 42\), \(+ x = -58\), \(-58 \gg_s 2 = -15\), \(+1 = -14 = \mathrm{trunc}(-100/7)\).

Try it

./course drill magic-division --seed 2 --difficulty medium --solution traces Magic for a random divisor and width; --difficulty hard asks for Warren's signed \(M\) and \(s\).

4. Invariants and correctness

Multiplication by constants

Proposition 13.7.8 (NAF: correctness and weight bound)

NAF(C) terminates, returns digits with \(\sum_i c_i 2^i = C\) and \(c_i c_{i+1} = 0\), and has at most \(\lceil (b + 1)/2 \rceil\) non-zero digits, where \(b\) is the bit length of \(C\). MulByConst computes \(C x \bmod 2^N\) with (weight \(- 1\)) additions or subtractions.

Proof

Invariant and termination: initially \(C_{\mathrm{orig}} = 2^0 C\). An iteration chooses \(c\) with \(C - c\) even (for odd \(C\), \(c = \pm 1\) makes \(C - c\) even; for even \(C\), \(c = 0\)), so \(C = c + 2 \cdot (C - c)/2\) and the invariant is maintained with \(j + 1\). \(C\) decreases (for \(C \ge 2\), \((C - c)/2 \le (C + 1)/2 < C\); for \(C = 1\), \(c = +1\) and the next \(C\) is 0), so the loop ends with \(C = 0\) and the sum equals \(C_{\mathrm{orig}}\). Non-adjacency: after a non-zero digit, \(C - c \equiv 0 \pmod 4\) (by the choice \(c = 2 - (C \bmod 4)\) gives \(C - c \in \{C - 1, C + 1\}\) divisible by 4), so the next \(C = (C - c)/2\) is even and the next digit is 0. Weight: non-zero digits are separated by zeros, and the NAF has at most \(b + 1\) digits (the top carry can add one), hence at most \(\lceil (b+1)/2 \rceil\) non-zero ones. Chain: each non-zero digit after the first contributes one addition or subtraction of \(x \ll i\), and \(\sum c_i (x \ll i) = C x\) in \(\mathbb{Z}/2^N\mathbb{Z}\) because shifting multiplies by \(2^i\) modulo \(2^N\).

Division by invariant integers

Theorem 13.7.9 (The add fix-up computes the 33-bit multiply without overflow)

Let \(m = 2^N + m'\) with \(0 \le m' < 2^N\), \(\ell \ge 1\), and \(h = \lfloor m' x / 2^N \rfloor\). Then for \(0 \le x < 2^N\): \(\big\lfloor \big( \lfloor (x - h)/2 \rfloor + h \big) / 2^{\ell - 1} \big\rfloor = \lfloor m x / 2^{N+\ell} \rfloor\), and no intermediate value exceeds \(N\) bits.

Proof

\(m x / 2^N = x + m' x / 2^N\), and for any real \(y\) and integer \(a\), \(\lfloor (a + y) / 2^{\ell} \rfloor = \lfloor (a + \lfloor y \rfloor) / 2^{\ell} \rfloor\) (the fractional part of \(y\) cannot carry across a multiple of \(2^\ell\) from an integer). So \(\lfloor m x / 2^{N+\ell} \rfloor = \lfloor (x + h) / 2^{\ell} \rfloor\). Since \(m' < 2^N\), \(h \le x\), so \(x - h \ge 0\), and \(\lfloor (x - h)/2 \rfloor + h = \lfloor (x + h)/2 \rfloor\) (add the integer \(h\) inside the floor). Finally \(\lfloor \lfloor z/2 \rfloor / 2^{\ell - 1} \rfloor = \lfloor z / 2^{\ell} \rfloor\) for integers \(z \ge 0\). Bounds: \(0 \le x - h < 2^N\), and \(\lfloor (x+h)/2 \rfloor \le x < 2^N\).

Theorem 13.7.10 (Signed division by a constant)

For \(2 \le \lvert d \rvert < 2^{N-1}\), Warren's algorithm returns \(M\) (an \(N\)-bit signed value) and \(s \ge 0\) such that for every \(-2^{N-1} \le x < 2^{N-1}\) the sequence \(q = \mathrm{mulhs}(M, x)\); \(q \mathrel{+}= x\) if \(d > 0 > M\); \(q \mathrel{-}= x\) if \(d < 0 < M\); \(q \gets q \gg_s s\); \(q \mathrel{+}= 1\) if \(q < 0\), computes \(\mathrm{trunc}(x / d)\) (division rounding toward zero, as sdiv).

Proof sketch (full proof: [War13, ch. 10]; [GM94, §5])

Take \(d > 0\) (negative divisors negate the result). Let \(\hat M\) be the exact multiplier the algorithm represents: \(\hat M = M\) if \(M \ge 0\), and \(\hat M = M + 2^N\) if the stored \(M\) is negative (the "\(q \mathrel{+}= x\)" step adds the missing \(2^N x / 2^N = x\), as in Theorem 13.7.9). The search chooses the smallest \(p = N + s\) with \(\hat M = \lceil 2^{p} / d \rceil\) and an error \(\hat M d - 2^p\) small enough — the signed analogue of Theorem 13.7.6, with the extreme dividends \(\pm 2^{N-1}\) in the role of \(n_c\). Then, as in Theorem 13.7.4: for \(0 \le x < 2^{N-1}\), \(\hat M x / 2^p = x/d + \varepsilon\) with \(0 \le \varepsilon < 1/d\), so the floor is \(\lfloor x/d \rfloor = \mathrm{trunc}(x/d)\) and \(q \ge 0\) needs no correction. For \(x < 0\), \(\hat M > 2^p / d\) makes \(\hat M x / 2^p\) lie strictly below \(x/d\), by less than \(1/d\), so its floor is \(\lceil x/d \rceil - 1\) whether or not \(d\) divides \(x\); the result is negative and the final "\(q \mathrel{+}= 1\)" yields \(\lceil x/d \rceil = \mathrm{trunc}(x/d)\). The course checks the result exhaustively for every divisor and every dividend at \(N = 8\) (tools/course/tests/test_ch13_drills.py, DivisionExhaustive), and LLVM checks its own implementation exhaustively for widths 3 to 12 (Lesson 13.9 §7).

When it breaks. A magic number computed for \(N\) bits is wrong for wider dividends; reusing a 32-bit \(m\) on 64-bit values is a classic bug. \(d = 1\), \(d = -1\) and powers of two need separate handling (shifts, with a bias for negative dividends in the signed case: (x + (x >>s (N-1)) >>u (N-k))) >>s k). Signed division of \(\mathrm{INT\_MIN}\) by \(-1\) is UB in the IR and traps on x86 in hardware; the multiply sequence silently returns \(\mathrm{INT\_MIN}\) — a refinement, since the source was UB.

5. Complexity

Technique	Time (worst)	Time (typical)	Space	Variables
NAF recoding	\(O(b)\)	\(b \le 64\)	\(O(b)\)	\(b\) bits of \(C\)
Optimal shift-add search (Bernstein)	exponential in the chain length	memoized, \(C\) small	table of costs	[Ber86]
Magic(d, N)	\(O(N)\) iterations of \(O(1)\) multi-precision operations	\(\le \lceil \log_2 d \rceil + 1\) iterations	\(O(1)\)	\(N\) width, \(d\) divisor
Emitted division	1 multiply + 1–4 add/shift	3–7 instructions	—	—

Justification. NAF: one iteration per digit, at most \(b + 1\) digits. Magic: by Theorem 13.7.4 the loop stops at \(\ell \le \lceil \log_2 d \rceil \le N\); each iteration does a ceiling division and a comparison of \((2N+1)\)-bit numbers. Warren's formulation avoids the big division by updating quotients and remainders incrementally (\(q_2 \gets 2 q_2\), …), which LLVM's DivisionByConstantInfo::get does on APInts.

Pathological family. Divisors just above a power of two need the most bits: for \(d = 2^{k} + 1\) the error \(e\) of \(m = \lceil 2^{N+\ell}/d \rceil\) cycles through large values, and \(m\) needs \(N + 1\) bits (the fix-up) for many \(\ell\); for \(d = 2^{N-1} + 1\) Warren's and LLVM's search stops one shift later than the minimum of Theorem 13.7.6 (the course's tests found this for \(d = 129\), \(N = 8\): LLVM-style \(\ell = 8\), minimal \(\ell = 7\)), still correct but with a larger multiplier. Scale: a 64-bit division by 7 is one mul and a few shifts instead of a 30–90-cycle div.

6. Variants and refinements

Multiplication by constants

• Factoring and lea chains (x86: \(3, 5, 9\) in one lea); shifted operands (AArch64 add w8, w0, w0, lsl #2); trade-off: target-specific cost models (box in §7).
• Bernstein's search with memoized costs of \(C\), \(C \pm 1\), \(C/(2^k \pm 1)\) [Ber86]; trade-off: compile time vs. optimality.
• Multiplication by the inverse for exact division (udiv exact, sdiv exact): multiply by \(d^{-1} \bmod 2^N\) for odd \(d\) [GM94, §9]; trade-off: only valid when the remainder is known to be 0.

Division by invariant integers

• Pre-shifting even divisors (\(x / 14 = (x \gg 1) / 7\)) so the magic number fits in \(N\) bits (LLVM's PreShift in DivisionByConstantInfo.cpp); trade-off: one more shift.
• Widening the multiply when a \(2N\)-bit multiply is cheap (LLVM's Widen for 32-bit division on x86-64, box in §7); trade-off: needs a fast \(2N \times 2N\) multiply.
• Remainder via \(x - d \lfloor x/d \rfloor\) (the umod10 box; trade-off: one more multiply-by-constant), and divisibility tests \(x \equiv 0 \pmod d\) via one multiply and one compare [War13, ch. 10]; trade-off: only answers "divisible?".
• Division by loop-invariant non-constant \(d\): compute the magic number once outside the loop (the libdivide library does this at run time); trade-off: the magic computation costs a division once.

7. In real compilers

Multiplication by constants

Multiplication by constants on x86-64 and AArch64

Reproduce (clang 23.1.2; any OS):

cat > mulc.c <<'EOF'
int mul7(int x)   { return x * 7; }
int mul10(int x)  { return x * 10; }
int mul45(int x)  { return x * 45; }
int mul641(int x) { return x * 641; }
EOF
for t in x86_64-unknown-linux-gnu aarch64-unknown-linux-gnu; do
  echo "=== $t"
  clang-23 --target=$t -O2 -S -o - mulc.c | grep -P '^(mul\d+:|\t(?!\.))' | grep -v '^\s*//\|# kill'
done

Output (complete):

=== x86_64-unknown-linux-gnu
mul7:                                   # @mul7
    leal    (,%rdi,8), %eax
    subl    %edi, %eax
    retq
mul10:                                  # @mul10
    addl    %edi, %edi
    leal    (%rdi,%rdi,4), %eax
    retq
mul45:                                  # @mul45
    leal    (%rdi,%rdi,8), %eax
    leal    (%rax,%rax,4), %eax
    retq
mul641:                                 # @mul641
    imull   $641, %edi, %eax                # imm = 0x281
    retq
=== aarch64-unknown-linux-gnu
mul7:                                   // @mul7
    lsl w8, w0, #3
    sub w0, w8, w0
    ret
mul10:                                  // @mul10
    add w8, w0, w0, lsl #2
    lsl w0, w8, #1
    ret
mul45:                                  // @mul45
    mov w8, #45                         // =0x2d
    mul w0, w0, w8
    ret
mul641:                                 // @mul641
    mov w8, #641                        // =0x281
    mul w0, w0, w8
    ret

What to notice: x * 7 is 8x − x on both targets (the NAF \(2^3 - 1\)); x * 10 is 2 · (x + 4x), an lea or a shifted-operand add plus a shift; x * 45 is two leas on x86 (\(9 \times 5\), factoring) but a mul on AArch64, where the cost model prefers one multiply to three shifted adds; x * 641 stays a multiply on both. The decisions live in X86ISelLowering.cpp (combineMul) and TargetLowering::decomposeMulByConstant (LLVM 23.1.2).

Division by invariant integers

Magic numbers in clang and GCC output

Reproduce (clang 23.1.2, gcc 13.3.0; Linux):

cat > div.c <<'EOF'
unsigned udiv7(unsigned x)  { return x / 7; }
unsigned udiv3(unsigned x)  { return x / 3; }
int      sdiv7(int x)       { return x / 7; }
unsigned umod10(unsigned x) { return x % 10; }
EOF
echo "=== clang-23 -O2"; clang-23 --target=x86_64-unknown-linux-gnu -O2 -masm=intel -S -o - div.c | grep -P '^([a-z]\w*:|\t(?!\.))' | grep -v '# kill'
echo "=== gcc -O2";      gcc -O2 -masm=intel -S -o - div.c | grep -P '^([a-z]\w*:|\t(?!\.))' | grep -v endbr64

Output (complete):

=== clang-23 -O2
udiv7:                                  # @udiv7
    mov eax, edi
    movabs  rcx, 2635249153617166336
    mul rcx
    mov rax, rdx
    ret
udiv3:                                  # @udiv3
    mov ecx, edi
    mov eax, 2863311531
    imul    rax, rcx
    shr rax, 33
    ret
sdiv7:                                  # @sdiv7
    movsxd  rax, edi
    imul    rcx, rax, -1840700269
    shr rcx, 32
    add eax, ecx
    mov ecx, eax
    shr ecx, 31
    sar eax, 2
    add eax, ecx
    ret
umod10:                                 # @umod10
    mov eax, edi
    mov ecx, edi
    mov edx, 3435973837
    imul    rdx, rcx
    shr rdx, 35
    add edx, edx
    lea ecx, [rdx + 4*rdx]
    sub eax, ecx
    ret
=== gcc -O2
udiv7:
    mov eax, edi
    imul    rax, rax, 613566757
    shr rax, 32
    sub edi, eax
    shr edi
    add eax, edi
    shr eax, 2
    ret
udiv3:
    mov eax, edi
    mov edx, 2863311531
    imul    rax, rdx
    shr rax, 33
    ret
sdiv7:
    movsx   rax, edi
    imul    rax, rax, -1840700269
    shr rax, 32
    add eax, edi
    sar edi, 31
    sar eax, 2
    sub eax, edi
    ret
umod10:
    mov eax, edi
    mov edx, 3435973837
    imul    rax, rdx
    shr rax, 35
    lea edx, [rax+rax*4]
    mov eax, edi
    add edx, edx
    sub eax, edx
    ret

What to notice: x / 3 is imul 2863311531 (0xAAAAAAAB) and shr 33 in both compilers: \(\ell = 1\), total shift \(32 + \ell\) (§3). x % 10 uses 0xCCCCCCCD and shr 35 (\(\ell = 3\)), then \(x - 10q\). x / 7 needs the 33-bit multiplier: GCC emits the fix-up of Theorem 13.7.9 with \(m' = 613566757\); clang instead multiplies the zero-extended \(x\) by a single 64-bit constant and keeps the high half (next box). Signed x / 7: both use \(M = -1840700269\) (0x92492493), add \(x\) (because \(M < 0 < d\)), shift by \(s = 2\) and add the sign bit — Theorem 13.7.10's sequence.

Where LLVM computes the magic numbers

Reproduce (LLVM 23.1.2 sources; curl; python3):

URL=https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/llvm/lib/Support/DivisionByConstantInfo.cpp
curl -sL $URL > DivisionByConstantInfo.cpp
grep -B1 -A3 'Calculate the magic numbers required to implement an unsigned integer' DivisionByConstantInfo.cpp
sed -n '/For IsAdd case with AllowWidenOptimization/,/^  }$/p' DivisionByConstantInfo.cpp
python3 -c 'print((2**32 + 613566757) << (64 - 35))'

Output (complete):

/// Calculate the magic numbers required to implement an unsigned integer
/// division by a constant as a sequence of multiplies, adds and shifts.
/// Requires that the divisor not be 0.  Taken from "Hacker's Delight", Henry
/// S. Warren, Jr., chapter 10.
  // For IsAdd case with AllowWidenOptimization, compute widened magic.
  // This is for optimizing 32-bit division using 64-bit multiplication.
  // The actual magic constant is 2^W + Magic ((W+1)-bit).
  // We pre-shift it left by (W*2 - OriginalShift) to avoid runtime shift.
  if (Retval.IsAdd && AllowWidenOptimization) {
    unsigned W = D.getBitWidth();
    unsigned OriginalShift = Retval.PostShift + W + 1;
    // Since PostShift >= 1, shift amount is at most W-2, so W*2 bits suffice.
    Retval.Magic = (APInt::getOneBitSet(W * 2, W) + Retval.Magic.zext(W * 2))
                       .shl(W * 2 - OriginalShift);
    Retval.IsAdd = false;
    Retval.PostShift = 0;
    Retval.Widen = true;
  }
2635249153617166336

What to notice: UnsignedDivisionByConstantInfo::get cites Hacker's Delight, chapter 10 [War13], and its "widen" branch turns the 33-bit magic \(2^{32} + m'\) (the IsAdd case) into a 64-bit constant pre-shifted by \(64 - (32 + 3) = 29\): \((2^{32} + 613566757) \ll 29 = 2\,635\,249\,153\,617\,166\,336\), the constant in clang's udiv7 above. TargetLowering::BuildUDIV in llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp emits the sequence [LLVM-DivConst].

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Multiplication by constants	Exact for every constant; gain only when the chain is short	\(O(b)\) to compute · 1–3 cheap instructions vs a 3-cycle mul	Target-dependent; wrong cost models make code slower	Low (NAF), medium (search + costs)	Instruction selection (x86 lea, AArch64 shifted operands)
Division by invariant integers	Exact for every \(N\)-bit dividend (Theorems 13.7.4–13.7.10)	\(O(N)\) to compute · 1 multiply + few ops vs a 20–90-cycle divide	Always a large win; needs a proof per variant	Medium (the proofs are the hard part)	Every compiler: SelectionDAG BuildUDIV/BuildSDIV, GCC expand_divmod, Cranelift ISLE rules

Choose shift-add multiplication when the constant's NAF (or a factorization) needs one or two cheap operations on the target; otherwise keep the multiply. Choose magic-number division always for constant divisors — the only choices are the variant (pre-shift, fix-up, widen) and the target's multiply-high instruction.

9. Assessment

Technique	Quiz questions	Drills	Flashcards	Exercises
Multiplication by constants	naf-trace, mul-lea	justification: the NAF recoding is a 5-line algorithm traced in the quiz; the drill magic-division covers the harder half of the lesson	tag mul-const	E2 (R10 mul-pow2)
Division by invariant integers	magic-7, magic-criterion, find-divconst	./course drill magic-division	tag div-const	E2 (R12–R14); Lab Part B (verify a magic rewrite)

References

See the chapter references.