Direct update of data flow representations for a meaning-preserving program restructuring tool

ABSTRACT

Automated assistance for meaning-preserving global restructuring is an approach for helping software engineers improve the structure of programs, thus lowering the costs of maintenance. The consturction of a restructuing tool encounters many conflicting goals---such as simplicity. extensibility, and good performance---that cannot be met without some compromise. In particular, the current technique for assisting restructuring uses a costly program representation---a Program Dependence Graph (PDG) with alias information---that is not practical to recompute from scratch after each restructuring transformation. There are at least two possible solutions. A commonly suggested approach for efficiently updating data flow representations is to use a generic incremental algorithm that does not make use of the special nature of the restructuring. This approach is general, but it does not yet handle aliasing fully. By taking advantage of the special nature of the restructuring transformations it is possible to implement a more efficient update than generic update that also handles aliasing. The idea is to implement direct updates to the PDG that are analogous to the changes on the program text. The downsides to direct update are that it is application-specific, applies only to semantically restricted applications like restructuring, and may be more complex. The choice between the two techniques requires an understanding of the current and future needs of the tool's users.This paper describes the direct approach of updating the PDG and related representations for restructuring, provides techniques for managing its complexity, critiques its advantages and shortcomings relative to generic incremental update, and presents performance results.

REFERENCES

• Aho et al. 86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• Allen & Cocke 72: F. E. Alten and J. Cocke. A catalogue of optimizing transformations. In R. Rustin, editor, Design and Optimization of Compilers. Prentice-Hall, Englewood Cliffs, NJ, 1972.
• Allen 70: Frances E. Allen, Control flow analysis, Proceedings of a symposium on Compiler optimization, p.1-19, July 27-28, 1970, Urbana-Champaign, Illinois
• Belady & Lehman 71: M. M. Lehman , L. A. Belady, Program evolution: processes of software change, Academic Press Professional, Inc., San Diego, CA, 1985
• Belady & Lehman 76: M. M. Lehman , L. A. Belady, Program evolution: processes of software change, Academic Press Professional, Inc., San Diego, CA, 1985
• Burke & Ryder 90: Michael G. Burke , Barbara G. Ryder, A Critical Analysis of Incremental Iterative Data Flow Analysis Algorithms, IEEE Transactions on Software Engineering, v.16 n.7, p.723-728, July 1990 [doi>10.1109/32.56098]
• Burke 90: Michael Burke, An interval-based approach to exhaustive and incremental interprocedural data-flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.341-395, July 1990 [doi>10.1145/78969.78963]
• Cartwright & Felleisen 89: E. Cartwright , M. Felleisen, The semantics of program dependence, ACM SIGPLAN Notices, v.24 n.7, p.13-27, July 1989
• Chase et al. 90: David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.25 n.6, p.296-310, Jun. 1990
• Choi et al. 91: Jong-Deok Choi , Ron Cytron , Jeanne Ferrante, Automatic construction of sparse data flow evaluation graphs, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.55-66, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99594]
• Cytron et al. 88: 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]
• Ferrante et al. 87: 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]
• Griswold & Bowdidge 93: William G. Griswold , Robert W. Bowdidge, Program Restructuring via Design-Level Manipulation, Selected papers from the Workshop on Studies of Software Design, p.127-139, May 17-18, 1993
• Griswold & Notkin 93: 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]
• Griswold 91: W. G. Griswold. Program Restructuring to Aid Software Maintenance. PhD dissertation, University of Washington, Dept. of Computer Science& Engineering, August 1991. Technical Report No. 91-08-04.
• Hoare et al. 87: C. A. R. Hoare , I. J. Hayes , He Jifeng , C. C. Morgan , A. W. Roscoe , J. W. Sanders , I. H. Sorensen , J. M. Spivey , B. A. Sufrin, Laws of programming, Communications of the ACM, v.30 n.8, p.672-686, Aug. 1987 [doi>10.1145/27651.27653]
• Kuck et al. 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]
• Landi & Ryder 92: William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, ACM SIGPLAN Notices, v.27 n.7, p.235-248, July 1992
• Landi et al. 93: William Landi , Barbara G. Ryder , Sean Zhang, Interprocedural modification side effect analysis with pointer aliasing, ACM SIGPLAN Notices, v.28 n.6, p.56-67, June 1993
• Larus & Hilfinger 88: J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.24-31, June 20-24, 1988, Atlanta, Georgia, United States
• Larus 89: James Richard Larus , Paul Hifinger, Restructuring symbolic programs for concurrent execution on multiprocessors, 1989
• Lientz & Swanson 80: Bennett P. Lientz , E. Burton Swanson, Software Maintenance Management, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1980
• Lippe 92: Ernst Lippe , Norbert van Oosterom, Operation-based merging, Proceedings of the fifth ACM SIGSOFT symposium on Software development environments, p.78-87, December 09-11, 1992, Tyson's Corner, Virginia, United States
• Marlowe & Ryder 90: Thomas J. Marlowe , Barbara G. Ryder, An efficient hybrid algorithm for incremental data flow analysis, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.184-196, December 1989, San Francisco, California, United States [doi>10.1145/96709.96728]
• Marlowe & Ryder 91: T. J. Marlowe and B. G. Ryder. Hybrid incremental alias algorithms. In Hawaii International Conference on Systems Sojiware, January 1991.
• Parnas 72: 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]
• Parsons 92: Rebecca Jane Parsons, Semantic program dependence graphs, Rice University, Houston, TX, 1992
• Podgurski & Clarke 90: A. Podgurski , L. A. Clarke, A Formal Model of Program Dependences and its Implications for Software Testing, Debugging, and Maintenance, IEEE Transactions on Software Engineering, v.16 n.9, p.965-979, September 1990 [doi>10.1109/32.58784]
• Pollock & Soffa 89: L. L. Pollock , M. L. Soffa, An Incremental Version of Iterative Data Flow Analysis, IEEE Transactions on Software Engineering, v.15 n.12, p.1537-1549, December 1989 [doi>10.1109/32.58766]
• Ramalingam & Reps 89: G. Ramalingam and T. Reps. Semantics of program representation graphs. Technical Report 900, Computer Sciences Departrnent University of Wisconsirr, Madison WI, December 1989.
• Reps & Teitelbaum 87: Thomas Reps , Tim Teitelbaum, Language processing in program editors, Computer, v.20 n.11, p.29-40, Nov. 1987 [doi>10.1109/MC.1987.1663414]
• Rowe et al. 91: Lawrence A. Rowe , Joseph A. Konstan , Brian C. Smith , Steve Seitz , Chung Liu, The PICASSO applications framework, Proceedings of the 4th annual ACM symposium on User interface software and technology, p.95-105, November 11-13, 1991, Hilton Head, South Carolina, United States [doi>10.1145/120782.120793]
• Ryder et al. 88: B. G. Ryder , T. J. Marlowe , M. C. Paull, Conditions for incremental iteration: examples and counterexamples, Science of Computer Programming, v.11 n.1, p.1-15, Oct. 1988 [doi>10.1016/0167-6423(88)90061-5]
• Ryder et al. 90: Barbara G. Ryder , William Landi , Hemant D. Pande, Profiling an Incremental Data Flow Analysis Algorithm, IEEE Transactions on Software Engineering, v.16 n.2, p.129-140, February 1990 [doi>10.1109/32.44377]
• Selke 90: R. P. Selke. Transforming program dependence graphs. Technical Report TR90-131, Department of Computer Science, Rice University, Houston, Texas, 1990.
• Shivers 88: O. Shivers, Control flow analysis in scheme, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.164-174, June 20-24, 1988, Atlanta, Georgia, United States
• Shivers 91: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• Steele 91: Guy L. Steele, Jr., Common LISP: the language (2nd ed.), Digital Press, Newton, MA, 1990
• Venkatesh 91: G. A. Venkatesh, The semantic approach to program slicing, ACM SIGPLAN Notices, v.26 n.6, p.107-119, June 1991
• Yang 90: Wuu Yang , Thomas Reps , Susan Horwitz, A new algorithm for semantics-based program integration, 1990
• Yang et at. 89: W. Yang, S. Horwitz, and T. Reps. Detecting program components with equivalent behaviors. Technical Report 840, Computer Sciences Department University of Wisconsin, Madison WI, April 1989.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.3 Software Management
          Subjects: Software development

General Terms:
Design, Management, Theory