DAG pattern matching

Michael Werts <werts@csulb.edu>
Wed, 29 Sep 1993 21:55:23 GMT

          From comp.compilers

Related articles
DAG pattern matching werts@csulb.edu (Michael Werts) (1993-09-29)
DAG pattern matching cwf@research.att.com (1993-10-04)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Michael Werts <werts@csulb.edu>
Keywords: question, optimize
Organization: Cal State Long Beach
Date: Wed, 29 Sep 1993 21:55:23 GMT

I'm interested in adapting the tree pattern matching techniques used by
IBurg to work with dags like those used in lcc. I think the labelling
phase would be almost identical; one would just have to check for
previously labelled nodes while doing a depth-first traversal of the
graph. I'm less clear on how to correctly implement the reduction phase.
Is there any discussion in the literature on this?

Also would the code generated from a dag in this manner be better than
that generated from a tree representation? I understand that there is no
pretense of optimality when using the dag, but is the suboptimal dag code
going to be "better" than the optimal tree code in general?

And finally :) How does one go about writing the tree grammars that Iburg
and Burg use, especially with respect to assigning costs? The only thing
I've read along these lines is the BEG paper which suggested starting out
with all the trivial rules, just to ensure that the code generator will be

Thanks in advance.
MICHAEL WERTS -- werts@csulb.edu
Computer Engineering Computer Science
California State University Long Beach

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.