Code Generation 4
COP-3402

Here is the start to compiler/CodeGen.py

import os
import sys
import math
from textwrap import indent, dedent
from antlr4 import *
from grammar.SimpleIRLexer import SimpleIRLexer
from grammar.SimpleIRParser import SimpleIRParser
from grammar.SimpleIRListener import SimpleIRListener
import logging
logging.basicConfig(level=logging.DEBUG)

# This class defines a complete listener for a parse tree produced by SimpleIRParser.
class CodeGen(SimpleIRListener):
    def __init__(self, filename, outfile):
        self.filename = filename
        self.outfile = outfile
        self.symtab = {}
        self.bitwidth = 8

    def enterLocalvars(self, ctx:SimpleIRParser.LocalvarsContext):
        """Allocates space for local variables, including input parameters"""
        # get list of local variables
        locals = [ local.getText() for local in ctx.NAME() ]
        # create a list of offsets of the bitwidth
        offsets = map(lambda x: (x+1)*-self.bitwidth, range(len(locals)))
        # create a dictionary mapping locals to offsets
        self.symtab = dict(zip(locals, offsets))
        logging.debug(self.symtab)
        # compute the size of the stack space
        stackspace = len(self.symtab.keys()) * self.bitwidth
        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'))

    def enterAssign(self, ctx:SimpleIRParser.AssignContext):
        """Assign value to a variable"""
        if SimpleIRParser.NAME == ctx.operand.type:
            operand = f"{self.symtab[ctx.operand.text]}(%rbp)"
        elif SimpleIRParser.NUM == ctx.operand.type:
            operand = f"${ctx.operand.text}"
        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'))

    def enterDeref(self, ctx:SimpleIRParser.DerefContext):
        """Derefence a variable and assign is value"""
        # TODO
        pass

    def enterRef(self, ctx:SimpleIRParser.RefContext):
        """Get the address of a varaible"""
        # TODO
        pass

    def enterAssignderef(self, ctx:SimpleIRParser.AssignderefContext):
        """Assign to a dereferenced variable"""
        # TODO
        pass

def main():
    import sys
    if len(sys.argv) > 1:
        filepath = sys.argv[1]
        input_stream = FileStream(filepath)
        filename = os.path.basename(filepath)
    else:
        input_stream = StdinStream()
        filename = "stdin"

    lexer = SimpleIRLexer(input_stream)
    stream = CommonTokenStream(lexer)
    parser = SimpleIRParser(stream)
    tree = parser.unit()
    if parser.getNumberOfSyntaxErrors() > 0:
        print("syntax errors")
        exit(1)
    # print(tree.toStringTree())
    walker = ParseTreeWalker()
    walker.walk(CodeGen(filename, sys.stdout), tree)

if __name__ == '__main__':
    main()

The CodeGen class provides a self.outfile file to write to. In python, write a string using

self.outfile.write("The string to emit")

Alternatively, you can use a format string to make creating templates easier, where anything inside curly braces is evaluated, e.g., the following prints a string followed by the contents of a variable called name:

self.outfile.write(f"This is the what is in the name variable: {name}")

To retrive ANTLR parse tree contents, use the ctx context parameter provided to each listener using the name of the token, e.g., the following will get the NAME token from the syntax tree for a function production and store it in the name python variable.

name = ctx.NAME()

Given a derefence statement, e.g.,

t2 := *t1

where the variables have the following offsets

the following assembly code will load the value at the addressed stored in t1 and store that value into t2

mov -40(%rbp), %rax  # value of the deref'ed variable (t1)
mov (%rax), %rbx  # the value in memory at address %rax (*t1)
mov %rbx, -48(%rbp)  # store the result in the assigned var (t2)

Recall that the offset of variables is stored in self.symtab.

Given a reference statement, e.g,.

t1 := &x

where the variables have the following offsets from the base pointer

the following assembly code will store the address of x into t1

mov %rbp, %rax  # start with stack frame address
add $-24, %rax  # add the offset of the referenced var (x)
mov %rax, -40(%rbp)  # store the result in the assigned var (t1)

Recall that the offset of variables is stored in self.symtab.

Given a dereference assignment statement

*t1 := 11

where t1 has offset -40, the following assembly will store the value 11 into the address given by t1

mov	-40(%rbp), %rax # get the value of ~t1~
mov	$11, %rbx # get the right-hand-side value
mov	%rbx, (%rax) # store %rbx into the address in memory given by %rax

(%rax) means store not to %rax itself, but to the memory location given by the address in %rax.

Recall that the offset of variables is stored in self.symtab.

See these resources for more information on gdb.

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

cd ~/codegen4
wget https://www.cs.ucf.edu/~gazzillo/teaching/cop3402fall24/files/compiler-examples.tar
tar -xvf compiler-examples.tar

Download the wrapper here.

cd ~/codegen4
wget https://www.cs.ucf.edu/~gazzillo/teaching/cop3402fall24/files/compiler-wrapper.tar
tar -xvf compiler-wrapper.tar

Be sure your compiler only defines the functions given in the template (enterLocalvars, enterAssign, enterOperation, enterLabel, enterGoto, enterIfgoto). Do not define enterUnit, enterFunction, exitFunction, or enterCall and just omit them from your CodeeGen.py, since code from these functions are pregenerated in the wrapper template for you.

Enter your code to compile inside of the given main.ir where it says "add your code to try out here". Do not change any other lines of the program.

function main # DO NOT CHANGE
localvars a b c d e f g result retval # DO NOT CHANGE
# add your code to try out here
retval := call print_int result # DO NOT CHANGE
return 0 # DO NOT CHANGE

Be sure to assign result to your desired output, since this will be printed by print_int. Here is an example use of the wrapper:

function main # DO NOT CHANGE
localvars a b c d e f g result retval # DO NOT CHANGE
# add your code to try out here
a := 7
b := 4
result := 7 % 4
retval := call print_int result # DO NOT CHANGE
return 0 # DO NOT CHANGE

Compile main.ir with the wrapper using the following (be sure you have downloaded it already and that you are in your pipenv shell):

cd ~/codegen4
make -C wrapper clean all

This will run codegen and add the resulting assembly to a template assembly file, the assembly into a program called wrapper.elf. If compilation fails you will see error output, such as

main.s: Assembler messages:
main.s:16: Error: symbol `main' is already defined
make: *** [Makefile:18: main.o] Error 1

Your error will vary depending on what went wrong.

If compilation and assembly were successful, you can run the program with

./wrapper/wrapper.elf

It will print whatever was set to result in your main.ir.

The wrapper contains the precompiled main.ir split into wrapper_start.s and wrapper_end.s. These contains the assembly code produced by a complete implementation of codegen2 for the function, call, and return IR statements.

The Makefile runs your codegen and saves the output to main.s, i.e.,

codegen main.ir | tee main.s.body

Then it "wraps" the output of your compiler with the start and end of the precompiled assembly file to produce a complete main.s assembly program, i.e.,

cat wrapper_start.s main.s.body wrapper_end.s > main.s

Finally, it assembles main.s as usual and links it with iolib.c, which provides the print_int function, into the executable wrapper.elf:

gcc -c main.s
gcc -o wrapper.elf main.o iolib.c  

The only file you need to submit is compiler/CodeGen.py.

Once you have set up the repo, all you need to do is use git add, git commit, and git push to stage, commit, and sync your repo to the grading git server.

Be sure you have already downloaded the test wrapper.

You can check that you've submitted correctly by cloning, building, and testing your repo.

cd ~
git clone gitolite3@eustis3.eecs.ucf.edu:cop3402/NID/codegen4 codegen4_new
cd codegen4_new
pipenv install -e ./
pipenv shell
make -C grammar/
codegen << EOT > main.s.body
function main # DO NOT CHANGE
localvars a b c d e f g result retval # DO NOT CHANGE
a := 1 + 2
a := a * 6
a := a - 1
a := a % 10
a := a / 3
result := a
retval := call print_int result # DO NOT CHANGE
return 0 # DO NOT CHANGE
EOT
cat wrapper/wrapper_start.s main.s.body wrapper/wrapper_end.s > main.s
gcc -o main main.s wrapper/iolib.c
./main # you should see 2 printed out

Note that this is not comprehensive test of your compiler, but just a validation that the project has been submitted and runs for one test case.