From arr[i] to an Address

The previous lesson showed that a dereference is a memory access whose address comes from a register. Array indexing is the same idea with one extra step: the address has to be computed from a base and an index. C++ writes that computation as arr[i]. The compiler turns it into a single, very characteristic addressing mode.

Here is the function we will read all lesson:

int elementAt(const int* arr, int i)
{
    return arr[i];
}

At -O2 it is almost nothing:

elementAt(int const*, int):
    movsx rax, esi
    mov   eax, DWORD PTR [rdi+rax*4]
    ret

The interesting line is the second one. [rdi+rax*4] is the form you will see for array access again and again, so let us understand exactly what it computes.

The base + index*scale Addressing Mode

x86-64 can compute an address from three pieces in a single operand:

[ base + index * scale ]
  • base is a register holding a starting address. Here it is rdi, the array pointer arr.
  • index is a register holding how many elements to move. Here it is rax, which holds i.
  • scale is the size of one element in bytes. Here it is 4, because each int is 4 bytes.

So [rdi+rax*4] computes arr + i*4: start at the base of the array, advance i elements, where each element is 4 bytes. That is precisely the address of arr[i]. The DWORD PTR then reads 4 bytes from it. One instruction does the multiply, the add, and the load.

This is the heart of the lesson: the scale in the addressing mode is the element size. When you see *4, you are looking at an array of 4-byte elements (int, float); *8 is an 8-byte type (long, double, or a pointer); *2 is a 2-byte short. The scale tells you how big each element is, which usually tells you the element type.

Why movsx First

Before the load, there is movsx rax, esi. The index i is an int, which arrived in the 32-bit esi. But an address calculation needs a full 64-bit register, so the compiler sign-extends i from 32 bits into the 64-bit rax. That is what movsx does ("move with sign extension"): it copies a smaller signed value into a larger register, filling the upper bits so the number keeps its sign. After this, rax holds i as a 64-bit value, ready to be the index in [rdi+rax*4].

You will see movsx (or its cousin movzx, "move with zero extension", for unsigned types) constantly right before array accesses. It is a sign that an int index is being widened to take part in an address.

A Constant Index Folds Into a Displacement

What if the index is a compile-time constant instead of a variable? Then there is nothing to compute at run time, and the addressing mode simplifies:

int thirdElement(const int* arr)
{
    return arr[3];
}

thirdElement(int const*):
    mov eax, DWORD PTR 12[rdi]
    ret

No movsx, no index register, no scale. The compiler did the arithmetic itself: 3 * 4 = 12, and baked that 12 straight into the operand as a displacement. 12[rdi] means "12 bytes past the address in rdi", which is exactly &arr[3]. This is the same displacement form you saw with -4[rbp], just applied to an array. Whenever the index is known at compile time, expect to see a fixed displacement rather than a *scale term.

The Scale Changes With the Element Size

To see that the scale really is the element size, change the element type. With a char array, each element is 1 byte:

char charAt(const char* s, int i)
{
    return s[i];
}

charAt(char const*, int):
    movsx rax, esi
    movzx eax, BYTE PTR [rdi+rax]
    ret

Two things changed. First, the addressing mode is now just [rdi+rax] with no *scale at all: a scale of 1 is the default, so the assembler does not bother writing *1. The element size is 1 byte, so moving i elements means adding exactly i. Second, the load is BYTE PTR (1 byte) instead of DWORD PTR, and it uses movzx to widen the single byte up into eax for the return. The size keyword and the scale both shrank to match the smaller element.

So reading the addressing mode tells you the layout at a glance: [rdi+rax*4] is a 4-byte-element array, [rdi+rax] is a 1-byte-element array. The scale and the PTR size always agree with the type being indexed.

The Same Computation, Spelled Out at -O0

At -O0 the compiler does not pack everything into one operand. Here is elementAt unoptimized:

elementAt(int const*, int):
    push rbp
    mov  rbp, rsp
    mov  QWORD PTR -8[rbp], rdi
    mov  DWORD PTR -12[rbp], esi
    mov  eax, DWORD PTR -12[rbp]
    cdqe
    lea  rdx, 0[0+rax*4]
    mov  rax, QWORD PTR -8[rbp]
    add  rax, rdx
    mov  eax, DWORD PTR [rax]
    pop  rbp
    ret

It is longer, but every piece of the optimized version is hiding in here. The arguments are stashed on the stack, then i is reloaded and cdqe sign-extends it (the -O0 equivalent of the movsx above). The line lea rdx, 0[0+rax*4] computes i*4, the byte offset, into rdx using exactly the *4 scale. Then mov rax, ... loads the base address, add rax, rdx adds the offset to get &arr[i], and mov eax, [rax] finally loads the element. The optimizer's one-line [rdi+rax*4] is just this whole sequence collapsed into a single addressing mode.

Try It Yourself

The exercise for this lesson asks you to complete a small elementAt function and print a few array elements. Once your output is correct, read the assembly panel and find the base+index*scale operand. Confirm the scale matches the size of an int. That one operand is the entire idea of array indexing, expressed in the machine.

Key Takeaways

  • arr[i] compiles to the addressing mode [base + index*scale], computing arr + i*elementSize in one operand.
  • The scale equals the element size: *4 for int/float, *8 for long/double/pointers, *2 for short, and an implicit *1 (no scale written) for char.
  • An int index is widened to 64 bits with movsx (signed) or movzx (unsigned) before it can take part in an address.
  • A constant index is folded into a fixed displacement (e.g. arr[3] becomes 12[rdi]); no index register or scale appears.
  • The PTR size keyword (DWORD PTR, BYTE PTR, ...) always matches the element type being read.
  • At -O0 the same address is built step by step (lea for the offset, add for the base); -O2 collapses it into one [base+index*scale] operand.