CS 394P: Data Flow Analysis

Due: February 21, 2005.

This assignment is to write some basic programs for data flow analysis.

Examine the code in the file dataflow.lsp . This file contains some helper functions and some test data.

We will represent a basic block as a node containing code as a progn of statements. Each node also has a node number, the numbers of its successor nodes, and places to hold the data flow information. Data flow information will be represented as sets of symbols, where each symbol is either a variable or a compiler variable that represents a subexpression. You can use the Lisp functions union, intersection, and set-difference to manipulate these sets.

1. Call the function (initexprs) once to initialize the expression table, *exprs* . (initexprs) will associate each subexpression with a compiler variable, which will be a generated symbol. After calling (initexprs), you can look at *exprs* to see what it produced.
2. Write a function (comp-kill node) to create the computed and killed sets due to the code in a node, and save the results in the node data structure. You can use (setf (computed node) ...) and (setf (killed node) ...) to store the results. Each of these sets will be represented as a list of symbols.
3. Write a loop to call comp-kill on all nodes.
4. Write a function (avail-entry node) to compute what is available on entry to a node from what is available on exit from its predecessors. You can assume that (avail-exit node) has been stored; initially, of course, it will be empty.
5. Write a function to iteratively compute (avail-exit node) based on (avail-entry node) and what is computed and killed within the node. Continue updating these values until there is no further change.
6. Write a function to iterate through all nodes and identify redundant parts of the code. For each node, print out the node number and iterate through each statement of the code. Keep an available set that is available-on-entry initially, and update it for each statement. If a statement involves some redundant code, print out the statement and the redundant expression.

You will probably find that not all of the subexpressions that are actually redundant are identified by your algorithm. The remaining ones can be found using more sophisticated methods.

The following functions can be used in writing your code:

• (predecessors node) returns a list of node numbers of the predecessors of node.
• (expcomputed exp) returns the set of subexpressions that are computed in the process of computing exp.
• (killedby var) returns the set of subexpressions that are killed by redefinition of var.