From: pjones AT acs DOT bu DOT edu
Subject: Re: this is optimization?
To: mcastle AT umr DOT edu (Mike Castle)
Date: Fri, 14 Oct 1994 10:37:39 -0400 (EDT)
Cc: djgpp AT sun DOT soe DOT clarkson DOT edu

> Might try "gso" Gnu SuperOptimizer.  It was an attempt by someone
> to write an exhaustive optimizer that goes through every possible
> combination (or rather, reasonable combination) of op codes to
> see which should run fastest (and produce the same output,
> natch).  It's available as a standalone program last I saw, and
> not part of any compiler.  
> 
> Should be available on prep.ai.mit.edu, I suppose.  If not, try
> archie.  386 is one of the architectures it supports.  
> 
> Never used it myself, just heard about it.
> 
> Oh, it also only works on functions, no whole files, as it's time
> consuming.  From what I understand, anyway.

Yes, I once wrote one of these at Sun Labs for the SPARC, based on a 
"Superoptimizer" paper written by someone at Columbia University.  The
problem is, because of the (rather) exhaustive search, it is totally 
impractical for anything but short sequences of a few instructions.  In
this case, it can be used to find clever ways of finding, for example,
the absolute value.  Therefore, it couldn't be used to optimize even
functions of general programs.  Also, I don't think it would be reliable
for optimizing small windows of code within larger functions, because 
it would then be difficult to test all relavent initial states for the
correct output state (it would no longer just be an issue of one or
two inputs).

Peter Jones