The Multi-Procedure Equivalence Theorem

Abstract

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.