Optimizing Message Sends in Object-Oriented Languages Through Type Invariant Region Analysis

Mark Leair and Santosh Pande

To appear at ACM SIGPLAN Workshop on Types in Compilation (TIC00), Montreal, Canada, 21 September 2000


Typical programs written in object oriented (OO) languages result in a large number of dynamic message sends due to limitations of static analysis. Dynamic messages can be optimized in OO programs by inlining run-time type tests or by using (polymorphic) inline caches. However, both of these techniques result in significant run-time overheads. In this work, we propose a new optimization based on the following key observation : run-time type testing of a method at {\it every} call-site is extraneous. Many times a polymorphic object, although statically unknown in type, is fixed at run-time and never mutates. In such cases, run-time type testing for its methods is only needed when an object is instantiated. We propose a flow-sensitive analysis which exploits this observation by calculating regions in a program where an object's type is invariant. The type check is hoisted at the entry point of a region and its results are shared over all dispatches that lie within the intraprocedural region. This results in more direct calls in a given program. We implemented this optimization in Vortex, an optimizing object-oriented compiler back-end, and demonstrated its effectiveness on six large Cecil benchmarks. When we augmented the optimizations in Vortex with our framework, we observed an average speed-up of 9.22\%. Moreover, in the dynamic call-sites that we did optimize, we were able to avoid 91\% of the dynamic dispatches in the best case. This same benchmark also showed the best speed-up at 17.9\%.

Server START Conference Manager
Update Time 27 Jul 2000 at 15:10:32
Maintainer rwh+tic@cs.cmu.edu.
Start Conference Manager
Conference Systems