Transcript ppt

Compiler construction
in4020 – lecture 12
Koen Langendoen
Delft University of Technology
The Netherlands
Summary of lecture 11
• (nested) routines
• activation records
• routine descriptors
mies
parameter i
static link
dynamic link
ret. address
noot
• code generation for
parameter
static link i
dynamic link
ret. address
control flow statements
• conditional expressions: true & false labels
• case-statement:
jump table
• for-statement:
overflow
Quiz
6.30 Why are parameters stacked
in the reverse order? That is,
why is the last parameter
pushed first when calling a
routine?
parameter k
...
parameter 1
registers
dynamic link
return address
FP
local variables
working stack
parameter n
...
parameter 1
SP
Overview:
memory management
• explicit deallocation
• malloc() + free()
• implicit deallocation: garbage collection
• reference counting
• mark & scan
• two-space copying
Memory management
What has a compiler to do with memory
management?
• compiler uses heap-allocated data structures
• modern languages have automatic data
(de)allocation
• garbage collection part of runtime support system
• compiler usually assists in identifying pointers
Data allocation with
explicit deallocation
#include <stdlib.h>
void
void
void
void
*calloc(size_t nmemb, size_t size);
*malloc(size_t size);
free(void *ptr);
*realloc(void *ptr, size_t size);
malloc()
• find free block of requested size
• mark it in use
• return a pointer to it.
free()
• mark the block as not in use.
Heap layout
chunk
chunk
block
S
I
Z
E
in use
block
S
I
Z
E
free
S
I
Z
E
S
I
Z
E
S
S
S
S
0
1
0
1
low
pointer to
user data
...
high
marked marked
in use
free
Free()
S
I
Z
E
infree
use
S
I
Z
E
free
S
I
Z
E
S
I
Z
E
S
S
S
S
0
1
1
0
1
...
PROCEDURE Free (Block pointer):
SET Chunk pointer TO Block pointer – Admin size;
SET Chunk pointer .free TO True;
Malloc()
S
I
Z
E
infree
use
S
I
Z
E
free
S
I
Z
E
S
I
Z
E
S
S
S
S
0
1
1
0
1
...
FUNCTION Malloc (Block size) RETURNS a generic pointer:
SET Pointer TO Free block of size (Block size);
IF pointer /= NULL: RETURN pointer;
Coalesce free chunks ();
RETURN Free block of size (Block size);
Free block of size
(request)
S
I
Z
E
infree
use
S
I
Z
E
free
S
I
Z
E
S
I
Z
E
S
S
S
S
1
0
1
0
1
...
block pointer
• walk chunks from low to high
• check if chunk is free AND large enough
• if so, mark chunk in use AND return block pointer
Free block of size
(request)
S
I
Z
E
S
I
Z
infree
use
E
S
I
Z
E
free
S
I
Z
E
S
I
Z
E
S
S
S
S
S
1
0
1
1
0
1
...
block pointer
•
•
•
•
walk chunks from low to high
check if chunk is free AND large enough
if so, mark chunk in use AND return block pointer
optimization: split chunk to free unused part
Free block of size
FUNCTION Free block of size (Block size)
RETURNS a generic pointer:
SET Chunk ptr TO Heap low;
SET Request TO Block size + Admin size;
WHILE Chunk ptr < Heap high:
IF Chunk ptr .free AND Chunk ptr .size >= Request:
Split chunk (Chunk ptr, Request)
SET Chunk ptr .free TO False;
RETURN Chunk ptr + Admin size;
SET Chunk ptr TO Chunk ptr + Chunk ptr .size;
RETURN NULL;
Coalesce free chunks ()
S
I
Z
E
S
I
Z
infree
use
E
S
I
Z
E
S
I
Z
E
S
I
Z
E
S
S
S
S
S
1
0
1
1
0
1
next
next
• walk chunks from low to high
• check if chunk is free
• if so, coalesce all subsequent free chunks
...
Coalesce free chunks
PROCEDURE Coalesce free chunks ():
SET Chunk ptr TO Heap low;
WHILE Chunk ptr < Heap high:
IF Chunk ptr .free:
SET Next TO Chunk ptr + Chunk ptr .size;
WHILE Next < Heap high AND Next .free:
SET Next TO Next + Next .size;
SET Chunk ptr .size TO Next - Chunk ptr;
SET Chunk ptr TO Chunk ptr + Chunk ptr .size;
Optimizations
free: poor performance (linear search)
malloc: irregular performance (coalesce phase)
solutions:
• free lists indexed by size
• coalesce at free()
S
I
Z
E
S
I
Z
infree
use
E
S
I
Z
E
S
S
S
1
0
1
1
use first field
as next ptr
2log(size)
3 4 5 6
free list
S
I
Z
E
S
I
Z
E
S
S
0
1
...
Malloc() with free lists
FUNCTION Malloc (Block size) RETURNS a generic pointer:
SET Chunk size TO Block size + Admin size;
SET Index TO 2log(Chunk size);
IF Index < 3:
SET Index TO 3;
IF Index <= 10 AND Free list[Index] /= NULL:
SET Pointer TO Free list[Index];
SET Free list[Index] .next TO Pointer .next;
RETURN Pointer + Admin size;
RETURN Free block of size (Block size);
Exercise (5 min.)
• give the pseudo code for free() when
using free lists indexed by size.
Answers
Answers
PROCEDURE Free (Block pointer):
SET Chunk pointer TO Block pointer – Admin size;
SET Index TO 2log(Chunk pointer .size);
IF Index <= 10:
SET Chunk pointer .next TO Free list[Index];
SET Free list[Index] TO Chunk pointer;
ELSE
SET Chunk pointer .free TO True;
// Coalesce subsequent free chunks
Break
Garbage collection
• memory allocation is explicit (new)
• memory deallocation is implicit
• garbage set: all chunks that will no longer be
used by the program
• chunks without incoming pointers
• chunks that are unreachable from non-heap data
Example
heap
root set
A
D
B
E
C
F
Garbage
heap
root set
A
D
B
E
C
F
Cyclic garbage
garbage?
heap
root set
A
D
B
E
C
• “no-pointers”: NO
• “not-reachable”: YES
F
Compiler assistance:
identifying pointers
• pointers inside chunks
• user-defined data structures
• compiler: generate self-descriptive chunks
• pointers located outside the heap (root set)
• global data + stack
• compiler: generate activation record descriptions
Self-descriptive chunks
• bitmap per data type
• problem: overhead per chunk / interpretation
• compiler-generated routine per data type
• calls GC for each pointer
• problem: recursion
• organize data type to start off with n pointers
• solution: n can be squeezed into chunk admin
Reference counting
heap
root set
A
D
2
1
B
E
0
1
C
1
0
2
1
F
2
1
• record #pointers to each chunk
• reclaim when reference count drops to zero
Maintaining reference
counts
IF Points into the heap (q):
pointer assignment:
VAR p, q : pointer;
...
p := q;
source
Increment q .ref count;
IF Points into the heap (p):
Decrement p .ref count;
IF p .ref count = 0:
Free recursively (p);
SET p TO q;
target
PROCEDURE Free recursively (Pointer):
FOR each field fi of record Pointer:
IF Points into the heap (fi):
Decrement fi .ref count;
IF fi .ref count = 0:
Free recursively (fi);
Free chunk (Pointer);
Mark & scan
heap
root set
A
D
B
E
C
F
• mark all reachable chunks
• scan heap for unmarked chunks that can be freed
PROCEDURE Mark (Pointer):
Mark
&
scan
IF NOT Points into the heap (Pointer): RETURN;
SET Pointer .marked TO True;
FOR each field fi of record Pointer:
Mark (fi);
PROCEDURE Scan ():
SET Chunk ptr TO Heap low;
WHILE Chunk ptr < Heap high:
IF Chunk ptr .marked:
SET Chunk ptr .marked TO False;
ELSE
SET Chunk ptr .free TO True;
SET Chunk ptr TO Chunk ptr + Chunk ptr .size;
Advanced marking
• problem: mark() is recursive
• solution: embed stack in the chunks
each chunk records:
• a count denoting which child pointer is next
• a pointer to the parent node
Advanced marking
to parent
size
pointer cnt
mark bit
free bit
S p p
2 t t
1 r r
p
t
r
0
S p p
1 t t
1 r r
0
p
t
r
S p p
t t
0 r r
0
Advanced marking:
pointer reversal
• avoid additional parent pointer
• use the n-th child pointer when visiting child n
to parent
S p p
2 t t
1 r r
p
t
r
0
S p p
1 t t
1 r r
0
p
t
r
Two-space copying
• most chunks have a short live time
• memory fragmentation must be addressed
copy all reachable chunks
to consecutive locations
• partition heap in two spaces
from
to
Two-space copying
• most chunks have a short live time
• memory fragmentation must be addressed
copy all reachable chunks
to consecutive locations
• partition heap in two spaces
from
to
from
to
Copying to to-space
from
A
D
B
• copy root set
E
C
F
• leave forwarding
pointers
• scan to-space for
reachable cells in
from-space
to
A
C
scan
scan
Copying to to-space
from
A
B
• copy root set
E
C
F
• leave forwarding
pointers
• scan to-space for
reachable cells in
from-space
to
A
C
scan
scan
D
Copying to to-space
from
A
B
• copy root set
E
C
F
• leave forwarding
pointers
• scan to-space for
reachable cells in
from-space
to
A
C
D
scan
scan
Copying to to-space
from
A
B
• copy root set
E
C
• leave forwarding
pointers
• scan to-space for
reachable cells in
from-space
to
A
C
D
scan
scan
F
Copying to to-space
from
A
B
• copy root set
E
C
• leave forwarding
pointers
• scan to-space for
reachable cells in
from-space
to
A
C
D
F
scan
scan
Copying to to-space
from
A
B
• copy root set
E
C
• leave forwarding
pointers
• scan to-space for
reachable cells in
from-space
to
A
C
D
F
scan
scan
Copying to to-space
from
A
B
• copy root set
E
C
• leave forwarding
pointers
• scan to-space for
reachable cells in
from-space
to
A
C
D
F
scan
Copying to to-space
from
• copy root set
• leave forwarding
pointers
• scan to-space for
reachable cells in
from-space
to
A
C
D
F
scan
Summary
Memory management
• explicit deallocation
• malloc() + free()
• implicit deallocation: garbage collection
• reference counting
• mark & scan
• two-space copying
Homework
• study sections:
• 5.2.6
• 5.2.7
Compaction
Generational garbage collection
• assignment 2:
• make Asterix OO
• deadline June 4 08:59
• print handout for last week [blackboard]