Optimizing Compiler - Common Themes

Common Themes

To a large extent, compiler optimization techniques have the following themes, which sometimes conflict.

Optimize the common case

The common case may have unique properties that allow a fast path at the expense of a slow path. If the fast path is taken most often, the result is better overall performance.

Avoid redundancy

Reuse results that are already computed and store them for later use, instead of recomputing them.

Less code

Remove unnecessary computations and intermediate values. Less work for the CPU, cache, and memory usually results in faster execution. Alternatively, in embedded systems, less code brings a lower product cost.

Fewer jumps by using straight line code, also called branch-free code

Less complicated code. Jumps (conditional or unconditional branches) interfere with the prefetching of instructions, thus slowing down code. Using inlining or loop unrolling can reduce branching, at the cost of increasing binary file size by the length of the repeated code. This tends to merge several basic blocks into one.

Locality

Code and data that are accessed closely together in time should be placed close together in memory to increase spatial locality of reference.

Exploit the memory hierarchy

Accesses to memory are increasingly more expensive for each level of the memory hierarchy, so place the most commonly used items in registers first, then caches, then main memory, before going to disk.

Parallelize

Reorder operations to allow multiple computations to happen in parallel, either at the instruction, memory, or thread level.

More precise information is better

The more precise the information the compiler has, the better it can employ any or all of these optimization techniques.

Runtime metrics can help

Information gathered during a test run can be used in profile-guided optimization. Information gathered at runtime (ideally with minimal overhead) can be used by a JIT compiler to dynamically improve optimization.

Strength reduction

Replace complex or difficult or expensive operations with simpler ones. For example, replacing division by a constant with multiplication by its reciprocal, or using induction variable analysis to replace multiplication by a loop index with addition.