Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!uxc!uxc.cso.uiuc.edu!m.cs.uiuc.edu!p.cs.uiuc.edu!gillies
From: gillies@p.cs.uiuc.edu
Newsgroups: comp.arch
Subject: Re: quest for breakthroughs (long)
Message-ID: <76700068@p.cs.uiuc.edu>
Date: 17 Feb 89 23:33:00 GMT
References: <740@tetons.UUCP>
Lines: 34
Nf-ID: #R:tetons.UUCP:740:p.cs.uiuc.edu:76700068:000:1713
Nf-From: p.cs.uiuc.edu!gillies    Feb 17 17:33:00 1989


/* 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?

> But you could micro-optimize the entire program and still end up with slower
> code than a handcoder or a good compiler for various reasons.....because
> of various reasons.....

I think you need an appropriate definition of "compilation".  You
can't expect the compiler to go off and implement new algorithms.  You
cannot assume there is a library of compiled subroutines.

You might be able to define an optimal compilation as one where every
state of the "important" state variables in the source (programming)
language, is also represented somewhere at some time in the target
(assembly) language program, during its execution.

Under this definition, code transformations are not allowed to remove
redundant code, but they are allowed to combine redundant
computations...

You also must enforce a space-time tradeoff, so the compiler doesn't
just precompute everything and use a lookup table.  The ASPLOS paper
required the programs to be as short as possible.