10.3 How the compiler works

Conceptually the compiler can be viewed as performing a series of separate passes.

• In the first pass the source code is macro expanded in the appropriate macro environment.
• A series of source to source optimizing transformations are performed to simplify the source tree. Type declarations are used to select specialized, efficient versions of low level functions.
• A graph is generated from the source tree. The structure of the graph reflects the flow of control in the tree. The nodes of the graph contain blocks of intermediate code for an abstract machine with byte addressing and an infinite set of registers. Register allocation is performed based on data flow analysis and machine specific rules concerning live ranges across code fragments.
• The blocks of intermediate code are translated into a single linear sequence of target machine code through a process of template matching.
• Finally the relative branch instructions are "fixed up" to point to the correct locations in the code sequence.

The compiler is in fact much more complex than this model might suggest. Machine specific optimizations, for example, can be included in any of the passes. The distinction between passes is also not as simple as that listed above. However, this description is sufficient to allow the programmer to make optimal use of the compiler.