MotivationThe AssignmentGetting StartedYour ReportHints for doing the assignmentWhat to turn inDue dateCS 553 Compiler Construction — Fall 2006 Project #2Register Allocation Due September 22, 2005In this assignment you will implement different register allocators and compare the generated MIPScode in terms of the numb er of cycles required for execution. This assignment should b e done withgroups of two, but can be done individually if necessary. Groups will implement four variations ofregister allocation and individuals will implement two.1 MotivationRegister allocation is arguably the most important program optimization in the compiler. TheMiniJava compiler version being provided spills all variables to memory. The implications of spillingall the variables is that a MIPS template instruction like"add ‘d0, ‘s0, ‘s1"will be expanded into four MIPS template instructions using the load-load-compute-store concept"lw ‘d0, -16( ‘s0)", uses = [ t60 --> "\%fp" ], defs = [ t77 --> "\%t0" ]"lw ‘d0, -20( ‘s0)", uses = [ t60 --> "\%fp" ], defs = [ t78 --> "\%t1" ]"add ‘d0, ‘s0, ‘s1, uses = [ t77 --> "\%t0" , t78 --> "\%t1" ],defs = [ t79 --> "\%t2" ]"sw ‘s0, -24( ‘s1)", uses = [ t79 --> "\%t2", t60 --> "\%fp" ].The code shown above assumes that the temporaries for the original add instruction’s s0 and s1slots are put into memory locations -16(%fp) and -20(%fp) and the temporaries for the originald0 slot is stored at memory location -24(%fp). The temporaries used above are just made upto illustrate what happens. In the code, the temporary for the frame pointer is provided by theMipsFrame on an FP() call. The MipsFrame tempReg() method provides temporary registers foruse when generating load-load-compute-store code.Due to the major code expansion that occurs when spilling all temporaries, register allocation canreduce the number of cycles exe cuted by up to 75%!12 The AssignmentYour assignment is to design implement four different versions of register allocation, compare theperformance of the generated MIPS code amongst the four versions and the provided MiniJavacompiler, and report on your design decisions, testing strategies, and performance results. Of thefour versions of register allocation at least one of the versions must be based on graph coloringtechniques and all four versions must be able to handle spilling. You will design each of the fourversion by selec ting amongst the following options:• Implem ent register allocation for the IR Tree data structure using Algorithm 11.11 in theTiger book.• Use Algorithm 11.10 in the Tiger book before performing graph coloring.• Possible spilling heuristics: random spill choice, the temporary with the fewest uses and defs,some combination of the uses and defs and degree in the interference graph, other possibilitiesthat you design• Type of spilling: optimistic or pessimistic• Coales cing options: no coalescing, George, Briggs, other possibilities that you design• Other options that you designIt should be possible to select one of your four versions on the comm and line. For example,% java -jar MiniJavaCompiler.jar -v1 file.java% java -jar MiniJavaCompiler.jar -v2 file.java...Your group will need to create at least two test input programs. To check correctness, compare theoutput of the MIPS code running with SPIM to the output of the same program run with the JVM.Design your test cases so that they w ill break an incorrect implementation of register allocation.Feel free to share such test cases with other groups in the class, but each group must submit theirown two test cases. Individuals not working with a partner must also generate two test cases. Also,performance in terms of dynamic cycles executed should be better when using register allocationthan the provided MiniJava compiler.Your group will also need to create two benchmark input programs. The benchmark programsshould be designed to show off one or more of your register allocation implementations. Individualsnot working with a partner must also generate two benchmarks. The benchmark programs fromthe whole class will be run through each submitted compiler using the version of regis ter allocationthat you predict will perform the best overall. We will compare the “best” register allocator from2each group in class. There are things you can do that are not described here that will result inbetter code than what is currently generated. If you discover these and decide to do them, theycan be considered as “other options that you design”.Graph the results of your four versions of register allocation and the provided MiniJava compilerfor both of your benchmark programs. Explain the results.3 Getting Started1. The MiniJava compiler was s ent to the class mailing list. You will be adding functionality tothis provided compiler. The tree-base d register allocation schemes will operate on the linkedlist of statement Trees generated with the following statement in Main.java:LinkedList<Stm> traced = (new TraceSchedule(b)).stms;The graph-coloring based register allocators can be called in Codegen.java where currentlyall registers are spilled:// spill all the registersretlist = frame.spillAll(retlist);Alternate organizations of the code in the compiler are welcome.2. Read chapters 10 and 11 in the Tiger book. Some of the code discussed in those chapters isavailable at http://www.cambridge.org/resources/052182060X/.3. Work out some examples by hand before jumping into the implementation of any one version.4. I have installed a version of SPIM that counts c ycles on the CS machines.% /s/bach/b/class/cs553/spim-7.2.1-keepstats/spim -keepstats file.s4 Your ReportThe report is an ess ential part of your completed assignment. Use it to describe your reasoningbehind each of your register allocation designs, assumptions, difficulties, insights, and results. Or-ganize 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.3• Des cribe the options that you used in each of your register allocation implementations. Mo-tivate your selection of the various options.• Prese nt and explain graphs that exhibit the performance difference b e tween MIPS programsgenerated by the provided MiniJava compiler and the four versions of register allocation