Re: optimizing compiler against average assembly programmer.

>>>>>>
Isn't there also something to say about the instruction sets? The 68K
has some tricky instructions so I do expect weird combinations to
output unexpected results, but what about more streamlined ISAs as
current typical CISCs ? Would the Superoptimizer really be useful on a
MIPS ?
<<<<<<


I went through the analysis of the SO a few years back. This is from
memory, but I seem to recall that the cost was a function of


(#inputs) X (

The actual SO program generates all possible programs of a given
sequence, determines if they compute the correct result, throws out
those programs that don't compute the correct result, and then
compares the results of those that do. If the function above is "f",
then the complexity is roughly O(f!); very bad indeed.


Note that "#machine instrs" is the number of possible machine
instructions. This includes all the possible combinations of operands
(e.g., a three-byte jmp instruction with a 2-byte displacement is
actually 65,536 instructions, not one instruction; ditto for loads
with immediate operands or memory offsets). This is why the original
super-optimizer didn't support memory operands or flow of control
instructions -- the combinatorial explosion was just too great.


As I recall, the MIPS architecture has oodles of 32-bit instructions
(over a billion?) so I doubt a "true" SO would be practical on MIPS.
Even if you eliminated the jmp and memory operand instructions, the
large number of registers on a typical RISC chip (especially ones with
three address instructions) produces an excessively large instruction
space to draw from.


While my memory concerning the analysis may be off, NP-Completeness
suggests that the best solution known today runs in O(2**n) time (pick
your n). SOs are useless for all but the most trivial of programs. I
did a simple computation about five years ago and figured out that a
typical "end of quarter" assignment I give in UCR's intro to
programming course would take longer than the known lifetime of the
Universe to optimize. Even the "Meaning of Life" took less time that
this to compute (at least, if you believe Douglas Adams :-).


please leave the SO out of the assembly vs. compilers arguments.
Unless we prove P=NP, SOs aren't even in the running.
Randy Hyde


P.S. BTW, to bring the argument to the same conclusion this thread
yields every time, the correct answer is "Yes, humans will always be
able to produce better code; but compilers will produce *good* code
in far less time."


See: http://webster.ucr.edu/Page_asm/GreatDebate.html
for more details.
--

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