chased@rbbb.Eng.Sun.COM (David Chase) (03/01/91)
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
kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) (03/01/91)
In article <8890@exodus.Eng.Sun.COM> chased@rbbb.Eng.Sun.COM (David Chase) writes: >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 Why resort to idioms? One of the things I tried when I was young(er) and brash(er) was making a more-or-less gp theorem prover (with a few bb heuristics thrown in) generate code for simple register-oriented machines. The idea was, if this is getting a bit unclear, to write each machine-level construct as an `axiom' and try to prove an hll program as a `theorem'. (If you think it's crazy, you're in good company -- a logician I explained it to at the time didn't seem to like the idea either). The big problem was finding a convenient notation for the `axioms' and `theorem' (and would conceptually sit somewhere between these two). Try expressing the semantics of jumps in predicate logic! (It can be done in several ways). Although this typically ran orders of magnitude (at LEAST) slower than the (then) worst (alternatively, read `best') optimizing compilers the approach looked promising for the days when clock cycles might drop below 500 ns and machines might cost less than 100k. -kym p.s. The tp did use unification and there's several very cheap but little-known algorithms for dealing with cycles.
kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) (03/01/91)
In article <1991Mar1.042434.9601@bingvaxu.cc.binghamton.edu> kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) writes: >Why resort to idioms? To answer my own question -- I guess if I called them `lemmas' the use of some commonly-occuring patterns in a given programming language is obvious. Such lemmas _could_ be generated automatically (although non-trivially I think) given some basic stats from a structure-oriented editor and the language grammar. -kym