Detecting Program Components With Equivalent Behaviors

File(s):

Author(s): Yang, Wuu; Horwitz, Susan; Reps, Thomas
Publisher: University of Wisconsin-Madison Department of Computer Sciences
Date: Mar 15, 2012
Abstract: 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/59110
Export: Export to RefWorks