CMSC 430 Project 5: C-- Code optimizer

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

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.

Your task is to extend the compiler to:

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

  For instance, the following displays information for basic block 5,
  showing it has basic block 4 as a predecessor, and basic blocks 6 & 9
  as successors.  The local variables ranges generated/killed are 
  shown, as well as variables live on entry (IN) and exit (OUT).
  The actual instruction(s) in the basic block is simply "ISTORE 2"

    ** Basic block: 5 **
      Length: 1  Successors:  6 9  Predecessors: 4
      GEN {}  KILL {2}  IN {3, 4}  OUT {2, 3, 4}
    >     6: istore_2

- Compute data flow information to solve the live variable problem
  for all local scalar variables (you can ignore arrays & global vars)

   1) insert code to compute local information (i.e., GEN and KILL)
         by looking for ILOAD and ISTORE instructions

   2) merge information at joins (combine data to compute OUT for 
         each basic block) 

   3) propagate information through the basic block (compute IN from 
         OUT and local information)

   4) 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.

  For instance, local variable 4 is shown to be live between 
  the "ISTORE 4" and "ILOAD 4" instructions:

    [B 1]  [Live                         ]   1: istore 4
    [B 2]  [Live              4          ]
    [B 2]  [Live              4          ]
                 ...
    [B m]  [Live              4          ]   n: iload 4

- Elminate some (very simple) dead code

  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 (not
  required for the project) would actually eliminate the computations... 

--------------------------------------------

Some data structures you will need to use:

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

--------------------------------------------

- class bBlock

bBlock is used to representa 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 sucessors, 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 as.
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.