\section{Target Machine Code Generation}
\label{Section:Target Machine Code Generation}

The tree-structured intermediate TML code generated so far is easy to
re-write (by the optimizer), but cannot be executed efficiently.  We
need some linear program representation that is easy to process by some
(real or abstract) target machine.

Currently, we have implemented a code generator for a stack-based
abstract machine (TVM, {\em Tycoon Virtual Machine}) using byte-coded
instructions, and an experimental ANSI C code generator. We will sketch
the C code generator at the end of this section in order to discuss the
major topics. But before the code generator is called, three additional
passes are made through the TML tree: exception conversion, environment
analysis and closure conversion. These passes simplify the task of the
code generator by rewriting the TML tree into a form more biased towards
stack-based target machines.

\subsection{Exception Conversion}
\label{Section:Exception Conversion}

The exception conversion pass removes the exception continuation argument from
every \p{proc} abstraction and application and inserts an appropriate sequence
of calls to the primitive procedures \p{pushHandler} and
\p{popHandler}. This isolates the target code generator from exception
handling details.

The primitives \p{pushHandler} and \p{popHandler} maintain a runtime stack of
exception handlers (cf. section \ref{Section:Exceptions}).  These exception
handlers are represented in TML as continuations that receive the exception
object as an argument. At the target machine level, these continuations will
be represented as assembly language labels. A \p{pushHandler} call will push
the value of this label (i.e. a code pointer) onto the exception handler
stack, and a corresponding \p{popHandler} call will eventually remove it. If
an exception is raised, control will be transferred immediately to the continuation
on top of the exception handler stack.

In the following example, an exception handler is bound to the
continuation variable \p{e}. Subsequently, the exception \p{intError} is
raised by passing a newly created exception object to the exception
handler bound to \p{e}. This handler is also passed in a nested call to
the procedure \p{p}.  The exception handler itself issues a \p{reraise}
statement after processing the exception in the statement \p{D}. After
exception conversion, the exception continuation argument to the
procedure call is removed and passed implicitely on the exception
handler stack:


\xbegin
\k{proc}(ce cc)
 ($\lambda$(e)
      \mv{A}
      (vector intError \k{cont}(err)
      (e err))      ; raise \p{err}
      \mv{B}
      (p e cc)      ; call \p{p}
      \mv{C}
   \k{cont} (exc) ; handler \p{e}
     \mv{D}          
     (ce exc)       ; reraise \p{exc}\xmiddle{}
\k{proc}(cc)
  ($\lambda$(c e)
       (pushHandler e \k{cont}()
       \mv{A}
       (vector intError \k{cont}(err)
       (raise err))
       \mv{B}
       (p c)       ; call \p{p} (no exception argument any more)
       \mv{C}
    \k{cont}(t)       ; continuation \p{c}
      (popHandler \k{cont}()
      (cc t))
    \k{cont} (exc)    ; handler \p{e}
      \mv{D}
      (raise exc))    ; reraise \p{exc} \xend

      
%\subsection{Cell conversion}

%\vbox{

%The cell conversion pass removes all destructive assignments to
%variables and replaces them by explicit manipulation of the store
%through primitive procedures:

%\xbegin
%((lambda (x)
%    (:= x 99
%      (cont () \dots x\dots)))
%  77)\xmiddle{}
%(array 77
%   (cont (x)
%     (\arrayset{} x 0 99 (cont ()   ; value assignment
%     \dots
%     (\arrayget{} x (cont (v)           ; value extraction
%     \dots v\dots)))))) \xend}


\subsection{Environment Analysis and Closure Conversion}
\label{Section:Environment Analysis and Closure Conversion}

Similar to Scheme \cite{Stee86} and ML \cite{MTH90}, the Tycoon
language TL and its intermediate representation language TML are block
structured languages with functions (procedures) as first class
values. In such a language, a function \p{f} may be lexically nested
within another function \p{g}. Function \p{f} may access its formal
parameters and local variables, but it may also reference a variable
\p{v} defined in the lexically enclosing function \p{g}. We say that \p{v} is a
{\em bound} or {\em local} variable with respect to \p{g}, and a {\em free} or
{\em global} variable with respect to \p{f}:

\xbegin
\lll{}\k{let} g(v :Int) = \k{begin}
  \k{let} f() = v
  f
\k{end},
cc,
ce\ggg\xmiddle{}
($\lambda$(g) (cc g)
  \k{proc}(v e c)            ; function \p{g}
    ($\lambda$(f) (c f)            ; return the value of \p{f}
      \k{proc}(e c)           ; function \p{f}
        (c v)))            ; return the value of \p{v} \xend


The Tycoon compiler has to generate efficient code for this kind of
variable access. The task of the compiler is further complicated by
the fact that the lifetime of \p{v} bound in function \p{g} may exceed the
activation of \p{g}, since function \p{f} may be stored in data structures and
be applied later, after the enclosing function \p{g} has already
returned. Therefore, the values of free variables cannot be allocated
on the stack, but must be allocated on the heap. 

In the Tycoon system, the runtime representation of a function value is a
heap data structure called a {\em closure record}.  A closure record is
essentially an array containing a pointer to the executable code of the
function, and the value of each free variable referenced in the body of the
function. The executable code knows the position of each free variable within
the closure record. This is the {\em flat closure} approach to function
representation \cite{App92}. Flat closures trade closure creation time for
fast access of free variables.  This is important in persistent object systems
where object slot access typically imposes some overhead
\cite{Math92}.

The flat closure approach requires that variable values may be copied freely
and spread out into multiple locations. This is possible in TML since
variables are never modified once they are bound. During TML code generation,
any references to mutable TL variables have been cell-converted into explicit
operations on the store (see section \ref{Section:L-Value Bindings}).

The {\em environment analysis} pass of the Tycoon compiler determines the set
of free variables for each \p{proc} abstraction, and allocates a slot within
the closure record for each. This pass also identifies references to
literal objects that cannot be represented directly within the byte sequence
of the executable code, but must be fetched from the heap at run time.  A slot
within the {\em literal vector} of the function is allocated for such an
object. To illustrate this, the above example function \p{f} is slightly modified
to return a pair consisting of the global variable v and a literal string
object:

\xbegin
\lll{}let g(v :Int) = \k{begin}
  \k{let} f() =
    \k{array} v "string literal" \k{end}
  f
\k{end},
cc,
ce\ggg\xmiddle{}
($\lambda$(g) (cc g)
  \k{proc}(v e c)                  ; function g
      ($\lambda$(f) (c f)
        \k{proc}(e c)              ; function f
          (array v "string literal" c))) \xend

Following environment analysis, the {\em closure conversion} pass
removes every reference to free variables by explicit closure
allocation, passing and access ({\em Closure Passing Style}
\cite{App89}). This isolates the later passes from closure format
details.

At runtime, each function will receive it's closure record as
an additional parameter, making the stored free variable values
accessible to the executable code.  Moreover, every reference to a
literal object is translated into an indexed access to the literal
vector.  The runtime representation of \p{f} is depicted in figure
\ref{Fig:Closure Representation}. We say that the resulting TML code 
is {\em closed} because it does not contain any free variables any
more:


\xbegin
($\lambda$(g) (cc g)
  \k{proc}(v e c)                ; function g
   ($\lambda$(f) (c f)
     \k{proc} (e c)              ; function f
       (array v "string literal" c))) \xmiddle{}
(array                           ; create closure record for g
  \k{proc}(env v e c)             ; function g
    (array                       ; create closure record for f
       \k{proc}(env e c)          ; function f
        (\arrayget{} env 1 \k{cont} (t1)  ; fetch value of v into t1
        (\arrayget{} env 0 \k{cont} (t2)  ; fetch literal vector into t2
        (\arrayget{} t2 1 \k{cont} (t3)    ; fetch string literal into t3
        (array t1 t3 c))))     ; return array 
      v                           ; free variable value
      c)
  cc)\xend

\begin{figure}[b]
\epsfbild{closure.epsf}{\epsfxsize=0.6\columnwidth}
\label{Fig:Closure Representation}
\caption{Closure Representation}
\end{figure}

Traditionally, the formal parameter for the closure record is given the name
\p{env} because it actually contains the {\em lexical environment} of the
function at the time the closure was created, i.e. at the time the TL source
code of the function was evaluated. Note that function \p{g} does also receive
a closure record even though it does not contain any free variables. This is
necessary because g may be called from sites that do not know this property of
\p{g}. Therefore, the standard Tycoon calling sequence must be used, passing
an explicit closure record.

A somewhat more complex translation scheme is necessary for the closure
conversion of mutually recursive function bindings in an application of
the \p{Y} primitive. Essentially, additional TML code is generated that,
after all closure records have been created, patches each closure record
with the references to the closure records of all the other
functions. This code generation actually implements the semantics of the
\p{Y} primitive, i.e. it {\em computes} the least fixed point, a vector
of mutually recursive functions.

\subsection{Generating ANSI C Code}
\label{Section:Generating ANSI C Code}

After all the processing described in the previous sections,
C code generation is almost a trivial task.  Since there are no more free
variable references, each \k{proc} abstraction can be translated
separately into an equivalent C language function, and continuations
are 'flattened out' by translating them into a label followed by C
code implementing the body of the continuation.  References to
continuation variables are translated into C language gotos,
optionally preceeded by an assignment of the continuation argument to
a temporary variable.  Live variable analysis as described in
\cite{Wulf73,Gawe92} helps reducing the number of temporary
variables actually needed\footnote{Since this optimization is usually
done by optimizing C compilers anyway, we have not implemented it as a
part of the C code generator.}.

Note that the last argument of a \k{proc} abstraction
(user level procedure) is always the continuation
argument:

\xbegin
\k{proc} (x y c)
  ($\lambda$(c2)
       \dots{}(c2 88)\dots
    \k{cont}(t)
      (c t))\xmiddle{}
\tspoid{} f(\tspoid{} x, \tspoid{} y)
  \{
  \tspoid{} t;
  \dots
  t = MAKE\_INT(88);
  \k{goto} c2;
  \dots
c2:
  \k{return} t;
  \} \xend


Ordinary bindings are translated into local blocks:

\xbegin
($\lambda$(x y) \dots
  88
  99)\xmiddle{}
\{
\tspoid{} x = MAKE\_INT(88);
\tspoid{} y = MAKE\_INT(99);
\dots
\} \xend

Procedure calls are translated into C language function calls,
storing the result in the temporary variable allocated for the
continuation, and passing control to the continuation:

\xbegin
(f x y c)\xmiddle{}
\tspoid{} t;
\dots
t = f(x y);
\k{goto} c; \xend

The translation of calls to primitive procedures is fairly straightforward
using equivalent C language expressions and/or appropriate runtime system
calls.

As an example, consider a call to the primitive procedure '\p{==}'. If all the
values of the different branches are simple integer constants (or can be
encoded as such, like character values), the C language \p{switch} statement
can be used. C compilers typically generate very efficient code (jump tables)
for this kind of statement:

\xbegin
(== x
  1  2  3  4  5
  c1 c1 c2 c2 c2
  c3) \xmiddle{}
\k{switch} (x)
  \{
  \k{case} 1:
  \k{case} 2:  \k{goto} c1;
  \k{case} 3:
  \k{case} 4:
  \k{case} 5:  \k{goto} c2;
  \k{default}: \k{goto} c3;
  \} \xend

If some of the branch values are object identifiers, a cascaded \p{if}
statement must be used, fetching the object identifiers form the literal
vector of the current function. Note that object identifiers are not
constant values since they may be changed at any time by the underlying object
store. This might happen if the object store uses a compacting garbage
collector.


