Abstract Iterative Type Analysis and Extended Message Splitting: Optimizing Dynamically-Typed Object-Oriented Programs

Object-oriented languages have suffe=d from poor perfor-mance caused by frequent and slow dynamically-bound pro-cedure calls. The best way to speed up a procedure call is to compile it out, but dynamic binding of object-oriented pro-cedure calls without static receiver type information pre-eludes inlining. Iterative type analysis and extended mes-sage splitting are new compilation techniques that extract much of the necessary type information and make it possible to hoist run-time type tests out of loops. Our system compiles code on-the-fly that is customized to the actual data types used by a running program, The com-piler constructs a control flow graph annotated with type in-formation by simultaneously performing type analysis and Wining. Extended message splitting preserves type infonna-tion that would otherwise be lost by a control-flow merge by duplicating all the code between the merge and the place that uses the information. Iterative type analysis computes the types of variables used in a loop by repeatedly recompiling the loop until the computed types reach a fix-point. Together these two techniques enable our SELF compiler to split off a copy of an entire loop, optimized for the common-case types. By the time our SELF compiler generates code for the graph, it has eliminated many dynamically-dispatched procedure calls and type tests. The resulting machine code is twice as fast as that generated by the p~vious SELF compiler, four times faster than ParcPlace Systems SmalltalHO, * the fast-est commercially available dynamically-typed object-orient-ed language implementation, and nearly half the speed of op-timized C. Iterative type analysis and extended message splitting have cut the performance penalty for dynamically-typed object-oriented languages in half. l SmaLltaJk-80 is a trademark of ParcPlace Systems, Inc. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct com-mercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying i