Faculty Candidate

Speaker:		Kent Dybvig Indiana University
Topic:		Fast and Effective Procedure Inlining
Date:		Tuesday, December 15, 1998
Time:		9:30 AM
Place:		Gould-Simpson, Room 701

ABSTRACT

Inlining is an important optimization for programs that use procedural abstraction. By replacing a call with an inline expansion of the procedure body, inlining eliminates procedure linkage overhead and often uncovers opportunities for further optimization. Naively expanding all calls inline, however, can lead to unbounded code growth or cause the compiler to loop indefinitely. The effectiveness of an inlining algorithm is therefore determined not only by its ability to recognize inlining opportunities but also by its discretion in exercising those opportunities. To be practical, it must have acceptable compile-time overhead and must scale well to large programs. In this talk, I will describe an inlining algorithm for higher-order languages that combines simple analysis techniques with demand-driven online transformation to achieve consistent and often dramatic performance gains with bounded code growth in fast linear time. The algorithm has proven to be as effective as techniques based on offline flow analysis without the high cost associated with those techniques.

This is joint work with graduate student Oscar Waddell, who presently holds a post-doctoral position at the University of Kansas.