An Efficient Algorithm for Computing all Program Forward Static Slices

Authors: Jehad Al Dallal

Abstract:

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).

Keywords: Program slicing, static slicing, forward slicing, program dependence graph (PDG).

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1084918

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.