Project 5 - Instruction selection
Skip navigation COMP3710: Compiler Design and Implementation Research School of Computer Science Search query Search ANU web, staff & maps Search current site content Search Menu Search query Search COMP3710 Lectures Labs Deliverables Resources Search ANU web, staff & maps Search current site content Lectures Labs Deliverables Resources menu Search query Search COMP3710 Search query Labs Week 1 - Introduction Project 1 - Scanning Project 2 - Parsing Project 3 - Semantic Analysis Project 4 - Translation Project 5 - Instruction selection Related sites CS Homepage GitLab Streams Current students You are here » Labs » Project 5 - Instruction selection Description Implement instruction selection, translating from (canonicalized) Tree code to x86-64 assembly using the provided framework. A register allocator is provided as a library. Implement your own register allocator as extra credit. 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 coding, fork the Project 5 repo on GitLab. This project includes new source code that completes the compiler from MiniJava to machine code, with the instruction selection step to be implemented by you. The framework for building the AST and printing out the results is the same as before, in src/mj/Absyn.java. The tree-based IR is the same as before, in src/Translate/*.java. New directores are src/Assem/ - the assembly representation src/Graph/ - graph utilities, if you choose to do register allocation src/Canon/ - tree canonicalization, needed before isel src/RegAlloc/ - data structures for register allocation, 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 lib/*/*.class. You can re-implement them yourself as extra credit. You may choose to base your Project 5 work on the provided solution, 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/mj. The grading script will work with either solution as long as you put its source in the proper place. Provided Liveness and Register Allocation Originally this course was designed so that you would tackle liveness and register allocation in Project 6. Due to the circumstances around the course in Semester 1 2020, we have shortened the projects, so that Project 5 is the final project. However, to have a functioning compiler, we provide you with a register allocator so that you can finally run the machine code on a real machine! In fact, correct execution of programs running on a real machine is how your instruction selection project will be assessed. Extra-credit Liveness and Register Allocation If you choose to implement liveness and register allocation, you can do so by re-implementing the src/RegAlloc/RegAlloc.java class. It should be a drop-in replacement for the binary algorithm. Implement the class src/RegAlloc/RegAlloc.java with a constructor public RegAlloc.RegAlloc(Translate.Frame, java.util.LinkedList
, java.io.PrintWriter); Rewrite the list of instructions in-place to assign registers and insert spills and reloads as necessary. If the example programs run properly using your allocator (without the provided one), you will receive extra credit. You can earn up to 2 points extra credit in this part of the project. 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:lib mj.Main
Running the driver outputs a dump of several phases of translation, as well as a .s assembly file. The assembly file can be assembled and linked using gcc. The grade.sh script adds a tiny bit of assembly and then uses gcc to compile and link the assembly against a skeleton C program that can feed inputs to the program. This is how your project will be assessed. Refer to the grade script on how the C code is linked with your .s files. 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 register allocator as a binary. Instructions This project includes a new IR, the src/Assem/Instr.java representation, which is simply a representation of assembly 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 a concrete subclass in src/x64/. We will no longer need the frame in src/tint. If you plan to use your translation from Project 4, updated it to use the class from src/x64. 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 4 will not use the interpreter. You will run the binaries that come out of your compiler. Runtime For NullPointerException and ArrayIndexOutOfBoundsException, the Frame class has methods badPtr and badSub that returns labels to which your generated code should jump. These labels will be defined in C in the runtime (not the interpreter, like last project). The ‘new’ function which allocates memory is also implemented in the C runtime. Expected Output The class mj.Translate contains a main method that loads files, invokes the parser, runs the semantic analysis phase, and invokes translation, and then runs instruction selection (your work in this project), and then register allocation (a provided library). Like Project 4, the grading script will execute the machine code output from your compiler and check that each translated program computes the expected result. This allows your solution maximum freedom in how it chooses to do instruction selection. You are being graded on correctness only, not code quality. As long as the resultant program computes the expected result, everything is fine. Make sure to run against the provided tests. After the Project 4 regrade phase, you are welcome to use the testcases from project 4 while working on project 5. They are designed to work in both projects. This time, stdout and stderr are not checked at all–only the final .s file is used. FAQ, Tips, and Tricks 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. Updated: 09 Jul 2020 / Responsible Officer: Director, RSCS / Page Contact: Course Convenor Contact ANU Copyright Disclaimer Privacy Freedom of Information +61 2 6125 5111 The Australian National University, Canberra CRICOS Provider : 00120C ABN : 52 234 063 906 You appear to be using Internet Explorer 7, or have compatibility view turned on. Your browser is not supported by ANU web styles. » Learn how to fix this » Ignore this warning in future home
