Data flow analysis of parallel programs

Data flow analysis is the prerequisite of performing optimizations
such as common subexpression eliminations or code motion of partial
redundant expressions on imperative sequential programs. To apply
these transformations to parallel imperative programs, the notion
of data flow must be extended to concurrent programs.The additional
source language features are: common address space (shared memory),
nested parallel statements (PAR),or-parallelism, critical regions
and message passing. The underlying interleaving semantics of
the concurrently-executed processes result in the so-called state
space explosion which on first appearance prevents the computation
of the meet over all path solution needed for data flow analysis.

For the class of one-bit data flow problems (also known as
bit-vector problems) we can show that for the computation of the
meet over all path solution, not all interleavings are needed.
Based on that, we can give simple data flow equations
representing the data flow effects of the PAR statement.The
definition of a parallel control flow graph leads to an efficient
extension of Killdal's algorithm to compute the data flow of a
... mehrconcurrent program.The time complexity is the same as for analyzing
a ``comparable'' sequential program.