Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!newstop!exodus!rbbb.Eng.Sun.COM!chased
From: chased@rbbb.Eng.Sun.COM (David Chase)
Newsgroups: comp.arch
Subject: What the compiler CAN do for you
Message-ID: <8890@exodus.Eng.Sun.COM>
Date: 1 Mar 91 03:02:59 GMT
Sender: news@exodus.Eng.Sun.COM
Organization: Sun Microsystems, Mt. View, Ca.
Lines: 36

I thought, amid all the flaming, that I ought to add some useful
information.  What compilers CAN do, pretty easily (given recent
algorithms, some of which have semi-publicly available
implementations) is recognize patterns in trees.  This is no
substitute for all the other optimizations that are performed, but it
does add interesting possibilities to instruction selection.

The best patterns are those in which each "variable" appears only once
(e.g., "minus(plus(a,b),a)" depends on "a" appearing twice -- i.e.,
we're all wimps and don't do unification yet, usually, because, well,
it doesn't seem to be worth the effort).  DAGs are a pain, and graphs
containing cycles are also a pain.

There's various techniques, both top-down and bottom-up.  I know more
about bottom-up.  That technique recognizes the most general class of
patterns, and is quite efficient, but also runs the risk of impossibly
large tables.  (Very) recent work addresses problems of instruction
selection combined with scheduling and register management -- I do not
know the particulars here.

So, given this, if someone were designing a return-of-the-revenge-of-
CISC architecture, any ideas what it might look like?  One approach to
this problem might be one that was tried for APL -- identify a set of
100 idioms that "covers" 99% of most APL programs, and then target
each of those patterns with carefully thought-out code.  The resulting
instruction set might look horrible -- it probably does not contain a
"count set bits" instruction, but it might contain a
  "set condition code if *(R + C1) == C2"
instruction.

Probably, this is pointless -- the instructions so recognized would be
incredibly complicated and difficult to render efficiently/correctly
in your favorite semiconductor.  But, it's a thought.

David Chase
Sun