High Performance Computing - Charles Severance [30]
Optimizing Compiler Tour*
We will start by taking a walk through an optimizing compiler to see one at work. We think it’s interesting, and if you can empathize with the compiler, you will be a better programmer; you will know what the compiler wants from you, and what it can do on its own.
Compilation Process
Figure 2.1. Basic compiler processes
The compilation process is typically broken down into a number of identifiable steps, as shown in Figure 2.1. While not all compilers are implemented in exactly this way, it helps to understand the different functions a compiler must perform:
A precompiler or preprocessor phase is where some simple textual manipulation of the source code is performed. The preprocessing step can be processing of include files and making simple string substitutions throughout the code.
The lexical analysis phase is where the incoming source statements are decomposed into tokens such as variables, constants, comments, or language elements.
The parsing phase is where the input is checked for syntax, and the compiler translates the incoming program into an intermediate language that is ready for optimization.
One or more optimization passes are performed on the intermediate language.
An object code generator translates the intermediate language into assembly code, taking into consideration the particular architectural details of the processor in question.
As compilers become more and more sophisticated in order to wring the last bit of performance from the processor, some of these steps (especially the optimization and code-generation steps) become more and more blurred. In this chapter, we focus on the traditional optimizing compiler, and in later chapters we will look more closely at how modern compilers do more sophisticated optimizations.
Intermediate Language Representation
Because we are most interested in the optimization of our program, we start our discussion at the output of the parse phase of the compiler. The parse phase output is in the form of an an intermediate language (IL) that is somewhere between a high-level language and assembly language. The intermediate language expresses the same calculations that were in the original program, in a form the compiler can manipulate more easily. Furthermore, instructions that aren’t present in the source, such as address expressions for array references, become visible along with the rest of the program, making them subject to optimizations too.
How would an intermediate language look? In terms of complexity, it’s similar to assembly code but not so simple that the definitions[17] and uses of variables are lost. We’ll need definition and use information to analyze the flow of data through the program. Typically, calculations are expressed as a stream of quadruples — statements with exactly one operator, (up to) two operands, and a result.[18] Presuming that anything in the original source program can be recast in terms of quadruples, we have a usable intermediate language. To give you an idea of how this works, We’re going to rewrite the statement below as a series of four quadruples:
A = -B + C * D / E
Taken all at once, this statement has four operators and four operands: /, *, +, and - (negate), and B, C, D, and E. This is clearly too much to fit into one quadruple. We need a form with exactly one operator and, at most, two operands per statement. The recast version that follows manages to do this, employing temporary variables to hold the intermediate results:
T1 = D / E
T2 = C * T1
T3 = -B
A = T3 + T2
A workable intermediate language would, of course, need some other features, like pointers. We’re going to suggest that we create our own intermediate language to investigate how optimizations work. To begin, we need to establish a few rules:
Instructions consist of one opcode, two operands, and a result. Depending on the instruction, the operands may be empty.
Assignments are of the form X := Y op Z, meaning X gets the result of op applied to Y and Z.