UNIT-6 CODE GENERATION AND CODE SCHEDULING

Issues in Code Generation, Input to Code Generator, Instruction Selection, Register

Allocation, Simple Target Machine Model, Program and Instruction Costs, Register
allocation & Assignments, Code Generation Algorithm, Code Generators, Optimal
Code Generation for Expressions, Code Generation From DAG.

CODE GENERATION:
Code generation can be considered as the final phase of compilation. Through post code
generation, optimization process can be applied on the code, but that can be seen as a part of
code generation phase itself. 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.

ISSUES IN CODE GENERATION:

A code generator is a crucial part of a compiler that converts the intermediate representation
of source code into machine-readable instructions. Its main task is to produce the correct and
efficient code that can be executed by a computer. The design of the code generator should
ensure that it is easy to implement, test, and maintain.
The following issues arise during the code generation phase:
1. Input to code generator
2. Target program
3. Memory management
4. Instruction selection
5. Register allocation
6. Evaluation order
1. Input to Code Generator:
The input to the code generator comes from the intermediate code generated by the compiler's
front-end. This intermediate code is usually a higher-level representation of the program, like
triples, quadruples, or abstract syntax trees. Along with this intermediate code, the code
generator also uses information from the symbol table, which holds the addresses of variables
and other data objects. One key challenge here is that the input must be free from syntactic
and semantic errors, as the code generator assumes that proper type-checking and other error
checks have already been handled by the front-end. Handling the input correctly is crucial for
generating the correct target code.
2. Target Program:
The target program is the final output of the code generator, which can be in the form of
absolute machine language, relocatable machine language, or assembly language. Each type
of output has its own set of challenges:
 Absolute Machine Language is easy to execute but lacks flexibility because it is
bound to specific memory locations.
 Relocatable Machine Language allows parts of the program to be moved around in
memory, making it suitable for linking multiple modules, but it requires a linking
loader and has some overhead.
 Assembly Language is symbolic and needs an additional step (an assembler) to
convert it into machine code, but it makes the code generation process easier.
Choosing the appropriate form for the target program depends on factors such as the
program’s needs, execution environment, and whether the program will be linked with other
modules.
3. Memory Management:
Memory management in the code generation phase involves mapping variable names to their
corresponding memory locations. The code generator works closely with the front-end to
access the symbol table, where memory addresses for variables are stored. A major challenge
is ensuring that the code generator uses memory efficiently, avoids memory conflicts, and
correctly handles dynamic memory allocation. This requires careful handling of variable
storage, particularly for dynamically allocated objects or large data structures, such as arrays
or objects in object-oriented languages.
4. Instruction Selection:
Instruction selection is the process of choosing the most suitable machine instructions to
translate intermediate code into executable code. The goal is to optimize the generated code
by selecting instructions that are efficient and appropriate for the target machine. If the right
instructions are not selected, the resulting code can be inefficient and slow. A code generator
might need to decide between different ways of implementing the same operation, such as
using different addressing modes or optimizing for processor-specific features. For example,
the respective three-address statements would be translated into the latter code sequence as
shown below:
Three Address Code:
P:= Q + R
S:= P + T
Assembly Code (Inefficient):
MOV Q, R0 (Load the value of Q into register R0)
ADD R, R0 (Add the value of R to the value in R0)
MOV R0, P (Store the value of R0 into the variable P)
MOV P, R0 (Load the value of P back into R0)
ADD T, R0 (Add the value of T to R0)
MOV R0, S (Store the value of R0 into the variable S)
Here the fourth statement is redundant as the value of the P is loaded again in that statement
that just has been stored in the previous statement. It leads to an inefficient code sequence.
Assembly Code (Efficient):
MOV Q, R0 (Load Q into R0)
ADD R, R0 (Add R to R0)
ADD T, R0 (Add T to R0)
MOV R0, S (Store the final result in S)
A given intermediate representation can be translated into many code sequences, with
significant cost differences between the different implementations. Prior knowledge of
instruction cost is needed in order to design good sequences, but accurate cost information is
difficult to predict.
5. Register Allocation Issues
Efficient use of registers is important because registers are faster than memory, and utilizing
them effectively can significantly improve program performance. The challenge lies in
selecting the right variables to store in registers at different points in the program.
Register allocation involves two stages:
1. Register Allocation: It is selecting which variables will reside in the registers at each
point in the program
 2. Register Assignment: Assigning specific registers to those variables selected in
Register Allocation.
The difficulty arises in managing which variables are allocated to registers, especially when
the number of available registers is limited. Poor register allocation can lead to spills, where
data is temporarily stored in memory, causing slower performance.
To understand the concept consider the following three address code sequence
t:= a + b
t:= t*c
t:= t/d
Their efficient machine code sequence is as follows:
MOV a, R0
ADD b, R0
MUL c, R0
DIV d, R0
MOV R0, t
6. Evaluation Order
The evaluation order refers to the sequence in which expressions are evaluated in the
generated code. This order can significantly affect the efficiency of the program. For
example, evaluating certain expressions first might require fewer registers or fewer
instructions. The challenge is to determine the optimal order in which to execute operations
so that the program requires fewer resources (like memory or registers) and runs more
efficiently. This is often a complex problem, as finding the best evaluation order can be
computationally expensive, and in some cases, it may require sophisticated algorithms to find
the optimal solution.
TARGET MACHINE:
 A target machine refers to a 4 byte addressable machine with n number of registers.
 The target machine is capable of two address instruction of form operation source,
destination
 Operation is described by an op-code, source and destination are described with an
addressing mode.
A Simple Target Machine Model is an idealized computer used in compiler design, featuring
basic components like byte-addressable memory, a small register set (R0, R1...), and a
limited instruction set (ADD, MOV, JUMP) for easy mapping from intermediate code,
 focusing on core concepts like instruction selection, register allocation, and addressing modes
without real-world complexities like pipelines or caches. It helps teach how compilers
generate low-level code for fundamental operations
Components of a Simple Target Machine Model
1. Registers
o Small, fast storage units inside the CPU
o Used to hold operands and intermediate results during expression evaluation
2. Memory: Larger storage area for variables, arrays, and data not stored in registers
3. Instruction Set
o A small collection of fundamental machine instructions such as:
 LOAD (load data from memory to register)
 STORE (store data from register to memory)
 ADD, SUB, MUL, DIV
 MOV (move data between registers)
4. Addressing Modes
o Ways to specify operands, e.g., register, direct, indirect addressing

5. Stack or Register-based Architecture

o Some simple models use a stack to hold operands
o Others use registers like R0, R1, R2… to perform operations
Example of Simple Target Machine Instructions
For an expression like:
x=a+b*c
The simple target machine model might generate instructions such as:
LOAD R1, b
LOAD R2, c
MUL R1, R2
LOAD R3, a
ADD R3, R1
STORE x, R3
Instruction cost:
Instruction cost = 1+cost for source and destination address modes. This cost corresponds to
the length of the instruction. Address modes involving registers have cost zero. Address
modes involving memory location or literal have cost one. Instruction length should be
minimized if space is important. Doing so also minimizes the time taken to fetch and perform
the instruction. example: MOV R0, R1 copies the contents of register R0 into R1. It has cost
one, since it occupies only one word of memory.
The three-address statement a : = b + c can be implemented by many different instruction
sequences :
i) MOV b, R0
ADD c, R0 cost = 6
MOV R0, a
ii) MOV b, a
ADD c, a cost = 6
iii) Assuming R0, R1 and R2 contain the addresses of a, b, and c:
MOV *R1, *R0
ADD *R2, *R0 cost = 2
In order to generate good code for target machine, we must utilize its addressing capabilities
efficiently
Register Allocation:
One machine optimization of particular importance is register allocation, which is perhaps
the single most effective optimization for all architectures. Registers are the fastest kind of
memory available, but as a resource, they can be scarce. The problem is how to minimize
traffic between the registers and what lies beyond them in the memory hierarchy to eliminate
time wasted sending data back and forth across the bus and the different levels of caches.
Your Decaf back-end uses a very naïve and inefficient means of assigning registers, it just
fills them before performing an operation and spills them right afterwards. A much more
effective strategy would be to consider which variables are more heavily in demand and keep
those in registers and spill those that are no longer needed or won't be needed until much
later. One common register allocation technique is called "register coloring", after the central
idea to view register allocation as a graph coloring problem. If we have 8 registers, then we
try to color a graph with eight different colors. The graph‘s nodes are made of "webs" and the
arcs are determined by calculating interference between the webs. A web represents a
variable‘s definitions, places where it is assigned a value (as in x = …), and the possible
different uses of those definitions (as in y = x + 2). This problem, in fact, can be approached
as another graph. The definition and uses of a variable are nodes, and if a definition reaches a
use, there is an arc between the two nodes. If two portions of a variable‘s definition-use graph
are unconnected, then we have two separate webs for a variable. In the interference graph for
the routine, each node is a web. We seek to determine which webs don't interfere with one
another, so we know we can use the same register for those two variables. For example,
consider the following code:
i = 10;
j = 20;
x = i + j;
y = j + k;
We say that i interferes with j because at least one pair of i‘s definitions and uses is separated
by a definition or use of j, thus, i and j are "alive" at the same time. A variable is alive
between the time it has been defined and that definition‘s last use, after which the variable is
dead. If two variables interfere, then we cannot use the same register for each. But two
variables that don't interfere can since there is no overlap in the liveness and can occupy the
same register.
Once we have the interference graph constructed, we r-color it so that no two adjacent nodes
share the same color (r is the number of registers we have, each color represents a different
register). You may recall that graph-coloring is NP-complete, so we employ a heuristic rather
than an optimal algorithm. Here is a simplified version of something that might be used:
1. Find the node with the least neighbors. (Break ties arbitrarily.)
2. Remove it from the interference graph and push it onto a stack
3. Repeat steps 1 and 2 until the graph is empty.
4. Now, rebuild the graph as follows:
a. Take the top node off the stack and reinsert it into the graph
b. Choose a color for it based on the color of any of its neighbors presently in the
graph, rotating colors in case there is more than one choice.
c. Repeat a and b until the graph is either completely rebuilt, or there is no color
available to color the node.
 If we get stuck, then the graph may not be r-colorable, we could try again with a
different heuristic, say reusing colors as often as possible. If no other choice, we have to spill
a variable to memory.
Graph Coloring for register assignment (Chaitin's Algorithm):
 Register allocation is interpreted as a graph coloring problem .
 Nodes represent live range of the variable.
 Edges represent the connection between two live ranges .
 Assigning color to the nodes such that no two adjacent nodes have same color .
 Number of colors represents the minimum number of registers required .
A k-coloring of the graph is mapped to k registers .
Steps :
1. Choose an arbitrary node of degree less than k .
2. Push that node onto the stack and remove all of it's outgoing edges .
3. Check if the remaining edges have degree less than k, if YES goto 5 else goto #
4. If the degree of any remaining vertex is less than k then push it onto to the stack .
5. If there is no more edge available to push and if all edges are present in the stack POP
each node and color them such that no two adjacent nodes have same color.
6. Number of colors assigned to nodes is the minimum number of registers needed .
# spill some nodes based on their live ranges and then try again with same k value . If
problem persists it means that the assumed k value can't be the minimum number of registers
.Try increasing the k value by 1 and try the whole procedure again .
For the same instructions mentioned above the graph coloring will be as follows :
Assuming k=4

After performing the graph coloring, final graph is obtained as follows

final graph with k(4) colors
Note : Any color(register) can be assigned to 'i' as it has no edge to any other nodes .

A SIMPLE CODE GENERATOR:

A code generation, in the context of compilers, translates intermediate code (like three-
address code) into target machine code, often focusing on efficient resource utilization,
particularly registers.
For example: consider the three-address statement a :=b+c It can have the following sequence
of codes:
ADD Rj, Ri Cost = 1 // if Ri contains b and Rj contains c
(or)
ADD c, Ri Cost = 2 // if c is in a memory location
(or)
MOV c, Rj Cost = 3 // move c from memory to Rj and add
ADD Rj, Ri
Register and Address Descriptors:
• Generating Target code from Three address statement.
Keep computed results in register as long as possible.
• x = a + b; Value of a stored in register.
Use of descriptors to keep track of register contents and addresses for name.
• Register Descriptor is used keep track of current contents of all registers. Initially all
registers are empty.
• Address descriptor stores location where current value of the name can be found at run
time. Information is available in symbol table.
Mode Operand addressability:
  S – value of operand in storage.
 R – value of operand in Register.
 IS – address of operand in storage (indirect addressing).
 IR – address of operand in Register (indirect register addressing)
Register descriptors:
Register descriptors are data structures that store information about the registers used in the
program. This includes the registration number and its name, along with its type. The
compiler uses this information when generating machine code for your program, so it's
important to keep it up-to-date while writing code!
The compiler uses the register file to determine what values will be available for use in your
program. This is done by walking through each of the registers and determining if they
contain valid data or not. If there's nothing in a register, then it can be used for other
purposes.

By using register descriptors we can keep track of the registers which are currently occupied.
The status field is of Boolean type which is used to check whether the register is occupied
with some data or not. When the status field holds the value True' then operand descriptors
fields contains the pointer to the operand descriptor who is having the latest value in the
register.
Address Descriptor
An address descriptor is used to represent the memory locations used by a program. Address
descriptors are created by the get Reg function, which returns a structure containing
information about how to access memory. Address descriptors can be created for any
instruction in your program's code and stored in registers or on the stack; however, only one
instance of an address descriptor will exist at any given time (unless another thread is
executing).
The address descriptor has following fields.

The attributes mean type of the operand. It generally refers to the name of temporary
variables.
The addressing mode indicates whether the addresses are of type 'S', 'R','IS','IR'.
The third field is location field which indicates whether the address is in storage location or in
register.
CODE GENERATION ALGORITHM:
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.
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.
FUNCTION getreg:
1. If Y is in register (that holds no other values) and Y is not live and has no next use after X
= Y op Z then return register of Y for L.
2. Failing (1) return an empty register
3. Failing (2) if X has a next use in the block or op requires register then get a register R,
store its content into M (by Mov R, M) and use it.
4. Else select memory location X as L.
The function getreg returns the location L to hold the value of x for the assignment x :=
y op z.
1. If the name y is in a register that holds the value of no other names (recall that copy
instructions such as x := y could cause a register to hold the value of two or more variables
the register of y for L. Update the address descriptor of y to indicate that y is no longer in L.
2. Failing (1), return an empty register for L if there is one.
3. Failing (2), if x has a next use in the block, or op is an operator such as indexing, that
requires a register, find an occupied register R. Store the value of R into memory location (by
MOV R, M) if it is not already in the proper memory location M, update the address
descriptor M, and return R. If R holds the value of several variables, a MOV instruction must
be generated for each variable that needs to be stored. A suitable occupied register might be
one whose datum is referenced furthest in the future, or one whose value is also in memory.
4. If x is not used in the block, or no suitable occupied register can be found, select the
memory location of x as L.
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:
CODE GENERATION FROM DAG:
Generating code from DAG is much simpler than the linear sequence of three address code.
Using DAG we can rearrange some sequence of instructions and generate an efficient code.
There are various algorithms used generating code from DAG
1. Rearranging order
2. Heuristic ordering
3. Labeling algorithm
1. Rearranging order:
The order of three address code affects the cost of the object code being generated In the sense
that by changing the order in which computations are done we can obtain the object code with
minimum cost.
For example: (a + b) - (e - (c + d))
Three address code
t1 := a + b
t2 := c + d
t3 := e - t2
t4 := t1 - t3
Rearranging order of instructions
t2 := c + d
t3 := e - t2
t1 := a + b
t4 := t1 - t3
A DAG can be constructed for the above sequence as follows
2. Heuristic Ordering:
The heuristic ordering algorithm is as follows.
1) Obtain all the interior nodes. Consider these interior nodes as unlisted interior nodes
2) while (unlisted interior nodes remain)
{
3) pick up an unlisted node n, whose parents have been listed
4) list n;
5) while (the leftmost child m of n has no unlisted parent AND is not leaf
{
6) list m;
7) n=m
}
}
First we will draw a DAG for some given expression.
The DAG is first numbered from top to bottom and from left to right. Then consider the
unlisted interior nodes 1.2 3 4 5 6 8.
Initially the only node with unlisted parent is 1 .. set n=1 by line 4) of algorithm Now left
argument of 1 is 2 and parent of 2 is 1 which is listed. Hence list 2. .. set n=2 by line 7) of
algorithm

Now we will find the leftmost node of 2 and that is 6. But 6 has unlisted parent 5. Hence we
can not select 6.
We therefore can switch to 3. The parent of 3 is 1 which is listed one. Hence list 3 set n=3

The left of 3 is 4. As parent of 4 is 3 and that is listed hence list 4. Left of 4 is 5 which has
listed parent(i.e. 4) hence list 5. Similarly list 6

As now only 8 is remaining from the unlisted interior nodes we will list it. Hence the
resulting list is 1 2 3 4 5 6 8. Then the order of computation is decided by reversing this list.
We get the order of evaluation as 8 6 5 4 3 2 [Link] also means that we have to perform the
computations at these nodes in the given order
t8=d/e
t6=a-b
t5=t6+c
t4=t5*t8
t3=t4-e
t2=t6+t4
t1=t2*t3
3. Labeling Algorithm:
The labeling algorithm generates the optimal code for given expression in which minimum
registers are required. Using labeling algorithm the labeling can be done to the tree by
visiting nodes in bottom up order. By this all the child nodes will be labeled before its parent
nodes.
For computing the label at node n with the label L1 to left child and label 1.2 to the right
child as
Label (n) = max(L1, L2) if L1 !=L2
L1+1 if L1 !=L2
 We start in bottom-up fashion and label left leaf as 1 and right leaf as 0.
 If labels of the children of a node n are 1.1 and L2 respectively then
Label (n) = max(L1, L2) if L1 !=L2
Label (n) = L1+1 if L1 =L2
1. Generate machine code for the following instruction V=a+(b*c)-d.
Sol:
Generating machine code for an expression like V = a + (b * c) - d requires knowing the
specific CPU architecture (e.g., x86, ARM, RISC-V), instruction set, and addressing modes,
as machine code is a series of binary data that a specific CPU interprets directly.
Below are examples of how the equivalent assembly code (which is then converted to
machine code by an assembler) would look for different instruction set architectures,
assuming variables are stored in memory and values are loaded into registers for arithmetic
operations.
Three-Address Instructions
In this architecture, each instruction can specify up to three operands (two source operands
and one destination).
Assembly
MUL R1, b, c ; R1 = b * c (multiply b and c, store in Register 1)
ADD R2, a, R1 ; R2 = a + R1 (add a to R1, store in Register 2)
SUB V, R2, d ; V = R2 - d (subtract d from R2, store in V)
Two-Address Instructions
In this common architecture, one operand often serves as both a source and the destination.
assembly
MOV R1, b ; R1 = b (move the value of b into R1)
MUL R1, c ; R1 = R1 * c (multiply R1 by c)
MOV R2, a ; R2 = a (move the value of a into R2)
ADD R2, R1 ; R2 = R2 + R1 (add R1 to R2)
SUB R2, d ; R2 = R2 - d (subtract d from R2)
MOV V, R2 ; V = R2 (move the final result into V)
One-Address Instructions
This type of instruction uses an implied accumulator register (AC) for most operations.
assembly
LOAD b ; AC = b (load b into the accumulator)
MUL c ; AC = AC * c (multiply the accumulator by c)
STORE T1 ; T1 = AC (store the intermediate result in temporary memory T1)
LOAD a ; AC = a (load a into the accumulator)
ADD T1 ; AC = AC + T1 (add T1 to the accumulator)
SUB d ; AC = AC - d (subtract d from the accumulator)
STORE V ; V = AC (store the final result in V)
Machine Code (Binary/Hexadecimal)
The actual machine code would be the binary representation of these assembly instructions,
which varies by CPU. For example, the x86 instruction MOV EAX, 0x5 might be the
machine code B8 05 00 00 00 in hexadecimal. A human programmer rarely interacts directly
with this binary format.