IR Representation

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	César <divcesar@gmail.com>
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> (permalink)
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

Show key headers only | View raw

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.

Back to comp.compilers | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

IR Representation César <divcesar@gmail.com> - 2015-09-04 14:39 -0300
  Re: IR Representation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-05 16:51 +0000
    Re: IR Representation César <divcesar@gmail.com> - 2015-09-07 23:05 -0300
      Re: IR Representation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-09-08 07:49 +0000
        Re: IR Representation César <divcesar@gmail.com> - 2015-09-11 17:01 -0300
          Re: IR Representation Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2015-09-12 19:45 +0200
  Re: IR Representation George Neuner <gneuner2@comcast.net> - 2015-09-08 18:45 -0400

csiph-web