Transcript Slides

Code Generation III
PAs

PA4


5.1 – 7.2
PA5 (bonus)

24.1 – 24.2
2
PA4

Translate AST to LIR (file.ic -> file.lir)





Instruction list for every method
Dispatch table for each class
Literal strings (all literal strings in file.ic)
Optimizations (optional)
Use microLIR simulator
3
microLIR simulator

Java application


Use it to test your translation







Accepts and executes file.lir
Checks correct syntax
Performs lightweight semantic checks
Runtime semantic checks
Debug modes (-verbose:1|2)
Prints program statistics (#registers, #labels, etc.)
Comes with sample inputs
Read Manual
4
IC compiler
Compiler
ic
IC
Program
Lexical
Analysis
Syntax
Analysis
Parsing
AST
Symbol
Table
etc.
Inter.
Rep.
(IR)
Code
Generation
exe
x86
executable
5
Translating static calls
LIR code:
StaticCall _A_foo(a=R1,b=5,c=x),R3
# push caller-saved registers
push %eax
push %ecx
push %edx
# push parameters
mov -4(%ebp),%eax
push %eax
push $5
mov -8(%ebp),%eax
push %eax
# push x
# push 5
# push R1
call _A_foo
mov %eax,-16(%ebp)
# store returned value in R3
# pop parameters (3 params*4 bytes = 12)
add $12,%esp
# pop caller-saved registers
pop %edx
pop %ecx
pop %eax
6
Translating virtual calls
LIR code:
R1
DVPtr
x
y
VirtualCall R1.2(b=5,c=x),R3
# push caller-saved registers
push %eax
push %ecx
push %edx
# push parameters
mov -4(%ebp),%eax
push %eax
push $5
# push x
# push 5
# Find address of virtual method and call it
mov -8(%ebp),%eax
# load this
push %eax
# push this
mov 0(%eax),%eax
# Load dispatch table address
call *8(%eax)
# Call table entry 2 (2*4=8)
_DV_A
0
_A_rise
1
_A_shine
2
_A_twinkle
mov %eax,-12(%ebp)
# store returned value in R3
# pop parameters (2 params+this * 4 bytes = 12)
add $12,%esp
# pop caller-saved registers
pop %edx
pop %ecx
pop %eax
7
Library function calls
class Library {
static void println(string s);
static void print(string s);
static void printi(int i);
static void printb(boolean b);
static int readi();
...
//
//
//
//
//
prints string s followed by a newline.
prints string s.
prints integer i.
prints boolean b.
reads one character from the input.
Static function calls
 Reference type arguments require nonnull runtime check

8
Function prologue/epilogue
_A_foo:
# prologue
push %ebp
mov %esp,%ebp
# push local variables of foo
sub $12,%esp # 3 local vars+regs * 4 = 12
# push callee-saved registers
push %ebx
push %esi
push %edi
function body
_A_foo_epilogoue: # extra label for each function
# pop callee-saved registers
pop %edi
pop %esi
pop %ebx
mov %ebp,%esp
pop %ebp
ret
9
Representing dispatch tables
PA4
file.lir
_DV_A: [_A_sleep,_A_rise,_A_shine]
_DV_B: [_A_sleep,_B_rise,_B_shine,_B_twinkle]
file.ic
class A {
void sleep() {…}
void rise() {…}
void shine() {…}
static void foo() {…}
}
class B extends A {
void rise() {…}
void shine() {…}
void twinkle() {…}
}
PA5
file.s
# data section
.data
.align 4
_DV_A:
.long _A_sleep
.long _A_rise
.long _A_shine
_DV_B:
.long _A_sleep
.long _B_rise
.long _B_shine
.long _B_twinkle
10
Runtime checks

Insert code to check attempt to perform illegal
operations

Null pointer check



Array bounds check



__allocateArray(size) – size needs to be >0
Do we need to check argument of __allocateObject(#)?
Division by zero


MoveArray
Array allocation size check


MoveField, MoveArray, ArrayLength, VirtualCall
Reference arguments to library functions should not be null
Div, Mod
If check fails jump to error handler code that
prints a message and gracefully exists program
11
Null pointer check
# null pointer check
cmp $0,%eax
je labelNPE
Single generated handler for entire program
labelNPE:
push $strNPE
call __println
push $1
call __exit
# error message
# error code
12
Array bounds check
# array bounds check (eax = array, ecx = index)
mov -4(%eax),%ebx # ebx = length
cmp %ecx,%ebx
jle labelABE
# ebx <= ecx ?
cmp $0,%ecx
jl labelABE
# ecx < 0 ?
Single generated handler for entire program
labelABE:
push $strABE
call __println
push $1
call __exit
# error message
# error code
13
Array allocation size check
# array size check
cmp $0,%eax
# eax == array size
jle labelASE
# eax <= 0 ?
Single generated handler for entire program
labelASE:
push $strASE # error message
call __println
push $1
# error code
call __exit
14
Division by zero check
# division by zero check
cmp $0,%eax
# eax is divisor
je labelDBE
# eax == 0 ?
Single generated handler for entire program
labelDBE:
push $strDBE # error message
call __println
push $1
# error code
call __exit
15
Hello world example
class Library {
void println(string s);
...
}
class Hello {
static void main(string[] args) {
Library.println("Hello world\n");
}
}
16
Representing strings
4
1
1
1
1
1
13
H
e
l
l
o
1
1
1
1
1
1
1
1
w
o
r
l
d
\
n
String reference

Array preceded by a word indicating the length of the
array
17
Assembly file structure
.title
header
statically-allocated
data: string literals
and dispatch tables
"hello.ic“
# global declarations
.global __ic_main
# data section
.data
.align 4
.int 13
str1: .string "Hello world\n“
# text (code) section
.text
#---------------------------------------------------.align 4
__ic_main:
push %ebp
# prologue
mov %esp,%ebp
Method bodies
and error handlers
push $str1
call __print
add $4, %esp
# print(...)
mov $0,%eax
# return 0
mov %ebp,%esp
pop %ebp
ret
# epilogue
18
Implementation

Hacker’s approach: translate directly to text



Not flexible
Hard to debug
Use objects representation
Possible instruction hierarchy
ASMInstr
LabelInstr
BinOpInstr
UnOpInstr
CallInstr
ASMInstr
JumpInstr
CondJumpInstr
RetInstr
Possible operand hierarchy
ASMOperand
Immediate
Integer
X86Reg
Memory
Literal
Reg
Variable
Parameter
Displacement
Implementation example
class BinOpInstr extends ASMInstr {
public final Operand src;
public final Operand dst;
public final String name;
public BinOpInstr(String name, Operand src, Operand dst) {
// Sanity check
if (src instanceof Memory &&
dst instanceof Memory) {
throw new RuntimeException(“Too many memory operands for arith instruction!”);
this.name = name;
this.src = src;
this.dst = dst;
}
public String toString() {
if (ASMInstr.intelSyntax) {
return name + “ “ + src + “,” + dst;
}
else {
return name + “ “ + dst + “,” + src;
}
}
}
From assembly to executable
prog.ic
IC
Program
Lexical
Analysis
Syntax
Analysis
AST
Parsing
Symbol
Table
etc.
Inter.
Rep.
(IR)
Code
Generation
prog.s
x86
assembly
prog.s
x86
assembly
GNU
assembler
prog.o
libic.a
(libic + gc)
GNU
linker
prog.exe
23
Optimizations

More efficient register allocation for
statements





IC statement
Basic Block
Method
…
Eliminate unnecessary labels and jumps

Post-translation pass
24
Optimizing labels/jumps
If we have subsequent labels:
_label1:
_label2:
We can merge labels and redirect jumps to the merged
label


If we have
jump label1
_label1:
Can eliminate jump

Eliminate labels not mentioned by any instruction
25