Computer Science › Section I · Data abstractions › Topic I.6

Pointers in machine language

Stacks, linked lists and trees all depend on following pointers, but a machine can only do that if its instructions allow it. Extending the Sparrow teaching machine with one new kind of load and store shows exactly what hardware support for pointers looks like.

A load Sparrow cannot do

To pop a stack, as in "Implementing data structures", a program must read the cell its stack pointer indicates. The Sparrow machine from "Machine language" cannot do that directly. Its SET instruction, 0x2RXY, puts the value XY itself into register R, but the value on top of the stack is not known in advance. Its LOAD instruction, 0x1RXY, reads the cell at address XY, but XY is fixed when the program is written, while the top of the stack moves as the program runs. What the program does know is where the pointer is kept. It needs an instruction whose address comes from data, computed while the program runs.

Three ways to name data

The ways an instruction can identify its data are called addressing modes. In immediate addressing, the operand is the data itself, as in Sparrow's SET. In direct addressing, the operand is the data's address, as in LOAD and STORE. In indirect addressing, the instruction says where to find the address: memory-indirect designs keep that address in a memory cell, and register-indirect designs keep it in a register. Machines without any indirect mode forced some early programmers to make a program rewrite the address field of its own LOAD instruction while running. That works, because code is data, as "Program execution and the machine cycle" explained, but it is hard to read and easy to get wrong.

An extension: op-code F

Sparrow, as defined in "Machine language", leaves op-code F unused. This topic extends Sparrow with two register-indirect instructions that use it; they are not part of the original table. In 0xFRSN, R is the register that receives or supplies the data, S is the register holding the address, and the final digit N chooses the action. 0xFRS0, indirect LOAD: copy into register R the cell whose address is in register S. 0xFRS1, indirect STORE: copy register R into the cell whose address is in register S. N values 2 to F remain undefined, and register S is never changed. Keeping pointers in registers lets ADD and SUB move them without extra trips to memory.

Worked example: three loads compared

Suppose register R8 holds 0x3B, cell 0xC4 holds 0x3B, and cell 0x3B holds 0x9E. Compare what each instruction leaves in R5. 1. 0x25C4 is immediate: R5 receives the operand itself, 0xC4. 2. 0x15C4 is direct: R5 receives the contents of cell 0xC4, which is 0x3B. 3. 0xF580 is the indirect LOAD with R = 5, S = 8 and N = 0: R8 holds 0x3B, so R5 receives the contents of cell 0x3B, which is 0x9E. 4. Check with a simulator of extended Sparrow: the results are 0xC4, 0x3B and 0x9E, and R8 still holds 0x3B. Three instructions, three different answers, because each finds its data a different way.

Inside the machine cycle

The new instructions fit the machine cycle unchanged. Fetch works as always: two cells go into the instruction register and the program counter rises by 2. Decode sees op-code F and reads the last digit to choose load or store. Execute reads register S, places its value on the bus as an address, and then performs one memory read into R or one memory write from R. So an indirect LOAD touches memory for data exactly once, like a direct LOAD; only the source of the address differs. A memory-indirect design would need two memory reads, one to fetch the pointer and one to fetch the data, which is one reason register-indirect designs are common.

Push and pop in Sparrow

Use the stack convention from "Implementing data structures": register RF, the stack pointer, holds the address of the next free cell, and the stack grows towards higher addresses. Keep the constant 1 in R1. To push R5, store it at the free cell, then move the pointer up: 0xF5F1, then 0x5FF1, which sets RF to RF + R1. To pop into R6, move the pointer down to the top entry, then load it: 0x6FF1, which sets RF to RF − R1, then 0xF6F0. The order matters. Loading before moving the pointer would read the free cell above the top, which holds no entry.

Worked example: two pushes and a pop

A program at 0x00: 0x2101 (R1 = 1), 0x2FE0 (RF = 0xE0, an empty stack), 0x252A (R5 = 0x2A), 0xF5F1 and 0x5FF1 (push), 0x2517 (R5 = 0x17), 0xF5F1 and 0x5FF1 (push), 0x6FF1 and 0xF6F0 (pop into R6), 0x0000. 1. The first push stores 0x2A in cell 0xE0, and RF becomes 0xE1. 2. The second stores 0x17 in 0xE1, and RF becomes 0xE2. 3. The pop lowers RF to 0xE1 and loads 0x17 into R6, the last value pushed. 4. A simulated run agrees after 11 machine cycles. Cell 0xE1 still holds 0x17: popping does not erase, and the next push simply overwrites it.

Worked example: summing a linked list

Each node is two cells, a value then a next pointer, with 0x00 as null. Cell 0x70, the head pointer, holds 0x80. Node 0x80 holds 0x05 and 0x90; node 0x90 holds 0x0C and 0x84; node 0x84 holds 0x09 and 0x00. The program at 0x00: 0x1270, 0x2300, 0x2101, then at 0x06 0xD212, 0xF420, 0x5334, 0x5521, 0xF250, 0xE006, and at 0x12 0x3371, 0x0000. 1. R2 takes the head pointer, R3 = 0 is the sum, and R1 = 1. 2. If R2 is null, jump to 0x12. 3. Load the node's value through R2 and add it to R3. 4. Point R5 at the next field, then load the next pointer into R2. 5. Repeat. The sum, 0x1A = 26, goes to cell 0x71 after 24 cycles.

Pointers in real processors

Real instruction sets provide these modes and more. ARM's LDR r0, [r1] loads r0 from the address in r1, and x86-64's mov rax, [rbx] does the same with rbx: both are register-indirect. Most machines also offer base-plus-offset addressing, such as [rbx + 8], which adds a constant to a register; that suits a record's fields, whose fixed offsets were described in "Implementing data structures". Processors also have a dedicated stack pointer register, SP on ARM and RSP on x86-64, which programs use to manage the call stack. On these machines the stack usually grows towards lower addresses, the reverse of our convention, so push lowers the pointer.

Common mistakes to avoid

First, forgetting that the F instructions are an extension: the Sparrow table in "Machine language" has no op-code F. Second, confusing the two registers in 0xFRSN: R holds the data, and S holds the address. Third, writing an address in an F instruction, as if 0xF5C4 loaded from cell 0xC4; its last digit, 4, is undefined. Fourth, popping in the wrong order: lower the pointer first, then load. Fifth, following a pointer without testing for null; the linked-list program checks R2 before every load. Sixth, expecting a pop to erase the cell it read.

Key takeaways

Immediate addressing puts the data in the instruction, direct addressing puts its address there, and indirect addressing says where the address is kept. Original Sparrow has only the first two, so it can follow a pointer only by rewriting its own instructions. The extension uses op-code F: 0xFRS0 loads R from the cell whose address is in S, and 0xFRS1 stores R there. With a stack pointer in RF, a push is a store then an add, and a pop is a subtract then a load. Register-indirect loads let programs walk arrays, stacks and linked lists; real processors such as ARM and x86-64 provide them.

Flashcards

Flashcard

Addressing mode

The way an instruction identifies the data it uses

Immediate, direct, indirect.

Test your understanding

Question 1 of 5

On extended Sparrow, register R9 holds 0x5D, cell 0x5D holds 0x07, and cell 0x07 holds 0x44. What does the instruction 0xF290 put in register R2?

Question 2 of 5

Which extended-Sparrow instruction copies register R3 into the cell whose address is held in register RA?

Question 3 of 5

A stack occupies cells 0xC0 to 0xC2, holding 0x11, 0x22 and 0x33, and RF, the next-free-cell pointer, holds 0xC3. R1 holds 1. After 0x6FF1 and then 0xF4F0, what do R4 and RF hold?

Question 4 of 5

Which addressing mode does Sparrow's LOAD instruction 0x1RXY use?

Question 5 of 5

Why can original Sparrow's 0x1RXY not pop a stack whose top keeps moving?

← Previous topicNext topic →