A conservative data flow algorithm for detecting all pairs of statements that may happen in parallel

fnaumovic avruningcsumassedu Information about which pairs of statements in a con current program can execute in parallel is important for optimizing and debugging programs for detecting anomalies and for improving the accuracy of dataow analysis In this paper we describe a new data ow al gorithm that nds a conservative approximation of the set of all such pairs We have carried out an initial comparison of the precision of our algorithm and that of the most precise of the earlier approaches Masti cola and Ryders nonconcurrency analysis using a sample of concurrent Ada programs that includes the collection assembled by Masticola For these ex amples our algorithm was almost always more precise than nonconcurrency analysis in the sense that the set of pairs identied by our algorithm as possibly happen ing in parallel is a proper subset of the set identied by nonconcurrency analysis In cases we were able to use reachability analysis to determine exactly the set of pairs of statements that may happen in parallel For these cases there were a total of only six pairs identi ed by our algorithm that cannot actually happen in paralle