Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-66644f4456-2xp4c Total loading time: 0 Render date: 2025-02-13T03:17:17.176Z Has data issue: true hasContentIssue false

10 - Semantics of program representation graphs

Published online by Cambridge University Press:  06 August 2010

By
G. Ramalingam  and
Thomas Reps
Edited by
Yves Bertot ,
Gérard Huet ,
Jean-Jacques Lévy  and
Gordon Plotkin
G. Ramalingam
Affiliation:
Microsoft Research India; Bangalore, India
Thomas Reps
Affiliation:
University of Wisconsin; Madison, WI; USA
Yves Bertot
Affiliation:
INRIA-Sophia Antipolis, France
Gérard Huet
Affiliation:
Institut National de Recherche en Informatique et en Automatique (INRIA), Rocquencourt
Jean-Jacques Lévy
Affiliation:
Institut National de Recherche en Informatique et en Automatique (INRIA), Rocquencourt
Gordon Plotkin
Affiliation:
University of Edinburgh
Get access

Summary

Abstract

Program representation graphs (PRGs) are an intermediate representation for programs. (They are closely related to program dependence graphs.) In this paper, we develop a mathematical semantics for PRGs that, inspired by Kahn's semantics for a parallel programming language, interprets PRGs as dataflow graphs. We also study the relationship between this semantics and the standard operational semantics of programs. We show that (i) the semantics of PRGs is more defined than the standard operational semantics, and (ii) for states on which a program terminates normally, the PRG semantics is identical to the standard operational semantics.

Introduction

In this paper, we develop a mathematical semantics for program representation graphs (PRGs) and study its relationship to a standard (operational) semantics of programs. Program representation graphs are an intermediate representation of programs, introduced by Yang et al. in an algorithm for detecting program components that exhibit identical execution behaviors. They combine features of static-single-assignment forms (SSA forms) and program dependence graphs (PDGs) (See Fig. 10.1 for an example program and its PRG.) PRGs have also been used in an algorithm for merging program variants.

Program dependence graphs have been used as an intermediate program representation in various applications such as vectorization, parallelization, and merging program variants. A number of variants of the PDG have been used as the basis for efficient program analysis by optimizing compilers as well as other tools.

Type
Chapter
Information
From Semantics to Computer Science
Essays in Honour of Gilles Kahn
 , pp. 205 - 234
Publisher: Cambridge University Press
Print publication year: 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]A., Aho, R., Sethi and J., Ullman. Compilers: Principles, Techniques and Tools. Addison-Wesley, 1985.Google Scholar
[2]B., Alpern, M., Wegman, and F., Zadeck. Detecting equality of variables in programs. In POPL, pp. 1–11, 1988.Google Scholar
[3]T., Amtoft. Slicing for modern program structures: a theory for eliminating irrelevant loops. Information Processing Letters, 106:45–51, 2008.Google Scholar
[4]R., Cartwright and M., Felleisen. The semantics of program dependence. In PLDI, pp. 13–27, 1989.Google Scholar
[5]R., Cytron, J., Ferrante, B., Rosen, M., Wegman and F., Zadeck. An efficient method of computing static single assignment form. In POPL, pp. 25–35, 1989.Google Scholar
[6]J., Ferrante, K., Ottenstein and J., Warren. The program dependence graph and its use in optimization. TOPLAS, 3(9):319–349, 1987.Google Scholar
[7]J., Field. A simple rewriting semantics for realistic imperative programs and its application to program analysis. In PEPM, pp. 98–107, 1992.Google Scholar
[8]R., Giacobazzi and I., Mastroeni. Non-standard semantics for program slicing. HOSC, 16(4):297–339, 2003.Google Scholar
[9]J., Hatcliff, J., Corbett, M., Dwyer, S., Sokolowski and H., Zheng. A formal study of slicing for multi-threaded programs with JVM concurrency primitives. In SAS, 1999.Google Scholar
[10]S., Horwitz, J., Prins and T., Reps. On the adequacy of program dependence graphs for representing programs. In POPL, pp. 146–157, 1988.Google Scholar
[11]S., Horwitz, J., Prins and T., Reps. Integrating non-interfering versions of programs. TOPLAS, 11(3):345–387, 1989.Google Scholar
[12]G., Kahn. The semantics of simple language for parallel programming. In IFIP Congress, pp. 471–475, 1974.Google Scholar
[13]D., Kuck, R., Kuhn, B., Leasure, D., Padua and M., Wolfe. Dependence graphs and compiler optimizations. In POPL, pp. 207–218, 1981.Google Scholar
[14]D., Kuck, Y., Muraoka, and S., Chen. On the number of operations simultaneously executable in FORTRAN-like programs and their resulting speed-up. IEEE Trans. on Computers, C-21(12):1293–1310, 1972.Google Scholar
[15]K., Ottenstein, R., Ballance and A., MacCabe. The program dependence web: A representation supporting control-, data-, and demand-driven interpretation of imperative languages. In PLDI, pp. 257–271, 1990.Google Scholar
[16]K., Ottenstein and L., Ottenstein. The program dependence graph in a software development environment. In Softw. Eng. Symp. on Practical Softw. Dev. Environments, pp. 177–184, 1984.Google Scholar
[17]K., Pingali, M., Beck, R., Johnson, M., Moudgill, and P., Stodghill. Dependence flow graphs: An algebraic approach to program dependencies. In Advances in Languages and Compilers for Parallel Processing, pp. 445–467. M.I.T. Press, 1991.Google Scholar
[18]G., Ramalingam and T., Reps. Appendix A: Proofs. “www.cs.wisc.edu/wpis/papers/soprgs08-proofs.pdf”.
[19]G., Ramalingam and T., Reps. Semantics of program representation graphs. TR-900, Computer Science Department, University of Wisconsin, Madison, WI, 1989.
[20]T., Reps and W., Yang. The semantics of program slicing and program integration. In CCIPL, pp. 360–374, 1989.Google Scholar
[21]B., Rosen, M., Wegman, and F., Zadeck. Global value numbers and redundant computations. In POPL, pp. 12–27, 1988.Google Scholar
[22]R., Selke. A rewriting semantics for program dependence graphs. In POPL, pp. 12–24, 1989.Google Scholar
[23]R., Shapiro and H., Saint. The representation of algorithms. Tech. Rep. CA-7002-1432, Massachusetts Computer Associates, 1970.
[24]D., Weise, R., Crew, M., Ernst and B., Steensgaard. Value dependence graphs: Representation without taxation. In POPL, pp. 297–310, 1994.Google Scholar
[25]M., Weiser. Program slicing. In ICSE, pp. 439–449, 1981.Google Scholar
[26]W., Yang. A New Algorithm for Semantics-Based Program Integration. PhD thesis, Computer Science Department, University of Wisconsin, Madison, WI, Aug. 1990.
[27]W., Yang, S., Horwitz and T., Reps. Detecting program components with equivalent behaviors. TR-840, Computer Science Department, University of Wisconsin, Madison, WI, Apr. 1989.Google Scholar
[28]W., Yang, S., Horwitz and T., Reps. A program integration algorithm that accommodates semantics-preserving transformations. TOSEM, 1(3):310–354, July 1992.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×