subtree sharing (Claude Castelluccia)
Mon, 30 Oct 1995 14:33:36 GMT

          From comp.compilers

Related articles
subtree sharing (1995-10-30)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Claude Castelluccia)
Keywords: optimize, question, comment
Organization: Compilers Central
Date: Mon, 30 Oct 1995 14:33:36 GMT


I am writing a code generator which generates a "C" code from an
internal representation generated by a synchronous language. This
internal representation has a Tree structure. As a result, there are
a lot of identical branches and subtrees and the generated code can
be very large. I am looking for algorithms that can find the
similarities in the trees and avoid the code duplication by sharing
the identical subtrees or branches. Where can I find such algo.? Any
pointers would be welcome!

Also do you know of any algo. that can identify almost-identical
subtrees? By almost-identical, I mean that the subtrees are identical
except from 1 or 2 elements.

Given a tree representation, is it possible to find the
representation that will lead to the smallest code size? Is that
problem NP-complete? My concern is the code size, I am not concerned
by the performance of the code!

Thanks a lot for your help!


        Claude Castelluccia

        INRIA -- Projet RODEO
        B.P. 93, 06902 Sophia-Antipolis Cedex FRANCE
        Tel: +33 93 65 78 09
[Finding common subexpressions while building a parse tree is a standard
optimization covered in books and is not very hard -- you keep track of the
subtrees as you build them. -John]

Post a followup to this message

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