CMSC 430, Spring 2009
Theory of Language Translation
Project 5 - C-- : Code Analyzer
In this project you will add some global data-flow analysis to your C-- compiler.
Getting StartedProject 5 will be implemented in Java in Eclipse. Download the following file:
See project 2 description for description of project files and syntax/semantics of C--. Compared to project 5, there are some changes:
RequirementsYou are given a skeleton data flow analyzer for calculating live variables. The existing code builds a simplified control flow graph (CFG) assuming all statements are in a single basic block. It then performs iterative data-flow analysis on the (reverse) CFG, but lacks code to compute local effects and propagate data-flow information between basic blocks.
Data-flow frameworkYour must extend the compiler to implement a global data-flow analysis framework. To begin with, you must build the control flow graph correctly in the presence of control flow (i.e., handle IF, GOTO, and RETURN statements) For simplicity, you can put every statement in its own basic block. Existing code in the compiler will display the control-flow graph as a list of basic blocks, with lists of predecessor & successors.
Live VariablesNext you must compute data flow information to solve the live variable problem for all local scalar variables (you can ignore arrays & global vars)
Dead code eliminationFinally, you must use live variable information to eliminate dead stores for local scalar variables (ISTOREs). These instructions should be replaced with POP instructions. A more sophisticated implementation would actually eliminate the computations, but is not necessary.
BitSet (from java.util.BitSet)BitSet is used to represent data-flow information in each basic block. A bit at position X is set to represent information about local variable at index X. BitSet has the following methods:
void and(BitSet set) Performs a logical AND of this target bit set with the argument bit set. void andNot(BitSet set) Clears all of the bits in this BitSet whose corresponding bit is set in the specified BitSet. void clear(int bitIndex) Sets the bit specified by the index to false. Object clone() Cloning this BitSet produces a new BitSet that is equal to it. boolean equals(Object obj) Compares this object against the specified object. boolean get(int bitIndex) Returns the value of the bit with the specified index. void or(BitSet set) Performs a logical OR of this bit set with the bit set argument. void set(int bitIndex) Sets the bit specified by the index to true. void xor(BitSet set) Performs a logical XOR of this bit set with the bit set argument.
bBlockbBlock is used to represent an individual basic block. It maintains its connections to other bBlocks, and uses BitSets to store data-flow information. bBlock has the following fields and methods:
int num; // number for basic block int len; // number of instructions in basic block InstructionHandle first; // first instruction in basic block InstructionHandle last; // last instruction in basic block bBlock  pred; // predecessors bBlock  succ; // successors BitSet in; // BitSet out; // BitSet gen; // BitSet kill; // int currPred; // iterator: number of current predecessor int currSucc; // iterator: number of current successor public void setSucc(bBlock bb) // add bb to successors, updates bb's predecessors public void setPred(bBlock bb) // add bb to predecessors, updates bb's successors public bBlock getSucc() // used together to iterate over all successors public bBlock getSuccNext()control flow graph ( bBlock cfg ) The CFG is simply represented by an array of bBlocks. By convention, blocks are kept in the order of the original code for 0..X, with an extra bBlock at X+1 (with 0 instructions) to represent the end of the procedure.
SubmissionYou can submit your project in two ways:
Please carefully read the academic honesty section of the course syllabus. In particular, remember that you are not allowed to show or copy any code for your project, either from the web or other students. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus---please review it at this time.