Semantics-preserving procedure extraction

ABSTRACT

Procedure extraction is an important program transformation that can be used to make programs easier to understand and maintain, to facilitate code reuse, and to convert “monolithic” code to modular or object-oriented code. Procedure extraction involves the following steps: The statements to be extracted are identified (by the programmer or by a programming tool). If the statements are not contiguous, they are moved together so that they form a sequence that can be extracted into a procedure, and so that the semantics of the original code is preserved. The statements are extracted into a new procedure, and are replaced with an appropriate call. This paper addresses step 2: in particular, the conditions under which it is possible to move a set of selected statements together so that they become “extractable”, while preserving semantics. Since semantic equivalence is, in general, undecidable, we identify sufficient conditions based on control and data dependences, and define an algorithm that moves the selected statements together when the conditions hold. We also include an outline of a proof that our algorithm is semantics-preserving. While there has been considerable previous work on procedure extraction, we believe that this is the first paper to provide an algorithm for semantics-preserving procedures extraction given an arbitrary set of selected statements in an arbitrary control-flow graph.

REFERENCES

• ABS94: Todd M. Austin , Scott E. Breach , Gurindar S. Sohi, Efficient detection of all pointer and array access errors, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.290-301, June 20-24, 1994, Orlando, Florida, United States
• And94: L.O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994. (DIKU report 94/19).
• BD77: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• BDFH97: J. A. Bergstra , T. B. Dinesh , J. Field , J. Heering, Toward a complete transformational toolkit for compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.5, p.639-684, Sept. 1997 [doi>10.1145/265943.265944]
• BG98: Robert W. Bowdidge , William G. Griswold, Supporting the restructuring of data abstractions through manipulation of a program visualization, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.2, p.109-157, April 1998 [doi>10.1145/279310.279312]
• BH93: Samuel Bates , Susan Horwitz, Incremental program testing using program dependence graphs, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.384-396, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158694]
• CLZ86: Ron Cytron , Andy Lowry , F. Kenneth Zadeck, Code motion of control structures in high-level languages, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.70-85, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512651]
• CY79: L.L. Constantine and E. Yourdon. Structured Design. Prentice-Hall, Englewood Cliffs, New Jersey, 1979.
• Fea82: Martin S. Feather, A System for Assisting Program Transformation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.1-20, Jan. 1982 [doi>10.1145/357153.357154]
• FOW87: 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]
• GN93: William G. Griswold , David Notkin, Automated assistance for program restructuring, ACM Transactions on Software Engineering and Methodology (TOSEM), v.2 n.3, p.228-269, July 1993 [doi>10.1145/152388.152389]
• KH99: R. Komondoor and S. Horwitz. Semanticspreserving procedure extraction. Technical Report TR-1407, Computer Sciences, University of Wisconsin-Madison, 1999.
• KKP+81: 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]
• LD98: A. Lakhotia and J-C. Deprez. Restructuring programs by tucking statements into functions. Information and Software Technology, 40(11- 12):677-689, November 1998.
• LMW79: Richard C. Linger , Bernard I. Witt , H. D. Mills, Structured Programming; Theory and Practice the Systems Programming Series, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• LRZ93: William Landi , Barbara G. Ryder , Sean Zhang, Interprocedural modification side effect analysis with pointer aliasing, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.56-67, June 21-25, 1993, Albuquerque, New Mexico, United States
• LS86: S. Letovski and E. Soloway. Delocalized plans and program comprehension. IEEE Software, pages 198-204, May 1986.
• LV97: Filippo Lanubile , Giuseppe Visaggio, Extracting Reusable Functions by Flow Graph-Based Program Slicing, IEEE Transactions on Software Engineering, v.23 n.4, p.246-259, April 1997 [doi>10.1109/32.588543]
• Pap86: Christos Papadimitriou, The theory of database concurrency control, Computer Science Press, Inc., New York, NY, 1986
• Par72: D. L. Parnas, On the criteria to be used in decomposing systems into modules, Communications of the ACM, v.15 n.12, p.1053-1058, Dec. 1972 [doi>10.1145/361598.361623]
• PP96: Alberto Pettorossi , Maurizio Proietti, Rules and strategies for transforming functional and logic programs, ACM Computing Surveys (CSUR), v.28 n.2, p.360-414, June 1996 [doi>10.1145/234528.234529]
• Ram88: Lyle Ramshaw, Eliminating go to's while preserving program structure, Journal of the ACM (JACM), v.35 n.4, p.893-920, Oct. 1988 [doi>10.1145/48014.48021]
• RSW96: Spencer Rugaber , Kurt Stirewalt , Linda M. Wills, Understanding interleaved code, Reverse engineering, Kluwer Academic Publishers, Norwell, MA, 1996
• SJ87: H.M. Sneed and G. Jandrasics. Software recycling. In Proc. Conf. Software Maintenance, pages 82-90, 1987.
• WFW+94: Robert P. Wilson , Robert S. French , Christopher S. Wilson , Saman P. Amarasinghe , Jennifer M. Anderson , Steve W. K. Tjiang , Shih-Wei Liao , Chau-Wen Tseng , Mary W. Hall , Monica S. Lam , John L. Hennessy, SUIF: an infrastructure for research on parallelizing and optimizing compilers, ACM SIGPLAN Notices, v.29 n.12, p.31-37, Dec. 1994 [doi>10.1145/193209.193217]
• WL95: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States
• WM92: S. Wu and U. Manber. Agrep- a fast approximate pattern-matching tool. In Usenix Winter 1992 Technical Conference, pages 153-162, January 1992.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

General Terms:
Algorithms, Design, Languages