9
Code Generation and Machine-dependent Optimization
What you will learn in this chapter
- What are the issues in Code Generation?
- How does the Target language influence code generation?
- How does the Instruction Set of the processor influence code generation?
- How are the registers of the processors utilized?
- How are the registers of the processors allocated?
- How is the instruction ordering selected?
- How are various constructs in the High Level programming language implemented in the target language?
- How are Functions and Procedures implemented?
- What is Optimization?
- What are Machine-dependent and Machine-independent optimizations?
- What are the methods of Machine-dependent optimization?
Key Words
code generation, intermediate representation, target language, instruction set, registers, data structures, control constructs, procedures and functions, activation record, code optimization, machine-dependent optimization, register allocation
The last phase of compilation is Code Generation. This phase takes the Intermediate Representation of the original source program as input and produces a semantically equivalent program in the target language as output. Depending upon the nature of the target language, there may be subsequent steps necessary to make the program ultimately executable on a particular platform. In a typical case of Linux/Unix-like platform, the target language is generally a (simplified) assembly code, and further steps of assembly through the system assembler linking with language library and loading are required to get an executable program. Further, while generating the target code, it will be highly desirable to generate a “good” code, one which satisfies the basic requirement of any good algorithm – it should be correct and efficient.
The basic requirements of the Code Generation phase are:
- The generated target language program must correctly and faithfully express the algorithm specified by the source program (and not what the programmer intended, unfortunately!).
- The target language program should be efficient, which means, it should use the platform resources as efficiently as possible. Target instructions most economical in CPU time utilization should be used and program layout should use minimum possible memory, consistent with that requirement.
- The code generator itself should be efficient, and it should generate the target code as fast as possible.
In order to satisfy these requirements, several things need to be done:
- The nature of the target code and Run-Time environment should be known well enough.
- The factors needed to be considered in code generation – the input Intermediate Representation (IR), selection of instruction sequence in the target code, allocation of processor components, especially the CPU registers and actual order of computation in the final target code – should be examined from the viewpoint of code Optimization.
- In fact, it is found that the code optimization, though conceptually a separate phase, actually has to be done in several passes over the IR and ad-hoc generated code. Thus a good, optimizing compiler will be working some what like what is shown in Fig. 9.1.
Fig. 9.1 Code generator in the compiler chain. The dashed arrows show the order in which we discuss the phases, from pedagogical necessity
We first discuss, after detailing our concerns in the task of code generation, a naïve code generator, without any worry of inefficiency of the generated code. Of course, correctness of the generated code must be ensured even in presence of special cases and idiosyncrasy of the target language. Then we point out some typical inefficiencies and see how the code generator can deal with them and generate better target code, by what is called machine-dependent optimization. We shall also discuss some concepts like Basic Blocks which are used in a real-life compiler, viz., GNU gcc.