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\%.
