Optimization Topics
From 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>
Other
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.