Fritz Henglein. Global tagging optimization by type inference. In LFP '92: Proceedings of the 1992 ACM conference on LISP and functional programming, Also DIKU Semantics Report D-102, Pages 205-215, New York, NY, USA, June 1992.
Download paper: (link)
Download paper:
Adobe portable document (pdf)
Copyright notice:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Tag handling accounts for a substantial amount of execution cost in latently typed languages such as Common LISP and Scheme, especially on architectures that provide no special hardware support. We present a tagging optimization algorithm based on type inference that is global: it traces tag information across procedure boundaries, not only within procedures; efficient: it runs asymptotically in almost-linear time with excellent practical run-time be- havior (e.g. 5,000 line Scheme programs are processed in a matter of seconds); useful: it eliminates at compile-time between 60 and 95% of tag handling operations in nonnumerical Scheme code (based on preliminary data); structural: it traces tag information in higher order (procedure) values and especially in structured (e.g. list) values, where reportedly 80% of tag handling operations take place; well-founded: it is based on a formal static typing discpline with a special type Dynamic that has a robust and semantically sound ``minimal typing'' property; implementation-independent: no tag implementation technology is presupposed; the re- sults are displayed as an explicitly typed source program and can be interfaced with compiler backends of statically typed languages such as Standard ML; user-friendly: no annotations by the programmer are necessary; it operates on the program source, provides useful type information to a programmer in the spirit of ML's type system, and makes all tag handling operations necessary at run-time explicit (and thus shows which ones can be eliminated without endangering correctness of program execution). This agenda is accomplished by: * maintaining and tracing only a minimum of information - no sets of abstract closures or cons points etc. that may reach a program point are kept, only their collective tagging information; no repeated analysis of program points is performed; * scheduling processing steps such that each one contributes to the final result - no idle or partially idle traversals of the syntax tree are performed; instead all relevant constraints are extracted in a single pass over the syntax tree; * using theoretically and practically very efficient data structures; in particular, the union/find data structure is used to maintain and solve the extracted constraints. This improves and complements previous work on tagging optimization in several respects. * In the LISP compiler for S1 [BGS82], in Orbit [KKR*86], and in Screme [VP89,Ple91] tagging optimization (representation analysis) is typically performed for atomic types (numbers), based on local control flow information. Our analysis is global and based on abstract data flow information. * In TICL [MK90] type analysis of Common LISP programs relies on costly repeated analysis and programmer type declarations. * Shivers [Shi91a] similarly uses potentially expensive and complicated data flow re- analysis for type recovery in Scheme and relies to some degree on programmer type declarations; his analysis works on the CPS transform of a Scheme program and as such the results are not presentable to the user/programmer. The main practical contribution of our tagging optimization algorithm is likely to be its combination of execution efficiency and ability to eliminate tag handling operations in structured data, especially in lists: Steenkiste and Hennessy report that 80% of all dynamic type checking operations are due to list operations, most of which are statically eliminated by our type inference algorithm. The computed information can also be used for unboxing and closure allocation (reference escape) analysis, although this is not pursued in this paper
[ Dyntyp ]
@InProceedings{henglein92c,
Author = {Henglein, Fritz},
Title = {Global tagging optimization by type inference},
BookTitle = {LFP '92: Proceedings of the 1992 ACM conference on LISP and functional programming},
Pages = {205--215},
Publisher = {ACM},
Address = {New York, NY, USA},
Month = {June},
Year = {1992}
}
Get EndNote Reference (.ref)