Runtime Environments
Runtime Environments
CS106 — Compiler Principles and Construction
Fall 2011
MUST FIT
Zhiyao Liang
Runtime Environments Dr. Zhiyao Liang
1
Introduction
Some aspects of code generation depend on different target machines.
Some aspects of code generation remains the same across different architectures.
Like the features of runtime environment
Runtime environment is :
the structure of registers and memory of the target machine for the purpose of guiding the execution.
operations (how to maintain) of these structures during run time.
Runtime Environments Dr. Zhiyao Liang
2
Intro cont.
Runtime behavior describe the behavior of target code, not the compiler.
Compiler generates code that maintains the runtime environment (indirect).
Running an compiler only do the code generation.
Interpreter directly runs the runtime environment.
Running an interpreter also means running the runtime environment.
Runtime Environments Dr. Zhiyao Liang
3
Three kinds of RE
Fully static environment: FORTRAN77
Stack-based environment: C, C++, Pascal
Fully dynamic environment: functional languages like LISP
Runtime Environments Dr. Zhiyao Liang
4
Memory organization in runtime
Computer memory = registers + RAM
RAM is divided into: code area + data area.
Before running a program, its code is loaded into the code area.
code area cannot change during runtime.
Compiler knows the entry point (address) of each procedure and function.
The address of procedure/function has a fixed offset away from the base point.
Entry point = offset + base
base may change in different execution (relocatable code)
Runtime Environments Dr. Zhiyao Liang
5
RAM = random access memory
5
code area in memory
Runtime Environments Dr. Zhiyao Liang
6
Data that can be fixed in memory before execution (non-dynamic data)
global data
like those outside of any function
static data
e.g., {… static int x;…}
Large constant data (we only want one copy of it in memory)
large integer, float. float x = 3.141526
String literals. “Long long time ago”.
small constants (0, 1, 3) are included directly into target code.
Runtime Environments Dr. Zhiyao Liang
7
non-fixed data in memory
The compiler does not know:
How many times a function is called.
Each function call needs separate memory space (on the stack) for its local variables and bookkeeping data.
Called the procedure activation record.
How much dynamic memory allocation (on the heap) using malloc()
100 tree nodes or 1000 tree nodes?
Runtime Environments Dr. Zhiyao Liang
8
A general organization of runtime memory
Runtime Environments Dr. Zhiyao Liang
9
code area
heap
Global/static area
stack
free space
Procedure activation record at a minimum
Runtime Environments Dr. Zhiyao Liang
10
Space for arguments
Space for bookkeeping information, like return address
Space for local data
Space for local temporaries
Same size for each call of the same function
Same size for each call of all function.
return address is set the caller
An activation record can be saved in:
static area (FORTRAN77)
stack area (C, Pascal)
Called a stack frame
heap area (LISP)
return address: the address of the instruction that will be executed when this call is finished.
local temporaries are for the intermediate computation data.
10
Registers
Commonly, data (instruction ,data) are loaded from memory into registers, and results are saved back to memory.
Special purpose registers:
program counter (pc)
frame pointer (fp)
stack pointer (sp)
argument pointer (ap)
Runtime Environments Dr. Zhiyao Liang
11
pc: address of the next instruction to be executed
fp: the current activation record.
ap: the arugment area of the current activation record
sp: the stack top.
11
Calling sequence
Operations needed for a procedure call
allocation for the activation record.
adjusting registers.
bookkeeping.
call sequence vs. return sequence.
Design issues:
How much are done by the caller, or by the callee?
Runtime Environments Dr. Zhiyao Liang
12
Fully static runtime environment
The simplest case, all data are fixed in memory (FORTRAN77).
How much memory is used is known at compile time.
Restrictions:
Each procedure is called a fixed time (one time).
no recursive procedure.
no dynamic allocation (no malloc() ).
Runtime Environments Dr. Zhiyao Liang
13
Fully static runtime environment
Runtime Environments Dr. Zhiyao Liang
14
A FORTRAN77 program and its RE
Runtime Environments Dr. Zhiyao Liang
15
The arrow means pass by reference (reference as arugments)
15
Stack-based runtime environments
For C, new activation record is saved at the stop of a stack.
Then a function call is done, its activation record is deallocated from the stack.
Each procedure can have several activation records on the stack.
The stack grows and shrinks.
Why recursion can consume all memory?
Runtime Environments Dr. Zhiyao Liang
16
Stack-based environment without local procedures (such as C)
This kind of RE requires two things:
A pointer to the current frame (activation record)
Call the frame pointer (fp), usually kept in a register.
Information (link or record) of the preceding frame, which is the one to be covered.
Commonly kept in the middle of the current frame as a pointer to the previous frame, called the control link, dynamic link, or old fp.
Sometimes there is a stack pointer pointing to the stack top.
Runtime Environments Dr. Zhiyao Liang
17
One C program and its RE
#include
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;
}
Runtime Environments Dr. Zhiyao Liang
18
No arrow for arguments , since C is pass-by-value.. Return address is the address of the code to be executed (in the code area)
18
Calling structure can be described as activation tree.
Runtime Environments Dr. Zhiyao Liang
19
Difference between fp and sp?
http://www.cs.purdue.edu/homes/hosking/502/spim/node23.html
Layout of a stack frame.
The frame pointer points just below the last argument passed on the stack.
The stack pointer points to the first word after the frame.
Runtime Environments Dr. Zhiyao Liang
20
Runtime Environments Dr. Zhiyao Liang
21
x=2
main()
g(2)
g(2)
f(1)
g(1)
f(1)
x–
g(1)
f.x —
g(1)
g(1)
f.x = 1
A C program and its execution
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 row is the computation of one function call. When one row finishes, the caller row resumes computation.
21
cont.
Runtime Environments Dr. Zhiyao Liang
22
cont.
Runtime Environments Dr. Zhiyao Liang
23
The address of local data can be computed based on fp
Runtime Environments Dr. Zhiyao Liang
24
These offsets are known by the compiler
Code can be generated accordingly.
24
Example.
Runtime Environments Dr. Zhiyao Liang
25
suppose an integer needs 2 bytes; address needs 4 bytes, double needs 8 bytes
25
Calling sequence:
when a procedure is called
Compute the arguments. Save (push to stack) them into the new frame
Store fp as the control link in the new frame.
Change fp as the beginning of the new frame
Save the return address of in the new frame
jump to the code of the procedure
Allocate space for local data on the stack
Runtime Environments Dr. Zhiyao Liang
26
return address can use pc.
26
Calling sequence:
when a procedure exits
Copy the fp to the sp (sp = fp)
Load the contral link into fp (fp = control link)
Jump to the return address (change pc)
Change sp to pop the arguments.
Runtime Environments Dr. Zhiyao Liang
27
Example, the call sequence
(0) before the last call of g() in Fig 7.6.b
Runtime Environments Dr. Zhiyao Liang
28
28
(1) argument m is pushed
Runtime Environments Dr. Zhiyao Liang
29
(2) fp is pushed onto the stack, as the control link
Runtime Environments Dr. Zhiyao Liang
30
(3) fp = sp, push the return address, jump to g
Runtime Environments Dr. Zhiyao Liang
31
A push always changes the sp automatically.
31
(4) push the local data y
Runtime Environments Dr. Zhiyao Liang
32
Complication:
Dealing with variable-length data
In different call of the same procedure,
the number of arguments can be different.
E.g., printf()
The size of array parameter or local array can vary.
How to deal with it?
Use an extra argument (at fixed address), which is the actual number of argument.
Use an pointer (at fixed address), which points to the border of data (beginning or end of the array data).
Runtime Environments Dr. Zhiyao Liang
33
33
Complication: local temporaries.
Local temporaries are partial results of computations that must be saved.
The compiler knows how many temporary data should be saved.
Runtime Environments Dr. Zhiyao Liang
34
Local temporaries:
x[i] = (i + j) * (i/k + f(j))
Runtime Environments Dr. Zhiyao Liang
35
Complication: nested declaration
How about a block inside a block?
Generate an activation record for a nest block is not efficient,
since it is much simpler than a function call.
Data of a nested block can be saved like temporaries.
Runtime Environments Dr. Zhiyao Liang
36
Example, after entering block A.
void p(int x, double y)
{ char a;
int i;
…
A: {double x;
int j;
…
}
…
B:{ char *a;
int k;
…
}
…
}
Runtime Environments Dr. Zhiyao Liang
37
After entering block A.
37
Example, after entering block B.
void p(int x, double y)
{ char a;
int i;
…
A: {double x;
int j;
…
}
…
B:{ char *a;
int k;
…
}
…
}
Runtime Environments Dr. Zhiyao Liang
38
After entering block A.
38
Not covered in classroom
Stack-based environment with local procedures.
Stack-based environments with procedure parameters.
Dynamic Memory
Fully dynamic runtime environments
Dynamic Memory in Object-Oriented Languages
Heap Management
Automatic Management of the Heap
Runtime Environments Dr. Zhiyao Liang
39
Parameter Passing Mechanisms
Parameters of a function means some locations in an activation record of it.
Binding of the parameters to the arguments means to store some values at the locations in an activation record, according to the arguments.
Parameter passing mechanisms:
pass by value (also known as call by value)
pass by reference (call by reference)
pass by value-result
pass by name (also called delayed evaluation)
Runtime Environments Dr. Zhiyao Liang
40
C only has pass by value. C++ provide choices of passing mechanisms.
40
Pass by value
Arguments are expressions and it is evaluated the time of call.
The values of the arguments become the values of parameters.
It is the only parameter passing mechanism of C.
Runtime Environments Dr. Zhiyao Liang
41
Pass by value
When the parameter is a pointer, an argument is an address, and this address is copied to the parameter during a function call.
Runtime Environments Dr. Zhiyao Liang
42
// cannot change argument
void int2(int x)
{ ++x; ++x;}
// can change argument
void int2(int * x)
{ ++(*x); ++(*x);}
/* array parameters are actually pointer parameters. */
void init(int x[], int size)
{ int i;
for (i=0; i