Ideas for a submission to PLDI `98

The submission deadline is 5pm CST November 7.

Priorities

What follows is a list of Things To Do for the submission. We need to prioritize the list, decide which subset to target for the submission, and which (slightly larger) subset to target for the final paper. Each of the things in the list (but not all of them!) could be finished by the deadline for the final paper, but not necessarily by the submission deadline.

  1. *Name for our system
  2. *Benchmarks
  3. *Regression tests
  4. *Instrumentation
  5. Features
  6. Optimizations
  7. Other Infrastructure

Other Paper Thoughts

Abstract

Here is a sample abstract that I wrote a few months ago. It has a weak slant, but no mention of contributions. Somebody munge it to make it better or replace it.

We previously presented the design of a dynamic compilation system for C [PEPM97]. The system requires the user to specify what code is to be dynamically compiled and leaves most of the key cost/benefit trade-offs open to user control through declarative annotatations. From these annotations our system automatically produces light-weight specialized dynamic compilers for annotated regions of the program. In this paper, we present results in applying the system to several real programs and reflect upon which functionality was required to obtain those results and to what degree we have succeeded in making dynamic compilation both fast and effective.

Introduction

What is DC; DC is cool

Dynamic Compilation, the generation and optimization of code at runtime, has received much attention recently as a means of transforming programs using information available at runtime. Proposed applications for this capability have included specializing architectural simulators for the configuration being simulated, language interpreters for the program being interpreted, numerical programs for dimensions and values of frequently used arrays, and critical paths in operating systems for the type of data being processed and the current state of the system. Trends in software engineering toward dynamic reconfigurability, parameterization for re-use and portability across hardware architecture all imply a promising role for dynamic compilation.

People have shown DC is viable, but not for big programs

Recent research efforts have made considerable progress towards proving the viability of dynamic compilation. In particular, researchers have demonstrated that run-time optimization overhead can be more than amortized quickly by the increased efficiency of the optimized code for many small, frequently used kernels. Existing techniques have, however, failed to demonstrate applicability on any existing applications of the size and complexity of the interpreters and simulators mentioned above. The underlying reason for the failure is the tradeoff between expressivity of the language interface for dynamic compilation and its ease of use:

This the new stuff we do

In this paper, we describe a declarative annotation-based system which:

  • Is expressive enough to exploit complex opportunities for dynamic compilation in large, realistic programs. The required expressiveness is significantly beyond that of existing annotation-based DC systems.
  • Requires only sparse annotations of existing statically compilable code, thereby eliminating the rewriting hurdle of existing imperative systems
  • Is based on a principled extension of traditional offline PE techniques to the online case, and
  • Produces code of quality comparable to that other existing systems at similar speeds.

    • This is how we do it, in a paragraph

    Summarize features (~list from PEPM paper intro):

    We can get speedups on reasonable inputs for _big_ programs

    We demonstrate the effectiveness of our approach by profitably applying dynamic compilation to javap, the bytecode interpreter for the Java programming language, and to MIPSI, an instruction-level simulator for the MIPS R3000. Translating the dynamically compiled regions of these programs (x and y lines of C) into an imperative language would clearly require a lengthy, painstaking effort by programmers using an imperative scheme. In contrast, we enable dynamic compilation of both systems by adding a few carefully selected annotations (x and y lines) to their C source code. We also identify the features of these applications that prevent existing annotation-based systems from optimizing them without substantial re-writing. (These applications are representative-- talk of other similar alluring ones!)

    JITs do much better than us; why? opportunities...

    Using java provides us the opportunity... The existence of hand-written "just-in-time" (and conventional) compilers for Java bytecode allows us to measure a few more data-points on the code-quality vs. compilation time curve.

    We do as well as other systems: not trading off expressivity/ease for speed

    The improved expressivity and ease of use of our system do not come at the expense of dynamically generated code quality or longer dynamic compile times. Though our current system is not configured for extremely aggressive run-time optimizations (we do not perform global optimizations such as register allocation or scheduling), we use a combination of cheap local optimization, extensive static global optimization of templates for dynamic code and customized code-generators to achieve speedups and code-generation costs comparable to those of other existing systems. We

    We will do much better, once our future work is done: microbenchmarks with proposed optimizations

    Show this (Brian's list):

    Summary of sections (important: what will be the order and content of sections?)

    Outline

    None yet. Anyone, anyone?


    Last updated September 26, 1997.
    Brian Grant (grant@cs.washington.edu)