IR Representation

=?UTF-8?B?Q8Opc2Fy?= <>
Fri, 4 Sep 2015 14:39:00 -0300

          From comp.compilers

Related articles
IR Representation (=?UTF-8?B?Q8Opc2Fy?=) (2015-09-04)
Re: IR Representation (2015-09-05)
Re: IR Representation (=?UTF-8?B?Q8Opc2Fy?=) (2015-09-07)
Re: IR Representation (2015-09-08)
Re: IR Representation (George Neuner) (2015-09-08)
Re: IR Representation (=?UTF-8?B?Q8Opc2Fy?=) (2015-09-11)
Re: IR Representation (Hans-Peter Diettrich) (2015-09-12)
| List of all articles for this month |

From: =?UTF-8?B?Q8Opc2Fy?= <>
Newsgroups: comp.compilers
Date: Fri, 4 Sep 2015 14:39:00 -0300
Organization: Compilers Central
Keywords: optimize, question
Posted-Date: 04 Sep 2015 16:44:31 EDT


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

- 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

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,

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.