Chapter-Nine
Code-Generation
Basic Topics of Chapter 9
• Introduction to Code Generation • Run-Time Storage Management
• Issues in the design of a code • The Function getReg
generator • An example of code generation
• Register and Address descriptors
• Basic blocks and Flow graphs
• The Target Machine
Introduction to Code Generator
Code generation can be considered as the final phase of compilation.
It generates a target code for a sequence of three-address statement.
It consider each statement in turn, remembering if any of the operands of the statement are
currently in registers and taking advantage of that fact if possible.
The code generated by the compiler is an object code of some lower-level programming language,
for example, assembly language.
We have seen that the source code written in a higher-level language is transformed into
a lower-level language that results in a lower-level object code, which should have the
following minimum properties:
It should carry the exact meaning of the source code.
It should be efficient in terms of CPU usage and memory management
Introduction to Code Generator
This phase generates the target code consisting of assembly code.
i. Memory locations are selected for each variable
ii. Instructions are translated into a sequence of assembly instructions.
iii. Variables and intermediate results are assigned to memory
registers.
Position of code Generator
Issues in the design of code generator
• A code generator is expected to have an understanding of the target machine’s runtime
environment and its instruction set.
• The following are issues in the design of code generator
• Input to the code generator
• Target program
• Memory management
• Instruction selection
• Register allocation
• Choice of evaluation order/ Instruction ordering
• Approaches to code generation
Input to the code generator
IR + Symbol table
IR Type : Intermediate representation has various forms. It can be in
Abstract Syntax Tree (AST) structure,
Polish Notation (infix, prefix and postfix)
3-address code.
We assume front end produces low-level IR, i.e. values of names in it can
be directly manipulated by the machine instructions.
Syntactic and semantic errors have been already detected.
Target program
The output of code generator is target program.
Output may take variety of forms
Absolute machine language(executable code)
Re-locatable machine language(object files for linker)
Assembly language(facilitates debugging)
Absolute machine language has advantage that it can be placed in a fixed location in
memory and immediately executed.
Re-locatable machine language program allows subprograms to be compiled
separately.
Producing assembly language program as o/p makes the process of code generation
somewhat easier.
Memory Management
Mapping names in the source program to addresses of data objects in run time
memory is done by front end & code generator.
If a machine code is being generated, labels in three address statements have to
be converted to addresses of instructions.
This process is analogous to “back-patching” technique.
Note: What is Back-patching?
Is the process of leaving a blank slot for missing information and fill in the
slot when the information becomes .
Instruction selection
Choose appropriate target-machine instructions to implement the IR statements.
If we do not care about the efficiency of the target program, instruction selection is
straightforward.
The quality of the generated code is determined by its speed and size. Example:
Register Allocation
Instructions involving register operands are usually shorter and faster than those
involving operands in memory.
Two sub-problems:
Register Allocation: select the set of variables that will decide what values to
keep in which registers.
Register Assignment: select specific register that a variable reside in
Complications imposed by the hardware architecture
Example: register pairs for multiplication and division
Register allocation Cont’d
The multiplication instruction is of the form.
M x, y
where x, is the multiplicand, is the even register of an even/odd
register pair.
The multiplicand value is taken from the odd register pair.
The multiplier y is a single register.
The product occupies the entire even/odd register pair.
Register allocation: Example
Choice of Evaluation Order
At last, the code generator decides the order in which the instruction will be executed.
It creates schedules for instructions to execute them.
The order in which computations are performed can affect the efficiency of the target
code.
When instructions are independent, their evaluation order can be changed.
Choice of Evaluation Order: Example
Approaches to Code generation
Criterion for a code generator is to produce correct code.
Given the premium on correctness, designing a code generator so it can
be easily implemented, tested, and maintained is an important design
goal.
Register and Address Descriptors:
• The code generator has to track both the registers (for availability) and addresses
(location of values) while generating the code.
• For both of them, the following two descriptors are used:
• Register descriptor :·
– is used to inform the code generator about the availability of registers.
– is used to keep track of what is currently in each registers.
• The register descriptors show that initially all the registers are empty.
– Whenever a new register is required during code generation, this descriptor is
consulted for register availability.
Register and Address Descriptors:
• Address descriptor :
– Values of the names (identifiers) used in the program might be stored at
different locations while in execution.
– An address descriptor stores the location where the current value of the
name can be found at run time.
– These locations may include CPU registers, heaps, stacks, memory or a
combination of the mentioned locations.
Register and Address Descriptors: …
• Code generator keeps both the descriptor updated in real-time. For a load statement,
LD R1, x, the code generator:
– updates the Register Descriptor R1 that has value of x and
– updates the Address Descriptor (x) to show that one instance of x is in R1.
Register and Address Descriptors:
…
• Basic blocks comprise of a sequence of three-address instructions.
• Code generator takes these sequence of instructions as input.
• Note :
– If the value of a name is found at more than one place (register, cache, or memory),
the register’s value will be preferred over the cache and main memory.
– Likewise cache’s value will be preferred over the main memory.
– Main memory is barely given any preference.
The Function getReg
• getReg : Code generator uses getReg function to determine the status of available
registers and the location of name values.
• getReg works as follows:
– If variable Y is already in register R, it uses that register.
– Else if some register R is available, it uses that register.
– Else if both the above options are not possible, it chooses a register that requires
minimal number of load and store instructions.
The Function getReg
• For an instruction x = y OP z, the code generator may perform the following actions.
• Let us assume that L is the location (preferably register) where the output of y OP z is to be
saved:
– Call function getReg, to decide the location of L.
– Determine the present location (register or memory) of y by consulting the Address
Descriptor of y.
– If y is not presently in register L, then generate the following instruction to copy the
value of y to L:
– MOV y’, L
– where y’ represents the copied value of y.
The Function getReg …
– Determine the present location of z using the same method used in step 2 for y and generate
the following instruction:
– OP z’, L where z’ represents the copied value of z.
– Now L contains the value of y OP z, that is intended to be assigned to x. So, if L is a register,
update its descriptor to indicate that it contains the value of x.
– Update the descriptor of x to indicate that it is stored at location L.
– If y and z has no further use, they can be given back to the system.
– Other code constructs like loops and conditional statements are transformed into assembly
language in general assembly way.
Rules for updating the register and
address descriptors
1. For the instruction LD R, x
– Change the register descriptor for register R so it holds only x.
– Change the address descriptor for x by adding register R as an additional location.
2. For the instruction ST x, R, change the address descriptor for x to include its own
memory location.
3. For an operation such as ADD Rx, Ry, Rz implementing a three-address instruction x =
y+x
i. Change the register descriptor for Rx so that it holds only x.
ii. Change the address descriptor for x so that its only location is R x.
• Note that the memory location for x is not now in the address descriptor for x.
iii. Remove Rx from the address descriptor of any variable other than x.
Rules for updating the register and address descriptors …
4. When we process a copy statement x = y, after generating the load for y into register
Ry, if needed, and after managing descriptors as for all load statements (per rule 1):
– Add x to the register descriptor for Ry.
– Change the address descriptor for x so that its only location is R y .
An Example of Code Generator:
• Generating Code for Assignment Statements:
– The assignment d : = (a-b) + (a-c) + (a-c) might be translated into the following three-
address code sequence:
• Code sequence for the example is:
Instructions generated and the changes in the register and
address descriptors
Instructions generated and the
changes in the register and address
descriptors
Reading Assignment
• Basic blocks and Flow graphs
• The Target Machine
• Run-Time Storage Management
• The End !