The stack and the frame pointer
prerequisite
Read these first:
The stack is the memory a function uses for its own working storage: saved registers, local variables, and the bookkeeping that lets control return to the caller. It grows downward, from higher addresses toward lower ones, and the stack pointer sp points at the lowest in-use byte.
The frame pointer fp, the register x29, marks a fixed point in the current function's slice of the stack, its frame. Because sp can move during a function, code reads and writes locals at steady offsets from fp instead, so each local keeps one stable address for the life of the call.
Where the stack lives
A running program's memory is split into regions. The instructions and the global variables sit at the low end, the stack starts near the top, and the space between is shared by two regions that grow toward each other:
higher addresses +----------------------+ | stack | grows down as functions open frames | | | | v | | | | ^ | | | | | heap | grows up as malloc hands out memory +----------------------+ | .bss | globals that start at zero | .data | globals with starting values | .text | the program's instructions +----------------------+ lower addressesBecause sp points at the last byte in use and the stack grows toward lower addresses, this kind of stack is called full descending. AArch64 has no push or pop instruction; the pre-index and post-index forms do the job. str x19, [sp, -16]! is a push: move sp down 16 bytes, then store. ldr x19, [sp], 16 is a pop: load, then move sp back up. Both move sp by 16 even though x19 is 8 bytes, to keep sp a multiple of 16.
The prologue and epilogue
A function that calls other functions opens with a prologue and closes with an epilogue. The prologue saves the caller's frame pointer and the return address, then claims space for the new frame; the epilogue restores them and hands control back.
The pair instructions do this in one step each. stp fp, lr, [sp, alloc]! is a pre-index store: it first adds alloc to sp, and since alloc is negative (-32 in the program below), that moves sp down by 32 bytes; then it stores fp and lr at the address sp now holds. The epilogue's ldp fp, lr, [sp], dealloc is a post-index load: it reads the two back, then adds dealloc (32) to lift sp back up. Between the two, mov fp, sp points fp at the new frame. The program below prints n = 5.
// The frame skeleton: prologue, one local by fp offset, epiloguedefine(fp, x29)define(lr, x30)define(n_r, w9)n_s = 16alloc = -(16 + 16) & -16dealloc = -alloc.datafmt: .string "n = %d\n".text .balign 4 .global mainmain: stp fp, lr, [sp, alloc]! // save fp+lr and open the frame mov fp, sp mov w0, 5 str w0, [fp, n_s] ldr n_r, [fp, n_s] ldr x0, =fmt mov w1, n_r bl printf mov w0, 0 ldp fp, lr, [sp], dealloc // restore fp+lr and close the frame retWhat lr holds
bl label does two things: it puts the address of the instruction after the bl into lr, the register x30, and it jumps to label. ret jumps to whatever address lr holds. That is how a function finds its way back to its caller.
When main starts, lr holds the address in the C start-up code that called main. The first bl printf inside main overwrites lr with an address inside main, so without a saved copy, main's own ret would jump back into main instead of out of it. The prologue saves lr for exactly this reason. The 16 bytes holding the saved fp and lr are called the frame record, and because each saved fp points at the caller's frame record, the records form a chain back through every active call.
warning
Two rules keep a frame correct. First, sp must stay a multiple of 16 whenever it is used to reach memory or another function runs, which is why the frame size is rounded with & -16. Second, a function that calls anything must save fp and lr on entry and restore them before it returns: lr holds the address to return to, and a call overwrites it, so losing it strands the function with no way back.
Locals in the frame
Local variables live at fixed offsets above fp. Storing one is str w0, [fp, 16]; reading it back is ldr w1, [fp, 16]. The offsets are yours to choose, as long as they stay inside the space the prologue reserved. Course programs name each offset once at the top, as in a_s = 16. That line is an assembler equate: a name for a number, fixed before the program runs. define(a_s, 16) does the same job through m4. The assembler can also give a register a second name, as in fp .req x29, but course programs name registers with m4 define lines instead.
The reserved size comes from the alignment formula alloc = -(16 + locals) & -16, where locals is the number of bytes the function needs. The leading sixteen bytes hold the saved fp and lr pair, and the & -16 rounds the frame up to a multiple of sixteen so the stack keeps its alignment.
Here is the rounding worked out for two 4-byte ints. -(16 + 8) is -24. In two's complement, -16 is all 1s except for four 0s at the bottom, so & -16 clears the lowest four bits of -24:
-24 ...1111 1110 1000 -16 ...1111 1111 0000 -24 & -16 ...1111 1110 0000 = -32Clearing low bits of a negative number moves it further from zero, so the frame can only grow: 24 bytes needed, 32 reserved, and dealloc is 32.
The two editors below allocate frames, fill locals with fixed values, and read them back by offset. The first prints sum = 13, product = 42 and the second prints total = 42.
Reading input into the frame
A frame local is a good place for scanf to put what it reads, because scanf needs the address of each variable, and a local's address is fp plus its offset. add x1, fp, first_s computes that address; it does not load anything. After the call the numbers sit in the frame, safe from anything scanf did to x0 through x18, and ldr brings them into registers.
The program below reads two whole numbers and prints the larger. The lesson feeds it 27 45, so it prints a = 27, b = 45, the larger is 45. Its frame holds two 4-byte ints, so it uses the alloc worked out above.
pitfall
ldr x1, [fp, first_s] in place of add x1, fp, first_s hands scanf the value stored in the local instead of its address. scanf then writes to whatever address that value happens to be, and the program either crashes or quietly changes memory it does not own.
Locals made partway through
A function does not have to claim all its space in the prologue. A block of code that needs a temporary local can move sp down when it starts and back up when it ends. The new bytes sit below fp, so they are reached with negative offsets. The program below prints block local = 99.
// Make room for a local partway through main, use it, then give the room backdefine(fp, x29)define(lr, x30)t_s = -16 // the block's local sits below fp.datafmt: .string "block local = %d\n".text .balign 4 .global mainmain: stp fp, lr, [sp, -16]! mov fp, sp sub sp, sp, 16 // 16 more bytes, so sp stays a multiple of 16 mov w9, 99 str w9, [fp, t_s] ldr x0, =fmt ldr w1, [fp, t_s] bl printf add sp, sp, 16 // hand the bytes back before the epilogue mov w0, 0 ldp fp, lr, [sp], 16 retTwo details matter. The block moves sp by 16, not by the 4 bytes it uses, so sp stays a multiple of 16 while printf runs. And the block gives its bytes back with add sp, sp, 16 before the epilogue, because ldp fp, lr, [sp], 16 reads the saved pair at sp: with sp still 16 bytes low, it would load the wrong values and ret would jump to a bad address.
pitfall
Common mistakes from this lesson, each with a broken program and its fix that you can run:
Check yourself
- A function needs five 4-byte ints as locals. What are
allocanddealloc? - After
stp fp, lr, [sp, -32]!andmov fp, sp, where are the savedfpandlr, and what is the lowest offset fromfpa local can use? - Why does
mainneed to savelrwhen it callsprintf, even thoughmainnever useslritself?
answers
show answers
- The locals take 20 bytes, so -(16 + 20) is -36, and -36 & -16 is -48.
allocis -48 anddeallocis 48. fpis saved at[fp]andlrat[fp, 8], so the first free offset is 16.main's finalretuseslr.bl printfreplaceslrwith a return address insidemain, so without the saved copy,retwould never leavemain.
Practice
- Stack of plates: four locals at named frame offsets, loaded back top first.
- The leaky frame: a program that crashes because
sploses its alignment. Find the line and fix it. - Three in a row: three locals in the frame, filled by
scanfand printed smallest first. - Intermediate quiz: memory and the stack and challenge: frame layout, locals made inside a block, and alignment.
- Predict: memory and the stack (challenge): work out frame sizes, padding, and the address a store writes to.