Revision as of 18:09, 2 June 2012

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;

Becomes:

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;

Other

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.

Other

Exercises

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