Detecting Program Components With Equivalent Behaviors

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.