Description
Part 1: Reading Compilers – Principles, Techniques, & Tools, 2nd Edition, Sections 8.2, 8.3, 8.4 Homework Exercises – laboratory assignment and answer the questions at the end of the assignment.
Introduction In this assignment you optimize the calculator program to generate improved intermediate code. You optimize the quad linked list by improving the generation and/or optimizing the linked list. You are allowed to improvement the code in any location in the compiler (scanner, symbol table, parser, IR code generator).
You can reuse temporary locations, optimize temporary variables and/or reduce the instruction set. You use the previous test programs to compare your results. For extra credit you add optimization methods for generating the array quads. Part 2: Laboratory From a console window, make a directory on your computer in your EECS337 directory under your Case ID and call it hw11. mkdir ~/EECS337/caseid/hw11/ ; where caseid is YOUR Case ID, enter all in lower case
Change directory to the hw11 directory. cd ~/EECS337/caseid/hw11/
Download a copy of: hw11_caseid.tar file to the hw11 directory from https://blackboard.case.edu/ in the EECS337 homework assignment area. To untar the tar file type the command: tar xvf hw11_caseid.tar
The following files will be created in the current working directory. Codegen.c is included to fix a bug in the get_address routine to update the memory pointer based on the size of the input. Makefile hw11_test.sh
Copy the following files from the assignment 10 directory to this directory with the commands: cp ../hw10/lex.l . cp ../hw10/main.c . cp ../hw10/quad.c . cp ../hw10/symbol_table.c . cp ../hw10/yacc.y . cp ../hw10/yystype.h .
Optional: If you did not complete the last assignment you can download the hw10solutions.tar file from the assignment directory and use that as your starting code. Use the command “tar xvf hw10solutions.tar”. A hw10/ directory will be created with the files. In that case edit all the files and change “caseid” to your Case ID.
You are now ready to solve the laboratory assignment.
Part 3: Laboratory Assignment Edit the files and make changes to implement code optimization. You should consider where you want to do the optimization and design and implement one change at a time. If that does not show an improvement then try another method.
You can change the code in the parser functions (quad.c) to generate better quads or write a state machine to post process the quad linked listed. One example of optimization to remove t1 is shown below. t1 = 1; a = t1; a = 1; Compare the results of this program to the results of assignment 10 to see the changes and quantify the results.
diff hw11_test.txt ../hw10/hw10_test.txt | more
For example edit the quad.c file and change the new_quad1 function to remove the temporary operands when both operands are either an identifier or a constant. This checks if the two previous expressions were an identifier or constant production.
/* * check if optimize quad */ if( q1-operator == ‘=’ && q1-dst_type == TYPE_TEMPORARY && ( q1op1_type == TYPE_IDENTIFIER || q1-op1_type == TYPE_CONSTANT) && q2-operator == ‘=’ && q2-dst_type == TYPE_TEMPORARY && ( q2op1_type == TYPE_IDENTIFIER || q2-op1_type == TYPE_CONSTANT)) { data.temp–; data.temp–; quad1 = new_quad( operator, TYPE_TEMPORARY, next_temp(), q1op1_type, q1-op1_index, q2-op1_type, q2-op1_index); free_quad( q1); free_quad( q2); return quad1; }
/* * do the previous thing */
Save the quad.c file.
Build the calc program and fix any errors using the commands: make clean make
To test your version, type the command below: ./calc + symbol and enter the lines below. ./calc +symbol for caseid start time: Mon Nov 11 11:22:12 2013 Enter calculator expression and $ to exit int a; int b; int c; a = (b + 2) * 2 + (b + 2);
t1 = b + 2 t1 = t1 * 2 t2 = b + 2 a = t1 + t2 $ symbol table: index: 1 identifier: a length: 2 specifier: int index: 2 constant: 4 length: 2 format: decimal index: 3 identifier: b length: 2 specifier: int index: 4 identifier: c length: 2 specifier: int index: 5 constant: 2 length: 2 format: decimal
Test using the test files using the commands below. The output for the first file is shown. ./calc +symbol ../hw10/math24.txt ./calc +symbol ../hw10/math25.txt for caseid start time: Mon Nov 11 11:41:09 2013 c1 = 1 s2 = c1 + 2 i4 = s2 + 4 t2 = s2 / i4 t3 = t2 * 10 l8 = c1 + t3 symbol table: index: 1 identifier: c1 length: 3 specifier: char index: 2 identifier: s2 length: 3 specifier: short index: 3 constant: 2 length: 2 format: decimal index: 4 identifier: i4 length: 3 specifier: int index: 5 constant: 4 length: 2 format: decimal index: 6 identifier: l8 length: 3 specifier: long index: 7 constant: 8 length: 2 format: decimal index: 8 constant: 1 length: 2 format: decimal index: 9 constant: 10 length: 3 format: decimal Part 4: Output Generation When all your lab assignments have been completed execute the homework script file “./hw11_test.sh” using the command below. ./hw11_test.sh & hw11_test.txt
Print out the hw11_test.txt file and put your name, assignment number and date on it. Turn in the file for the assignment and answer the questions at the end of the assignment. If you made a lot of changes to one file then print out that file and include it with your assignment.
Your final directory structure for the calc compiler should be as below (using your Case ID): EECS337/caseid/hw11/Makefile EECS337/caseid/hw11/calc EECS337/caseid/hw11/hw11_caseid.tar EECS337/caseid/hw11/hw11_test.sh EECS337/caseid/hw11/hw11_test.txt EECS337/caseid/hw11/lex.l EECS337/caseid/hw11/main.c EECS337/caseid/hw11/quad.c EECS337/caseid/hw11/symbol_table.c EECS337/caseid/hw11/yacc.y EECS337/caseid/hw11/yystype.h
Part 5: Extra Credit (5 points) Save a copy of your code and then edit the source files to optimize the array quads. X = Y[ Z ] X[ Y ] = Z
Build the calc program and fix any errors using the commands: make clean make
Test using the extra credit test files using the commands below: ./calc +symbol ../hw10/math26.txt ; X[ Y ] = Z
Edit the hw11_test.sh file and remove the comment to test the math26.txt file. When the extra credit code is complete and working then execute the homework script file “./hw11_test.sh” using the command below. ./hw11_test.sh & hw11_test.txt Print out this version of the hw11_test.txt file. Mark this output with EXTRA CREDIT and put your name, assignment number, date on it and turn it in instead of the file from Part 4. Upload ONLY your quad.c file to blackboard in the assignment area. Submit it with the comments hw11 with your CaseID on the title line. The extra credit will be graded on-line and your score will be added to your assignment score. Answer the questions at the end of the assignment.
Part 6: Laboratory Questions
1) Explain the type of optimization you performed in this assignment and quantify the results. (Reduction in the number of temporaries, number of quads and instructions.
HW10 TEMPS HW11 TEMPS HW10 QUADS HW11 QUADS Math24.txt Math25.txt Math26.txt