Chapter 7
Runtime Environments
Gang S. Liu
College of Computer Science & Technology
Harbin Engineering University
Introduction
• In previous chapter we have studied the phases of
a compiler
1. Scanning
2. Parsing
3. Static semantic analysis
• These stages
– depend only on the properties of the source language.
– are completely independent
• Of the target (machine or assembly) language
• The properties of the target machine
• Operating system
Compiler Construction
[email protected]
2
Last Stage
• The last stage of compile process is
the code generation .
__________________
• Much of this task is dependent on the details of the
target machine.
• The general characteristics of the code generation
remains the same across a wide variety of
architectures.
Compiler Construction
[email protected]
3
Runtime Environment
•
•
Runtime Environment is 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 run time environment
1. Fully static environment (FORTRAN77)
2. Stack-based environment (C, C++, PASCAL)
3. Fully dynamic environment (LISP)
•
Hybrids of these are also possible.
Compiler Construction
[email protected]
4
Memory Organization
Memory
ROM
Register Area
Code Area
RAM
Data Area
In most compiled languages, it is not possible to make changes
to the code area during execution.
The code area is fixed prior to the execution, and all code
addresses are computable at compile time.
Compiler Construction
[email protected]
5
Code Memory
Entry point for procedure 1
Code for
Procedure 1
Entry point for procedure 2
Code for
Procedure 2
.
.
Entry point for procedure n
Code for
Procedure n
Entry point of each procedure and function is known at compile time.
Compiler Construction
[email protected]
6
Data Area
• Only a small part of data can be assigned fixed
locations before execution begins
– Global and/or static data
– Compile-time constants
• Large integer values
• Floating-point values
– Literal strings
Compiler Construction
[email protected]
7
Dynamic Memory
• The memory area for the allocation of dynamic
data can be organized in many different ways.
• A typical organization divides the dynamic
memory into
– stack area (LIFO protocol)
– heap area
Compiler Construction
[email protected]
8
Memory Organization
code area
global/static area
stack
free space
heap
Compiler Construction
[email protected]
9
Procedure Activation Record
• An important unit of memory
• Procedure activation record contains memory
allocated for the local data of a procedure or
function when it is called, or activated.
arguments
bookkeeping information
(return address)
local data
local temporaries
Compiler Construction
• The picture illustrates the general
organization of an activation record.
• Details depend on the architecture
of target machine and properties of the
language.
• When activation records are kept on
stack, they are called stack frames.
[email protected]
10
Registers
• Registers may be used to store temporaries, local
variables, or even global variables.
• When a processor has many registers, the entire
static area and whole activation records may be
kept in the registers.
• Special purpose registers
– Program counter (PC)
– Stack pointer (SP)
Compiler Construction
[email protected]
11
Calling Sequence
• The calling sequence is the sequence of operations
that must occur when a procedure or function is
called.
– Allocation of memory for the activation record
– The computation and storing the arguments
– Storing and setting registers
Compiler Construction
[email protected]
12
Calling Sequence Design
1. Division of the calling sequence operations
between the caller and the callee.
• It is easier to generate calling sequence code at the point
of call rather than inside the callee.
• This causes the size of the size to grow.
2. Processor support versus generating explicit code
for each step of calling sequence.
Compiler Construction
[email protected]
13
Return Sequence
• The return sequence is the sequence of operations
needed when a procedure or function returns.
– The placing of the return value where it can be accessed
by the caller
– Readjustment of registers
– Releasing of activation record memory
Compiler Construction
[email protected]
14
Runtime Environment
•
•
Runtime Environment is 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 run time environment
1. Fully static environment (FORTRAN77)
2. Stack-based environment (C, C++, PASCAL)
3. Fully dynamic environment (LISP)
•
Hybrids of these are also possible.
Compiler Construction
[email protected]
15
Fully Static Runtime Environment
• The simplest kind of a runtime environment.
• All data are static, remaining in memory for the
duration of the program.
– All variables can be accessed directly via fixed addresses
• Each procedure has only a single activation record,
which is allocated statically prior the execution.
• Such environment can be used to implement a
language in which
– There are no pointers or dynamic allocation,
– Procedures cannot be called recursively.
• Example: FORTRAN77
Compiler Construction
[email protected]
16
Memory Organization
(static runtime environment)
code for main procedure
code for procedure 1
…
Code area
code for procedure n
global data area
activation record of main procedure
activation record of procedure 1
Data area
…
activation record
of procedure n
[email protected]
Compiler Construction
17
Example 7.1
PROGRAM TEST
COMMON MAXSIZE
INTEGER MAXSIZE
REAL TABLE(10), TEMP
MAXSIZE=10
READ *, TABLE(1), TABLE(2), TABLE(3)
CALL QADMEAN(TABLE, 3, TEMP)
PRINT *, TEMP
END
Compiler Construction
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
[email protected]
18
END
Example 7.1 Data Area
Global area
MAXSIZE
TABLE
Activation
record of main
(1)
(2)
…
(10)
TEMP
3
arguments
bookkeeping information
(return address)
local data
A
Activation
record of
QUADMEAN
local temporaries
SIZE
QMEAN
return address
TEMP
Arrows indicate the
values of the parameters
K
Compiler Construction
[email protected]
19
Stack-based Runtime
Environment
• In a language in which recursive calls are allowed,
activation records cannot be allocated statically.
• Activation records are allocated in a stack-based
fashion.
• This stack is called the stack of activation records
(runtime stack, call stack).
• Each procedure may have several different
activation records at one time.
Compiler Construction
[email protected]
20
Global Procedures
•
In a language where all procedures are global
(the C language), a stack-based environment
requires two things:
1. A pointer the current activation record to allow access
to local variables.
– This pointer is called the frame pointer (fp) and is usually
kept in a register.
2. The position or size of the caller’s activation record
– This information is commonly kept in the current activation
record as a pointer to the previous activation record and
referred as the control link or dynamic link.
– Sometimes, the pointer is called the old fp
3. Additionally, there may be a stack pointer (sp)
– It always points to the top of the stack
Compiler Construction
[email protected]
21
Example 7.2
#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;
}
Compiler Construction
[email protected]
Suppose the user inputs
the values 15 and 10 to
this program
u
v
u%v
15
10
5
10
5
0
5
0
End
22
Memory Organization
code area
global/static area
stack
free space
heap
Compiler Construction
[email protected]
23
Procedure Activation Record
• An important unit of memory
• Procedure activation record contains memory
allocated for the local data of a procedure or
function when it is called, or activated.
arguments
bookkeeping information
(return address)
local data
local temporaries
Compiler Construction
[email protected]
24
Example 7.2
#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;
}
Compiler Construction
[email protected]
Suppose the user inputs
the values 15 and 10 to
this program
u
v
u%v
15
10
5
10
5
0
5
0
End
25
Example 7.2 (cont)
sp
fp
sp
fp
sp
fp
sp
fp
sp
x: 15
y: 10
u: 15
v: 10
control link
return address
u: 10
v: 5
control link
return address
u: 5
v: 0
control link
return address
free space
Compiler Construction
#include
Global static
area
<stdio.h>
int x,y;
Activation
of main
intrecord
gcd(int
u,int v)
{
if (v == 0) return u;
Activation record
of firstgcd(v,
call to gcd
else return
u%v);
}
main()
Activation
{ record of second call to gcd
scanf(“%d%d”, &x, &y);
printf(“%d\n”, gcd(x,y));
return of
0;third call to gcd
Activation record
}
Direction of stack grow
[email protected]
26
Example 7.3
int x=2;
void g(int); /* prototype */
void f (int n)
{
static int x=1; x=1
g(n);
g(1)
x--;
x=1-1=0
}
void g(int m)
{
y=m-1=1-1=0
int y = m-1; y=m-1=2-1=1
if(y>0)
y=1>0
y=0
{
f(1)
f(y);
x--=2-1=1
x--;
g(y);
g(1)
}
[email protected]
} Compiler Construction
main ()
{
g(x);
return 0;
}
y=m-1=1-1=0
y=0
27
Memory Organization
code area
global/static area
stack
free space
heap
Compiler Construction
[email protected]
28
Procedure Activation Record
• An important unit of memory
• Procedure activation record contains memory
allocated for the local data of a procedure or
function when it is called, or activated.
arguments
bookkeeping information
(return address)
local data
local temporaries
Compiler Construction
[email protected]
29
Example 7.3
int x=2;
void g(int); /* prototype */
void f (int n)
{
static int x=1; x=1
g(n);
g(1)
x--;
x=1-1=0
}
void g(int m)
{
y=m-1=1-1=0
int y = m-1; y=m-1=2-1=1
if(y>0)
y=1>0
y=0
{
f(1)
f(y);
x--=2-1=1
x--;
g(y);
g(1)
}
[email protected]
} Compiler Construction
main ()
{
g(x);
return 0;
}
30
Example 7.3 (cont)
x: 2
x (from f): 1
Global static area
Activation record of main
fp
sp
m:2
control link
return address
y: 1
Activation record of call to g
n:1
control link
return address
Activation record of call to f
m:1
control link
return address
y: 0
Activation record of call to g
Compiler Construction
free
space
During the second call to g
[email protected]
31
Example 7.3
int x=2;
void g(int); /* prototype */
void f (int n)
{
static int x=1; x=1
g(n);
g(1)
x--;
x=1-1=0
}
void g(int m)
{
y=m-1=1-1=0
int y = m-1; y=m-1=2-1=1
if(y>0)
y=1>0
y=0
{
f(1)
f(y);
x--=2-1=1
x--;
g(y);
g(1)
}
[email protected]
} Compiler Construction
main ()
{
g(x);
return 0;
}
y=m-1=1-1=0
y=0
32
Example 7.3 (cont)
x: 1
x (from f): 0
Global static area
Activation record of main
fp
sp
m:2
control link
return address
y: 1
Activation record of call to g
m:1
control link
return address
y: 0
Activation record of call to g
free space
During the third call to g
Compiler Construction
[email protected]
33
Activation Tree
• A useful tool for the analysis of complex
structures in a program.
• Activation tree: each activation record becomes a
node on this tree, and the descendants of each
node represent all the calls made during the call
corresponding to that node.
main()
g(2)
f(1)
g(1)
g(1)
Compiler Construction
[email protected]
34
Access to Variables
• In static environment, parameters and local
variables can be accessed by fixed addresses.
• In a stack-based environment, they must be found
by offset from the current frame pointer.
• In most languages, the offset for each local
variable is still statically computable by compiler.
– The declarations of a procedure are fixed at compile
time and the memory size to be allocated for each
declaration is fixed by its data type.
Compiler Construction
[email protected]
35
Example
• Each activation record of g has the same form.
m
control link
mOffset = +4
fp
return address
y
yOffset=-6
We assumed that the stack grows from higher to lower memory
addresses, integers require 2 bytes of storage and addresses
require 4 bytes.
Compiler Construction
[email protected]
36
Example 7.5
x: 1
x (from f): 0
Global static area
Activation record of main
fp
sp
m:2
control link
return address
y: 1
Activation record of call to g
free space
Compiler Construction
Before the third call to g
[email protected]
37
Example 7.5 (cont)
fp
rest of stack
rest of stack
m: 2
m: 2
control link
control link
fp
return address
return address
y: 1
y: 1
sp
sp
free space
Compiler Construction
The value of parameter
m is pushed onto the
[email protected]
stack.
m: 2
free space
38
Example 7.5 (cont)
fp is pushed rest of stack
onto the stack. m: 2
fp
control link
rest of stack
m: 2
fp
control link
return address
return address
y: 1
y: 1
m: 2
m: 2
sp
sp
control link
free space
free space
Compiler Construction
[email protected]
39
Example 7.5 (cont)
sp is copied
into fp.
fp
sp
rest of stack
rest of stack
m: 2
m: 2
control link
control link
return address
return address
y: 1
y: 1
m: 2
m: 2
control link
control link
fp=sp
free space
free space
Compiler Construction
[email protected]
40
Example 7.5 (cont)
rest of stack
The return rest of stack
address is pushed
m: 2
onto the stack.
control link
fp=sp
m: 2
control link
return address
return address
y: 1
y: 1
m: 2
m: 2
control link
fp
control link
sp
return address
free space
Compiler Construction
free space
[email protected]
41
Example 7.5 (cont)
rest of stack
rest of stack
The new local variable
m: 2
y is allocated and
control link
initialized.
m: 2
control link
return address
return address
y: 1
y: 1
m: 2
m: 2
fp
control link
sp
return address
free space
Compiler Construction
fp
control link
return address
sp
[email protected]
y: 1
free space
42
Homework
• 7.1, 7.2
Compiler Construction
[email protected]
43
Descargar

Document