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).
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:64370", author = "Jehad Al Dallal", title = "An Efficient Algorithm for Computing all Program Forward Static Slices", 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).", volume = "2", number = "4", pages = "1327-4", }