Name:

CSC548 Final exam: Spring 2000-2001

This is a closed-book, closed-note exam.

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Question 1 (15 points)

a) When is a program in SSA form?

b) When is a program in functional SSA form?

c) What is a phi-function?

c) Are phi-functions required by programs in SSA form? If so, provide an example. If not, explain why not.

d) Are phi-functions required by programs in functional SSA form? If so, provide an example. If not, explain why not.

e) Give one advantage and one disadvantage of functional SSA form compared to SSA form.

Question 3 (25 points)

Consider the following imperative program:

class C {
  method foo (n : Integer, m : Integer) {
    var x : Integer; x := n;
    var y : Integer;
    var z : Integer; z := 1;
    label outer : while (true) {
      x := x - 1;
      y := n;
      label inner : while (true) {
        z := z + 1;
        y := y - 1;
        if (x == 0) { break outer; } 
        else if (y == 0) { break inner; }
        else { continue inner; }
      }
      continue outer;
    }
    return z;
  }
}

This question asks you to convert this program into functional SSA form, and then to remove any resulting innner methods.

a) Remove imperative control-flow features, by replacing while-loops by inner method decalarations, and break and continue statements by inner method calls.

b) Remove imperative data-flow features, by adding extra parameters to inner methods to replace live imperative variables. The resulting program should be in functional SSA form.

c) Perform lambda-lifting, to remove the inner methods.

Question 3 continued

Question 4 (15 points)

Perform inline method expansion on the class C defined:

  class List {
    field hd : Integer; field tl : List; field sz : Integer;
    method cons (hd : Integer) : List { return new List { hd=hd; tl=this; sz=this.sz+1; } }
    method head () : Integer { return this.hd; }
    method tail () : List { return this.tl; }
    method size () : Integer { return this.sz; }
  }
  object empty : List { hd=0; tl=empty; sz=0; }
  class C {
    method foo (l : List) : Integer {
      if (l.size () > 0) { 
        let tmp1 : List = l.tail ();
        let tmp2 : Integer = foo (tmp1);
        let tmp3 : Integer = l.head (); 
        return tmp2 + tmp3;
      } else { 
        return 0;
      }
    }
    method bar () : Integer {
      return this.foo (empty.cons (1));
    }
  }

You should inline any method of 10 lines or less. You should not inline any function currently being inlined (to avoid infinite inlining of recursive functions). You should perform constant propogation, constant folding, and resolve constant conditions, where possible.

Question 4 continued

Question 5 (15 points)

Explain, with an example, how Cheney's copying garbage-collection algorithm works.

Question 5 cont.

Question 6 (25 points)

a) What is a generational garbage collection algorithm?

b) Why are generational gc alogithms used?

c) What is the remembered set for a generational gc algorithm?

d) How is the remembered set maintained?

e) What is the page marking algorithm for generational gc? Why is it used?

f) Give three ways in which a generational copying gc algorithm can improve cache performance of a program.

Question 6 cont.

Question 7 (5 points)

What was your favourite topic in this course? What was your least favourite? Which extra topic would you like to see covered?

Worksheet

You can use this sheet as scrap paper.

Worksheet

You can use this sheet as scrap paper.

Worksheet

You can use this sheet as scrap paper.

Worksheet

You can use this sheet as scrap paper.