Issues in Code Generation

In the code generation phase, various issues can arises:

1. Input to the code generator
2. Target program
3. Memory management
4. Instruction selection
5. Register allocation
6. Evaluation order
1. Input to the code generator
o The input to the code generator contains the intermediate representation of the
source program and the information of the symbol table. The source program is
produced by the front end.
o Intermediate representation has the several choices:
a) Postfix notation
b) Syntax tree
c) Three address code
o We assume front end produces low-level intermediate representation i.e. values of
names in it can directly manipulated by the machine instructions.
o The code generation phase needs complete error-free intermediate code as an input
requires.

Code generator is used to produce the target code for three-address statements. It uses registers to store the ope
three address statement.
Example:
Consider the three address statement x:= y + z. It can have the following sequence of codes:
MOV x, R0
ADD y, R0
2. Target program:
The target program is the output of the code generator. The output can be:
a) Assembly language: It allows subprogram to be separately compiled.
b) Relocatable machine language: It makes the process of code generation easier.
c) Absolute machine language: It can be placed in a fixed location in memory and can be
executed immediately.
3. Memory management:
 o During code generation process the symbol table entries have to be mapped to
actual p addresses and levels have to be mapped to instruction address.
o Mapping name in the source program to address of data is co-operating done by the
front end and code generator.
o Local variables are stack allocation in the activation record while global variables are
in static area.
4. Instruction selection:
o Nature of instruction set of the target machine should be complete and uniform.
o When you consider the efficiency of target machine then the instruction speed and
machine idioms are important factors.
o The quality of the generated code can be determined by its speed and size.

Example:
The Three address code is:
a:= b + c
d:= a + e
Inefficient assembly code is:
MOV b, R0 R0→b
ADD c, R0 R0 c + R0
MOV R0, a a → R0
MOV a, R0 R0→ a
ADD e, R0 R0 → e + R0
MOV R0, d d → R0
5. Register allocation
Register can be accessed faster than memory. The instructions involving operands in register are
shorter and faster than those involving in memory operand.
The following sub problems arise when we use registers:
Register allocation: In register allocation, we select the set of variables that will reside in
register.
Register assignment: In Register assignment, we pick the register that contains variable.
Certain machine requires even-odd pairs of registers for some operands and result.
For example:
Consider the following division instruction of the form: D x, y
Where,
x is the dividend even register in even/odd register pair
y is the divisor
Even register is used to hold the reminder.
Old register is used to hold the quotient.
There are three popular Register allocation algorithms .
1. Naive Register Allocation
2. Linear Scan Algorithm
3. Chaitin’s Algorithm
6. Evaluation order:
The efficiency of the target code can be affected by the order in which the computations are
performed. Some computation orders need fewer registers to hold results of intermediate than
others.

Simple Target Machine Model

Target Machine
o The target machine (or) computer is a type of byte-addressable machine. It has 4
bytes to a word.
o The target machine has n general purpose registers, R0, R1,...., Rn-1. It also has
three-address instructions of the form: op, source, destination
Where, op is used as an op-code and source and destination are used as a data field.
o It has the following op-codes:
ADD (add source to destination)
SUB (subtract source from destination)
MOV (move source to destination)
o The source and destination of an instruction can be specified by the combination of
registers and memory location with address modes.
A target machine is related to the last phase of the compiler, i.e., the code generator. A code
generator is a machine-dependent phase of the compiler because whatever the input is given to
the code generator, the code generator converts the input into the final target code.
Instructions
Instructions available in the target machine are as follows:
 Store operation: ST r, x; this instruction stores the value in location x to register r.
  Load operation: LD dst, addr this instruction loads addr location value into location dst.
It means dst=addr. This instruction will load the value of location x to location r.
 Conditional jump: The standard form of this operation is Bond,r, L. Where r is registered,
L is a label, and cond stands for any of the general tests on the value in register r.
 Unconditional jump: BR L; this operation jumps from branch BR to level L.
 Computation operations: OP dst, src1, src2 OP like operator ADD, SUB.

MODE FORM ADDRESS EXAMPLE ADDED COST

absolute M M Add R0, R1 1

register R R Add temp, R1 0

ADD 100 (R2),

indexed c(R) C+ contents(R) 1
R1

indirect register *R contents(R) ADD * 100 0

indirect
*c(R) contents(c+ contents(R)) (R2), R1 1
indexed

literal #c c ADD #3, R1 1

o Here, cost 1 means that it occupies only one word of memory.

o Each instruction has a cost of 1 plus added costs for the source and destination.
o Instruction cost = 1 + cost is used for source and destination mode.

Example:
1. Move register to memory R0 → M
MOV R0, M
cost = 1+1+1 (since address of memory location M is in word following the instr
uction)
2. Indirect indexed mode:
MOV * 4(R0), M
cost = 1+1+1 (since one word for memory location M, one word
for result of *4(R0) and one for instruction)
3. Literal Mode:
MOV #1, R0
cost = 1+1+1 = 3 (one word for constant 1 and one for instruction)

Program and Instruction cost

 If we want to select an instruction, we will select an instruction whose programming
costs are less. every machine will have its fixed instruction cost.
 In most of the machines and in most of the instructions the time taken to fetch an
instruction from memory exceeds the time spent executing the instruction, so if the
length of the instruction is reduced it has an extra benefit.

Instruction operation cost

MOV R0, R1 (Register to register) 1

MOV R0, M (Register to memory) 2

MOV M, R0(Memory to register) 2

MOV 4(R0), M (4+contents(R0) into memory) 3

MOV *4(R0,M) contents(contents(4+contents(R0))) into memory 3

MOV #1, R0 (store 1 into R0) 3

ADD 4(R0),*12(R1) (add contents(4+contents(R0) to value at location contents(12+

3
contents(R1))

Register Allocation and Assignment

1. Global Register Allocation
2. Usage Counts
3. Register Assignment for Outer Loops
4. Register Allocation by Graph Coloring
Instructions involving only register operands are faster than those involving memory operands.
On modern machines, processor speeds are often an order of magnitude or more faster than
memory speeds. Therefore, efficient utilization of registers is vitally important in generating
good code. This section presents various strategies for deciding at each point in a program what
values should reside in registers (register allocation) and in which register each value should
reside (register assignment).
One approach to register allocation and assignment is to assign specific values in the target
program to certain registers. For example, we could decide to assign base addresses to one
group of registers, arithmetic computations to another, the top of the stack to a fixed register,
and so on.
This approach has the advantage that it simplifies the design of a code gener-ator. Its
disadvantage is that, applied too strictly, it uses registers inefficiently; certain registers may go
unused over substantial portions of code, while unnec-essary loads and stores are generated
into the other registers. Nevertheless, it is reasonable in most computing environments to
reserve a few registers for base registers, stack pointers, and the like, and to allow the remaining
registers to be used by the code generator as it sees fit.
1. Global Register Allocation
The code generation algorithm used registers to hold values for the duration of a single basic
block. However, all live variables were stored at the end of each block. To save some of these
stores and corresponding loads, we might arrange to assign registers to frequently used
variables and keep these registers consistent across block boundaries (globally).
One strategy for global register allocation is to assign some fixed number of registers to hold the
most active values in each inner loop. The selected values may be different in different loops.
Registers not already allocated may be used to hold values local to one block. This approach has
the drawback that the fixed number of registers is not always the right number to make
available for global register allocation.
To make the decision about allocation and assignments, the global allocator mostly uses graph
coloring by building an interference graph. Register allocator then attempts to construct a k-
coloring for that graph where ‘k’ is the no. of physical registers.
 In case, the compiler can’t directly construct a k-coloring for that graph, it modifies
the underlying code by spilling some values to memory and tries again.
 Spilling actually simplifies that graph which ensures that the algorithm will halt.
Global Allocator uses several approaches:
 Discovering Global live ranges.
 Estimating Spilling Costs.
 Building an Interference graph.
2.Usage Counts
3. Register Assignment for Outer Loops
Having assigned registers and generated code for inner loops, we may apply the same idea to
progressively larger enclosing loops. If an outer loop L1 contains an inner loop L2, the names
allocated registers in L2 need not be allocated registers in L1 — L2. Similarly, if we choose to
allocate x a register in L2 but not Li, we must load x on entrance to L2 and store x on exit
from L2. We leave as an exercise the derivation of a criterion for selecting names to be allocated
registers in an outer loop L, given that choices have already been made for all loops nested
within L.
4. Register Allocation by Graph Coloring

Code Generator
A code generator is a compiler that translates the intermediate representation of the source
program into the target program. In other words, a code generator translates an abstract
syntax tree into machine-dependent executable code
(OR)
Code generator is used to produce the target code for three-address statements. It uses
registers to store the operands of the three address statement.
Example:
Consider the three address statement x:= y + z. It can have the following sequence of codes:
MOV x, R0
ADD y, R0
Register and Address Descriptors:
o A register descriptor contains the track of what is currently in each register. The register
descriptors show that all the registers are initially empty.
o An address descriptor is used to store the location where current value of the name can
be found at run time.

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:
t:= a-b
u:= a-c
v:= t +u
d:= v+u
Code sequence for the example is as follows:

Statement Code Generated Register descriptor Address descriptor

Register empty

t:= a - b MOV a, R0 R0 contains t t in R0

 SUB b, R0

MOV a, R1 R0 contains t t in R0
u:= a - c
SUB c, R1 R1 contains u u in R1

R0 contains v u in R1
v:= t + u ADD R1, R0
R1 contains u v in R1

ADD R1, R0 d in R0
d:= v + u R0 contains d
MOV R0, d d in R0 and memory

Optimal Code Generation for Expressions

1 Ershov Numbers
2 Generating Code From Labeled Expression Trees
3 Evaluating Expressions with an Insufficient Supply of Registers
We can choose registers optimally when a basic block consists of a single expres-sion
evaluation, or if we accept that it is sufficient to generate code for a block one expression at a
time. In the following algorithm, we introduce a numbering scheme for the nodes of an
expression tree (a syntax tree for an expression) that allows us to generate optimal code for an
expression tree when there is a fixed number of registers with which to evaluate the expression.

GENERATING CODE FROM DAGs

The advantage of generating code for a basic block from its dag representation is that from a
dag we can easily see how to rearrange the order of the final computation sequence than we
can start from a linear sequence of three-address statements or quadruples.
Rearranging the order
The order in which computations are done can affect the cost of resulting object code. For
example, consider the following basic block:
t1 : = a + b
t2 : = c + d
t3 : = e - t2
t4 : = t1 - t3
Generated code sequence for basic block:
 MOV a , R0
ADD b , R0
MOV c , R1
ADD d , R1
MOV R0 , t1
MOV e , R0
SUB R1 , R0
MOV t1 , R1
SUB R0 , R1
MOV R1 , t4
Rearranged basic block:
Now t1 occurs immediately before t4.
t2 : = c + d
t3 : = e - t2
t1 : = a + b
t4 : = t1 - t3
Revised code sequence:
MOV c , R0
ADD d , R0
MOV a , R0
SUB R0 , R1
MOV a , R0
ADD b , R0
SUB R1 , R0
MOV R0 , t4
In this order, two instructions MOV R0 , t1 and MOV t1 , R1 have been saved.
A Heuristic ordering for Dags
The heuristic ordering algorithm attempts to make the evaluation of a nod the evaluation of its
leftmost argument. The algorithm shown below produces the ordering in reverse.
Algorithm:
1) while unlisted interior nodes remain do begin
2) select an unlisted node n, all of whose parents have been listed;
3) list n;
4) while the leftmost child m of n has no unlisted parents and is not a leaf do begin
5) list m;
6) n:=m
Example: Consider the DAG shown below
Initially, the only node with no unlisted parents is 1 so set n=1 at line (2) and list 1 at line (3).
Now, the left argument of 1, which is 2, has its parents listed, so we list 2 and set n=2 at line (6).
Now, at line (4) we find the leftmost child of 2, which is 6, has an unlisted parent 5. Thus we
select a new n at line (2), and node 3 is the only candidate. We list 3 and proceed down its left
chain, listing 4, 5 and 6. This leaves only 8 among the interior nodes so we list that. The resulting
list is 1234568 and the order of evaluation is 8654321.
Code sequence:
t8 : = d + e
t6 : = a + b
t5 : = t6 - c
t4 : = t5 * t8
t3 : = t4 - e
t2 : = t6 + t4
t1 : = t2 * t3
This will yield an optimal code for the DAG on machine whatever be the number of registers.