A new algorithm for semantics-based program integration
Wuu Yang, Thomas Reps, Susan B. Horwitz · Minds at UW (University of Wisconsin) · 1990
Programmers frequently face the problem of integrating several variants of a base program. Semantics-based program integration is a technique that attempts to create an integrated program that incorporates the changed computations of the variants as well as the computations of the base program that are preserved in all variants. Horwitz, Prins, and Reps were the first to address the problem of semantics-based program integration. They presented an integration algorithm that creates the integrated program by merging certain program slices of the variants. Our study provides semantic foundations for their approach: we show that the integrated program produced by their algorithm includes all required computations. We also develop a new program-integration algorithm with the same semantic properties. In addition, the new integration algorithm has two significant characteristics: (1) it is extendible in that it can incorporate any techniques for detecting program components with equivalent behaviors and (2) it can accommodate semantics-preserving transformations. The new integration algorithm improves on the integration algorithm of Horwitz, Prins, and Reps in that there are classes of program modifications for which their algorithm reports interference while the new integration algorithm produces satisfactory integrated programs. One fundamental problem integration is to detect program components with equivalent behaviors. For this purpose, we devised the Sequence-Congruence Algorithm, which divides program components into equivalence classes by a partitioning scheme. We show that components in the same equivalence classes have equivalent behaviors. The new integration algorithm is actually a family of algorithms, parameterized by the techniques used to detect equivalent components. Any equivalence-detection techniques can be used. Many techniques, such as constant propagation and invariant code movement, can be combined with the Sequence-Congruence Algorithm to detect larger classes of equivalent components. The new integration algorithm is capable of accommodating semantics-preserving transformations. It allows different states of computations to be modified independently in different variants as long as the same values are computed in each stage. Due to the use of a technique called limited slicing, these semantics-preserving transformations can be accommodated by the new integration algorithm.