Lec 12 - Code Generator

Code Generation
An Overview !!
Phases of a compiler
Program (character stream)
Lexical Analyzer (Scanner)
Token
Stream
Syntax Analyzer (Parser)
Parse Tree
Semantic Analyzer
Intermediate Representation
Intermediate Code Optimizer
Optimized Intermediate Representation
Code Generator
Assembly code
2
OR
Program (character stream)
Lexical Analyzer (Scanner)
Token
Stream
Syntax Analyzer (Parser)
Parse Tree
Semantic Analyzer
High-level IR
Low-level IR
Intermediate Representation
Code Generator
Assembly code
3
Position of Code Generator
4
Role of a Code Generator
􀂃Severe requirements imposed
– Output must be correct and high quality, means it should make
effective use of the resources of the target machine
– Code generator should run efficiently
􀂃Generating optimal code is un-decidable

– Must rely on heuristic techniques that generate good code
– Choice of heuristic technique is very important
􀂃Details are dependent on target language and operating system
􀂃Certain generic issues are inherent in the design of basically all code
generators
5
Issues in the Design of Code Generator
 Input to the Code Generator

 Output of Code Generator
 Memory Management
 Instruction Selection
 Register Allocation
6
Input to Code Generator
 The input to the code generator consists of:
 Intermediate code produced by the front end
 Information in the symbol table
 Remember that intermediate code can come in many

forms
 We will concentrate on three-address code
 The code generator typically assumes that:

 Input is free of errors
 Type checking has taken place and necessary type
conversions operators have already been inserted

7
Output of Code Generator
 The target program is the output of the code generator
 Can take a variety of forms

1. Absolute machine language
 code that need not be modified, translated, or interpreted before it
can be used by the processor for which it was designed.
 it can be placed in a location in memory and immediately executed
 Inflexible
2. Re-locatable machine language
 code that can be run from any memory location
 Allows subprograms to be compiled separately
 Overhead of extra linking and loading step
3. Assembly language
 makes the process of code generation somewhat easier
 We can generate symbolic instructions and use the macro facilities
of the assembler to help generate code .
8
 The price paid is the assembly step after code generation
Memory Management
 Compiler must map names in source code
to addresses of data objects at run-time
 Done cooperatively by front-end and

code generator
 Code generator uses information in

symbol table
9
Instruction Selection
 Depends on the nature of the instruction set
 If efficiency is not a concern, instruction selection is straightforward

 For each type of three-address statement, there is a code skeleton for
outlining target code
 Unfortunately, this kind of statement – by - statement code generation
often produces poor code. For example, the sequence of statements
a := b + c
d := a + e
would be translated into
MOV b, R0
ADD c, R0
MOV R0, a
MOV a, R0
ADD e, R0
MOV R0, d
 Here the fourth statement is redundant, and so is the third if ‘a’ is not
subsequently used. 10
Register Allocation
 Instructions are usually faster if operands are in
registers instead of memory
 Efficient utilization of registers is important in

generating good code
 Register allocation selects the set of variables that

will reside in registers
 A register assignment phase picks the specific

register in which a variable resides
11
Generating Assembly Code
Learn by Examples !!
Points to Remember
 Assembly Instructions are of the form
 OP Source , Destination
 For example
 MOV Source , Destination
 Moves source to destination
 ADD Source , Destination
 Adds source to destination
 SUB Source , Destination
 Subtracts source from destination
 MUL Source , Destination
 Multiplies source with destination and stores result in destination
 DIV Source , Destination
 Divides destination with source and stores result in destination
13
Example 1 (a = b + c)
 Three Address Code  Assembly Code
 MOV b, R0;
 t1 = b + c  ADD c, R0;
 a = t1  MOV R0, a
14
Example 2 ( a = a + 1)
 MOV a, R0;
 t1 = a + 1  ADD #1, R0;
 a = t1  MOV R0, a
15
Example 3 (a := b * -c + b * -c;)
( Consider optimization not done)
 t1 := -c  MOV c, R0;
 t2 := b * t1  MUL #-1,R0;
 t3 := -c  MUL b,R0;
 t4 := b * t3  MOV c, R1;
 t5 := t2 + t4  MUL #-1,R1;
 a := t5  MUL b,R1;
 ADD R1,R0;
 MOV R0,a;
16
Example 4 (a := b * -c + b * -c;)
( Consider optimization done)
 t1 := -c  MOV c, R0;
 t2 := b * t1  MUL #-1,R0;
 t3 := t2 + t2  MUL b,R0;
 a := t3  ADD R0,R0;
 MOV R0, a;
17
Example 5 d:=(a-b) + (a-c) + (a-c)
(Consider optimization not done)
Three Address Code Assembly Code



 t1 := a – b;
 mov a, r0
 t2 := a – c;
 sub b,r0
 t3 := t1 + t2;
 mov a,r1
 t4 := a – c;
 sub c,r1
 t5 := t3 + t4;
 add r1,r0
 d := t5;
 mov a,r2
 sub c,r2
 add r2,r0 ;
 mov r0,d
Example 5 d:=(a-b) + (a-c) + (a-c)
(Consider optimization done)
Three Address Code Assembly Code



 t1 := a – b;
 mov a, r0
 t2 := a – c;
 sub b,r0
 t3 := t1 + t2;
 mov a,r1
 t4 := t3 + t2;
 sub c,r1
 d := t4;
 add r1,r0
 add r1,r0 ;
 mov r0,d
Let’s Revise
Position of Code Generator
21
Issues in the Design of Code Generator
 Input to the Code Generator

 Output of Code Generator
 Memory Management
 Instruction Selection
 Register Allocation
22
Generating Assembly Language
 Assembly Instructions are of the form

 OP Source , Destination
 For example
 MOV Source , Destination
 Moves source to destination
 ADD Source , Destination
 Adds source to destination
 SUB Source , Destination
 Subtracts source from destination
 MUL Source , Destination
 Multiplies source with destination and stores result in destination
 DIV Source , Destination
 Divides destination with source and stores result in destination

23

Lec 12 - Code Generator

Uploaded by

Copyright:

Available Formats

Lec 12 - Code Generator

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lec 12 - Code Generator

Uploaded by

Copyright:

Available Formats

Code Generation

􀂃Generating optimal code is un-decidable

􀂃Details are dependent on target language and operating system

 Input to the Code Generator

 Information in the symbol table

 Remember that intermediate code can come in many

 The code generator typically assumes that:

 Type checking has taken place and necessary type

conversions operators have already been inserted

 Can take a variety of forms

 Done cooperatively by front-end and

 Code generator uses information in

 If efficiency is not a concern, instruction selection is straightforward

 Efficient utilization of registers is important in

 Register allocation selects the set of variables that

 A register assignment phase picks the specific

 Moves source to destination

 ADD Source , Destination

 Adds source to destination

 SUB Source , Destination

 Subtracts source from destination

 MUL Source , Destination

 Multiplies source with destination and stores result in destination

 DIV Source , Destination

 Divides destination with source and stores result in destination

Three Address Code Assembly Code

Three Address Code Assembly Code

 Input to the Code Generator

 Assembly Instructions are of the form

 Moves source to destination

 ADD Source , Destination

 Adds source to destination

 SUB Source , Destination

 Subtracts source from destination

 MUL Source , Destination

 Multiplies source with destination and stores result in destination

 DIV Source , Destination

 Divides destination with source and stores result in destination

You might also like