TAC for expressions and array accesses (address calculation)

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• What is the difference between triples and indirect triples? from Lesson 4.2.1
• Write the type expression of int a[3][4]. from Lesson 3.4
• How many LR(0) items does a production with 3 symbols on its right side give? from Lesson 2.4.2

1 · The Story

📖

Seat numbers

Mr. Patel’s auditorium has 10 rows of 20 seats, numbered from row 0, seat 0. Each seat cushion is 4 handspans wide, and the first seat of row 0 starts at the wall mark 1000.

The usher Arjun finds a seat quickly: skip whole rows first (row number × 20 seats), then seats within the row, then multiply by the cushion width and add the starting mark. Row 3, seat 5: 1000 + (3 × 20 + 5) × 4 = 1260.

If the seats had been numbered column by column instead (all row-0..9 seats of column 0 first), the same seat would be at 1000 + (5 × 10 + 3) × 4. Dev writes the usher’s method into the draft as small arithmetic cards.

2 · Predict First

🤔

int A[10][20], base 1000, 4 bytes per element, indices from 0, stored row by row: what is the address of A[3][5]? Write your guess down. The answer is in the vault.

3 · Core Concept

One-dimensional arrays

For A[low … high] with element width w and base address base: addr(A[i]) = base + (i − low) × w. With low = 0 this is base + i × w.

Two-dimensional arrays

A[n₁][n₂] with lower bounds low₁, low₂:

• Row-major (C, rows stored one after another): addr = base + ((i − low₁) × n₂ + (j − low₂)) × w.
• Column-major (Fortran): addr = base + ((j − low₂) × n₁ + (i − low₁)) × w.

In general (row-major), for k dimensions: offset = ((i₁ × n₂ + i₂) × n₃ + i₃) … × w, with each iₖ measured from its lower bound.

Compile-time part

Rewrite base + (i × n₂ + j) × w as i × (n₂ × w) + j × w + base: the constants n₂ × w and w are known at compile time, so the code only multiplies by constants.

TAC for array references

In TAC, x = a[t] means “the value at address base(a) + t”, with t a byte offset. For c + a[i][j] with a of type int[2][3] (width 4, so a row is 3 × 4 = 12 bytes):

( 1) t1 = i * 12
( 2) t2 = j * 4
( 3) t3 = t1 + t2
( 4) t4 = a[t3]
( 5) t5 = c + t4

An assignment a[i][j] = v computes the same offset and ends with a[t3] = v.

Story → compiler term

4 · Visual

Every address computed by the formulas.

Row-major storage drawn as stacked rows (bottom = row 0).

5 · Worked Examples

Example 1 Easy

A[1 … 50] of 8-byte reals starts at 100. Address of A[7]?

Solution

100 + (7 − 1) × 8 = 148. Arjun counts seats from 1 here, so subtract the lower bound first.

Example 2 Medium

int A[10][20] (4 bytes), base 1000. Address of A[3][5] in row-major and column-major, indices from 0; then from 1.

Solution

Row-major: 1000 + 65 × 4 = 1260. Column-major: 1000 + 53 × 4 = 1212. From 1 (row-major): 1000 + ((3 − 1) × 20 + (5 − 1)) × 4 = 1176.

Example 3 GATE

Write TAC for x = c + a[i][j], a of type int[2][3], int width 4, row-major from 0.

Solution

( 1) t1 = i * 12
( 2) t2 = j * 4
( 3) t3 = t1 + t2
( 4) t4 = a[t3]
( 5) x = c + t4

A row is 3 × 4 = 12 bytes, so i is scaled by 12 and j by 4. Five instructions; the address arithmetic needs no base until the indexed copy, exactly the usher’s “skip rows, then seats”.

6 · Shortcuts

⚡

Row-major offset = (i·n₂ + j)·w; column-major = (j·n₁ + i)·w; subtract lower bounds first. Valid when: any 2-D address question; check which order and which lower bound the question uses.

⚡

3-D row-major: ((i·n₂ + j)·n₃ + k)·w. Valid when: higher-dimensional arrays.

7 · GATE Traps

⚠️

• Row-major multiplies the first index by the number of columns (n₂), not rows.
• Forgetting to subtract a lower bound of 1 is the commonest error.
• Multiply by the element width at the end (or scale each term).
• In TAC, a[t] uses a byte offset t, not an element index.
• C is row-major; Fortran is column-major.

8 · Memory Hook

🧠

Row-major: skip whole rows, then seats. Column-major: skip whole columns, then seats.

9 · Connect the Dots

Expressions and arrays are now straight lines of instructions. Programs also branch and loop. The next lesson translates if, while and Boolean conditions into jumps, and shows the trick that fills in jump targets in one pass.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksRow-major

int A[1..5][1..8] stored row-major from address 2000, 2 bytes per element. Address of A[4][6]?

Numerical answer: ________

Q2NAT2 marksColumn-major

Same array stored column-major. Address of A[4][6]?

Numerical answer: ________

Q3NAT1 mark3-D

int B[3][4][5] (4 bytes), row-major from 0, base 500. Address of B[2][1][3]?

Numerical answer: ________

Q4MCQ1 markScaling

For a of type int[2][3] (4-byte ints, row-major), the TAC for a[i][j] multiplies i by:

• (A) 3
• (B) 4
• (C) 12
• (D) 2

Q5MCQ1 markLayout

In row-major storage, consecutive memory locations hold:

• (A) elements of the same column
• (B) elements of the same row
• (C) diagonal elements
• (D) random elements

11 · Rule Card

• 1-D: base + (i − low) × w.
• Row-major 2-D: base + ((i − low₁) × n₂ + (j − low₂)) × w.
• Column-major 2-D: base + ((j − low₂) × n₁ + (i − low₁)) × w.
• k-D row-major: Horner form ((i₁ n₂ + i₂) n₃ + …) × w.
• TAC: scale indices by constants, then x = a[t] / a[t] = y with byte offset t.

12 · Concept Ledger

base addresselement width wrow-major ordercolumn-major orderlower boundbyte offsetindexed copy x = a[t]

13 · Answer Vault