Honors Compilers
			 G22.3130 Spring 2000

			     Assignment 6
		     Global Dataflow Analysis

			Due Tuesday, April 18


Your assignment is to build a flow graph for each procedure in a
pointless program and to compute global dataflow information
(e.g. reaching definitions, live variables, available expression) on
each flow graph. The global dataflow information you choose to compute
is up to you, and will depend on the optimization(s) that you choose
to implement in Assignment 7.

Choosing an Optimization
-----------------------

In order to decide what dataflow information to compute, you must
choose the optimization(s) that you will implement for assignment 7. 
See assignment 7 for details.


Building a Flow Graph
---------------------

This phase should take the three-address code in its internal
representation, as enerated by your intermediate code generator, and
form a flow graph for each procedure. Each node in the flow graph is a
basic block, which can be represented by a Java object containing:

  1. An array or vector of quadruples, as described in assignment 4. 
  2. An array or vector of predecessor nodes.
  3. An array or vector of successor nodes.
  4. Field(s) to represent dataflow information (see below).
  4. Any other fields you feel are necessary (e.g. a field giving the 
     "name" of the basic block, which can simply be an integer).

The algorithm for constructing a flow graph from straight-line code
(as generated by your intermediate code generator) is simple and is
described in the dragon book.


Computing Global Dataflow Information
-------------------------------------

Depending on the optimization(s) you choose to implement for
assignment 7, your compiler should compute reaching definitions,
UD-chains, DU-chains, available expressions, and/or live variables.
Only compute what is necessary.

You are free to use the dataflow equations in the Dragon book for
specifying IN[B], OUT[B], GEN[B], KILL[B], etc. as well as the
iterative algorithms for computing these sets.

Feel free to represent the dataflow information as you like. If you
choose to use a bitvector (or some array structure where each element
corresponds to a particular instruction), then you will probably need
to assign each instruction in the flow graph a number corresponding
to its position in the bitvector. The Dragon books describes how
to do this.

Generating Assembly from the Flow Graph
---------------------------------------

Once your compiler has performed the desired anlysis and
optimization(s), it must be able to generate assembly code, as it did
for assignment 5. This can be implemented in one of two ways:

1. Adapt your assembly code generator to work on flow graphs.

2. Add code to the optimization phase that coverts a flow graph back to
   the format expected by your assembly code generator.  

Either way is fine.


Output to Turn in
-----------------

You will be given a Pointless program. Your compiler should print the
following for each procedure in the program:

1. Print out the flow graph, basic block by basic block. The output does
   not have to be fancy. Each basic block can be printed as a list of
   quadruples along with the "name" of the basic block and the names
   of its predecessors and successors. No edges need to be drawn graphically.

2. Print out IN and OUT sets for each block, computed by the dataflow analysis.
   This output should be somewhat readable, at least.