[bitc-dev] Closure conversion

[Jonathan S. Shapiro]

Right now, BitC is excessively conservative about closure conversion. In
particular, we lift all loops into actual procedures. The idea was that
they would get re-inlined, but because of the way we are currently
building procedure objects, GCC isn't smart enough to do that.

So the question is: when can we avoid hoisting an inner procedure -- or
what can we do that will let GCC put it back in-line for us.

There are two cases:

  1. When the closure of the inner procedure contains only global
     references. In this case the closure may be treated as empty.
     We already do this, and in this case GCC can successfully inline
     the hoisted procedure.

  2. When the closure of the inner procedure contains no new elements
     in comparison to the closure of its containing procedure. In
     this case we can re-use the existing closure of the containing
     procedure and no new closure needs to be fabricated. As long
     as this is true we don't need to create a procedure object and
     we can rely on GCC to re-inline the hoisted procedure for us.

The second case is one that we are not currently checking. The reason is
that it leads to garbage aliasing if the inner procedure escapes. In
particular, if the containing procedure's closure captures (a, b, c),
but the inner procedure's closure only captures (a, b), then "c" will
remain reachable (according to the collector) for as long as the inner
procedure is live.

In the case of loops it is easy to show that these inner procedures do
not escape: we are introducing the procedure ourselves, and we know this
by construction.

In the case of general inner procedures, escape analysis appears to be
required. This can be conservative. For example, if we can show that the
return type of the procedure does not (deeply) contain any field of
procedure type, and we can further show that the lambda form does not
appear (transitively) as a value on the right hand side of any SET! or
LET form, we know that the procedure does not escape.

This may be sufficient in practice.

Swaroop: reactions?