Transcript Figure contd… from the prev. slide…

Chapter 7
Subroutines
Dr. A.P. Preethy
7.1 Introduction
There is frequently a need either to repeat a computation or to repeat the
computation with different arguments.
• Subroutines can be used in such situations
• Subroutines may be either open or closed
Open subroutine
• is insertion of required code whenever it is needed in the program
e.g. macro
• arguments are passed in the registers that are given as arguments to
the subroutine.
Closed subroutine
• is one in which the code appears only once in the program;
whenever it is needed, a jump to the code is executed, and when it
completes, a return is made to the instruction occurring after the jump
instruction.
• arguments may be placed in registers or on the stack
• A subroutine also allows you to debug code once and then sure that
all future instantiations of the code will be correct
• Any register that the subroutine uses must first be saved and then
restored after the subroutine completes execution
• Arguments to subroutines are normally considered to be local
variables of the subroutine,and the subroutine is free to change
them
• However, this is not always the case, for e.g., in multiplication,
multiplicand is not changed
2
7.2
Open Subroutines
• The cmul macro discussed in Chapter 6 is an open subroutine, and can
handle multiplication by constants:
cmul (%r0, 603, %g1, %r1)
• To multiply %r0 by 100,
cmul(%r0, 100, %g1, %r0)
• And the code expands into:
!start open coded multiply for
!%r0= %r0 * 100, using %g1 as temp
sll %r0, 2, %r0
sll %r0, 3, %g1
sub %r0, %g1, %r0
sll %g1, 2, %g1
add %r0, %g1, %r0
! end open coded multiply
• Open Subroutines are very efficient with no wasted instructions
• Open Subroutines are very flexible and can be as general as the program
wishes to make them
• Every time open subroutine referenced, the code is expanded, resulting
in long code
• So it is better to write code once as a closed subroutine and to branch to
the code, whenever needed
7.3
Register Saving
• Almost any computation will involve the use of registers
Usually when subroutines are called, registers are pushed onto the stack
and popped from, when it returns
• To avoid the execution time involved, in CISC, sometimes a special
register save mask is used, that would indicate, by bits that were set, which
registers were to be saved
(contd….)
(Register Saving contd…)
• SPARC architecture provides a register file with a mapping register that
indicates the active registers
• It provides 128 registers, with the programmer having access to the eight
global registers, and only 24 of the mapped registers at a time
• save instruction changes the register mapping so that new registers are
provided
• restore instruction restores the register mapping on subroutine return
• The 32 registers are divided into four groups : in, local, out and general
• The eight general register %g0 to %g8 are not mapped and are global to
all subroutines
• “in” & “out” register are used to pass arguments to closed subroutine
• “local” registers are used for subroutine’s local variables
• When save instruction is executed the out register become the in register,
and a new set of local and out registers is provided
• The mapping pointer into the register file is changed by 16 registers
The next two slides show Register Sets
(Figure 7.1)
8
Figure 7.1: A Register Set
(Figure contd…on next slide)
9
(Figure contd…from the prev. slide)
Figure 7.1: A Register Set
10
• The current register set is indicated by the current window ptr (cwp).
•
The last free register set is marked by the window invalid bit, in the
WIM
•
After save instruction is executed, the situation in Figure 7.2 results,
the prior subroutine’s register contents remain unchanged until a
restore instruction is executed, resetting the cwp
(Figure 7.2 follows …)
11
Figure 7.2: Register Sets
12
• If a further five subroutine calls are made without any returns, window
overflow will occur (Figure 7.3 follows on the next slide)
• The out registers being used are from the invalid register window marked
by the wim bit
• Hardware trap will occur at the time of window overflow
• saves and restores can be made in a range of six without window overflows
or underflows (it is expensive if recursive subroutine calls are frequently
made)
Figure 7.3: Windows Overflow
14
More about Register window mapping…
• Register window mapping explains why the frame pointer (%o6)
becomes stack pointer (%i6) after save instruction
Save %sp, -64, %sp
• This will subtract 64 from the current stack pointer, but stores the result
into the new stack pointer, leaving the old %sp contents unchanged, which
becomes the new %fp
• restore instruction restores the register window set. On doing this, a
register window can underflow if the cwp is moved to the wim. When this
happens the window trap routine restores the registers from the stack and
resets the pointers
• restore is also an add instruction and is used as the final add instruction in
a subroutine
7.4
Subroutine Linkage
• The SPARC architecture supports two instructions, call and jmpl, for
linking to subroutines
• The address of instruction which called the subroutine is stored in %o7
• The return from subroutine is to %o7 + 8, which is the address of the next
instruction to be executed in the main program
• If a save instruction is executed at the beginning of the subroutine, the
contents of %o7 will become %i7, and the return will have to be to %i7 + 8
(contd…)
Subroutine Linkage contd…
• call instruction
• If the subroutine name is known at assembly time, the call instruction
may be used
• call instruction has a target address label
• It stores %pc contents to %o7
• always followed by a delay slot instruction
jmpl instruction
•
If address of the subroutine is computed, it must be loaded into a
register, and then jmpl instruction is used to call the subroutine
• jmpl instruction has two source arguments (two registers or a register
and a constant), and a destination register
• subroutine address is the sum of the source arguments, and the address
of the jmpl instruction is stored in the destination register
• always followed by a delay slot instruction
• to call a subroutine whose address is in register %o0 and to store the
return address into %o7, we would write:
jmpl %o0, %o7
18
Subroutine Linkage contd…
• The assembler recognizes
call
%o0
jmpl
%o0, %07
as
• The return from a subroutine also makes use of the jmpl instruction
• We need to return to %i7 + 8
• Assembler recognizes ret for:
jmpl
%i7 + 8, %g0
Subroutine Linkage contd…
• The call to subroutine is:
call
subr
nop
• And at the entry of the subroutine
subr:
save
%sp, … %sp
with the return
ret
restore
• The restore instruction is normally used to fill the delay slot of the ret
instruction
The ret is expanded to: jmpl
%i7 + 8, %g0
restore
7.5
Arguments to Subroutines
• Arguments to subroutines can follow in-line after the call
instruction, be on the stack, or located in registers
• If the addresses and the values of the arguments are known at the
assembly time (e.g. 3 and 4) then we can write :
call add
nop
3
4
(contd… on next slide)
(contd.. from the prev. slide)
• The following subroutine code results:
add:
save
%sp, -64, %sp
ld
[%i7 + 8], %i0 !first argument
ld
[%i7 +12], %i1 !second argument
add
%i1, %i0, %i0
jmpl
%i7 + 16, %g0 !return address
restore
• This type of argument passing is very efficient, but limited
• Recursive calls are not possible, nor is it possible to compute
any of the arguments
Using Stack
• Each argument should be stored before the subroutine may be called
• But allows flexibility to compute arguments, pass any number of
arguments, and support recursive calls
• Time is wasted to store the arguments on stack and retrieve them at the
time of computation
In SPARC:
• allows first six arguments to be placed in %o0-%05, the rest on the
stack, however, space is reserved on the stack for the first six also
• One word space reserved for each argument, so bytes must be moved
as words
• %o6 is sp and %07 is for return address
•After the execution of a save instruction, the arguments will be in %o0%05
• The arguments are located on the stack, after the 64 bytes
reserved for register window saving
• On the stack, immediately after 64 bytes reserved for register
window saving, there is a pointer to where a structure may be
returned (discussed in Section 7.7)
• Thus structure return pointer will be at %sp + 64 and the first
argument, if it were on the stack, at %sp + 68
• Before arguments may be placed onto the stack, space on the
stack must be provided by subtracting the number of bytes
required for arguments from the stack pointer
The space is created when we execute the save instruction on subroutine
entry
.global subroutine_name
subroutine_name:
save
%sp, -(64 + 4 + 24 + local) & -8, %sp
This save instruction will provide:
• Space for saving the register window set, if necessary
• A structure pointer
• A place to save six arguments
• Space for any local variable
(contd…)
• If we had a subroutine vector with local variables
vector()
{
int a,b;
char d;
• Then save instruction would be
save
%sp, -(64 + 4 + 24 + 9) & -8, %sp
Resulting in subtraction of 104 bytes (Figure 7.4)
Figure 7.4: The stack part I
(figure contd… on next slide)
27
(Figure 7.4 contd… from the prev. slide)
Figure 7.4: The stack part II
28
The stack is shown again in the figure below to differentiate
the frames referenced by %fp and %sp.
Figure 7.5: The stack showing Two Frames part I
(Figure continues on
29
next slide…)
(Figure contd… from the prev. slide…)
Figure 7.5: The stack showing Two Frames part II
30
31
we might define a subroutine entry macro, begin-fn, to be called after the
definition of local variables with the name of the subroutine as argument:
32
7.6 Examples
33
The example’s translation into assembly languages is:
(code contd… on next slide)
34
Code contd… from the prev. slide
sth
%o0, [%o1 + %o2]
Id
[%fp + x_s] , %o0 ‘!y = x*a’
call .mul
mov
%a_r, %o1
st
%o0, [%fp + y_s]
ld
Add
[%fp + x_s], %o0
%i_r, %o0, %j_r
‘!j = x+i’
ld
[%fp + x_s], %o0
‘!return = x+y’
ld
[%fp + y_s], %o1
ret
Restore %o0, %o1, %o0
35
The code expands into:
‘!a_r in %i0
‘!b_r in %i1
‘!c_r in %i2
!local variables
x_s = -4
y_s = -8
ary_s = -264
‘! i_r in %l0
‘!j_r in %l1
36
(contd…. on next slide)
(contd…)
37
(contd… from the prev. slide)
38
7.7
Return Values
• Functions are subroutines which return a value
• In SPARC, the return value is always returned in register %o0, i.e. %i0 of
called program
• We have to put the return value in %i0 before executing restore instruction
40
The function zero returns a structure.
When call is made to zero, a pointer to where the returned struct
is to be stored is passed to the function at %sp + 64.
(contd…on next slide)
41
42
•Thus returning structure in this manner is a little
dangerous. (due to insufficient size)
• This type of errors are hard to debug
• The other method is :
–The caller, passes a pointer to the beginning of the storage
in %sp + struct_s and place number of bytes of storage
expected to be received. For example:
43
44
7.8
Subroutines with many arguments
45
46
The stack when foo has been entered is shown in Figure 7.6. Inside foo
the arguments may be accessed by
define(a8-s, arg-d(8))
define(a7-s, arg-d(7))
47
7.9
Leaf Subroutines
• A leaf routine is one that does not call any other routines (e.g.
.mul)
• Leaf routine may only use the first six out register and the global
register %g0 and %g1
• A leaf subroutine does not execute either call or restore
instruction
%fp ->
Figure 7.6: The Stack with additional Arguments Part I
(Figure contd… on next slide)
49
(Figure contd…from the prev. slide)
Figure 7.6: The Stack with additional Arguments Part II
50
51
7.10
Pointers as Arguments to Subroutines
Given the swap function, arguments must be passed to the
function in order for the values to be swapped:
52
53
7.11
Summary
• Subroutines simplify writing code, provide structures, and help to
control programming errors.
• In the case of closed subroutines, register-saving mechanism facilitates
subroutine linkages.
• Stack frame introduced as storage for registers, arguments, local
variables, and the return address.
• Return of scalars and structures, and passing of arguments discussed.
55