Wiki**3

Basic Blocks

Instruction sequence where control flow starts at the first instruction and ends at the last, without jumps (except at the last instruction).

Transformations in a basic block maintain the block semantics (considered as an atomic entity).

Optimization Levels

• User - algorithm- and application-level optimizations
• Generic - considers intermediate code (processor-independent)
• Peephole - window over a series of consecutive instructions
• Local - optimization within a basic block
• Inter-block (information flow between blocks, mainly cycles)
• Global - multiple jumps (jumps to jumps, jumps to the next instruction)

Machine-independent optimizations

Constant folding

Direct evaluation of expressions using only literal and known values:

 int *x = (int *)malloc(1024 * 4);
 int  y = 3;
 int  z = 20 * y + 10;
</c>

Becomes:
<c>
 int *x = (int *)malloc(4096);
 int  y = 3;
 int  z = 70;

Elimination of Common Subexpressions

Using temporary variables to store common results:

  d = c * (a + b)
  e = (a + b) / 2

Becomes:

  t = a + b
  d = c * t
  e = t / 2

Cycles / Loops

Loop unrolling

  for (i = 1; i < n; i++)
    a[i] = b[i] + 10;

Becomes:

  for (i = 1; i < (n/4)*4; i+=4) {
    a[i]   = b[i]   + 10;
    a[i+1] = b[i+1] + 10;
    a[i+2] = b[i+2] + 10;
    a[i+3] = b[i+3] + 10;
  }
 
  // rest of the cycle
  for (; i < n; i++)
    a[i] = b[i] + 10;

Moving invariant code

  for (i = 1; i < n; i++) {
    a[i] = b[i] + c * d;
    e = g[k];
  }

Becomes:

  t = c * d;
  for (i = 1; i < n; i++) {
    a[i] = b[i] + t;
  }
  e = g[k];

Variable induction

  for (i = 1; i < n; i++)
    k = i * 4 + m;

Becomes:

  k = m;
  for (i = 1; i < n; i++)
    k = k + 4;

Machine-dependent Optimizations

Algebraic Simplification

 xor eax,eax

instead of

 mov 0,eax

Strength Reduction

 x << 2 + x

instead of

 x * 5

Instruction Reordering

Reorder independent instructions in order to avoid register spilling.

Exercises

• Exercises 01
• Exercises 02
• Exercises 03
• Exercises 04
• Exercises 05
• Exercises 06