Assignments for COM 3356
Spring 1996

[ Assignment #1 | Assignment #2 ]

Add closure analysis, as described below, as a new pass for your quirk13 compiler. This pass precedes the code generation pass.

Closure analysis operates on a type-checked abstract syntax tree in which all variables have been renamed so that no variable is bound in more than one place. Its purpose is to collect information that will allow the code generator to allocate variables on a stack instead of a heap, and to avoid allocating closures for known procedures whose extent is bounded by the extent of the block in which they are declared.

Definition: A function expression that occurs within a quirk13 program is said to escape if any of the following are true:

• The function expression is not the right hand side of a declaration.
• The function expression is the right hand side of a declaration of some variable f, but f is mentioned in one or both of the following ways:
  • outside the operator position of a call
  • within a function expression that escapes

Closure analysis marks all of the function expressions that escape and computes the set of free variables that are mentioned within each function expression that escapes. This can be done in one pass over the abstract syntax tree, followed by the computation of a transitive closure. The pass

• computes the set of free variables for each function expression,
• computes a list of all the function expressions
• computes a list of all the declarations whose right hand side is a function expression
• marks every function expression that is not the right hand side of a declaration
• marks every variable that occurs outside of call position

Following the pass, a transitive closure is computed by

• marking every variable that is referred to by a marked function expression
• marking every function expression that occurs as the right hand side of a declaration of a marked variable

Submit the following items by electronic mail to will@ccs.neu.edu.

• Your full name.
• A shar archive containing the new code you wrote for this assignment. Please do not include code for the rest of your compiler.

COM 3356 Assignment #2.
Assigned: Wednesday, 3 April 1996
Due: Wednesday, 24 April

Change your code generator to exploit information obtained by the closure analysis you wrote for assignment #1.

There are many different ways to do this. We will cover some of them in class.

Test your technique on a variety of quirk13 programs, and record the performance of those programs both with and without closure optimization. (An easy way to disable closure optimization is to perform the closure analysis as usual, but to mark all function expressions and variables afterwards as though they escape.)

Submit the following items by electronic mail to will@ccs.neu.edu.

• A short description (one-half to two pages) of the technique you used for closure optimization.
• A table of your benchmark results, both with and without closure optimization.
• The MIPS code your optimizing compiler generates for /course/com1355/Quirk13/Q13code/fib.q.