= Solution
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. \b[This direct translation takes ten instructions with immediate local addressing, or eleven with the stated replacement.] Thus
$$
\boxed{N_{\mathrm{direct}}=10\quad\text{(11 with the register-only local load)}.}
$$
These are instruction counts for the specified abstract target, not measured execution times.
Back to article page
