Lesson 13.6 — Reassociation: ranks and tree-height reduction¶
Techniques: rank-based reassociation (Briggs and Cooper 1994; LLVM's Reassociate, GCC's tree-ssa-reassoc); tree-height reduction (Baer and Bovet 1968; Brent 1974; LLVM's MachineCombiner) · Pebble implements:
pebble-reassociatewith Briggs–Cooper ranks (exercise E5) · Lab: — (drillreassoc-ranks) · Prerequisites: Lesson 13.4 (canonical forms), Lesson 13.5 (value numbering), Ch 15 (reverse postorder, loops) · Time: 4 hours
In a loop, s = s + (i + a + 4 + b) computes a + 4 + b on every iteration although a and b never change — but the parse tree ((i + a) + 4) + b has no subexpression that is loop-invariant, so loop-invariant code motion cannot hoist anything. Addition is associative and commutative, so the compiler may regroup the sum as ((a + b) + 4) + i, whose inner part is invariant. Reassociation chooses such a grouping deliberately. Two goals pull in different directions: grouping by rank (how deep in the loop nest a value is defined) exposes invariant and common subexpressions (Briggs and Cooper); balancing the tree reduces its height and hence the latency of the computation on a pipelined or parallel machine (tree-height reduction). This lesson develops both, proves when reassociation is correct in modular integer arithmetic — and exactly which flags survive — and why floating-point addition needs the reassoc flag.
1. Problem and motivation¶
Given an expression tree of one associative and commutative operator \(\oplus\) over leaves \(x_1, \dots, x_n\), choose a grouping and an order of the leaves. pebblec runs pebble-reassociate before pebble-lvn so that equal sums written in different orders get equal value numbers, and so that loop-invariant parts become separate instructions for later loop optimizations (Ch 18).
Rank-based reassociation¶
Briggs and Cooper proposed ranking every value by the reverse-postorder (RPO) position of its block, sorting the operands of each \(\oplus\)-tree by rank, and building the tree so that low-rank operands are combined first; the lowest-rank subexpressions are then loop-invariant (and constant subexpressions fold), which enables code motion, value numbering and constant propagation [BC94]. LLVM's Reassociate pass implements this ("constants are assigned rank = 0, function arguments are rank = 1, and other values are assigned ranks corresponding to the reverse post order traversal", Reassociate.cpp [LLVM-Reassociate]); GCC's tree-ssa-reassoc.cc ranks operands similarly [GCC-reassoc]. Pebble's E5 follows the definition below.
Tree-height reduction¶
A left-deep chain of \(n\) additions has height \(n - 1\): each addition waits for the previous one. The balanced tree has height \(\lceil \log_2 n \rceil\), so on a machine that can issue several additions per cycle it finishes sooner. Baer and Bovet (1968) gave an algorithm for compiling arithmetic expressions for parallel evaluation by exploiting associativity and commutativity [BB68]; Brent (1974) proved that any expression with \(n\) operations can be evaluated in \(O(\log n)\) parallel time using distributivity as well [Bre74]. In today's compilers the balancing is done late, with latencies known: LLVM's MachineCombiner reassociates floating-point and integer chains when that shortens the critical path [LLVM-MachineCombiner].
2. Definitions and algorithms¶
Definition 13.6.1 (Expression tree of an operator)
Let \(\oplus \in \{\mathsf{add}, \mathsf{mul}, \mathsf{and}, \mathsf{or}, \mathsf{xor}\}\) on \(\texttt{i}N\). An instruction \(u\) with opcode \(\oplus\) is an internal node if it has exactly one use, that use has the same opcode, and it is in the same block; otherwise it is a root. The tree of a root \(r\) is \(r\) together with the internal nodes reachable from it through operands; its leaves are the operands of its nodes that are not internal nodes of the tree.
Definition 13.6.2 (Rank)
Number the blocks of \(G\) in reverse postorder starting at 1: \(R(B) = \mathrm{rpo}(B) + 1\). The rank of a value is:
Ties are broken by position: arguments in order, then instructions in RPO block order and program order within a block. pebble-reassociate<print-ranks> prints exactly these numbers (exercise E5), and the drill reassoc-ranks computes them.
Ranks in the loop of @sum
With blocks entry (R = 1), loop (R = 2), exit (R = 3): arguments a, b, n have rank 1; the phis i and s are opaque in loop, rank 2; t1 = add i, a has rank \(\max(2, 1) = 2\); a load in exit has rank 3.
Algorithm 13.6.3 (Rank-based reassociation)
- Input: a function in SSA form.
- Output: every \(\oplus\)-tree rebuilt as a left-deep chain over its non-constant leaves sorted by (rank, position), with all constant leaves folded into one constant as the last operand.
- Precondition: \(\oplus\) is associative and commutative on the type (integers; floating point only with
reassoc). - Postcondition: each rebuilt tree computes the same value (Theorem 13.6.7) with flags per Theorem 13.6.8; in every chain, operand ranks never decrease from the innermost node outwards.
- Invariant: trees already rebuilt are never internal nodes of later trees (roots are processed in RPO; a root's value is a leaf of any tree that uses it).
function Reassociate(f):
compute rank and position of every value (Definition 13.6.2)
for r in the roots of f, in RPO order: # Definition 13.6.1
RebuildTree(r)
function RebuildTree(r):
⊕ ← opcode(r); L ← Leaves(r)
K ← fold of the constant leaves under ⊕ (identity e⊕ if none)
V ← the non-constant leaves, sorted by (rank, position) # stable
if K is absorbing for ⊕ (0 for mul/and, −1 for or): result ← K
else:
ops ← V followed by K unless K = e⊕ # e: 0 for add/or/xor, 1 for mul, −1 for and
result ← ops[0]
for j in 1 .. |ops| − 1:
result ← new instruction ⊕(result, ops[j]) before r, with flags per Theorem 13.6.8
replace every use of r by result; delete r and the internal nodes
function Leaves(u):
for each operand o of u:
if o is an internal node of u's tree (Definition 13.6.1): yield Leaves(o)
else: yield o
Tree-height reduction¶
Definition 13.6.4 (Height with arrival times)
Each leaf \(x_j\) has an arrival time \(a_j \ge 0\) (when its value is ready). A binary tree over the leaves, where each \(\oplus\) node takes one unit of time, has completion time \(T\), the time its root is ready: a leaf is ready at \(a_j\), an internal node at \(1 + \max\) of its children's times. With all \(a_j = 0\), \(T\) is the tree's height.
Algorithm 13.6.5 (Huffman-style tree-height reduction)
- Input: leaves \(x_1, \dots, x_n\) of one associative and commutative \(\oplus\), with arrival times \(a_1, \dots, a_n\).
- Output: a binary tree over the leaves with minimal completion time.
- Precondition: \(\oplus\) associative and commutative (all \(n!\) orders and all groupings are allowed); each \(\oplus\) costs one unit; unlimited parallelism.
- Postcondition: the completion time is \(\min\) over all binary trees (Theorem 13.6.10).
- Invariant: the queue holds the roots of the partial trees built so far; each has the earliest ready time achievable for its set of leaves.
function Balance(leaves with times a_j):
Q ← priority queue of (a_j, x_j), smallest time first
while |Q| > 1:
(t1, u) ← pop min of Q
(t2, v) ← pop min of Q # t1 ≤ t2
w ← new node ⊕(u, v), ready at 1 + t2 # = 1 + max(t1, t2)
push (1 + t2, w) into Q
return the single tree left in Q
With all \(a_j = 0\) this produces a tree of height \(\lceil \log_2 n \rceil\). LLVM's MachineCombiner makes local versions of this choice with real latencies, only when the critical path gets shorter.
3. Worked example¶
Running example (tests/ch13/lit/reassoc-ranks.ll and reassoc-rewrite.ll):
define i32 @sum(i32 %a, i32 %b, i32 %n) {
entry:
br label %loop
loop:
%i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
%s = phi i32 [ 0, %entry ], [ %s.next, %loop ]
%t1 = add i32 %i, %a
%t2 = add i32 %t1, 4
%t3 = add i32 %t2, %b
%s.next = add i32 %s, %t3
%i.next = add i32 %i, 1
%c = icmp slt i32 %i.next, %n
br i1 %c, label %loop, label %exit
exit:
ret i32 %s.next
}
flowchart TD
entry([entry]) --> loop[loop]
loop --> loop
loop --> exit[exit]Rank-based reassociation¶
Ranks (RPO: entry, loop, exit, so \(R\) = 1, 2, 3):
| value | kind | rank | position |
|---|---|---|---|
a, b, n |
arguments | 1 | 0, 1, 2 |
i, s |
phis in loop |
2 | 3, 4 |
t1 = add i, a |
expression | max(2, 1) = 2 | 5 |
t2 = add t1, 4 |
expression | max(2, 0) = 2 | 6 |
t3 = add t2, b |
expression | 2 | 7 |
s.next = add s, t3 |
expression | 2 | 8 |
i.next = add i, 1 |
expression | 2 | 9 |
c = icmp i.next, n |
expression | 2 | 10 |
Trees: t1, t2, t3 each have one use by an add in the same block, so they are internal; s.next has two uses (the phi and ret), so it is a root; i.next is a root (its users are a phi and an icmp). Algorithm 13.6.3 on the root s.next:
| step | action | state |
|---|---|---|
| 1 | Leaves(s.next) |
s, Leaves(t3) → s, Leaves(t2), b → s, Leaves(t1), 4, b → s, i, a, 4, b |
| 2 | fold constants | \(K = 4\) |
| 3 | sort non-constant leaves by (rank, position) | a (1, 0), b (1, 1), i (2, 3), s (2, 4) |
| 4 | build chain | x1 = add a, b; x2 = add x1, i; x3 = add x2, s; s.next = add x3, 4 |
The innermost node add a, b has rank 1: loop-invariant, so LICM hoists it (the box in §7 shows LLVM doing this). The tree for i.next (add i, 1) is already in the canonical shape and is left alone.
Tree-height reduction¶
Algorithm 13.6.5 on eight leaves \(x_1..x_8\) with arrival times \((0, 0, 0, 0, 0, 0, 2, 3)\) (the last two come from slower computations):
| step | pop | pop | new node ready at | queue after (times) |
|---|---|---|---|---|
| 0 | — | — | — | 0 0 0 0 0 0 2 3 |
| 1 | \(x_1\) (0) | \(x_2\) (0) | \(y_1\): 1 | 0 0 0 0 1 2 3 |
| 2 | \(x_3\) (0) | \(x_4\) (0) | \(y_2\): 1 | 0 0 1 1 2 3 |
| 3 | \(x_5\) (0) | \(x_6\) (0) | \(y_3\): 1 | 1 1 1 2 3 |
| 4 | \(y_1\) (1) | \(y_2\) (1) | \(y_4\): 2 | 1 2 2 3 |
| 5 | \(y_3\) (1) | \(x_7\) (2) | \(y_5\): 3 | 2 3 3 |
| 6 | \(y_4\) (2) | \(x_8\) (3) | \(y_6\): 4 | 3 4 |
| 7 | \(y_5\) (3) | \(y_6\) (4) | root: 5 | 5 |
Completion time 5. The left-deep chain in index order finishes at 7 (the chain has height 7 and \(x_8\) arrives before its turn); the balanced tree ignoring arrival times, \(((x_1 x_2)(x_3 x_4))((x_5 x_6)(x_7 x_8))\), finishes at \(\max(2, 1 + \max(1, 1 + 3)) + 1 = 6\).
Try it
./course drill reassoc-ranks --seed 3 --difficulty medium --solution computes ranks for a loop and the sorted leaf order of one tree, exactly as above.
4. Invariants and correctness¶
Rank-based reassociation¶
Lemma 13.6.6 (Ranks and loops)
Let \(L\) be a natural loop with header \(h\) in a reducible CFG, and number blocks in RPO. (a) Every value defined outside \(L\) and used inside \(L\) has rank \(< R(h)\). (b) Every phi and every opaque instruction in a block of \(L\) has rank \(\ge R(h)\). (c) An expression has rank \(\ge\) the rank of each operand.
Proof
(a) A value used in \(L\) and defined outside \(L\) is, by SSA, defined in a block \(D\) that dominates the use; since the use is in \(L\) and \(D \notin L\), \(D\) dominates \(h\) (every path from the entry into \(L\) passes through \(h\)) and \(D \ne h\), so \(D\) precedes \(h\) in RPO (a dominator precedes the nodes it dominates in every DFS preorder and in RPO). Arguments have rank 1 \(\le R(\mathit{entry}) \le R(h)\), and 1 \(< R(h)\) unless \(h\) is the entry block, which has no incoming back edge by convention (Ch 15). Opaque values in \(D\) have rank \(R(D) < R(h)\), and expressions have the maximum of such ranks, by induction on the definition order. (b) The blocks of \(L\) are dominated by \(h\), so they follow \(h\) in RPO: \(R(B) \ge R(h)\). (c) By definition.
Theorem 13.6.7 (Reassociation preserves values)
Rebuilding a tree without poison-generating flags (Algorithm 13.6.3) is a refinement of the original tree, for \(\oplus \in \{\mathsf{add}, \mathsf{mul}, \mathsf{and}, \mathsf{or}, \mathsf{xor}\}\) on \(\texttt{i}N\).
Proof
\((\mathbb{Z}/2^N\mathbb{Z}, +)\), \((\mathbb{Z}/2^N\mathbb{Z}, \cdot)\) and the bitwise operations on \(\{0,1\}^N\) are commutative monoids, so every grouping and every order of the same multiset of leaves denotes the same element (generalized associativity and commutativity, by induction on the number of leaves), and folding the constant leaves first is one such grouping. For poison: if any leaf is poison, the rebuilt chain is poison (rule P-Op, every leaf is an operand of some node), which refines anything; if no leaf is poison and the source is not poison, the rebuilt chain computes the same value. If the source is poison with non-poison leaves, a flag failed in the source, and any target value refines poison. The absorbing case: a product with a zero leaf is 0 whatever the other leaves (if a leaf is poison, the source is poison and 0 refines it). So in all cases the result refines the source.
Theorem 13.6.8 (Which flags survive reassociation)
In the rebuilt chain: (a) nsw may not be kept, even when every node of the source had it; (b) nuw on add may be kept on every new node when every source node had nuw; (c) nuw on mul may not be kept; (d) disjoint on or may be kept when every source node had it.
Proof
(a) Counterexample on \(\texttt{i}8\): source (a + b) + c with nsw on both, \(a = 100\), \(b = -100\), \(c = 100\): \(a + b = 0\) and \(0 + 100 = 100\), no overflow; the rebuilt (a + c) + b computes \(a + c = 200 \notin [-128, 128)\): poison with nsw. (b) If every source add nuw is non-poison, every source node's exact unsigned sum is \(< 2^N\); in particular the root's exact sum \(S = \sum_j x_j < 2^N\) (the root's exact value is the exact sum of all leaves, since no node wrapped). Every node of the rebuilt chain computes the exact sum of a subset of the leaves, which is \(\le S < 2^N\) because all leaves are non-negative as unsigned numbers. So no rebuilt node wraps, and nuw holds wherever the source is not poison. (c) Counterexample: source (a * b) * c with nuw on both, \(a = c = 16\), \(b = 0\) on \(\texttt{i}8\): \(a \cdot b = 0\), \(0 \cdot c = 0\), no overflow; the regrouping (a * c) * b (the sorted order when \(\mathrm{rank}(c) < \mathrm{rank}(b)\)) computes \(a \cdot c = 256\), poison with nuw — unlike sums, a product of a subset of the factors can exceed the whole product when another factor is 0. (d) If every source or disjoint is non-poison, the two operands of every node share no bit; by induction the leaves under a node are pairwise disjoint, and at the root all leaves are pairwise disjoint. Any node of the rebuilt tree ORs two disjoint unions of pairwise-disjoint leaves, which share no bit.
Theorem 13.6.9 (Rank order exposes loop invariants)
In a chain built by Algorithm 13.6.3 inside a natural loop \(L\) with header \(h\), the leaves of rank \(< R(h)\) form a prefix \(x_{(1)}, \dots, x_{(k)}\) of the sorted order; they include every leaf defined outside \(L\), and all of them are loop-invariant, so the innermost \(k - 1\) nodes compute only loop-invariant values and can be hoisted out of \(L\).
Proof
By Lemma 13.6.6 (a), leaves defined outside \(L\) have rank \(< R(h)\). A leaf defined inside \(L\) is a phi or opaque instruction of \(L\) (rank \(\ge R(h)\) by (b)), or an expression; an expression has rank \(< R(h)\) only if, recursively, all its operands have rank \(< R(h)\), i.e. it is a pure computation over constants, arguments and values defined outside \(L\) — loop-invariant. So every leaf of rank \(< R(h)\) is loop-invariant, and sorting by rank puts all of them before every leaf of rank \(\ge R(h)\) (such an in-loop invariant expression may sort between two leaves defined outside \(L\), which is why the prefix is described by rank). The left-deep chain combines the first \(k\) leaves in its innermost \(k - 1\) nodes, whose operands are all invariant.
When it breaks. Reassociating floating-point addition changes results (Proposition 13.1.14 (c)): it is allowed only when every instruction of the tree carries reassoc (and nsz where signed zeros matter), as the LangRef's rewrite-based flag rules require (Lesson 13.8). Keeping nsw breaks (Theorem 13.6.8 (a)): LLVM's Reassociate drops it; so does pebble-reassociate.
Tree-height reduction¶
Theorem 13.6.10 (The greedy tree has minimal completion time)
Algorithm 13.6.5 produces a binary tree whose completion time is minimal among all binary trees over the leaves with the given arrival times.
Proof
Write \(d_j\) for the depth of leaf \(x_j\). Every internal node adds one unit, so by induction on the tree the completion time is \(T = \max_j (a_j + d_j)\). We prove by induction on \(n\) that the greedy tree minimizes \(T\); \(n = 1\) is trivial. Let \(n \ge 2\) and let \(u, v\) be the leaves the algorithm pops first, \(a_u \le a_v \le\) every other arrival time.
Some optimal tree has \(u\) and \(v\) as siblings (exchange argument). Take an optimal tree \(T^\ast\) and an internal node \(w\) of maximal depth; both its children are leaves \(p, q\), at the maximal leaf depth \(D\). Exchange the positions of \(u\) and \(p\): the two affected terms become \(a_u + D\) and \(a_p + d_u\); since \(a_u \le a_p\) and \(d_u \le D\), both are \(\le a_p + D\), one of the old terms, so \(\max_j (a_j + d_j)\) does not increase. Exchange \(v\) and \(q\) the same way (\(a_v \le a_q\), \(d_v \le D\)). The result is still optimal and has \(u, v\) as the children of \(w\).
Reduction. In a tree where \(u, v\) are siblings at depth \(d\), their parent \(w\) is ready at \(1 + \max(a_u, a_v) = 1 + a_v\). Replacing the subtree \(w\) by a single leaf with arrival time \(1 + a_v\) at depth \(d - 1\) replaces the two terms \(a_u + d, a_v + d\) (maximum \(a_v + d\)) by \((1 + a_v) + (d - 1) = a_v + d\): the completion time is unchanged. So optimal trees for the original instance with \(u, v\) siblings correspond one-to-one, with equal completion times, to trees for the reduced instance of \(n - 1\) leaves — which is exactly the instance the algorithm continues with. By the induction hypothesis the algorithm's tree for the reduced instance is optimal, hence so is its tree for the original. (This is Huffman's argument with \(\max\) in place of \(+\); Golumbic studies such "combinatorial merging" problems [Gol76].)
Corollary 13.6.11 (Balanced height)
With all arrival times 0, the minimal height of a binary tree with \(n\) leaves is \(\lceil \log_2 n \rceil\), and the left-deep chain has height \(n - 1\).
Proof
A binary tree of height \(h\) has at most \(2^h\) leaves, so \(h \ge \lceil \log_2 n \rceil\); the greedy algorithm pairs leaves level by level (all ties at the same time), reaching this bound. The chain has one node per level.
5. Complexity¶
| Technique | Time (worst) | Time (typical) | Space | Variables |
|---|---|---|---|---|
| Rank-based reassociation | \(O(n + \sum_T k_T \log k_T)\) | linear | \(O(n)\) ranks | \(n\) instructions, \(k_T\) leaves of tree \(T\) |
| Tree-height reduction (greedy) | \(O(k \log k)\) per tree | small \(k\) | \(O(k)\) | \(k\) leaves |
Justification. Ranks: one pass over the blocks in RPO, each instruction looks at its operands once. Each tree is collected once (each internal node belongs to exactly one tree) and sorted. The greedy algorithm does \(k - 1\) iterations of two pops and one push on a heap of size \(\le k\).
Pathological family. Reassociation can undo useful sharing: for \(t = a + b\) used both alone and inside \(u = (a + b) + c\), \(t\) has two uses, so it is a leaf of \(u\)'s tree and survives — but if each of \(m\) roots contains a different single-use copy of \(a + b\) sorted apart by rank (for example \(a + x_j + b\) with \(\mathrm{rank}(x_j) = \mathrm{rank}(a)\) and position between \(a\) and \(b\)), the result computes \(m\) different chains and no common subexpression \(a + b\) remains; LLVM's Reassociate keeps a pair map of frequent operand pairs to counter this (box in §7). For tree-height reduction, a chain of \(n\) additions where each \(x_j\) arrives at time \(j - 1\) is already optimal as a chain: balancing it gains nothing, and a balancer ignoring arrival times makes it worse (completion \(\lceil \log_2 n \rceil + n - 1\) instead of \(n\)).
6. Variants and refinements¶
Rank-based reassociation¶
- Distribution (factoring \(a \cdot b + a \cdot c = a \cdot (b + c)\) and its reverse), which Briggs and Cooper also consider; trade-off: can increase work if both products are needed elsewhere [BC94].
- Pair maps (LLVM): prefer groupings that occur often in the function, so CSE finds them; trade-off: extra pass over all trees [LLVM-Reassociate].
- N-ary reassociation (LLVM
NaryReassociate) regroups to reuse existing values dominating the tree; trade-off: dominator-tree queries. - Linearization of subtraction and negation (\(x - y = x + (-y)\)) so that subtractions join the add tree; GCC and LLVM both do it; E5 omits it.
Tree-height reduction¶
- Tree-height balancing in the middle end (Cooper and Torczon's algorithm, which ranks operands and rebuilds balanced trees block by block [EaC3, Ch. 8]); trade-off: it runs without latency information, so it may lengthen chains that were not critical.
- Brent's theorem uses distributivity to evaluate any expression in \(O(\log n)\) parallel steps [Bre74]; trade-off: more operations.
- Latency-aware reassociation in the back end (MachineCombiner, with the scheduling model) [LLVM-MachineCombiner]; trade-off: must not increase register pressure too much.
- Vectorizer reductions: loop vectorization reassociates a sum into several partial sums (requires
reassocfor floating point) — Ch 18.
7. In real compilers¶
Rank-based reassociation¶
LLVM Reassociate: invariant parts first, then LICM and CSE
Reproduce (opt 23.1.2; any OS):
cat > reassoc.ll <<'EOF'
define i32 @sum(i32 %a, i32 %b, i32 %n) {
entry:
br label %loop
loop:
%i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
%s = phi i32 [ 0, %entry ], [ %s.next, %loop ]
%t1 = add i32 %i, %a
%t2 = add i32 %t1, 4
%t3 = add i32 %t2, %b
%s.next = add i32 %s, %t3
%i.next = add i32 %i, 1
%c = icmp slt i32 %i.next, %n
br i1 %c, label %loop, label %exit
exit:
ret i32 %s.next
}
define i32 @cse(i32 %a, i32 %b, i32 %c) {
%x = add i32 %a, %c
%y = add i32 %x, %b
%z = add i32 %b, %a
%w = add i32 %z, %c
%r = xor i32 %y, %w
ret i32 %r
}
EOF
echo "=== reassociate"; opt -passes=reassociate -S reassoc.ll | sed -n '/^loop:/,/br i1/p;/^define i32 @cse/,/^}/p'
echo "=== reassociate,licm"; opt -passes='reassociate,loop-mssa(licm)' -S reassoc.ll | sed -n '/^define i32 @sum/,/^exit:/p'
echo "=== reassociate,early-cse"; opt -passes='reassociate,early-cse' -S reassoc.ll | sed -n '/^define i32 @cse/,/^}/p'
Output (complete):
=== reassociate
loop: ; preds = %loop, %entry
%i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
%s = phi i32 [ 0, %entry ], [ %s.next, %loop ]
%t1 = add i32 %a, 4
%t2 = add i32 %t1, %b
%t3 = add i32 %t2, %i
%s.next = add i32 %t3, %s
%i.next = add i32 %i, 1
%c = icmp slt i32 %i.next, %n
br i1 %c, label %loop, label %exit
define i32 @cse(i32 %a, i32 %b, i32 %c) {
%x = add i32 %b, %a
%y = add i32 %x, %c
%z = add i32 %b, %a
%w = add i32 %z, %c
%r = xor i32 %y, %w
ret i32 %r
}
=== reassociate,licm
define i32 @sum(i32 %a, i32 %b, i32 %n) {
entry:
%t1 = add i32 %a, 4
%t2 = add i32 %t1, %b
br label %loop
loop: ; preds = %loop, %entry
%i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
%s = phi i32 [ 0, %entry ], [ %s.next, %loop ]
%t3 = add i32 %t2, %i
%s.next = add i32 %t3, %s
%i.next = add i32 %i, 1
%c = icmp slt i32 %i.next, %n
br i1 %c, label %loop, label %exit
exit: ; preds = %loop
=== reassociate,early-cse
define i32 @cse(i32 %a, i32 %b, i32 %c) {
%x = add i32 %b, %a
%y = add i32 %x, %c
ret i32 0
}
What to notice: in @sum, Reassociate rebuilt the tree so that a + 4 + b (arguments and a constant, low rank) comes first and the phis i and s last; LICM then hoisted %t1 and %t2 into entry (Theorem 13.6.9). In @cse, both sums became (b + a) + c, and EarlyCSE found them equal, so the xor folded to 0. LLVM gives each argument its own rank and puts b before a; the grouping principle is the same as E5's.
LLVM's rank map in the source
Reproduce (LLVM 23.1.2 sources; curl):
URL=https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/llvm/lib/Transforms/Scalar/Reassociate.cpp
curl -sL $URL > Reassociate.cpp
sed -n '/^\/\/ This pass reassociates commutative expressions/,/^\/\/ than values not in loops\./p' Reassociate.cpp
sed -n '/^void ReassociatePass::BuildRankMap/,/^}/p' Reassociate.cpp
Output (complete):
// This pass reassociates commutative expressions in an order that is designed
// to promote better constant propagation, GCSE, LICM, PRE, etc.
//
// For example: 4 + (x + 5) -> x + (4 + 5)
//
// In the implementation of this algorithm, constants are assigned rank = 0,
// function arguments are rank = 1, and other values are assigned ranks
// corresponding to the reverse post order traversal of current function
// (starting at 2), which effectively gives values in deep loops higher rank
// than values not in loops.
void ReassociatePass::BuildRankMap(Function &F,
ReversePostOrderTraversal<Function*> &RPOT) {
unsigned Rank = 2;
// Assign distinct ranks to function arguments.
for (auto &Arg : F.args()) {
ValueRankMap[&Arg] = ++Rank;
LLVM_DEBUG(dbgs() << "Calculated Rank[" << Arg.getName() << "] = " << Rank
<< "\n");
}
// Traverse basic blocks in ReversePostOrder.
for (BasicBlock *BB : RPOT) {
unsigned BBRank = RankMap[BB] = ++Rank << 16;
// Walk the basic block, adding precomputed ranks for any instructions that
// we cannot move. This ensures that the ranks for these instructions are
// all different in the block.
for (Instruction &I : *BB)
if (mayHaveNonDefUseDependency(I))
ValueRankMap[&I] = ++BBRank;
}
}
What to notice: the header comment describes Definition 13.6.2 (constants 0, arguments 1, blocks in RPO), but BuildRankMap actually gives the arguments distinct ranks 3, 4, … and each block the rank ++Rank << 16, with distinct ranks for non-movable instructions inside it: the implementation refines the comment, a small example of "read the code, not only the comment". getRank computes the maximum over operands for movable expressions (llvm/lib/Transforms/Scalar/Reassociate.cpp, ReassociatePass::getRank) [LLVM-Reassociate].
GCC's reassoc pass: ranks, folding constants, merging equal leaves
Reproduce (gcc 13.3.0; Linux):
cat > reas.c <<'EOF'
unsigned h(unsigned a, unsigned b, unsigned c) { return ((a + 3) + b) + ((c + 5) + a); }
EOF
gcc -O2 -c reas.c -fdump-tree-reassoc1-details=reas.txt -o /dev/null
grep 'Rank for\|Transforming\|^ into' reas.txt
sed -n '/<bb 2>/,/^}/p' reas.txt
Output (complete):
Rank for _10 is 1
Transforming _9 = _1 + c_6(D);
into _11 = _10 + 8;
Transforming _3 = _9 + a_4(D);
into _12 = _11 + c_6(D);
Transforming _7 = _3 + 8;
into _7 = _12 + b_5(D);
<bb 2> [local count: 1073741824]:
_10 = a_4(D) * 2;
_11 = _10 + 8;
_12 = _11 + c_6(D);
_7 = _12 + b_5(D);
return _7;
}
What to notice: GCC linearized ((a + 3) + b) + ((c + 5) + a) into one operand list, turned the two copies of a into a * 2, folded 3 + 5 into 8, and rebuilt the chain ordered by rank (gcc/tree-ssa-reassoc.cc, reassociate_bb and get_rank, releases/gcc-15.1.0) [GCC-reassoc]. The unsigned type matters: for signed int GCC must not reassociate in a way that introduces overflow (C's UB), the source-level analogue of Theorem 13.6.8 (a).
Tree-height reduction¶
MachineCombiner balances a reassociable floating-point chain
Reproduce (llc 23.1.2; any OS):
cat > th.ll <<'EOF'
define double @sum4(double %a, double %b, double %c, double %d) {
%t1 = fadd reassoc nsz double %a, %b
%t2 = fadd reassoc nsz double %t1, %c
%t3 = fadd reassoc nsz double %t2, %d
ret double %t3
}
define double @sum4_strict(double %a, double %b, double %c, double %d) {
%t1 = fadd double %a, %b
%t2 = fadd double %t1, %c
%t3 = fadd double %t2, %d
ret double %t3
}
EOF
llc -O2 -mtriple=x86_64-linux-gnu th.ll -o - | grep -P '^(sum4|\t(?!\.)).*' | grep -v '^\s*#'
Output (complete):
sum4: # @sum4
addsd %xmm1, %xmm0
addsd %xmm3, %xmm2
addsd %xmm2, %xmm0
retq
sum4_strict: # @sum4_strict
addsd %xmm1, %xmm0
addsd %xmm2, %xmm0
addsd %xmm3, %xmm0
retq
What to notice: with reassoc nsz, the chain ((a + b) + c) + d (height 3) became (a + b) + (c + d) (height 2): the two inner addsd are independent and can run in parallel. Without the flags the chain stays, because floating-point addition is not associative (Proposition 13.1.14). This is MachineCombiner using TargetInstrInfo::getMachineCombinerPatterns for reassociation (llvm/lib/CodeGen/MachineCombiner.cpp) [LLVM-MachineCombiner].
8. Comparison¶
| Technique | Power / precision | Speed (asymptotic · practical) | Output / error quality | Implementation effort | Typical use |
|---|---|---|---|---|---|
| Rank-based reassociation | Exposes loop invariants, constants and common subexpressions; can destroy sharing | \(O(n + \sum k \log k)\) · fast | Left-deep chains (long critical paths); must drop nsw |
Medium | Mid-level: LLVM Reassociate, GCC reassoc, pebble-reassociate |
| Tree-height reduction | Minimal critical path for one tree (with arrival times) | \(O(k \log k)\) per tree | Balanced trees need more registers | Low–medium | Back end with latencies: MachineCombiner; vectorized reductions |
Choose rank-based reassociation in the middle end, before LICM, GVN and constant propagation: it makes their jobs possible. Choose tree-height reduction late, when the target's latencies and issue width are known and the tree is on the critical path; the two conflict (a chain is best for code motion, a balanced tree for latency), which is why LLVM does them in different phases.
9. Assessment¶
| Technique | Quiz questions | Drills | Flashcards | Exercises |
|---|---|---|---|---|
| Rank-based reassociation | ranks-map, reassoc-order |
./course drill reassoc-ranks |
tag reassociation |
E5 (pebble-reassociate) |
| Tree-height reduction | tree-height, thr-greedy |
justification: the greedy trace is short and is asked in the quiz with concrete arrival times; a random drill would repeat Huffman-style merging without new decisions | tag tree-height |
— |
References¶
See the chapter references.