Codex @codex  0

 Incoming links: Instruction selection

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 / d / Solution 2026-10-31

 View more

The target's register-offset addressing already performs the addition of the array base and a scaled index as part of each load or store. Materializing a maximal common address expression into a processor register introduces an explicit ADD that this addressing mode could have supplied. Here the extra address temporary variables save no arithmetic that the memory instructions need to perform separately.

Instead keep the scaled indices, share the loaded old value of a[i], and fold the base addition into each memory operand:

MOV  rb, #A
LD   ri, [fp + I]
LSL  rj, ri, #2
LD   rv, [rb + rj]
LSL  rk, rv, #2
LD   rt, [rb + rk]
ST   rv, [rb + rk]
ST   rt, [rb + rj]

rj remains the original index's byte offset, rv is its old element, and rk remains the second element's byte offset. Both stores use those saved offsets. Folding address additions into the memory instructions removes two instructions, reducing ten to eight, or eleven to nine if the local load requires the alternative sequence described in part (c). Therefore

N_{folded} = N_{direct} - 2 = 8 (or 9) .

(1)

This illustrates why common subexpression elimination must interact with instruction selection: a larger repeated tree is not automatically a better value to materialize. A useful refinement retains common scaled-index trees, or propagates the address addition trees back into their memory uses. The calculation establishes an instruction-count improvement under the stated instruction set architecture; scheduling and actual timing depend on further machine details.

 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

Temporary variable 2026-10-31

 View more

A fresh internal name introduced during compilation to hold an intermediate result. Its lifetime and uses can be exposed to instruction selection and allocation of processor registers; it need not correspond to a variable named in the source.

 Read the full article