COMPILER CONSTRUCTION
Principles and Practice
Kenneth C,Louden
7,Runtime Environments
PART ONE
Contents
Part One
7.1 Memory Organization During Program Execution
7.2 Fully Static Runtime Environments
7.3 Stack-Based Runtime Environments
Part Two
7.4 Dynamic Memory
7.5 Parameter Passing Mechanisms
7.6 A Runtime Environment for the TINY Language
The precious chapters studied the phases of a
compiler that perform static analysis of the
source language
– Scanning,parsing,and static semantic analysis
– Depends only on the properties of the source
language
This chapter and the next turn to the task of
studying how a compiler generates executable
code
– Additional analysis,such as that performed by an
optimizer
– Some of this can be machine independent,but much of
the task of code generation is dependent on the details
of the target machine
Runtime Environment
The structure of the target computer’s registers
and memory that serves to manage memory and
maintain the information needed to guide the
execution process
Three kinds of runtime environments
(1) Fully static environment; FORTRAN77
(2) Stack-Based environment; C C++
(3) Fully dynamic environment; LISP
Main issues will be discussed in more detail in the
chapter,
– For each environment,the language features and their
properties
(1) Scoping and allocation issues;
(2) Nature of procedure calls;
(3) Parameter passing mechanisms
Focus on the general structure of the environment
Note:
– The compiler can only maintain an environment only
indirectly
– It must generate code to perform the necessary
maintenance operations during program execution.
7.1 Memory Organization During
Program Execution
The memor y of a t y pic a l c omput e r,
A r e g ist e r a r e a ;
Addr e ssable R a ndom a c c e ss m e mor y ( R AM),
A c ode a r e a ;
A da ta a re a,
The c ode a re a is fix e d pr ior to e x e c uti on,a nd c a n be visuali z e d a s
follows,
Entr y poi nt er t o pr ocedur e1 → C ode f or pr oced ur e 1
Entr y poi nt er t o pr ocedur e2 → C ode f or pr oced ur e 2
…
Entr y poi nt er t o pr ocedur e n → C ode f or pr oced ur e n
I n p a rticula r,th e e ntr y po int for e a c h p roc e du re a n d func ti on is known a t
c ompi le tim e,
The global and/or static data of a program can be
fixed in memory prior to execution
– Data are allocated separately in a fixed area in a similar
fashion to the code
In Fortran77,all data are in this class;
In Pascal,global variables are in this class;
In C,the external and static variables are in this class
The constants are usually allocated memory in
the global/static area
– Const declarations of C and Pascal;
– Literal values used in the code,
such as,Hello%D\n” and Integer value 12345:
Printf(“Hello %d\n”,12345);
The memory area used for dynamic data can be
organized in many different ways
– Typically,this memory can be divided into a stack area
and a heap area;
A stack area used for data whose allocation occurs in FIFO
fashion;
A heap area used for dynamic allocation occurs not in FIFO
fashion.
Generally,the architecture of the target machine
includes a processor stack for procedure calls and
returns.
– Sometimes,a compiler will have to arrange for the
explicit allocation of the processor stack in an
appropriate place in memory.
T h e ge n e r al organi z at io n of r u n tim e stor age,
C ode a re a
Globa l/ static a re a
S tac k
↓
F re e spac e
↑
He a p
W he re,the a rr o ws indi c a te the dire c ti on of g row th of the stac k
a nd he a p,
Pr oc e d u r e ac tivat ion r e c o r d (A n im p or t an t u n it o f m e m o r y
all oc at ion )
Memor y a ll oc a ted for the loca l data of a proc e dure or f unc ti on,
An a c ti va ti on re c or d mus t conta ins t he f oll owing s e c ti ons,
S pa c e f or a r g uments
( pa ra m e ter s )
S pa c e f or bookk e e pin g
info rma ti on,including r e turn
a ddre ss
S pa c e f or lo c a l data
S pa c e f or lo c a l t e mpora ri e s
Note,thi s pictur e onl y il lust ra t e s the g e n e r a l or ga niz a ti on of a n
a c ti va ti on re c o rd,
Some parts of an activation record have the same size for
all procedures
– Space for bookkeeping information
Other parts of an activation record may remain fixed for
each individual procedure
– Space for arguments and local data
Some parts of activation record may be allocated
automatically on procedure calls:
– Storing the return address
Other parts of activation record may need to be allocated
explicitly by instructions generated by the compiler:
– Local temporary space
Depending on the language,activation records may be
allocated in different areas:
– Fortran77 in the static area;
– C and Pascal in the stack area; referred to as stack frames
– LISP in the heap area.
Processor registers are also part of the
structure of the runtime environment
– Registers may be used to store temporaries,local
variables,or even global variables;
– In newer RISC processor,keep entire static area and
whole activation records;
– Special-purpose registers to keep track of execution
PC program counter;
SP stack pointer;
FP frame pointer;
AP argument pointer
The sequence of operations when calling the
functions,calling sequence
– The allocation of memory for the activation record;
– The computation and storing of the arguments;
– The storing and setting of necessary registers to affect
the call
The additional operations when a procedure or
function returns,return sequence (VS call)
– The placing of the return value where the caller can
access it;
– The readjustment of registers;
– The possible releasing for activation record memory
The important aspects of the design of the
calling sequence:
(1) How to divide the calling sequence
operations between the caller and callee
At a minimum,the caller is responsible for
computing the arguments and placing them in
locations where they may be found by the callee
(2) To what extent to rely on processor support
for calls rather that generating explicit code
for each step of the calling sequence
7.2 Fully Static Runtime
Environments
T h e e n tir e p r ogr a m m e m or y c an b e visu ali z e d as
f oll o w s,
C od e f or m ai n pr ocedur e
C od e f or pr oce dur e 1
…
C od e f or pr oce dur e n
C od e ar ea
G l obal data ar ea
A ct i vat i on r e cord o f m ai n
pr ocedur e
A ct i vat i on r ecor d o f
pr ocedur e 1
…
A ct i vat i on r ecor d o f
pr ocedur e n
D at a ar ea
All data are static,remaining fixed in memory for
the duration of program execution
For a language,such as FORTRAN77,no pointer
or dynamic allocation,no recursive procedure
calling
– The global variables and all variables are allocated
statically.
– Each procedure has only a single activation record.
– All variable,whether local or global,can be accessed
directly via fixed address.
Relative little overhead in terms of bookkeeping
information to retain in each activation record;
And no extra information about the environment
needs to be kept in an activation record;
The calling sequence is simple.
– Each argument is computed and stored into its
appropriate parameter location;
– The return address is saved,and jump to the beginning
of the code of the callee;
– On return,a simple jump is made to the return address.
Example,A FORTRAN77 sample program
PROGRAM TEST
COMMON MAXSIZE
INTEGER MAXSIZE
REAL TABLE(10),TEMP
MAXSIZE = 10
READ *,TABLE(1),TABLE(2),TABLE(3)
CALL QUADMEAN(TABLE,3,TEMP)
PRINT *,TEMP
END
SUBROUTINE QUADMEAN(A,SIZE,QMEAN)
COMMON MAXSIZE
INTEGER MAXSIZE,SIZE
REAL A(SIZE),QMEAN,TEMP
INTEGER K
TEMP=0.0
IF ((SIZE,GT,MAXSIZE),OR,(SIZE,LT,1) GOTO 99
DO 10 K=1,SIZE
TEMP=TEMP+A(K)*A(K)
10 CONTINUE
99 QMEAN = SQRT(TEMP/SIZE)
RETURN
END
A r u n ti m e e n vir on m e n t f or t h e p r ogr a m ab ove,
G l obal ar ea MA X SIZ E
T A B L E ( 1)
( 2)
…
( 10)
T E MP
A ct i vat i on r ec ord of m ai n
pr ocedur e
3
A
SI Z E
Q ME A N
R et u rn a ddr es s
T E MP
K
A ct i vat i on r ecord o f
pr ocedur e Q U A D M E A N
U n nam ed l ocat i on
N ot e,T h e u n n am e d locat ion is u se d to stor e te m p or ar y valu e
d u r in g the c om p u tat ion of ar ithm e ti c e xp r e ssi on,
7.3 Stack-Based Runtime
Environments
For a language,in which
– Recursive calls are allowed;
– Local variables are newly allocated at each call;
– Activation records cannot be allocated statically
Activation records must be allocated in a stack-
based fashion
– The stack of activation records grows and shrinks with
the chain of calls in the executing program.
– Each procedure may have several different activation
records on the call stack at one time,each
representing a distinct call.
– More complex strategy for bookkeeping and
variable access,which depends heavily on the
properties of the language being compiled.
7.3.1 Stack-Based Environments
Without Local Procedures
In a language where all properties are global (such
as C language),the stack-based environment
requires two things:
(1) Frame pointer or fp,a pointer to the current
activation record to allow access to local
variable; Control link or dynamic link,a
point to a record of the immediately preceding
activation
(2) Stack pointer or sp,a point to the last
location allocated on the call stack
Example,The simple recursive implementation of
Euclid’s algorithm to compute the greatest common divisor
of two non-negative integer
# include <stdio.h>
int x,y;
int gcd(int u,int v)
{ if (v==0) return u;
else return gcd(v,u%v);
}
main()
{scanf(“%d%d”,&x,&y);
printf(“%d\n”,gcd(x,y));
return 0;
}
Suppose the user inputs the values 15 and 10 to this program,
T h e e n vir on m e n t du r in g the t h ird call,
X,15
Y,10
G l obal / st at i c ar ea
A ct i vat i on r ec ord o f m ai n
U,15
V,10
C o ntr ol l i n k
R et ur n ad dr es s
A ct i vat i on r ec ord o f
Fir st cal l t o gcd
U,10
V,5
C ontr ol l i nk
R et ur n ad dr es s
A ct i vat i on r ec ord o f
Secon d cal l t o gc d
U,5
V,0
C o ntr ol l i n k
R et ur n ad dr es s
A ct i vat i on r ec ord o f
T hi rd c al l t o gcd
Fr ee s pac e D i r ect i on o f
S t ack gr ow t h
Af te r the f in al c all to g c d,e ac h of the ac tivat i on s is r e m ove d in turn
f r om the st ac k,
Fp
sp
Example,Int x=2;
Void g(int);/*prototype*/
Void f(int n)
{static int x=1;
g(n);
x--;
}
void g(int m)
{int y=m-1;
if (y>0)
{ f(y);
x--;
g(y);
}
}
main( )
{g(x);
return 0;
}
(a) Run tim e e n vir on m e n t o f t h e ab ove p r ogr a m d u r in g
the se c on d c all t o g
x,2
x ( f r om f ),1
G l obal / st at i c ar ea
A ct i vat i on r ec ord o f
m ai n
M,2
C ontr ol l i nk
R et u rn a ddr es s
y,1
A ct i vat i on r ec ord o f
C al l t o g
n,1
C ontr ol l i nk
R et u rn a dd r es s
A ct i vat i on r ec ord o f
C al l t o f
m,1
C ontr ol l i nk
R et u rn a ddr es s
y,0
A ct i vat i on r ec ord o f
C al l t o g
Fr ee s pac e
fp
sp
(b) R u n tim e e n vir on m e n t of t h e ab ove p r ogr am d u r in g
the t h ird call to g
x,1
x ( f r om f ),0
G l obal / st at i c ar ea
A ct i vat i on r ec ord o f
m ai n
m,2
C ontr ol l i nk
R et u rn a ddr es s
y,1
A ct i vat i on r ec ord o f
C al l t o g
m,1
C ontr ol l i nk
R et u rn a dd r es s
y,0
A ct i vat i on r ec ord o f
C al l t o g
Fr ee s pac e
fp
sp
Ac tivat ion s tr e e,a us e ful tool fo r the a n a ly s is of c ompl e x c a ll ing
struc ture s
E xam pl e,act i vat i on tr ees f or t he pr ogr am of f i gur es 7,3 and 7.5
m ai n( )
gcd( 15,1 0)
gcd( 10,5)
gcd( 5,0)
( a)
m ai n( )
g( 2)
f ( 1) g( 1)
g( 1)
( b)
N ot e,In ge neral,t he st ack of act i vat i on r eco rds at t h e begi nni ng o f a p art i cul ar
cal l has a st r uct ur e e qui v al ent t o t he path f r om t he corr es po ndi ng nod e i n t h e
act i vat i on tr ee t o t he r o ot,
Access to Names:
– Parameters and local variable can no longer be
accessed by fixed addresses,instead they must
be found by offset from the current frame
pointer.
– In most language,the offset can be statically
computable by the compiler.
C onsi de r the proc e du re g in t he C prog r a m of F i g u re 7.5,
m
C ont r ol l i nk
R et ur n ad dr es s
y
Note,
Ea c h a c ti va ti on re c or d of g h a s e x a c tl y the sa me fo rm,a nd th e
pa ra mete r m a nd the lo c a l va ria ble y a re a lw a y s in e x a c tl y the sa me
re lative lo c a ti on in t he a c ti va ti on re c or d,
B oth m a nd y c a n b e a c c e ssed b y their f ix e d of fse t fr om t he f p,
W e ha ve mOf fs e t=+ 4 a n d y O f fse t = - 6,
The re fe r e nc e s to m a nd y c a n be wr it ten in mac hine c ode a s 4( fp) a nd
– 6( fp),
fp
m O f f se t
yO f f se t
E xam pl e 7.4 C o nsi der t he C pr oc edur e
V oi d f ( i nt x,char c)
{ i nt a[ 10] ;
double y;
…
}
T h e ac tivat ion r e c o r d f or a c all t o f w ou l d ap p e ar as
x
c
C ontr ol l i nk
R et ur n ad dr es s
a[ 9]
…
a[ 1]
a[ 0]
y
O f f se t o f x
fp O f f se t o f c
O f f se t o f a
O f f se t o f y
Assumi ng two b y tes fo r int e g e rs,four b y t e s for a ddre sses,one b y t e
for c ha ra c ter a nd e i g ht b y t e s fo r double - p re c isi on floa ti ng point,we
would ha ve the f oll owin g o f fse t value s,
N am e O f f se t
x +5
c +4
a - 24
y - 32
Now,a n a c c e ss of a [ i],would r e qu ire th e c o mput a ti on of the
a ddre ss,
( - 24+ 2*i)( fp)
The calling sequence,
– When a procedure is called
Compute the arguments and store them in their correct
positions in the new activation record of the procedure;
Store the fp as the control link in the new activation record;
Change the fp so that it points to the beginning of the new
activation record;
Store the return address in the new activation record;
Perform a jump to the code of the procedure to be called.
– When a procedure exits
Copy the fp to the sp.
Load the control link into the fp.
Perform a jump to the return address;
Change the sp to pop the arguments.
E x am p l e 7,5 C o n s i d e r t h e s i t u a t i o n j u s t b e fo re t h e l as t
cal l t o g
( r es t of st ack)
M,2
C ont r ol l i nk
R et ur n addr es s
Y,1
F r ee s pace
fp
sp
A ct i vat i on r eco rd
of c al l t o g
As the n e w c all to g is m ad e,f irst the valu e of p ar ame te r m is p u sh e d on to
the r u n tim e stac k,
( r es t of st ack)
M,2
C ont r ol l i nk
R et ur n addr es s
Y,1
M,1
F r ee s pace
fp
sp
A ct i vat i on
r ecord o f cal l
t o g
T h e n t h e f p is p u sh e d o n to t h e stac k,
( r es t of st ack )
M,2
C o ntr ol l i n k
R et ur n a ddr es s
Y,1
M,1
C o ntr ol l i n k
Fr ee s pac e
fp
sp
A ct i vat i on
r ecord o f cal l t o
g
Now,the sp is c opied in to the fp,the re turn a ddre ss is pushe d onto the
stac k,a nd the jump t o the ne w c a ll of g is m a de,
( r es t of st ack)
M,2
C ont r ol l i nk
R et ur n addr es s
Y,1
M,1
C ont r ol l i nk
r etu r n ad d r ess
F r ee s pace
fp
sp
A ct i vat i on
r ecord o f cal l t o
g
N e w act i vat i on r ecord
O f cal l t o g
F in all y,g all oc a te s an d in itial ize s the n e w y on the sta c k to c o m p let e the
c on str u c tion o f t h e n e w ac tivat ion r e c or d,
( r es t of st ack )
M,2
C o ntr ol l i n k
R et ur n a ddr es s
Y,1
M,1
C o ntr ol l i n k
r et urn a dd r ess
y,0
Fr ee s pac e
fp
sp
A ct i vat i on
r ecord o f cal l t o
g
N e w act i vat i on r eco rd
of c al l t o g
Dealing with variable-length data
– The number of arguments in a call may vary from call
to call,and
– The size of an array parameter or a local array variable
may vary from call to call
– An example of situation 1 is the printf function in C:
Printf(“%d%s%c”,n,prompt,ch)
– Has four arguments,while
Printf(“Hello,world\n”)
– Has only one argument
C compiler typically deal with this by pushing the
arguments to a call in reverse order onto the
runtime stack,The first parameter is always
located at a fixed offset from the fp in the
implementation described above
Another option is to use a processor mechanism
such as ap (argument pointer) in VAX
architecture.
An example of situation 2 is the unconstrained array of
Ada:
Type int_vector is
Array(INTEGER range <>) of INTEGER;
Procedure sum (low,high,INTEGER;
A,Int_vector) return INTEGER
Is
Temp,Int_Array (low..high);
Begin
…
end sum;
A typical method is to use an extra level of indirection
for the variable-length data,storing a pointer to the
actual data in a location that can be predicated at compile
time.
W e co u l d im p l em en t an ac t i v a t i o n rec o r d f o r SU M as f o l l o w s,
( r es t of st ack )
L ow,…
H i gh,…
A,
Si ze of A,1 0
C ont r ol l i nk
R et ur n ad dr es s
I,…
A [ 9]
…
A [ 0]
F r ee s pace
N o w,fo r ins t an ce,ac ces s t o A [i ] can b e ac h i e v e d by com p u t i n g
@6 ( fp ) +2 * i
A ct i vat i on r eco rd o f
cal l t o Sum
V ari abl e - l engt h
D at a ar ea
fp
sp
Note:
– In the implementation described in the previous
example,the caller must know the size of any
activation record of Sum
– The size of the parameter part and the bookkeeping
part is known to the compiler at the point of call
– The size of the local variable part is not,in general,
known at the point of call,Variable-length local
variables can be dealt with in a similar way
Local Temporaries and Nested Declarations:
– Two more complications to the basic stack-based
runtime environment
(1) Local temporaries are partial results of computations
that must be saved across procedure calls,for example:
x[i] = (i + j) *(i/k + f(j))
The three partial results need to be saved across
the call to f:
The address x[i];
The sum i+j;
The quotient i/k;
T h e r u n tim e sta c k m igh t app e ar as f oll o w s at t h e p oin t j u st bef or e t h e c all t o f,
( r es t of st ack )
…
cont r ol l i n k
r et urn ad dr es s
…
A ddr es s of x[ I]
R es ul t o f I+ j
R es ul t o f i / j
Fr ee s pac e
A ct i vat i on r ecord o f
pr ocedur e cont ai ni ng
t he expr es si on
S t ack of t em porari es
N e w act i vat i on r eco rd
of cal l t o f ( a bout t o
cr eat ed)
fp
sp
Nested declarations present a similar problem,Consider
the C code
Void p( int x,double y)
{ char a;
int I;
…
A:{double x;
Int j;
…
}
…
B:{char *a;
Int k;
…
}
…
}
There are two block (also called compound statement),labeled
A and B nested inside the body of procedure p.
The nested local declaration does not need to be allocated until
entered;
Both A and B do not need to be allocated simultaneously.
A s i m p l er m et h o d i s t o t rea t t h em i n a s i m i l ar w a y t o t em p o r ary
ex p res s i o n,F o r i n s t a n ce,j u s t af t er en t er i n g b l o c k A i n t h e s am p l e
C j u s t g i v e n,t h e r u n t i m e st ac k w o u l d ap p e ar as f o l l o w s,
( r es t of st ack )
X,
Y,
cont r ol l i n k
r et urn ad dr es s
a,
I,
x,
J,
Fr ee s pac e
A ct i vat i on r ecord o f
cal l t o p
A l l ocat ed ar ea f or bl o ck
A
fp
sp
A n d j u s t a ft er e n t ry to b l o ck B i t w o u l d l o o k a s f o l l o w s,
( r es t of st ack)
X,
Y,
cont r ol l i nk
r et ur n addr es s
a,
I,
a,
k,
F r ee s pace
A ct i vat i on r eco rd o f
cal l t o p
A l l ocat ed ar ea f or
bl ock B
fp
sp
7.3.2 Stack-Based Environment
with local Procedures
Consider the non-local and non-global references
Example,Pascal program showing nonlocal,nonglobal
reference
Program nonlocalRef;
Procedure P;
Var N,integer;
Procedure Q;
Begin
(* a reference to N is now non-local andnon-global *)
end; (* q*)
Procedure R(N,integer);
Begin
Q;
End;(*r *)
Begin(*p*)
N:=1;
R(2);
End ;(*p*)
Begin (* main*)
P;
End.
T h e ru n ti m e stac k fo r th e p ro g ram a b o v e,
C ontrol l ink
R e turn a ddre ss
N:1
N:2
C ontrol l ink
R e turn a ddre ss
C ontrol l ink
R e turn a ddre ss
F re e spac e
fp
sp
A ct i v at i on r ecor d of
m ai n pr ogr am
A ct i v at i on r ecor d of
C al l t o p
A ct i v at i on r ecor d of
C al l t o r
A ct i v at i on r ecor d of
C al l t o q
N cannot be found using any of the
bookkeeping information that is kept in the
runtime environment up to now
To solve the above problem about variable access,
we add an extra piece of bookkeeping information
called the access link to each activation record
Access link represents the defining environment
of the procedure;
Control link represents the calling environment of
the procedure.
The runti m e s ta ck fo r the pr o g r a m a bo v e w i t h a cce s s l i n k s
a dded,
< no a c c e ss l ink>
C ontrol l ink
R e turn a ddre ss
N:1
N:2
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
F re e spac e
fp
sp
A ct i v at i on r eco r d of
m ai n pr ogr am
A ct i v at i on r ecor d of
C al l t o p
A ct i v at i on r ecor d of
C al l t o r
A ct i v at i on r ecor d of
C al l t o q
Note,
– The activation record of procedure p itself
contains no access link,as any nonlocal
reference with p must be a global reference and
is accessed via the global reference mechanism
– This is the simplest situation,where the
nonlocal reference is to a declaration in the
next outermost scope.
Example,Pascal code demonstrating access chaining
Program chain
Procedure p;
Var x,integer;
Procedure q;
Procedure r;
Begin
X:=2;
…
if … then p;
end;(*r*)
begin
r;
end;(*q*)
begin
q;
end;(*p*)
begin(* main *)
p;
end.
In this code,the assignment to x inside r,which
refers to the x of p,must traverse two scope
levels to find x
In this environment,x must be reached by
following tow access links,a process that is called
access chaining
The runtim e st a ck afte r the f i rs t ca l l to r,
< no a c c e ss l ink>
C ontrol l ink
R e turn a ddre ss
x,1
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
F re e spac e
fp
sp
A ct i v at i on r ecor d of
m ai n pr ogr am
A ct i v at i on r ecor d of
C al l t o p
A ct i v at i on r ecor d of
C al l t o q
A ct i v at i on r ecor d of
C al l t o r
Note:
– The amount of chaining,determined by comparing
the nesting level at the point of access with one of the
declaration of the name
– In the above situation,the assignment to x is at nesting
level 3,and x is declared at the nesting level 1,so two
access links must be followed
– However,the access chaining is an inefficient method
for variable access,for each nonlocal reference with a
large nesting difference,a lengthy sequence of
instruction must be executed.
– There is a method of implementing access links in a
lookup table indexed by nesting level,called display,
to avoid the execution overhead of chaining.
The calling sequence
The changes needed to implement access links:
(1) The access link must be pushed onto the runtime stack
just before the fp during a call
(2) The sp must be adjusted by an extra amount to remove
the access link after an exit
How to find the access link of a procedure during
a call?
– Using the (compile-time) nesting level information
attached to the declaration of the procedure
– Generate an access chain as if to access a variable at
the same nesting level
– The access link and the control link are the same,
if the procedure is local
Give n the c od e of PR OG RA M CHAIN the runtim e stac k a ft e r the se c ond c a ll to r
( assuming a r e c ursi v e c a ll to p ) w ould l ook a s follows,
< no a c c e ss l ink>
c ontrol l ink
re turn a ddr e ss
x,…
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
Ac c e ss l i nk
C ontrol l ink
R e turn a ddre ss
< no a c c e ss l ink>
c ontrol l ink
re turn a ddr e ss
x,…
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
F re e spac e
A ct i v at i on r ecor d
of m ai n pr ogr am
A ct i v at i on r ecor d
o f cal l t o p
A ct i v at i on r ecor d
of cal l t o q
A ct i v at i on r ecor d
of cal l t o r
A ct i v at i on r ecor d
of cal l t o p
A ct i v at i on r ecor d
of cal l t o q
A ct i v at i on r ecor d
of cal l t o r
fp
sp
7.3.3 Stack-Based Environment with
Procedure Parameters
Example 7.7 Consider the standard pascal program of Figure 7.14,
which has a procedure p,with a parameter a that is also a procedure.
Program closureEx(output)
Procedure p (procedure a);
Begin
a;
end;
procedure q;
var x:integer;
procedure r;
begin
writeln(x);
end;
begin
x:=2;
p(r);
end; (* q*)
begin (* main *)
q;
end.
T h e r u n tim e sta c k j u st af te r t h e c all t o p in t h e c od e of F igu r e 7.14
<n o ac c e ss l in k >
c on tr ol l in k
r e turn ad d r e ss
x,2
A,<ip
r
,e p >
<n o ac c e ss l in k >
c on tr ol l in k
r e turn ad d r e ss
Fr e e sp ac e
fp
sp
A ct i v at i on r ecor d of
m ai n pr ogr am
A ct i v at i on r ec or d of
cal l t o q
A ct i v at i on r ecor d of
cal l t o p
T h e r u n tim e sta c k j u st af te r t h e c all t o a in t h e c od e of F igu r e 7.14
< no a c c e ss l ink>
c ontrol l ink
re turn a ddr e ss
x,2
A:< ip
r
,e p>
< no a c c e ss l ink>
c ontrol l ink
re turn a ddr e ss
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
F re e spac e
fp
sp
A ct i v at i on r ecor d of
m ai n pr ogr am
A ct i v at i on r ecor d of
cal l t o q
A ct i v at i on r ecor d of
cal l t o p
A ct i v at i on r ecor d of
cal l t o a
Note:
– The calling sequence must distinguish clearly between
ordinary procedures and procedure parameters
– When calling ordinary procedure,fetch the access link
using the nesting level and jump directly to the code of
the procedure
– A procedure parameter has its access link stored in the
local activation record,and an indirect call must be
performed to the ip stored in the current activation
record
– If all procedure values are stored in the
environment as closures,the following page shows
the environment
Run tim e stac k just af te r the c all to a in the c od e of F igu r e 7.14 w ith all
p r oc e d u r e s k e p t as c los u r e s in t h e e n vir on m e n t
p:<ip
p
,- >
q:<ip
q
,- >
< no a c c e ss l ink>
c ontrol l ink
re turn a ddr e ss
x,2
r,< ip
r
,e p>
a,<ip
r
,e p>
< no a c c e ss l ink>
c ontrol l in k
re turn a ddr e ss
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
F re e spac e
fp
sp
A ct i v at i on r ecor d of
m ai n pr ogr am
A ct i v at i on r ecor d of
cal l t o q
A ct i v at i on r ecor d of
cal l t o p
A ct i v at i on r ecor d of
cal l t o a
End of Part One
THANKS
Principles and Practice
Kenneth C,Louden
7,Runtime Environments
PART ONE
Contents
Part One
7.1 Memory Organization During Program Execution
7.2 Fully Static Runtime Environments
7.3 Stack-Based Runtime Environments
Part Two
7.4 Dynamic Memory
7.5 Parameter Passing Mechanisms
7.6 A Runtime Environment for the TINY Language
The precious chapters studied the phases of a
compiler that perform static analysis of the
source language
– Scanning,parsing,and static semantic analysis
– Depends only on the properties of the source
language
This chapter and the next turn to the task of
studying how a compiler generates executable
code
– Additional analysis,such as that performed by an
optimizer
– Some of this can be machine independent,but much of
the task of code generation is dependent on the details
of the target machine
Runtime Environment
The structure of the target computer’s registers
and memory that serves to manage memory and
maintain the information needed to guide the
execution process
Three kinds of runtime environments
(1) Fully static environment; FORTRAN77
(2) Stack-Based environment; C C++
(3) Fully dynamic environment; LISP
Main issues will be discussed in more detail in the
chapter,
– For each environment,the language features and their
properties
(1) Scoping and allocation issues;
(2) Nature of procedure calls;
(3) Parameter passing mechanisms
Focus on the general structure of the environment
Note:
– The compiler can only maintain an environment only
indirectly
– It must generate code to perform the necessary
maintenance operations during program execution.
7.1 Memory Organization During
Program Execution
The memor y of a t y pic a l c omput e r,
A r e g ist e r a r e a ;
Addr e ssable R a ndom a c c e ss m e mor y ( R AM),
A c ode a r e a ;
A da ta a re a,
The c ode a re a is fix e d pr ior to e x e c uti on,a nd c a n be visuali z e d a s
follows,
Entr y poi nt er t o pr ocedur e1 → C ode f or pr oced ur e 1
Entr y poi nt er t o pr ocedur e2 → C ode f or pr oced ur e 2
…
Entr y poi nt er t o pr ocedur e n → C ode f or pr oced ur e n
I n p a rticula r,th e e ntr y po int for e a c h p roc e du re a n d func ti on is known a t
c ompi le tim e,
The global and/or static data of a program can be
fixed in memory prior to execution
– Data are allocated separately in a fixed area in a similar
fashion to the code
In Fortran77,all data are in this class;
In Pascal,global variables are in this class;
In C,the external and static variables are in this class
The constants are usually allocated memory in
the global/static area
– Const declarations of C and Pascal;
– Literal values used in the code,
such as,Hello%D\n” and Integer value 12345:
Printf(“Hello %d\n”,12345);
The memory area used for dynamic data can be
organized in many different ways
– Typically,this memory can be divided into a stack area
and a heap area;
A stack area used for data whose allocation occurs in FIFO
fashion;
A heap area used for dynamic allocation occurs not in FIFO
fashion.
Generally,the architecture of the target machine
includes a processor stack for procedure calls and
returns.
– Sometimes,a compiler will have to arrange for the
explicit allocation of the processor stack in an
appropriate place in memory.
T h e ge n e r al organi z at io n of r u n tim e stor age,
C ode a re a
Globa l/ static a re a
S tac k
↓
F re e spac e
↑
He a p
W he re,the a rr o ws indi c a te the dire c ti on of g row th of the stac k
a nd he a p,
Pr oc e d u r e ac tivat ion r e c o r d (A n im p or t an t u n it o f m e m o r y
all oc at ion )
Memor y a ll oc a ted for the loca l data of a proc e dure or f unc ti on,
An a c ti va ti on re c or d mus t conta ins t he f oll owing s e c ti ons,
S pa c e f or a r g uments
( pa ra m e ter s )
S pa c e f or bookk e e pin g
info rma ti on,including r e turn
a ddre ss
S pa c e f or lo c a l data
S pa c e f or lo c a l t e mpora ri e s
Note,thi s pictur e onl y il lust ra t e s the g e n e r a l or ga niz a ti on of a n
a c ti va ti on re c o rd,
Some parts of an activation record have the same size for
all procedures
– Space for bookkeeping information
Other parts of an activation record may remain fixed for
each individual procedure
– Space for arguments and local data
Some parts of activation record may be allocated
automatically on procedure calls:
– Storing the return address
Other parts of activation record may need to be allocated
explicitly by instructions generated by the compiler:
– Local temporary space
Depending on the language,activation records may be
allocated in different areas:
– Fortran77 in the static area;
– C and Pascal in the stack area; referred to as stack frames
– LISP in the heap area.
Processor registers are also part of the
structure of the runtime environment
– Registers may be used to store temporaries,local
variables,or even global variables;
– In newer RISC processor,keep entire static area and
whole activation records;
– Special-purpose registers to keep track of execution
PC program counter;
SP stack pointer;
FP frame pointer;
AP argument pointer
The sequence of operations when calling the
functions,calling sequence
– The allocation of memory for the activation record;
– The computation and storing of the arguments;
– The storing and setting of necessary registers to affect
the call
The additional operations when a procedure or
function returns,return sequence (VS call)
– The placing of the return value where the caller can
access it;
– The readjustment of registers;
– The possible releasing for activation record memory
The important aspects of the design of the
calling sequence:
(1) How to divide the calling sequence
operations between the caller and callee
At a minimum,the caller is responsible for
computing the arguments and placing them in
locations where they may be found by the callee
(2) To what extent to rely on processor support
for calls rather that generating explicit code
for each step of the calling sequence
7.2 Fully Static Runtime
Environments
T h e e n tir e p r ogr a m m e m or y c an b e visu ali z e d as
f oll o w s,
C od e f or m ai n pr ocedur e
C od e f or pr oce dur e 1
…
C od e f or pr oce dur e n
C od e ar ea
G l obal data ar ea
A ct i vat i on r e cord o f m ai n
pr ocedur e
A ct i vat i on r ecor d o f
pr ocedur e 1
…
A ct i vat i on r ecor d o f
pr ocedur e n
D at a ar ea
All data are static,remaining fixed in memory for
the duration of program execution
For a language,such as FORTRAN77,no pointer
or dynamic allocation,no recursive procedure
calling
– The global variables and all variables are allocated
statically.
– Each procedure has only a single activation record.
– All variable,whether local or global,can be accessed
directly via fixed address.
Relative little overhead in terms of bookkeeping
information to retain in each activation record;
And no extra information about the environment
needs to be kept in an activation record;
The calling sequence is simple.
– Each argument is computed and stored into its
appropriate parameter location;
– The return address is saved,and jump to the beginning
of the code of the callee;
– On return,a simple jump is made to the return address.
Example,A FORTRAN77 sample program
PROGRAM TEST
COMMON MAXSIZE
INTEGER MAXSIZE
REAL TABLE(10),TEMP
MAXSIZE = 10
READ *,TABLE(1),TABLE(2),TABLE(3)
CALL QUADMEAN(TABLE,3,TEMP)
PRINT *,TEMP
END
SUBROUTINE QUADMEAN(A,SIZE,QMEAN)
COMMON MAXSIZE
INTEGER MAXSIZE,SIZE
REAL A(SIZE),QMEAN,TEMP
INTEGER K
TEMP=0.0
IF ((SIZE,GT,MAXSIZE),OR,(SIZE,LT,1) GOTO 99
DO 10 K=1,SIZE
TEMP=TEMP+A(K)*A(K)
10 CONTINUE
99 QMEAN = SQRT(TEMP/SIZE)
RETURN
END
A r u n ti m e e n vir on m e n t f or t h e p r ogr a m ab ove,
G l obal ar ea MA X SIZ E
T A B L E ( 1)
( 2)
…
( 10)
T E MP
A ct i vat i on r ec ord of m ai n
pr ocedur e
3
A
SI Z E
Q ME A N
R et u rn a ddr es s
T E MP
K
A ct i vat i on r ecord o f
pr ocedur e Q U A D M E A N
U n nam ed l ocat i on
N ot e,T h e u n n am e d locat ion is u se d to stor e te m p or ar y valu e
d u r in g the c om p u tat ion of ar ithm e ti c e xp r e ssi on,
7.3 Stack-Based Runtime
Environments
For a language,in which
– Recursive calls are allowed;
– Local variables are newly allocated at each call;
– Activation records cannot be allocated statically
Activation records must be allocated in a stack-
based fashion
– The stack of activation records grows and shrinks with
the chain of calls in the executing program.
– Each procedure may have several different activation
records on the call stack at one time,each
representing a distinct call.
– More complex strategy for bookkeeping and
variable access,which depends heavily on the
properties of the language being compiled.
7.3.1 Stack-Based Environments
Without Local Procedures
In a language where all properties are global (such
as C language),the stack-based environment
requires two things:
(1) Frame pointer or fp,a pointer to the current
activation record to allow access to local
variable; Control link or dynamic link,a
point to a record of the immediately preceding
activation
(2) Stack pointer or sp,a point to the last
location allocated on the call stack
Example,The simple recursive implementation of
Euclid’s algorithm to compute the greatest common divisor
of two non-negative integer
# include <stdio.h>
int x,y;
int gcd(int u,int v)
{ if (v==0) return u;
else return gcd(v,u%v);
}
main()
{scanf(“%d%d”,&x,&y);
printf(“%d\n”,gcd(x,y));
return 0;
}
Suppose the user inputs the values 15 and 10 to this program,
T h e e n vir on m e n t du r in g the t h ird call,
X,15
Y,10
G l obal / st at i c ar ea
A ct i vat i on r ec ord o f m ai n
U,15
V,10
C o ntr ol l i n k
R et ur n ad dr es s
A ct i vat i on r ec ord o f
Fir st cal l t o gcd
U,10
V,5
C ontr ol l i nk
R et ur n ad dr es s
A ct i vat i on r ec ord o f
Secon d cal l t o gc d
U,5
V,0
C o ntr ol l i n k
R et ur n ad dr es s
A ct i vat i on r ec ord o f
T hi rd c al l t o gcd
Fr ee s pac e D i r ect i on o f
S t ack gr ow t h
Af te r the f in al c all to g c d,e ac h of the ac tivat i on s is r e m ove d in turn
f r om the st ac k,
Fp
sp
Example,Int x=2;
Void g(int);/*prototype*/
Void f(int n)
{static int x=1;
g(n);
x--;
}
void g(int m)
{int y=m-1;
if (y>0)
{ f(y);
x--;
g(y);
}
}
main( )
{g(x);
return 0;
}
(a) Run tim e e n vir on m e n t o f t h e ab ove p r ogr a m d u r in g
the se c on d c all t o g
x,2
x ( f r om f ),1
G l obal / st at i c ar ea
A ct i vat i on r ec ord o f
m ai n
M,2
C ontr ol l i nk
R et u rn a ddr es s
y,1
A ct i vat i on r ec ord o f
C al l t o g
n,1
C ontr ol l i nk
R et u rn a dd r es s
A ct i vat i on r ec ord o f
C al l t o f
m,1
C ontr ol l i nk
R et u rn a ddr es s
y,0
A ct i vat i on r ec ord o f
C al l t o g
Fr ee s pac e
fp
sp
(b) R u n tim e e n vir on m e n t of t h e ab ove p r ogr am d u r in g
the t h ird call to g
x,1
x ( f r om f ),0
G l obal / st at i c ar ea
A ct i vat i on r ec ord o f
m ai n
m,2
C ontr ol l i nk
R et u rn a ddr es s
y,1
A ct i vat i on r ec ord o f
C al l t o g
m,1
C ontr ol l i nk
R et u rn a dd r es s
y,0
A ct i vat i on r ec ord o f
C al l t o g
Fr ee s pac e
fp
sp
Ac tivat ion s tr e e,a us e ful tool fo r the a n a ly s is of c ompl e x c a ll ing
struc ture s
E xam pl e,act i vat i on tr ees f or t he pr ogr am of f i gur es 7,3 and 7.5
m ai n( )
gcd( 15,1 0)
gcd( 10,5)
gcd( 5,0)
( a)
m ai n( )
g( 2)
f ( 1) g( 1)
g( 1)
( b)
N ot e,In ge neral,t he st ack of act i vat i on r eco rds at t h e begi nni ng o f a p art i cul ar
cal l has a st r uct ur e e qui v al ent t o t he path f r om t he corr es po ndi ng nod e i n t h e
act i vat i on tr ee t o t he r o ot,
Access to Names:
– Parameters and local variable can no longer be
accessed by fixed addresses,instead they must
be found by offset from the current frame
pointer.
– In most language,the offset can be statically
computable by the compiler.
C onsi de r the proc e du re g in t he C prog r a m of F i g u re 7.5,
m
C ont r ol l i nk
R et ur n ad dr es s
y
Note,
Ea c h a c ti va ti on re c or d of g h a s e x a c tl y the sa me fo rm,a nd th e
pa ra mete r m a nd the lo c a l va ria ble y a re a lw a y s in e x a c tl y the sa me
re lative lo c a ti on in t he a c ti va ti on re c or d,
B oth m a nd y c a n b e a c c e ssed b y their f ix e d of fse t fr om t he f p,
W e ha ve mOf fs e t=+ 4 a n d y O f fse t = - 6,
The re fe r e nc e s to m a nd y c a n be wr it ten in mac hine c ode a s 4( fp) a nd
– 6( fp),
fp
m O f f se t
yO f f se t
E xam pl e 7.4 C o nsi der t he C pr oc edur e
V oi d f ( i nt x,char c)
{ i nt a[ 10] ;
double y;
…
}
T h e ac tivat ion r e c o r d f or a c all t o f w ou l d ap p e ar as
x
c
C ontr ol l i nk
R et ur n ad dr es s
a[ 9]
…
a[ 1]
a[ 0]
y
O f f se t o f x
fp O f f se t o f c
O f f se t o f a
O f f se t o f y
Assumi ng two b y tes fo r int e g e rs,four b y t e s for a ddre sses,one b y t e
for c ha ra c ter a nd e i g ht b y t e s fo r double - p re c isi on floa ti ng point,we
would ha ve the f oll owin g o f fse t value s,
N am e O f f se t
x +5
c +4
a - 24
y - 32
Now,a n a c c e ss of a [ i],would r e qu ire th e c o mput a ti on of the
a ddre ss,
( - 24+ 2*i)( fp)
The calling sequence,
– When a procedure is called
Compute the arguments and store them in their correct
positions in the new activation record of the procedure;
Store the fp as the control link in the new activation record;
Change the fp so that it points to the beginning of the new
activation record;
Store the return address in the new activation record;
Perform a jump to the code of the procedure to be called.
– When a procedure exits
Copy the fp to the sp.
Load the control link into the fp.
Perform a jump to the return address;
Change the sp to pop the arguments.
E x am p l e 7,5 C o n s i d e r t h e s i t u a t i o n j u s t b e fo re t h e l as t
cal l t o g
( r es t of st ack)
M,2
C ont r ol l i nk
R et ur n addr es s
Y,1
F r ee s pace
fp
sp
A ct i vat i on r eco rd
of c al l t o g
As the n e w c all to g is m ad e,f irst the valu e of p ar ame te r m is p u sh e d on to
the r u n tim e stac k,
( r es t of st ack)
M,2
C ont r ol l i nk
R et ur n addr es s
Y,1
M,1
F r ee s pace
fp
sp
A ct i vat i on
r ecord o f cal l
t o g
T h e n t h e f p is p u sh e d o n to t h e stac k,
( r es t of st ack )
M,2
C o ntr ol l i n k
R et ur n a ddr es s
Y,1
M,1
C o ntr ol l i n k
Fr ee s pac e
fp
sp
A ct i vat i on
r ecord o f cal l t o
g
Now,the sp is c opied in to the fp,the re turn a ddre ss is pushe d onto the
stac k,a nd the jump t o the ne w c a ll of g is m a de,
( r es t of st ack)
M,2
C ont r ol l i nk
R et ur n addr es s
Y,1
M,1
C ont r ol l i nk
r etu r n ad d r ess
F r ee s pace
fp
sp
A ct i vat i on
r ecord o f cal l t o
g
N e w act i vat i on r ecord
O f cal l t o g
F in all y,g all oc a te s an d in itial ize s the n e w y on the sta c k to c o m p let e the
c on str u c tion o f t h e n e w ac tivat ion r e c or d,
( r es t of st ack )
M,2
C o ntr ol l i n k
R et ur n a ddr es s
Y,1
M,1
C o ntr ol l i n k
r et urn a dd r ess
y,0
Fr ee s pac e
fp
sp
A ct i vat i on
r ecord o f cal l t o
g
N e w act i vat i on r eco rd
of c al l t o g
Dealing with variable-length data
– The number of arguments in a call may vary from call
to call,and
– The size of an array parameter or a local array variable
may vary from call to call
– An example of situation 1 is the printf function in C:
Printf(“%d%s%c”,n,prompt,ch)
– Has four arguments,while
Printf(“Hello,world\n”)
– Has only one argument
C compiler typically deal with this by pushing the
arguments to a call in reverse order onto the
runtime stack,The first parameter is always
located at a fixed offset from the fp in the
implementation described above
Another option is to use a processor mechanism
such as ap (argument pointer) in VAX
architecture.
An example of situation 2 is the unconstrained array of
Ada:
Type int_vector is
Array(INTEGER range <>) of INTEGER;
Procedure sum (low,high,INTEGER;
A,Int_vector) return INTEGER
Is
Temp,Int_Array (low..high);
Begin
…
end sum;
A typical method is to use an extra level of indirection
for the variable-length data,storing a pointer to the
actual data in a location that can be predicated at compile
time.
W e co u l d im p l em en t an ac t i v a t i o n rec o r d f o r SU M as f o l l o w s,
( r es t of st ack )
L ow,…
H i gh,…
A,
Si ze of A,1 0
C ont r ol l i nk
R et ur n ad dr es s
I,…
A [ 9]
…
A [ 0]
F r ee s pace
N o w,fo r ins t an ce,ac ces s t o A [i ] can b e ac h i e v e d by com p u t i n g
@6 ( fp ) +2 * i
A ct i vat i on r eco rd o f
cal l t o Sum
V ari abl e - l engt h
D at a ar ea
fp
sp
Note:
– In the implementation described in the previous
example,the caller must know the size of any
activation record of Sum
– The size of the parameter part and the bookkeeping
part is known to the compiler at the point of call
– The size of the local variable part is not,in general,
known at the point of call,Variable-length local
variables can be dealt with in a similar way
Local Temporaries and Nested Declarations:
– Two more complications to the basic stack-based
runtime environment
(1) Local temporaries are partial results of computations
that must be saved across procedure calls,for example:
x[i] = (i + j) *(i/k + f(j))
The three partial results need to be saved across
the call to f:
The address x[i];
The sum i+j;
The quotient i/k;
T h e r u n tim e sta c k m igh t app e ar as f oll o w s at t h e p oin t j u st bef or e t h e c all t o f,
( r es t of st ack )
…
cont r ol l i n k
r et urn ad dr es s
…
A ddr es s of x[ I]
R es ul t o f I+ j
R es ul t o f i / j
Fr ee s pac e
A ct i vat i on r ecord o f
pr ocedur e cont ai ni ng
t he expr es si on
S t ack of t em porari es
N e w act i vat i on r eco rd
of cal l t o f ( a bout t o
cr eat ed)
fp
sp
Nested declarations present a similar problem,Consider
the C code
Void p( int x,double y)
{ char a;
int I;
…
A:{double x;
Int j;
…
}
…
B:{char *a;
Int k;
…
}
…
}
There are two block (also called compound statement),labeled
A and B nested inside the body of procedure p.
The nested local declaration does not need to be allocated until
entered;
Both A and B do not need to be allocated simultaneously.
A s i m p l er m et h o d i s t o t rea t t h em i n a s i m i l ar w a y t o t em p o r ary
ex p res s i o n,F o r i n s t a n ce,j u s t af t er en t er i n g b l o c k A i n t h e s am p l e
C j u s t g i v e n,t h e r u n t i m e st ac k w o u l d ap p e ar as f o l l o w s,
( r es t of st ack )
X,
Y,
cont r ol l i n k
r et urn ad dr es s
a,
I,
x,
J,
Fr ee s pac e
A ct i vat i on r ecord o f
cal l t o p
A l l ocat ed ar ea f or bl o ck
A
fp
sp
A n d j u s t a ft er e n t ry to b l o ck B i t w o u l d l o o k a s f o l l o w s,
( r es t of st ack)
X,
Y,
cont r ol l i nk
r et ur n addr es s
a,
I,
a,
k,
F r ee s pace
A ct i vat i on r eco rd o f
cal l t o p
A l l ocat ed ar ea f or
bl ock B
fp
sp
7.3.2 Stack-Based Environment
with local Procedures
Consider the non-local and non-global references
Example,Pascal program showing nonlocal,nonglobal
reference
Program nonlocalRef;
Procedure P;
Var N,integer;
Procedure Q;
Begin
(* a reference to N is now non-local andnon-global *)
end; (* q*)
Procedure R(N,integer);
Begin
Q;
End;(*r *)
Begin(*p*)
N:=1;
R(2);
End ;(*p*)
Begin (* main*)
P;
End.
T h e ru n ti m e stac k fo r th e p ro g ram a b o v e,
C ontrol l ink
R e turn a ddre ss
N:1
N:2
C ontrol l ink
R e turn a ddre ss
C ontrol l ink
R e turn a ddre ss
F re e spac e
fp
sp
A ct i v at i on r ecor d of
m ai n pr ogr am
A ct i v at i on r ecor d of
C al l t o p
A ct i v at i on r ecor d of
C al l t o r
A ct i v at i on r ecor d of
C al l t o q
N cannot be found using any of the
bookkeeping information that is kept in the
runtime environment up to now
To solve the above problem about variable access,
we add an extra piece of bookkeeping information
called the access link to each activation record
Access link represents the defining environment
of the procedure;
Control link represents the calling environment of
the procedure.
The runti m e s ta ck fo r the pr o g r a m a bo v e w i t h a cce s s l i n k s
a dded,
< no a c c e ss l ink>
C ontrol l ink
R e turn a ddre ss
N:1
N:2
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
F re e spac e
fp
sp
A ct i v at i on r eco r d of
m ai n pr ogr am
A ct i v at i on r ecor d of
C al l t o p
A ct i v at i on r ecor d of
C al l t o r
A ct i v at i on r ecor d of
C al l t o q
Note,
– The activation record of procedure p itself
contains no access link,as any nonlocal
reference with p must be a global reference and
is accessed via the global reference mechanism
– This is the simplest situation,where the
nonlocal reference is to a declaration in the
next outermost scope.
Example,Pascal code demonstrating access chaining
Program chain
Procedure p;
Var x,integer;
Procedure q;
Procedure r;
Begin
X:=2;
…
if … then p;
end;(*r*)
begin
r;
end;(*q*)
begin
q;
end;(*p*)
begin(* main *)
p;
end.
In this code,the assignment to x inside r,which
refers to the x of p,must traverse two scope
levels to find x
In this environment,x must be reached by
following tow access links,a process that is called
access chaining
The runtim e st a ck afte r the f i rs t ca l l to r,
< no a c c e ss l ink>
C ontrol l ink
R e turn a ddre ss
x,1
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
F re e spac e
fp
sp
A ct i v at i on r ecor d of
m ai n pr ogr am
A ct i v at i on r ecor d of
C al l t o p
A ct i v at i on r ecor d of
C al l t o q
A ct i v at i on r ecor d of
C al l t o r
Note:
– The amount of chaining,determined by comparing
the nesting level at the point of access with one of the
declaration of the name
– In the above situation,the assignment to x is at nesting
level 3,and x is declared at the nesting level 1,so two
access links must be followed
– However,the access chaining is an inefficient method
for variable access,for each nonlocal reference with a
large nesting difference,a lengthy sequence of
instruction must be executed.
– There is a method of implementing access links in a
lookup table indexed by nesting level,called display,
to avoid the execution overhead of chaining.
The calling sequence
The changes needed to implement access links:
(1) The access link must be pushed onto the runtime stack
just before the fp during a call
(2) The sp must be adjusted by an extra amount to remove
the access link after an exit
How to find the access link of a procedure during
a call?
– Using the (compile-time) nesting level information
attached to the declaration of the procedure
– Generate an access chain as if to access a variable at
the same nesting level
– The access link and the control link are the same,
if the procedure is local
Give n the c od e of PR OG RA M CHAIN the runtim e stac k a ft e r the se c ond c a ll to r
( assuming a r e c ursi v e c a ll to p ) w ould l ook a s follows,
< no a c c e ss l ink>
c ontrol l ink
re turn a ddr e ss
x,…
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
Ac c e ss l i nk
C ontrol l ink
R e turn a ddre ss
< no a c c e ss l ink>
c ontrol l ink
re turn a ddr e ss
x,…
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
F re e spac e
A ct i v at i on r ecor d
of m ai n pr ogr am
A ct i v at i on r ecor d
o f cal l t o p
A ct i v at i on r ecor d
of cal l t o q
A ct i v at i on r ecor d
of cal l t o r
A ct i v at i on r ecor d
of cal l t o p
A ct i v at i on r ecor d
of cal l t o q
A ct i v at i on r ecor d
of cal l t o r
fp
sp
7.3.3 Stack-Based Environment with
Procedure Parameters
Example 7.7 Consider the standard pascal program of Figure 7.14,
which has a procedure p,with a parameter a that is also a procedure.
Program closureEx(output)
Procedure p (procedure a);
Begin
a;
end;
procedure q;
var x:integer;
procedure r;
begin
writeln(x);
end;
begin
x:=2;
p(r);
end; (* q*)
begin (* main *)
q;
end.
T h e r u n tim e sta c k j u st af te r t h e c all t o p in t h e c od e of F igu r e 7.14
<n o ac c e ss l in k >
c on tr ol l in k
r e turn ad d r e ss
x,2
A,<ip
r
,e p >
<n o ac c e ss l in k >
c on tr ol l in k
r e turn ad d r e ss
Fr e e sp ac e
fp
sp
A ct i v at i on r ecor d of
m ai n pr ogr am
A ct i v at i on r ec or d of
cal l t o q
A ct i v at i on r ecor d of
cal l t o p
T h e r u n tim e sta c k j u st af te r t h e c all t o a in t h e c od e of F igu r e 7.14
< no a c c e ss l ink>
c ontrol l ink
re turn a ddr e ss
x,2
A:< ip
r
,e p>
< no a c c e ss l ink>
c ontrol l ink
re turn a ddr e ss
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
F re e spac e
fp
sp
A ct i v at i on r ecor d of
m ai n pr ogr am
A ct i v at i on r ecor d of
cal l t o q
A ct i v at i on r ecor d of
cal l t o p
A ct i v at i on r ecor d of
cal l t o a
Note:
– The calling sequence must distinguish clearly between
ordinary procedures and procedure parameters
– When calling ordinary procedure,fetch the access link
using the nesting level and jump directly to the code of
the procedure
– A procedure parameter has its access link stored in the
local activation record,and an indirect call must be
performed to the ip stored in the current activation
record
– If all procedure values are stored in the
environment as closures,the following page shows
the environment
Run tim e stac k just af te r the c all to a in the c od e of F igu r e 7.14 w ith all
p r oc e d u r e s k e p t as c los u r e s in t h e e n vir on m e n t
p:<ip
p
,- >
q:<ip
q
,- >
< no a c c e ss l ink>
c ontrol l ink
re turn a ddr e ss
x,2
r,< ip
r
,e p>
a,<ip
r
,e p>
< no a c c e ss l ink>
c ontrol l in k
re turn a ddr e ss
Ac c e ss l ink
C ontrol l ink
R e turn a ddre ss
F re e spac e
fp
sp
A ct i v at i on r ecor d of
m ai n pr ogr am
A ct i v at i on r ecor d of
cal l t o q
A ct i v at i on r ecor d of
cal l t o p
A ct i v at i on r ecor d of
cal l t o a
End of Part One
THANKS
