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: <c>

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;

</c>

Elimination of Common Subexpressions

Using temporary variables to store common results: <c>

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

</c>

Becomes: <c>

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

</c>

Cycles / Loops

Loop unrolling

<c>

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

</c>

Becomes: <c>

 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;

</c>

Moving invariant code

<c>

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

</c>

Becomes: <c>

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

</c>

Variable induction

<c>

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

</c>

Becomes: <c>

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

</c>

Machine-dependent Optimizations

Algebraic Simplification

<asm>

xor eax,eax

</asm>

instead of <asm>

mov 0,eax

</asm>

Strength Reduction

<c>

x << 2 + x

</c>

instead of <c>

x * 5

</c>

Instruction Reordering

Reorder independent instructions in order to avoid register spilling.

Exercises

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