Functions

Code generation overview

Recall: compiler takes source language and produces target language
- Translate, not execute
Generates equivalent program in assembly
- Each language construct has corresponding assembly code patterns

What are functions in programming languages?

Function abstraction: encapsulate a computation

Defined by name (usually) and its input/output

User-defined extension of the language
Lots of uses: abstraction, reuse, organization, interfaces, and more
Higher-order functions can take functions as inputs
Lambda functions allow runtime creation of anonymous functions

Function behavior

(Diagram)

Caller transfers control to callee function
Caller provides input values
Callee provides output value(s)
Execution resumes in caller once callee is finished

One box for main
One box for f
Start running main (exec calls this)
Stop running main and start running f
Finish f, then resume main where we left off
Parameters and return values

Function calls in assembly

A call to function f():

retval = f()

A simple definition of a function f():

begin f()
return 5
end

x86-64 assembly

The assembly call is a branch to label f. The function definition:

f:
  mov $5, %rax
  ret

This is the call to function f():

call f
mov %rax, -16(%rbp)

The return value is saved to register %rax by convention, which is saved to a variable via a mov.

-16(%rbp) represents the retval variable. We’ll see how this works below.

How `call` and `ret` work

call f
- First saves the return address
- Then branches to f
ret
- Retrieves the return address
- Then branches back to the return address

Example

   f:
1:    mov $5, %rax
2:    ret
   _start:
3:    call f
4:    mov %rax, -16(%rbp)

_start is the entry point to the program (think main).

Diagram

Instruction pointer (address of the next instruction to execute)
Start at instruction pointer 3 (_start label)
Execute call
- Save return address (instruction pointer + 1 = 4)
- Branch to f (instruction pointer = 1)
Execute mov
Execute ret
- Retrieve return address (instruciton pointer = 4)
Execute mov

What if we have multiple nested function calls?

Use a stack

We need to save multiple return addresses while we wait for returns

Multiple calls

   h:
1:    mov $7, %rax
2:    ret
   g:
3:    call h
4:    ret
   _start:
5:    call g
6:    mov %rax, -16(%rbp)

Diagram

Start at instruction pointer 5 (_start label)
Execute call
- Push return address on to stack (instruction pointer + 1 = 6)
- Branch to g (instruction pointer = 3)
Execute call
- Push return address on to stack (instruction pointer + 1 = 4)
- Branch to h (instruction pointer = 1)
Execute mov
Execute ret
- Retrieve return address (instruciton pointer = 4)
Execute ret
- Retrieve return address (instruciton pointer = 6)
Execute mov

Function-local variables

int saved_n;  // One variable for all calls to f()

int f(int n) {
  int f_n;

  if (n <= 1) {
    return 1;
  } else {
    saved_n = n;
    n = n - 1;
    f_n = f(n);
    return f_n * saved_n;
  }
}

int main() {
  f(3);
}

Diagram

f(3)
- saved_n = 3
- f(2)
  - saved_n = 2
  - f(1)
    - return 1;
  - f_n = 1
  - f_n * saved_n = 1 * 2
  - return 2
- f_n = 2
- f_n * saved_n = 2 * 2 (want this to be 2 * 3, but saved_n was overwritten)

We need saved_n to be function-local

We need a fresh memory location for each call to a function, i.e., each call to f.

If instead we have one memory location for each definition, recursion will not work as expected.

Factorial with function-local variables

int f(int n) {
  int saved_n;  // One variable for each call to f()
  int f_n;

  if (n <= 1) {
    return 1;
  } else {
    saved_n = n;
    n = n - 1;
    f_n = f(n);
    return f_n * saved_n;
  }
}

int main() {
  f(3);
}

How do we store function-local variables? Use a stack

Diagram

f(3) (push locals to the stack)
- saved_n = 3
- f(2) (push locals to the stack)
  - saved_n = 2
  - f(1) (push locals to the stack)
    - return 1;
  - f_n = 1
  - f_n * saved_n = 1 * 2
  - return 2
- f_n = 2
- f_n * saved_n = 2 * (now this is 2 * 3, because saved_n for f(2) was saved)

Local variable allocation

begin example_variables()
locals x, y
x = 1
y = x
return y
end

x86-64 stack operations

Register %rsp always points to top element of the stack
push pushes value to stack
pop pops value from stack

The stack grows downwards

Bottom of stack is a higher memory address
Top of stack is a lower address
Push
- Subtracts from stack pointer
- Copy data into stack pointer address
Pop
- Copy data from stack pointer address
- Add to stack pointer

Implementation of push and pop - push %rax is equivalent to - sub $8, %rsp - mov %rax, (%rsp) - pop %rax - mov (%rsp), %rax - add $8, %rsp

Technically there are multiple push operations depending on the type and size of the operand

Allocating space for local variables

Slang

begin example_variables()
locals x, y
# ...
return y
end

Assembly:

example_variables:
  sub $16, %rsp # Allocate stack space for locals
  # ...
  add $16, %rsp # Deallocate stack spcae for locals
  ret

Diagram

Show stack space in memory, label stack entries with addresses
Start with the stack and stack pointer (show its value, not just as an arrow)
Step through each instruction
Show how the stack pointer and memory is updated

Using stack space for local variables

Assign each variable to a stack entry
Effectively an array of local variables

Diagram

Draw stack for example_variables
Name each stack entry according to the variable name

Allocating local variables

Save the address of the local variables
The base pointer %rbp is a special register to hold the local variable address
mov $rsp, $rbp

Why not use the stack pointer, %rsp, instead?

It may be used within the function to store data, making it hard to compute the offset

Setting the base pointer

example_variables:
  mov %rsp, %rbp    # Set the base pointer first
  sub $16, %rsp     # Allocate stack space for locals
  # ...
  add $16, %rsp     # Remove local variable stack space
  ret

set the base pointer before allocating stack space so that we always have the same offset from rbp for each variable.

The symbol table

Record the offset from %rbp (the base pointer)

locals x, y

Variable	Offset
x	-16
y	-24

Why negative offsets? Because the stack grows downwards addresses, so we store the beginning of the locals and push space for all of them.

Why start from -16? Don’t want to overwrite what’s already at %rbp (which is actually the return address since we haven’t saved the old rbp yet).

Diagram

Use rbp to point to the start of the locals
Show the offsets from rbp

Complete local variable example

Caller

retval = example_variables()

Callee

begin example_variables()
locals x, y
x = 1
y = x
return y
end

Recall

example_variables

Pushes/subtracts from %rbp to make space for locals
Saves %rbp first to track location of locals in memory
Accesses variables via offsets from %rbp

Symbol table for `example_variables`

Variable	Offset	Assembly operand
x	-16	-16(%rbp)
y	-24	-24(%rbp)

Assembly

example_variables:
  # Set the base pointer
  mov %rsp, %rbp

  push %rbx
  # Allocate stack space for locals
  sub $16, %rsp

  # x = 1
  mov $1, %rax
  mov %rax, -16(%rbp)

  # y = x
  mov -16(%rbp), %rax
  mov %rax, -24(%rbp)

  # Return value
  mov -24(%rbp), %rax

  # Remove local variable stack space
  add $16, %rsp
  pop %rbx
  ret

Diagram

Stack with addresses
rsp and rbp with address values and arrows
rax

Saving the caller’s base pointer

Where does rbp point to after a function returns?

It still points to the callee’s stack frame

Save and update `rbp`

Save the caller’s rbp before setting it

push %rbp       # Save old base ponter
mov %rsp, %rbp  # Set new base pointer

Restore `rbp`

Pop the caller’s rbp before returning

pop %rbp    # Restore the caller's base pointer

Complete stack frame setup

example_variables:
  push %rbp         # Save the caller's base pointer
  mov %rsp, %rbp    # Set the base pointer

  push %rbx         # Save old %rbx

  sub $16, %rsp     # Allocate stack space for locals

  # ...

  add $16, %rsp     # Remove local variable stack space
  pop %rbx          # Restore the caller's base pointer
  pop %rbp          # Restore the caller's base pointer

  ret               # Return

Function prologue

push %rbp       # Save the caller's base pointer
mov %rsp, %rbp  # Set the base pointer
push %rbx       # Save old %rbx
sub $16, %rsp   # Allocate stack space for locals

Function epilogue

add $16, %rsp   # Remove local variable stack space
pop %rbx        # Restore old %rbx
pop %rbp        # Restore the caller's base pointer
ret

Complete example

Caller

begin main()
locals retval
retval = example_variables()
return retval
end

Callee

begin example_variables()
locals x, y
x = 1
y = x
return y
end

Assembly

example_variables:
  # Prologue
  push %rbp         # Save the caller's base pointer
  mov %rsp, %rbp    # Set the base pointer
  push %rbx         # Save old %rbx
  sub $16, %rsp     # Allocate stack space for locals

  # x = 1
  mov $1, %rax
  mov %rax, -8(%rbp)

  # y = x
  mov -8(%rbp), %rax
  mov %rax, -16(%rbp)

  # return y
  mov -16(%rbp), %rax

  # Epilogue
  add $16, %rsp     # Remove local variable stack space
  pop %rbx          # Restore old %rbx
  pop %rbp          # Restore the caller's base pointer
  ret

Diagram

Stack with address labels
rbp, rbp with addresses and arrows
Start with stack frame setup for main
- Caller is C runtime, rbp and return value can be any addresses
- One entry for retval
Step through the call to example variables

Calling convention

Stack frame layout
System V x86-64 Application Binary Interface (ABI) defines it

More resources on the ABI and calling conventions

https://sourceware.html/git/?p=glibc.git;a=blob;f=stdio-common/vfprintf-internal.c;h=547a3a868b4668bf615cf3f39a92e3c11cbb98ad;hb=HEAD#l1288

https://wiki.osdev.html/Calling_Conventions

https://eli.thegreenplace.net/2011/09/06/stack-frame-layout-on-x86-64/

https://en.wikipedia.html/wiki/X86_calling_conventions#Register_preservation

https://stackoverflow.com/questions/1658294/whats-the-purpose-of-the-lea-instruction

https://www.fireeye.com/blog/threat-research/2008/03/instruction-poi.html

Layout

Caller-managed
- Stack-allocated parameters
- Return address
Callee-managed
- Old base pointer
- Local variables

Caller has access to the parameters and its own return address.

The callee also has to save certain registers if it uses them, e.g., rbx

Passing parameters

Since each function has its own local state, how do we communicate values from one function to another?

Registers and stack parameters

Use registers for some
Use the stack for the rest
- Callee can now access them without caller’s stack frame

Complete stack frame

Stack contents	Managed by
Parameter N	Caller
Parameter N-1	Caller
…	Caller
Parameter 8	Caller
Parameter 7	Caller
Return address	Caller
———————–	————
Old base pointer	Callee
Local variable 1	Callee
Local variable 2	Callee
…
Local variable N	Callee

Where are parameters 1-6? These are the parameters passed via registers in the x86-64 System V ABI

See this blog post for more information.

8 parameters
6 on registers
2 on stack
caller sets up registers and stack
caller sets return address (call)
caller branches to the callee function
callee saves the old base pointer
callee allocates space for its local variables
stack teardown happens in reverse order

Parameter example

begin main()
locals retval, x
x = 3
retval = func(x)
return retval
end

begin func(a)
return a
end

Assembly

main:
  # Prologue
  pushq %rbp        # Save old base ponter
  movq %rsp, %rbp   # Set new base pointer
  push %rbx         # Save old %rbx
  sub $16, %rsp     # Allocate stack space for locals

  # Assign 3 to x
  mov $3, %rax
  mov %rax, -24(%rbp)

  # Function call
  mov -24(%rbp), %rdi
  call func
  mov %rax, -16(%rbp)

  # Set return value
  mov -16(%rbp), %rax

  # Epilogue
  add $16, %rsp     # Deallocate stack space for locals
  pop %rbx          # Restore old %rbx
  pop %rbp          # Restore %rbp
  ret               # Return

func:
  # Prologue
  pushq %rbp        # Save old base ponter
  movq %rsp, %rbp   # Set new base pointer
  push %rbx         # Save old %rbx
  sub $8, %rsp      # Allocate stack space for locals

  # Move register parameter a to local variable
  mov %rdi, -16(%rbp)

  # Set return value
  mov -16(%rbp), %rax

  # Epilogue
  add $8, %rsp      # Deallocate stack space for locals
  pop %rbx          # Restore old %rbx
  pop %rbp          # Restore %rbp
  ret               # Return

Code generation overview

What are functions in programming languages?

Function abstraction: encapsulate a computation

Function behavior

Function calls in assembly

x86-64 assembly

How call and ret work

Example

Multiple calls

Function-local variables

Factorial with function-local variables

Local variable allocation

x86-64 stack operations

The stack grows downwards

Allocating space for local variables

Using stack space for local variables

Allocating local variables

Setting the base pointer

The symbol table

Complete local variable example

Recall

Symbol table for example_variables

Assembly

Saving the caller’s base pointer

Save and update rbp

Restore rbp

Complete stack frame setup

Function prologue

Function epilogue

Complete example

Assembly

Calling convention

Layout

Passing parameters

Registers and stack parameters

Complete stack frame

Parameter example

Assembly

How `call` and `ret` work

Symbol table for `example_variables`

Save and update `rbp`

Restore `rbp`