Path: csiph.com!au2pb.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!border2.nntp.dca1.giganews.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end From: =?UTF-8?B?Q8Opc2Fy?= Newsgroups: comp.compilers Subject: IR Representation Date: Fri, 4 Sep 2015 14:39:00 -0300 Organization: Compilers Central Lines: 46 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <15-09-005@comp.compilers> NNTP-Posting-Host: news.iecc.com Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" X-Trace: miucha.iecc.com 1441399471 33523 2001:470:1f07:1126:0:676f:7373:6970 (4 Sep 2015 20:44:31 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Fri, 4 Sep 2015 20:44:31 +0000 (UTC) Keywords: optimize, question Posted-Date: 04 Sep 2015 16:44:31 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:1600 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.