ABSTRACT
We present staged allocation, a technique for specifying calling conventions by composing tiny allocators called stages. A specification written using staged allocation has a precise, formal semantics, and it can be executed directly inside a compiler. Specifications of nine standard C~calling conventions range in size from 15 to 30 lines each. An implementation of staged allocation takes about 250 lines of ML or 650~lines of C++. Each specification can be used not only to help a compiler implement the calling convention but also to generate a test suite.
- Appel, Andrew W. 1992. Compiling with Continuations. Cambridge: Cambridge University Press. Google ScholarDigital Library
- Apple Computer. 2003. Mach-O Runtime Architecture.Google Scholar
- Bailey, Mark W. 2000. CSDL: Reusable Computing System Descriptions for Retargetable Systems Software. PhD thesis, University of Virginia, Dept of Computer Science. Google ScholarDigital Library
- Bailey, Mark W. and Jack W. Davidson. 1995. A formal model and specification language for procedure calling conventions. In Conference Record of the 22nd Annual ACM Symposium on Principles of Programming Languages, pages 298--310. Google ScholarDigital Library
- --------. 1996. Target-sensitive construction of diagnostic programs for procedure calling sequence generators. Proceedings of the ACM SIGPLAN '96 Conference on Programming Language Design and Implementation, in SIGPLAN Notices 31 (May): 249--257. Google ScholarDigital Library
- --------. 2003. Automatic detection and diagnosis of faults in generated code for procedure calls. IEEE Transactions on Software Engineering 29 (November): 1031--1042. Google ScholarDigital Library
- Davidson, Jack W. and David B. Whalley. 1991. Methods for saving and restoring register values across function calls. Software---Practice & Experience 21 (2): 149--165. Google ScholarDigital Library
- Fraser, Christopher W. and David R. Hanson. 1995. A Retargetable C Compiler: Design and Implementation. Redwood City, CA: Benjamin/Cummings. Google ScholarDigital Library
- George, Lal. 1999. SMLNJ: Garbage collection API. As of November 2005, available from http://www.smlnj.org/compiler-notes/gc-api.ps.Google Scholar
- Griswold, Ralph E. and Madge T. Griswold. 1996. The Icon Programming Language. Third edition. San Jose, CA: Peer-to-Peer Communications. Google ScholarDigital Library
- Hutton, Graham. 1992. Higher-order functions for parsing. Journal of Functional Programming 2 (July): 323--343.Google ScholarCross Ref
- Ierusalimschy, Roberto. 2003. Programming in Lua. Lua.org. ISBN 85-903798-1-7.Google Scholar
- Leroy, Xavier, Damien Doligez, Jacques Garrigue, Didier Rémy, and Jérôme Vouillon. 2004. The Objective Caml system release 3.08: Documentation and user's manual. INRIA. Available at http://pauillac.inria.fr/ocaml/htmlman.Google Scholar
- Lindig, Christian. 2005. Random testing of C calling conventions. In Sixth International Symposium on Automated and Analysis-Driven Debugging (AADEBUG), pages 3--11. Google ScholarDigital Library
- Lindig, Christian and Norman Ramsey. 2004. Declarative composition of stack frames. In 13th International Conference on Compiler Construction (CC 2004), Vol. 2985 of LNCS, pages 298--312.Google ScholarCross Ref
- Mealy, George H. 1955. A method for synthesizing sequential circuits. Bell System Technical Journal 34 (5): 1045--1079.Google ScholarCross Ref
- Peyton Jones, Simon L., Norman Ramsey, and Fermin Reig. 1999. C--: a portable assembly language that supports garbage collection. In International Conference on Principles and Practice of Declarative Programming, Vol. 1702 of LNCS, pages 1--28. Springer Verlag. Google ScholarDigital Library
- Ramsey, Norman. 2005. Embedding an interpreted language using higher-order functions and types. Journal of Functional Programming. To appear. A preliminary version of this paper appeared in Proceedings of the ACM Workshop on Interpreters, Virtual Machines, and Emulators, June 2003. Google ScholarDigital Library
- Ramsey, Norman and Christian Lindig. 2002. Custom calling conventions in a portable assembly language. Unpublished paper available at http://www.eecs.harvard.edu/~nr/pubs/custom-abstract.html.Google Scholar
- Ramsey, Norman and Simon L. Peyton Jones. 2000. A single intermediate language that supports multiple implementations of exceptions. Proceedings of the ACM SIGPLAN~'00 Conference on Programming Language Design and Implementation, in SIGPLAN Notices 35 (May): 285--298. Google ScholarDigital Library
- Smith, Michael D. and Glenn Holloway. 2000. An introduction to Machine SUIF and its portable libraries for analysis and optimization. See http://www.eecs.harvard.edu/machsuif/software/nci/overview.html.Google Scholar
- Stroustrup, Bjarne. 1997. The C++ Programming Language. Third edition. Reading, MA: Addison-Wesley. Google ScholarDigital Library
Index Terms
- Staged allocation: a compositional technique for specifying and implementing procedure calling conventions
Recommendations
Staged allocation: a compositional technique for specifying and implementing procedure calling conventions
Proceedings of the 2006 POPL ConferenceWe present staged allocation, a technique for specifying calling conventions by composing tiny allocators called stages. A specification written using staged allocation has a precise, formal semantics, and it can be executed directly inside a compiler. ...
Staged compilation
Traditional compilers compile and optimize files separately, making worst-case assumptions about the program context in which a file is to be linked. More aggressive compilation architectures perform cross-file interprocedural or whole-program analyses, ...
Staged compilation
PEPM '02: Proceedings of the 2002 ACM SIGPLAN workshop on Partial evaluation and semantics-based program manipulationTraditional compilers compile and optimize files separately, making worst-case assumptions about the program context in which a file is to be linked. More aggressive compilation architectures perform cross-file interprocedural or whole-program analyses, ...
Comments