This is the second segment of a three part series exploring the various aspects of compiler technology.
Code optimization is today the core problem of compiler design. Although some work still goes into parsing methods, most research targets the problems of optimization. There are broadly two types of optimizations, optimizations for speed and for memory space. Sometimes an optimization does both. Before I go much further it is worth mentioning what optimizations provide.
Why Optimize?
Memory
First, memory space. How much code does it take to fill up the memory of a modern PC? A lot is the answer. Modern operating systems take multiple megabytes of disk space, but much of it is graphics, sound and documentation. Also virtual memory means that large executables don’t block up memory much. For most practical purposes size doesn’t matter anymore. All that matters is the consumption of instruction cache, which can affect speed.
The exception is the embedded world where bytes still matter. Embedded system developers have resurrected methods from decades ago to face this. Recently they have also developed optimizations especially targeted to save power.
Speed
There are two types of programs those that need to be fast and those that don’t. With ever increasing speed of processors and peripherals more applications fall into the latter category. Of those where speed is critical there are several possible bottlenecks:
- Hard disk & File system
- Network
- Operating system kernel
- Languages standard library
- Users
- Memory
- Processor
The compiler can affect only the last strongly. Sometimes it can improve memory bandwidth or latency. Operating system and language libraries maybe affected by the compiler they are compiled with.
Together this means that many if not most programs don’t benefit from optimization.
Endless Possibilities
A vast range of optimizations has been applied and studied, here I will concentrate on the most important ones, the most important thirty odd that is. It is difficult to classify optimizations, crudely there are two types:
- Elimination of unnecessary work (henceforth “strength reduction”).
- Selection of the best patterns of instructions.
These two overlap each other at the edges since selection of the best pattern of instructions involves preventing the processor doing unnecessary work. Below is a list of the various types of optimizations; the higher level optimizations will be first, with the lowest level of optimizations being covered in the last part of this series.
- Strength reductions
- Dead code elimination
- Hoisting of invariants from loops
- Common sub-expression elimination
- Jump removal
- Constant folding
- Inlining
- Trace scheduling
- Arithmetic simplification
- Tail call optimization
- Iteration order reversal
- Loop unrolling
- Induction variable elimination
- Selection of efficient instruction patterns
- Loop fusion
- Loop fission
- Prefetching
- Blocking
- Memory bank optimization
- Instruction combination
- Instruction selection (peephole optimization)
- If conversion
- Register allocation
- Register movement elimination
- Instruction scheduling
- Delayed branch scheduling
- Vectorization
- Threading
Some of these optimizations are done when the program is represented close to its source form, as for example tree, others are done later when it is in a low-level form. This lower level form is close to assembly language in semantics. In general each optimization is performed one at a time. A subroutine applying the optimization goes through the tree, does some stuff and then another subroutine does more stuff, etc. These are passes. The separation of the optimization problem into multiple passes makes developing or altering several optimizing passes at once possible. Of course it doesn’t have to be done this way, but this is how it is almost always done, see [2] for one alternative.
I’ll introduce one further piece of jargon: the `basic block’ is a section of code with no jumps, into or out of it. It’s a useful idea because doing optimizations within basic blocks is much easier than doing them everywhere.
I apologize if some of this isn’t particularly interesting; optimizations are determined by necessity, necessity is a horribly uneven writer, but when it’s good no one can touch it.
Discuss (15 comments)