IR transforms for side-effect elimination

Martin Ellis <>
21 Oct 2004 22:22:22 -0400

          From comp.compilers

Related articles
IR transforms for side-effect elimination (Martin Ellis) (2004-10-21)
| List of all articles for this month |

From: Martin Ellis <>
Newsgroups: comp.compilers
Date: 21 Oct 2004 22:22:22 -0400
Organization: University of Newcastle upon Tyne
Keywords: optimize, question
Posted-Date: 21 Oct 2004 22:22:22 EDT

Hi all,

I'm looking for papers/books about transforms that eliminate
side-effects from an IR fragment for finding ILP, particularly ones
that consider their correctness using formal techniques.

I'd also appreciate comments on how various transformation can be
combined and any pointers to other useful literature...

The most appropriate reference I've found so far is Appel's Modern
Compiler Implementation in ML, which describes a transformation on
IR-trees that moves all the constructs with state and control
side-effects to the top of each tree.

The ML implementation given as 5 mutually recursive functions, and I
have been thinking about how one might prove its correctness (preserve
semantics and lift side-effects). Anyone know of similar/
simpler/alternative presentations of this idea?

The Dragon book describes the construction of a DAG but from a tuple
representation. I'm interested in combinations of this technique with
that described in Appel:

1) Not combine them at all, just use the tuple->DAG method for CSE,
finding parallelism, and rearranging for better register use. Then
DAG->ISA instructions.

2) IR-trees->IR-tuples (as in Appel, but generating IR rather than for
an ISA), then IR-tuples->DAG (as Dragon book), then generate code for
a specific architecture: DAG->ISA instructions.

3) IR-trees->DAG->ISA instructions. This is probably what I want,
as it skips conversion to and from tuples as in (2) but I don't think
I've seen any presentation of Trees->DAG anywhere - anyone?
(DAG->ISA is in the 'Crafting a Compiler' books).

I'm not fond of (1) because generating tuples from an AST doesn't
seem very natural to me - but does (2) sound a bit heavy handed?
Am I likely to run into problems translating IR-trees to DAGs in (3)?

Thanks for all comments and suggestions,

Post a followup to this message

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