April 2018 Final Examination
EXAMINER:
Compiler Design COMP-520
14:00 – 17:00 April 30, 2018
Alexander Jacob Krolik ASSOC. EXAMINER:
INSTRUCTIONS
Prof. Clark Verbrugge
STUDENT NAME:
McGILL ID:
X
CLOSED BOOK OPEN BOOK
SINGLE-SIDED PRINTED ON BOTH SIDES OF THE PAGE
X
X
EXAM:
MULTIPLE CHOICE
Note: The Examination Security Monitor Program detects pairs of students with unusually similar answer patterns on multiple-choice exams. Data generated by this program can be used as admissible evidence, either to initiate or corroborate an investigation or a charge of cheating under Section 16 of the Code of Student Conduct and Disciplinary Procedures.
ANSWER IN BOOKLET EXTRA BOOKLETS PERMITTED: YES NO ANSWER ON EXAM
X
X
SHOULD THE EXAM BE: RETURNED KEPT BY STUDENT
CRIB SHEETS:
X
NOT PERMITTED PERMITTED e.g. one 8 1/2X11 handwritten double-sided sheet Specifications:
DICTIONARIES:
X
TRANSLATION ONLY REGULAR NONE
CALCULATORS:
X
NOT PERMITTED PERMITTED (Non-Programmable)
ANY SPECIAL INSTRUCTIONS:
Course: COMP-520 Compiler Design
Page number: 1 / 6
Q1. (20 points) Scanners and Parsers
In this question you will define a grammar for a simple programming language, Heffalump. A Heffalump program consists of a list of function declarations. Function declarations have an identifier, 0 or more parameters, and 1 or more return types (return types can be void or any value type). All types should be defined as keywords. Integers and floating point numbers may not have leading zeros, floating point numbers must have digits on both sides of the decimal, strings consist of letters and numbers only, and identifiers follow the typical definition we use in class.
The Heffalump language has statements and expressions. Statements can be assignment statements, function calls, return statements, block statements, an if-else statement (branches are blocks – state- ment lists enclosed by curly braces, and else branch is optional), or the call to a built-in function output. Blocks (and function bodies) may start with declarations, followed by zero or more statements.
Expressions can be ordinary arithmetic expressions defined using +, -, * and /, function calls, or type casts for converting between value types. Expressions should be left-associative and have the normal precedence. Unary minus is also supported and has higher precedence than subtraction. There is an additional operator ** which is used for specifying exponentiation (it has the highest precedence among binary expressions, and is right-associative). Parentheses can also be used in expressions.
Comments use the # style and should be ignored by the scanner. ***There is an example of a correct Heffalump program below.***
(a) (10 points) Give the specification of the scanner for this language using either flex or SableCC. (b) (10 points) Give an unambiguous LALR(1) grammar for the language in either bison or SableCC
without precedence directives. Do not provide actions for building the AST. fun main(s -> string) : void {
{
} }
0.0;
vark,kc-> output(“i=”+i,”k=”+k);
# declaration with optional expression
# comma-separated identifier list
# single assignment
# multiple assignment
# function call #outputbuiltin
# function with multiple return values
# function with multiple parameters
# typecast from int to float
# if-else statement
varf-> float = vari,j -> int;
f=1.0;
i, j = 0, 1;
fun cube(i -> int) : int, int {
return i, i ** 3;
}
fun div(n -> int, d -> int) : float {
var n -> float =
if n > 0 {
return (n – 1) / d;
} else {
return div(n * -1, d);
}
}
float = cube(i);
Course: COMP-520 Compiler Design
Page number: 2 / 6
Q2. (10 points) Typechecking
Consider the following correctly-typed example program written in a language with function calls, type casts, and user defined types.
float foo(int i) {
return i * 2.0
}
void main() {
typedef num = float
float a = foo(5)
num b = num(5)
}
(a) (5 points) Give the type inference rule for typechecking a type cast, assumming you have a utility function isCastable(src,dst). [Hint: your context consists of F,T,V where F is the set of functions, T is the set of defined types, and V is the set of variables].
(b) (5 points) Describe the following type inference rule for function calls in prose.
F,T,V `e1 :⌧1 ··· F,T,V `en :⌧n F (f ) = ⌧1 ⇥ · · · ⇥ ⌧n ! ⌧
F,T,V ` f(e1,…,en) : ⌧ Consider the following small JOOS program.
public class Tree {
protected int rings;
public Integer height(int mix) {
int i = 0;
int height = 0;
while (i < mix) {
height = (height - 2) * rings;
i++; }
return new Integer(height);
}
}
(a) (8 points) Show the bytecode code, in Jasmin format, for the height method. Be sure to indi- cate both the locals limit and the stack limit in the Jasmin code. Do not perform any aggressive optimization.
(b) (4 points) For each line of bytecode instructions, show the state of the expression (baby) stack.
(c) (3 points) The evaluation of JOOS expressions and statements in JVM bytecode must respect which invariants?
Q3. (15 points) Bytecode Generation
Course: COMP-520 Compiler Design Page number: 3 / 6
Q4. (10 points) Optimization
(a) (5 points) Consider the following sequence of JVM bytecode instructions.
iload_0
dup
aload_1
swap
putfield size I
pop
Provide a general peephole optimization that could be applied to reduce the size of the above code. Format your answer as transformation, using {x}, {y}, etc. for general operands. For example:
(b) (5 points) Consider the optimizations A and B on VirtualRISC code, where [. . . ] denotes some arbitrary sequence of instructions that follow.
iload_{x}
iconst_0
imul
=) iconst_0
Briefly justify why your pattern is sound, in general, by analyzing the state of the stack and locals.
mov R1, R3 mov R1, R3
_label: A _label: B
subR1,R3,R1 ==) subR1,R1,R1 ==) [...] [...]
Are either of these optimizations sound? Justify your answer.
Q5. (12 points) Native Code Generation
_label:
mov 0, R1
[...]
Consider the following small JOOS program and the corresponding bytecode instructions in Jasmin format.
public static int baz(int a, int b) {
int ret = 0;
if (a < b) {
ret = a * b;
}
return ret; }
.method public static baz(II)I
.limit locals 3
.limit stack 2
iconst_0
istore_2
iload_0
iload_1
if_icmpge _end
iload_0
iload_1
imul
istore_2
_end:
iload_2
ireturn
.end method
(a) (4 points) Provide the register and memory mapping for your locals, stack and scratch space using the fixed register allocation scheme with m = n = k = 2 (m registers for locals, n for stack locations, and k for scratch).
(b) (8 points) Generate the corresponding VirtualRISC code for part (a) by explicitly modelling the stack.
Course: COMP-520 Compiler Design Page number: 4 / 6
Q6. (10 points) Garbage Collection
(a) (5 points) Give the reference counts of the objects 1,2,3 at the 2 points indicated in the code below. Answer in your exam booklet, not on the exam paper
void f() {
Object a = new Object(1);
Object b = new Object(2);
Composite c = new Composite(a, b);
{
a=b
// (i) GIVE THE REFERENCE COUNTS FOR OBJECTS 1,2 AT THIS POINT Object b = new Object(3);
c = new Composite(a, b);
}
// (ii) GIVE THE REFERENCE COUNTS FOR OBJECTS 1,2,3 AT THIS POINT
}
(b) (5 points) Consider the following states for a stop-and-copy garbage collector. Both the initial state and the first forward have been illustrated. Draw the next forward that will execute. Be sure to update the scan and next pointers. Answer in your exam booklet, not on the exam paper
Course: COMP-520 Compiler Design Page number: 5 / 6
Q7. (8 points) Special Topics
(a) (4 points) In modern GPU architectures, global memory access latency is very high, making it an important target for optimization. Given a memory transaction size of 2 elements, which access pattern below results in the lowest number of accesses? Justify your answer by providing the total number of memory transactions in both cases.
(a) (b)
(b) (4 points) In WebAssembly, the ISA (instruction set architecture) must be validated before execution. Describe 2 properties that are checked during the validation phase.
Q8. (15 points) GoLite Project
(a) (1 point) Give your implementation platforms (C/flex/bison, Java/SableCC, or whatever you are using) and your git group number.
(b) (4 points) In GoLite, switch statements may omit their switch expression. Describe the semantics of this form of switch statement, and give the output of the program below.
package main
func main() {
switch {
} }
case true:
println("true")
default:
println("default")
(c) (5 points) Describe how your code generation phase ensures the semantics you described in part (b) are correctly implemented in your target language.
(d) (5 points) Discuss your selection of target language, and the advantages/disadvantages that came with this choice.
Course: COMP-520 Compiler Design Page number: 6 / 6