johnson@cs.uiuc.edu (Ralph Johnson) (08/01/90)
David Chase argued that it was already known how to find instructions that
matched complicated patterns in the original program. I am familiar with
about half of the papers that he mentioned, so perhaps I am missing
something, but it was my understanding that these techniques were not very
good for matching instructions with loops in them, like block moves.
Further, the incompleteness of arithmetic says that it may not be possible to
canonicalize all input patterns. The tree matching techniques are very good
at finding complex addressing modes, but they are not the end-all and be-all
of code generation.
I would love to be proven wrong, because we have built our own code generator
(in Smalltalk, which is why we didn't use someone else's), and are always
looking for ways to improve it.
By the way, the GNU compilers use a pattern matching code generator. Also, I
agree that those who are interested in this area should take a look at Robert
Henry's UWCODEGEN.
Ralph Johnson - University of Illinois at Urbana-Champaign
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus| world}!esegue. Meta-mail to compilers-request@esegue.moss@cs.umass.edu (08/07/90)
I'm jumping into this thread without having seen what went before, and I'm
also at home so I can't use my bookshelf to double check my memory, but I seem
to recall that someone did a PhD thesis in the last ten years that indeed
could match patterns for rather complex instructions, though I am not sure
about loops (I do think it tried for block moves and such, so maybe loops are
included?). My recollection comes up with Rick Cattell's thesis, but I could
be wrong about that. Further comments? (And maybe I'll try to find his thesis
among my books when I'm next in my office ....) Eliot
--
J. Eliot B. Moss, Assistant Professor
Department of Computer and Information Science
Lederle Graduate Research Center
University of Massachusetts
Amherst, MA 01003
(413) 545-4206; Moss@cs.umass.edu
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus| world}!esegue. Meta-mail to compilers-request@esegue.pd@complex.Eng.Sun.COM (Peter C. Damron) (08/15/90)
I have been following with interest the postings on recognition of idioms/complex instructions. I have included a brief summary of the relevant discussion at the end of this posting. I have been working on a dissertation with Robert Henry from University of Washington. The tentative title is: "Code Generation for Complex Instructions using Graph Parsing" I can't really summarize the whole dissertation here, but let me try to cover a few salient points. Goal ---- Be able to recognize instances of "complex instructions" embedded in the intermediate representation of a source program. Where, complex instructions are things like "block copy", "string search", "polynomial evaluation", etc. Method ------ Use the program dependence graph (PDG) as the intermediate representation, thus bringing related computations into connected sub-graphs. Use a graph grammar to encode the computations of the complex instructions into graph patterns. Use graph parsing (or graph pattern matching) to find instances of pattern graphs (complex instructions) in a given subject PDG. Results and Comments -------------------- 1. Code Generation ------------------ It is possible to devise techniques to recognize instances of "complex instructions" and generator code for them. Historically, there have been a number of approaches to this problem. They can be roughly categorized as: A. Assembly language code B. Library routines (that get in-lined) C. Peephole or other special purpose optimizations D. Code generators Probably the most successful technique is to use library routines, and in-line them when appropriate. Peephole optimization techniques tend to be non-portable and difficult to develop or extend. Code generators have so far been limited to recognizing tree patterns (and DAG patterns to some degree). The tree patterns may be used to "encode" or describe arbitrarily large expressions (as noted by chased@Eng.Sun.COM (David Chase)). However, tree pattern matchers typically operate on ordered (as in left, then right) binary trees. One problem with this type of representation is the arbitrary order imposed on unordered operations (e.g. sequences of statements that are not dependent on each other). Perhaps tree pattern matchers can be extended to handle this problem. Another problem involves recognizing control flow (or dependence) constructs (as noted by johnson@cs.uiuc.edu (Ralph Johnson)). It does seem that structured control flow would be encodable into a tree form, but loops may still be a problem because of the associated data flow (or dependence). This causes the program representation to form a more general directed graph. It would be interesting to study further whether tree (or dag) based pattern matchers could be used to recognize instances of complex instructions in structured programs. I considered the more general problem of recognizing complex instructions in the presence of arbitrary control and data flow (really control and data dependence). The most relevant references that I know of are: %T Analyzing Exotic Instructions for a Retargetable Code Generator %A Thomas M. Morgan %A Lawrence A. Rowe %P 197-204 %J CCC82 (Sigplan Compiler Construction Conf.) %D 1982 %X This work develops techniques for transforming high-level language constructs into machine language constructs. Emphasis in on determining equivalence. Not really suitable for code generation. Summary of Morgan's dissertation work. %T Analysis Techniques for Exotic Machine Instructions and Their Use in Retargetable Compilers %A T. M. Morgan %R PhD Dissertation %I UCBCS %D JUN 1982 %A Lawrence Snyder %K larry %T Recognition and Selection of Idioms for Code Optimization %J ACTA %V 17 %P 327-348 %D 1982 %X This is basically a tree pattern matching algorithm for APL that uses dynamic programming to select patterns/idioms. A pre-cursor to later tree pattern matching work. 2. Use of the PDG ----------------- It is possible to use the program dependence graph as an intermediate representation, and generate code directly. Whether it is possible to optimize on the PDG is another question to which I think the answer is yes. After all, after flow analysis, all types of intermediate representations end up being dependence graphs. The only thing special about the PDG is that the dependence edges are more explicit, and control dependence is used instead of control flow. I would like to thank Karl Ottenstein from Los Alamos National Lab, and Tom Reps from Univ. of Wisconsin for providing front-ends to produce PDG's. 3. Graph Parsing and Graph Pattern Matching ------------------------------------------- It is possible to describe graphs as complex as PDG's using a (a new type of) graph grammar. It is possible to parse PDG's based on graph grammars of this type. However, graph parsing is pretty slow (worst case exponential for PDG graphs, in practice it looks like about n**2 as far out as I've tried). Also, graph parsers are quite difficult to describe, though the basic concepts of the construction are quite simple. Overall, this is not likely to be a useful technique for production compilers. Hope I wasn't too long winded, Peter. ---------------------------- Peter C. Damron Sun Microsystems, Inc. Advanced Languages, MS 12-40 2550 Garcia Ave. Mtn. View, CA 94043 pdamron@eng.sun.com ---------------------------- Well, let me see if I can summarize the discussion so far. It all started out with some discussion about implementing special functions efficiently. I believe that cik@l.cc.purdue.edu (Herman Rubin) was one of the one who suggested that nint() was a candidate for a function best written in assembler. Then ok@mudla.cs.mu.OZ (Richard O'Keefe) suggested the code: > double nint(double x) { > return ceil(x + 0.5) - (fmod(x*0.5 + 0.25, 1.0) != 0); > } Then, cik@l.cc.purdue.edu (Herman Rubin) comments: > I do not see how a compiler can recognize that the complicated body of code > can be replaced by a single instruction and make that substitution. One > could put that one in, but another will arise, and another. And these will > continue to crop up as long as the language primitives are restricted as > they now are. Now, chased@Eng.Sun.COM (David Chase) enters the picture with: > Sounds to me like another case of someone who hasn't done their homework. > Besides peephole optimization (mentioned by Preston Briggs), there's also > Graham-Glanville style code-generation, which has been adapted in recent > years to take advantage of improvements in tree-pattern matching... > > To make a long story short, you just write down the patterns, and ... > the tree-pattern-matcher generator spits out tables for you. > Find a new pattern, just add it to the list of patterns with a cost and code > generation rule, and you're set. There's a bit of additional work required > to canonicalize the input patterns (think of all the horrible ways that > > ceil(x + 0.5) - (fmod(x*0.5 + 0.25, 1.0) != 0) > > could be permuted), but similar transformations are already done to assist in > the recognition of loop-invariant and inductive computations (for example). > People have proposed optimizing APL in a similar fashion ... > > Do people build code generators like this today? Yes. Write to Robert > Henry, rrh@cs.washington.edu, and ask for UWCODEGEN. Then, johnson@cs.uiuc.edu (Ralph Johnson) points out: > David Chase argued that it was already known how to find instructions that > matched complicated patterns in the original program. I am familiar with > about half of the papers that he mentioned, so perhaps I am missing > something, but it was my understanding that these techniques were not very > good for matching instructions with loops in them, like block moves. > Further, the incompleteness of arithmetic says that it may not be possible to > canonicalize all input patterns. The tree matching techniques are very good > at finding complex addressing modes, but they are not the end-all and be-all > of code generation. > > By the way, the GNU compilers use a pattern matching code generator. Also, I > agree that those who are interested in this area should take a look at Robert > Henry's UWCODEGEN. Also, moss@cs.umass.edu (J. Eliot B. Moss) mentions: > ... I seem to recall that someone did a PhD thesis in the last ten years > that indeed could match patterns for rather complex instructions, though I > am not sure about loops (I do think it tried for block moves and such, so > maybe loops are included?). My recollection comes up with Rick Cattell's > thesis... Also of note is a comment by the moderator johnl@esegue.segue.boston.ma.us (John R. Levine) in response to a posting with a nice review intermediate representations by preston@rice.edu (Preston Briggs). > [Anybody tried program dependency graphs, per Ferrante et al. at IBM. From > the articles I've seen, they look pretty neat. -John] -- Send compilers articles to compilers@esegue.segue.boston.ma.us {ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.