Project3

[Project 3 is due on Monday, 12/16]

Problem: Using the SSA form generated in Project 2, implement one of the following SSA-based optimizations, and compare the performance of the generated optimized code with the unoptimized one (either using the tests provided or your own pattern-directed tests).

  • Constant Propagation and Folding
  • Copy Propagation
  • Dead Code Elimination

The performance of the generated code can be evaluated using the MARS MIPS simulator. Submit a short report highlighting your findings.

Note: To keep things simple, we would not have any function exceeding 4 arguments. 

Source code: The starting source code is located here. To compile the code, use the following command:

make -B

Running our compiler: For compiling a test (say test1.cmm), use the following command:

./ccmm test1.cmm

Tests: The new tests are located here.

Running the generated code: Invoke “spim” and use the following commands to run the generated code (say, test1.s):

(spim) load "test1.s"
(spim) run

In order to run another program (say, test2.s) in the same spim session, use the following command:

(spim) reinit
(spim) load "test2.s"
(spim) run

Measuring performance: In order to evaluate the performance of the generated code, we will use dynamic instruction count as a metric. Here are some guidelines for using MARS for that purpose:

  • Copy Mars4_4.jar from this folder.
  • Run the following command to invoke the tool: java -jar Mars4_4.jar
  • Open a generated assembly code (e.g. test4.s) by pressing Ctrl+o.
  • Press F3 to load the program.
  • Invoke Instruction Counter from the Tools menu and press Connect to MIPS.
  • Press F5 to run the program. You can enter any required inputs through the Run I/O box.
  • The dynamic instruction count can be noted down from the Instruction Counter window.

Here is a snapshot of the tool in action:

pattern006

 Debugging clues: You will find a number of auxiliary files generated along with the final assembly code (*.s). For example in the factorial example (test2.cmm), here are some of the files generated to better understand the compilation of the factorial function:

  • fact.dot: For visualization of the fact() CFG

fact

  • UseDef_fact.txt: Def and use sites for every variable in the fact() symbol table.
  • test2.ir: Dump of the intermediate representation for the whole program.
  • IG_fact_colored.dot: Colored interference graph for fact()

pattern007

The call frame layout used in our CCMM compiler is as follows (please refer to CallStackFrame.h):

pattern009

Submitting to provide:

provide comp181 project3 <file1> [<file2> [<file3> ...]]

Comments are closed.