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 incorporates 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 only applies to programs written in a restricted language --- in particular, the algorithm does not handle programs with procedures. This paper describes a generalization of the Horwitz-Prins-Reps algorithm that handles programs that consist of multiple (and possibly mutually recursive) procedures.

We show that two straightforward generalizations of the Horwitz-Prins-Reps algorithm yield unsatisfactory results. The key issue in developing a satisfactory algorithm is how to take into account different calling contexts when determining what has changed in the variants A and B. Our solution to this problem involves identifying two different kinds of affected components of A and B: those affected regardless of how the procedure is called, and those affected by a changed or new calling context. The algorithm makes use of interprocedural program slicing to identify these components, as well as components in Base, A, and B with the same behavior.

CR 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.3 [Programming Languages]: Language Constructs -- control structures, procedures, functions, and subroutines; D.3.4 [Programming Languages]: Processors -- compilers, interpreters, optimization; E.1 [Data Structures] graphs.

General Terms: Algorithms, Design, Theory

Additional Key Words and Phrases: Control dependence, data dependence, data-flow analysis, flow-insensitive summary information, program dependence graph, program slicing, semantics-based program integration

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