[SOLVED] CS compiler assembly mips Procedures

Procedures
COMP273 McGill 1

a HLL Functions -> MIPS Procedures Passing arguments
Function calls
The stack
Nested functions
Register Conventions
a Be aware:
There are many ways to program
This might be the most complicated topic in MIPS COMP273 McGill
2
Overview

HLL Functions to MIPS Procedure
//asimplefunction inC
int sum (int x, int y ) { return x + y ;
}
void main () {
int a = sum ( 3, 6 ) ; }
How do we convert this into MIPS assembly?
a What instructions can accomplish this?
a What information must compiler / programmer keep track of?
COMP273 McGill 3

int sum (int x, int y ) { return x + y ;
a
The parent/caller needs to
a Save arguments to child/callee
}
void main () { a
int a = sum ( 3, 6 ) ; }
Save return address to child/callee a Branch to child/callee
main is the parent/caller sum is the child/callee
The Caller and the Callee
a
The child/callee needs to
a Save the return value for parent/caller
a Branch back to parent/caller
COMP273 McGill
5

Register Conventions on Passing Arguments
a Registers play a major role in keeping track of information
a Register conventions
int sum (int x, int y ) { return x + y ;
Arguments Return value
$a0, $a1, $a2, $a3
$v0, $v1
}
void main () {
a Parent/Caller should save the arguments in $a0, $a1, $a2, $a3 a Child/Callee should save the return values in $v0, $v1
int a = sum ( 3, 6 ) ; }
COMP273 McGill 6

}
# Save argument to $a1
COMP273 McGill
7
Register Conventions on Passing Arguments
int sum (int x, int y ) {
return x + y ;
# Add $a0 + $a1
# Save the result in $v0
}
void main () {
int a = sum ( 3, 6 ) ;
# Save argument to $a0
add$v0, $a0, $a1
li $a0, 3
li $a1, 6

// C code
# MIPS code
int sum (int x, int y ) { return x + y ;
Sum: add $v0, $a0, $a1 j AfterSum
# $t0 = $a0 + $a1 # jump to AfterSum
}
void main () {
Main:li $a0,3 li $a1,6
#$a0=3 #$a1=6
# jump to sum
}
AfterSum:
addi$s0,$v0,3 #a=sum(3,6)+3
int a; // $s0
a = sum(3,6) + 3;
j sum

First Try with Jump
8

// C code
int sum (int x, int y ) { return x + y ;
If Sum has multiple callers, how does it return to the right place?
}
void main () {
# MIPS code
Sum: add $v0, $a0, $a1 # $t0 = $a0 + $a1
int a; // $s0
a = sum(3,6) + 3;
j ???
# jump to ???

int b; // $s1
b = sum(4,8) + 7 ; }
Not perfect!
9

0x1008
j AfterSum Main:li $a0,3
0x2000
0x2004
0x2008
li $a1,6 j sum
#$a0=3 #$a1=6
# jump to sum
0x200C
AfterSum: addi $s0, $v0, 3 # a = sum(3,6) + 3
Label = Address of the Instructions
# MIPS code from the
last example
# $t0 = $a0 + $a1 # jump to AfterSum
0x1000 Sum: add $v0, $a0, $a1
11

0x1000
0x1008
Sum: add $v0, $a0, $a1 j 0x200C
0x2000
0x2004
0x2008
Main: li $a0, 3 li $a1, 6 j 0x1000
#$a0=3 #$a1=6
# jump to sum
0x200C
AfterSum: addi $s0, $v0, 3 # a = sum(3,6) + 3
Label = Address of the Instructions
# MIPS code from the
last example
# $t0 = $a0 + $a1 # jump to AfterSum
Save the return address of the caller, so we can jump back
12

Register Conventions for Jump a Registerforthereturnaddress$ra
int sum (int x, int y ) { return x + y ;
}
void main () {
int a = sum ( 3, 6 ) ; }
a Parent/Caller saves the returning address in $ra before jumping a Child/Callee jumps to the $ra after done
COMP273 McGill
13

Jump Register Operation a JumpRegisterjr
Syntax: jr register j label
jr $ra
Jr takes an address
J takes a label (fixed location)
(variable location)
Only useful if we know exact address to jump to
Rarely applicable in situations other than return from function
COMP273 McGill 14

int sum (int x, int y ) {
return x + y ;
0x1008 jr 0x2000 Main: li
$ra $a0, 3
# jump to address $ra
}
void main () {
}
int a = sum ( 3, 6 ) ;

0x2004 0x2008 0x200C 0x2010
li $a1, 6
li $ra, 0x2010
jSum
# $a0 = 3
# $a1 = 6
# save address to $ra # jump to sum
COMP273 McGill
15
Jump Register Operation
Address
0x1000
# MIPS code
Sum: add $t0, $a0, $a1 # $t0 = $a0 + $a1
AfterSum:
Need to find the address of the next instruction

COMP273 McGill
16
Main:li li la
$a0,3 $a1,6
$ra, AfterSum Sum
#$a0=3
#$a1=6
# load address to $ra # jump to sum
AfterSum:
j
Load Address
a Pseudo-instruction: Load Address la Register Label
Sum: add jr
$t0, $a0, $a1
$ra
# $t0 = $a0 + $a1
# jump to address $ra

Jump and Link Instruction
a JumpandLinksyntax:jallabel
Step 1 (link): Save address of next instruction into $ra (Why next?)
Step 2 (jump): Jump to the given label
jal should really be called laj (}a ^o]vl v iua_
a Very useful for function calls:
jal stores return address in $ra jr jumps back to that address
COMP273 McGill 18

int sum (int x, int y ) {
return x + y ;
}
void main () {
A little bit simpler than jr and jal
}
# MIPS code
int a = sum ( 3, 6 ) ;
COMP273 McGill
19
Address
0x2000
0x2004
0x2008
0x200C
Main:li $a0,3 li $a1,6
#$a0=3 #$a1=6
# jump to sum
Jump and Link Instruction
0x1000
0x1008
Sum: add $t0, $a0, $a1 jr $ra
# $t0 = $a0 + $a1
# jump to address $ra
jal Sum

int square (int x ) {
return x * x ;
}
void main () {
a SumSquare calledsquare, but $ra will be overwritten when calling square
}
What about Nested Procedures?
}
int sumSquare (int x, int y ) {
a maincalledsumSquare, save the returning address in $ra
return square(x) + y ;
int a = sumSquare ( 3, 6 ) ;

COMP273 McGill
20

COMP273 McGill
22
Memory Layout
Where Instructions are stored (.text in MARS)
Statically allocated variables (.data in MARS) Dynamically decleard variables.
Explicitly created space, e.g., malloc(); new;
Space for local variables and registers in procedure calls

COMP273 McGill
23
Memory Layout
Size of the text and data are fixed once the program is compiled
Heap starts at lower address and grows downward toward higher memory locaion
Stack starts at a fixed address and grows upward toward lower memory location

COMP273 McGill
24
Stack v.s Heap
Stack is very organized. It is used to save data for procedures

a Stack is used to support subroutines
a Register $29 or $sp is used as a Stack Pointer points to the top of the stack
a The elements on the stack are words
COMP273 McGill
25
Stack

COMP273 McGill
26
Push and Pop for Stack
a Push: add an item on the top of the stack
a Pop: take the top element and remove it from the stack
a Stack pointer $sp always points to the last used space in the stack.

Push the Stack
a Register $sp always points to the last used space in the stack.
a To push, decrement this pointer by 4, then fill it with data.
# move the stack pointer down
addi $sp, $sp, -4
# store the content of $s0 into address $sp sw $s0, 0($sp)
COMP273 McGill 27

Pop the Stack
a Register $sp always points to the last used space in the stack.
a To pop, load the data and increment the stack pointer by 4
# load the content in address $sp to $s0
lw $s0, 0($sp)
# move the stack pointer up
addi $sp, $sp, 4
COMP273 McGill 28

Nested Call
a If you are a subroutine that will call another subroutine, follow this convention
Before you call anyone, push the return address in $ra on the stack
When you are done calling, pop the return address of the stack into $ra
COMP273 McGill 29

}
COMP273 McGill
30
Nested Call
# 1.
push $ra onto the stack
// Nested functions in C
addi
sw
# 2. jal
# 3. add
# 4.
lw
addi #5.
jr $ra
# move stack pointer # store $ra
int square (int x ) { return x * x ;
}
int sumSquare (int x, int y ) {
return square(x) + y ;
}
void main () {
int a = sumSquare ( 3, 6 ) ;
Main:
li$a0, 3
li$a1, 6
jal Sum
Square:
Sum:
$sp, $sp, -4
$ra, 0($sp)
Jump to Square ($ra is overwritten) Square
Return from Square. $v0 has the result $v0, $v0, $a1 # Calculate square(x) + y pop $ra so we can return to the main $ra, 0($sp)
$sp, $sp, 4 # move stack pointer jump back to main
some code here

int a
int b
int c
= 2 ; // Use $s0 for a = sum ( 3, 6 ) ;
= a + b;
}
COMP273 McGill
32
Save Variables in Procedure
int sum (int x, int y ) {
int z = 5 ; // Use $s0 for z return z + x + y ;
a What if the callee needs some registers for local variables?
}
void main () {
a Canwemakesurethat
the callee does
not overwrite important data?

int a
int b
int c
= 2 ; // Use $s0 for a = sum ( 3, 6 ) ;
= a + b;
}
COMP273 McGill
33
Save Variables in Procedure
int sum (int x, int y ) {
int z = 4 ; // Use $s0 for z return z + x + y ;
For the Callee:
1. Pushtheregisterstothestack 2. Executethecalleeinstructions
}
void main () {
3. Beforereturningtothecaller, restore the registers from the stack

int sum (int x, int y ) { intz=5;//Use$s0forz return z + x + y ;
#Fo1.r tphusehC$asl0leteo: the stack addi $sp, $sp, -4
}
void main () {
#2.2.EExxecute cthaleleinesstriuncstirounctsions
}
# jump back to main
int a = 2 ; // Use $s0 for a int b = sum ( 3, 6 ) ;
int c = a + b;
add $v0,$s0,$a1 #$v0=z+x+y # 3.sRtaesctkore $s0 for the caller
COMP273 McGill
34

Save Variables in Procedure
Sum:
1. Pushtheregisterstothestack
sw $s0, 0($sp) # Store $s0
li $s0,5 #$s0=5
3. Beforereturningtothecaller,
add $s0,$s0,$a0 #$s0=z+x restore the registers from the
sw $s0, 0($sp) addi $sp, $sp, 4 jr $ra
# Restore $s0

Assembly Variables: Registers (from slide 08)
COMP273 McGill 37

Register Conventions in Procedure Call
If the callee is going to use some saved registers, it must save those saved registers on the stack
The callee }ev[o v o} e oZ temporary registers If the caller wants to preserve the temporary registers, it
must save those tempororay registers on the stack
COMP273 McGill 38

2. Assignargument(s),ifany 3. JumpandLinkjal
2. 3.
Use the saved registers
4. Restoretempvariable(s)from stack
Restore the values of saved registers from stack
Steps for Procedure Call
Caller Callee
1. Pushthetempvariable(s)if needed onto stack
1.
Push the saved registers onto stack if needed
COMP273 McGill
4.
Jump back with jr $ra
39

COMP273 McGill
returning. dZo[e Z oZ[a called saved registers. 40
Name
Waea }v  ooM2
No, they are expected to contain return values NoU oZ a aPuvoe2
No, any procedure may change them at any time
$v0-v1 $a0-$a3 $t0-$t9
$s0-$s7
YES. If the callee changes these registers, it must restore the original values before
Preserved on Call?

COMP273 McGill
41
Name
Waea }v  ooM2
$sp
Yes. The stack pointer must point to the same place before and after the jal ooU }a oe oZ ooa }v[o be able to restore values from the stack.
$ra
Yes, until the next jal call NoU oZ a aPuvoe2 Always 0
$a0-$a3
$zero
Preserved on Call?

Lastly
a Each register has a purpose and limits to its usage. Learn oZe v (}oo} oZuU v ]( }[a a]o]vP all the code yourself
a If every developer follows the same standard, it would be easier to exchange code or build large software
COMP273 McGill
42

a Functionsarecalledwithjalandjr a Stack is your friend
a Text Section 2.8
Purpose
Operations
Arithmetic Memory Decision Unconditional Branches
add, addi
lw, sw
Review
beq, bne, slt, slti, sltu, sltiu j, jal, jr
COMP273 McGill
43