Code Generator in Compiler Design: Generating Target Code from Intermediate Representations

Learn how the code generator phase in a compiler transforms intermediate representations, such as three-address code, into optimized target code. Understand register allocation, instruction selection, and optimization techniques used in code generation.

Code Generator in Compiler Design

The code generator is responsible for producing the target code from three-address statements. It utilizes registers to store the operands of these statements, optimizing the process for efficiency.

Example of Code Generation

For a three-address statement x := y + z, the sequence of generated code might be:

Example

MOV x, R0
ADD y, R0

Register and Address Descriptors

  • Register Descriptor: Keeps track of what each register currently holds. Initially, all registers are empty.
  • Address Descriptor: Stores the location of the current value of a variable at runtime (in memory, registers, or both).

Code-Generation Algorithm

The algorithm takes a sequence of three-address statements as input. For a statement of the form a := b op c, the following steps are performed:

  1. Invoke getreg to determine the register L for storing the result of b op c.
  2. Check the address descriptor for b to find its location (b'), preferring registers over memory. If b is not in L, generate MOV b', L.
  3. Generate OP z', L, where z' is the location of z (prefer registers if available).
  4. Update the address descriptor for a to indicate it is in L. Remove a from other descriptors if necessary.
  5. Alter the register descriptor to mark unused registers for b and z after execution, if they are no longer live.

Generating Code for Assignment Statements

Consider the assignment statement:

d := (a-b) + (a-c) + (a-c)

The three-address code translation is:

Three-Address Code

t := a - b
u := a - c
v := t + u
d := v + u

Generated Code Sequence

Statement Code Generated Register Descriptor Address Descriptor
t := a - b MOV a, R0
SUB b, R0 		R0 contains t t in R0
u := a - c MOV a, R1
SUB c, R1 		R0 contains t, R1 contains u t in R0, u in R1
v := t + u ADD R1, R0 R0 contains v, R1 contains u u in R1, v in R0
d := v + u ADD R1, R0
MOV R0, d 		R0 contains d d in R0, d in memory

Key Takeaways

  • Using a code generator ensures optimized utilization of registers and memory.
  • Address and register descriptors play a crucial role in tracking variable locations and register usage.
  • Efficient code generation minimizes redundant operations and improves runtime performance.