Incremental compilation of optimized code

ABSTRACT

Although optimizing compilers have successfully been used to reduce the size and running times of compiled programs, present incremental compilers only support the incremental update of unoptimized code. In this work, we extend the notion of incremental compilation to include optimized code. Techniques to incrementally compile locally optimized code, given intermediate code modifications are developed using a program representation based on flow graphs and dags. A model is designed to represent both unoptimized and optimized code and to maintain an optimizing history. Changes to the optimized code which either destroy optimizations or create conditions for further optimizations are incorporated into the model and the optimized code without recompiling unaffected optimizations.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: 2. L. V. Atkinson, J. J. McGregor, and S. D. North, "Context-sensitive editing as an approach to incremental compilation," The Computer Journal 24(3). pp. 222- 229 (1981).
• 3: Jay Earley , Paul Caizergues, A method for incrementally compiling languages with nested statement structure, Communications of the ACM, v.15 n.12, p.1040-1044, Dec. 1972 [doi>10.1145/361598.361614]
• 4: 4. Jeanne Ferrante, K. J. Ottenstein, and J. D. Warren, "The program dependence graph and its use in optimization," RC 10208 (#44947) (August 1983).
• 5: Carlo Ghezzi , Dino Mandrioli, Incremental Parsing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.58-70, July 1979 [doi>10.1145/357062.357066]
• 6: Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
• 7: John Hennessy, Symbolic Debugging of Optimized Code, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.323-344, July 1982 [doi>10.1145/357172.357173]
• 8: 8. Harry Katzan. Jr., "Batch, conversational, and incremental compilers," Proceedings AFIPS Spring Joint Computer Conference 34, pp. 47-56 (1969).
• 9: 9. Raul Medina-Mora and Peter H. Feiler, "An incremental programming environment." IEEE Transactions on Software Engineering SE-7(5), pp. 472-481 (Sept. 1981).
• 10: Karl J. Ottenstein , Linda M. Ottenstein, High-level debugging assistance via optimizing compiler technology, Proceedings of the symposium on High-level debugging, March 20-23, 1983, Pacific Grove, California
• 11: Barbara G. Ryder, Incremental data flow analysis, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.167-176, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567084]
• 12: 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]
• 13: 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
• 14: Ron Tischler , Robin Schaufler , Charlotte Payne, Static analysis of programs as an aid to debugging, Proceedings of the symposium on High-level debugging, March 20-23, 1983, Pacific Grove, California
• 15: 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
• 16: Polle T. Zellweger, An interactive high-level debugger for control-flow optimized programs, Proceedings of the symposium on High-level debugging, March 20-23, 1983, Pacific Grove, California

INDEX TERMS

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

General Terms:
Algorithms, Design, Languages, Performance, Theory