|subtree sharing firstname.lastname@example.org (1995-10-30)|
|From:||email@example.com (Claude Castelluccia)|
|Keywords:||optimize, question, comment|
|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 firstname.lastname@example.org
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
Search the comp.compilers archives again.