Procedures (a.k.a. functions, subroutines) are the most important abstraction is progreamming.

Call Stack

A call stack is a hardware-supported, runtime data structure.

• Stores return addresses so procedures know where to return to.
• Used to allocate stack frames: per-procedure-call storage area for local variables, temporary values, and (sometimes) argument values.
• It's a stack (LIFO discipline with push and pop).

A stack pointer register %rsp contains the address of the current "top" of the stack.

• Important: the stack grows towards lower addresses, so top of stack is at lower address than the bottom of the stack.

Instruction pointer register %rip contains code address of next instruction to be updated.

• Control flow changes the value of %rip.
• Called "program counter" by other architectures.

Push and Pop push: pushes a data value onto the call stack.

• E.g., pushq %rax will decrement %rsp by 8. It stores the value in %rax at memory location pointed-to by %rsp.

pop: pops a data value from the call stack

• E.g., popq %rax loads value at memory location pointed-to by %rsp into %rax and then increments %rsp by 8.

push and pop are useful for saving and restoring register values.

• Various size operands (1, 2, 4, 8 bytes) can be pushed and popped; need to consider alignment.

Call and Ret

call instruction: calls procedure

• %rip contains address of instruction following call instruction.
• Push %rip onto the stack (as though pushq %rip was executed): this is the return address.
• Change %rip to the address of the first instruction of called procedure.
• Called procedure starts executing.

ret instruction: returns from proceudre

• Pop saved return address from stack into %rip (as though popq %rip was executed).
• Execution continues at return address.

Stack Alignment Recall: storage for multibyte values should be allocated in memory using natural alignment (if the data is 4 byte its address must be a multiple of 4.) - This is true of stack-allocated values.

The Linux x86-64 calling conventions require %rsp to be a multiple of 16 at the point of a procedure call (to ensure that 16 byte values can be accessed on the stack if necessary).

• This is an issue because an entry to a procedure %rsp mod 16= 8 because the call instruction (which called the procedure) pushed %rip (the program counter) onto the stack.

So to ensure the correct stack alignment:

• on the procedure entry: subq $8, %rsp
• and prior to procedure return: addq $8, %rsp

The Linux printf function will segfault if the stack is misaligned.

Register use conventions

There is only one set of CPU register (the storage locations that computational instructions will access- absolutely necessary for computations). Every procedure has to share this one set.

Register use conventions are rules that all procedures use to avoid conflicts. They're also called conventions.

We also need to consider how argument values are passed to called procedures. Calling conventions typically designate that some argument values are passed in specific registers.

• The procedure return value is typically returned in a specific register.

Sometimes, you can violate these conventions and get away with it. However, you should always follow the appropriate reigster use conventions because (1) they help you modularize your own code (because they set groundrules that allow procedures to interact with each other safely). (2) They allow your code to interoperate with other code, including library routines and (OS) system calls.

x86-64 Linux register use conventions:

• Arugments 1-6 passed in %rdi, %rsi, %rdx, %rcx, %r8, %r9. Argument 7 and beyond, and "large" arguments such as pass-by-value, struct data, should be passed on stack.
• integer or pointer return value returned in %rax
• Caller-saved registers: %r10, %r11 (and also the argument registers). %rax is also caller safe.
• Callee-saved registers: %rbx, %rbp, %r12, %r13, %14, %r15

Caller-saved vs Callee-saved

When a procedure is called:

• Callee-saved registers: caller may assume that the procedure call will preserve their value. In general, all procedures must save their value to memory before modifying them, and restore them before returning.
• Caller-saved registers: caller must not assume that the procedure call will preserve their value. In general, any procedure can freely modify them. A caller might need to save their contents to memory prior to calling a procedure and restore the value afterwards.

Using registers correctly means that you shoud:

• Use caller-saved registers (e.g., %r10) for very short-term temporary values or computations.
• You can use the argument registers as (caller-saved) temporary registers. However, just keep in mind that called procedures can modify them.
• Use callee-saved, temporary registers for longer term values that need to persist across procedure calls. Good as a loop variaibles.
  • Use pushq/popq to save and restore their values on procedure entry and exit.

Stack Memory Allocation

Sometimes, registeres aren't sufficient to store the data used in a procedure, so storage for variables must be allocated in memory.

Options:

• You could use global variable (in .data or .bss segments), but it can make the program behavior difficult to understand, and they aren't useful for recursive or reentrant functions. In general, it's a waste of memory.
• You could use heap allocation (i.e. malloc, free). However, there's overhead due to bookkeeping and locking.
• The call stack is the ideal place to allocate storage for local variable.

Stack Allocation

To allocate n bytes, substract n from %rsp. This updates %rsp pointer to the beginning of the allocated memory. (When you deallocate, add n to %rsp).

Complication: instructions such as push and pop will change %rsp. The solution is to use frame pointer register %rsp to keep track of allocated memory area.

Using the frame pointer On entry to the procedure,

pushq %rsp
subq $N %rsp
movq %rsp, %rbp

Then, before returning from procedure:

addq $N %rsp
popq %rbp

• %rbp points to a block of N bytes allocated in the current stack frame (make sure that N mod 16 == 0 to ensure correct stack enlightment)

Example stack allocation

.section .rodata
sPromptMsg: .string "Enter two integers: "
sInputFmtL: .string "%ld %ld"
sResultMsg: .string "Sum is  %ld\n"

.section .text
	.globl main
main:
	pushq %rbp // store what ever addres rbp is
	subq $16 %rsp // allocating 16 bytes
	movq %rsp, %rbp // point %rbp to alloc'ed buf

	movq $sPromptMsg, %rdi // print out prompt
	call printf 

	movq %sInputFmt, %rdi
	leaq 0(%rbp) %rdi // pass the address of the first var
	leaq 8(%rbp) %rdx // pass the address of the second var
	call scanf

	movq 0(%rsp) %rdi // pass value of first var 
	movq 8(%rsp) %rsi // pass value of first var 
	call addLongs // call procedure

	movq $sResultMsg, %rdi 
	movq %rax, %rsi // move the results of addLong to second var
	call printf

	addq $16 %rsp // deallocate local vars
	popq %rbp // reallocate frame pointer
	ret


addLongs // does not use stack, ignore alignment
	movq %rdi, %rax
	addq %rsi, %rax
	ret