This page includes questions by the instructor (John Boyland) and others. At least one of the questions will appear on the third midterm. All but one of the questions will be at least similar to a question here.
The following review questions from the (new) textbook may appear on the midterm:
Calculate the method and attribute offsets for the following program:
class A : IO is
A(initx : Integer, inity : Integer) begin ... end;
x : Integer;
y : String;
type_name() : String := ...;
getx() : Integer := ...;
gety() : String := ...;
z : Boolean;
testz() : Boolean := ...;
in_int() : Integer := ...;
end;
class B : A is
B(x : Integer, y:Integer, z : Integer) : A(x,y) begin ... end;
a : String;
testz() : Boolean := ...;
seta(s : String) : Object := ...;
geta() : String := ...;
copy() : Object := ...;
end;
class Main : IO is
Main() begin ... end;
a : Integer;
seta(i : Integer) : Object := ...;
geta() : Integer := ...;
b : Boolean;
copy() : Object := ...;
end;
class Object is -- from basic classes
Object() native;
abort() : Object := ...;
type_name() : String := ...;
copy() : Object := ...;
equals(other : Object) := ...;
end;
class IO is -- ditto
IO();
out_string(s : String) : IO := ...;
out_int(i : Integer) : IO := ...;
in_string() : String := ...;
in_int() : Integer := ...;
end;
Evaluate the Homework #8 attribute grammar [provided in exam] for computing offsets on the tree for the following method body. Draw the tree and decorate each node with its reg and max attributes:
let
x : Integer := y*y+4;
in
case a.f(i+3) of
when y:Integer => y+x
when z:Object => z.type_name().length()
esac <= 4
end
try again with
let x : Integer := 0; in
while x < 10 loop
if x = 1 then x := x*2
else x := x + 2 endif
pool
end
Write the rules for computing temporaries for array access and array update as in a[i+1] := a[i] + 1 Suppose the APS constructors are of the following forms and that the expressions are evaluated left to right:
constructor array_access(array,index:Expression) : Expression constructor array_update(array,index,new_value:Expression) : Expression(Trees built using these constructors have two and three expression children, respectively.) The array_update nodes subsume the assignment: assign nodes are only used for assigning single variables, not array elements.
Give the attribute grammar rules for these constructors to compute the number of temporaries required: reg is an inherited attribute, max is a synthesized attribute:
array_access(array,index:Expression) ; Expression array.reg = ... index.reg = ... max = ... array_update(array,index,new_value:Expression) : Expression array.reg = ... index.reg = ... new_value.reg = ... max = ...Apply your rules to the tree for the following expression:
a[i := i+1] := x + x * y / 10 - y
Write an attribute grammar for expressions that computes whether an expression could possibly be void. (Assume all parameters and local variables could be void; self is never void.) Use a single synthesized attribute maybeVoid which is true or false. Such an attribute grammar could be used to avoid the need to test whether the receiver object of a dispatch was void.
Suppose we tried to do better with local variables and case-bound variables. For example in
let io : IO := new IO; in ... endio is not void. What would we need to be careful of?
Given the expression x+(y+(z+(t+u))), how many temporaries are needed? Is there any way to minimize this number? Without changing the evaluation order? What if the operations were all - (subtraction) ?
The reference Cool compiler produces a lot of redundant and slow code for simple expressions like a+b, x*(1-x) etc. Why is it difficult to generate smart code for cases like this?
If we have an expression such as x + very complex expression, it would use fewer temporaries if we evaluated the very complex expression first and then fetched x. Why can't the Cool compiler always do this?
In the code generator for Cool, we had to copy an integer before adding it to another integer. The C++ compiler never does this. Why did we need to? In what situations (give at least one general case) could an optimizing Cool compiler avoid a copy without introducing bugs? (Don't assume that the integer can be unboxed.)
What purpose do the prototype objects have in the Cool compiler? Do they ever get changed?
In an object-oriented language (such as Cool), one method may override another. For a method call such as x.foo(), the compiler is unable to determine exactly what method body will be called at runtime. How does the compiler nonetheless arrange to have the correct method called?
Describe one of the two ways the Cool code generator can arrange for the most specific branch of a case to be selected. Give an example. Why does this method work?
An optimizing Cool compiler (or at least one that didn't always assume the worse case) would make better use of registers. Sketch an idea for using registers to hold temporary values. Your solution should mention whether scratch registers (AKA caller saved) should be used (that may be overwritten in a call) or saved registers (that then must be saved in our method prologue).
Consider how to implement array update in Cool inline, rather than calling Array.set_item. Assume you have an array_update node with three children: array, index and expr. Show the code that should be generated with blank boxes where the code for the three children should be generated. You may write pseudo-assembly code or MIPS code as you wish. Remember that the result of any expression should be evaluated into $a0. Make sure to handle the cases that the array is void, or the index is out of range.
Schedule the following instructions to avoid the stall due to a load delay (assuming a load delay of 1 clock cycle). Explain your reasoning (dependencies, etc.).
r2 = r1 + 3
r1 = A # load
r3 = r2 + r1
r2 = 5
Write a Cool program whose output will almost certainly be different if there are any mistakes in the code generation of subtraction. Make sure to test the temporary calculations and code generation (including spilling, copying, correct evaluation order and correct operation). You may assume that the rest of the compiler is correct, but it is fine if your code also detects bugs elsewhere.