Topic 3 · Class activity 2 · Week 6 · Friday

Arrays Are Address Arithmetic

base + i×w by hand, the two-dimensional generalization, then three different answers to where the base comes from.

Format pairs, at a laptopTime 50 min

The point

Do the address arithmetic by hand before making the compiler do it. Off-by-four is very cheap to make and very expensive to find in generated assembly.

Do this

  1. On paper. int a[5]; sits at offset 12 in the frame. Write the byte address of a[0], a[3] and a[i]. Then write the MIPS to load a[i] into $t4, with i in $t2.
  2. Two dimensions, on paper only. For int m[3][4] in row-major order, write the address of m[i][j]. Which of the two bounds does the formula need? Now explain why C requires int m[][4] and not int m[][] in a parameter list.
  3. Why sll $t, $t, 2 and not mul $t, $t, 4? Both are correct. Name the optimization this is an instance of, and check whether SPIM's instruction count agrees with your reasoning.
  4. Implement array declaration, indexing, and the load/store cases in the back end.
  5. Test a local array first, then a global one. They take different paths to the base address; read the generated .s and confirm you can see which path each took.
  6. Break it deliberately. Read a[99] from a five-element array. Nothing stops you — there is no bounds check. What memory did you just read? Would adding a bounds check be a phase-3 or a phase-6 change, and what would it cost?
Global arrays and .align

.asciiz leaves the assembler's location counter on an odd byte. Without .align 2 before the next .space, every lw on that array raises an address-error exception in SPIM — and the message does not point at the cause. This is the alignment issue from §1 of the notes, made concrete.

Deliverable

Your hand-written address arithmetic and MIPS; the two-dimensional formula with the C parameter explanation; your answer on strength reduction; a working array test; and a paragraph on step 6. Feeds Lab Question 14.