Code Generation: Globals and Functions
Lecture 09

Code generation overview
Function semantics
Function implementation
Implementing functions in SimpleC
Readings
Assembly language resources

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

Assembly file layout

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

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

What about local variables, malloc'ed data?

Local variables and heap-allocated variables are stored in memory allocated at runtime
Running program (process) works with the OS to be allocated memory as needed at load and runtime

Function semantics

What are functions in programming languages?

Function abstraction: encapsulate a computation

Defined by name (usually) and its input/output

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

How do functions work?

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

Function calls "freeze" state of caller

(Diagram)

How would you implement this with just assembly?

Save state on stack
Unconditional branch
Save return value
Another branch to go back to where we left off

"Nested" function calls freeze state of many callees

(Diagram)

Can think of recursive functions as invokes a fresh instance of the function, rather than calling itself.

Function implementation

Stack frame (or activiation record)

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

Parameter passing

Registers and/or stack

Registers are faster, but limited in number
May need to save them before making call

Application binary interface (ABI)

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

Note that parameter passing is done through registers for the first 6 parameters, then on the stack as needed.

More resources on the ABI and calling conventions

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

https://wiki.osdev.org/Calling_Conventions

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

https://en.wikipedia.org/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

Intel x86-64 support for functions

%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

Recall that "points to" just means that the register holds an address

Writing and calling ABI-compatible functions

Function definition
- Prologue
- Epilogue
Function call
- Parameter passing
- Return value
(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

gdb resources:

https://sourceware.org/gdb/onlinedocs/gdb/Memory.html

https://sourceware.org/gdb/onlinedocs/gdb/Registers.html#Registers

https://visualgdb.com/gdbreference/commands/set_disassembly-flavor

http://dbp-consulting.com/tutorials/debugging/basicAsmDebuggingGDB.html

https://github.com/longld/peda

https://sourceware.org/gdb/onlinedocs/gdb/Auto-Display.html#Auto-Display https://sourceware.org/gdb/onlinedocs/gdb/Continuing-and-Stepping.html https://sourceware.org/binutils/docs-2.16/as/index.html https://sourceware.org/binutils/docs/as/i386_002dMemory.html

Implementing functions in SimpleC

Recall: compiler is translating (not executing) the function

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

Generate while walking the tree

(Diagram)

Implement by emitting assembly "templates" from the compiler

(Coding demo)

make CFLAGS="-g" # turn on debugging symbols

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
objdump -s test