10.7 Epilogue

Optimization is the field where most compiler research is done today. The tasks of the front-end – Scanner, Parser, Semantic Analysis – are well understood, and unoptimized code generation is relatively straightforward. Optimization, on the other hand, still retains a sizable measure of mysticism. High-quality optimization is more of an art than a science. Compilers for mature languages are not judged by how well they parse or analyze the code – you just expect it to do it right with a minimum of problems – but instead by the quality of the object code they produce.

In terms of algorithm complexity, many optimization problems are NP-complete and thus most optimization algorithms rely on heuristics and approximations. It may be possible to come up with a case where a particular optimization algorithm fails to produce better code or perhaps even makes it worse. However, the algorithms tend to do rather well overall.

It is worth noting that efficient code starts with intelligent decisions by the programmer. No one expects a compiler to replace BubbleSort with Quicksort. If a programmer uses an inefficient algorithm, no amount of optimization can make it efficient. Talking in terms of the complexity measure Big-O, a compiler can only make improvements to constant factors. However, all else being equal, you want an algorithm with low constant factors.

From the viewpoint of a debugger like gdb, the shortcuts taken by optimized code may occasionally produce surprising results: some variables you declared may not exist at all; flow of control may briefly move where you did not expect it; some statements may not be executed because they compute constant results or their values were already at hand; some statements may execute in different places because they were moved out of loops, etc. Though it is possible to debug a program compiled with −O using gdb, conceptually you optimize a program which is known to be without bugs. The basic idea is: first get it working right and only then optimize.