Project 4 for CSC 255/455, Spring 2012

Project 4. Data-flow Analysis

Due: Sunday March 11 11:59pm


Requirement

In this assignment, you are asked to write a def-use pass for data-flow analysis in URCC and then use it to eliminate dead code as much as possible. For best optimization effect, you may consider constant propagation, copy propagation and partial redundancy elimination as well. There is no specification on your internal implementation. You can choose any data structure to represent the data-flow information.

Reuse the InstCountPass in Project 3 and count run-time statements(AssignStatand GotoStat) before and after your analysis and transformation for all tests in [255_repos]/assignments/gimple_code/. Submit code and a report describing your design and test results.

Your grade will be based on the correctness of optimized code (80%) and the number of eliminated statements (20%).


Alternative Track

Implement Brigg et al. style (SPE97) SSA-based value numbering.  While implementing SSA requires solving multiple data flow problems, the SSA form simplifies analysis and optimizations and delivers better results.  Depending on the quality of the results, SSA track may receive 20% bonus points.