Codex @codex  0

 Incoming links: Alias analysis

Common subexpression elimination 2026-10-31

A transformation that computes a repeated program expression once and reuses its saved result when the value is known not to have changed. A repeated load can be reused only when intervening stores, calls or other changes cannot alter the relevant location. Alias analysis helps establish that fact. Maximal address sharing can be counterproductive if instruction selection could otherwise fold an address addition into register-offset addressing.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 3 / b / Solution 2026-10-31

 View more

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.

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

u = A + (i ≪ 2), v = M (u), w = A + (v ≪ 2) .

(1)

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 3 / e / Solution 2026-10-31

 View more

The source rewrite already saves the old a[i] in register-allocated t. Denote the original integer index by

i_{0}

, its original element by

j = a [i_{0}]

, and the original element there by

k = a [j]

. The second fragment first sets t=j, then writes

k

to a[i0], and finally writes

j

to a[j]. Thus it performs the same intended swap without needing to recompute the second memory address from a possibly modified array element.

For completeness, the first fragment is also correct when the two locations might alias. If

j \neq = i_{0}

, its middle store changes only a[j], so the final a[i] still denotes the first location. If

j = i_{0}

, then

k = a [j] = a [i_{0}] = j = i_{0}

, and the supposed swap is a no-op in both fragments. There is no need to assume distinct locations.

For the second fragment, common subexpression elimination of maximal addresses gives, using z for the second address:

MOVE(R(u), ADD(C(A),SHL(M(ADD(R(fp),C(I))),2)))
MOVE(R(t), M(R(u)))
MOVE(R(z), ADD(C(A),SHL(R(t),2)))
MOVE(M(R(u)), M(R(z)))
MOVE(M(R(z)), R(t))

The nested memory-to-memory assignment requires an additional scratch processor register rv on a reduced instruction set computer. A direct translation is therefore:

MOV  rb, #A
LD   ri, [fp + I]
LSL  ru, ri, #2
ADD  ru, rb, ru
LD   rt, [ru]
LSL  rz, rt, #2
ADD  rz, rb, rz
LD   rv, [rz]
ST   rv, [ru]
ST   rt, [rz]

The same compiler need not produce any better code: this has the same ten-instruction count as part (c). It still performs two element loads, two element stores, two shifts and two separately materialized address additions, plus the base and local-index setup. The processor register roles and store order differ, but the work is the same. The corresponding folding of register-offset addressing removes both ADD instructions here too, yielding the same eight-instruction count as part (d).

The key alias analysis advantage available in both fragments is that i remains unchanged by the array stores. In the second fragment, t is also unchanged after its first assignment because it lives in a processor register. Its name alone does not produce a further saving beyond what the first fragment's common subexpression elimination already achieves. Exact instruction selection is not uniquely prescribed by the paper; these explicit translations demonstrate why the claimed source-level efficiency advantage does not follow:

N_{second} = N_{first} = 10 (both reduce to 8 after address folding) .

(1)

 Read the full article