Unit VI : Code Optimization and Code Generation
Course : Language Processor and Compiler Construction
Manisha Mali
manisha.mali@viit.ac.in
BRACT’S, Vishwakarma Institute of Information Technology, Pune-48
(An Autonomous Institute affiliated to Savitribai Phule Pune University)
(NBA and NAAC accredited, ISO 9001:2015 certified)
Department of Computer Engineering
Code Generation
Unit VI
3
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
Index
• Issues in code generation
• Register allocation and assignment
• Code generator concept
4
Introduction
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
Source
Intermediate Intermediate
program Front code Code code Code target
program
end Optimizer generator
Symbol
table
Position of code generator
5
Code generation Manisha Mali, Department
of Computer Engineering,
26-Oct-20
VIIT , Pune-48
• Produces the target language in a specific
architecture.
• The target program is normally a relocatable object
file containing the machine codes.
• Ex:
( assume that we have an architecture with instructions whose at least one
of its operands is a machine register)
MOVE id2,R1
MULT id3,R1
ADD #1,R1
MOVE R1,id1
Manisha Mali
6
Code Generation Manisha Mali, Department
of Computer Engineering,
VIIT , Pune-48
26-Oct-20
• Requirements imposed on a code generator
▫ Preserving the semantic meaning of the source
program and being of high quality
▫ Making effective use of the available resources of the
target machine
▫ The code generator itself must run efficiently.
• A code generator has three primary tasks:
▫ Instruction selection, register allocation, and
instruction ordering
Manisha Mali
7
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
Issues in the Design of a Code
Generator
• Details depend on
▫ Target language
▫ Operating System
• But following issues are inherent in all code
generation problems
▫ Input to the Code Generator
▫ Memory management
▫ Instruction Selection
▫ Register allocation and
▫ Evaluation order
▫ Approaches to code generation
8
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
Input to the Code Generator
• We assume, front end has
▫ Scanned, parsed and translate the source program into
a reasonably detailed intermediate representations
▫ Type checking, type conversion and obvious semantic
errors have already been detected
▫ Symbol table is able to provide run-time address of the
data objects
▫ Intermediate representations may be
Postfix notations
Three address representations
Stack machine code
Syntax tree
DAG
9
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
Target Programs
• The output of the code generator is the target
program.
• Target program may be
▫ Absolute machine language
It can be placed in a fixed location of memory and
immediately executed
▫ Re-locatable machine language
Subprograms to be compiled separately
A set of re-locatable object modules can be linked
together and loaded for execution by a linker
▫ Assembly language
Easier
10
Instruction Selection
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
• The nature of the instruction set of the target
machine determines the difficulty of the instruction
selection.
• Uniformity and completeness of the instruction set
are important
• Instruction speeds is also important
▫ Say, x = y + z
Mov y, R0
Add z, R0
Mov R0, x
Statement by statement code generation often
produces poor code
11
Instruction Selection (2)
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
a=b+c
d=a+e
MOV b, R0
ADD c, R0
MOV R0,
MOV R0, aa If a is subsequently
used
MOV a,
MOV a, R0
R0
ADD e, R0
MOV R0, d
12
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
Instruction Selection (3)
• The quality of the generated code is determined
by its speed and size.
• Cost difference between the different
implementation may be significant.
▫ Say a = a + 1
Mov a, R0
Add #1, R0
Mov R0, a
▫ If the target machine has increment instruction
(INC), we can write
inc a
13
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
Register Allocation
• Instructions involving register operands are usually
shorter and faster than those involving operands in
memory.
• Efficient utilization of register is particularly
important in code generation.
• The use of register is subdivided into two sub
problems
▫ During register allocation, we select the set of
variables that will reside in register at a point in the
program.
▫ During a subsequent register allocation phase, we pick
the specific register that a variable will reside in.
14
A Code-Generation Algorithm Manisha Mali, Department
of Computer Engineering,
VIIT , Pune-48
26-Oct-20
The code-generation algorithm takes as input a sequence of Three-
address statements constituting a basic block. For each three-
address statement of the form x : = y op z perform the Following
actions :
1. Invoke a function getreg to determine the location L where the
result of the computation y op z should be stored. L will usually be a
register, but it could also be a memory location.
2. Consult the address descriptor for y to determine y', (one of) the
current location(s) of y. Prefer the register for y' if the value of y is
currently both in memory and a register. If the value of y is not
already in L, generate the instruction MOV y' ,L to place a copy of y
in L,
3. Generate the instruction OP z ' , L where z' is a current location of
z. Again, prefer a register to a memory location if z is in both.
Update the address descriptor of x to indicate that x is in location L.
If L is a register, update its descriptor to indicate that it contains the
value of x. and remove x from all other register descriptors.
4. If the current values of y and/or z have no next uses, are not live on
exit from the block. and are in registers, alter the register descriptor
to indicate that, after execution of x := y op z, those registers no
longer will contain y and/or z, respectively.
15
A Code-Generation Algorithm (Cont’d)
Manisha Mali, Department 26-Oct-20
• Consider d := (a-b) + (a-c) + (a-c)
of Computer Engineering,
VIIT , Pune-48
• Three address code sequence is
t := a-b
u := a-c
v := t+u
d :=v+u
• Code
sequence is
16
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
Tree-
rewriting
for some
target-
machine
instructi
on
17
Syntax-directed translation scheme
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
constructed
18
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
Generating code from DAG
1. Rearranging the order
2. Heuristic for ordering nodes of DAG
3. Labeling algorithm
4. Code generation by traversing a labeled tree
19
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
Dynamic Programming Code generation
algorithm
• Machine instructions for operations
• Machine instructions for copy statements
• Ending the basic block
• Managing register and address descriptors
20
Exercise Manisha Mali, Department
of Computer Engineering,
VIIT , Pune-48
26-Oct-20
For the machine that contains three registers R1,
R2, R3 and following instructions. [16 Mks]
MOV MEM, REG
MOV REG, MEM
SUB REG1, REG2
SUB MEM,REG
MOV REG1,REG2
Use optimal code generation algorithm for
following expression tree and generate target
code.
(((a – b) – (c – d)) – (e – (f – (g – h))))
21
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
Exercise (Contd)
MOV MEM, REG /* load data in memory Mem
to register Reg
MOV REG, MEM /* store data in register Reg to
memory Mem
SUB REG1, REG2 /* Reg2 – Reg1 Reg2
SUB MEM,REG /* Reg – Mem Reg
MOV REG1,REG2 /* Move data in register Reg1 to
register Reg2
22
Exercise (Contd)
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
Optimized Three Address code
23
Exercise (Contd) Manisha Mali, Department
of Computer Engineering,
26-Oct-20
Generated code
VIIT , Pune-48
• MOV a, R0
• SUB b, R0
• MOV c, R1
• SUB d, R1
• SUB R1, R0
• MOV f, R2
• MOV g, R1
• SUB h, R1
• SUB R1, R2
• MOV e, R1
• SUB R2, R1
• SUB R1, R0
24
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
Exercise
• given the code fragment
x := a*a + 2*a*b + b*b;
y := a*a – 2*a*b + b*b;
draw the dependency graph before and after
common subexpression elimination.
25
Answers Manisha Mali, Department
of Computer Engineering,
26-Oct-20
x := a*a + 2*a*b + b*b; VIIT , Pune-48
y := a*a – 2*a*b + b*b;
dependency graph before CSE
x y
+ +
+ * - *
* * b b * * b b
a a * b a a * b
2 a 2 a
26
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
Answers
dependency graph after CSE
x y
+ +
+ * - *
* * b * * b b
a * a a * b
2 2 a
27
Answers
Manisha Mali, Department 26-Oct-20
of Computer Engineering,
VIIT , Pune-48
dependency graph after CSE
x y
+ +
+ * -
* * b
a *
2
26-Oct-20
References
• D. M. Dhamdhere, Systems Programming and Operating Systems,
Tata McGraw-Hill, ISBN 13:978-0-07-463579-7, Second Revised
Manisha Mali, Department of Computer
Edition
• Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, Compilers Principles,
Engineering, VIIT , Pune-48
Techniques and Tools, Addison Wesley, ISBN:981–235–885 - 4,
Low Price Edition
• J. J. Donovan, Systems Programming, McGraw-Hill, ISBN 13:978-
0-07-460482-3, Indian Edition
28
26-Oct-20
Manisha Mali, Department of Computer Engineering, VIIT , Pune-48
29
