Re: [?] Trees vs. Tuples for IRs (Kenn Heinrich)
19 Sep 1998 21:20:00 -0400

          From comp.compilers

Related articles
[?] Trees vs. Tuples for IRs (Nick Shaffner) (1998-09-13)
Re: [?] Trees vs. Tuples for IRs (Chris Clark USG) (1998-09-18)
Re: [?] Trees vs. Tuples for IRs (1998-09-18)
Re: [?] Trees vs. Tuples for IRs (1998-09-19)
Re: [?] Trees vs. Tuples for IRs (Clifford Click) (1998-09-22)
Re: [?] Trees vs. Tuples for IRs (William D Clinger) (1998-09-26)
Re: [?] Trees vs. Tuples for IRs (Peter Klausler) (1998-09-26)
| List of all articles for this month |

From: (Kenn Heinrich)
Newsgroups: comp.compilers
Date: 19 Sep 1998 21:20:00 -0400
Organization: none
References: 98-09-042 98-09-058
Keywords: design

Chris Clark USG <> 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

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

Post a followup to this message

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