Data Flow Analysis

Very Busy Expression Analysis

Consider the following program:

z = 3
# some point in the program (point A)
if i % 2 == 0:
  x = a*b
else:
  y = a*b

# exit

Note that a*b is used twice in the program. Moreover, we can compute a*b value at point A in the program. Let’s do that:

z = 3
t = a*b # some point in the program (point A)

if i % 2 == 0:
  x = t
else:
  y = t

# exit

Now, we want to automatically find such places. The places where we can define new variables (t in this example) and where we can use them in all possible paths of the program starting from point A of the program. In the previous example, the very busy expression is a*b. For example, following program does not have a very busy expression:

z = 3
# point A
if i % 2 == 0:
  x = a*b
else:
  y = a + b

# exit

This does not have a very busy expression because there is no expression at point A. Dataflow analysis can find the expressions through bacward pass since this information flows from back to the head.

Available Expression Analysis

This one is also used for computer program optimizations. If we once computed value for an expression, we can use it in the future computations. This analysis helps us re-use that information. For example, consider this program:

1: x = 1
2: y = 2
3: z = 3

4: c = x+y
5: d = x-y

6: e = x+y-1
7: x += 1

8: c = x+y

In this program, line 4 computes expression x+y and line 5 computes expression x-y. These can be used in the next lines of the program. However, if we change some variable that are used in the expressions, the expression will be invalid. For example, we can use x+y expression in line 4, 5 and 6. However, after line 7, it will be invalid because we need to recalculate the value of it! Finding which values can be recomputed can be calculated with available expression analysis.

Live Variable Analysis

This is a bit easier. Assume we are at some point in the program. If we are going to use a variable in the program after the given point in the program, we say that the variable is live. For example, in the following program, variable x is live after line 1 and in line 2 and 3. Moreover, variable y is live after line 2 and in line 3.

1: x = 2
2: y = 3
3: c = 2*y
4: d = x