Electronic Systems Design Seminar
http://embedded.eecs.berkeley.edu/esd-seminar

Abstract

In many programming applications, there are often small fragments of code which have a disproportionately large impact on overall performance. For such fragments, it is often the case that the code generated by the best available compiler is not adequately efficient. These code fragments are therefore often implemented directly in machine code, by skilled engineers who work hard to squeeze out the last ounce of performance from the target microprocessor. While this approach produces the required efficient code, it is an expensive use of a scarce resource (namely, the valuable time of the skilled engineer). The goal of the Denali project is to conserve this valuable resource, by building a tool that generates highly efficient code automatically, with little or no intervention from programmers.

Although automatic code generation has a long history, there has been little work on the problem of generating near-optimal machine code. The only comparable effort which we are aware of is Henry Massalin's "superoptimizer" (which later became the GNU superoptimizer) which uses a brute force approach to enumerate programs in order of increasing length. Since brute force does not scale, this approach works only for tiny programs. In contrast, Denali uses a more powerful technique, viz., the goal-directed search engine of an automatic theorem prover, and can tackle larger programs.

I shall describe the key idea underlying Denali and give a brief outline of the design of the current prototype. This prototype generates code for the Alpha EV6 microprocessor, and has been used to generate machine code programs of upto 30 instructions.