Code Generator

A code generator is an important phase of a compiler that converts intermediate code, such as three-address code, into target code that can be executed by the target machine. It selects suitable machine instructions and uses registers and memory locations to represent the operations.

In this chapter, you will learn what a code generator is, how it translates three-address statements into target code, and how register and address descriptors are used during code generation.

What is a Code Generator?

A code generator is a compiler component that produces target code from an intermediate representation of the source program.

The target code may be assembly code, machine code, or another low-level representation depending on the compiler and target machine.

The code generator must consider factors such as:

• Available machine instructions
• Registers available on the target machine
• Memory locations
• Operand locations
• Evaluation order
• Efficient use of registers

For example, consider the following three-address statement:

x := y + z

A possible sequence of target instructions is:

MOV R0, y
ADD R0, z
MOV x, R0
Here, R0 is used to hold the intermediate result of y + z.

Register and Address Descriptors

During code generation, the compiler maintains information about where values are currently stored. Two important data structures used for this purpose are register descriptors and address descriptors.

Register Descriptor

A register descriptor keeps track of the value currently stored in each machine register.

For example:

Register     Contents
R0           y + z
R1           empty
R2           x

Initially, the registers may be considered empty. As instructions are generated, the descriptor is updated to reflect the values stored in each register.

Address Descriptor

An address descriptor keeps track of the locations where the current value of a name can be found at runtime.

For example, if the value of x is currently available in register R0 and memory location x, the address descriptor can represent:

x → {R0, memory[x]}

The compiler uses this information to avoid unnecessary loads and stores.

A Code-Generation Algorithm

The algorithm takes a sequence of three-address statements as input. For each three address statement of the form a:= b op c perform the various actions. These are as follows:

1. Invoke a function getreg to find out the location L where the result of computation b op c should be stored.
2. Consult the address description for y to determine y'. If the value of y currently in memory and register both then prefer the register y' . If the value of y is not already in L then generate the instruction MOV y' , L to place a copy of y in L.
3. Generate the instruction OP z' , L where z' is used to show the current location of z. if z is in both then prefer a register to a memory location. Update the address descriptor of x to indicate that x is in location L. If x is in L then update its descriptor and remove x from all other descriptor.
4. If the current value of y or z have no next uses or not live on exit from the block or in register then alter the register descriptor to indicate that after execution of x : = y op z those register will no longer contain y or z.

Generating Code for Assignment Statements

The assignment statement d:= (a-b) + (a-c) + (a-c) can be translated into the following sequence of three address code:

Code sequence for the example is as follows: