MotivationGetting StartedThe AssignmentGather Ye Benchmarks While Ye MayTiming the Results of C-Breeze PassesWriting a WalkerVisualizing Control-Flow GraphsHints for doing the assignmentYour ReportWhat to turn inDue dateCS 553 Compiler Construction — Fall 2005 Programming Assignment #2Investigating C-Breeze Due October 21, 2005In this assignment you will investigate the C-Breeze compiler by applying some transformationphases to C benchmarks and analyzing the change in execution time, by visualizing the control-flowgraph generated by C-Breeze, and by writing a simple analysis. I recommend working in groups ofsize two.1 MotivationDoing research in the compilers area usually involves prototyping your algorithms and showingtheir effect on real codes. Instead of building a compiler infrastructure by scratch, most researchersuse and contribute to an existing compiler infrastructure. In this class we will be investigating theC-Breeze compiler infrastructure.Testing the results of previous optimizations and designing and impleme nting new optimizationsare common activities that occur in compilers research. These activities require a certain setof skills: finding benchmarks, timing program execution, visualization, designing test cases, andimplementing new analyses and transformations.The goal of this assignment is to introduce you to many of these skills by working with real Cbenchmarks that you will find on the internet. You will also be designing some simple test casesyourself, learning how to time program execution, learning how to use the graphviz package forgraph visualization, and learning how to write a simple analysis in C-Breeze.2 Getting Started1. Get a copy of the initial project2 files% cp ~cs553/project2/Project2.tar .% tar xf Project2.tar2. Build project2% makeBuilding project 2 results in an executable called cbz. Here are some examples of cbz usage:% ./cbz -ast test1.c% ./cbz -dismantle test1.c% ./cbz -cfg -c-code test1.cThe above commands generate a file called test1.p.c. Look at the file to see what the compiler isdoing.13 The Assignment3.1 Gather Ye Benchmarks While Ye MayFind a small (> 102LOC), medium (> 103LOC), and large (> 104LOC) C benchmark from thenet with a small and large input set for each. WARNING: This probably won’t be easy!• There should have a separate directory for each benchmark under your project2 directory.• The project2/Makefile should have a rule for ”make testbench” that runs each benchmarkthrough cbz with the command ”./cbz -dismantle benchmark.cc”.• The project2/Makefile should have a rule ”make runbench” that runs each benchmark on itssmall and large input set.Make sure to keep track of which benchmarks you are unable to com pile with cbz. See thereport requirements.3.2 Timing the Results of C-Breeze PassesUse the unix ”time” command to the benchmark runs before and after applying constant propaga-tion and copy propagation separately. For example, assuming the big benchmark exec utable wasin the subdirectory big and was called bigexec:% time big/bigexec smallInput// recompile big using constprop% ./cbz -cfg -constprop -c-code big/*.c% time big/bigexec-cp smallInputThe commands above are not exactly w hat you need to do. You will have to organize thingsyourself so that the following invocations of make work:• The project2/Makefile should have a rule for ”make timebench” that runs runs and timeseach benchmark on its s mall and large input set.• The project2/Makefile should have a rule ”make timeconstpropbench” that runs each bench-mark on its small and large input set after it has had constant propagation performed.• The project2/Makefile should have a rule ”make timecopypropbench” that runs each bench-mark on its small and large input set after it has had constant propagation performed.3.3 Writing a WalkerWrite a program analysis that counts the numbe r of addition, subtraction, multiplication, anddivision operations that occur within a program. Start by understanding the CountAssign examplein the online documentation. (The code for this is already in the starting Project2 directory).23.4 Visualizing Control-Flow GraphsVisualization of graphs that result from program analysis can be immensley useful when it comesto debugging analysis implementations. dot (http://www.graphviz.org/) is a very popular andfree graph visualization package, which already happ e ns to be installed on the CS linux machines(yeah Wayne!). For this part of the assignment you will be generating a text dot file that describesthe CFG created by C-Breeze and then using dot to visualize the graph by generating a postscriptfile.To generate the dot file, write a walker for C-Breeze. The dot user guide at http://www.graphviz.org/Documentation/dotguide.pdf describes the various components of a dot file. TheCFG dot files should have a node for each basic block, edges between nodes to represent the controlflow, and the statements for the basic block should be the label for the corresponding node.Here is the com mand you use to create the postscript file:dot -Tps test.dot > test-dot.psYou will need to use something like ps2pdf if you are using pdflatex to generate your report.4 Hints for doing the assignmentFor generating dot files, use print walker.h and print walker.cc as example of how you might gen-erate a text description for a control-flow graph. The key methods will be at basicblock in yourWalker and basicblocknode:preds(). You will have to maintain a mapping between basic blocknodes and unique integer ids.Not all parts of the assignment depend upon one another. Therefore, you can skip around.As always you should start this assignment early. I will be available during regular officehours and by email. I can look at your code and help point you in the right direction, but theamount of help I can give may be inversely proportional to the amount of time until the due date.By no means should you spend several hours trying to figure out a weird bug; consult me for help.When e-mailing me about the project, send a copy of the relevant section of your code (not as anattachment; send it as text appended to your message). Give a good description of what is goingwrong, which should include information about the stack in a debugger.5 Your ReportThe report is an essential part of your completed assignme nt. Use it to describe your solution,assumptions, difficulties, insights, and results. Organize and present your document as if it werethe only