A stack is a last-in, first-out storage structure for function-call contexts: each call pushes a context, and each return pops the current one. A machine-level stack can also hold a function’s local variables and compound literals in a reserved memory area. The stack pointer and base pointer describe that area, while offsets locate stored objects. section 15.2.2 section 13.5
Listing 13.4 An assembler version of the fgoto function
.type fgoto, @function
fgoto:
pushq %rbp # Save base pointer
movq %rsp, %rbp # Load stack pointer
subq $48, %rsp # Adjust stack pointer
movl %edi, -36(%rbp) # fgoto#0 => n
movl $0, -4(%rbp) # init j
movq $0, -16(%rbp) # init p
.L_AGAIN:
cmpq $0, -16(%rbp) # if (p)
je .L_ELSE
movq -16(%rbp), %rax # p ==> rax
movl (%rax), %edx # *p ==> edx
movq -24(%rbp), %rax # ( == q)?
cmpq -16(%rbp), %rax # (p == )?
jne .L_YES
movl $.L_STR_EQ, %eax # Yes
jmp .L_NO
.L_YES:
movl $.L_STR_NE, %eax # No
.L_NO:
movl -4(%rbp), %esi # j ==> printf#1
movl %edx, %ecx # *p ==> printf#3
movq %rax, %rdx # eq/ne ==> printf#2
movl $.L_STR_FRMT, %edi # frmt ==> printf#0
movl $0, %eax # clear eax
call printf
.L_ELSE:
movq -16(%rbp), %rax # p ==|
movq %rax, -24(%rbp) # ==> q
movl -4(%rbp), %eax # j ==|
movl %eax, -28(%rbp) # ==> cmp_lit
leaq -28(%rbp), %rax # &cmp_lit ==|
movq %rax, -16(%rbp) # ==> p
addl $1, -4(%rbp) # ++j
movl -4(%rbp), %eax # if (j
cmpl -36(%rbp), %eax # <= n)
jbe .L_AGAIN # goto AGAIN
leave # Rearange stack
ret # return statement
Use the annotated assembly to trace stack-frame setup: save the base pointer, copy the stack pointer, reserve 48 bytes, and access local objects through offsets from the base pointer. section 13.5
Recursive calls and exhaustion
With unbounded recursion, every call requires another function-call context. Because returns never remove those contexts, the finite stack eventually cannot provide space for the next one; the failure is stack overflow. Variable-length arrays can create a separate risk because their runtime-dependent sizes make stack usage difficult to estimate. section 15.2.2 section 15.2.2
