The "superoptimizer" is an invention of Dr. Henry Massalin. Basically, you take a real complete machine description at the register level (of course they exist -- how do you think they do instruction set simulations these days?) and exhaustively search for the shortest or fastest (your pick) program that performs a given task. Henry invented a number of smart tricks to speed up the search dramatically -- even so, more than about a dozen or 15 instructions and you will find yourself waiting an unacceptable period. However, for short sequences that need to have the hell optimized out of them its great -- it does wonders for inner loops in signal processing applications, for example. It has some big limitations -- you can't do pointer stuff, for example. However, its been of enormous help to Henry in real-world problems. I was under the impression that the technique was now well known (but not widely implemented). I suppose I was wrong on that. Henry's own implementations (all assembler and very fast) are unavailable, but the FSF distributes something called "Gnu Superopt" that performs a similar task -- since it does its work in C its a LOT slower. Jamie Lawrence says:
At 4:47 PM 07/07/94 +0100, Graham Toal wrote:
PS I dunno what superoptimisizer Perry is talking about but I've never heard of a real one that works. You have to feed in a complete machine description at register transfer level and i don't know if those exist for real machines; also the problem is almost certainly exponential time for a *guaranteed* solution as Perry claims is possible.
The only tool I have ever seen that created real results was a tool that caused more headaches than solutions. (Inside, proprietary tool, can't go into details) It only worked on its native platform and one could feed it up to about 4K of code to analyse.