Re: On-the-fly compilation from VM code to machine code

>>[Runtime code generation.]


danhicks@aol.com (DanHicks) writes:
>[RISC code optimization is time-consuming. Without register
> allocation and instruction scheduling, code is ~10X slower.
> Fast register allocation means loops will suffer and scheduling
> takes much longer.]


Although fully-general register allocation and scheduling takes as
long as, well, fully-general register allocation and scheduling, there
are several ways in which the problem can be narrowed enough to make
optmiization ``fast enough''.


  - The code that's being optimized will be reused so many times that
      the optimization cost can be large. I can construct cases in which
      I can generate C code and call GNU CC (which does lots of fork(),
      exec(), and so forth calls, lots of text munging, and so on) and
      the program is *still* faster than statically-compiled code. For
      large inputs.


  - The context of code generation is sufficiently constrained that a
      simpler algorithm does ``well enough''. That is, it matters most
      that the code is better than the statically-optimized code; if
      there are still missed optimizations that's too bad but may still
      be acceptable.


  - Where the general structure of the final code is known statically,
      much of the optimization is done statically. For example, the
      static compiler can produce ``large instruction'' templates
      [Henry87] that are concatenated at runtime. As above, it matters
      first that the code is faster than the static code, second that the
      optimizations are exploited fully.


Yes, with RTCG there is a fundamental conflict between generating good
code and generating code quickly. It doesn't seem to be fatal, though
[KEH93].


As for the specific task of compiling from VM code to machine code,
there are a variety of systems that compile from one machine
instruction set (possibly virtual) to another's, and some of them use
dynamic compilation quite successfully [CK94]. If anything, the task
of converting between real machine representations should be harder
because there's less high-level information. In practice, the best
static and dynamic transltors are competative with each other and can
run applications at a fair fraction of the native-compiled speed
[CK94].


Pardon me while I blow my own horn:


%L CK94
%A Bob Cmelik
%A David Keppel
%T Shade: A Fast Instruction-Set Simulator for Execution Profiling
%J Proceedings of the 1994 ACM SIGMETRICS Conference
on the Measurement and Modeling of Computer Systems
%D May 1994
%P 128-137


%L Henry87
%A Robert R. Henry
%T Code Generation by Table Lookup
%R 87-07-07
%I University of Washington Computer Science
%D 1987


%L KEH93
%A David Keppel
%A Susan J. Eggers
%A Robert R. Henry
%T Evaluating Runtime-Compiled Value-Specific Optimizations
%R UWCSE 93-11-02
%I University of Washington Department of Computer Science and
Engineering
%D November 1993


;-D on ( Virtuous Machine Code ) Pardo
--

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