MotivationThe AssignmentGetting StartedYour ReportHints for doing the assignmentWhat to turn inDue dateCS 553 Compiler Construction — Fall 2006 Project #3Program Optimization Due November 3, 2005In this assignment you will implement different program optimizations that use the results of data-flow analysis and compare the generated MIPS code in terms of the number of cycles required forexecution. This assignment should be done with groups of two, but can be done individually ifnecessary. Each program optimization will be assigned a number of stars to estimate how difficultit will be to implement it. Groups will implement program optimizations that sum to four or morestars, whereas individuals need only reach a s um of two or more.1 MotivationProgram optimizations such as dead-code elimination, copy propagation, constant propagation,common subexpression elimination, code motion, and induction variable elimination are commonlyapplied to low-level intermediate representations to reduce the overall instruction count for a pro-gram. The reduction in instruction count resulting from these program optimizations typicallyresults in a performance improvement as well. Also, higher-level transformations often assumevarious subsets of these optimizations for cleaning up the code after parts of the high-level trans-formation have been applied.2 The AssignmentYour assignment is to implement dead-code elimination and one or more other program optimiza-tions in the MiniJava compiler.• Copy propagation (1 star)• Constant propagation without constant folding (1 star)• Constant propagation with constant folding (2 stars)• Common sub-expression elimination (2 stars)• Code motion or hoisting (4 stars)• Induction variable elimination (5 stars)For every extra star that you implement, test, and evaluate, you will receive 1 extra point for thisassignment.1It should be possible to specify each optimization you implement on the command line. For example,% java -jar MiniJavaCompiler.jar --copyprop file.java% java -jar MiniJavaCompiler.jar --copyprop --deadcode file.java...You should also have a “–fast” option that p erforms your optimizations in an order that you believewill provides the best possible performance in most cases.NOTE: For this project, your compiler should not print out debug information. Instead the compilershould just print one line of output indicating each program optimization that is being applied.For example,Applying constant propagationApplying dead-code eliminationApplying copy propagationApplying dead-code eliminationApplying register allocation via graph coloringYour group will need to create at least two test input programs per optimization implemented.To check correctness, compare the output of the MIPS code running with SPIM to the output ofthe same program run with the JVM. Des ign your test cases so that they will break an incorrectimplementation of the implemented program optimizations. Feel free to share such test c ase s withother groups in the class, but each group must submit their own two test cases. Individuals notworking with a partner must also generate two test cases per optimization.Your group will also need to create two benchmark input programs. The benchmark programsshould be designed to show off one or more of your program optimization implementations. Indi-viduals not working with a partner must also generate two benchmarks. The benchmark programsfrom the whole class will be run through each submitted compiler using the “–fast” option. Wewill compare the results from each group in class.Graph the results for each program optimization you implement, your “–fast” option, the MiniJavacompiler provided for the register allocation project, and your version of the compiler that performsregister allocation for both of your benchmark programs. Explain the results.3 Getting Started1. A new version of the MiniJava compiler was sent to the class mailing list. You will be addingfunctionality to this provided compiler or your own version of the compiler that you wrote forthe register allocation project. Much of the infrastructure needed for this project is already2in place. Do a search for the phrase “Project3Implement” to find places in the code whereyou will be adding functionality.2. You will need to implement the following to support many of the possible program optimiza-tions:• A method in FlowGraph for removing a node. See FlowGraph.rmFlowGraphNode().• A method in FlowGraph for generating a new list of instructions after performing anoptimization. See FlowGraph.getInstrList().• A data-flow analysis framework has been provided and the Liveness package exhibitsusage of the framework.• A DeadCodeElim package has been provided, but you must implement it.• New subclasses for Assem.Instr have been provided and Mips/Codegen.java is generatingthe new instruction subclasses. You must implement the method in Codegen.java thatregenerates MIPS code for the Assem.Instr subclasses.3. Work out some examples by hand before jumping into the implementation of any programoptimization.4 Your ReportThe report is an essential part of your completed assignment. Use it to describe your reasoningbehind each program optimization you implement, assumptions, difficulties, insights, and results.Organize and present your document as if it were the only basis for your assignment’s grade. Theformat of your writeup is up to you, but it should minimally include the following:• Introduce the main goals of the project and in a couple of sentences summarize what youhave accomplished.• Briefly describe the optimizations you chose to implement. Motivate your selection of thoseoptimizations.• Present and explain graphs that exhibit the performance difference between MIPS programsgenerated by the provided MiniJava compiler and and your extended MiniJava compiler.• How did you test your program optimization implementations?• What problems did you encounter while im plementing the program optimizations? If youknew someone who was just about to start work on this assignment, what advice would yougive them? Do you agree with the star ranking provided?• What, if any, outside sources did you use (e.g., articles, books, other students)? This isparticularly important. It’s OK to look at books and articles and speak with your professorand fellow students (although sharing code and working together is strictly forbidden), but3as with any scientific