Transcript Subroutine

Subroutines
Natawut Nupairoj
Assembly Language
1
Subroutines
• A subroutine is a piece of program codes that
performs some particular functions.
– Function, Procedure, Method
• A subroutine must behave:
– in-line execution: flow naturally.
– no unintended side effects: must declare explicitly
which registers will be changed which will be not after
the call.
– multiple arguments: should allow a caller to pass
more than one argument.
Natawut Nupairoj
Assembly Language
2
Subroutine
• Thus, CPU must provide:
• Call/return mechanism.
– Save the address of the instruction being executed (pc)
of the caller so that, when return, it can resume
execution at the next instruction.
• A register protection mechanism.
– How to save the values of the register before the call
and restore the values back when returns from calling.
• An argument passing convention.
– An agreement between caller and callee on how
arguments are to be passed.
Natawut Nupairoj
Assembly Language
3
Call/Return Mechanism
•
•
•
•
•
Two special instructions: call and ret.
Use “call” to call for a particular subroutine.
Use “ret” to return from the subroutine.
Both have a delay slot.
Example:
.global sub_a
sub_a: save %sp, -96, %sp
...
call sub_b
nop
...
Natawut Nupairoj
.global sub_b
sub_b: save %sp, -64, %sp
...
...
...
ret
restore ! AFTER ret
Assembly Language
4
Register Saving
• Subroutine must explicitly declare which
registers will be changed, which won’t.
• Subroutine also needs to use registers for
computation.
• To reduce the side-effect (due to modifying
registers), we will save values in registers before
doing anything and restore back before return.
• In most CPUs, we will push/pop values in
registers to/from the stack.
• In SPARC, we have save/restore instructions.
Natawut Nupairoj
Assembly Language
5
Register Saving
• Save: allocate space in stack and save registers
(in special ways).
• Restore: deallocate space and restore registers
(in special ways).
• Pushing/Poping registers to/from stack requires
lots of time.
• In SPARC, we use the concept “Register
Window” (performed by Save andRestore).
Natawut Nupairoj
Assembly Language
6
SPARC Register
• SPARC has 8 global registers and 128 general
registers.
• For general registers, only 24 registers are
active or “mapped” at any time.
• Thus this makes 24 + 8 = 32 registers available.
• The mapping mechanism is called “register
window”.
• SPARC has two internal pointers:
– CWP: Current Window Pointer
– WIM: Window Invalid Mark
Natawut Nupairoj
Assembly Language
7
SPARC Register Window
24
registers
CWP
in
%i0 - %i7
local
%l0 - %l7
global
%g0 - %g7
out
%o0 - %o7
Un-mapped
Mapped
WIM
Natawut Nupairoj
Assembly Language
8
Effect of Save Instruction
24
registers
CWP
in
%i0 - %i7
global
%g0 - %g7
local
%l0 - %l7
out
%o0 - %o7
Un-mapped
WIM
Natawut Nupairoj
Mapped
Assembly Language
9
Effect of Save Instruction
Before "Save"
%fp
in
%i0 - %i7
local
%l0 - %l7
After "Save"
%sp
%fp
out
%o0 - %o7
in
%i0 - %i7
local
%l0 - %l7
%sp
out
%o0 - %o7
Natawut Nupairoj
Assembly Language
10
Effect of Save Instruction
Before “Save”
Before "Save"
%fp
%sp
in
%i0 - %i7
Stack area for A
%fp
local
%l0 - %l7
After "Save"
%sp
%fp
out
%o0 - %o7
in
%i0 - %i7
After “Save”
%sp
local
%l0 - %l7
Stack area for B
(%sp) %fp
%sp
Stack area for A
out
%o0 - %o7
(%fp)
Natawut Nupairoj
Assembly Language
11
Effect of Save Instruction
• Provide a new set of local registers.
• Provide a new set of out registers.
• Make the old “out” registers into the new “in”
registers.
• In the process, the old %sp becomes the new
%fp.
• Global registers remain unchanged.
Natawut Nupairoj
Assembly Language
12
Register Window Overflow
• Since we have only 128 general registers, we
can save at most 7 sets of registers.
• This means we can “save” 7 times without
having to “restore”.
• What happen if we run out of registers ?
• We save it to the main memory, provided in the
stack !!!
• Remember, every time we allocate spaces in
stack with “save”, we always reserve 64 bytes to
save registers.
Natawut Nupairoj
Assembly Language
13
Register Window Overflow
7
WIM
7
Save Registers
6
5
6
Local Vars
5
4
4
3
3
2
2
CWP
1
1
WIM
0
Natawut Nupairoj
CWP
Assembly Language
0
14
Arguments to Subroutines
• How we can pass arguments to a subroutine ?
• Remember, the “out” registers of the caller
become the “in” registers of the called
subroutine.
• However, we can passed at most 6 registers
(%o0-%o5) because %o6 is the stack pointer
and %o7 contains the return address.
• The called subroutine accesses the arguments
via the “in” registers.
Natawut Nupairoj
Assembly Language
15
Passive Arguments
Before "Save"
%fp
in
%i0 - %i7
local
%l0 - %l7
After "Save"
%sp
%fp
out
%o0 - %o7
in
%i0 - %i7
local
%l0 - %l7
%sp
out
%o0 - %o7
Natawut Nupairoj
Assembly Language
16
Our Fifth Program
int mul(int a, int b)
{
int r;
register int i;
r = 0;
i = b;
while(i > 0) {
r = r + a;
i--;
}
main()
{
int r;
short x, y;
x = 10;
y = 30;
r = mul(x, y);
}
return r;
}
Natawut Nupairoj
Assembly Language
17
Our Fifth Program
mul:
define(mul_a_r, i0)
define(mul_b_r, i1)
define(mul_r_s, -4)
define(mul_i_r, l0)
define(r_s, -4)
define(x_s, -6)
define(y_s, -8)
.global mul
save %sp, (-64-4)&-8, %sp
clr %l1
st
%l1, [%fp + mul_r_s]
mov %mul_b_r, %mul_i_r
Natawut Nupairoj
! r = 0;
! i = b;
Assembly Language
18
Our Fifth Program
loop:
cmp
ble
nop
%mul_i_r, 0
done
ld
add
st
[%fp + mul_r_s], %l1
%l1, %mul_a_r, %l1
%l1, [%fp + mul_r_s]
sub
ba
nop
%mul_i_r, 1, %mul_i_r ! i--;
loop
Natawut Nupairoj
! start while loop
! r + a
! r = r + a;
Assembly Language
19
Our Fifth Program
done:
main:
ld
[%fp + mul_r_s], %i0
ret
restore
.global main
save %sp, (-64-8)&-8, %sp
mov 10, %l0
sth %l0, [%fp + x_s]
mov 30, %l0
sth %l0, [%fp + y_s]
Natawut Nupairoj
! return r;
! After ret
! x = 10;
! y = 30;
Assembly Language
20
Our Fifth Program
ldsh [%fp + x_s], %o0
ldsh [%fp + y_s], %o1
call mul
nop
st
%o0, [%fp + r_s]
mov
ta
1, %g1
0
Natawut Nupairoj
! prepare first arg.
! prepare second arg.
Assembly Language
21
Optimizing the Common Case
• Why does SPARC have 128 registers (which can
provide upto 7 saves before overflowed) ?
• Why does SPARC have 8 “out” registers to pass
arguments to a subroutine ?
• The SPARC designers studied real programs
and conclude that these are quite common.
• We can have more registers, but it may cost
more and we will not gain much improvement.
• This is called “optimizing the common case”.
Natawut Nupairoj
Assembly Language
22
Return Values
• A subroutine that returns a value is called a
function.
• We can store the returned value in the “in”
registers of the called subroutine and they will
become the “out” registers when return.
• In sub_a:
In sub_b:
...
call sub_b
nop
st
%o0, [%fp-4]
...
Natawut Nupairoj
...
add %o0, %l2, %l3
mov %l3, %i0
ret
restore
Assembly Language
23
Return Values
• Or we can use “restore” to return value to any
register.
restore %l3, %l0, %i5
• This adds %l3 with %l0 (both from the called
subroutine registers) then stores the result in
%i5 of the calling subroutine (or after “restore”).
• However, typical common convention is to
return value in %o0 (of the calling subroutine).
Natawut Nupairoj
Assembly Language
24
Passing many Arguments
• In some subroutines, passing only 6 arguments
may not be enough.
• If more than 6 arguments are required, we store
the rest in the stack before calling.
• For example, main calls:
sub1(1, 2, 3, 4, 5, 6, 7, 8);
• We put first 6 arguments in %o0-%o5.
• Then put the last two arguments in the stack.
• Thus, we must allocate more spaces before
calling.
Natawut Nupairoj
Assembly Language
25
Passing many Arguments
(main stack)
%sp
%sp
64 bytes to save
registers
64 bytes to save
registers
%sp + 64 + 4
%sp + 64 + 8
local vars.
%fp
Natawut Nupairoj
last two args
local vars.
%fp
Assembly Language
26
Passing many Arguments
%sp
64 bytes to save
registers
for
sub1
local vars.
%fp
64 bytes to save
registers
for
main
%fp + 64 + 4
%fp + 64 + 8
last two args
local vars.
Natawut Nupairoj
Assembly Language
27
Passing many Arguments
main:
save
...
add
mov
st
mov
st
mov
mov
mov
mov
mov
Natawut Nupairoj
%sp, -64, %sp
%sp, -8, %sp
! Allocate for 2 args.
8, %o0
%o0, [%sp + 8+64]
7, %o0
%o0, [%sp + 4+64]
6, %o5
5, %o4
4, %o3
3, %o2
2, %o1
Assembly Language
28
Passing many Arguments
call _sub1
mov 1, %o0
sub %sp, -8, %sp
...
! Delay Slot
! Release stack.
• In sub1:
sub1:
save
ld
ld
add
add
sub
...
Natawut Nupairoj
%sp,
[%fp
[%fp
%o0,
%i5,
%o0,
(-92&-8), %sp
+ 8+64], %o0
+ 4+64], %o1
%o1, %o0
%o0, %o0
%i4, %o0
! The last two args.
! The sixth argument.
! The fourth argument.
Assembly Language
29
Our Sixth Program
main()
{
int x, y;
x =
y =
x =
10,
12;
x + 1;
sub1(2, 0, x, y, x+5,
3, y);
}
Natawut Nupairoj
sub1(int a, int b, int c, int
d, int e, int f, int g,
int h)
{
int r;
r = a + b + c + d + e + f
+ g + h;
return r;
}
Assembly Language
30
Our Sixth Program
define(x_s, -4)
define(y_s, -8)
define(arg7_s, 64+4)
define(arg8_s, 64+8)
! main
define(a_r,
define(b_r,
define(c_r,
define(d_r,
define(e_r,
define(f_r,
define(g_s,
define(h_s,
define(r_s,
! sub1
Natawut Nupairoj
%i0)
%i1)
%i2)
%i3)
%i4)
%i5)
arg7_s)
arg8_s)
-4)
! 7th arg.
! 8th arg.
Assembly Language
31
Our Sixth Program
main:
.global main
save %sp, (-64-8)&-8, %sp
mov 12, %l0
st
%l0, [%fp + x_s]
add %l0, 1, %l0
st
%l0, [%fp + y_s]
add
%sp, -8, %sp
mov
mov
ld
ld
2, %o0
0, %o1
[%fp + x_s], %o2
[%fp + y_s], %o3
Natawut Nupairoj
! x = 12;
! y = x + 1;
!
!
!
!
!
!
Assembly Language
Reserve
the 7th
The 1st
The 2nd
The 3rd
The 4th
stack for
and 8th args.
arg.
arg.
arg.
arg.
32
Our Sixth Program
ld
add
mov
mov
mov
st
ld
st
call
nop
st
sub
[%fp + x_s], %l0
%l0, 5, %l0
%l0, %o4
10, %o5
3, %l0
%l0, [%sp + arg7_s]
[%fp + y_s], %l0
%l0, [%sp + arg8_s]
sub1
%o0, [%fp + x_s]
%sp, -8, %sp
! Store result from sub1
! Release stack
mov
ta
1, %g1
0
! Exit program
Natawut Nupairoj
! The 5th arg.
! The 6th arg.
! 3 is the 7th arg.
! Y is the 8th arg.
Assembly Language
33
Our Sixth Program
sub1:
.global sub1
save %sp, (-64-4)&-8, %sp
add %i0, %i1, %l0
add %l0, %i2, %l0
add %l0, %i3, %l0
add %l0, %i4, %l0
add %l0, %i5, %l0
ld
[%fp + g_s], %l1
add %l0, %l1, %l0
ld
[%fp + h_s], %l1
add %l0, %l1, %l0
st
%l0, [%fp + r_s]
ld
[%fp + r_s], %o0
ret
restore %o0, 0, %o0
Natawut Nupairoj
! Read the 7th arg.
! Read the 8th arg.
! Store result to r.
! return r;
! After ret
Assembly Language
34