Denali: A Goal-directed Superoptimizer

Rajeev Joshi
Greg Nelson
Keith H. Randall

2002 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'02)
Berlin, Germany, June 17 - 19, 2002.

[Full text in Postscript, 344KB]


This paper provides a preliminary report on a new research project that aims to construct a code generator that uses an automatic theorem prover to produce a very high-quality (in fact, nearly mathematically optimal) machine code for modern architectures. The code generator is not intended for use in an ordinary compiler, but is intended to be used for inner loops and critical subroutines in those cases where peak performance is required, no available compiler generates adequately efficient code, and where current engineering practice is to use hand-coded machine language. The paper describes the design of the superoptimizer, and presents some encouraging preliminary results.