Skip to content

Latest commit

 

History

History
119 lines (106 loc) · 6.42 KB

notes.md

File metadata and controls

119 lines (106 loc) · 6.42 KB

Codegen Notes

For our codegen method (of ast node), we need the following parameters:

  • Output stream: where the assembly is being printed to
  • Context struct (TBD): Stores the info we need regarding stuff
  • Destreg: register where the result of the operation is stored

Registers

$0: Set to 0 $at (1): Don't touch $v0-$v1 (2-3): Return value from subroutine (if value is 1 word then only $v0 is needed) $a0-$a3 (4-7): Function arguments $t0-$t9 (8-15, 24-25): Temporary registers (whatever we want) $s0-$s7 (16-23): Saved registers (value is preserved across function calls) $k0-$k1 (26-27): Don't touch $gp (28): Global pointer (used for static global variables - probably ignore) $sp (29): Stack pointer $fp (30): Frame pointer $ra (31): Return address in subroutine call

Stack Frame Shit

The stack grows downwards (i.e. decrement $sp to allocate space), and a stack frame contains 5 sections (order is top of the stack to bottom of the stack -- lower addressed memory to higher addressed memory):

  • Argument section (must always allocate at least 4 words), used to store arguments that are passed to any subroutine that are called by the current subroutine. Slots are allocated by the caller but used by the callee
  • Saved registers section, used to store the values in $s0-$s7 which need to be preserved across function calls (must copy values back before returning)
  • Return address section, used to store $ra (so in can be restored after nested function call)
  • Pad section, used to ensure the total size of the stack is a multiple of 8 (doubleword alighned)
  • Local Data storage section, used for any local variable storage (enough words must be reserved for a function to fit all it's local data, including the value of any temporary registers it needs to preserve across subroutine calls)

More specific stuff

  • For a function, search through it's scope to see if it contains a function call, if it doesn't it's a leaf function (i.e. doesn't need to store $ra in the stack)
  • If a function doesn't contain any declarations in it's scope, it's a simple function that doesn't need any stack pointer changes
  • If a function does contain declarations (i.e. local variables that need space to be stored), it's stack can just contain space for those local variables:
int g(int x, int y){
  int a[32];
  // Do stuff
  return a[0];
}

Would produce the following assembly:

addiu $sp,$sp,(-128) # push stack frame to allocate space for array of 32 ints (32*4 = 128)
... # do stuff
lw $v0,0($sp) # $sp is pointing at start of array a
addiu $sp,$sp,128 # pop stack frame
jr $ra # return

Stack implementation

Current mental model for our stack allocation is as follows:

  • At the start of a function call, stack decrements by 8, storing $ra and $fp (this is the bottom of the stack frame)
  • When needed, local variables can be stored in the stack and the stack pointer get incremented as needed.
  • Whenever we encounter a variable as we traverse our AST (within a function), that variable is immediately stored in the stack / assigned space, it's stored in varBindings for the current frame, and the stack pointer is incremented appropriately.
  • When a sub-function call is encountered, all data registers are stored in the stack (should already be done), the required space is allocated at the top of the stack as we go through the parameter list and the required space for arguments of the called sub-function is created at the top of the stack.
  • At the start of a function, the frame pointer will update to the stack pointer, which has decremented by 8 to store $ra and $fp. This means that when local variables are stored and the stack is decremented, the offset stored in the variable map will be relative to the frame pointer (i.e. 1st variable stored will have an offset of 4 provided it's size is 1 word).

When we do a function call, we increment the frame pointer by the size of the previous stack (+ 8? check values) so that we can increment the stack pointer as we copy the parameters, and then move our frame pointer once this is completed to the top of the copied parameters.

More on the copying process. We copy the arguments into the next stack frame at the function call, but DO NOT INCREMENT THE STACK POINTER (this will be done later in the function def) when copying, store things at offset of (stackFrame.offset+param.size). The stackFrame.argSize will tell us by how much to increment the stack pointer by later.

Small update for this, we need to rework where arguments are stored on the stack to ensure compatability with the assembly generated by gcc in the testing process. This should be fine, I'll just need to update the offset for the parameters in funciton def, and update the copy process in function call when it's created.

Global stuff

This is how we should codegen the global variable int x = 42;:

.globl x
.data
.size x, 4
x:
  .word 42

This is how we should codegen the global variable int x;:

.globl x
.data
.size x, 4
x:
  .space 4

This is how should codegen the global array int arr[2]:

.globl arr
.data
.size arr, 8
arr:
  .space 8

This is how we should codegen the global array int arr[2] = {9, 10}:

.globl arr
.data
.size arr, 8
arr:
  .word 9
  .word 10

Therefore in general in our root node we need to:

  • Check isFunction() to see if variable
  • Print directives .globl <id> and .data
  • Check getArraySize() to see how big data is (in bytes)
  • Print .size <id>, <size>
  • Print <id>:
  • Check isInit()
  • If not init, use .space <size>
  • If init, use .word <value>, repeat for arrays

Floats

For floating point operations, we won't track the floating point registers, and exclusively use $f0+f1 and $f2+f3 as the 2 registers for floating point operations, with results always stored in $f0+f1. It is the job of the assignment instructions to move floating point results from the floating point registers back to the usual mips registers, as well as convert single register floats into double precision floats if needed => need to check if float/double for binary assign, init declarator and return (we'll need to add return type information to functions). All other operations managing floating points will use the floating point registers as destreg.

IMPORANT: operation li.s creates a single precision float => will need to upscale do double if needed

RANDOM NOTE: WE NEED TO CHECK IF RIGHT OP IS FUNCTION FOR REST OF BINARY ASSIGN + INIT DECLARATIONS