ABSTRACT On Optimal Slicing of Parallel Programs

Optimal program slicing determines for a statement S in a program π whetherornotSaffects a specified set of statements, given that all conditionals in π are interpreted as non-deterministic choices. Only recently, it has been shown that reachability of program points and hence also optimal slicing is undecidable for multi-threaded programs with (parameterless) procedures and synchronization [23]. Here, we sharpen this result by proving that slicing remains undecidable if synchronization is abandoned—although reachability becomes polynomial. Moreover, we show for multi-threaded programs without synchronization, that slicing stays PSPACE-hard when procedure calls are forbidden, and becomes NP-hard for loopfree programs. Since the latter two problems can be solved in PSPACE and NP, respectively, even in presence of synchronization, our new lower bounds are tight. Finally, we show that the above decidability and lower bound properties equally apply to other simple program analysis problems like copy constant propagation and true liveness of variables. This should be contrasted to the problems of strong copy constant propagation and (ordinary) liveness of variables for which polynomial algorithms have been designed [15, 14, 24]