next up previous contents index
Next: Expressions with conditional evaluation Up: Expression simplification Previous: Expression nodes   Contents   Index

Updates

To deal with updates, we first define, in Figure A.6, an abstracted visitChildren algorithm, convenient particularly for variable expressions (i.e. expressions that can appear on the left-hand-side of an assignment). The subexpressions of a variable expression are mostly self-explanatory. They are:

Figure A.6: Standalone function for visiting subexpressions of a variable.

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\begin{tabbing}
{\it visitChi...
...erb$}$ \\
\>\verb$}$ \\
\verb$}$
\end{tabbing}\end{minipage}\end{displaymath}

The visitChildren function is applied to the left-hand-side of a simple assignment in Figure A.7. An important point is that one does not recursively apply the simplify algorithm to the expression representing the variable itself; the recursion is on the subexpressions of the variable expression. The case of an autoincrement or autodecrement expression is also straightforward, and it is given in A.8. There is a complication in the case of compound assignments; they will be dicussed in the next section.

Figure A.7: Simplification of simple assignment expressions.

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\begin{tabbing}
{\it simplify...
...} of LHS variable}\}$ \\
\verb$}$
\end{tabbing}\end{minipage}\end{displaymath}

Figure A.8: Simplification of autoincrement/decrement expressions.

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\begin{tabbing}
{\it simplify...
... operand variable}\}$ \\
\verb$}$
\end{tabbing}\end{minipage}\end{displaymath}

Compound assignment needs special treatment in the simplify algorithm. Assuming $\oplus$ is one of the supported operators, a problem arises in

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\begin{tabbing}
$v$\verb$ $$\oplus$\verb$= $$e$\end{tabbing}\end{minipage}\end{displaymath}

if $e$ includes a subexpression $e_i$ that must be precomputed, and $e_i$ may define $v$ (i.e. subexpression $e_i$ has a def of $v$ in its access set). The underlying problem is that there is then an anti-dependence from $v$ to $e_i$ and an output dependence from $e_i$ to $v$. Hence one cannot move the code for $e_i$ without splitting the compound assignment.

In this case we are essentially forced to translate the assignment to

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\begin{tabbing}
$v$\verb$ = $$v$\verb$ $$\oplus$\verb$ $$e$\end{tabbing}\end{minipage}\end{displaymath}

thus allowing the use of $v$ on the RHS to be precomputed. Moreover if $v$ itself is a non-trivial expression, you may then have to mark its subexpressions as being multiply-referenced to avoid their repeated computation.

It is fairly difficult to imagine realistic code in which this situation would arise, but here is a contrived example:

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{verbatim}a [n++] += sum(blackBox()) ;\end{verbatim}\end{minipage}\end{displaymath}

We will suppose blackBox() is a method that returns a multiarray result, but whose behavior is otherwise unknown. The method sum() might add the elements of a multiarray. On the left-hand-side, a is an array--a local variable, say--and we will assume n is also a local variable.

According to our simplification rules, the composite multiarray expression blackBox(a) must be precomputed, and assigned to a temporary. So a naive transformation might be:

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{verbatim}__$t...
...ackBox() ;
a [n++] += sum(__$t1) ;\end{verbatim}\end{minipage}\end{displaymath}

where __$t1 is the name of a temporary. In general this transformation is illegal, because blackBox() could modify the value of a [n] as a side-effect (even if the array reference a is a local variable, the referenced array may be accessible by other methods). In this situation, the correct semantics of the original code is to increment the initial, unmodified value of a [n]. But our naively transformed code increments the value modified by blackBox().

To solve this problem, we should precompute the initial value of the left-hand-side of the assignment, something like

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{verbatim}__$t...
...) ;
a [n++] = __$t1 + sum(__$t2) ;\end{verbatim}\end{minipage}\end{displaymath}

Of course this still isn't correct due to the repetition of the subscript expression in the variable a [n++]. A correct transformation is:

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{verbatim}__$t...
...;
a [__$t1] = __$t2 + sum(__$t3) ;\end{verbatim}\end{minipage}\end{displaymath}

An algorithm is given in Figure A.9. Note that $e_l$ may be marked as a multiply referenced variable. Such expressions were mentioned in section A.3.2. The effect of marking a variable expression in this way is to alter the behavior of the visitChildren function defined in Figure A.6, causing it to treat all the subexpressions, $e_i$, as if they are multiply referenced values.

Figure A.9: Simplification of compound assignment expressions.

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\begin{tabbing}
{\it simplify...
...} of LHS variable}\}$ \\
\verb$}$
\end{tabbing}\end{minipage}\end{displaymath}


next up previous contents index
Next: Expressions with conditional evaluation Up: Expression simplification Previous: Expression nodes   Contents   Index
Bryan Carpenter 2003-04-15