Overview

In this project you will begin implementing a compiler-backend for the class’s custom programming, Slang (Simple Language) by adding compiler support for arithmetic and branching instructions.

Setup

Run the following commands to download the starter code for this project, and to set up your git repository for project submission:

mkdir -p ~/cop3402fal26/
wget https://www.cs.ucf.edu/~pappas/teaching/cop3402/fal2026/files/codegen1-starter-code.tar
tar -xvf codegen1-starter-code.tar -C ~/cop3402fal26/
cd ~/cop3402fal26/codegen1
git init
git add .
git commit
# Enter a commit message in the editor that pops up
git remote add submission gitolite3@eustis3.eecs.ucf.edu:cop3402/$USER/codegen1
git push --set-upstream submission master

Starter code structure

The starter code comes with the following files:

.
├── .gitignore          # File telling git to ignore binary outputs.
├── grammar.ebnf        # File defining Slang's grammar.
├── iolib.c             # C file defining I/O functions for testing Slang.
├── include/            # Header files.
│   ├── cli.h           # Header for the compiler's command line interface.
│   ├── codegen.h       # Header for the compiler's back-end.
│   ├── globals.h       # Header declaring global variables.
│   ├── lex.h           # Header for the Slang compiler's lexer.
│   ├── parse.h         # Header for the Slang compiler's parser.
│   ├── symbol_table.h  # Header for the Slang compiler's symbol table.
│   └── util.h          # Header declaring various utility functions.
├── Makefile            # The project's Makefile.
├── src/                # C files.
│   ├── cli.c           # Definition of Slang's command-line interface.
│   ├── codegen.c       # Compiler back-end. The only file you must modify.
│   ├── globals.c       # Definition of Slang's global variables.
│   ├── lex.c           # Definition of Slang's lexer.
│   ├── parse.c         # Definition of Slang's parser.
│   ├── slang.c         # Entry-point for the Slang compiler.
│   ├── slang-format.c  # Entry point for the Slang auto-formatter.
│   ├── symbol_table.c  # Definition of the Slang symbol table.
│   └── util.c          # Defintion of utility functions.
├── tests/              # Public tests case.
└── template.sg         # A template file you can use to test your compiler.

All these files must be added, committed, and pushed with git. Do not add to source control any generated or binary files (e.g., .o files, or the bin/slang binary itself).

You do not need to read all these files in order to complete this project. The only file you will be modifying is src/codegen.c. The project requirements section explains what changes to make to this file.

Building your project

Run the following command to build your compiler (tested on eustis):

cd ~/cop3402fal2026/codegen1
make

The result of the above command will be the bin/slang executable file. This is the executable for the Slang compiler.

Project requirements

For this and all other codegen assignments, you will complete the assignment by implementing a few specific functions in the file src/codegen.c that are labeled with comments that say TODO. Other functions will either be given to you, or hard-coded to work for this specific assignment’s test cases. You should only modify functions labeled with TODO comments, and should not modify any given or hard-coded functions.

Here is a listing of all the functions in this assignment, and whether they are given to you, hard-coded, or are a function you must implement yourself:

The next subsections describe the functions you must implement yourself.

visit_arithmetic()

This function should emit assembly code that performs a given arithmetic operation on two operands (which may each be a variable or integer), and stores the result in a destination variable.

Here are some examples (assume a has an offset of -16 and b has an offset of -24):

a = 1 + b

mov $1, %rax
mov -24(%rbp), %rbx
add %rbx, %rax
mov %rax, -16(%rbp)

a = b / 1

mov -24(%rbp), %rax
mov $1, %rbx
cqo
idiv %rbx
mov %rax, -16(%rbp)

Here is the relevant snippet from the grammar.ebnf file defining the grammar rule for a Slang arithmetic operation:

arithmetic = identifier '=' value arithop value

A Slang arithmetic operation consists of an identifier (i.e., an alphanumeric sequence that may contain an underscore, and may not begin with a number), followed by an equals sign (=), followed by a value (which is either an integer or an identifier), an arithmetic operator (which is one of +, -, *, /, or %), and another value.

Here is the definition of the Arithmetic struct you defined in include/parse.h while completing the slang-format exercise; this struct has all the fields you need to implement visit_arithmetic():

typedef struct arithmetic {
    Identifier          left_hand_side;
    Value               left_operand;
    Arithmetic_Operator operator;
    Value               right_operand;
} Arithmetic;

To compile Slang arithmetic operations to assembly code, modify the function visit_arithmetic() to emit assembly code that does the following steps:

1. Loads the operands (arithmetic.left_operand and arithmetic.right_operand) into temporary register %rax and %rbx.
2. Performs the arithmetic operation (determined by arithmetic.operator) on the temporary registers.
3. Stores the result of the arithmetic operation into the destination variable (arithmetic.left_hand_side).

Loading the operands

First load the operands of the operation into temporary registers. To do this, first emit (i.e., printf()) assembly code that uses a mov instruction to load the left operand into the %rax register, and then emit assembly code that uses a mov instruction to load the right operand into the %rbx register. To get the assembly code for each operand, you can pass the operand to the given function value_to_string(). For instance, you can use the following code snippet to get the assembly code for the left operand:

char *left_operand = value_to_string(arithmetic.left_operand);

Given a Slang value, value_to_string() returns a null-terminated string containing its assembly representation. For instance, the value 2 would result in "$2", and a variable a with offset -16 from the stack frame would result in "-16(%rbp)". The result of value_to_string() must be freed after you are done using it, e.g.:

free(left_operand);

For more examples of how to use value_to_string(), check the definition of the given function visit_assignment().

After getting the assembly code for each operand, emit a mov instruction that stores the operand’s value into either %rax (for the left operand) or %rbx (for the right operand).

Performing the arithmetic operation

After loading the operands into the temporary registers %rax and %rbx, next perform the arithmetic operation itself. You can determine the type of the arithmetic operation to perform by reading the value of arithmetic.operator. The enum values for this struct field are listed below, along with the corresponding assembly instruction:

For the add, sub, and imul instructions, you can simply emit the instruction name, followed by the temporary registers %rbx and %rax. For instance, to emit an add instruction, you would print:

add %rbx, %rax    # %rax = %rax + %rbx

The above instruction adds %rax to %rbx, and stores the result into %rax. For sub and imul, simply replace add with the appropriate instruction.

Division and modulo are performed differently than addition, subtraction, and multiplication, but both division and modulo follow the same set of steps. First, emit a cqo instruction to sign-extend the %rax register with the %rdx register, then emit the idiv instruction to perform the division/modulo operation to divide the value in %rax by the value in %rbx, e.g.,

cqo
idiv %rbx

The idiv instruction places the quotient of the division in the %rax register, and the remainder in the %rdx register. For modulo, you should emit an instruction to mov the remainder from the %rdx register into the %rax register afterward.

You may wish to use a switch statement to check the value of arithmetic.operator, and print the corresponding assembly code for each operation.

switch(arithmetic.operator) {
  case ARITHOP_PLUS:
    // Emit addition
    break;
  // Rest of cases
}

If you receive a compiler warning about not all cases being covered, try adding a default case.

Storing the result into the destination variable

The previous steps should store the result of the arithmetic operation in the %rax register, so to store the result of the operation into the destination variable, emit an instruction to mov the contents of the %rax register into the offset from the stack frame offset at which the destination variable lies. This offset is stored in the global symbol table, and you can use the function offset_for_name() (defined in src/symbol_table.c) to get the offset for a given variable. For instance, to get the offset for a variable with name name, you would use:

int offset = offset_for_name(name);

In the case of compiling arithmetic operations, the destination variable’s name is stored in arithmetic.left_hand_side.text.

For instance, assuming the variable x has a stack frame offset of -16, you would emit the following assembly code to store the contents of the %rax register into x:

mov %rax, -16(%rbp)

For an example of some code that uses the offset_for_name() function, see the definition of the given function visit_assignment().

visit_label()

This function should emit assembly code for a branch label with a given name.

Here are some examples (assume a has an offset of -16, and b has an offset of -24):

truelabel:

truelabel:

falselabel:

falselabel:

Here is the relevant snippet from the grammar.ebnf file defining the grammar rule for a Slang label:

label = identifier ':'

A Slang label simply consists of an identifier (i.e., an alphanumeric sequence that may contain an underscore, and may not begin with a number), followed by a colon (:).

Here is the definition of the Label struct you defined in include/parse.h while completing the slang-format exercise; this struct has all the fields you need to implement visit_label():

typedef struct label {
    Identifier  name;
} Label;

Slang labels have the same syntax as assembly labels, so to compile a Slang label to assembly, simply emit the label name’s text (given in label.name.text), followed by a colon. The label text is guaranteed to be null-terminated, so you can use the %s format specifier to print it.

visit_goto()

This function should emit assembly code that branches to a given label.

Here are some examples:

goto truelabel

jmp truelabel

goto falselabel

jmp falselabel

Here is the relevant snippet from the grammar.ebnf file defining the grammar rule for a Slang goto:

goto = 'goto' identifier

A Slang goto simply consists of the keyword goto, followed by an identifier.

Here is the definition of the Goto struct you defined in include/parse.h while completing the slang-format exercise; this struct has all the fields you need to implement visit_goto():

typedef struct goto_ {
    Identifier  name;
} Goto;

Slang gotos have almost the same syntax as assembly gotos; the only difference is that in assembly, the word goto should instead be jmp. So to compile a Slang goto to assembly, simply emit the text jmp, followed by the goto name’s text (given in goto_.name.text). The goto text is guaranteed to be null-terminated, so you can use the %s format specifier to print it.

visit_if()

This function should emit assembly code that compares two operands (which may each be a variable or integer) to each other with a given relational operator, and then branches to a given branch label if the result of the comparison is true.

Here are some examples (assume a has an offset of -16):

if a != 5 goto truelabel

mov -16(%rbp), %rax
mov $5, %rbx
cmp %rbx, %rax
jne truelabel

if 3 = a goto truelabel

mov $3, %rax
mov -16(%rbp), %rbx
cmp %rbx, %rax
je truelabel

Here is the relevant snippet from the grammar.ebnf file defining the grammar rule for a Slang if statement:

if = 'if' value relational_operator value 'goto' identifier

A Slang if statement consists of a value, followed by a relational operator (which is one of <, >, =, <=, >=, or !=), followed by another value, followed by the goto keyword, followed by an identifier (which should be the name of a label).

Here is the definition of the If struct you defined in include/parse.h while completing the slang-format exercise; this struct has all the fields you need to implement visit_if():

typedef struct if_ {
    Value               left_operand;
    Relational_Operator operator;
    Value               right_operand;
    Identifier          name;
} If;

To compile Slang if statements to assembly code, modify the function visit_if() to emit assembly code that does the following steps:

1. Loads the operands (if_.left_operand and if_.right_operand) into temporary registers %rax and %rbx.
2. Compares the values of the %rax and %rbx registers to each other.
3. Performs a conditional jump (where the kind of jump performed is determined by if_.operator).

Loading the operands

Follow the same steps as for arithmetic instructions to load the operands of the if statement into the temporary registers %rax and %rbx,

Comparing the values

To compare the values in the %rax and %rbx registers, simply emit a cmp instruction, followed by the %rbx and %rax registers, e.g.:

cmp %rbx, %rax

Note that the order of the operands is important.

Performing the conditional jump

Finally, after emitting the cmp instruction to compare the values in the temporary registers %rax and %rbx, emit the conditional jump itself. You can determine the type of the jump to perform by reading the value of if_.operator. The enum values for this struct field are listed below, along with the corresponding assembly instruction and logical operator:

For all instructions, you can simply emit the instruction name, followed by the label name. For instance, to emit a jump to the label head when the result of the previous cmp instruction was “less than”, you would print:

jle head

Running your compiler

The starter code comes with a template file, template.sg, which you can use for testing your compiler on arbitrary input. Initially, template.sg should contain the following contents:

begin main()                                # DO NOT CHANGE
locals a, b, c, d, e, f, g, result, retval  # DO NOT CHANGE
# START OF YOUR CODE
result = 0
# END OF YOUR CODE
retval = print_int(result)                  # DO NOT CHANGE
return 0                                    # DO NOT CHANGE
end                                         # DO NOT CHANGE

(Note that the print_int() function is not defined in this file itself, but rather in the provided iolib.c file.) You can test your compiler out on the provided template file by first building it with make, and then passing it to the bin/slang executable as input:

make
./bin/slang template.sg

Assuming you have not modified the template.sg file, the output of the above command should be the following:

.file       "template.sg"
.section    .note.GNU-stack,"",@progbits
.text
.globl      main
.type       main, @function
main:
    pushq %rbp          # Push old base pointer
    mov %rsp, %rbp      # Set new base pointer
    pushq   %rbx        # Push old %rbx
    sub $80, %rsp       # Allocate locals
    mov $0, %rax        # Move $0 into %rax
    mov %rax, -72(%rbp) # Move %rax into result
    mov -72(%rbp), %rdi # Move local "result" into %rdi
    call    print_int   # Call function print_int()
    mov %rax, -80(%rbp) # Move returned value into "retval"
    mov $0, %rax        # Set return value
    add $80, %rsp       # Deallocate locals
    popq    %rbx        # Pop old %rbx
    popq    %rbp        # Pop old %rbp
    ret                 # Return back to caller

The above assembly code is your compiler’s translated assembly output for the Slang file template.sg. The comments (text starting with #) say what each line does.

You can modify the template file to test other features of your compiler. When doing so, make sure to never modify any lines of the template ending with the comment # DO NOT CHANGE, as the provided hard-coded functions will only work if these lines are left unchanged. Only add code between the comments, # START OF YOUR CODE and # END OF YOUR CODE. For instance, to modify the template to test your compiler’s ability to compile simple assignment statements (which is given to you in the visit_assignment() function), you could change the template to the following:

begin main()                                # DO NOT CHANGE
locals a, b, c, d, e, f, g, result, retval  # DO NOT CHANGE
# START OF YOUR CODE
result = 0
result = 1
# END OF YOUR CODE
retval = print_int(result)                  # DO NOT CHANGE
return 0                                    # DO NOT CHANGE
end                                         # DO NOT CHANGE

Notice the new line that was added, result = 1.

Then re-run:

./bin/slang template.sg

And you should receive the following output:

.file       "template.sg"
.section    .note.GNU-stack,"",@progbits
.text
.globl      main
.type       main, @function
main:
    pushq %rbp          # Push old base pointer
    mov %rsp, %rbp      # Set new base pointer
    pushq   %rbx        # Push old %rbx
    sub $80, %rsp       # Allocate locals
    mov $0, %rax        # Move $0 into %rax
    mov %rax, -72(%rbp) # Move %rax into result
    mov $1, %rax        # Move $1 into %rax
    mov %rax, -72(%rbp) # Move %rax into result
    mov -72(%rbp), %rdi # Move local "result" into %rdi
    call    print_int   # Call function print_int()
    mov %rax, -80(%rbp) # Move returned value into "retval"
    mov $0, %rax        # Set return value
    add $80, %rsp       # Deallocate locals
    popq    %rbx        # Pop old %rbx
    popq    %rbp        # Pop old %rbp
    ret                 # Return back to caller

Notice the two new lines of output, which form the compiled assembly code for result = 1:

    mov $1, %rax        # Move $1 into %rax
    mov %rax, -72(%rbp) # Move %rax into result

You can add more Slang code to the template file to test that your compiler correctly implements the project requirements.

Running your compiled code

You can use gcc to assemble your compiler output to form a binary object file. And since our compiled code follows the x86 64 System V ABI, we can even link our assembled Slang code with assembled C code. This allows us to compile and link the template.sg file with the provided iolib.c file to call the functions print_int() and read_int(), which are defined in iolib.c, from within our own Slang code! print_int() and read_int() are defined in iolib.c, whose contents are listed here for your convenience:

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int print_int(int64_t x) {
  printf("%" PRId64 "\n", x);
  return 0;
}

int64_t read_int() {
  int64_t x;
  scanf("%" PRId64 "d", &x);
  return x;
}

To compile, link, and run our Slang code, first ensure your bin/slang executable is ready-to-run by invoking make:

make

Then run the following code code snippet to compile the template file template.sg to template.s, assemble and link the result with the provided iolib.c file, and finally run the resulting template binary:

./bin/slang template.sg -o template.s
gcc template.s iolib.c -o template
./template

Assuming the template.sg file has not been modified, the output of the above commands should simply be 0.

You can modify the template.sg file and re-run the above steps to check that different Slang features run correctly when compiled with your compiler.

Note that although the bin/slang executable supports a -o flag for redirecting its output to a file, by default it prints its output to stdout, so you can also simply use the > operator to redirect bin/slang’s output to a file instead if you prefer, e.g.,

./bin/slang template.sg > template.s

Self-check

The makefile included in the starter code provides a make test rule you can use to quickly test that your compiler correctly implements all required functionality for this assignment. You can run this rule as follows:

make test

If your code works correctly, then make test should print the name of all this project’s odd-numbered test cases, each followed by the word “success”. Note that the grading server will test your code against the even-numbered test cases as well, which are not given to you, but are described below. You should test that your compiler passes all even-numbered test cases by either writing your own tests, or by running your compiler on sample programs made by modifying the given template file, template.sg.

After using make test to verify that your compiler passes all odd-numbered test cases (and hopefully using your own tests to verify that it passes all even-numbered test cases as well), you should absolutely also check that you submitted your code correctly via git by running make test from within a fresh clone of your repo. You can do this with the following command:

rm -fr ~/tmp/codegen1_selfcheck
git clone gitolite3@eustis3.eecs.ucf.edu:cop3402/$USER/codegen1 ~/tmp/codegen1_selfcheck
cd ~/tmp/codegen1_selfcheck
make test

If your code was pushed successfully, then your fresh clone should pass all tests as well.

Test cases

The test cases used to grade the project are listed below. You can run make test to test your code against the odd-numbered test cases, which are provided publicly. The even-numbered test cases are private, and you should write your own tests for them.

All test cases test your compiler on code based on the provided template file, template.sg. To ensure that your code works with this template, be sure to follow the project requirements, and only modify functions labeled with TODO comments.

Grading schema