C and tcc: a language and compiler for dynamic code generation

ABSTRACT

Dynamic code generation allows programmers to use run-time information in order to achieve performance and expressiveness superior to those of static code. The 'C(Tick C) language is a superset of ANSI C that supports efficient and high-level use of dynamic code generation. 'C provides dynamic code generation at the level of C expressions and statements and supports the composition of dynamic code at run time. These features enable programmers to add dynamic code generation to existing C code incrementally and to write important applications (such as “just-in-time” compilers) easily. The article presents many examples of how 'C can be used to solve practical problems. The tcc compiler is an efficient, portable, and freely available implementation of 'C. tcc allows programmers to trade dynamic compilation speed for dynamic code quality: in some aplications, it is most important to generate code quickly, while in others code quality matters more than compilation speed. The overhead of dynamic compilation is on the order of 100 to 600 cycles per generated instruction, depending on the level of dynamic optimizaton. Measurements show that the use of dynamic code generation can improve performance by almost an order of magnitude; two- to four-fold speedups are common. In most cases, the overhead of dynamic compilation is recovered in under 100 uses of the dynamic code; sometimes it can be recovered within one use.

REFERENCES

• 1: Joel Auslander , Matthai Philipose , Craig Chambers , Susan J. Eggers , Brian N. Bershad, Fast, effective dynamic compilation, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.149-159, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 2: B. N. Bershad , S. Savage , P. Pardyak , E. G. Sirer , M. E. Fiuczynski , D. Becker , C. Chambers , S. Eggers, Extensibility safety and performance in the SPIN operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.267-283, December 03-06, 1995, Copper Mountain, Colorado, United States
• 3: Andrew D. Birrell , Bruce Jay Nelson, Implementing remote procedure calls, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.39-59, February 1984 [doi>10.1145/2080.357392]
• 4: BRIGGS, P. AND HARVEY, T. 1994. Multiplication by integer constants. http ://softlib. rice. edu/MSCP.
• 5: CHAITIN, G. J., AUSLANDER, M. A., CHANDRA, A. K., COCKE, J., HOPKINS, M. E., AND MARK- STEIN, P. W. 1981. Register allocation via coloring. Comput. Lang. 6, 47-57.
• 6: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.146-160, June 19-23, 1989, Portland, Oregon, United States
• 7: D. D. Clark , D. L. Tennenhouse, Architectural considerations for a new generation of protocols, Proceedings of the ACM symposium on Communications architectures & protocols, p.200-208, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 8: Charles Consel , François Noël, A general approach for run-time specialization and its application to C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.145-156, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237767]
• 9: L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800542]
• 10: Scott Draves, Lightweight Languages for Interactive Graphics, Carnegie Mellon University, Pittsburgh, PA, 1995
• 11: Dawson R. Engler , Todd A. Proebsting, DCG: an efficient, retargetable dynamic code generation system, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.263-272, October 05-07, 1994, San Jose, California, United States
• 12: Dawson R. Engler, VCODE: a retargetable, extensible, very fast dynamic code generation system, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.160-170, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 13: Dawson R. Engler , Wilson C. Hsieh , M. Frans Kaashoek, C: a language for high-level, efficient, and machine-independent dynamic code generation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.131-144, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237765]
• 14: D. R. Engler , M. F. Kaashoek , J. O'Toole, Jr., Exokernel: an operating system architecture for application-level resource management, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.251-266, December 03-06, 1995, Copper Mountain, Colorado, United States
• 15: George E. Forsythe , Michael A. Malcolm , Cleve B. Moler, Computer Methods for Mathematical Computations, Prentice Hall Professional Technical Reference, 1977
• 16: FRASER, C. W. 1980. copt. ftp ://ftp. cs.princeton, edu/pub/ lcc/contrib/copt, shar.
• 17: FRASER, C. W. AND HANSON, D. R. 1990. A code generation interface for ANSI C. Technical Report CS-TR-270-90, Department of Computer Science, Princeton University.
• 18: Christopher W. Fraser , David R. Hanson, A Retargetable C Compiler: Design and Implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 19: Christopher W. Fraser , Robert R. Henry , Todd A. Proebsting, BURG: fast optimal instruction selection and tree parsing, ACM SIGPLAN Notices, v.27 n.4, p.68-76, April 1992 [doi>10.1145/131080.131089]
• 20: Brian Grant , Markus Mock , Matthai Philipose , Craig Chambers , Susan J. Eggers, Annotation-directed run-time specialization in C, Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.163-178, June 12-13, 1997, Amsterdam, The Netherlands
• 21: Samuel P. Harbison , Guy L. Steele, Jr., C: a reference manual (3rd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 22: Urs Hölzle , David Ungar, Optimizing dynamically-dispatched calls with run-time type feedback, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.326-336, June 20-24, 1994, Orlando, Florida, United States
• 23: KELSEY, R., CLINGER, W., REES, J., (EDITORS), ET AL. 1998. Revised5 Report on the Algorithmic Language Scheme. http ://www-swiss. ai. mit. edu/~j affer/r5rs_toc, html.
• 24: David Keppel, A portable interface for on-the-fly instruction space modification, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.86-95, April 08-11, 1991, Santa Clara, California, United States
• 25: KEPPEL, D., EGGERS, S., AND HENRY, R. 1991. A case for runtime code generation. Tech. Rep. 91-11-04, University of Washington.
• 26: KEPPEL, D., EGGERS, S., AND HENRY, R. 1993. Evaluating runtime-compiled value-specific optimizations. Tech. Rep. 93-11-02, Department of Computer Science and Engineering, University of Washington.
• 27: LEONE, M. AND DYBVIG, R. K. 1997. Dynamo: A staged compiler architecture for dynamic program optimization. Tech. Rep. 490, Indiana University Computer Science Department.
• 28: Peter Lee , Mark Leone, Optimizing ML with run-time code generation, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.137-148, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 29: John K. Ousterhout, Tcl and the Tk toolkit, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• 30: PIKE, R., LOCANTHI, B., AND REISER, J. 1985. Hardware/software trade-offs for bitmap graphics on the Blit. Softw. Pract. Exper. 15, 2 (Feb.), 131-151.
• 31: Massimiliano Poletto , Dawson R. Engler , M. Frans Kaashoek, tcc: a system for fast, flexible, and high-level dynamic code generation, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.109-121, June 16-18, 1997, Las Vegas, Nevada, United States
• 32: Massimiliano Poletto , Vivek Sarkar, Linear scan register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.895-913, Sept. 1999 [doi>10.1145/330249.330250]
• 33: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 34: C. Pu , T. Autrey , A. Black , C. Consel , C. Cowan , J. Inouye , L. Kethana , J. Walpole , K. Zhang, Optimistic incremental specialization: streamlining a commercial operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.314-321, December 03-06, 1995, Copper Mountain, Colorado, United States
• 35: Pu, C., iV{ASSALIN, H., AND IOANNIDIS, J. 1988. The Synthesis kernel. Comput. Syst. 1, 1, 11-32.
• 36: CORPORATE SPARC International, Inc., The SPARC architecture manual (version 9), Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 37: Guy L. Steele, Jr., Common LISP: the language (2nd ed.), Digital Press, Newton, MA, 1990
• 38: Chandramohan A. Thekkath , Henry M. Levy, Limits to low-latency communication on high-speed networks, ACM Transactions on Computer Systems (TOCS), v.11 n.2, p.179-203, May 1993 [doi>10.1145/151244.151247]
• 39: Jack E. Veenstra , Robert J. Fowler, MINT: A Front End for Efficient Simulation of Shared-Memory Multiprocessors, Proceedings of the Second International Workshop on Modeling, Analysis, and Simulation On Computer and Telecommunication Systems, p.201-207, January 31-February 02, 1994
• 40: Larry Wall , Randal L. Schwartz, Programming perl, O'Reilly & Associates, Inc., Sebastopol, CA, 1991
• 41: Emmett Witchel , Mendel Rosenblum, Embra: fast and flexible machine simulation, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.68-79, May 23-26, 1996, Philadelphia, Pennsylvania, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Specialized application languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Code generation; Run-time environments

General Terms:
Algorithms, Languages, Performance

Keywords:
ANSI C, compilers, dynamic code generation, dynamic code optimization