David Chase


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.

Sun Microsystems (Labs)

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

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

NaturalBridge Inc. (
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.
CenterLine Software, Cambridge, Massachusetts
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.
Thinking Machines Corporation, Cambridge, Massachusetts
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.
Sun Microsystems, Mountain View, California.
Staff Engineer 1/92-10/93.
Member of Technical Staff 4, 4/90-1/92.
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.
Olivetti Research Center, Menlo Park, California.
Research Engineer, 9/87-2/90.
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.
IBM Research, San Jose, California.
Student Intern, 5/85-12/85.
Designed and implemented interpreters for FP84; studied problems with graph-reduction and equational rewriting for FP84.
Rice University, Houston, Texas.
Research Assistant, summers 1980 and 1981, 5/82-5/85.
Implemented portions (parser, flow analysis subroutines) of vectorizing Fortran translator. Designed and implemented portions of Rn 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.

Chase, “An Improvement to Bottom-up Pattern Matching”. ACM POPL, 1987.
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.
Chase, Garbage Collection and Other Optimizations. Dissertation, 1987.
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).
Chase, “Safety Considerations for Storage Allocation Optimizations”. ACM PLDI, 1988.
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.
Chase, Wegman, and Zadeck, “Analysis of Pointers and Structures”. ACM PLDI, 1990.
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.
Boehm and Chase, “A Proposal for Garbage-Collector-Safe C Compilation”. Journal of C Language Translation, December, 1992.
Describes an engineering solution to use of a garbage collector with an uncooperative or minimally cooperative optimizer.
Chase, “Implementation of Exception Handling (part one)” Journal of C Language Translation, June, 1994.
Survey of some exception handling implementation techniques for basic support of C++ exceptions, with discussion of normal-case efficiency, optimizer interaction, and linker interaction.
Chase, “Implementation of Exception Handling (part two)” Journal of C Language Translation, October, 1994.
Interaction with debuggers and non-standard calling conventions. Support for asynchronous exception handling.

“Portable optimizer-safe garbage collection”.
Modula-3 meeting, June 1992, Palo Alto, California.
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.
“Compilation and Optimization for SPARC Version 9”.
SPARC Version 9 Developer’s Conference, October 1992, Burlingame, California.
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.
“Static Single Assignment lecture”
Guest lecture at U Massachusetts class taught by Gary Pollice, Lowell, Mass., May, 1995.

Professional activities


Reviewer: Software Practice and Experience; Concurrency Practice and Experience; SIGPLAN PLDI Conference; ACM TOPLAS.

Provisional editor for the on-line garbage-collection-list Frequently Asked Questions (, FAQ at )