More Web Proxy on the site http://driver.im/

article

Free access

The semantics of program dependence

Authors:

Robert Cartwright,

Mattias FelleisenAuthors Info & Claims

ACM SIGPLAN Notices, Volume 24, Issue 7

Pages 13 - 27

https://doi.org/10.1145/74818.74820

Published: 21 June 1989 Publication History

Abstract

Optimizing and parallelizing compilers for procedural languages rely on various forms of program dependence graphs (pdgs) to express the essential control and data dependencies among atomic program operations. In this paper, we provide a semantic justification for this practice by deriving two different forms of program dependence graph — the output pdg and the def-order pdg—and their semantic definitions from non-strict generalizations of the denotational semantics of the programming language. In the process, we demonstrate that both the output pdg and the def-order pdg (with minor technical modifications) are conventional data-flow programs. In addition, we show that the semantics of the def-order pdg dominates the semantics of the output pdg and that both of these semantics dominate—rather than preserve—the semantics of sequential execution.

References

[1]

AHO, A., R. SETm, AND J. ULLMAN. Compilers--Principles, Techniques, and Tools. Addison-Wesley, Reading, Mass., 1985.

Digital Library

[2]

FERRANTE, J. AND K. OTTENSTEIN. A program form based on data dependency in predicate regions. In Proc. l Oth A CM Symposium on Principles of Programming Languages, 1983, 217-236.

Digital Library

[3]

FERRANTE, J., K. OTTENSTEiN, AND J. WAR- ttEN. The program dependence graph and its use in optimization. A CM Trans. Program. Lang. $yst. 9(3), 1987, 319-349.

Digital Library

[4]

HORWITZ, S., J. PruNs, AND T. Rv. rs. On the adequacy of program dependence graphs representing programs. In Proc. 15th A CM Symposium on Principles of Programming Languages, 1988, 146-157.

Digital Library

[5]

HORWITZ, S., J. PRINS, AND T. REPS. integrating non-interfering versions of programs. In Proc. 15th ACM Symposium on Principles of Programming Languages, 1988, 133-145.

Digital Library

[6]

JORRING, U. AND W. L. SC~ERLIS. Compilers and staging transformations. In Proc. 13th A CM Symposium on Principles of Programming Languages, 1986, 86-96.

Digital Library

[7]

KUCK, D. J., R. H. KUHN, D. A. PADUA, AND M. WOLFE. Dependence graphs and compiler optimizations. In Proc. 8th A CM Symposium on Principles of Programming Languages, 1981, 207- 218.

Digital Library

[8]

OTTENSTEIN, K. J. An intermediate program form based on a cyclic data-dependence graph. Technical Report No 81-1, Department of Computer Science, Michigan Tech. University, 1981.

[9]

SCHMIDT, D.A. Denotational Semantics: A Methodology for Language Development. Allyn and Bacon, Newton, Mass., 1986.

Digital Library

[10]

SELKE, R. P. A Rewriting Semantics for Program Dependence Graphs. In Proc. 16th A CM Symposium on Principles of Programming Languages, 1989, 12-24

Digital Library

[11]

WAND, M. Loops in combinator-based compilers. in Proc. l Oth Symposium on Principles of Programming Languages, 1983, 190-196.

Digital Library

[12]

WAND, M. Semantics-directed machine architecture. In Proc. 9th Symposium on Principles of Programming Languages, 1982, 234-241.

Digital Library

[13]

WAND, M. Deriving target code as a representation of continuation semantics. A CM Trans. Program. Lang. Syst. 4(3), 1982, 496-517.

Digital Library

[14]

WARREN, J. A hierarchical basis for reordering transformations. In Proc. llth A CM Symposium on Principles of Programming Languages, 1984, 272-282.

Digital Library

[15]

WOLFE, M. J. Optimizing Supercompilers for Supercomputers. Ph.D. dissertation, University of Illinois, 1982.

Digital Library

Cited By

Ullah FNaeem MBajahzar AAl-Turjman F(2021)IoT-based Cloud Service for Secured Android Markets using PDG-based Deep Learning ClassificationACM Transactions on Internet Technology10.1145/341820622:2(1-17)Online publication date: 22-Oct-2021
https://dl.acm.org/doi/10.1145/3418206
Halder RCortesi A(2013)Abstract program slicing on dependence condition graphsScience of Computer Programming10.1016/j.scico.2012.05.00778:9(1240-1263)Online publication date: Sep-2013
https://doi.org/10.1016/j.scico.2012.05.007
Ward MZedan H(2010)Combining dynamic and static slicing for analysing assemblerScience of Computer Programming10.1016/j.scico.2009.11.00175:3(134-175)Online publication date: Mar-2010
https://doi.org/10.1016/j.scico.2009.11.001
Show More Cited By

Index Terms

The semantics of program dependence

Recommendations

The semantics of program dependence
PLDI '89: Proceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementation

Optimizing and parallelizing compilers for procedural languages rely on various forms of program dependence graphs (pdgs) to express the essential control and data dependencies among atomic program operations. In this paper, we provide a semantic ...
The program dependence graph and its use in optimization

In this paper we present an intermediate program representation, called the program dependence graph (PDG), that makes explicit both the data and control dependences for each operation in a program. Data dependences have been used to represent only the ...
An operational semantics of program dependence graphs for unstructured programs
ASIAN'06: Proceedings of the 11th Asian computing science conference on Advances in computer science: secure software and related issues

The program dependence graph (PDG) represents data and control dependences between statements in a program. The PDG is a useful intermediate representation for compiler code optimizations, because compiler code optimizations mostly rely on data and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 24, Issue 7

Proceedings of the SIGPLAN '89 symposium on Interpreters and interpretive techniques

July 1989

355 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/74818

Editor:
Richard Wexelblat

Issue’s Table of Contents

PLDI '89: Proceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementation
June 1989
355 pages
ISBN:089791306X
DOI:10.1145/73141
Editor:
R. L. Wexelblat
ACM Headquarters, New York, NY

Copyright © 1989 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: 21 June 1989

Published in SIGPLAN Volume 24, Issue 7

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

92
Total Citations
View Citations
972
Total Downloads

Downloads (Last 12 months)137
Downloads (Last 6 weeks)15

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ullah FNaeem MBajahzar AAl-Turjman F(2021)IoT-based Cloud Service for Secured Android Markets using PDG-based Deep Learning ClassificationACM Transactions on Internet Technology10.1145/341820622:2(1-17)Online publication date: 22-Oct-2021
https://dl.acm.org/doi/10.1145/3418206
Halder RCortesi A(2013)Abstract program slicing on dependence condition graphsScience of Computer Programming10.1016/j.scico.2012.05.00778:9(1240-1263)Online publication date: Sep-2013
https://doi.org/10.1016/j.scico.2012.05.007
Ward MZedan H(2010)Combining dynamic and static slicing for analysing assemblerScience of Computer Programming10.1016/j.scico.2009.11.00175:3(134-175)Online publication date: Mar-2010
https://doi.org/10.1016/j.scico.2009.11.001
Wu F(2006)Formal specification of program slicingACM SIGPLAN Notices10.1145/1229493.122949741:12(18-27)Online publication date: 1-Dec-2006
https://dl.acm.org/doi/10.1145/1229493.1229497
Binkley DDanicic SGyimóthy THarman MKiss ÁKorel B(2006)Theoretical foundations of dynamic program slicingTheoretical Computer Science10.1016/j.tcs.2006.01.012360:1(23-41)Online publication date: 21-Aug-2006
https://dl.acm.org/doi/10.1016/j.tcs.2006.01.012
Reps TTurnidge T(2005)Program specialization via program slicingPartial Evaluation10.1007/3-540-61580-6_20(409-429)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-61580-6_20
Harman MHierons R(2002)An overview of program slicingSoftware Focus10.1002/swf.412:3(85-92)Online publication date: 25-Jan-2002
https://doi.org/10.1002/swf.41
Agrawal H(1994)On slicing programs with jump statementsACM SIGPLAN Notices10.1145/773473.17845629:6(302-312)Online publication date: 1-Jun-1994
https://dl.acm.org/doi/10.1145/773473.178456
Agrawal HSarkar VRyder BSoffa M(1994)On slicing programs with jump statementsProceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation10.1145/178243.178456(302-312)Online publication date: 1-Aug-1994
https://dl.acm.org/doi/10.1145/178243.178456
Griswold W(1993)Direct update of data flow representations for a meaning-preserving program restructuring toolProceedings of the 1st ACM SIGSOFT symposium on Foundations of software engineering10.1145/256428.167063(42-55)Online publication date: 1-Dec-1993
https://dl.acm.org/doi/10.1145/256428.167063
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