Re: [?] Trees vs. Tuples for IRs

>> What are the pros and cons of using trees versus tuples for a
>> compiler's intermediete representation?


Generally, when I use trees for an IR, I wish I were using tuples, and
vice versa. But I believe that tuples have an edge when developing an
optimizing compiler, for several reasons.


First, the final program is going to be a sequential list of machine
instructions. If you use basic blocks of tuples, you may be able to
design a single IR for your target machine that can represent the
input to the optimizer, the output of the code generator, and all
stages in between. Having fewer IRs in a compiler lends itself to
reliability and speed. You can't do this for all machines, but it's
nice when it's possible.


Second, when doing data dependence analysis, your focus will more
naturally be on the dependences between memory references rather than
statements. Your "statement splitting" will already have been done.


Third, your compiler is likely to be faster, simply because you'll be
traversing arrays or lists with iterative loops rather than trees with
recursive functions. Real compilers are real programs, and the choice
of an IR always involves issues of memory management. How you
allocate, insert, delete, and copy your text will significantly affect
the speed of compilation.


A related issue is that of the representation of data flow between
operations. The choice is between using explicit "compiler temps" to
link operations, or using the position (address, or tuple index, or
whatever) of an operation to denote its result. There are complex
tradeoffs between the two approaches.
--

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