Local optimisation

Why it exists

The code produced by a straightforward translation is wasteful: the same expression is computed twice, a variable is copied around, a constant is added to zero, a temporary is never used. Optimisation rewrites the code so that it runs faster or is smaller without changing what it computes. The easiest place to start is the basic block (basic blocks): control cannot jump into the middle of it or out of it, so the effect of each instruction on the values is easy to follow. Optimisation inside one block is local optimisation; across blocks it needs data flow analysis (data flow framework).

Prerequisites

You need basic blocks (basic blocks and control flow graphs) and three-address code.

Precise definitions

Safety. A transformation is safe (a correct optimisation) if the optimised program computes the same result as the original for all inputs. In a block this means: the variables that are live on exit (used later, in other blocks) get the same values, and the observable effects (printing, memory stores to memory visible elsewhere) are the same.

Local transformations on a basic block.

Local value numbering (LVN). A systematic algorithm that does the first six of these at once. Give every distinct value a number. Keep a table from variables to the number of the value they hold and from expressions $(\text{op}, v_1, v_2)$ to a value number. For each instruction $x = y \text{ op } z$ in order:

1. Look up (or create) the value numbers $v_y$, $v_z$ of the operands. If both are constants, fold; if an identity applies (y + 0, y * 1, ...), the result has the value number of the other operand.
2. Otherwise look up $(\text{op}, v_y, v_z)$ (for a commutative operator sort the two numbers). If it is in the table, the value has been computed already by some variable: replace the instruction by a copy from that variable (common subexpression elimination). If not, give it a new number and keep the instruction (writing each operand by the variable that currently holds the value: copy propagation).
3. Make $x$ hold that value number (and remove $x$ from the old value it held).

After the pass, delete assignments to variables that are not live on exit and are not used later in the block (dead-code elimination, by a backward scan). The key point is step 3: an assignment kills the old value of the variable, so an expression that mentioned the old value is not a common subexpression any more.

Peephole optimisation. A small window (a peephole) slides over the generated code and replaces patterns by shorter or faster ones: redundant loads and stores (ST R0, a followed by LD a, R0: drop the load), unreachable code (after an unconditional jump), flow-of-control optimisation (a jump to a jump goto L1 ... L1: goto L2 becomes goto L2; a conditional jump over a jump is inverted), algebraic simplification and strength reduction, and use of machine idioms (increment instructions, special addressing modes). It is applied to target code, repeatedly, because one replacement can enable another.

Limits. Local optimisation sees one block only. It cannot know that a value computed in an earlier block is still valid, or that a variable is dead because of what happens in a later block (the live-on-exit set must be given). That is the job of data flow analysis (liveness, available expressions).

How it works

The block a = b + c; b = a - d; c = b + c; d = a - d. The instruction 4 computes a - d again, and neither a nor d has changed since instruction 2: its value number is the same as that of b, so it becomes the copy d = b. The instruction 3, b + c, looks like instruction 1 but is not a common subexpression, because b was reassigned in instruction 2 (so it has a new value number). The animation shows the numbers v1, v2, ... of the values and the action taken for each instruction.

A block with constants, identities and copies. t1 = 4 makes a * t1 into a * 4; x = t2 + 0 is the same value as t2; y = x and z = y * 1 are again that value; w = a * 4 repeats t2 = a * 4. Everything after the second instruction becomes a copy of t2, and t1, which nobody uses, is dead.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The units of work are the basic blocks; the data structure that shares common subexpressions is the DAG of a block. What is live on exit comes from liveness analysis; availability of expressions across blocks is available expressions and global CSE. The instructions optimised here are three-address code.

PYQs

Consider the following ANSI C code segment:
z = x + 3 + y->f1 + y→f2;
  for (i = 0; i< 200; i = i + 2)
{
    if (z >i) {
      p = p + x + 3:
      q = q + y→f2;
    } else {
      p = p + y→f2:
      q = q + x + 3:
    }
}
Assume that the variable y points to a struct (allocated
on the heap) containing two fields f1 and f2, and the
local variables x, y, z, p, q, and i are allotted registers.
Common
sub-expression
elimination
(CSE)
optimization is applied on the code. The number of
addition and dereference operations (of the form y->f1
or y->f2) in the optimized code, respectively, are:

Which one of the following is FALSE?

The minimum number of arithmetic operations
required to evaluate the polynomial P(x) = x5 + 4x3 +
6x + 5 for a given value of x, using only one
temporary variable is ____ .

Consider the following C code segment.

 for (i = 0; < i< n; i++)

{

    for (j=0; j< n; j++)

    {

        if (i%2)

        {

            x += (4*j + 5*i);

            y += (7 + 4*j);

        }

    }

}

Which one is false?

Self-check

Revision card

References