dynamic compilation/optimization II

[uicbert.eecs.uic.edu!wilson@uxc.cso.uiuc.edu]

(Please excuse if this redunds;  I tried to post it before, but it didn't 
appear to make it.)

There seems to be some interest out there, so here's a bit more detail
on those dynamic compilation ideas:

*  When a chunk of code is dynamically compiled (not optimized yet), it
   is given a little prologue that increments a count every time it is
   executed.  When the count exceeds a threshold, the code is recompiled
   with a much higher level of optimization.  The most optimized code
   would not have this prologue to slow it down, since it wouldn't
   need it anymore.  Highly optimized code might be less subject
   to being discarded as well.

*  The business about noticing common types of arguments and compiling
   specially optimized versions could be handled similarly.  A little
   prologue would check every nth execution for types, rather than
   every execution.  Most times, it would just increment a counter.
   Very highly optimized code could forego the checking and counting
   entirely, assuming it had already learned all of the likely argument
   type combinations.  (Actually, every nth time it would change n
   a little to avoid rhythmic problems.)

*  Something like this might also be useful for trace scheduling.
   Every now and then you execute an "instrumented" version of the
   code that collects data on common execution patterns.

Any comments?  Does anybody know of any systems that use dynamic
compilation?  I know a couple of Smalltalks do it, and now
I'm told that MIT Scheme has a somewhat  similar cache-with-
dependencies mechanism for variable lookups.

Does anybody have any opinions on the expected efficiency of such a system?
It seems to me that it could be quite good.  It could also be advantageous
in that it would not optimize a lot of the code.  In particular, it could
keep things in a more debuggable form than something that optimizes
more stupidly, without much performance penalty.  (Especially since
frequently modified things will never get heaviliy optimized.)

I only have a few references on dynamic compilation, none of which go into
anything advanced.  If you have others, please send them to me and I'll
pass them on to interested parties.

(Besides the ones in Andy Gordon's posting, there was "An Evaluation
of Throw-away Compiling" in Software Practice and Experience, vol. 13
(1983), pp. 241-249.)

I have not gotten any responses indicating that dynamic compilation has
been used to control levels of optimization or to recompile when
optimizer assumptions are violated.


Paul R. Wilson                         
Human-Computer Interaction Laboratory
U. of Illin. at C. EECS Dept. (M/C 154)   wilson%uicbert@uxc.cso.uiuc.edu
Box 4348   Chicago,IL 60680