CMSC 430: 

Project 4: C-- Code optimizer

In this project you will add some simple peephole optimizations
to your C-- code generator, as well as several global optimizations.  

Optimizations are turned on when the "-O" command-line flag is 
detected, and the boolean variable "optFlag" is set to true.
Write your code so that optimizations are performed only when
"optFlag" is true.


Part 1:  Peephole optimizations 

Implement the following transformations as part of AST or bytecode generation.

- evaluate constant arithmetic expressions (e.g., 1+2 -> 3)
- fold constant relational expressions (e.g., 1 == 1 -> true)
- simplify boolean expressions (e.g., true && x -> x)
- apply algebraic simplification (e.g., 0+x -> x)
- simplify IF statements (e.g., IF (true) stmt1 ELSE stmt2 -> stmt1)
- simplify WHILE loops (e.g., WHILE (true) stmts -> L stmts GOTO L)

You should base your optimizer on your code generator from project 4.


Part 2:  Global optimizations

You are given a skeleton data flow analyzer for calculating Live variables.
The existing code builds a simplified control flow graph (CFG), treating
every statement as a basic block, and assuming all statements are executed
in order.  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)

- in the data flow computation function, 

   1) insert code to compute local information (i.e., GEN and KILL)
   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.

Code in the compiler will display the control-flow and data-flow information 
you compute for each program, and use it to warn of possible references to
uninitialized variables.

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

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.