|DAG pattern matching email@example.com (Michael Werts) (1993-09-29)|
|DAG pattern matching firstname.lastname@example.org (1993-10-04)|
|Date:||Mon, 4 Oct 1993 16:30:00 GMT|
Michael Werts at Cal State Long Beach writes
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?
Todd Proebsting and I worked on this problem for a couple of months last
year and finally concluded that it was easier to undag the input (ie,
assign to temporaries those nodes with multiple references) and then to
eliminate those temporaries that don't pay off.
Consider the C statement "p->x=12;" when field x happens to be at offset
12. The node that develops the value 12 thus has two references. When
compiling for a machine like the MIPS R3000, one reference is a store
instruction that must have 12 in a register. The other reference is an
addressing mode that must have 12 in an immediate field. I never found a
satisfactory way to reconcile such conflicting demands on the fly. I
needed a simple solution -- I have to explain it in a book that Dave
Hanson and I are writing about lcc -- and all solutions were trashing my
otherwise satisfactory reducers.
Finally, I decided to undag completely before labelling and to tweak
iburg's labeller to allow each use of an undagging temporary to use the
temporary *or* to re-evaluate the expression stored in that temporary,
whichever costs less. If all references re-evaluate, then I delete the
assignment to the temporary.
If someone can adapt burg/iburg to dags *simply*, I'd like to hear about
it, but be warned that Todd and I regard this as a swamp and are glad to
be out of it. Worse, we attempted only tree patterns on dag input; one
really wants dag patterns on dag input, which seems even harder.
AT&T Bell Laboratories
Return to the
Search the comp.compilers archives again.