Article

Free access

The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages

Authors:

Karl J. Ottenstein,

Robert A. Ballance,

Arthur B. MacCabeAuthors Info & Claims

PLDI '90: Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation

Pages 257 - 271

https://doi.org/10.1145/93542.93578

Published: 01 June 1990 Publication History

Abstract

The Program Dependence Web (PDW) is a program representation that can be directly interpreted using control-, data-, or demand-driven models of execution. A PDW combines a single-assignment version of the program with explicit operators that manage the flow of data values. The PDW can be viewed as an augmented Program Dependence Graph. Translation to the PDW representation provides the basis for projects to compile Fortran onto dynamic dataflow architectures and simulators. A second application of the PDW is the construction of various compositional semantics for program dependence graphs.

References

[1]

ALLAN, S. J., AND OLDENHOEFT, A. E. A flow analysis procedure for the translation of high level languages to a data flow language. IEEE Trans. on Computers TC-29, 9 (Sept. 1980), 826-831.

Digital Library

[2]

ALPERN, B., WEGMAN, M. N., AND ZADECK, F.K. Detecting equality of variables in programs. In Proceedings of the 15th Annual A CM Sympos:ium on Principles of Programming Languages (San Diego, California, January 13-15, 1988), ACM, pp. 1-11.

Digital Library

[3]

ARVIND, DERTOUZOS, M. L., NIKHIL, R. S., AND PAPADOPOULOS, G. M. Project Dataflow: A parallel computing system based on the Monsoon architecture and the Id programming language. Computation Structures Group Memo 285, Massachusetts Institute of Technology Laboratory for Computer Science, Cambridge, Massachusetts, March 25, 1988.

[4]

AaVIND, AND GOSTELOW, K. P. The U- interpreter. IEEE Computer i5, 2 (Feb. 1982), 42- 50.

[5]

ARVIND, AND NIKHIL, R. S. Executing a program on the MIT tagged-token datafiow architecture. iEEE Trans. on Computers TC-3g, 3 (March 1990), 300-318.

Digital Library

[6]

ARVIND, NIKHIL, R. S., AND PiNGALI, K. K. i- Structures: Data structures for parallel computing. A CM Trans. on Programming Languages and Systems 11, 4 (Oct. 1989), 598-632.

Digital Library

[7]

BALLANCE, R. A., MACCABE, A. B., ANO OT- TENSTEIN, K. J. The program dependence web: A representation supporting control, data, and demand-driven interpretation of imperative languages. Technical Report LA-UR-89-3654, Los Alamos National Laboratory, 1990.

[8]

BECK, M., AND PINGALI, K. From control flow to datafiow. Tech. Rep. 89-1050, Cornell University, Dept. of Computer Science, Oct. 1989.

[9]

CARTWRIGHT, R., AND FELLEISEN, M. The semantics of program dependence. In Proc. of the SIGPLAN '89 Conference on Programming Language Design and Implementation (Portland, Oregon, June 21-23, 1989), ACM, pp. 13-27. Appeared as Sigplan Notices, 24(7), July 1989.

Digital Library

[10]

CYTRON, R., FERRANTE, J., ROSEN, B. K., WEGMAN, M. N., AND ZADECK, F. K. An emcient method of computing static single assignment form. In Proceedings of the ldth Annual A CM Symposium on Principles of Programming Languages (Los Angeles, January 17-19, 1989), ACM, pp. 25-35.

Digital Library

[11]

ELLCEY, S. J. The program dependence graph: Interprocedural information representation and general space requirements. M.S. thesis, Michigan Technological University, Jan. 1985.

[12]

FERR^NTE, J., AND MACe., M. On linearizing parallel code. In Proceedings of the 12th Annual A CM Symposium on Principles of Programming Languages (New Orleans, Louisiana, January 14- 16, 1985), ACM, pp. 179-190.

Digital Library

[13]

FERRANTE, J., OTTENSTEINS K. J., AND WAtt- REN, J. D. The program dependence graph and its use in optimization. A CM Trans. on Programming Languages and Systems 9, 3 (July 1987), 319-349.

Digital Library

[14]

GRAFE, V. G., DAVXDSON, G. S., HOCH, J. E., AND HOLMES, V. P. The epsilon dataflow processor. In Proc. 16th International Symposium on Computer Architecture (1989).

Digital Library

[15]

GaArE, V. G., HocH, J. E., AND DAVlDSON, G. S. Eps'88: Combining the best features of yon Neurnann and dataflow computing. Sanclia Report SAND88-3128, Sandia National Laboratories, Albuquerque, New Mexico, 87185, Jan. 1989.

[16]

NIKHIL, R. S. Id (version 88.0)reference manual. Computation Structures Group Memo 284, Massachusetts Institute of Technology Laboratory for Computer Science, Cambridge, Massachusetts, March 25, 1988.

[17]

NIKHIL, R. S., FENSTERMACHER, P. R., AND HICKS, J. E. Id World reference manual (for LISP machines). Computation structures group memo, Massachusetts Institute of Technology Laboratory for Computer Science, Cambridge, Massachusetts, August 23, 1988.

[18]

OTTENSTgIN, K. J. Data-Flow Graphs as an Intermediate Program Form. PhD thesis, Purdue University, Jan. 1978. Available through University Microfilms, Ann Arbor, MI.

Digital Library

[19]

OTTENSTEIN, K. J. Summary of presentation. Tech. Rep. TM-t36, Massachusetts Institute of Technology Laboratory for Computer Science, June 1979. (Report on the Second Workshop on Data Flow Computer and Program Organization, M.I.T., July 1978).

[20]

OTTENSTEIN, K. J., AND ELLCEY, S. J. Experience compiling Fortran to program dependence graphs. Tech. rep., Los Alamos National Laboratory, 1989. In progress.

[21]

PADUA, D. A., AND WOLFE, M. J. Advanced compiler optimizations for supercomputers. Communications of the A CM 29, 12 (Dec. 1986), 1184- 1201.

Digital Library

[22]

PAPADOPOULOS, G. M. Implementation of a general-purpose dataflow multiprocessor. Tech. rep., Massachusetts Institute of Technology Laboratory for Computer Science, Cambridge, Massachusetts, Aug. 1988.

[23]

SELKE, R. P. A rewriting semantics for program dependence graphs. In Proceedings of the 16ih Annual ACM Symposium on Principles of Programming Languages (Los Angeles, January 17-19, 1989), ACM, pp. 12-24.

Digital Library

[24]

SUHLER, P. Personal communications.

[25]

TaAUB, K. R. A compiler for the MIT taggedtoken datafiow architecture. Tech. rep., Massachusetts Institute of Technology Laboratory for Computer Science, Cambridge, Massachusetts, Aug. 1986.

Digital Library

[26]

VEE:N, A. H. Reconciling data flow machines and conventional languages. In Proc. Conf. on Analysing Problem Classes and Programming for Parallel Computing (Nurnberg, 1981), W. Handler, Ed., no. 111 in LNCS, Springer-Verlag, pp. 127- 140.

Digital Library

[27]

VEEN, A. H. The Misconstrued Semicolon: Reconciling Imperative Languages and Daiaflow Machines, vol. CWI Tract 26. Centrum voor Wiskunde en Informatica, P.O. Box 4079, 1009 AB Amsterdam, The Netherlands, 1986.

Digital Library

Cited By

Yao PZhou JXiao XShi QWu RZhang C(2024)Falcon: A Fused Approach to Path-Sensitive Sparse Data Dependence AnalysisProceedings of the ACM on Programming Languages10.1145/36564008:PLDI(567-592)Online publication date: 20-Jun-2024
https://doi.org/10.1145/3656400
Campos Ferreira Guimarães BQuintão Pereira FVerbrugge CLhoták OShen X(2023)Lazy Evaluation for the Lazy: Automatically Transforming Call-by-Value into Call-by-NeedProceedings of the 32nd ACM SIGPLAN International Conference on Compiler Construction10.1145/3578360.3580270(239-249)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3578360.3580270
Herklotz YDemange DBlazy SKrebbers RTraytel DPientka BZdancewic S(2023)Mechanised Semantics for Gated Static Single AssignmentProceedings of the 12th ACM SIGPLAN International Conference on Certified Programs and Proofs10.1145/3573105.3575681(182-196)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3573105.3575681
Show More Cited By

Index Terms

The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages
1. Software and its engineering
  1. Software creation and management
    1. Designing software
      1. Software implementation planning
        Software design techniques
    2. Software development process management
  2. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
        Control structures
      2. Language types
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs

Recommendations

The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages

The Program Dependence Web (PDW) is a program representation that can be directly interpreted using control-, data-, or demand-driven models of execution. A PDW combines a single-assignment version of the program with explicit operators that manage the ...
Intrinsically-typed definitional interpreters for imperative languages

A definitional interpreter defines the semantics of an object language in terms of the (well-known) semantics of a host language, enabling understanding and validation of the semantics through execution. Combining a definitional interpreter with a ...
Demand-driven pointer analysis

Known algorithms for pointer analysis are “global” in the sense that they perform an exhaustive analysis of a program or program component. In this paper we introduce a demand-driven approach for pointer analysis. Specifically, we describe a demand-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '90: Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation

June 1990

351 pages

ISBN:0897913647

DOI:10.1145/93542

Chairman:
Bernard N. Fischer

ACM SIGPLAN Notices Volume 25, Issue 6
Jun. 1990
343 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/93548
Editor:
Marina Chen
Issue’s Table of Contents

Copyright © 1990 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]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

182
Total Citations
View Citations
2,060
Total Downloads

Downloads (Last 12 months)252
Downloads (Last 6 weeks)28

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yao PZhou JXiao XShi QWu RZhang C(2024)Falcon: A Fused Approach to Path-Sensitive Sparse Data Dependence AnalysisProceedings of the ACM on Programming Languages10.1145/36564008:PLDI(567-592)Online publication date: 20-Jun-2024
https://doi.org/10.1145/3656400
Campos Ferreira Guimarães BQuintão Pereira FVerbrugge CLhoták OShen X(2023)Lazy Evaluation for the Lazy: Automatically Transforming Call-by-Value into Call-by-NeedProceedings of the 32nd ACM SIGPLAN International Conference on Compiler Construction10.1145/3578360.3580270(239-249)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3578360.3580270
Herklotz YDemange DBlazy SKrebbers RTraytel DPientka BZdancewic S(2023)Mechanised Semantics for Gated Static Single AssignmentProceedings of the 12th ACM SIGPLAN International Conference on Certified Programs and Proofs10.1145/3573105.3575681(182-196)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3573105.3575681
Hussein SRayadurgam SMcCamant SSharma VHeimdahl MGnesi SPlat NHartmanns ASchaefer I(2022)Counterexample-guided inductive repair of reactive contractsProceedings of the IEEE/ACM 10th International Conference on Formal Methods in Software Engineering10.1145/3524482.3527650(46-57)Online publication date: 18-May-2022
https://dl.acm.org/doi/10.1145/3524482.3527650
Elakhras AGuerrieri AJosipovic LIenne P(2022)Unleashing Parallelism in Elastic Circuits with Faster Token Delivery2022 32nd International Conference on Field-Programmable Logic and Applications (FPL)10.1109/FPL57034.2022.00046(253-261)Online publication date: Aug-2022
https://doi.org/10.1109/FPL57034.2022.00046
Rosemann JMoll SHack S(2021)An abstract interpretation for SPMD divergence on reducible control flow graphsProceedings of the ACM on Programming Languages10.1145/34343125:POPL(1-31)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434312
Kucuk YHenderson TPodgurski A(2021)Improving Fault Localization by Integrating Value and Predicate Based Causal Inference Techniques2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)10.1109/ICSE43902.2021.00066(649-660)Online publication date: May-2021
https://doi.org/10.1109/ICSE43902.2021.00066
Sharma VHussein SWhalen MMcCamant SVisser WDevanbu PCohen MZimmermann T(2020)Java Ranger: statically summarizing regions for efficient symbolic execution of JavaProceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3368089.3409734(123-134)Online publication date: 8-Nov-2020
https://dl.acm.org/doi/10.1145/3368089.3409734
Kamkin AKhoroshilov AKotsynyak APutro P(2020)Deductive Binary Code Verification Against Source-Code-Level SpecificationsTests and Proofs10.1007/978-3-030-50995-8_3(43-58)Online publication date: 20-Jun-2020
https://doi.org/10.1007/978-3-030-50995-8_3
Wronski BGarcia-Dorado IErnst MKelly DKrainin MLiang CLevoy MMilanfar P(2019)Handheld multi-frame super-resolutionACM Transactions on Graphics10.1145/3306346.332302438:4(1-18)Online publication date: 12-Jul-2019
https://dl.acm.org/doi/10.1145/3306346.3323024
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

Figures

Tables

Media

View Table of Conten