Code Generation 2
COP-3402

This function is given to you. It creates assembly code boilerplate for you.

This function generates assembly instructions that allocate space on the stack for all local variables. In SimpleIR, all variables are 64-bit integers. enterLocalvars is given to you. It works by first collecting the set of variables to allocate space for from the syntax tree of the input program:

locals = [ local.getText() for local in ctx.NAME() ]

Then it creates space on the stack for each local variable. The memory location of each local variable can be determined by an offset from the base pointer %rbp per the System V AMD64 ABI. The compiler records each variables offset in a table that maps the name of the variable to its offset from %rbp, which the compiler will use to translate variable accesses and assignments whenever the variable is used in SimpleIR instructions. The given enterLocalvars function creates this dictionary with a little python cleverness, i.e.,

# create a list of offsets of the bytewidth
offsets = map(lambda x: (x+1)*-self.bytewidth, range(len(locals)))
# create a dictionary mapping locals to offsets
self.symtab = dict(zip(locals, offsets))

self.symtab now contains a mapping from each local variable to its own offset (which are multiples of the 8-byte width), e.g., -8, -16, -24, etc. (Do you remember why the offsets are negative in this ABI?)

Finally, the functions computes the total amount of space required for the local variables (number of variables times 8 bytes each), aligns the stack to 16 bytes (required by the ABI), and emits a assembly instruction that updates the stack pointer to allocate the space, i.e.,

# compute the size of the stack space
stackspace = len(self.symtab.keys()) * self.bytewidth
logging.debug(stackspace)
# ceiling to 8 bytes
stackoffset = math.ceil(stackspace / 8) * 8
# align to 16 bytes by adding 8 to account for rbx if already aligned to 16 bytes
stackoffset += (stackoffset + 8) % 16
logging.debug(stackoffset)
# Emit an instruction to allocate stack space for locals
self.outfile.write(indent(dedent(f'''\
    # allocate stack space for locals
    sub\t${stackoffset}, %rsp
'''), '\t'))

Because of this function, self.symtab will tell you how to translate variable uses into offsets from the base pointer %rbp for generating equivalent assembly instructions.

The syntax of the assignment statement is

assign: NAME ':=' operand=(NAME | NUM);

Notice that operand may either be a NAME (which is the syntax of an identifier) or a NUM (which is the syntax for an integer literal). An assignment takes either a constant integer literal or a variable identifier and copies that data to the left-hand side variable. This translates to either a mov immediate to a register (integer literal) or a load from memory to a register (variable name on right-hand side), followed by a store of that value to the memory location associated with the variable name.

If the right-hand side is a variable name, the compiler will generate a load from the memory location of the variable to a temporary register (we'll use %rax for the temporary register). To determine the memory location, recall that our compiler assigns each local variable an offset from %rbp that we stored in a offset table created by enterLocalvars. For example, if variable b has offset -24 from %rbp, to load that memory location's value into %rax, we use the following instruction:

mov -24(%rbp), %rax

-24(%rbp) means, take the value of %rbp (which is a pointer to the current stack) frame, add -24 to it, then dereference the address and load that value into %rax.

To implement this in our compiler, enterAssign first determies whether the operand is a NAME or a NUM, i.e.,

if SimpleIRParser.NAME == ctx.operand.type:

When the operand is a NAME, the compiler creates the %rbp-indirect offset argument, e.g., -24(%rbp), i.e.,

operand = f"{self.symtab[ctx.operand.text]}(%rbp)"

When the operand is a NUM, we only need to use an immediate value argument, i.e.,

elif SimpleIRParser.NUM == ctx.operand.type:
    operand = f"${ctx.operand.text}"

Either way, the operand python variable now contains the corresponding assembly instruction argument for the right-hand side of the SimpleIR statement.

Finally, enterAssign generates the copy of the right-hand side to the temporary register %rax, then stores the value into the memory location of the left-hand side variable:

self.outfile.write(indent(dedent(f'''\
    # assign {ctx.operand.text} to {ctx.NAME(0).getText()}
    mov\t{operand}, %rax
    mov\t%rax, {self.symtab[ctx.NAME(0).getText()]}(%rbp)
'''), '\t'))

The left-hand size variable's memory location can also be found using the offset table (self.symtab). The name of the variable is retrieved from syntax tree with ctx.NAME(0).getText(), since the left-hand side variable is the first NAME in the grammar for the assignment.

To create the function, emit the assembly pseudo-ops .globl and .type with the name of the function (ctx.NAME()), as well as a label for the function. Then emit the prologue. Use whatever the name of the function is for all three, e.g., for the function factorial the function creation and prologue would look like this:

        .globl factorial
        .type factorial, @function
factorial:
  # prologue
        pushq	%rbp # save old base ponter
        movq	%rsp, %rbp # set new base pointer
        push	%rbx # %rbx is callee-saved

Emit the assembly function epilogue and return instruction, i.e.,

# epilogue
mov	%rbp, %rsp # restore old stack pointer
pop	%rbp # restore old base pointer
ret

This is the same for all functions.

In SimpleIR, the input program first declares all local variables, e.g.,

localvars x a b c d e f g h

then it declares which of those local variables is a parameter, e.g.,

params a b c d e f g h

In the above example, all local variables, except for x are also parameters. The set of parameters is a subset of the local variables (or the same set).

The enterLocalvars function emits code that creates space for all local variables, including parameters. enterParams then copies the parameter values set by the caller to the corresponding parameter local variables. For instance, for the above set of params, the following assembly code copies the caller's values to the callee's local variables:

# move register parameter a to local variable
mov	%rdi, -16(%rbp)
# move register parameter b to local variable
mov	%rsi, -24(%rbp)
# move register parameter c to local variable
mov	%rdx, -32(%rbp)
# move register parameter d to local variable
mov	%rcx, -40(%rbp)
# move register parameter e to local variable
mov	%r8, -48(%rbp)
# move register parameter f to local variable
mov	%r9, -56(%rbp)
# move stack parameter h to local variable
mov	16(%rbp), %rax
mov	%rax, -72(%rbp)
# move stack parameter g to local variable
mov	24(%rbp), %rax
mov	%rax, -64(%rbp)

The caller passes parameters both via registers and the stack, the first six via registers and the rest via the stack. To copy these parameters to the memory locations for the callee's local variable, enterParams generates mov instructions for the first size parameters from the ABI-defined set of parameter registers, i.e.,

registers = [ "%rdi", "%rsi", "%rdx", "%rcx", "%r8", "%r9" ]

enterParams can retrieve the list of parameters names for the input program from the ANTLR syntax tree, i.e.,

params = [ param.getText() for param in ctx.NAME() ]

The list of register and stack parameters can be spliced with

register_params = params[0:6]
stack_params = params[6:]

For each of the register parameters, generate a mov from the corresponding register to the local variable's memory location. The local variables' memory locations are offsets from the base pointer, as described in enterLocalvars, i.e., by passing the name of the variable to self.symtab to get the offset. Then generate the mov instruction from the register, e.g., from the example above

# move register parameter c to local variable
mov	%rdx, -32(%rbp)

This instruction stores the value in %rdx, i.e., the third parameter, into -32(%rbp), which is the memory location of the local variable c for the above program. See enterAssign for more details on getting the memory location of local variables.

For the stack allocated parameters, mov them from the stack to the local variable. Since this is move between two memory location, the instruction set requires first copying to a temporary register (we'll use %rax), resulting in two move instructions. The first instruction copies from the parameter's memory location on the stack to %rax, e.g.,

mov	16(%rbp), %rax

Then the next instruction copies from %rax to the location variable's memory location, given by self.symtab, e.g.,

mov	%rax, -72(%rbp)

The offsets are positive from the %rbp (why is this the case?) and they start from 16. This is because %rbp plus 0 is the old base pointer, %rbp plus 8 is the return address, then %rbp plus 16 is the 7th parameter (the first after the register parameters), %rbp plus 24 is the 8th, etc.

See these resources for more information on gdb.

• Basic Assembler Debugging with GDB
• Chapter 2 of 21st Century C

function main
localvars argc argv x a b c d e f g h
params argc argv
a := 1
b := 2
c := 3
d := 4
e := 5
f := 6
g := 7
h := 8
x := call paramtest a b c d e f g h
return x

Try assigning x to different input parameters to test that parameters are being passed correctly both through registers and through the stack.

function paramtest
localvars x a b c d e f g h
params a b c d e f g h
x := c
return x