Superoptimizer (was Re: Folk Theorem ...)

Dave Gillespie <synaptx!thymus!daveg@uunet.UU.NET> writes:


      This thread seems short on concrete examples, so here are a few from my
      personal experience:


      * There will always be things no compiler writer will think of.


Are you so sure? There is a program called superoptimizer, which does the
trick (for short sequences!) I cannot imagine that any human would come up
with the same tricks that this program came up by searching all possible
code combinations by executing them on the spot and comparing results. It
would construct all one instruction sequences, then all two instruction
sequences, etc. The original idea comes from Henry Massalin of Columbia
University, and there is now a GNU version available also.


References:


Henry Massalin, "Superoptimizer -- A Look at the Smallest Program", ACM,
1/1987 (my copies don't say the publication, but I would suspect SIGPLAN)


a paper in the 1992 ACM SIGPLAN conference on Programming Language Design
and Implementation, about "the GNU superoptimizer and its application in
GCC"


The README in the GNU superopt package, available from isy.liu.se via
anonymous ftp in /pub/gnu/superopt-2.3.tar.gz


>From the README file:
<quote>
GNU SUPEROPTIMIZER


The superoptimizer is a function sequence generator that uses a exhaustive
generate-and-test approach to find the shortest instruction sequence for a
given function. You have to tell the superoptimizer which function and
which CPU you want to get code for, and how many instructions you can
accept.


The superoptimizer can't generate very long sequences, unless you have a
very fast computer or very much spare time. The time complexity of the
used algorithm is approximately


2 n
O(m n )


where m is the number of available instructions on the architecture and n
is the shortest sequence for the goal function.


The superoptimizer can't guarantee that it finds the best possible
instruction sequences for all possible functions. For example, it doesn't
even try to include immediate constants (other that -1, 0, +1, and the
smallest negative and biggest positive numbers) in the sequences. It
often makes a good job for functions that depend on registers only.


WARNING! The generated sequences might be incorrect with a very small
probability. Always make sure a sequence is correct before using it. So
far, I have never discovered any incorrect sequences. If you find one,
please let me know about it!




OPTIONS


The `-f' option has always to be defined to tell the superoptimizer for
which function it should try to to find an instruction sequence. See
below for possible function names.


Option names may be abbreviated.


-assembler
Output assembler suitable to feed /bin/as instead of pseudo-code
suitable for humans.


-max-cost n
Limit the `cost' of the instruction sequence to n. May be used to
stop the search if no instruction sequence of that length or
shorter is found. By default this is 5.


-extra-cost n
Search for sequences n more expensive than the cheapest found
sequence. Default is 0 meaning that only the cheapest sequence(s)
are printed.


-no-carry-insns
Don't use instructions that use the carry flag. This might be
desirable on RISCs to simplify instruction scheduling.


-f<goal-function-name>


where <goal-function-name> is one of eq, ne, les, ges, lts, gts,
leu, geu, ltu, gtu, eq0, ne0, les0, ges0, lts0, gts0, neq, nne,
nles, nges, nlts, ngts, nleu, ngeu, nltu, ngtu, neq0, nne0, nles0,
nges0, nlts0, ngts0, maxs, mins, maxu, minu, sgn, abs, nabs, gray,
or gray2, etc, etc.


eq, ne, les, etc, computes the C expression "a == b", "a != b", "a
<= b", etc, where the operation codes ending in `s' indicates
signed comparison; `u` indicates unsigned comparison.


eq0,... computes "a == 0", ...


The `n' before the names means that the corresponding function
value is negated, e.g. nlt is the C expression "-(a < b)".


maxs, mins, maxu, minu are binary (i.e. two argument) signed
respectively unsigned max and min.


sgn is the unary sign function; -1 for negative, 0 for zero, and +1
for positive arguments.


abs and nabs are absolute value and negative absolute value,
respectively.


For a complete list of goal function and their definitions, look in
the file goal.def. You can easily add your own goal functions to
that file.




READING SUPEROPTIMIZER OUTPUT


The superoptimizer by default outputs sequences in high-level language like
syntax. For example, this is the output for M88000/abs:


1: r1:=arith_shift_right(r0,0x1f)
r2:=add_co(r1,r0)
r3:=xor(r2,r1)
2: r1:=arith_shift_right(r0,0x1f)
r2:=add(r1,r0)
r3:=xor(r2,r1)
3: r1:=arith_shift_right(r0,0x1f)
r2:=xor(r1,r0)
r3:=adc_co(r2,r1)


r1:=arith_shift_right(r0,0x1f) means "shift r0 right 31 steps
arithmetically and put the result in r1". add_co is "add and set carry".
adc_co is the subtraction instruction found on most RISCs, i.e. "add with
complement and set carry". This may seem dumb, but there is an important
difference in the way carry is set after an addition-with-complement and a
subtraction. The suffixes "_ci" and "_cio" means respectively that carry
is input but not affected, and that carry is both input and generated.


The interesting value is always the value computed by the last instruction.
...
The GNU superoptimizer and its application in GCC are described in the
proceedings of the ACM SIGPLAN conference on Programming Language Design
an Implementation, 1992.


<end of quote>


mike
--


Michael Gschwind, Institut fuer Technische Informatik, TU Wien
snail: Treitlstrasse 3-182-2 || A-1040 Wien || Austria
email: mike@vlsivie.tuwien.ac.at
phone: +(43)(1)58801 8156 fax: +(43)(1)569 697
--

Return to the comp.compilers page.
Search the comp.compilers archives again.