Module V:

Design of a simple Code Generator

R19CS301 - Automata Theory and Session by:

Compiler Design S. Sampath Kumar, ASP/CSE

5 October 2024 Design of a simple Code Generator 1

 2 5 October 2024

Agenda
➢ Next Use
➢ Register and Address Descriptors
➢ Code Generator Algorithm
➢ Code sequences for pointer assignments
➢ Conditional Statements

Design of a simple Code Generator

 3 5 October 2024

MODULE V: Intermediate Code, Code Generation and

Code Optimization

Issues in Code Generation - Design of a simple

Code Generator - Principal Sources of Optimization
– Peep-hole optimization – DAG - Optimization of
Basic Blocks

Design of a simple Code Generator

 4 5 October 2024

Course Outcomes:
CO # Outcome K Level

Design and analyze Finite Automata and regular expression for any given Regular
CO1 K3
language
Understand and apply concepts of Context-Free Grammars, Push-Down Automata,
CO2 K3
and Turing machines to analyze computational problems and language ambiguities.
Demonstrate proficiency in Lexical Analysis, including defining tokens, recognizing
CO3 K2
tokens, and utilizing tools like Lex

CO4 Analyze and construct different parsers K3

Design efficient code generators and optimize code using techniques like peep-hole
CO5 K2
optimization, DAGs, and basic block optimization.

Design of a simple Code Generator

 5 5 October 2024

Next-Use
A three-address statement x:=y+z is said to define
x and to use y and z.
 A name in a basic block is said to be live at a
given point if its value is used after that point in
the program.
 Use of a name:
 ifstatement i assigns a value to x ;
 stmt j has x as an operand and control can flow from i
to j along a path with no intervening assignments to
 we can say that j uses the value of x computed at i.

Design of a simple Code Generator

 6 5 October 2024

Next-Use
 Next-use information is needed for dead-code
elimination and register assignment
 Next-use is computed by a backward scan of a
basic block and performing the following actions on
statement
i: x := y op z
 Add liveness/next-use info on x, y, and z to statement i
 Set x to “not live” and “no next use”
 Set y and z to “live” and the next uses of y and z to i
Design of a simple Code Generator
 7 5 October 2024

Next-Use (Step 1)

i: a := b + c

j: t := a + b [ live(a) = true, live(b) = true, live(t) = true,

nextuse(a) = none, nextuse(b) = none, nextuse(t) = none ]

Attach current live/next-use information

Design of a simple Code Generator
Because info is empty, assume variables are live
 8 5 October 2024

Next-Use (Step 2)

i: a := b + c live(a) = true nextuse(a) = j

live(b) = true nextuse(b) = j
live(t) = false nextuse(t) = none
j: t := a + b [ live(a) = true, live(b) = true, live(t) = true,
nextuse(a) = none, nextuse(b) = none, nextuse(t) = none ]

Compute live/next-use information at j

Design of a simple Code Generator
 9 5 October 2024

Next-Use (Step 3)

i: a := b + c [ live(a) = true, live(b) = true, live(c) = false,

nextuse(a) = j, nextuse(b) = j, nextuse(c) = none ]

j: t := a + b [ live(a) = true, live(b) = true, live(t) = true,

nextuse(a) = none, nextuse(b) = none, nextuse(t) = none ]

Attach current live/next-use information to i

Design of a simple Code Generator
 10 5 October 2024

Next-Use (Step 4)
live(a) = false nextuse(a) = none
live(b) = true nextuse(b) = i
live(c) = true nextuse(c) = i
live(t) = false nextuse(t) = none
i: a := b + c [ live(a) = true, live(b) = true, live(c) = false,
nextuse(a) = j, nextuse(b) = j, nextuse(c) = none ]

j: t := a + b [ live(a) = false, live(b) = false, live(t) = false,

nextuse(a) = none, nextuse(b) = none, nextuse(t) = none ]

Compute live/next-use information i

Design of a simple Code Generator
 11 5 October 2024

A Code Generator
 Generates target code for a sequence of three-
address statements using next-use information
 Uses new function getreg to assign registers to
variables
 Computed results are kept in registers as long as
possible, which means until:
 Result is needed in another computation
 End of procedure call or end of block
 Checks if operands to three-address code are
available in registers

Design of a simple Code Generator

 12 5 October 2024

Register and Address Descriptors

A register descriptor keeps track of what is currently
stored in a register at a particular point in the code,
e.g. a local variable, argument, global variable, etc.
MOV a,R0 “R0 contains a”
 An address descriptor keeps track of the location
where the current value of the name can be found
at run time, e.g. a register, stack location, memory
address, etc.
MOV a,R0
MOV R0,R1 “a in R0 and R1”
Design of a simple Code Generator
 13 5 October 2024

The Code Generation Algorithm

 For each statement x := y op z
1. Set location L = getreg(y, z)
2. If y  L then generate
MOV y’,L
where y’ denotes one of the locations where the value of y is
available (choose register if possible)
3. Generate
OP z’,L
where z’ is one of the locations of z;
Update register/address descriptor of x to include L
If L is a register update its descriptor
4. If y and/or z has no next use and is stored in register, update
register descriptors to remove y and/or z

Design of a simple Code Generator

 14 5 October 2024

Code Generation Algorithm

 For x:= y
 If y is in a register change the register and address descriptor
to record that x is found only in register for y
 If y is in memory; invoke getreg and load y and then make it
the location of x (or) use MOV y, x

Design of a simple Code Generator

 15 5 October 2024

The getreg Algorithm

 To compute getreg(y, z)
1. If y is stored in a register R and R only holds the value
y, and y has no next use, then return R;
Update address descriptor: value y no longer in R
2. Else, return a new empty register if available
3. Else, if x has a next use in the block find an occupied
register R;
Store contents (register spill) by generating
MOV R,M
for every M in address descriptor of y;
Return register R
4. Return a memory location
Design of a simple Code Generator
 17 5 October 2024

Code Generation Example

Statements Code Generated Register Descriptor Address Descriptor
Registers empty
t := a - b MOV a,R0 R0 contains t t in R0
SUB b,R0

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

SUB c,R1 R1 contains u u in R1

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

R1 contains u v in R0

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

MOV R0,d d in R0 and
memory

Design of a simple Code Generator

 18 5 October 2024

Code sequences for indexed assignments

a : = b[i]
i is in Register Ri MOV b(Ri), R (2)
i is in Memory Mi MOV Mi, R
MOV b(R), R (4)
i in Stack MOV Si(A), R
MOV b(R), R (4)

Design of a simple Code Generator

 19 5 October 2024

Code sequences for indexed assignments

 a[i] := b
i is in Register Ri MOV b, a(Ri) (3)
i is in Memory Mi MOV Mi, R
MOV b, a(R) (5)
i in Stack MOV Si(A), R
MOV b, a(R) (5)

Design of a simple Code Generator

 20 5 October 2024

Code sequences for pointer assignments

a = *p
p is in Register Rp MOV *Rp, a (2)
p is in Mp MOV Mp, R
MOV *R, R (3)
p is in Stack MOV Sp(A), R
MOV *R, R (3)

Design of a simple Code Generator

 21 5 October 2024

Code sequences for pointer assignments

*p := a
p is in Register Rp MOV a, *Rp (2)
p is in Mp MOV Mp, R
MOV a, *R (4)
p is in Stack MOV a, R
MOV R, *Sp(A) (4)

Design of a simple Code Generator

 22 5 October 2024

Conditional Statements
 Branch if value of register meets the required condition
 Condition codes
if x < y goto z
CMP x, y
CJ< z
Example 1
x := y +z if x < 0 goto z
MOV y, R0
ADD z, R0
MOV R0, x
CJ< z
Example 2

Design of a simple Code Generator

23 5 October 2024

Design of a simple Code Generator

 24 5 October 2024

References
 Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman,
“Compilers: Principles, Techniques and Tools”, Second Edition,
Pearson Education, 2009.
 Steven S. Muchnick, “Advanced Compiler Design and
Implementation”, Morgan Kaufmann Publishers - Elsevier Science,
India, Indian Reprint 2003.
 V. Raghavan, “Principles of Compiler Design”, Tata McGraw Hill
Education Publishers, 2010.
 Allen I. Holub, “Compiler Design in C”, Prentice-Hall Software
Series, 1993.
 Randy Allen, Ken Kennedy, “Optimizing Compilers for Modern
Architectures: A Dependence based Approach”, Morgan
Kaufmann Publishers, 2002.
Design of a simple Code Generator
25 5 October 2024

Design of a simple Code Generator