Detecting Program Components With Equivalent Behaviors
File(s)
Date
1989Author
Yang, Wuu
Horwitz, Susan
Reps, Thomas
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Metadata
Show full item recordAbstract
The execution behavior of a program component is defined as the sequence of values produced at the component during program execution. This paper presents an efficient algorithm for detecting program components ? in one or more program ? that exhibit identical execution behaviors. The algorithm operates on a new graph representation for programs that combines features of static-single-
assignment forms and program dependence graphs. The result provides insight into the relationship between execution behaviors and (control and flow) dependence in the program. The algorithm, called the Sequence-Congruence Algorithm, is applicable to programs written in a language that includes scalar variables and constants, assignment statements, conditional statements, and while-loops. The Sequence-Congruence Algorithm can be used as the basis for an algorithm for integrating program variants.
Permanent Link
http://digital.library.wisc.edu/1793/59110Citation
TR840