Incremental global reoptimization of programs

ABSTRACT

Although optimizing compilers have been quite successful in producing excellent code, two factors that limit their usefulness are the accompanying long compilation times and the lack of good symbolic debuggers for optimized code. One approach to attaining faster recompilations is to reduce the redundant analysis that is performed for optimization in response to edits, and in particulars, small maintenance changes, without affecting the quality of the generated code. Although modular programming with separate compilation aids in eliminating unnecessary recompilation and reoptimization, recent studies have discovered that more efficient code can be generated by collapsing a modular program through procedure inlining. To avoid having to reoptimize the resultant large procedures, this paper presents techniques for incrementally incorporating changes into globally optimized code. An algorithm is given for determining which optimizations are no longer safe after a program change, and for discovering which new optimizations can be performed in order to maintain a high level of optimization. An intermediate representation is incrementally updated to reflect the current optimizations in the program. Analysis is performed in response to changes rather than in preparation for possible changes, so analysis is not wasted if an edit has no far-reaching effects. The techniques developed in this paper have also been exploited to improve on the current techniques for symbolic debugging of optimized code.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: M. P. Bivens , M. L. Soffa, Incremental register reallocation, Software—Practice & Experience, v.20 n.10, p.1015-1047, Oct. 1990 [doi>10.1002/spe.4380201005]
• 3: 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]
• 4: M. D. Carroll , B. G. Ryder, Incremental data flow analysis via dominator and attribute update, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.274-284, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73584]
• 5: Keith D. Cooper , Ken Kennedy , Linda Lorczon, Interprocedural optimization: eliminating unnecessary recompilation, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.58-67, June 25-27, 1986, Palo Alto, California, United States
• 6: Jack W. Davidson , Anne M. Holler, A study of a C function inliner, Software—Practice & Experience, v.18 n.8, p.775-790, August 1988 [doi>10.1002/spe.4380180805]
• 7: Peter H. Feiler , Raul Medina-Mora, An Incremental Programming Environment, Proceedings of the 5th international conference on Software engineering, p.44-53, March 09-12, 1981, San Diego, California, United States
• 8: Ray Ford , Duangkaew Sawamiphakdi, A greedy concurrent approach to incremental code generation, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.165-178, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318634]
• 9: Peter Fritzson, Preliminary experience from the dice system a distributed incremantal compiling environment, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.113-123, April 1984
• 10: HusoN, C. A. An in-line subroutine expander for Parafrase. M.S. Thesis, Tech. Rep. UIUCDCS-R-82-1118, Univ. of Illinois at Urbana-Champaign, Dec. 1982.
• 11: Fahimeh Jalili , Jean H. Gallier, Building friendly parsers, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.196-206, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582175]
• 12: KEABLES, J., ROBERSON, K., AND VON MAYRHAUSER, A. Data fiow analysis and ifs application to software maintenance. In Proceedings of Conference on Software Mointenance (Phoenix, Ariz., Oct. 1988) pp. 335-347.
• 13: 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]
• 14: Lori L. Pollock , Mary Lou Soffa, Incremental compilation of optimized code, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.152-164, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318629]
• 15: Lori L Pollock, An approach to incremental compilation of optimized code, University of Pittsburgh, Pittsburgh, PA, 1986
• 16: L. L. Pollock , M. L. Soffa, High-level debugging with the aid of an incremental optimizer, Proceedings of the Twenty-First Annual Hawaii International Conference on Software Track, p.524-532, January 1988, Kailua-Kona, Hawaii, United States
• 17: 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]
• 18: Thomas Reps , Tim Teitelbaum , Alan Demers, Incremental Context-Dependent Analysis for Language-Based Editors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.449-477, July 1983 [doi>10.1145/2166.357218]
• 19: Stephen Richardson , Mahadevan Ganapathi, Interprocedural analysis vs. procedure integration, Information Processing Letters, v.32 n.3, p.137-142, August 24, 1989 [doi>10.1016/0020-0190(89)90014-8]
• 20: Barbara G. Ryder , Marvin C. Paull, Incremental data-flow analysis algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.1, p.1-50, Jan. 1988 [doi>10.1145/42192.42193]
• 21: Martin Carroll , Barbara G Ryder, An incremental algorithm for software analysis, Proceedings of the second ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.171-179, December 09-11, 1986, Palo Alto, California, United States
• 22: Robert W. Schwanke , Gail E. Kaiser, Smarter recompilation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.627-632, Oct. 1988 [doi>10.1145/48022.214505]
• 23: Mayer D. Schwartz , Norman M. Delisle , Vimal S. Begwani, Incremental compilation in Magpie, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.122-131, June 17-22, 1984, Montreal, Canada
• 24: Walter F. Tichy, Smart recompilation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.273-291, July 1986 [doi>10.1145/5956.5959]
• 25: Frank Kenneth Zadeck, Incremental data flow analysis in a structured program editor, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.132-143, June 17-22, 1984, Montreal, Canada

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Code generation

General Terms:
Algorithms, Languages, Performance

Keywords:
compiler optimization, incremental data flow analysis, incremental reoptimization, optimization dependencies