Simula front-end: Heap-allocated activation records

["Knut Aksel Røysland" <knutroy at ifi dot uio dot no>]

Hi!

I am trying to develop (or at least do the initial planning and
development of) a Simula front-end to GCC. The concern giving me the
most headaches nowadays, is the existence of coroutines in Simula and
its implications on how to utilize the run-time stack.

Generally, coroutines implies that activation records cannot be stored
on a global stack because program flow does not necessarily cause them
to be allocated and freed according the LIFO-pattern of a stack.

The implementation I envision, will thus allocate activation records
on heap upon entering routines. These records will then be used to
hold return address, static link, dynamic link, local variables and
temporaries of the corresponding routine, thereby relieving the
run-time stack of all of its traditional responsibilities.

This scheme will of course cause a penalty in efficiency when there
are no coroutines (so that the stack actually could have been used).
For now, I disregard that issue.

This is, in short, how I plan to perform procedure/function entries:

    * allocate an activation record of compile-time-calculated size
    * store return address (found on stack or in global variable) in
      activation record
    * ditto for static link and dynamic link
    * initialize local variables
    * ...

The critical points, wrt. not having anything important on the stack,
are the places where other routines are being called (which in turn
may yield control to another coroutine, hence potentially clobbering
the stack):

    * ...
    * make sure all live temporaries are stored in the activation
      record
    * perform call
    * ...

Other than across routine calls, the stack is a safe place for
temporaries (coroutines being predictably cooperative, not
preemptive).

Procedure/function exits will look something like this:

    * ...
    * retrieve dynamic link and static link
    * retrieve return address
    * free activation record
    * return to or go to return address


And so I reach the point of deciding how to implement this, bringing
me to this mailing list.

My primary concern is not how I redirect "local variables" to residing
on the heap, but rather how I make temporaries end up in a
heap-allocated activation record.

I have a few alternative methods in mind:

1) The front-end inserts extra nodes in the expression trees, much
   like gcc/java/expr.c:force_evaluation_order does to force
   left-to-right evaluation of Java expressions. (Simula also requires
   this btw.) This could be a combination of a SAVE_EXPR and a
   MODIFY_EXPR - the latter ensuring that the target for the temporary
   is in the heap-allocated activation record.

2) The front-end involves itself in the expansion of RT-expressions,
   inserting necessary code to store away temporaries. In both of
   these two first cases, the front-end will keep track of the maximum
   required space of temporaries.

3) Using some magic, the front-end instructs the back-end, that all
   stack slots should actually be allocated on heap using a
   run-time-provided base address. This also requires that the
   back-end can be inquired of the maximum size of this area.

   On second thought, this approach may actually result in
   unnecessarily large activation records, as the maximum usage of
   temporaries may actually be somewhere else than across a routine
   call, which means that the stack may be utilized as well.

Any comments and suggestions on how to proceed are greatly
appreciated.

At least under approaches 1 and 2, I will also need to generate code
to pick up the return address and put it in the heap-allocated
activation record. Not being too intimate with GBE just yet, I could
use some good instructions on that as well.

Suggestions on alternative approaches to the design of a
coroutine-aware run-time system, are of course also welcome.


TIA

--
Knut Aksel Røysland