Code Improvement

Motivation and Goals

We want our compiler to produce good code, at least we usually do. We may wish to "optimize" one or more of:

• Program size
• Program speed
• Number of page swaps
• General system traffic

General optimization is generally undecidable and many specific optimization tasks happen to take provably exponential time or are NP-Hard. So we normally speak of code improvement, and strive to:

Do those things that give the most improvement for the least amount of work.

This means, for instance, that you might see compilers that don't bother doing any improving any code unless it is inside a loop.

Two goals:

Safety

The optimized code does the "same thing" as the unoptimized code

Profitability

The optimized code is actually better (smaller or faster) than the unoptimized code

Where Can Optimization Be Done?

There is no single optimization phase in a compiler. Lots of things happen to improve code:

1. The programmer needs to "find a better algorithm". Not many (if any) compilers can turn bubblesort into quicksort.
2. The intermediate code generator can be smart about how it generates intermediate code.
3. The compiler can make a pass or two or three over the intermediate code to improve it.
4. The code generator can be smart, with clever instruction selection, by employing register tracking, etc.
5. The compiler can make a pass or two or three over the target code to improve it.
6. The run time system can adapt to the way a program is running, possibly recompiling and relinking on the fly
7. The programmer profiles the running code and finds out where the memory leaks and bottlenecks and excessive resource consumption are occurring, and rewrites the code accordingly.

Optimization Strategies

In general, you'll try to

• maximize the use of registers, then the cache, then memory
• reduce the amount of code
• reduce conditional jumps (they make branch prediction difficult)
• reuse code results rather than recompute them
• optimize the use of pipelines and cores

But note the need for tradeoffs! You can get rid of some jumps by unrolling loops, but this makes more code.

A Catalog of Optimization Techniques

Machine Independent Optimizations

• Constant Folding
• Algebraic Simplification (e.g. operand reordering)
• Strength Reduction
• Unreachable Code Elimination
• Dead Code Elimination
• Copy Propagation
• Common Subexpression Elimination
• Loop Unrolling
• Loop Fission
• Loop Fusion
• Loop Inversion
• Loop Interchange
• Loop Invariant Factoring
• Jump Threading
• Induction Variable Simplification
• Tail Recursion Elimination
• Inline Expansion

Mostly Machine Independent Optimizations

• Efficient address computation
• Simplified stack frames
• Static allocation of frames
• Inlining

Machine Dependent Optimizations

• Careful instruction selection, using an understanding of caches, pipelines, branch prediction algorithms, scheduling rules, alignment requirements
• Smart register allocation
• Smart use of address modes
• Balancing across multiple CPUs

Links

• Compiler Optimization at Wikipedia
• Wikipedia's Compiler Optimizations Category Page
• Agner Fog's Software Optimization Resources