Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science 6.035, Spring 2010 Optimizer Project Assignment Thursday, Apr 1 Important Dates: Design Proposal: Thursday, Apr 15 Checkpoint: Wednesday, Apr 28 Final Compiler and Documentation: Wednesday, May 12 @ 11am Derby: Thursday, May 13 In this final phase of the project your goal is to reduce the execution time of your generated code while preserving the semantics of the given application. This phase is completely opened-ended; you are not required to implement any specific transformations. Your grade will be based on your overall design (with heavy emphasis on the writeup) and how well your compiler performs as compared to the submissions of the other groups. During the final class, we will hold the Compiler Derby where your compiler implementation will compete against the implementations of your fellow classmates on a hidden program (the derby program). In the final month of class, we will cover various code improving optimizations. The AMD64 architecture is very complex and aggressive. A substantial portion of this project phase is to determine which optimizations will provide a benefit given the programs of the provided benchmark suite and the target architecture. Some optimizations that we will cover in class include: • Register Allocation – Your compiler can implement a graph coloring based register alloca-tor. See Chapter 16 of the Whale book and §9.7 of the Dragon book . Your register allocator should take advantage of the full set of general-purpose re gisters provided by the x86-64 ISA. It should also respect the Linux calling convention including caller-save and callee-save properties of each register. • List Scheduling – Instruction scheduling minimizes pipeline stalls for long latency operations such as loads, multiplies, and divides. See Chapter 17 of Whale book. • Instruction Selection – So far, we have been using a restricted subset of the x86-64 ISA. As a peephole optimization, you might replace a sequence of simple instructions with a single, complex instruction that performs the same operation in fewer cycles. • Data Parallelization – Computation executed in different iteration of a loop may be in-dependent of each other. We are providing you with a library to help you find independent computations, and p erform automatic loop parallelization. Since we will run your code on a 4-way parallel machine, exploiting parallelism may reduce your execution time by up to a factor of 4. 1In order to identify and prioritize optimizations, we have provided you with a benchmark suite of image-processing programs. These programs are more complex than the code that has been pro-vided during the previous phases, so your first priority is to produce correct unoptimized assembly code for each benchmark. After your compiler produces correct unoptimized code, you should begin to study the applications of the benchmark suite. You will use these programs (and any other programs provided during previous phases) to determine which optimizations you will implement and in what order they will be applied. You are expected to analyze the assembly code produced by your compile r to classify the effectiveness of each proposed optimization, perhaps first applying the optimization manually and empirically measuring the benefit. Your writeup should include evidence for the effectiveness of each optimization you considered. You are not limited to the optimizations covered in class. You are free to implement any opti-mization that you come across in your reading or any optimization that you devise. However, your writeup must demonstrate that each optimization is effective and semantics preserving. Further-more, you must argue that each optimization is general, meaning it is not a special-case optimization that works only for the derby program or a specific application in the benchmark suite. You should consult AMD’s documentation for details regarding our target architecture and the ISA. The documentation is linked from the class website. To benchmark your generated assembly code, provide the -pg option to gcc or cc while assembling in order to generate profiling information. After the code is executed, you can use gprof to examine the generated profile statistics. Also, you can use the Unix command time focusing on the “user” time. A more accurate timing mechanism is included in the provided thread library. It will be discussed during the project recitation. Writeup The writeup for this project is extremely important. Although it explicitly accounts for only 20% of the grade, it will also be used to determine your score for the Implementation aspect of the project (40%). Your written documentation must discuss each optimization that you considered. The thoroughness of your exploration of the optimization space will be an important aspect of your grade. For each optimization that you implement, your writeup must convince the re ader that the optimization was beneficial, general, and correct. For each optimization that you decide not to implement, you must convince the reader that the optimization would not be beneficial given your generated code for the given benchmarks and our target architecture. You should include assembly or IR code examples for each optimization. Show how your generated code is transformed by the optimization (might be hand-applied for optimizations you did not implement). Highlight the benefit of the optimization on the assembly or IR code. Discuss exactly how the benefit was achieved given the characteristics of our target architecture. Include empiric al evidence that proves your conclusion for the optimization. Your compiler should include a “full optimizations” command-line option