Suppose a teacher writes on the board "find (a + b) × c, and also find (b + a) × c". A sharp student notices that both questions have the same answer and works it out only once. A compiler can be taught to be that sharp student, but first it needs a picture of the code in which "the same value" is easy to spot.
In Basic Blocks & Flow Graphs we cut a program into basic blocks: straight-line pieces of three-address code with one entry and one exit. In this chapter we look inside one basic block and build a picture of how its values are computed from one another. That picture is a directed acyclic graph, or DAG.
The DAG of a basic block is a directed acyclic graph in which every leaf stands for the initial value of a variable or a constant, every interior node stands for an operator applied to its children, and every node carries a (possibly empty) list of the variables that hold its value. A computation that the builder recognises as already done (same operator, same child nodes) is not repeated: it is represented by the existing node.
We will build DAGs step by step, see how they expose common subexpressions and dead code, regenerate shorter code from them, handle arrays and pointers safely, and solve the "how many nodes and edges" questions that appear in exams. Every DAG and every rewritten block in this chapter was produced or checked by a small Python program, and each rewritten block was tested against the original on thousands of random inputs.
Why Build a DAG?
Three-address code is a list of instructions. A list is great for executing, but poor for answering questions like these:
Is
t2 = b + acomputing something we already have int1?Is the value assigned to
xever used before the block ends?Which variables does the block read before writing them?
Can two instructions be swapped without changing the result?
A DAG answers all of these by its shape. Two instructions that compute the same value land on the same node. A value that nobody uses becomes a node with no parent and no useful name. The leaves tell you exactly which incoming values the block depends on. And the edges tell you the only ordering that really matters: a node must be computed after its children.
You have already met a close relative: the syntax tree of an expression. A DAG is a syntax tree in which identical subtrees are shared instead of repeated. The difference is that a block DAG covers many statements at once and also tracks which variable holds which value as assignments happen.
Expression: (a + b) * (a + b)
Syntax tree DAG
* *
/ \ / \
+ + \ /
/ \ / \ +
a b a b / \
a b
7 nodes 4 nodes (the + node has two edges coming into it from *)Parts of a Basic-Block DAG
Part | What it represents | How it is written |
|---|---|---|
Leaf | The initial value a variable has when the block starts, or a constant | Variable name with subscript 0, e.g. b0; constants as they are, e.g. 4 |
Interior node | The result of applying an operator to the values of its children | Labelled by the operator: +, *, -, =[ ], [ ]=, ... |
Attached identifiers | The variables that hold this node's value at the current point (at the end, once construction finishes) | A list next to the node, e.g. {t1, t2} |
Edges | From an operator node to each operand node | Ordered: left operand, right operand |
Output nodes | Nodes whose value is still needed after the block (a live variable is attached) | Determined using liveness information on exit |
Why the subscript 0? Because inside a block a variable can be overwritten. If a is assigned halfway through, "a" in the first half and "a" in the second half are different values. a0 always means "whatever a held when we entered the block", so it never becomes ambiguous.
Why acyclic? Every node is created from nodes that already exist, so edges always point from a newer node to an older one. Inside a basic block there are no jumps backward, so a cycle can never form. (Loops show up between blocks, in the flow graph, never inside one block.)
The Construction Algorithm
We process the instructions of the block from first to last, keeping a table node(x) that tells us which node currently holds the value of each variable x.
For each instruction, in order:
Case 1: x = y op z
1. If node(y) is undefined, create a leaf y0 and set node(y) = that leaf.
Do the same for z.
2. Look for an existing node n with operator op, left child node(y)
and right child node(z). (If op is commutative, like + or *,
also accept children in the swapped order.)
If there is none, create it.
3. Remove x from the identifier list of the old node(x), if any.
Append x to the list of n, and set node(x) = n.
Case 2: x = op y (unary minus, not, type conversion ...)
Same as Case 1 with a single child.
Case 3: x = y (copy)
Do not create a node. Just let n = node(y) (create leaf y0 if needed),
then do step 3: move x to n.Step 2 is where the magic happens. "Look for an existing node" is exactly the check that finds common subexpressions. And step 3, removing x from its old node, is what keeps the DAG honest when a variable is overwritten: the old node still exists (other nodes may depend on it), but it no longer belongs to x.
Key rule: a node is reused only if its operator AND its children are the same nodes. The same variable names are not enough, because a variable may have changed in between.
Worked Example 1: Spotting Common Subexpressions
Consider this block:
(1) t1 = a + b
(2) t2 = b + a
(3) t3 = t1 * c
(4) t4 = t2 * c
(5) a = t3 - d
(6) t5 = a + b
(7) e = t4 + t5We build the DAG one instruction at a time. Node numbers n1, n2, ... are given in the order the nodes are created.
Instr. | What happens | node(...) after |
|---|---|---|
(1) t1 = a + b | Create leaves a0 (n1) and b0 (n2). No + node with children (n1, n2) exists, so create n3 = +(n1, n2). Attach t1. | a=n1, b=n2, t1=n3 |
(2) t2 = b + a | node(b)=n2, node(a)=n1. Look for +(n2, n1). Since + is commutative, n3 = +(n1, n2) matches. No new node. Attach t2 to n3. | t2=n3 |
(3) t3 = t1 * c | Create leaf c0 (n4). Create n5 = *(n3, n4). Attach t3. | c=n4, t3=n5 |
(4) t4 = t2 * c | node(t2)=n3, node(c)=n4, so we look for *(n3, n4): it is n5. No new node. Attach t4 to n5. | t4=n5 |
(5) a = t3 - d | Create leaf d0 (n6). Create n7 = -(n5, n6). Attach a to n7. (a was on leaf n1 only as its initial value; now node(a)=n7.) | d=n6, a=n7 |
(6) t5 = a + b | node(a)=n7, node(b)=n2. Look for +(n7, n2). n3 is +(n1, n2), which has a different left child. So create n8 = +(n7, n2). Attach t5. | t5=n8 |
(7) e = t4 + t5 | node(t4)=n5, node(t5)=n8. Create n9 = +(n5, n8). Attach e. | e=n9 |
The finished DAG:
Node Operator Children Attached identifiers
n1 leaf a0 - -
n2 leaf b0 - -
n3 + n1, n2 t1, t2
n4 leaf c0 - -
n5 * n3, n4 t3, t4
n6 leaf d0 - -
n7 - n5, n6 a
n8 + n7, n2 t5
n9 + n5, n8 e
n9: + {e}
/ \
/ n8: + {t5}
/ / \
/ n7: - {a} \
/ / \ \
n5: * {t3, t4} d0 \
/ \ \
n3: + {t1, t2} c0 \
/ \ \
a0 b0 <-----------------------+ (n8's right child is the leaf b0)
9 nodes (4 leaves + 5 interior), 10 edgesLook at what the DAG has told us:
t1andt2sit on the same node: b + a is a common subexpression of a + b.t3andt4sit on the same node: the second multiplication is redundant.t5 = a + bis not a common subexpression, even though the text "a + b" appeared in line (1). The variableawas changed in line (5), and the DAG noticed because node(a) moved from n1 to n7.
That last point is the most common trap in exams and in hand optimisation: always ask whether an operand was redefined between the two occurrences.
Rebuilding Code from the DAG
A DAG is useful because we can turn it back into code, and the new code is often shorter. The rules are:
Generate one instruction for each interior node, and only after its children are available.
For each node, pick one attached variable to receive the result. Prefer a variable that is live on exit from the block (needed later). If none of its variables is live, use a temporary.
If a node has several attached variables that are live on exit, compute into one of them and add copies (
y = x) for the others.If no live variable is attached to a node and no other node uses it, do not generate it at all: it is dead.
Be careful with the order when a variable that is a leaf (its initial value is still needed) gets overwritten. Its initial value must be used before the overwrite.
Assume only a and e are live on exit from Example 1 (all t's are temporaries). The rebuilt block is:
t1 = a + b // n3 (uses a0, so it must come before a is overwritten)
t3 = t1 * c // n5
a = t3 - d // n7
t5 = a + b // n8
e = t3 + t5 // n9Seven instructions became five, and the program computes the same final a and e. (We checked this by running both versions on 2000 random sets of inputs.) Notice that the order of t1 = a + b and a = t3 - d cannot be swapped: t1 needs the old a.
Worked Example 2: When a Variable Is Redefined
(1) p = q + r
(2) s = p * t
(3) q = p * t
(4) u = q + r
(5) v = s + rInstr. | What happens |
|---|---|
(1) | Leaves q0 (n1), r0 (n2). New n3 = +(n1, n2) with {p}. |
(2) | Leaf t0 (n4). New n5 = *(n3, n4) with {s}. |
(3) | *(n3, n4) already exists: n5. Attach q to n5. Now node(q) = n5, not q0. Labels of n5: {s, q}. |
(4) | node(q) = n5, node(r) = n2. No +(n5, n2) yet, so new n6 = +(n5, n2) with {u}. |
(5) | node(s) = n5, node(r) = n2. +(n5, n2) exists: n6. Attach v. Labels of n6: {u, v}. |
n6: + {u, v}
/ \
n5: * {s, q} \
/ \ \
n3: + {p} t0 |
/ \ |
q0 r0 <------------+
6 nodes (3 leaves: q0, r0, t0 + 3 interior), 6 edgesLine (5) looks completely different from line (4) as text (s + r versus q + r), yet the DAG shows they compute the same value, because at that moment s and q hold the same value. Textual matching would miss this; the DAG does not.
If all of p, s, q, u, v are live on exit, the rebuilt code is:
p = q + r
s = p * t
q = s // copy: q and s share node n5
u = s + r
v = u // copy: u and v share node n6Two multiplications/additions were replaced by cheap copies. If only v is live on exit, the DAG shows that p, s, q and u are just stepping stones, and the block shrinks to:
t1 = q + r
t2 = t1 * t
v = t2 + rValue Numbering: How the Search Is Made Fast
Step 2 of the algorithm says "look for an existing node". Scanning every node each time would be slow for big blocks. Real compilers use the value-number method: every node gets a number (its value number), and a hash table maps a signature to that number.
signature of a leaf : the name, e.g. "b0", or the constant
signature of an op node : (op, value number of left child, value number of right child)For a commutative operator we sort the two child numbers before hashing, so (+, 1, 2) and (+, 2, 1) give the same key. Here is the table for Example 1 (value numbers equal the node numbers we used):
Signature (key) | Value number | Found or created at |
|---|---|---|
a0 | 1 | created (1) |
b0 | 2 | created (1) |
(+, 1, 2) | 3 | created (1), found again (2) |
c0 | 4 | created (3) |
(*, 3, 4) | 5 | created (3), found again (4) |
d0 | 6 | created (5) |
(-, 5, 6) | 7 | created (5) |
(+, 2, 7) | 8 | created (6) |
(+, 5, 8) | 9 | created (7) |
With hashing, each instruction is processed in expected O(1) time, so building the DAG for a block of n instructions takes about O(n). Note that minus is not commutative, so its key keeps the order (5, 6).
What a DAG Is Used For
Use | How the DAG shows it |
|---|---|
Local common subexpression elimination | Two instructions that compute the same value get the same node; we generate it once. |
Dead code elimination | Delete any root (node with no parents) that has no live variable attached. Repeat, since deleting a root can turn its children into new dead roots. |
Copy propagation inside the block |
|
Reordering instructions | Any order that evaluates children before parents (plus the extra ordering rules for arrays and pointers below) is valid. The code generator can pick an order that needs fewer registers. |
Which names are used in the block | The leaves: these are the values that flow into the block. |
Which values are visible after the block | Each variable's final node; these are the values that flow out. |
Algebraic simplification | Apply identities (x + 0 = x, x * 1 = x, ...) while building, so more nodes become shareable. |
Dead Code Elimination on a DAG
Take Example 2 with only v live on exit. The roots are the nodes nobody points to. Only n6 is a root, and it has v attached, so nothing is removed. Now imagine a sixth instruction w = q * r with w dead: it would create n7 = *(n5, n2), a root with only a dead label, so we delete it. Its children (n5, n2) still have other parents, so the deletion stops there. If they did not, they would become roots and we would check them too.
Algebraic Identities and Constant Folding
The basic algorithm only matches nodes that are written in exactly the same way (allowing swapped operands for commutative operators). A smarter builder simplifies before searching:
Identity | Effect in the DAG |
|---|---|
x + 0 = 0 + x = x, x - 0 = x | No new node; the result is node(x) |
x * 1 = 1 * x = x, x / 1 = x | No new node |
x * 2 → x + x (or a shift) | Cheaper operator (strength reduction) |
x2 → x * x | Avoids a call to a power function |
2 * 3.14 → 6.28 | Constant folding: both children are constants, so compute at compile time and make a constant leaf |
a > b ⇔ a - b > 0 (on machines that compare through subtraction, and only if the subtraction cannot overflow) | Lets a later |
A word of caution: identities that are true in mathematics are not always true for machine numbers. For floating-point values, x * 0 = 0 fails when x is NaN or infinity, and (a + b) + c may differ from a + (b + c) because of rounding. Compilers only apply such rules when the language allows it (for example, GCC's -ffast-math).
Arrays, Pointers and Procedure Calls
Sharing nodes is only safe if the value really cannot have changed. With plain variables the compiler knows exactly what each assignment changes. With arrays and pointers it often does not.
(1) x = a[i]
(2) a[j] = y
(3) z = a[i]It is tempting to say "line (3) is the same as line (1), so z = x". That is wrong if i == j at run time: line (2) then changed a[i]. The compiler usually cannot know whether i equals j. The safe treatment is:
An array read
x = a[i]is a node with operator=[ ]and children a0 and node(i).An array write
a[j] = yis a node with operator[ ]=and three children: a0, node(j), node(y). Creating it kills every existing node whose value depends on arraya. A killed node may not receive new labels and can never be matched again.
Node Operator Children Labels Status
n1 leaf a0 - -
n2 leaf i0 - -
n3 =[] n1, n2 x KILLED by n6
n4 leaf j0 - -
n5 leaf y0 - -
n6 []= n1, n4, n5 -
n7 =[] n1, n2 z new node, because n3 is killedWhen code is rebuilt, there is one more ordering rule: n3 (the read) must be evaluated before n6 (the write), and n7 after it, even though no ordinary edge says so. The same idea applies to:
Assignment through a pointer
*p = w: if the compiler does not know what p points to, it must kill every node that could be read through p, which in the worst case means every node for a variable whose address may have been taken.Procedure calls: a called function may change any variable it can reach (globals, anything passed by reference), so a call kills all nodes that depend on those variables.
This is why programs heavy on pointers are harder to optimise, and why languages and compilers care about alias analysis (C's restrict keyword exists to promise the compiler that two pointers do not overlap).
DAG vs Related Representations
Point | Syntax tree | DAG of a basic block | Flow graph |
|---|---|---|---|
Represents | One expression or statement | All values computed in one basic block | The whole procedure: blocks and jumps between them |
Nodes | Operators and operands | Distinct values (operators, initial values, constants) | Basic blocks |
Sharing | None: repeated subexpressions appear repeatedly | Identical values share one node | Not applicable |
Cycles | Never (a tree) | Never | Yes, loops create cycles |
Main use | Front end, semantic checks, translation | Local optimisation, code generation for a block | Global optimisation, data-flow analysis |
Solved Problems
Problem 1: Count nodes and edges
Construct the DAG and give the number of nodes and edges:
t1 = 4 * i
x = t1
t2 = 4 * i
t3 = x + t2
i = t3Solution.
t1 = 4 * i: leaves 4 (n1) and i0 (n2); node n3 = *(n1, n2) with {t1}.
x = t1: a copy. No node; x joins n3. Labels {t1, x}.
t2 = 4 * i: *(n1, n2) exists (i has not changed yet). t2 joins n3. Labels {t1, x, t2}.
t3 = x + t2: both operands are n3. New n4 = +(n3, n3) with {t3}.
i = t3: a copy; i joins n4. Labels of n4: {t3, i}.
n4: + {t3, i}
|| (both edges go to n3)
n3: * {t1, x, t2}
/ \
4 i04 nodes and 4 edges. Note that n4 has two separate edges to n3 (left operand and right operand), so they both count. If only i is live on exit, the block becomes t1 = 4 * i followed by i = t1 + t1.
Problem 2: Is it a common subexpression?
(1) a = b + c
(2) b = a - d
(3) e = b + cIs b + c in line (3) a common subexpression of line (1)?
Solution. No. Line (2) redefines b, so node(b) is the "-" node when line (3) is processed, while the "+" node of line (1) has the leaf b0 as its left child. The children differ, so a new node is created. The DAG has leaves b0, c0, d0 and interior nodes +, -, + : 6 nodes, 6 edges.
Problem 3: Hidden common subexpression
(1) x = y * z
(2) w = x
(3) y = w
(4) u = y * zHow many interior nodes does the DAG have?
Solution. Line (1) creates *(y0, z0) labelled x. Lines (2) and (3) are copies: w and y both join the * node. In line (4), node(y) is the * node itself, not y0, so we need *(*-node, z0), which is new. Two interior nodes (plus 2 leaves). Line (4) is not a repeat of line (1): y now holds y0·z0, so u = y0·z0·z0.
Problem 4: Rebuild with minimum instructions
For Example 2 in this chapter, if s and v are live on exit, what is the shortest rebuilt code?
Solution. Nodes needed: n3 (feeds n5), n5 (holds s, feeds n6), n6 (holds v). p, q and u are not live, so n3 gets a temporary and no copies are needed. The temporary must be a fresh name: we cannot call it t, because t is a program variable whose initial value n5 still needs. Using T1:
T1 = q + r
s = T1 * t
v = s + rThree instructions, compared with five in the original.
Common Mistakes
Matching by text instead of by node. "a + b" appearing twice is a common subexpression only if neither a nor b changed in between. Always look up node(a) and node(b) at that moment.
Forgetting to move a label. When x is reassigned, x must be removed from its old node. If you leave it there, you may later share a stale value.
Creating a node for a copy.
x = ymakes no new node; x is attached to node(y).Ignoring commutativity, or applying it to the wrong operators. b + a matches a + b, but b - a does not match a - b.
Counting edges wrongly. An edge goes from each operator node to each operand. x + x has two edges to the same child. Leaves have no outgoing edges.
Sharing array reads across an array write.
a[j] = ykills earliera[i]nodes because i may equal j.Treating a DAG as a flow graph. A basic-block DAG describes one block. Loops and branches live in the flow graph, not in the DAG.
Interview and Exam Questions
What do the leaves and interior nodes of a basic-block DAG represent?
Leaves are the initial values of variables on entry to the block (written x0) or constants. Interior nodes are operators applied to their children, and each carries the list of variables currently holding that value.
Why is it called "acyclic"?
A node is always created from nodes that already exist, so every edge points from a newer node to an older one. A basic block has no backward jumps, so no cycle can form.
How does a DAG detect common subexpressions?
Before creating a node for x = y op z, the builder searches for an existing node with the same operator and the same child nodes (in either order for a commutative operator). If found, x is attached to it instead of creating a new node.
How is dead code removed using a DAG?
Repeatedly delete any root that has no live variable attached. A deleted root's children may become roots and are checked in turn.
Why can't a[i] be reused after a[j] = y?
Because i and j may be equal at run time, so the write may have changed a[i]. The [ ]= node kills all nodes that read from a, and the next read of a[i] creates a fresh node.
What is value numbering?
An implementation of DAG construction where each node has a number and a hash table maps the signature (op, left value number, right value number) to that number, so finding an existing node takes expected constant time.
Is a DAG optimisation local or global?
Local: it works within one basic block. Finding common subexpressions across blocks needs global techniques such as available-expressions analysis (see Data-Flow Analysis).
(GATE-style) How many nodes are in the DAG of: a = b * c; d = b * c; e = a + d?
Leaves b0, c0; one * node labelled {a, d}; one + node with both edges to the * node. Total 4 nodes and 4 edges.
Summary
The DAG of a basic block has leaves for initial values (x0) and constants, interior nodes for operators, and a list of variables attached to each node.
It is built instruction by instruction using node(x). A new node is created only if no node with the same operator and the same children exists; assignments move the variable's label.
Copies
x = ycreate no node. Commutative operators match in either order.The DAG gives local common subexpression elimination, dead code elimination, copy propagation, algebraic simplification and freedom to reorder.
Value numbering with a hash table makes construction fast.
When rebuilding code, compute each needed node once, prefer live variables as targets, add copies for extra live names, and respect ordering for overwritten leaves.
Array writes, pointer writes and calls kill nodes they might affect, and impose extra ordering.
A DAG optimises one block. To optimise across blocks and loops, see the next chapters, Code Optimization Techniques and Data-Flow Analysis.