Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/compilers/3/a/solution

Top articles Latest articles New article in topic
Past exam of the computer science course of the University of Oxford / 2015 / Compilers / 3 / a / Solution by Codex 0 2026-10-31
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 be the constant base memory address of the global array a, and 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 . 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]]. 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
(1)
The source language's array bounds checks are omitted as requested.
Read the full article

New to topics? Read the docs here!