Description

• Please read all instructions (including these) carefully.
• There are 6 questions on the exam, some with multiple parts. You have 180 minutes to work on the exam.
TOTAL 120
• Please write your answers in the space provided on the exam, and clearly mark your solutions. Do not write on the back of exam pages or other pages.
NAME:
SIGNATURE:
Problem Max points Points
1 10
2 20
3 20
4 20
5 30
6 20
1. Type Soundness (10 points)
1 class A { };
2 class B inherits A{ foo() : Int {1}; };
3 class C { a : A <- new A; helper(t:A):A {a <- t};};
4 class D inherits C { a : B <- new B;
5 caller():Int {a.foo()};};
6 class Main {
7 d:D <- new D;
8 c:C <- d;
9 main(): Int {{
10 c.helper(new A);
11 d.caller();
12 }};
13 };
• On which line of code does this program crash when run? Explain why in no more than one sentence.
• Change one token in the program so that the modified program type checks using the unsound rule but runs successfully to completion anyway. Indicate your change directly on the code above.
2. Type Checking and Operational Semantics (20 points)
Below is a full specification for type checking attributes in Cool, including the complete definition of helper functions used by the type checking rules:
P(C) = The parent of class C.
Attr(C) = [a1 : T1,…,an : Tn] is the list of attributes textually declared in class C.
Extend(O,C) = O[Ti/ai] for every ai : Ti entry in Attr(C)
Context(Object) = ∅
Context(C) = Extend(Context(P(C)),C) if C 6= Object
OC = Context(C)
OC(x) = T0
O [SELFTYPE /self],M,C ` e : T
[Attr-Init]
OC,M,C ` x : T0 ← e1;
[Attr-No-Init]
(a) Attributes in Cool are protected, meaning they are visible to child classes but not outside of the class. A private attribute is visible only within the class where it is declared and is not visible even to child classes. We extend Cool with private attributes by using the syntax:
feature ::= private ID : TYPE[← expr]
Give modified type checking rules for private attributes. Show the definitions of any new or modified helper functions used by your rules.
(b) Give a succinct explanation for why no changes are required to the operational semantics of Cool to implement private attributes (i.e., at runtime private attributes are treated just like protected attributes).
3. Type Checking and Operational Semantics (20 points)
Consider adding pairs to Cool. A pair is a tuple of length 2 where the elements can have different types:
Type ::= … | (Type,Type)
expr ::= … | new (expr,expr) | first(expr) | second(expr)
A new(e1,e2) expression allocates and initializes a pair using the values of the two expressions e1 and e2. For an expression e that evaluates to a pair, first(e) evaluates to the first component of the value of e and second(e) evaluates to the second component of the value of e.
(a) Give type checking rules for these three constructs.
(b) Give operational semantics rules for these three constructs. Assume that pairs are a new kind of runtime value. If v1 and v2 are Cool values, then (v1,v2) is a pair value. Note that a value is not allocated in the heap—you don’t need to allocate memory locations to construct a pair value.
4. Optimization (20 points)
An important optimization that we did not discuss in class is method inlining: a function call is replaced by the body of the function. That is, given a method call
e1.f(e2)
and the definition of the method
f(x : T) : T 0{e3}
we replace the entire method dispatch by
let x : T ← e2 in e3
and thereby eliminate the method call. Now assume that to use method inlining for method f, we replace all calls to f by the body of f as outlined above. Also assume that we never do method inlining for a recursive method.
(a) How does method inlining make programs faster: What computation is saved by inlining?
(b) Name one cost of method inlining: How can it make programs worse?
(c) What are the best candidates for method inlining? That is, what characteristic(s) of methods indicate that the cost/benefit ratio of using method inlining is good for a particular method call?
5. Liveness and Register Allocation (30 points)
(a) Consider the following control-flow graph where the set of live variables at each point of the program are provided for you. Variable a is live upon entry and g is live upon exit. Listed from simplest to most complex, program statements can take one of the following forms: x = 1, x = y and x = y + z, where x, y, z are variables. Variables can be used more than once in a statement. Do not assign to dead variables.

a b c d e f g
a
b
c
d
e
f
g

(c) Using the graph coloring heuristic provided in lecture 16, give the smallest number of colors k that enables the heuristic to succeed without spilling. If there are multiple nodes that could be deleted from the graph, break ties first by selecting a node with the fewest neighbors and second by choosing the node whose label is first in alphabetical order. Using your provided k, give the state of the stack when all nodes have been deleted from the graph.
Value of k:
Top of stack (pushed last)

Bottom of stack (pushed first)
Register Variable
r1
r2
r3
r4
r5
r6
r7
6. Code Generation (20 points)
The following is a valid Cool program:
class Main inherits IO {
main() : Int {
let a: Int in {
a <- 1; while in_int() = 0 loop { a <- a * 3 + 1; out_int(a); } pool; a;
}
};
};
Below is MIPS assembly that implements this program, with some parts missing. We have also omitted the prototype objects and init labels since they are not needed to answer the question. Assume that Int(x) is the label of the integer constant x. Fill in the blanks (there are 5 lines in total) in the following assembly so that it correctly implements the program above.
Main_dispTab:
.word Object.abort
.word Object.type_name
.word Object.copy
.word IO.out_string
.word IO.out_int
.word IO.in_string
.word IO.in_int
.word # …
Main.main: Main.main
addiu $sp $sp
sw $fp 12($sp)
sw $s0 8($sp)
sw $ra 4($sp)
addiu $fp $sp 16
move $s0 $a0
la $a0 Int(1)
sw label0: $a0 8($fp)
move $a0 $s0
lw $t1 8($a0)
lw $t1 24($t1)
jalr $t1

sw $a0 )
la $t2 Int(0)
lw $t1 12($fp)
la $a0 bool_const1
beq $t1 $t2 label2
la $a1 bool_const0
jal label2: equality_test
lw $t1 12($a0)
beq $t1 $zero label1
lw $t2 8($fp)
sw $t2 12($fp)
la $a0 Int(3)
jal Object.copy
lw $t2 12($a0)
lw $t3 12($fp)
lw $t1 12($t3)
mul
sw $t1 12($a0)
sw $a0 12($fp)
la $a0 Int(1)
jal Object.copy
lw $t2 12($a0)
lw $t3 12($fp)
lw $t1 12($t3)
add $t1 $t1 $t2
sw $t1 )
sw $a0 8($fp)
lw $t3 8($fp)
sw $t3 0($sp)
addiu $sp $sp -4
move $a0 $s0
lw $t1 8($a0)
lw $t1 16($t1)
jalr $t1
b label1:
lw $a0 8($fp)
lw $fp 12($sp)
lw $s0 8($sp)
lw $ra 4($sp)
addiu $sp $sp 28
jr $ra