Name:

CSC548 Final exam: Spring 2001-2002

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

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Question 1 (20 points)

a) When is a program in SSA form?

b) When is a program in functional SSA form?

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

d) Functional SSA form requires intoducing nested methods. Give two ways that code generation for nested methods can be implemented. Give one advantage and one disadvantage for each implementation.

Question 1 continued

Question 2 (20 points)

a) Convert the following method to SSA form, introducing phi-functions where necessary:

  method foo (a : Integer, b : Integer) {
    var x : Integer; x := a;
    var y : Integer; y := b;
    do {
      y := y*x;
      x := x-1;
    } while (x > 0);
    if (y < 0) {
      y := -y;
    }
    return y;
  }

Question 2 continued

b) Convert the same method into functional SSA form, introducing nested methods where necessary.

Question 3 (15 points)

Perform inline method expansion on the class C defined:

  class C {
    method foo (x : Integer) {
      if (x > 10) {
        let a : Integer = this::C.bar (x);
        return a*x;
      } else {
        return x;
      }
    }
    method bar (y : Integer) {
      let b : Integer = y/2;
      return this::C.foo (b);
    }
  }

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 3 continued

Question 4 (15 points)

a) Explain, with an example, how reference counting garbage-collection algorithm works.

b) Reference counting is not implemented by most modern run-time systems. Give a one- or two-sentence explaination of why not.

Question 4 cont.

Question 5 (25 points)

A garbage collector can gain significant performance benefits if it has hardware support from the Memory Management Unit (MMU). The MMU can provide either read barriers or write barriers.

a) What is a read barrier? What is a write barrier?

b) Explain how an MMU which provides write barriers can be used to improve the performance of a generational garbage collector.

c) Explain how an MMU which provides read barriers can be used to improve the performance of an incremental garbage collector.

Question 5 cont.

Question 6 (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.