CMSC 430, Spring 2009

Theory of Language Translation

Project 5 - C-- : Code Analyzer

Due 11:59pm Tue, May 12th, 2009 (extended to Fri, May 15th)

Project Update

  • May 11: Also updated test01.c, test02.c, and test06.c to match corresponding .out files.
  • May 11: Added capability for automated testing

    Automated testing explicitly generates sequences of Java byte code instructions. It only relies on optimizeCode() in ClassFile.java, and does not use your mycc compiler or code generator. You can still use your mycc compiler to generate additional test cases for your data-flow analysis code.

    To use automated testing:

Introduction

In this project you will add some global data-flow analysis to your C-- compiler.

Getting Started

Project 5 will be implemented in Java in Eclipse. Download the following file:
  • Eclipse project archive file p5.zip
You can import the project into Eclipse as an existing project in an archive file.

Along with files used to make direct submissions to the submit server (submit.jar, .submit , submit.rb), you will find the following project files:

Changes

See project 2 description for description of project files and syntax/semantics of C--. Compared to project 5, there are some changes:

  • ClassFile.java now contains skeleton code to perform global data-flow analysis
  • bBlock.java contains code to represent and manipulate basic blocks
You should not need to make any changes to your scanner, parser, or type checker to perform code generation.

Requirements

You 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 framework

Your 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 Variables

Next you must compute data flow information to solve the live variable problem for all local scalar variables (you can ignore arrays & global vars)
  • insert code to compute local information (i.e., GEN and KILL) by looking for ILOAD and ISTORE instructions
  • merge information at joins (combine data to compute OUT for each basic block)
  • propagate information through the basic block (compute IN from OUT and local information)
  • ensure the iterative framework is properly initialized and halts
Existing code in the compiler will display the data-flow information for each basic blocks, and will also use the IN set for the first basic block to warn of possible references to uninitialized variables.

Dead code elimination

Finally, 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.

Useful Classes

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. 

bBlock

bBlock 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.

Submission

You can submit your project in two ways:
  • Submit your mycc.lex, mycc.cup, and ClassFile.java files by first putting all files in a single .zip or .jar archive. The files should be at the top level of the archive, not in a subdirectory.

    You may create a jar archive containing mycc.cup, mycc.lex, and ClassFile.java by going to the directory containing your project, then either execute goJar (or goJar.bat) or type the following command directly:

    jar cf p5.jar mycc.cup mycc.lex ClassFile.java

    You can submit the resulting p5.jar archive to to the submit server by clicking on the submit link in the column "web submission".

    Select the p5.jar archive using the "Browse" button, then press the "Submit project!" button.

  • Submit directly by executing a Java program on a computer with Java and network access. Use the submit.jar file from the archive p5.zip, To submit, go to the directory containing your project, then either execute goSubmit (or goSubmit.bat) or type the following command directly:

    java -jar submit.jar

    You will be asked to enter your class account and password, then all files in the directory (and its subdirectories) will be put in a jar file and submitted to the submit server. If your submission is successful you will see the message:

    Successful submission # received for project 5

Academic Integrity

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.