Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!pasteur!ames!claris!apple!oracle!hqpyr1!csimmons
From: csimmons@hqpyr1.oracle.UUCP (Charles Simmons)
Newsgroups: comp.arch
Subject: Re: quest for breakthroughs (long)
Message-ID: <671@oracle.oracle.com>
Date: 20 Feb 89 20:46:59 GMT
References: <740@tetons.UUCP> <76700068@p.cs.uiuc.edu>
Sender: news@oracle.com
Reply-To: csimmons@oracle.UUCP (Charles Simmons)
Organization: Oracle Corporation, Belmont CA
Lines: 68

In article <76700068@p.cs.uiuc.edu> gillies@p.cs.uiuc.edu writes:
>
>/* Written 10:01 am  Feb 15, 1989 by colwell@mfci.UUCP in p.cs.uiuc.edu:comp.arch */
>> Nah, at that low a level, you could do what Henry Massalin did with
>> the "Superoptimizer" he built at Columbia (ASPLOS-II proceedings).
>> (His program tried every instruction sequence combination up to 
>> sequences of several instructions to find the ones that computed a
>> given function the quickest, including use of side-effects and
>> bizarre uses for carry bits and the like.  Fascinating experiment.)
>
>That's precisely the article I was thinking about when I originally
>thought of the problem -- I should have mentioned this.  Are there
>architectures where combinatorial search can be used for practical
>compilation?  Are these architectures useful?

Somewhat related:  I recently had the pleasure of porting about
300 instructions of 68020 assembler to the MIPS processor.  I took the
68020 algorithm and translated it into C.  I then had the MIPS
compiler compile the C code.  With the exception of 2 instructions,
the output of the MIPS compiler was exactly what I would have
written if I had been writing in assembler.

My conclusion is that for an elegant architechture, such as the R2000,
combinatorial searches won't buy you much.  On less elegant
architechtures, such as the 680x0 and 80x86, there are a sufficient
number of special cases that a combinatorial search can find cute
code sequences.  (Alternatively, the R2000 instruction set has very few
instructions that aren't easily accessible from C.  The 680x0 and 80x86
have numerous instructions that aren't accessible from C.  For example,
C compilers normally won't generate rotate instructions.  The 'bfffo'
instruction on the 68020 also tends to be inaccessible to compilers.)

Contrariwise, if you do have a problem on which you want to perform
a combinatorial search, since the R2000 has far fewer special cases
than, say, the 68020, the combinatorial search won't explode quite
so quickly.  It will also be relatively easy to decide when one sequence
of instructions is more optimal than another.

(One of my favorite puzzles:  You have two 32-bit registers
containing some pattern of bits.  The most significant bit of a register
is numbered "0".  You want to move bits 0, 2, 4, and 16 from the
first register, and bit 0 of the second register into some subset
of the low-order eight bits of some register.  The high-order 24 bits
of the destination register must end up as zero.  The three bits in
the low-order byte of the destination register which are not copies
of the five bits of interest may have any value at all.)

(The places where the MIPS compiler didn't produce optimal
code were generated by source of the form:

	register unsigned long a, b, c;
	c &= ~(a | b);

Clearly, we would like for this to generate the code:

	nor $temp, $a, $b
	and $c, $c, $temp

The actual code generated was:

	or $temp, $a, $b
	nor $temp, $temp, $0
	and $c, $c, $temp

Since the 'nor' instruction doesn't directly map into the C language,
I didn't really expect the compiler to handle this minor special case.)

-- Chuck