David Chase
dr2chase@mac.com

Education

Ph.D. Computer Science, 1988 (dissertation completed 8/87), Rice University, Houston. Committee: Ken Kennedy (chair), Richard Tapia, William Golson.
M.S. Computer Science, 1984, Rice University, Houston.
B.S. Electrical Engineering (cum laude), 1982, Rice University, Houston.
Completed degree requirements for B.A. Mathematical Science.

Experience
Sun Microsystems (Labs)
11/2003-present

Design and prototype implementation of Fortress. Includes advanced parsing, transactional memory, runtime representations of novel type systems, extreme concurrency, and the usual boring optimizations.

Design and implementation of a component-based system for building I/O virtualization devices.

As part of a distributed three-person team, designed and implemented BulletTrain, a Java bytecode-to-Pentium native static compiler, linker, compilation manager, runtime, and core set of libraries. Technical responsibilities included design and implementation of a pattern-matching code generator, calling conventions, interface to garbage collector, exception handling, threads, weak references, Java Native Interface, floating point libraries, modeling of JVM type system, and end-to-end testing and debugging. Also participated in design and implementation of check-removal optimizations, lock optimizations, register allocation, unsafe extensions, class data structures, and libraries. Additional responsibilities included web site design, business development, patent searches, and participation in standards meetings.

Designed runtime checking library and compiler/translator-inserted instrumentation for a C++ compiler/translator. Implemented runtime checking library. Also weathered mid-project mutation from C++ compiler-instrumenter into C++-to-C++ translator-instrumenter. Implemented live demo of this product for WWW use.

Improved speed of C* library functions, designed and implemented a driver configuration file to simplify compiler installation and linker invocation, ported CM Fortran vector unit code generation improvements into C* compiler, took over “global-local” programming tools, ported C* compiler sources to Ansi C. Worked on a design for machine-independent (high-level-language) back end for CM languages. Informally worked on C++ interfaces for MPP.

Designed and implemented machine-specific optimizations in a code generator for Sparc. Designed parts of 64-bit Sparc architecture and applications binary interface. Designed parts of run-time environment for C++.

Code generator: Implemented control flow analysis, including incremental update of intervals, dominator and post-dominator trees, for other portions of the code generator (register allocator, scheduler, pipeliner). Implemented “peephole” optimizations, SSA-based dead code elimination, code reordering transformations, constant instruction hoisting, base register detection, and many cases of code generation. Added support for execution profiling, position-independent code generation, thread-local storage, C volatile variables, tail calls, and windowless-routine tail calls. Implemented pattern-matching for branch removal.

64-bit Sparc: Defined and lobbied for prefetch and non-faulting-load instructions. Did bit-twiddling homework for 64-bit constant generation, and 64-bit multiplication and division instructions.

C++ run-time and 64-bit ABI: Lobbied for exception handling features in 64-bit ABI, and designed parts of exception-handling system, including interface with code generator, optimizer, and register allocator. Wrote example implementations of exception dispatcher and exception handler. Helped define new 64-bit calling conventions.

Designed and implemented C-generating backend and run-time system, including run-time type checks, exception handling, and a thread-safe garbage collector port, for portable Modula-3 on Unix and Mach. Consulted with design group on usefulness of i860 and proposed software standards. Ported Acorn C and Modula Execution Library to Sun UNIX for use with Acorn Modula-2+. Helped obtain, configure and install software needed to start work at the new lab.

Designed and implemented interpreters for FP84; studied problems with graph-reduction and equational rewriting for FP84.

Implemented portions (parser, flow analysis subroutines) of vectorizing Fortran translator. Designed and implemented portions of Rⁿ Fortran programming environment; work included AST-based parsers, unparsers, type-checkers, and interfaces for use in a syntax-directed editor. Teaching assistant (grading and tutorials) for algorithms and programming classes.

A practical improvement to the generation of compressed tables for tree pattern matching. This work was extended by Pelegri-Llopart to incorporate pattern selection based on costs to support Graham-Glanville style code generation, and has been applied to research and applications at the University of Washington, University of Wisconsin, NYU, Sun, and IBM.

This addressed the interaction, both good and bad, of garbage collection and code optimization, presented algorithms for inferring lifetime of linked data structures, and addressed other optimization issues related to memory allocation (optimization for time versus dynamic space consumption constraints).

This describes interactions between storage allocation optimization and bounded resources. Optimization can prolong the lifetime of dynamically allocated storage, leading to an unbounded (ratio) increase in memory use. Strategies for safe optimization are described.

Describes an incremental version of SSA-style data flow analysis adapted for use with linked data structures. Approximations of reference counting described here can be used to discover trees. This improves on results presented in my thesis.

Describes an engineering solution to use of a garbage collector with an uncooperative or minimally cooperative optimizer.

Survey of some exception handling implementation techniques for basic support of C++ exceptions, with discussion of normal-case efficiency, optimizer interaction, and linker interaction.

Interaction with debuggers and non-standard calling conventions. Support for asynchronous exception handling.

Careful use of assignments to “volatile” variables in C prevents most optimizers from hiding pointers from garbage collectors. Careful choice of variable names permits easy post-processing to remove the stores, thus avoiding the costs. The most likely hindrance to optimization is increased register pressure.

In the future, memory latency and mispredicted branch costs will play a large part in program (in)efficiency. SPARC Version 9 contains new instructions and architectural features to help optimizing compilers address these problems. These features include prefetch instructions, multiple condition codes, branch on register contents, non-faulting load instructions, additional floating point registers, and static branch prediction bits.