(→Strength Reduction) |
|||
Line 21: | Line 21: | ||
Direct evaluation of expressions using only literal and known values: | Direct evaluation of expressions using only literal and known values: | ||
− | <c> | + | <source lang="c"> |
int *x = (int *)malloc(1024 * 4); | int *x = (int *)malloc(1024 * 4); | ||
int y = 3; | int y = 3; | ||
Line 32: | Line 32: | ||
int y = 3; | int y = 3; | ||
int z = 70; | int z = 70; | ||
− | </ | + | </source> |
== Elimination of Common Subexpressions == | == Elimination of Common Subexpressions == | ||
Using temporary variables to store common results: | Using temporary variables to store common results: | ||
− | <c> | + | <source lang="c"> |
d = c * (a + b) | d = c * (a + b) | ||
e = (a + b) / 2 | e = (a + b) / 2 | ||
− | </ | + | </source> |
Becomes: | Becomes: | ||
− | <c> | + | <source lang="c"> |
t = a + b | t = a + b | ||
d = c * t | d = c * t | ||
e = t / 2 | e = t / 2 | ||
− | </ | + | </source> |
== Cycles / Loops == | == Cycles / Loops == | ||
=== Loop unrolling === | === Loop unrolling === | ||
− | <c> | + | <source lang="c"> |
for (i = 1; i < n; i++) | for (i = 1; i < n; i++) | ||
a[i] = b[i] + 10; | a[i] = b[i] + 10; | ||
− | </ | + | </source> |
Becomes: | Becomes: | ||
− | <c> | + | <source lang="c"> |
for (i = 1; i < (n/4)*4; i+=4) { | for (i = 1; i < (n/4)*4; i+=4) { | ||
a[i] = b[i] + 10; | a[i] = b[i] + 10; | ||
Line 69: | Line 69: | ||
for (; i < n; i++) | for (; i < n; i++) | ||
a[i] = b[i] + 10; | a[i] = b[i] + 10; | ||
− | </ | + | </source> |
=== Moving invariant code === | === Moving invariant code === | ||
− | <c> | + | <source lang="c"> |
for (i = 1; i < n; i++) { | for (i = 1; i < n; i++) { | ||
a[i] = b[i] + c * d; | a[i] = b[i] + c * d; | ||
e = g[k]; | e = g[k]; | ||
} | } | ||
− | </ | + | </source> |
Becomes: | Becomes: | ||
− | <c> | + | <source lang="c"> |
t = c * d; | t = c * d; | ||
for (i = 1; i < n; i++) { | for (i = 1; i < n; i++) { | ||
Line 86: | Line 86: | ||
} | } | ||
e = g[k]; | e = g[k]; | ||
− | </ | + | </source> |
=== Variable induction === | === Variable induction === | ||
− | <c> | + | <source lang="c"> |
for (i = 1; i < n; i++) | for (i = 1; i < n; i++) | ||
k = i * 4 + m; | k = i * 4 + m; | ||
− | </ | + | </source> |
Becomes: | Becomes: | ||
− | <c> | + | <source lang="c"> |
k = m; | k = m; | ||
for (i = 1; i < n; i++) | for (i = 1; i < n; i++) | ||
k = k + 4; | k = k + 4; | ||
− | </ | + | </source> |
=== Other === | === Other === | ||
Line 106: | Line 106: | ||
== Algebraic Simplification == | == Algebraic Simplification == | ||
− | <asm> | + | <source lang="asm"> |
xor eax,eax | xor eax,eax | ||
− | </ | + | </source> |
instead of | instead of | ||
− | <asm> | + | <source lang="asm"> |
mov 0,eax | mov 0,eax | ||
− | </ | + | </source> |
== Strength Reduction == | == Strength Reduction == | ||
− | <c> | + | <source lang="c"> |
x << 2 + x | x << 2 + x | ||
− | </ | + | </source> |
instead of | instead of | ||
− | <c> | + | <source lang="c"> |
x * 5 | x * 5 | ||
− | </ | + | </source> |
== Instruction Reordering == | == Instruction Reordering == |
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).
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;
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
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;
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];
for (i = 1; i < n; i++)
k = i * 4 + m;
Becomes:
k = m;
for (i = 1; i < n; i++)
k = k + 4;
xor eax,eax
instead of
mov 0,eax
x << 2 + x
instead of
x * 5
Reorder independent instructions in order to avoid register spilling.