|
|
| (One intermediate revision by the same user not shown) |
| Line 1: |
Line 1: |
| {{NAVCompiladores}}
| | #REDIRECT [[ist:Optimization Topics]] |
| {{TOCright}}
| |
| == 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 ==
| |
| | |
| x << 2 + x
| |
| | |
| instead of
| |
| | |
| x * 5
| |
| | |
| == Instruction Reordering ==
| |
| | |
| Reorder independent instructions in order to avoid register spilling.
| |
| | |
| == Other ==
| |
| | |
| == Exercises ==
| |
| | |
| * [[Optimization Topics/Exercise 01|Exercises 01]]
| |
| * [[Optimization Topics/Exercise 02|Exercises 02]]
| |
| * [[Optimization Topics/Exercise 03|Exercises 03]]
| |
| * [[Optimization Topics/Exercise 04|Exercises 04]]
| |
| * [[Optimization Topics/Exercise 05|Exercises 05]]
| |
| * [[Optimization Topics/Exercise 06|Exercises 06]]
| |
| | |
| [[category:Compiladores]]
| |
| [[category:Ensino]]
| |