Program integration for languages with procedure calls

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 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 applied to programs written in a restricted language—in particular, the algorithm does not handle programs with procedures. This article 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.

REFERENCES

• 1: ~BALL~ T., HORWITZ, S, AND REPS, T. 1990. Correctness of an algorithm for reconstituting a ~program from a depend~nce graph. TR-947, Computer Sciences Dept., Univ. of Wisconsin, ~Madison, Wisc.
• 2: David Wendell Binkley, Multi-procedure program integration, University of Wisconsin at Madison, Madison, WI, 1992
• 3: ~BINKLEY, D., HORWITZ, S.~ AND REPS, T. 1995. The theory of multi-procedure integration. Tech. ~Rep., Computer Sciences Dept., Univ of Wisconsin, Madison, Wisc. In preparation.
• 4: K. D. Cooper , K. Kennedy, Interprocedural side-effect analysis in linear time, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.57-66, June 20-24, 1988, Atlanta, Georgia, United States
• 5: ~DONZEAU-GOUGE, V., HUET, G., KAH~, G, ANn LANG, B. 1984. Programming environments ~based on structured editors: The MENTOR experience. In Interactwe Programming Environ- ~Ments, D. Barstow, E. Sandewall, and H. Shrobe, Eds. McGraw-Hfil, New York, 128 140.
• 6: 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]
• 7: 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]
• 8: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 9: 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]
• 10: William Landi , Barbara G. Ryder, Pointer-induced aliasing: a problem taxonomy, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.93-103, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99599]
• 11: ~NOTKIN, D., ELLISON, R. J., STAUDT, B. J., KAISER, G. E., KANT, E., HABERMAN, A. N., AMBRIOLA, V., ~AND MONTANGERO, C. 1985. Special issue on the GANDALF project. J. Syst. Softw. 5, 2 ~(May).
• 12: 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
• 13: ~REps, T. 1989. Demonstration of a prototype tool for program integration. TR-819, Computer ~Sciences Dept., Univ. of Wisconsin, Madison, Wisc.
• 14: ~REPS, T. 1993. The Wisconsin program-integration system reference manual: Release 2.0. ~Unpublished Report, Computer Sciences Dept., Univ. of Wisconsin, Madison, Wisc.
• 15: T. Reps , T. Bricker, Illustrating interference in interfering versions of programs, Proceedings of the 2nd International Workshop on Software configuration management, p.46-55, October 24-27, 1989, Princeton, New Jersey, United States
• 16: Thomas W. Reps , Tim Teitelbaum, The synthesizer generator: a system for constructing language-based editors, Springer-Verlag New York, Inc., New York, NY, 1989
• 17: ~REPS, T. AND YANa, W. 1988. The semantics of program slicing. TR-777, Computer Sciences ~Dept., Univ. of Wisconsin, Madison, Wisc.
• 18: ~REPS, T., SAGIV., M., AND HORWITZ, S. 1994. Interprocedural datafiow analysis via graph ~reachability. Tech. Rep. TR 94-14, Datalogisk Institut, Univ. of Coopenhagen, Denmark.
• 19: ~RICE, H.G. 1953. Classes of recursively enumerable sets and their decision problems. Trans. ~AMS 89, 25 59. As cited in Hopcroft and Ullman, Introduction to Automata Theory, Lan- ~guages, and Computation. Addison-Wesley, Reading, Mass. 1979.
• 20: ~SHARIR, M. AND PNUELI, A. 1981. Two approaches to interprocedural data flow analysis. In ~Program Flow Analysts: Theory and Applications, S. S. Muchnick and N. D. Jones, Eds. ~Prentice-Hall, Englewood Cliffs, N.J.
• 21: ~WEISER, M. 1984. Program slicing. IEEE Trans. Softw. Eng. SE-IO, 4 (July), 352-357.
• 22: 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: Version control

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: Restructuring, reverse engineering, and reengineering
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Design, Languages, Theory

Keywords:
control dependence, data dependence, data-flow analysis, flow-insensitive summary information, program dependence graph, program slicing, semantics-based program integration