Editing Data-flow analysis (section)

== Special classes of problems ==
There are a variety of special classes of dataflow problems which have efficient or general solutions.

=== Bit vector problems ===
The examples above are problems in which the data-flow value is a set, e.g. the set of [[reaching definitions]] (Using a bit for a definition position in the program), or the set of live variables. These sets can be represented efficiently as '''[[Bit array|bit vectors]]''', in which each bit represents set membership of one particular element. Using this representation, the join and transfer functions can be implemented as bitwise logical operations. The join operation is typically union or intersection, implemented by bitwise ''logical or'' and ''logical and''.
The transfer function for each block can be decomposed in so-called ''gen'' and ''kill'' sets.

As an example, in live-variable analysis, the join operation is union. The ''kill'' set is the set of variables that are written in a block, whereas the ''gen'' set is the set of variables that are read without being written first. The data-flow equations become

:<math> out_b = \bigcup_{s \in succ_b} in_s </math>

:<math> in_b = (out_b - kill_b) \cup gen_b </math>

In logical operations, this reads as

 out(''b'') = 0
 '''for''' ''s'' '''in''' succ(''b'')
     out(''b'') = out(''b'') '''or''' in(''s'')
 in(''b'') = (out(''b'') '''and not''' kill(''b'')) '''or''' gen(''b'')

Dataflow problems which have sets of data-flow values which can be represented as bit vectors are called '''bit vector problems''', '''gen-kill problems''', or '''locally separable problems'''.<ref name="Reps_1995"/> Such problems have generic polynomial-time solutions.<ref name="Knoop_1996"/>

In addition to the reaching definitions and live variables problems mentioned above, the following problems are instances of bitvector problems:<ref name="Knoop_1996"/>
* [[Available expression]]s
* Very busy expressions
* [[Use-define chain|Use-definition chains]]

=== IFDS problems ===
'''Interprocedural, finite, distributive, subset problems''' or '''IFDS''' problems are another class of problem with a generic polynomial-time solution.<ref name="Reps_1995"/><ref name="Naeem_2010"/> Solutions to these problems provide context-sensitive and flow-sensitive dataflow analyses.

There are several implementations of IFDS-based dataflow analyses for popular programming languages, e.g. in the Soot<ref name="Bodden_2012"/> and WALA<ref name="Rapoport_2015"/> frameworks for Java analysis.

Every bitvector problem is also an IFDS problem, but there are several significant IFDS problems that are not bitvector problems, including truly-live variables and possibly-uninitialized variables.