Computer Sciences Dept.

Detecting Program Components With Equivalent Behaviors

Wuu Yang, Susan Horwitz and Thomas Reps

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.

Download this report (PDF)

Return to tech report index

Computer Science | UW Home