--------------------------------------------------------------------
      Descartes: A Dynamically Adaptive Compiler and Run-Time System
				  using
	  Continual Profile-Driven Program Multi-Specialization
   --------------------------------------------------------------------

			     Michael R. Blair

		  Massachusetts Institute of Technology
		Artificial Intelligence Laboratory and/or
		     Laboratory for Computer Science


  In profiling-based methods of program optimization, one gathers dynamic
information from sample program runs in order to focus optimization efforts
to those code fragments that stand to benefit most.  This ordinarily
requires a programmer-crafted suite of program inputs from which dynamic
statistical data about a program's behavior can be deduced.  This profiling
is usually done only once and thereafter the optimized code is frozen.

  Unfortunately, improving a program's _average_ performance on some
_typical_ inputs does not ensure _optimal_ performance on any _specific_
input.  Worse, it is often difficult to reliably ascertain what constitutes
a typical input for highly general programs.  For example: What is a
typical circuit for a circuit simulator?  What is a typical image for an
image-processing system?  What constitutes a typical program for a compiler
or interpreter or operating system?  The answers can vary wildly among
different sites and program users.  They can even vary dramatically from
day to day for a user with changing needs and goals.

  What is needed is some way for programs to adapt themselves automatically
to their diverse and changing application environments.

  The Descartes system marries a set of run-time profiling tools to a
profile-guided source-to-source specializer and an optimizing compiler for
the Scheme dialect of Lisp.  This yields on-the-fly identification and
specialization of performance-critical high-level program modules.
Preliminary experiments have demonstrated that a handful of carefully
chosen principled specializations can dramatically improve code speed with
only moderate profiling overhead and modest code-space growth.  For
example, profile-driven automatic optimization of a genetic pedigree
analysis program (a Bayesian belief network) has produced a speedup factor
of 5 over the original code produced by the MIT Scheme compiler. This was
achieved with less than a 2-fold increase in code size.

  In this talk, I will discuss how this system decides what code to
optimize, how it performs the optimizations, to what degree and at what
cost.