1
Advantage: some optimizations (e.g. constant propagation) become
easier, since no flow analysis is required.
Disadvantage: overhead of converting into functional SSA form.
2 a)
Every variable has a single, unique assignment.
b)
Phi functions phi(a,b) indicate "unknown" values, where statically we
cannot determine whether the value will be a or b. These unknowns are
resolved at run-time.
c)
They are introduced after if-statements and at the beginning of
do-loops, which are the points in the CFG where a node may have
multiple incoming edges.
d)
The program:
if (x) { y := 1; } else { y := 2; }
print (y);
is converted to:
if (x1) { y1 := 1; } else { y2 := 2; }
y3 := phi(y1,y2);
print (y3);
3
a)
class C {
method foo (n : Integer) {
var a : Integer; a := 0;
var x : Integer; x := n;
var y : Integer;
method break_outer () {
return a;
}
method continue_outer () {
if (x > 0) {
x := x - 1;
y := n;
method break_inner () {
return inner.continue_outer ();
}
method continue_inner () {
if (True) {
a := a + 1;
y := y - 1;
if (y == 0) { return inner.break_inner (); }
else { return inner.continue_inner (); }
} else {
return inner.break_inner ();
}
}
return inner.continue_inner ();
} else {
return inner.break_outer ();
}
}
return inner.continue_outer ();
}
}
b)
class C {
method foo (n : Integer) {
let a1 : Integer = 0;
let x1 : Integer = n;
method break_outer (a2 : Integer) {
return a2;
}
method continue_outer (a3 : Integer, x2 : Integer) {
if (x2 > 0) {
let x3 : Integer = x2 - 1;
let y1 : Integer = n;
method break_inner (a4 : Integer, x4 : Integer) {
return inner.continue_outer (a4, x4);
}
method continue_inner (a5 : Integer, x5 : Integer, y2 : Integer) {
if (True) {
let a6 : Integer = a5 + 1;
let y3 : Integer = y2 - 1;
if (y3 == 0) { return inner.break_inner (a6, x5); }
else { return inner.continue_inner (a6, x5, y3); }
} else {
return inner.break_inner (a5, x5);
}
}
return inner.continue_inner (a3, x3, y1);
} else {
return inner.break_outer (a3);
}
}
return inner.continue_outer (a1, x1);
}
}
c) Wasn't covered in 2002 syllabus, but here's the answer in case
you're curious...
class C {
method break_outer (a2 : Integer) {
return a2;
}
method break_inner (a4 : Integer, x4 : Integer, n : Integer) {
return inner.continue_outer (a4, x4, n);
}
method continue_inner (a5 : Integer, x5 : Integer, y2 : Integer, n : Integer) {
if (True) {
let a6 : Integer = a5 + 1;
let y3 : Integer = y2 - 1;
if (y3 == 0) { return inner.break_inner (a6, x5, n); }
else { return inner.continue_inner (a6, x5, y3, n); }
} else {
return inner.break_inner (a5, x5, n);
}
}
method continue_outer (a3 : Integer, x2 : Integer, n : Integer) {
if (x2 > 0) {
let x3 : Integer = x2 - 1;
let y1 : Integer = n;
return inner.continue_inner (a3, x3, y1, n);
} else {
return inner.break_outer (a3);
}
}
method foo (n : Integer) {
let a1 : Integer = 0;
let x1 : Integer = n;
return inner.continue_outer (a1, x1, n);
}
}
4
class C {
method foo (x : Integer) : Integer {
if (x > 0) {
let tmp1 : Integer = x-1;
// inlining this::C.foo (tmp1)
if (tmp1 > 0) {
let tmp3 : Integer = tmp1-1;
let tmp4 = this::C.foo (tmp3);
let tmp5 = tmp4 * tmp1;
return tmp5 * x;
} else {
let tmp6 : Integer = 1;
return tmp6 * x;
}
} else {
return 1;
}
}
method baz (x : Integer) : Integer {
let tmp : Integer = x * x;
// inlining this::C.foo (tmp)
if (tmp > 0) {
let tmp7 : Integer = tmp-1;
let tmp8 : Integer = this::C.foo (tmp7);
return tmp7 * tmp;
} else {
return 1;
}
}
}
5
Mark phase: Starting from the roots of the heap, perform a depth-first
search marking the nodes:
method visit (node) {
if (node is not marked) {
mark the node;
for each child of node {
visit (child);
}
}
}
Sweep phase: Sweep through the whole heap adding unmarked nodes to the
free list:
for each node in the heap {
if (node is not marked) {
add node to free list;
}
}
[ Examples were covered in class and in Appel, I'm not going to try to
draw them in ascii-art! ]
6
a) An incremental gc algorithm is one which spreads the cost of gc
through the run-time, rather than having a "monolithic" gc which halts
the program while it runs to completion.
b) Incremental gc is used for applications such as GUIs where
responsiveness is important: it is more important for the program to
be responsive to external events than it is for it to run to
completion quickly.
c) Nodes are colored in three colors:
white: untouched by the gc
grey: touched by the gc, but the children have not
black: touched by the gc, and so have the children.
d) Baker's algorithm maintains:
i) black nodes (in to-space, not between scan and next) do not have
white children (in from-space)
ii) the gc has access to the list of all grey nodes (in to-space
between scan and next).
iii) the mutator (user code) does not have direct access to any
pointers to white objects.
e) The algorithm has:
i) when the mutator allocates a new object, it is created as a black
object at the bottom of to-space. When n bytes are allocated, we
forward at least n bytes of objects (advancing scan by at least n).
ii) when the mutator reads a field of a grey object, we forward the
child object (to make sure it is either grey or black, not white).
(This is called a read barrier,)
f) Baker's algorithm uses a read barrier, but if it is implemented in
software, then the read barrier is expensive. Appel, Ellis and Li use
the VM subsystem to mark each page containing grey objects with a read
barrier. Each time the page is read, all the objects on the page are
forwarded, and the read barrier is removed. Thus there is no extra
cost to regular execution, since the MMU hardware performs the
read-barrier.
7
Generational copying.