Path: csiph.com!au2pb.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end
From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Subject: Re: IR Representation
Date: Tue, 08 Sep 2015 07:49:21 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 49
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <15-09-011@comp.compilers>
References: <15-09-005@comp.compilers> <15-09-006@comp.compilers> <15-09-010@comp.compilers>
NNTP-Posting-Host: news.iecc.com
X-Trace: miucha.iecc.com 1441740720 97828 2001:470:1f07:1126:0:676f:7373:6970 (8 Sep 2015 19:32:00 GMT)
X-Complaints-To: abuse@iecc.com
NNTP-Posting-Date: Tue, 8 Sep 2015 19:32:00 +0000 (UTC)
Keywords: optimize, design
Posted-Date: 08 Sep 2015 15:32:00 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: csiph.com comp.compilers: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/