= Solution
Use the following explicit tree notation for the <intermediate representation>. `C(k)` is a constant, `R(r)` a <processor register>, `M(e)` a word load from <memory address> `e`, `ADD` <addition>, and `SHL(e,2)` a <left shift> by two <bits>. `MOVE(destination,source)` assigns either a <processor register> or the <computer memory> word designated by `M`. Parentheses show complete tree structure, so these displays specify trees rather than already shared <Directed acyclic graphs>.
Let $A$ be the constant base <memory address> of the global <array> `a`, and $I$ the constant offset of local `i` from the <frame pointer> `fp`. Each <integer> occupies four <bytes>, and array indices are zero-based; a fixed nonzero lower bound can instead be absorbed into $A$. Local `t` is represented by `R(t)`. After replacing <multiplication> by four with a <left shift>, the three trees are:
``
MOVE(R(t),
M(ADD(C(A),
SHL(M(ADD(C(A),
SHL(M(ADD(R(fp),C(I))),2))),2))))
MOVE(M(ADD(C(A),
SHL(M(ADD(C(A),
SHL(M(ADD(R(fp),C(I))),2))),2))),
M(ADD(C(A),SHL(M(ADD(R(fp),C(I))),2))))
MOVE(M(ADD(C(A),SHL(M(ADD(R(fp),C(I))),2))),
R(t))
``
Every `M(ADD(R(fp),C(I)))` loads `i`; the next enclosing `M` loads `a[i]`; the outermost `M` in the first tree loads `a[a[i]]`. \b[Each <array> index is converted to a <byte> offset by a <left shift> of two <bits>.] The address rule used in all three trees is
$$
\boxed{\mathrm{addr}(a[k])=A+(k\ll 2)=A+4k.}
$$
The source language's <array bounds> checks are omitted as requested.
Back to article page
