subtree sharing

Hi,


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.


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        Claude Castelluccia castelluccia@sophia.inria.fr


        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]
--

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