Transcript mov -8(%ebp)

Code Generation II
IC compiler
Compiler
ic
IC
Program
Lexical
Analysis
Syntax
Analysis
Parsing
AST
Symbol
Table
etc.
Inter.
Rep.
(IR)
Code
Generation
exe
x86
executable
2
x86 assembly



AT&T syntax and Intel syntax
We’ll be using AT&T syntax
Work with GNU Assembler (GAS)
3
Immediate and register operands

Immediate




Value specified in the instruction itself
Preceded by $
Example: add $4,%esp
Register



Register name is used
Preceded by %
Example: mov %esp,%ebp
4
Memory Access

Memory operands



Obtain value at given address
Example: mov (%eax), %ebx
Base displacement





Obtain value at computed address
Syntax: disp(base,index,scale)
address = base + (index * scale) + displacement
Example: mov $42, 2(%eax)
Example: mov $42, (%eax,%ecx,4)
5
Accessing Variables

Examples




%ebp + 8 = first parameter
%eax = %ebp + 8
(%eax) = the value 572
8(%ebp) = the value 572
%eax,%ebp+8
…
Use offset from frame pointer
…

param n
…
572
Return address
ebp
ebp-4
SP
Previous ebp
local 1
…
local n
6
LIR to assembly

Need to know how to translate:

Function bodies



Translation for each kind of LIR instruction
Calling sequences
Correctly access parameters and variables




Compute offsets for parameter and variables
Dispatch tables
String literals
Runtime checks & error handlers
7
Translating LIR instructions

Translate function bodies:
1.
Compute offsets for:


Local variables & LIR registers (-4,-8,-12,…)
Function parameters (+8,+12,+16,…)

2.
take this parameter into account
Translate instruction list for each function

Local translation for each LIR instruction

local (machine) register allocation
8
Memory offsets implementation
// MethodLayout instance per function declaration
class MethodLayout {
// Maps variables/parameters/LIR registers to
// offsets relative to frame pointer (EBP)
Map<Memory,Integer> memoryToOffset;
}
PA5
1
virtual function takes
one extra parameter: this
(manual) LIR translation
void foo(int x, int y) {
int z = x + y;
g = z; // g is a field
Library.printi(z);
}
PA4
_A_foo:
Move x,R0
Add y,R0
Move R0,z
Move this,R1
MoveField R0,R1.1
Library __printi(R0),Rdummy
MethodLayout for foo
Memory
Offset
this
+8
x
+12
y
+16
z
-4
R0
-8
R1
-12
9
Memory offsets example
2
LIR translation
_A_foo:
Move x,R0
Add y,R0
Move R0,z
Move this,R1
MoveField R0,R1.1
Library __printi(R0),Rdummy
MethodLayout for foo
Memory
Offset
this
+8
x
+12
y
+16
z
-4
R0
-8
R1
-12
Translation to x86 assembly
_A_foo:
push %ebp
mov %esp,%ebp
sub $12, %esp
mov 12(%ebp),%eax
mov %eax,-8(%ebp)
mov 16(%ebp),%eax
add -8(%ebp),%eax
mov %eax,-8(%ebp)
mov -8(%ebp),%eax
mov %eax,-4(%ebp)
mov 8(%ebp),%eax
mov %eax,-12(%ebp)
mov -8(%ebp),%eax
mov -12(%ebp),%ebx
mov %eax,4(%ebx)
mov -8(%ebp),%eax
push %eax
call __printi
add $4,%esp
_A_foo_epilogoue:
mov %ebp,%esp
pop %ebp
ret
# prologue
# Move x,R0
# Add y,R0
# Move R0,z
# Move this,R1
# MoveField R0,R1.1
# Library __printi(R0)
# epilogoue
10
Translating instructions
LIR Instruction
Translation
MoveArray R1[R2],R3
mov
mov
mov
mov
-8(%ebp),%ebx # -8(%ebp)=R1
-12(%ebp),%ecx # -12(%ebp)=R2
(%ebx,%ecx,4),%ebx
%ebx,-16(%ebp) # -16(%ebp)=R3
MoveField x,R2.3
mov -12(%ebp),%ebx # -12(%ebp)=R2
mov -8(%ebp),%eax # -12(%ebp)=x
mov %eax,12(%ebx) # 12=3*4
MoveField _DV_A,R1.0
movl $_DV_A,(%ebx) # (%ebx)=R1.0
(movl means move 4 bytes)
ArrayLength y,R1
mov -8(%ebp),%ebx # -8(%ebp)=y
mov -4(%ebx),%ebx # load size
mov %ebx,-12(%ebp) # -12(%ebp)=R1
Add R1,R2
mov -16(%ebp),%eax # -16(%ebp)=R1
add -20(%ebp),%eax # -20(%ebp)=R2
mov %eax,-20(%ebp) # store in R2
11
Translating instructions
LIR Instruction
Translation
Mul R1,R2
mov -8(%ebp),%eax # -8(%ebp)=R2
imul -4(%ebp),%eax # -4(%ebp)=R1
mov %eax,-8(%ebp)
Div R1,R2
(idiv divides EDX:EAX
stores quotient in EAX
stores remainder in EDX)
mov $0,%edx
mov -8(%ebp),%eax
mov -4(%ebp),%ebx
idiv %ebx
mov %eax,-8(%ebp)
Mod R1,R2
mov $0,%edx
mov -8(%ebp),%eax
mov -4(%ebp),%ebx
idiv %ebx
mov %edx,-8(%ebp)
# -8(%ebp)=R2
# -4(%ebp)=R1
# store in R2
# -8(%ebp)=R2
# -4(%ebp)=R1
Compare R1,x
mov -4(%ebp),%eax
cmp -8(%ebp),%eax
# -4(%ebp)=x
# -8(%ebp)=R1
Return R1
(returned value stored in EAX register)
mov -8(%ebp),%eax # -8(%ebp)=R1
jmp _A_foo_epilogue
Return Rdummy
jmp _A_foo_epilogue
12
SP
call
Callee push code
callee
caller
…
Caller push code
FP
Push caller-save registers
Push actual parameters
(in reverse order)
…
caller
Call sequences
(prologue)
Callee pop code
(epilogue)
push return address
Jump to call address
Caller pop code
SP
Push current base-pointer
bp = sp
Push local variables
Push callee-save registers
Param n
…
param1
SP
Pop callee-save registers
Pop callee activation record
Pop old base-pointer
return
Copy returned value
Reg 1
…
Reg n
SP
SP
Previous fp
Local 1
Local 2
…
…
Local n
FP
pop return address
Jump to address
Pop parameters
Pop caller-save registers
Return address
SP
13
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
only if the value
stored in these
registers is needed by
the caller
callerh
# push parameters
mov -4(%ebp),%eax
push %eax
push $5
mov -8(%ebp),%eax
push %eax
# push x
Only if return
register is not
Rdummy
# 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
14
Virtual functions

Indirect call: call *(Reg)

Example: call *(%eax)

Used for virtual function calls
Dispatch table lookup
 Passing/receiving the this variable

15
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
16
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
Optional:
only if
only if the these
register allocation
registers will be
optimization is used
modified
(in PA5) by the collee
# 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
17
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
18
Runtime checks

Insert code to check attempt to perform illegal operations

Null pointer check






MoveField, MoveArray, ArrayLength, VirtualCall
Reference arguments to library functions should not be null
Array bounds check
Array allocation size check
Division by zero
If check fails jump to error handler code that prints a
message and gracefully exists program
19
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
20
Array bounds check
# array bounds check
mov -4(%eax),%ebx #
mov $0,%ecx
#
cmp %ecx,%ebx
jle labelABE
#
cmp $0,%ecx
jl labelABE
#
ebx = length
ecx = index
ebx <= ecx ?
ecx < 0 ?
Single generated handler for entire program
labelABE:
push $strABE
call __println
push $1
call __exit
# error message
# error code
21
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
22
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
23
Hello world example
class Library {
void println(string s);
}
class Hello {
static void main(string[] args) {
Library.println("Hello world!");
}
}
24
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“
symbol exported to
linker
string length
in bytes
# text (code) section
.text
#---------------------------------------------------.align 4
__ic_main:
push %ebp
# prologue
comment
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
25
Assembly file structure
.title
"hello.ic“
# global declarations
.global __ic_main
# data section
.data
.align 4
.int 13
str1: .string "Hello world\n“
# text (code) section
.text
prologue – save ebp
and set to be esp
push print parameter
call print
store return value of
main in eax
#---------------------------------------------------.align 4
__ic_main:
push %ebp
# prologue
mov %esp,%ebp
push $str1
call __print
add $4, %esp
# print(...)
mov $0,%eax
# return 0
mov %ebp,%esp
pop %ebp
ret
# epilogue
pop parameter
epilogue – restore
esp and ebp (pop)
26
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
27