Deadline#

Your work should be committed and pushed to your forked gitlab repo by 11:59pm on Tuesday 9 May 2023.

This project is worth 10% of total course mark.

Description#

Implement instruction selection, translating from (canonicalized) Tree code to x86-64 assembly using the provided framework. A simple (non-spilling, non-coalescing) register allocator is provided as a library.

And finally you get to run some compiled MoJo programs!

Getting Started#

Before starting this project, familiarize yourself with Chapters 9, 10, and 11 of the textbook and review the lecture notes on instruction selection.

To get started fork the Project 5 repository on gitlab.

This project includes new source code that completes the compiler from MoJo to assembly code (which you can assemble and link to run on x86-64). Your task is to perform instruction selection by “tiling” the canonical intermediate code trees via “maximal munch”. We have provided the following:

  • The framework for building the AST and printing out the results is the same as before, in src/mojo/Absyn.java.
  • The tree-based IR is the same as before, in src/Translate/*.java.
  • New folders include:
    • src/Assem/: the assembly code representation.
    • src/Graph/: graph utilities, for register allocation.
    • src/Canon/: tree canonicalization, needed before instruction selection to lower the IR trees to straightline basic blocks and traces.
    • src/Mips/: contains an implementation of code generation for the Mips R2000 architecture (which was discussed in lectures) that will give you a sense of how the “tiling” process works.
    • src/FlowGraph: built during control flow analysis, and used as input to data flow analysis to compute liveness of variabls.
    • src/RegAlloc/: data structures for register allocation, though not the algorithm itself.

Provided Translation Solution#

The Project repo also includes binaries that implement all the stages of the compiler necessary prior to instruction selection. The liveness and register allocation phases are also provided as binaries in bin/*/*.class.

You may choose to base your Instruction Selection work on the provided binaries for earlier phases of the compiler, or continue using your own solution. It is expected that you do not try to reverse engineer the class files of the provided solution to improve your score on prior projects, although you may run them to understand why your solution might be broken.

You can use your own solution by copying your files from Projects 2–4 into src/mojo. The grading script will work with either solution as long as you put its source in the proper place.

Provide Liveness and Register Allocation#

You will tackle liveness analysis and graph colouring register allocation in the final project, but to have a mostly-functional compiler where you can assemble, link, and run simple programs we have provided you with a dumbed down register allocator that does not spill or coalesce moves. Without spilling it is incapable of compiling more interesting programs such as the Queens family, and without “coalescing” you will see how profligate we have been in creating temporaries. However, for simple programs you should be able to generate assembly code that you can run on a real machine.

Where to Add Your Code#

All the action in this project is in src/x64/Codegen.java. The driver for running the full compilation is in src/mj/Main.java.

You should only need to edit src/x64/Codegen.java to complete this project. After you get it to compile, you can run the driver with:

% java -cp bin mojo.Main -main <prog>.mj

Running the driver outputs a dump of several phases of translation, as well as a <prog>.s assembly file. The assembly file can be assembled and linked using gcc (on an x86-64 machine such as those in the School of Computing’s Linux labs). If you don’t have an x86-64 machine of your own then you can copy the .s file to a lab machine and use gcc to assemble it into an executable with the command:

gcc -no-pie -o <prog> <prog>.s

where <prog.s> is the assembly file generated by the MoJo compiler and <prog> is the name of the executable that you can then run with the command ./<prog>. If you need more help on how to do this please ask on https://edstem.org in the COMP3710 discussion.

Running on a Mac (including Apple Silicon ARM64)#

First make sure you have the Apple command line developer tools installed by typing the command xcode-select --install into a terminal prompt.

To compile your programs for assembly on a Mac you can specify the target using the flag -target=x64osx as follows:

% java -cp bin mojo.Main -main -target=x64osx <prog>.mj

This will ensure that global symbols are prepended with _ which is what is expected by Apple’s development tools. The command to assemble your .s file on Mac is:

gcc --target=x86_64-apple-macos -o <prog> <prog>.s

This will generate an x64-apple-macos binary that you can run with the command ./<prog>.

You might ask: how does this x86-64 binary run on Apple Silicon ARM64? The answer is that Apple provides an x86-64 dynamic binary translator called Rosetta.

There is Lots of Code to Help You Here#

The provided framework is mostly the same as before; there is now a new driver for the entire compilation process, as well as a list of instructions and a simple register allocator as a binary.

Instructions#

This project includes a new IR, implemented in src/Assem/Instr.java, which is simply a representation of assembly code instructions. You will generate instructions that use the string names (mnemonics) of x86-64 assembly language, e.g. “movq” and “addq”, etc.

Frames#

The src/Translate/Frame.java class provides an abstract representation of stack frames. It has concrete subclasses in src/x64/ and src/Mips/.

Code#

You will translate the Tree code of method bodies into a list of instructions, and the framework will output them to an assembly file.

Interpreter#

Project 5 will not use the interpreter. You can run the compiled MoJo programs that come out of your compiler as described above.

Runtime#

Instead of the limited set of runtime functions supported by the interpreter from Project 4 we can now link to any function in the standard C library. You will need to declare external C functions appropriately for use from MoJo programs. For example:

def putchar(i: int): int;
/* Print the character encoded by i to standard output */

def puts(t: Text): int;
/* Print a string to standard output followed by a newline */

def printf(format: Text; i: int);
/* Use with a format string like "%d\n" to print an int */

Expected Output#

The class mojo.Main contains a main method that loads files, invokes the parser, runs the semantic analysis phase, invokes translation, and then runs instruction selection (your work in this project), followed by register allocation (a provided binary). Like Project 4, the grading script will compare the output from your compiler with the expected output from mine. This will be useful to you in understanding the project and what you need to implement. However, your solution will be graded on correctness, not code quality. As long as your compiled programs compute the expected result then you are good.

Turn In and Grading#

  • Like previous projects, you should fork the project repo to get started.
  • Like before, you don’t need to turn anything in.
  • We will pull from your repo’s master branch at the deadline.
  • We will rebuild your submission from source with your Makefile.
  • We will run the grading script on your code with additional test inputs that are not included in the repo.
  • We will provide the additional test inputs along with your score after the deadline.
bars search times arrow-up