Subroutines, Part 2
CSE 262, Spring 2003
© G. Drew Kessler and William M.
Pottenger
1
Activation Records and Instances
An activation record is the data used by the subroutine
while it is active that is not the subroutine’s code
An activation record instance is the data for a
particular call to a subroutine
An activation record typically contains, at least:
 Local variable storage
 Parameter storage
 Return address
© G. Drew Kessler and William M. Pottenger
2
Languages with Static Local Variables
(that do not support recursion)
For static variable languages, there is only one
activation record instance per subroutine.
Can be organized at compile time and allocation at
load time.
Main
Data
A
B
Code
Main
A
B
Local variables
Local variables
Parameters
Return address
Local variables
Parameters
Return address
© G. Drew Kessler and William M. Pottenger
Procedure A(int x, real y)
...
end
Procedure B(int a)
real z = 5.0
A(a, 5.0)
end
Main
int n = 6
B(n)
end
3
Using the Stack for Stack-Dynamic
Local Variables
For Stack-Dynamic Local Variables, need a new
activation record instance for each time a subroutine is
called.
 Allows recursion
Procedure A(int x, real y)
 Use run-time stack
...
B
A
B
B
Main Main Main Main Main
Call Sequence
© G. Drew Kessler and William M. Pottenger
end
Procedure B(int a)
real z = 5.0
A(a, 5.0)
end
Main
int n = 6
B(n)
end
4
Activation Record (AR) for StackDynamic Variables
Local variables
Stack
built
upward
Parameters
Dynamic Link
Top of previous AR
Static Link
Return Address
Memory
Addresses
Local variables
Parameters
0
Bottom of AR of
parent scope
...
Local variables and parameters are located by
(address of activation record, local_offset) pair
© G. Drew Kessler and William M. Pottenger
5
Simple Example
int n = 6
Procedure A(int x, real y)
...
end
Procedure B(int a)
real z = 5.0
A(a, 5.0)
end
Main
B(n)
end
© G. Drew Kessler and William M. Pottenger
A
B
Main
x
y
ret
z
a
ret
n
Dynamic
Static
Dynamic
Static
6
Nested Subroutine Example
int y
Procedure A()
int x, y
procedure B(real z)
int x
begin
y = 6
end
procedure C(real y)
begin
B(y)
x = 4
end
Begin
A()
end
Begin
C(2.0)
end
© G. Drew Kessler and William M. Pottenger
7
Example with Recursion
Procedure Merge(int A[], int L, int M, int R)
/* Merge L to M with M+1 to R ranges of A
*/
end
Procedure MergeSort(int A[], int L, int R)
int M = L+R/2
if (L<R)
MergeSort(A, L, M)
MergeSort(A, M+1, R)
Merge(A, L, M, R)
end
end
Main
Num[5] = {4, 5, 2, 1, 3}
MergeSort(Num, 0, 4)
© G.end
Drew Kessler and William M. Pottenger
8
Referencing Environments in
Statically Scoped Languages
© G. Drew Kessler and William M. Pottenger
9
Non-local Variables, Statically Scoped
How to find non-local variable using static scoping
 Static Chain or Displays
Static Chain
 Use static link in AR
 Determine distance to AR of parent scope at
compile time
 Calculate static_depth for each subroutine
 Calculate nesting_depth from caller to callee’s
parent scope
 Static link is this number of hops along static
chain from caller
© G. Drew Kessler and William M. Pottenger
10
Tracking Referencing Environments
using a Display
Displays less common in modern architectures
Essentially a collection of static links stored in an array
© G. Drew Kessler and William M. Pottenger
11
Dynamic Scoping - Deep Access
(Not the same as deep binding!)
Follow the dynamic links until variable is found
int y, n
Procedure A
int x
x = n
end
Procedure B
int x = 2
int n = 4
A()
y = x
end
Main
n = 5
y = 3
B(n)
end
A
B
Main
x
ret
x
n
ret
y
n
Dynamic
Dynamic
If run-time stack is tall, may be very slow
© G. Drew Kessler and William M. Pottenger
12
Dynamic Scoping - Shallow Access
Provides same semantics as deep access
One method: maintain stack for each variable name
(separate from AR’s)
int y, n
Procedure A
int x
x = n
end
Procedure B
int x = 2
int n = 4
A()
y = x
end
Main
n = 5
y = 3
B(n)
end
© G. Drew Kessler and William M. Pottenger
B
Main Main
y
n
A
B
x
Costly to enter and exit
subprograms due to
stack maintenance
13
The Binding of
Referencing Environments
Recall that the referencing environment of a
statement or expression is the set of active bindings
during execution
When a procedure is passed as an argument, the
referencing environment and the procedure itself
are packaged together and called a closure
If a language supports passing subroutines as
parameters, should the referencing environment be
the one in which the subroutine is passed or the
environment in which it is finally executed?
© G. Drew Kessler and William M. Pottenger
14
 Morgan Kaufmann (Figure
reproduced by permission of
author/publisher)
© G. Drew Kessler and William M. Pottenger
15
Shallow vs. Deep Binding
Shallow binding refers to when the (non-local)
referencing environment of a procedure instance is
the referencing environment in force at the time the
procedure is invoked (i.e., the one in which the
procedure is invoked)
Deep binding refers to when the (non-local)
referencing environment of a procedure instance is
the referencing environment in force at the time the
procedure's declaration is elaborated (i.e., the one in
which the procedure was passed as an argument)
 It’s as if the procedure were called in the caller
Both of these binding methods can be applied using
either static or dynamic scope rules
© G. Drew Kessler and William M. Pottenger
16
Notes on Subroutine Bindings
The difference between deep and shallow
binding is not apparent unless you pass
procedures as parameters
The difference will only be noticeable for nonlocal references, that is, references which are
neither local nor global
 E.g., binding rules aren’t relevant in
languages such as C which have no nested
subroutines
To the best of our knowledge, no language
with static scope rules has shallow binding
© G. Drew Kessler and William M. Pottenger
17
General Overview: Making the Call
The steps followed when calling and returning from a
subroutine is knows as subprogram linkage
Steps needed when calling a subroutine:
 Allocate memory for parameters as needed
 Copy values to pass-by-value and pass-by-valueresult parameters
 Allocate memory for non-static local variables
 Save execution status of calling program
 Provide “return address”
 Set up mechanism for non-local variable access
 Transfer control to subroutine code
© G. Drew Kessler and William M. Pottenger
18
General Overview:
Handling the Return
Steps need on the return from a subroutine:
 Copy values for pass-by-result and pass-by-valueresult parameters
 Deallocate storage for called subroutine local
variables, parameters, and run-time system info
 Restore state of calling subroutine, introducing
result of called subroutine, if applicable
 Restore mechanism for accessing non-local
variables from calling subroutine
 Return control to calling subroutine
© G. Drew Kessler and William M. Pottenger
19
Memory Stacks
Useful for stacked environments/subroutine call & return even if
operand stack not part of architecture
Stacks that Grow Down vs. Stacks that Grow Up:
Inf. Big
Inf. Big
up
Memory
Addresses
a
b
c
grows
down
grows
up
down
0 Little
0 Little
$sp
Grows Down
Grows Up
PUSH: Decrement $sp
Store to offset($sp)
PUSH: Increment $sp
Store to offset($sp)
POP:
POP: Load from offset($sp)
Decrement $sp
Load from offset($sp)
Increment $sp
Portions UCB Fall 1997 Dave Patterson
© G. Drew Kessler and William M. Pottenger
20
MIPS: Software conventions for Registers
0
zero constant 0
16
1
at
reserved for assembler
. . . (caller can clobber)
2
v0
expression evaluation &
23
s7
3
v1
function results
24
t8
4
a0
arguments
25
t9
5
a1
26
k0 reserved for OS kernel
6
a2
27
k1
7
a3
28
gp Pointer to global area
8
t0
temporary: caller saves
29
sp
Stack pointer
(callee can clobber)
30
fp
frame pointer
31
ra
Return Address (HW)
...
15
t7
s0
callee saves
temporary (cont’d)
UCB Fall 1997 Dave Patterson
© G. Drew Kessler and William M. Pottenger
21
Call-Return Linkage: MIPS Stack Frame
‘Extra’ Args
High Mem
$fp
Saved Registers
Callee preserves
caller’s $ra, $sp,
$fp, $gp, $s0-$s7
as necessary
Stack
grows
down
Local Variables
Low Mem
Reference args and
local variables at
fixed offset from $fp
$sp grows and shrinks
during expression eval
$sp
° Block structured languages contain link to lexically enclosing frame
° Compilers normally keep scalar variables in registers, not memory!
° Note that $sp = $sp - frame size; $fp = $sp + (frame size - 4)
- gcc initializes $fp to $sp at procedure entry: what is sign of the gcc offset?
° Some compilers don’t use $fp as frame pointer - can you think how (why)?
Portions UCB Fall 1997 Dave Patterson
© G. Drew Kessler and William M. Pottenger
22
Procedure Call Case Study
•
•
•
•
•
•
put parameters in $a0-$a3++ and on stack
jal procedure
allocate local storage needed by procedure
execute procedure code
put results in $v0/$v1 (plus on ‘heap’)
jr $ra
© G. Drew Kessler and William M. Pottenger
23
Procedure Call: Details
• Caller:
– Pass args in registers $a0-$a3. Additional args
may be passed in other registers or on stack
– Save caller-saved registers ($a0-$a3 and $t0$t9)
– Execute jal to callee’s first instruction: this
saves caller’s return address in $ra
© G. Drew Kessler and William M. Pottenger
24
Procedure Call: Details
Callee (prior to execution):
 Allocate ‘local’ stack memory needed to store local
variables, save registers, etc.
 $sp = $sp - size of stack frame
 Save callee-saved registers (e.g., $s0-$s7, $fp,
$ra)
 Establish frame pointer
 $fp = $sp + (size of stack frame - 4)
© G. Drew Kessler and William M. Pottenger
25
Procedure Call: Details
• Callee return (after execution):
– If return value, place in $v0/$v1
– Restore all callee-saved registers (e.g., $fp, $ra)
– Restore $sp to original value
• $sp = $sp + size of callee stack frame
– Return control to caller
• jr $ra
© G. Drew Kessler and William M. Pottenger
26
$fp
$sp
$ra
Saving $ra and
$fp during
procedure call
high
address
$fp
$sp
$ra
low
address
$fp
$sp
$ra
$fp
Portions UCB Fall 1997 Dave Patterson
© G. Drew Kessler and William M. Pottenger
27
Descargar

Subroutines, Part 2