Source-Level Optimization of Run-Time Program Generators

  • Samuel Kamin
  • Barış Aktemur
  • Philip Morton
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3676)


We describe our efforts to use source-level rewriting to optimize run-time program generators written in Jumbo, a run-time program generation system for Java. Jumbo is a compiler written in compositional style, which brings the advantage that any program fragment can be abstracted out and compiled to an intermediate form. These forms can be put together at run-time to build complete programs. This principle provides a high level of flexibility in writing program generators. However, this comes at the price of inefficient run-time compilation. Using source-level transformations, we optimize the run-time generation of byte code from fragments, achieving speedups of 5–15%. We discuss the optimization process and give several examples.


Program Generation Partial Evaluation Abstract Syntax Java Virtual Machine Denotational Semantic 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Kamin, S., Clausen, L., Jarvis, A.: Jumbo: Run-time Code Generation for Java and its Applications. In: Proc. of the Intl. Symp. on Code Generation and Optimization (CGO 2003), pp. 48–56. IEEE Computer Society, Los Alamitos (2003)CrossRefGoogle Scholar
  2. 2.
    Clausen, L.: Optimization. In Distributed Run-time Compilation. PhD thesis, University of Illinois at Urbana-Champaign (2004)Google Scholar
  3. 3.
    Kamin, S.: Routine Run-time Code Generation. In: Companion of the 18th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2003), pp. 208–220. ACM Press, New York (2003); Also appeared in: SIGPLAN Notices, vol. 38, pp. 44-56 (2003)CrossRefGoogle Scholar
  4. 4.
    Kamin, S.: Program Generation Considered Easy. In: Proc. of the 2004 ACM SIGPLAN Symp. on Partial Evaluation and Semantics-based Program Manipulation (PEPM 2004), pp. 68–79. ACM Press, New York (2004)CrossRefGoogle Scholar
  5. 5.
    Taha, W., Sheard, T.: MetaML and Multi-stage Programming with Explicit Annotations. Theoretical Computer Science 248, 211–242 (2000)zbMATHCrossRefGoogle Scholar
  6. 6.
    Taha, W., Calcagno, C., Leroy, X., Pizzi, E.: MetaOCaml,
  7. 7.
    Engler, D.R., Hsieh, W.C., Kaashoek, M.F.: C: A Language for High-level, Efficient, and Machine-independent Dynamic Code Generation. In: Proc. of the 23rd ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages (POPL 1996), pp. 131–144. ACM Press, New York (1996)CrossRefGoogle Scholar
  8. 8.
    Poletto, M., Hsieh, W.C., Engler, D.R., Kaashoek, M.F.: C and tcc: A Language and Compiler for Dynamic Code Generation. ACM Transactions on Programming Languages and Systems 21, 324–369 (1999)CrossRefGoogle Scholar
  9. 9.
    Poletto, M., Engler, D.R., Kaashoek, M.F.: tcc: A System for Fast, Flexible, and High-level Dynamic Code Generation. In: Proc. of the ACM SIGPLAN 1997 Conference on Programming Language Design and Implementation (PLDI 1997), pp. 109–121. ACM Press, New York (1997)CrossRefGoogle Scholar
  10. 10.
    Oiwa, Y., Masuhara, H., Yonezawa, A.: DynJava: Type Safe Dynamic Code Generation in Java. In: The 3rd JSSST Workshop on Programming and Programming Languages, PPL 2001 (2001)Google Scholar
  11. 11.
    Consel, C., Lawall, J.L., Meur, A.F.L.: A Tour of Tempo: A Program Specializer for the C Language. Sci. Comput. Program. 52, 341–370 (2004)zbMATHCrossRefGoogle Scholar
  12. 12.
    Grant, B., Mock, M., Philipose, M., Chambers, C., Eggers, S.J.: DyC: an expressive annotation-directed dynamic compiler for C. Theoretical Computer Science 248, 147–199 (2000)zbMATHCrossRefGoogle Scholar
  13. 13.
    Hornof, L., Jim, T.: Certifying compilation and run-time code generation. In: Partial Evaluation and Semantic-Based Program Manipulation, pp. 60–74 (1999)Google Scholar
  14. 14.
    Zook, D., Huang, S.S., Smaragdakis, Y.: Generating AspectJ Programs with Meta-AspectJ. In: Karsai, G., Visser, E. (eds.) GPCE 2004. LNCS, vol. 3286, pp. 1–18. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  15. 15.
    Kamin, S., Callahan, M., Clausen, L.: Lightweight and Generative Components-1: Source-Level Components. In: Czarnecki, K., Eisenecker, U.W. (eds.) GCSE 1999. LNCS, vol. 1799, pp. 49–64. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  16. 16.
    Kamin, S., Callahan, M., Clausen, L.: Lightweight and Generative Components-2: Binary-Level Components. In: Taha, W. (ed.) SAIG 2000. LNCS, vol. 1924, pp. 28–50. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  17. 17.
    Stoy, J.: Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory. The MIT Press, Cambridge (1977)Google Scholar
  18. 18.
    Gosling, J., Joy, B., Steele, G.: The Java Language Definition. Addison-Wesley, Reading (1996)Google Scholar
  19. 19.
    Morton, P.: Analyses and Rewrites for Optimizing Jumbo. Master’s thesis, University of Illinois at Urbana-Champaign (2005)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Samuel Kamin
    • 1
  • Barış Aktemur
    • 1
  • Philip Morton
    • 1
  1. 1.University of Illinois at Urbana-ChampaignUSA

Personalised recommendations