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\u27s algorithm to compute the data flow of a concurrent program.The time complexity is the same as for analyzing a ``comparable\u27\u27 sequential program