Runtime environment consideration in Compiler

Runtime environment in Compiler

1. 1
Run-Time Environments
Ref: Chapter 7

2. ProgramandMemory
•Program needs memory to execute instructions
•Procedureandvariablesrequiremappingwith
actualmemorylocationatruntime
2

3. Runtime environment
•Runtime environment
–State of target machine
–To provide services to running processes
–E.g. software libraries, environment variables
•Runtime support system
–FacilatetsCommunication between process and runtime
environment
–Mostly generated with executable program itself
–MemoryallocationandDe-allocationduringexecution
of program
3

4. 4
Procedure Activation and
Lifetime
•A procedure is activatedwhen called
•The lifetimeof an activation of a procedure
is the sequence of steps between the first
and last steps in the execution of the
procedure body
•A procedure is recursiveif a new activation
can begin before an earlier activation of the
same procedure has ended

5. Activation Tree
•Process : program in execution
•Program:setof code and procedures
•Activation:execution of procedure
•Activationrecord: All necessary information required to
call a procedure
–When procedureisexecuted,itsactivationrecordisstoredonthe
stack,alsoknownascontrolstack
–Activationrecordofcalledprocedureisstoredonthestack
–Whenexecuted,controlisreturnedtocalledprocedure(showin
activationtree)
5

6. 6
Activation Records
(Subroutine Frames)
Returned value
Actual parameters
Optional control link
Optional access link
Save machine status
Local data
Temporaries
Caller’s
responsibility
to initialize
Callee’s
responsibility
to initialize
fp
(frame pointer)

7. 7
Procedure Activations: Example
program sort(input, output)
var a : array [0..10] of integer;
procedure readarray;
var i : integer;
begin
for i := 1 to 9 do read(a[i])
end;
function partition(y, z : integer) : integer
var i, j, x, v : integer;
begin …
end
procedure quicksort(m, n : integer);
var i : integer;
begin
if (n > m) then begin
i := partition(m, n);
quicksort(m, i -1);
quicksort(i + 1, n)
end
end;
begin
a[0] := -9999; a[10] := 9999;
readarray;
quicksort(1, 9)
end.
Activations:
begin sort
enter readarray
leave readarray
enter quicksort(1,9)
enter partition(1,9)
leave partition(1,9)
enter quicksort(1,3)
…
leave quicksort(1,3)
enter quicksort(5,9)
…
leave quicksort(5,9)
leave quicksort(1,9)
end sort.

8. 8
Activation Trees: Example
s
q(1,9)
q(1,3)
p(1,3)q(1,0)q(2,3)
q(2,1)p(2,3) q(3,3)
p(1,9)
r
q(5,9)
p(5,9)q(5,5)q(7,9)
q(7,7)p(7,9) q(9,9)
Activation tree for the sort program
Note: also referred to as the dynamic call graph

9. 9
Control Stack
s
q(1,9)
q(1,3)
p(1,3)q(1,0)q(2,3)
p(1,9)
r
Activations:
begin sort
enter readarray
leave readarray
enter quicksort(1,9)
enter partition(1,9)
leave partition(1,9)
enter quicksort(1,3)
enter partition(1,3)
leave partition(1,3)
enter quicksort(1,0)
leave quicksort(1,0)
enter quicksort(2,3)
…
Control
stack:
Activation tree:
s
q(1,9)
q(1,3)
q(2,3)

10. Storage Allocation
•Manage runtime memory requirements for
10
Component Memory
requirements
Memory
Code Known at
compile time
Fixed
Procedure Known at
compile time
Static
But called
randomly
Stack storage to
manage
procedure calls
and activation
Variable Known at
runtime
May change
runtime
Heap memory
for allocation
and de-llocation

11. MemoryAllocation
11
Static AllocationStack AllocationHeap Allocation
Allocation at Fix location Runtime Runtime
Allocation change
during execution
No
Component
Allocated
Code Procedure calls
and their
activation records
Variables and
claim it back
when variables are
no more required
Memory grow and
shrink
Yes dynamicallyYes dynamically

12. 12
Scope Rules
•Environmentdetermines name-to-object
bindings: which objects are in scope?
program prg;
var y : real;
function x(a : real) : real;
begin … end;
procedure p;
var x : integer;
begin
x := 1;
…
end;
begin
y := x(0.0);
…
end.
Variable xlocally declared in p
A function x

13. 13
Mapping Names to Values
name storage value
environment state
var i;
…
i := 0;
…
i := i + 1;

14. 14
Mapping Names to Values
name storage value
environment state
var i;
…
i := 0;
…
i := i + 1;
At compile time At run time

15. 15
Static and Dynamic Notions of
Bindings
Static Notion Dynamic Notion
Definition of a procedure
Activations of the
procedure
Declaration of a nameBindings of the name
Scope of a declarationLifetime of a binding

16. 16
Stack Allocation
•Activation records(subroutine frames) on the run-
time stack hold the state of a subroutine
•Calling sequencesare code statements to create
activations records on the stack and enter data in
them
–Caller’s calling sequence enters actual arguments,
control link, access link, and saved machine state
–Callee’s calling sequence initializes local data
–Callee’s return sequence enters return value
–Caller’s return sequence removes activation record

17. 17
Control Links
fp
sp
Control link
Stack
growth
Callee’s activation record
Caller’s activation record
The control link is the old
value of the fp

18. 18
Scope with Nested Procedures
program sort(input, output)
var a : array [0..10] of integer;
x : integer;
procedure readarray;
var i : integer;
begin … end;
procedure exchange(i, j : integer);
begin x := a[i]; a[i] := a[j]; a[j] := x end;
procedure quicksort(m, n : integer);
var k, v : integer;
function partition(y, z : integer) : integer
var i, j : integer;
begin … exchange(i, j) … end
begin
if (n > m) then begin
i := partition(m, n);
quicksort(m, i -1);
quicksort(i + 1, n)
end
end;
begin
…
quicksort(1, 9)
end.

19. 19
Access Links (Static Links)
s
a x
q(1,9)
access
k v
s
a x
q(1,9)
access
k v
q(1,3)
access
k v
s
a x
q(1,9)
access
k v
q(1,3)
access
k v
p(1,3)
access
i j
s
a x
q(1,9)
access
k v
q(1,3)
access
k v
p(1,3)
access
i j
e(1,3)
access
The access link points to the
activation record of the static
parent procedure:
sis parent of r, e, and q
qis parent of p

20. 20
Accessing Nonlocal Data
•To implement access to nonlocal data ain
procedure p, the compiler generates code to
traverse n
p-n
aaccess links to reach the
activation record where aresides
–n
pis the nesting depth of procedure p
–n
ais the nesting depth of the procedure
containing a

21. 21
Parameter Passing Modes
•Call-by-value: evaluate actual parameters and
enter r-values in activation record
•Call-by-reference: enter pointer to the storage of
the actual parameter
•Copy-restore(aka value-result): evaluate actual
parameters and enter r-values, after the call copy
r-values of formal parameters into actuals
•Call-by-name: use a form of in-line code
expansion (thunk) to evaluate parameters