The Multi-Procedure Equivalence Theorem
File(s)
Date
1989Author
Binkley, David
Horwitz, Susan
Reps, Thomas
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Metadata
Show full item recordAbstract
Program dependence graphs have been used in program optimization, vectorization, and parallelization. They have also been used as the internal representation for programs in programming environments, as well as for automatically merging program variants.
This paper concerns the question of whether program dependence graphs are ?adequate? as a program representation. Previous results on the adequacy of program dependence graphs have been limited to a language without procedures and procedure calls. Our main result is a theorem that extends previous results to a language with procedures and procedure calls. The theorem shows that if the program dependence graphs of two programs are isomorphic then the programs are strongly equivalent.
Permanent Link
http://digital.library.wisc.edu/1793/59210Citation
TR890