\section{Optimization}
\label{Section:Optimization}

%


The translation algorithm described in the previous section produces TML
code that is far from 'optimal' in terms of code size and execution
speed. A great deal of this inefficency stems from the translation
process itself. We have tried to keep the translation process as simple
as possible, so it generates a lot of unnecessary abstractions and
$\lambda$-bindings. It is much simpler to run a separate optimization
pass on the resulting TML tree rather than trying hard to improve the
translation algorithm itself. This has the additional advantage that
certain inefficiencies introduced by the TL programmer (in order to keep
the TL program more readable, for example) will be removed also. And, as
we will see in section
\ref{Section:Extensions for Reflective Runtime Optimization},
a small extension will enable us to
optimize programs at runtime where a lot of valuable information is
available to the optimizer.

We have organized the optimization phase into two separate passes,
namely the reduction pass and the expansion pass. During the reduction
pass, a number of generic rewrite rules are applied to the TML tree
until no more rule is applicable.  Termination is guaranteed because
each of the rewrite rules reduces the size of the TML tree if it is
applied (therefore the name {\em reduction} for this pass).

The subsequent expansion pass tries to subsitute bound
$\lambda$-abstractions (procedures or continuations) at the places they
are applied.  Effectively, this CPS transformation performs {\em
procedure inlining} in terms of traditional compiler optimization. The
decision whether a given use of a bound abstracion is to be substituted
is based on a heuristic cost model similar to the one described by
\cite{App92}.

When one or more abstractions are substituted during the expansion pass,
there usually is the opportunity to perform more reductions on the TML
tree (this is indeed the main reason why we perform procedure inlining
at all), so each expansion pass is followed by a reduction
pass. Likewise, the reduction pass may reveal new opportunities to
perform procedure inlining, so the two passes are applied repeatedly
until no more changes are made to the TML tree. To guarantee the
termination of this process even in obscure cases, a penalty is
accumulated at each round of the reduction/expansion phases. The
optimization process stops when this penalty reaches a certain
limit.

%This cancellation may take place
%at any time since the TML rewrite rules never leave the TML tree in an
%inconsistend state.

\subsection{TML Rewrite Rules}
\label{Section:TML Rewrite Rules}

In this section, we give a formal definition of the generic TML rewrite
rules. We will present them using the notation

\tmlrewrite{rule name}{(precondition)}{A}{B}

indicating that the TML expression $A$ may be rewritten to the TML
expression $B$ if and only if $precondition$ evaluates to true. By
convention, an empty precondition evaluates to true.

In the precondition, we denote the number of occurrences of a variable
$v$ in an TML expression $E$ with $\tmlrefcount{E}{v}$. This function is
defined inductively on the abstract syntax of TML as follows:

\begin{tabular}{rcl}
$ \tmlrefcount{v}{v} $ & = & $ 1 $ \\
$ \tmlrefcount{l}{v} $ & = & $ 0 $ \\
$ \tmlrefcount{p}{v} $ & = & $ 0 $ \\
$ \tmlrefcount{v_1}{v_2} $ & = & $ 0 \quad (v_1 \neq v_2) $ \\
$ \tmlrefcount{\lambda{}(v_1..v_n)\:app}{v} $ & = &
  $ \tmlrefcount{app}{v} $ \\ %\hspace{-4pt}
$ \tmlrefcount{(val_0\:val_1..val_n)}{v} $ & = & $ 
   \sum_{i=0}^n \tmlrefcount{val_i}{v} $ \\
\end{tabular}

Similarly, on the right side of a TML rewrite rule, we use the notation
$\tmlsubst{E}{val}{v}$ that denotes the expression $E$ where every
occurence of the variable $v$ is replaced by the value $val$. Name
clashes cannot occur during substitution because each variable is bound
only once in a TML tree (unique binding rule). This property is achieved
by the {\em $\alpha$-conversion} performed during TML code generation,
and is never violated by any of the TML rewrite rules, except in one
case: if, in an application of the substitution rule, the value
substituted is an abstraction, the formal parameters of this abstraction
occur temporarily at two different places within the TML tree: 1. at the
original place, namely as a parameter to the $\lambda$-application, and
2. at the place the abstraction was substituted for the
variable. However, this does not do any harm because the first occurence
of the abstraction will be removed immediately (by an application of the
rewrite rule {\em remove}) since the substituted variable is not
referenced any more.

Variable substitution is defined inductively on the abstract syntax
of TML as follows:

\begin{tabular}{rcl}
$ \tmlsubst{v}{val}{v} $ & = & $ val $ \\
$ \tmlsubst{v'}{val}{v} $ & = & $ v' \quad (v \neq v') $ \\
$ \tmlsubst{l}{val}{v} $ & = & $ l $ \\
$ \tmlsubst{p}{val}{v} $ & = & $ p $ \\
$ \tmlsubst{\{\lambda{}(v_1..v_n)\:app\}}{val}{v} $ & = & $ %\hspace{-4pt}
   \lambda{}(v_1..v_n)\:\{\tmlsubst{app}{val}{v}\} $ \\
$ \tmlsubst{(val_0\:val_1..val_n)}{val}{v} $ & = & $
   (\tmlsubst{val_0}{val}{v}\:\tmlsubst{val_1}{val}{v}..\tmlsubst{val_n}{val}{v}) $ \\
\end{tabular}

Values bound to $\lambda$-variables may be substituted freely within the
TML tree since, due to CPS, they are not allowed to contain nested
primitive or function calls that may cause side effects in the store.

%Note that the unique binding rule is
%not violated by the substitution rules.

The complete set of the TML rewrite rules that is currently implemented
as a part of the reduction pass is given below. The expansion pass uses
a variant of the {\p subst} rewrite rule in order to perform procedure
inlining.  Although each individual rule is fairly simple, the
combination of these rules is surprisingly powerful. Many of the
well-known standard program optimizations like constant and copy
propagation, dead code elimination and procedure inlining are just
special cases of these general $\lambda$-calculus transformations.

%\newdimen\parskiptemp
%\parskiptemp=\parskip
%\parskip 3ex

\newcommand{\fasl}[1]{#1}

\input{tml4a}

%\parskip=\parskiptemp



\subsection{Extensions for Reflective Runtime Optimization}
\label{Section:Extensions for Reflective Runtime Optimization}

In the Tycoon system, the compiler (and, therefore, the optimizer) is an
integral part of the persistent programming environment. This enables
us to call the optimizer {\em statically}, during normal program
compilation, or {\em dynamically} at runtime.

For each TL function \p{f}, the target code generator emits code that is
augmented with a reference to a compact persistent representation of the TML
tree for \p{f}. This persistent CPS representation is called
PTML (Persistent Tycoon Machine Language) and is isomorphic to TML.

At runtime, it is possible to map PTML expressions back into TML
expressions, re-invoke the optimizer and code-generator. Since this
compilation takes place during program evaluation, we call our approach
{\em reflective optimization}.

The mapping from PTML back to TML also returns the set of R-value
bindings established at runtime. These bindings correspond to free
variables (module names, function names, constant names) in the source
text and they naturally give rise to context-dependent, inter-procedure
and inter-module optimizations ({\em optimization across abstraction
barriers}).
     
To speed up repeated optimizations of (shared) functions, the optimizer
attaches several derived attributes (costs, savings, ...) to the 
generated code which also become part of the persistent system state.

For example, this is a Tycoon interface \p{complex} that exports an
abstract data type \p{complex.T} and some functions
\p{complex.x}, \p{complex.y}, ..  on values of that type:

\vbox{
\begin{xple}
  \k{module} complex \k{export} 
    \k{Let} T = \k{Tuple} x,y :Real \k{end}
    \k{let} new(x,y :Real):T = \k{tuple} x y \k{end}
    \k{let} x(complex :T) :Real = complex.x
    \k{let} y(complex :T) :Real = complex.y
    ...
  \k{end}
\end{xple}
}

\vbox{
Here is a function \p{abs} that uses these exported functions:

\begin{xple}
  \k{let} abs(c :complex.T) :Real =
    sqrt(complex.x(c) * complex.x(c) + complex.y(c) * complex.y(c))
\end{xple}
}

In the static context of this function, the implementation of the
module (the binding to the module value) is not availabe. Only after
module linkage (Tycoon has first class modules), the dynamic context
of \p{abs} contains bindings to the exported function. 

The programmer can obtain a (dynamically created) function
\p{optimizedAbs} that is equivalent to the original function \p{abs}
but that (hopefully) executes faster than the original by explicitly
invoking the optimizer on \p{abs}:

\begin{xple}
  \k{let} optimizedAbs = reflect.optimize(abs)
\end{xple}

In our current implementation, the compiler would inline the bodies of 
\p{{complex.x}} and \p{{complex.y}}, i.e., \p{optimizedAbs} is equivalent to:

\begin{xple}
  \k{let} optimizedAbs(c :complex.T) :Real =
    sqrt(c.x*c.x + c.y*c.y)
\end{xple}

Finally, the optimized function can be applied:

\begin{xple}
  optimizedAbs(complex.new(3 4))
\end{xple}

The main extension that is necessary to be able to carry out this kind
of dynamic optimization is to re-establish, in TML, the R-value bindings
of global variables as they are stored in the {\em closure record}
(cf. section \ref{Section:Environment Analysis and Closure Conversion})
of the runtime representation of a given procedure. For the example
above, this means that the values of the variables
\p{complex}, '+', '*' which are global to the function \p{abs}
globaland
\p{sqrt} are fetched from the closure record of \p{abs} and are bound to the
corresponding identifiers {\em before} the (original) body of \p{abs} is
executed\footnote{This is a TML listing similar to the output of our TML
pretty-printer.
%, with vertical bars indicating the nesting level in each output line.
Note that, during $\alpha$-conversion, each identifier name is appended
with a unique number in order to distinguish it from any other
identifier.}:

\vbox{
\begin{xple}
  \k{proc}(c\_10 c\_11)
    ($\lambda$(complex\_6 *\_7 +\_8 sqrt\_9)
        ([] complex\_6 2 cont(t\_12)            ; here begins the original body of  \p{abs}
        (t\_12 c\_10 cont(t\_13)
        ([] complex\_6 2 cont(t\_14)
        (t\_14 c\_10 cont(t\_15)
        (*\_7 t\_13 t\_15 cont(t\_16)
        ([] complex\_6 3 cont(t\_17)
        (t\_17 c\_10 cont(t\_18)
        (+\_8 t\_16 t\_18 cont(t\_19)
        ([] complex\_6 3 cont(t\_20)
        (t\_20 c\_10 cont(t\_21)
        (*\_7 t\_19 t\_21 cont(t\_22)
        (sqrt\_9 t\_22 cont(t\_23)
        (c\_11 t\_23)))))))))))))               ; here ends the original body of  \p{abs}
      $<\!oid 0x005b4780\!>$           ; value of module \p{complex}
      $<\!oid 0x001b4044\!>$           ; value of function \p{'*'}
      $<\!oid 0x001b4024\!>$           ; value of function \p{'+'}
      $<\!oid 0x00993d28\!>$)         ; value of function \p{sqrt}
\end{xple}
}

Given these value bindings, the optimizer is able to perform
subsitution, constant folding and procedure inlining in the usual way,
yielding a result that is equivalent to the above TL code for
\p{optimizedAbs}.

\leaveout{
The TML representation of the original function \p{abs} is as follows:

\begin{xple}
  proc(c\_7 e\_5 c\_6)
    ([] complex\_7 2 cont(t\_8)
    (t\_8 c\_7 e\_5 cont(t\_9)
    ([] complex\_7 2 cont(t\_10)
    (t\_10 c\_7 e\_5 cont(t\_11)
    (*\_72 t\_9 t\_11 e\_5 cont(t\_12)
    ([] complex\_7 3 cont(t\_13)
    (t\_13 c\_7 e\_5 cont(t\_14)
    (+\_50 t\_12 t\_14 e\_5 cont(t\_15)
    ([] complex\_7 3 cont(t\_16)
    (t\_16 c\_7 e\_5 cont(t\_17)
    (*\_72 t\_15 t\_17 e\_5 cont(t\_18)
    (sqrt\_4 t\_18 e\_5 cont(t\_19)
    (c\_6 t\_19))))))))))))))
\end{xple}


proc(c'10 c'11)
  ([] c'10 1 cont(t'13)
  ([] c'10 1 cont(t'15)
  (* t'13 t'15
  | cont()
  | : (vector "intOverflow" cont(exc'56)
  | : (raise exc'56))
  | cont(t'16)
  | : ([] c'10 2 cont(t'18)
  | : (+ t'16 t'18 cont(t'19)
  | : ([] c'10 2 cont(t'21)
  | : (* t'19 t'21
  | : | cont()
  | : | . (vector "intOverflow" cont(exc'39)
  | : | . (raise exc'39))
  | : | c'11)))))))

}


\leaveout{
The Tycoon programming
environment offers the module \p{reflect} that exports a function
\p{optimize} with the signature

\begin{quote}
  \p{optimize(A <:Ok a :A):A}
\end{quote}


The \p{optimize} function calls the optimizer
(* call the optimizer (at run time) to simplify a.
       Return an equivalent value. If a is a function,
       optimize() will return an equivalent function that
       has the potential to run much faster. 
       A should be a function type, i.e. A <: Fun(..).. *)
}

