Re: Books on compiler backends?

Kaleb Pederson <>
Mon, 11 Feb 2008 13:03:48 -0800 (PST)

          From comp.compilers

Related articles
Books on compiler backends? (Kaleb Pederson) (2008-02-05)
Re: Books on compiler backends? (Jyrki Saarinen) (2008-02-09)
Re: Books on compiler backends? (Kaleb Pederson) (2008-02-11)
| List of all articles for this month |

From: Kaleb Pederson <>
Newsgroups: comp.compilers
Date: Mon, 11 Feb 2008 13:03:48 -0800 (PST)
Organization: Compilers Central
References: 08-02-025 08-02-033
Keywords: books, code
Posted-Date: 12 Feb 2008 20:05:20 EST

On Feb 9, 3:06 am, Jyrki Saarinen <>
> Take a look at the SableCC. It produces standard Visitor design pattern code
> after you have described the structure of your AST (it does it even without,
> but that's not likely to be very useful).

The visitor design pattern is great and I understand it well, but it
doesn't solve the problem that I was alluding to (perhaps too weakly).
The problem is that checking each node to see if it matches one of the
many patterns that need to be replaced is extremely inefficient, and
that's about where my knowledge breaks down.

Based on my understanding, I want to find an optimal or optimum
solution, possibly using a maximal much algorithm, but there's a few
things that I'm unsure of. At this point, I'm not really doing
instruction selection, but I do have a number of subtree patterns that
I want replaced with optimized versions. If possible and optimal, I
would like to use an algorithm that will do this for me, so I need not
create a visitor that needs N passes through my AST to discover, and
possibly replace, N different types of subtrees.

Can I use the standard maximal munch algorithm, with the replacement
for all nodes being the node itself at cost X and then, for all
replacement subtrees, indicate that the replacement subtree has cost X
- y (eg. some lower cost so it will always be preferred to the non-
replacement)? What other algorithms, if any, should I look at?



Post a followup to this message

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