Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1600 > unrolled thread

IR Representation

Back to article view | Back to comp.compilers

Contents

  IR Representation César <divcesar@gmail.com> - 2015-09-04 14:39 -0300
    Re: IR Representation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-05 16:51 +0000
      Re: IR Representation César <divcesar@gmail.com> - 2015-09-07 23:05 -0300
        Re: IR Representation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-08 07:49 +0000
          Re: IR Representation César <divcesar@gmail.com> - 2015-09-11 17:01 -0300
            Re: IR Representation Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2015-09-12 19:45 +0200
    Re: IR Representation George Neuner <gneuner2@comcast.net> - 2015-09-08 18:45 -0400

#1600 — IR Representation

Hi,

For learning purpose I am writing a compiler for a small subset of the C
language. I intend to implement a few simple optimizations in the IR and
also to support at least two target ISAs (x86-64 and some ARM). I would
also like to use a tree pattern matching Inst. Selection. However, I am
struggling on how to store/represent the IR.

Given the above objectives which way to represent the IR would be better? A
linear sequence of instructions or a tree? My thoughts on this are as
follow:

- I believe that a linear sequence of instructions would be easier to
optimize/analyze, right? 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...

- Currently, I intend to use a single, tree-like, IR since I can extract a
linear order from the tree and it suits well the instruction selection
algorithm.

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?

- Option (a) seems much simpler to create, but I believe the trees would be
very small, possibly degrading the efficiency of the tree pattern matching
instruction selection algorithm. [Currently, this is the format that I
intend to use.]

- I believe option (b) create the opportunity for matching larger patterns
and thus could improve performance. But there is a lot of redundant
nodes/code in this representation and it also seems harder to implement
than option (a).

I have read a few books/papers about these things but as you can see I
still have a lot of questions. I would really like to hear your comments
about the above topics!


Thank you,
CC)sar.

[toc] | [next] | [standalone]

#1601

=?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/

[toc] | [prev] | [next] | [standalone]

#1605

Hi Anton, thank you for the answer.

On Sat, Sep 5, 2015 at 1:51 PM, Anton Ertl
<anton@mips.complang.tuwien.ac.at> wrote:
>
> =?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?
>

This linear representation is really just an array of IR instructions,
something on these lines: vector<Instruction*>; As operands
instructions have pointers to entries in the symbol table.

As for optimizations I was planning to start with common sub. expr.
elimination, dead code elimination, loop-invariant code motion, etc.
and later on move to more complex optimizations.  I agree with you
that if I have the instructions stored in a stack it would be easy to
do. However, my initial understanding of linear was really an array of
instructions... and from that to construct a tree it seemed a little
complex, it seems like trying to reconstruct an AST from an assembly
stream of instructions.

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

I did not understand how can you represent the program using just a
single tree, because sometimes the computations are just
independent... What would be the a single tree for these programs:

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

or this one:

a = b + c;
d = e + f;

In my current implementation I represent both examples as set of trees
(a forest).

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

I think it's better if I come up with something simpler working first.
This seems to be a really good text. I'll read it. Thank you for the
link!
[You make it one tree by inventing a node type for a statement sequence,
either an N-ary one, or a bunch of (statement, next node) pairs.  As
he said, it's largely a matter of programming preference. -John]

[toc] | [prev] | [next] | [standalone]

#1606

>This linear representation is really just an array of IR instructions,
>something on these lines: vector<Instruction*>; As operands
>instructions have pointers to entries in the symbol table.

Sounds like quadruples.

>However, my initial understanding of linear was really an array of
>instructions... and from that to construct a tree it seemed a little
>complex, it seems like trying to reconstruct an AST from an assembly
>stream of instructions.

Creating a DAG from quadruples is easy: If you have an instruction

a = b+c

create a + tree node, with the tree nodes stored in b and c as
operands, and store a pointer to the resulting + node in a.

If you want trees instead of DAGs, a way to do it is to have a parent
count in each node, and if the parent count exceeds 1, create a store
node as parent of the multi-parent node, and use a reference to the
place where the result was stored as child of the node that would
otherwise be parents of the multi-parent node.

>I did not understand how can you represent the program using just a
>single tree, because sometimes the computations are just
>independent... What would be the a single tree for these programs:
>
>a = b[5];
>c = a + 1;
>d = a * c;
>e = a + a;

As our moderator writes, insert artificial nodes for connecting them.
E.g.,

s1 s2
 \ /
  ;  s3
   \ /
    ;

where s1, s2, s3 are the trees for the statements.

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

[toc] | [prev] | [next] | [standalone]

#1608

Thank you Anton [and John]. With the addition of an artificial node
everything made sense now.

Now I am wondering, how do you usually represent conditional nodes and
looping structures using trees?

Eg.:

       c = a + b;
       if c > 10 goto L1 else goto L2
L1:  a = 10;
       goto L3;
L2:  a = 20;
L3:


CC)sar.


On Tue, Sep 8, 2015 at 4:49 AM, Anton Ertl
<anton@mips.complang.tuwien.ac.at> wrote:
>>This linear representation is really just an array of IR instructions,
>>something on these lines: vector<Instruction*>; As operands
>>instructions have pointers to entries in the symbol table.
>
> Sounds like quadruples. ...

[toc] | [prev] | [next] | [standalone]

#1609

CC)sar schrieb:

> Now I am wondering, how do you usually represent conditional nodes and
> looping structures using trees?
>
> Eg.:
>
>        c = a + b;
>        if c > 10 goto L1 else goto L2
> L1:  a = 10;
>        goto L3;
> L2:  a = 20;
> L3:

The general representation of control flow forms *graphs*, not *trees*.

In your example control flow branches off in the "if" statement, into
two branches starting at L1 and L2 respectively, which happen to join
again at L3. You can consider each GOTO as a leaf in a tree, so that you
can convert the graph into trees. Then, in the case of well structured
code, L1 and L2 become child nodes of the "if" statement, and L3 will
become its sequential successor (right sibling), as L3 is the common
target reachable by both branches. The compiler can eliminate a GOTO
leaf and replace it by the tree of the GOTO target label, which then
indicates the next instruction during sequential execution. This process
continues until all trees have been merged into one big tree.

DoDi

[toc] | [prev] | [next] | [standalone]

#1607

On Fri, 4 Sep 2015 14:39:00 -0300, Cisar <divcesar@gmail.com> wrote:

>- I believe that a linear sequence of instructions would be easier to
>optimize/analyze, right?

Not necessarily.

Tree or dag forms tend to be better for analyzing control flow and for
rearranging code.   Dag forms are particularly good for finding common
subexpressions.  Linear forms tend to be better for analyzing data
dependencies, for scheduling, etc.

Some compilers use a hybrid IR where control flow is expressed as a
tree or dag in which the nodes are linear form basic blocks.

And, of course, you can use a linear IR as your basic form and, where
needed, create separate trees or dags which reference it.

George

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web