Local Optimisation and DAG Representation of Basic Blocks

• Basic Blocks and Control-Flow Graphs: what a basic block is and how a program is partitioned into blocks.
• DAGs for single expressions and the value-number method (see the note Intermediate Representations: Syntax Trees, DAGs and Three-Address Code).

• Leaf. One node per variable or constant whose initial value (on entry to the block) is used, written $a_0, b_0, \ldots$.
• Interior node. One node per distinct operation $\langle op, \text{left child}, \text{right child}\rangle$ on current values.
• Labels. Each node carries the list of variables whose current value it is. An assignment $x = \ldots$ moves label $x$ to the new (or found) node and removes it from any other.
• Local common subexpression. An instruction whose operator and operand nodes match an existing node: no new node is created, and only a label is added.
• Live on exit. Variables whose values may be used after the block. Only nodes reachable from them need code.
• Dead code. An instruction whose result is not live on exit and not used later in the block.

Building the DAG of a block

1. Find the node for the current value of $y$: the node labelled $y$ if any, otherwise a leaf $y_0$ (created if needed). Do the same for $z$.
2. Look for an existing node with operator $op$ and exactly these children. If one exists, use it; otherwise create it.
3. Remove label $x$ from whatever node had it, and attach $x$ to this node.

Example 1: a block with a hidden trap

1) t1 = a * b
2) t2 = a * b
3) c  = t2 + d
4) a  = c - d
5) e  = a * b
6) t3 = c - d

Regenerating code from the DAG

t1 = a * b
c  = t1 + d
a  = c - d
e  = a * b

Example 2: shared nodes despite a redefinition

a = b + c
b = a - d
c = b + c
d = a - d

Example 3: counting nodes, edges and instructions

1) t1 = a + b
2) t2 = a + b
3) t3 = t1 * c
4) b  = t3 - d
5) t4 = a + b
6) t5 = t2 * c
7) x  = t4 + t5

t1 = a + b
t2 = t1 * c
b  = t2 - d
t3 = a + b
x  = t3 + t2

Other local transformations

• Dead-code elimination. Delete any root node (no parents) that has no live label, and repeat.
• Constant folding. Evaluate operations on constants at compile time: x = 2 * 3.14 becomes x = 6.28.
• Algebraic identities. $x + 0 = x$, $x \times 1 = x$, $x - x = 0$ (for integers), $x / 1 = x$.
• Reduction in strength. Replace an expensive operator by a cheaper one: $x^2 \to x \times x$, $2 \times x \to x + x$, $x / 2 \to x \times 0.5$ for floating point, multiplication by a power of 2 by a shift for unsigned integers.
• Commutativity and associativity. If the compiler may use them, $x \times y$ and $y \times x$ can share a node; the basic method does not assume this.
• Copy propagation within the block. After x = y, a later use of x may read y only if that copy reaches the use with no intervening redefinition or possible modification of either x or y, including through aliases. This may make the copy dead. In x=y; y=9; z=x, replacing z=x by z=y is invalid.

Array references and pointers

x = a[i]
a[j] = y
z = a[i]

Peephole optimisation

• Redundant loads and stores: after ST a, R0, an immediate LD R0, a can go (if the load is not a jump target).
• Unreachable code: instructions after an unconditional jump with no label pointing to them.
• Jumps to jumps: goto L1 where L1: goto L2 becomes goto L2.
• Algebraic simplification and strength reduction on target instructions.
• Machine idioms: using auto-increment addressing or special instructions.

• DAG nodes = leaves for initial values used + distinct operations on current values. Count carefully after each reassignment.
• Edges = 2 per binary node + 1 per unary node.
• A DAG detects only local common subexpressions; global ones across blocks need available-expression analysis (see the note Common Subexpression Elimination).
• Textual equality is neither necessary nor sufficient: equal text can denote different values (Example 1, line 5) and different text can denote equal values.
• Order of regeneration matters: a label may be assigned only when no later node still needs the variable's old value.

• "A redefined variable gets a new leaf." A leaf stands only for the value on entry; after a redefinition the variable labels the node for its new value, which may be an existing leaf for a copy or an operation node for a computation.
• "Copy statements create nodes." They only attach a label.
• "Array assignments can be optimised like scalars." They must kill nodes that read the same array.

• Count DAG nodes and edges. Apply this to a block; watch reassigned variables and repeated expressions.
• Minimum number of instructions. After local common-subexpression and dead-code elimination, given the variables live on exit.
• Spot the trap. Where a textual repeat is not a common subexpression because an operand changed.
• The opposite trap. Different text, same value, as t5 = t2 * c and t3 = t1 * c when $t_1$ and $t_2$ label one node (Example 3).
• Order constraints when regenerating. An instruction that overwrites a variable must follow every instruction that reads the variable's old value.
• Name the transformation. Constant folding, strength reduction, algebraic simplification, copy propagation, dead-code elimination, peephole patterns.
• Array and pointer kills. As a reason an apparent common subexpression is not one.

• Basic Blocks and Control-Flow Graphs: prerequisite. The unit that local optimisation works on.
• Common Subexpression Elimination: dependent. Extending reuse of computed values across blocks.