= Solution
The useful repeated <program expressions>, nested inside one another, are the <memory address> of `a[i]`, its value, and the <memory address> of `a[a[i]]`. Materialize each maximal reusable tree at the level at which it is shared, using fresh <temporary variables> `u`, `v`, and `w`:
``
MOVE(R(u), ADD(C(A),SHL(M(ADD(R(fp),C(I))),2)))
MOVE(R(v), M(R(u)))
MOVE(R(w), ADD(C(A),SHL(R(v),2)))
MOVE(R(t), M(R(w)))
MOVE(M(R(w)), R(v))
MOVE(M(R(u)), R(t))
``
Thus `u` is a saved <memory address>, `v` the old <integer> value of `a[i]`, `w` the second saved <memory address>, and `t` the old value at that second location. The two large address trees occur both in loads and as store destinations. After extracting them, the repeated load of `a[i]` inside the second address and as the middle assignment's source becomes `v`. Extracting every smaller nested tree again would add no benefit.
The relevant <alias analysis> facts are that local `i` does not occupy any location written through global `a`, that <frame pointer> `fp` and base $A$ stay fixed, and that `t,u,v,w` are distinct <processor registers> or otherwise nonoverlapping <temporary variables>. There are no intervening calls, <volatile memory accesses>, or concurrent changes. Under these assumptions, loading `i` once remains valid even across the array stores. Before the middle store, no array location has yet changed, so both its target <memory address> and its source value can be computed and saved earlier.
\b[No assumption that the two array locations are distinct is required.] The middle store may change `a[i]` when its target coincides with it, but `v` is not loaded again afterwards: only the saved address `u` is needed for the final store. It would be unsound to retain an arbitrary array load across an aliasing store and then treat it as the new contents; that is not what these trees do.
For a language with a true global <array>, a distinct local variable, and no arbitrary means of fabricating <pointers> to unrelated storage, these facts follow simply from declarations and the <stack frame> layout. Accesses must denote valid <array> elements. In an unrestricted low-level language with overlapping storage, arbitrary <pointer> arithmetic or unchecked out-of-range accesses, that conclusion requires extra guarantees. Omitting emitted <array bounds> checks does not itself prove that all <memory addresses> are valid. If $M$ denotes a word load, the saved quantities are
$$
\boxed{u=A+(i\ll2),\quad v=M(u),\quad w=A+(v\ll2).}
$$
Back to article page
