An optimal algorithm for the construction of the system dependence graph

Program slicing can be used to aid in a variety of software maintenance act ivities including code understanding, code testing, debugging, and program reengineering. Program slicing (as well as other program analysis functions including forward slicing) can be efficiently performed on an internal pro gram representation called a system dependence graph (SDG). The constructio n of the SDG depends primarily on the calculation of the transitive depende nces which in turn depends in the calculation of the data dependences. In t his paper we demonstrate the correctness and the optimality (with respect t o the number of iterations required) of our method of calculating the trans itive data dependences. We make a worst-case analysis of our algorithm, and find that is faster than the Horwitz, Reps, and Binkley (HRB) algorithm, a nd comparable to the Reps, Horwitz, Sagiv, and Rosay (RHSR) algorithm. Furt hermore, our method requires neither the (explicit) calculation of the GMOD and GREF sets nor the construction of a linkage grammar and the correspond ing subordinate characteristic graphs of the linkage grammar's non-terminal s. Unlike both the HRB and RHSR algorithms, our algorithm treats recursive procedures separately, permitting a faster (linear time) solution of nonrec ursive procedures. Additionally, a beneficial side effect of this method is that it provides us with a new method for performing interprocedural, how- sensitive data flow analysis. (C) 2000 Published by Elsevier Science Inc. A ll rights reserved.