On: Early Superoptimizer Results

[WalterBright]

I remember a paper on "Superoptimization" back in the 80's. It worked by starting with an algorithm, and doing an exhaustive search of every instruction sequence to see if the sequence implemented the algorithm. Of course, it only worked for very small algorithms, but it produced some very interesting results that were promptly incorporated into about every compiler.

[cokernel_hacker → WalterBright]

It was almost certainly "Superoptimizer -- A Look at the Smallest Program" [1], authored by the ingenious Dr. Massalin.

Dr. Massalin is also responsible for "The Synthesis Kernel" [2], a kernel written around the idea of wringing out performance.

Definitely worth a look for speed demon-type programmers like compiler engineers.

[1] http://www.stanford.edu/class/cs343/resources/superoptimizer... [2] https://www.usenix.org/legacy/publications/compsystems/1988/...

[wiml → WalterBright]

Might well have been the predecessor to or inspiration for GNU Superopt (which has been moribund for twenty years now...).