Chapter 29 of 33

DAG Representation of Basic Blocks

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 + a computing something we already have in t1?

  • Is the value assigned to x ever 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 + t5

We 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 edges

Look at what the DAG has told us:

  • t1 and t2 sit on the same node: b + a is a common subexpression of a + b.

  • t3 and t4 sit on the same node: the second multiplication is redundant.

  • t5 = a + b is not a common subexpression, even though the text "a + b" appeared in line (1). The variable a was 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:

  1. Generate one instruction for each interior node, and only after its children are available.

  2. 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.

  3. 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.

  4. If no live variable is attached to a node and no other node uses it, do not generate it at all: it is dead.

  5. 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        // n9

Seven 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 + r

Instr.

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 edges

Line (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 n6

Two 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 + r

Value 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

x = y creates no node; x simply joins y's node, and later uses of x refer straight to that node.

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 t = a - b share the comparison's node

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] = y is a node with operator [ ]= and three children: a0, node(j), node(y). Creating it kills every existing node whose value depends on array a. 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 killed

When 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).


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  = t3

Solution.

  • 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      i0

4 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 + c

Is 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 * z

How 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 + r

Three 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 = y makes 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] = y kills earlier a[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 = y create 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.