DyC: An expressive annotation-directed dynamic compiler for C. (English) Zbl 0949.68052
We present the design of DyC, a dynamic-compilation system for C based on run-time specialization. Directed by a few declarative user annotations that specify the variables and code on which dynamic compilation should take place, a binding-time analysis computes the set of run-time constants at each program point in the annotated procedure’s control-flow graph; the analysis supports program-point-specific polyvariant division and specialization. The results of the analysis guide the construction of a run-time specializer for each dynamically compiled region; the specializer supports various caching strategies for managing dynamically generated code and mixes of speculative and demand-driven specialization of dynamic branch successors. Most of the key cost/benefit trade-offs in the binding-time analysis and the run-time specializer are open to user control through declarative policy annotations. DyC has been implemented in the context of an optimizing compiler, and initial results have been promising. The speedups we have obtained are good, and the dynamic-compilation overhead is among the lowest of any dynamic-compilation system, typically 20-200 cycles per instruction generated on a Digital Alpha 21164. The majority of DyC’s functionality has been used to dynamically compile an instruction-set simulator. Only three annotations were required, but a few other changes to the program had to be made due to DyC’s lack of support for static global variables. This deficiency and DyC’s rudimentary support for partially static data structures are the primary obstacles to making DyC easy to use.
MSC:
| 68N20 | Theory of compilers and interpreters |
Keywords:
Dynamic compilation; specialization; partial evaluation; constant folding; run-time code generation; program optimization; dataflow analysis; C languageReferences:
| [1] | D.R. Engler, W.C. Hsieh, M.F. Kaashoek, ′C: A language for high-level, efficient, and machine-independent dynamic code generation, Conf. Record of POPL ’96: 23rd ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, January 1996, pp. 131-144.; D.R. Engler, W.C. Hsieh, M.F. Kaashoek, ′C: A language for high-level, efficient, and machine-independent dynamic code generation, Conf. Record of POPL ’96: 23rd ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, January 1996, pp. 131-144. |
| [2] | M. Poletto, D.R. Engler, M.F. Kaashoek, tcc: A system for fast, flexible, and high-level dynamic code generation, SIGPLAN Notices, Proc. ACM SIGPLAN ’97 Conf. on Programming Language Design and Implementation, June 1997, pp. 109-121.; M. Poletto, D.R. Engler, M.F. Kaashoek, tcc: A system for fast, flexible, and high-level dynamic code generation, SIGPLAN Notices, Proc. ACM SIGPLAN ’97 Conf. on Programming Language Design and Implementation, June 1997, pp. 109-121. |
| [3] | D.R. Engler, T.A. Proebsting, DCG: an efficient, retargetable dynamic code generator, Proc. 6th Internat. Conf. on Architectural Support for Programming Languages and Operating Systems, October 1994, pp. 263-273.; D.R. Engler, T.A. Proebsting, DCG: an efficient, retargetable dynamic code generator, Proc. 6th Internat. Conf. on Architectural Support for Programming Languages and Operating Systems, October 1994, pp. 263-273. |
| [4] | M. Leone, P. Lee, Optimizing ML with run-time code generation, SIGPLAN Notices, Proc. ACM SIGPLAN ’96 Conf. on Programming Language Design and Implementation, May 1996, pp. 137-148.; M. Leone, P. Lee, Optimizing ML with run-time code generation, SIGPLAN Notices, Proc. ACM SIGPLAN ’96 Conf. on Programming Language Design and Implementation, May 1996, pp. 137-148. |
| [5] | C. Consel, F. Noël, A general approach for run-time specialization and its application to C, Conf. Record of POPL ’96: 23rd ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, January 1996, pp. 145-156.; C. Consel, F. Noël, A general approach for run-time specialization and its application to C, Conf. Record of POPL ’96: 23rd ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, January 1996, pp. 145-156. |
| [6] | J. Auslander, M. Philipose, C. Chambers, S. Eggers, B. Bershad, Fast, effective dynamic compilation, SIGPLAN Notices, Proc. ACM SIGPLAN ’96 Conf. on Programming Language Design and Implementation, May 1996, pp. 149-159.; J. Auslander, M. Philipose, C. Chambers, S. Eggers, B. Bershad, Fast, effective dynamic compilation, SIGPLAN Notices, Proc. ACM SIGPLAN ’96 Conf. on Programming Language Design and Implementation, May 1996, pp. 149-159. |
| [7] | Goldberg, A.; Robson, D., Smalltalk-80The Language and its Implementation (1983), Addision-Wesley: Addision-Wesley Reading, MA · Zbl 0518.68001 |
| [8] | Lindholm and Yellin, 1997.; Lindholm and Yellin, 1997. |
| [9] | E.G. Sirer, Measuring limits of fine-grain parallelism, Princeton University Senior Project, June 1993.; E.G. Sirer, Measuring limits of fine-grain parallelism, Princeton University Senior Project, June 1993. |
| [10] | Jones, N. D.; Gomard, C. K.; Sestoft, P., Partial Evaluation and Automatic Program Generation (1993), Prentice-Hall: Prentice-Hall Englewood cliffs, NJ · Zbl 0875.68290 |
| [11] | Kernighan, B. W.; Ritchie, D. M., The C Programming Language (1988), Prentice-Hall: Prentice-Hall Englewood cliffs, NJ · Zbl 0697.68008 |
| [12] | R.P. Wilson, M.S. Lam, Efficient context-sensitive pointer analysis for C programs, SIGPLAN Notices, Proc. ACM SIGPLAN ’95 Conf. on Programming Language Design and Implementation, June 1995, pp. 1-12.; R.P. Wilson, M.S. Lam, Efficient context-sensitive pointer analysis for C programs, SIGPLAN Notices, Proc. ACM SIGPLAN ’95 Conf. on Programming Language Design and Implementation, June 1995, pp. 1-12. |
| [13] | B. Steensgaard, Points-to analysis in almost linear time, Conf. Record of POPL ’96: 23rd ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, January 1996, pp. 32-41.; B. Steensgaard, Points-to analysis in almost linear time, Conf. Record of POPL ’96: 23rd ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, January 1996, pp. 32-41. |
| [14] | U. Meyer, Techniques for partial evaluation of imperative languages, Proc. Symp. on Partial Evaluation and Semantics-Based Program Manipulation ’91, Published as SIGPLAN Notices 26(9). June 1991, pp. 94-105.; U. Meyer, Techniques for partial evaluation of imperative languages, Proc. Symp. on Partial Evaluation and Semantics-Based Program Manipulation ’91, Published as SIGPLAN Notices 26(9). June 1991, pp. 94-105. |
| [15] | R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, F.K. Zadeck, An efficient method of computing static single assignment form, Conf. Record of the 16th Ann. ACM Symp. on Principles of Programming Languages, January 1989, pp. 25-35.; R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, F.K. Zadeck, An efficient method of computing static single assignment form, Conf. Record of the 16th Ann. ACM Symp. on Principles of Programming Languages, January 1989, pp. 25-35. |
| [16] | Ferrante, J.; Ottenstein, K. J.; Warren, J. D., The program dependence graph and its use in optimization, ACM trans. programming languages systems, 9, 3, 319-349 (1987) · Zbl 0623.68012 |
| [17] | Lowney et al., 1993.; Lowney et al., 1993. |
| [18] | Scott Thibault, Charles Consel, Gilles Muller, Safe and efficient active network programming, Technical Report Research Report 1170, IRISA, January 1998.; Scott Thibault, Charles Consel, Gilles Muller, Safe and efficient active network programming, Technical Report Research Report 1170, IRISA, January 1998. |
| [19] | A.M. Erosa, L.J. Hendren, Taming control flow: a structured approach to eliminating goto statements, Proc. 1994 IEEE Internat. Conf. on Computer Languages, May 1994, pp. 229-240.; A.M. Erosa, L.J. Hendren, Taming control flow: a structured approach to eliminating goto statements, Proc. 1994 IEEE Internat. Conf. on Computer Languages, May 1994, pp. 229-240. |
| [20] | Consel, C.; Hornof, L.; Noël, F.; Noyé, J.; Volanschi, N., A uniform approach for compile-time and run-time specialization, (Danvy, O.; Glück, R.; Thiemann, P., Partial Evaluation. Dagstuhl Castle, Germany, February 1996, Lecture Notes in Computer Science, Vol. 1110 (1996), Springer: Springer Berlin), 54-72 |
| [21] | Volanschi, E. N.; Consel, C.; Muller, G.; Cowan, C., Declarative specialization of object-oriented programs, SIGPLAN Notices, 32, 10, 286-300 (1997) |
| [22] | M. Leone, P. Lee, Optimizing ML with run-time code generation, Technical Report CMU-CS-95-205, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, December 1995.; M. Leone, P. Lee, Optimizing ML with run-time code generation, Technical Report CMU-CS-95-205, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, December 1995. |
| [23] | L.O. Andersen, Self-applicable C program specialization, Proc. Workshop on Partial Evaluation and Semantics-Based Program Manipulation ’92, June 1992, pp. 54-61. Published as Yale University Technical Report YALEU/DCS/RR-909.; L.O. Andersen, Self-applicable C program specialization, Proc. Workshop on Partial Evaluation and Semantics-Based Program Manipulation ’92, June 1992, pp. 54-61. Published as Yale University Technical Report YALEU/DCS/RR-909. |
| [24] | L.O. Andersen, Program analysis and specialization for the C programming language, Ph.D. Thesis, DIKU, University of Copenhagen, Denmark, 1994. Published as DIKU Research Report 94/19.; L.O. Andersen, Program analysis and specialization for the C programming language, Ph.D. Thesis, DIKU, University of Copenhagen, Denmark, 1994. Published as DIKU Research Report 94/19. |
| [25] | L.O. Andersen, C program specialization, Technical Report 92/14, DIKU, University of Copenhagen, Denmark, May 1992.; L.O. Andersen, C program specialization, Technical Report 92/14, DIKU, University of Copenhagen, Denmark, May 1992. |
| [26] | Consel, C., A tour of Schism: A partial evaluation system for higher-order applicative languages, Proc. Symp. on Partial Evaluation and Semantics-Based Program Manipulation ’93, 145-154 (1993) |
| [27] | D. Weise, R. Conybeare, E. Ruf, S. Seligman, Automatic online partial evaluation, in: J. Hughes (Ed.), Record of the 1991 Conf. on Functional Programming Languages and Computer Architecture, Cambridge, MA, 1991. Lecture Notes in Computer Science Vol. 523, Springer, Berlin, 1991, pp. 165-191.; D. Weise, R. Conybeare, E. Ruf, S. Seligman, Automatic online partial evaluation, in: J. Hughes (Ed.), Record of the 1991 Conf. on Functional Programming Languages and Computer Architecture, Cambridge, MA, 1991. Lecture Notes in Computer Science Vol. 523, Springer, Berlin, 1991, pp. 165-191. |
| [28] | D. Keppel, Runtime code generation, Ph.D. Thesis, University of Washington, 1996.; D. Keppel, Runtime code generation, Ph.D. Thesis, University of Washington, 1996. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
