Lambda the Ultimate

Nope. This is just a fixed-size peephole window.

The one problem I can see with this is that because it matches physical instructions rather than templates, it wouldn't work if you tried to apply peephole optimisation before register assignment, like VPO. Still, you could almost certainly use the idea of superoptimisation to generate peephole templates, at least in principle.

Sometimes you get lucky. If the guess was wrong (through performance analysis of the optimized code segment), try again and filter out similar matching rules to prune your 'guess list'. Then try again; optimizers are not supposed to be fast (performance wise), just make code run faster...

Who cares if I run my optimizer when I leave at night to get the results when I get to work the next day? How about on every binary on my system?

This would require feedback on performance improvements back into the database to help with the tree/'guess list' pruning. The database does not (and should not) be constant but a bit 'self aware' as to if what it is doing is helping with what it's supposed to do.

Blindly optimizing is no better than being the root of all evil (as Knuth might say).

The problem is that the complexity of the search can be exponential in the number of rules. Assume that you have n rules, if the rewrite system is confluent then you can try them in any order, so you will only need n attempts. In this case increasing the number of rules from 10s of handwritten rules to millions of generated rules would result in a night of number crunching to optimise the program.

If the system that they've generated is not confluent then you have to worry about phase ordering. So now the optimisation process will be O(2^n) and that night of number-crunching has just turned into thousands of years...

The cost of an optimization matters, whether it be an optimalization or merely an amelioration. It's a simple economic formula:

total_expected_savings = s * n - c
   where 
       s = average_savings_per_run
       n = expected_number_of_runs 
       c = cost_of_optimization

Now, this formula is fraught with difficulty in the case of recursive code, but limiting the discussion to peephole optimization drastically simplifies things.

Optimizations that pay for themselves in just a few runs are the most attractive, and indeed, some of these have even been implemented in hardware on high-end CPUs. Examples of this approach includes Digital's FX!32, Hewlett Packard's Dynamo for PA-RISC, Intel's Pentium Pro, and Transmeta's Crusoe, some more successful, others less.

(The Pentium Pro has even outlived it's younger Pentium-4 cousin, thanks to being brought back with the Core 2.)

Also, when dealing with higher-level languages, don't underestimate the advantage fast-running optimizer! You can test the performance of your code quickly, then tweak it to run faster, and rinse and repeat. The quicker the turnaround of the compiler, the more repetitions of hand-optimization programmer will do, ultimately creating sort of a hybrid human-computer optimizer.

And no, running code through an interpreter (or less-optimizing compiler) isn't as good. It's easy to start hand-optimizing code for the interpreter instead of the compiler.

The best programmers have a good, approximate understanding their language's implementation. This knowledge is indispensable for writing code that is short, readable, and fast. They will learn how to write cleaner code without sacrificing speed by putting the compiler to work for them.

As a side-effect of reaching this level of sophistication, these programmers will probably waste less time with hand-optimizations that contribute more code ugliness than speed, and instead focus their efforts on the changes that really pay off.