Paper Info
Title
The semantics of program dependence
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.
Year
DOI
Venue
1989
10.1145/74818.74820
Special Interest Group on Programming Languages
Keywords
Field
DocType
data flow,programming language
Procedural programming,Graph,Program Dependence Graph,Operational semantics,Programming language,Computer science,Generalization,Denotational semantics,Theoretical computer science,Compiler,Semantics
Conference
Volume
Issue
ISSN
24
7
0362-1340
ISBN
Citations 
PageRank 
0-89791-306-X
73
10.67
References 
Authors
10
2
Name
Order
Citations
PageRank
Robert Cartwright152967.27
Matthias Felleisen23001272.57