What are GEN and KILL statements in dataflow analysis?

Question

In data flow analysis, is GEN statement where a variable is used and KILL statement is where variable is redefined?

Answer 1

Dataflow analysis works on sets of facts. GEN points are points in the graph where one of the facts you care about becomes true, and KILL points are points in the graph where one of the facts you care about becomes false.

The GEN and KILL points thus depend on the facts you care about.

For example: if you were doing a constant propagation analysis you might care about the fact that variable x has the constant value 3. Any point in the graph where x is assigned the value 3 is a GEN point. Any point in the graph where x is assigned a constant value other than 3 is a KILL point.

If you were doing reaching definitions, and x is defined in two different places then the facts you are interested in are (1) "x from the first definition may be available here" and (2) "x from the second definition may be available here." In this case the point where x is first defined is a GEN point for fact (1) and a KILL point for fact (2). The point where x is second defined is a GEN point for fact (2) and a KILL point for fact (1).

As a third example, suppose you were doing a liveness analysis. This is a backwards analysis. In this case the places where x is used are GEN points, because x is live at the statement where it is used, and at some of the statements above the statement where it is used. The definitions of x are KILL points, because the previous definitions of x are no longer needed after this node (as well as at along all the nodes along the reverse path until you reach a GEN statement higher in the graph.)