DAG representation of basic blocks

Why it exists

A basic block is a list of instructions, but what it computes is a set of values that depend on each other, not a sequence. Drawing the block as a directed acyclic graph (DAG) shows this directly. Two instructions that compute the same expression from the same operands share one node, so common subexpressions are found automatically; values that are never used are exposed as nodes with no live identifier; and the order of the instructions can be rearranged in any order that respects the edges.

Prerequisites

You need basic blocks (basic blocks and control flow graphs).

Precise definitions

DAG of a basic block. A directed acyclic graph with these nodes:

• Leaf nodes, one for each variable or constant that is used before it is assigned in the block, labelled with the initial value of the variable, written with subscript 0 (b0, c0) or with the constant.
• Interior nodes, labelled by an operator, with edges to the nodes of their operands (in order, left and right). Every interior node has at least one identifier attached to it as a label (the variables assigned that value) — or none, if the value is only used as an intermediate result.

Each node also keeps the list of identifiers attached to it: the variables that hold that value at the end of the block.

Construction algorithm. Start with no nodes. For each instruction in order:

1. x = y op z: find the node for the current value of y (if there is none, create a leaf labelled y0), likewise for z. If a node labelled op with exactly these two children already exists, use it; otherwise create it. Attach x to this node and remove x from any other node it was attached to before.
2. x = op y: the same with one child.
3. x = y (copy): find the node for y and attach x to it; no new node.

Because attaching x removes it from its old node, the DAG always records the latest value of each variable. An assignment to a variable does not change nodes that used its old value (those nodes keep their children), which is why a redefinition correctly prevents sharing.

What the DAG tells.

• Common subexpressions: step 1 finds the existing node, no new node is created: a repeated expression with unchanged operands is one node.
• Nodes and edges: the number of nodes is (number of leaves) + (number of interior nodes); every interior node has as many edges as operands, so for binary operators the number of edges is twice the number of interior nodes. An interior node with two equal children has two parallel edges.
• Dead code: an interior node with no live identifier and no parent computes nothing used on exit and can be removed together with the nodes only it needs.
• Output: the DAG is evaluated in a topological order (children before parents): each interior node is computed once into one of its live identifiers (or a temporary if it has none but is used by another node), and the other live identifiers are copied from it. Different topological orders give different code, and a good order reduces registers and loads.

Limits of the simple DAG. For an array element x = a[i] or a[j] = y the DAG must consider that a store a[j] may change what a[i] means (if i and j can be equal): the stores kill the nodes of the earlier loads from the same array; similarly an assignment through a pointer or a procedure call can change anything it may reach. The textbook handles these with extra rules (nodes for array operations, ordering constraints); the algorithm above is for scalar variables.

How it works

The block a = b + c; b = a - d; c = b + c; d = a - d (all four variables live on exit). Watch the table of nodes: instructions 1 and 2 create interior nodes, instruction 3 creates a new interior node although it looks like instruction 1 (the b in it is the value of node 5, not b0), and instruction 4 creates no new node: a - d0 already exists as node 5, so d is simply attached to it, next to b. The final DAG has 6 nodes (three leaves b0, c0, d0 and three interior nodes) and 6 edges, and the code regenerated from it is a = b + c; b = a - d; c = b + c; d = b.

When only z is live after x = a + b; y = a + b; z = x * y: the second instruction finds the node of a + b again, and z = x * y becomes a node whose two children are the same node (two edges to it). Neither x nor y is live, so the sum is held in a temporary and z is computed as t1 * t1: the block shrinks from 3 to 2 instructions.

And the expression from the beginning of the intermediate-code pages. The two occurrences of -c and of b * -c become one node each.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The DAG is built per basic block of the intermediate code, and it implements the common subexpression and dead-code parts of local optimisation, where the same results are obtained by value numbering. Which variables are live on exit is a liveness question.

PYQs

Consider the basic block given below.

a= b + c

c =a + d

d =b + c

e =d - b
a =e + b

The minim um number of nodes and edges present
in the DAG representation of the above basic block
respectively are

Self-check

Revision card

References