ABSTRACT
Much of the research in compiler design and optimization has traditionally focused on the effectiveness and efficiency of code optimization. However, the subject of efficiency of the entire compilation process itself (as opposed to the complexity of individual analysis or optimization algorithms) remains a highly complex and less investigated topic. In this paper we present a global approach to extensible and efficient compiler design, which aims at also improving the effectiveness and efficiency of analysis and optimization capabilities. Extensibility in complex compiler systems goes well beyond modularity of design and it needs to be considered from the early stages of the design, especially the design of the Intermediate Representation (IR). One of the primary barriers to compiler pass extensibility and modularity is interference between passes caused by transformations that invalidate existing analysis information. In this paper we also present a callback system which is provided to automatically track changes to the compiler's internal representation (IR) allowing full pass reordering and an easy-to-use interface for developing lazy update incremental analysis passes. We present a new algorithm for incremental interprocedural data flow analysis and demonstrate the benefits of our design framework and our prototype compiler system. It is shown that compilation time for multiple data flow analysis algorithms can be cut in half by incrementally updating data flow analysis. Our quantitative performance analysis is based on well-known benchmarks instead of random graphs like previous works. For smaller optimizations, order of magnitude improvements have been demonstrated. Our approach also simplifies design and implementation and hides many of the intricacies of a compiler's internal structures from the developer.
- Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison Wesley, 1986. Google ScholarDigital Library
- M. G. Burke and B. G. Ryder. A critical analysis of incremental iterative data flow analysis algorithms. IEEE Transactions on Software Engineering, 16(7):723--728, 1990. Google ScholarDigital Library
- Alan Carle and Lori Pollock. Modular specification of incremental program transformation systems. In Proceedings of the 11th International Conference on Software Engineering, 1997. Google ScholarDigital Library
- M. Carroll and B. Ryder. Incremental data flow update via attribute and dominator updates. In ACM SIGPLAN-SIGACT Symposium on the Principles of Programming Languages, pages 274--284. ACM Press, 1988. Google ScholarDigital Library
- M.D. Carroll and B.G. Ryder. Incremental data flow analysis via dominator and attribute update. In Proceedings of the Conference on Principles of Programming Languages, NY, 1997. IEEE. Google ScholarDigital Library
- Milind Girkar and Constantine~D. Polychronopoulos. The hierarchical task graph as a universal intermediate representation. International Journal of Parallel Programming, 22(5):519--551, October 1994. Google ScholarDigital Library
- Larry G. Jones. Efficient evaluation of circular attribute grammars. ACM Transactions on Programming Languages and Systems (TOPLAS), 12(3):429--462, 1990. Google ScholarDigital Library
- T. Marlowe and B. Ryder. Hybrid incremental alias algorithms. In Proceedings of the Twentyfourth Hawaii International Conference on System Sciences, 1991.Google ScholarCross Ref
- Lori L. Pollock and Mary~Lou Soffa. Incremental global reoptimization of programs. ACM Transactions on Programming Languages and Systems, 14(2):173--200, April 1992. Google ScholarDigital Library
- C. Polychronopoulos. The promis compiler web page. http://promis.csrd.uiuc.edu/.Google Scholar
- The GNU Project. Gcc releases. http://www.gnu.org/software/gcc/releases.html.Google Scholar
- The National Compiler Infrastructure Project. The national compiler infrastructure project. http://www-suif.stanford.edu/suif/NCI, January 1998. Also at http://www.cs.virginia.edu/nci.Google Scholar
- G. Ramalingam and Thomas Reps. A categorized bibliography on incremental computation. In Conference record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Charleston, South Carolina, pages 502--510, 1993. Google ScholarDigital Library
- T. Reps, T. Teitelbaum, and A. Demers. Incremental context-dependent analysis for language-based editors. ACM Transactions on Programming Languages and Systems, 5(3):449--477, July 1983. Google ScholarDigital Library
- B. G. Ryder, W. Landi, and H. D. Pande. Profiling an incremental data flow analysis algorithm. IEEE Transactions on Software Engineering, 16(2):129--140, 1990. Google ScholarDigital Library
- Barbara G. Ryder and Marvin C. Paull. Incremental data-flow analysis algorithms. ACM Transactions on Programming Languages and Systems, 10(1):1--50, January 1988. Google ScholarDigital Library
- H. Saito, N. Stavrakos, S. Carroll, and C. Polychronopoulos. The design of the PROMIS compiler. Compiler Construction Conference, Lecture Notes in Computer Science, 1575:214--228, 1999. Google ScholarDigital Library
- D. Soroker, M. Karasick, J. Barton, and D. Streeter. Extension mechanisms in montana. In Proceedings of the 8th IEEE Israeli Conference on Software and Systems, 1997. Google ScholarDigital Library
- Vugranam~C. Sreedhar, Guang~R. Gao, and Yong-Fong Lee. A new framework for exhaustive and incremental data flow analysis using DJ graphs. In SIGPLAN Conference on Programming Language Design and Implementation, pages 278--290, 1996. Google ScholarDigital Library
- R. S. Sundaresh and P. Hudak. Incremental computation via partial evaluation. In Eighteenth Annual ACM Symposium on Principles of Programming Languages, Orlando, Florida, pages 1--13. New York: ACM, 1991. Google ScholarDigital Library
- Zhiquiang Tan and Karen A. Lemone. A research environment for incremental data flow analysis. In Proceedings of the 1985 ACM thirteenth annual conference on Computer Science, pages 356--362, NY, 1985. ACM Press. Google ScholarDigital Library
- R. Wilson, R. French, C. Wilson, S. Amarasinghe, J. Anderson, S. Tjiang, S. Liao, C. Tseng, M. Hall, M. Lam, and J. Hennessy. The SUIF compiler system: a parallelizing and optimizing research compiler. Technical Report CSL-TR-94-620, Stanford University, May 1994. Google ScholarDigital Library
- Jyh-Shiarn Yur, Barbara G. Ryder, and William Landi. An incremental flow- and context-sensitive pointer aliasing analysis. In Proceedings of the 21st International Conference on Software Engineering (ICSE-99), pages 442--452, NY, May 16--22 1999. ACM Press. Google ScholarDigital Library
Index Terms
- A framework for incremental extensible compiler construction
Recommendations
The jastadd extensible java compiler
Proceedings of the 2007 OOPSLA conferenceThe JastAdd Extensible Java Compiler is a high quality Java compiler that is easy to extend in order to build static analysis tools for Java, and to extend Java with new language constructs. It is built modularly, with a Java 1.4 compiler that is ...
The JastAdd extensible Java compiler
OOPSLA '07: Companion to the 22nd ACM SIGPLAN conference on Object-oriented programming systems and applications companionThe JastAdd Extensible Java Compiler is a high quality Java compiler that is easy to extend with new analyses as well as new language constructs. In this demonstration we show how the existing framework for name analysis and type checking can be ...
The jastadd extensible java compiler
OOPSLA '07: Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems, languages and applicationsThe JastAdd Extensible Java Compiler is a high quality Java compiler that is easy to extend in order to build static analysis tools for Java, and to extend Java with new language constructs. It is built modularly, with a Java 1.4 compiler that is ...
Comments