I have a few different trees, which resemble what the AST that compilers often deal with.

For example:

tree 1

( (a, b), (c, d) )

Imagine that each tree split represents the function "add", then tree 1 simply says: add a and b, then add c and d, in the end, add the sum of these 2 sums as the final result.

tree 2

( ( (a, b), (c, d) ), (e, f) )

obviously, I can merge tree 1 into tree 2, because tree 2 is simply constructed by adding a sibling (e, f) to tree 1.

By doing so, I don't need to re-visit a, b, c , d twice, I can simply add e and f, and add the result to the result of tree 1, to get the result of tree 2.

If I have a lot of these kind of trees, with overlapping (redundant sub-subtrees), is there an algorithm that can automatically create a graph that covers all the computation in the most efficient way ?

PS: all the trees share the same set of leaf,in this case, a b c d e f. Some trees are taller (deeper), some are shallower.

PS2: tree are not necessarily binary trees. A tree could have multiple

PS3: there could be a tree like ( (a,b), (g,h) ), i can still be partially merged with tree 1


Yes, this is sort of common subexpression elimination.

Simple approach for binary trees: introduce nodes 1 for a ... 6 for f.

Traverse your trees. When you have new pair like (1, 2) or (4, 5) introduce for them new nodes like 7 and 8, when you hit old pair, add edge from it.

You will need unordered map from pair of nodes to node, representing this pair:

(1, 2) -> 7
(3, 4) -> 8
(7, 8) -> 9

More on CSE avaliable by following links from wikipedia

If tree is not binary tree, first make it binary tree with first child / right sibling procedure. CSE in compilers most often is done on three-address code (like GIMPLE in GCC), i.e. on binary expressions only just because it is really more convenient


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.