Path: csiph.com!au2pb.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!peer03.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end From: =?UTF-8?B?Q8Opc2Fy?= Newsgroups: comp.compilers Subject: Re: IR Representation Date: Mon, 7 Sep 2015 23:05:29 -0300 Organization: Compilers Central Lines: 69 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <15-09-010@comp.compilers> References: <15-09-005@comp.compilers> <15-09-006@comp.compilers> NNTP-Posting-Host: news.iecc.com Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Trace: miucha.iecc.com 1441682673 28127 2001:470:1f07:1126:0:676f:7373:6970 (8 Sep 2015 03:24:33 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Tue, 8 Sep 2015 03:24:33 +0000 (UTC) Keywords: optimize, design, comment Posted-Date: 07 Sep 2015 23:24:33 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com X-Received-Bytes: 3888 X-Received-Body-CRC: 2364126181 Xref: csiph.com comp.compilers:1605 Hi Anton, thank you for the answer. On Sat, Sep 5, 2015 at 1:51 PM, Anton Ertl wrote: > > =?UTF-8?B?Q8Opc2Fy?= 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; 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: > 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]