The University of Arizona
banner image

  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.