Schematic algorithm

A generic version of the algorithm for simplification--applicable to most of the expressions in the language--is given in Figure A.5. The algorithm is written as a recursive function, simplify. The main input to this function is an expression term $e$, which is modified by the function. Along with the modified version of $e$, the simplify function outputs a sequence of statements, INITS, which declares and initializes any temporaries that were introduced in the simplification of $e$. It also outputs ``access sets'' for $e$ and INITS.

Figure A.5: Schematic algorithm for expression simplification.

$$\begin{minipage}[t]{\linewidth}\begin{tabbing} {\it simplify... ... = {}$ \\ \>\verb$}$ \\ \verb$}$ \end{tabbing}\end{minipage}$$

The algorithm traverses sub-expressions in right to left order. If a sub-expression must be precomputed, the associated code will have to be moved in front of sibling sub-expressions currently to its left. If there are no dependencies between the moved sub-expression and its left siblings, this is fine. But if there is a dependency, the sibling expression must also be precomputed, to preserve the original order of evaluation.

Dependencies are detected using access sets. These record uses and definitions of individual variables, or categories of variables, within expressions. The simplify function computes these access sets on the fly and returns two of them in the values ACCESS and INIT_ACCESS. The set ACCESS is the set of program variable accesses in the translated expression $e'$. The set INIT_ACCESS is the set of program variable accesses in the ``precomputation'' code--code for initialization of temporaries defined in INITS (both sets exclude accesses to temporaries themselves).

At the time a subexpression is visited, the variable INIT_ACCESS holds accesses in ``precomputation'' code already generated by subexpressions to the right of the current expression. If a dependency is discovered between the translated version of the current expression and the code we already know must move ``to the left'', the whole of the current expression must also ``move to the left'', to be precomputed before the code already scheduled to move.

Multiply referenced values and composite expressions are handled in different parts of the algorithm, but currently they are a treated in exactly the same way.