Name:

CSC548 Final exam: Spring 2002-2003

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

Answer all questions.

Time allowed: 2 hours

Total number of points: 100

Question 1 (25 points)

a) When is a program in SSA form?

b) What is a phi-function?

c) Why are phi-functions necessary when translating a program into SSA form?

d) When is a program in functional SSA form?

e) What is a nested method?

f) Why are nested methods necessary when translating a program into functional SSA form?

g) 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) : Integer {
    let mutable x : Integer = 0;
    while (x > a) {
      let mutable y : Integer = x;
      while (y < b) { 
        y := y+a; 
      }
      x := x+y;
    }
    return x;
  }

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 method defined:

  class C {
    method foo (x : Integer) {
      method bar (y : Integer) {
        if (y < 10) {
          return inner.bar (y+x);
        } else {
          return y+1;
        }
      }
    }
    method baz () {
      let a : Integer = this:C::foo (1);
      let b : Integer = this:C::foo (a);
      return 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 (35 points)

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

b) Mark-sweep can be implemented using a constant amount of extra space by making use of pointer reversal. Explain this, with an example.

c) Mark-sweep requires the maintainance of a free list which has problems with fragmentation. Explain this, with an example.

d) A garbage collector can perform better with support from the compiler to provide descriptions of record layout and frame layout. Explain this, with an example.

e) Garbage collectors for languages such as C (where the compiler does not provide this support) use mark-sweep rather than copying. Explain why.

Question 4 cont.

Question 4 cont.

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