Assignment 2

This assignment has 3 questions.

Perform available expressions analysis, i.e. compute gen, kill, in and out for each block for the given flow graph. Show in and out for each block for each iteration till a fix-point is reached.

Entry and Exit blocks are not shown in the graph. The first block of the program is (1) and the last block is (9)

Perform live variables analysis, i.e. compute gen, kill, in and out for each block for the given flow graph. Show in and out for each block for each iteration till a fix-point is reached.

Entry and Exit blocks are not shown in the graph. The first block of the program is (1) and the last block is (9)

Consider a simple language that has only two arithmetic operations: addition (+), and multiplication (*). Further, the language has only integer variables. Otherwise it is similar to the 3-address language discussed in class.

For any given program in this language, we would like to divide program variables into the following four categories at each program point:

1. Positive Even
2. Positive Odd
3. Negative Even
4. Negative Odd

Here, if a variable X is marked "Positive Even" at a program point p, it means that X has a value at p that is definitely a positive even number. The other categories are defined analogously. Assume 0 is positive for the analysis purpose.

1. Design a data flow analysis for 3-address programs in this language. In particular, describe the direction of the analysis, the lattice (or the component lattices), the transfer functions for the different types of the statements, and the meet operation.

2. Are your flow functions monotonic? Give proof. If you can not give proof, give intuition.