Path: csiph.com!au2pb.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!news.misty.com!news.iecc.com!.POSTED!nerds-end From: anton@mips.complang.tuwien.ac.at (Anton Ertl) Newsgroups: comp.compilers Subject: Re: IR Representation Date: Sat, 05 Sep 2015 16:51:15 GMT Organization: Institut fuer Computersprachen, Technische Universitaet Wien Lines: 79 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <15-09-006@comp.compilers> References: <15-09-005@comp.compilers> NNTP-Posting-Host: news.iecc.com X-Trace: miucha.iecc.com 1441571007 334 2001:470:1f07:1126:0:676f:7373:6970 (6 Sep 2015 20:23:27 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Sun, 6 Sep 2015 20:23:27 +0000 (UTC) Keywords: optimize, design Posted-Date: 06 Sep 2015 16:23:27 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:1601 =?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? > 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: - anton -- M. Anton Ertl anton@mips.complang.tuwien.ac.at http://www.complang.tuwien.ac.at/anton/