DAG pattern matching

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
complete.


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

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