Call Forwarding: A Simple Interprocedural Optimization Technique
for Dynamically Typed Languages
Koen De Bosschere
Saumya Debray
David Gudeman
Sampath Kannan
Abstract
This paper discusses call forwarding, a simple interprocedural
optimization technique for dynamically typed languages. The basic idea
behind the optimization is straightforward: find an ordering for
the ``entry actions'' of a procedure, and generate multiple entry points
for the procedure, so as to maximize the savings realized from
different call sites bypassing different sets of entry actions.
We show that the problem of computing optimal solutions to arbitrary call
forwarding problems is NP-complete, and describe an efficient greedy algorithm
for the problem. Experimental results indicate that (i) this algorithm
is effective, in that the solutions produced are generally close to
optimal; and (ii) the resulting optimization leads to significant
performance improvements for a number of benchmarks tested.