Staged allocation: a compositional technique for specifying and implementing procedure calling conventions

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.

REFERENCES

• 1: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 2: Apple Computer. 2003. Mach-O Runtime Architecture.
• 3: Mark W. Bailey , Jack W. Davidson, Csdl: reusable computing system descriptions for retargetable systems software, 2000
• 4: Mark W. Bailey , Jack W. Davidson, A formal model and specification language for procedure calling conventions, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.298-310, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199517]
• 5: --------. 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.
• 6: Mark W. Bailey , Jack W. Davidson, Automatic Detection and Diagnosis of Faults in Generated Code for Procedure Calls, IEEE Transactions on Software Engineering, v.29 n.11, p.1031-1042, November 2003 [doi>10.1109/TSE.2003.1245304]
• 7: Jack W. Davidson , David B. Whalley, Methods for saving and restoring register values across function calls, Software—Practice & Experience, v.21 n.2, p.149-165, Feb. 1991 [doi>10.1002/spe.4380210204]
• 8: Christopher W. Fraser , David R. Hanson, A Retargetable C Compiler: Design and Implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 9: George, Lal. 1999. SMLNJ: Garbage collection API. As of November 2005, available from http://www.smlnj.org/compiler-notes/gc-api.ps.
• 10: Ralph E. Griswold , Madge T. Griswold, The ICON Programming Language, Annabooks, 1996
• 11: Hutton, Graham. 1992. Higher-order functions for parsing. Journal of Functional Programming 2 (July): 323--343.
• 12: Ierusalimschy, Roberto. 2003. Programming in Lua. Lua.org. ISBN 85-903798-1-7.
• 13: 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.
• 14: Christian Lindig, Random testing of C calling conventions, Proceedings of the sixth international symposium on Automated analysis-driven debugging, p.3-12, September 19-21, 2005, Monterey, California, USA [doi>10.1145/1085130.1085132]
• 15: 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.
• 16: Mealy, George H. 1955. A method for synthesizing sequential circuits. Bell System Technical Journal 34 (5): 1045--1079.
• 17: Simon L. Peyton Jones , Norman Ramsey , Fermin Reig, C--: A Portable Assembly Language that Supports Garbage Collection, Proceedings of the International Conference PPDP'99 on Principles and Practice of Declarative Programming, p.1-28, September 29-October 01, 1999
• 18: Norman Ramsey, Embedding an interpreted language using higher-order functions and types, Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators, p.6-14, June 12-12, 2003, San Diego, California [doi>10.1145/858570.858571]
• 19: 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.
• 20: Norman Ramsey , Simon Peyton Jones, A single intermediate language that supports multiple implementations of exceptions, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.285-298, June 18-21, 2000, Vancouver, British Columbia, Canada
• 21: 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.
• 22: Bjarne Stroustrup, The C++ Programming Language, Third Edition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Retargetable compilers

General Terms:
Algorithms, Design, Languages, Standardization

Keywords:
calling conventions