Zhong Shao
Andrew W. Appel
Skip Abstract Section
Abstract
Modern compilers often implement function calls (or returns) in two steps: first, a “closure” environment is properly installed to provide access for free variables in the target program fragment; second, the control is transferred to the target by a “jump with arguments (for results).” Closure conversion—which decides where and how to represent closures at runtime—is a crucial step in the compilation of functional languages. This paper presents a new algorithm that exploits the use of compile-time control and data-flow information to optimize funtion calls. By extensive closure sharing and allocation by 36% and memory fetches for local and global variables by 43%; and improves the already efficient code generated by an earlier version of the Standard ML of New Jersey compiler by about 17% on a DECstation 5000. Moreover, unlike most other approaches, our new closure-allocation scheme the strong safe-for-space-complexity rule, thus achieving good asymptotic space usage.
- APPEL, A. W. 1987. Garbage collection can be faster than stack allocation. Information Processing Letter 25, 4, 275-279. Google Scholar
- APPEL, A. W. 1992. Compiling with Continuations. Cambridge University Press, New York. Google Scholar
- APPEL, A. W. 1994. Loop headers in A-calculus or CPS. Lisp and Symbolic Computation 7, 337-343. Also available as Princeton University Tech Report CS-TR-460-94.Google Scholar
- APPEL, t. W. AND JIM, T. 1988. Optimizing closure environment representations. Tech. Rep. 168, Dept. of Computer Science, Princeton University, Princeton, NJ.Google Scholar
- APPEL, t. W. AND JIM, T. 1989. Continuation-passing, closure-passing style. In Sixteenth ACM Syrup. on Principles of Programming Languages. ACM Press, New York, 293-302. Google Scholar
- APPEL, A. W. AND MACQUEEN, D. B. 1991. Standard ML of New Jersey. In Third Int'l Syrup. on Prog. Lang. Implementation and Logic Programming, M. Wirsing, Ed. Springer-Verlag, New York, 1-13.Google Scholar
- APPEL, t. W. AND SHAO, Z. 1992. Callee-save registers in continuation-passing style. Lisp and Symbolic Computation 5, 3, 191-221. Google Scholar
- APPEL, t. W. AND SHAO, Z. 1996. Empirical and analytic study of stack versus heap cost for languages with closures. Journal of Functional Programming 6, 1 (January), 47-74.Google Scholar
- AUGUSTSSON, L. 1989. Garbage collection in the < u, g >-machine. Tech. Rep. PMG memo 73, Dept. of Computer Sciences, Chalmers University of Technology, Goteborg, Sweden. December.Google Scholar
- BALL, T. AND LARUS, J. R. 1993. Branch prediction for free. In Proc. ACM SIGPLAN '93 Conf. on Prog. Lang. Design and Implementation. ACM Press, New York, 300-313. Google Scholar
- BRIGGS, P., COOPER, K. D., KENNEDY, K., AND TORCZON, L. 1989. Coloring heuristics for register allocation. In Proc. ACM SIGPLAN '89 Conf. on Prog. Lang. Design and Implementation. ACM Press, New York, 275-284. Google Scholar
- CARDELLI, L. 1984. Compiling a functional language. In Proc. of the 198g ACM Conference on Lisp and Functional Programming. ACM Press, New York, 208-217. Google Scholar
- CHAITIN, G. J. 1982. Register allocation and spilling via graph coloring. In Symposium on Compiler Construction. ACM Sigplan, New York, 98-105. Google Scholar
- CHASE, D. R. 1988. Safety considerations for storage allocation optimizations. In Proc. ACM SIGPLAN '88 Conf. on Prog. Lang. Design and Implementation. ACM Press, New York, 1-9. Google Scholar
- CHENG, P., HARPER, R., AND LEE, P. 1998. Generational stack collection and profile-driven pretenuring. In Proc. ACM SIGPLAN '98 Conf. on Prog. Lang. Design and Implementation. ACM Press, New York, 162-173. Google Scholar
- CHOW, F. C. 1988. Minimizing register usage penalty at procedure calls. In Proc. ACM SIGPLAN '88 Conf. on Prog. Lang. Design and Implementation. ACM Press, New York, 85-94. Google Scholar
- CLINGER, W. D. 1998. Proper tail recursion and space efficiency. In Proc. ACM SIGPLAN '98 Conf. on Prog. Lang. Design and Implementation. ACM Press, New York, 174-185. Google Scholar
- CLINGER, W. D., HARTHEIMER, t. H., AND OST, E. ~/{. 1988. Implementation strategies for continuations. In 1988 ACM Conference on Lisp and Functional Programming. ACM Press, New York, 124-131. Google Scholar
- COUSINEAU, G., CURIEN, P. L., AND iV{AUNY, iV{. 1985. The categorical abstract machine. In Functional Programming Languages and Computer Architecture, LNCS Vol 201, J. P. Jouannaud, Ed. Springer-Verlag, New York, 50-64. Google Scholar
- DIWAN, t., TARDITI, D., AND MOSS, E. 1994. Memory subsystem performance of programs using copying garbage collection. In Proc. 21st Annual ACM SIGPLAN-SIGACT Syrup. on Principles of Programming Languages. ACM Press, New York, 1-14. Google Scholar
- FLANAGAN, C., SABRY, A., DUBA, B. F., AND FELLEISEN, M. 1993. The essence of compiling with continuations. In Proc. A CM SIGPLAN '93 Conf. on Prog. Lang. Design and Implementation. ACM Press, New York, 237-247. Google Scholar
- GEORGE, L. AND APPEL, A. W. 1996. Iterated register coalescing. In Proc. Twenty-third Annual A CM SIGPLAN-SIGA CT Syrup. on Principles of Programming Languages. ACM Press, New York, 208-218. Google Scholar
- GEORGE, L., GUILLAUME, F., AND REPPY, J. 1994. A portable and optimizing backend for the SML/NJ compiler. In Proceedings of the 1994 International Conference on Compiler Construction. Springer-Verlag, New York, 83-97. Google Scholar
- GOMARD, C. I~. AND SESTOFT, P. 1991. Globalization and live variables. In Proceedings of the 1991 Symposium on Partial Evaluation and Semantics-Based Program Manipulation. ACM Press, New York, 166-177. Google Scholar
- HANSON, C. 1990. Efficient stack allocation for tail-recursive languages. In 1990 ACM Conference on Lisp and Functional Programming. ACM Press, New York, 106-118. Google Scholar
- HIEB, R., DYBVIG, R. I~., AND BRUGGEMAN, C. 1990. Representing control in the presence of first-class continuations. In Proc. A CM SIGPLAN '90 Conf. on Prog. Lang. Design and Iraplementation. ACM Press, New York, 66-77. Google Scholar
- JOHNSSON, T. 1985. Lambda Lifting: Transforming Programs to Recursive Equations. In The Second International Conference on Functional Programming Languages and Computer Atchitecture. Springer-Verlag, New York, 190-203. Google Scholar
- JouPPI, N. P. 1993. Cache write policies and performance. In Proceedings of the 20th Annual International Symposium on Computer Architecture. ACM Press, New York, 191-201. Google Scholar
- KELSEY, R. AND HUDAK, P. 1989. Realistic compilation by program transformation. In Sixteenth ACM Syrup. on Principles of Programming Languages. ACM Press, New York, 281-292. Google Scholar
- KRANZ, D. 1987. ORBIT: An optimizing compiler for Scheme. Ph.D. thesis, Yale University, New Haven, CT. Google Scholar
- KRANZ, D., I~ELSEY, R., REES, J., HUDAK, P., PHILBIN, J., AND ADAMS, N. 1986. ORBIT: An optimizing compiler for Scheme. SIGPLAN Notices (Proc. Sigplan '86 Syrup. on Compiler Construction) 21, 7 (July), 219-233. Google Scholar
- LANDIN, P. J. 1964. The mechanical evaluation of expressions. Computer Journal 6, 4, 308-320.Google Scholar
- MILNER, R., TOFTE, M., AND HARPER, R. 1990. The Definition of Standard ML. MIT Press, Cambridge, Massachusetts. Google Scholar
- MORRISETT, G., CRARY, I~., GLEW, N., AND WALKER, D. 1998. Stack-based typed assembly language. In Proc. 1998 International Workshop on Types in Compilation: LNCS Vol 1473, X. Leroy and A. Ohori, Eds. Springer-Verlag, Kyoto, Japan, 28-52. Google Scholar
- MUCHNICK, S. S. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, San Francisco, California. Google Scholar
- RAMSEY, N. AND PEYTON JONES, S. 1999. A single intermediate language that supports multiple implementations of exceptions. Technical paper yet to be published.Google Scholar
- REPPY, J. H. 1993. A high-performance garbage collector for Standard ML. Technical memorandum, AT&T Bell Laboratories, Murray Hill, NJ. January.Google Scholar
- ROZAS, G. J. 1984. Liar, an Algol-like compiler for scheme. S.B. thesis, MIT Dept. of Computer Science and Electrical Engineering.Google Scholar
- RYDER, B. G. AND PAULL, M. C. 1986. Elimination algorithms for data flow analysis. ACM Computing Surveys 18, 3 (September), 277-316. Google Scholar
- SHAO, Z. 1994. Compiling Standard ML for efficient execution on modern machines. Ph.D. thesis, Princeton University, Princeton, NJ. Tech Report CS-TR-475-94. Google Scholar
- SHAO, Z. 1997. Flexible representation analysis. In Proc. 1997 ACM SIGPLAN International Conference on Functional Programming (ICFP'97). ACM Press, New York, 85-98. Google Scholar
- SHAO, Z. AND APPEL, A. W. 1994. Space-efficient closure representations. In 1994 ACM Conference on Lisp and Functional Programming. ACM Press, New York, 150-161. Google Scholar
- SHAO, Z. AND APPEL, A. W. 1995. A type-based compiler for Standard ML. In Proc. ACM SIGPLAN '95 Conf. on Prog. Lang. Design and Implementation. ACM Press, New York, 116- 129. Google Scholar
- SHIVERS, O. 1991. Control-flow analysis of higher-order languages. Ph.D. thesis, Carnegie Mellon Univ., Pittsburgh, Pennsylvania. CMU-CS-91-145. Google Scholar
- STEELE, G. L. 1978. Rabbit: a compiler for Scheme. Tech. Rep. AI-TR-474, MIT, Cambridge, MA. Google Scholar
- STEELE, G. L. AND SUSSMAN, G. J. 1980. The dream of a lifetime: A lazy variable extent mechanism. In Proceedings of the 1980 LISP Conference. ACM Press, Stanford, 163-172. Google Scholar
- TARJAN, R. E. 1974. Testing flow graph reducibility. Journal of Computer and System Science 9, 3 (December), 355-365.Google Scholar
- UNGAR, D. M. 1986. The Design and Evaluation of A High Performance Smalltalk System. MIT Press, Cambridge,MA. Google Scholar
- WAND, M. AND STECKLER, P. 1994. Selective and lightweight closure conversion. In Proc. 21st Annual A CM SIGPLAN-SIGA CT Syrup. on Principles of Programming Languages. ACM Press, New York, 435-445. Google Scholar
Index Terms
- Efficient and safe-for-space closure conversion
Recommendations
Typed closure conversion for the calculus of constructions
PLDI '18Dependently typed languages such as Coq are used to specify and verify the full functional correctness of source programs. Type-preserving compilation can be used to preserve these specifications and proofs of correctness through compilation into the ...
Typed closure conversion for the calculus of constructions
PLDI 2018: Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and ImplementationDependently typed languages such as Coq are used to specify and verify the full functional correctness of source programs. Type-preserving compilation can be used to preserve these specifications and proofs of correctness through compilation into the ...
Closure Conversion in Little Pieces
PPDP '23: Proceedings of the 25th International Symposium on Principles and Practice of Declarative ProgrammingClosure conversion, an essential step in compiling functional programs, is traditionally presented as a global transformation from a language with higher-order functions to one without. Optimizing this transformation can be done at any of its three ...
Comments