Re: How does one identify common subexpressions in a tree?

awerman@panix.com (Aaron Werman) writes:
>In a project that I am working on, much of the data comes in tree form
>where most of the data is duplicated many times over. It would
>tremendously simplify the task of analysing the data if common subtrees
>could be extracted.


I'd use some variation of value numbering, which accomplishes
common-subexpression elimination.


Basically, it would work bottom-up in your tree (or forest of trees).


Hash each leaf to detect common leaves, conceptually assigning each
distinct set of leaves a unique index (a value number).


Working bottom-up, examine interior (non-leaf nodes). All the children
should already have value numbers. Hash the node and all the children
(that is, their value numbers) to get a value number for the node. If the
tree node is already in the hash table, just use the old VN. If not
present, add it to the table and assign a new number.


When I build these, I usually just use pointers to hash-table entries for
value numbers.


When we use this for optimization in compilers, we also take advantage of
commutative operators. Additionally, care is required in the presence of
control flow.


Preston Briggs
--

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