Dataflow analysis

As a motivating example, consider the C fragment below, which sets r to xy.

It is possible to optimize it slightly by replacing the expression y₁*2 at line 7 by t.

This is valid because, at line 7, the expression y₁*2 is what we call available. This means that, no matter how line 7 is reached, y₁*2 will have been computed previously at line 4, and its value stored in variable t. This value is still valid at line 7 because no redefinition of y₁ (or t) appears between these two points.

Generally speaking, we can define for every program point the set of available expressions, which is the set of all non-trivial expressions whose value has already been computed at that point. These can then be computed iteratively, as illustrated in the image below, where the above program is presented in control-flow graph form.

(Note: to better understand how the computation of the sets of available expressions above proceeds, it is recommended to look at the lecture slides, where it appears in animated form. This is true for several images in these lecture notes.)

The ideas presented informally above can be formalized by:

1. introducing a variable \(i_n\) for the set of expressions available before node \(n\), and a variable \(o_n\) for the set of expressions available after node \(n\) (\(i\) stands for input, \(o\) for output),
2. defining equations between those variables,
3. solving those equations.

For our example program, the equations are:

and they can be solved iteratively as follows:

1. initialize all sets \(i_1, \ldots, i_{10}, o_1, \ldots, o_{10}\) to the set of all non-trivial expressions in the program, here {y₁*2, y₁+1, r*r, r*x},
2. viewing the equations as assignments, compute the "new" value of those sets,
3. iterate until fixed point is reached.

Initialization is done that way because we are interested in finding the largest sets satisfying the equations: the larger a set is, the more information it conveys for this analysis.

Before trying to solve it, we can simplify the above system of equations by replacing all \(i_k\) variables by their value. We get:

The simpler system can be solved by iterating until a fixed point is reached, which happens after 7 iterations, as illustrated below (iterations proceed from left to right):

In general, for a node \(n\) of the control-flow graph, the equations have the following form:

where \(p_1, \ldots, p_k\) are the predecessors of \(n\), \(\mathrm{gen_{AE}}(n)\) are the non-trivial expressions computed by \(n\), and \(\mathrm{kill_{AE}}(n)\) is the set of all non-trivial expressions that use a variable modified by \(n\).

Notice that for the second equation to be correct, expressions that are computed by \(n\) but which use a variable modified by \(n\) must not be part of \(\mathrm{gen_{AE}}(n)\). For example:

The above equations can be simplified by substituting \(i_n\) in \(o_n\), to obtain the following equation for \(o_n\):

These are the dataflow equations for the available expressions dataflow analysis.

The available expressions analysis just presented in one example of a dataflow analysis. Dataflow analysis is an analysis framework that can be used to approximate various properties of programs. The results of those analyses can be used to perform several optimisations, for example:

• common sub-expression elimination,
• dead code elimination,
• constant propagation,
• register allocation,
• etc.

In the following, we will only consider intra-procedural dataflow analyses. That is, analyses that work on a single function at a time. As in our example, those analyses work on the code of a function represented as a control-flow graph (CFG).

The nodes of the CFG are the statements of the function, while the edges of the CFG represent the flow of control: there is an edge from \(n_1\) to \(n_2\) if and only if control can flow immediately from \(n_1\) to \(n_2\). That is, if the statements of \(n_1\) and \(n_2\) can be executed in direct succession.

We associate to every node \(n\) a pair of variables \((i_n,o_n)\) that give the set of variables live when the node is entered or exited, respectively. These variables are defined as follows:

where \(\mathrm{gen_{LV}}(n)\) is the set of variables read by \(n\), \(\mathrm{kill_{LV}}(n)\) is the set of variables written by \(n\) and \(s_1, \ldots, s_k\) are the successors of \(n\).

Substituting \(o_n\) in \(i_n\), we obtain the following equation for \(i_n\):

We are interested in finding the smallest sets of variables live at a given point, as the information conveyed by a set decreases as its size increases. Therefore, to solve these equations by iteration, we initialize all sets with the empty set.

The example below illustrates the computation of live variables:

The result of the analysis makes it clear that neither x nor y are live at the same time as z. Therefore, z can be replaced by either x or y, thereby saving one assignment:

We associate to every node \(n\) a pair of variables \((i_n,o_n)\) that give the set of definitions reaching the entry and exit of \(n\), respectively. These variables are defined as follows:

where \(\mathrm{gen_{RD}}(n)\) is \(\{n\}\) if \(n\) is a definition, \(\emptyset\) otherwise, \(\mathrm{kill_{RD}}(n)\) is the set of definitions defining the same variables as \(n\) itself and \(p_1, \ldots, p_k\) are the predecessors of \(n\).

Substituting \(i_n\) in \(o_n\), we obtain the following equation for \(o_n\):

We are interested in finding the smallest sets of definitions reaching a point, as the information conveyed by a set decreases as its size increases. Therefore, to solve the equations by iteration, we initialize all sets with the empty set.

The example below illustrates the computation of reaching definitions:

The result of the analysis makes it clear that a single, constant definition of y reaches node 5. Therefore, y can be replaced by 3 in node 5.

If the language being analyzed permits uninitialized variables, the above analysis can produce incorrect results. This can be illustrated by the following example:

To solve this problem, all variables should be recorded as "initialized in some unknown location" at the entry of the first node:

We associate to every node \(n\) a pair of variables \((i_n,o_n)\) that give the set of expressions that are very busy when the node is entered or exited, respectively. These variables are defined as follows:

where \(\mathrm{gen_{VB}}(n)\) is the set of expressions evaluated by \(n\), \(\mathrm{kill_{VB}}(n)\) is the set of expressions killed by \(n\) and \(s_1, \ldots, s_k\) are the successors of \(n\).

Substituting \(o_n\) in \(i_n\), we obtain the following equation for \(i_n\):

We are interested in finding the largest sets of very busy expressions, as the information conveyed by a set increases with its size. Therefore, to solve the equations by iteration, we initialize all sets with the set of all non-trivial expressions appearing in the program.

The example below illustrates the computation of very busy expressions:

The result of the analysis make it clear that a-b is very busy before the conditional. It can therefore be evaluated earlier:

Computing the fixed point by simple iteration as we did works, but is wasteful as the information for all nodes is re-computed at every iteration.

It is possible to do better by remembering, for every variable v, the set dep(v) of the variables whose value depends on the value of v itself. Then, whenever the value of some variable v changes, we only re-compute the value of the variables that belong to dep(v).

This work-list algorithm could be expressed as follows in Scala:

def solve[T](eqs: Seq[(Int => T) => T],
	     dep: Int => List[Int],
	     init: T): (Int => T) = {
  def loop(q: List[Int], sol: Map[Int,T]): (Int => T) =
    q match {
      case i :: is =>
	val y = eqs(i)(sol)
	if (y == sol(i))
	  loop(is, sol)
	else
	  loop(is ::: (dep(i) diff q), sol + i->y)
      case Nil =>
	sol
    }
  loop(List.range(0, eqs.length),
       Map.empty withDefaultValue init)
}

Using it to solve our example system of equations, we end up needing "only" 11 computations, 7 less than with the standard iterative technique:

While the work-list algorithm was more efficient on our example than the basic iterative technique, it should be clear that the process could be even faster if the elements of the work-list were ordered in the reverse order. This is because live variables analysis is a backward analysis.

The goal of node ordering is to order the elements of the work-list in such a way that the solution is computed as fast as possible.

For backward analyses, ordering the variables in the work-list according to a post-order traversal of the CFG nodes speeds up convergence. For forward analyses, reverse post-order has the same characteristic.

By ordering the nodes in post-order, only 6 computations are required to obtain the solution to our example:

Until now, CFG nodes were single instructions. In practice, basic blocks tend to be used as nodes, to reduce the size of the CFG.

When dataflow analysis is performed on a CFG composed of basic blocks, a pair of variables is attached to every block, not to every instruction.

Once the solution is known for basic blocks, computing the solution for individual instructions is easy.

All dataflow analyses we have seen work on sets of values.

If these sets are dense, a good way to represent them is to use bit vectors: a bit is associated to every possible element of the set, and its value is 1 if and only if the corresponding element belongs to the set.

On such a representation, set union is bitwise-or, set intersection is bitwise-and, set difference is bitwise-and composed with bitwise-negation.

This technique can be illustrated on our running example: