A program integration algorithm that accommodates semantics-preserving transformations

ABSTRACT

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 (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.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: ALLEN, F. E. AND COCKE, J.A. A catalogue of optimizing transformations. In Deszgn and Optimtzation of Compilers, R. Rustin, Ed. Prentice-Hall, Englewood Cliffs, NJ, 1972, pp. 1-30.
• 4: B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
• 5: Karl J. Ottenstein , Robert A. Ballance , Arthur B. MacCabe, The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.257-271, June 1990, White Plains, New York, United States
• 6: V Berzins, On merging software extensions, Acta Informatica, v.23 n.6, p.607-619, Nov. 1986 [doi>10.1007/BF00264309]
• 7: R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75280]
• 8: J. B. Dennis, First version of a data flow procedure language, Programming Symposium, Proceedings Colloque sur la Programmation, p.362-376, April 09-11, 1974
• 9: Peter J. Downey , Ravi Sethi , Robert Endre Tarjan, Variations on the Common Subexpression Problem, Journal of the ACM (JACM), v.27 n.4, p.758-771, Oct. 1980 [doi>10.1145/322217.322228]
• 10: FEATHER, M.S. Detecting interference when merging specification evolutions. Unpublished report, Information Sciences Inst.. Univ. of Southern California, Marina del Rey. CA, 1989.
• 11: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 12: HOPCROFT, j.E. An n log n algorithm for minimizing the states of a finite automaton. In The Theory of Machines and Computations, 1971, pp. 189-196.
• 13: Susan Horwitz , Jan Prins , Thomas Reps, Integrating noninterfering versions of programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.345-387, July 1989 [doi>10.1145/65979.65980]
• 14: Susan Horwitz , Thomas Reps, Efficient comparison of program slices, Acta Informatica, v.28 n.9, p.713-732, Nov. 1991
• 15: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• 16: A. Lakhotia , L. Sterling, Composing recursive logic programs with clausal join, New Generation Computing, v.6 n.2-3, p.211-225, March-April 1988 [doi>10.1007/BF03037138]
• 17: David B. Loveman, Program Improvement by Source-to-Source Transformation, Journal of the ACM (JACM), v.24 n.1, p.121-145, Jan. 1977 [doi>10.1145/321992.322000]
• 18: Greg Nelson , Derek C. Oppen, Fast Decision Procedures Based on Congruence Closure, Journal of the ACM (JACM), v.27 n.2, p.356-364, April 1980 [doi>10.1145/322186.322198]
• 19: Karl J. Ottenstein , Linda M. Ottenstein, The program dependence graph in a software development environment, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.177-184, April 1984
• 20: RAMALINGAM, G. Personal commumcabon 1989
• 21: RAMALINGAM, G. AND REPS, T. Semantics of program representation graphs. Tech Rep. 900, Dept. of Computer Sciences, Univ. of Wisconsin, Madison, Dec. 1989.
• 22: REPS, T. AND YANG, W. The semantics of program shcing. Tech. Rep. 777, Dept. of Computer Sciences, Univ. of Wisconsin, Madison, June, 1988
• 23: Thomas W. Reps , Wuu Yang, The Semantics of Program Slicing and Program Integration, Proceedings of the International Joint Conference on Theory and Practice of Software Development, Volume 2: Advanced Seminar on Foundations of Innovative Software Development II and Colloquium on Current Issues in Programming Languages, p.360-374, March 13-17, 1989
• 24: Charles Rich, Inspection Methods in Programming: Cliches and Plans, Massachusetts Institute of Technology, Cambridge, MA, 1987
• 25: B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73562]
• 26: WEISER, M. Program slicing. IEEE Trans Soflw. Eng. SE-10, 4 (July, 1984), 352-357.
• 27: YANG, W., HORWlTZ, S., AND REPS, T Detecting program components w~th equivalent behaviors Tech Rep. 840, Dept of Computer Sciences, Umv. of Wisconsin, Madison, Apr. 1989.
• 28: Wuu Yang , Susan Horwitz , Thomas Reps, A program integration algorithm that accommodates semantics-preserving transformations, Proceedings of the fourth ACM SIGSOFT symposium on Software development environments, p.133-143, December 03-05, 1990, Irvine, California, United States
• 29: Wuu Yang , Thomas Reps , Susan Horwitz, A new algorithm for semantics-based program integration, 1990

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Restructuring, reverse engineering, and reengineering

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Programmer workbench**
      D.2.3 Coding Tools and Techniques
          Subjects: Program editors
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Version control; Enhancement**
      D.2.9 Management
          Subjects: Software configuration management
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Interpreters; Optimization; Compilers

General Terms:
Algorithms, Design

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