stack/heap analysis, closures, stack caches

Mitchell Wand writes:
>At the risk of being repetitious, let me remind people that
>continuation-based compiling does NOT imply heap-based allocation. It is
>perfectly fine to do continuation-based compiling and still do analysis to
>put whatever you can on a stack.


This is quite right. I probably should have made it clear that our
(Scheme) system uses heap-based binding environments continuations as
necessary. Both are initially allocated in a small (usually 4KB) stack
cache area. If code captures a binding environment, i.e. when creating a
closure, the captured environment is copied to the heap (environments it's
nested in may also have to be copied). Subsequent closure creations in
the same environment just share it by taking a pointer to the heap-
allocated environment.


Continuations are copied to the heap when code executes call-with-
current-continuation. Both continuations and environments are flushed to
the heap if the cache fills up, which isn't often, because stacks have
good locality on the scale of KB.


(This is the Rees-Rozas-Kelsey stack cache I'm talking about. I think
Richard Kelsey wrote a paper about it a while back, but I don't know its
current status.)


We've found this to be very effective---we now have lots more "real" data
on the heap than continuations and environments. It used to be the other
way around, as I said in a previous posting.


>In particular, in the absence of call/cc and the like, continuations
>(activation records) can ALWAYS be stack-allocated. Heap allocation is
>only necessary for environments (closures), even if your compiler is
>arbitrarily stupid.
>
>With slightly more effort, you can do an escape or closure analysis to
>determine when a closure has dynamic extent, so you can allocate it on the
>stack. Steele's RABBIT compiler (ca 1977) and Kranz et al's ORBIT
>compiler (ca 1986) both do this.


Our compiler (written mostly by Jonathan Rees and Richard Kelsey) is
intentionally pretty simple, and it only does a teeny bit of analysis; it
relies on the stack cache to do the rest. The analysis consists of
inlining trivial lambda combinations (i.e., procedure creations where you
never do anything with the procedure except call it) and converting very
simple tail recursions into inline loops. Both of these are trivial
little syntactic hacks, with no real data- or control-flow analysis. This
is considerably easier to implement than the "escape analysis" of Kranz et
al. In fact, it can allocate LESS stuff on the heap, because only
closures that are actually created cause copying of captured environments
into the heap. (We don't have to pessimistically heap allocate everything
that MIGHT need to be on heap.)


      -- PRW


| Paul R. Wilson, runtime environmentalist email: wilson@cs.utexas.edu
| U. of Texas Computer Sciences Dept. voice: (512) 471-9555
| Taylor Hall 2.124, Austin, TX 78712-1188 fax: (512) 471-8885
--

Return to the comp.compilers page.
Search the comp.compilers archives again.