Transcript Document

Course Overview
PART I: overview material
1
2
3
Introduction
Language processors (tombstone diagrams, bootstrapping)
Architecture of a compiler
PART II: inside a compiler
4
5
6
7
Syntax analysis
Contextual analysis
Runtime organization
Code generation
PART III: conclusion
8
9
Interpretation
Review
Runtime Organization (Chapter 6)
1
Routines
• Data Representation: how to represent values of the source
language on the target machine
• Expression Evaluation: How to organize computing the values of
expressions (taking care of intermediate results)
• Stack Storage Allocation: How to organize storage for variables
(considering lifetimes of global and local variables)
• Routines: How to implement procedures, functions (and how to
pass their parameters and return values)
• Heap Storage Allocation: How to organize storage for variables
(considering lifetimes of heap variables)
• Object Orientation: Runtime organization for OO languages
(how to handle classes, objects, methods)
Runtime Organization (Chapter 6)
2
Routines
We call the assembly language equivalent of procedures “routines”.
In the preceding material we already learned some things about the
implementation of routines in terms of the stack allocation model:
• Addressing locals and globals through LB, L1, L2, …, and SB
• Link data: static link, dynamic link, and return address
We have yet to learn how the static link and the L1, L2, etc. registers
are set up.
We have yet to learn how a routine can receive argument values from
its caller, and return results to its caller.
Runtime Organization (Chapter 6)
3
Routines
We call the assembly language equivalent of procedures “routines”.
What are routines? Unlike procedures/functions in higher level
languages, they are not directly supported by language constructs.
Instead they are modeled in terms of how to use the low-level
machine to “emulate” procedures.
What behavior needs to be “emulated”?
• Calling a routine and returning to the caller after completion
• Passing arguments to a called routine
• Returning a result from a routine
• Accessing local and non-local variables
Runtime Organization (Chapter 6)
4
Routines
• Transferring control to and from a routine:
Most low-level processors have CALL and RET instructions
for transferring control from caller to callee and back.
• Transmitting arguments and return values:
Caller and callee must agree on a method to transfer argument
and return values.
=> This is called the “routine protocol”
!
There are many possible ways to pass argument and return
values.
=> A routine protocol is like a “contract” between the caller
and the callee.
The routine protocol is often dictated by the operating system.
Runtime Organization (Chapter 6)
5
Routine Protocol Examples
The routine protocol depends on the machine architecture (e.g. stack
machine versus register machine).
Example 1: A possible routine protocol for a RM
- Passing of arguments:
first argument in R1, second argument in R2, etc.
- Passing of return value:
return the result (if any) in R0
Note: this example is simplistic:
- What if more arguments than registers?
- What if the representation of an argument is larger than can be
stored in a register?
For RM protocols, the protocol usually also specifies who (caller or
callee) is responsible for saving the previous contents of registers.
Runtime Organization (Chapter 6)
6
Routine Protocol Examples
Example 2: A possible routine protocol for a stack machine
- Passing of arguments:
pass arguments on the top of the stack.
- Passing of return value:
leave the return value on the stack top, in place of the
arguments.
Note: this protocol puts no boundary on the number of arguments
and the size of the arguments.
Most micro-processors have registers as well as a stack. Such
“mixed” machines also often use a protocol like this one.
The “Triangle Abstract Machine” also adopts this routine protocol.
We now look at it in detail (in TAM).
Runtime Organization (Chapter 6)
7
TAM: Routine Protocol
just before the call
SB
just after return
SB
globals
LB
globals
LB
args
ST
result
ST
What happens in between call and return?
Runtime Organization (Chapter 6)
8
TAM: Routine Protocol
(1) just before the call
(2) just after entry
LB
args
ST
LB
args
link data
ST
Note: Going from (1) to (2) in TAM is the execution of a single
CALL instruction.
Runtime Organization (Chapter 6)
9
TAM: Routine Protocol
(2) just after entry
LB
args
(3) during execution of routine
LB
link data
link data
ST
ST
Runtime Organization (Chapter 6)
args
local
data
shrinks
and grows
during
execution
(enter/exit
blocks,
push/pop
temporary
values)
10
TAM: Routine Protocol
(4) just before return
(5) just after return
LB
LB
args
ST
result
link data
ST
local
data
result
Note: Going from (4) to (5) in TAM is the execution of a single
RET instruction.
Runtime Organization (Chapter 6)
11
TAM: Routine Protocol, Example
Example Triangle Program
let var g: Integer;
func F(m: Integer, n: Integer) : Integer ~
m*n ;
proc W(i:Integer) ~
let const s ~ i*i
in begin
putint(F(i,s));
putint(F(s,s))
end
in begin
getint(var g);
W(g+1)
end
Runtime Organization (Chapter 6)
12
TAM: Routine Protocol, Example
let var g: Integer;
...
in begin
getint(var g);
W(g+1)
end
TAM assembly code:
PUSH
1
for g
LOADA
0[SB]
CALL
getint
LOAD
0[SB]
CALL
succ
CALL(SB) W
link)
Runtime Organization (Chapter 6)
-- expand globals to make place
-- push address of g (pass-by-ref)
-- read integer into g
-- push value of g
-- add 1
-- call W (using SB as static
13
TAM: Routine Protocol, Example
func F(m: Integer, n: Integer) : Integer ~
m*n ;
F: LOAD
LOAD
CALL
RETURN(1)
-2[LB] -- push value of argument m
-1[LB] -- push value of argument n
mult
-- multiply m and n
2
-- return, replacing 2-word
argument pair by 1-word result
Arguments are
addressed relative to
LB (note the negative
offsets!)
Runtime Organization (Chapter 6)
Size of return value and argument
space needed for updating the stack
upon return from call.
14
TAM: Routine Protocol, Example
proc W(i: Integer) ~
let const s~i*i
in ... F(i,s) ...
W: LOAD
LOAD
CALL
LOAD
LOAD
CALL(SB)
…
RETURN(0)
-1[LB]
-1[LB]
mult
-1[LB]
3[LB]
F
-- push value of argument i
-- push value of argument i
-- multiply: result is value of s (3[LB])
-- push value of argument i
-- push value of local variable s
-- call F (using SB as static link)
1
-- return, replacing 1-word
argument by 0-word result
Runtime Organization (Chapter 6)
15
TAM: Routine Protocol, Example
let var g: Integer;
...
in begin
getint(var g);
W(g+1)
end
after reading g
SB
g 3
ST
Runtime Organization (Chapter 6)
just before call to W
SB
g 3
ST
arg #1
4
16
TAM: Routine Protocol, Example
proc W(i: Integer) ~
let const s~i*i
in ... F(i,s) ...
just after entering W
just after computing s
just before calling F
SB
SB
SB
LB
ST
g
arg #1
3
4
link
data
g
3
arg i 4
LB
link
data
16
ST
g
3
arg i 4
LB
link
data
s 16
arg #1 4
arg #2 16
ST
static link
dynamic link
Runtime Organization (Chapter 6)
17
TAM: Routine Protocol, Example
func F(m: Integer, n: Integer) : Integer ~
m*n ;
just before calling F
just after entering F
SB
SB
g
3
arg i 4
LB
link
data
s 16
arg #1 4
arg #2 16
ST
arg i
LB
ST
Runtime Organization (Chapter 6)
g
s
arg m
arg n
3
4
link
data
16
4
16
link
data
just before return
from F
SB
g 3
arg i
4
link
data
s 16
arg m 4
arg n 16
LB
link
data
64
ST
18
TAM: Routine Protocol, Example
func F(m: Integer, n: Integer) : Integer ~
m*n ;
just before return
from F
SB
g 3
arg i
4
link
data
s 16
arg m 4
arg n 16
LB
link
data
64
SB
LB
ST
after return
from F
g 3
arg i
4
link
data
s 16
64
…
ST
Runtime Organization (Chapter 6)
19
TAM Routine Protocol: Frame Layout Summary
arguments
LB
ST
dynamic link
static link
return address
local variables
and intermediate
results
Runtime Organization (Chapter 6)
Arguments for current procedure.
They were put here by the caller.
Link data
Local data, grows and shrinks
during execution.
20
Accessing variables, addressing schemas (revised)
We now have a complete picture of the different kinds of addresses
that are used for accessing variables and formal parameters stored
on the stack.
Type of variable
Load instruction
Global
LOAD +offset[SB]
Local
LOAD +offset[LB]
Parameter
LOAD -offset[LB]
Non-local, 1 level up
LOAD +offset[L1]
Non-local, 2 levels up
LOAD +offset[L2]
Runtime Organization (Chapter 6)
21
Static Links
We have already seen somewhat how the static link in the call frame is
initialized by a parameter of the CALL instruction.
But how can the compiler determine this parameter at compile time?
To understand this we need to know a few things about the Triangle
programming language.
• Statically scoped, block-structured language.
• The static link points to the scope where the function was
defined.
• If there are no higher-order funcs or procs, the compiler always
knows which func/proc is being called. That func/proc must be
defined somewhere within the active scope.
So the static link can always be found in one of the display registers!
Runtime Organization (Chapter 6)
22
Static Links
The static link can always be found in one of the display registers:
let proc P( ) ~
let proc Q( ) ~
let proc Q1
proc Q2
in Qbody
proc S( ) ~
let proc S1
proc S2
in Sbody
in Pbody
in ...Main Program...
Call
from
to
Q1body
Q2body
Main
P
S1body
S2body
S
S2
Runtime Organization (Chapter 6)
P
Q
S
P
S1
S2
Q
S
S1
S
P
Static link?
SB
LB
LB
SB
LB
LB
L1
L1
L1
L2
SB
23
Arguments
We have already discussed how space on the stack is
allocated for arguments to routines.
We now discuss some specific issues about
• passing by value versus passing by reference
• passing of functional and procedural parameters
Runtime Organization (Chapter 6)
24
Arguments: by value or by reference
Some programming languages allow two kinds of
parameter passing to functions/procedures.
Example: in Triangle (similar in Pascal or C++)
Var/reference parameter
Constant/value parameter
let proc S(var n:Integer, i:Integer) ~
n:=n+i;
var today: record
y:integer, m:Integer, d:Integer
end;
in begin
b := {y ~ 2002, m ~ 2, d ~ 22}; ! b is non-local
S(var b.m, 6);
end
Runtime Organization (Chapter 6)
25
Arguments: by value or by reference
Value parameters:
At the call site the argument is an expression. The evaluation of that
expression leaves some value on the stack. This value is passed to the
procedure/function.
Typical instructions for putting a value parameter on the stack:
LOADL 6
LOAD 3[L1]
Var/reference parameters:
Instead of passing a value on the stack, the address of a memory location is
pushed. This implies a restriction that only “variable-like” things can be
passed to a var parameter. In Triangle there is an explicit keyword var at
the call-site, to signal passing a var parameter. In Pascal and C++ the
reference is created implicitly (but the same restrictions apply).
Typical instructions for putting a var parameter on the stack:
LOADA 5[LB]
LOADA 10[SB]
Runtime Organization (Chapter 6)
26