On Optimal Slicing of Parallel Programs

Optimal program sli ing determines for a statement S in a program whether or not S ae ts a spe ied set of state-ments, given that all onditionals in are interpreted as non-deterministi hoi es. Only re ently, it has been shown that rea hability of pro-gram points and hen e also optimal sli ing is unde idable for multi-threaded programs with (parameterless) pro edures and syn hronization [23℄. Here, we sharpen this result by proving that sli ing remains unde idable if syn hronization is abandoned|although rea hability be omes polynomial. Moreover, we show for multi-threaded programs without syn hronization, that sli ing stays PSPACE-hard when pro-edure alls are forbidden, and be omes NP-hard for loop-free programs. Sin e the latter two problems an be solved in PSPACE and NP, respe tively, even in presen e of syn-hronization, our new lower bounds are tight. Finally, we show that the above de idability and lower bound properties equally apply to other simple program analysis problems like opy onstant propagation and true liveness of variables. This should be ontrasted to the prob-lems of strong opy onstant propagation and (ordinary) liveness of variables for whi h polynomial algorithms have been designed [15, 14, 24℄