article

Free access

Interprocedural slicing using dependence graphs

Authors:

D. BinkleyAuthors Info & Claims

ACM SIGPLAN Notices, Volume 23, Issue 7

Pages 35 - 46

https://doi.org/10.1145/960116.53994

Published: 01 June 1988 Publication History

Abstract

A slice of a program with respect to a program point p and variable x consists of all statements of the program that might affect the value of x at point p. This paper concerns the problem of interprocedural slicing — generating a slice of an entire program, where the slice crosses the boundaries of procedure calls. To solve this problem, we introduce a new kind of graph to represent programs, called a system dependence graph, which extends previous dependence representations to incorporate collections of procedures (with procedure calls) rather than just monolithic programs. Our main result is an algorithm for interprocedural slicing that uses the new representation.

The chief difficulty in interprocedural slicing is correctly accounting for the calling context of a called procedure. To handle this problem, system dependence graphs include some data-dependence edges that represent transitive dependencies due to the effects of procedure calls, in addition to the conventional direct-dependence edges. These edges are constructed with the aid of an auxiliary structure that represents calling and parameter-linkage relationships. This structure takes the form of an attribute grammar. The step of computing the required transitive-dependence edges is reduced to the construction of the subordinate characteristic graphs for the grammar's nonterminals.

References

[1]

Babich, W.A. and Jazayeri, M., "The method of attributes for data flow analysis: Part IL Demand analysis," Acts Informatica 10(3)pp. 265-272 (October 1978).

Digital Library

[2]

Banning, J.P., "An efficient way to find the side effects of procedure calls and the aliases of variables," pp. 29-41 in Conference Record of the Sixth ACM Symposium on Principles of Programming Languages, (San Antonio, TX, Jan. 29-3 l, 1979), ACM, New York (1979).

Digital Library

[3]

Callahan, D., "The program summary graph and flow-sensitive interprocedural data flow analysis," Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation, (Atlanta, GA, June 22-24, 1988), ACM SIGPLAN Notices, (June 1988).

Digital Library

[4]

Cooper, K.D. and Kennedy, K., .Interproceduml side-effect analysis in linear time," Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation, (Atlanta, GA, lune 22-24, 1988), ACM SIGPLANNotices, (June 1988).

Digital Library

[5]

Ferrante, J., Ottenstein, K., and Warren, J., "The program delmndence graph and its use in optimization," ACM Transactions on Programruing Languages and Systems 9(3) pp. 319-349 (July 1987).

Digital Library

[6]

Horwitz, S., Prins, j, and Reps, T, "Integrating non-interfering versions of programs," TR-690, Computer Sciences Department, University of Wisconsin, Madison, WI (March 1987).

[7]

Horwitz, S., Prins, J., and Reps, T., "Inmgrating non-interfering versions of programs," pp. 133-145 in Conference Record of the Fifteenth ACM Symposium on Principles of Programming Languages, (San Diego, CA, january 13-15, 1988), ACM, New York 0988).

Digital Library

[8]

Horwitz, S., Reps, T., and Binldey, D., .lnterprocedural slicing using dependence graphs," TR-756, Caxtputer Sciences Department, University of Wisconsin, Madison, WI (March 1988).

[9]

Kastens, U., .Ordered attribute grammars," Acta Inf. 13(3)pp. 229- 256 (1980).

[10]

Knuth, D.E., "Semantics of context-free languages," Math. $yst. Theory 2(2) pp. 127-145 (June 1968).

[11]

Kou, L.T., "On live-dead analysis for global data flow problenas," Journal ofthe ACM 24(3) pp. 473-483 (iluly 1977).

Digital Library

[12]

Kuek, D.J., Muraoka, Y., and Chert, S.C., "On the number of operations simultaneously executable in FORTRAN-like programs and their resulting speed-up," 1EEE Trans. on Computers C-21(12)pp. 1293-1310 (December 1972).

Digital Library

[13]

Myers, E., "A precise inter-procedural data flow algorithm," pp. 219- 230 in Conference Record of the Eighth ACM Symposium on Principles of Programming Languages, (Williamsburg, VA, January 26-28, 1981), ACM, New York (1981).

Digital Library

[14]

Ottenstein, K.J. and Ouenstein, L.M., "The program dependence graph in a software develognnent environment," Proceedings of the ACM $1GSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, (Pittsburgh, PA, Apr. 23-25, 1984), ACM $IGPLAN Notices 19(5) pp. 177-184 (May 1984).

Digital Library

[15]

Reps, T. and Yang, W., "The semantics of program slicing," Tech. Rep. in preparation, Computer Sciences Department. University of Wisconsin, Madison, WI (Spring 1988).

[16]

Waite, W.M. and Goos, G., Compiler Construction, Springer-Verlag, New York (1983).

Digital Library

[17]

Weiser, M., "Program slicing," IEEE Transactions on Software Engineering SE-10(4) pp. 352-357 (July 1984).

Digital Library

Cited By

Lee SBinkley DFeldt RGold NYoo S(2025)Causal program dependence analysisScience of Computer Programming10.1016/j.scico.2024.103208240(103208)Online publication date: Feb-2025
https://doi.org/10.1016/j.scico.2024.103208
Avitan MRavve EVolkovich Z(2024)Assembly Function Recognition in Embedded Systems as an Optimization ProblemMathematics10.3390/math1205065812:5(658)Online publication date: 23-Feb-2024
https://doi.org/10.3390/math12050658
Hüther LSohr KBerger BRothe HEdelkamp S(2024)Machine Learning for SAST: A Lightweight and Adaptable ApproachComputer Security – ESORICS 202310.1007/978-3-031-51482-1_5(85-104)Online publication date: 11-Jan-2024
https://doi.org/10.1007/978-3-031-51482-1_5
Show More Cited By

Index Terms

Interprocedural slicing using dependence graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

Interprocedural slicing using dependence graphs
PLDI '88: Proceedings of the ACM SIGPLAN 1988 conference on Programming language design and implementation

A slice of a program with respect to a program point p and variable x consists of all statements of the program that might affect the value of x at point p. This paper concerns the problem of interprocedural slicing — generating a slice of an entire ...
Interprocedural slicing using dependence graphs

The notion of a program slice, originally introduced by Mark Weiser, is useful in program debugging, automatic parallelization, and program integration. A slice of a program is taken with respect to a program point p and a variable x; the slice consists ...
Interprocedural slicing using dependence graphs
20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979-1999: A Selection

A slice of a program with respect to a program point p and variable x consists of all statements of the program that might affect the value of x at point p. This paper concerns the problem of interprocedural slicing -- generating a slice of an entire ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 23, Issue 7

Proceedings of the SIGPLAN '88 conference on Programming language design and implementation

July 1988

338 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/960116

Issue’s Table of Contents

PLDI '88: Proceedings of the ACM SIGPLAN 1988 conference on Programming language design and implementation
June 1988
338 pages
ISBN:0897912691
DOI:10.1145/53990
Editor:
R. L. Wexelblat
Philips Laboratories, Briarcliff Manor, NY

Copyright © 1988 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1988

Published in SIGPLAN Volume 23, Issue 7

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

315
Total Citations
View Citations
2,593
Total Downloads

Downloads (Last 12 months)277
Downloads (Last 6 weeks)36

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lee SBinkley DFeldt RGold NYoo S(2025)Causal program dependence analysisScience of Computer Programming10.1016/j.scico.2024.103208240(103208)Online publication date: Feb-2025
https://doi.org/10.1016/j.scico.2024.103208
Avitan MRavve EVolkovich Z(2024)Assembly Function Recognition in Embedded Systems as an Optimization ProblemMathematics10.3390/math1205065812:5(658)Online publication date: 23-Feb-2024
https://doi.org/10.3390/math12050658
Hüther LSohr KBerger BRothe HEdelkamp S(2024)Machine Learning for SAST: A Lightweight and Adaptable ApproachComputer Security – ESORICS 202310.1007/978-3-031-51482-1_5(85-104)Online publication date: 11-Jan-2024
https://doi.org/10.1007/978-3-031-51482-1_5
Vu TDo TVo H(2023)Context-Encoded Code Change Representation for Automated Commit Message GenerationInternational Journal of Software Engineering and Knowledge Engineering10.1142/S021819402350049334:01(185-202)Online publication date: 16-Sep-2023
https://doi.org/10.1142/S0218194023500493
Wang LHu PKong XOuyang WLi BXu HShao T(2023)Microservice architecture recovery based on intra-service and inter-service featuresJournal of Systems and Software10.1016/j.jss.2023.111754204:COnline publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1016/j.jss.2023.111754
Stiévenart QBinkley DDe Roover C(2023)An empirical evaluation of quasi-static executable slicesJournal of Systems and Software10.1016/j.jss.2023.111666200(111666)Online publication date: Jun-2023
https://doi.org/10.1016/j.jss.2023.111666
Feichtinger KHinterreiter DLinsbauer LPrähofer HGrünbacher P(2021)Guiding feature model evolution by lifting code-level dependenciesJournal of Computer Languages10.1016/j.cola.2021.10103463(101034)Online publication date: Apr-2021
https://doi.org/10.1016/j.cola.2021.101034
Soto-Valero CHarrand NMonperrus MBaudry B(2021)A comprehensive study of bloated dependencies in the Maven ecosystemEmpirical Software Engineering10.1007/s10664-020-09914-826:3Online publication date: 25-Mar-2021
https://dl.acm.org/doi/10.1007/s10664-020-09914-8
Galindo CPérez SSilva J(2021)Slicing Unconditional Jumps with Unnecessary Control DependenciesLogic-Based Program Synthesis and Transformation10.1007/978-3-030-68446-4_15(293-308)Online publication date: 13-Feb-2021
https://doi.org/10.1007/978-3-030-68446-4_15
Keirsgieter WVisser W(2020)Graft: Static Analysis of Java Bytecode with Graph DatabasesConference of the South African Institute of Computer Scientists and Information Technologists 202010.1145/3410886.3410901(217-226)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.1145/3410886.3410901
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents