Closure analysis

Here are some data that can be used to check the closure analysis of Assignment #1.

Program     Function Expressions   Escaping   Variables
-------     --------------------   --------   ---------
adt.q                  15             12          53
array.q                 2              1           9
binarytree.q           24             14          75
fact.q                  1              0           4
fib.q                   2              0           9
permute.q              12              7          30
polymorph.q             1              1           2
primes.q                5              4          16
quicksort.q            22             11          63
rev.q                   8              0          28
selectionsort.q         7              1          30
small0.q                0              0           1
small1.q                0              0           2
small2.q                0              0           1
small3.q                0              0           5
small4.q                0              0           5
small5.q                0              0           4
small6.q                0              0           4
small7.q                0              0           4
small8.q                0              0           8

Let's take a closer look at primes.q. This program contains 5 function expressions and 16 variables:

    divides_1       in_9
    x_2             k_10
    counter_3       result_11
    filter_4        in_12
    primes_5        max_13
    max_6           next_14
    a_7             read_int
    b_8             write_int

--
--  primes.q with explicit function expressions
--

{
  proc (int, int) -> bool divides =
    -- escapes
    -- free: { }
    function (int a, int b) -> bool {
      (b/a) * a = b
    };

  ref int x = new 1;

  proc () -> int counter() =
    -- escapes
    -- free: {x_2}
    function () -> int {
      x := x + 1;
      x
    };

  proc (proc () -> int, int) -> proc () -> int filter =
    -- escapes
    -- free: {divides_1, filter_4}
    function (proc () -> int in, int k) -> proc () -> int {
      -- escapes
      -- free: {divides_1, filter_4, in_9, k_10}
      function () -> int {
        int result = in();
        if divides (k, result)
          then (filter (in, k)) ()
          else result
        }
    };

  proc (proc () -> int, in) -> string primes =
    -- does not escape
    -- free: {filter_4, primes_5, write_int}
    function (proc () -> int in, int max) -> string {
      int next = in();
      write_int(next);
      if next < max
        then primes (filter (in, next), max)
        else "done"
    };

  int max = read_int();

  primes (counter, max)
}

You have many choices for Assignment #2:

1. Optimize first order programs, but don't optimize if any function expression escapes.
2. Optimize first order programs, and make special allowances for procedures that are passed to newarray.
   • Allocate all variables on the stack, and allocate a stack closure for every function expression; or
   • Compile as in Pascal.
3. Allocate variables on the stack if possible, but allocate a heap closure for every function expression.
4. Allocate variables on the stack if possible, and allocate a heap closure only for those function expressions that escape.
5. Use lambda lifting to remove free variables from function expressions that do not escape; allocate a heap closure for those that do escape.

I implemented three levels of optimization:

;
; (qopt 0):  No optimization.
;
; (qopt 1):
;
; Performs passive first order closure analysis to:
;   find all function expressions;
;   compute their free variables;
;   mark all function expressions that escape;
;   mark all variables that occur free in any function
;     expression.
; Doesn't allocate a rib for blocks with no declarations.
; If none of the variables declared at the head of a block
;   escapes, then they are allocated on the stack.
; Allocates formal parameters on the stack.
; Closes all function expressions by copying their free
;   variables into the closure (or the rib containing the
;   free variable, if it resides in a heap-allocated rib).
;
; (qopt 2):
;
; Closure analysis marks only those variables that occur
;   free in a function expression that escapes.
; Variables that name function expressions that do not
;   escape are marked as known.
; Function expressions that do not escape are not closed.
; Calls to known functions are compiled as in Ada83.

Lambda lifting

If a function expression occurs as the right hand side of a declaration of some variable f, and f occurs only in call position, then the compiler can locate all calls to the procedures that will result from evaluating the function expression.

Let's call f a known procedure, because the compiler knows exactly where f is called.

Lambda lifting is an optimization that

1. moves the declarations of known procedures to the outermost (global) block of a program,
2. adds their non-global free variables as new formal parameters, and
3. changes every call to a known procedure to pass its non-global free variables.

The primes.q program contains three known procedures: divides, filter, and primes. All three are already declared at the outermost block. That means they have no free variables, so lambda lifting is trivial.

Gambit

Twobit