Re: Static vs. dynamic analysis

chuck_lins@gateway.qm.apple.com (Chuck Lins) writes:


      In theory, i could imagine a system where the compiler runs continuously
      receiving trace information on each routine as it runs. The compiler
      recompiles the routine based on the amortized the cost over the long run.
      But this is in theory; i doubt this would be very practical.


This is not just a theoretical possibility, it is already being done. For
example, there are systems that compile byte code into machine language
on-the-fly, and backpatching (as used in Smalltalk message dispatch)
constitutes a simple form of runtime code generation based on dynamic
program properties.


      I think the goal for static analysis is that it should be based on
      empirical evidence from real-world programs. Unfortunately, the
      hardware/compiler vendors having this information (eg IBM) keep it a
      closely guarded secret.


I believe that runtime code generation and runtime code optimization will
become very important in the not too distant future.


The kinds of decisions and optimizations we are talking about here are:


  * what sections of code benefit most from costly optimization?
  * what code needs to be inlined?
  * what is the most likely set of values (including type tags)
      to occur at a particular conditional?
  * what exceptions are likely to be taken?


A compiler can perhaps make informed guesses at compile time about some
kinds of dynamic properties of a program for limited classes of programs
(some limited kinds of numerical programs, database applications).
However, for my own programs, I know that in many cases, the kinds of
optimizations that a compiler would have to perform depend very much on
the exact input to the program.


I think it would be a nice (M.A., Ph.D.) project to prototype and
demonstrate the value of such techniques with a (mostly portable) dynamic
optimizer for CommonLisp; such a system would insert some extra code into
functions to keep simple statistics about function calls and runtime types
and generate type-specialized and inlined versions of functions as needed
(invoking the CommonLisp compiler on-the-fly). Any takers?


Thomas.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.