Name:

CSC548 Final exam: Practice exam

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Question 1 (5 points)

Give one advantage and one disadvantage of converting an imperative program into functional SSA form.

Question 2 (10 points)

a) When is a program in SSA form?

b) What is a phi-function?

c) When converting a program to SSA form, when are phi-functions necessary?

d) Provide an example to illustrate your answer to part c).

Question 3 (25 points)

Consider the following imperative program:

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

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 following program:

  class C {
    method foo (x : Integer) : Integer {
      if (x > 0) { 
        let tmp1 : Integer = x-1; 
        let tmp2 = this.foo (tmp1);
        return tmp2 * x;
      } else { 
        return 1;
      }      
    }
    method baz (x : Integer) : Integer {
      let tmp : Integer = x * x;
      return this.foo (tmp);
    }
  }

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).

Question 4 continued

Question 5 (15 points)

Explain, with an example, how the mark-sweep garbage-collection algorithm works.

Question 5 cont.

Question 6 (25 points)

a) What is an incremental garbage collection algorithm?

b) Why are incremental gc alogithms used?

c) What is a three-color gc algorithm?

d) What invariants does Baker's algorithm maintain?

e) How does Baker's algorithm maintain these invariants?

f) How does Appel, Ellis and Li's algorithm use the virtual memory system to improve the efficiency of Baker's algorithm?

Question 6 cont.

Question 7 (5 points)

If you were to implement a programming language, what garbage collection mechanism would you use?