CS618 Program Analysis (2016-17 Ist Semester, IIT Bombay)

Assignment 2

This assignment has 3 questions.

  1. Available Expression Analysis
  2. Live Variables Analysis
  3. Design a Data Flow Analysis

Q1: Available Expression Analysis

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)

Q2: Live Variables Analysis

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)

Q3: Design a Data Flow Analysis

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.


Take me to the Top

powered by Pandoc

Last Modified at : Fri Aug 5 06:19:49 IST 2016