A Program Integration Algorithm that Accommodates Semantics-Preserving Transformations

Wuu Yang, Susan Horwitz, Thomas Reps

Research output: Contribution to journalArticlepeer-review

38 Scopus citations


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 et al.[13]. 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 1992 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.

Original languageEnglish
Pages (from-to)310-354
Number of pages45
JournalACM Transactions on Software Engineering and Methodology (TOSEM)
Issue number3
StatePublished - 7 Jan 1992


  • coarsest partition
  • control dependence
  • data dependence
  • data-flow analysis
  • flow dependence
  • program dependence graph
  • program integration
  • program representation graph
  • static-single-assignment form

Fingerprint Dive into the research topics of 'A Program Integration Algorithm that Accommodates Semantics-Preserving Transformations'. Together they form a unique fingerprint.

Cite this