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:

• If the variable is a named expression, the subexpressions are:
  • the prefix of named expression, if it is non-null and is an expression (not a type).
• If the variable is a field reference with a general expression prefix, the subexpressions are:
  • the prefix expression of the field reference.
• If the variable is a field reference with a super prefix, there are no subexpressions.
• If the variable is an array element reference, the subexpressions are:
  • the target array of the element reference,
  • the integer subscripts, if any, of the element reference, and
  • the ``shift'' expressions in any shifted-distributed-index subscripts of the element reference.

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

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

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{minipage}[t]{\linewidth}\begin{tabbing} {\it simplify... ...} of LHS variable}\}$ \\ \verb$}$ \end{tabbing}\end{minipage}$$

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

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

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

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

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{minipage}[t]{\linewidth}\begin{tabbing} $v$\verb$ = $$v$\verb$ $$\oplus$\verb$ $$e$\end{tabbing}\end{minipage}$$

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{minipage}[t]{\linewidth}\small\begin{verbatim}a [n++] += sum(blackBox()) ;\end{verbatim}\end{minipage}$$

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{minipage}[t]{\linewidth}\small\begin{verbatim}__$t... ...ackBox() ; a [n++] += sum(__$t1) ;\end{verbatim}\end{minipage}$$

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{minipage}[t]{\linewidth}\small\begin{verbatim}__$t... ...) ; a [n++] = __$t1 + sum(__$t2) ;\end{verbatim}\end{minipage}$$

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{minipage}[t]{\linewidth}\small\begin{verbatim}__$t... ...; a [__$t1] = __$t2 + sum(__$t3) ;\end{verbatim}\end{minipage}$$

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{minipage}[t]{\linewidth}\begin{tabbing} {\it simplify... ...} of LHS variable}\}$ \\ \verb$}$ \end{tabbing}\end{minipage}$$