Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 3 / c

Here is a literal instruction selection for the trees in part (b), with the temporary variables allocated to processor registers. MOV r,#k loads an arbitrary constant in one instruction. LD and ST load and store one four-byte word; [r] denotes zero-offset access. LSL is a left shift. We use conventional base-plus-immediate access for the fixed local offset I.

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

The first four instructions construct u, the fifth obtains v, the next two construct w, and the last three perform the remaining load and the two stores. Each destructive update of ru or rw reuses a processor register whose previous value is no longer needed. We assume enough processor registers to avoid a register spill.

If the target offers only the explicitly mentioned two-register register-offset addressing and lacks base-plus-immediate access, replace the one local load by MOV rk,#I; LD ri,[fp+rk]; all other conclusions are unchanged. A zero processor register or a zero-offset load supplies the notation [ru] and [rw] as usual. This direct translation takes ten instructions with immediate local addressing, or eleven with the stated replacement. Thus These are instruction counts for the specified abstract target, not measured execution times.