DAG pattern matching

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.


Chris Fraser
AT&T Bell Laboratories
cwf@research.att.com
--

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