Re: [?] Trees vs. Tuples for IRs

Chris Clark USG <clark@quarry.zk3.dec.com> writes:
>> What are the pros and cons of using trees versus tuples for a
>> compiler's intermediete representation?
>
>Okay, there are fixed a-rity tuples and n-ary tuples. Most people
>when talking about tuples mean fixed arity ones, so I'll discuss them
>also.


<SNIP - a nice introduction expurgated for brevity>


One other thought about tuples and trees is that people often think of
tuples only in the context of expresisons and basic blocks, while a
tree can imply an AST consisting of all the control flow information
at the source language level. But a tree and a tuple represenation
can be equivalent for representing the full AST if you define tree
node types for FOR, WHILE, etc. as well as the usual ADD, LOAD, and so
forth. You could do the same with tuples, letting you represent your
AST in either tree or tuple form.


If you think of a limited binary (or n-ary) tree, you can convert it
to tuples, as Chris Clark pointed out. Tuples can represent DAGS (or
any graph) as well as trees, so the tuples may be more expressive
(e.g. for common subexpression factoring, a la dragon book) that plain
binary trees.


The two representaions (tuples and DAGs)can be pretty much considered
equivalent from a theoretical point, it's mostly implementation
concerns that determine what is best for you. Something like a
forward pass and a reverse over a basic clock of tuples can be pretty
much accomplished by a tree traversal, generating inherited and
synthesised attributes.


Hope this helps a bit,


- Kenn
-----------------------------------------------
Kenn Heinrich
OS/2 guy, hardware designer, and proud of it!
--

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