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

Groups > comp.compilers > #1605

Re: IR Representation

Show all headers | View raw

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]

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web