An Efficient Algorithm for Computing all Program Forward Static Slices

Program slicing is the task of finding all statements in a program that directly or indirectly influence the value of a variable occurrence. The set of statements that can affect the value of a variable at some point in a program is called a program backward slice. In several software engineering applications, such as program debugging and measuring program cohesion and parallelism, several slices are computed at different program points. The existing algorithms for computing program slices are introduced to compute a slice at a program point. In these algorithms, the program, or the model that represents the program, is traversed completely or partially once. To compute more than one slice, the same algorithm is applied for every point of interest in the program. Thus, the same program, or program representation, is traversed several times. In this paper, an algorithm is introduced to compute all forward static slices of a computer program by traversing the program representation graph once. Therefore, the introduced algorithm is useful for software engineering applications that require computing program slices at different points of a program. The program representation graph used in this paper is called Program Dependence Graph (PDG).

Authors:

• Jehad Al Dallal

Keywords:

• Program slicing
• static slicing
• forward slicing
• program dependence graph (PDG).

References:

[1] M. Weiser, Program slicing, IEEE Transactions on Software
Engineering, 1984, 10(4), pp. 352-357.
[2] B. Korel and J. Laski, Dynamic slicing of computer programs, The
Journal of Systems and Software, 1990, 13(3), pp. 187-195.
[3] S. Horwitz, T. Reps, and D. Binkley, Interprocedural slicing using
dependence graphs, ACM Transactions on Programming Languages and
Systems, 1990, 12(1), pp. 26-60.
[4] P. Hausler, Denotational program slicing, In Proceedings of the 22nd
Hawaii International Conference on System Sciences, Hawaii, 1989, pp.
486-494.
[5] J. Bergstar and B. Carre, Information-flow and data flow analysis of
while-programs, ACM Transactions on Programming Languages and
Systems, 7(1), 1985, pp. 37-61.
[6] K. Ottenstein and L. Ottenstein, The program dependence graph in
software development environment, In Proceedings of the ACM
SIGSOFT/SIGPLAN Software Engineering Symposium on Practical
Software Development Environments, SIGPLAN Notices 19(6), 1984,
pp. 177-184.
[7] F. Tip, A survey of program slicing techniques, Technical Report: CSR9438,
CWI (Centre for Mathematics and Computer Science),
Amsterdam, The Netherlands, 1994.
[8] M. Weiser, Programmers use slices when debugging, Communications
of the ACM, 1982, 25, pp. 446-452.
[9] R. Gupta, M. Harrold, and M. Soffa, An approach to regression testing
using slicing, Proceedings of the International Conference on Software
Maintenance, 1992, pp. 299-308.
[10] K. Gallagher and J. Lyle, Using program slicing in software
maintenance, IEEE Transactions on Software Engineering, 1991, 17(8),
pp. 751 - 761.
[11] S. Horwitz, J. Prins, and T. Reps, Integrating non-interfering versions of
programs, ACM Transactions on Programming Languages and Systems,
1989, 11(3), pp. 345-387.
[12] L. Ott and J. Thuss, Slice based metrics for estimating cohesion,
Proceedings of the IEEE-CS International Metrics Symposium, 1993,
pp. 78-81.
[13] H. Longworth, Slice based program metrics, Master-s thesis, Michigan
Technological University, 1985.