Superoptimizer

[Torbjorn Granlund]

There is now a general higher-level "superoptimizer" available from
the swox.com/gmp/devel/ area.  Using it, I successfully optimized the
toom evaluation code.  The evaluation code was messy before; now it is
totally incomprehensible.  :-)

The old superoptimizer (ftp://ftp.gnu.org/pub/gnu/superopt/) took an
n->1 function and generated assembly code for it (for x86, sparc,
alpha, etc).

The new superoptimizer takes an m->n function and generates the
cheapest sequences of plain mathematical operations implementing the
function.  I have thus far succeeded in generating sequences for
functions requiring up to 10 operation long sequences, but I expect it
can generate sequences of up to perhaps 14 operations.  These long
sequences are achieved with early pruning (when k more operations are
to be generated, require that <= than k goal values remain to
synthesize, since one operation can generate at most one goal value)
and by sequence canonicalization.

The cost is very dependent on the arity of the goal function, both m
and n.

The search is a purely numerical exercise; there is no symbol
manipulation going on.  I suppose that one should prove the sequences
correct with some symbol manipulation, but I haven't implemented that.
The superoptimizer can check one possible sequence every clock cycle
thanks to the cheapness of just computing numerically.

http://swox.com/gmp/devel/superopt-va.c
http://swox.com/gmp/devel/goal-va.def

-- 
Torbjörn