Information about which statements in a concurrent program may happen
in parallel (MHP) has a number of important applications. It can be
used in program optimization, debugging, program understanding tools,
improving the accuracy of data flow approaches, and detecting
synchronization anomalies, such as data races. For example, in
optimization, if it is known that two threads of control will never
attempt to enter a critical region of code at the same time, any
unnecessary locking operations can be removed.

In general, the problem of precisely computing all pairs of statements
that may execute in parallel is undecidable. If we assume that all
control paths in all threads of control are executable, then the
problem is NP-complete. In this paper, we call the solution with this
assumption the ideal MHP information for a program. To compute the MHP
information efficiently, a trade-off must be made, where instead of
the ideal information, a conservative estimate of all MHP pairs is
computed. In this context a conservative set contains all the pairs
that can actually execute in parallel but may also contain spurious
pairs. The precision of such approaches can be measured by comparing
the set of pairs computed by an approach with the ideal set, if the
latter is known.

In this paper we propose a data flow algorithm for computing a
conservative estimate of the MHP information for Java programs with a
worst-case time bound that is cubic in the size of the program.  To
evaluate the practical precision of our algorithm, we have carried out
a preliminary experimental comparison of our algorithm and a
reachability analysis that determines the ideal MHP information for
concurrent Java programs. This initial experiment indicates that our
algorithm precisely computed the ideal MHP information in the vast
majority of cases we examined. In the two out of 29 cases where our
MHP algorithm turned out to be less than ideally precise, the number
of spurious pairs was small compared to the total number of ideal MHP
pairs.