Lesson 8.3 — Trees and DAGs: ASTs, HIR and expression DAGs¶
Techniques: abstract syntax trees and high-level IRs (HIR: desugared, name-resolved, typed trees), expression DAGs built by (local) value numbering · Pebble uses: the front end's AST (
pebble/include/pebble/AST/) is the tree IR; PIR comes after it; value numbering returns in Ch 13 and Ch 17 · Lab: the Tiny syntax tree (labs/ch00-exec/include/tiny/AST.h) is the input of both Chapter 8 labs · Prerequisites: Lesson 8.1 · Time: 3–5 hours
The first IR a compiler builds is a tree: the parser's abstract syntax tree. Compilers then keep a tree-shaped IR for a while (rustc's HIR and THIR, Clang's AST, GCC's GENERIC), because source-level questions (types, names, borrows) are easiest to ask about source-shaped code. The second graph in this lesson shares equal subtrees. That turns a tree into a DAG, and building it is the first optimization most compilers perform.
1. Problem and motivation¶
The problem. (a) Represent a program so that each construct and its operands are directly reachable, with source structure intact, and lower surface syntax to a smaller core language before later phases run. (b) Represent a straight-line computation so that equal computations are shared, which detects redundancy.
Abstract syntax trees and HIR¶
An abstract syntax tree keeps the grammar's structure without the concrete syntax: parentheses, keywords and precedence levels are gone, and operators point at their operands. Tree-walking interpreters (Lesson 0.2) evaluate it directly. A high-level IR (HIR) is an AST after desugaring (a smaller set of node kinds) and name resolution (each use points at its declaration), often with types attached. rustc lowers the AST to HIR, where while has become loop { if … else { break } }, and then to THIR, a typed tree used for pattern checking and MIR building [RUSTC-HIR; Rustc-Guide]. Clang keeps a single, fully typed AST with implicit conversions made explicit as ImplicitCastExpr nodes [Clang-AST]. The design question for a tree IR is what to keep (source fidelity for diagnostics and tools) versus what to normalize (fewer cases for later passes).
Expression DAGs and value numbering¶
In (a + b) * (a - b) followed by (b + a) * (a - b), the tree repeats a + b (commuted) and a - b. An expression DAG shares them: one node per distinct value. The algorithm that builds it is value numbering: give every computed value a number, and look each new operation up by (operator, operand numbers). Ershov used a hash table to detect repeated operations in 1958 [Ers58]. Cocke and Schwartz described local value numbering for basic blocks [CS70], and [Dragon2, §6.1.2, §8.5.1] and [EaC3, Ch. 8] teach it. LLVM's EarlyCSE pass and the CSE map of SelectionDAG are hash-consing value numberers [LLVM-EarlyCSE].
2. Definitions and algorithms¶
Abstract syntax trees and HIR¶
Definition 8.3.1 (Ranked alphabet, term, AST)
A ranked alphabet \(\Sigma\) assigns each constructor \(f\) an arity \(\mathrm{ar}(f) \in \mathbb{N}\). The terms \(T(\Sigma)\) are the least set with \(f(t_1, \dots, t_k) \in T(\Sigma)\) whenever \(\mathrm{ar}(f) = k\) and \(t_i \in T(\Sigma)\). An abstract syntax tree is a term over the constructors of a language's abstract grammar, for Tiny \(\{\mathsf{int}_k, \mathsf{var}_x, \mathsf{neg}, \mathsf{not}, \oplus, \&\&, \Vert, \mathsf{assign}_x, \mathsf{while}, \mathsf{if}, \mathsf{seq}, \mathsf{return}\}\) (Definition 0.2.1). \(\lvert t \rvert\) is the number of nodes.
Definition 8.3.2 (HIR; desugaring)
A high-level IR for a source language \(S\) is a tree language \(H\) whose constructors are
a subset of \(S\)'s plus a few core constructors, together with a desugaring
\(D : T(\Sigma_S) \to T(\Sigma_H)\) defined by structural recursion. \(D\) is correct if
\(\langle D(t), \sigma \rangle \Downarrow \sigma'\) iff \(\langle t, \sigma \rangle \Downarrow \sigma'\)
for all states. For Tiny-with-loops, let the core add \(\mathsf{loop}\{\bar{b}\}\) (repeat
forever) and \(\mathsf{break}\) (leave the innermost loop), with the big-step rules
\(\langle \mathsf{break} \cdot \bar{s}, \sigma \rangle \Downarrow_{\mathrm{brk}} \sigma\),
\(\dfrac{\langle \bar{b}, \sigma \rangle \Downarrow_{\mathrm{brk}} \sigma'}{\langle \mathsf{loop}\{\bar{b}\}, \sigma \rangle \Downarrow \sigma'}\) and
\(\dfrac{\langle \bar{b}, \sigma \rangle \Downarrow \sigma_1 \quad \langle \mathsf{loop}\{\bar{b}\}, \sigma_1 \rangle \Downarrow \sigma'}{\langle \mathsf{loop}\{\bar{b}\}, \sigma \rangle \Downarrow \sigma'}\),
where \(\Downarrow_{\mathrm{brk}}\) ("finished by a break") propagates out of if and
statement sequences like an exception.
Algorithm 8.3.3 (Desugar while into loop/if/break)
- Input: a Tiny statement tree.
- Output: an equivalent tree without
while(Definition 8.3.2). - Precondition: the tree is well formed.
- Postcondition: no \(\mathsf{while}\) node remains; semantics preserved (Theorem 8.3.6).
- Invariant: each recursive call returns a tree whose subtrees are already desugared.
function D(s):
case s of
while c { b }: return loop { if c { D*(b) } else { break } }
if c { b1 } else { b0 }: return if c { D*(b1) } else { D*(b0) }
x = e: return x = e
function D*(ss): return [ D(s) for s in ss ]
This is rustc's rule (lower_expr_while_in_loop_scope, §7).
Expression DAGs and value numbering¶
Definition 8.3.4 (Expression DAG; value number)
For a straight-line block (Definition 8.2.2) over TAC, the expression DAG is the graph with one leaf per distinct constant and per variable read before any assignment in the block, and one interior node per distinct key \((\mathit{op}, n_1, n_2)\) whose operands are nodes. Each node is labeled with the variables that hold its value at the end of the block. A value number is a node's identifier. Two computations are syntactically equivalent if they have the same key, where the operand numbers of commutative operators (\(\mathsf{add}, \mathsf{mul}, \mathsf{eq}, \mathsf{ne}\)) are sorted.
Algorithm 8.3.5 (Local value numbering)
- Input: a basic block \(c_0 \dots c_{k-1}\) of TAC.
- Output: a value number \(\mathrm{VN}(i)\) for every instruction's result, the DAG, and the set of redundant instructions (whose value some variable already holds).
- Precondition: the block has no jumps except possibly its last instruction.
- Postcondition: \(\mathrm{VN}(i) = \mathrm{VN}(j)\) implies both instructions compute the same value in every execution (Lemma 8.3.7), and every instruction syntactically equivalent to an earlier one whose value is still held is reported (Theorem 8.3.8).
- Invariant: after processing \(c_0 \dots c_{i-1}\): \(\mathit{var}[x]\) is the number of \(x\)'s current value; \(\mathit{table}[\kappa]\) is the number of key \(\kappa\); \(\mathit{holders}[v]\) is the set of variables whose current value has number \(v\).
function LVN(block):
table ← {}; var ← {}; holders ← {}; next ← 0; redundant ← []
function Leaf(a): # value number of an operand
if a is a variable and a ∈ var: return var[a]
κ ← ("const", a) if a is a constant else ("initial", a)
if κ ∉ table: next ← next + 1; table[κ] ← next
if a is a variable: Assign(a, table[κ])
return table[κ]
function Assign(x, v):
if x ∈ var: holders[var[x]] ← holders[var[x]] \ {x} # x's old value is killed
var[x] ← v; holders[v] ← holders[v] ∪ {x}
for i, c in enumerate(block):
if c is `x = a`: Assign(x, Leaf(a)); VN(i) ← var[x]; continue
if c is not an operation: continue # the final jump
ns ← [Leaf(a) for each operand a of c]
if c.op is commutative: ns ← sort(ns)
κ ← (c.op, ns...)
if κ ∈ table and holders[table[κ]] ≠ ∅: add i to redundant # reuse a holder
else if κ ∉ table: next ← next + 1; table[κ] ← next # a new DAG node
Assign(c.dst, table[κ]); VN(i) ← table[κ]
return VN, table, redundant
3. Worked example¶
Abstract syntax trees and HIR on the running example¶
The running example's while statement as an AST (constructors of Definition 8.3.1):
flowchart TD
W([while]) --> C["≤ (i, n)"]
W --> S[seq]
S --> IF[if]
S --> A2["assign i (+ (i, 1))"]
IF --> OR["‖"]
IF --> A1["assign s (+ (s, i))"]
OR --> E1["== (% (i, 3), 0)"]
OR --> E2["== (% (i, 5), 0)"]Algorithm 8.3.3 rewrites the root:
| step | node | action | result |
|---|---|---|---|
| 1 | while (i <= n) {…} |
rule for while |
loop { if (i <= n) { D*(body) } else { break } } |
| 2 | if (… ‖ …) { s = s + i } (empty else) |
rule for if |
unchanged shape; D* of each branch |
| 3 | s = s + i |
rule for assignment | unchanged |
| 4 | i = i + 1 |
rule for assignment | unchanged |
The resulting tree has 3 more nodes than the original (loop, if, break) and one fewer node kind. That is the trade of a core language: every later pass handles one loop construct instead of three (while, for, loop in Rust).
Expression DAGs on the running example's straight-line cousin¶
straight.tiny lowered by Algorithm 8.1.4 (one basic block) and every event of Algorithm 8.3.5 (value_numbering in tools/course/lib/irforms.py):
| # | instruction | key | VN | outcome | holders after |
|---|---|---|---|---|---|
| 0 | a = 7 |
leaf 7 | 1 | new leaf | a: 1 |
| 1 | b = 5 |
leaf 5 | 2 | new leaf | b: 2 |
| 2 | t.0 = add a, b |
(add, 1, 2) | 3 | new node | t.0: 3 |
| 3 | t.1 = sub a, b |
(sub, 1, 2) | 4 | new node | t.1: 4 |
| 4 | x = mul t.0, t.1 |
(mul, 3, 4) | 5 | new node | x: 5 |
| 5 | t.2 = add b, a |
(add, 1, 2) sorted | 3 | redundant (t.0 holds it) | t.0, t.2: 3 |
| 6 | t.3 = sub a, b |
(sub, 1, 2) | 4 | redundant (t.1 holds it) | t.1, t.3: 4 |
| 7 | t.4 = mul t.2, t.3 |
(mul, 3, 4) | 5 | redundant (x holds it) | x, t.4: 5 |
| 8 | y = add t.4, x |
(add, 5, 5) | 6 | new node | y: 6 |
| 9 | a = 2 |
leaf 2 | 7 | new leaf; kills a's old value | a: 7 (1 has no holder) |
| 10 | t.5 = add a, b |
(add, 2, 7) | 8 | new node | t.5: 8 |
| 11 | t.6 = sub a, b |
(sub, 7, 2) | 9 | new node | t.6: 9 |
| 12 | z = mul t.5, t.6 |
(mul, 8, 9) | 10 | new node | z: 10 |
| 13 | t.7 = add x, y |
(add, 5, 6) | 11 | new node | t.7: 11 |
| 14 | t.8 = add t.7, z |
(add, 10, 11) sorted | 12 | new node | t.8: 12 |
Three redundant instructions (5, 6, 7) and a DAG of 12 nodes (3 leaves, 9 operators) for 15 instructions. Instruction 10 looks like instruction 2, but a has a new value number (7), so the key differs. The kill in row 9 is what makes the algorithm sound. After removing the redundant instructions and forwarding their holders, the block computes the same result, 51 (ch08-run --form=tiny labs/ch08-forms/inputs/straight.tiny).
flowchart BT
L7((7)) --> ADD3["3: add"]
L5((5)) --> ADD3
L7 --> SUB4["4: sub"]
L5 --> SUB4
ADD3 --> MUL5["5: mul · x, t.4"]
SUB4 --> MUL5
MUL5 --> ADD6["6: add · y"]
MUL5 --> ADD6
L2((2)) --> ADD8["8: add"]
L5 --> ADD8
L2 --> SUB9["9: sub"]
L5 --> SUB9
ADD8 --> MUL10["10: mul · z"]
SUB9 --> MUL10(The two additions 11 and 12 at the top are omitted from the drawing.) Node 5 has two holders, x and t.4. Node 6 has both operands equal to node 5, so an edge from a DAG node may appear twice.
Try it
./course drill value-numbering --seed 3 --difficulty hard --solution: the same table for a random
block with commuted repeats and a reassignment that kills an available value.
4. Invariants and correctness¶
Abstract syntax trees and HIR¶
Theorem 8.3.6 (Desugaring while is correct)
For every Tiny statement sequence \(\bar{s}\) and state \(\sigma\): \(\langle D^*(\bar{s}), \sigma \rangle \Downarrow \sigma'\) iff \(\langle \bar{s}, \sigma \rangle \Downarrow \sigma'\), and \(D^*(\bar{s})\) never finishes by a break at top level.
Proof
By induction on the height of derivations, simultaneously for both directions. The only
non-trivial case is \(W = \mathsf{while}\ c\ \{\bar{b}\}\) with
\(D(W) = \mathsf{loop}\ \{\ \mathsf{if}\ c\ \{D^*(\bar{b})\}\ \mathsf{else}\ \{\mathsf{break}\}\ \}\).
(\(\Rightarrow\) for while) If \(\langle c, \sigma \rangle \Downarrow 0\), the loop body
takes the else branch and finishes by a break with state \(\sigma\), so the loop's first rule
gives \(\sigma\), as the while rule does. If \(c\) is non-zero, the body runs
\(D^*(\bar{b})\), which by the induction hypothesis reaches the same \(\sigma_1\) as \(\bar{b}\)
and does not break (Tiny bodies contain no break). The loop's second rule then continues
from \(\sigma_1\), matching the unrolling rule of while, and the induction hypothesis
applies to the shorter remaining derivation. (\(\Leftarrow\)) Every derivation of
\(\mathsf{loop}\) ends with its first rule after finitely many applications of the second.
Each application of the second rule corresponds to a true test and one run of \(\bar{b}\),
and the final one to a false test, which is exactly a derivation of the while. Assignments
and if are mapped homomorphically. A top-level break is impossible because every
\(\mathsf{break}\) that \(D\) introduces sits inside the \(\mathsf{loop}\) that \(D\) introduces
around it.
Expression DAGs and value numbering¶
Lemma 8.3.7 (Equal value numbers mean equal values)
At every point of Algorithm 8.3.5, and for every execution of the block: if two keys or variables have the same value number, they denote the same integer at the corresponding points of the execution. In particular, for each \(x\) with \(\mathit{var}[x] = v\), the current value of \(x\) is the value of node \(v\).
Proof
By induction on the number of processed instructions. A leaf number stands for a constant
or for a variable's value at block entry, which is fixed during an execution of the block.
An operation's number \(\mathit{table}[\kappa]\) stands for \(\mathit{op}\) applied to the
values of its operand numbers. By the induction hypothesis those are well defined, and
Tiny's operators are total functions (Definition 0.2.2), so equal keys denote equal
values. Sorting commutative operands does not change the value. Assign updates
\(\mathit{var}[x]\) exactly when \(x\) is written, so the claim about \(x\) holds after every
instruction. Values that another variable still holds are unaffected: their numbers still
denote the same values.
Theorem 8.3.8 (Local value numbering is sound and syntactically complete)
(a) Soundness: if instruction \(i\) is reported redundant, then any \(h \in \mathit{holders}[\mathrm{VN}(i)]\) just before \(i\) holds exactly the value \(c_i\) computes, so \(c_i\) can be replaced by the copy \(\mathit{dst} = h\). (b) Syntactic completeness: if \(c_i\) is syntactically equivalent (Definition 8.3.4) to an earlier \(c_j\) whose value is still held by some variable, then \(i\) is reported. (c) The DAG has exactly one node per distinct key or leaf.
Proof
(a) By Lemma 8.3.7, \(h\)'s current value is node \(\mathrm{VN}(i)\)'s value, and \(c_i\)
computes the value of the same key, hence the same value. (b) Key equality is exactly the
definition of syntactic equivalence, given that operand numbers are computed by Leaf,
which returns \(\mathit{var}[a]\) for assigned variables. The earlier \(c_j\) inserted its key
into \(\mathit{table}\), and a holder exists by hypothesis, so the first branch fires.
(c) A node is created only when its key is absent, and keys are never removed. The
converse, semantic completeness, fails: LVN does not know that \(x \cdot 2 = x + x\) or
that \((a+b)+c = a+(b+c)\). E-graphs (Lesson 8.5) address that.
Proposition 8.3.9 (A DAG can be exponentially smaller than its tree)
Let \(e_0 = a\) and \(e_{k+1} = e_k + e_k\). The tree of \(e_k\) has \(2^{k+1} - 1\) nodes, while
its DAG (and the TAC block t1 = add a, a; t2 = add t1, t1; …) has \(k + 1\) nodes.
Proof
Tree: \(\lvert e_0 \rvert = 1\) and \(\lvert e_{k+1} \rvert = 2 \lvert e_k \rvert + 1\), so \(\lvert e_k \rvert = 2^{k+1} - 1\) by induction. DAG: both operands of \(e_{k+1}\) have the same value number, so each level adds exactly one node by Theorem 8.3.8(c), giving \(k + 1\).
5. Complexity¶
Variables: \(\lvert t \rvert\) = tree nodes, \(k\) = instructions in a block.
| Technique | Time (worst) | Time (typical) | Space | Justification |
|---|---|---|---|---|
| AST construction and desugaring (Alg. 8.3.3) | \(O(\lvert t \rvert)\) | same | \(O(\lvert t \rvert)\) | one constant-size rewrite per node; while adds 3 nodes |
| Local value numbering (Alg. 8.3.5) | \(O(k^2)\) with a degenerate hash; \(O(k \log k)\) with a balanced tree | \(O(k)\) expected | \(O(k)\) | \(O(1)\) expected per hash lookup; at most 2 operands per key |
Pathological family. Proposition 8.3.9's \(e_k\) makes a tree IR exponential where the DAG is linear. A compiler that expands macros or inlines naively can build such trees, and every tree traversal then pays \(2^{k+1}\). The reverse problem arises for LVN's keys: with a poor hash (for example, one that ignores operand order and operator), all \(k\) keys collide and each lookup scans the whole bucket, which gives \(\Theta(k^2)\). LLVM's EarlyCSE hashes the opcode, the (sorted) operands and flags [LLVM-EarlyCSE].
At scale. Clang's AST for a single C++ translation unit including the standard library can have millions of nodes. That is why Clang keeps one AST and does not copy it into further tree IRs. rustc builds THIR per function body and discards it after MIR construction [Rustc-Guide].
6. Variants and refinements¶
Abstract syntax trees and HIR¶
- Lossless syntax trees (rust-analyzer's rowan, Roslyn, tree-sitter) keep every token and trivia for tooling. The trade-off: more memory, and every pass must skip trivia (Ch 4).
- Typed tree IRs (rustc THIR, Clang's AST with
ImplicitCastExpr) record types and implicit conversions in the tree, so MIR building or IR generation needs no type inference. The cost is a second tree or a heavier first one. - Desugaring early vs late. Swift type-checks the full AST and desugars during SILGen, rustc desugars before type checking (HIR). Desugaring early simplifies the type checker but makes diagnostics harder to phrase in source terms.
Expression DAGs and value numbering¶
- Superlocal and dominator-based value numbering extend the table along extended basic blocks or down the dominator tree, with scoped hash tables [EaC3, Ch. 8]. LLVM's
EarlyCSEis the dominator-tree version (Ch 13). - Global value numbering partitions all SSA values into congruence classes (Alpern, Wegman and Zadeck [AWZ88]; Click's hash-based GVN [Cli95]). It finds equalities through phis that LVN cannot see (Ch 17).
- Hash-consed DAGs as an IR: LLVM's
SelectionDAGCSEs nodes in aFoldingSetas they are created, so the instruction selector works on a DAG per block (Ch 21) [LLVM-SDAG].
7. In real compilers¶
Abstract syntax trees and HIR¶
Clang builds one typed AST: ForStmt and IfStmt in clang/include/clang/AST/Stmt.h (LLVM 23.1.2) [Clang-AST]. rustc lowers the AST to HIR in compiler/rustc_ast_lowering (lower_expr_while_in_loop_scope in src/expr.rs, rustc 1.94.1) [RUSTC-HIR], builds the typed THIR (compiler/rustc_middle/src/thir.rs, Thir) [RUSTC-THIR], and from it MIR (Lesson 8.7). GCC's tree IR is GENERIC, dumped with -fdump-tree-original (Lesson 8.7).
Clang's AST of the running example
Reproduce (clang 23.1.2; sed removes the node addresses, which change from run to run):
clang-23 -fsyntax-only -Xclang -ast-dump -fno-color-diagnostics euler1.c \
| sed -n '/FunctionDecl.*euler1/,$p' | sed -E 's/ 0x[0-9a-f]+//g'
Output (complete):
`-FunctionDecl <euler1.c:1:1, line:7:1> line:1:6 euler1 'long (long)' external-linkage
|-ParmVarDecl <col:13, col:18> col:18 used n 'long'
`-CompoundStmt <col:21, line:7:1>
|-DeclStmt <line:2:3, col:13>
| `-VarDecl <col:3, col:12> col:8 used s 'long' cinit
| `-ImplicitCastExpr <col:12> 'long' <IntegralCast>
| `-IntegerLiteral <col:12> 'int' 0
|-ForStmt <line:3:3, line:5:12>
| |-DeclStmt <line:3:8, col:18>
| | `-VarDecl <col:8, col:17> col:13 used i 'long' cinit
| | `-ImplicitCastExpr <col:17> 'long' <IntegralCast>
| | `-IntegerLiteral <col:17> 'int' 1
| |-<<<NULL>>>
| |-BinaryOperator <col:20, col:25> 'int' '<='
| | |-ImplicitCastExpr <col:20> 'long' <LValueToRValue>
| | | `-DeclRefExpr <col:20> 'long' lvalue Var 'i' 'long'
| | `-ImplicitCastExpr <col:25> 'long' <LValueToRValue>
| | `-DeclRefExpr <col:25> 'long' lvalue ParmVar 'n' 'long'
| |-UnaryOperator <col:28, col:29> 'long' postfix '++'
| | `-DeclRefExpr <col:28> 'long' lvalue Var 'i' 'long'
| `-IfStmt <line:4:5, line:5:12>
| |-BinaryOperator <line:4:9, col:32> 'int' '||'
| | |-BinaryOperator <col:9, col:18> 'int' '=='
| | | |-BinaryOperator <col:9, col:13> 'long' '%'
| | | | |-ImplicitCastExpr <col:9> 'long' <LValueToRValue>
| | | | | `-DeclRefExpr <col:9> 'long' lvalue Var 'i' 'long'
| | | | `-ImplicitCastExpr <col:13> 'long' <IntegralCast>
| | | | `-IntegerLiteral <col:13> 'int' 3
| | | `-ImplicitCastExpr <col:18> 'long' <IntegralCast>
| | | `-IntegerLiteral <col:18> 'int' 0
| | `-BinaryOperator <col:23, col:32> 'int' '=='
| | |-BinaryOperator <col:23, col:27> 'long' '%'
| | | |-ImplicitCastExpr <col:23> 'long' <LValueToRValue>
| | | | `-DeclRefExpr <col:23> 'long' lvalue Var 'i' 'long'
| | | `-ImplicitCastExpr <col:27> 'long' <IntegralCast>
| | | `-IntegerLiteral <col:27> 'int' 5
| | `-ImplicitCastExpr <col:32> 'long' <IntegralCast>
| | `-IntegerLiteral <col:32> 'int' 0
| `-CompoundAssignOperator <line:5:7, col:12> 'long' '+=' ComputeLHSTy='long' ComputeResultTy='long'
| |-DeclRefExpr <col:7> 'long' lvalue Var 's' 'long'
| `-ImplicitCastExpr <col:12> 'long' <LValueToRValue>
| `-DeclRefExpr <col:12> 'long' lvalue Var 'i' 'long'
`-ReturnStmt <line:6:3, col:10>
`-ImplicitCastExpr <col:10> 'long' <LValueToRValue>
`-DeclRefExpr <col:10> 'long' lvalue Var 's' 'long'
What to notice: a term in the sense of Definition 8.3.1, with name resolution done
(DeclRefExpr … Var 'i' points at the declaration) and every implicit conversion made
explicit (LValueToRValue, IntegralCast). Clang did not desugar: ForStmt keeps its
four children (the <<<NULL>>> is the absent condition-variable slot), += is still
CompoundAssignOperator, and source ranges are kept for diagnostics. Clang's code generator
handles each construct directly.
rustc's HIR: while is gone
Reproduce (rustc 1.94.1; -Zunpretty is unstable, and RUSTC_BOOTSTRAP=1 enables it on a stable compiler for inspection only):
cat > euler1.rs <<'EOF'
pub fn euler1(n: i64) -> i64 {
let mut s = 0;
let mut i = 1;
while i <= n {
if i % 3 == 0 || i % 5 == 0 {
s += i;
}
i += 1;
}
s
}
EOF
RUSTC_BOOTSTRAP=1 rustc --crate-type=lib -Zunpretty=hir euler1.rs
Output (complete):
extern crate std;
#[prelude_import]
use ::std::prelude::rust_2015::*;
fn euler1(n: i64)
->
i64 {
let mut s = 0;
let mut i = 1;
loop {
if i <= n {
if i % 3 == 0 || i % 5 == 0 { s += i; }
i += 1;
} else { break; }
}
s
}
What to notice: exactly Algorithm 8.3.3. The while became
loop { if i <= n { … } else { break; } } (rustc's lower_expr_while_in_loop_scope
builds hir::ExprKind::Loop with LoopSource::While, so diagnostics can still say
"while"). The HIR also injected the prelude import. -Zunpretty=thir-tree prints the
next, typed tree IR, with a type on every expression node.
Expression DAGs and value numbering¶
LLVM: EarlyCSE in llvm/lib/Transforms/Scalar/EarlyCSE.cpp hashes SimpleValues and swaps the operands of commutative binary operators before hashing (DenseMapInfo<SimpleValue>::getHashValue), which is the sorted key of Definition 8.3.4 [LLVM-EarlyCSE]. SelectionDAG keeps its CSE map as FoldingSet<SDNode> CSEMap in llvm/include/llvm/CodeGen/SelectionDAG.h [LLVM-SDAG]. GCC: value numbering over SSA in gcc/tree-ssa-sccvn.cc (do_rpo_vn) [GCC-SCCVN].
EarlyCSE removes the commuted repeat
Reproduce (clang 23.1.2, opt 23.1.2):
cat > cse.c <<'EOF'
long f(long a, long b) {
long x = (a + b) * (a - b);
long y = (b + a) * (a - b) + x;
a = 2;
long z = (a + b) * (a - b);
return x + y + z;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm cse.c -o - \
| opt -passes=sroa -S -o cse.ll
sed -n '/define/,/^}/p' cse.ll
opt -passes=early-cse -S cse.ll | sed -n '/define/,/^}/p'
Output (complete; before, then after):
define dso_local i64 @f(i64 noundef %a, i64 noundef %b) #0 {
entry:
%add = add nsw i64 %a, %b
%sub = sub nsw i64 %a, %b
%mul = mul nsw i64 %add, %sub
%add1 = add nsw i64 %b, %a
%sub2 = sub nsw i64 %a, %b
%mul3 = mul nsw i64 %add1, %sub2
%add4 = add nsw i64 %mul3, %mul
%add5 = add nsw i64 2, %b
%sub6 = sub nsw i64 2, %b
%mul7 = mul nsw i64 %add5, %sub6
%add8 = add nsw i64 %mul, %add4
%add9 = add nsw i64 %add8, %mul7
ret i64 %add9
}
define dso_local i64 @f(i64 noundef %a, i64 noundef %b) #0 {
entry:
%add = add nsw i64 %a, %b
%sub = sub nsw i64 %a, %b
%mul = mul nsw i64 %add, %sub
%add4 = add nsw i64 %mul, %mul
%add5 = add nsw i64 2, %b
%sub6 = sub nsw i64 2, %b
%mul7 = mul nsw i64 %add5, %sub6
%add8 = add nsw i64 %mul, %add4
%add9 = add nsw i64 %add8, %mul7
ret i64 %add9
}
What to notice: the three instructions of rows 5–7 in §3 (%add1 = b + a, %sub2,
%mul3) are gone, and their uses now point at %add, %sub, %mul. That is
Theorem 8.3.8(a), with SSA names instead of holders. After a = 2, SSA has already
renamed a (the constant 2 is substituted), so no kill is needed: in SSA form every name
is single-assignment and keys can never go stale (Lesson 8.4). That is why LVN is easier
on SSA.
8. Comparison¶
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Abstract syntax trees and HIR | full source structure; types and names attached in HIR/THIR | \(O(\lvert t \rvert)\) per pass · tree traversals chase pointers | best diagnostics: source ranges on every node | low (tree) to high (typed HIR with desugaring) | front ends: Clang AST, rustc HIR/THIR, GCC GENERIC, Pebble AST |
| Expression DAGs and value numbering | shares syntactically equal computations inside a block (Theorem 8.3.8) | \(O(k)\) expected · 15 instructions → 12 nodes, 3 redundant (§3) | a DAG per block; holders say where values live | low (hash table + kill rule) | local CSE (EarlyCSE), SelectionDAG, basic-block code generation |
Choose a tree IR for everything that talks about the source: type checking, name resolution, borrow checking, macro expansion, diagnostics. Keep it close to the source, and desugar into a core only as far as later passes benefit. Choose a DAG / value numbering inside basic blocks when you want redundancy elimination and a compact picture of dataflow. Move to SSA-based GVN (Ch 17) for whole functions.
9. Assessment¶
| Technique | Quiz ids (solutions/quizzes/ch08.yaml) |
Drill | Flashcard tag | Exercises |
|---|---|---|---|---|
| Abstract syntax trees and HIR | hir-desugar-while, ast-vs-dag-size |
none: desugaring rules are one line each, so a drill would only test recall. The quiz computes sizes instead | ast-hir |
the lab consumes the provided Tiny AST (labs/ch00-exec/include/tiny/AST.h) |
| Expression DAGs and value numbering | lvn-redundant, lvn-nodes, llvm-where-earlycse-commutative |
./course drill value-numbering |
value-numbering |
exercises.md, X1 ★ |
Forgetting the kill
In x = add a, b; x = 1; z = add a, b, the key of z is found in the table. If x = 1
did not remove x from the holders of the old value, LVN would replace z by the copy
z = x and return 1 instead of \(a + b\). With the kill, no variable holds the value any
more, and the instruction is (correctly) recomputed. test_ch08.py checks both cases, and
the drill's hard level includes a reassignment.
References¶
See the chapter references.