Re: IR Representation

=?UTF-8?B?Q8Opc2Fy?= <divcesar@gmail.com> writes:
>- I believe that a linear sequence of instructions would be easier to
>optimize/analyze, right?


What kind of linear representation do you have in mind? And what
optimizations?


> However, a tree seems better given that I want to
>use a tree pattern matching instruction selection.
>
>- I could use a linear representation for optimization and later convert
>the IR to a tree-like format before instruction selection. However, this
>conversion seems not so easy...


It's pretty easy from a quadruple or stack representation. For both,
the IR nodes are also tree nodes; for quadruples, the pseudo-registers
are the edges, while for a stack representation the stack items are
the edges. If you get a node with multiple parents, you can cut the
edges from this node to the parent and replace it with a
pseudo-register node in the parents. Example:


Source;


a = b[5];
c = a+1;
d = a*c;


Looks pretty much the same as quadruple code. As stack code:


b 5 .[.] dup 1 + *


As graph (with the root at the bottom)


  b 5
  |/
.[.] (->a)
|\ 1
| \ /
| + (->c)
\ /
  * (->d)


Broken into trees:


  b 5
  |/
.[.] (->a)


    a 1
      \ /
a + (->c)
  \ /
    * (->d)


>Besides, I have a question about storing the IR as a tree. Should I
>(a) create an individual tree for each expression/statement in the
>source or (b) should I create a single tree concatenating the trees
>for each expression?


Whatever suits your purpose. My students often create a tree for the
whole program, but for the task I give them I recommend doing just a
tree for each simple statement, because the tree-parsing instruction
selection that they use is not useful for combining tree nodes at a
higher level (AST nodes for function definitions and such); so when
they have a tree for the whole program, they just have to write
tree-parsing rules for all these nodes without any benefit from
tree-parsing.


You can also have data-flow graphs for whole basic blocks or more (but
that's not directly derived from the abstract syntax tree like my
students are using). If you want to go in that direction, I recommend
reading Marc Brandis' thesis:
<ftp://ftp.inf.ethz.ch/doc/diss/th11024.ps.gz>


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

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