Given a program Base and two variants, A and B, each created by modifying separate copies of Base, the goal of program integration is to determine whether the modifications interfere, and if they do not, to create an integrated program that includes both sets of changes as well as the portions of Base preserved in both variants. Text-based integration techniques, such as the one used by the UNIX diff3 utility, are obviously unsatisfactory because one has no guarantees about how the execution behavior of the integrated program relates to the behaviors of Base, A, and B. The first program-integration algorithm to provide such guarantees was developed by Horwitz, Prins, and Reps. However, a limitation of that algorithm is that it incorporates no notion of semantics-preserving transformations. This limitation causes the algorithm to be overly conservative in its definition of interference. For example, if one variant changes the way a computation is performed (without changing the values computed) while the other variant adds code that uses the result of the computation, the algorithm would classify those changes as interfering. This paper describes a new integration algorithm that is able to accommodate semantics-preserving transformations.

Categories and Subject Descriptors: D.2.2 [Software Engineering]: Tools and Techniques -- programmer workbench; D.2.3 [Software Engineering]: Coding -- program editors; D.2.6 [Software Engineering]: Programming Environments; D.2.7 [Software Engineering]: Distribution and Maintenance -- enhancement, restructuring, version control; D.2.9 [Software Engineering]: Management -- programming teams, software configuration management; D.3.4 [Programming Languages]: Processors -- compilers, interpreters, optimization; E.1 [Data Structures] graphs

General Terms: Algorithms, Design

Additional Key Words and Phrases: coarsest partition, control dependence, data dependence, data-flow analysis, flow dependence, program dependence graph, program integration, program representation graph, static-single-assignment form

(Click here to access the paper: PostScript, PDF.)