Functions
Compiler Implementation
COP-3402 COP-3402

• Defined by name (usually) and its input/output

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

int g(int b) {
  return b * 2;
}

int f(int a) {
  return g(a) + 1;
}

int main() {
  printf("%d\n", f(3));
}

int x;

int f() {
  x = 1;
  y = g();
  print(x);
  print(y);
}

int g() {
  x = 2;
  return x;
}

int f() {
  int x;
  x = 1;
  y = g();
  print(x);
  print(y);
}

int g() {
  int x;
  x = 2;
  return x;
}

int factorial(int x) {
  static int old_x;

  if (x <= 0) {
    return 1;
  } else {
                old_x = x;
                x = x - 1;
    return factorial(x) * old_x;
  }
}

• Change static to auto
  • auto is the default in C
  • i.e., int x is really auto int x in a function

int factorial(int x) {
  auto int old_x;

  if (x <= 0) {
    return 1;
  } else {
                old_x = x;
                x = x - 1;
    return old_x * factorial(x);
  }
}

int fib(int n) {
        static int n_minus_1;
        static int n_minus_2;

        if (n <= 0) {
                // F_0 = 0
                return 0;
        } else if (n == 1) {
                // F_1 = 1
                return 1;
        } else {
                // F_n = F_n-1 + F_n-2
                n_minus_1 = fib(n - 1);
                n_minus_2 = fib(n - 2);
                return n_minus_1 + n_minus_2;
        }
}

int fib(int n) {
        auto int n_minus_1;
        auto int n_minus_2;

        if (n <= 0) {
                // F_0 = 0
                return 0;
        } else if (n == 1) {
                // F_1 = 1
                return 1;
        } else {
                // F_n = F_n-1 + F_n-2
                n_minus_1 = fib(n - 1);
                n_minus_2 = fib(n - 2);
                return n_minus_1 + n_minus_2;
        }
}

• Holds all information needed to "freeze" state of function
  • Parameters and local variables
  • Return address
  • Caller's stack frame (nested calls)

• Registers and/or stack

• Calling conventions and stack frame layout
  • How to pass parameters
  • Layout of data in the stack frame
  • How to return values
  • Caller and callee responsbilities
• Architecture- and OS-dependent
  • Stack frame layout on x86 64

• %rbp - base pointer points to the current function's stack frame
• %rsp - stack pointer points to the top of the stack
• push/pop - push to and pop from the stack (move data and update %rsp)
• call - saves next instruction address (%rip) onto stack and branches to function's address
• ret - pops the caller's next instruction address and branches to it

• Function definition
  • Prologue
  • Epilogue
• Function call
  • Parameter passing
  • Return value
• Stack frame layout on x86 64
• (Demo)

# https://github.com/longld/peda
# for C compile with -g for debug symbols
# run gdb
gdb example
b main # break at main
si # step instruction, assembly instructions (intead of code)
info file # get address of rodata
x/8xb 0x0000555555556000 # print memory, 8 he(x) (b)ytes
x/i addr # print as instruction

# dump symtab
objdump -s test

• data
  • Fixed size, global data section (bss section is zeroed out)
• rodata
  • Immutable data, e.g., for string constants
• text
  • Executable part

https://wiki.osdev.org/ELF

#+BEGIN_NOTES Note that the heap and stack and created at runtime by the OS

https://wiki.osdev.org/ELF#Loading_ELF_Binaries https://stackoverflow.com/questions/9226088/how-are-the-different-segments-like-heap-stack-text-related-to-the-physical-me

Memory layout

• Need to print out (emit) equivalent assembly
• Retrieve name, parameters from AST
• Type-checker provides function type guarantees

• (Diagram)

Examples for code generation

Running your assembly